Amos Beimel's Publications (updated August 2013)
Copyright and Accuracy
The Copyright for the papers below are with the respective publishers.
Online versions are provided for research purposes only. The versions
provided may not be identical to the published ones and some include more
updated reports.
 A. Beimel, Y. Ishai, E. Kushilevitz, and
I. Orlov. Share conversion and private information
retrieval. In Proc. of the 27th Annu. IEEE Conf. on Computational Complexity,
pages 258268, 2012.
pdf
 A. Beimel. Private Information Retrieval: A Primer.
(ps),
(pdf).
Submitted for
publication, 2008.

A. Beimel,
Y. Ishai, E. Kushilevitz,
and J. F. Raymond. Breaking the
Barrier for InformationTheoretic Private Information
Retrieval.(ps),
(pdf).
In
Proc. of the 43rd IEEE Symposium on Foundations of Computer Science
(FOCS), pages 261270, 2002.
Full version:
(ps),
(pdf).
[Updated April 2006]

A. Beimel and Y. Stahl. Robust InformationTheoretic Private Information
Retrieval (ps),
(pdf).
In Proc. of the 3rd Conference on Security in Communication Networks,
volume 2576 of Lecture
Notes in Computer Science, pages 326–341,
2002.
Journal version:
(ps),
(pdf).
[Updated July 2006]

A. Beimel,
Y. Ishai, and E. Kushilevitz. General
constructions for informationtheoretic private information retrieval.
(ps),
(pdf).
JCSS, 71(2):247281, 2005. This paper includes the results of
A. Beimel and
Y. Ishai. InformationTheoretic Private Information Retrieval: A Unified
Construction.
(ps),
(pdf).
ICALP 2001, volume 2076 of LNCS, pages 8998, 2001.

A. Beimel,
Y. Ishai, and
T. Malkin.
Reducing the Servers Computation in Private Information Retrieval: PIR
with Preprocessing
(ps),
(pdf).
Journal of Cryptology, 17(2):125151, 2004.
Conference version:
CRYPTO
2000, vol. 1880 of LNCS, pages 5674. Springer, 2000.

A. Beimel,
Y. Ishai,
T. Malkin, and
E.
Kushilevitz.
Oneway
functions are essential for singleserver private information retrieval.
In Proc. of the 31st Annu. ACM Symp. on the Theory of Computing (STOC),
pages 8998, 1999.
SecretSharing and Key Distribution

A. Beimel, A. BenEfraim,
C. Padró, and Ilya Tyomkin.
Multilinear secret sharing schemes.
In
Proc. of the 11th Theory of Cryptography Conference,
volume 8349 of Lecture Notes in Computer Science, pages 394418, SpringerVerlag,
2014.
PDF file.
 A. Beimel, O. Farras, and Y. Mintz.
Secret sharing schemes for very dense graphs (pdf). In
Advances in Cryptology – CRYPTO 2012,
Lecture Notes in Computer Science,
SpringerVerlag,
2012.
 A. Beimel. SecretSharing Schemes: A Survey (pdf), 2011
 A. Beimel and I. Orlov. Secret Sharing and NonShannon Information Inequalities. In
Proc. of the 6th Theory of Cryptography Conference, volume 5444 of Lecture
Notes in Computer Science, pages 539–557, SpringerVerlag, 2009.
(pdf),
(ps).

A. Beimel and A. Paskin. On linear secret sharing for
connectivity in directed graphs. In Proc. of the Sixth Conference
on Security and Cryptography for Networks, volume 5229 of Lecture
Notes in Computer Science, pages 172–184, SpringerVerlag, 2008.
(pdf),
(ps).

A. Beimel, N.
Livne, and C. Padró.
Matroids Can Be Far From Ideal Secret Sharing.
In Proc. of the fifth Theory of Cryptography Conference,
2008.
(ps),
(pdf).

A. Beimel and M. Franklin.
WeaklyPrivate Secret Sharing.
In the Fourth Theory of Cryptography Conference,
2007.
(ps),
(pdf).

A. Beimel and N. Livne.
On Matroids and Nonideal Secret Sharing.
In Proc. of the third Theory of Cryptography Conference,
volume 3876 of Lecture
Notes in Computer Science, pages 482501,
2006.
(ps),
(pdf).
Journal version: IEEE Trans. on Info. Theory, 2008. To appear.
(ps),
(pdf).
[Updated Dec. 2007]

A. Beimel,
T. Tassa, and
E. Weinreb.
Characterizing Ideal Weighted Threshold Secret Sharing
(ps),
(pdf).
In Proc. of the second Theory of Cryptography Conference,
volume 3378 of Lecture
Notes in Computer Science, pages 600–619,
2005.
Full version:
(ps),
(pdf).
[Updated October 2006]

A. Beimel and
Y.
Ishai. On the power of nonlinear secretsharing (ps),
(pdf).
SIAM Journal on Discrete Mathematics, 19(1):258280, 2005.
Conference version: IEEE Conference on Computational Complexity,
pages 188  202, 2001.
[Updated August 2004]

