Introduction
Notarization Phase
During the Notarization Phase the Requester
, otherwise referred to as the User
, and the Notary
work together to generate an authenticated Transcript
of a TLS session with a Server
.
Listed below are some key points regarding this process:
 The identity of the
Server
is not revealed to theNotary
, but theRequester
is capable of proving theServer
identity to aVerifier
later.  The
Notary
only ever sees the encrypted application data of the TLS session.  The protocol guarantees that the
Requester
is not solely capable of constructing requests, nor can they forge responses from theServer
.
Requester
The Requester
is the party which runs the TLS connection with the Server
. The Requester
constructs application payloads, eg. HTTP requests, and coordinates with the Notary
to encrypt them with the TLS session keys prior to sending them. Subsequently, the Requester
works with the Notary
to decrypt responses from the Server
. The plaintext of the application data is only ever revealed to the Requester
.
Notary
The Notary
is the party of which the authenticity of the Transcript
relies on. During the session the Notary
withholds its' shares of the TLS keys and participates in a series of secure 2party computation protocols with the Requester
to operate the TLS connection.
Server
The Server
can be any server which supports TLS. The TLSNotary protocol is entirely transparent to the Server
, thus it can not be censored nor does it have to support any additional functionality.
Transcript
The primary artifact generated from this phase is called the Transcript
. It contains session metadata, handshake data, and commitments to all the requests and responses. Typically the Transcript
is signed by the Notary
, however that is not necessary in the case where the Notary
will also act as the Verifier
in the selective disclosure phase.
Note that the server ephemeral key does not reveal the identity of the server to the
Notary
.
Key Exchange
In TLS, the first step towards obtaining TLS session keys is to compute a shared secret between the client and the server by running the ECDH protocol. The resulting shared secret in TLS terms is called the premaster secret PMS
.
Using the notation from Wikipedia, below is the 3party ECDH protocol between the Server
the Requester
and the Notary
, enabling the Requester
and the Notary
to arrive at shares of PMS
.
Server
sends its public key $Q_{b}$ toRequester
, andRequester
forwards it toNotary
Requester
picks a random private key share $d_{c}$ and computes a public key share $Q_{c}=d_{c}∗G$Notary
picks a random private key share $d_{n}$ and computes a public key share $Q_{n}=d_{n}∗G$Notary
sends $Q_{n}$ toRequester
who computes $Q_{a}=Q_{c}+Q_{n}$ and sends $Q_{a}$ toServer
Requester
computes an EC point $(x_{p},y_{p})=d_{c}∗Q_{b}$Notary
computes an EC point $(x_{q},y_{q})=d_{n}∗Q_{b}$ Addition of points $(x_{p},y_{p})$ and $(x_{q},y_{q})$ results in the coordinate $x_{r}$, which is
PMS
. (The coordinate $y_{r}$ is not used in TLS)
Using the notation from here, our goal is to compute $x_{r}=(x_{q}−x_{p}y_{q}−y_{p} )_{2}−x_{p}−x_{q}$ in such a way that
 Neither party learns the other party's $x$ value
 Neither party learns $x_{r}$, only their respective shares of $x_{r}$.
We will use two maliciously secure protocols described on p.25 in the paper Eﬃcient Secure TwoParty Exponentiation:
A2M
protocol, which converts additive shares into multiplicative shares, i.e. given sharesa
andb
such thata + b = c
, it converts them into sharesd
ande
such thatd * e = c
M2A
protocol, which converts multiplicative shares into additive shares
We apply A2M
to $y_{q}+(−y_{p})$ to get $A_{q}∗A_{p}$ and also we apply A2M
to $x_{q}+(−x_{p})$ to get $B_{q}∗B_{p}$. Then the above can be rewritten as:
$x_{r}=(B_{q}A_{q} )_{2}∗(B_{p}A_{p} )_{2}−x_{p}−x_{q}$
Then the first party locally computes the first factor and gets $C_{q}$, the second party locally computes the second factor and gets $C_{p}$. Then we can again rewrite as:
$x_{r}=C_{q}∗C_{p}−x_{p}−x_{q}$
Now we apply M2A
to $C_{q}∗C_{p}$ to get $D_{q}+D_{p}$, which leads us to two final terms each of which is the share of $x_{r}$ of the respective party:
$x_{r}=(D_{q}−x_{q})+(D_{p}−x_{p})$
Overview
The premaster secret (PMS
) must be put through a PRF
(pseudorandom function) defined by the TLS spec in order to compute the symmetric TLS keys and also to compute the verify_data
for the Client_Finished
and the Server_Finished
messages.
Below we describe how the parties (N
stands for Notary
and U
stands for User
) who have their shares of PMS
can use 2PC to compute the PRF
.
Since the TLSNotary protocol already uses Garbled Circuits and Oblivious Transfer which give 128bit computational security for the parties against each other, we argue that it is acceptable to perform some PRF computations outside of 2PC as long as it is done with at least 128bit security. Performing some PRF computations outside of 2PC allows to save on computation and bandwidth.
Note that the User's TLS connection retains the standard TLS security guarantees against any thirdparty adversary.
To elaborate, recall how HMAC is computed (assuming k <= block size):
HMAC(k, m) = H((k ⊕ opad)  H((k ⊕ ipad)  m))
Notice that both H(k ⊕ opad) and H(k ⊕ ipad) can be computed separately prior to finalization. In this document we name these units as such:
outer hash state
: H(k ⊕ opad)inner hash state
: H(k ⊕ ipad)inner hash
: H((k ⊕ ipad)  m)
In TLS, the master secret is computed like so:
seed = "master secret"  client_random  server_random
a0 = seed
a1 = HMAC(pms, a0)
a2 = HMAC(pms, a1)
p1 = HMAC(pms, a1  seed)
p2 = HMAC(pms, a2  seed)
ms = (p1  p2)[:48]
Notice that in each step the key, in this case PMS
, is constant. Thus both the outer
and inner hash state
can be reused for each step.
Below is the description of the all the steps to compute the PRF
both inside and outside the 2PC circuit.
 Computing the master secret
 Inside the circuit
 To evaluate the circuit, the parties input their
