Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with one-way function:
TR98-033 | 12th June 1998
C.P. Schnorr

Security of Allmost ALL Discrete Log Bits

Let G be a finite cyclic group with generator \alpha and with
an encoding so that multiplication is computable in polynomial time. We
study the security of bits of the discrete log x when given \exp_{\alpha}(x),
assuming that the exponentiation function \exp_{\alpha}(x) = \alpha^x is one-way.
... more >>>

TR04-074 | 26th August 2004
Emanuele Viola

On Parallel Pseudorandom Generators

Revisions: 1

We study pseudorandom generator (PRG) constructions $G^f : {0,1}^l \to {0,1}^{l+s}$ from one-way functions $f : {0,1}^n \to {0,1}^m$. We consider PRG constructions of the form $G^f(x) = C(f(q_{1}) \ldots f(q_{poly(n)}))$
where $C$ is a polynomial-size constant depth circuit
and $C$ and the $q$'s are generated from $x$ arbitrarily.
more >>>

TR04-095 | 3rd November 2004
Daniele Micciancio

Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions

We investigate the average case complexity of a generalization of the compact knapsack problem to arbitrary rings: given $m$ (random) ring elements a_1,...,a_m in R and a (random) target value b in R, find coefficients x_1,...,x_m in S (where S is an appropriately chosen subset of R) such that a_1*x_1 ... more >>>

TR05-076 | 2nd July 2005
Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev

Time hierarchies for cryptographic function inversion with advice

We prove a time hierarchy theorem for inverting functions
computable in polynomial time with one bit of advice.
In particular, we prove that if there is a strongly
one-way function, then for any k and for any polynomial p,
there is a function f computable in linear time
with one ... more >>>

TR06-034 | 9th March 2006
Moni Naor, Guy Rothblum

The Complexity of Online Memory Checking

Suppose you want to store a large file on a remote and unreliable server. You would like to verify that your file has not been corrupted, so you store a small private (randomized)``fingerprint'' of the file on your own computer. This is the setting for the well-studied authentication problem, and ... more >>>

TR07-117 | 8th November 2007
Edward Hirsch, Dmitry Itsykson

An infinitely-often one-way function based on an average-case assumption

We assume the existence of a function f that is computable in polynomial time but its inverse function is not computable in randomized average-case polynomial time. The cryptographic setting is, however, different: even for a weak one-way function, every possible adversary should fail on a polynomial fraction of inputs. Nevertheless, ... more >>>

TR09-143 | 22nd December 2009
Noam Livne

On the Construction of One-Way Functions from Average Case Hardness

In this paper we study the possibility of proving the existence of
one-way functions based on average case hardness. It is well-known
that if there exists a polynomial-time sampler that outputs
instance-solution pairs such that the distribution on the instances
is hard on average, then one-way functions exist. We study ... more >>>

TR11-012 | 2nd February 2011
Andrej Bogdanov, Alon Rosen

Input locality and hardness amplification

We establish new hardness amplification results for one-way functions in which each input bit influences only a small number of output bits (a.k.a. input-local functions). Our transformations differ from previous ones in that they approximately preserve input locality and at the same time retain the input size of the original ... more >>>

TR12-005 | 13th January 2012
Periklis Papakonstantinou, Guang Yang

A remark on one-wayness versus pseudorandomness

Every pseudorandom generator is in particular a one-way function. If we only consider part of the output of the
pseudorandom generator is this still one-way? Here is a general setting formalizing this question. Suppose
$G:\{0,1\}^n\rightarrow \{0,1\}^{\ell(n)}$ is a pseudorandom generator with stretch $\ell(n)> n$. Let $M_R\in\{0,1\}^{m(n)\times \ell(n)}$ be a linear ... more >>>

TR12-175 | 13th December 2012
James Cook, Omid Etesami, Rachel Miller, Luca Trevisan

On the One-Way Function Candidate Proposed by Goldreich

Revisions: 1

A function $f$ mapping $n$-bit strings to $m$-bit strings can be constructed from a bipartite graph with $n$ vertices on the left and $m$ vertices on the right having right-degree $d$ together with a predicate $P:\{0,1\}^d\rightarrow\{0,1\}$. The vertices on the left correspond to the bits of the input to the ... more >>>

TR14-082 | 3rd June 2014
Yu Yu, Dawu Gu, Xiangxue Li

The Randomized Iterate Revisited - Almost Linear Seed Length PRGs from A Broader Class of One-way Functions

Revisions: 3

We revisit ``the randomized iterate'' technique that was originally used by Goldreich, Krawczyk, and Luby (SICOMP 1993) and refined by Haitner, Harnik and Reingold (CRYPTO 2006) in constructing pseudorandom generators (PRGs) from regular one-way functions (OWFs). We abstract out a technical lemma with connections to several recent work on cryptography ... more >>>

TR14-108 | 10th August 2014
Andrej Bogdanov, Christina Brzuska

On Basing Size-Verifiable One-Way Functions on NP-Hardness

Revisions: 1

We prove that if the hardness of inverting a size-verifiable one-way function can
be based on NP-hardness via a general (adaptive) reduction, then coAM is contained in NP. This
claim was made by Akavia, Goldreich, Goldwasser, and Moshkovitz (STOC 2006), but
was later retracted (STOC 2010).

more >>>

TR14-109 | 14th August 2014
Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan

Quantum lower bound for inverting a permutation with advice

Revisions: 1

Given a random permutation $f: [N] \to [N]$ as a black box and $y \in [N]$, we want to output $x = f^{-1}(y)$. Supplementary to our input, we are given classical advice in the form of a pre-computed data structure; this advice can depend on the permutation but \emph{not} on ... more >>>

TR15-045 | 1st April 2015
Benny Applebaum, Yuval Ishai, Eyal Kushilevitz

Minimizing Locality of One-Way Functions via Semi-Private Randomized Encodings

Revisions: 1

A one-way function is $d$-local if each of its outputs depends on at most $d$ input bits. In (Applebaum, Ishai, and Kushilevitz, FOCS 2004) it was shown that, under relatively mild assumptions, there exist $4$-local one-way functions (OWFs). This result is not far from optimal as it is not hard ... more >>>

ISSN 1433-8092 | Imprint