ZKPs for FMD flag consistency

Cryptography Zoo Shielded State Sync
1

Context

A proposal for the private state synchronization problem using Fuzzy Message Detection (FMD) and Trusted Execution Environments (TEEs) is put forward in this thread.

To send message m to user \mathsf{uid}, the idea is to attach to m a ciphertext flag \vec{f} generated with an FMD public key pk_\mathsf{{fmd}} associated to the receiver identity \mathsf{uid}. \vec{f} is tested with the detection keys associated to pk_\mathsf{{fmd}} to filter out irrelevant messages.

The novelty being in that the detection keys are handed to TEEs to mitigate key leakage, and, with a very minor modification of the FMD test, we can set large false-positive rates at each TEE for increased privacy, but, by combining their filtered output, achieve low overall false-positive rates in the resulting system.

What problems can arise?

When the anoma Resource Machine is shielded, the message m consists of encrypted data in the valueRef field of the resource object, and it is sent anonymously to the receiver with, say, user identifier \mathsf{uid}.

There are at least two problems that arise when senders (resource owners) delegate the creation of the resource to untrusted solvers (resource creators). The fact the transfer is anonymous just makes things more complicated.

Problem 1: The rightful receiver problem. A sender asks a solver: ‘‘here is the plaintext message pt, please send it to user \mathsf{uid}’’. How can we enforce the solver sends pt to \mathsf{uid}?

Note that it is the sender who needs to convinced. Indeed, only the sender should know the right (anonymous) receiver. Therefore, if we were to solve this problem using ZKPs somehow, then it must be the sender who verifies the proof.

This post is NOT about this problem.

Problem 2: The flag consistency problem. A solver misbehaves and sends an encrypted message m inconsistent with the FMD flag ciphertexts \vec{f}. Thus, the message is addressed to the rigth user \mathsf{uid}, but flag \vec{f} is generated with the FMD public key pk'_{\mathsf{fmd}} of a different user \mathsf{uid}'.

Messages with inconsistent flags are potentially filtered out during the FMD test. Thus, whereas a full scan retrieves the inconsistent message addressed to user \mathsf{uid}, a filtered scan may not. To some extent, this desincentives users to use any efficient FMD-based solution to retrieve their messages, and be stuck with the inefficient full scan and trial-decrypt solution.

Note. The rightful receiver and the flag consistency problems above can be subsumed under the sound delegation problem, which asks how can we enforce untrusted solvers to behave honestly when creating resources. Thus, any solution to either of the former problems can be used to build a solution to the (more general) latter problem.

Solving the flag consistency problem

I will not provide a specific solution. Instead I will describe a generic approach. If we believe it makes sense, then we can think about how to make it concrete, and how to optimize it.

User identities and public keys

Clearly, user public keys must be somehow publicly associated to the user identity \mathsf{uid}. This applies to both

  • verifiable encryption public keys pk_\mathsf{ve} in the shielded RM,
  • and FMD public keys pk_\mathsf{fmd}.

Otherwise, senders/solvers would not know what keys they should use.

For example, such association forms the basis of the trial-decrypt message retrieval. Users decrypt the candidate ciphertext and check whether that yields something meaningful. This works for the obvious reason. If user \mathsf{uid} has verifiable encryption keypair (sk_\mathsf{ve},pk_\mathsf{ve}), and the ciphertext ct is encrypted under pk'_\mathsf{ve}, then m:=\mathsf{Dec}_{sk_\mathsf{ve}}(ct) is likely to be meaningless if pk_\mathsf{ve}\neq pk'_\mathsf{ve}.

A failed (or incomplete) solution

In this thread reply an attempt to solve the consistency problem is sketched. Unfortunately, it does not seem work.

The suggestion was to encrypt the FMD public key pk_\mathsf{fmd} inside the verifiable ciphertext ct that contains the message. The informally given NP statement therein was (slightly rephrased to align notation):

The cursive highlights the problem: a misbehaving encryptor (e.g. solver) could encrypt a different FMD key pk'_\mathsf{fmd} corresponding to another user \mathsf{uid}' and prove that. So we are back to square one.

Linking public keys

The root problem in the failed attempt above is that there is no link between the FMD public key pk_\mathsf{fmd} and the verifiable encryption public key pk_\mathsf{ve}. What I mean is that, even though they are associated to the same user, there is no programatic link between both keys.

Without such link, I do not see an obvious way to guarantee that an untrusted encryptor (e.g. solver) uses keys for the same user. So we are going to consider a specific linking strategy that ties together both public keys. A user with identifier \mathsf{uid} is publicly associated with a master public key pk_M. There are two key derivation processes

(sk_M,pk_M) \stackrel{\mathsf{deriveVE}}{\longrightarrow}(sk_\mathsf{ve},pk_\mathsf{ve}),

and

(sk_M,pk_M) \stackrel{\mathsf{deriveFMD}}{\longrightarrow}(sk_\mathsf{fmd},pk_\mathsf{fmd}).

For now, let us leave undefined the key derivation processes \mathsf{deriveVE}, \mathsf{deriveFMD}. We just assume they take as part of their inputs the user master keypair (sk_M,pk_M).

