All reports by Author Alon Rosen:

__
TR24-088
| 29th April 2024
__

Tamer Mour, Alon Rosen, Ron Rothblum#### Locally Testable Tree Codes

__
TR23-098
| 5th July 2023
__

Andrej Bogdanov, Pravesh Kothari, Alon Rosen#### Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method

__
TR20-044
| 8th April 2020
__

Marshall Ball, Elette Boyle, Akshay Degwekar, Apoorvaa Deshpande, Alon Rosen, Vinod Vaikuntanathan, Prashant Vasudevan#### Cryptography from Information Loss

Revisions: 1

__
TR19-074
| 22nd May 2019
__

Arka Rai Choudhuri, Pavel HubĂˇ?ek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, Guy Rothblum#### Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir

__
TR17-113
| 1st July 2017
__

Andrej Bogdanov, Alon Rosen#### Pseudorandom Functions: Three Decades Later

__
TR17-039
| 28th February 2017
__

Marshall Ball, Alon Rosen, Manuel Sabin, Prashant Nalini Vasudevan#### Average-Case Fine-Grained Hardness

__
TR16-092
| 3rd June 2016
__

Gilad Asharov, Alon Rosen, Gil Segev#### Indistinguishability Obfuscation Does Not Reduce to Structured Languages

Revisions: 1

__
TR16-059
| 14th April 2016
__

Alon Rosen, Gil Segev, Ido Shahaf#### Can PPAD Hardness be Based on Standard Cryptographic Assumptions?

Revisions: 2

__
TR15-008
| 14th January 2015
__

Igor Carboni Oliveira, Siyao Guo, Tal Malkin, Alon Rosen#### The Power of Negations in Cryptography

Revisions: 1

__
TR15-001
| 2nd January 2015
__

Nir Bitansky, Omer Paneth, Alon Rosen#### On the Cryptographic Hardness of Finding a Nash Equilibrium

Revisions: 1

__
TR14-033
| 10th March 2014
__

Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, Alon Rosen#### Candidate Weak Pseudorandom Functions in $\mathrm{AC}0 \circ \mathrm{MOD}2$

Revisions: 1

__
TR11-126
| 17th September 2011
__

Benny Applebaum, Andrej Bogdanov, Alon Rosen#### A Dichotomy for Local Small-Bias Generators

__
TR11-012
| 2nd February 2011
__

Andrej Bogdanov, Alon Rosen#### Input locality and hardness amplification

__
TR06-147
| 27th November 2006
__

Chris Peikert, Alon Rosen#### Lattices that Admit Logarithmic Worst-Case to Average-Case Connection Factors

Revisions: 1

__
TR05-158
| 12th December 2005
__

Chris Peikert, Alon Rosen#### Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices

__
TR03-060
| 7th September 2003
__

Danny Harnik, Moni Naor, Omer Reingold, Alon Rosen#### Completeness in Two-Party Secure Computation - A Computational View

__
TR01-064
| 10th September 2001
__

Moni Naor, Omer Reingold, Alon Rosen#### Pseudo-Random Functions and Factoring

__
TR01-050
| 24th June 2001
__

Ran Canetti, Joe Kilian, Erez Petrank, Alon Rosen#### Black-Box Concurrent Zero-Knowledge Requires $\tilde\Omega(\log n)$ Rounds

Tamer Mour, Alon Rosen, Ron Rothblum

Tree codes, introduced in the seminal works of Schulman (STOC 93', IEEE Transactions on Information Theory 96') are codes designed for interactive communication. Encoding in a tree code is done in an online manner: the $i$-th codeword symbol depends only on the first $i$ message symbols. Codewords should have good ... more >>>

Andrej Bogdanov, Pravesh Kothari, Alon Rosen

The low-degree method postulates that no efficient algorithm outperforms low-degree polynomials in certain hypothesis-testing tasks. It has been used to understand computational indistinguishability in high-dimensional statistics.

We explore the use of the low-degree method in the context of cryptography. To this end, we apply it in the design and analysis ... more >>>

Marshall Ball, Elette Boyle, Akshay Degwekar, Apoorvaa Deshpande, Alon Rosen, Vinod Vaikuntanathan, Prashant Vasudevan

Reductions between problems, the mainstay of theoretical computer science, efficiently map an instance of one problem to an instance of another in such a way that solving the latter allows solving the former. The subject of this work is ``lossy'' reductions, where the reduction loses some information about the input ... more >>>

Arka Rai Choudhuri, Pavel HubĂˇ?ek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, Guy Rothblum

