Yael Tauman Kalai

According to our database, Yael Tauman Kalai authored at least 119 papers between 2001 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

Polynomial Size, Short-Circuit Resilient Circuits for NC.

Yael Tauman Kalai, Raghuvansh R. Saxena

Proceedings of the 16th Innovations in Theoretical Computer Science Conference, 2025

2024

SNARGs under LWE via Propositional Proofs.

Zhengzhong Jin, Yael Tauman Kalai, Alex Lombardi, Vinod Vaikuntanathan

IACR Cryptol. ePrint Arch., 2024

Universal SNARGs for NP from Proofs of Correctness.

Zhengzhong Jin, Yael Tauman Kalai, Alex Lombardi, Surya Mathialagan

IACR Cryptol. ePrint Arch., 2024

Classical Commitments to Quantum States.

Sam Gunn, Yael Tauman Kalai, Anand Natarajan, Agi Villanyi

IACR Cryptol. ePrint Arch., 2024

Somewhat Homomorphic Encryption from Linear Homomorphism and Sparse LPN.

Henry Corrigan-Gibbs, Alexandra Henzinger, Yael Kalai, Vinod Vaikuntanathan

IACR Cryptol. ePrint Arch., 2024

2023

SNARGs for Monotone Policy Batch NP.

Zvika Brakerski, Maya Farber Brodsky, Yael Tauman Kalai, Alex Lombardi, Omer Paneth

IACR Cryptol. ePrint Arch., 2023

On the works of Avi Wigderson.

Boaz Barak, Yael Kalai, Ran Raz, Salil P. Vadhan, Nisheeth K. Vishnoi

CoRR, 2023

2022

Efficient Multiparty Interactive Coding - Part II: Non-Oblivious Noise.

Ran Gelles, Yael Tauman Kalai, Govind Ramnarayan

IEEE Trans. Inf. Theory, 2022

Quantum Advantage from Any Non-Local Game.

Yael Tauman Kalai, Alex Lombardi, Vinod Vaikuntanathan, Lisa Yang

IACR Cryptol. ePrint Arch., 2022

Boosting Batch Arguments and RAM Delegation.

Yael Tauman Kalai, Alex Lombardi, Vinod Vaikuntanathan, Daniel Wichs

IACR Cryptol. ePrint Arch., 2022

SNARGs and PPAD Hardness from the Decisional Diffie-Hellman Assumption.

Yael Tauman Kalai, Alex Lombardi, Vinod Vaikuntanathan

IACR Cryptol. ePrint Arch., 2022

Rate-1 Non-Interactive Arguments for Batch-NP and Applications.

Lalita Devadas, Rishab Goyal, Yael Kalai, Vinod Vaikuntanathan

IACR Cryptol. ePrint Arch., 2022

Constructive Post-Quantum Reductions.

Nir Bitansky, Zvika Brakerski, Yael Tauman Kalai

IACR Cryptol. ePrint Arch., 2022

Verifiable Private Information Retrieval.

Shany Ben-David, Yael Tauman Kalai, Omer Paneth

IACR Cryptol. ePrint Arch., 2022

Succinct Classical Verification of Quantum Computation.

James Bartusek, Yael Tauman Kalai, Alex Lombardi, Fermi Ma, Giulio Malavolta, Vinod Vaikuntanathan, Thomas Vidick, Lisa Yang

IACR Cryptol. ePrint Arch., 2022

Interactive Coding with Small Memory.

Klim Efremenko, Bernhard Haeupler, Gillat Kol, Nicolas Resch, Raghuvansh Saxena, Yael Tauman Kalai

Electron. Colloquium Comput. Complex., 2022

Circuits Resilient to Short-Circuit Errors.

Klim Efremenko, Bernhard Haeupler, Yael Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh Saxena

Electron. Colloquium Comput. Complex., 2022

Interactive error correcting codes over binary erasure channels resilient to > ½ adversarial corruption.

