Encryption

Here we will explain our protocol for 2PC encryption using a block cipher in counter-mode.

Our documentation on Dual Execution with Asymmetric Privacy is recommended prior reading for this section.

It is important to recognise that the Notary's keyshare is an ephemeral secret. It is only private for the duration of the User's TLS session, after which the User is free to learn it without affecting the security of the protocol.

It is this fact which allows us to achieve malicious security for relatively low cost. More details on this here.

Premature Leakage

A small amount of undetected premature keyshare leakage is quite tolerable. For example, if the Notary leaks 3 bits of their keyshare, it gives the User no meaningful advantage in any attack, as she could have simply guessed the bits correctly with $2^{- 3} = 12.5%$ probability and mounted the same attack. Assuming a sufficiently long cipher key is used, eg. 128 bits, this is not a concern.

The equality check at the end of our protocol ensures that premature leakage is detected with a probability of $1 - 2^{- k}$ where k is the number of leaked bits. The Notary is virtually guaranteed to detect significant leakage and can abort prior to notarization.

Plaintext Leakage

Our protocol assures no leakage of the plaintext to the Notary during both encryption and decryption. The Notary reveals their keyshare at the end of the protocol, which allows the Notary to open their garbled circuits and oblivious transfers completely to the User. The User can then perform a series of consistency checks to ensure that the Notary behaved honestly. Because these consistency checks do not depend on any inputs of the User, aborting does not reveal any sensitive information (in contrast to standard DualEx which does).

Integrity

During the entirety of the TLS session the User performs the role of the garbled circuit generator, thus ensuring that a malicious Notary can not corrupt or otherwise compromise the integrity of messages sent to/from the Server.

Notation

$p$ is one block of plaintext
$c$ is the corresponding block of ciphertext, ie $c = Enc (k, c t r) \oplus p$
$k$ is the cipher key
$c t r$ is the counter block
$k_{U}$ and $k_{N}$ denote the User and Notary cipher keyshares, respectively, where $k = k_{U} \oplus k_{N}$
$z$ is a mask randomly selected by the User
$ec t r$ is the encrypted counter-block, ie $ec t r = Enc (k, c t r)$
$Enc$ denotes the block cipher used by the TLS session
$com_{x}$ denotes a binding commitment to the value $x$
$[x]_{A}$ denotes a garbled encoding of $x$ chosen by party $A$

Encryption Protocol

The encryption protocol uses DEAP without any special variations. The User and Notary directly compute the ciphertext for each block of a message the User wishes to send to the Server:

$f (k_{U}, k_{N}, c t r, p) = Enc (k_{U} \oplus k_{N}, c t r) \oplus p = c$

The User creates a commitment to the plaintext active labels for the Notary's circuit $Com ([p]_{N}, r) = com_{[p]_{N}}$ where $r$ is a random key known only to the User. The User sends this commitment to the Notary to be used in the authdecode protocol later. It's critical that the User commits to $[p]_{N}$ prior to the Notary revealing $Δ$ in the final phase of DEAP. This ensures that if $com_{[p]_{N}}$ is a commitment to valid labels, then it must be a valid commitment to the plaintext $p$ . This is because learning the complementary wire label for any bit of $p$ prior to learning $Δ$ is virtually impossible.

Decryption Protocol

The protocol for decryption is very similar but has some key differences to encryption.

For decryption, DEAP is used for every block of the ciphertext to compute the masked encrypted counter-block:

$f (k_{U}, k_{N}, c t r, z) = Enc (k_{U} \oplus k_{N}, c t r) \oplus z = ec t r_{z}$

This mask $z$ , chosen by the User, hides $ec t r$ from the Notary and thus the plaintext too. Conversely, the User can simply remove this mask in order to compute the plaintext $p = c \oplus ec t r_{z} \oplus z$ .

Following this, the User can retrieve the wire labels $[p]_{N}$ from the Notary using OT.

Similarly to the procedure for encryption, the User creates a commitment $Com ([p]_{N}, r) = com_{[p]_{N}}$ where $r$ is a random key known only to the User. The User sends this commitment to the Notary to be used in the authdecode protocol later.

Proving the validity of $[p]_{N}$

In addition to computing the masked encrypted counter-block, the User must also prove that the labels $[p]_{N}$ they chose afterwards actually correspond to the ciphertext $c$ sent by the Server.

This is can be done efficiently in one execution using the zero-knowledge protocol described in [JKO13] the same as we do in the final phase of DEAP.

The Notary garbles a circuit $G_{N}$ which computes:

$p \oplus ec t r = c$

Notice that the User and Notary will already have computed $ec t r$ when they computed $ec t r_{z}$ earlier. Conveniently, the Notary can re-use the garbled labels $[ec t r]_{N}$ as input labels for this circuit. For more details on the reuse of garbled labels see [AMR17].

tlsn-docs