• 
  

  2011

• Secure Efficient Multiparty Computing of Multivariate Polynomials and Applications
  Dana Dachman-Soled and Tal Malkin and Mariana Raykova and Moti Yung
  ACNS 2011, to appear.
• Efficient Circuit-Size Independent Public Key Encryption with KDM Security
  Tal Malkin and Isamu Teranishi and Moti Yung
  Eurocrypt 2011, to appear.
• On the Black-Box Complexity of Optimally-Fair Coin Tossing
  Dana Dachman-Soled and Yehuda Lindell and Mohammad Mahmoody and Tal Malkin
  TCC, 2011, to appear.
• Signatures Resilient to Continual Leakage on Memory and Computation
  Yevgeniy Vahlis and Tal Malkin and Isamu Teranishi and Moti Yung
  TCC 2011, to appear.[eprint]
• Signatures Resilient to Continual Leakage on Memory and Computation
  Tal Malkin and Isamu Teranishi and Yevgeniy Vahlis and Moti Yung
  TCC 2011, to appear.
• Amortized Sublinear Secure Multi Party Computation
  Dov Gordon and Jonathan Katz and Vladimir Kolesnikov and Tal Malkin and Mariana Raykova and Yevgeniy Vahlis
  Workshop on Cryptography and Security in the Clouds, 2011.
• Key Dependent Message Security: Recent Results and Applications
  Tal Malkin and Isamu Teranishi and Moti Yung
  CODASPY 2011.

  2010

• A Group Signature Scheme From Lattice Assumptions
  Dov Gordon and Jonathan Katz and Vinod Vaikuntanathan
  Asiacrypt 2010.
• How Should We Solve Search Problems Privately?
  Amos Beimel and Tal Malkin and Kobbi Nissim and Enav Weinreb
  Journal of Cryptology, 23(2), 2010. Preliminary version appeared in CRYPTO 2007.
• BiTR: Built-in Tamper Resistance
  Seung Geol Choi and Aggelos Kiayias and Tal Malkin
  Eprint 2010/503.
• Hard Instances for Satisfiability and Quasi-one-way Functions
  Andrej Bogdanov and Kunal Talwar and Andrew Wan
  ICS, pp. 290-300, Tsinghua University Press, 2010.

  2009

• Improved Non-committing Encryption with Applications to Adaptively Secure Protocols
  Seung Geol Choi and Dana Dachman-Soled and Tal Malkin and Hoeteck Wee
  ASIACRYPT, Lecture Notes in Computer Science, Vol. 5912, pp. 287-302, Springer, 2009.
• Secure Multi-party Computation Minimizing Online Rounds
  Seung Geol Choi and Ariel Elbaz and Tal Malkin and Moti Yung
  ASIACRYPT, Lecture Notes in Computer Science, Vol. 5912, pp. 268-286, Springer, 2009.
• Secure Anonymous Database Search
  Mariana Raykova and Binh Vo and Steven Bellovin and Tal Malkin
  ACM CCSW, 2009.
• The Kurosawa-Desmedt key encapsulation is not chosen-ciphertext secure
  Seung Geol Choi and Javier Herranz and Dennis Hofheinz and Jung Yeon Hwang and Eike Kiltz and Dong Hoon Lee and Moti Yung.
  Inf. Process. Lett. 109(16), 2009.
• The Zodiac Policy Subsystem: A Policy-Based Management System for a High-Security MANET
  Yuu-Heng Cheng and Mariana Raykova and Alexander Poylisher and Scott Alexander and Martin Eiger and Steven M. Bellovin
  POLICY, pp. 174-177, IEEE Computer Society, 2009.
• Oblivious Image Matching
  Shai Avidan and Ariel Elbaz and Tal Malkin Ryan Moriarty
  Invited book chapter to "Protecting Privacy in Video Surveillance", Andrew Senior (editor)
  Springer, 2009, ISBN: 978-1-84882-300-6 2009.
• Efficient Robust Private Set Intersection
  Dana Dachman-Soled and Tal Malkin and Mariana Raykova and Moti Yung
  ACNS, Lecture Notes in Computer Science, Vol. 5536, pp. 125-142, 2009.
• A Unified Framework for the Analysis of Side-Channel Key Recovery Attacks
  François-Xavier Standaert and Tal Malkin and Moti Yung
  EUROCRYPT, Lecture Notes in Computer Science, Vol. 5479, pp. 443-461, Springer, 2009.
• Simple, Black-Box Constructions of Adaptively Secure Protocols
  Seung Geol Choi and Dana Dachman-Soled and Tal Malkin and Hoeteck Wee
  TCC, Lecture Notes in Computer Science, Vol. 5444, pp. 387-402, Springer, 2009.
