Warning: Registration is free but mandatory. Registration deadline: May 01, 2019, 11:59 PM.
May 03, 2019 (Friday) at Google, 111 8th Ave, New York, NY 10011.
Program
| 09:30 – 10:00. | Introduction/Coffee |
| 10:00 – 10:50. |
Dana Dachman-Soled (University of Maryland) Limits to Non-Malleability |
| 11:00 – 11:50. |
Paul Grubbs (Cornell Tech) Message Franking: Invisible Salamanders, Encryptment, and AMFs |
| 12:00 – 02:00. | Lunch (not provided) |
| 02:00 – 02:50. |
Fermi Ma (Princeton) New Techniques for Obfuscating Conjunctions |
| 03:00 – 03:50. |
Mark Simkin (Aarhus University) The Communication Complexity of Threshold Private Set Intersection |
| 03:50 – 04:20. | Ice Cream Social |
| 04:20 – 05:10. |
Willy Quach (Northeastern University) Reusable Designated-Verifier NIZKs for all NP from CDH |
Registration Very important
Registration is free but mandatory.
Registration deadline: May 03, 2019, 00:00 (ET).
Only registered participants will be allowed to enter.
Venue
Address: Google, 111 8th Ave, New York, NY 10011.
Room 3E206 Mega Bell
Visitors need to be accompanied to the room. Please arrive in advance.
Organizers
Fabrice Benhamouda (IBM Research)
Tal Rabin (IBM Research)
with the help and support of Tancrède Lepoint (Google).
Support
Some travel support for NY CryptoDay is provided by DIMACS/Simons Collaboration in Cryptography through NSF grant #CNS-1523467.
Abstracts
-
Limits to Non-Malleability / Dana Dachman-Soled (University of Maryland)
There have been many successes in constructing explicit non-malleable codes for various classes of tampering functions in recent years, and strong existential results are also known. In this work we ask the following question: When can we rule out the existence of a non-malleable code for a tampering class F?
We show that non-malleable codes are impossible to construct for three different tampering classes:
- Functions that change d/2 symbols, where d is the distance of the code;
- Functions where each input affects only a single output;
- Functions where each of the n outputs is a function of n-\log n input symbols.
We additionally rule out constructions of non-malleable codes against certain classes F via reductions to the assumption that a distributional problem is hard for F, that make black-box use of the tampering functions in the proof. In particular, this yields concrete obstacles for the construction of efficient codes for NC, even assuming average-case variants of P not in NC.
Joint work with Marshall Ball, Mukul Kulkarni and Tal Malkin.
-
Message Franking: Invisible Salamanders, Encryptment, and AMFs / Paul Grubbs (Cornell Tech)
A challenge in deploying end-to-end encrypted (E2EE) messaging is that it prevents the service provider from identifying abusive or threatening messages and taking punitive action against parties that send them. In this talk we study message franking, recently proposed by Facebook as a way to overcome this challenge. Message franking enables verifiable reporting of abusive messages sent in E2EE chats while preserving deniability.
First we will give a high-level overview of the architecture and security goals of message franking, using Facebook’s implementation as an example. Next, we will describe a vulnerability in Facebook’s message franking implementation: by exploiting the use of Galois/Counter mode for encrypting attachments, a sender can craft an abusive message that the receiver cannot report as abusive. We disclosed this vulnerability to Facebook and were awarded a bug bounty for it.
Because this flaw stems from the use of fast but non-committing authenticated encryption, we formalize compactly committing authenticated encryption (ccAE), a new primitive which is sufficient for message franking when the service provider can see communication metadata. We present a fast ccAE scheme called HFC and show its efficiency is essentially optimal via a lower bound on blockcipher-based hashing.
Finally, we turn to metadata-private messaging systems like Signal, where the service provider cannot see communication metadata. In such systems message franking schemes like Facebook’s cannot be used. Other seeming solutions for abuse reporting (such as digital signatures) cannot be used because they break deniability. To enable abuse reporting for metadata-private messaging we introduce asymmetric message franking (AMF) schemes. We describe security goals for AMFs as well as an instantiation based on proofs of knowledge.
Joint work with Jiahui Lu, Thomas Ristenpart, Yevgeniy Dodis, Joanne Woodage, Nirvan Tyagi, Ian Miers, and Julia Len.
-
New Techniques for Obfuscating Conjunctions / Fermi Ma (Princeton)
A conjunction over a binary alphabet is a boolean function specified by a length n pattern of 0’s, 1’s and wildcards. On input bit strings of length n, the function outputs 1 if the input matches the pattern at all non-wildcard positions. At CRYPTO 2018, Bishop et al. proposed a simple and elegant construction to obfuscate this class of functions by embedding the pattern in the error positions of a noisy Reed-Solomon codeword, and placing the codeword in a group exponent. They prove their scheme achieves a notion of security called “distributional virtual black box” in the generic group model for random conjunctions with at most 0.774n wildcards.
In this talk, we’ll abstract the Bishop et al. scheme to obtain a significantly more efficient “dual” scheme. In the generic group model, our scheme admits an intuitive proof of security and does not place any restrictions on the number of wildcards.
Next, we’ll describe a simple modification to the construction that avoids encoding in a group exponent and is secure under the Learning Parity with Noise (LPN) assumption. At the heart of our security proof is a reduction from standard LPN to LPN with “structured error.”
No prior knowledge of the Bishop et al. paper will be assumed.
Based on joint work with James Bartusek, Tancrède Lepoint, and Mark Zhandry.
https://eprint.iacr.org/2018/936.pdf
-
The Communication Complexity of Threshold Private Set Intersection / Mark Simkin (Aarhus University)
Threshold private set intersection enables Alice and Bob who hold sets A and B of size n to compute the intersection thereof if the sets do not differ by more than some threshold parameter t. In this work, we investigate the communication complexity of this problem and we establish the first upper and lower bounds. We show that any protocol has to have a communication complexity of Omega(t). We show that an up to polylog factors matching upper bound of O(t) can be obtained via fully homomorphic encryption. We present a computationally more efficient protocol based on weaker assumptions, namely additively homomorphic encryption, with a communication complexity of O(t^2). For applications like biometric authentication, where a given fingerprint has to have a large intersection with a fingerprint from a database, our protocols may result in significant communication savings. Prior to this work, all previous protocols had a communication complexity of Omega(n). Our protocols are the first ones with communication complexities that mainly depend on the threshold parameter t and only logarithmically on the set size n.
Joint work with Satrajit Ghosh.
-
Reusable Designated-Verifier NIZKs for all NP from CDH / Willy Quach (Northeastern University)
Non-interactive zero-knowledge proofs (NIZKs) are a fundamental cryptographic primitive. Despite a long history of research, we only know how to construct NIZKs under a few select assumptions, such as the hardness of factoring or using bilinear maps. Notably, there are no known constructions based on either the computational or decisional Diffie-Hellman (CDH/DDH) assumption without relying on a bilinear map.
In this paper, we study a relaxation of NIZKs in the designated verifier setting (DV-NIZK), in which the public common-reference string is generated together with a secret key that is given to the verifier in order to verify proofs. In this setting, we distinguish between one-time and reusable schemes, depending on whether they can be used to prove only a single statement or arbitrarily many statements. For reusable schemes, the main difficulty is to ensure that soundness continues to hold even when the malicious prover learns whether various proofs are accepted or rejected by the verifier. One-time DV-NIZKs are known to exist for general NP statements assuming only public-key encryption. However, prior to this work, we did not have any construction of reusable DV-NIZKs for general NP statements from any assumption under which we didn’t already also have standard NIZKs.
In this work, we construct reusable DV-NIZKs for general NP statements under the CDH assumption, without requiring a bilinear map. Our construction is based on the hidden-bits paradigm, which was previously used to construct standard NIZKs. We define a cryptographic primitive called a hidden-bits generator (HBG), along with a designated-verifier variant (DV-HBG), which modularly abstract out how to use this paradigm to get both standard NIZKs and reusable DV-NIZKs. We construct a DV-HBG scheme under the CDH assumption by relying on techniques from the Cramer-Shoup hash-proof system, and this yields our reusable DV-NIZK for general NP statements under CDH.
We also consider a strengthening of DV-NIZKs to the malicious designated-verifier setting (MDV-NIZK) where the setup consists of an honestly generated common random string and the verifier then gets to choose his own (potentially malicious) public/secret key pair to generate/verify proofs. We construct MDV-NIZKs under the “one-more CDH” assumption without relying on bilinear maps.
Joint work with Ron D. Rothblum and Daniel Wichs.