Meghal Gupta, Yael Tauman Kalai, Rachel Yun Zhang

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

2021

Efficient Multiparty Interactive Coding - Part I: Oblivious Insertions, Deletions and Substitutions.

Ran Gelles, Yael Tauman Kalai, Govind Ramnarayan

IEEE Trans. Inf. Theory, 2021

Somewhere Statistical Soundness, Post-Quantum Security, and SNARGs for P.

Yael Tauman Kalai, Vinod Vaikuntanathan, Rachel Yun Zhang

IACR Cryptol. ePrint Arch., 2021

Interactive Error Correcting Codes Over Binary Erasure Channels Resilient to $>\frac12$ Adversarial Corruption.

Meghal Gupta, Yael Tauman Kalai, Rachel Yun Zhang

IACR Cryptol. ePrint Arch., 2021

Somewhere Statistical Soundness, Post-Quantum Security, and SNARGs.

Yael Tauman Kalai, Vinod Vaikuntanathan, Rachel Yun Zhang

Proceedings of the Theory of Cryptography - 19th International Conference, 2021

2020

SNARGs for Bounded Depth Computations from Sub-Exponential LWE.

Yael Tauman Kalai, Rachel Yun Zhang

IACR Cryptol. ePrint Arch., 2020

SNARGs for Bounded Depth Computations and PPAD Hardness from Sub-Exponential LWE.

Ruta Jawale, Yael Tauman Kalai, Dakshita Khurana, Rachel Yun Zhang

IACR Cryptol. ePrint Arch., 2020

Privacy-Preserving Automated Exposure Notification.

Ran Canetti, Yael Tauman Kalai, Anna Lysyanskaya, Ronald L. Rivest, Adi Shamir, Emily Shen, Ari Trachtenberg, Mayank Varia, Daniel J. Weitzner

IACR Cryptol. ePrint Arch., 2020

Deterministic and Efficient Interactive Coding from Hard-to-Decode Tree Codes.

Zvika Brakerski, Yael Tauman Kalai, Raghuvansh Saxena

Electron. Colloquium Comput. Complex., 2020

Non-signaling proofs with o(√ log n) provers are in PSPACE.

Dhiraj Holden, Yael Tauman Kalai

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Witness Indistinguishability for Any Single-Round Argument with Applications to Access Control.

Zvika Brakerski, Yael Kalai

Proceedings of the Public-Key Cryptography - PKC 2020, 2020

Beyond Perturbations: Learning Guarantees with Arbitrary Adversarial Test Examples.

Shafi Goldwasser, Adam Tauman Kalai, Yael Kalai, Omar Montasser

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Identifying unpredictable test examples with worst-case guarantees.

Shafi Goldwasser, Adam Tauman Kalai, Yael Tauman Kalai, Omar Montasser

Proceedings of the Information Theory and Applications Workshop, 2020

Low Error Efficient Computational Extractors in the CRS Model.

Ankit Garg, Yael Tauman Kalai, Dakshita Khurana

Proceedings of the Advances in Cryptology - EUROCRYPT 2020, 2020

Delegation with Updatable Unambiguous Proofs and PPAD-Hardness.

Yael Tauman Kalai, Omer Paneth, Lisa Yang

Proceedings of the Advances in Cryptology - CRYPTO 2020, 2020

2019

A Survey of Leakage-Resilient Cryptography.

Yael Tauman Kalai, Leonid Reyzin

IACR Cryptol. ePrint Arch., 2019

How to Delegate Computations Publicly.

Yael Kalai, Omer Paneth, Lisa Yang

IACR Cryptol. ePrint Arch., 2019

Computational Extractors with Negligible Error in the CRS Model.

Ankit Garg, Yael Tauman Kalai, Dakshita Khurana

IACR Cryptol. ePrint Arch., 2019

Fully Homomorphic NIZK and NIWI Proofs.

Prabhanjan Ananth, Apoorvaa Deshpande, Yael Tauman Kalai, Anna Lysyanskaya