PMS
shares. The circuit outputs:
 H(PMS ⊕ opad) called
PMS
outer hash state
toN
and  H(PMS ⊕ ipad) called
PMS
inner hash state
toU
 Outside the circuit

U
computes H((PMS ⊕ ipad)  a0) calledinner hash
ofa1
and passes it toN
. 
N
computesa1
and passes it toU
. 
U
computes theinner hash
ofa2
and passes it toN
. 
N
computesa2
and passes it toU
. 
U
computes theinner hash
of p2 and passes it toN
. 
N
computesp2
and passes it toU
. >Note that now both parties knowp2
which is the last 16 bytes of the master secret. They still don't know the other 32 bytes of the master secret, which ensures adequate security. 
U
computes theinner hash
ofp1
.
 Inside the circuit
 To evaluate the circuit,
N
inputs thePMS outer hash state
andU
inputsp2
and theinner hash
ofp1
. The circuit computes the master secret (MS
).
 Computing the expanded keys
The parties proceed to compute the expanded keys
. The corresponding python code is:
seed = str.encode("key expansion") + server_random + client_random
a0 = seed
a1 = hmac.new(ms , a0, hashlib.sha256).digest()
a2 = hmac.new(ms , a1, hashlib.sha256).digest()
p1 = hmac.new(ms, a1+seed, hashlib.sha256).digest()
p2 = hmac.new(ms, a2+seed, hashlib.sha256).digest()
ek = (p1 + p2)[:40]
client_write_key = ek[:16]
server_write_key = ek[16:32]
client_write_IV = ek[32:36]
server_write_IV = ek[36:40]
 Inside the circuit
 Having computed
MS
, the circuit outputs:
 H(MS ⊕ opad) called the
MS outer hash state
toN
and  H(MS ⊕ ipad) called the
MS inner hash state
toU
 Outside the circuit

U
computes theinner hash
ofa1
and sends it toN
. 
N
computesa1
and sends it toU
. 
U
computes theinner hash
ofa2
and sends it toN
. 
N
computesa2
and sends it toU
. 
U
computes theinner hash state
ofp1
and theinner hash state
ofp2
.
 Inside the circuit
 To evaluate the circuit,
N
inputsMS outer hash state
(from Step 10) andU
inputsinner hash state
ofp1
andinner hash state
ofp2
. The circuit computesp1
andp2
. The circuit outputs xor shares of theexpanded keys
to each party.
 Computing the encrypted Client_Finished
 Inside the circuit
 To evaluate the circuit, the parties input their shares of the
expanded keys
. The circuit outputs data needed to encrypt and authenticate theClient_Finished
(CF
) message.
 Outside the circuit
The parties proceed to compute verify_data
for the CF
message. The corresponding python code is:
# (handshake_hash) is a sha256 hash of all TLS handshake message up to this point
seed = str.encode('client finished') + handshake_hash
a0 = seed
a1 = hmac.new(ms, a0, hashlib.sha256).digest()
p1 = hmac.new(ms, a1+seed, hashlib.sha256).digest()
verify_data = p1[:12]

U
computesinner hash
ofa1
and sends it toN
. 
N
(who hasMS
outer hash state
from Step 10) computesa1
and sends it toU
. 
U
computesinner hash
ofp1
and sends it toN
. 
N
computesp1
and getsverify_data
and sends it toU
.
Note that it is safe for
N
to knowverify_data
forCF
.
Using the data from Step 17, U
proceeds to encrypt and authenticate CF
and sends it to the webserver.
 Verifying the Server_Finished
Upon U
's receiving the encrypted Server_Finished
(SF
) from the webserver, the parties proceed to compute verify_data
for SF
, to enable U
to check that the received SF
is correct. The corresponding python code is:
# (handshake_hash) is a sha256 hash of all TLS handshake message up to this point
seed = str.encode('server finished') + handshake_hash
a0 = seed
a1 = hmac.new(ms, a0, hashlib.sha256).digest()
p1 = hmac.new(ms, a1+seed, hashlib.sha256).digest()
verify_data = p1[:12]
 Outside the circuit

