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 #CNS-1523467.

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 sub-linear, or even exponentially smaller than the memory size. We construct a two-message 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 T-time 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 super-polynomial 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 three-message zero-knowledge argument system with soundness against uniform polynomial-time cheating provers. More generally, beyond uniform provers, our protocol provides a natural and meaningful security guarantee against real-world adversaries, which we formalize following Rogaway’s “human-ignorance” 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 key-less collision-resistant 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 t-out-of-n threshold secret sharing scheme for one-bit 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 one-bit 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 game-theoretic 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 secret-key cryptography does not seem to require much structure, as we advance up the ranks into public-key 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 public-key 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 one-way permutations and homomorphic encryption, such complexity-theoretic structure is known to be inherent. In contrast, it is known that one-way functions, which indeed appear unstructured, do {\em not} imply hard problems NP∩coNP under black-box reductions. Yet for many, even basic, primitives, including public-key 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 black-box reductions. More generally, we show that even the power of indistinguishability obfuscation does not yield black-box constructions of such hard structured problems. Then, leveraging the the fact that indistinguishability obfuscation can be used to construct all spoken primitives in a black-box 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.