IACR Cryptol. ePrint Arch., 2019

No-Signaling Proofs with O(√(log n)) Provers are in PSPACE.

Dhiraj Holden, Yael Kalai

CoRR, 2019

Efficient Multiparty Interactive Coding for Insertions, Deletions, and Substitutions.

Ran Gelles, Yael Tauman Kalai, Govind Ramnarayan

Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

A survey of leakage-resilient cryptography.

Yael Tauman Kalai, Leonid Reyzin

Proceedings of the Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, 2019

2018

Special Section on the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC 2015).

Costis Daskalakis, Yael Kalai, Sandy Irani

SIAM J. Comput., 2018

On Publicly Verifiable Delegation From Standard Assumptions.

Yael Kalai, Omer Paneth, Lisa Yang

IACR Cryptol. ePrint Arch., 2018

Statistical Witness Indistinguishability (and more) in Two Messages.

Yael Tauman Kalai, Dakshita Khurana, Amit Sahai

IACR Cryptol. ePrint Arch., 2018

Proofs of Ignorance and Applications to 2-Message Witness Hiding.

Apoorvaa Deshpande, Yael Kalai

IACR Cryptol. ePrint Arch., 2018

Monotone Batch NP-Delegation with Applications to Access Control.

Zvika Brakerski, Yael Tauman Kalai

IACR Cryptol. ePrint Arch., 2018

A Lower Bound for Adaptively-Secure Collective Coin-Flipping Protocols.

Ilan Komargodski, Ran Raz, Yael Tauman Kalai

Electron. Colloquium Comput. Complex., 2018

Non-Interactive Non-Malleability from Quantum Supremacy.

Yael Kalai, Dakshita Khurana

Electron. Colloquium Comput. Complex., 2018

Interactive Coding with Constant Round and Communication Blowup.

Klim Efremenko, Elad Haramaty, Yael Kalai

Electron. Colloquium Comput. Complex., 2018

Non-Interactive Delegation for Low-Space Non-Deterministic Computation.

Saikrishna Badrinarayanan, Yael Kalai, Dakshita Khurana, Amit Sahai, Daniel Wichs

Electron. Colloquium Comput. Complex., 2018

Succinct delegation for low-space non-deterministic computation.

Saikrishna Badrinarayanan, Yael Tauman Kalai, Dakshita Khurana, Amit Sahai, Daniel Wichs

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

2017

Distinguisher-Dependent Simulation in Two Rounds and its Applications.

Abhishek Jain, Yael Tauman Kalai, Dakshita Khurana, Ron Rothblum

IACR Cryptol. ePrint Arch., 2017

Succinct Spooky Free Compilers Are Not Black Box Sound.

Zvika Brakerski, Yael Tauman Kalai, Renen Perlman

IACR Cryptol. ePrint Arch., 2017

Promise Zero Knowledge and its Applications to Round Optimal MPC.

Saikrishna Badrinarayanan, Vipul Goyal, Abhishek Jain, Yael Tauman Kalai, Dakshita Khurana, Amit Sahai

IACR Cryptol. ePrint Arch., 2017

Delegating Computation: Interactive Proofs for Muggles.

Shafi Goldwasser, Guy N. Rothblum, Yael Tauman Kalai

Electron. Colloquium Comput. Complex., 2017

Constant-Rate Interactive Coding Is Impossible, Even In Constant-Degree Networks.

Ran Gelles, Yael Tauman Kalai

Electron. Colloquium Comput. Complex., 2017

Multi-Collision Resistance: A Paradigm for Keyless Hash Functions.

Nir Bitansky, Omer Paneth, Yael Tauman Kalai

Electron. Colloquium Comput. Complex., 2017

On Virtual Grey Box Obfuscation for General Circuits.

Nir Bitansky, Ran Canetti, Yael Tauman Kalai, Omer Paneth

Algorithmica, 2017

