Constructing SFMD
The original FMD paper provides three constructions of RFMD. The first two realize functionality for restricted falsepositive probabilities of the form $p=2_{−n}$; the third supports arbitrary fractional probabilities using a much more complex and expensive construction.
The first two schemes, RFMD1 and RFMD2, are constructed similarly to a Bloom
filter: the Flag
procedure encrypts a number of 1
bits, and the Test
procedure uses information in a detection key to check whether some subset of
them are 1
, returning true
if so and false
otherwise. The false positive
probability is controlled by extracting only a subset of the information in the
root key into the detection key, so that it can only check a subset of the bits
encoded in the flag ciphertext. We focus on RFMD2, which provides more compact
ciphertexts and chosenciphertext security.
In this section, we:
 recall the construction of RFMD2, changing notation from the paper;
 adapt RFMD2 to SFMD2, which provides sender FMD instead of receiver FMD;
 extend SFMD2 to support diversified detection, allowing multiple, unlinkable flag keys to be detected by a single detection key;
 extend SFMD2 to use deterministic derivation, allowing 32byte flag and detection keys to support arbitraryprecision false positive probabilities;
 summarize the resulting construction and describe how it can be integrated with the Sapling key heirarchy.
The RFMD2 construction
First, we recall the paper’s construction of RFMD2, changing from multiplicative to additive notation and adjusting variable names to be consistent with future extensions.
The construction supports restricted false positive values $p=2_{−n}$ for $n≤γ$, a global parameter determining the minimum false positive rate. $G$ is a group of prime order $q$ and $H_{1}:G_{3}→{0,1}$ and $H_{2}:G×{0,1}_{γ}→Z_{q}$ are hash functions.
RFMD2/KeyGen
Choose a generator $B$ G$. For $i=1,…,γ$, choose $x_{i}$ Z_{q}$ and compute $X_{i}=[x_{i}]B$. Return the root key $rk←(x_{1},…,x_{γ})$ and the flag key $fk←(B,X_{1},…,X_{γ})$.
RFMD2/Extract
On input $p=2_{−n}$ and root key $rk$, parse $(x_{1},…,x_{γ})←rk$ and return $(x_{1},…,x_{n})$ as the detection key.
RFMD2/Flag
On input $fk$, first parse $(B,X_{1},…,X_{n})←fk$, then proceed as follows:
 Choose $r$ Z_{q}$ and compute $P←[r]B$.
 Choose $z$ Z_{q}$ and compute $Q←[z]B$.
 For each $i=1,…,γ$, compute
 a key bit $k_{i}←H_{1}(P∣∣[r]X_{i}∣∣Q)$;
 a ciphertext bit $c_{i}←k_{i}⊕1$.
 Compute $m←H_{2}(P∣∣c_{1}∣∣⋯∣∣c_{γ})$.
 Compute $y←(z−m)r_{−1}$.
Return the flag ciphertext $fc←(P,y,c_{1},…,c_{γ})$.
RFMD2/Test
On input $dk$, $fc$, first parse $(x_{1},…,x_{n})←dk$, $(P,y,c_{1},…,c_{γ})←fc$, then proceed as follows:
 Compute $m←H_{2}(P∣∣c_{1}∣∣⋯∣∣c_{γ})$.
 Recompute $Q$ as $Q←[y]P+[m]B$.
 For each $i=1,…,γ$, compute
 a key bit $k_{i}←H_{1}(P∣∣[x_{i}]P∣∣Q)$;
 a plaintext bit $b_{i}←c_{i}⊕k_{i}$.
