Public derivation and diversification
The scheme above is based in BIP32 and does not allow to diversify FMD public keys.
Here we discuss a different way to do key derivation that accounts for diversification.
Desiderata
We want to achieve the following two features.
- Compactness: Derive an FMD public key pk_f from a compressed public key pk_c. Derivation must be public and it must hold size(pk_c)< size(pk_f). Only compressed keys pk_c are part of payment addresses.
- Diversification: A user controlling m addresses wants to have m unlinkable FMD public keys pk_{a,f}, one per address a. All public keys pk_{a,f} being associated with the same FMD secret key sk_f (i.e. same sk_f for all user’s addresses).
Description
The system parameters are an integer t\geq 2, and group \mathbb{G} of order q (the domain of public keys).
High level idea. The idea is to use as a master key a secret polynomial \tilde{p}(X)\in\mathbb{Z}_q[X] of degree t. The corresponding compressed public key is the polynomial in “the exponent”, thus a vector of t+1 points in \mathbb{G}. To derive arbitrarily many secrets, evaluate \tilde{p}(X) at \gamma>t different public evaluation points x_1,\ldots,x_\gamma. Unlinkability is achieved by randomizing the compressed public key.
The different keys are defined next.
- Master secret key An at most t-degree polynomial \tilde{p}(X)=\sum_{k=0}^t c_kX^k in \mathbb{Z}_q[X]. Thus:
sk_m:=(c_0,\ldots,c_t)\in\mathbb{Z}_q^t
Each coefficient c_i is sampled randomly or derived from other secret-key material controlled by the user.
- Master public key. The coefficients of \tilde{p}(X) encoded in the exponent of a fixed basepoint G\in\mathbb{G}. Thus
pk_m = (C_0,\ldots,C_t)\in\mathbb{G}^{t+1}\text{ where } C_i = [c_i]G.
- FMD secret key The FMD secret key sk_f for a batch of addresses a_1,\ldots,a_m (controlled by the user that knows sk_m) are \gamma evaluations of the secret polynomial \tilde{p}(X) at public points x_1,\ldots,x_\gamma. Thus:
sk_{f} := (\tilde{p}(x_1),\ldots,\tilde{p}(x_\gamma))\in\mathbb{Z}_q^t
- Compressed FMD public key For address a, the compressed public key pk_{a,c} is a randomization of the master public key pk_m. Choose randomizer r_a\in\mathbb{Z}_q, and define address basepoint G_a = [r_a]G, and C_{a,i}:=[r_a]C_i, then
pk_{a,c}:=(G_a,C_{a,0},\ldots,C_{a,t})\in\mathbb{G}^{t+2}.
Note that pk_{a,c}= (G_a,[c_0]G_a,\ldots,[c_t]G_a). Thus, it encodes the secret polynomial \tilde{p}(X) using address basepoint G_a.
- FMD public key. The uncompressed FMD public key for address a are the evaluations of \tilde{p}(X) “in the exponent” using basepoint G_a. Namely if P_{a,i} = [\tilde{p}(x_i)]G_a, then
pk_{a,f} := (P_{a,1},\ldots,P_{a,\gamma})\in\mathbb{G}^{\gamma}
Public derivation
The uncompressed FMD public key pk_{a,f} is obtained evaluating the encoded polynomial in pk_{a,c} at public points x_1,\ldots,x_\gamma. Concretely:
P_{a,i} = \sum_{k=0}^t [x_i^k]C_{a,k}
for all i\leq\gamma.
Diversification
All FMD public keys pk_{a,f} derived from the same master secret key sk_m:=\tilde{p}(X) are associated with the same FMD secret key sk_f := (s_1,\ldots,s_\gamma), where s_i = \tilde{p}(x_i). This is because, as noted, each compressed public key pk_{a,c} encodes \tilde{p}(X) using basepoint G_a.
Batch-diversification
It may be desirable to not have all the set of m addresses controlled by the same FMD secret keys, but yet controlled by the same master secret/public keys. This protects against potential leakage of sk_f.
We can achieve this by evaluating pk_m at distinct set of public evaluation points (x_1,\ldots,x_\gamma), (x'_1,\ldots,x'_\gamma). Each batch would yield different FMD secret keys sk_f := (\tilde{p}(x_1),\ldots,\tilde{p}(x_\gamma)), sk'_f := (\tilde{p}(x'_1),\ldots,\tilde{p}(x'_\gamma)).
Dynamic choice of \gamma
The maximum false-positive detection rate 2^{-\gamma} can be chosen by the sender at the moment of sending the message – i.e. at the moment of creating the FMD flag ciphertexts. This is because it can evaluate the compressed public key pk_c at arbitrarily many public evaluation points x_i.
Flow diagram
pk_m = (C_0,\ldots,C_t) \stackrel{\stackrel{\text{ compressed public keys}}{\text{randomize}}}{\longrightarrow}
\begin{cases}
& \mathsf{addr_1}: pk_{1,c}:=(G_1,C_{1,0},\ldots,C_{1,t}) \\
& \vdots\\
& \mathsf{addr_m}: pk_{m,c}:=(G_m,C_{m,0},\ldots,C_{m,t})
\end{cases}
\stackrel{\stackrel{\text{ uncompressed FMD public keys}}{\text{evaluate in the exponent}}}{\longrightarrow}
\begin{cases}
& \mathsf{addr_1}: pk_{f,1}:=(P_{1,1},\ldots,P_{1,\gamma_1}) \\
& \vdots\\
& \mathsf{addr_m}: pk_{f,m}:=(P_{m,1},\ldots,P_{m,\gamma_m})
\end{cases}
\text{ possibly } \gamma_i\neq\gamma_j
Unlinkability
If the DDH problem is hard in group \mathbb{G}, then the master public key pk_m and any set of m compressed public keys pk_{a,c}:=([r_a]G,[r_ac_0]G,\ldots,[r_ac_t]G) look unrelated.
Let addresses a ranging 1\ldots m. By the DDH assumption, we have that for any coefficient c_i it holds
(G,[c_i]G,[r_1]G,[r_1c_i]G,\ldots,[r_m]G,[r_mc_i]G)\approx (G,[c_i]G,[r_1]G,R_1,\ldots,[r_m]G,R_m),
for random points R_j.
Tradeoffs: key-recovery threshold and address size
Note: This is is a threshold scheme. If more than t FMD secret keys are leaked, then the master secret key can be recovered.
For example, if t=2, then addresses only need to have 3 points in \mathbb{G} for the compressed public key pk_{a,c}. However, if 3 FMD secret keys s_{i_1},s_{i_2},s_{i_3} are leaked from sk_f, then can recover all the other FMD secret keys s_{i_j} for 1\leq j\leq \gamma (with Lagrange interpolation can recover the 2-degree secret polynomial \tilde{p}(X)).
In general, with t+2 points in addresses need to leak at least t+1 FMD secret keys. Esentially, we are using Shamir secret sharing to generate each secret key s_i, so any set of t or less s_i leak no information whatsover about the secret polynomial \tilde{p}(X).
So larger t yields better security but larger addresses.
Impact in FMD2 implementation
The modifications of the FMD2 scheme are minimal. The only modification is that the basepoint is not common to all users/addresses: when flagging and testing for address a, the base point G_a (included in pk_{a,c}) must be used.