Arrow Research search

Author name cluster

Moni Naor

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

64 papers
2 author rows

Possible papers

64

FOCS Conference 2025 Conference Paper

Shuffling Cards When You Are of Very Little Brain: Low Memory Generation of Permutations

  • Boaz Menuhin
  • Moni Naor

How can we generate a permutation of the numbers 1 through n such that, given the history so far, it is hard to guess the next element? The twist is that the permutation generator (the "Dealer") has limited memory, while the "Guesser" has unlimited memory. With unbounded memory (or even just n bits), the Dealer can generate a truly random permutation, for which the expected number of correct guesses is ln n. Our main results establish tight bounds for the relationship between the guessing probability and the memory m required to generate the permutation. We suggest a method for an m-bit Dealer that operates in constant time per turn and ensures that any Guesser can correctly guess only O(n/m + log m) cards in expectation. The method is fully transparent, requiring no hidden information from the Dealer (i. e. , it is "open book" or "whitebox"). We further show that this bound is essentially optimal, even if the Dealer is allowed to use secret memory. Specifically, for any m-bit Dealer, there is a (computationally powerful) Guesser that achieves Ω(n/m + log m) correct guesses in expectation. We point out that the assumption that the Guesser is computationally powerful is necessary: under cryptographic assumptions, there exists a low-memory Dealer that can fool any computationally bounded Guesser. Finally, we present an O(n) bit memory Dealer that generates perfectly random permutations and operates in constant time per turn.

Details

SODA Conference 2024 Conference Paper

Adjacency Sketches in Adversarial Environments

  • Moni Naor
  • Eugene Pekel

An adjacency sketching or implicit labeling scheme for a family F of graphs is a method that defines for any n vertex G ∈ F an assignment of labels to each vertex in G, so that the labels of two vertices tell you whether or not they are adjacent. The goal is to come up with labeling schemes that use as few bits as possible to represent the labels. By using randomness when assigning labels, it is sometimes possible to produce adjacency sketches with much smaller label sizes, but this comes at the cost of introducing some probability of error. Both deterministic and randomized labeling schemes have been extensively studied, as they have applications for distributed data structures and deeper connections to universal graphs and communication complexity. The main question of interest is which graph families have schemes using short labels, usually O (log n ) in the deterministic case or constant for randomized sketches. In this work we consider the resilience of probabilistic adjacency sketches against an adversary making adaptive queries to the labels. This differs from the previously analyzed probabilistic setting which is “one shot”. We show that in the adaptive adversarial case the size of the labels is tightly related to the maximal degree of the graphs in F. This results in a stronger characterization compared to what is known in the non-adversarial setting. In more detail, we construct sketches that fail with probability ɛ for graphs with maximal degree d using 2 d log(1/ɛ) bit labels and show that this is roughly the best that can be done for any specific graph of maximal degree d, e. g. a d -ary tree. * The full version of the paper can be accessed at https: //arxiv. org/abs/2309. 03728

Details

TCS Journal 2023 Journal Article

Mirror games against an open book player

  • Roey Magen
  • Moni Naor

Mirror games were invented by Garg and Schneider (ITCS 2019). Alice and Bob take turns (with Alice playing first) in declaring numbers from the set { 1, 2, …, 2 n }. If a player picks a number that was previously played, that player loses the game and the other player wins. If all numbers are declared without repetition, the result is a draw. Bob has a simple mirror strategy that assures he won't lose the game and requires no memory. On the other hand, Garg and Schneider showed that every deterministic Alice requires memory of size that is proportional to n in order to secure a draw. Regarding probabilistic strategies, previous work showed that assuming Alice has access to a secret random perfect matching over { 1, 2, …, 2 n } allows her to achieve a draw in the game w. p. at least 1 − 1 n and using only polylog bits of memory. We show that the requirement for secret bits is crucial: for an ‘open book’ Alice with no secrets (Bob knows her memory but not future coin flips) and memory of at most n / 4 c bits for any c ≥ 2, there is a Bob that wins w. p. close to 1 − 2 − c / 2.

Details DOI

NeurIPS Conference 2023 Conference Paper

Private Everlasting Prediction

  • Moni Naor
  • Kobbi Nissim
  • Uri Stemmer
  • Chao Yan