U
computesinner hash
ofa1
and sends it toN
. 
N
(who hasMS
outer hash state
from Step 10) computesa1
and sends it toU
. 
U
computesinner hash
ofp1
.
 Inside the circuit
 To evaluate the circuit,
N
inputsMS
outer hash state
(from Step 10) andU
inputsinner hash
ofp1
. The circuit outputsverify_data
forSF
toU
.
The parties proceed to decrypt and authenticate the SF
in 2PC. U
checks that verify_data
from SF
matches verify_data
from Step 25.
Encryption
Here we will explain our protocol for 2PC encryption using a block cipher in countermode.
Our documentation on Dual Execution with Asymmetric Privacy is recommended prior reading for this section.
Preliminary
Ephemeral Keyshare
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,ctr)⊕p$
 $k$ is the cipher key
 $ctr$ is the counter block
 $k_{U}$ and $k_{N}$ denote the User and Notary cipher keyshares, respectively, where $k=k_{U}⊕k_{N}$
 $z$ is a mask randomly selected by the User
 $ectr$ is the encrypted counterblock, ie $ectr=Enc(k,ctr)$
 $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},ctr,p)=Enc(k_{U}⊕k_{N},ctr)⊕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 counterblock:
$f(k_{U},k_{N},ctr,z)=Enc(k_{U}⊕k_{N},ctr)⊕z=ectr_{z}$
This mask $z$, chosen by the User, hides $ectr$ from the Notary and thus the plaintext too. Conversely, the User can simply remove this mask in order to compute the plaintext $p=c⊕ectr_{z}⊕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 counterblock, 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 zeroknowledge 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⊕ectr=c$
Notice that the User and Notary will already have computed $ectr$ when they computed $ectr_{z}$ earlier. Conveniently, the Notary can reuse the garbled labels $[ectr]_{N}$ as input labels for this circuit. For more details on the reuse of garbled labels see [AMR17].
At the end of the TLSNotary protocol, the User has the authenticated AES ciphertext which can be thought of as a commitment to the plaintext. This form of commitment is not amenable to use cases when the User wants to make part of the plaintext public while keeping another part private. Naively, the User's option is to prove the decryption of the ciphertext in zeroknowledge which is computationally expensive.
We describe two less computationally heavy approaches for converting the AES ciphertext commitments.
The first approach is useful for commitments to the data which the User intends to make public. It is based on decrypting the ciphertext with Garbled Circuits and producing a hash commitment to the wire labels.
The second approach is useful for commitments to the private data which the User later intends to prove statements about in zeroknowledge. This approach produces a Poseidon hash over the private data.
We describe an interactive protocol between the User U
and the Notary N
, whereby U
can convert the authenticated AES ciphertext into a hash commitment to Garbled Circuits wire labels.
 Creating the new commitment

At the end of the TLSNotary session, both
U
andN
know the authenticated AESciphertext
. 
N
reveals his TLS session key shares toU
. 
U
decrypts theciphertext
in the clear and learns the plaintextp
. 
N
picks aseed
and uses it as the source of randomness to generate (in the semihonest model) a privacyfree garbled circuit whose functionality is to accept the plaintext input, encrypt it, and output the ciphertext. 
With
p
as her circuit input,U
receives input wire labelsIWLs
via Oblivious Transfer and then evaluates the circuit on thoseIWLs
. The result of the evaluation are output wire labelsOWLs
whichU
does not know the decoding for. 
U
sends two commitments:commitment to IWLs
andcommitment to OWLs
toN
. 
N
reveals theseed
andU
checks that the circuit (including itsIWLs
andOWLs
) was generated correctly and, if successful, reveals herOWLs
. 
N
verifiescommitment to OWLs
and then checks that decodedOWLs
match theciphertext
(from Step 0) and, if successful, signs (seed
+commitment to IWLs
).
Now, (
seed
+commitment to IWLs
) becomeU
's new commitment top
.
 Verifying the commitment
Verifier performs the following steps:

Receives the following from
U
: plaintextp
,signature
for (seed
+commitment to IWLs
),seed
,commitment to IWLs
. 
(using a trusted
N
s pubkey) Verifies thesignature
. 
Regenerates the
IWLs
from theseed
. 
Picks only those
IWLs
which correspond top
and checks that the commitment to thoseIWLs
matchescommitment to IWLs
. 
Accepts
p
as authentic.
 Dynamic commitment using a Merkle tree