• Optimal Cryptographic Hardness of Learning Monotone Functions
  Dana Dachman-Soled and Homin K. Lee and T. Malkin and Rocco A. Servedio and Andrew Wan and Hoeteck Wee
  Theory of Computing 5(1), pp. 257-282, 2009
• Anonymity in Wireless Broadcast Networks
  Matt Blaze and John Ioannidis and Angelos D. Keromytis and Tal Malkin and Aviel D. Rubin
  International Journal of Network Security, 8(1), pp. 37-51, 2009.
• Private Multiparty Sampling and Approximation of Vector Combinations
  Yuval Ishai and Tal Malkin and Martin J. Strauss and Rebecca N. Wright
  Journal of Theoretical Computer Science, pages 1730-1745, 2009. Preliminary version appeared in ICALP 2007.

  2008

• Privacy Preserving Pattern Classification
  Shai Avidan and Ariel Elbaz and Tal Malkin
  ICIP, pages 1684-1687, 2008.
• Does Physical Security of Cryptographic Devices Need a Formal Study?
  François-Xavier Standaert and Tal G. Malkin and Moti Yung
  ICITCS, pages 70-70 2008. Invited talk.
• What Can We Learn Privately?
  Shiva P. Kasiviswanathan and Homin K. Lee and Kobbi Nissim and Sofya Raskhodnikova and Adam Smith
  FOCS, pages 531-540, 2008.
• Improved Separations between Nondeterministic and Randomized Multiparty Communication
  Matei David and Toniann Pitassi and Emanuele Viola
  APPROX-RANDOM, pages 371-384, 2008.
• The Sum of d Small-Bias Generators Fools Polynomials of Degree d
  Emanuele Viola
  IEEE Conference on Computational Complexity, pages 124-127, 2008.
• Hardness amplification proofs require majority
  Ronen Shaltiel and Emanuele Viola
  STOC, pages 589-598, 2008.
• PAR: Payment for Anonymous Routing
  Elli Androulaki and Mariana Raykova and Shreyas Srivatsan and Angelos Stavrou and Steven M. Bellovin
  Privacy Enhancing Technologies, pages 219-236, 2008.
• Optimal Cryptographic Hardness of Learning Monotone Functions
  Dana Dachman-Soled and Homin K. Lee and T. Malkin and Rocco A. Servedio and Andrew Wan and Hoeteck Wee
  ICALP (1), pages 36-47, 2008.
• Reputation Systems for Anonymous Networks
  Elli Androulaki and Seung Geol Choi and Steven Bellovin and Tal Malkin
  Privacy Enhancing Technologies, pages 202-218, 2008.
• Black-Box Construction of a Non-malleable Encryption Scheme from Any Semantically Secure One
  Seung Geol Choi and Dana Dachman-Soled and Tal Malkin and Hoeteck Wee
  TCC, pages 427-444, 2008.
• A Block Cipher Based Pseudo Random Number Generator Secure Against Side-Channel Key Recovery
  Christophe Petit and François-Xavier Standaert and Olivier Pereira and Tal Malkin and Moti Yung
  ASIACCS, pages 56-65, ACM, 2008.
• Fair Traceable Multi-Group Signatures
  Vicente Benjumea and Seung Geol Choi and Javier Lopez and Moti Yung
  Financial Cryptography, pages 231-246, 2008.

  2007

• Two-Party Computing with Encrypted Data
  Seung Geol Choi and Arial Elbaz and Ari Juels and Tal Malkin and Moti Yung
  ASIACRYPT, pages 298-314, 2007.
• Cryptographic Strength of SSL/TLS Servers: Current and Recent Practices
  Homin K. Lee and T. Malkin and Erich Nahum
  IMC, pages 83-92, 2007.
• Towards a Separation of Semantic and CCA Security for Public Key Encryption
  Yael Gertner and Tal Malkin and Steven Myers
  TCC 2007.
• LP Decoding Corrects a Constant Fraction of Error
  Jon Feldman and Tal Malkin and Cliff Stein abd Rocco Servedio and Martin Wainwright
  IEEE Transactions on Information Theory, 53(1),2007. Preliminary version appeared in ISIT 2004.
• Distribution-Free Testing Lower Bounds for Basic Boolean Functions
  Dana Glasner and Rocco Servedio
  APPROX-RANDOM, Lecture Notes in Computer Science, Vol. 4627, pp. 494-508, Springer, 2007.
