My Publications

Publications in Cryptography

[GHKRRW08] Strongly-Resilient and Non-Interactive Hierarchical Key-Agreement in MANETs, Rosario Gennaro, Shai Halevi, Hugo Krawczyk, Tal Rabin, Steffen Reidt, and Stephen D. Wolthusen. Proceedings of ESORICS 2008, to appear.

[BHHO08] Circular-Secure Encryption from Decision Diffie-Hellman, Dan Boneh, Shai Halevi, Mike Hamburg, and Rafail Ostrovsky. In Advances in Cryptography - CRYPTO'08, Springer, 2008, to appear.

[GHKR08] Threshold RSA for Dynamic and Ad-Hoc Groups, Rosario Gennaro, Shai Halevi, Tal Rabin, and Hugo Krawczyk. In Advances in Cryptography - EUROCRYPT'08, LNCS vol. 4965, pages 88-107, Springer, 2008.

[HR08] Degradation and Amplification of Computational Hardness, Shai Halevi and Tal Rabin. The 5th Theory of Cryptography Conference - TCC'08. LNCS vol. 4948, pages 623-640. Springer, 2008.

[HMR08]On Seed-Incompressible Functions , Shai Halevi, Steven Myers, and Charles Rackoff. The 5th Theory of Cryptography Conference - TCC'08. LNCS vol. 4948, pages 19-36. Springer, 2008.

[CCG+08] Cryptanalysis of ISO/IEC 9796-1, D. Coppersmith, J.S. Coron, F. Grieu, S. Halevi, C. Jutla, D. Naccache, and J.P. Stern. Journal of Cryptology, 21(1), Pages 27-51. Springer, 2008.

[HK07] Security under Key-Dependent Inputs, Shai Halevi and Hugo Krawczyk. 14th ACM-CCS, pages 466-475, 2008. ACM.

[H07] Invertible Universal Hashing and the TET Encryption Mode, S. Halevi, Advances in Cryptology - CRYPTO '07. LNCS vol. 4622, pages 412-429. Springer, 2007.