In situations where U
does not know in advance which subset of the public data she will be revealing later to the Verifier, U
can commit to the Merkle tree of all her input wire labels (from Step 4 above).
Later, U
can reveal only those Merkle leaves which she wants to make public to the Verifier.
Secure 2Party Computation
Dual Execution with Asymmetric Privacy
Introduction
Malicious secure 2party computation with garbled circuits typically comes at the expense of dramatically lower efficiency compared to execution in the semihonest model. One technique, called Dual Execution [MF06] [HKE12], achieves malicious security with a minimal 2x overhead. However, it comes with the concession that a malicious adversary may learn $k$ bits of the other's input with probability $2_{−k}$.
We present a variant of Dual Execution which provides different tradeoffs. Our variant ensures complete privacy for one party, by sacrificing privacy entirely for the other. Hence the name, Dual Execution with Asymmetric Privacy (DEAP). During the execution phase of the protocol both parties have private inputs. The party with complete privacy learns the authentic output prior to the final stage of the protocol. In the final stage, prior to the equality check, one party reveals their private input. This allows a series of consistency checks to be performed which guarantees that the equality check can not cause leakage.
Similarly to standard DualEx, our variant ensures output correctness and detects leakage (of the revealing parties input) with probability $1−2_{−k}$ where $k$ is the number of bits leaked.
Preliminary
The protocol takes place between Alice and Bob who want to compute $f(x,y)$ where $x$ and $y$ are Alice and Bob's inputs respectively. The privacy of Alice's input is ensured, while Bob's input will be revealed in the final steps of the protocol.
Premature Leakage
Firstly, our protocol assumes a small amount of premature leakage of Bob's input is tolerable. By premature, we mean prior to the phase where Bob is expected to reveal his input.
If Alice is malicious, she has the opportunity to prematurely leak $k$ bits of Bob's input with $2_{−k}$ probability of it going undetected.
Aborts
We assume that it is acceptable for either party to cause the protocol to abort at any time, with the condition that no information of Alice's inputs are leaked from doing so.
Committed Oblivious Transfer
In the last phase of our protocol Bob must open all oblivious transfers he sent to Alice. To achieve this, we require a very relaxed flavor of committed oblivious transfer. For more detail on these relaxations see section 2 of ZeroKnowledge Using Garbled Circuits [JKO13].
Notation
 $x$ and $y$ are Alice and Bob's inputs, respectively.
 $[X]_{A}$ denotes an encoding of $x$ chosen by Alice.
 $[x]$ and $[y]$ are Alice and Bob's encoded active inputs, respectively, ie $Enc(x,[X])=[x]$.
 $com_{x}$ denotes a binding commitment to $x$
 $G$ denotes a garbled circuit for computing $f(x,y)=v$, where:
 $Gb([X],[Y])=G$
 $Ev(G,[x],[y])=[v]$.
 $d$ denotes output decoding information where $De(d,[v])=v$
 $Δ$ denotes the global offset of a garbled circuit where $∀i:[x]_{i}=[x]_{i}⊕Δ$
 $PRG$ denotes a secure pseudorandom generator
 $H$ denotes a secure hash function
Protocol
The protocol can be thought of as three distinct phases: The setup phase, execution, and equalitycheck.
Setup
 Alice creates a garbled circuit $G_{A}$ with corresponding input labels $([X]_{A},[Y]_{A})$, and output label commitment $com_{[V]_{A}}$.
 Bob creates a garbled circuit $G_{B}$ with corresponding input labels $([X]_{B},[Y]_{B})$.
 For committed OT, Bob picks a seed $ρ$ and uses it to generate all randomtape for his OTs with $PRG(ρ)$. Bob sends $com_{ρ}$ to Alice.
 Alice retrieves her active input labels $[x]_{B}$ from Bob using OT.
 Bob retrieves his active input labels $[y]_{A}$ from Alice using OT.
 Alice sends $G_{A}$, $[x]_{A}$, $d_{A}$ and $com_{[V]_{A}}$ to Bob.
 Bob sends $G_{B}$, $[y]_{B}$, and $d_{B}$ to Alice.
Execution
Both Alice and Bob can execute this phase of the protocol in parallel as described below:
Alice
 Evaluates $G_{B}$ using $[x]_{B}$ and $[y]_{B}$ to acquire $[v]_{B}$.
 Decodes $[v]_{B}$ to $v_{B}$ using $d_{B}$ which she received earlier. She computes $H([v_{B}]_{A},[v]_{B})$ which we will call $check_{A}$.
 Computes a commitment $Com(check_{A},r)=com_{check_{A}}$ where $r$ is a key only known to Alice. She sends this commitment to Bob.
 Waits to receive $[v]_{A}$ from Bob^{1}.
 Checks that $[v]_{A}$ is authentic, aborting if not, then decodes $[v]_{A}$ to $v_{A}$ using $d_{A}$.
At this stage, if Bob is malicious, Alice could detect that $v_{A}=v_{B}$. However, Alice must not react in this case. She proceeds with the protocol regardless, having the authentic output $v_{A}$.
Bob
 Evaluates $G_{A}$ using $[x]_{A}$ and $[y]_{A}$ to acquire $[v]_{A}$. He checks $[v]_{A}$ against the commitment $com_{[V]_{A}}$ which Alice sent earlier, aborting if it is invalid.
 Decodes $[v]_{A}$ to $v_{A}$ using $d_{A}$ which he received earlier. He computes $H([v]_{A},[v_{A}]_{B})$ which we'll call $check_{B}$, and stores it for the equality check later.
 Sends $[v]_{A}$ to Alice^{1}.
 Receives $com_{check_{A}}$ from Alice and stores it for the equality check later.
