About

Nir Bitansky is a professor at the Khoury College of Computer Science at Northeastern University, with a primary research focus on cryptography. His work encompasses a variety of topics including computing on encrypted data, program obfuscation, lattice-based cryptography, information-theoretic cryptography, and the foundations of cryptography. He is actively involved in the theory and security groups and has contributed to advancing cryptographic techniques and protocols. Prior to his current position, he was a Josef Raviv Memorial Postdoctoral Fellow at IBM Research T.J. Watson from 2011 to 2013. He earned his PhD in Computer Science from New York University in 2011 under the supervision of Yevgeniy Dodis. His academic background also includes a Bachelor's degree in Mathematics and a Master's degree in Computer Science from Stanford University, completed in 2005. His research has been recognized with awards such as the best paper award at STOC 2023, the 2022 faculty research award from J.P. Morgan, the 2018 Sloan Research Fellowship, and the 2018 NSF CAREER Award. His extensive publication record and active participation in cryptography conferences and program committees underscore his significant contributions to the field.

Research topics

• Computer Science
• Algorithm
• Discrete mathematics
• Mathematics
• Programming language
• Quantum mechanics
• Physics
• Philosophy
• Theoretical computer science

Selected publications

• Succinct Randomized Encodings from Laconic Function Evaluation, Faster and Simpler

  Lecture notes in computer science · 2025-01-01 · 3 citations

  book-chapter1st authorCorresponding
  PublisherDOI

• Additive Randomized Encodings from Public Key Encryption

  Lecture notes in computer science · 2025-01-01

  book-chapter1st authorCorresponding
  PublisherDOI

• Robust Additive Randomized Encodings from IO and Pseudo-Non-linear Codes

  Lecture notes in computer science · 2024-01-01 · 1 citations

  book-chapter1st authorCorresponding
  PublisherDOI

• Amplification of Non-interactive Zero Knowledge, Revisited

  Lecture notes in computer science · 2024-01-01 · 5 citations

  book-chapter1st authorCorresponding
  PublisherDOI

• Dot-Product Proofs and Their Applications

  2024-10-27 · 4 citations

  article1st authorCorresponding

  A dot-product proof (DPP) is a simple probabilistic proof system in which the input statement <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\boldsymbol{x}$</tex> and the proof <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\boldsymbol{\pi}$</tex> are vectors over a finite field <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbb{F}$</tex>, and the proof is verified by making a single dot-product query <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\langle \boldsymbol{q}, (\boldsymbol{x}\Vert\boldsymbol{\pi})\rangle$</tex> jointly to <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\boldsymbol{x}$</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\boldsymbol{\pi}$</tex>. A DPP can be viewed as a 1-query fully linear PCP. We study the feasibility and efficiency of D PPs, obtaining the following results: •Small-field DPP. For any finite field <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbb{F}$</tex> and Boolean circuit <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$C$</tex> of size <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$S$</tex>, there is a D PP for proving that there exists <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\boldsymbol{w}$</tex> such that <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$C(\boldsymbol{x},\ \boldsymbol{w})=1$</tex> with a proof <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\boldsymbol{\pi}$</tex> of length <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$S\cdot \text{poly}(\vert \mathbb{F}\vert)$</tex> and soundness error <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\varepsilon=O(1/\sqrt{\vert \mathbb{F}\vert })$</tex>. We show this error to be asymptotically optimal. In particular, and in contrast to the best known PCPs, there exist strictly linear-length DPPs over constant-size fields. •Large-field DPP. If <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\vert \mathbb{F}\vert\geq$</tex> poly <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(S/\varepsilon)$</tex>, there is a similar DPP with soundness error <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\varepsilon$</tex> and proof length <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(S)$</tex> (in field elements). The above results do not rely on the PCP theorem and their proofs are considerably simpler. We apply our DPP constructions toward two kinds of applications. •Hardness of approximation. We obtain a simple proof for the NP-hardness of approximating MAXLIN (with dense instances) over any finite field <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbb{F}$</tex> up to some constant factor <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$c &gt; 1$</tex>, independent of F. Unlike previous PCP-based proofs, our proof yields exponential-time hardness under the exponential time hypothesis (ETH). •Succinct arguments. We improve the concrete efficiency of succinct interactive arguments in the generic group model using input-independent preprocessing. In particular, the communication is comparable to sending two group elements and the verifier's computation is dominated by a single group exponentiation. We also show how to use DPPs together with linear-only encryption to construct succinct commit-and-prove arguments.

  PublisherDOI

