2023

• Downward Self-Reducibility in TFNP
  Prahladh Harsha, Daniel Mitropolsky, Alon Rosen
  ITCS 2023
• Lower Bounds for (Batch) PIR with Private Preprocessing
  Kevin Yeo
  ASIACRYPT 2023
• Lower Bound Framework for Differentially Private and Oblivious Data Structures
  Giuseppe Persiano, Kevin Yeo
  ASIACRYPT 2023
• Limits on Revocable Proof Systems, with Implications for Stateless Blockchains
  Miranda Christ, Joseph Bonneau
  FC 2023
• The Smoothed Complexity of Policy Iteration for Markov Decision Processes
  Miranda Christ, Mihalis Yannakakis
  STOC 2023

2022

• Limits of Preprocessing for Single-Server PIR
  Giuseppe Persiano, Kevin Yeo
  SODA 2022
• Oblivious Message Retrieval
  Zeyu Liu, Eran Tromer
  CRYPTO 2022
• Differential Privacy and Swapping: Examining De-Identification's Impact on Minority Representation and Privacy Preservation in the US Census
  Miranda Christ, Sarah Radway, Steven M. Bellovin
  S&P 2022
• Poly Onions: Achieving Anonymity in the Presence of Churn
  Megumi Ando, Miranda Christ, Anna Lysyanskaya, Tal Malkin
  TCC 2022
• XSPIR: Efficient Symmetrically Private Information Retrieval from Ring-LWE
  Chengyu Lin, Zeyu Liu, Tal Malkin
  ESORICS 2022
• Unclonable Polymers and Their Cryptographic Applications
  Ghada Almashaqbeh, Ran Canetti, Yaniv Erlich, Jonathan Gershoni, Tal Malkin, Itsik Pe'er, Anna Roitburd-Berman, Eran Tromer
  EUROCRYPT 2022
• Randomness Extraction from Somewhat Dependent Sources
  Marshall Ball, Oded Goldreich, Tal Malkin
  ITCS 2022

2021

• Polynomial-time trace reconstruction in the smoothed complexity model
  Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
  SODA 2021
• Linear Threshold Secret-Sharing with Binary Reconstruction
  Marshall Ball, Alper Çakan, Tal Malkin
  ITC 2021
• Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime
  Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
  ITCS 2021
• Total Functions in the Polynomial Hierarchy
  Robert Kleinberg, Oliver Korten, Daniel Mitropolsky, Christos Papadimitriou
  ITCS 2021

2020

• Edit Distance in Near-Linear Time: it’s a Constant Factor
  Alexandr Andoni, Negev Shekel Nosatzki
  FOCS 2020
• Topology-Hiding Communication from Minimal Assumptions
  Marshall Ball, Elette Boyle, Ran Cohen, Lisa Kohl, Tal Malkin, Pierre Meyer, Tal Moran
  TCC 2020
• Can a Public Blockchain Keep a Secret?
  Fabrice Benhamouda, Craig Gentry, Sergey Gorbunov, Shai Halevi, Hugo Krawczyk, Chengyu Lin, Tal Rabin, Leonid Reyzin
  TCC 2020
• Lower Bounds for Multi-server Oblivious RAMs
  Kasper Green Larsen, Mark Simkin, Kevin Yeo
  TCC 2020
• Settling the relationship between Wilber's bounds for dynamic optimality
  Victor Lecomte, Omri Weinstein
  ESA 2020
• Non-Malleability against Polynomial Tampering
  Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, Tal Malkin, Li-Yang Tan
  CRYPTO 2020
• New Techniques for Zero-Knowledge: Leveraging Inefficient Provers to Reduce Assumptions, Interaction, and Trust
  Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni
  CRYPTO 2020
• Lower Bounds for Encrypted Multi-Maps and Searchable Encryption in the Leakage Cell Probe Mode
  Sarvar Patel, Giuseppe Persiano, Kevin Yeo
  CRYPTO 2020
