Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Amos Beimel:

TR20-008 | 26th January 2020
Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter

Better Secret-Sharing via Robust Conditional Disclosure of Secrets

A secret-sharing scheme allows to distribute a secret $s$ among $n$ parties such that only some predefined ``authorized'' sets of parties can reconstruct the secret, and all other ``unauthorized'' sets learn nothing about $s$. The collection of authorized sets is called the access structure. For over 30 years, it was ... more >>>

TR17-168 | 5th November 2017
Amos Beimel, Iftach Haitner, Nikolaos Makriyannis, Eran Omri

Tighter Bounds on Multi-Party Coin Flipping, via Augmented Weak Martingales and Di erentially Private Sampling

Revisions: 6

In his seminal work, Cleve [STOC 1986] has proved that any r-round coin-flipping protocol can be efficiently biassed by ?(1/r). The above lower bound was met for the two-party case by Moran, Naor, and Segev [Journal of Cryptology '16], and the three-party case (up to a polylog factor) by Haitner ... more >>>

TR05-141 | 29th November 2005
Amos Beimel, Paz Carmi, Kobbi Nissim, Enav Weinreb

Private Approximation of Search Problems

Many approximation algorithms have been presented in the last decades
for hard search problems. The focus of this paper is on cryptographic
applications, where it is desired to design algorithms which do not
leak unnecessary information. Specifically, we are interested in
private approximation algorithms -- efficient algorithms ... more >>>

TR03-086 | 1st December 2003
Amos Beimel, Tal Malkin

A Quantitative Approach to Reductions in Secure Computation

Secure computation is one of the most fundamental cryptographic tasks.
It is known that all functions can be computed securely in the
information theoretic setting, given access to a black box for some
complete function such as AND. However, without such a black box, not
all functions can be securely ... more >>>

TR01-015 | 9th February 2001
Amos Beimel, Yuval Ishai

Information-Theoretic Private Information Retrieval: A Unified Construction

A Private Information Retrieval (PIR) protocol enables a user to
retrieve a data item from a database while hiding the identity of the
item being retrieved. In a $t$-private, $k$-server PIR protocol the
database is replicated among $k$ servers, and the user's privacy is
protected from any collusion of up ... more >>>

TR95-001 | 1st January 1995
Amos Beimel, Anna Gal, Michael S. Paterson

Lower Bounds for Monotone Span Programs

The model of span programs is a linear algebraic model of
computation. Lower bounds for span programs imply lower bounds for
contact schemes, symmetric branching programs and for formula size.
Monotone span programs correspond also to linear secret-sharing schemes.
We present a new technique for proving lower bounds for ... more >>>

ISSN 1433-8092 | Imprint