Nir Bitansky - Homepage

I'm a faculty member at Tel Aviv University's School of Computer Science. I'm interested in the theory of computation at large, and the theory of cryptography in particular.

Before joining TAU I was a postdoctoral researcher at MIT CSAIL hosted by Vinod Vaikuntanathan. I completed my Ph.D. at Tel Aviv University where I was advised by Ran Canetti.


        Email: nirbitan at tau dot ac dot il

        Office: Check Point Building 344

Students and Postdocs

Ph.D.Sapir Freizeit Nathan Geier Omri Shmueli (co-advised with Zvika Brakerski)
M.Sc.Dana Shamir (co-advised with Omer Paneth)Tomer Solomon (graduated 2023)Noa Eizenstadt (graduated 2020) Omri Shmueli (graduated 2020)Nathan Geier (graduated 2021)Michael Kelner (graduated 2021)Idan Gerichter (graduated 2022) Sapir Freizeit (graduated 2022)
PostdocChethan Kamath (co-hosted with Omer Paneth, now Assistant Professor at IIT Bombay)Eylon Yogev (co-hosted with Omer Paneth, now Assistant Professor at Bar-Ilan University)



Batch Proofs are Statistically Hiding

  with Chethan Kamath, Omer Paneth, Ron Rothblum, and Prashant Vasudevan


Non-Interactive Universal Arguments

  with Omer Paneth, Dana Shamir, and Tomer Solomon


Bootstrapping Homomorphic Encryption via Functional Encryption

  with Tomer Solomon


PPAD is as Hard as LWE and Iterated Squaring

  with  Arka Rai Choudhuri, Justin Homgren, Chethan Kamath, Alex Lombardi, Omer Paneth, and Ron D. Rothblum

TCC 2022 PDF 

Constructive Post-quantum Reductions

           with Zvika Brakerski and Yael Tauman Kalai


Statistically Sender Private OT from LPN and Derandomization

           with Sapir Freizeit


Non-malleable Commitments Against Quantum Attacks 

           with Huijia Lin and Omri Shmueli


Classical Binding for Quantum Commitments

           with Zvika Brakerski 

TCC 2021   PDF

Post-quantum Resettably-Sound Zero Knowledge

           with Michael Kelner and Omri Shmueli

TCC 2021, QCRYPT 2021   PDF

       Characterizing Deterministic Prover Zero Knowledge

           with Arka Rai Choudhuri

TCC 2020   PDF

Weakly Extractable One Way Functions

               with Noa Eizenstadt and Omer Paneth

TCC 2020   PDF

Post-quantum Zero Knowledge in Constant Rounds

           with Omri Shmueli

STOC 2020, QCRYPT 2020, QIP 2021   PDF

On the Cryptographic Hardness of Local Search

           with Idan Gerichter

ITCS 2020    PDF


       On Oblivious Amplification of Coin-Tossing Protocols

           with Nathan Geier

ITCS 2020    PDF

On the Complexity of Collision Resistant Hash Functions: New and Old Black-Box Separations 

           with Akshay Degwekar

TCC 2019 PDF

On Round-Optimal Statistical Zero-Knowledge Arguments

    with Omer Paneth


Weak Zero-Knowledge Beyond the Black-Box Barrier

         with Dakshita Khurana and  Omer Paneth

       STOC 2019, Siam Journal on Computing 2022 PDF

Distributional Collision Resistance Beyond One-Way Functions

         with  Iftach Haitner, Ilan Komargodski, and Eylon Yogev

        EUROCRYPT 2019  PDF  

One-Message Zero Knowledge and Non-Malleable Commitments

         with  Huijia Lin

        TCC 2018   PDF

Multi-Collision Resistance: A Paradigm for Keyless Hash Functions

         with Yael Tauman Kalai, and Omer Paneth

        STOC 2018   PDF


