Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PSEUDORANDOM FUNCTIONS:
Reports tagged with pseudorandom functions:
TR01-057 | 15th August 2001
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, Ke Yang

#### On the (Im)possibility of Obfuscating Programs

Informally, an <i>obfuscator</i> <b>O</b> is an (efficient, probabilistic)
"compiler" that takes as input a program (or circuit) <b>P</b> and
produces a new program <b>O(P)</b> that has the same functionality as <b>P</b>
yet is "unintelligible" in some sense. Obfuscators, if they exist,
would have a wide variety of cryptographic ... more >>>

TR12-182 | 24th December 2012
Itay Berman, Iftach Haitner, Ilan Komargodski, Moni Naor

#### Hardness Preserving Reductions via Cuckoo Hashing

Revisions: 2

A common method for increasing the usability and uplifting the security of pseudorandom function families (PRFs) is to hash" the inputs into a smaller domain before applying the PRF. This approach, known as Levin's trick", is used to achieve PRF domain extension" (using a short, e.g., fixed, input length PRF ... more >>>

TR15-009 | 16th January 2015
Aloni Cohen, Shafi Goldwasser, Vinod Vaikuntanathan

#### Aggregate Pseudorandom Functions and Connections to Learning

Revisions: 1

In the first part of this work, we introduce a new type of pseudo-random function for which aggregate queries'' over exponential-sized sets can be efficiently answered. An example of an aggregate query may be the product of all function values belonging to an exponential-sized interval, or the sum of all ... more >>>

TR16-082 | 22nd May 2016
Benny Applebaum, Pavel Raykov

#### Fast Pseudorandom Functions Based on Expander Graphs

We present direct constructions of pseudorandom function (PRF) families based on Goldreich's one-way function. Roughly speaking, we assume that non-trivial local mappings $f:\{0,1\}^n\rightarrow \{0,1\}^m$ whose input-output dependencies graph form an expander are hard to invert. We show that this one-wayness assumption yields PRFs with relatively low complexity. This includes weak ... more >>>

TR16-197 | 7th December 2016
Igor Carboni Oliveira, Rahul Santhanam

#### Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness

We prove several results giving new and stronger connections between learning theory, circuit complexity and pseudorandomness. Let C be any typical class of Boolean circuits, and C[s(n)] denote n-variable C-circuits of size at most s(n). We show:

Learning Speedups: If C[$n^{O(1)}$] admits a randomized weak learning algorithm under the uniform ... more >>>

TR17-113 | 1st July 2017
Andrej Bogdanov, Alon Rosen

#### Pseudorandom Functions: Three Decades Later

In 1984, Goldreich, Goldwasser and Micali formalized the concept of pseudorandom functions and proposed a construction based on any length-doubling pseudorandom generator. Since then, pseudorandom functions have turned out to be an extremely influential abstraction, with applications ranging from message authentication to barriers in proving computational complexity lower bounds.

In ... more >>>

TR21-009 | 1st February 2021
Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich

#### One-way Functions and Partial MCSP

One-way functions (OWFs) are central objects of study in cryptography and computational complexity theory. In a seminal work, Liu and Pass (FOCS 2020) proved that the average-case hardness of computing time-bounded Kolmogorov complexity is equivalent to the existence of OWFs. It remained an open problem to establish such an equivalence ... more >>>

TR21-125 | 23rd August 2021
Zhiyuan Fan, Jiatu Li, Tianqi Yang

#### The Exact Complexity of Pseudorandom Functions and Tight Barriers to Lower Bound Proofs

Revisions: 1

How much computational resource do we need for cryptography? This is an important question of both theoretical and practical interests. In this paper, we study the problem on pseudorandom functions (PRFs) in the context of circuit complexity. Perhaps surprisingly, we prove extremely tight upper and lower bounds in various circuit ... more >>>

ISSN 1433-8092 | Imprint