The Fiat-Shamir heuristic transforms a public-coin interactive proof into a non-interactive argument, by replacing the verifier with a cryptographic hash function that is applied to the protocolâ€™s transcript. Constructing hash functions for which this transformation is sound is a central and long-standing open question in cryptography.

We show that ... more >>>

Andrej Bogdanov, Alon Rosen

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 >>>

Marshall Ball, Alon Rosen, Manuel Sabin, Prashant Nalini Vasudevan

We present functions that can be computed in some fixed polynomial time but are hard on average for any algorithm that runs in slightly smaller time, assuming widely-conjectured worst-case hardness for problems from the study of fine-grained complexity. Unconditional constructions of such functions are known from before (Goldmann et al., ... more >>>

Gilad Asharov, Alon Rosen, Gil Segev

We prove that indistinguishability obfuscation (iO) and one-way functions do not naturally reduce to any language within $NP \cap coNP$. This is proved within the framework introduced by Asharov and Segev (FOCS '15) that captures the vast majority of techniques that have been used so far in iO-based constructions.

Our ... more >>>

Alon Rosen, Gil Segev, Ido Shahaf

We consider the question of whether average-case PPAD hardness can be based on standard cryptographic assumptions, such as the existence of one-way functions or public-key encryption. This question is particularly well-motivated in light of new devastating attacks on obfuscation candidates and their underlying building blocks, which are currently the only ... more >>>

Igor Carboni Oliveira, Siyao Guo, Tal Malkin, Alon Rosen

The study of monotonicity and negation complexity for Boolean functions has been prevalent in complexity theory as well as in computational learning theory, but little attention has been given to it in the cryptographic context. Recently, Goldreich and Izsak (2012) have initiated a study of whether cryptographic primitives can be ... more >>>

Nir Bitansky, Omer Paneth, Alon Rosen

We prove that finding a Nash equilibrium of a game is hard, assuming the existence of indistinguishability obfuscation and injective one-way functions with sub-exponential hardness. We do so by showing how these cryptographic primitives give rise to a hard computational problem that lies in the complexity class PPAD, for which ... more >>>

Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, Alon Rosen

Pseudorandom functions (PRFs) play a fundamental role in symmetric-key cryptography. However, they are inherently complex and cannot be implemented in the class $\mathrm{AC}^0( \mathrm{MOD}_2)$. Weak pseudorandom functions (weak PRFs) do not suffer from this complexity limitation, yet they suffice for many cryptographic applications. We study the minimal complexity requirements for ... more >>>

Benny Applebaum, Andrej Bogdanov, Alon Rosen

We consider pseudorandom generators in which each output bit depends on a constant number of input bits. Such generators have appealingly simple structure: they can be described by a sparse input-output dependency graph and a small predicate that is applied at each output. Following the works of Cryan and Miltersen ... more >>>

Andrej Bogdanov, Alon Rosen

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 >>>

Chris Peikert, Alon Rosen

We demonstrate an \emph{average-case} problem which is as hard as

finding $\gamma(n)$-approximate shortest vectors in certain

$n$-dimensional lattices in the \emph{worst case}, where $\gamma(n)

= O(\sqrt{\log n})$. The previously best known factor for any class

of lattices was $\gamma(n) = \tilde{O}(n)$.

To obtain our ... more >>>

Chris Peikert, Alon Rosen

The generalized knapsack function is defined as $f_{\a}(\x) = \sum_i

a_i \cdot x_i$, where $\a = (a_1, \ldots, a_m)$ consists of $m$

elements from some ring $R$, and $\x = (x_1, \ldots, x_m)$ consists

of $m$ coefficients from a specified subset $S \subseteq R$.

Micciancio ...
more >>>

Danny Harnik, Moni Naor, Omer Reingold, Alon Rosen

A Secure Function Evaluation (SFE) of a two-variable function f(.,.) is a protocol that allows two parties with inputs x and y to evaluate

f(x,y) in a manner where neither party learns ``more than is necessary". A rich body of work deals with the study of completeness for secure ...
more >>>

Moni Naor, Omer Reingold, Alon Rosen

Factoring integers is the most established problem on which

cryptographic primitives are based. This work presents an efficient

construction of {\em pseudorandom functions} whose security is based

on the intractability of factoring. In particular, we are able to

construct efficient length-preserving pseudorandom functions where

each evaluation requires only a ...
more >>>

Ran Canetti, Joe Kilian, Erez Petrank, Alon Rosen

We show that any concurrent zero-knowledge protocol for a non-trivial

language (i.e., for a language outside $\BPP$), whose security is proven

via black-box simulation, must use at least $\tilde\Omega(\log n)$

rounds of interaction. This result achieves a substantial improvement

over previous lower bounds, and is the first bound to rule ...
more >>>