Bob, even if malicious, has learned nothing except the purported output $v_{A}$ and is not convinced it is correct. In the next phase Alice will attempt to convince Bob that it is.
Alice, if honest, has learned the correct output $v$ thanks to the authenticity property of garbled circuits. Alice, if malicious, has potentially learned Bob's entire input $y$.
This is a significant deviation from standard DualEx protocols such as [HKE12]. Typically the output labels are not returned to the Generator, instead, output authenticity is established during a secure equality check at the end. See the section below for more detail.
Equality Check
 Bob opens his garbled circuit and OT by sending $Δ_{B}$, $y$ and $ρ$ to Alice.
 Alice, can now derive the purported input labels to Bob's garbled circuit $([X]_{B},[Y]_{B})$.
 Alice uses $ρ$ to open all of Bob's OTs for $[x]_{B}$ and verifies that they were performed honestly. Otherwise she aborts.
 Alice verifies that $G_{B}$ was garbled honestly by checking $Gb([X]_{B},[Y]_{B})==G_{B}$. Otherwise she aborts.
 Alice now opens $com_{check_{A}}$ by sending $check_{A}$ and $r$ to Bob.
 Bob verifies $com_{check_{A}}$ then asserts $check_{A}==check_{B}$, aborting otherwise.
Bob is now convinced that $v_{A}$ is correct, ie $f(x,y)=v_{A}$. Bob is also assured that Alice only learned up to k bits of his input prior to revealing, with a probability of $2_{−k}$ of it being undetected.
Analysis
Malicious Alice
On the Leakage of Corrupted Garbled Circuits [DPB18] is recommended reading on this topic.
During the first execution, Alice has some degrees of freedom in how she garbles $G_{A}$. According to [DPB18], when using a modern garbling scheme such as [ZRE15], these corruptions can be analyzed as two distinct classes: detectable and undetectable.
Recall that our scheme assumes Bob's input is an ephemeral secret which can be revealed at the end. For this reason, we are entirely unconcerned about the detectable variety. Simply providing Bob with the output labels commitment $com_{[V]_{A}}$ is sufficient to detect these types of corruptions. In this context, our primary concern is regarding the correctness of the output of $G_{A}$.
[DPB18] shows that any undetectable corruption made to $G_{A}$ is constrained to the arbitrary insertion or removal of NOT gates in the circuit, such that $G_{A}$ computes $f_{A}$ instead of $f$. Note that any corruption of $d_{A}$ has an equivalent effect. [DPB18] also shows that Alice's ability to exploit this is constrained by the topology of the circuit.
Recall that in the final stage of our protocol Bob checks that the output of $G_{A}$ matches the output of $G_{B}$, or more specifically:
$f_{A}(x_{1},y_{1})==f_{B}(x_{2},y_{2})$
For the moment we'll assume Bob garbles honestly and provides the same inputs for both evaluations.
$f_{A}(x_{1},y)==f(x_{2},y)$
In the scenario where Bob reveals the output of $f_{A}(x_{1},y)$ prior to Alice committing to $x_{2}$ there is a trivial adaptive attack available to Alice. As an extreme example, assume Alice could choose $f_{A}$ such that $f_{A}(x_{1},y)=y$. For most practical functions this is not possible to garble without detection, but for the sake of illustration we humor the possibility. In this case she could simply compute $x_{2}$ where $f(x_{2},y)=y$ in order to pass the equality check.
To address this, Alice is forced to choose $f_{A}$, $x_{1}$ and $x_{2}$ prior to Bob revealing the output. In this case it is obvious that any valid combination of $(f_{A},x_{1},x_{2})$ must satisfy all constraints on $y$. Thus, for any nontrivial $f$, choosing a valid combination would be equivalent to guessing $y$ correctly. In which case, any attack would be detected by the equality check with probability $1−2_{−k}$ where k is the number of guessed bits of $y$. This result is acceptable within our model as explained earlier.
Malicious Bob
ZeroKnowledge Using Garbled Circuits [JKO13] is recommended reading on this topic.
The last stage of our variant is functionally equivalent to the protocol described in [JKO13]. After Alice evaluates $G_{B}$ and commits to $[v]_{B}$, Bob opens his garbled circuit and all OTs entirely. Following this, Alice performs a series of consistency checks to detect any malicious behavior. These consistency checks do not depend on any of Alice's inputs, so any attempted selective failure attack by Bob would be futile.
Bob's only options are to behave honestly, or cause Alice to abort without leaking any information.
Malicious Alice & Bob
They deserve whatever they get.
Computing MAC in 2PC
 What is a MAC
 How a MAC is computed in AESGCM
 Computing MAC using secure twoparty computation (2PC)
1. What is a MAC
When sending an encrypted ciphertext to the Webserver, the User attaches a checksum to it. The Webserver uses this checksum to check whether the ciphertext has been tampered with while in transit. This checksum is known as the "authentication tag" and also as the "Message Authentication Code" (MAC).
In order to create a MAC for some ciphertext not only the ciphertext but also some secret key is used as an input. This makes it impossible to forge some ciphertext without knowing the secret key.
The first few paragraphs of this article explain what would happen if there was no MAC: it would be possible for a malicious actor to modify the plaintext by flipping certain bits of the ciphertext.
2. How a MAC is computed in AESGCM
In TLS the plaintext is split up into chunks called "TLS records". Each TLS
record is encrypted and a MAC is computed for the ciphertext. The MAC (in
AESGCM) is obtained by XORing together the GHASH output
and the GCTR output
. Let's see how each of those outputs is computed:
2.1 GCTR output
The GCTR output
is computed by simply AESECB encrypting a counter block with
the counter set to 1 (the iv, nonce and AES key are the same as for the rest of
the TLS record).
2.2 GHASH output
The GHASH output
is the output of the GHASH function described in the
NIST publication
in section 6.4 in this way: "In effect, the GHASH function calculates $X_{1}•H_{m}⊕X_{2}•H_{m−1}⊕...⊕X_{m−1}•H_{2}⊕X_{m}•H$". $H$
and $X$ are elements of the extension field $GF(2_{128})$.
 "•" is a special type of multiplication called
