Benny Chor

I&C Journal 2005 Journal Article

Tight lower bounds for certain parameterized NP-hard problems

• Jianer Chen
• Benny Chor
• Mike Fellows
• Xiuzhen Huang
• David Juedes
• Iyad A. Kanj
• Ge Xia

Based on the framework of parameterized complexity theory, we derive tight lower bounds on the computational complexity for a number of well-known NP-hard problems. We start by proving a general result, namely that the parameterized weighted satisfiability problem on depth-t circuits cannot be solved in time n o(k) m O(1), where n is the circuit input length, m is the circuit size, and k is the parameter, unless the (t −1)-st level W[t −1] of the W-hierarchy collapses to FPT. By refining this technique, we prove that a group of parameterized NP-hard problems, including weighted sat, hitting set, set cover, and feature set, cannot be solved in time n o(k) m O(1), where n is the size of the universal set from which the k elements are to be selected and m is the instance size, unless the first level W[1] of the W-hierarchy collapses to FPT. We also prove that another group of parameterized problems which includes weighted q -sat (for any fixed q ⩾2), clique, independent set, and dominating set, cannot be solved in time n o(k) unless all search problems in the syntactic class SNP, introduced by Papadimitriou and Yannakakis, are solvable in subexponential time. Note that all these parameterized problems have trivial algorithms of running time either n k m O(1) or O(n k ).

I&C Journal 2001 Journal Article

On Privacy and Partition Arguments

• Benny Chor
• Yuval Ishai

A function and f(x 1, x 2, …, x n) is said to be t-private if there exists a (randomized) communication protocol for computing f, such that no coalition of at most t participants can infer any additional information from the execution of the protocol other than what follows from their inputs and the value of f. It is known that every n-argument function f defined over finite domains can be computed ⌊ n−1 2 ⌋-privately. The classes of 1-private two-argument functions and of t-private Boolean functions admit relatively simple characterizations. In contrast, the general question of characterizing the class of t-private functions of n arguments is still open. The only technique that appears in the literature for proving non-t-privacy of a function f(x 1, x 2, …, x n) over a finite domain, where n≥3 and ⌈ n 2 ⌉≤t≤n−1, uses a reduction to the two-party case via a partition argument. A necessary condition for f being t-private is that for every partition (S; S ) of the parties {1, 2, …, n} such that both |S|≤t and | S |≤t, the two-argument function obtained by viewing f as a function of {xi } i∈S and {xi } i∈ S is 1-private. The question whether the use of such partition reductions together with the two-party characterization is powerful enough to characterize privacy in the multiparty case was raised as an open problem in previous works. These works also exhibit an affirmative answer for specific classes of functions. We answer this question negatively. We show that even if more general partition reductions are used, in which the n parties are partitioned into k sets (2≤k≤n−1) rather than just two, those reductions are still too weak to characterize privacy. On the other hand, we show that increasing the number of sets k does give some extra characterization power.

STOC Conference 1997 Conference Paper

Computationally Private Information Retrieval (Extended Abstract)

• Benny Chor
• Niv Gilboa

FOCS Conference 1995 Conference Paper

Private Information Retrieval

• Benny Chor
• Oded Goldreich 0001
• Eyal Kushilevitz
• Madhu Sudan 0001

We describe schemes that enable a user to access k replicated copies of a database (k/spl ges/2) and privately retrieve information stored in the database. This means that each individual database gets no information on the identity of the item retrieved by the user. For a single database, achieving this type of privacy requires communicating the whole database, or n bits (where n is the number of bits in the database). Our schemes use the replication to gain substantial saving. In particular, we have: A two database scheme with communication complexity of O(n/sup 1/3/). A scheme for a constant number, k, of databases with communication complexity O(n/sup 1/k/). A scheme for 1/3 log/sub 2/ n databases with polylogarithmic (in n) communication complexity.

FOCS Conference 1990 Conference Paper

Private Computations Over the Integers (Extended Abstract)

• Benny Chor
• Mihály Geréb-Graus
• Eyal Kushilevitz

The possibility of private distributed computations of n-argument functions defined over the integers is considered. A function f is t-private if there exists a protocol for computing f so that no coalition of <or=t participants can infer any additional information from the execution of the protocol. It is shown that certain results for private computation over finite domains cannot be extended to infinite domains. The possibility of privately computing f is shown to be closely related to the communication complexity of f. A complete characterization of t-private Boolean functions over countable domains is given.

STOC Conference 1989 Conference Paper

A Zero-One Law for Boolean Privacy (extended abstract)

• Benny Chor
• Eyal Kushilevitz

STOC Conference 1989 Conference Paper

On the Theory of Average Case Complexity

• Shai Ben-David
• Benny Chor
• Oded Goldreich 0001
• Michael Luby