Non-interactive delegation and batch NP verification from standard computational assumptions.

Zvika Brakerski, Justin Holmgren, Yael Tauman Kalai

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

2016

From Obfuscation to the Security of Fiat-Shamir for Proofs.

Yael Tauman Kalai, Guy N. Rothblum, Ron D. Rothblum

IACR Cryptol. ePrint Arch., 2016

3-Message Zero Knowledge Against Human Ignorance.

Nir Bitansky, Zvika Brakerski, Yael Tauman Kalai, Omer Paneth, Vinod Vaikuntanathan

IACR Cryptol. ePrint Arch., 2016

Non-Interactive RAM and Batch NP Delegation from any PIR.

Zvika Brakerski, Justin Holmgren, Yael Tauman Kalai

Electron. Colloquium Comput. Complex., 2016

On the Space Complexity of Linear Programming with Preprocessing.

Yael Tauman Kalai, Ran Raz, Oded Regev

Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

2015

Delegating RAM Computations.

Yael Tauman Kalai, Omer Paneth

IACR Cryptol. ePrint Arch., 2015

Adaptively Secure Coin-Flipping, Revisited.

Shafi Goldwasser, Yael Tauman Kalai, Sunoo Park

IACR Cryptol. ePrint Arch., 2015

Cryptographic Assumptions: A Position Paper.

Shafi Goldwasser, Yael Tauman Kalai

IACR Cryptol. ePrint Arch., 2015

On Obfuscation with Random Oracles.

Ran Canetti, Yael Tauman Kalai, Omer Paneth

IACR Cryptol. ePrint Arch., 2015

Compressing Communication in Distributed Protocols.

Yael Tauman Kalai, Ilan Komargodski

Electron. Colloquium Comput. Complex., 2015

Interactive Coding for Multiparty Protocols.

Abhishek Jain, Yael Tauman Kalai, Allison Bishop Lewko

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Arguments of Proximity - [Extended Abstract].

Yael Tauman Kalai, Ron D. Rothblum

Proceedings of the Advances in Cryptology - CRYPTO 2015, 2015

2014

Fast Interactive Coding against Adversarial Noise.

Zvika Brakerski, Yael Tauman Kalai, Moni Naor

J. ACM, 2014

On the Space Complexity of Linear Programming with Preprocessing.

Yael Tauman Kalai, Ran Raz

Electron. Colloquium Comput. Complex., 2014

Leakage-resilient coin tossing.

Elette Boyle, Shafi Goldwasser, Yael Tauman Kalai

Distributed Comput., 2014

The impossibility of obfuscation with a universal simulator.

Henry Cohn, Shafi Goldwasser, Yael Tauman Kalai

CoRR, 2014

Securing Circuits and Protocols against 1/poly(k) Tampering Rate.

Dana Dachman-Soled, Yael Tauman Kalai

Proceedings of the Theory of Cryptography - 11th Theory of Cryptography Conference, 2014

The Impossibility of Obfuscation with Auxiliary Input or a Universal Simulator.

Nir Bitansky, Ran Canetti, Henry Cohn, Shafi Goldwasser, Yael Tauman Kalai, Omer Paneth, Alon Rosen

Proceedings of the Advances in Cryptology - CRYPTO 2014, 2014

2013

Overcoming the Worst-Case Curse for Cryptographic Constructions.

Shafi Goldwasser, Yael Tauman Kalai, Raluca A. Popa, Vinod Vaikuntanathan, Nickolai Zeldovich

IACR Cryptol. ePrint Arch., 2013

A Note on the Impossibility of Obfuscation with Auxiliary Input.

Shafi Goldwasser, Yael Tauman Kalai

IACR Cryptol. ePrint Arch., 2013

Protecting Obfuscation Against Algebraic Attacks.

Boaz Barak, Sanjam Garg, Yael Tauman Kalai, Omer Paneth, Amit Sahai

IACR Cryptol. ePrint Arch., 2013

