Speaker: Hai Brenner The Interdisciplinary Center, Herzliya, Israel
Time: 2014-09-29 14:30-2014-09-29 15:30
Venue: FIT 1-222

Abstract:

I will present the construction of SPRING, a lattice based PRF. Banerjee, Peikert and Rosen (ePrint Report 2011/401) put forward a new, rigorously provable approach for constructing pseudorandom objects (namely, pseudorandom generators and functions) based on ``rounded products'' in certain polynomial rings. Their approach has the potential to help bridge the gap between theoretically sound and practically efficient constructions of symmetric cryptographic objects. In their paper, BPR present two alternative constructions: one is based on a construction by Naor and Reingold, using pseudorandom synthesizers, while the other is more “direct” and is based on the subset product of polynomials.
This talk will consist of two parts: in the first part I will present both BPR constructions, and the main theoretical ideas underlying these constructions. In the second part, I will describe efficient implementation of their “direct” functions. A main component is a computation over the ring $Z_q$ for $q=257$ (which admits fast implementation using the Fast Fourier Transform, and some other tricks which I will describe). Such computation outputs biased bits, and two methods are suggested to reduce the bias. One uses “Chinese remainder” with another $Z_2$ component (which is already implemented in modern computer chips). The second uses dual-BCH code (which results in very efficient hardware implementation).
Based on joint works with Abhishek Banerjee, Lubos Gaspar, Ga?tan Leurent, Chris Peikert, Alon Rosen and Fran?ois-Xavier Standaert.

Short Bio:

I have a B.A. in philosophy and math from the Ben-Gurion University of the Negev in Israel, and also an MSc in math and computer science. My field of research was Differential-Privacy.
Currently, I work as a research assistant and a programmer in the FACT center in the Interdisciplinary Center, Herzliya, Israel. My main tasks there are some research and implementing efficient software codes for the SPRING PRF and for commitment scheme protocols.