multiplication in a finite field
described in section 6.3 of the NIST publication.  ⊕ is
addition in a finite field
and it is defined as XOR.
In other words, GHASH splits up the ciphertext into 16byte blocks, each block
is numbered $X_{1},X_{2},...$ etc. There's also $H$
which is called the GHASH key
, which just is the AESencrypted zeroblock. We
need to raise $H$ to as many powers as there are blocks, i.e. if
we have 5 blocks then we need 5 powers: $H,H_{2},H_{3},H_{4},H_{5}$.
Each block is multiplied by the corresponding power and all products are summed
together.
Below is the pseudocode for multiplying two 128bit field elements x
and y
in $GF(2_{128})$:
1. result = 0
2. R = 0xE1000000000000000000000000000000
3. bit_length = 128
4. for i=0 upto bit_length1
5. if y[i] == 1
6. result ^= x
7. x = (x >> 1) ^ ((x & 1) * R)
8. return result
Standard math properties hold in finite field math, viz. commutative: $a+b=b+a$ and distributive: $a(b+c)=ab+ac$.
3. Computing MAC using secure twoparty computation (2PC)
The goal of the protocol is to compute the MAC in such a way that neither party
would learn the other party's share of $H$ i.e. the GHASH key
share. At the start of the protocol each party has:
 ciphertext blocks $X_{1},X_{2},...,X_{m}$.
 XOR share of $H$: the
User
has $H_{u}$ and theNotary
has $H_{n}$.  XOR share of the
GCTR output
: theUser
has $GCTR_{u}$ and theNotary
has $GCTR_{n}$.
Note that 2. and 3. were obtained at an earlier stage of the TLSNotary protocol.
3.1 Example with a single ciphertext block
To illustrate what we want to achieve, we consider the case of just having
a single ciphertext block $X_{1}$. The GHASH_output
will be:
$X_{1}•H=X_{1}•(H_{u}⊕H_{n})=X_{1}•H_{u}⊕X_{1}•H_{n}$
The User
and the Notary
will compute locally the left and the right terms
respectively. Then each party will XOR their result to the GCTR output
share
and will get their XOR share of the MAC:
User
: $X_{1}•H_{u}⊕GCTR_{u}=MAC_{u}$
Notary
: $X_{1}•H_{n}⊕GCTR_{n}=MAC_{n}$
Finally, the Notary
sends $MAC_{n}$ to the User
who obtains:
$MAC=MAC_{n}⊕MAC_{u}$
For longer ciphertexts, the problem is that higher powers of the hashkey $H_{k}$ cannot be computed locally, because we deal with additive sharings, i.e.$(H_{u})_{k}⊕(H_{n})_{k}=H_{k}$.
3.2 Computing ciphertexts with an arbitrary number of blocks
We now introduce our 2PC MAC protocol for computing ciphertexts with an arbitrary number of blocks. Our protocol can be divided into the following steps.
Steps
 First, both parties convert their additive shares $H_{u}$ and $H_{n}$ into multiplicative shares $H_{u}$ and $H_{n}$.
 This allows each party to locally compute the needed higher powers of these multiplicative
shares, i.e for $m$ blocks of ciphertext:
 the user computes $H_{u} _{2},H_{u} _{3},...H_{u} _{m}$
 the notary computes $H_{n} _{2},H_{n} _{3},...H_{n} _{m}$
 Then both parties convert each of these multiplicative shares back to additive shares
 the user ends up with $H_{u},H_{u},...H_{u}$
 the notary ends up with $H_{n},H_{n},...H_{n}$
 Each party can now locally compute their additive MAC share $MAC_{n/u}$.
The conversion steps (1 and 3) require communication between the user and the notary. They will use A2M (AdditiontoMultiplication) and M2A (MultiplicationtoAddition) protocols, which make use of oblivious transfer, to convert the shares. The user will be the sender and the notary the receiver.
3.2.1 (A2M) Convert additive shares of H into multiplicative share
At first (step 1) we have to get a multiplicative share of $H_{n/u}$, so that notary and user can locally compute the needed higher powers. For this we use an adapted version of the A2M protocol in chapter 4 of Efficient Secure TwoParty Exponentiation.
The user will decompose his share into $i$ individual oblivious transfers $t_{u,i}=R⋅(k⋅2_{i}+H_{u,i}⋅2_{i}⊕s_{i})$, where
 $R$ is some random value used for all oblivious transfers
 $s_{i}$ is a random mask used per oblivious transfer, with $∑_{i}s_{i}=0$
 $k∈0,1$ depending on the receiver's choice.
