NY CryptoDay will take place. But due to the winter storm, some talks might be canceled or moved.
Feb 10, 2017 (Friday) at Columbia University, the Mudd Building, Computer Science Dept, 500 West 120th Street, New York, NY. CS Conference Room and Lounge.
|9:30 – 10:00.||Introduction/Coffee|
|10:00 – 10:50.||Antigoni Polychronidou (Cornell Tech)
Secure Computation in the Tamper Proof Hardware Model
|11:00 – 11:50.||Gilad Asharov (Cornell Tech)
Privacy-Preserving Search of Similar Patients in Genomic Data
|12:00 – 2:00.||Lunch (not provided)|
|2:00 – 2:50.||Leonid Reyzin (Boston University)
Scrypt is Maximally Memory-Hard
|3:00 – 3:50.|
Address: Columbia University, the Mudd Building, Computer Science Dept, 500 West 120th Street, New York, NY.
CS Conference Room and Lounge: Follow directions to department office below, then go through double wooden-glass doors and head down hallway to left. The entrance to the CS lounge and conference room is to the right of the door leading outside to the courtyard.
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.
Fabrice Benhamouda (IBM Research)
Tal Rabin (IBM Research)
with the help and support of Tal Malkin (Columbia).
Some travel support for NYC Crypto Day is provided by DIMACS/Simons Collaboration in Cryptography through NSF grant #CNS-1523467.
- Secure Computation in the Tamper Proof Hardware Model / Antigoni Polychroniadou (Cornell Tech)
We put forth a new formulation of tamper-proof hardware in the Global Universal Composable (GUC) framework introduced by Canetti et al. in TCC 2007. All previous works in the tamper-proof model rely on the UC-formulation by Katz in Eurocrypt 2007 which fails to adequately capture tokens in a concurrent setting. We address these shortcomings by relying on our GUC framework where we make the following contributions:Static setting: When restricting to static corruptions, we construct the first secure two-party and multi-party computation protocols for general functionalities under minimal computational assumptions using stateless tokens. More precisely, we show how to realize arbitrary functionalities with GUC security in two rounds in the two-party case (which is round-optimal) and three rounds in the multi-party case assuming only One-Way Functions (OWFs).
Adaptive setting: Achieving constant-round adaptively secure protocols (where all parties can be corrupted) in the plain model is a notoriously hard problem. We extend the GUC model to incorporate adaptive corruptions and provide constant-round protocols assuming only OWFs using stateless tokens. In contrast, prior works in the CRS model require very strong assumptions, in particular, the existence of indistinguishability obfuscation. Our protocols are constructed based on a technique of lifting Yao’s garbled circuits to the adaptive setting using stateless tokens.
Joint works with Carmit Hazay and Muthu Venkitasubramaniam.
Privacy-Preserving Search of Similar Patients in Genomic Data / Gilad Asharov (Cornell Tech)
The growing availability of genomic data holds great promise for advancing medicine and research, but unlocking its full potential requires adequate methods for protecting the privacy of individuals whose genome data we use. One example of this tension is running Similar Patient Query on remote genomic data: In this setting a doctor that holds the genome of his/her patient may try to find other individuals with “close” genomic data (in edit distance), and use the data of these individuals to help diagnose and find effective treatment for that patient’s conditions. This is clearly a desirable mode of operation, however, the privacy exposure implications are considerable, so we would like to carry out the above “closeness” computation in a privacy preserving manner.
Secure-computation techniques offer a way out of this dilemma, but the high cost of computing edit distance privately poses a great challenge. Wang et al.~proposed recently [ACM CCS ’15] an efficient solution, for situations where the genome sequences are so close that edit distance between two genomes can be well approximated just by looking at the indexes in which they differ from the reference genome. However, this solution does not extend well to cases with high divergence among individual genomes, and different techniques are needed there.
In this work we put forward a new approach for highly efficient edit-distance approximation, that works well even in settings with much higher divergence. We present contributions both in the design the approximation method itself and in the protocol for computing it privately.
Our tests indicate that our approximation method works well even in regions of the genome where the distance between individuals is 5% or more with many insertions and deletions (compared to 99.5% similarly with mostly substitutions, as considered by Wang et al.).
As for speed, our protocol implementation takes just a few seconds to run on databases with thousands of records, each of length thousands of alleles, and it scales almost linearly with both the database size and the length of the sequences in it. As an example, in the datasets of the recent iDASH competition, it takes less than two seconds to find the nearest five records to the query, in a size 500 dataset of length 3500 sequences. This is 2-3 orders of magnitude faster than using straightforward approaches.
Joint work with Shai Halevi, Yehuda Lindell, and Tal Rabin.
- Scrypt is Maximally Memory-Hard / Leonid Reyzin (Boston University)
The function scrypt (Percival, 2009) is defined as the result of n steps, where each step consists of selecting one or two previously computed w-bit values (the selection depends on the values themselves) and hashing them to get a new w-bit value. Because it is conjectured that this function is memory-hard, it has been used for key derivation and proofs of work in cryptocurrencies, and has inspired subsequent designs. We show that indeed scrypt is maximally memory-hard in the parallel random oracle model. Specifically, we show that the product of memory and time used during the computation of scrypt must be Theta(n^2 w), even if the adversary is allowed to make an unlimited number of parallel random oracle queries at each step. Moreover, even if the amount of memory used fluctuates during the computation, we show that the sum of memory usage over time (a.k.a. “cumulative memory complexity” introduced by Alwen and Serbinenko at STOC 2015) is Theta(n^2 w), which implies high memory cost even for adversaries who can amortise the cost over many evaluations.Our result improves both quantitatively and qualitatively upon the recent work by Alwen et al. (Eurocrypt ’16) who proved a weaker lower bound of Omega(n^2 w / log^2 n) for a restricted class of adversaries. Our proof is the first showing optimal memory hardness in the random oracle model for any MHF.
Joint work with Joel Alwen, Binyi Chen, Krzysztof Pietrzak, and Stefano Tessaro.
- Cryptography with Updates / Prabhanjan Ananth (UCLA) – Canceled due to the winter storm
Starting with the work of Bellare, Goldreich and Goldwasser [CRYPTO’94], a rich line of work has studied the design of updatable cryptographic primitives. For example, in an updatable signature scheme, it is possible to efficiently transform a signature over a message into a signature over a related message without recomputing a fresh signature. In this work, we continue this line of research, and perform a systematic study of updatable cryptography. We take a unified approach towards adding updatability features to recently studied cryptographic objects such as attribute-based encryption, functional encryption, witness encryption, indistinguishability obfuscation, and many others that support non-interactive computation over inputs. We, in fact, go further and extend our approach to classical protocols such as zero-knowledge proofs and secure multiparty computation. To accomplish this goal, we introduce a new notion of updatable randomized encodings that extends the standard notion of randomized encodings to incorporate updatability features. We show that updatable randomized encodings can be used to generically transform cryptographic primitives to their updatable counterparts. We provide various definitions and constructions of updatable randomized encodings based on varying assumptions, ranging from one-way functions to compact functional encryption.
Joint work with Aloni Cohen and Abhishek Jain.