A private learner is trained on a sample of labeled points and generates a hypothesis that can be used for predicting the labels of newly sampled points while protecting the privacy of the training set [Kasiviswannathan et al. , FOCS 2008]. Past research uncovered that private learners may need to exhibit significantly higher sample complexity than non-private learners as is the case of learning of one-dimensional threshold functions [Bun et al. , FOCS 2015, Alon et al. , STOC 2019]. We explore prediction as an alternative to learning. A predictor answers a stream of classification queries instead of outputting a hypothesis. Earlier work has considered a private prediction model with a single classification query [Dwork and Feldman, COLT 2018]. We observe that when answering a stream of queries, a predictor must modify the hypothesis it uses over time, and in a manner that cannot rely solely on the training set. We introduce {\em private everlasting prediction} taking into account the privacy of both the training set {\em and} the (adaptively chosen) queries made to the predictor. We then present a generic construction of private everlasting predictors in the PAC model. The sample complexity of the initial training sample in our construction is quadratic (up to polylog factors) in the VC dimension of the concept class. Our construction allows prediction for all concept classes with finite VC dimension, and in particular threshold functions over infinite domains, for which (traditional) private learning is known to be impossible.

PDF Details

STOC Conference 2021 Conference Paper

Adversarial laws of large numbers and optimal regret in online classification

  • Noga Alon
  • Omri Ben-Eliezer
  • Yuval Dagan
  • Shay Moran
  • Moni Naor
  • Eylon Yogev

Laws of large numbers guarantee that given a large enough sample from some population, the measure of any fixed sub-population is well-estimated by its frequency in the sample. We study laws of large numbers in sampling processes that can affect the environment they are acting upon and interact with it. Specifically, we consider the sequential sampling model proposed by Ben-Eliezer and Yogev (2020), and characterize the classes which admit a uniform law of large numbers in this model: these are exactly the classes that are online learnable . Our characterization may be interpreted as an online analogue to the equivalence between learnability and uniform convergence in statistical (PAC) learning. The sample-complexity bounds we obtain are tight for many parameter regimes, and as an application, we determine the optimal regret bounds in online learning, stated in terms of Littlestone’s dimension , thus resolving the main open question from Ben-David, Pál, and Shalev-Shwartz (2009), which was also posed by Rakhlin, Sridharan, and Tewari (2015).

Details

SODA Conference 2020 Conference Paper

The Power of Distributed Verifiers in Interactive Proofs

  • 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 graph G belongs to some language in a small number of rounds, and with small communication bound, i. e. , the proof size. This interactive model was introduced by Kol, Oshman and Saxena (PODC 2018) as a generalization of noninteractive distributed proofs. They demonstrated the power of interaction in this setting by constructing protocols for problems as Graph Symmetry and Graph Non-Isomorphism – both of which require proofs of Ω( n 2 )-bits without interaction. In this work, we provide a new general framework for distributed interactive proofs that allows one to translate standard interactive protocols (i. e. , with a centralized verifier) to ones where the verifier is distributed with a proof size that depends on the computational complexity of the verification algorithm run by the centralized verifier. We show the following: Every (centralized) computation performed in time O ( n ) on a RAM can be translated into three-round distributed interactive protocol with O (log n ) proof size. This implies that many graph problems for sparse graphs have succinct proofs (e. g. , testing planarity). Every (centralized) computation implemented by either a small space or by uniform NC circuit can be translated into a distributed protocol with O (1) rounds and O (log n ) bits proof size for the low space case and polylog( n ) many rounds and proof size for NC. We show that for Graph Non-Isomorphism, one of the striking demonstrations of the power of interaction, there is a 4-round protocol with O (log n ) proof size, improving upon the O ( n log n ) proof size of Kol et al. For many problems, we show how to reduce proof size below the seemingly natural barrier of log n. By employing our RAM compiler, we get a 5-round protocol with proof size O (log log n ) for a family of problems including Fixed Automorphism, Clique and Leader Election (for the latter two problems we actually get O (1) proof size). Finally, we discuss how to make these proofs noninteractive arguments via random oracles. Our compilers capture many natural problems and demonstrate the difficulty in showing lower bounds in these regimes.

Details

FOCS Conference 2017 Conference Paper

