Oct 26, 2018 (Friday) at Columbia University, the Mudd Building, Computer Science Dept, 500 West 120th Street, New York, NY. CS 480 (new CS conference room).
Program
| 09:30 – 10:00. | Introduction/Coffee |
| 10:00 – 10:50. |
Kevin Yeo (Google LLC) PanORAMa: Oblivious RAM with Logarithmic Overhead |
| 11:00 – 11:50. |
Naomi Ephraim (Cornell University) On the Complexity of Compressing Obfuscation |
| 12:00 – 02:00. | Lunch (not provided) |
| 02:00 – 02:50. |
Giorgos Zirdelis (Northeastern University) PPP-Completeness with Connections to Cryptography |
| 03:00 – 03:50. |
Mariana Raykova (Yale University) A Simple Obfuscation Scheme for Pattern-Matching with Wildcards |
Venue
Address: Columbia University, the Mudd Building, Computer Science Dept, 500 West 120th Street, New York, NY. CS 480 (new CS conference room).
CS 480 (new CS conference room): 480 CS conference room is located in the Computer Science Building, itself located in the lobby of the 4th floor of the Mudd Engineering Building. Note that this is a different room than before.
The department office is at the entrance to the Computer Science Building, itself located in the lobby of the 4th floor of the Mudd Engineering Building. There are doors to Mudd on the 1st floor at 500 West 120th Street (near Amsterdam Avenue). The Mudd doors on the campus level are on the 4th floor. Starting at the main entrance to the campus at Broadway and 116th Street, walk along College Walk and turn left up the steps. At the top of the steps is a large building with a dome: Low Library. Take the walkway to the right of Low Library, and the Mudd building is at the end of this walk. Upon entering Mudd, turn right and then right again. This is the entrance to Computer Science.
Organizers
Fabrice Benhamouda (IBM Research)
Tal Rabin (IBM Research)
with the help and support of Tal Malkin (Columbia).
Support
Some travel support for NY CryptoDay is provided by DIMACS/Simons Collaboration in Cryptography through NSF grant #CNS-1523467.
Abstracts
-
PanORAMa: Oblivious RAM with Logarithmic Overhead / Kevin Yeo (Google LLC)
We present PanORAMa, the first Oblivious RAM construction that achieves communication overhead O(logN⋅loglogN) for database of N blocks and for any block size B=Ω(logN) while requiring client memory of only a constant number of memory blocks. Our scheme is only an O(loglogN) factor away from the Ω(logN) lower bound shown by Larsen and Nielsen [CRYPTO ’18].
Our construction follows the hierarchical approach to ORAM design and relies on two main building blocks of independent interest: a new oblivious hash table construction with improved amortized O(logN+poly(loglogλ)) communication overhead for security parameter λ and N=poly(λ), assuming its input is randomly shuffled; and a complementary new oblivious random multi-array shuffle construction, which shuffles N blocks of data with communication O(Nloglogλ+NlogNlogλ) when the input has a certain level of entropy. We combine these two primitives to improve the shuffle time in our hierarchical ORAM construction by avoiding heavy oblivious shuffles and leveraging entropy remaining in the merged levels from previous shuffles. As a result, the amortized shuffle cost is asymptotically the same as the lookup complexity in our construction.
This is a joint work with Sarvar Patel, Giuseppe Persiano and Mariana Raykova.
-
On the Complexity of Compressing Obfuscation / Naomi Ephraim (Cornell University)
Indistinguishability obfuscation has become one of the most exciting cryptographic primitives due to its far reaching applications in cryptography and other fields. However, to date, obtaining a plausibly secure construction has been an illusive task, thus motivating the study of seemingly weaker primitives that imply it, with the possibility that they will be easier to construct. We provide a systematic study of compressing obfuscation, one of the most natural and simple to describe primitives that is known to imply indistinguishability obfuscation when combined with standard assumptions. A compressing obfuscator is roughly an indistinguishability obfuscator that outputs just a slightly compressed encoding of the truth table. This generalizes notions introduced by Lin et al. (PKC 2016) and Bitansky et al. (TCC 2016) by allowing for a broader regime of parameters.
We view compressing obfuscation as an independent cryptographic primitive and show various positive and negative results concerning its power and plausibility of existence, demonstrating significant differences from full-fledged indistinguishability obfuscation. First, we show that as a cryptographic building block, compressing obfuscation is weak. In particular, when combined with one-way functions, it cannot be used in a black-box way to achieve public-key encryption, even under (sub-)exponential security assumptions. This is in sharp contrast to indistinguishability obfuscation, which together with one-way functions implies almost all cryptographic primitives. Second, we show that to construct compressing obfuscation with perfect correctness, one only needs to assume its existence with a very weak correctness guarantee and polynomial hardness (along with standard assumptions). Lastly, we characterize the existence of compressing obfuscation with statistical security, showing a deep connection between compressing obfuscation and various concepts in complexity theory and learning theory.
This is joint work with Gilad Asharov, Ilan Komargodski, and Rafael Pass.
-
PPP-Completeness with Connections to Cryptography / Giorgos Zirdelis (Northeastern University)
Polynomial Pigeonhole Principle (PPP) is an important subclass of TFNP with profound connections to the complexity of the fundamental cryptographic primitives: collision-resistant hash functions and one-way permutations. In contrast to most of the other subclasses of TFNP, no complete problem is known for PPP. Our work identifies the first PPP-complete problem without any circuit or Turing Machine given explicitly in the input, and thus we answer a longstanding open question from [Papadimitriou1994]. Specifically, we show that constrained-SIS (cSIS), a generalized version of the well-known Short Integer Solution problem (SIS) from lattice-based cryptography, is PPP-complete.
In order to give intuition behind our reduction for constrained-SIS, we identify another PPP-complete problem with a circuit in the input but closely related to lattice problems. We call this problem BLICHFELDT and it is the computational problem associated with Blichfeldt’s fundamental theorem in the theory of lattices.
Building on the inherent connection of PPP with collision-resistant hash functions, we use our completeness result to construct the first natural hash function family that captures the hardness of all collision-resistant hash functions in a worst-case sense, i.e. it is natural and universal in the worst-case. The close resemblance of our hash function family with SIS, leads us to the first candidate collision-resistant hash function that is both natural and universal in an average-case sense.
Finally, our results enrich our understanding of the connections between PPP, lattice problems and other concrete cryptographic assumptions, such as the discrete logarithm problem over general groups.
Joint work with Katerina Sotiraki and Manolis Zampetakis.
-
A Simple Obfuscation Scheme for Pattern-Matching with Wildcards / Mariana Raykova (Yale University)
We give a simple and efficient method for obfuscating pattern matching with wildcards. In other words, we construct a way to check an input against a secret pattern, which is described in terms of prescribed values interspersed with unconstrained “wildcard” slots. As long as the support of the pattern is sufficiently sparse and the pattern itself is chosen from an appropriate distribution, we prove that a polynomial-time adversary cannot find a matching input, except with negligible probability. We rely upon the generic group heuristic (in a regular group, with no multilinearity). Previous work provided less efficient constructions based on multilinear maps or LWE.
Joint work with Allison Bishop, Lucas Kowalczyk, Tal Malkin, Valerio Pastro, Kevin Shi.