Obfuscation for Evasive Functions.

Boaz Barak, Nir Bitansky, Ran Canetti, Yael Tauman Kalai, Omer Paneth, Amit Sahai

IACR Cryptol. ePrint Arch., 2013

How to Delegate Computations: The Power of No-Signaling Proofs.

Yael Tauman Kalai, Ran Raz, Ron Rothblum

Electron. Colloquium Comput. Complex., 2013

Why "Fiat-Shamir for Proofs" Lacks a Proof.

Nir Bitansky, Dana Dachman-Soled, Sanjam Garg, Abhishek Jain, Yael Tauman Kalai, Adriana López-Alt, Daniel Wichs

Proceedings of the Theory of Cryptography - 10th Theory of Cryptography Conference, 2013

Delegation for bounded space.

Yael Tauman Kalai, Ran Raz, Ron D. Rothblum

Proceedings of the Symposium on Theory of Computing Conference, 2013

Reusable garbled circuits and succinct functional encryption.

Shafi Goldwasser, Yael Tauman Kalai, Raluca A. Popa, Vinod Vaikuntanathan, Nickolai Zeldovich

Proceedings of the Symposium on Theory of Computing Conference, 2013

How to Run Turing Machines on Encrypted Data.

Shafi Goldwasser, Yael Tauman Kalai, Raluca A. Popa, Vinod Vaikuntanathan, Nickolai Zeldovich

Proceedings of the Advances in Cryptology - CRYPTO 2013, 2013

Secure Computation against Adaptive Auxiliary Information.

Elette Boyle, Sanjam Garg, Abhishek Jain, Yael Tauman Kalai, Amit Sahai

Proceedings of the Advances in Cryptology - CRYPTO 2013, 2013

2012

Smooth Projective Hashing and Two-Message Oblivious Transfer.

Shai Halevi, Yael Tauman Kalai

J. Cryptol., 2012

Succinct Functional Encryption and Applications: Reusable Garbled Circuits and Beyond.

Shafi Goldwasser, Yael Tauman Kalai, Raluca A. Popa, Vinod Vaikuntanathan, Nickolai Zeldovich

IACR Cryptol. ePrint Arch., 2012

Securing Circuits Against Constant-Rate Tampering.

Dana Dachman-Soled, Yael Tauman Kalai

IACR Cryptol. ePrint Arch., 2012

On the (In)security of the Fiat-Shamir Paradigm, Revisited.

Dana Dachman-Soled, Abhishek Jain, Yael Tauman Kalai, Adriana López-Alt

IACR Cryptol. ePrint Arch., 2012

Efficient Interactive Coding Against Adversarial Noise.

Zvika Brakerski, Yael Tauman Kalai

Electron. Colloquium Comput. Complex., 2012

Multiparty computation secure against continual memory leakage.

Elette Boyle, Shafi Goldwasser, Abhishek Jain, Yael Tauman Kalai

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Formulas Resilient to Short-Circuit Errors.

Yael Tauman Kalai, Allison B. Lewko, Anup Rao

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011

Memory Delegation.

Kai-Min Chung, Yael Tauman Kalai, Feng-Hao Liu, Ran Raz

IACR Cryptol. ePrint Arch., 2011

A Parallel Repetition Theorem for Leakage Resilience.

Zvika Brakerski, Yael Tauman Kalai

IACR Cryptol. ePrint Arch., 2011

Program Obfuscation with Leaky Hardware.

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

IACR Cryptol. ePrint Arch., 2011

Leaky Pseudo-Entropy Functions.

Mark Braverman, Avinatan Hassidim, Yael Tauman Kalai

Proceedings of the Innovations in Computer Science, 2011

Cryptography with Tamperable and Leaky Memory.

Yael Tauman Kalai, Bhavana Kanukurthi, Amit Sahai

Proceedings of the Advances in Cryptology - CRYPTO 2011, 2011

2010

