Our next Crypto Day will be May 6th at Georgetown.  We will hold in it in room 155 of the business school building; see here for directions.  Please find the abstract of the talks below.  The plan is to allocate 1 hour 20 minutes for each talk, with the talk itself to an hour, and then there can be 20 minutes (hopefully lively) questions/discussion. In terms of getting to Georgetown, check out the GUTS bus.  Otherwise, the closest metro stop is probably Foggy Bottom.


Preliminary schedule:

9-9:40AM: Welcome breakfast
9:40-11AM Mukul
11AM-12:20PM Mohammad
12:20PM-2PM Lunch (on your own)
2pm-3:20pm Paul
3:20-4:40pm George


Non-Malleable Codes for Bounded Depth, Bounded Fan-in Circuits

Mukul R. Kulkarni

Non-malleable codes are a relaxation of error correcting codes, for settings in which privacy, but not necessarily correctness, is desired. Instead of requiring that after modification—i.e. tampering—of the codeword, the original message can always be recovered, non-malleable codes allow a different message to be recovered, as long as the recovered message is unrelated to the original message.  This relaxation potentially allows for the construction of coding schemes for rich classes of tampering classes, beyond what can be done for error correcting codes. In applications, non-malleable codes are used to encode the memory of a device, and thus protect against (certain classes) of adversarial tampering.

Dziembowski et al. [ITCS 2010] introduced the notion of non-malleable codes and since then, constructing such codes has been a highly active area of research. Unfortunately, nearly all previous results consider only “compartmentalized” tampering classes, wherein a codeword is split into blocks and the attacker is assumed to tamper with different blocks of codeword independently of each other.
In our work, we consider a natural, non-compartmentalized class of tampering functions. Specifically, we present non-malleable codes secure against tampering functions that can be represented by bounded depth, bounded fan-in circuits. More generally, our scheme is resilient against “local” tampering functions wherein any output bit is dependent on at most n^{\delta} bits, where n is the total number of bits in the codeword and 0 \leq \delta < 1 is a constant. Notably this function class includes NC^0.
Bio: Mukul R. Kulkarni is a doctoral student at the University of Maryland, College Park studying under the guidance of Dr. Dana Dachman-Soled. His research interests involve Tamper Resilient Cryptography.


Lower-Bounds on Assumptions behind Indistinguishability Obfuscation

Mohammad Mahmoody


In this talk, we first show that basing IO on a variety of assumptions (e.g., trapdoor permutations, bi-linear maps, etc) in a weakly black-box way is as hard as basing public-key encryption on one-way functions (in a non-black-box way). The latter has remained as one of the most challenging open questions in cryptography. Then, by combining our results with a recent result of Brakerski, Brzuska, and Fleischhacker, we rule out any fully black-box construction of IO from the same set of primitives assuming the existence of one-way functions and that the polynomial-hierarchy does not collapse.

Based on joint works with Ameer Mohammed, Soheil Nematihaji, Rafael Pass, and abhi shelat.
Bio: Mohammad Mahmoody is an assistant professor at the Univ of Virginia. He got his PhD from Princeton in 2010 under supervision of Boaz Barak and then spent a few years in Rafael Pass’s crypto group at Cornell before joining UVa in 2013.

New Inference Attacks on Order-Preserving and Order-Revealing Encryption

Paul Grubbs

Order-preserving Encryption (OPE) has, of late, received a great deal of attention from the research community and from industry. It has proven to be an enormously useful tool in areas like cloud security and encrypted databases. However, for most plaintext distributions of practical interest very little is known about the concrete security of OPE. In this talk, I will describe some new cryptanalytic attacks on OPE and order-revealing encryption. I will also motivate stronger adversarial models and present new attacks in those settings. Finally, I will present experimental results of implementing the attacks on several data sets. Our results show that the concrete security of OPE and ORE is very low in some settings, and that more work is needed to understand the consequences (and hopefully, the limits) of inference attacks against encryption schemes that leak order. Joint work with Kevin Sekniqi, Muhammad Naveed, and Tom Ristenpart.
Bio: Paul Grubbs is a PhD student in Computer Science at Cornell University and Cornell Tech, working on the theory and practice of cryptography. Currently he is interested in property-preserving encryption, searchable encryption, and applied crypto. Before starting his PhD, he worked for two and a half years as a cryptography engineer at Skyhigh Networks, a cloud security startup in Campbell, CA.

Accessing Data while Preserving Privacy

Georgios Kellaris

We initiate a formal research of the privacy-efficiency tradeoff of secure database systems. Such systems, such as CryptDB and Cipher-base, try to mitigate the high costs of full-fledged cryptographic solutions by relaxing the security guarantees they provide. We provide abstract models that capture the basic properties of these systems and identify their fundamental leakage channels. These models allow performing a generic and implementation independent investigation of the inherent tradeoffs between security and efficiency. In particular, this modeling allows us in some cases to devise generic reconstruction attacks where the server learns the secret attributes of every record stored in the database, pointing to inherent limitations of these models.

We present a new model of differentially private storage where differential privacy is preserved even against an attacker that controls the data and the queries made to it. We give a generic construction of differentially private storage that combines ORAM and differentially private sanitizers. We also provide efficient constructions and lower bounds for some specific query sets. We have implemented some of our algorithms, and report on their efficiency.Joint work with Georgios Kellaris, George Kollios, Kobbi Nissim, and Adam O’Neill.

Bio: Georgios is currently a Post-Doctoral Fellow at CRCS, Harvard University, and at Boston University. He received his Ph.D. degree in Computer Science and Engineering from the Hong Kong University of Science and Technology (2015), under the supervision of prof. Dimitris Papadias, and with the support of the Hong Kong Ph.D. Fellowship Scheme. He holds a 4-year B.Sc. in Informatics and Telecommunications from the University of Athens (2006) and a 2-year M.Sc. degree in Digital Systems from the University of Piraeus (2008). He has worked as a researcher at the University of Piraeus in Greece, the Singapore Management University and the Nanyang Technological University in Singapore, and at Boston University. His research interests include databases and differential privacy.