A. Beimel,
M. Burmester,
Y.
Desmedt, and E. Kushilevitz.
Computing
functions of a shared secret. SIAM J. on Discrete Mathematics.
13(3):324345, 2000.

A. Beimel and
B. Chor.
Secret
sharing with public reconstruction.
IEEE Trans. on Info. Theory,
44(5):18871896, 1998. Extended abstract in CRYPTO '95.

A. Beimel and
B. Chor.
Communication
in key distribution schemes.
IEEE Trans. on Info. Theory, 42(1):1928,
1996. Extended abstract in CRYPTO '93, vol. 773 of LNCS, pp. 444455. 1994.

A. Beimel and
B. Chor.
Universally
ideal secret sharing schemes.
IEEE Trans. on Info. Theory, 40(3):786794,
1994. Extended abstract in CRYPTO '92.

A. Beimel. Secure
Schemes for Secret Sharing and Key Distribution. Dept.
of Computer Science, Technion,
1996. Advisor: Benny Chor.
Differential Privacy

A. Beimel, K. Nissim,
and U. Stemmer.
Learning privately with labeled and unlabeled
examples. In Proc. of the ACMSIAM Symposium on Discrete Algorithms  SODA'15, 2015.
To appear. Full version CoRR, abs/1407.2662.

A. Beimel, K. Nissim,
and U. Stemmer.
Private Learning and Sanitization: Pure vs. Approximate Differential Privacy.
In Proceedings of the 17th International Workshop on Randomization and Computation (RANDOM),
pages 363378. 2013.
Full version CoRR, abs/1407.2674.

A. Beimel, K. Nissim,
and U. Stemmer.
Characterizing the Sample Complexity of Private Learners.
In Proceedings of the 4th conference on Innovations in Theoretical Computer Science (ITCS),
pages 97110, 2013.
Full version CoRR, abs/1402.2224.

A. Beimel,
S. P. Kasiviswanathan,
and K. Nissim.
Bounds on the Sample Complexity for Private Learning and Private Data Release.
In the Seventh Theory of Cryptography Conference, 2010.
To appear.
(pdf),
(ps).

A. Beimel, K. Nissim, and
E. Omri.
Distributed private data analysis:
Simultaneously solving how and what.
In
Advances in Cryptology – CRYPTO 2008,
volume 5157 of
Lecture Notes in Computer Science, pages 451–468.
SpringerVerlag,
2008.
(pdf),
(ps).
Full version:
(pdf),
(ps).
[Updated Dec. 2009.]
Secure Multiparty Computation

G. Asharov, A. Beimel, N. Makriyannis, and E. Omri.
Complete Characterization of Fairness in Secure TwoParty Computation of Boolean Functions.
In Proc. of the 12th Theory of
Cryptography Conference, volume 9014 of Lecture Notes in Computer Science, pages 199 –
228, SpringerVerlag, 2015.
Full version:
Cryptology ePrint Archive, Report 2014/1000.

A. Beimel, A. Gabizon, Y. Ishai, E. Kushilevitz, S. Meldgaard, and A. PaskinCherniavsky.
Noninteractive secure multiparty computation. In Advances in Cryptology  CRYPTO 2014,
volume 8617 of Lecture Notes in Computer Science, pages 387404, SpringerVerlag, 2014.
Full version:
Cryptology ePrint Archive, Report 2014/960.

A. Beimel, Y. Ishai, R. Kumaresan, and E. Kushilevitz. On the cryptographic complexity
of the worst functions. In Proc. of the 11th Theory of Cryptography Conference, volume 8349
of Lecture Notes in Computer Science, pages 317342, SpringerVerlag, 2014.

A. Beimel,
E. Omri, and
I. Orlov.
Secure Multiparty Computation with Partial Fairness. Submitted for Publication, 2010.
(pdf).

A. Beimel,
E. Omri, and
I. Orlov.
Protocols for multiparty coin toss with dishonest majority. In
Advances in Cryptology  CRYPTO 2010, volume 6223 of Lecture Notes in Computer
Science, pages 538  557. Springer, 2010.
(pdf).
Journal version: J. of Cryptology, 2013.
(pdf).

A. Beimel,
T. Malkin,
K. Nissim, and
E. Weinreb.
How should we solve search problems
privately? In Advances in Cryptology  CRYPTO 2007, volume 4622 of
Lecture Notes in Computer Science, pages 31  49. Springer, 2007.
(pdf).

A. Beimel,
R. Hallak, and K. Nissim.
Private Approximation of Clustering and Vertex Cover.
In the Fourth Theory of Cryptography Conference,
volume 4932 of Lecture
Notes in Computer Science, pages 338403,
2007.
(ps),
(pdf).

A. Beimel, P. Carmi,
K. Nissim, and
E. Weinreb.
Private Approximation of Search Problems.
In Proc. of 38th Annu. ACM Symp. on the Theory of Computing
(STOC), pages 119128, 2006.
(ps),
(pdf).
Journal Version: (ps),
(pdf).
[Updated Oct. 2006]

