CryptoDay @ CUNY, Friday Oct 14, 2016
Note: changed location
Oct 14, 2016 (Friday) at City College (CUNY), 5.1 Visualization Room, 5th Floor of the CUNY ASRC Building, 85 St Nicholas Terrace, New York, NY.
Program
9:30 – 10:00.  Introduction/Coffee 
10:00 – 10:50.  Omer Paneth (Boston University) Delegating RAM Computations 
11:00 – 11:50.  Siyao Guo (NYU) Threshold Secret Sharing Requires a Linear Share Alphabet 
12:00 – 2:00.  Lunch (not provided) 
2:00 – 2:50.  Akshay Degwekar (MIT) Structure vs Hardness through the Obfuscation Lens 
3:00 – 3:50.  Mark Zhandry (Princeton) Obfuscation and Weak Multilinear Maps 
Venue
Address: 5.1 Visualization Room, 5th Floor of the CUNY ASRC Building, 85 St Nicholas Terrace, New York, NY.
[Visitor Information] [Google Maps]
Organizers
Fabrice Benhamouda (IBM Research)
Tal Rabin (IBM Research)
with the help and support of Rosario Gennaro (CUNY).
Support
Some travel support for NYC Crypto Day is provided by DIMACS/Simons Collaboration in Cryptography through NSF grant #CNS1523467.
Abstracts

Delegating RAM Computations / Omer Paneth (Boston University)
In the setting of cloud computing a user wishes to delegate its data, as well as computations over this data, to a cloud provider. Each computation may read and modify the data, and these modifications should persist between computations. Minding the computational resources of the cloud, delegated computations are modeled as RAM programs. In particular, the delegated computations’ running time may be sublinear, or even exponentially smaller than the memory size. We construct a twomessage protocol for delegating RAM computations to an untrusted cloud. In our protocol, the user saves a short digest of the delegated data. For every delegated computation, the cloud returns, in addition to the computation’s output, the digest of the modified data, and a proof that the output and digest were computed correctly. When delegating a Ttime RAM computation P with security parameter n, the cloud runs in time Poly(T,n) and the user in time Poly(P, log(T), n). Our protocol is secure assuming superpolynomial hardness of the Learning with Error (LWE) assumption. Security holds even when the delegated computations are chosen adaptively as a function of the data and output of previous computations.
I will also present an application of RAM delegation to obtaining the first threemessage zeroknowledge argument system with soundness against uniform polynomialtime cheating provers. More generally, beyond uniform provers, our protocol provides a natural and meaningful security guarantee against realworld adversaries, which we formalize following Rogaway’s “humanignorance” approach (VIETCRYPT 2006): in a nutshell, we give an explicit uniform reduction from any adversary breaking the soundness of our protocol to finding collisions in some keyless collisionresistant hash functions.
Based on joint works with Nir Bitansky, Zvika Brakerski, Yael Kalai and Vinod Vaikuntanathan.
 Threshold Secret Sharing Requires a Linear Share Alphabet / Siyao Guo (NYU)
We prove that for every n and 1 < t < n any toutofn threshold secret sharing scheme for onebit secrets requires share size log(t + 1). Our bound is tight when t = n − 1 and n is a prime power. In 1990 Kilian and Nisan proved the incomparable bound log(n − t + 2). Taken together, the two bounds imply that the share size of Shamir’s secret sharing scheme (Comm. ACM ’79) is optimal up to an additive constant even for onebit secrets for the whole range of parameters 1 < t < n.More generally, we show that for all 1 < s < r < n, any ramp secret sharing scheme with secrecy threshold s and reconstruction threshold r requires share size log((r + 1)/(r − s)).As part of our analysis we formulate a simple gametheoretic relaxation of secret sharing for arbitrary access structures. We prove the optimality of our analysis for threshold secret sharing with respect to this method and point out a general limitation.Joint work with Andrej Bogdanov and Ilan Komargodski (in TCC16B).

Structure vs Hardness through the Obfuscation Lens / Akshay Degwekar (MIT)
Cryptography relies on the computational hardness of structured problems. While secretkey cryptography does not seem to require much structure, as we advance up the ranks into publickey cryptography and beyond, we typically rely on problems with considerable algebraic structure such as factoring, discrete logarithms, and shortest (or closest) vectors in lattices. This structure, on the one hand, enables advanced applications such as publickey and homomorphic encryption , but on the other, also puts their hardness in question. In particular, this structure is exactly what puts them in low (and so called structured) complexity classes such as NP∩coNP and Statistical Zero Knowledge (SZK).
For certain primitives, which indeed appear structured, like oneway permutations and homomorphic encryption, such complexitytheoretic structure is known to be inherent. In contrast, it is known that oneway functions, which indeed appear unstructured, do {\em not} imply hard problems NP∩coNP under blackbox reductions. Yet for many, even basic, primitives, including publickey encryption, oblivious transfer, and functional encryption, there is a gap in our understanding.
We prove that hard problems in NP∩coNP or SZK do not follow from any of these primitives under blackbox reductions. More generally, we show that even the power of indistinguishability obfuscation does not yield blackbox constructions of such hard structured problems. Then, leveraging the the fact that indistinguishability obfuscation can be used to construct all spoken primitives in a blackbox manner, we deduce the same for these primitives.
Joint work with Nir Bitansky and Vinod Vaikuntanathan.
 Obfuscation and Weak Multilinear Maps / Mark Zhandry (Princeton)
Given the significance of obfuscation to cryptography, it is crucial to understand its security. Obfuscation is currently constructed using an object called multilinear maps. Unfortunately, multilinear maps have been subject to many attacks, leaving almost all applications of multilinear maps completely broken. One of the main holdouts is program obfuscation, though in light of these attacks all previous arguments for the security of obfuscation are unconvincing. Is obfuscation not yet broken simply because it is complicated and hard to analyze? Or is there some fundamental reason why known attacks cannot be applied to obfuscation?In this talk, I will discuss two recent works that show, in the case of obfuscation using GGH13 multilinear maps, the answer is somewhere in the middle. First, I will show a polynomial attack that applies to several existing obfuscation candidates, even those proven secure in the “generic multilinear map model”. Then, I will demonstrate a simple fix that blocks our attacks. Moreover, I will prove the new scheme secure in a new abstract model for multilinear maps which captures all known attacks. Thus, we obtain the first obfuscation candidate with a convincing argument for security in light of recent attacks.Joint work with Sanjam Garg, Eric Miles, Pratyay Mukherjee, Amit Sahai, and Akshayaram Srinivasan.