• Amplifying Collision Resistance: A Complexity-Theoretic Treatment
  Ran Canetti and Ron L. Rivest and Madhu Sudan and Luca Trevisan and Salil Vadhan and Hoeteck Wee
  CRYPTO, pages 264-283, 2007.
• Separating Models of Learning from Correlated and Uncorrelated Data
  Ariel Elbaz and Homin K. Lee and Rocco A. Servedio and Andrew Wan
  Journal of Machine Learning Research(8), pages 277-290, 2007.
• Anonymity 2.0 - X.509 Extensions Supporting Privacy-Friendly Authentication
  Vicente Benjumea and Seung Geol Choi and Javier Lopez and Moti Yung
  CANS, pages 265-281, 2007.

  2006

• Generalized Environmental Security From Number Theoretic Assumptions
  Tal Malkin and Ryan Moriarty and Nikolai Yakovenko
  TCC, 2006.
• Short Traceable Signatures Based on Bilinear Pairings
  Seung Geol Choi and Kunsoo Park and Moti Yung
  IWSEC, pages 88-103, 2006.

  2005

• A Comparative Cost/Security Analysis of Fault Attack Countermeasures
  Tal Malkin and François-Xavier Standaert and Moti Yung
  FDTC, 2005.
• Mercurial Commitments with Applications to Zero-Knowledge Sets
  Melissa Chase and Alexander Healy and Anna Lysyanskaya and Tal Malkin and Leonid Reyzin
  EUROCRYPT, Lecture Notes in Computer Science, Vol. 3494, pp. 422-439, Springer, 2005.
• Secure Multiparty Computation of Approximations.
  Joan Feigenbauma and Yuval Ishai and Tal Malkin and Kobbi Nissim and Martin Strauss and Rebecca Wright
  ACM Transactions an Algorithms,2005. Preliminary version appeared in ICALP 2001.
• PSST! Are You Using a Secure SSL/TLS Server?
  Homin K. Lee and Tal Malkin and Erich Nahum and Noel Codella
  Appeared at the 2005 IBM Security and Privacy Technology Symposium, Sponsored by IBM Research and the IBM Academy of Technology

  2004

• On the Capacity of Secure Network Coding
  Jon Feldman and Tal Malkin and Cliff Stein and Rocco Servedio
  Allerton, 2004.
• On Adaptive vs. Non-Adaptive Security of Multiparty Protocols.
  Ran Canetti and Ivan Damgard and Stefan Dziembowski and Yuval Ishai and Tal Malkin
  Journal Of Cryptology, 17(3), pages 153-207, June 2004. Preliminary version appeared in EUROCRYPT 2001.
• The Hierarchy of Key Evolving Signatures and a Characterization of Proxy Signatures
  Tal Malkin and Satoshi Obana and Moti Yung
  EUROCRYPT, 2004.
• Reducing the Servers Computation in Private Information Retrieval: PIR with Preprocessing
  Amos Beimel and Yuval Ishai and Tal Malkin
  Journal of Cryptology, 17(2), pages 125–151, March 2004. Preliminary version appeared in CRYPT0 2000.
• Collaborative Distributed Intrusion Detection
  Michael Locasto and Janak Parekh and Sal Stolfo and Angelos Keromytis and Tal Malkin and Vishal Misra
  Technical Report CUCS-012-04, Columbia University Comptuer Science Department, March 2004.
• A Quantitative Approach to Reductions in Secure Computation
  Amos Beimel and Tal Malkin
  TCC, 2004. Full version available at ECCC valume 86, 2003.
• Algorithmic Tamper-Proof Security: Theoretical Foundations for Security against Hardware Tampering
  Rosario Gennaro and Anna Lysyanskaya and Tal Malkin and Silvio Micali and Tal Rabin
  TCC, 2004.
• The dual receiver cryptosystem and its applications
  Theodore Diament and Homin K. Lee and Angelos D. Keromytis and Moti Yung
  ACM Conference on Computer and Communications Security, pages 330-343, 2004.
• Improved Randomness Extraction from Two Independent Sources
  Yevgeniy Dodis and Ariel Elbaz and Roberto Oliveira and Ran Raz
  APPROX-RANDOM, pages 334-344, 2004.

  2003

• On the Performance, Feasibility, and Use of Forward-Secure Signatures
  Eric Cronin, Sugih Jamin, Tal Malkin, Patrick McDaniel
  CCS, 2003.
• WAR: Wireless Anonymous Routing
  Matt Blaze and John Ioannidis and Angelos D. Keromytis and Tal Malkin and Avi Rubin
  Security Protocols Workshop, 2003.

Cryptography Laboratory
Columbia University Department of Computer Science
1214 Amsterdam Avenue
New York, NY 10027-7003