Verifiable Random Functions from Non-Interactive Witness-Indistinguishable Proofs

        TCC 2017,  Journal of Cryptology 2019    PDF        


 Structure vs Hardness through the Obfuscation Lens

           with Akshay Degwekar and Vinod Vaikuntanathan

        CRYPTO 2017, Siam Journal on Computing 2021   Draft        


On Removing Graded Encodings from Functional Encryption

           with Huijia Lin and Omer Paneth 

        EUROCRYPT 2017   PDF


 A Note on Perfect Correctness by Derandomization

           with Vinod Vaikuntanathan

        EUROCRYPT 2017, Journal of Cryptology 2022 PDF


From Cryptomania to Obfustopia through Secret-Key Functional Encryption

           with Ryo Nishimaki, Alain Passelègue, and Daniel Wichs

        TCC 2016B, Journal of Cryptology 2019    PDF


3-Message Zero Knowledge against Human Ignorance

           with Zvika Brakerski, Yael Tauman Kalai, Omer Paneth, and Vinod Vaikuntanathan

        TCC 2016B    PDF               


        Time-Lock Puzzles from Randomized Encodings

           with Shafi Goldwasser, Abhishek Jain, Omer Paneth, Vinod Vaikuntanathan, and Brent Waters

        ITCS 2016    PDF      


        Indistinguishability Obfuscation: from Approximate to Exact

           with Vinod Vaikuntanathan

        TCC 2016A   PDF    


        Perfect Structure on the Edge of Chaos

           with Omer Paneth and Daniel Wichs

        TCC 2016A     PDF


Indistinguishability Obfuscation from Functional Encryption

           with Vinod Vaikuntanathan

        FOCS 2015, Journal of the ACM 2018    PDF    


On the Cryptographic Hardness of Finding a Nash Equilibrium

         with Omer Paneth and Alon Rosen

        FOCS 2015    PDF


        Succinct Randomized Encodings and their Applications

        with Sanjam Garg, Huijia Lin, Rafael Pass, and Sidharth Telang  

        STOC 2015    PDF, Siam Journal on Computing 2019 (merged with Canetti, Holmgren, Jain, and Vaikuntanathan) 

        Merge of [BGT] and [LP]


        ZAPs and Non-Interactive Witness-Indistinguishability from Indistinguishability Obfuscation

         with Omer Paneth

        TCC 2015    PDF


On Virtual Grey Box Obfuscation for General Circuits

         with Ran Canetti, Yael Tauman Kalai, and Omer Paneth

        CRYPTO 2014,    Algorithmica 2016     Draft


The Impossibility of Obfuscation with Auxiliary Input or a Universal Simulator

         with Ran Canetti, Henry Cohn, Shafi Goldwasser, Yael Tauman Kalai, Omer Paneth, and Alon Rosen

        CRYPTO 2014    PDF     

        Merge of [BCPR] and [CGK]      


Leakage-Tolerant Computation with Input-Independent Preprocessing

        with Dana Dachman-Soled and Huijia Lin

        CRYPTO 2014    PDF       


On the Existence of Extractable One-Way Functions

         with Ran Canetti, Omer Paneth, and Alon Rosen

        STOC 2014,    Siam Journal on Computing 2016     Draft 

        Merge of [BCP] and [BCPR]      


Obfuscation for Evasive Functions

         with Boaz Barak, Ran CanettiYael Tauman Kalai, Omer Paneth, and Amit Sahai

        TCC 2014    PDF


Why "Fiat-Shamir for Proofs" Lacks a Proof

        with Dana Dachman-Soled, Sanjam Garg, Abhishek Jain, Yael Tauman Kalai, Adriana Lopez-Alt, and Daniel Wichs 

        TCC 2013

        Merge of [BGW] and [DJKL]


Succinct Non-Interactive Arguments via Linear Interactive Proofs

        with Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, Omer Paneth

        TCC 2013, Journal of Cryptology 2022    PDF


Recursive Composition and Bootstrapping for SNARKs and Proof-Carrying Data

         with Ran Canetti, Alessandro Chiesa, Eran Tromer

        STOC 2013    PDF        