The notary's choice in the ith OT will depend on the bit value in the ith position of his additive share $H_{n}$. In the end the multiplicative share of the user $H_{u} $ will simply be the inverse $R_{−1}$ of the random value, and the notary will sum all his OT outputs, so that all the $s_{i}$ will vanish and hence he gets his multiplicative share $H_{n} $.
$H =H_{u}⊕H_{n}=R_{−1}⋅R⋅i∑ (H_{u,i}⊕H_{n,i})⋅2_{i}⊕s_{i}=R_{−1}⋅i∑ t_{u,i}⊕R⋅i∑ s_{i}=H_{u} ⋅H_{n} $
3.2.2 (M2A) Convert multiplicative shares $H_{k}$ into additive shares
In step 3 of our protocol, we use the oblivious transfer method described in chapter 4.1 of the Gilboa paper Two Party RSA Key Generation to convert all the multiplicative shares $H_{n/u} $ back into additive shares $H_{n/u}$. We only show how the method works for the share $H_{n/u} $, because it is the same for higher powers.
The user will be the OT sender and decompose his shares into $i$ individual oblivious transfers $t_{u,i}=k⋅H_{u} ⋅2_{i}+s_{i}$, where $k∈0,1$, depending on the receiver's choices. Each of these OTs is masked with a random value $s_{i}$. He will then obliviously send them to the notary. Depending on the binary representation of his multiplicative share, the notary will choose one of the choices and do this for all 128 oblivious transfers.
After that the user will locally XOR all his $s_{i}$ and end up with his additive share $H_{u}$, and the notary will do the same for all the results of the oblivious transfers and get $H_{n}$.
$H =H_{u} ⋅H_{n} =H_{u} ⋅i∑ H_{n,i} ⋅2_{i}=i∑ (H_{n,i} ⋅H_{u} ⋅2_{i}⊕s_{i})⊕i∑ s_{i}=i∑ t_{u,i}⊕i∑ s_{i}≡H_{n}⊕H_{u} $
3.3 Free Squaring
In the actual implementation of the protocol we only compute odd multiplicative shares, i.e. $H,H_{3},H_{5},…$, so that we only need to share these odd shares in step 3. This is possible because we can compute even additive shares from odd additive shares. We observe that for even $k$:
$H_{k} =(H_{n}⊕H_{u})_{2}=(H_{n})_{2}⊕H_{n}H_{u}⊕H_{u}H_{n}⊕(H_{u})_{2}=(H_{n})_{2}⊕(H_{u})_{2}=H_{n}⊕H_{u} $
So we only need to convert odd multiplicative shares into odd additive shares, which gives us a 50% reduction in cost. The remaining even additive shares can then be computed locally.
3.3 Creating a robust protocol
Both the A2M and M2A protocols on their own only provide semihonest security. They are secure against a malicious receiver, but the sender has degrees of freedom to cause leakage of the MAC keyshares. However, for our purposes this does not present a problem as long as leakage is detected.
To detect a malicious sender, we require the sender to commit to the PRG seed used to generate the random values in the share conversion protocols. After the TLS session is closed the MAC keyshares are no longer secret, which allows the sender to reveal this seed to the receiver. Subsequently, the receiver can perform a consistency check to make sure the sender followed the protocol honestly.
3.3.1 Malicious notary
The protocol is secure against a malicious notary, because he is the OT receiver, which means that there is actually no input from him during the protocol execution except for the final MAC output. He just receives the OT input from the user, so the only thing he can do is to provide a wrong MAC keyshare. This will cause the server to reject the MAC when the user sends the request. The protocol simply aborts.
3.3.2 Malicious user
A malicious user could actually manipulate what he sends in the OT and potentially endanger the security of the protocol by leaking the notary's MAC key. To address this we force the user to reveal his MAC key after the server response so that the notary can check for the correctness of the whole MAC 2PC protocol. Then if the notary detects that the user cheated, he would simply abort the protocol.
The only problem when doing this is, that we want the whole TLSNotary protocol to work under the assumption that the notary can intercept the traffic between the user and the server. This would allow the notary to trick the user into thinking that the TLS session is already terminated, if he can force the server to respond. The user would send his MAC key share too early and the notary could, now having the complete MAC key, forge the ciphertext and create a valid MAC for it. He would then send this forged request to the server and forward the response of the server to the user.
To prevent this scenario we need to make sure that the TLS connection to the
server is terminated before the user sends his MAC key share to the notary.
Following the TLS RFC,
we leverage close_notify
to ensure all messages sent to the server have been
processed and the connection is closed. Unfortunately, many server TLS
implementations do not support close_notify
. In these cases we instead send an
invalid message to the server which forces it to respond with a fatal alert
message and close the connection.
FiniteField Arithmetic
Some protocols used in TLSNotary need to convert twoparty sharings of products or sums of some field elements into each other. For this purpose we use share conversion protocols which use oblivious transfer (OT) as a subprotocol. Here we want to have a closer look at the security guarantees these protocols offer.
Adding covert security
Our goal is to add covert security to our share conversion protocols. This
means that we want an honest party to be able to detect a malicious adversary,
who is then able to abort the protocol. Our main concern is that the adversary
might be able to leak private inputs of the honest party without being noticed.
For this reason we require that the adversary cannot do anything which would
give him a better chance than guessing the private input at random, which is
guessing $k$ bits with a probability of $2_{−k}$ for not being detected.
In the following we want to have closer look at how the sender and receiver can deviate from the protocol.
Malicious receiver
Note that in our protocol a malicious receiver cannot forge the protocol output, since he does not send anything to the sender during protocol execution. Even when this protocol is embedded into an outer protocol, where at some point the receiver has to open his output or a computation involving it, then all he can do is to open an output $y_{′}$ with $y_{′}=y$, which is just equivalent to changing his input from $b→b_{′}$.
Malicious sender
In the case of a malicious sender the following things can happen:
 The sender can impose an arbitrary field element $b_{′}$ as input onto the receiver without him noticing. To do this he simply sends $(t_{i},t_{i})$ in every OT, where $k$ is ith bit of $b_{′}$.
 The sender can execute a selectivefailure attack, which allows him to learn any predicate about the receiver's input. For each OT round $i$, the sender alters one of the OT values to be $T_{i}=t_{i}+c_{i}$, where $c_{i}∈F,k∈{0,1}$. This will cause that in the end the equation $a⋅b=x+y$ no longer holds but only if the forged OT value has actually been picked by the receiver.
 The sender does not use a random number generator with a seed $r$ to sample the masks $s_{i}$, instead he simply chooses them at will.
