aboutsummaryrefslogtreecommitdiff
path: root/doc/paper
diff options
context:
space:
mode:
Diffstat (limited to 'doc/paper')
-rw-r--r--doc/paper/postquantum_melt.tex116
1 files changed, 81 insertions, 35 deletions
diff --git a/doc/paper/postquantum_melt.tex b/doc/paper/postquantum_melt.tex
index 455f03d15..6167b570a 100644
--- a/doc/paper/postquantum_melt.tex
+++ b/doc/paper/postquantum_melt.tex
@@ -351,6 +351,8 @@ security requirements in this case, impacting our algorithm choices.
\section{Post-quantum key exchanges}
+% \subsection{Isogenies between super-singular elliptic curves}
+
In \cite{SIDH?,SIDH16}, there is a Diffie-Helman like key exchange
(SIDH) based on computing super-singular eliptic curve isogenies
which functions as a drop in replacement, or more likely addition,
@@ -360,7 +362,7 @@ In SIDH, private keys are the kernel of an isogeny in the 2-torsion
or the 3-torsion of the base curve. Isogenies based on 2-torsion can
only be paired with isogenies based on 3-torsion, and visa versa.
This rigidity makes constructing signature schemes with SIDH hard
-\cite{}, but does not impact our use case.
+\cite{??SIDHsig??}, but does not impact our use case.
We let $\mu$ and $\Mu$ be the SIDH 2-torsion private and public keys,
repectively. We simlarly let $\lambda$ and $\Lambda$ be the
@@ -373,47 +375,85 @@ Our 2-torsion and 3-torsion public key derivation functions
$\CPK(\mu)$ and $\LPK(\lambda)$ along with our two key derivation
functions $\KEX_2$ and $\KEX_3$, all work as described in
\cite[\S6]{SIDH16}.
+% We refer to \cite[??]{SIDH?15?} and \cite[]{SIDH?11?} for further background.
-% We refer to \cite[\S6]{SIDH16}, \cite[??]{SIDH?15?}, and
-% \cite[]{SIDH?11?} for further discussion of the implementation.
+If using SIDH, then we naturally depend upon the security assumption
+used in SIDH, but combining this with ECDH is stronger than either
+alone.
-There is no relationship between $\mu$ and $\lambda$ in SIDH, so
-$\Lambda$ cannot itself leak any information about $C$.
+... proof ...
-\smallskip
+At least, there is no relationship between $\mu$ and $\lambda$ in
+SIDH though, so $\Lambda$ cannot itself leak any information about
+$(C,\Mu,S)$.
+
+% \smallskip
-Ring-LWE based key exchanges like \cite{Peikert14,NewHope} require
-that both Alice and Bob's keys be ephemeral because the success or
-failure of the key exchange leaks one bit about both keys\cite{}.
-As a result, authentication with Ring-LWE based schemes remains
-harder than with discrete log schemes\cite{}.
-
-We observe however that the Taler wallet controls both sides during
-the refresh protocol, so the wallet can ensure that the key exchange
-always succeeds. In fact, the Ring-LWE paramaters could be tunned to
-leave the probability of failure rather high, saving the exchange
-bandwidth, storage, and verification time.
-
-We let $\mu$ and $\Mu$ be Alice (initator) side the private and public
-keys, repectively. We simlarly let $\lambda_j$ and $\Lambda_j$ be the
-Bob (respondent) private and public keys.
-% DO IT :
+We note that $\Lambda$ contains two points used by $\KEX_3$ to
+evaluate its secret isogeny but not used by $\KEX_2$. We do not
+consider this a weakness for taxability because the cut and choose
+protocol already requires that the exchange verify the public
+key $\Lambda_j$ for $j \neq \gamma$.
+
+\smallskip
+% \subsection{Ring Learning with Errors}
+
+In \cite{Peikert14,NewHope}, there is another key exchange based on
+a variant of the Ring-LWE problem. Ring-LWE key exchange has a
+worrying relationship with this hidden subgroup problem on dihedral
+groups \cite{??,??}, but also a reasuring relationship with NP-hard
+problems.
+
+We again let $\mu$ and $\Mu$ denote the Alice (initator) side the
+private and public keys, repectively. We likewise let $\lambda$
+and $\Lambda$ be the Bob (respondent) private and public keys.
+% DO IT?
Again now, $\CPK$, $\CSK$, $\LPK$, $\LSK$, $\KEX_2$ and $\KEX_3$
can be defined from \cite{Peikert14,NewHope}.
-\smallskip
+A priori, one worried that unlinkability might fail even without
+the Ring-LWE key exchange itself being broken because $\lambda_j$
+and $\Lambda_j$ are constructed using the public key $\Mu$.
+
+First, the polynomial $a$ commonly depends upon $\Mu$, like in
+\cite{NewHope}, so unlinkability explicity depends upon the Ring-LWE
+problem\cite{}. [[ PROOF ??? ]]
+
+Second, the reconciliation information in $\Lambda$ might leak
+additional information about $\lambda$.
+[[ LITTERATURE ADDRESSES THIS POINT ??? ]]
+
+Ring-LWE key exchanges require that both Alice and Bob's keys be
+ephemeral because the success or failure of the key exchange
+leaks one bit about both keys\cite{}. As a result, authentication
+with Ring-LWE based schemes remains harder than with discrete log
+schemes\cite{??RLWEsig??}, and this situation impacts us as well.
+
+A Taler wallet should control both sides during the refresh protocol,
+ which produces an interesting connundrum.
+An honest wallet could ensure that the key exchange always succeeds.
+If wallets were honest, then one could tune the Ring-LWE paramaters
+to leave the probability of failure rather high,
+ saving the exchange bandwidth, storage, and verification time.
+A dishonest wallet and merchant could conversely search the key space
+to find an exchange that fails, meaning the wallet could aid the
+merchant in tax evasion.
+
+[[ IS THE FOLLOWING IMPOSSIBLE ??? ]]
+
+If possible, we should tune the Ring-LWE paramaters to reduce costs
+to the exchange, and boost the unlinkability for the users, while
+simultaniously
+
+% \smallskip
+% \subsection{Comparson}
At present, the SIDH implemention in \cite{SIDH16} requires about
one third the key material and 100?? times as much CPU time as the
Ring-LWE implemention in \cite{NewHope}.
-As noted above, Ring-LWE admits significant optimizations for the
-Taler refresh situation.
-
-We observe however that the Ring-LWE public key $\Lambda$ has a risk
-of leaking information about $\Mu$. In particular, if polynomial $a$
-depends upon $\Mu$, like in \cite{NewHope}, then anonymity explicity
-depends upon the Ring-LWE problem\cite{}.
-...
+[[ We believe this provides a strong reason to continue exploring
+paramater choices for Ring-LWE key exchange along with protocol tweaks.
+... ]]
\section{Hashed-based one-sided public keys}
@@ -493,14 +533,16 @@ In this scenarion, we refresh from a pseudo-coin $(C,\Mu)$ where
As a result, our hash-based scheme should increase the security
paramater $\delta$ to allow a query for every withdrawal operation.
-Instead, we propose using a Merkle tree of Alice side Ring-LWE keys,
-while continuing to invent the Bob side Ring-LWE key.
+Instead, ...
+[[ ??? we propose using a Merkle tree of Alice side Ring-LWE keys,
+while continuing to invent the Bob side Ring-LWE key. ??? ]]
-...
-% Use birthday about on Alice vs Bob keys
+% Use birthday about on Alice vs Bob keys?
\section{Conclusions}
+...
+
\bibliographystyle{alpha}
\bibliography{taler,rfc}
@@ -519,6 +561,10 @@ while continuing to invent the Bob side Ring-LWE key.
\item
\end{itemize}
+\begin{itemize}
+\item
+\item
+\end{itemize}