# Prof. Amos Beimel

 Associate professorHead of department As a head of the department Phone : 08-6477845 Room : 101B Office hours:by email appointment

## Contacts

 Email: Homepage: Office: 115 in 37 building Phone number: 08-6428052 Fax number: 08-6477650 Box number: 35 Office hours: Sun 14:00-16:00

## Teaching

 Spring 2004 20215351 Cryptography Fall 2004-2005 20221111 Complexity Fall 2004-2005 20215351 Cryptography Spring 2005 20221151 Computational Complexity 2 Spring 2007 20215351 Cryptography Spring 2007 20225071 Randomized algorithms and probabilistic methods Fall 2007-2008 20221111 Complexity Fall 2007-2008 20215351 Cryptography Spring 2008 20212041 Design of Algorithms Spring 2008 20225001 Privacy and Secure Computation Fall 2008-2009 20215351 Cryptography Fall 2008-2009 20225291 Advanced Topics in Complexity Fall 2008-2009 20221111 Complexity Spring 2009 20212041 Design of Algorithms Fall 2009-2010 20215351 Cryptography Fall 2009-2010 20221111 Complexity Spring 2010 20212041 Design of Algorithms Fall 2010-2011 20221111 Complexity Spring 2011 20212041 Design of Algorithms Spring 2011 20221151 Computational Complexity 2 Fall 2011-2012 20221111 Complexity Fall 2011-2012 20225731 Error Correcting Codes and their Applications in Computer Science Spring 2012 20212041 Design of Algorithms Fall 2012-2013 20215351 Cryptography Fall 2012-2013 20225821 Cryptography 2 Fall 2012-2013 20221111 Complexity

## Research groups

 Complexity Cryptography and security

## Education

 1989  -  B.A  Technion, computer science 1992  -  M.Sc  technion, computer scienceAdvisor: Benny Chor 1996  -  D.Sc  Technion, Computer ScienceAdvisor: Benny Chor

## Selected publications all BibTex

