Warning: Registration is free but mandatory.
Mar 2, 2018 (Friday) at Cornell Tech, Bloomberg Center, room 165.
|9:30 – 10:00.||Introduction/Coffee|
|10:00 – 10:50.||Fabrice Benhamouda (IBM → Columbia)
k-Round MPC from k-Round OT via Garbled Interactive Circuits
|11:00 – 11:50.||Sophia Yakoubov (Boston University)
Fuzzy Password-Authenticated Key Exchange
|12:00 – 2:00.||Lunch (not provided)|
|2:00 – 2:50.||Ilan Komargodski (Cornell Tech)
Collision Resistant Hashing for Paranoids:
Dealing with Multiple Collisions
|3:00 – 3:50.||Alex Lombardi (MIT)
Anonymous IBE, Leakage Resilience and Circular Security from New Assumptions
Registration Very Important
Registration for attending this event is free but mandatory. You can register by going to the registration form. Please register by Wed. Feb 28, 2017 11:59 PM EST. Only registered participants will be allowed on Cornell Tech premises
Cornell Tech, Bloomberg Center, room 165
2 West Loop Road
New York NY 10044
Fabrice Benhamouda (IBM Research → Columbia University)
Tal Rabin (IBM Research)
with the help and support of Rafael Pass (Cornell Tech).
Some travel support for NYC Crypto Day is provided by DIMACS/Simons Collaboration in Cryptography through NSF grant #CNS-1523467.
- k-Round MPC from k-Round OT via Garbled Interactive Circuits / Fabrice Benhamouda (IBM → Columbia)
We present new constructions of round-efficient, or even round-optimal, Multi-Party Computation (MPC) protocols from Oblivious Transfer (OT) protocols. Our constructions establish a tight connection between MPC and OT: In the setting of semi-honest security, for any k≥2, k-round semi-honest OT is necessary and complete for k-round semi-honest MPC. In the round-optimal case of k=2, we obtain 2-round semi-honest MPC from 2-round semi-honest OT, resolving the round complexity of semi-honest MPC assuming weak and necessary assumption. In comparison, previous 2-round constructions rely on either the heavy machinery of indistinguishability obfuscation or witness encryption, or the algebraic structure of bilinear pairing groups. More generally, for an arbitrary number of rounds k, all previous constructions of k-round semi-honest MPC require at least OT with k′ rounds for k′≤⌊k/2⌋.In the setting of malicious security, we show: For any k≥5, k-round malicious OT is necessary and complete for k-round malicious MPC. In fact, OT satisfying a weaker notion of delayed-semi-malicious security suffices. In the common reference string model, for any k≥2, we obtain k-round malicious Universal Composable (UC) protocols from any k-round semi-malicious OT and non-interactive zero-knowledge. Previous 5-round protocols in the plain model, and 2-round protocols in the common reference string model all require algebraic assumptions such as DDH or LWE.At the core of our constructions is a new framework for garbling interactive circuits. Roughly speaking, it allows for garbling interactive machines that participates in interactions of a special form. The garbled machine can emulate the original interactions receiving messages sent in the clear (without being encoded using secrets), and reveals only the transcript of the interactions, provided that the transcript is computationally uniquely defined. We show that garbled interactive circuits for the purpose of constructing MPC can be implemented using OT. Along the way, we also propose a new primitive of witness selector that strengthens witness encryption, and a new notion of zero-knowledge functional commitments.
Joint work with Huijia (Rachel) Lin.
- Fuzzy Password-Authenticated Key Exchange / Sophia Yakoubov (Boston University)
Consider key agreement by two parties who start out knowing a common secret (which we refer to as “pass-string”, a generalization of “password”), but face two complications: (1) the pass-string may come from a low-entropy distribution, and (2) the two parties’ copies of the pass-string may have some noise, and thus not match exactly. We provide the first efficient and general solutions to this problem that enable, for example, key agreement based on commonly used biometrics such as iris scans. The problem of key agreement with each of these complications individually has been well studied in literature. Key agreement from low-entropy shared pass-strings is achieved by password-authenticated key exchange (PAKE), and key agreement from noisy but high-entropy shared pass-strings is achieved by information-reconciliation protocols as long as the two secrets are “close enough.” However, the problem of key agreement from noisy low-entropy pass-strings has never been studied. We introduce (universally composable) fuzzy password-authenticated key exchange (fPAKE), which solves exactly this problem. fPAKE does not have any entropy requirements for the pass-strings, and enables secure key agreement as long as the two pass-strings are “close” for some notion of closeness. We also give two constructions. The first construction achieves our fPAKE definition for any (efficiently computable) notion of closeness, including those that could not be handled before even in the high-entropy setting. It uses Yao’s Garbled Circuits in a way that is only two times more costly than their use against semi-honest adversaries, but that guarantees security against malicious adversaries. The second construction is more efficient, but achieves our fPAKE definition only for pass-strings with low Hamming distance. It builds on very simple primitives: robust secret sharing and PAKE.
Joint work with Pierre-Alain Dupont and Julia Hesse and David Pointcheval and Leonid Reyzin.
- Collision Resistant Hashing for Paranoids: Dealing with Multiple Collisions / Ilan Komargodski (Cornell Tech)
A collision resistant hash (CRH) function is one that compresses its input yet it is hard to find a collision, i.e. a x_1 != x_2 s.t. h(x_1) = h(x_2). Collision resistant hash functions are one of the more useful cryptographic primitives both in theory and in practice and two prominent applications are in signature schemes and succinct zero-knowledge arguments. We consider a relaxation of the above requirement that we call Multi-CRH, a function where it is hard to find x_1, x_2,…,x_k which are all distinct, yet h(x_1) = h(x_2) = … = h(x_k). We show that in major applications of CRH functions it is possible to replace them by the weaker notion of an MCRH, albeit at some price. On the other hand we show black-box separation results from standard CRH and a hierarchy of such Multi-CRHs.
Based on a joint work with Moni Naor and Eylon Yogev.
- Anonymous IBE, Leakage Resilience and Circular Security from New Assumptions / Alex Lombardi (MIT)
In anonymous identity-based encryption (IBE), ciphertexts not only hide their corresponding messages, but also their target identity. We construct an anonymous IBE scheme based on the Computational Diffie-Hellman (CDH) assumption in general groups (and thus, as a special case, based on the hardness of factoring Blum integers).Our approach extends and refines the recent tree-based approach of Cho et al. (CRYPTO’17) and Döttling and Garg (CRYPTO’17). Whereas the tools underlying their approach do not seem to provide any form of anonymity, we introduce two new building blocks which we utilize for achieving anonymity: blind garbled circuits (which we construct based on any one-way function), and blind batch encryption (which we construct based on CDH).
We also show that the “batch encryption” building block is useful for constructions in the realm of leakage resilience and KDM (or circular) security, and can additionally be constructed from the Learning Parity with Noise (LPN) assumption, albeit with very small noise rate. This also yields an LPN-based IBE scheme.
Joint work with Zvika Brakerski, Gil Segev, and Vinod Vaikuntanathan.