donau

technicaldesign.tex (23893B)

---

 \newcommand{{\pub}}{{\sf pub}}
 \newcommand{{\priv}}{{\sf priv}}
 \newcommand{{\DI}}{{\sf DI}}
 \newcommand{{\UDI}}{{\sf UDI}}
 \newcommand{{\sign}}{{\sf sign}}
 \newcommand{{\verify}}{{\sf verify}}
 \newcommand{{\blind}}{{\sf blind}}
 \newcommand{{\unblind}}{{\sf unblind}}
 
 \section{Protocol Description}\label{technical}
 
 The previous section identified several requirements and desired features
 that a donation system must or should satisfy.
 The technically most challenging part is to permit donors
 to stay anonymous towards the charity they are donating to and to keep private
 from the tax authorities which charities they donated to.
 The protocol presented in this section addresses this
 challenge and all of the design goals from
 Section~\ref{sec:designgoals}. In
 Section~\ref{discussion} we discuss how
 the various optional capabilities could be achieved on
 top of this core protocol design.
 
 %Some of these are
 %contradictory and any deployment needs to prioritize compliance with local
 %laws and regulations.
 % CG: not sure they are actually contradictory, modulo if
 % you are strict on pseudonymity vs. anonymity; but even
 % here you're only linkable across donations to the same
 % charity, which is probably OK.
 
 This section provides a technical overview of our Donau protocol, starting with
 some cryptographic background followed by the setup and usage.
 The Donau service is typically run by the tax authority but can be an independent entity.
 
 % The first section introduces some notation and definitions used later on in the protocol description.
 % Concepts from cryptography are also explained when necessary.
 %
  \subsection{Background \& Terminology}\label{notation_and_definitions}
  Digital cash makes use of \textbf{blind signatures}~\cite{Chaum89} to issue tokens. Our
  design uses the same mechanism to unlink the donation process from the issued
  donation receipts.  This section introduces the definition and
  security properties of blind signatures.
 
 %    \paragraph{Cryptographic Hash Function}
 %      A cryptographic hash function $H$ is a function that takes as input an arbitrarily
 % long bit string
 %      and returns a fixed-length output string, which satisfies some security
 % requirements. In formulas
 % $$H: \{0,1\}^* \rightarrow \{0,1\}^n, m \mapsto h = H(m).$$
 % The function $H$ should provide preimage resistance, that means that
 % it should be infeasible to find an input that hashes to a given output. It
 % should also provide second-preimage resistance, that means that it should be
 % infeasible to find a second input that maps to the same output as a given input.
 % Even more restricting, it should provide collision resistance, meaning that it
 % should be infeasible to find two inputs that hash to the same output (without
 % any other restriction).
 
 %      Sometimes a hash function gets used in a scenario where the natural input
 % values come from a small, easily guessable set, like passwords or PINs.
 % In this scenario an attacker could break preimage resistance by just iterating
 % through all possible inputs to find the matching one and, worse, could even
 % store all resulting hash values in a big table for instant preimage lookups for
 % all users. One partial fix is to {\bf salt} the hash, i.e., to add a random
 % suffix or prefix to the input before hashing it. Applications then need to
 % store the salt as well. If the salt can be kept private this stops the simple
 % preimage attacks, otherwise it at least requires the attacker to try all inputs
 % {\em per targeted hash}. We write a {\bf salted hash} as $h = H(m, s)$, where
 % $s$ is the salt value.
 
 %    \paragraph{Digital Signatures}
 
 %      A digital signature is a cryptographic scheme for authenticating a message or document, analogous to a handwritten signature.
 %      A signer creates a public/private keypair.
 %      The private signing key is used to generate a signature on a message.
 %      The public key is distributed, and can be used by anybody to verify the authenticity of the signature.
 %      A signature scheme is secure if, among other things, the private key cannot be computed from the public key and if
 %      nobody can generate a signature that verifies for some message under a
 % public key if they do not have access to the matching private key.
 
    Informally, a blind signature is a digital signature where the signer does
    not know the message that they are signing.  The party requesting the
    signature hides the true message with a secret value called a {\bf blinding
      factor}, which can later be used to derive a valid signature on the
    original, unblinded message.
 
    Like standard digital signature schemes, blind signature schemes should
    achieve \textbf{unforgeability} --- the property that users without the
    secret signing key should be unable to generate new, valid
    signatures. Unlike standard digital signatures, blind signatures must also
    achieve \textbf{blindness} --- the property that curious signers should
    never be able to link previously issued blind signatures with their
    unblinded counterparts.
 
    \textrm{Slightly more formally, we define blind signatures as a quadruple of algorithms:}
    \begin{itemize}
      \item $KeyGen(1^\lambda)$: Generates a verification/signing key pair $(K^{\pub}, K^{\priv})$.
      \item $Blind(m,  b, K^{\pub})$: Takes a message $m$, blinding factor $b$, and verification key $K^{\pub}$ of the signer and computes the blinded message $\overline{m}$.
      \item $BlindSign(K^{\priv}, \overline{m})$: Takes secret signing key $K^{\priv}$ and blinded message $\overline{m}$ and computes the blind signature $\overline{\sigma}$.
      \item $Unblind(\overline{\sigma}, b, K^{\pub})$: Takes blind signature $\overline{\sigma}$, blinding factor $b$ and verification key $K^{\pub}$ of the signer, and returns the unblinded signature $\sigma$ on message $m$ (or $\bot$).
    \end{itemize}
 
 It should be impossible for the signer to infer information about the message
 they sign and it should be impossible for them to trace their signature later,
 see Hoepman's recent paper~\cite{2023/hoepman} highlighting that these are two
 separate requirements.
 
 The most well-known blind signature scheme, going back to Chaum's original
 work~\cite{Chaum89}, is based on RSA. A signature on message $m$ under RSA key
 public key $(n,e)$ is $s\equiv m^d \bmod n$, where $(n,d)$ is the corresponding
 private key. Instead of asking for a signature on $m$ one can request a
 signature on the blinded value $m'\equiv m\cdot r^e \bmod n$ for some randomly
 chosen $r$, receive the blind signature $s'$, and obtain the signature on $m$
 by unblinding $s'$ by computing $s'/r \bmod n$.
 
 In addition to blind signatures, Donau uses the
 Ed25519~\cite{DBLP:journals/jce/BernsteinDLSY12} signature scheme
 for signing ($\sign$) and verifying ($\verify$).
 
 \subsection{Key generation and initial setup}\label{key_generation_and_initial_setup}
 
 Before incognito donations to charities can be executed, all participants in
 the donation system (i.e., the Donau service, charities, and donors) must perform some
 initial setup steps.
 
 \subsubsection{Donau service key generation}\label{donau_key_generation}
 \begin{enumerate}
 \item The Donau service generates an Ed25519 keypair
   $(D^{\pub}$, $D^{\priv})$, called the {\bf Donau Key}, for digital signatures.
   \item The Donau service also generates a set of \textbf{Donation Unit} keypairs
 $(K_x^{\pub}, K_x^{\priv})$ for blind signatures, corresponding to different
 currency denominations $x$ that a donation can be composed of.
 \end{enumerate}
 The Donau service publishes all public keys over an authenticated channel.
 It uses fresh Donation Unit keys for each tax period.
 
 \subsubsection{Charity key generation and registration}\label{charity_key_generation}
 \begin{enumerate}
   \item Each charity generates its own Ed25519 {\bf Charity Key} $( C^{\pub},
 C^{\priv} )$.
   \item The charity also fetches the Donation Unit public keys from the
 Donau service.
   \item The charity transmits its public key $C^{\pub}$ to the party controlling the Donau service
 using an authenticated channel.
   \item The party in charge of Donau service administration
 validates that the charity is authentic and a legally recognized
 charitable organization. After successful verification, the charity public key
 $C^{\pub}$ is registered in the Donau database.
 \end{enumerate}
 
 \subsubsection{Donor Identifier generation}
 
 Each donor generates a personal \textbf{Donor Identifier} $\DI$ by
 computing a salted hash of their taxpayer ID
 \begin{align*}
   \DI = H(\texttt{TAXID}, S)
 \end{align*}
 where $H$ is a cryptographic hash function and
 $S$ is a random salt with sufficient entropy to
 prevent guessing attacks, and {\tt TAXID} is their taxpayer ID.
 The donor stores the salt $S$ along with their $\DI$.
 
 A donor uses their Donor Identifier every time they
 make a donation and again when requesting a donation receipt from the Donau service.
 
 They need to use the salt to link the Donation Identifier to their tax
 ID and claim the tax benefits for their donation. The use of the salt
 ensures that the $\DI$ cannot be linked to the donor by anybody
 without $S$, even if they know {\tt TAXID}.
 
 
 \subsection{Donating to a charity}\label{donating_to_a_charity}
 % \subsection{Donor donates to charity and transmits \textbf{Unique Donor identifiers} (future donation receipts)}
 When a donor wishes to donate to a charity, they first retrieve the Donau service's Donation Unit
 public keys $K_x^{\pub}$ for the current tax period.
 The donor then represents their donation as a sum of the Donation Units offered by the Donau service.
 
 \emph{Example: Assuming the Donau service publishes the Donation units $\{1,2,4,8\}$, a donation of $7$ would be split into 1 unit each of the values $4$, $2$ and $1$.}
 
 For each necessary Donation Unit the donor generates a \textbf{Unique Donor
 Identifier (UDI)} by appending a random nonce $N_i$ to the value $\DI$.
 If multiple instances of the same Donation Unit are needed to represent
 the target sum, the donor creates a different nonce $N_i$ for each instance $i$
 of that Donation Unit.
 The donor must remember all UDIs.
 
 \emph{In our example, there are $3$ Unique Donor Identifiers needed to represent the donated value of $7$. We can write them as:}
 \begin{align*}
   u_1 &= ( \DI, N_1) \\
   u_2 &= ( \DI, N_2) \\
   u_3 &= ( \DI, N_3)
 \end{align*}
 {\em where $\DI$ is the Donor Identifier from above, and the $N_i$s are nonces.}
 
 Next the donor blinds the Unique Donor Identifiers using a unique blinding factor for each one.
 This hides the information in the UDIs from third parties, including the Donau
 service and charity, and protects against linkability. The result is a set of {\bf Blinded Unique Donor Identifiers (BUDIs)}.
 
 {\em In our example, the Blinded Unique Donor Identifiers would be}
 \begin{align*}
   \overline u_1 &= \blind (u_1, b_1, K_1^{\pub}) \\
   \overline u_2 &= \blind (u_2, b_2, K_2^{\pub}) \\
   \overline u_3 &= \blind (u_3, b_3, K_4^{\pub})
 \end{align*}
 {\em with random blinding factors $b_1$, $b_2$, and $b_3$}.
 
 So far, the \textbf{Blinded Unique Donor Identifiers} do not carry information about their monetary values.
 The \emph{intended effective value is indicated} by grouping each Unique Donor Identifier with
 the hash of its respective Donation Unit public key $K^{\pub}_x$.
 We call this pair a \textbf{Blinded Unique Donor Identifier Key Pair} (\textbf{BKP}).
 It is only the \emph{intended effective} value because their value is zero until they are signed by the Donau service.
 Note that they must be signed with the matching Donation Unit key as the
 blinding and unblinding operations rely strongly on the public key.
 
 
 {\em The BKPs for our example are:}
 \begin{align*}
      \overline \mu_1 &= ( \overline u_1, h({K^{\pub}_1}) ) \\
      \overline \mu_2 &= ( \overline u_2, h({K^{\pub}_2}) ) \\
      \overline \mu_3 &= ( \overline u_3, h({K^{\pub}_4}) )
 \end{align*}
 
 
 These individual BKPs are then put in an array $\vec{\mu}$ of BKPs.
 
 {\em Here }
 \begin{align*}
      \vec{\mu} &= ( \overline \mu_1,
      \overline \mu_2,\overline \mu_3
      )
 \end{align*}
 
 The donor sends this array to the charity along with the corresponding
 payment.
 
 \subsection{Charity receives donation}\label{charity_receives_donation}
 Upon receiving the array $\vec{\mu}$ of BKPs and the corresponding payment from the donor,
 the charity verifies that the total amount claimed in the BKPs
 (based on the Donation Unit public key hashes $h(K_x^{\pub})$) is less than or
 equal to the amount they received in the payment.
 The charity then signs the array of BKPs with its Ed25519 Charity Key.
 That is, it computes
 \begin{align*}
     \sigma_c = \sign(\vec{\mu}, C^{\priv})
 \end{align*}
 The charity sends the array $\vec{\mu}$ of BKPs and their signature $\sigma_c$ to the Donau service to generate a receipt.
 
 \subsection{Donau service generates donation receipt}\label{donau_creates_donation_receipt}
 When the Donau service receives a signed set of BKPs from a charity, it verifies the charity's signature.
 It then checks that no legal restrictions are being violated.
 If none are, the Donau service increments its record of the charity's total receipts by the
 total amount of the donation, i.e., the sum of the denominations used in the
 BKPs.
 The Donau service then blindly signs all BUDIs using the Donation Unit private keys
 $K_x^{\priv}$
 that correspond to the public keys hashed in the BKPs.
 
 {\em In our example, the Donau service blindly signs the three BUDIs submitted by the charity}
 \begin{align*}
   \overline{\beta_1} = \blind\_\sign(\overline u_1, K_1^{\priv}) \\
   \overline{\beta_2} = \blind\_\sign(\overline u_2, K_2^{\priv}) \\
   \overline{\beta_3} = \blind\_\sign(\overline u_3, K_4^{\priv})
 \end{align*}
 
 These signatures constitute a blinded donation receipt from the Donau service, and the Donau service sends these back to the charity,
 which in turn forwards them to the donor.
 
 \subsection{Donor receives donation receipt}\label{donor_receives_donation_receipt}
 Upon receiving the blinded donation receipt from the Donau service via the charity,
 the donor verifies the blind signatures over the BUDIs.
 If they verify, the donor then unblinds them to obtain signatures over the original UDIs.
 These UDIs, their unblinded signatures, and their respective hashed Donation Unit public keys
 constitute a collection of donation receipts.
 These donation receipts are stored on the donor's device.
 
 {\em In our example: the donor unblinds the Donau service signatures $\overline{\beta_1}, \overline{\beta_2}, \overline{\beta_3}$, obtaining:}
 \begin{align*}
   \beta_1 &= \unblind(\overline{\beta_1}, b_1, K_1^{\pub}) \\
   \beta_2 &= \unblind(\overline{\beta_2}, b_2, K_2^{\pub}) \\
   \beta_3 &= \unblind(\overline{\beta_3}, b_3, K_4^{\pub})
 \end{align*}
 {\em The donor then creates the final Donation Receipts:}
 \begin{align*}
   r_1 &= ( \UDI_1, \beta_1, h(K_1^{\pub}) ) \\
   r_2 &= ( \UDI_2, \beta_2, h(K_2^{\pub}) ) \\
   r_3 &= ( \UDI_3, \beta_3, h(K_4^{\pub}) )
 \end{align*}
 
 \subsection{Donor requests an annual donation statement from Donau service}\label{donor_requests_a_donation_statement_from_the_donau}
 In order for the donor to claim a tax deduction,
 the donor needs to obtain a final donation statement which can be sent to the tax authority.
 The donor sends their saved donation receipts $\{r_1, \ldots, r_k\}$, accumulated throughout the tax period, to the Donau service.
 This can in principle be done multiple times during the tax period;
 however, the receipts must not be submitted at a time strongly correlated with the donation to achieve
 \emph{unlinkability} between the \emph{issuance} of the receipts (which happens at the time of donation)
 and their \emph{submission} for the Donation Statement.
 
 Remember that each $\UDI$ is the concatenation of the donor identifier $\DI$ and
 a random nonce, i.e., they all start with the same $\DI$.
 
 Once the Donau service receives the donor's donation receipts, it checks that for each receipt:
 \begin{itemize}
   \item the public key $K_x^{\pub}$ is known.
   \item the signature $\beta$ is correct using the corresponding public key
 $K_x^{\pub}$.
   \item the Donor Identifier $\DI$ is the same in all receipts.
 %    (With multiple wallets each wallet must simply obtain a separate Donation Statement)
   \item the nonces are unique and were not submitted before by the same donor,
 identified as $\DI$.
 \end{itemize}
 
 Importantly, the Donau service does not see signatures of the charities the donor
 donated to, so it does not know where the donor spent money.
 They also only see a collection of common denominations, so they are unable to correlate total donation amounts per charity.
 Finally, the receipts are unblinded, so they are unlinkable to any signature the Donau service has seen before.
 
 The Donau service then generates a signature over the total \texttt{amount} of all receipts, the current tax period (\texttt{year}) and the Donor Identifier.
 This results in a final signature called the \textbf{Donation Statement}, which the Donau service returns to the donor:
 \begin{align*}
   \sigma_s = \sign(( \DI, \textsf{amount}_{\sf Total}, \textsf{year}) ),
 D^{\priv})
 \end{align*}
 
 \subsection{Donor sends final statement to a validator}\label{donor_sends_final_statement_to_a_validator}
 Finally, to claim their deduction, the donor includes their donation statement
 in their tax declaration. The implementation detailed in the next section
 chooses to represent this information as a QR-Code
 \begin{align*}
   \texttt{QR} = (\texttt{TAXID}, S, \textsf{year}, \textsf{amount}_{\sf
 Total}, \sigma_s).
 \end{align*}
 Other representations and integration into software for filing tax returns are
 possible. It is relevant that {\tt TAXID} and salt $S$ are included to
 recompute the donation identifier $\DI$ while linking the donation receipt to
 the tax ID.
 
 The validator at the tax office verifies the \textbf{Donation Statement Signature} $\sigma_s$.
 \begin{align*}
   \verify((H({\tt TAXID},S), \textsf{amount}_{\sf Total}, \textsf{year}) ),\sigma_s,
 D^{\pub})
 \end{align*}
 
 
 % Putting unused defs from the thesis here in case they're needed for some reason later. don't want to recopy
 
 %   \item \textbf{Donation Unit Key generation}
 %     \begin{displaymath}
 %       ( K_x^{\pub}, K_x^{\priv} ) := Keygen^B(\omega)
 %     \end{displaymath}
 %     where $\omega$ is a source of entropy. The resulting key pair represents
 %     a \textbf{Donation Unit}. The result is a public key $K_x^{\pub}$ and
 %     private key $K_x^{\priv}$. The equivalent used in Taler system is a \texttt{Denomination}.
 %
 %   \item \textbf{Donau Key generation}
 %     \begin{displaymath}
 %       ( D^{\pub}, D^{\priv} ) := Keygen^D(\omega)
 %     \end{displaymath}
 %     where $D^{\pub}$ and $D^{\priv}$ are the respective public and private Donau keys.
 %
 %   \item \textbf{Charity Key generation}
 %     \begin{displaymath}
 %       ( C^{\pub}, C^{\priv} ) := Keygen^C(\omega)
 %     \end{displaymath}
 %     where $C^{\pub}$ and $C^{\priv}$ are the respective public and private Charity keys.
 %
 %   \item \textbf{Donation Unit (DU)}
 %     \begin{displaymath}
 %       ( K_x^{\pub}, K_x^{\priv} )
 %     \end{displaymath}
 %     A Donation Unit consists of a public and private key where $x$ is the associated value (e.g. 2 EUR).
 %
 %   \item \textbf{Donor Identifier (DI)}
 %     \begin{displaymath}
 %       i := H(\texttt{TAXID}, S)
 %     \end{displaymath}
 %     where $S$ is a random salt with sufficient entropy to prevent guessing attacks to invert the hash function.
 %
 %   \item \textbf{Unique Donor Identifier (UDI)}
 %     \begin{displaymath}
 %       u := ( i, N )
 %     \end{displaymath}
 %     where $N$ is a high-entropy nonce to make the resulting hash \textbf{unique} per donation.
 %
 %   \item \textbf{Blinded Unique Donor Identifier (BUDI)}
 %     \begin{displaymath}
 %       \overline{u} := \blind( u, b, K_x^{\pub} )
 %     \end{displaymath}
 %     A \textbf{BUDI} is the result of blinding a Unique Donor Identifier $u$
 %     where $b$ is the blinding factor and $K_x^{\pub}$ the associated Key. The blinding is done to protect the privacy of the donor.
 %
 %   \item \textbf{Blinded Unique Donor Identifier Key Pair (BKP)}
 %     \begin{displaymath}
 %       p := ( \overline{u}, H(K_x^{\pub}) )
 %     \end{displaymath}
 %     A \textbf{Blinded Unique Donor Identifier Key Pair} is the result of
 %     adding the corresponding hash of the \textbf{Donation Unit} public key to
 %     the \textbf{Blinded Unique Donor Identifier} $\overline{u}$ where
 %     $H(K_x^{\pub})$ is the hash of the \textbf{Donation Unit} public key.
 
 %   \item \textbf{Digital Signatures}
 %     A digital signature
 %     \begin{itemize}
 %       \item \textbf{Normal signing (e.g. EdDSA):}
 %       \begin{align}
 %         \fbox{$s := sign(m,k^{\priv})$}
 %       \end{align}
 %       where $m$ is a message and $k^{\priv}$ is the private key used to sign
 %       the message, for example the Donau private key $D^{\priv}$ or the
 %       Charity private key $C^{\priv}$.\\
 
 %       Applications:
 %       \begin{itemize}
 %       \item Signatures over a \textbf{Blinded Unique Donor Identifier Key Pair}:
 %         \begin{align}
 %           \fbox{$\vec{\mu}_s := sign(\vec{p},C^{\priv})$}
 %         \end{align}
 %           where $H(K_x^{\pub})$ indicates which \textbf{Donation Unit} key should be used by the Donau to sign the resulting \textbf{Donation Receipt}. Thus, this hash carries the information about the exact value, the final Donation Receipt should carry.
 %
 %         A charity signs a collection of \textbf{Blinded Unique Donor Identifier Key Pairs} before transferring them to the Donau to issue the \textbf{Donation Receipts}
 %
 %       \item Generation of the \textbf{Donation Statement}
 %       \end{itemize}
 %
 %       \item \textbf{Blind signing(e.g. RSA/CS):}
 %       \begin{align}
 %         \fbox{$\overline{\beta} := \blind\_sign(\overline{u},K_x^{\priv})$}
 %       \end{align}
 %       where $\overline{u}$ is a blinded value and $K_x^{\priv}$ is the private key used to blind sign the message.\\
 %
 %       Application:
 %       \begin{itemize}
 %         \item The Donau blind signs \textbf{Blinded Unique Donor Identifiers} received from the Charity with the private key matching the public key in the received \textbf{Blinded Unique Donor Identifier Key Pair}
 %       \end{itemize}
 %     \end{itemize}
 %
 %   \item \textbf{Verify Functions}
 %
 %   To verify the signatures $m$ corresponds to the message and $s$ to the signature:
 %
 %   \begin{itemize}
 %     \item \textbf{normal verify}
 %     \begin{displaymath}
 %       verify(m,s, P^{\pub})
 %     \end{displaymath}
 %     where $P^{\pub}$ can be the Donau public key $D^{\pub}$ or Charity public
 %     key $C^{\pub}$.
 %
 %     \item \textbf{blind verify}
 %       \begin{displaymath}
 %         verify\_blind(m,s,K_x^{\pub})
 %       \end{displaymath}
 %       verify a signature that was made blind and made with a Donation Unit
 %       private key $K_x^{\priv}$.
 %   \end{itemize}
 %
 %   \item \textbf{Donation Receipt}
 %     \begin{displaymath}
 %       r := ( u, \beta, H(K_x^{\pub}) )
 %     \end{displaymath}
 %     where $\beta$ is the unblinded signature sent to the Donau to get the \textbf{Donation Statement}.
 %
 %   \item \textbf{Donation Statement Signature}
 %     \begin{displaymath}
 %       \sigma := sign(( i, \Sigma{\vec{r}}, \texttt{Year}), D^{\priv})
 %     \end{displaymath}
 %     The \textbf{Donation Statement Signature} is the signature over the sum (amount donated) of all the \textbf{Donation Receipts} $\Sigma{\vec{r}}$, that a donor has received from donating throughout the year where $i$ is the \textbf{Donor Identifier}. The \textbf{Donation Statement} itself includes all sign values and the signature itself.
 %
 %     These \textbf{Donation Statement Signatures} attest the amount donated in a particular year by a specific donor.