From 4141467d47a276365cbb9629b66c84b2c4e74dd4 Mon Sep 17 00:00:00 2001 From: Jeff Burdges Date: Tue, 3 May 2016 14:49:07 +0200 Subject: rename PQ paper file --- doc/paper/postquantum.tex | 581 +++++++++++++++++++++++++++++++++++++++++ doc/paper/postquantum_melt.tex | 581 ----------------------------------------- 2 files changed, 581 insertions(+), 581 deletions(-) create mode 100644 doc/paper/postquantum.tex delete mode 100644 doc/paper/postquantum_melt.tex (limited to 'doc') diff --git a/doc/paper/postquantum.tex b/doc/paper/postquantum.tex new file mode 100644 index 000000000..6167b570a --- /dev/null +++ b/doc/paper/postquantum.tex @@ -0,0 +1,581 @@ +\documentclass{llncs} +%\usepackage[margin=1in,a4paper]{geometry} +\usepackage[T1]{fontenc} +\usepackage{palatino} +\usepackage{xspace} +\usepackage{microtype} +\usepackage{tikz,eurosym} +\usepackage{amsmath,amssymb} +\usepackage{enumitem} +\usetikzlibrary{shapes,arrows} +\usetikzlibrary{positioning} +\usetikzlibrary{calc} + +% Relate to: +% http://fc14.ifca.ai/papers/fc14_submission_124.pdf + +% Terminology: +% - SEPA-transfer -- avoid 'SEPA transaction' as we use +% 'transaction' already when we talk about taxable +% transfers of Taler coins and database 'transactions'. +% - wallet = coins at customer +% - reserve = currency entrusted to exchange waiting for withdrawal +% - deposit = SEPA to exchange +% - withdrawal = exchange to customer +% - spending = customer to merchant +% - redeeming = merchant to exchange (and then exchange SEPA to merchant) +% - refreshing = customer-exchange-customer +% - dirty coin = coin with exposed public key +% - fresh coin = coin that was refreshed or is new +% - coin signing key = exchange's online key used to (blindly) sign coin +% - message signing key = exchange's online key to sign exchange messages +% - exchange master key = exchange's key used to sign other exchange keys +% - owner = entity that knows coin private key +% - transaction = coin ownership transfer that should be taxed +% - sharing = coin copying that should not be taxed + + +\title{Post-quantum anonymity in Taler} + +\begin{document} +\mainmatter + +\author{Jeffrey Burdges} +\institute{Intria / GNUnet / Taler} + + +\maketitle + +\begin{abstract} +David Chaum's original RSA blind sgnatures provide information theoretic +anonymity for customers' purchases. In practice, there are many schemes +that weaken this to provide properties. We describe a refresh protocol +for Taler that provides customers with post-quantum anonymity. +It replaces an elliptic curve Diffe-Hellman operation with a unique +hash-based encryption scheme for the proof-of-trust via key knoledge +property that Taler requires to distinguish untaxable operations from +taxable purchases. +\end{abstract} + + +\section{Introduction} + +David Chaum's RSA blind sgnatures \cite{} can provide financial +security for the exchange, or traditionally mint, + assuming RSA-CTI \cite{,}. + +A typical exchange deployment must record all spent coins to prevent +double spending. It would therefore rotate ``denomination'' signing +keys every few weeks or months to keep this database from expanding +indefinitely \cite{Taler??}. As a consequence, our exchange has +ample time to respond to advances in cryptgraphy by increasing their +key sizes, updating wallet software with new algorithms, or +even shutting down. + +In particular, there is no chance that quantum computers will emerge +and become inexpensive within the lifetime of a demonination key. +Indeed, even a quantum computer that existed only in secret posses +little threat because the risk of exposing that secret probably exceeds +the exchange's value. + +\smallskip + +We cannot make the same bold pronouncement for the customers' anonymity +however. We must additionally ask if customers' transactions can be +deanonymized in the future by the nvention of quantum computes, or +mathematical advances. + +David Chaum's original RSA blind sgnatures provide even information +theoretic anonymity for customers, giving the desired negative answer. +There are however many related schemes that add desirable properties +at the expense of customers' anonymity. In particular, any scheme +that supports offline merchants must add a deanonymization attack +when coins are double spent \cite{B??}. + +Importantly, there are reasons why exchanges must replace coins that +do not involve actual financial transactons, like to reissue a coin +before the exchange rotates the denomination key that signed it, or +protect users' anonymity after a merchant recieves a coin, but fails +to process it or deliver good. + +In Taler, coins can be partially spent by signing with the coin's key +for only a portion of the value determined by the coin's denomination +key. This allows precise payments but taints the coin with a +transaction, which frequently entail user data like a shipng address. +To correct this, a customer does a second transaction with the exchange +where they sign over the partially spent coin's risidual balance +in exchange for new freshly anonymized coins. +Taler employs this {\em refresh} or {\em melt protocol} for +both for coins tainted through partial spending or merchant failures, +as well as for coin replacement due to denomination key roration. + +If this protocol were simply a second transaction, then customers +would retain information theoreticaly secure anonymity. +In Taler however, we require that the exchange learns acurate income +information for merchants. If we use a regular transaction, then +a customer could conspire to help the merchant hide their income +\cite[]{Taler??}. +To prevent this, the refresh protocol requires that a customer prove +that they could learn the private key of the resulting new coins. + +At this point, Taler employs an elliptic curve Diffie-Hellman key +exchange between the coin's signing key and a new linking key +\cite[??]{Taler??}. As the public linking key is exposed, +an adversary with a quantum computer could trace any coins involved +in either partial spending operations or aborted transactions. +A refresh prompted by denomination key rotation incurs no anonymity +risks regardless. + +\smallskip + +We propose two variations on Taler's refresh protocol that offer +resistane to a quantum adversary. + +First, we describe attaching contemporary post-quantum key exchanges, +based on either super-singular eliptic curve isogenies \cite{SIDH} or +ring learning with errors (Ring-LWE) \cite{Peikert14,NewHope}. +These provide strong post-quantum security so long as the underlying +scheme remains secure; however, these schemes youth leaves them +relatively untested. + +Second, we propose a hash based scheme whose anonymity garentee needs +only the one-way assumption on our hash function. In this scheme, +the vible security paramater is numerically far smaller than in the +key exchange systems, but covers query complexity which we believe +suffices. + +We describe this hash based proof-of-encryption-to-self scheme in +parallel with the +As is the practice with hash based signature schemes + + + + +In this paper, we describe a post-quantum + +It replaces an elliptic curve Diffe-Hellman operation with a unique +hash-based encryption scheme for the proof-of-trust via key knoledge +property that Taler requires to distinguish untaxable operations from +taxable purchases. + +... + +\smallskip + +We observe that several elliptic curve blind signature schemes provide +information theoreticly secure blinding as well, but + Schnorr sgnatures require an extra round trip \cite{??}, and + pairing based schemes offer no advnatages over RSA \cite{??}. + +There are several schemes like Anonize \cite{} in Brave \cite{}, +or Zcash \cite{} used in similar situations to blind signatures. +% https://github.com/brave/ledger/blob/master/documentation/Ledger-Principles.md +In these systems, anonymity is not post-quantum due to the zero-knowledge +proofs they employ. + + +\section{Taler's refresh protocol} + +\def\Mu{M} +\def\Eta{} +\def\newmathrm#1{\expandafter\newcommand\csname #1\endcsname{\mathrm{#1}}} +\newmathrm{CPK} +\newmathrm{CSK} +\newmathrm{LPK} +\newmathrm{LSK} +\newmathrm{KEX} + + +We shall describe Taler's refresh protocol in this section. +All notation defined here persists throughout the remainder of + the article. + +We let $\kappa$ denote the exchange's taxation security parameter, +meaning the highest marginal tax rate is $1/\kappa$. Also, let +$\theta$ denote the maximum number of coins returned by a refresh. + +\smallskip + +We label place holders $\eta$, $\lambda$, $\Lambda$, $\mu$, and $\Mu$ +for key material involved in post-quantum operations. +We view $\Lambda$ and $\Mu$ as public keys with respective + private keys $\lambda$ and $\mu$, and +$\eta$ as the symetric key resulting from the key exchange between them. + +We need effeciently computable functions + $\CPK$, $\CSK$, $\LPK$, $\LSK$, $\KEX_2$ and $\KEX_3$ such that +\begin{itemize} +\item $\mu = \CSK(s)$ for a random bitstring $s$, + $\Mu = \CPK(\mu)$, +\item $\lambda = \LSK(t,\mu)$ for a bitstring $t$, + $\Lambda = \LPK(\lambda)$, and +\item $\eta = \KEX_2(\lambda,\Mu) = \KEX_3(\Lambda,\mu)$. +\end{itemize} +In particular, if $\KEX_3(\Lambda,\mu)$ would fail + then $\KEX_2(\lambda,\Mu)$ must fail too. + +% Talk about assumption that if KEX_2 works then KEX_3 works? +If these are all read as empty, then our description below reduces +to Taler's existing refresh protocol. + +\smallskip + +A coin $(C,\Mu,S)$ consists of + a Ed25519 public key $C = c G$, + a post-quantum public key $\Mu$, and + an RSA-FDH signature $S = S_d(C || \Mu)$ by a denomination key $d$. +A coin is spent by signing a contract with $C$. The contract must +specify the recipiant merchant and what portion of the value denoted +by the denomination $d$ they recieve. +If $\Mu$ is large, we may replace it by $H(C || \Mu)$ to make signing +contracts more efficent. + +There was of course a blinding factor $b$ used in the creation of +the coin's signature $S$. In addition, there was a private seed $s$ +used to generate $c$, $b$, and $\mu$, but we need not retain $s$ +outside the refresh protocol. +$$ c = H(\textrm{"Ed25519"} || s) +\qquad \mu = \CSK(s) +\qquad b = H(\textrm{"Blind"} || s) $$ + +\smallskip + +We begin refresh with a possibly tainted coin $(C,\Mu,S)$ that +we wish to refresh into $n \le \theta$ untainted coins. + +In the change sitaution, our coin $(C,\Mu,S)$ was partially spent and +retains only a part of the value determined by the denominaton $d$. +There is usually no denomination that matchets this risidual value +so we must refresh from one coin into $n \le \theta$. + +For $x$ amongst the symbols $c$, $C$, $\mu$, $\Mu$, $b$, and $s$, +we let $x_{j,i}$ denote the value normally denoted $x$ of + the $j$th cut of the $i$th new coin being created. +% So $C_{j,i} = c_{j,i} G$, $\Mu_{j,i}$, $m_{j,i}$, and $b^{j,i}$ +% must be derived from $s^{j,i}$ as above. +We need only consider one such new coin at a time usually, +so let $x'$ denote $x_{j,i}$ when $i$ and $j$ are clear from context. +In other words, $c'$, $\mu'$, and $b_j$ are derived from $s_j$, + and both $C' = c' G$ and $\Mu' = \CSK(s')$. + +\paragraph{Wallet phase 1.} +\begin{itemize} +\item For $j=1 \cdots \kappa$: + \begin{itemize} + \item Create random $\zeta_j$ and $l_j$. + \item Also compute $L_j = l_j G$. + \item Generate $\lambda_j = \LSK((j,i),\mu)$, + $\Lambda_j = \LPK(\lambda_j)$, and + $\eta_j = \KEX_2(\lambda_j,\Mu)$. + \item Set the linking commitment $\Gamma_{j,0} = (L_j,E_{l_j C}(\Lambda_j))$. + \item Set $k_j = H(l_j C || \eta_j)$. +\smallskip + \item For $i=1 \cdots n$: + \begin{itemize} + \item Set $s' = H(\zeta_j || i)$. + \item Derive $c'$, $m'$, and $b'$ from $s'$ as above. + \item Compute $C' = c' G$ and $\Mu' = \CPK(m')$ too. + \item Compute $B_{j,i} = B_{b'}(C' || \Mu')$. + \item Encrypt $\Gamma'_{j,i} = E_{k_j}(s')$. + \item Set the coin commitments $\Gamma_{j,i} = (\Gamma'_{j,i},B_{j,i})$ +\end{itemize} +\smallskip +\end{itemize} +\item Send $(C,\Mu,S)$ and the signed commitments + $\Gamma_* = S_C( \Gamma_{j,i} \quad\textrm{for}\quad j=1\cdots\kappa, i=0 \cdots n )$. +\end{itemize} + +\paragraph{Exchange phase 1.} +\begin{itemize} +\item Verify the signature $S$ by $d$ on $(C || \Mu)$. +\item Verify the signatures by $C$ on the $\Gamma_{j,i}$ in $\Gamma_*$. +\item Pick random $\gamma \in \{1 \cdots \kappa\}$. +\item Mark $C$ as spent by saving $(C,\gamma,\Gamma_*)$. +\item Send $\gamma$ as $S(C,\gamma)$. +\end{itemize} + +\paragraph{Wallet phase 2.} +\begin{itemize} +\item Save $S(C,\gamma)$. +\item For $j = 1 \cdots \kappa$ except $\gamma$: + \begin{itemize} + \item Create a proof $\lambda_j^{\textrm{proof}}$ that + $\lambda_j$ is compatable with $\Lambda_j$ and $\Mu$. + \item Set a responce tuple + $R_j = (\zeta_j,l_j,\lambda_j,\lambda_j^{\textrm{proof}})$. + \end{itemize} +\item Send $S_C(R_j \quad\textrm{for}\quad j \ne \gamma )$. +\end{itemize} + +\paragraph{Exchange phase 2.} +\begin{itemize} +\item Verify the signature by $C$. +\item For $j = 1 \cdots \kappa$ except $\gamma$: + \begin{itemize} + \item Compute $\eta_j = \KEX_2(\lambda_j,\Mu)$. + \item Verify that $\Lambda_j = \LPK(\lambda_j)$ + \item Set $k_j = H(l_j C || \eta_j)$. + \item For $i=1 \cdots n$: + \begin{itemize} + \item Decrypt $s' = D_{k_j}(\Gamma'_{j,i})$. + \item Compute $c'$, $m'$, and $b'$ from $s_j$. + \item Compute $C' = c' G$ too. + \item Verify $B' = B_{b'}(C' || \Mu')$. + \end{itemize} + \end{itemize} +\item If verifications all pass then send $S_{d_i}(B_\gamma)$. +\end{itemize} + +We could optionally save long-term storage space by +replacing $\Gamma_*$ with both $\Gamma_{\gamma,0}$ and + $S_C(\Eta_{j,i} \quad\textrm{for}\quad j \ne \gamma )$. +It's clear this requires the wallet send that signature in some phase, +but also the wallet must accept a phase 2 responce to a phase 1 request. + +\smallskip + +There is good reason to fear tax evasion committed during the +initial withdrawal of a coin as well. A merchant simply provides +the customer with a blinded but unpurchased coin and asks them to +pay to withdraw it. + +\subsection{Withdrawal}\label{subsec:withdrawal} + +In Taler, we may address tax fraud on initial withdrawal by turning +withdrawal into a refresh from a pseudo-coin $(C,\Mu)$ in which + $C$ is the user's reserve key \cite[??]{Taler} and + $\Mu$ s a post-quantum public key kept with $C$. +We see below however that our public key algorithm has very different +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, +for Taler's refresh protocol. + +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{??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 +SIDH 3-torsion private and public keys. + +We envision the 2-torsion secret key generation function $\CSK(s)$ +for $\mu$ being deterministic with seed $s$, but the 3-torsion secret +key generation function $\LSK()$ ignores the arguments given above +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. + +If using SIDH, then we naturally depend upon the security assumption +used in SIDH, but combining this with ECDH is stronger than either +alone. + +... proof ... + +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 + +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}. + +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}. +[[ 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} + +We now define our hash-based encryption scheme. +Let $\delta$ denote our query security paramater and + let $\mu$ be a bit string. +For $j \le \kappa$, we define a Merkle tree $T_j$ of height $\delta$ +with leaves $\eta_j = H(\mu || "YeyCoins!" || t || j)$ + for some leaf index $t \le 2^\delta$. +Let $t_j$ denote the root of $T_j$. +Set $\Mu = H(t_1 || \cdots || t_\kappa)$, + which defines $\CPK(\mu)$. + +Now let $\lambda_j = \LSK((t,j),\mu)$ consist of +$(t,j,\eta_j)$ along with both + the Merkle tree path that proves $\eta_j$ is a leaf of $T_j$, +and $(t_1,\ldots,t_\kappa)$, + making $\LSK$ an embelished Merkle tree path function. +Also let $\Lambda_j = \LPK(\lambda_j)$ be $(t,j)$ + +We define $\KEX_2(\lambda_j,\Mu)$ to be $\eta_j$ + if $\lambda_j$ proves that $\eta_j$ is the $t$ leaf for $\Mu$, +or empty otherwise. +$\KEX_3(\Lambda_j,\mu)$ simply recomputes $\eta_j$ as above. +If $\KEX_2$ works then so does $\KEX_3$. + +As $\Lambda_j = (t,j)$, it matters that $\lambda_j$ actually +demonstrates the position $t$ in the Merkle tree. + +... proofs ... + +\smallskip + +We observe that $\CPK$ has running time $O(2^\delta)$, severely +limiting $\delta$. We lack the time-space trade offs resolve +this issue for hash-based signature (see \cite{SPHINCS}). + +Imagine that $\delta = 0$ so that $T_j = H(\eta_j)$. +In this scenario, a hostile exchange could request two different +$\gamma$ to learn all $\eta_j$, if the wallet reruns its second +phase. In principle, the wallet saves the exchange's signed +choice of $\gamma$ before revealing $\eta_j$ for $j \neq \gamma$. +It follows that even $\delta = 0$ does technically provides +post-quantum anonymity, + +We must worry about attacks that rewind the wallet from phase 2 to +phase 1, or even parallelism bugs where the wallet answer concurrent +requests. We cannot remove the curve25519 exchange $l_j C$ from the +refresh protocol becausenn such attacks would represent serious risks +without it. With our $l_j C$ component, there is little reason for +an attacker to pursue $\eta_j$ alone unless they expect to break +curve25519 in the future, either through mathematical advances or +by building a quantum computer. + +We therefore view $\delta$ as a query complexity paramater whose +optimial setting depends upo nthe strength of the overall protocoll. + +\smallskip + +We can magnify the effective $\delta$ by using multiple $\eta_j$. + +... analysis ... +% multiple withdrawals + +We believe this provides sufficent post-quantum security for +refreshing change. + + +\section{Hash and Ring-LWE hybrid} + +We noted in \S\ref{subsec:withdrawal} above that exchange might +require that initial withdrawals employs a refresh-like operation. +In this scenarion, we refresh from a pseudo-coin $(C,\Mu)$ where + $C$ is the user's reserve key \cite[??]{Taler} and + $\Mu$ s a post-quantum public key kept with $C$. +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. ??? ]] + +% Use birthday about on Alice vs Bob keys? + +\section{Conclusions} + +... + + +\bibliographystyle{alpha} +\bibliography{taler,rfc} + +% \newpage +% \appendix + +% \section{} + + + +\end{document} + +\begin{itemize} +\item +\item +\end{itemize} + +\begin{itemize} +\item +\item +\end{itemize} + + + + + +Crazy pants ideas : + +Use a larger Mrkle tree with start points seeded throughout + +Use a Merkle tree of SWIFFT hash functions becuase + their additive homomorphic property lets you keep the form of a polynomial + + + diff --git a/doc/paper/postquantum_melt.tex b/doc/paper/postquantum_melt.tex deleted file mode 100644 index 6167b570a..000000000 --- a/doc/paper/postquantum_melt.tex +++ /dev/null @@ -1,581 +0,0 @@ -\documentclass{llncs} -%\usepackage[margin=1in,a4paper]{geometry} -\usepackage[T1]{fontenc} -\usepackage{palatino} -\usepackage{xspace} -\usepackage{microtype} -\usepackage{tikz,eurosym} -\usepackage{amsmath,amssymb} -\usepackage{enumitem} -\usetikzlibrary{shapes,arrows} -\usetikzlibrary{positioning} -\usetikzlibrary{calc} - -% Relate to: -% http://fc14.ifca.ai/papers/fc14_submission_124.pdf - -% Terminology: -% - SEPA-transfer -- avoid 'SEPA transaction' as we use -% 'transaction' already when we talk about taxable -% transfers of Taler coins and database 'transactions'. -% - wallet = coins at customer -% - reserve = currency entrusted to exchange waiting for withdrawal -% - deposit = SEPA to exchange -% - withdrawal = exchange to customer -% - spending = customer to merchant -% - redeeming = merchant to exchange (and then exchange SEPA to merchant) -% - refreshing = customer-exchange-customer -% - dirty coin = coin with exposed public key -% - fresh coin = coin that was refreshed or is new -% - coin signing key = exchange's online key used to (blindly) sign coin -% - message signing key = exchange's online key to sign exchange messages -% - exchange master key = exchange's key used to sign other exchange keys -% - owner = entity that knows coin private key -% - transaction = coin ownership transfer that should be taxed -% - sharing = coin copying that should not be taxed - - -\title{Post-quantum anonymity in Taler} - -\begin{document} -\mainmatter - -\author{Jeffrey Burdges} -\institute{Intria / GNUnet / Taler} - - -\maketitle - -\begin{abstract} -David Chaum's original RSA blind sgnatures provide information theoretic -anonymity for customers' purchases. In practice, there are many schemes -that weaken this to provide properties. We describe a refresh protocol -for Taler that provides customers with post-quantum anonymity. -It replaces an elliptic curve Diffe-Hellman operation with a unique -hash-based encryption scheme for the proof-of-trust via key knoledge -property that Taler requires to distinguish untaxable operations from -taxable purchases. -\end{abstract} - - -\section{Introduction} - -David Chaum's RSA blind sgnatures \cite{} can provide financial -security for the exchange, or traditionally mint, - assuming RSA-CTI \cite{,}. - -A typical exchange deployment must record all spent coins to prevent -double spending. It would therefore rotate ``denomination'' signing -keys every few weeks or months to keep this database from expanding -indefinitely \cite{Taler??}. As a consequence, our exchange has -ample time to respond to advances in cryptgraphy by increasing their -key sizes, updating wallet software with new algorithms, or -even shutting down. - -In particular, there is no chance that quantum computers will emerge -and become inexpensive within the lifetime of a demonination key. -Indeed, even a quantum computer that existed only in secret posses -little threat because the risk of exposing that secret probably exceeds -the exchange's value. - -\smallskip - -We cannot make the same bold pronouncement for the customers' anonymity -however. We must additionally ask if customers' transactions can be -deanonymized in the future by the nvention of quantum computes, or -mathematical advances. - -David Chaum's original RSA blind sgnatures provide even information -theoretic anonymity for customers, giving the desired negative answer. -There are however many related schemes that add desirable properties -at the expense of customers' anonymity. In particular, any scheme -that supports offline merchants must add a deanonymization attack -when coins are double spent \cite{B??}. - -Importantly, there are reasons why exchanges must replace coins that -do not involve actual financial transactons, like to reissue a coin -before the exchange rotates the denomination key that signed it, or -protect users' anonymity after a merchant recieves a coin, but fails -to process it or deliver good. - -In Taler, coins can be partially spent by signing with the coin's key -for only a portion of the value determined by the coin's denomination -key. This allows precise payments but taints the coin with a -transaction, which frequently entail user data like a shipng address. -To correct this, a customer does a second transaction with the exchange -where they sign over the partially spent coin's risidual balance -in exchange for new freshly anonymized coins. -Taler employs this {\em refresh} or {\em melt protocol} for -both for coins tainted through partial spending or merchant failures, -as well as for coin replacement due to denomination key roration. - -If this protocol were simply a second transaction, then customers -would retain information theoreticaly secure anonymity. -In Taler however, we require that the exchange learns acurate income -information for merchants. If we use a regular transaction, then -a customer could conspire to help the merchant hide their income -\cite[]{Taler??}. -To prevent this, the refresh protocol requires that a customer prove -that they could learn the private key of the resulting new coins. - -At this point, Taler employs an elliptic curve Diffie-Hellman key -exchange between the coin's signing key and a new linking key -\cite[??]{Taler??}. As the public linking key is exposed, -an adversary with a quantum computer could trace any coins involved -in either partial spending operations or aborted transactions. -A refresh prompted by denomination key rotation incurs no anonymity -risks regardless. - -\smallskip - -We propose two variations on Taler's refresh protocol that offer -resistane to a quantum adversary. - -First, we describe attaching contemporary post-quantum key exchanges, -based on either super-singular eliptic curve isogenies \cite{SIDH} or -ring learning with errors (Ring-LWE) \cite{Peikert14,NewHope}. -These provide strong post-quantum security so long as the underlying -scheme remains secure; however, these schemes youth leaves them -relatively untested. - -Second, we propose a hash based scheme whose anonymity garentee needs -only the one-way assumption on our hash function. In this scheme, -the vible security paramater is numerically far smaller than in the -key exchange systems, but covers query complexity which we believe -suffices. - -We describe this hash based proof-of-encryption-to-self scheme in -parallel with the -As is the practice with hash based signature schemes - - - - -In this paper, we describe a post-quantum - -It replaces an elliptic curve Diffe-Hellman operation with a unique -hash-based encryption scheme for the proof-of-trust via key knoledge -property that Taler requires to distinguish untaxable operations from -taxable purchases. - -... - -\smallskip - -We observe that several elliptic curve blind signature schemes provide -information theoreticly secure blinding as well, but - Schnorr sgnatures require an extra round trip \cite{??}, and - pairing based schemes offer no advnatages over RSA \cite{??}. - -There are several schemes like Anonize \cite{} in Brave \cite{}, -or Zcash \cite{} used in similar situations to blind signatures. -% https://github.com/brave/ledger/blob/master/documentation/Ledger-Principles.md -In these systems, anonymity is not post-quantum due to the zero-knowledge -proofs they employ. - - -\section{Taler's refresh protocol} - -\def\Mu{M} -\def\Eta{} -\def\newmathrm#1{\expandafter\newcommand\csname #1\endcsname{\mathrm{#1}}} -\newmathrm{CPK} -\newmathrm{CSK} -\newmathrm{LPK} -\newmathrm{LSK} -\newmathrm{KEX} - - -We shall describe Taler's refresh protocol in this section. -All notation defined here persists throughout the remainder of - the article. - -We let $\kappa$ denote the exchange's taxation security parameter, -meaning the highest marginal tax rate is $1/\kappa$. Also, let -$\theta$ denote the maximum number of coins returned by a refresh. - -\smallskip - -We label place holders $\eta$, $\lambda$, $\Lambda$, $\mu$, and $\Mu$ -for key material involved in post-quantum operations. -We view $\Lambda$ and $\Mu$ as public keys with respective - private keys $\lambda$ and $\mu$, and -$\eta$ as the symetric key resulting from the key exchange between them. - -We need effeciently computable functions - $\CPK$, $\CSK$, $\LPK$, $\LSK$, $\KEX_2$ and $\KEX_3$ such that -\begin{itemize} -\item $\mu = \CSK(s)$ for a random bitstring $s$, - $\Mu = \CPK(\mu)$, -\item $\lambda = \LSK(t,\mu)$ for a bitstring $t$, - $\Lambda = \LPK(\lambda)$, and -\item $\eta = \KEX_2(\lambda,\Mu) = \KEX_3(\Lambda,\mu)$. -\end{itemize} -In particular, if $\KEX_3(\Lambda,\mu)$ would fail - then $\KEX_2(\lambda,\Mu)$ must fail too. - -% Talk about assumption that if KEX_2 works then KEX_3 works? -If these are all read as empty, then our description below reduces -to Taler's existing refresh protocol. - -\smallskip - -A coin $(C,\Mu,S)$ consists of - a Ed25519 public key $C = c G$, - a post-quantum public key $\Mu$, and - an RSA-FDH signature $S = S_d(C || \Mu)$ by a denomination key $d$. -A coin is spent by signing a contract with $C$. The contract must -specify the recipiant merchant and what portion of the value denoted -by the denomination $d$ they recieve. -If $\Mu$ is large, we may replace it by $H(C || \Mu)$ to make signing -contracts more efficent. - -There was of course a blinding factor $b$ used in the creation of -the coin's signature $S$. In addition, there was a private seed $s$ -used to generate $c$, $b$, and $\mu$, but we need not retain $s$ -outside the refresh protocol. -$$ c = H(\textrm{"Ed25519"} || s) -\qquad \mu = \CSK(s) -\qquad b = H(\textrm{"Blind"} || s) $$ - -\smallskip - -We begin refresh with a possibly tainted coin $(C,\Mu,S)$ that -we wish to refresh into $n \le \theta$ untainted coins. - -In the change sitaution, our coin $(C,\Mu,S)$ was partially spent and -retains only a part of the value determined by the denominaton $d$. -There is usually no denomination that matchets this risidual value -so we must refresh from one coin into $n \le \theta$. - -For $x$ amongst the symbols $c$, $C$, $\mu$, $\Mu$, $b$, and $s$, -we let $x_{j,i}$ denote the value normally denoted $x$ of - the $j$th cut of the $i$th new coin being created. -% So $C_{j,i} = c_{j,i} G$, $\Mu_{j,i}$, $m_{j,i}$, and $b^{j,i}$ -% must be derived from $s^{j,i}$ as above. -We need only consider one such new coin at a time usually, -so let $x'$ denote $x_{j,i}$ when $i$ and $j$ are clear from context. -In other words, $c'$, $\mu'$, and $b_j$ are derived from $s_j$, - and both $C' = c' G$ and $\Mu' = \CSK(s')$. - -\paragraph{Wallet phase 1.} -\begin{itemize} -\item For $j=1 \cdots \kappa$: - \begin{itemize} - \item Create random $\zeta_j$ and $l_j$. - \item Also compute $L_j = l_j G$. - \item Generate $\lambda_j = \LSK((j,i),\mu)$, - $\Lambda_j = \LPK(\lambda_j)$, and - $\eta_j = \KEX_2(\lambda_j,\Mu)$. - \item Set the linking commitment $\Gamma_{j,0} = (L_j,E_{l_j C}(\Lambda_j))$. - \item Set $k_j = H(l_j C || \eta_j)$. -\smallskip - \item For $i=1 \cdots n$: - \begin{itemize} - \item Set $s' = H(\zeta_j || i)$. - \item Derive $c'$, $m'$, and $b'$ from $s'$ as above. - \item Compute $C' = c' G$ and $\Mu' = \CPK(m')$ too. - \item Compute $B_{j,i} = B_{b'}(C' || \Mu')$. - \item Encrypt $\Gamma'_{j,i} = E_{k_j}(s')$. - \item Set the coin commitments $\Gamma_{j,i} = (\Gamma'_{j,i},B_{j,i})$ -\end{itemize} -\smallskip -\end{itemize} -\item Send $(C,\Mu,S)$ and the signed commitments - $\Gamma_* = S_C( \Gamma_{j,i} \quad\textrm{for}\quad j=1\cdots\kappa, i=0 \cdots n )$. -\end{itemize} - -\paragraph{Exchange phase 1.} -\begin{itemize} -\item Verify the signature $S$ by $d$ on $(C || \Mu)$. -\item Verify the signatures by $C$ on the $\Gamma_{j,i}$ in $\Gamma_*$. -\item Pick random $\gamma \in \{1 \cdots \kappa\}$. -\item Mark $C$ as spent by saving $(C,\gamma,\Gamma_*)$. -\item Send $\gamma$ as $S(C,\gamma)$. -\end{itemize} - -\paragraph{Wallet phase 2.} -\begin{itemize} -\item Save $S(C,\gamma)$. -\item For $j = 1 \cdots \kappa$ except $\gamma$: - \begin{itemize} - \item Create a proof $\lambda_j^{\textrm{proof}}$ that - $\lambda_j$ is compatable with $\Lambda_j$ and $\Mu$. - \item Set a responce tuple - $R_j = (\zeta_j,l_j,\lambda_j,\lambda_j^{\textrm{proof}})$. - \end{itemize} -\item Send $S_C(R_j \quad\textrm{for}\quad j \ne \gamma )$. -\end{itemize} - -\paragraph{Exchange phase 2.} -\begin{itemize} -\item Verify the signature by $C$. -\item For $j = 1 \cdots \kappa$ except $\gamma$: - \begin{itemize} - \item Compute $\eta_j = \KEX_2(\lambda_j,\Mu)$. - \item Verify that $\Lambda_j = \LPK(\lambda_j)$ - \item Set $k_j = H(l_j C || \eta_j)$. - \item For $i=1 \cdots n$: - \begin{itemize} - \item Decrypt $s' = D_{k_j}(\Gamma'_{j,i})$. - \item Compute $c'$, $m'$, and $b'$ from $s_j$. - \item Compute $C' = c' G$ too. - \item Verify $B' = B_{b'}(C' || \Mu')$. - \end{itemize} - \end{itemize} -\item If verifications all pass then send $S_{d_i}(B_\gamma)$. -\end{itemize} - -We could optionally save long-term storage space by -replacing $\Gamma_*$ with both $\Gamma_{\gamma,0}$ and - $S_C(\Eta_{j,i} \quad\textrm{for}\quad j \ne \gamma )$. -It's clear this requires the wallet send that signature in some phase, -but also the wallet must accept a phase 2 responce to a phase 1 request. - -\smallskip - -There is good reason to fear tax evasion committed during the -initial withdrawal of a coin as well. A merchant simply provides -the customer with a blinded but unpurchased coin and asks them to -pay to withdraw it. - -\subsection{Withdrawal}\label{subsec:withdrawal} - -In Taler, we may address tax fraud on initial withdrawal by turning -withdrawal into a refresh from a pseudo-coin $(C,\Mu)$ in which - $C$ is the user's reserve key \cite[??]{Taler} and - $\Mu$ s a post-quantum public key kept with $C$. -We see below however that our public key algorithm has very different -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, -for Taler's refresh protocol. - -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{??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 -SIDH 3-torsion private and public keys. - -We envision the 2-torsion secret key generation function $\CSK(s)$ -for $\mu$ being deterministic with seed $s$, but the 3-torsion secret -key generation function $\LSK()$ ignores the arguments given above -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. - -If using SIDH, then we naturally depend upon the security assumption -used in SIDH, but combining this with ECDH is stronger than either -alone. - -... proof ... - -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 - -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}. - -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}. -[[ 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} - -We now define our hash-based encryption scheme. -Let $\delta$ denote our query security paramater and - let $\mu$ be a bit string. -For $j \le \kappa$, we define a Merkle tree $T_j$ of height $\delta$ -with leaves $\eta_j = H(\mu || "YeyCoins!" || t || j)$ - for some leaf index $t \le 2^\delta$. -Let $t_j$ denote the root of $T_j$. -Set $\Mu = H(t_1 || \cdots || t_\kappa)$, - which defines $\CPK(\mu)$. - -Now let $\lambda_j = \LSK((t,j),\mu)$ consist of -$(t,j,\eta_j)$ along with both - the Merkle tree path that proves $\eta_j$ is a leaf of $T_j$, -and $(t_1,\ldots,t_\kappa)$, - making $\LSK$ an embelished Merkle tree path function. -Also let $\Lambda_j = \LPK(\lambda_j)$ be $(t,j)$ - -We define $\KEX_2(\lambda_j,\Mu)$ to be $\eta_j$ - if $\lambda_j$ proves that $\eta_j$ is the $t$ leaf for $\Mu$, -or empty otherwise. -$\KEX_3(\Lambda_j,\mu)$ simply recomputes $\eta_j$ as above. -If $\KEX_2$ works then so does $\KEX_3$. - -As $\Lambda_j = (t,j)$, it matters that $\lambda_j$ actually -demonstrates the position $t$ in the Merkle tree. - -... proofs ... - -\smallskip - -We observe that $\CPK$ has running time $O(2^\delta)$, severely -limiting $\delta$. We lack the time-space trade offs resolve -this issue for hash-based signature (see \cite{SPHINCS}). - -Imagine that $\delta = 0$ so that $T_j = H(\eta_j)$. -In this scenario, a hostile exchange could request two different -$\gamma$ to learn all $\eta_j$, if the wallet reruns its second -phase. In principle, the wallet saves the exchange's signed -choice of $\gamma$ before revealing $\eta_j$ for $j \neq \gamma$. -It follows that even $\delta = 0$ does technically provides -post-quantum anonymity, - -We must worry about attacks that rewind the wallet from phase 2 to -phase 1, or even parallelism bugs where the wallet answer concurrent -requests. We cannot remove the curve25519 exchange $l_j C$ from the -refresh protocol becausenn such attacks would represent serious risks -without it. With our $l_j C$ component, there is little reason for -an attacker to pursue $\eta_j$ alone unless they expect to break -curve25519 in the future, either through mathematical advances or -by building a quantum computer. - -We therefore view $\delta$ as a query complexity paramater whose -optimial setting depends upo nthe strength of the overall protocoll. - -\smallskip - -We can magnify the effective $\delta$ by using multiple $\eta_j$. - -... analysis ... -% multiple withdrawals - -We believe this provides sufficent post-quantum security for -refreshing change. - - -\section{Hash and Ring-LWE hybrid} - -We noted in \S\ref{subsec:withdrawal} above that exchange might -require that initial withdrawals employs a refresh-like operation. -In this scenarion, we refresh from a pseudo-coin $(C,\Mu)$ where - $C$ is the user's reserve key \cite[??]{Taler} and - $\Mu$ s a post-quantum public key kept with $C$. -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. ??? ]] - -% Use birthday about on Alice vs Bob keys? - -\section{Conclusions} - -... - - -\bibliographystyle{alpha} -\bibliography{taler,rfc} - -% \newpage -% \appendix - -% \section{} - - - -\end{document} - -\begin{itemize} -\item -\item -\end{itemize} - -\begin{itemize} -\item -\item -\end{itemize} - - - - - -Crazy pants ideas : - -Use a larger Mrkle tree with start points seeded throughout - -Use a Merkle tree of SWIFFT hash functions becuase - their additive homomorphic property lets you keep the form of a polynomial - - - -- cgit v1.2.3