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 DachmanSoled (University of Maryland) Limits to NonMalleability 
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 DesignatedVerifier 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 #CNS1523467.
Abstracts

Limits to NonMalleability / Dana DachmanSoled (University of Maryland)
There have been many successes in constructing explicit nonmalleable 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 nonmalleable code for a tampering class F?
We show that nonmalleable 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 nonmalleable codes against certain classes F via reductions to the assumption that a distributional problem is hard for F, that make blackbox use of the tampering functions in the proof. In particular, this yields concrete obstacles for the construction of efficient codes for NC, even assuming averagecase 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 endtoend 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 highlevel 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 noncommitting 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 blockcipherbased hashing.
Finally, we turn to metadataprivate 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 metadataprivate 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 nonwildcard 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 ReedSolomon 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 DesignatedVerifier NIZKs for all NP from CDH / Willy Quach (Northeastern University)
Noninteractive zeroknowledge 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 DiffieHellman (CDH/DDH) assumption without relying on a bilinear map.
In this paper, we study a relaxation of NIZKs in the designated verifier setting (DVNIZK), in which the public commonreference 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 onetime 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. Onetime DVNIZKs are known to exist for general NP statements assuming only publickey encryption. However, prior to this work, we did not have any construction of reusable DVNIZKs for general NP statements from any assumption under which we didn’t already also have standard NIZKs.
In this work, we construct reusable DVNIZKs for general NP statements under the CDH assumption, without requiring a bilinear map. Our construction is based on the hiddenbits paradigm, which was previously used to construct standard NIZKs. We define a cryptographic primitive called a hiddenbits generator (HBG), along with a designatedverifier variant (DVHBG), which modularly abstract out how to use this paradigm to get both standard NIZKs and reusable DVNIZKs. We construct a DVHBG scheme under the CDH assumption by relying on techniques from the CramerShoup hashproof system, and this yields our reusable DVNIZK for general NP statements under CDH.
We also consider a strengthening of DVNIZKs to the malicious designatedverifier setting (MDVNIZK) 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 MDVNIZKs under the “onemore CDH” assumption without relying on bilinear maps.
Joint work with Ron D. Rothblum and Daniel Wichs.