Identity gate feature

[sinui0]

In our garbled circuit protocols, we have two variants of encoded values: Values which have been encoded directly via the encoder, and values generated by computing the garbling algorithm (aka output labels). Recomputing a computed value can be quite expensive depending on the complexity of the circuit they come from.

We avoid this expense in our transcript commitment protocol by making sure that the encodings for the plaintext values are always generated directly via the encoder. This introduces some extra complexity during decryption, as we have to perform an additional oblivious transfer and ZKP to prove the chosen plaintext encrypts to the expected ciphertext.

There is a fairly simple alternative to our current approach: identity gates. A gate which encrypts a label using an output label as the key.

1. Generator garbles a circuit which generates output labels $W_O$
2. Evaluator evaluates the garbled circuit to get active output labels $w_O$
3. Generator generates new labels using the encoder $W_X$
4. Generator encrypts $W_X$ using $W_O$ for keys: $Gate_X = Enc(W_O, W_X)$
5. Generator sends $Gate_X$ directly
6. Evaluator evaluates $Gate_X$ using $w_O$ to learn the active $w_X$ value.

This process need not be coupled to the garbled circuit execution, it can be pretty neatly encapsulated into a new trait:

/// This trait provides a method for cloning values in memory.
#[async_trait]
pub trait ValueClone {
  /// Clones the provided values.
  async fn clone(&mut self, values: &[ValueRef], new_values: &[ValueRef]) -> Result<(), CloneError>;
}

Using this, our decryption protocol can be simplified. We would simply decrypt the ciphertext in the VM, clone the plaintext so the labels are generated via the encoder, then the Prover would commit to these labels instead. Eliminating the need for additional OT + ZKP process.

[themighty1]

Does this approach affect the DualEx equality check? Do both parties still need to hold the decoded circuit's output?

[themighty1]

Im still confused how this interplays with DEAP as described in https://docs.tlsnotary.org/protocol/2pc/deap.html
As per DEAP. In Step 9 Alice learns the plaintext and in Step 14 Bob learns the plaintext. So DEAP requires that both parties learn the plaintext output.
But since we want to prevent the Notary from seeing the plaintext, the current decryption protocol masks the plaintext output and adds the OT+ZKP steps on top.
I don't see how using identity gates removes the need of having a mask+OT+ZKP.

[sinui0]

The decryption process is almost the same:

1. Alice and Bob compute the masked plaintext $Enc(k, ctr) \oplus c \oplus z = p \oplus z = p_z$ (this is the value with which they perform the equality check)
2. Alice removes the OTP to learn the authentic plaintext.

Separately, Alice still has Bob's active encoding for $p$ stored in memory: $[p]_B$

1. Bob generates a new encoding for $p$: $[P]'_B$ and encrypts it (creates an identity gate $Gate^I_p$) using the previous encoding and sends it to Alice.
2. Alice uses $[p]_B$ to evaluate $Gate^I_p$ and learns the new active encoding $[p]'_B$
3. Alice commits to this new encoding as she wishes

During DEAP finalization Alice verifies that $[P]'_B$ and $Gate^I_p$ were generated correctly.

You can think of this as an oblivious transfer, where Bob is the Sender and Alice the Receiver. Bob sends the full encoding $[P]'_B$ and Alice receives the active encoding corresponding to her choice:

$$Bob: \mathsf{OTSend}([P]'_B)$$ $$Alice: [p]'_B \leftarrow \mathsf{OTRecv}([p]_B)$$

The key point is this: The only choice Alice can make is $[p]_B$, as she does not know the full encoding $[P]_B$.

We do not need to perform a ZKP to prove that $[p]'_B$ encrypts back to the correct ciphertext because Bob knows Alice can not choose a different $p$.

In our current method Alice can choose a different $p$ when we perform the OT using KOS. That is why we have to perform the ZKP.

[themighty1]

Thanks for explaining. Makes sense now. Yes, this approach seems sound.