Benny Chor

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

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

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.