Amos Beimel's Publications (updated August 2013)

Copyright and Accuracy

The Copyright for the papers below are with the respective publishers. On-line versions are provided for research purposes only. The versions provided may not be identical to the published ones and some include more updated reports.

Cryptography

Private Information Retrieval

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 258-268, 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 $O(n^{1/(2k-1)})$ Barrier for Information-Theoretic Private Information Retrieval.(ps), (pdf). In Proc. of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS), pages 261-270, 2002.

pdf

A. Beimel and Y. Stahl. Robust Information-Theoretic 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 information-theoretic private information retrieval. (ps), (pdf). JCSS, 71(2):247-281, 2005. This paper includes the results of A. Beimel and Y. Ishai. Information-Theoretic Private Information Retrieval: A Unified Construction. (ps), (pdf). ICALP 2001, volume 2076 of LNCS, pages 89-98, 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):125-151, 2004. Conference version: CRYPTO 2000, vol. 1880 of LNCS, pages 56-74. Springer, 2000.
A. Beimel, Y. Ishai, T. Malkin, and E. Kushilevitz. One-way functions are essential for single-server private information retrieval. In Proc. of the 31st Annu. ACM Symp. on the Theory of Computing (STOC), pages 89-98, 1999.

Secret-Sharing and Key Distribution

A. Beimel, A. Ben-Efraim, C. Padró, and Ilya Tyomkin. Multi-linear secret sharing schemes. In Proc. of the 11th Theory of Cryptography Conference, volume 8349 of Lecture Notes in Computer Science, pages 394--418, Springer-Verlag, 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, Springer-Verlag, 2012.
A. Beimel. Secret-Sharing Schemes: A Survey (pdf), 2011
A. Beimel and I. Orlov. Secret Sharing and Non-Shannon Information Inequalities. In Proc. of the 6th Theory of Cryptography Conference, volume 5444 of Lecture Notes in Computer Science, pages 539–557, Springer-Verlag, 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, Springer-Verlag, 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. Weakly-Private Secret Sharing. In the Fourth Theory of Cryptography Conference, 2007. (ps), (pdf).
A. Beimel and N. Livne. On Matroids and Non-ideal Secret Sharing. In Proc. of the third Theory of Cryptography Conference, volume 3876 of Lecture Notes in Computer Science, pages 482-501, 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 secret-sharing (ps), (pdf). SIAM Journal on Discrete Mathematics, 19(1):258-280, 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):324-345, 2000.
A. Beimel and B. Chor. Secret sharing with public reconstruction. IEEE Trans. on Info. Theory, 44(5):1887-1896, 1998. Extended abstract in CRYPTO '95.
A. Beimel and B. Chor. Communication in key distribution schemes. IEEE Trans. on Info. Theory, 42(1):19-28, 1996. Extended abstract in CRYPTO '93, vol. 773 of LNCS, pp. 444-455. 1994.
A. Beimel and B. Chor. Universally ideal secret sharing schemes. IEEE Trans. on Info. Theory, 40(3):786-794, 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 ACM-SIAM 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 363-378. 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 97-110, 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. Springer-Verlag, 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 Two-Party Computation of Boolean Functions. In Proc. of the 12th Theory of Cryptography Conference, volume 9014 of Lecture Notes in Computer Science, pages 199 – 228, Springer-Verlag, 2015. Full version: Cryptology ePrint Archive, Report 2014/1000.
A. Beimel, A. Gabizon, Y. Ishai, E. Kushilevitz, S. Meldgaard, and A. Paskin-Cherniavsky. Non-interactive secure multiparty computation. In Advances in Cryptology - CRYPTO 2014, volume 8617 of Lecture Notes in Computer Science, pages 387-404, Springer-Verlag, 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 317-342, Springer-Verlag, 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 338-403, 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 119-128, 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 238-257, 2004. Full version (ps), (pdf).
A. Beimel, T. Malkin, and S. Micali. The all-or-nothing nature of two-party 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:185-210, 1999. Preliminary version in WDAG '97, volume 1320 of LNCS, pages 245-259, 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):1196-1215, 2005. Preliminary version in Proc. of the 44th IEEE Symp. on Foundations of Computer Science. (FOCS), pages 428-437, 2003. (ps), (pdf).
A. Beimel and A. Gal. On arithmetic branching programs (ps), (pdf). Journal of Computer Systems Sciences, 59:195-220, 1999. Preliminary version in Proc. of the 13th Annu. IEEE Conf. on Computational Complexity, pages 68-80, 1998.
A. Beimel, A. Gal, and M. Paterson. Lower bounds for monotone span programs (ps), (pdf). Computational Complexity, 6(1):29-45, 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(5-6):213-220, 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):69-83, 2001. Preliminary version in Proc. of the 11th Conf. on Computational Learning Theory (COLT), pages 294-302, 1998.
A. Beimel and E. Kushilevitz. Learning boxes in high dimension (ps), (pdf). Algorithmica, 22(1/2):76-90, 1998. Preliminary version in EuroCOLT '97, vol. 1208 of LNAI, pp. 3-15. 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):506-530, 2000. Preliminary version: On the applications of multiplicity automata in learning. In Proc. of the 37th Symp. on Foundations of Comp. Sci. (FOCS), pages 349-358, 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. Ben-Moshe, Y. Ben-Shimol, 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 Max-2-Connected Bayes Networks is NP-Hard. Artificial Intelligence, 173(12–13):1150–1153, 2009. (ps), (pdf).