If all plaintext bits $b_{i}=1$, return $1$ (match); otherwise, return $0$.
To see that the Test
procedure detects true positives, first note that
since $P=[r]B$ and $y=(z−m)r_{−1}$,
$Q =[y]P+[m]B=[(z−m)r_{−1}][r]B+[m]B=[z]B, $
so the detector will recompute the $Q$ used by the sender; then, since $[r]X_{i}=[r][x_{i}]B=[x_{i}]P$, the detector’s $k_{i}←H_{1}(P∣∣[x_{i}]P∣∣Q)$ is the
same as the sender’s $k_{i}←H_{1}(P∣∣[r]X_{i}∣∣Q)$.
On the other hand, if the ciphertext was created with a different flag key, the resulting $k_{i}$ will be random bits, giving the desired $2_{−n}$ false positive probability.
One way to understand the components of the construction is as follows: the message consists of $γ$ bits of a Bloom filter, each encrypted using hashed ElGamal with a common nonce $r$ and nonce commitment $P=[r]B$. The points $P,Q$ are included in the ElGamal hash, ensuring that any change to either will result in a random bit on decryption. The pair $(Q,y)$ act as a public key and signature for a onetime signature on the ciphertext as follows: the sender constructs the point $Q$ as the output of a chameleon hash with basis $(P,B)$ on input $(0,z)$, then uses the hash trapdoor (i.e., their knowledge of the discrete log relation $P=[r]B$) to compute a collision $(y,m)$ involving $m$, a hash of the rest of the ciphertext. The collision $y$ acts as a onetime signature with public key $Q$.
The fact that the generator $B$ was selected at random in each key generation is not used by the construction and doesn’t seem to play a role in the security analysis; in fact, the security proof in Appendix F has the security game operate with a common generator. In what follows, we instead assume that $B$ is a global parameter.
From RFMD2 to SFMD2
Changing this construction to the SFMD model is fairly straightforward: rather
than having the sender encrypt $γ$ bits of the Bloom filter and only allow
the detector to decrypt $n≤γ$ of them, we have the sender only encrypt
$n≤γ$ bits of the Bloom filter and allow the detector to decrypt all
potential bits. As noted in the previous
section, this means that in the SFMD context,
there is no separation of capability between the root key and the detection key.
For this reason, we skip the Extract
algorithm and (conceptually) merge the
root key into the detection key.
The SFMD2 construction then works as follows:
SFMD2/KeyGen
For $i=1,…,γ$, choose $x_{i}$ Z_{q}$ and compute $X_{i}=[x_{i}]B$. Return the detection key $dk←(x_{1},…,x_{γ})$ and the flag key $fk←(X_{1},…,X_{γ})$.
SFMD2/Flag
On input flag key $fk$, first parse $(X_{1},…,X_{n})←fk$, then proceed as follows:
 Choose $r$ Z_{q}$ and compute $P←[r]B$.
 Choose $z$ Z_{q}$ and compute $Q←[z]B$.
 For each $i=1,…,n$, compute
 a key bit $k_{i}←H_{1}(P∣∣[r]X_{i}∣∣Q)$;
 a ciphertext bit $c_{i}←k_{i}⊕1$.
 Compute $m←H_{2}(P∣∣n∣∣c_{1}∣∣⋯∣∣c_{n})$.
 Compute $y←(z−m)r_{−1}$.
Return the flag ciphertext $fc←(P,y,c_{1},…,c_{n})$.
SFMD2/Test
On input detection key $dk$ and flag ciphertext $fc$, first parse $(x_{1},…,x_{γ})←dk$ and $(P,y,c_{1},…,c_{n})←fc$, then proceed as follows:
 Compute $m←H_{2}(P∣∣n∣∣c_{1}∣∣⋯∣∣c_{n})$.
 Recompute $Q$ as $Q←[y]P+[m]B$.
 For each $i=1,…,n$, compute
 a key bit $k_{i}←H_{1}(P∣∣[x_{i}]P∣∣Q)$;
 a plaintext bit $b_{i}←c_{i}⊕k_{i}$.
