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.
I completed my Ph.D. at Tel Aviv University where I was advised by Ran Canetti.
I then spent three years as a postdoctoral researcher at MIT CSAIL hosted by Vinod Vaikuntanathan.
Contact
Email: nirbitan at tau dot ac dot il
Office: Check Point Building 344
Publications
Constructive Post-quantum Reductions
with Zvika Brakerski and Yael Tauman Kalai
Manuscript PDF
Statistically Sender Private OT from LPN and Derandomization
with Sapir Freizeit
Manuscript PDF
Non-malleable Commitments Against Quantum Attacks
with Huijia Lin and Omri Shmueli
EUROCRYPT 2022 PDF
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
CRYPTO 2019 PDF
Weak Zero-Knowledge Beyond the Black-Box Barrier
with Dakshita Khurana and Omer Paneth
STOC 2019 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 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)
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
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
Obfuscation for Evasive Functions
with Boaz Barak, Ran Canetti, Yael 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
Succinct Non-Interactive Arguments via Linear Interactive Proofs
with Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, Omer Paneth
TCC 2013 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
Thesis
Getting Inside the Adversary's Head: New Directions in Non-Black-Box Knowledge Extraction
Tel Aviv University 2015 PDF
Some Videotaped Talks
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 2021
Eurocrypt 2021, 2019, 2018, 2017
Foundations of Computer Science (FOCS) 2022, 2018
Innovations in Theoretical Computer Science (ITCS) 2020
Public Key Cryptography (PKC) 2017
Theory of Cryptography Conference (TCC) 2022, 2019, 2017, 2016A, 2015
Graduate Teaching
Foundations of Cryptography Fall 2021, Fall 2019, Fall 2017
Foundations of Cryptography: Advanced Topics 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-2022