Articles BibTeXA. Beimel and S. Dolev and N. Singer. RT oblivious erasure correcting. IEEE/ACM Transactions on Networking, 2007. BibTeXA. Beimel and Y. Stahl. Robust information-theoretic private information retrieval. J. of Cryptology, 2007. BibTeXA. Beimel. On private computation in incomplete networks. Distributed Computing, 19(3):237--252, 2007. BibTeXA. Beimel and E. Weinreb. Monotone circuits for monotone weighted threshold functions. Information Processing Letters, 97(1):12-18, 2006. BibTeXA. Beimel and L. Malka. Efficient Reliable Communication over Partially Authenticated Networks. Distributed Computing, 18(1):1-19, 2005. BibTeXA. Beimel and Y. Ishai. On the Power of Nonlinear Secret-Sharing. SIAM J. of Discrete Mathematics, 19(1):258-280, 2005. BibTeXA. Beimel and E. Weinreb. Separating the Power of Monotone Span Programs over Different Fields. SIAM J. on Computing, 34(5):1196-1215, 2005. BibTeXA. Beimel Y. Ishai and E. Kushilevitz. General constructions for information-theoretic private information retrieval. Journal of Computer Systems Sciences, 71(2):247-281, 2005. BibTeXA. Beimel Y. Ishai and T. Malkin. Reducing the Servers Computation in Private Information Retrieval: PIR with Preprocessing. J. of Cryptology, 17(2):125-151, 2004. BibTeXA. Beimel and S. Dolev. Buses for anonymous message delivery. J. of Cryptology, 16(1):25-39, 2003. BibTeXA. Beimel, F. Geller, and E. Kushilevitz. The query complexity of finding local minima in the lattice. Information and Computation, 171(1):69-83, 2001. BibTeXA. Beimel F. Bergadano N. H. Bshouty E. Kushilevitz and S. Varricchio. Learning Functions Represented as Multiplicity Automata. J. of the ACM, 47(3):506-530, 2000. BibTeXA. Beimel M. Burmester Y. Desmedt and E. Kushilevitz. Computing Functions of a Shared Secret. SIAM J. on Discrete Mathematics, 13(3):324-345, 2000. BibTeXA. Beimel and E. Kushilevitz. Learning unions of high-dimensional boxes over the reals. Information Processing Letters, 73(5-6):213-220, 2000. BibTeXA. Beimel and M. Franklin. Reliable Communication over Partially Authenticated Networks. Theoretical Computer Science, 220:185-210, 1999. BibTeXA. Beimel and A. Gál. On Arithmetic Branching Programs. JCSS, 59:195-220, 1999. BibTeXA. Beimel and B. Chor. Secret sharing with public reconstruction. IEEE Transactions on Information Theory, 44(5):1887-1896, 1998. BibTeXA. Beimel and E. Kushilevitz. Learning Boxes in High Dimension. Algorithmica, 22(1/2):76-90, 1998. BibTeXA. Beimel A. Gál and M. Paterson. Lower Bounds for Monotone Span Programs. Computational Complexity, 6(1):29-45, 1997. BibTeXA. Beimel and B. Chor. Communication in Key Distribution Schemes. IEEE Trans. on Information Theory, 42(1):19-28, 1996. BibTeXBeimel, A. and Chor, B.. Universally Ideal Secret Sharing Schemes. IEEE Trans. on Information Theory, 40(3):786-794, 1994. BibTeXA. Beimel and R. Hallak and K. Nissim. Private approximation of clustering and vertex cover. In Proc. of the fourth Theory of Cryptography Conference, vol. 4392 of Lecture Notes in Computer Science, 383--403, 2007. BibTeXA. Beimel and T. Malkin and K. Nissim and E. Weinreb. How should we solve search problems privately?. In Advances in Cryptology - CRYPTO 2007, vol. 4622 of Lecture Notes in Computer Science, 31--49, 2007. BibTeXA. Beimel and M. Franklin. Weakly-private secret sharing schemes.. In Proc. of the fourth Theory of Cryptography Conference, vol. 4392 of Lecture Notes in Computer Science}, 253--272, 2007. BibTeXA. Beimel and P. Carmi and K. Nissim and E. Weinreb. Private approximation of search problems. In Proc. of the 38th Annu. ACM Symp. on the Theory of Computing (STOC), pages 119-128, 2006. BibTeXA. Beimel and M. Franklin. Edge Eavesdropping Games. In Proc. of Fifth Conference on Security and Cryptography for Networks, R. De Prisco and M. Yung editor, vol. 4116 of Lecture Notes in Computer Science, 1-17, Springer-Verlag, 2006. To appear. BibTeXA. Beimel and N. Livne. On matroids and non-ideal secret sharing. In Proc. of the third Theory of Cryptography Conference, vol. 3876 of Lecture Notes in Computer Science, 482-501, 2006. BibTeXA. Beimel. On Private Computation in Incomplete Networks. In Proc. of the 12th Colloquium on Structural Information and Communication Complexity (SIROCCO), A. Pelc M. Raynal editor, vol. 3499 of Lecture Notes in Computer Science, 18-33, Springer-Verlag, 2005. BibTeXA. Beimel and E. Weinreb. Monotone Circuits for Weighted Threshold Functions. In Proc. of 20th Annu. IEEE Conf. on Computational Complexity, pages 67-75, 2005. BibTeXA. Beimel T. Tassa and E. Weinreb. Characterizing Ideal Weighted Threshold Secret Sharing. In The Second Theory of Cryptography Conference - TCC 2005, J. Kilian editor, vol. 3378 of Lecture Notes in Computer Science, 600-619, Springer-Verlag, 2005. BibTeXA. Beimel, S. Dolev, and N. Singer. RT oblivious erasure correcting. In 2004 IEEE Information Theory Workshop, 2004. Brief Announcement also published in Proc. of the 23nd ACM Symp. on Principles of Distributed Computing (PODC). BibTeXA. Beimel and T. Malkin. A quantitative Approach to Reductions in Secure Computation. In The First Theory of Cryptography Conference - TCC 2004, M. Naor editor, vol. 2951 of Lecture Notes in Computer Science, 238-257, Spring-er-Ver-lag, 2004. BibTeXA. Beimel and L. Malka. Efficient Reliable Communication over Partially Authenticated Networks. In Proc. of the 22nd ACM symp. on Principles of Distributed Computing, pages 233-242, 2003. BibTeXA. Beimel and E. Weinreb. Separating the Power of Monotone Span Programs over Different Fields. In Proc. of the 44th IEEE Symp. on Foundations of Computer Science, pages 428-437, 2003. BibTeXA. Beimel and Y. Stahl. Robust information-theoretic private information retrieval. In 3rd Conf. on Security in Communication Networks, S. Cimato C. Galdi G. Persiano editor, vol. 2576 of Lecture Notes in Computer Science, 326-341, Springer-Verlag, 2002. BibTeXA. Beimel Y. Ishai E. Kushilevitz and J. F. Raymond. Breaking the $O(n^\frac12k-1)$ Barrier for Information-Theoretic Private Information Retrieval. In Proc. of the 43rd IEEE Symp. on Foundations of Computer Science, pages 261-270, 2002. BibTeXA. Beimel and Y. Ishai. On the Power of Nonlinear Secret-Sharing. In Proc. of the 16th IEEE Conf. on Computational Complexity, pages 188 - 202, 2001. BibTeXA. Beimel and Y. Ishai. Information-Theoretic Private Information Retrieval: A Unified Construction. In Proc. of the 28th International Colloquium on Automata, Languages and Programming, P. G. Spirakis J. van Leeuven editor, vol. 2076 of Lecture Notes in Computer Science, 912-926, Springer, 2001. BibTeXA. Beimel and S. Dolev. Buses for anonymous message delivery. In Proc. of the 2nd International Conference on FUN with Algorithms, pages 1 - 13, 2001. BibTeXA. Beimel Y. Ishai and T. Malkin. Reducing the Servers Computation in Private Information Retrieval: PIR with Preprocessing. In Advances in Cryptology - CRYPTO 2000, M. Bellare editor, vol. 1880 of Lecture Notes in Computer Science, 56-74, Springer-Verlag, 2000. BibTeXA. Beimel Y. Ishai E. Kushilevitz and T. Malkin. One-way Functions are Essential for Single-Server Private Information Retrieval. In Proc. of the 31st ACM Symp. on the Theory of Computing, pages 89-98, 1999. BibTeXA. Beimel T. Malkin and S. Micali. The All-or-Nothing Nature of Two-Party Secure Computation. In Advances in Cryptology - CRYPTO 99, Michael Wiener editor, vol. 1666 of Lecture Notes in Computer Science, 80-97, Spring-er-Ver-lag, 1999. BibTeXA. Beimel, F. Geller, and E. Kushilevitz. The query complexity of finding local minima in the lattice. In Proc. of 11th Annu. ACM Conf. on Computational Learning Theory (COLT), pages 294-302, 1998. BibTeXA. Beimel and A. Gál. On Arithmetic Branching Programs. In Proc. of the 13th IEEE Conf. on Computational Complexity, pages 68-80, 1998. BibTeXA. Beimel and M. Franklin. Reliable Communication over Partially Authenticated Networks. In WDAG 97, M. Mavronicolas P. Tsigas editor, vol. 1320 of "Lecture Notes in Computer Science", 245-259, Springer-Verlag, 1997. BibTeXA. Beimel and E. Kushilevitz. Learning Boxes in High Dimension. In 3rd European Conf. on Computational Learning Theory (EuroCOLT 97), S. Ben-David editor, vol. 1208 of Lecture Notes in Artificial Intelligence, 3-15, Springer-Verlag, 1997. BibTeXA. Beimel F. Bergadano N. H. Bshouty E. Kushilevitz and S. Varricchio. On the Applications of Multiplicity Automata in Learning. In Proc. of the 37th IEEE Symp. on Foundations of Computer Science, pages 349-358, 1996. BibTeXA. Beimel A. Gál and M. Paterson. Lower Bounds for Monotone Span Programs. In Proc. of the 36th IEEE Symp. on Foundations of Computer Science, pages 674-681, 1995. BibTeXBeimel, A. and Chor, B.. Secret Sharing with Public Reconstruction. In Advances in Cryptology - CRYPTO 95, D. Coppersmith editor, vol. 963 of Lecture Notes in Computer Science, 353-366, Springer-Verlag, 1995. BibTeXA. Beimel and B. Chor. Interaction in Key Distribution Schemes. In Advances in Cryptology - CRYPTO 93, Stinson, D. R. editor, vol. 773 of Lecture Notes in Computer Science, 444-455, Springer-Verlag, 1994. BibTeXBeimel, A. and Chor, B.. Universally Ideal Secret Sharing Schemes. In Advances in Cryptology - CRYPTO 92, Brickell, E. F. editor, vol. 740 of Lecture Notes in Computer Science, 183-195, Springer-Verlag, 1993.