Tal Malkin's Publications

Below are all my publications up to 2011. I've stopped updating this page because you can find my publications on my group's webpage. Specifically, check out the Crypto Lab publications page for papers that have already appeared, and the news page for recent papers in preprint form (typically available on ePrint). If those pages don't look updated either, or if you really want only papers including me rather than anyone from my group, you can check out my dblp and Google Scholar pages.

Publications up to 2011

• BiTR: Built-in Tamper Resilience
  Seung Geol Choi, Aggelos Kiayias, Tal Malkin.
  Asiacrypt 2011, to appear.

• Private Search in the Real World
  Vasilis Pappas, Mariana Raykova, Binh Vo, Steven Bellovin, Tal Malkin
  ACSAC 2011.

• Secure Efficient Multiparty Computing of Multivariate Polynomials and Applications
  Dana Dachman-Soled, Tal Malkin, Mariana Raykova, Moti Yung
  ACNS 2011.

• Efficient Circuit-Size Independent Public Key Encryption with KDM Security
  Tal Malkin, Isamu Teranishi, Moti Yung
  Eurocrypt 2011.

• Signatures Resilient to Continual Leakage on Memory and Computation
  Tal Malkin and Isamu Teranishi and Yevgeniy Vahlis and Moti Yung
  TCC 2011. [eprint version]

• On the Black-Box Complexity of Optimally-Fair Coin Tossing
  Dana Dachman-Soled and Yehuda Lindell and Mohammad Mahmoody and Tal Malkin
  TCC, 2011.

• Amortized Sublinear Secure Multi Party Computation
  Dov Gordon, Jonathan Katz, Vladimir Kolesnikov, Tal Malkin, Mariana Raykova, Yevgeniy Vahlis
  Workshop on Cryptography and Security in the Clouds, 2011. [eprint version]

• Key Dependent Message Security: Recent Results\ and Applications
  Tal Malkin, Isamu Teranishi, Moti Yung
  CODASPY 2011.

• How Should We Solve Search Problems Privately?
  Amos Beimel and Tal Malkin and Kobbi Nissim and Enav Weinreb
  Journal of Cryptology, 23(2), 2010.

• 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.

• 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
  Francois-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

• 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.

• 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.

• Oblivious Image Matching
  Shai Avidan and Ariel Elbaz and Tal Malkin and Ryan Moriarty
  Invited book chapter to "Protecting Privacy in Video Surveillance", Andrew Senior (editor)
  Springer, 2009, ISBN: 978-1-84882-300-6 2009.

• Topics in Cryptology - CT-RSA 2008
  Tal Malkin (editor)
  Proceedings of the Cryptographers' Track at the RSA Conference (CT-RSA)
  Lecture Notes in Computer Science (LNCS) Vol 4964, Springer, 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?
  Francois-Xavier Standaert and Tal G. Malkin and Moti Yung
  ICITCS, pages 70-70 2008. Invited talk.

• 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 Francois-Xavier Standaert and Olivier Pereira and Tal Malkin and Moti Yung
  ASIACCS, pages 56-65, ACM, 2008.

• 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 Tal 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.

• Public Key Cryptography - PKC 2006
  Moti Yung, Yevgeniy Dodis, Aggelos Kiayias, Tal Malkin (editors)
  Proceedings of the 9th International Conference on Theory and Practice of Public Key Cryptography (PKC)
  Lecture Notes in Computer Science (LNCS) Vol 3958, Springer, 2006.

• Generalized Environmental Security From Number Theoretic Assumptions
  Tal Malkin and Ryan Moriarty and Nikolai Yakovenko
  TCC, 2006.

• A Comparative Cost/Security Analysis of Fault Attack Countermeasures
  Tal Malkin and Francois-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, Volume 2, Issue 3, July 2006.

• 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

• 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.

• Reducing the Servers Computation in Private Information Retrieval: PIR with Preprocessing
  Amos Beimel, Yuval Ishai, Tal Malkin
  Journal of Cryptology, 17(2), pp 125-151, March 2004.

