Sanjam Garg

Assistant Professor
685 Soda Hall
Computer Science Division
University of California, Berkeley
Berkeley, CA 94720

Email: sanjamg at berkeley dot edu 

I help organize the Berkeley Theory Lunch (please send me an email if you would like to volunteer for a talk) and BayArea Cryptoday!

Research Interests: Cryptography, Security and more broadly in Theoretical Computer Science.  

Program Committees: EUROCRYPT 2019, STOC 2018, PKC 2017, Asiacrypt 2016, SCN 2016CRYPTO 2016, PKC 2016CRYPTO 2015, TCC 2015, Asiacrypt 2014, PKC 2014, ProvSec 2014, Africacrypt 2014

Students:  

Postdocs:

Long-term Visitors: Xiao Liang, Sruthi Sekar, Romain Gay, Silas Richelson, Giulio Malavota, Tahereh Jafarikhan, Ameer Mohameed, Mohammad Mahmoody, Claudio OrlandiDaniel AponSusumu Kiyoshima, Pratyay Mukherjee, Omkant PandeyAntigoni Polychroniadou.

Short-term Visitors Ryo Nishimaki, Arpita Patra, Dominique Schröder, Russell Lai, Jörn Müller-Quade, Adam O' Neill, Eylon Yogev, Abhishek Jain, Ivan Visconti, Ran Gelles, Alain Passelègue, Michel Abdalla, Nishanth Chandran, Bhavana Kanukurthi, Mark Zhandry.  

Teaching 







            Sanjam Garg

