CryptoDay @ NYU, Friday July 14, 2017
July 14, 2017 (Friday) at NYU, WWH 1302, Warren Weaver Hall, 251 Mercer Street, New York, NY 10012.
Program
9:30 – 10:00.  Introduction/Coffee 
10:00 – 10:50.  Oxana Poburinnaya (Boston University) Equivocating Yao: ConstantRound Adaptively Secure Multiparty Computation in the Plain Model 
11:00 – 11:50.  Saleet Klein (MIT) The Edited Truth 
12:00 – 2:00.  Lunch (not provided) 
2:00 – 2:50.  Justin Holmgren (MIT) NonInteractive Delegation and Batch NP Verification from Standard Computational Assumptions 
3:00 – 3:50.  Muthuramakrishnan Venkitasubramaniam (University of Rochester) Garbled Circuits Meet PCPs: Active Security with Constant Communication Overhead in the Plain Model 
Venue
Address: NYU, WWH 1302, Warren Weaver Hall, 251 Mercer Street, New York, NY 10012.
[Directions] [Google Maps]
Organizers
Fabrice Benhamouda (IBM Research)
Tal Rabin (IBM Research)
with the help and support of Yevgeniy Dodis (NYU).
Support
Some travel support for NY CryptoDay is provided by DIMACS/Simons Collaboration in Cryptography through NSF grant #CNS1523467.
Abstracts

Equivocating Yao: ConstantRound Adaptively Secure Multiparty Computation in the Plain Model / Oxana Poburinnaya (Boston University)
Yao’s garbling scheme is one of the basic building blocks of cryptographic protocol design. Originally designed to enable twomessage, twoparty secure computation, the scheme has been extended in many ways and has innumerable applications. Still, a basic question has remained open throughout the years: Can the scheme be extended to guarantee security in the face of an adversary that corrupts both parties, adaptively, as the computation proceeds?
We answer this question in the affirmative. We define a new type of encryption, called functionally equivocal encryption (FEE), and show that when Yao’s scheme is implemented with an FEE as the underlying encryption mechanism, it becomes secure against such adaptive adversaries. We then show how to implement FEE from any one way function.
Combining our scheme with noncommitting encryption, we obtain the first twomessage, twoparty computation protocol, and the first constantround multiparty computation protocol, in the plain model, that are secure against semihonest adversaries who can adaptively corrupt all parties.
Joint work with Ran Canetti and Muthuramakrishnan Venkitasubramaniam.
 The Edited Truth / Saleet Klein (MIT)
We introduce two new cryptographic notions and accompanying constructions: encryption with deniable edits and encryption with invisible edits. An encryption scheme that supports deniable edits allows a user who owns a secret key sk and a large corpus of encrypted data c such that m = Dec_sk(c), to generate an alternative but legitimate looking secret key sk_{c,e} that decrypts c to an alternative “edited” data m’=Edit(m,e). Here, Edit is some supported edit function and e is a description of the particular edit to be applied. This generalizes classical receiver deniable encryption, which can be viewed as a special case of deniable edits where the edit function performs a complete replacement of the original data with e=m’. The new flexibility will allow us to design solutions with much smaller key sizes than required in classical receiver deniable encryption.Whereas deniable edits enable a user to modify the meaning of a single ciphertext in “hindsight”, the goal of encryption with invisible edits is to enable ongoing modifications of multiple ciphertexts. In the symmetrickey setting, there are “privileged” users (e.g., company managers) that know a secret key sk and “unprivileged” users (e.g., assistants) that know a different secret key sk_e. When a privileged user encrypts some message m, other privileged users can decrypt it correctly, but to an unprivileged user it will look like an encryption of m’ = Edit(m,e). In the publickey variant of invisibleedits, we further distinguish between privileged senders/receivers with privileged encryption/decryption keys pk and sk respectively vs. unprivileged senders/receivers with unprivileged encryption/decryption keys pk_e and sk_e respectively. Although users cannot tell if they are privileged or not, unprivileged receivers will only be able to recover edited messages from ciphertexts generated by privileged senders.Under the assumption that standard publickey encryption schemes exist, we show how to construct a publickey encryption scheme with deniable edits and a public key encryption scheme with invisible edits for any polynomialtime computable edit function. The size of the secret key sk in our constructions is (inherently) proportional to the description size e of the supported edits, but (in contrast with classical receiver deniable encryption) can be much smaller than the size m of the data itself. We also construct symmetric key encryption schemes with deniable edits and symmetric key encryption schemes with invisible edits, which only require the assumption that oneway functions exist.Joint work with Shafi Goldwasser and Daniel Wichs.

NonInteractive Delegation and Batch NP Verification from Standard Computational Assumptions / Justin Holmgren (MIT)
We present an adaptive and noninteractive protocol for verifying arbitrary efficient computations in fixed polynomial time. Our protocol is computationally sound and can be based on any computational PIR scheme, which in turn can be based on standard polynomialtime cryptographic assumptions (e.g. the worst case hardness of polynomialfactor approximation of shortvector lattice problems). In our protocol, the prover and the verifier do not need to interact at all: The verifier sets up a public key ahead of time, and this key can be used by any prover to prove arbitrary statements in a completely adaptive manner. Verification is done using a secret verification key, and soundness relies on this key not being known to the prover. Our protocol further allows to prove statements about computations of arbitrary RAM machines.Previous works either relied on knowledge assumptions, or could only offer nonadaptive twomessage protocols (where the first message could not be reused), and required either obfuscationbased assumptions or superpolynomial hardness assumptions.Additionally, for any NP language L, we show a 2message argument of knowledge which enjoys “batch succinctness” — the communication complexity is the size of one witness, but allows proving membership in L for many instances simultaneously.Joint work with Zvika Brakerski and Yael Tauman Kalai.
 Garbled Circuits Meet PCPs: Active Security with Constant
Communication Overhead in the Plain Model / Muthuramakrishnan Venkitasubramaniam (University of Rochester)
We consider the problem of constantround secure twoparty computation in the presence of active (malicious) adversaries. We present the first protocol that has only a constant multiplicative communication overhead compared to Yao’s protocol for passive adversaries, and can be implemented in the plain model by only making a blackbox use of (parallel) oblivious transfer and a pseudorandom generator. A similar result could previously be obtained only in an amortized setting, using preprocessing, or by assuming bitoblivioustransfer as an ideal primitive that has a unit communication cost. Our protocol also has the feature of using a small number of oblivious transfers and can be implemented with polylogarithmic (in the security parameter) computational overhead compared to its passivesecure counterpart. The protocol relies on a novel combination of previous techniques, together with a new variant of previous “MPC in the head” techniques that can be viewed as providing a constantrate interactive zeroknowledge PCP.An independently useful byproduct of our techniques is a simple sublinear zeroknowledge argument protocol for NP from any collisionresistant hash function, whose communication complexity is roughly the squareroot of the verification circuit size. This is the first sublinear argument protocol that simultaneously avoids heavy PCP machinery and the use of publickey cryptography. The protocol can be made noninteractive in the random oracle model.Joint work with Carmit Hazay and Yuval Ishai.