If all plaintext bits $b_{i}=1$, return $1$ (match); otherwise, return $0$.
The value of $n$ is included in the ciphertext hash to ensure that the encoding of the ciphertext bits is nonmalleable. Otherwise, the construction is identical.
Diversified detection: from SFMD2 to SFMD2d
The Sapling design provides viewing keys that support diversified addresses: a collection of publicly unlinkable addresses whose activity can be scanned by a common viewing key. For integration with Sapling, as well as other applications, it would be useful to support diversified detection: a collection of publicly unlinkable diversified flag keys that share a common detection key. This collection is indexed by data called a diversifier; each choice of diversifier gives a different diversified flag key corresponding to the same detection key.
In the Sapling design, diversified addresses are implemented by selecting the basepoint of the key agreement protocol as the output of a groupvalued hash function whose input is the diversifier. Because the key agreement mechanism only makes use of the secret key (the incoming viewing key) and the counterparty’s ephemeral public key, decryption is independent of the basepoint, and hence the choice of diversifier, allowing a common viewing key to decrypt messages sent to any member of its family of diversified transmission (public) keys.
A similar approach can be applied to SFMD2, but some modifications to the tag
mechanism are required to avoid use of the basepoint in the Test
procedure.
Let $D$ be the set of diversifiers, and let $H_{3}:D→G$ be a groupvalued hash function. At a high level, our goal is to replace use of a common basepoint $B$ with a diversified basepoint $B_{d}=H_{3}(d)$ for some $d∈D$.
Our goal is to have diversified flag keys, so we first replace $B$ by $B_{d}$ in
KeyGen
, so that $X_{i}=[x_{i}]B_{d}$ and the components of the flag key are
parameterized by the diversifier $d$. The sender will compute the key bits as
$k_{i}←H_{1}(P∣∣[r]X_{i}∣∣Q),$
and the receiver computes them as
$k_{i}←H_{1}(P∣∣[x_{i}]P∣∣Q).$
If $P=[r]B_{d}$ instead of $P=[r]B$, then $[x_{i}]P=[r]X_{i}$ and the middle
component will match.
But then the sender needs to construct $Q$ as $Q←[z]B_{d}$ in order to have a known discrete log relation between $P$ and $Q$. This is a problem, because $Q$ is recomputed by the receiver, but if the receiver must recompute it as $Q←[y]P+[m]B_{d}$, detection is bound to the choice of diversifier, and we need detection to be independent of the choice of diversifier.
The root of this problem is that the chameleon hash uses basis $(P,B)$, so the receiver’s computation involves the basepoint $B$. To avoid it, we can use a basis $(P_{1},P_{2})$, where $P_{i}←[r_{i}]B$. $P_{1}$ is used in place of $P$, but $Q$ is computed as $[z]P_{2}$, i.e., as the chameleon hash $⟨(0,z),(P_{1},P_{2})⟩$. The sender’s collision then becomes $y←(z−m)r_{1}r_{2} $, allowing the detector to recompute $Q$ as $Q←=== [y]P_{1}+[m]P_{2}[(z−m)r_{1}r_{2} ][r_{1}]B+[m]P_{2}[z−m]P_{2}+[m]P_{2}[z]P_{2}. $ The point $P_{2}$ must be included in the flag ciphertext, increasing its size, but detection no longer involves use of a basepoint (diversified or otherwise).
Concretely, this mechanism works as follows, splitting out generation of flag keys (diversifierdependent) from generation of detection keys:
SFMD2d/KeyGen
For $i=1,…,γ$, choose $x_{i}$ Z_{q}$, and return the detection key $dk←(x_{1},…,x_{γ})$.
SFMD2d/Diversify
On input detection key $dk$ and diversifier $d$, first parse $(x_{1},…,x_{γ})←dk$. Then compute the diversified base $B_{d}←H_{3}(d)$, and use it to compute $X_{i}=[x_{i}]B_{d}$. Return the diversified flag key $fk_{d}←(X_{1},…,X_{γ})$.
SFMD2d/Flag
On input diversified flag key $fk_{d}$ and diversifier $d$, first parse $(X_{1},…,X_{n})←fk_{d}$, then proceed as follows:
 Compute the diversified base $B_{d}←H_{3}(d)$.
 Choose $r_{1}$ Z_{q}$ and compute $P_{1}←[r]B_{d}$.
 Choose $r_{2}$ Z_{q}$ and compute $P_{2}←[r]B_{d}$.
 Choose $z$ Z_{q}$ and compute $Q←[z]P_{2}$.
 For each $i=1,…,n$, compute
 a key bit $k_{i}←H_{1}(P_{1}∣∣P_{2}∣∣[r]X_{i}∣∣Q)$;
 a ciphertext bit $c_{i}←k_{i}⊕1$.
 Compute $m←H_{2}(P_{1}∣∣P_{2}∣∣n∣∣c_{1}∣∣⋯∣∣c_{n})$.
 Compute $y←(z−m)r_{1}r_{2} $.