A. Beimel and T. Malkin.
A Quantitative Approach to Reductions in Secure Computation
In the first Theory of Cryptography Conference, volume 2951 of Lecture
Notes in Computer Science, pages 238257,
2004.
Full version
(ps),
(pdf).

A. Beimel, T. Malkin, and
S. Micali. The
allornothing nature of twoparty secure computation. In CRYPTO '99,
vol. 1666 of LNCS, pages 80  97, 1999. [Updated Dec. 1999]
Secure, Reliable, and Anonymous Message Transmission

A. Beimel and M. Franklin.
Edge eavesdropping games
(ps),
(pdf).
In Proc
of the 5th Conference on Security and Cryptography for Networks, 2006.
Full version:
(ps),
(pdf).

A. Beimel.
On private computation in incomplete networks
(ps),
(pdf).
In Proc. of the 12th Colloquium on Structural Information and Communication Complexity (SIROCCO),
volume 3499 of Lecture
Notes in Computer Science, pages 18–33,
2005.
Full version:
(ps),
(pdf).
[Updated July 2006.]

A. Beimel and L. Malka.
Efficient reliable
communication over partially authenticated networks.
(ps),
(pdf)).
Distributed Computing, 18(1):1–19, 2005.
In Proc. of the 22nd ACM Symp. on Principles of Distributed Computing
(PODC), pages 233–242, 2003.
(ps),
(pdf).

A. Beimel and
S. Dolev. Buses
for Anonymous Message Delivery (ps),
(pdf).
J. of Cryptology., 16(1):25–39, 2003.

A. Beimel and M. Franklin.
Reliable
communication over partially authenticated networks
(ps),
(pdf).
Theoretical Computer Science, (220)1:185210, 1999. Preliminary version in WDAG
'97, volume 1320 of LNCS, pages 245259, Springer, 1997.
Complexity Theory

A. Beimel, S. Ben Daniel,
E. Kushilevitz,
and E. Weinreb.
Choosing, Agreeing, and Eliminating in Communication Complexity.
ICALP 2010, 2010.(ps),
(pdf).
Journal version:
pdf.

A. Beimel and E. Weinreb.
Monotone Circuits for Weighted Threshold Functions.
(ps),
(pdf).
Information Processing Letters, 97(1):12–18, 2006.
In Proc. of 20th Annu. IEEE Conf. on Computational Complexity,
pages 6775, 2005.
(ps),
(pdf).

A. Beimel and
E. Weinreb.
Separating the Power of Monotone Span Programs over Different Fields
(ps),
(pdf).
SIAM Journal on Computing>, 34(5):11961215, 2005.
Preliminary version in Proc. of the 44th IEEE Symp. on Foundations of Computer Science.
(FOCS), pages 428437, 2003.
(ps),
(pdf).

A. Beimel and A.
Gal.
On arithmetic branching programs
(ps),
(pdf).
Journal of Computer Systems Sciences,
59:195220, 1999. Preliminary version in
Proc. of the 13th Annu. IEEE Conf. on Computational Complexity,
pages 6880, 1998.

A. Beimel, A. Gal,
and M.
Paterson.
Lower
bounds for monotone span programs
(ps),
(pdf).
Computational Complexity, 6(1):2945,
1997. Preliminary version in FOCS 95.
Computational Learning

A. Beimel and E. Kushilevitz.
Learning
unions of high dimensional boxes over the reals
(ps),
(pdf).
IPL,
73(56):213220, 2000.

A. Beimel, F. Geller, and E.
Kushilevitz. The query complexity of finding local minima in the lattice
(ps),
(pdf).
Information and Computation
171(1):6983, 2001. Preliminary version in
Proc. of the 11th Conf. on Computational Learning Theory (COLT),
pages 294302, 1998.

A. Beimel and E. Kushilevitz.
Learning
boxes in high dimension
(ps),
(pdf).
Algorithmica, 22(1/2):7690, 1998.
Preliminary version in EuroCOLT '97, vol. 1208 of
LNAI, pp. 315.
Springer, 1997.

A. Beimel, F. Bergadano,
N.
H. Bshouty, E. Kushilevitz,
and S. Varricchio.
Learning functions represented as multiplicity automata
(ps),
(pdf).
J. of the ACM.
47(3):506530, 2000. Preliminary version: On the applications of multiplicity
automata in learning. In
Proc. of the 37th Symp. on Foundations of Comp. Sci. (FOCS),
pages 349358, 1996.
Miscellaneous

A. Beimel, S. Dolev, and N. Singer.
RT Oblivious Erasure Correcting. IEEE/ACM Transactions on
Networking, 15(6):1321–1332, 2007.
(ps),
(pdf )

A. Beimel, B. BenMoshe, Y. BenShimol, P. Carmi, E. Chai,
I. Kitroser, and Eran Omri. Matrix Columns Allocation Problems.
Theoretical Computed Science, 410(21–23):2174–2183, 2009.
(ps),
(pdf).

E. Karpas, E. Shimony, and A. Beimel.
Approximate Belief Updating in Max2Connected Bayes Networks is NPHard.
Artificial Intelligence, 173(12–13):1150–1153, 2009.
(ps),
(pdf).