White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing

  • 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 while examining a linear number of edges. If the graph is given by a black-box, where to figure out whether a certain edge exists the box should be queried, then a large number of queries must be issued. But what if one is given a program or circuit for computing the existence of an edge? This problem was raised by Buss and Goldberg and Papadimitriou in the context of TFNP, search problems with a guaranteed solution. We examine the relationship between black-box complexity and white-box complexity for search problems with guaranteed solution such as the above Ramsey problem. We show that under the assumption that collision resistant hash function exist (which follows from the hardness of problems such as factoring, discrete-log and learning with errors) the white-box Ramsey problem is hard and this is true even if one is looking for a much smaller clique or independent set than the theorem guarantees. In general, one cannot hope to translate all black-box hardness for TFNP into white-box hardness: we show this by adapting results concerning the random oracle methodology and the impossibility of instantiating it. Another model we consider is the succinct black-box, where there is a known upper bound on the size of the black-box (but no limit on the computation time). In this case we show that for all TFNP problems there is an upper bound on the number of queries proportional to the description size of the box times the solution size. On the other hand, for promise problems this is not the case. Finally, we consider the complexity of graph property testing in the white-box model. We show a property which is hard to test even when one is given the program for computing the graph. The hard property is whether the graph is a two-source extractor.

Details

STOC Conference 2016 Conference Paper

Searchable symmetric encryption: optimal locality in linear space via two-dimensional balanced allocations

  • Gilad Asharov
  • Moni Naor
  • Gil Segev 0001
  • Ido Shahaf

Searchable symmetric encryption (SSE) enables a client to store a database on an untrusted server while supporting keyword search in a secure manner. Despite the rapidly increasing interest in SSE technology, experiments indicate that the performance of the known schemes scales badly to large databases. Somewhat surprisingly, this is not due to their usage of cryptographic tools, but rather due to their poor locality (where locality is defined as the number of non-contiguous memory locations the server accesses with each query). The only known schemes that do not suffer from poor locality suffer either from an impractical space overhead or from an impractical read efficiency (where read efficiency is defined as the ratio between the number of bits the server reads with each query and the actual size of the answer). We construct the first SSE schemes that simultaneously enjoy optimal locality, optimal space overhead, and nearly-optimal read efficiency. Specifically, for a database of size N , under the modest assumption that no keyword appears in more than N 1 − 1/loglog N documents, we construct a scheme with read efficiency Õ(loglog N ). This essentially matches the lower bound of Cash and Tessaro (EUROCRYPT ’14) showing that any SSE scheme must be sub-optimal in either its locality, its space overhead, or its read efficiency. In addition, even without making any assumptions on the structure of the database, we construct a scheme with read efficiency Õ(log N ). Our schemes are obtained via a two-dimensional generalization of the classic balanced allocations (“balls and bins”) problem that we put forward. We construct nearly-optimal two-dimensional balanced allocation schemes, and then combine their algorithmic structure with subtle cryptographic techniques.

Details

FOCS Conference 2014 Conference Paper

One-Way Functions and (Im)Perfect Obfuscation

  • Ilan Komargodski
  • Tal Moran
  • Moni Naor
  • Rafael Pass
  • Alon Rosen
  • Eylon Yogev

A program obfuscator takes a program and outputs a "scrambled" version of it, where the goal is that the obfuscated program will not reveal much about its structure beyond what is apparent from executing it. There are several ways of formalizing this goal. Specifically, in indistinguishability obfuscation, first defined by Barak et al. (CRYPTO 2001), the requirement is that the results of obfuscating any two functionally equivalent programs (circuits) will be computationally indistinguishable. Recently, a fascinating candidate construction for indistinguishability obfuscation was proposed by Garg et al. (FOCS 2013). This has led to a flurry of discovery of intriguing constructions of primitives and protocols whose existence was not previously known (for instance, fully deniable encryption by Sahai and Waters, STOC 2014). Most of them explicitly rely on additional hardness assumptions, such as one-way functions. Our goal is to get rid of this extra assumption. We cannot argue that indistinguishability obfuscation of all polynomial-time circuits implies the existence of one-way functions, since if P ≠ NP, then program obfuscation (under the indistinguishability notion) is possible. Instead, the ultimate goal is to argue that if P ≠ NP and program obfuscation is possible, then one-way functions exist. Our main result is that if NP ⊈; io-BPP and there is an efficient (even imperfect) indistinguishability obfuscator, then there are one-way functions. In addition, we show that the existence of an indistinguishability obfuscator implies (unconditionally) the existence of SZK-arguments for NP. This, in turn, provides an alternative version of our main result, based on the assumption of hard-on-the average NP problems. To get some of our results we need obfuscators for simple programs such as 3CNF formulas

Details

SODA Conference 2013 Conference Paper

Fast Algorithms for Interactive Coding

  • Zvika Brakerski
  • Moni Naor