A working generic solution

The idea is to generate a ZKP to attest to the consistency between the verifiable encryption public key and the FMD public key. Thus, to attest that both keys are linked in the way explained above, and hence belong to the same user.

Concretely, a ZKP for the following NP relation:

\mathcal{R}_{FC}:= \left\{ \begin{align} &(ct,\vec{f});(sk_M,pk_M,m,sk_\mathsf{fmd},pk_\mathsf{fmd},sk_\mathsf{ve},pk_\mathsf{ve},r_1,r_2) \text{ such that:}\\ &\qquad ct = \mathsf{Enc}_{pk_\mathsf{ve}}(m;r_1)\\ &\qquad \vec{f} = \mathsf{FMD.Flag}(pk_\mathsf{fmd};r_2)\\ &\qquad (sk_\mathsf{ve},pk_\mathsf{ve}) = \mathsf{deriveVE}(sk_M,pk_M)\\ &\qquad (sk_\mathsf{fmd},pk_\mathsf{fmd}) = \mathsf{deriveFMD}(sk_M,pk_M) \end{align} \right\}.

The instance (public input) of the relation is the pair (ct,\vec{f}). The verifiable encryption ciphertext and the FMD flag ciphertexts.

The witness (private input) of the relation is the user master keypair, the verifiable encryption keypair, the FMD keypair, the message, and the randomness to encrypt and generate the flag. The tuple (sk_M,pk_M,m,sk_\mathsf{fmd},pk_\mathsf{fmd},sk_\mathsf{ve},pk_\mathsf{ve},r_1,r_2).

Note that no information about the user \mathsf{uid} is leaked in the instance (ct,\vec{f}), nor in the zero-knowledge proof \pi_{FC}. This is because the three public keys (master, verifiable encryption, and FMD) are passed as witness, the verifiable encryption scheme is key-private, and the FMD scheme is detection-ambiguous.

Commit-and-prove approach

Let \mathsf{commit} be a binding and hiding commitment scheme with fixed commitment key pk_C. The relation \mathcal{R}_{FC} can be broken in two, provided we include a commitment to the master public key in the instances. One relation for the statements regarding verifiable encryption:

\mathcal{R}_{VE}:= \left\{ \begin{align} &(pk_C,c,ct);(sk_M,pk_M,m,sk_\mathsf{ve},pk_\mathsf{ve},r_0,r_1) \text{ such that:}\\ &\qquad c = \mathsf{commit}_{pk_C}(pk_M;r_0)\\ &\qquad ct = \mathsf{Enc}_{pk_\mathsf{ve}}(m;r_1)\\ &\qquad (sk_\mathsf{ve},pk_\mathsf{ve}) = \mathsf{deriveVE}(sk_M,pk_M)\\ \end{align} \right\},

and another relation for the statements regarding FMD flag generation:

\mathcal{R}_{FMD}:= \left\{ \begin{align} &(pk_C,c,\vec{f});(sk_M,pk_M,m,sk_\mathsf{fmd},pk_\mathsf{fmd},r_0,r_2) \text{ such that:}\\ &\qquad c = \mathsf{commit}_{pk_C}(pk_M;r_0)\\ &\qquad \vec{f} = \mathsf{FMD.Flag}(pk_\mathsf{fmd};r_2)\\ &\qquad (sk_\mathsf{fmd},pk_\mathsf{fmd}) = \mathsf{deriveFMD}(sk_M,pk_M) \end{align} \right\}.

In principle it should lead to smaller circuits, and proofs \pi_{VE} and \pi_{FMD} can be generated in parallel. Of course, the verifications should be done using the same commitment c. The commitment key pk_C should also be the same, but it can be re-used for different users.

Because c is hiding no information about the master public key pk_M is leaked in the instances (pk_C,c,ct) and (pk_C,c,\vec{f}). Hence no information about the user \mathsf{uid} is leaked.

Avoiding passing secret keys as witnesses

It would be good if users do not have to disclose their master, decryption and FMD secret keys to whoever generates the ZKPs (e.g. untrusted solvers). This can be achieved if we have a public key derivation processes for pk_{\mathsf{ve}}, pk_{\mathsf{fmd}} solely from the master public key pk_M:

pk_M \stackrel{\mathsf{publicDeriveVE}}{\longrightarrow} pk_\mathsf{ve},

and

pk_M \stackrel{\mathsf{publicDeriveFMD}}{\longrightarrow} pk_\mathsf{fmd}.

For correctness it should hold that \mathsf{publicDeriveX}(pk_M) = \mathsf{deriveX}(pk_M)[0] for \mathsf{X}\in\{\mathsf{VE,FMD}\}. This way, the relation \mathcal{R}_{FC} (and \mathcal{R}_{VE},\mathcal{R}_{FMD}) defined above can be stated in terms of the public derivation algorithms, that do not use secret keys at all.

We may use similar ideas to the process of generating unhardened Bitcoin Hierarchical Deterministic Wallets.

1 Like
2

Another problem is to enforce correctness of the flags generation. See also this post for more context. We define this problem as follows.

