Cryptoday March 11, 2016 @Cornell Tech
March 11, 2016 (Friday) at CornellTech, 111 8th Avenue #302 (Room “Touchdown”)
Program
9:30 – 10:00.  Introduction/Coffee 
10:00 – 10:50. 
Oded Regev (NYU)
Recovering Short Generators of Principal Ideals in Cyclotomic Rings

11:00 – 11:50.  Steven Goldfeder (Princeton) Thresholdoptimal DSA signatures and an Application to Bitcoin Wallet Security 
12:00 – 2:00.  Lunch (not provided) 
2:00 – 2:50.  Daniel Wichs (Northeastern) Multikey FHE, Spooky Encryption, and 2 Round MPC 
3:00 – 3:50.  Venkata Koppula (University of Texas, Austin) Circular Security Counterexamples for Arbitrary Length Cycles from LWE 
Registration Very Important
Registration for attending this event is free but mandatory. You can register by going to the registration form. Please register by Wed. March 9, 2016 11:59 PM. Only registered participants will be allowed on Cornell NYC Tech premises
Venue
Cornell Tech #302 (Room “Touchdown”)
111 8th Avenue
New York, NY 10011
Room “Touchdown”.
Please checkin at the lobby first where you will get a sticker. Then go to the third floor and follow the corridor for Cornell Tech, and then someone will greet you in the lobby and tell you how to get to “Touchdown.”
Organizers
Tal Rabin (IBM)
with the help and support of Rafael Pass (Cornell).
Some travel support for NYC Crypto Day is provided by DIMACS/Simons Collaboration in Cryptography through NSF grant #CNS1523467.
Abstracts

Recovering Short Generators of Principal Ideals in Cyclotomic Rings/ Oded Regev (NYU)
A handful of recent cryptographic proposals rely on the conjectured hardness of the following problem in the ring of integers of a cyclotomic number field: given a basis of a principal ideal that is guaranteed to have a “rather short” generator, find such a generator. Recently, Bernstein and CampbellGrovesShepherd sketched potential attacks against this problem; most notably, the latter authors claimed a
*polynomialtime quantum* algorithm. A key claim of Campbell et al. is that one step of their algorithm—namely, decoding the logunit lattice of the ring to recover a short generator from an arbitrary one—is classically efficient (whereas the standard approach on general lattices takes exponential time). However, very few convincing details were provided to substantiate this claim.In this work, we clarify the situation by giving a rigorous proof that the logunit lattice is indeed efficiently decodable, for any cyclotomic of primepower index. Combining this with the quantum algorithm from a recent work of Biasse and Song confirms the main claim of Campbell et al.
I will try not to assume any prior familiarity with algebraic number theory. Time permitting, I will mention some other corollaries of our techniques, such as a quantum polynomialtime algorithm for the $2^{O~(\sqrt{n})}$approximate Shortest Vector Problem on principal ideal lattices.
Joint work with Ronald Cramer, Leo Ducas, and Chris Peikert.
 Thresholdoptimal DSA signatures and an Application to Bitcoin Wallet Security/ Steven Goldfeder (Princeton)
We present the first thresholdoptimal signature scheme for DSA. I will present the details of our construction and our proof as well as compare it with previous threshold DSA schemes. We also present a compelling application to use our scheme: securing Bitcoin wallets. Bitcoin thefts are on the rise, and threshold DSA is necessary to secure Bitcoin wallets. Our scheme is the first general threshold DSA scheme that does not require an honest majority and is useful for securing Bitcoin wallets.This is joint work with Rosario Gennaro and Arvind Narayanan
 Multikey FHE, Spooky Encryption, and 2 Round MPC / Daniel Wichs (Norhteastern)
Consider a setting where several inputs x_i are encrypted under independently generated public keys pk_i resulting in ciphertexts c_i = Enc_{pk_i}(x_i). Standard FHE schemes allow arbitrary computation on each input separately, but in this work we are interested in performing a joint computation f(x_1,…,x_n) over all inputs. We consider two related scenarios:– In a multikey FHE, the goal is to perform a homomorphic computation that results in a ciphertext c* encrypting f(x_1,…,x_n). Furthermore, it should be possible to decrypt c* efficiently given all the secret keys. We show how to achieve this under LWE, significantly simplifying a construction of Clear and McGoldrick (CRYPTO ’15)
– In a “spooky” FHE, the goal is to perform a homomorphic computation that results in ciphertexts c’_i which are then individually decrypted under the respective secret keys sk_i yielding y_i = Dec_{sk_i}(c_i). By the security of the encryption, we know that each y_i individually cannot “signal” any information about x_j for j not equal to i. On the other hand, with standard FHE, we can achieve all “local” relationships where each y_i can depend arbitrarily on x_i. However, we show that it is also possible to achieve more complex relationships which are neither local nor signalling, and which we call “spooky”. In particular, for any function f, we can ensure that the y_i values are an additive secret sharing of f(x_1,…,x_n). We construct spooky FHE from LWE by adapting our construction of multikey FHE.
Both of the above results assume that the keys are created using some shared public randomness. We show how to get schemes that don’t rely on such common public randomness using indistinguishability obfuscation.
We give several applications of multikey and spooky FHE. Most importantly, we show how to realize MPC for arbitrary functions with the optimal 2 rounds of interaction.
Based on joint works with Pratyay Mukherjee, Yevgeniy Dodis, Shai Halevi and Ron Rothblum
 Circular Security Counterexamples for Arbitrary Length Cycles from LWE/ Venkata Koppula (University of Texas, Austin) We describe a public key encryption that is INDCPA secure under the Learning with Errors (LWE) assumption, but that is not circular secure for arbitrary length cycles. Previous separation results for cycle length greater than 2 require the use of indistinguishability obfuscation, which is not currently realizable under standard assumptions.