M2A Protocol Review
Without loss of generality let us recall the MultiplicationToAddition (M2A) protocol, but our observations also apply to the AdditionToMultiplication (A2M) protocol, which is very similar. We start with a short review of the M2A protocol.
Let there be a sender with some field element $a$ and some receiver with another field element $b$. After protocol execution the sender ends up with $x$ and the receiver ends up with $y$, so that $a⋅b=x+y$.
 $a,b,x,y∈F$
 $r$  rng seed
 $m$  bitlength of elements in $F$
 $n$  bitlength of rng seed
OT Sender
with input $a∈F,r←{0,1}_{n}$
 Sample some random masks: $s_{i}=rng(r,i),0≤i<m,s_{i}∈F$
 For every $s_{i}$ compute:
 $t_{i}=s_{i}$
 $t_{i}=a⋅2_{i}+s_{i}$
 Compute new share: $x=−∑s_{i}$
 Send $i$ OTs to receiver: $(t_{i},t_{i})$
OT Receiver
with input $b∈F$
 Set $v_{i}=t_{i}$ (from OT)
 Compute new share: $y=∑v_{i}$
Replay protocol
In order to mitigate the mentioned protocol deviations in the case of a malicious sender we will introduce a replay protocol.
In this section we will use capital letters for values sent in the replay protocol, which in the case of an honest sender are equal to their lowercase counterparts.
The idea for the replay protocol is that at some point after the conversion protocol, the sender has to reveal the rng seed $r$ and his input $a$ to the receiver. In order to do this, he will send $R$ and $A$ to the receiver after the conversion protocol has been executed. If the sender is honest then of course $r==R$ and $a==A$. The receiver can then check if the value he picked during protocol execution does match what he can now reconstruct from $R$ and $A$, i.e. that $T_{i}==t_{i}$.
Using this replay protocol the sender at some point reveals all his secrets because he sends his rng seed and protocol input to the receiver. This means that we can only use covertly secure share conversion with replay as a subprotocol if it is acceptable for the outer protocol, that the input to shareconversion becomes public at some later point.
Now in practice we often want to execute several rounds of shareconversion, as we need to convert several field elements. Because of this we let the sender use the same rng seed $r$ to seed his rng once and then he uses this rng instance for all protocol rounds. This means we have $l$ protocol executions $a_{n}⋅b_{n}=x_{n}+y_{n}$, and all masks $s_{n,i}$ produced from this rng seed $r$. So the sender will write his seed $R$ and all the $A_{n}$ to some tape, which in the end is sent to the receiver. As a security precaution we also let the sender commit to his rng seed before the first protocol execution. In detail:
Sender
 Sender has some inputs $a_{n}$ and picks some rng seed $r$.
 Sender commits to his rng seed and sends the commitment to the receiver.
 Sender sends all his OTs for $n$ protocol executions.
 Sender sends tape which contains the rng seed $R$ and all the $A_{n}$.
Receiver
 Receiver checks that $R$ is indeed the committed rng seed.
 For every protocol execution $l$ the receiver checks that $T_{n,i}==t_{n,i}$.
Having a look at the ways a malicious sender could cheat from earlier, we notice:
 The sender can no longer impose an arbitrary field element $b_{′}$ onto the receiver, because the receiver would notice that $t=T$ during the replay.
 The sender can still carry out a selectivefailure attack, but this is equivalent to guessing $k$ bits of $b$ at random with a probability of $2_{−k}$ for being undetected.
 The sender is now forced to use an rng seed to produce the masks, because during the replay, these masks are reproduced from $R$ and indirectly checked via $t==T$.