On the Impossibility of Approximate Obfuscation and Applications to Resettable Cryptography

         with Omer Paneth

        STOC 2013    (subsumed by Siam Journal on Computing 2015    Draft


From the Impossibility of Obfuscation to a New Non-Black-Box Simulation Technique

        with Omer Paneth 

        FOCS 2012,    Siam Journal on Computing 2015    Draft


Succinct Arguments from Multi-Prover Interactive Proofs and their Efficiency Benefits

        with  Alessandro Chiesa 

        CRYPTO 2012    PDF


Leakage-Tolerant Interactive Protocols

        with Ran Canetti and Shai Halevi

        TCC 2012    PDF


Point Obfuscation and 3-Message Zero Knowledge

        with Omer Paneth

        TCC 2012    PDF


The Hunting of the SNARK    

        with Ran Canetti, Alessandro Chiesa, Shafi Goldwasser, Huijia Lin, Aviad Rubinstein, Eran Tromer

        Journal of Cryptology 2016    PDF

Preliminary version: From Extractable Collision Resistance to Succinct Non-Interactive Arguments of Knowledge, and Back Again

        with Ran Canetti, Alessandro Chiesa, Eran Tromer

        ITCS 2012


Program Obfuscation with Leaky Hardware

        with Ran Canetti, Shafi Goldwasser, Shai Halevi, Yael Tauman Kalai, Guy N. Rothblum

        ASIACRYPT 2011    PDF


On Strong Simulation and Composable Point Obfuscation

        with Ran Canetti

        CRYPTO 2010,    Journal of Cryptology 2013    PDF



        Getting Inside the Adversary's Head: New Directions in Non-Black-Box Knowledge Extraction

        Tel Aviv University 2015    PDF

Some Videotaped Talks        

Constructive Post-quantum Reductions (Crypto '22)

Classical Binding for Quantum Commitments  (TCC '21)   

On the Cryptographic Hardness of Local Search  (ITCS '20)   

On Round-Optimal Statistical Zero-Knowledge Arguments  (Crypto '19)   

Our Current Knowledge of Knowledge Assumptions (Dimacs workshop on cryptographic assumptions '17)

On Removing Graded Encodings from Functional Encryption (Eurocrypt '17)   

        A Note on Perfect Correctness by Derandomization (Eurocrypt '17)

        A Reduction from Flying Pigs to Jumping Pigs (IAS, March '17)

        On the Cryptographic Hardness of Finding a Nash Equilibrium (IAS, March '17, shorter version at FOCS '15)

        Program Obfuscation: The Power of Unreadable Code (UW Colloquium, April '16) 

        Indistinguishability Obfuscation from Functional Encryption (FOCS '15)

        Time-Lock Puzzles from Randomized Encodings (Simons Institute, July '15)

        On Virtual Grey Box Obfuscation for General Circuits (Crypto '14)

        Leakage-Tolerant Computation with Input-Independent Preprocessing (Crypto '14)

Program Committees    

       Crypto      2024 (Area Chair) , 2021

Eurocrypt                                                                                             2021, 2019, 2018, 2017        

        Foundations of Computer Science (FOCS)                                2022, 2018                                                        

        Innovations in Theoretical Computer Science (ITCS)         2023, 2020 

        Public Key Cryptography (PKC)                                                       2017

        Theory of Cryptography Conference (TCC)                             2022, 2019, 2017, 2016A, 2015

Graduate Teaching

        Foundations of Cryptography                              Fall 2022, Fall 2021, Fall 2019, Fall 2017

 Foundations of Cryptography: Advanced Topics     Spring 2023, Spring 2021

 Lattices   Fall 2021, Fall 2019

 Seminar on Cryptographic Protocols               Fall 2021

        Seminar on Encrypted Computation                    Spring 2020

        Seminar on Zero-Knowledge Proofs                     Spring 2019

        Seminar on Advanced Topics in Crypto                     Spring 2022

Undergraduate Teaching

        The Theory Behind Blockchains                        Spring 2019

 Computational Models                                           Spring 2020-2024