To ensure malicious security of the Garbled Circuits 2PC, TLSNotary uses the Dual Execution protocol (see Section 7.6).

DualEX inherently leaks n bits of private input with probability . This is not a problem during the TLS handshake when the private inputs are symmetric keys or hash pre-images. Leaking n bits does not give the adversary any advantage, since with the same probability the adversary may have guessed those bits while brute-forcing the key or the pre-image.

However, the leakage becomes a problem when encrypting the request or decrypting the response, since leaking even 1 bit of the plaintext may be catastrophic for the User's privacy. To overcome this leakage, we use a variant of DualEx where privacy is guaranteed only for the User.