Monthly Archives: February 2016

March 11, 2016 (Friday) at Cornell-Tech, 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) Threshold-optimal DSA signatures and an Application to Bitcoin Wallet Security 12:00 – 2:00. Lunch (not provided) 2:00 – 2:50. Daniel Wichs (Northeastern) Multi-key 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 check-in 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 #CNS-1523467.

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 Campbell-Groves-Shepherd sketched potential  attacks against this problem; most notably, the latter authors claimed a
*polynomial-time quantum* algorithm. A key claim of Campbell et al. is  that one step of their algorithm—namely, decoding the log-unit 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 log-unit lattice is indeed efficiently decodable, for any cyclotomic  of prime-power 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 polynomial-time 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.

• Threshold-optimal DSA signatures and an Application to Bitcoin Wallet Security/ Steven Goldfeder (Princeton)
We present the first threshold-optimal 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
• Multi-key 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 multi-key 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 multi-key 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 multi-key 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 IND-CPA 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.