In the FMD1 and FMD2 constructions of Fuzzy Message Detection, to achieve a minimum false-positive rate p=2^{-\gamma}, the number of ElGamal public keys is \gamma.
If for example we fix \gamma = 16 and ElGamal encryption is instantiated over any popular 256-bit ellitpic curve, then the size of the FMD public key is 1KB. Larger choices of \gamma yield even larger public keys.
Question: How can we reduce the size of the public keys while maintaining the same minimum false-positive rate?
This will improve the efficiency of the FMD test run inside the TEEs in the FMD-TEE proposal, and would make generation of ZKPs for flag consistency less expensive.
A (partial) solution that minimizes communication bandwidth is to derive the \gamma public keys from a master public key. Only the master public key needs to be communicated with senders.
For the FMD1 or FMD2 schemes , the public keys are elliptic curve points. A BIP32-like derivation can then be done.
The key owner (receiver) initially does \gamma derivations parent private key → child private key to generate the \gamma kepypairs (sk_i,pk_i)_{i\leq\gamma} from a master secret key sk_m.
The key owner transmits (makes public) the master public key pk:=sk_m\cdot G
The sender does \gamma derivations parent public key → child public key to recover the \gamma public keys (pk_i)_{i\leq\gamma} from the master public key pk_m.
Above G denotes a fixed generator of the cyclic group where the FMD scheme is instantiated. It will hold pk_i = sk_i\cdot G for all i\leq\gamma.
This solution only partially answers the question because it does not improve the efficiency of the FMD test.