Consider two parties who wish to communicate in order to execute some interactive protocol π. 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 π (which was designed for an errorless channel). If π only contained one message, then a good error correcting code would have overcame the noise with only a constant overhead in communication, but this solution is not applicable to interactive protocols with many short messages. Schulman (FOCS 92, STOC 93) presented the notion of interactive coding: A simulator that, given any protocol π, is able to simulate it (i. e. produce its intended transcript) even with constant rate adversarial channel errors, and with only constant (multiplicative) communication overhead. Until recently, however, the running time of all known simulators was exponential (or sub-exponential) in the communication complexity of π (denoted N in this work). Brakerski and Kalai (FOCS 12) recently presented a simulator that runs in time poly( N ). Their simulator is randomized (each party flips private coins) and has failure probability roughly 2 −- N. In this work, we improve the computational complexity of interactive coding. While at least N computational steps are required (even just to output the transcript of π), the BK simulator runs in time. We present two efficient algorithms for interactive coding: The first with computational complexity O ( N log N ) and exponentially small failure probability; and the second with computational complexity O ( N ), but failure probability 1/poly( N ). (Computational complexity is measured in the RAM model.)

Details

FOCS Conference 2012 Conference Paper

The Privacy of the Analyst and the Power of the State

  • Cynthia Dwork
  • Moni Naor
  • Salil P. Vadhan

We initiate the study of "privacy for the analyst" in differentially private data analysis. That is, not only will we be concerned with ensuring differential privacy for the data (i. e. individuals or customers), which are the usual concern of differential privacy, but we also consider (differential) privacy for the set of queries posed by each data analyst. The goal is to achieve privacy with respect to other analysts, or users of the system. This problem arises only in the context of stateful privacy mechanisms, in which the responses to queries depend on other queries posed (a recent wave of results in the area utilized cleverly coordinated noise and state in order to allow answering privately hugely many queries). We argue that the problem is real by proving an exponential gap between the number of queries that can be answered (with non-trivial error) by stateless and stateful differentially private mechanisms. We then give a stateful algorithm for differentially private data analysis that also ensures differential privacy for the analyst and can answer exponentially many queries.

Details

FOCS Conference 2010 Conference Paper

Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation

  • Yuriy Arbitman
  • Moni Naor
  • Gil Segev 0001

The performance of a dynamic dictionary is measured mainly by its update time, lookup time, and space consumption. In terms of update time and lookup time there are known constructions that guarantee constant-time operations in the worst case with high probability, and in terms of space consumption there are known constructions that use essentially optimal space. However, although the first analysis of a dynamic dictionary dates back more than 45 years ago (when Knuth analyzed linear probing in 1963), the trade-off between these aspects of performance is still not completely understood. In this paper we settle two fundamental open problems: · We construct the first dynamic dictionary that enjoys the best of both worlds: it stores n elements using (1 + ϵ)n memory words, and guarantees constant-time operations in the worst case with high probability. Specifically, for any ϵ = Ω((log log n/log n) 1/2 ) and for any sequence of polynomially many operations, with high probability over the randomness of the initialization phase, all operations are performed in constant time which is independent of e. The construction is a two-level variant of cuckoo hashing, augmented with a "backyard" that handles a large fraction of the elements, together with a de-amortized perfect hashing scheme for eliminating the dependency on e. · We present a variant of the above construction that uses only (1 + o(1))B bits, where B is the information-theoretic lower bound for representing a set of size n taken from a universe of size u, and guarantees constant-time operations in the worst case with high probability, as before. This problem was open even in the amortized setting. One of the main ingredients of our construction is a permutation-based variant of cuckoo hashing, which significantly improves the space consumption of cuckoo hashing when dealing with a rather small universe.

Details

TCS Journal 2010 Journal Article

Basing cryptographic protocols on tamper-evident seals

  • Tal Moran
  • Moni Naor

In this article, we attempt to formally study two very intuitive physical models: sealed envelopes and locked boxes, often used as illustrations for common cryptographic operations. We relax the security properties usually required from locked boxes [such as in bit-commitment (BC) protocols] and require only that a broken lock or torn envelope be identifiable to the original sender. Unlike the completely impregnable locked box, this functionality may be achievable in real life, where containers having this property are called “tamper-evident seals”. Another physical object with this property is the “scratch-off card”, often used in lottery tickets. We consider three variations of tamper-evident seals, and show that under some conditions they can be used to implement oblivious transfer, BC and coin flipping (CF). We also show a separation between the three models. One of our results is a strongly fair CF protocol with bias bounded by O ( 1 / r ) (where r is the number of rounds); this was a stepping stone towards achieving such a protocol in the standard model (in subsequent work).

