Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR19-113 | 5th September 2019
Tomer Grossman, Ilan Komargodski, Moni Naor

Instance Complexity and Unlabeled Certificates in the Decision Tree Model

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

TR18-213 | 28th December 2018
Moni Naor, Merav Parter, Eylon Yogev

The Power of Distributed Verifiers in Interactive Proofs

Revisions: 1

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

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

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

TR16-199 | 15th December 2016
Pavel Hubacek, Moni Naor, Eylon Yogev

The Journey from NP to TFNP Hardness

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

TR16-049 | 28th March 2016
Cynthia Dwork, Moni Naor, Guy Rothblum

Spooky Interaction and its Discontents: Compilers for Succinct Two-Message Argument Systems

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

TR16-023 | 23rd February 2016
Ilan Komargodski, Moni Naor, Eylon Yogev

How to Share a Secret, Infinitely

Revisions: 4

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

TR15-146 | 7th September 2015
Elette Boyle, Moni Naor

Is There an Oblivious RAM Lower Bound?

Revisions: 1

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

TR13-014 | 11th January 2013
Zvika Brakerski, Moni Naor

Fast Algorithms for Interactive Coding

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

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

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

TR06-022 | 17th February 2006
Danny Harnik, Moni Naor

On the Compressibility of NP Instances and Cryptographic Applications

Revisions: 1

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

TR06-002 | 4th January 2006
Eyal Kaplan, Moni Naor, Omer Reingold

Derandomized Constructions of k-Wise (Almost) Independent Permutations

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

TR03-060 | 7th September 2003
Danny Harnik, Moni Naor, Omer Reingold, Alon Rosen

Completeness in Two-Party Secure Computation - A Computational View

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

TR02-043 | 11th July 2002
Dalit Naor, Moni Naor, Jeff Lotspiech

Revocation and Tracing Schemes for Stateless Receivers

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

TR02-001 | 8th January 2002
Cynthia Dwork, Moni Naor

Zaps and Their Applications

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

TR01-064 | 10th September 2001
Moni Naor, Omer Reingold, Alon Rosen

Pseudo-Random Functions and Factoring

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

TR01-062 | 9th September 2001
Moni Naor, Kobbi Nissim

Communication Complexity and Secure Function Evaluation

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

TR97-005 | 17th February 1997
Moni Naor, Omer Reingold

On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited

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

TR95-045 | 4th September 1995
Moni Naor, Omer Reingold

Synthesizers and Their Application to the Parallel Construction of Pseudo-random Functions

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

ISSN 1433-8092 | Imprint