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 ^[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:

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.
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 $P K$ and a master private key $S K$ .
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:
$δ_{i} = F_{M a s t e r P u b l i c K e y} (i)$ where $F$ is a Pseudo Random Function(explained later), and then the new public key is $P K_{i} = P K + δ_{i} G$ and the private key is: $S K_{i} = S K + δ_{i}$ , so anyone that has the master public key can calculate $δ_{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:
$δ_{i} = F_{M a s t e r P r i v a t e K e y} (i)$ where $F$ is a Pseudo Random Function, and the new public and private keys are again: $P K_{i} = P K + δ_{i} G$ and $S K_{i} = S K + δ_{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 $δ_{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.
$F : {0, 1}^{m} \times {0, 1}^{k} \to {0, 1}^{n}$

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 $P_{0}$ sets $c_{0} = a_{0} + b$ then now $c = \sum_{i} s_{i} + b$ .
Multiplying by a public value: $[c] = [a] \cdot b$ Each party computes $c_{i} = a_{i} \cdot b$ , which results in $c = \sum_{i} (b \cdot a_{i}) = b \cdot \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 $P_{i}$ sends their share $a_{i}$ , which allows everyone to compute the value $a = \sum_{i} a_{i}$ .

We also use $[a] \overset{$}{\leftarrow} 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^[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 $N$ to be secret shared and not public.

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 (\mod p)$ .
The Legendre symbol just gives the number 1 to quadratic residues, -1 to quadratic non residues and 0 to 0.

Formally (source):
$(\frac{a}{p}) = {\begin{cases} 1 if a is a quadratic residue modulo p and a \neq 0 \\ - 1 if a is a quadratic non residue modulo p \\ 0 if a = 0 (\mod p) \end{cases}$

(note that $(\frac{a}{p})$ 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^[3] $(\frac{a}{p}) = a^{(p - 1) / 2} (\mod p)$ in practice there are more efficient algorithms.

Making a pseudo random function out of it

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 $a \overset{$}{\leftarrow} F_{p}$ where $p$ is prime, the sequence of Legendre symbols $((\frac{a}{p}), (\frac{a + 1}{p}), (\frac{a + 2}{p}), . . .)$ is indistinguishable from randomness.

Now we can build a PRF from it as follows:
$f_{K} (M) = ((\frac{K + M}{p}), (\frac{K + M + 1}{p}), . . . (\frac{K + M + n - 1}{p}))$
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^[5].

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]$ ^[6]
A shared random quadratic non residue $[n]$ ^[7]
A shared random bit $[b] \in {0, 1}$ ^[8]

We then compute the blinder: $[t] = [b] \cdot ([s] - [n]) + [n]$
If $b = 0$ then $[t] = 0 \cdot ([s] - [n]) + [n] = [n]$
If $b = 1$ then $[t] = 1 \cdot ([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] \cdot ([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 = (\frac{u}{p})$ .
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 \cdot (2 \cdot [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 \cdot (2 \cdot 0 - 1) = - l$
if $[b] = 1$ then $[t]$ is QR(Legendre symbol $1$ ) and $[y] = l \cdot (2 \cdot 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 $(\frac{[K + M]}{p})$ 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.

https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki ↩︎
https://en.wikipedia.org/wiki/Naor–Reingold_pseudorandom_function ↩︎
https://en.wikipedia.org/wiki/Euler's_criterion ↩︎
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 ↩︎
$[s^{'}] \overset{$}{\leftarrow} F_{p}; [s] = [s^{'}] \cdot [s^{'}]$ ↩︎
You generate a random secret square and then multiply it by some publicly known Quadratic Non Residue ↩︎
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. ↩︎

Matan Hamilis

2021/09/19 21:19:52

input

I'd refrain from using the term "input" as its meaning could be ambiguous, perhaps "message" will be better suited? (Edited)

2021/09/19 21:22:15

who (Edited)

Elichai Turkel

2021/09/19 21:22:51

Hmm I guess you're right. I wrote input because that's how both Lindell and Boneh describe it, but message might be clearer (Edited)

2021/09/19 21:24:39

Formally: A function $\cF: \{0,1\}^m \times \{0,1\}^k \rightarrow \{0,1\}^n$ is called a PRF if the following criteria holds:

1. Typesetting: The "Let" is italicized. 2. Perhaps I'd consider phrasing the sentence as "A function F:{0,1}^m... is called a 'PRF' if the following two criteria hold:" just to skip typing the symbol "F" twice. (Edited)

2021/09/19 21:24:52

input -> message (?) (Edited)

2021/09/19 21:25:18

Period at the end of a sentence. (Edited)

2021/09/19 21:25:36

Should this be capitalized? (Edited)

2021/09/19 21:26:28

we h

Perhaps the variable 't' is redundant? You don't seem to use it in the rest of the definition. (Edited)

2021/09/19 21:28:19

Hmm it's technically a parameter of the PRF, but I can probably omit that like I've omitted `q` (the amount of queries allowed to the oracle) (Edited)

2021/09/19 21:34:00

their output m

repeat the word "problem", consider a synonym? (Edited)

2021/09/19 21:39:26

denotes

"denotes" or "is used to denote" may suit well here. (Edited)

2021/09/19 21:53:33

secret again

is it done simply with one of the participants acting as a dealer with a VSS scheme? (Edited)

2021/09/19 21:54:04

redundant period? (Edited)

2021/09/19 21:55:38

We can then convert that into a bit in a secret shared way by doing $([y]+1)/2$,

At this point I'm just wondering if this is so much effort for a single bit, is it better then building circuits for Chacha-20 / HMAC-SHA256? Or perhaps it isn't as much effort? An analysis would be nice :) (Edited)

2021/09/20 11:04:49

Added a sentence saying this can be done in parallel, so it doesn't increase the number of rounds (Edited)

Omer Shlomovits

2021/09/20 11:31:04

Legendrery

typo ? (Edited)

2021/09/20 11:32:40

eudo Random Fun

add (PRF) (Edited)

2021/09/20 11:36:31

replace with "computing" (Edited)

2021/09/20 11:41:04

seems like this subtitle can be MPC and PRF MPC (Edited)

2021/09/20 11:51:06

So if we

more like billions (Edited)

2021/09/20 11:57:39

hese

this? (Edited)

2021/09/20 11:59:10

legendary (Edited)

2021/09/20 12:08:41

I usually try to write without shortcuts: you will (Edited)

2021/09/20 12:21:44

Next we compute:

how ? (Edited)

2021/09/20 12:24:06

use "." instead of "," ? (Edited)

2021/09/22 08:12:34

It was a deliberate typo (Edited)

claudiorlandi

2021/09/22 14:09:04

For any adversary $A$ we have: $|Pr_K[A^{\cF_K}] - Pr_f[A^f]| < \epsilon$ Where $f$ is uniformly chosen over all functions $F: \{0,1\}^m \rightarrow \{0,1\}^n$

Agree with Omer the formal definition is probably an overkill for a blog post. Saying it looks indistinguishable from a random function should be enough for blog readers. (Edited)

2021/09/22 14:10:50

this is probably modulo something. Probably it is clear to experienced readers but could confuse casual ones. (Edited)

2021/09/22 14:12:49

Not billions for HMAC? Depends of course if you think about single block or multiple block hash. (Edited)

2021/09/22 14:13:23

So if we want something much faster and with low number of rounds,

Where do you get the thousands of rounds from? If you use yao it's constant round anyway. If you use MPC based on secret sharing the round complexity is the depth of the circuit which is typically not thousands? (Edited)

2021/09/22 14:22:23

build

nothing is easy in crypto :) (Edited)

2021/09/22 14:22:39

### How do we do this in MPC? At

Is this level of detail needed? (Edited)

2021/09/22 14:23:55

which algorithms? (Edited)

2021/09/22 14:25:50

Footnotes in footnotes aren't great :) (Edited)

2021/09/22 14:31:57

To do that we compute: $[y] = l \* (2 \* [b] - 1)$. $[y]$ is secret shared even though $l$ is public, because $[b]

This should probably have been explained much earlier, since you've already assumed you can compute efficiently Legendre symbols. (Edited)

2021/09/22 14:32:23

Capital (Edited)

2021/10/05 15:37:35

uncapitalize the "I" (Edited)

2021/10/05 18:35:40

Should it be capitalized? (Edited)

2021/10/05 18:39:53

e (

space (Edited)

2021/10/05 18:39:58

A-Tsai

2023/04/19 09:41:34

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$.

Question: Should c be sum(si) + n*b ? (Edited)