Details DOI

STOC Conference 2008 Conference Paper

Sketching in adversarial environments

  • Ilya Mironov
  • Moni Naor
  • Gil Segev 0001

We formalize a realistic model for computations over massive data sets. The model, referred to as the {\em adversarial sketch model}, unifies the well-studied sketch and data stream models together with a cryptographic flavor that considers the execution of protocols in "hostile environments", and provides a framework for studying the complexity of many tasks involving massive data sets. The adversarial sketch model consists of several participating parties: honest parties, whose goal is to compute a pre-determined function of their inputs, and an adversarial party. Computation in this model proceeds in two phases. In the first phase, the adversarial party chooses the inputs of the honest parties. These inputs are sets of elements taken from a large universe, and provided to the honest parties in an on-line manner in the form of a sequence of insert and delete operations. Once an operation from the sequence has been processed it is discarded and cannot be retrieved unless explicitly stored. During this phase the honest parties are not allowed to communicate. Moreover, they do not share any secret information and any public information they share is known to the adversary in advance. In the second phase, the honest parties engage in a protocol in order to compute a pre-determined function of their inputs. In this paper we settle the complexity (up to logarithmic factors) of two fundamental problems in this model: testing whether two massive data sets are equal, and approximating the size of their symmetric difference. We construct explicit and efficient protocols with sublinear sketches of essentially optimal size, poly-logarithmic update time during the first phase, and poly-logarithmic communication and computation during the second phase. Our main technical contribution is an explicit and deterministic encoding scheme that enjoys two seemingly conflicting properties: incrementality and high distance, which may be of independent interest.

Details

FOCS Conference 2006 Conference Paper

On the Compressibility of NP Instances and Cryptographic Applications

  • Danny Harnik
  • Moni Naor

We initiate the study of compression that preserves the solution to an instance of a problem rather than preserving the instance itself. Our focus is on the compressibility of NP decision 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 not. We want the length of the compressed instance to be polynomial in the length of the witness rather than the length of original input. Such compression enables to succinctly store instances until a future setting will allow solving them, either via a technological or algorithmic breakthrough or simply until enough time has elapsed. We give a new classification of NP with respect to compression. This classification forms a stratification of NP that we call the VC hierarchy. The hierarchy is based on a new type of reduction called W-reduction and there are compression-complete problems for each class. Our motivation for studying this issue stems from the vast cryptographic implications compressibility has. For example, we say that SAT is compressible if there exists a polynomial p(middot, middot) so that given a formula consisting of m clauses over n variables it is possible to come up with an equivalent (w. r. t satisfiability) formula of size at most p(n, log m). Then given a compression algorithm for SAT we provide a construction of collision resistant hash functions from any one-way function. This task was shown to be impossible via black-box reductions (D. Simon, 1998), and indeed the construction presented is inherently non-black-box. Another application of SAT compressibility is a cryptanalytic result concerning the limitation of everlasting security in the bounded storage model when mixed with (time) complexity based cryptography. In addition, we study an approach to constructing an oblivious transfer protocol from any one-way function. This approach is based on compression for SAT that also has a property that we call witness retrievability. However, we mange to prove severe limitations on the ability to achieve witness retrievable compression of SAT

Details

FOCS Conference 2005 Conference Paper

The Complexity of Online Memory Checking

  • Moni Naor
  • Guy N. Rothblum

We consider the problem of storing a large file on a remote and unreliable server. To verify that the file has not been corrupted, a user could store a small private (randomized) "fingerprint" on his own computer. This is the setting for the well-studied authentication problem in cryptography, and the required fingerprint size is well understood. We study the problem of sub-linear authentication: suppose the user would like to encode and store the file in a way that allows him to verify that it has not been corrupted, but without reading the entire file. If the user only wants to read t bits of the file, how large does the size s of the private fingerprint need to be? We define this problem formally, and show a tight lower bound on the relationship between s and t when the adversary is not computationally bounded, namely: s /spl times/ t = /spl Omega/(n), where n is the file size. This is an easier case of the online memory checking problem, introduced by Blum et al. in 1991, and hence the same (tight) lower bound applies also to that problem. It was previously shown that when the adversary is computationally bounded, under the assumption that one-way functions exist, it is possible to construct much better online memory checkers and sub-linear authentication schemes. We show that the existence of one-way functions is also a necessary condition: even slightly breaking the s /spl times/ t = /spl Omega/(n) lower bound in a computational setting implies the existence of one-way functions.