Return the flag ciphertext $fc←(P_{1},P_{2},y,c_{1},…,c_{n})$.
SFMD2d/Test
On input detection key $dk$ and flag ciphertext $fc$, first parse $(x_{1},…,x_{γ})←dk$ and $(P_{1},P_{2},y,c_{1},…,c_{n})←fc$, then proceed as follows:
 Compute $m←H_{2}(P_{1}∣∣P_{2}∣∣n∣∣c_{1}∣∣⋯∣∣c_{n})$.
 Recompute $Q$ as $Q←[y]P_{1}+[m]P_{2}$.
 For each $i=1,…,n$, compute
 a key bit $k_{i}←H_{1}(P_{1}∣∣P_{2}∣∣[x_{i}]P∣∣Q)$;
 a plaintext bit $b_{i}←c_{i}⊕k_{i}$.
If all plaintext bits $b_{i}=1$, return $1$ (match); otherwise, return $0$.
Deterministic flag key generation
One remaining obstacle is the size of the flag keys. A flag key supporting false positive probabilities down to $2_{−γ}$ requires $γ$ group elements; for instance, supporting probabilities down to $2_{−14}=1/16384$ with a 256bit group requires 448byte flag keys. It would be much more convenient to have smaller keys.
One way to do this is to use a deterministic key derivation mechanism similar to BIP32 to derive a sequence of child keypairs from a single parent keypair, and use that sequence as the components of a flag / detection keypair. To do this, we define a hash function $H_{4}:G×Z→Z_{q}$. Then given a parent keypair $(x,X=[x]B)$, child keys can be derived as $x_{i}X_{i} ←x+H_{4}(X∣∣i)←X+[H_{4}(X∣∣i)]B $ with $X_{i}=[x_{i}]B$. Unlike BIP32, there is only one sequence of keypairs, so there is no need for a chain code to namespace different levels of derivation, although of course the hash function $H_{4}$ should be domainseparated.
Applying this to SFMD2, the scalar $x$ becomes the compact detection key, and the point $X$ becomes the compact flag key. The full detection key $(x_{1},…,x_{γ})$ can be derived from the compact detection key $x$, and the full flag key $(X_{1},…,X_{γ})$ can be derived from the compact flag key $X$. In addition, it is no longer necessary to select the minimum false positive probability as a global parameter $γ$ prior to key generation, as the compact keys can be extended to arbitrary length (and thus arbitrary false positive probabilities).
Deterministic derivation is only possible in the SFMD setting, not the RFMD setting, because SFMD does not require any separation of capability between the component keys used for each bit of the Bloom filter. Public deterministic derivation does not allow separation of capability: given $X$ and any child secret $x_{i}$, it’s possible to recover the parent secret $x$ and therefore the entire subtree of secret keys. Thus, it cannot be used for RFMD, where the detection key is created by disclosing only some of the bits of the root key.
Unfortunately, this optimization does not seem to be possible to combine with diversified detection. The detection key components $x_{i}$ must be derived from the parent secret and (the hash of) public data, but diversified detection requires that different public data (flag keys) have the same detection key components.
 Is there some clever way to sidestep this issue? seems somewhat fundamental.
Sapling Integration
 Pick diversified detection XOR deterministic flag key generation

Addresses include a flag key / compact flag key
 32byte compact flag keys are probably workable, 320448 byte full flag keys are probably not.