Improved Delegation of Computation using Fully Homomorphic Encryption.

Kai-Min Chung, Yael Tauman Kalai, Salil P. Vadhan

IACR Cryptol. ePrint Arch., 2010

On Symmetric Encryption and Point Obfuscation.

Ran Canetti, Yael Tauman Kalai, Mayank Varia, Daniel Wichs

IACR Cryptol. ePrint Arch., 2010

Overcoming the Hole In The Bucket: Public-Key Cryptography Resilient to Continual Memory Leakage.

Zvika Brakerski, Yael Tauman Kalai, Jonathan Katz, Vinod Vaikuntanathan

IACR Cryptol. ePrint Arch., 2010

A Framework for Efficient Signatures, Ring Signatures and Identity Based Encryption in the Standard Model.

Zvika Brakerski, Yael Tauman Kalai

IACR Cryptol. ePrint Arch., 2010

Public-Key Encryption Schemes with Auxiliary Inputs.

Yevgeniy Dodis, Shafi Goldwasser, Yael Tauman Kalai, Chris Peikert, Vinod Vaikuntanathan

Proceedings of the Theory of Cryptography, 7th Theory of Cryptography Conference, 2010

Robustness of the Learning with Errors Assumption.

Shafi Goldwasser, Yael Tauman Kalai, Chris Peikert, Vinod Vaikuntanathan

Proceedings of the Innovations in Computer Science, 2010

2009

Black-Box Circular-Secure Encryption Beyond Affine Functions.

Zvika Brakerski, Shafi Goldwasser, Yael Tauman Kalai

IACR Cryptol. ePrint Arch., 2009

On cryptography with auxiliary input.

Yevgeniy Dodis, Yael Tauman Kalai, Shachar Lovett

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

2-Source Extractors under Computational Assumptions and Cryptography with Defective Randomness.

Yael Tauman Kalai, Xin Li, Anup Rao

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

Probabilistically Checkable Arguments.

Yael Tauman Kalai, Ran Raz

Proceedings of the Advances in Cryptology, 2009

2008

Network Extractor Protocols.

Yael Tauman Kalai, Xin Li, Anup Rao, David Zuckerman

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

One-Time Programs.

Shafi Goldwasser, Yael Tauman Kalai, Guy N. Rothblum

Proceedings of the Advances in Cryptology, 2008

2007

Concurrent Composition of Secure Protocols in the Timing Model.

Yael Tauman Kalai, Yehuda Lindell, Manoj Prabhakaran

J. Cryptol., 2007

Interactive PCP.

Yael Tauman Kalai, Ran Raz

Electron. Colloquium Comput. Complex., 2007

2006

Attacks on the Fiat-Shamir paradigm and program obfuscation.

Yael Tauman Kalai

PhD thesis, 2006

Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP.

Yael Tauman Kalai, Ran Raz

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

How to Leak a Secret: Theory and Applications of Ring Signatures.

Ronald L. Rivest, Adi Shamir, Yael Tauman

Proceedings of the Theoretical Computer Science, 2006

2005

Concurrent general composition of secure protocols in the timing model.

Yael Tauman Kalai, Yehuda Lindell, Manoj Prabhakaran

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

On the Impossibility of Obfuscation with Auxiliary Input.

Shafi Goldwasser, Yael Tauman Kalai

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

Smooth Projective Hashing and Two-Message Oblivious Transfer.

Yael Tauman Kalai

Proceedings of the Advances in Cryptology, 2005

2003

On the (In)security of the Fiat-Shamir Paradigm.

Shafi Goldwasser, Yael Tauman

Electron. Colloquium Comput. Complex., 2003

2001

Improved Online/Offline Signature Schemes.

Adi Shamir, Yael Tauman

Proceedings of the Advances in Cryptology, 2001

How to Leak a Secret.

Ronald L. Rivest, Adi Shamir, Yael Tauman

Proceedings of the Advances in Cryptology, 2001