Details

STOC Conference 2004 Conference Paper

Completeness in two-party secure computation: a computational view

  • 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 two-party computation. A function f is complete for SFE if a protocol for securely evaluating f allows the secure evaluation of all (efficiently computable) functions. The questions investigated are which functions are complete for SFE, which functions have SFE protocols unconditionally and whether there are functions that are neither complete nor have efficient SFE protocols.The previous study of these questions was mainly conducted from an Information Theoretic point of view and provided strong answers in the form of combinatorial properties. However, we show that there are major differences between the information theoretic and computational settings. In particular, we show functions that are considered as having SFE unconditionally by the combinatorial criteria but are actually complete in the computational setting. We initiate the fully computational study of these fundamental questions. Somewhat surprisingly, we manage to provide an almost full characterization of the complete functions in this model as well. More precisely, we present a computational criterion (called computational row non-transitivity ) for a function f to be complete for the asymmetric case. Furthermore, we show a matching criterion called computational row transitivity for f to have a simple SFE (based on no additional assumptions). This criterion is close to the negation of the computational row non-transitivity and thus we essentially characterize all "nice" functions as either complete or having SFE unconditionally.

Details

FOCS Conference 2000 Conference Paper

Zaps and Their Applications

  • 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, based on the existence of non-interactive zero-knowledge proofs in the shared random string model. The zap is in the standard model, and hence requires no common guaranteed random string. We introduce and construct verifiable pseudo-random bit generators (VPRGs), and give a complete existential characterization of both noninteractive zero-knowledge proofs and zaps in terms of approximate VPRGs. We present several applications for zaps; In the timing model of C. Dwork et al. (1998) and using moderately hard functions, we obtain 3-round concurrent zero knowledge and 2-round concurrent deniable authentication (the latter protocol also operates in the resettable model of R. Canetti et al. (2000)). In the standard model we obtain 2-round oblivious transfer using public keys (3-round otherwise). We note that any zap yields resettable 2-round witness-indistinguishability and obtain a 3-round timing-based resettable zero-knowledge argument system for any language in NP.

Details

FOCS Conference 1999 Conference Paper

Magic Functions

  • Cynthia Dwork
  • Moni Naor
  • Omer Reingold
  • Larry J. Stockmeyer

In this paper we show that three apparently unrelated problems are in fact very closely related. We sketch these problems at a high level. The selective decommitment problem first arose in a slightly different form, selective decryption, in the context of Byzantine agreement, no later than 1985. Instead of seeing encryptions of plaintexts the adversary is given commitments to the plaintexts. This problem is poorly understood even in strong-receiver commitments, which leak no information about the plaintext values information-theoretically. The second problem is in complexity theory: what can be proved in (a possibly weakened form of) zero-knowledge in a 3-round argument (interactive proof in which the prover is polynomial-time bounded)? The Fiat-Shamir Methodology is cryptographic, and addresses a methodology suggested by Fiat and Shamir (1987) to construct a (non-interactive) signature scheme from any 3-round (not necessarily zero-knowledge) public-coin identification scheme.

Details

FOCS Conference 1997 Conference Paper

Does Parallel Repetition Lower the Error in Computationally Sound Protocols?

  • Mihir Bellare
  • Russell Impagliazzo
  • Moni Naor

Whether or not parallel repetition lowers the error has been a fundamental question in the theory of protocols, with applications in many different areas. It is well known that parallel repetition reduces the error at an exponential rate in interactive proofs and Arthur-Merlin games. It seems to have been taken for granted that the same is true in arguments, or other proofs where the soundness only holds with respect to computationally bounded parties. We show that this is not the case. Surprisingly, parallel repetition can actually fail in this setting. We present four-round protocols whose error does not decrease under parallel repetition. This holds for any (polynomial) number of repetitions. These protocols exploit non-malleable encryption and can be based on any trapdoor permutation. On the other hand we show that for three-round protocols the error does go down exponentially fast. The question of parallel error reduction is particularly important when the protocol is used in cryptographic settings like identification, and the error represents the probability that an intruder succeeds.

Details

FOCS Conference 1997 Conference Paper

Number-theoretic Constructions of Efficient Pseudo-random Functions

  • Moni Naor
  • Omer Reingold