• Limits to Non-Malleability
  Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni, Tal Malkin
  ITCS 2020
• On the Complexity of Decomposable Randomized Encodings, or: How Friendly Can a Garbling-Friendly PRF be?
  Marshall Ball, Justin Holmgren, Yuval Ishai, Tianren Liu, Tal Malkin
  ITCS 2020
• Cryptography from Information Loss
  Marshall Ball, Elette Boyle, Akshay Degwekar, Apoorvaa Deshpande, Alon Rosen, Vinod Vaikuntanathan, Prashant Vasudevan
  ITCS 2020
• MicroCash: Practical Concurrent Processing of Micropayments
  Ghada Almashaqbeh, Allison Bishop, Justin Cappos
  Financial Crypto 2020
• Lower Bounds for Oblivious Near-Neighbor Search
  Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo
  SODA 2020

2019

• Synesthesia: Detecting Screen Content via Remote Acoustic Side Channels
  Daniel Genkin, Mihir Pattani, Roei Schuster, Eran Tromer
  S&P 2019
• Public-Key Function-Private Hidden Vector Encryption (and More)
  James Bartusek, Brent Carmer, Abhishek Jain, Zhengzhong Jin, Tancrède Lepoint, Fermi Ma, Tal Malkin, Alex J. Malozemoff, Mariana Raykova
  ASIACRYPT 2019
• Is Information-Theoretic Topology-Hiding Computation Possible?
  Marshall Ball, Elette Boyle, Ran Cohen, Tal Malkin, Tal Moran
  TCC 2019
• Non-Malleable Codes for Decision Trees
  Marshall Ball, Siyao Guo, Daniel Wichs
  CRYPTO 2019
• Garbled Neural Networks are Practical
  Marshall Ball, Brent Carmer, Tal Malkin, Mike Rosulek, Nichole Schimanski
  CRYPTO Workshop, PPML 2019; CCS Workshop, PPML 2019
• Two Party Distribution Testing: Communication and Security
  Alexandr Andoni, Tal Malkin, Negev Shekel Nosatzki
  ICALP 2019
• CAPnet: A Defense Against Cache Accounting Attacks on Content Distribution Networks
  Ghada Almashaqbeh, Kevin Kelley, Allison Bishop, Justin Cappos
  IEEE CNS 2019
• In pursuit of clarity in obfuscation
  Allison Bishop, Lucas Kowalczyk, Tal Malkin, Valerio Pastro, Mariana Raykova, Kevin Shi
  CFAIL 2019
• Non-interactive key exchange in a generic multilinear group: An underwhelming lower bound
  Allison Bishop, Lucas Kowalczyk, Valerio Pastro
  CFAIL 2019
• Mitigating Leakage in Secure Cloud-Hosted Data Structures: Volume-Hiding for Multi-Maps via Hashing
  Sarvar Patel, Giuseppe Persiano, Kevin Yeo, Moti Yung
  CCS 2019
• Lower Bounds for Differentially Private RAMs
  Giuseppe Persiano, Kevin Yeo
  EUROCRYPT 2019
• Compact Adaptively Secure ABE for NC^1 from k-Lin
  Lucas Kowalczyk, Hoeteck Wee
  EUROCRYPT 2019
• Non-Malleable Codes Against Bounded Polynomial Time Tampering
  Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni, Huijia Lin, Tal Malkin
  EUROCRYPT 2019
• ABC: A Cryptocurrency-Focused Threat Modeling Framework
  Ghada Almashaqbeh, Allison Bishop, Justin Cappos
  IEEE INFOCOM Workshop, CryBlock 2019. Selected as a best paper and invited for the COMCOM journal special issue.

2018

• Secure Two Party Distribution Testing
  Alexandr Andoni, Tal Malkin, and Negev Shekel Nosatzki.
  Privacy Preserving Machine Learning workshop, NeurIPS 2018
• Mitigating the One-Use Restriction in Attribute-Based Encryption
  Lucas Kowalczyk, Jiahui Liu, Tal Malkin, and Kailash Meiyappan
  ICISC 2018