Publications (dblp)

 2018
  • Trapdoor Functions from the Computation Diffie-Hellman Assumption
    Sanjam Garg and Mohammad Hajiabadi
    CRYPTO 2018 [pdf]
  • Adaptive Garbled RAM from Laconic Oblivious Transfer
    Sanjam Garg, Rafail Ostrovsky and Akshayaram Srinivasan
    CRYPTO 2018 [pdf]
  • On the Round Complexity of OT Extension
    Sanjam Garg, Mohammad Mahmoody, Daniel Masny and Izaak Meckler
    CRYPTO 2018 [pdf]
  • Limits on the Power of Garbling Techniques for Public-Key Encryption
    Sanjam Garg, Mohammad Hajiabadi, Mohammad Mahmoody, and Ameer Mohammed
    CRYPTO 2018 [pdf]
      
  • Two-Round Multiparty Secure Computation Minimizing Public Key Operations
    Sanjam Garg, Peihan Miao and Akshayaram Srinivasan
    CRYPTO 2018 [pdf]
  • Two-Round Multiparty Secure Computation from Minimal Assumptions
    Sanjam Garg and Akshayaram Srinivasan
    EUROCRYPT 2018 [pdf(Best Paper Award)
  • Adaptively Secure Garbling with Near Optimal Online Complexity
    Sanjam Garg and Akshayaram Srinivasan
    EUROCRYPT 2018 [pdf
  • A New Approach to Black-Box Concurrent Secure Computation
    Sanjam Garg, Susumu Kiyoshima and Omkant Pandey
    EUROCRYPT 2018 [pdf
  • New Constructions of Identity-Based and Key-Dependent Message Secure Encryption Schemes
    Nico Döttling, Sanjam Garg, Mohammad Hajiabadi and Daniel Masny
    PKC 2018 [pdf 
 2017
  • From Selective IBE to Full IBE and Selective HIBE
    Nico Döttling and Sanjam Garg
    TCC 2017 [pdf 
  • When does Functional Encryption Imply Obfuscation?
    Sanjam Garg, Mohammad Mahmoody, and Ameer Mohammed
    TCC 2017 [pdf(full version coming soon)
  • Two-Message Witness Indistinguishability and Secure Computation in the Plain Model from New Assumptions
    Saikrishna Badrinarayanan, Sanjam Garg, Yuval Ishai, Amit Sahai, and Akshay Wadia
    ASIACRYPT 2017 [pdf]
  • Garbled Protocols and Two Round MPC from Bilinear Maps
    Sanjam Garg and Akshayaram Srinivasan
    FOCS 2017 [pdf]  
  • Identity-Based Encryption from the Diffie-Hellman Assumption
    Nico Döttling and Sanjam Garg
    CRYPTO 2017 [pdf] (Best Paper Award and invited to Journal of Cryptology)
  • Lower Bounds on Obfuscation from All-or-Nothing Encryption Functionalities
    Sanjam Garg, Mohammad Mahmoody, and Ameer Mohammed
    CRYPTO 2017 [pdf] (full version coming soon)
  • Laconic Oblivious Transfer and Its Applications
    Chongwon Cho, Nico Döttling, Sanjam Garg, Divya Gupta, Peihan Miao and Antigoni Polychroniadou
    CRYPTO 2017 [pdf]
  • Incremental Program Obfuscation
    Sanjam Garg, and Omkant Pandey
    CRYPTO 2017 [pdf]
  • Cryptanalysis of Indistinguishability Obfuscation of Circuits over GGH13
    Daniel Apon, Nico Döttling, Sanjam Garg, and Pratyay Mukherjee
    ICALP 2017 [pdf]
  • On the Exact Round Complexity of Self-Composable Two-Party Computation
    Sanjam Garg
    , Susumu Kiyoshima and Omkant Pandey
    EUROCRYPT 2017 [pdf]
  • Breaking the Sub-Exponential Barrier in Obfustopia
    Sanjam Garg, Omkant Pandey, Akshayaram Srinivasan and Mark Zhandry
    EUROCRYPT 2017 [pdf]
2016
  • Secure Obfuscation in a Weak Multilinear Map Model
    Sanjam Garg,  Eric Miles, Pratyay Mukherjee, Amit Sahai, Akshayaram Srinivasan and Mark Zhandry
    TCC 2016-B [pdf] (Merger of [GMSand [MSZ])
  • Single-Key to Multi-Key Functional Encryption with Polynomial Loss
    Sanjam Garg and Akshayaram Srinivasan
    TCC 2016-B [pdf]
  • Secure Multiparty RAM Computation in Constant Rounds
    Sanjam Garg, Divya Gupta, Peihan Miao and Omkant Pandey
    TCC 2016-B [pdf]
  • Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
    Sanjam Garg, Omkant Pandey and Akshayaram Srinivasan

    CRYPTO 2016 [pdf]
  • TWORAM: Efficient Oblivious RAM in Two Rounds with Applications to Searchable Encryption
    Sanjam Garg, Payman Mohassel and Charalampos Papamanthou

    CRYPTO 2016 [pdf]
  • The Exact Round Complexity of Secure Computation
    Sanjam Garg, Pratyay Mukherjee, Omkant Pandey and Antigoni Polychroniadou

    EUROCRYPT 2016 [pdf]
  • Fully Secure Functional Encryption without Obfuscation
    Sanjam Garg, Craig Gentry, Shai Halevi and Mark Zhandry

    TCC 2016-A [pdf]
  • Obfuscation from Low Noise Multilinear Maps
    Nico Döttling, Sanjam Garg, Divya Gupta, Peihan Miao and Pratyay Mukherjee
    Manuscript [pdf]
2015
  • Black-Box Garbled RAM
    Sanjam Garg, Steve Lu and Rafail Ostrovsky
    FOCS 2015 [pdf
  • Cryptography with One-Way Communication
    Sanjam Garg, Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky and Amit Sahai
    CRYPTO 2015 [pdf
  • Garbled RAM from One-Way Functions
    Sanjam Garg, Steve Lu, Rafail Ostrovsky and Alessandra Scafuro
    STOC 2015 [pdf
  • Succinct Randomized Encodings and their Applications
    Nir Bitansky, Sanjam Garg, Huijia Lin, Rafael Pass and Sidharth Telang

    STOC 2015 [pdf] (a merger of [pdf] and [pdf])  (Invited to the STOC special issue of SICOMP)
  • Two-Round Adaptively Secure MPC from Indistinguishability Obfuscation 
    Sanjam Garg and Antigoni Polychroniadou
    TCC 2015 [pdf]
2014
  • On the Implausibility of Differing-Inputs Obfuscation and Extractable Witness Encryption with Auxiliary Input 
    Sanjam Garg, Craig Gentry, Shai Halevi and Daniel Wichs

    CRYPTO 2014  [pdf] (Invited and published in a special issue of Algorithmica Journal dedicated to top CRYPTO 2014 papers [pdf])
  • Protecting Obfuscation Against Algebraic Attacks 
    Boaz Barak, Sanjam Garg, Yael Tauman Kalai, Omer Paneth and Amit Sahai

    EUROCRYPT 2014  [pdf]
  • Efficient Round Optimal Blind Signatures
    Sanjam Garg and Divya Gupta

    EUROCRYPT 2014  [pdf]
  • Two-round secure MPC from Indistinguishability Obfuscation 
    Sanjam Garg, Craig Gentry, Shai Halevi and Mariana Raykova

    TCC 2014  [pdf(Invited to the Journal of Cryptology)
  • Cross Domain Secure Computation  
    Chongwon Cho, Sanjam Garg and Rafail Ostrovsky

    PKC 2014  [pdf] 
  • Balancing Output Length and Query Bound in Hardness Preserving Constructions of Pseudorandom Functions  
    Nishanth Chandran and  Sanjam Garg

    Indocrypt 2014  [pdf]
  • Fully Secure Attribute Based Encryption from Multilinear Maps
    Sanjam Garg, Craig Gentry, Shai Halevi and Mark Zhandry

    Manuscript 2014 [pdf]
2013
  • Differing-Inputs Obfuscation and Applications
    Prabhanjan Ananth, Dan Boneh, Sanjam Garg, Amit Sahai and Mark Zhandry

    Manuscript 2013 [pdf]

  • Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits 
    Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai and Brent Waters

    FOCS 2013  [pdf(Invited and published for the FOCS special issue of SICOMP [pdf] and CACM Research Highlights [pdf].)
  • Attribute Based Encryption for Circuits from Multilinear Maps 
    Sanjam Garg, Craig Gentry, Shai Halevi, Amit Sahai and Brent Waters

    CRYPTO 2013  [pdf]
  • Secure Computation Against Adaptive Auxiliary Information
    Elette Boyle, Sanjam Garg, Abhishek Jain, Yael Tauman Kalai and Amit Sahai

    CRYPTO 2013   [pdf]
  • Witness Encryption and its Applications
    Sanjam Garg, Craig Gentry, Amit Sahai and Brent Waters

    STOC 2013   [pdf]
  • Candidate Multilinear Maps from Ideal Lattices
    Sanjam Garg, Craig Gentry and Shai Halevi

    EUROCRYPT 2013  [pdf] (Best Paper Award and invited to Journal of Cryptology)
  • Why "Fiat-Shamir for Proofs" Lacks a Proof
    Nir Bitansky, Dana Dachman-Soled, Sanjam Garg, Abhishek Jain, Yael Tauman Kalai, Adriana Lopez-Alt and Daniel Wichs

    TCC 2013
    Merger of [BGW] and [DJKL
2012
  • Adaptively Secure Multi-Party Computation with Dishonest Majority
    Sanjam Garg and Amit Sahai

    CRYPTO 2012  [pdf]
  • Impossibility Results for Static Input Secure Computation
    Sanjam Garg, Abishek Kumarasubramanian, Rafail Ostrovsky and Ivan Visconti

    CRYPTO 2012  [pdf]
  • Concurrently Secure Computation in Constant Rounds
    Sanjam Garg, Vipul Goyal, Abhishek Jain and Amit Sahai

    EUROCRYPT 2012  [pdf]
  • Resettable Statistical Zero Knowledge
    Sanjam Garg, Rafail Ostrovsky, Ivan Visconti and Akshay Wadia

    TCC 2012  [pdf]
2011
  • Leakage-Resilient Zero Knowledge
    Sanjam Garg, Abhishek Jain and Amit Sahai

    CRYPTO 2011  [pdf]
  • Round Optimal Blind Signatures
    Sanjam Garg, Vanishree Rao, Amit Sahai, Dominique Schröder and Dominique Unruh

    CRYPTO 2011  [pdf]
  • Bringing People of Different Beliefs Together to do UC
    Sanjam Garg, Vipul Goyal, Abhishek Jain and Amit Sahai

    TCC 2011  [pdf]
2010
  • Building Efficient Fully Collusion-Resilient Traitor Tracing and Revocation Schemes
    Sanjam Garg, Abishek Kumarasubramanian, Amit Sahai and Brent Waters

    CCS 2010  [pdf]
2008
  • Improved bounds on security reductions for Discrete log based Signatures
    Sanjam Garg, Raghav Bhaskar and Satyanarayana V. Lokam

    CRYPTO 2008  [pdf]  
  • Anti-DDoS Virtualized Operation System
    Sanjam Garg and Huzur Saran

    ARES 2008
2007
  • Unified Architecture for Large-Scale Attested Metering
    Michael LeMay, George Gross,  Carl A. Gunter and  Sanjam Garg

    HICSS 2007  [pdf]