All reports by Author Moni Naor:

__
TR21-096
| 8th July 2021
__

Boaz Menuhin, Moni Naor#### Keep That Card in Mind: Card Guessing with Limited Memory

__
TR19-113
| 5th September 2019
__

Tomer Grossman, Ilan Komargodski, Moni Naor#### Instance Complexity and Unlabeled Certificates in the Decision Tree Model

__
TR18-213
| 28th December 2018
__

Moni Naor, Merav Parter, Eylon Yogev#### The Power of Distributed Verifiers in Interactive Proofs

Revisions: 1

__
TR17-015
| 4th February 2017
__

Ilan Komargodski, Moni Naor, Eylon Yogev#### White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing

Revisions: 2

__
TR16-199
| 15th December 2016
__

Pavel Hubacek, Moni Naor, Eylon Yogev#### The Journey from NP to TFNP Hardness

__
TR16-049
| 28th March 2016
__

Cynthia Dwork, Moni Naor, Guy Rothblum#### Spooky Interaction and its Discontents: Compilers for Succinct Two-Message Argument Systems

__
TR16-023
| 23rd February 2016
__

Ilan Komargodski, Moni Naor, Eylon Yogev#### How to Share a Secret, Infinitely

Revisions: 4

__
TR15-146
| 7th September 2015
__

Elette Boyle, Moni Naor#### Is There an Oblivious RAM Lower Bound?

Revisions: 1

__
TR13-014
| 11th January 2013
__

Zvika Brakerski, Moni Naor#### Fast Algorithms for Interactive Coding

__
TR12-182
| 24th December 2012
__

Itay Berman, Iftach Haitner, Ilan Komargodski, Moni Naor#### Hardness Preserving Reductions via Cuckoo Hashing

Revisions: 2

__
TR06-034
| 9th March 2006
__

Moni Naor, Guy Rothblum#### The Complexity of Online Memory Checking

__
TR06-022
| 17th February 2006
__

Danny Harnik, Moni Naor#### On the Compressibility of NP Instances and Cryptographic Applications

Revisions: 1

__
TR06-002
| 4th January 2006
__

Eyal Kaplan, Moni Naor, Omer Reingold#### Derandomized Constructions of k-Wise (Almost) Independent Permutations

__
TR03-060
| 7th September 2003
__

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

__
TR02-043
| 11th July 2002
__

Dalit Naor, Moni Naor, Jeff Lotspiech#### Revocation and Tracing Schemes for Stateless Receivers

__
TR02-001
| 8th January 2002
__

Cynthia Dwork, Moni Naor#### Zaps and Their Applications

__
TR01-064
| 10th September 2001
__

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

__
TR01-062
| 9th September 2001
__

Moni Naor, Kobbi Nissim#### Communication Complexity and Secure Function Evaluation

__
TR97-005
| 17th February 1997
__

Moni Naor, Omer Reingold#### On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited

__
TR95-045
| 4th September 1995
__

Moni Naor, Omer Reingold#### Synthesizers and Their Application to the Parallel Construction of Pseudo-random Functions

Boaz Menuhin, Moni Naor

A card guessing game is played between two players, Guesser and Dealer. At the beginning of the game, the Dealer holds a deck of $n$ cards (labeled $1, ..., n$). For $n$ turns, the Dealer draws a card from the deck, the Guesser guesses which card was drawn, and then ... more >>>

Tomer Grossman, Ilan Komargodski, Moni Naor

Instance complexity is a measure of goodness of an algorithm in which the performance of one algorithm is compared to others per input. This is in sharp contrast to worst-case and average-case complexity measures, where the performance is compared either on the worst input or on an average one, ... more >>>

Moni Naor, Merav Parter, Eylon Yogev

We explore the power of interactive proofs with a distributed verifier. In this setting, the verifier consists of $n$ nodes and a graph $G$ that defines their communication pattern. The prover is a single entity that communicates with all nodes by short messages. The goal is to verify that the ... more >>>

Ilan Komargodski, Moni Naor, Eylon Yogev

