EE Seminar: Local Arithmetic Pseudorandom Generators
Speaker: Lior Zichron,
M.Sc. student under the supervision of Prof. Benny Applebaum
Wednesday, June 7th, 2017 at 15:30
Room 011, Kitot Bldg., Faculty of Engineering
Local Arithmetic Pseudorandom Generators
Abstract
Pseudorandom generators (PRGs) use a short k-bit random seed to generate a longer m-bit pseudorandom string. Locally-computable PRGs are PRGs which enjoy a high level of efficiency: Each of their outputs can be computed based on constant number of inputs. In the last decade, such PRGs were extensively studied. Candidate constructions were suggested, in addition to several interesting applications.
In this work, we initiate the study of local PRGs over large field. That is, we view the seed as a sequence of k field elements and the output as a sequence of m field elements. We present two constructions of locally-sample arithmetic distributions based on Noisy Linear Sparse Mapping and based on Expander Graphs. Both constructions were studied in the binary setting by Alekhnovich (FOCS 2003) and Goldreich (ECCC 2000), respectively. For each of these candidates we present new attacks, and prove lower-bounds against restricted types of adversaries. Our results suggest that, in several aspects, the arithmetic setting seems to be easier to analyze and even more secure than the binary setting. In particular, it seems that security in the arithmetic setting requires modest combinatorial properties than the binary setting. Finally, we show that our constructions imply the first protocol for securely computing any arithmetic function with constant computational overhead.