• Non-Malleable Codes for Small-Depth Circuits
  Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, and Li-Yang Tan
  FOCS 2018
• Situational Access Control in the Internet of Things
  Roei Schuster, Vitaly Shmatikov, and Eran Tromer
  CCS 2018
• Tight Adaptively Secure Broadcast Encryption with Short Ciphertexts and Keys
  Romain Gay, Lucas Kowalczyk, and Hoeteck Wee
  SCN 2018
• Obfuscation from Polynomial Hardness: Beyond Decomposable Obfuscation
  Yuan Kang, Chengyu Lin, Tal Malkin, and Mariana Raykova
  SCN 2018
• Semantically Secure Anonymity: Foundations of Re-Encryption
  Adam L. Young and Moti Yung
  SCN 2018
• Proactive Secure Multiparty Computation with a Dishonest Majority
  Karim Eldefrawy, Rafail Ostrovsky, Sunoo Park, and Moti Yung
  SCN 2018
• A Simple Obfuscation Scheme for Pattern-Matching with Wildcards
  Allison Bishop, Lucas Kowalczyk, Tal Malkin, Valerio Pastro, Mariana Raykova, and Kevin Shi
  CRYPTO 2018
• Hardness of Non-Interactive Differential Privacy from One-Way Functions
  Lucas Kowalczyk, Tal Malkin, Jonathan Ullman, and Daniel Wichs
  CRYPTO 2018
• Proofs of Work From Worst-Case Assumptions
  Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan
  CRYPTO 2018
• Correcting Subverted Random Oracles
  Alexander Russell, Qiang Tang, Moti Yung, and Hong-Sheng Zhou
  CRYPTO 2018
• Drive-by Key-Extraction Cache Attacks from Portable Code
  Daniel Genkin, Lev Pachmanov, Eran Tromer
  ACNS 2018
• Unbounded ABE via Bilinear Entropy Expansion, Revisited
  Jie Chen, Jinqing Gong, Lucas Kowalczyk, and Hoeteck Wee
  EUROCRYPT 2018
• Exploring the Boundaries of Topology-Hiding Computation
  Marshall Ball, Elette Boyle, Tal Malkin, and Tal Moran
  EUROCRYPT 2018
• Non-Malleable Codes from Average-Case Hardness: AC0, Decision Trees, and Streaming Space-Bounded Tampering
  Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni, and Tal Malkin
  EUROCRYPT 2018
• Improved, Black-Box, Non-Malleable Encryption from Semantic Security
  Seung Geol Choi, Dana Dachman-Soled, Tal Malkin, and Hoeteck Wee
  Designs, Codes, and Cryptography 2018

2017

• Beauty and the Burst: remote identification of encrypted video streams
  Roei Schuster, Vitaly Shmatikov, and Eran Tromer
  USENIX Security 2017
• Average-Case Fine-Grained Hardness
  Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan
  STOC 2017
• Access Control Encryption for Equality, Comparison, and More
  Georg Fuchsbauer, Romain Gay, Lucas Kowalczyk, and Claudio Orlandi
  PKC 2017
• Improved, Black-Box, Non-Malleable Encryption from Semantic Security
  Seung Geol Choi, Dana Dachman-Soled, Tal Malkin, and Hoeteck Wee
  Design, Codes, and Cryptography 2017
• A Black-Box Construction of Non-Malleable Encryption from Semantically Secure Encryption
  Seung Geol Choi, Dana Dachman-Soled, Tal Malkin, and Hoeteck Wee
  Journal of Cryptography 2017
• Computational Integrity with a Public Random String from Quasi-Linear PCPs
  Eli Ben-Sasson, Iddo Bentov, Alessandro Chiesa, Ariel Gabizon, Daniel Genkin, Matan Hamilis, Evgenya Pergament, Michael Riabzev, Mark Silberstein, Eran Tromer, and Madars Virza
  EUROCRYPT 2017

2016

• ECDSA key extraction from mobile devices via nonintrusive physical side channels
  Daniel Genkin, Lev Pachmanov, Itamar Pipman, Eran Tromer, and Yuval Yarom
  CCS 2016
• Garbling Gadgets for Boolean and Arithmetic Circuits
  Marshall Ball, Tal Malkin, and Mike Rosulek
  CCS 2016
• Strong Hardness of Privacy from Weak Traitor Tracing
  Lucas Kowalczyk, Tal Malkin, Jonathan Ullman, and Mark Zhandry
  TCC 2016B
• Interactive Coding for Interactive Proofs
  Allison Bishop and Yevgeniy Dodis
  TCC 2016A
• Non-malleable Codes for Bounded Depth, Bounded Fan-In Circuits
  Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni, and Tal Malkin
  EUROCRYPT 2016
• Interactive Coding for Interactive Proofs
  Allison Bishop and Yevgeniy Dodis
  TCC 2016A
• Essentially Optimal Robust Secret Sharing with Maximal Corruptions
  Allison Bishop, Valerio Pastro, Rajmohan Rajaraman, and Daniel Wichs
  EUROCRYPT 2016
• Robust Secret Sharing Schemes Against Local Adversaries
  Allison Bishop and Valerio Pastro
  PKC 2016

2015

• Function-Hiding Inner Product Encryption
  Allison Bishop, Abhishek Jain, and Lucas Kowalczyk
  ASIACRYPT 2015
• New Circular Security Counterexamples from Decision Linear and Learning with Errors
  Allison Bishop, Susan Hohenberger, and Brent Waters
  ASIACRYPT 2015
• Bilinear Entropy Expansion from the Decisional Linear Assumption
  Lucas Kowalczyk and Allison Bishop
  CRYPTO 2015
• Indistinguishability Obfuscation for Turing Machines with Unbounded Memory
  Venkata Koppula, Allison Bishop Lewko, and Brent Waters
  STOC 2015
• Indistinguishability Obfuscation from the Multilinear Subgroup Elimination Assumption
  Craig Gentry, Allison Bishop Lewko, Amit Sahai, and Brent Waters
  FOCS 2015
• The Power of Negations in Cryptography
  Siyao Guo, Tal Malkin, Igor C Oliveira, and Alon Rosen
  TCC 2015
• A Profitable Sub-prime Loan: Obtaining the Advantages of Composite Order in Prime-Order Bilinear Groups
  Allison Lewko and Sarah Meiklejohn
  PKC 2015
• Malicious-client Security in Blind Seer: A Scalable Private DBMS
  Ben Fisch, Binh Vo, Fernando Krell, Abishek Kumarasubramanian, Vladimir Kolesnikov, Tal Malkin, and Steven M Bellovin
  IEEE Symposium on Security and Privacy 2015
• Interactive Coding for Multiparty Protocols
  Abhishek Jain, Yael Tauman Kalai, and Allison Bishop Lewko
  ITCS 2015
• Secure efficient history-hiding append-only signatures in the standard model
  Benoît Libert, Marc Joye, Moti Yung, and Thomas Peters
  PKC 2015
• A Little Honesty Goes a Long Way
  Juan A Garay, Ran Gelles, David S Johnson, Aggelos Kiayias, and Moti Yung
  TCC 2015
• Short group signatures via structure-preserving signatures: standard model security from simple assumptions
  Benoit Libert, Thomas Peters, and Moti Yung
  CRYPTO 2015

2014

• Witness Encryption from Instance Independent Assumptions
  Craig Gentry, Allison Lewko, and Brent Waters
  CRYPTO 2014
• Why Proving HIBE Systems Secure is Difficult
  Allison Lewko and Brent Waters
  EUROCRYPT 2014
• Can Optimally-Fair Coin Tossing Be Based on One-Way Functions?
  Dana Dachman-Soled, Mohammad Mahmoody, and Tal Malkin
  TCC 2014
• Order-Preserving Encryption Secure Beyond One-Wayness
  Isamu Teranishi, Moti Yung, and Tal Malkin
  ASIACRYPT 2014
• Non-malleability from malleability: Simulation-sound quasi-adaptive NIZK proofs and CCA2-secure encryption from homomorphic signatures
  Benoît Libert, Thomas Peters, Marc Joye, and Moti Yung
  EUROCRYPT 2014
• Concise multi-challenge cca-secure encryption and signatures with almost tight security
  Benoit Libert, Marc Joye, Moti Yung, and Thomas Peters
  ASIACRYPT 2014
• Blind SEER: A Scalable Private DBMS
  Vasilis Pappas, Fernando Krell, Binh Vo, Vladimir Kolesnikov, Tal Malkin, Seung Geol Choi, Wesley George, Angelos Keromytis, and Steve Bellovin
  IEEE Symposium on Security and Privacy 2014
• Traceable group encryption
  Benoît Libert, Moti Yung, Marc Joye, and Thomas Peters
  PKC 2014

2013

• Multi-party Computation of Polynomials and Branching Programs Without Simultaneous Interaction
  Dov Gordon, Tal Malkin, Mike Rosulek, and Hoeteck Wee
  EUROCRYPT 2013
• Adaptive and Concurrent Secure Computation from new Adaptive, Non-malleable Commitments
  Dana Dachman-Soled, Tal Malkin, Mariana Raykova, and Muthuramakrishnan Venkitasubramaniam
  ASIACRYPT 2013
• Secure computation for big data
  Tal Malkin
  TCC 2013
• Self-updatable encryption: Time constrained access control with hidden attributes and better efficiency
  Kwangsu Lee, Seung Geol Choi, Dong Hoon Lee, Jong Hwan Park, and Moti Yung
  ASIACRYPT 2013
• Sequential aggregate signatures with short public keys: Design, analysis and implementation studies
  Kwangsu Lee, Dong Hoon Lee, and Moti Yung
  PKC 2013

2012

• Efficient Robust Private Search Intersection
  Dana Dachman-Soled, Tal Malkin, Mariana Raykova, and Moti Yung
  IJACT 2(3), 2012.
• Mercurial Commitments with Applications to Zero-Knowledge Sets
  Melissa Chase, Alexander Healy, Anna Lysyanskaya, Tal Malkin, and Leonid Reyzin
  Journal of Cryptology.
• On the Security of Luo et al.’s Fully Secure Hierarchical Identity Based Encryption Scheme
  Kwangsu Lee, Jong Hwan Park, and Dong Hoon Lee
  IEICE Transactions 95-A(9).
• Secret swarm unit: Reactive k-secret sharing
  Shlomi Dolev, Limor Lahiani, and Moti Yung
  Ad Hoc Networks 10(7).
• Scalable Group Signatures with Revocation Benoît Libert, Thomas Peters, and Moti Yung
  EUROCRYPT 2012.
• Contextual OTP: Mitigating Emerging Man-in-the-Middle Attacks with Wireless Hardware Tokens
  Assaf Ben-David, Omer Berkman, Yossi Matias, Sarvar Patel, Cem Paya, and Moti Yung
  ACNS 2012.
• Group Signatures with Almost-for-Free Revocation
  Benoît Libert, Thomas Peters, and Moti Yung
  CRYPTO 2012.
• Scalable Group Signatures with Revocation Benoît Libert, Thomas Peters, and Moti Yung
  EUROCRYPT 2012.
• Strictly-Black-Box Zero-Knowledge and Efficient Validation of Financial Transactions
  Michael O. Rabin, Yishai Mansour, S. Muthukrishnan, and Moti Yung.
  ICALP 2012.
• Usable, Secure, Private Search
  Mariana Raykova, Ang Cui. Bihn Vo, Bin Liu, Tal Malkin, Steven M. Bellovin, and Salvatore J. Stolfo.
  IEEE Security & Privacy, Volume 10, Number 5, 2012.