Ramsey theory assures us that in any graph there is a clique or independent set of a certain size, roughly logarithmic in the graph size. But how difficult is it to find the clique or independent set? If the graph is given explicitly, then it is possible to do so ... more >>>

Pavel Hubacek, Moni Naor, Eylon Yogev

The class TFNP is the search analog of NP with the additional guarantee that any instance has a solution. TFNP has attracted extensive attention due to its natural syntactic subclasses that capture the computational complexity of important search problems from algorithmic game theory, combinatorial optimization and computational topology. Thus, one ... more >>>

Cynthia Dwork, Moni Naor, Guy Rothblum

We are interested in constructing short two-message arguments for various languages, where the complexity of the verifier is small (e.g. linear in the input size, or even sublinear if the input is coded appropriately).

In 2000 Aiello et al. suggested the tantalizing possibility of obtaining such arguments for all of ... more >>>

Ilan Komargodski, Moni Naor, Eylon Yogev

Secret sharing schemes allow a dealer to distribute a secret piece of information among several parties so that any qualified subset of parties can reconstruct the secret, while every unqualified subset of parties learns nothing about the secret. The collection of qualified subsets is called an access structure. The best ... more >>>

Elette Boyle, Moni Naor

An Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (JACM 1996), is a (probabilistic) RAM that hides its access pattern, i.e. for every input the observed locations accessed are similarly distributed. Great progress has been made in recent years in minimizing the overhead of ORAM constructions, with the goal of ... more >>>

Zvika Brakerski, Moni Naor

Consider two parties who wish to communicate in order to execute some interactive protocol $\pi$. However, the communication channel between them is noisy: An adversary sees everything that is transmitted over the channel and can change a constant fraction of the bits as he pleases, thus interrupting the execution of ... more >>>

Itay Berman, Iftach Haitner, Ilan Komargodski, Moni Naor

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

Moni Naor, Guy Rothblum

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

Danny Harnik, Moni Naor

We initiate the study of the compressibility of NP problems. We

consider NP problems that have long instances but relatively

short witnesses. The question is, can one efficiently compress an

instance and store a shorter representation that maintains the

information of whether the original input is in the language or

more >>>

Eyal Kaplan, Moni Naor, Omer Reingold

Constructions of k-wise almost independent permutations have been receiving a growing amount of attention in recent years. However, unlike the case of k-wise independent functions, the size of previously constructed families of such permutations is far from optimal.

In this paper we describe a method for reducing the size of ... 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 >>>

Dalit Naor, Moni Naor, Jeff Lotspiech

We deal with the problem of a center sending a secret message to

a group of users such that some subset of the users is considered

revoked and should not be able to obtain the content of the

message. We concentrate on the stateless receiver case, where

the users do ...
more >>>

Cynthia Dwork, Moni Naor

A zap is a two-round, witness-indistinguishable protocol in which

the first round, consisting of a message from the verifier to the

prover, can be fixed ``once-and-for-all" and applied to any instance,

and where the verifier does not use any private coins.

We present a zap for every language in NP, ...
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 >>>

Moni Naor, Kobbi Nissim

A secure function evaluation protocol allows two parties to jointly compute a function $f(x,y)$ of their inputs in a manner not leaking more information than necessary. A major result in this field is: ``any function $f$ that can be computed using polynomial resources can be computed securely using polynomial resources'' ... more >>>

Moni Naor, Omer Reingold

Luby and Rackoff showed a method for constructing a pseudo-random

permutation from a pseudo-random function. The method is based on

composing four (or three for weakened security) so called Feistel

permutations each of which requires the evaluation of a pseudo-random

function. We reduce somewhat the complexity ...
more >>>

Moni Naor, Omer Reingold

A pseudo-random function is a fundamental cryptographic primitive

that is essential for encryption, identification and authentication.

We present a new cryptographic primitive called pseudo-random

synthesizer and show how to use it in order to get a

parallel construction of a pseudo-random function.

We show an $NC^1$ implementation of synthesizers ...
more >>>