NDLI: Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions

Please wait, while we are loading the content...

Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Applebaum, Benny
Copyright Year	2013
Abstract	We continue the study of locally computable pseudorandom generators (PRGs) $G: \{0,1\}^n \rightarrow \{0,1\}^m$ such that each of their outputs depends on a small number $d$ of input bits. While it is known that such generators are likely to exist for the case of small sublinear stretch $m=n+n^{1-\delta}$, it is less clear whether achieving larger stretch such as $m=n+\Omega(n)$ or even $m=n^{1+\delta}$ is possible. The existence of such PRGs, which was posed as an open question in previous works, has recently gained an additional motivation due to several interesting applications. We make progress towards resolving this question by obtaining several local constructions based on the one-wayness of random local functions---a variant of an assumption made by Goldreich [Candidate one-way functions based on exporter graphs, 7 (ECCC 2000), TRCO-090]. Specifically, we construct collections of PRGs with the following parameters: (1) linear stretch $m=n+\Omega(n)$ and constant locality $d=O(1)$; (2) polynomial stretch $m=n^{1+\delta}$ and any (arbitrarily slowly growing) super-constant locality $d=\omega(1)$, e.g., $\log^{\star} n$; (3) polynomial stretch $m=n^{1+\delta}$, constant locality $d=O(1)$, and inverse polynomial distinguishing advantage (as opposed to the standard case of $n^{-\omega(1)}$). Our constructions match the parameters achieved by previous ad hoc candidates and are the first to do this under a one-wayness assumption. At the core of our results lies a new search-to-decision reduction for random local functions. This reduction also shows that some of the previous PRG candidates can be based on one-wayness assumptions. Altogether, our results fortify the existence of local PRGs of long stretch. As an additional contribution, we show that our constructions give rise to strong inapproximability results for the densest-subgraph problem in $d$-uniform hypergraphs for constant $d$. This allows us to improve the previous bounds of Feige [Relations between average case complexity and approximation complexity, in Proceedings of STOC 2002, pp. 534--543] and Khot [Ruling out PTAS for graph min-bisection-densest subgraph and bipartate clique, in Proceedings of FOCS 2004, pp. 136--145] from constant inapproximability factor to $n^{\varepsilon}$-inapproximability, at the expense of relying on stronger assumptions.
Starting Page	2008
Ending Page	2037
Page Count	30
File Format	PDF
ISSN	00975397
DOI	10.1137/120884857
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	5
Volume Number	42
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2013-10-24
Access Restriction	Subscribed
Subject Keyword	constant-depth circuits Data encryption NC$^0$ cryptography pseudorandomness densest-subgraph Cryptography
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Pseudorandom generators with long stretch and low locality from random local one-way functions

Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions (2013)

Cryptography in $NC^0$

Cryptographic Hardness of Random Local Functions : Survey

Pseudorandom Functions and Factoring

Efficiency Improvements in Constructing Pseudorandom Generators from One-Way Functions

On constructing parallel pseudorandom generators from one-way functions

On Pseudorandom Generators with Linear Stretch in NC0

On Constructing Parallel Pseudorandom Generators From One-Way Functions (2005)

Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions

Similar Documents

Pseudorandom generators with long stretch and low locality from random local one-way functions

Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions (2013)

Cryptography in $NC^0$

Cryptographic Hardness of Random Local Functions : Survey

Pseudorandom Functions and Factoring

Efficiency Improvements in Constructing Pseudorandom Generators from One-Way Functions

On constructing parallel pseudorandom generators from one-way functions

On Pseudorandom Generators with Linear Stretch in NC0

On Constructing Parallel Pseudorandom Generators From One-Way Functions (2005)

Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions