All reports by Author Amos Beimel:

__
TR23-091
| 18th June 2023
__

Benny Applebaum, Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Tianren Liu, Vinod Vaikuntanathan#### Succinct Computational Secret Sharing

__
TR22-006
| 12th January 2022
__

Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, Toniann Pitassi#### Secret Sharing, Slice Formulas, and Monotone Real Circuits

__
TR20-008
| 26th January 2020
__

Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter#### Better Secret-Sharing via Robust Conditional Disclosure of Secrets

Revisions: 2

__
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 Dierentially Private Sampling

Revisions: 6

__
TR05-141
| 29th November 2005
__

Amos Beimel, Paz Carmi, Kobbi Nissim, Enav Weinreb#### Private Approximation of Search Problems

__
TR03-086
| 1st December 2003
__

Amos Beimel, Tal Malkin#### A Quantitative Approach to Reductions in Secure Computation

__
TR01-015
| 9th February 2001
__

Amos Beimel, Yuval Ishai#### Information-Theoretic Private Information Retrieval: A Unified Construction

__
TR95-001
| 1st January 1995
__

Amos Beimel, Anna Gal, Michael S. Paterson#### Lower Bounds for Monotone Span Programs

Benny Applebaum, Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Tianren Liu, Vinod Vaikuntanathan

A secret-sharing scheme enables a dealer to share a secret $s$ among $n$ parties such that only authorized subsets of parties, specified by a monotone access structure $f:\{0,1\}^n\to\{0,1\}$, can reconstruct $s$ from their shares. Other subsets of parties learn nothing about $s$.

The question of minimizing the (largest) share size ... more >>>

Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, Toniann Pitassi

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$. For over 30 years, it was known that any (monotone) collection of authorized sets can be ... more >>>

Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter

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

Amos Beimel, Iftach Haitner, Nikolaos Makriyannis, Eran Omri

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

Amos Beimel, Paz Carmi, Kobbi Nissim, Enav Weinreb

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

Amos Beimel, Tal Malkin

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

Amos Beimel, Yuval Ishai

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

Amos Beimel, Anna Gal, Michael S. Paterson

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