• LP Decoding Corrects a Constant Fraction of Error (an expanded version).
  Jon Feldman, Tal Malkin, Cliff Stein, Rocco Servedio, Martin Wainwright.
  Proc. IEEE International Symposium on Information Theory (ISIT'04).

• The Hierarchy of Key Evolving Signatures and a Characterization of Proxy Signatures.
  Tal Malkin, Satoshi Obana, Moti Yung.
  In Proceedings of the 22th Annual IACR Eurocrypt conference (EUROCRYPT '04).

• A Quantitative Approach to Reductions in Secure Computation.
  Amos Beimel, Tal Malkin.
  In Proceedings of the First Theory of Cryptography Conference (TCC '04).
  A full version is available at the Electronic Colloquium on Computational Complexity, volume 86, 2003.

• Algorithmic Tamper-Proof Security.
  Rosario Gennaro, Anna Lysyanskaya, Tal Malkin, Silvio Micali, Tal Rabin.
  In Proceedings of the First Theory of Cryptography Conference (TCC '04).

• On the Design and Use of Forward Secure Signatures.
  Eric Cronin, Sugih Jamin, Tal Malkin, Patrick McDaniel.
  Proceedings of the 10th ACM Conference on Computer and Communications Security (CCS '03).

• Protocols for Anonymity in Wireless Networks.
  Matt Blaze, John Ioannidis, Angelos D. Keromytis, Tal Malkin, Avi Rubin.
  Proceedings of the 11th International Workshop on Security Protocols. April 2003, Cambridge, England.

• Efficient Generic Forward-Secure Signatures With An Unbounded Number Of Time Periods.
  Tal Malkin, Daniele Micciancio, Sara Miner.
  Proc. of the 20th Annual IACR Eurocrypt conference (EUROCRYPT '02).
  A longer, though slightly older, version is available here.

• On the Impossibility of Basing Trapdoor Functions on Trapdoor Predicates.
  Yael Gertner, Tal Malkin, Omer Reingold.
  Proc. of the 42st Annual Symposium on Foundations of Computer Science (FOCS '01).

• Secure Multiparty Computation of Approximations.
  Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin Strauss, Rebecca Wright.
  Proc. of the 28th International Colloquium on Automata, Languages and Programming (ICALP '01).
  

• On Adaptive vs. Non-Adaptive Security of Multiparty Protocols.
  Ran Canetti, Ivan Damgard, Stefan Dziembowski, Yuval Ishai, Tal Malkin.
  Proc. of the 19th Annual IACR Eurocrypt conference (EUROCRYPT '01).

• The Relationship between Public Key Encryption and Oblivious Transfer.
  Yael Gertner, Sampath Kannan, Tal Malkin, Omer Reingold, Mahesh Viswanathan.
  Proc. of the 41st Annual Symposium on Foundations of Computer Science (FOCS '00).

• Reducing the Servers Computation in Private Information Retrieval: PIR with Preprocessing.
  Amos Beimel, Yuval Ishai, Tal Malkin.
  Proc. of the 20th Annual IACR Crypto conference (CRYPTO '00).

• Single Database Private Information Retrieval Implies Oblivious Transfer.
  Giovanni Di Crescenzo, Tal Malkin, Rafail Ostrovsky.
  Proc. of the 18th Annual IACR Eurocrypt conference (EUROCRYPT '00).

• A Study of Secure Database Access and General Two-Party Computation.
  Tal Malkin.
  Ph.D. Thesis, Massachusetts Institute Of Technology.

• The All-Or-Nothing Nature of Two-Party Secure Computation.
  Amos Beimel, Tal Malkin, Silvio Micali.
  Proc. of the 19th IACR Crypto conference (CRYPTO '99).

• One-way Functions are Essential for Single-Server Private Information Retrieval.
  Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Tal Malkin.
  Proc. of the 31st ACM Symp. on the Theory of Computing (STOC '99).

• Efficient Communication-Storage Tradeoffs for Multicast Encryption.
  Ran Canetti, Tal Malkin, Kobbi Nissim.
  Proc. of the 17th IACR Eurocrypt conference (EUROCRYPT '99).

• A Random Server Model for Private Information Retrieval.
  Yael Gertner, Shafi Goldwasser, Tal Malkin.
  2nd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM '98).

• Protecting Data Privacy in Private Information Retrieval Schemes.
  Yael Gertner, Yuval Ishai, Eyal Kushilevitz, Tal Malkin.
  Journal of Computer and System Sciences (JCSS) vol. 60(3), pp. 592-629.
  An extended abstract has appeared in Proc. of the 30th ACM Symp. on the Theory of Computing (STOC '98).

• Efficient Distributed 1 out of n Oblivious Transfer.
  Technical Report MIT-LCS-TR-714, MIT Lab for Computer Science. Yael Gertner, Tal Malkin.
  

• Deductive Tableaux for Temporal Logic.
  Tal Malkin.
  M.Sc. Thesis, Weizmann Institute of Science.