We describe efficient constructions for various cryptographic primitives (both in private-key and in public-key cryptography). We show these constructions to be at least as secure as the decisional version of the Diffie-Hellman assumption or as the assumption that factoring is hard. Our major result is a new construction of pseudo-random functions such that computing their value at any given point involves two multiple products. This is much more efficient than previous proposals. Furthermore, these functions have the advantage of being in TC/sup 0/ (the class of functions computable by constant depth circuits consisting of a polynomial number of threshold gates) which has several interesting applications. The simple algebraic structure of the functions implies additional features. In particular, we show a zero-knowledge proof for statements of the form "y=f/sub s/(x)" and "y/spl ne/f(x)" given a commitment to a key s of a pseudo-random function f/sub s/.

Details

FOCS Conference 1995 Conference Paper

Splitters and Near-Optimal Derandomization

  • Moni Naor
  • Leonard J. Schulman
  • Aravind Srinivasan

We present a fairly general method for finding deterministic constructions obeying what we call k-restrictions; this yields structures of size not much larger than the probabilistic bound. The structures constructed by our method include (n, k)-universal sets (a collection of binary vectors of length n such that for any subset of size k of the indices, all 2/sup k/ configurations appear) and families of perfect hash functions. The near-optimal constructions of these objects imply the very efficient derandomization of algorithms in learning, of fixed-subgraph finding algorithms, and of near optimal /spl Sigma/II/spl Sigma/ threshold formulae. In addition, they derandomize the reduction showing the hardness of approximation of set cover. They also yield deterministic constructions for a local-coloring protocol, and for exhaustive testing of circuits.

Details

FOCS Conference 1995 Conference Paper

Synthesizers and Their Application to the Parallel Construction of Psuedo-Random Functions

  • Moni Naor
  • Omer Reingold

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/sup 1/ implementation of pseudo-random synthesizers based on the RSA or the Diffie-Hellman assumptions. This yields the first parallel (NC/sup 2/) pseudo-random function and the only alternative to the original construction of Goldreich, Gold-wasser and Micali (GGM). The security of our constructions is similar to the security of the underling assumptions. We discuss the connection with problems in computational learning theory.

Details

FOCS Conference 1994 Conference Paper

The Load, Capacity and Availability of Quorum Systems

  • Moni Naor
  • Avishai Wool