This paper takes the next step in developing the theory of average case complexity initiated by Leonid A. Levin. Previous works [Levin 84, Gurevich 87, Venkatesan and Levin 88] have focused on the existence of complete problems. We widen the scope to other basic questions in computational complexity. Our results include: the equivalence of search and decision problems in the context of average case complexity; an initial analysis of the structure of distributional-NP under reductions which preserve average polynomial-time; a proof that if all distributional-NP is in average polynomial-time then non-deterministic exponential-time equals deterministic exponential time (i.e., a collapse in the worst case hierarchy); definitions and basic theorems regarding other complexity classes such as average log-space.

FOCS Conference 1989 Conference Paper

Solvability in Asynchronous Environments (Extended Abstract)

• Benny Chor
• Lior Moscovici

The authors present necessary and sufficient combinatorial conditions that determine membership in SM/sub t/ (respectively, MP/sub t/), the class of distributed decision tasks that are solvable in the shared memory (resp. message passing) model by a t-resilient randomized protocol, which never errs and works in the presence of a strong adversary. The sufficiency of the conditions is proved by designing protocols that are applicable to all tasks in the appropriate class. The computational complexity of the membership characterization is studied. >

FOCS Conference 1985 Conference Paper

The Bit Extraction Problem of t-Resilient Functions (Preliminary Version)

• Benny Chor
• Oded Goldreich 0001
• Johan Håstad
• Joel Friedman
• Steven Rudich
• Roman Smolensky

We consider the following adversarial situation. Let n, m and t be arbitrary integers, and let f: {0, 1}n → {0, 1}m be a function. An adversary, knowing the function f, sets t of the n input bits, while the rest (n-t input, bits) are chosen at random (independently and with uniform probability distribution) The adversary tries to prevent the outcome of f from being uniformly distributed in {0, 1}m. The question addressed is for what values of n, m and t does the adversary necessarily fail in biasing the outcome of f: {0, 1}n → {0, 1}m, when being restricted to set t of the input bits of f. We present various lower and upper bounds on m's allowing an affirmative answer. These bounds are relatively close for t ≤ n/3 and for t ≥ 2n/3. Our results have applications in the fields of faulttolerance and cryptography.

FOCS Conference 1985 Conference Paper

Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity (Extended Abstract)

• Benny Chor
• Oded Goldreich 0001

We introduce a general model for physical sources or weak randomness. Loosely speaking, we view physical sources as devices which output strings according to probability distributions in which no single string is too probable. The main question addressed is whether it is possible to extract alrnost unbiased random bits from such "probability bounded" sources. We show that most or the functions can be used to extract almost unbiased and independent bits from the output of any two independent "probability-bounded" sources. The number of extractable bits is within a constant factor of the information theoretic bound. We conclude this paper by establishing further connections between communication complexity and the problem discussed above. This allows us to show that most Boolean functions have linear communication complexity in a very strong sense.

FOCS Conference 1985 Conference Paper

Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults (Extended Abstract)

• Benny Chor
• Shafi Goldwasser
• Silvio Micali
• Baruch Awerbuch

FOCS Conference 1984 Conference Paper

RSA/Rabin Bits are 1/2 + 1/poly(log N) Secure

• Werner Alexi
• Benny Chor
• Oded Goldreich 0001
• Claus-Peter Schnorr

We prove that RSA least significant bit is 1/2 + (1/[log c N]) secure, for any constant c (where N is the RSA modulus). This means that an adversary, given the ciphertext, cannot guess the least sigiiilicatnt bit of the plaintext with probability better than 1/2 + (1/[log c N]), unless he can break RSA.

STOC Conference 1983 Conference Paper

On the Cryptographic Security of Single RSA Bits

• Michael Ben-Or
• Benny Chor
• Adi Shamir

The ability to “hide” one bit in trapdoor functions has recently gained much interest in cryptography research, and is of great importance in many transactions protocols. In this paper we study the cryptographic security of RSA bits. In particular, we show that unless the cryptanalyst can completely break the RSA encryption, any heuristic he uses to determine the least significant bit of the cleartext must have an error probability greater than 1/4—ε A similar result is shown for Rabin's encryption scheme.

FOCS Conference 1982 Conference Paper

An Application of Number Theory to the Organization of Raster-Graphics Memory (Extended Abstract)

• Benny Chor
• Charles E. Leiserson
• Ronald L. Rivest

A high-resolution raster-graphics display is usually combined with processing power and a memory organization that facilitates basic graphics operations. For many applications, including interactive text processing, the ability to quickly move or copy small rectangles of pixels is essential. This paper proposes a novel organization of raster-graphics memory that permits all small rectangles to be moved efficiently. The memory organization is based on a doubly periodic assignment of pixels to M memory chips according to a "Fibonacci" lattice. The memory organization guarantees that if a rectilinearly oriented rectangle contains fewer than M/√5 pixels, then all pixels will reside in different memory chips, and thus can be accessed simultaneously. We also define a continuous amdogue of the problem which can be posed as, "What is the maximum density of a set of points in the plane such that no two points are contained in the interior of a rectilinearly oriented rectangle of area N. " We give a lower bound of 1/2N on the density of such a set, and show that 1/√5N can be achieved.