Nir Bitansky
I'm an associate professor of computer science at NYU Courant and part of the Theory Group and Cryptography Group.
I'm broadly interested in the theory of computation and the theory of cryptography in particular.
Before joining NYU, I was a faculty member at Tel Aviv University (now on leave). Before that 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
nirbitansky at nyu dot edu
Publications
Dot-Product Proofs and Their Applications
with Prahladh Harsha, Yuval Ishai, Ron Rothblum, and David Wu
FOCS 2024 PDF
Robust Additive Randomized Encodings from IO and Pseudo-non-linear Codes
with Sapir Freizeit
CRYPTO 2024 PDF
Amplification of Non-interactive Zero Knowledge, Revisited
with Nathan Geier
CRYPTO 2024 PDF
Reusable Online-Efficient Commitments
with Omer Paneth and Dana Shamir
CRYPTO 2024
Batch Proofs are Statistically Hiding
with Chethan Kamath, Omer Paneth, Ron Rothblum, and Prashant Vasudevan
STOC 2024 PDF
Non-Interactive Universal Arguments
with Omer Paneth, Dana Shamir, and Tomer Solomon
CRYPTO 2023 PDF
Bootstrapping Homomorphic Encryption via Functional Encryption
with Tomer Solomon
ITCS 2023 PDF
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
CRYPTO , QCRYPT 2022 PDF
Statistically Sender Private OT from LPN and Derandomization
with Sapir Freizeit
CRYPTO 2022 PDF
Non-malleable Commitments Against Quantum Attacks
with Huijia Lin and Omri Shmueli
EUROCRYPT, QCRYPT 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, 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)
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, 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
Thesis
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
Symposium on Theory of Computing (STOC) 2025
Theory of Cryptography Conference (TCC) 2022, 2019, 2017, 2016A, 2015