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: Constant-Round 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) Non-Interactive 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 #CNS-1523467.
Abstracts
-
Equivocating Yao: Constant-Round 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 two-message, two-party 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 non-committing encryption, we obtain the first two-message, two-party computation protocol, and the first constant-round multiparty computation protocol, in the plain model, that are secure against semi-honest 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 symmetric-key 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 public-key variant of invisible-edits, 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 public-key encryption schemes exist, we show how to construct a public-key encryption scheme with deniable edits and a public key encryption scheme with invisible edits for any polynomial-time 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 one-way functions exist.Joint work with Shafi Goldwasser and Daniel Wichs.
-
Non-Interactive Delegation and Batch NP Verification from Standard Computational Assumptions / Justin Holmgren (MIT)
We present an adaptive and non-interactive 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 polynomial-time cryptographic assumptions (e.g. the worst case hardness of polynomial-factor approximation of short-vector 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 non-adaptive two-message protocols (where the first message could not be re-used), and required either obfuscation-based assumptions or super-polynomial hardness assumptions.Additionally, for any NP language L, we show a 2-message 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 constant-round secure two-party 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 black-box use of (parallel) oblivious transfer and a pseudo-random generator. A similar result could previously be obtained only in an amortized setting, using preprocessing, or by assuming bit-oblivious-transfer 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 passive-secure 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 constant-rate interactive zero-knowledge PCP.An independently useful byproduct of our techniques is a simple sub-linear zero-knowledge argument protocol for NP from any collision-resistant hash function, whose communication complexity is roughly the square-root of the verification circuit size. This is the first sublinear argument protocol that simultaneously avoids heavy PCP machinery and the use of public-key cryptography. The protocol can be made non-interactive in the random oracle model.Joint work with Carmit Hazay and Yuval Ishai.
