Constructing S-FMD

The original FMD paper provides three constructions of R-FMD. The first two realize functionality for restricted false-positive probabilities of the form ; the third supports arbitrary fractional probabilities using a much more complex and expensive construction.

The first two schemes, R-FMD1 and R-FMD2, 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 R-FMD2, which provides more compact ciphertexts and chosen-ciphertext security.

In this section, we:

  • recall the construction of R-FMD2, changing notation from the paper;
  • adapt R-FMD2 to S-FMD2, which provides sender FMD instead of receiver FMD;
  • extend S-FMD2 to support diversified detection, allowing multiple, unlinkable flag keys to be detected by a single detection key;
  • extend S-FMD2 to use deterministic derivation, allowing 32-byte flag and detection keys to support arbitrary-precision false positive probabilities;
  • summarize the resulting construction and describe how it can be integrated with the Sapling key heirarchy.

The R-FMD2 construction

First, we recall the paper’s construction of R-FMD2, changing from multiplicative to additive notation and adjusting variable names to be consistent with future extensions.

The construction supports restricted false positive values for , a global parameter determining the minimum false positive rate. is a group of prime order and and are hash functions.

R-FMD2/KeyGen

Choose a generator . For , choose and compute . Return the root key and the flag key .

R-FMD2/Extract

On input and root key , parse and return as the detection key.

R-FMD2/Flag

On input , first parse , then proceed as follows:

  1. Choose and compute .
  2. Choose and compute .
  3. For each , compute
    1. a key bit ;
    2. a ciphertext bit .
  4. Compute .
  5. Compute .

Return the flag ciphertext .

R-FMD2/Test

On input , , first parse , , then proceed as follows:

  1. Compute .
  2. Recompute as .
  3. For each , compute
    1. a key bit ;
    2. a plaintext bit .

If all plaintext bits , return (match); otherwise, return .

To see that the Test procedure detects true positives, first note that since and , so the detector will recompute the used by the sender; then, since , the detector’s is the same as the sender’s .

On the other hand, if the ciphertext was created with a different flag key, the resulting will be random bits, giving the desired 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 and nonce commitment . The points are included in the ElGamal hash, ensuring that any change to either will result in a random bit on decryption. The pair act as a public key and signature for a one-time signature on the ciphertext as follows: the sender constructs the point as the output of a chameleon hash with basis on input , then uses the hash trapdoor (i.e., their knowledge of the discrete log relation ) to compute a collision involving , a hash of the rest of the ciphertext. The collision acts as a one-time signature with public key .

The fact that the generator 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 is a global parameter.

From R-FMD2 to S-FMD2

Changing this construction to the S-FMD model is fairly straightforward: rather than having the sender encrypt bits of the Bloom filter and only allow the detector to decrypt of them, we have the sender only encrypt 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 S-FMD 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 S-FMD2 construction then works as follows:

S-FMD2/KeyGen

For , choose and compute . Return the detection key and the flag key .

S-FMD2/Flag

On input flag key , first parse , then proceed as follows:

  1. Choose and compute .
  2. Choose and compute .
  3. For each , compute
    1. a key bit ;
    2. a ciphertext bit .
  4. Compute .
  5. Compute .

Return the flag ciphertext .

S-FMD2/Test

On input detection key and flag ciphertext , first parse and , then proceed as follows:

  1. Compute .
  2. Recompute as .
  3. For each , compute
    1. a key bit ;
    2. a plaintext bit .

If all plaintext bits , return (match); otherwise, return .

The value of is included in the ciphertext hash to ensure that the encoding of the ciphertext bits is non-malleable. Otherwise, the construction is identical.

Diversified detection: from S-FMD2 to S-FMD2-d

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 group-valued 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 S-FMD2, but some modifications to the tag mechanism are required to avoid use of the basepoint in the Test procedure.

Let be the set of diversifiers, and let be a group-valued hash function. At a high level, our goal is to replace use of a common basepoint with a diversified basepoint for some .

Our goal is to have diversified flag keys, so we first replace by in KeyGen, so that and the components of the flag key are parameterized by the diversifier . The sender will compute the key bits as and the receiver computes them as If instead of , then and the middle component will match.

But then the sender needs to construct as in order to have a known discrete log relation between and . This is a problem, because is recomputed by the receiver, but if the receiver must recompute it as , 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 , so the receiver’s computation involves the basepoint . To avoid it, we can use a basis , where . is used in place of , but is computed as , i.e., as the chameleon hash . The sender’s collision then becomes , allowing the detector to recompute as The point 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 (diversifier-dependent) from generation of detection keys:

S-FMD2-d/KeyGen

For , choose , and return the detection key .

S-FMD2-d/Diversify

On input detection key and diversifier , first parse . Then compute the diversified base , and use it to compute . Return the diversified flag key .

S-FMD2-d/Flag

On input diversified flag key and diversifier , first parse , then proceed as follows:

  1. Compute the diversified base .
  2. Choose and compute .
  3. Choose and compute .
  4. Choose and compute .
  5. For each , compute
    1. a key bit ;
    2. a ciphertext bit .
  6. Compute .
  7. Compute .

Return the flag ciphertext .

S-FMD2-d/Test

On input detection key and flag ciphertext , first parse and , then proceed as follows:

  1. Compute .
  2. Recompute as .
  3. For each , compute
    1. a key bit ;
    2. a plaintext bit .

If all plaintext bits , return (match); otherwise, return .

Deterministic flag key generation

One remaining obstacle is the size of the flag keys. A flag key supporting false positive probabilities down to requires group elements; for instance, supporting probabilities down to with a 256-bit group requires 448-byte 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 . Then given a parent keypair , child keys can be derived as with . 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 should be domain-separated.

Applying this to S-FMD2, the scalar becomes the compact detection key, and the point becomes the compact flag key. The full detection key can be derived from the compact detection key , and the full flag key can be derived from the compact flag key . 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 S-FMD setting, not the R-FMD setting, because S-FMD 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 and any child secret , it’s possible to recover the parent secret and therefore the entire subtree of secret keys. Thus, it cannot be used for R-FMD, 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 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
    • 32-byte compact flag keys are probably workable, 320-448 byte full flag keys are probably not.