A quorum system is a collection of sets (quorums) every two of which have a nonempty intersection. Quorum systems have been used for a number of applications in the area of distributed systems. We investigate the load, capacity and availability of quorum systems. We present four novel constructions of quorum system, all featuring optimal or near optimal load, and high availability. These desirable properties of the constructions translate into improvements of any protocol using them: a low work load on the processors and a high resilience to processor failures. The best construction, based on paths in a grid, has a load of O(1//spl radic/n), and a failure probability of exp(-O(/spl radic/n)) when the elements fail with probability p >

Details

FOCS Conference 1992 Conference Paper

Fault Tolerant Graphs, Perfect Hash Functions and Disjoint Paths

  • Miklós Ajtai
  • Noga Alon
  • Jehoshua Bruck
  • Robert Cypher
  • Ching-Tien Ho
  • Moni Naor
  • Endre Szemerédi

Given a graph G on n nodes the authors say that a graph T on n + k nodes is a k-fault tolerant version of G, if one can embed G in any n node induced subgraph of T. Thus T can sustain k faults and still emulate G without any performance degradation. They show that for a wide range of values of n, k and d, for any graph on n nodes with maximum degree d there is a k-fault tolerant graph with maximum degree O(kd). They provide lower bounds as well: there are graphs G with maximum degree d such that any k-fault tolerant version of them has maximum degree at least Omega (d square root k). >

Details

FOCS Conference 1992 Conference Paper

Witnesses for Boolean Matrix Multiplication and for Shortest Paths

  • Noga Alon
  • Zvi Galil
  • Oded Margalit
  • Moni Naor

The subcubic (O(n/sup w/) for w(3) algorithms to multiply Boolean matrices do not provide the witnesses; namely, they compute C=A. B but if C/sub ij/=1 they do not find an index k (a witness) such that A/sub ik/=B/sub kj/=1. The authors design a deterministic algorithm for computing the matrix of witnesses that runs in O(n/sup w/) time, where here O(n/sup w/) denotes O(n/sup w/(log n)/sup O(1)/). The subcubic methods to compute the shortest distances between all pairs of vertices also do not provide for witnesses; namely they compute the shortest distances but do not generate information for computing quickly the paths themselves. A witness for a shortest path from v/sub i/ to v/sub j/ is an index k such that v/sub k/ is the first vertex on such a path. They describe subcubic methods to compute such witnesses for several versions of the all pairs shortest paths problem. As a result, they derive shortest paths algorithms that provide characterization of the shortest paths in addition to the shortest distances in the same time (up to a polylogarithmic factor) needed for computing the distances; namely O(n/sup (3+w)/2/) time in the directed case and O(n/sup w/) time in the undirected case. They also design an algorithm that computes witnesses for the transitive closure in the same time needed to compute witnesses for Boolean matrix multiplication. >

Details

FOCS Conference 1991 Conference Paper

Amortized Communication Complexity (Preliminary Version)

  • Tomás Feder
  • Eyal Kushilevitz
  • Moni Naor

The authors study the direct sum problem with respect to communication complexity: Consider a function f: D to (0, 1), where D contained in (0, 1)/sup n/*(0, 1)/sup n/. The amortized communication complexity of f, i. e. the communication complexity of simultaneously computing f on l instances, divided by l is studied. The authors present, both in the deterministic and the randomized model, functions with communication complexity Theta (log n) and amortized communication complexity O(1). They also give a general lower bound on the amortized communication complexity of any function f in terms of its communication complexity C(f). >

Details

FOCS Conference 1991 Conference Paper

Checking the Correctness of Memories

  • Manuel Blum 0001
  • William S. Evans
  • Peter Gemmell
  • Sampath Kannan
  • Moni Naor

The notion of program checking is extended to include programs that alter their environment, in particular, programs that store and retrieve data from memory. The model considered allows the checker a small amount of reliable memory. The checker is presented with a sequence of requests (online) to a data structure which must reside in a large but unreliable memory. The data structure is viewed as being controlled by an adversary. The checker is to perform each operation in the input sequence using its reliable memory and the unreliable data structure so that any error in the operation of the structure will be detected by the checker with high probability. Checkers for various data structures are presented. Lower bounds of log n on the amount of reliable memory needed by these checkers, where n is the size of the structure, are proved. >

Details

FOCS Conference 1991 Conference Paper

Optimal File Sharing in Distributed Networks (Preliminary Version)

  • Moni Naor
  • Ron M. Roth

Given a distributed network of processors represented by an undirected graph G=(V, E) and a file size k, the problem of distributing an arbitrary file w of k bits among all nodes of the network G is considered. Memory devices are to be assigned to the node of G such that, by accessing the memory of its own and of its adjacent nodes, each node can reconstruct the contents of w. The objective is to minimize the total size memory in the network. A file distribution scheme that realizes this objective for k>>log Delta /sub G/, where Delta /sub G/, stands for the maximum degree in G, is presented. For this range of k, the total size of memory required by the suggested scheme approaches an integer programming lower bound on that size. >

Details

FOCS Conference 1991 Conference Paper

Search Problems in the Decision Tree Model (Preliminary Version)

  • László Lovász 0001
  • Moni Naor
  • Ilan Newman
  • Avi Wigderson

The relative power of determinism, randomness, and nondeterminism for search problems in the Boolean decision tree model is studied. It is shown that the CNF search problem is complete for all the variants of decision trees. It is then shown that the gaps between the nondeterministic, the randomized, and the deterministic complexities can be arbitrarily large for search problems. The special case of nondeterministic complexity is discussed. >

Details

FOCS Conference 1989 Conference Paper

Efficient Cryptographic Schemes Provably as Secure as Subset Sum

  • Russell Impagliazzo
  • Moni Naor

Very efficient constructions, based on the intractability of the subset sum problem for certain dimensions, are shown for a pseudorandom generator and for a universal one-way hash function. (Pseudorandom generators can be used for private key encryption, and universal one-way hash functions for signature schemes). The increase in efficiency in the construction is due to the fact that many bits can be generated/hashed with one application of the assumed one-way function. All the constructions can be implemented in NC using an optimal number of processors. >

Details

FOCS Conference 1989 Conference Paper

The Probabilistic Method Yields Deterministic Parallel Algorithms

  • Rajeev Motwani 0001
  • Joseph Naor
  • Moni Naor

A method is provided for converting randomized parallel algorithms into deterministic parallel algorithms. The approach is based on a parallel implementation of the method of conditional probabilities. Results obtained by applying the method to the set balancing problem, lattice approximation, edge-coloring graphs, random sampling, and combinatorial constructions are presented. The general form in which the method of conditional probabilities is applied sequentially is described. The reason why this form does not lend itself to parallelization are discussed. The general form of the case for which the method of conditional probabilities can be applied in the parallel context is given. >

Details