Publications
Conflict Checkable and Decodable Codes and Their Applications
Benny Applebaum and Eliran Kachlon
Proc. 35th SODA, 2024
Available as an ECCC and eprint report.
Advisor-Verifier-Prover Games and the Hardness of Information-Theoretic Cryptography
Benny Applebaum and Oded Nir
Proc. 64th FOCS, 2023
Available as an ECCC and eprint report.
How to Recover a Secret with O(n) Additions
Benny Applebaum, Oded Nir, and Benny Pinkas
Proc. 43rd Crypto, 2023
Available as an ECCC and eprint report.
Succinct Computational Secret Sharing
Benny Applebaum, Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Tianren Liu and Vinod Vaikuntanathan
Proc. 55th STOC, 2023
Available as an ECCC and eprint report.
The Round Complexity of Statistical MPC with Optimal Resiliency
Benny Applebaum, Eliran Kachlon and Arpita Patra
Proc. 55th STOC, 2023
Available as an ECCC and eprint report.
Actively Secure Arithmetic Computation and VOLE with Constant Computational Overhead
Benny Applebaum and Niv Konstantini
Proc. 42nd Eurocrypt, 2023
Available as an eprint report.
Quadratic Multiparty Randomized Encodings Beyond Honest Majority and Their Applications
Benny Applebaum, Yuval Ishai, Or Karni, Arpita Patra
Proc. 42nd Crypto, 2022
Available as an eprint report.
Verifiable Relation Sharing and Multi-Verifier Zero-Knowledge in Two Rounds: Trading NIZKs with Honest Majority
Benny Applebaum and Eliran Kachlon and Arpita Patra
Proc. 42nd Crypto, 2022
Available as an eprint report.
Secret Sharing, Slice Formulas, and Monotone Real Circuits
Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, Toniann Pitassi
Proc. of 13th, ITCS 2022
Available as an ECCC report
Round-optimal Honest-majority MPC in Minicrypt and with Everlasting Security
Benny Applebaum and Eliran Kachlon and Arpita Patra
Proc. 20th TCC, 2022
Available as an eprint report.
On Actively-Secure Elementary MPC Reductions
Benny Applebaum and Aarushi Goel
Proc. 19th TCC, 2021
Available as an eprint report.
Upslices, Downslices, and Secret-Sharing with Complexity of 1.5^n
Benny Applebaum and Oded Nir
Proc. 41st Crypto, 2021
Available as an ECCC and eprint report.
On the Randomness Complexity of Interactive Proofs and Statistical Zero-Knowledge Proofs
Benny Applebaum and Eyal Golombek
Proc. 2nd ITC, 2021
Available as an eprint report.
The Resiliency of MPC with Low Interaction: The Benefit of Making Errors
Benny Applebaum and Eliran Kachlon and Arpita Patra
Proc. 18th TCC, 2020
Available as an eprint report.
The Round Complexity of Perfect MPC with Active Security and Optimal Resiliency
Benny Applebaum and Eliran Kachlon and Arpita Patra
Proc. 61st FOCS, 2020
Available as an ECCC and eprint report.
Better Secret-Sharing via Robust Conditional Disclosure of Secrets
Benny Applebaum and Amos Beimel and Oded Nir and Naty Peter
Proc. 52nd STOC, 2020
Available as an ECCC and eprint report.
Separating Two-Round Secure Computation From Oblivious Transfer
Benny Applebaum and Zvika Brakerski and Sanjam Garg and Yuval Ishai and Akshayaram Srinivasan
Proc. 11th ITCS, 2020
Available as eprint report.
Sampling Graphs without Forbidden Subgraphs and Almost-Explicit Unbalanced Expanders
Benny Applebaum and Eliran Kachlon
Proc. 60th FOCS, 2019
Available as an ECCC report.
Secret-Sharing Schemes for General and Uniform Access Structures
Benny Applebaum and Amos Beimel and Oriol Farràs and Oded Nir and Naty Peter
Proc. 38th EUROCRYPT, 2019
Available as eprint report.
Degree 2 is Complete for the Round-Complexity of Malicious MPC
Benny Applebaum and Zvika Brakerski and Rotem Tsabary
Proc. 38th EUROCRYPT, 2019
Available as eprint report.
Placing Conditional Disclosure of Secrets in the Communication Complexity Universe
Benny Applebaum and Prashant Nalini Vasudevan
Journal of Cryptology 34(2): 11 (2021)
Conference version: Proc. 10th ITCS, 2019
Available as an ECCC and eprint report.
Perfect Secure Computation in Two Rounds
Benny Applebaum and Zvika Brakerski and Rotem Tsabary
SIAM J. Comput. 50(1): 68-97 (2021)
Conference version: Proc. 16th TCC, 2018
Available as eprint report.
On the Power of Amortization in Secret Sharing: d-Uniform Secret Sharing and CDS with Constant Information Rate
Benny Applebaum and Barak Arkis
ACM Trans. Comput. Theory 12(4): 24:1-24:21 (2020)
Conference version: Proc. 16th TCC, 2018
Available as an ECCC and eprint report.
The Communication Complexity of Private Simultaneous Messages, Revisited.
Benny Applebaum, and Thomas Holenstein, and Manoj Mishra, and Ofer Shayevitz
J. Cryptol. 33(3): 917-953 (2020)
Proc. 37th EUROCRYPT, 2018
Available as an ECCC and eprint report.
Exponentially-Hard gap-CSP and local PRG via Local Hardcore Functions
Benny Applebaum
Proc. 58th FOCS, 2017
Available as an ECCC report.
Secure Arithmetic Computation with Constant Computational Overhead
Benny Applebaum and Ivan Damgård and Yuval Ishai and Michael Nielsen and Lior Zichron
Proc. 37th CRYPTO, 2017
Available as an eprint report.
See also Lior Zichron's thesis.
Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-bounds, and Separations
Benny Applebaum and Barak Arkis and Pavel Raykov and Prashant Nalini Vasudevan
SIAM J. Comput. 50(1): 32-67, 2021
Conference version in Proc. 37th CRYPTO, 2017
Available as an ECCC and eprint report.
Low-Complexity Cryptographic Hash Functions
Benny Applebaum and Naama Haramaty and Yuval Ishai and Eyal Kushilevitz and Vinod Vaikuntanathan
Proc. 8th ITCS, 2017
Available as an ECCC and eprint report.
Fast Pseudorandom Functions Based on Expander Graphs
Benny Applebaum and Pavel Raykov
Proc. 14th TCC, 2016B
Available as an ECCC report.
On the Relationship between Statistical Zero-Knowledge and Statistical Randomized Encodings
Benny Applebaum and Pavel Raykov
Computational Complexity, 2018
Conference version in Proc. 36th CRYPTO, 2016.
Available as an ECCC report.
Algebraic Attacks against Random Local Functions and Their Countermeasures
Benny Applebaum and Shachar Lovett
SIAM J. Comput. 47(1): 52-79, 2018
Conference version in Proc. 48th STOC, 2016.
Available as an ECCC report.
From Private Simultaneous Messages to Zero-Information Arthur-Merlin Protocols and Back
Benny Applebaum and Pavel Raykov
Journal of Cryptology 30(4), 961-988, 2017.
Conference version in Proc. 13th TCC, 2016.
Available as an eprint report.
Related-Key Secure Pseudorandom Functions: The Case of Additive Attacks
Benny Applebaum and Eyal Widder
Available as an eprint report
Minimizing Locality of One-Way Functions via Semi-Private Randomized Encodings.
Benny Applebaum, Yuval Ishai and Eyal Kushilevitz.
Journal of Cryptology 31(1):1-22, 2018.
Available as an ECCC report.
Subsumes the manuscript "On One-Way Functions with Optimal Locality".
Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterminsitic Reductions
Benny Applebaum and Sergei Artemenko and Ronen Shaltiel and Guang Yang.
Computational Complexity, 25(2), 349-418, 2016, Special issue for CCC 2015.
Conference version in Proc. 30th CCC, 2015.
Available as an ECCC report.
Obfuscating Circuits via Composite-Order Graded Encoding
Benny Applebaum and Zvika Brakerski.
J. Cryptol. 34(2): 14 (2021)
Proc. 12th TCC, 2015.
Available as an eprint report.
Arithmetic Cryptography
Benny Applebaum, Jonathan Avron, and Christina Brzuska.
Journal of the ACM, 64(2), 2017
Proc. 6th ITCS, 2015.
Available as an ECCC report.
See also talks at GTACS and at the Simons Institute
Deterministic Rateless Codes for the Binary Symmetric Channel
Benny Applebaum, Liron David, and Guy Even.
Theory Comput. 14(1): 1-29 (2018)
Proc. 6th ITCS, 2015.
Available as an arxiv report.
Bootstrapping Obfuscators via Fast Pseudorandom Functions
Benny Applebaum.
Proc. 20th ASIACRYPT, 2014.
Available as an eprint report.
Encoding Functions with Constant Online Rate or How to Compress Keys in Garbled Circuits
Benny Applebaum, Yuval Ishai, Eyal Kushilevitz and Brent Waters.
SICOMP, 44(2), 433-466, 2015. (pdf)
Conference version in Proc. 33rd CRYPTO, 2013.
Available as an eprint report.
Locally Computable UOWHF with Linear Shrinkage
Benny Applebaum and Yoni Moses.
J. Cryptol. 30(3): 672-698 (2017)
Conference version in Proc. 32nd EUROCRYPT, 2013.
Available as an ECCC and eprint report.
Garbling XOR Gates "For Free" in the Standard Model
Benny Applebaum.
Journal of Cryptology, vol. 29, number 3, 552-576, 2016. (pdf)
Conference version in Proc. 10th TCC, 2013.
Available as an eprint Report.
Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions.
Benny Applebaum.
SICOMP, 42(5), 2008-2037, 2013. (pdf)
Conference version in Proc. 44th STOC, 2012.
Available as an ECCC Report.
A Dichotomy for Local Small-Bias Generators
Benny Applebaum, Andrej Bogdanov and Alon Rosen.
Journal of Cryptology, vol. 29, number 3, 577-596, 2016. (pdf)
Conference version in Proc. 9th TCC, 2012.
Available as an ECCC and eprint reports.
How to Garble Arithmetic Circuits
Benny Applebaum, Yuval Ishai and Eyal Kushilevitz.
SICOMP special issue for FOCS 2011, 43(2), 905-929, 2014. (pdf)
Conference version in Proc. 52nd FOCS, 2011. (pdf)
Key-Dependent Message Security: Generic Amplification and Completeness Theorems.
Benny Applebaum.
Journal of Cryptology, 27(3), 429-451, 2013. (pdf)
Conference version in Proc. 30th Eurocrypt, 2011. (pdf)
Semantic Security Under Related-Key Attacks.
Benny Applebaum, Danny Harnik and Yuval Ishai.
The 2nd Symposium on Innovations in Computer Science (ICS 2011).
Available as an ePrint Report.
From Secrecy to Soundness: Efficient Verification via Secure Computation.
Benny Applebaum, Yuval Ishai and Eyal Kushilevitz.
The 37th International Colloquium on Automata, Languages and Programming. (ICALP 2010, Track A).
Conference version (.pdf)
Public-Key Cryptography from Different Assumptions.
Benny Applebaum, Boaz Barak and Avi Wigderson.
The 42th ACM Symposium on Theory of Computing (STOC 2010).
Conference version (.pdf)
Draft of full version (.pdf)
Collaborative, Privacy-Preserving Data Aggregation at Scale.
Benny Applebaum, Matthew Caesar, Michael J. Freedman, Jennifer Rexford and Haakon Ringberg.
The 10th Privacy Enhancing Technologies Symposium (PETS 2010).
Conference version (.pdf)
Also available as an ePrint Report.
Cryptography by Cellular Automata or How Fast Can Complexity Emerge in Nature?
Benny Applebaum, Yuval Ishai and Eyal Kushilevitz.
The First Symposium on Innovations in Computer Science (ICS 2010).
Conference version (.pdf)
Fast Cryptographic Primitives and Circular Secure Encryption Based on Hard Learning Problems.
Benny Applebaum, David Cash, Chris Peikert and Amit Sahai.
Proc. 29th CRYPTO, 2009.
Conference version (.pdf)
Subsumes the following Technical-Report .
On Basing Lower-Bounds for Learning on Worst-Case Assumptions.
Benny Applebaum, Boaz Barak and David Xiao.
Proc. 49th FOCS, 2008.
Conference version (.pdf)
This version has more proofs than the proceedings version (but it may contain more typos).
Cryptography with Constant Input Locality.
Benny Applebaum, Yuval Ishai and Eyal Kushilevitz.
Journal of Cryptology, Special issue for Crypto 2007.
Proc. 27th Crypto, 2007.
Winner of the Best Paper Award.
Journal version (.pdf)
Conference version (.pdf)
On Pseudorandom Generators with Linear Stretch in NC0.
Benny Applebaum, Yuval Ishai and Eyal Kushilevitz.
Journal of Computational Complexity, 17(1):38-69, 2008, Special issue for Random 2006.
Conference version in Proc. 10th Random, 2006.
Journal version (.pdf)
Conference version (.pdf)
Computationally Private Randomizing Polynomials and Their Applications.
Benny Applebaum, Yuval Ishai and Eyal Kushilevitz.
Journal of Computational Complexity, 15(2):115-162, 2006, Special issue for CCC 2005.
Conference version in Proc. 20th IEEE Conference on Computational Complexity (CCC), 2005.
Journal version ( .pdf)
Conference version ( .pdf)
Cryptography in NC0.
Benny Applebaum, Yuval Ishai and Eyal Kushilevitz.
SIAM Journal of Computing, 36(4):845-888, 2006, Special Issue on Randomness and Complexity.
Co-winner of the 2007 SIAM Outstanding Paper Prize invited to JACM.
Conference version in Proc. 45th Symposium on Foundations of Computer Science (FOCS 2004).
Co-winner of the Best Paper Award.
Journal version (.pdf)
Conference version (.pdf)
Surveys
Garbled Circuits as Randomized Encodings of Functions: a Primer
Benny Applebaum.
In Tutorials on the Foundations of Cryptography Dedicated to Oded Goldreich
Published in Springer's series on Information Security and Cryptography, 2017.
Available as an ECCC report.
See also a tutorial in Simons Institute (part 1 & part 2)
Cryptographic Hardness of Random Local Functions (Survey)
Benny Applebaum.
Computational Complexity, vol. 25, number 3, 667-722, Special issue for TCC13.
Invited talk in Proc. 10th TCC, 2013. (pdf).
Available as an ECCC report.
Randomly Encoding Functions: A New Cryptographic Paradigm (Survey)
Benny Applebaum.
Invited to The 5th International Conference on Information Theoretic Security, (ICITS 2011)
Conference Version (pdf)
Cryptography in Constant Parallel Time.
Benny Applebaum.
Ph.D thesis, Technion, June 2007.
Received Honorable Mention for the ACM Doctoral Dissertation Award (2007) (.pdf)
Published in Springer's series on Information Security and Cryptography, 2014.
Copyright Notice. This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder. Also, some of these works have been submitted for publication. Copyright may be transferred without further notice and this version may no longer be accessible.