Forward secrecy in the context of the FMD-based sync solution states:
If the adversary corrupts a detection server at time t_c, the identity of recipients of messages sent at some past time t<t_c is not leaked.
We can achieve it by rotating detection keys from time to time.
User-enforced key rotation
Depending on scenarios, asking receivers to refresh their keys may be a burden. For example, if the receiver FMD public keys is hard-coded in addresses
- at each refresh new addresses need to be generated and published,
- senders neeed to make sure they are using the latest address for every user they want to communicate with.
Further, it is responsability of the users to rotate their own keys, so no key rotation might hapen at all.
System-enforced key rotation
The idea is that detection servers handle the key rotation process periodically, i.e. say every m batches of messages, and in the background, i.e. what is rotated is their own keys.
For this to work, FMD flag ciphertexts \vec{f}:=(u,y,c_1,\ldots,c_\gamma) are generated using an extra FMD public key pk_S:=(h_{S,1},\ldots,h_{S,\gamma}) owned by the detection server S, i.e. the detection server knows the private keys sk_S:=(x_{S,1},\ldots,x_{S,\gamma}) such that h_{S,i} = g^{x_{S,i}}. To generate each ciphertext bit c_i, an extra DDH mask h_{S,i}^{s_{S}} is also hashed, where s_S is fresh randomness. See below for the details.
Detection-ambiguity. The modified scheme retains detection-ambiguity. Although the same server FMD key is used for all receivers, FMD flags for different receivers still use different FMD (user) keys.
Liveness. The server FMD keyapir does not need to be associated with a particular server identity. If there are multiple servers, they will use the same FMD keypair (sk_S,pk_S). If one server goes offline, it is still possible to do FMD detection.
Server-side communication However, communication between the server is necessary at two moments:
- When a new detection server joins the system. The new joiner contacts an existing server to receive the current FMD keypair
- When the FMD keypair is rotated. For example, an elected leader generates and broadcast the keypair to the rest. The choice of the leader should be done randomly. This prevents malicious leader to re-use old keypairs and break forward secrecy.
Modifications to the original scheme
We highlight in bold the modifications to the original flag and test algorithms of the FMD2 scheme of the original paper.
The modifications require \gamma+1 extra group exponentiations during FMD flag generation, and n extra exponentiations during the FMD test. The flag ciphertext is augmented with one extra point v.
Flag
Input:
- Receiver public key pk:=(h_1,\ldots,h_\gamma)\in\mathbb{G}^\gamma
- Server public key pk_S:=(h_{S,1},\ldots,h_{S,\gamma})\in\mathbb{G}^\gamma.
- Sample random r,\mathbf{s},z,\gets\mathbb{Z}_q
- u:=g^r,\mathbf{v:=g^s}, w:=g^z
- For 1\leq i\leq \gamma do:
a. k_i := H(u,\mathbf{v},h_i^r,\mathbf{h_{S,i}^s},w) // Hash to \mathbb{Z}_2
b. c_i:=k_i+1 // Arithmetic in \mathbb{Z}_2 - m:=G(u,\mathbf{v},c_1,\ldots,c_\gamma) // Hash to \mathbb{Z}_q
- y:=(z-m)r^{-1} // Arithmetic in field \mathbb{Z}_q
- Output flag ciphertexts \vec{f}:=(u,\mathbf{v},y,c_1,\ldots,c_\gamma)
Test
Inputs:
- Receiver detection key dsk:=(x_{1},\ldots,x_{n})\in\mathbb{Z}_q^n for some n\leq\gamma
- Server detection key dsk_S:=(x_{S,1},\ldots,x_{S,n})\in\mathbb{Z}_q^n
- Flag ciphertexts \vec{f}:=(u,\mathbf{v},y,c_1,\ldots,c_\gamma)\in\mathbb{G}\boldsymbol{\times\mathbb{G}}\times\mathbb{Z}_q\times\mathbb{Z}_2^\gamma
- m:=G(u,\mathbf{v},c_1,\ldots,c_\gamma) // Hash to \mathbb{Z}_q
- w:=g^m\cdot u^y
- For 1\leq i \leq n do:
a. k_i := H(u,\mathbf{v},u^{x_{i}},\mathbf{v^{x_{S,i}}},w) // Hash to \mathbb{Z}_2
b. b_i:=k_{i}+c_{i} // Arithmetic in \mathbb{Z}_2 - If all b_i=1 output \mathsf{accept}. Else, output \mathsf{reject}.