HD wallets and the Legendrery PRF in MPC

$$ \def\sample{\stackrel{{\scriptscriptstyle\$}}{\leftarrow}} \def\isequal{\stackrel{?}{=}} \def\cP{\mathcal{P}} \def\cF{\mathcal{F}} \def\*{\cdot} \newcommand{\leg}[1]{\genfrac{(}{)}{}{}{#1}{p}} $$ # HD wallets and the Legendrery PRF in MPC ## Introduction In this post we explain what are Hierarchical Deterministic (HD) wallets and Pseudo Random Functions (PRFs), and how they can be used in a Multi Party Computation (MPC) setting in a very efficient manner.  ## Background ### HD Wallets Hierarchical Deterministic (HD) wallets were invented by Pieter Wuille ^[[https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki](https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki)], They provide a mechanism to generate a lot of private keys deterministically from a single master key. That way you only need to backup the master key and you can restore all future keys even if you generate multiple private keys. There are a few reasons why you would want to keep switching keys: 1. Privacy, if you generate a new address every time you receive a payment, it hides unrelated transactions from the sender, as the address was never used before. 2. Security, if a single private key is leaked via either a bad signature (faulty nonce) or some attack, the rest of the keys generated from the same master key are safe, and the bitcoins in them are also safe. There are 2 kinds of HD wallets: #### Non-Hardened Non-Hardened HD means that there's a master public key $PK$ and a master private key $SK$. You can generate new public keys using the master public key, and their corresponding private keys using the master private key. This allows you to use the master public key on a "hot" wallet and generate new public keys for every transaction without risking the private key. The downside of this is that if an attacker gets hold of your master public key you lose both the privacy and the security properties of the HD wallet. Generally speaking key generation here looks as follows: $\delta_i = \cF_{MasterPublicKey}(i)$ where $\cF$ is a Pseudo Random Function(explained later), and then the new public key is $PK_i = PK + \delta_i G$ and the private key is: $SK_i = SK + \delta_i$, so anyone that has the master public key can calculate $\delta_i$, which breaks both properties of the HD wallet. #### Hardened Hardened HD on the other hand, doesn't use the master public key to generate keys, instead it always uses the master private key, so it looks as follows: $\delta_i = \cF_{MasterPrivateKey}(i)$ where $\cF$ is a Pseudo Random Function, and the new public and private keys are again: $PK_i = PK + \delta_i G$ and $SK_i = SK + \delta_i$. On one hand you can no longer store the master public key on a web server to generate public keys, but on the other hand it means that leaking public keys will never expose $\delta_i$ so an attacker can't calculate future public keys, and can't calculate all private keys from a single leaked private key, that way both the privacy and security properties will hold as long as the master private key stays safe. ### PRFs Pseudo Random Functions (PRF) are a very common primitive in cryptography, we use them for HD wallets, but also to construct block ciphers, MACs (Message Authenticated Codes) and more. Simply speaking a PRF is defined as a function that receives a key $K$ and an input $M$ and returns an output $N$, where for anyone who doesn't have the key the output seems indistinguishable from randomness. $\cF: \{0,1\}^m \times \{0,1\}^k \rightarrow \{0,1\}^n$  ### MPC and Secret Sharing Multi-Party Computation (MPC) is concerned with computing functions over data that is shared between multiple parties while keeping the shares secret even from the other parties. One common way to do that is using Secret Sharing, which is a mechanism where we share a secret between multiple parties and do operations on that shared secret. Secret sharing works as follows, each party has a $a_i$ such that $s =\sum_i{a_i}$. Throughout the blog we'll use $[a]$ to say that $a$ is secret shared between $n$ parties. Now we can do arithmetics on secret shares: * Adding 2 secrets: $[c] = [a] + [b]$ Each party computes $c_i = a_i + b_i$ which results in $c = \sum_i{(a_i + b_i)}$. * Adding a public value: $[c] = [a] + b$ we just need a single party to add that value to their share, so if $\cP_0$ sets $c_0 = a_0 + b$ then now $c = \sum_i{s_i}+b$. * Multiplying by a public value: $[c] = [a] \* b$ Each party computes $c_i = a_i \* b$, which results in $c = \sum_i{(b \* a_i)} = b \* \sum_i{a_i}$ * Multiplying 2 secrets is much more complicated, in this blog post we'll assume it is possible but won't get into the details of how. A few common tricks use a Vandermonde matrix, Beaver triples, Oblivious Transfer, or a homomorphic encryption scheme like Paillier. * Opening a secret: If $[a]$ is some secret share value, then every party $\cP_i$ sends their share $a_i$, which allows everyone to compute the value $a = \sum_i{a_i}$. We also use $[a] \sample F_p$ to denote randomly sampling a shared secret from the field $F_p$ where $p$ is a prime. ## Motivation: MPC HD wallets MPC and secret sharing is used in practice in a lot of cryptocurrency wallets, currently these wallets either don't use a HD wallet, or use the *non-hardened* variant. In this post we describe a protocol that will allow us to implement the *hardened* variant of a HD wallet even when our key is secret shared. For that we need a PRF that can work with a shared key $[K]$, the input $M$ is assumed to be publicly known as it will be the index $i$ in the HD wallet calculation, but we want the output $[N]$ which is the new private key to be secret shared between the same participants. ## Existing MPC PRFs So what's the problem with known PRFs such as HMAC-SHA256 and Chacha20? If we want to use HMAC-SHA256 like BIP32 does over our shared key, we will either need a garbled circuit which requires a tremendous amount of computational and communication complexity, or to transform these algorithms into arithmetic circuits, which can then be computed using secret sharing arithmetic but these contain thousands of gates, and between dozens to hundreds rounds of communication. So if we want something much faster and with low number of rounds, there are a few known solutions like the Naor-Reingold PRF[^naor] which work on secret shared keys and are quite simple and efficient. These rely on the discrete logarithm and related problems, but their output must be public and we want the output $N$ to be secret shared and not public. [^naor]: [https://en.wikipedia.org/wiki/Naor–Reingold_pseudorandom_function](https://en.wikipedia.org/wiki/Naor%E2%80%93Reingold_pseudorandom_function) ## The Legendrery PRF ### Legendre Symbol The Legendre symbol is a way to symbolize if a scalar $a$ modulo a prime $p$ is a quadratic residue (QR) or quadratic non residue (QNR), $a$ is a quadratic residue iff there exist some $w$ such that $w^2 \equiv a \pmod p$. The Legendre symbol just gives the number 1 to quadratic residues, -1 to quadratic non residues and 0 to 0. Formally ([source](https://en.wikipedia.org/wiki/Legendre_symbol#Definition)): $$ \leg{a} = \begin{cases} 1 \quad \text{if $a$ is a quadratic residue modulo $p$ and $a \neq 0$} \\ -1 \text{ if $a$ is a quadratic non residue modulo $p$} \\ 0 \quad \text{if $a = 0 \pmod p$} \end{cases} $$ (note that $\leg{a}$ denotes "The Legendre symbol of $a$ modulo $p$") Calculating the Legendre symbol can be done in an efficient manner, the simplest way is using Euler's criterion[^Euler] $\leg{a} = a^{(p-1)/2} \pmod p$ in practice there are more efficient algorithms.  [^Euler]: https://en.wikipedia.org/wiki/Euler%27s_criterion ### Making a pseudo random function out of it This PRF was first proposed and analyzed by Ivan Damgård in 1990[^Damgard], he conjectured the hardness of a few problems, together they give us the following informal assumption: Given a randomly sampled $a \sample F_p$ where $p$ is prime, the sequence of Legendre symbols $(\leg{a}, \leg{a+1}, \leg{a+2},...)$ is indistinguishable from randomness. [^Damgard]: Damgård, I.B., 1990. On the randomness of Legendre and Jacobi sequences, in: Proceedings on Advances in Cryptology, CRYPTO ’88. Springer-Verlag, Berlin, Heidelberg, pp. 163–172.  Now we can build a PRF from it as follows: $$ \mathcal{f}_K(M) = (\leg{K+M}, \leg{K+M+1},... \leg{K+M+n-1}) $$ This gives us $n$ bits of output, we can map them from {-1,1} to {0,1} by doing: $(1+b)/2$ and we can either ignore the $0$ option due to very low probability(number of bits generated divided by the field size), or just define it as $1$. ### How do we do this in MPC? At first glance it looks hard to compute the Legendre symbol of a shared value in MPC, as all these algorithms involve a lot of multiplications, but we will quickly see that it's actually much easier by using a modified version of a trick shown by Grassi et al[^grassi]. [^grassi]: Grassi, L., Rechberger, C., Rotaru, D., Scholl, P., Smart, N.P., 2016. MPC-Friendly Symmetric Key Primitives. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS '16) pp. 430–443. [https://doi.org/10.1145/2976749.2978332](https://doi.org/10.1145/2976749.2978332) To do this we will blind the value of the shared secret $([K]+[M])$ in a way that affects its Legendre symbol in a predictable way, so that we can compute the symbol on a blinded public value, and then we will unblind that value using the shared blinder and get the shared Legendre symbol of $(K+M)$. For that we need blinding values with known Legendre symbols, so we will need to generate: * A shared random quadratic residue $[s]$ [^random_square] * A shared random quadratic non residue $[n]$ [^random_non_square] * A shared random bit $[b] \in \{0,1\}$[^random_bit] [^random_square]: $[s'] \sample F_p; [s] = [s'] \* [s']$ [^random_non_square]: You generate a random secret square and then multiply it by some publicly known Quadratic Non Residue [^random_bit]: You generate a random $[s]$, square it($[s^2]$), open the square, take the square root and divide the open sqrt by the original shared secret($\sqrt{s^2}/[s]$) that gives you a single shared bit $[b]$ that depends on if $[s]$ was QR or QNR. We then compute the blinder: $[t] = [b] \*([s] - [n]) + [n]$ If $b=0$ then $[t] = 0 \*([s] - [n]) + [n] = [n]$ If $b=1$ then $[t] = 1 \*([s] - [n]) + [n] = [s]$ So $[t]$ is either $[s]$ (which is QR) or $[n]$ (which is QNR) and $[t]$ is secret shared (because the operations were on $[s]$ and $[n]$ which are secret shared) Next we compute: $[u] = [t] \* ([K]+[M])$, so now $[u]$ contains $([K]+[M])$ blinded by $[t]$, and remember that $[t]$ is either QR or QNR depending on the value of $b$. This is where the magic happens, each party can send their $u_i$ to everyone else so we can open the value of $[u]$, this will not expose anything on $[K]$ or $M$ because they are blinded by $[t]$, and now that $u$ is public we can calculate the Legendre symbol $l = \leg{u}$. So $l$ is the Legendre symbol of $([K]+M)$ blinded by $[t]$, all we need to do is to make it a shared secret again and unblind $[t]$. To do that we compute: $[y] = l \* (2 \* [b] - 1)$. $[y]$ is secret shared even though $l$ is public, because $[b]$ is a secret share, and multiplying a public value by a shared value results in a shared value. Let's go over it: if $[b] = 0$ then $[t]$ is QNR(Legendre symbol $-1$) and $[y] = l \* (2 \* 0 - 1) = -l$ if $[b] = 1$ then $[t]$ is QR(Legendre symbol $1$) and $[y] = l \* (2 \* 1 - 1) = l$ You can see that this cancels out the effect of $[t]$, if $[t]$'s Legendre symbol is $-1$ it will multiply $l$ by $-1$ and will cancel the effect, otherwise it will multiply it by 1 (and hence the symbol won't change). This means that $[y]$ now contains the Legendre symbol $\leg{[K+M]}$ and it is secret shared because $[b]$ is secret shared, so no one knows what the actual symbol is. We can then convert that into a bit in a secret shared way by doing $([y]+1)/2$, This can be executed $n$ times in parallel to generate $n$ bits output, each time increasing $M$ by 1, that way the number of bits don't affect the number of communication rounds. For a fully dishonest majority, security proofs and an implementation wait for the paper ## Acknowledgments We thank Nikolaos Makriyannis who's a co-author on the yet to be published paper, and to Claudio Orlandi and the ZenGo-X team for reviewing it.