• Reusable Online-Efficient Commitments

  Lecture notes in computer science · 2024-01-01

  book-chapter1st authorCorresponding
  PublisherDOI

• Batch Proofs Are Statistically Hiding

  2024-06-10 · 11 citations

  articleOpen access1st authorCorresponding

  Batch proofs are proof systems that convince a verifier that x1,…,xt ∈ L, for some NP language L, with communication that is much shorter than sending the t witnesses. In the case of statistical soundness (where the cheating prover is unbounded but the honest prover is efficient given the witnesses), interactive batch proofs are known for UP, the class of unique-witness NP languages. In the case of computational soundness (where both honest and dishonest provers are efficient), non-interactive solutions are now known for all of NP, assuming standard lattice or group assumptions. We exhibit the first negative results regarding the existence of batch proofs and arguments: - Statistically sound batch proofs for L imply that L has a statistically witness indistinguishable (SWI) proof, with inverse polynomial SWI error, and a non-uniform honest prover. The implication is unconditional for obtaining honest-verifier SWI or for obtaining full-fledged SWI from public-coin protocols, whereas for private-coin protocols full-fledged SWI is obtained assuming one-way functions. This poses a barrier for achieving batch proofs beyond UP (where witness indistinguishability is trivial). In particular, assuming that NP does not have SWI proofs, batch proofs for all of NP do not exist. - Computationally sound batch proofs (a.k.a batch arguments or BARGs) for NP, together with one-way functions, imply statistical zero-knowledge (SZK) arguments for NP with roughly the same number of rounds, an inverse polynomial zero-knowledge error, and non-uniform honest prover. Thus, constant-round interactive BARGs from one-way functions would yield constant-round SZK arguments from one-way functions. This would be surprising as SZK arguments are currently only known assuming constant-round statistically-hiding commitments. We further prove new positive implications of non-interactive batch arguments to non-interactive zero knowledge arguments (with explicit uniform prover and verifier): - Non-interactive BARGs for NP, together with one-way functions, imply non-interactive computational zero-knowledge arguments for NP. Assuming also dual-mode commitments, the zero knowledge can be made statistical. Both our negative and positive results stem from a new framework showing how to transform a batch protocol for a language L into an SWI protocol for L.

  PublisherOA PDFDOI

• Non-interactive Universal Arguments

  Lecture notes in computer science · 2023-01-01 · 1 citations

  book-chapter1st author
  PublisherDOI

• A Note on Perfect Correctness by Derandomization

  Journal of Cryptology · 2022-05-13 · 3 citations

  articleOpen access1st authorCorresponding

  Abstract We show a general compiler that transforms a large class of erroneous cryptographic schemes (such as public-key encryption, indistinguishability obfuscation, and secure multiparty computation schemes) into perfectly correct ones. The transformation works for schemes that are correct on all inputs with probability noticeably larger than half , and are secure under parallel repetition. We assume the existence of one-way functions and of functions with deterministic (uniform) time complexity $$2^{O(n)}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mn>2</mml:mn><mml:mrow><mml:mi>O</mml:mi><mml:mo>(</mml:mo><mml:mi>n</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:msup></mml:math> and non-deterministic circuit complexity $$2^{\Omega (n)}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mn>2</mml:mn><mml:mrow><mml:mi>Ω</mml:mi><mml:mo>(</mml:mo><mml:mi>n</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:msup></mml:math> . Our transformation complements previous results that showed how public-key encryption and indistinguishability obfuscation that err on a noticeable fraction of inputs can be turned into ones that for all inputs are often correct, showing that they can be made perfectly correct. The technique relies on the idea of “reverse randomization” [Naor, Crypto 1989] and on Nisan–Wigderson style derandomization, previously used in cryptography to remove interaction from witness-indistinguishable proofs and commitment schemes [Barak, Ong and Vadhan, Crypto 2003].

  PublisherOA PDFDOI

• Statistically Sender-Private OT from LPN and Derandomization

  Lecture notes in computer science · 2022-01-01 · 10 citations

  book-chapter1st authorCorresponding
  PublisherDOI

Frequent coauthors

• Omer Paneth

  55 shared

• Vinod Vaikuntanathan

  53 shared

• Sanjam Garg

  40 shared

• Ran Canetti

  40 shared

• Abhishek Jain

  Johns Hopkins University

  39 shared

• Justin Holmgren

  37 shared

• Rafael Pass

  37 shared

• Sidharth Telang

  Johns Hopkins University

  37 shared

Labs

• Wichs LabPI

Education

• Ph.D.

  MIT

• Other

  Tel Aviv University's School of Computer Science

Awards & honors

• Crypto 2024 Area Chair