Problem 3: Correctness of FMD flags: Given a commitment \mathsf{cm} of pk_\mathsf{fmd}, and flag ciphertexts \vec{f}, we want to enforce that \vec{f} has been generated with the committed pk_\mathsf{fmd}.

For concreteness we will focus on the FMD2 construction of the FMD paper. We assume it is instantiated over an elliptic curve \mathbb{G} = E(\mathbb{F}_p) and that G is a point of order q. The flag generation is as follows.

\underline{\mathsf{FMD2.flag}:}
Input:

  • Public key pk:=(H_1,\ldots,H_\gamma)\in\mathbb{G}^\gamma
  • Randomness r,z\in \mathbb{Z}_q
  1. U:=r\cdot G, W:=z\cdot G
  2. For 1\leq i\leq \gamma do:
    a. D_i:=r_i\cdot H_i
    b. k_i := \mathsf{H}(U,D_i,W) // Hash to \mathbb{Z}_2
    c. c_i:=k_i+1 // Arithmetic in \mathbb{Z}_2
  3. m:=\mathsf{G}(U,c_1,\ldots,c_\gamma) // Hash to \mathbb{Z}_q
  4. y:=(z-m)r^{-1} // Arithmetic in field \mathbb{Z}_q
  5. Output flag ciphertexts \vec{f}:=(U,y,c_1,\ldots,c_\gamma)

Note we pass the randomness r,z\gets\mathbb{Z}_q as input, which allows to use r,z in the arithmetic circuit below. The relation for which we want to generate proofs is

\mathcal{R}_{fmd} := \left\{(\mathsf{cm},\vec{f})\ ;\ (pk,r,z,s)\ \big\lvert\ \begin{aligned} & \mathsf{cm} = \mathsf{commit}(pk;s) \\ & \vec{f} = \mathsf{FMD2.flag}(pk,r,z) \end{aligned} \right\}

The instance is (\mathsf{cm},\vec{f}), and the witness is (pk,r,z,s).

The arithmetic circuit

The most expensive operations are the three scalar multiplications in the calculations of U,W,D_i. For this reason, we define the arithmetic circuit below over the base field \mathbb{F}_p of \mathbb{G}.

Getting rid of the hash \mathsf{G} in the circuit. The inputs of the hash \mathsf{G} are derived from the flag ciphertext, which is part of the instance of \mathcal{R}_{fmd}. This means we do not need to enforce in zero-knowledge that m = \mathsf{G}(U,c_1,\ldots,c_\gamma). Instead, the circuit enforces correctness of a modified algorithm \mathsf{FMD2.flag}' that takes m as an additional input, and skips step 3. Thus, we will generate proofs for the relation

\mathcal{R}'_{fmd} := \left\{(\mathsf{cm},\vec{f},m)\ ;\ (pk,r,z,s)\ \big\lvert\ \begin{aligned} & \mathsf{cm} = \mathsf{commit}(pk;s) \\ & \vec{f} = \mathsf{FMD2.flag}'(pk,r,z,m) \end{aligned} \right\}

It clearly holds

\begin{aligned} &(\mathsf{cm},\vec{f},m);(pk,r,z,s))\in\mathcal{R}'_{fmd} \land m = \mathsf{G}(U,c_1,\ldots,c_\gamma)\\ &\Rightarrow(\mathsf{cm},\vec{f});(pk,r,z,s))\in\mathcal{R}_{fmd}\\ \end{aligned}

So what the verifier does is, first derive m from the flag \vec{f}, and then verify a ZKP for \mathcal{R}'_{fmd}.

The hash \mathsf{H} in the circuit. We use Poseidon hash over \mathbb{F}_p to hash (the coordinates of) points U,D,W onto a single field element and then take its LSB bit:

\underline{\mathsf{H}(U,D,W):}

  1. h = \mathsf{Poseidon}(x_U,y_U,x_D,y_D,x_W,y_W)
  2. Output LSB bit of field element h

Committing to the public key. In a similar way to commit to the public key pk:=(H_1,\ldots,H_\gamma), which are points in \mathbb{G} we hash with Poseidon all their coordinates, along with a hiding field element s. The commitment \mathsf{cm} is a single field element.

The circuit for \mathsf{FMD2.flag}'. It has parameter \gamma hard-coded. It is defined as follows.

\underline{\mathsf{CircuitFMD2Flag'}:}
Public input:

  • Commitment \mathsf{cm}
  • Flag ciphertext \vec{f}:=(U,y,c_1,\ldots,c_\gamma)
  • m // Purportedly, the result of the hash \mathsf{G}

Private input:

  • Public key pk:=(H_1,\ldots,H_\gamma)
  • Randomness r,z\in \mathbb{Z}_q
  • Blinding factor s
  1. Check \mathsf{cm}=\mathsf{Poseidon}(H_1,\ldots,H_\gamma,s)
  2. Check U = r\cdot G and W = z\cdot G
  3. For 1\leq i \leq\gamma:
    a. Check D_i = r \cdot H_i
    b. Check bit c_i and bit \mathsf{H}(U,D_i,W) are different
  4. Check yr = z-m\mod q // Emulate arithmetic modulo q in \mathbb{F}_p.