[CHK07] A forward-secure public-key encryption scheme, Ran Canetti, Shai Halevi and Jonathan Katz. Journal of Cryptology, 20(3), Pages 265-294. Springer, 2007. (Earlier version in EUROCRYPT'03, pages 255-271.)

[BCHK06] Chosen-ciphertext security from identity-based encryption, D. Boneh, R. Canetti, S. Halevi and J. Katz. SICOMP 36(5), Pages 915-942, 2006. (Earlier version in EUROCRYPT'04, pages 207-222.)

[HK06] Strengthening Digital Signatures via Randomized Hashing, Shai Halevi and Hugo Krawczyk. Advances in Cryptology - CRYPTO '06. LNCS vol. 4117, pages 41-59. Springer, 2006.

[CHS06] Mitigating Dictionary Attacks on Password-Protected Local Storage, Ran Canetti, Shai Halevi and Michael Steiner. Advances in Cryptology - CRYPTO '06. LNCS vol. 4117, pages 160-179. Springer, 2006.

[BBH06] Chosen Ciphertext Secure Public Key Threshold Encryption Without Random Oracles , Dan Boneh, Xavier Boyen, and Shai Halevi, RSA-CT 2006, LNCS vol. 3860, pages 226-243. Springer, 2006.

[BH05] An architecture for robust pseudo-random generation and applications to /dev/random, Boaz Barak and Shai Halevi. 12th ACM-CCS, pages 203-212, 2005. ACM.

[CHK+05] Universally composable password-based key exchange, R. Canetti, S. Halevi, J. Katz, Y. Lindell and P. MacKenzie. Advances in Cryptology - EUROCRYPT '05. LNCS vol. 3494, pages 404-421. Springer, 2005.

[CHS05] Hardness amplification of computational riddles, R. Canetti, S. Halevi and M. Steiner. The 2nd Theory of Cryptography Conference - TCC'05. LNCS vol. 3378, pages 17-33. Springer, 2005.

[CHK05] Adaptively secure non-interactive public-key encryption, R. Canetti, S. Halevi, and J. Katz. The 2nd Theory of Cryptography Conference - TCC'05. LNCS vol. 3378, pages 150-168. Springer, 2005.

[H04] EME*: extending EME to handle arbitrary-length messages with associated data, S. Halevi. INDOCRYPT 2004, LNCS vol. 3348, pages 315-327. Springer, 2004.

[CGH04a] The random oracle methodology, rivisited, R. Canetti, O. Goldreich and S. Halevi. JACM, vol. 51, no. 4, pages 557-594. July 2004, ACM. (Preliminiary version appeared in STOC '98, Pages 209-218.)

[HR04] A parallelizable enciphering mode, Shai Halevi and Phil Rogaway. The RSA conference - Cryptographer's track, RSA-CT '04. LNCS vol. 2964, pages 292-304. Springer, 2004.

[CGH04b] On the random-oracle methodology as applied to length-restricted signature schemes, Ran Canetti, Oded Goldreich and Shai Halevi. The 1st Theory of Cryptography Conference - TCC '04. LNCS vol. 2951, pages 40-57. Springer, 2004.

[HR03] A tweakable enciphering mode, Shai Halevi and Phil Rogaway. Advances in Cryptology - CRYPTO '03. LNCS vol. 2729, pages 482-499. Springer, 2003.

[SECOBS] A Two Layered Approach for Securing an object store network, Alain Azagury, Ran Canetti, Michael Factor, Shai Halevi, Ealan Henis, Dalit Naor, Noam Rinetzky, Ohad Rodeh, and Julian Satran. 1st International IEEE Security in Storage Workshop (SISW 2002)

[CHJ02] Cryptanalysis of stream ciphers with linear masking, Don Coppersmith, Shai Halevi and Charanjit Jutla. Advances in Cryptology - CRYPTO '02. LNCS vol. 2442, Pages 515-532. Springer, 2002.

[HCJ02] Scream: a software-efficient stream cipher, Shai Halevi, Don Coppersmith and Charanjit Jutla. FSE '02, LNCS vol. 2365, Pages 195-209. Springer, 2002.

[BHH01] The modular inversion hidden number problem, Dan Boneh, Shai Halevi, and Nick Howgrave-Graham. Advances in Cryptology - ASIACRYPT '01, LNCS vol. 2248, Pages 36-51. Springer, 2001.

[DHR00] A cryptographic solution to a game theoretic problem, Yevgeniy Dodis, Shai Halevi, and Tal Rabin. Advances in Cryptology - CRYPTO 2000. LNCS vol. 1880, Pages 112-130, Springer, 2000.

[CGH00] Computing inverses over a shared secret modulus, Dario Catalano, Rosario Gennaro, and Shai Halevi. Advances in Cryptology - EUROCRYPT 2000. LNCS vol. 1807, Pages 190-206, Springer, 2000.

[CDHKS00] Exposure-resilient functions and all-or-nothing transforms, R. Canetti, Y. Dodis, S. Halevi, E. Kushilevitz, and A. Sahai. Advances in Cryptology - EUROCRYPT 2000. LNCS vol. 1807, Pages 453-469, Springer, 2000.

[CHH00] Maintaining authenticated communication in the presence of break-ins, R. Canetti, S. Halevi,and A. Herzberg. Journal of Cryptology, 13(1), Pages 61-105. Springer, 2000. (Preliminiary version appeared in PODC'97, Pages 15-24, ACM.)

[HK99] Public-key cryptography and password protocols, S. Halevi and H. Krawczyk. In ACM Transactions on Information and System Security (TISSEC), Vol 2, No. 3, Pages 230-268, August 1999. ACM. (Preliminiary version appeared in the 5th ACM-CCS, Pages 122-131. 1998. ACM.)

[BHKKR99] UMAC:Fast and secure message authentication, J. Black, S. Halevi, H. Krawczyk, T.Krovetz and P. Rogaway. In Advances in Cryptology - CRYPTO '99, pages 216-233, Springer, LNCS vol. 1666, 1999.

[GHR99] Secure hash-and-sign signatures without the random oracle, R. Gennaro, S. Halevi and T. Rabin. In Advances in Cryptography - EUROCRYPT '99, pages 123-139, Springer, LNCS vol. 1592. 1999.

[H99] Efficient Commitment Schemes with Bounded Sender and Unbounded Receiver, S. Halevi. In Journal of Cryptology, vol. 12, no. 2, pages 77-89. Springer, 1999. (Preliminiary version appeared in Advances in CRYPTO '95, Pages 84-96, Springer.)

[BHSV98] Many-to-one Trapdoor Functions and their Relation to Public-key Cryptosystems, M. Bellare, S. Halevi, A. Sahai and S. Vadhan. In Advances in Cryptography - CRYPTO '98, pages 283-298, Springer, LNCS vol. 1462. 1998.

[GGH97a] Public-Key Cryptosystems from Lattice Reduction Problems, O. Goldreich, S. Goldwasser and S. Halevi. In Advances in Cryptography - CRYPTO '97, pages 112-131, 1997. Springer, LNCS vol. 1294.

[GGH97b] Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem, O. Goldreich, S. Goldwasser and S. Halevi. In Advances in Cryptography - CRYPTO '97, pages 105-111, 1997. Springer, LNCS vol.1294.

[HK97] MMH: Message Authentication in Software in the Gbit/second Rates, S. Halevi and H. Krawczyk. In proceedings of the 4th Workshop on Fast Software Encryption, pages 172-189. Springer, LNCS vol. 1267, 1997.

[HM96] Practical and Provably-Secure Commitment Schemes from Collision-Free Hashing, S. Halevi and S. Micali. In Advances in Cryptography - CRYPTO '96, LNCS vol. 1109, pages 201-215, Springer. 1996.

Publications in other areas

[GHJRW08] Rationality and Traffic Attraction: Incentives for Honest Path Announcements in BGP, Sharon Goldberg, Shai Halevi, Aaron D. Jaggard, Vijay Ramachandran, and Rebecca N. Wright, SIGCOMM 2008, to appear.

[DH01] Incremental codes, Yevgeniy Dodis, and Shai Halevi. APPROX '01, LNCS 2129, pages 75-89. Springer, 2001.

[HKKN01] Private approximation of NP-hard functions, Shai Halevi, Robert Krauthgamer, Eyal Kushilevitz, and Kobbi Nissim. Proceedings of the 33rd annual symposium on Theory of computing - STOC '01, pages 550-559. ACM, 2001.

[BHHN00] Clock Synchronization with Faults and Recoveries, Boaz Barak, Shai Halevi, Amir Herzberg, and Dalit Naor. Proceedings of the 19th annual ACM symposium on Principles of distributed computing - PODC 2000, pages 133-142. ACM, 2000.

[GHLP99] Computing from partial solutions, A. Gal, S. Halevi, E. Petrank and D. Lipton. In Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999.

[BHS98] Potential Function Analysis of Greedy Hot-Potato Routing, A. Ben-Dor, S. Halevi and A. Schuster. Theory Comput. Systems, vol. 31, pages 41-61 1998, Springer. (Preliminary version appeared in PODC '94, Pages 225-234. ACM.)

[BH93] 0-1 Permanent is #P-Complete, a Simpler Proof, Amir Ben-Dor and Shai Halevi. In proceedings of the 2'nd Israeli Symposium on Theory and Computing Systems, pages 108-117, 1993. IEEE.

Manuscripts

[GH08] Rational ASes and Traffic Attraction: Incentives for honestly announcing paths in BGP, Sharon Goldberg and Shai Halevi. TR-813-08, Department of Computer Science, Princeton University, February 2008.

[H05b] A plausible approach to computer-aided cryptographic proofs, Shai Halevi. 2005.

[HKN05] Enforcing Confinement in Distributed Storage and a Cryptographic Model for Access Control, Shai Halevi, Paul A. Karger, and Dalit Naor. 2005.

[H05a] A sufficient condition for key-privacy, Shai Halevi. 2005.

[H01] An observation regarding Jutla's modes of operation, Shai Halevi, 2001.

[MARS] MARS - a candidate cipher for AES, C. Burwick, D. Coppersmith, E. D'Avignon, R. Gennaro, S. Halevi, C. Jutla, S.M. Matyas Jr., L. O'Connor, M. Peyravian, D. Safford and N. Zunic. Presented in the 1st AES conference, 1998, NIST.

[HM98] A Stronger Notion of Proofs of Knowledge. S. Halevi and S. Micali, 1998.

[GGH96] Collision-Free Hashing from Lattice Problems, O. Goldreich, S. Goldwasser and S. Halevi, 1996.

[HP95] Storing Classified Files, S. Halevi and E. Petrank. 1995.

[BH91] On the Provability of P vs. NP, S. Ben-David and S. Halevi. TR #699, November 1991, Dept. of Computer Science, Technion, Israel.