• Secure Two-Party Computation in Sublinear Amortized Time
  Dov Gordon, Jonathan Katz, Vladimir Kolesnikov, Fernando Krell, Mariana Raykova, Tal Malkin, and Yevgeniy Vahlis
  CCS 2012.
• On the Centrality of Off-Line E-Cash to Concrete Partial Information Games
  Seung Geol Choi, Dana Dachman-Soled, and Moti Yung. SCN 2012.
• Fully Forward-Secure Group Signatures
  Benoît Libert and Moti Yung
  Cryptography and Security 2012.
• Non-interactive CCA-Secure Threshold Cryptosystems with Adaptive Security: New Framework and Constructions
  Benoît Libert and Moti Yung
  TCC 2012.
• How to Delegate and Verify in Public: Verifiable Computation from Attribute-Based Encryption
  Bryan Parno and Mariana Raykova and Vinod Vaikuntanathan
  TCC 2012.
• The power of the dinur-nissim algorithm: breaking privacy of statistical and graph databases
  Krzysztof Choromanski and Tal Malkin
  PODS 2012.
• Secure Multi-Party Computation of Boolean Circuits with Applications to Privacy in On-Line Marketplaces
  Seung Geol Choi and Kyung-Wook Hwang and Jonathan Katz and Tal Malkin and Dan Rubenstein
  CT-RSA 2012.
• Computational Extractors and Pseudorandomness
  Dana Dachman-Soled and Rosario Gennaro and Hugo Krawczyk
  TCC 2012.

  2011

• Secure Efficient Multiparty Computing of Multivariate Polynomials and Applications
  Dana Dachman-Soled and Tal Malkin and Mariana Raykova and Moti Yung
  ACNS 2011.
• From Protecting a System to Protecting a Global Ecosystem
  Moti Yung
  Communications and Multimedia Security 2011.
• Private search in the real world
  Vasilis Pappas and Mariana Raykova and Binh Vo and Steven M. Bellovin and Tal Malkin
  ACSAC 2011.
• BiTR: Built-in Tamper Resilience
  Seung Geol Choi and Aggelos Kiayias and Tal Malkin
  ASIACRYPT 2011.
• Key dependent message security: recent results and applications
  Tal Malkin and Isamu Teranishi and Moti Yung
  CODASPY 2011.
• Efficient Circuit-Size Independent Public Key Encryption with KDM Security
  Tal Malkin and Isamu Teranishi and Moti Yung
  Eurocrypt 2011.
• On the Security of Hash Functions Employing Blockcipher Postprocessing
  Donghoon Chang and Mridul Nandi and Moti Yung
  FSE 2011.
• Adaptively Secure Non-interactive Threshold Cryptosystems
  Benoît Libert and Moti Yung
  ICALP 2011.
• On the Black-Box Complexity of Optimally-Fair Coin Tossing
  Dana Dachman-Soled and Yehuda Lindell and Mohammad Mahmoody and Tal Malkin
  TCC 2011.
• Signatures Resilient to Continual Leakage on Memory and Computation
  Yevgeniy Vahlis and Tal Malkin and Isamu Teranishi and Moti Yung
  TCC 2011.
• Signatures Resilient to Continual Leakage on Memory and Computation
  Tal Malkin and Isamu Teranishi and Yevgeniy Vahlis and Moti Yung
  TCC 2011.
• 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, IBM Zurich, 2011.
• Key dependent message security: recent results and applications
  Tal Malkin and Isamu Teranishi and Moti Yung
  CODASPY 2011.
• A zero-knowledge based framework for RFID privacy
  Robert H. Deng and Yingjiu Li and Moti Yung and Yunlei Zhao
  Journal of Computer Security 2011.
• Efficient traceable signatures in the standard model
  Benoît Libert and Moti Yung
  Theoretical Computer Science 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.
• 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
500 West 120th Street
New York, NY 10027