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.
Hierarchical Deterministic (HD) wallets were invented by Pieter Wuille [1], 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:
There are 2 kinds of HD wallets:
Non-Hardened HD means that there's a master public key and a master private key .
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:
where is a Pseudo Random Function(explained later), and then the new public key is and the private key is: , so anyone that has the master public key can calculate , which breaks both properties of the HD wallet.
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:
where is a Pseudo Random Function, and the new public and private keys are again: and .
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 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.
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 and an input and returns an output , where for anyone who doesn't have the key the output seems indistinguishable from randomness.
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 such that .
Throughout the blog we'll use to say that is secret shared between parties.
Now we can do arithmetics on secret shares:
We also use to denote randomly sampling a shared secret from the field where is a prime.
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 , the input is assumed to be publicly known as it will be the index in the HD wallet calculation, but we want the output which is the new private key to be secret shared between the same participants.
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[2] 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 to be secret shared and not public.
The Legendre symbol is a way to symbolize if a scalar modulo a prime is a quadratic residue (QR) or quadratic non residue (QNR), is a quadratic residue iff there exist some such that .
The Legendre symbol just gives the number 1 to quadratic residues, -1 to quadratic non residues and 0 to 0.
Formally (source):
(note that denotes "The Legendre symbol of modulo ")
Calculating the Legendre symbol can be done in an efficient manner, the simplest way is using Euler's criterion[3] in practice there are more efficient algorithms.
This PRF was first proposed and analyzed by Ivan Damgård in 1990[4], he conjectured the hardness of a few problems, together they give us the following informal assumption:
Given a randomly sampled where is prime, the sequence of Legendre symbols is indistinguishable from randomness.
Now we can build a PRF from it as follows:
This gives us bits of output, we can map them from {-1,1} to {0,1} by doing: and we can either ignore the option due to very low probability(number of bits generated divided by the field size), or just define it as .
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[5].
To do this we will blind the value of the shared secret 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 .
For that we need blinding values with known Legendre symbols, so we will need to generate:
We then compute the blinder:
If then
If then
So is either (which is QR) or (which is QNR) and is secret shared (because the operations were on and which are secret shared)
Next we compute: , so now contains blinded by , and remember that is either QR or QNR depending on the value of .
This is where the magic happens, each party can send their to everyone else so we can open the value of , this will not expose anything on or because they are blinded by , and now that is public we can calculate the Legendre symbol .
So is the Legendre symbol of blinded by , all we need to do is to make it a shared secret again and unblind .
To do that we compute: . is secret shared even though is public, because is a secret share, and multiplying a public value by a shared value results in a shared value.
Let's go over it:
if then is QNR(Legendre symbol ) and
if then is QR(Legendre symbol ) and
You can see that this cancels out the effect of , if 's Legendre symbol is it will multiply by and will cancel the effect, otherwise it will multiply it by 1 (and hence the symbol won't change).
This means that now contains the Legendre symbol and it is secret shared because 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 ,
This can be executed times in parallel to generate bits output, each time increasing 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
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.
https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki ↩︎
https://en.wikipedia.org/wiki/Naor–Reingold_pseudorandom_function ↩︎
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. ↩︎
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 ↩︎
You generate a random secret square and then multiply it by some publicly known Quadratic Non Residue ↩︎
You generate a random , square it(), open the square, take the square root and divide the open sqrt by the original shared secret() that gives you a single shared bit that depends on if was QR or QNR. ↩︎