Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Justin Holmgren and Ron Rothblum. Linear-Size Boolean Circuits for Multiselection. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{holmgren_et_al:LIPIcs.CCC.2024.11, author = {Holmgren, Justin and Rothblum, Ron}, title = {{Linear-Size Boolean Circuits for Multiselection}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {11:1--11:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.11}, URN = {urn:nbn:de:0030-drops-204070}, doi = {10.4230/LIPIcs.CCC.2024.11}, annote = {Keywords: Private Information Retrieval, Batch Selection, Boolean Circuits} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Adam Bouland, Bill Fefferman, Soumik Ghosh, Tony Metger, Umesh Vazirani, Chenyi Zhang, and Zixin Zhou. Public-Key Pseudoentanglement and the Hardness of Learning Ground State Entanglement Structure. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 21:1-21:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bouland_et_al:LIPIcs.CCC.2024.21, author = {Bouland, Adam and Fefferman, Bill and Ghosh, Soumik and Metger, Tony and Vazirani, Umesh and Zhang, Chenyi and Zhou, Zixin}, title = {{Public-Key Pseudoentanglement and the Hardness of Learning Ground State Entanglement Structure}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {21:1--21:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.21}, URN = {urn:nbn:de:0030-drops-204175}, doi = {10.4230/LIPIcs.CCC.2024.21}, annote = {Keywords: Quantum computing, Quantum complexity theory, entanglement} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Yangjing Dong, Honghao Fu, Anand Natarajan, Minglong Qin, Haochen Xu, and Penghui Yao. The Computational Advantage of MIP^∗ Vanishes in the Presence of Noise. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 30:1-30:71, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dong_et_al:LIPIcs.CCC.2024.30, author = {Dong, Yangjing and Fu, Honghao and Natarajan, Anand and Qin, Minglong and Xu, Haochen and Yao, Penghui}, title = {{The Computational Advantage of MIP^∗ Vanishes in the Presence of Noise}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {30:1--30:71}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.30}, URN = {urn:nbn:de:0030-drops-204263}, doi = {10.4230/LIPIcs.CCC.2024.30}, annote = {Keywords: Interactive proofs, Quantum complexity theory, Quantum entanglement, Fourier analysis, Matrix analysis, Invariance principle, Derandomization, PCP, Locally testable code, Positivity testing} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Noam Mazor and Rafael Pass. Gap MCSP Is Not (Levin) NP-Complete in Obfustopia. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 36:1-36:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mazor_et_al:LIPIcs.CCC.2024.36, author = {Mazor, Noam and Pass, Rafael}, title = {{Gap MCSP Is Not (Levin) NP-Complete in Obfustopia}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {36:1--36:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.36}, URN = {urn:nbn:de:0030-drops-204322}, doi = {10.4230/LIPIcs.CCC.2024.36}, annote = {Keywords: Kolmogorov complexity, MCSP, Levin Reduction} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Shuangle Li, Bingkai Lin, and Yuwei Liu. Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems Under ETH. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 107:1-107:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{li_et_al:LIPIcs.ICALP.2024.107, author = {Li, Shuangle and Lin, Bingkai and Liu, Yuwei}, title = {{Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems Under ETH}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {107:1--107:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.107}, URN = {urn:nbn:de:0030-drops-202500}, doi = {10.4230/LIPIcs.ICALP.2024.107}, annote = {Keywords: Nearest Codeword Problem, Hardness of Approximations, Fine-grained Complexity, Parameterized Complexity, Minimum Distance Problem, Shortest Vector Problem} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Nico Döttling and Tamer Mour. On the Black-Box Complexity of Correlation Intractability. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 40:1-40:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dottling_et_al:LIPIcs.ITCS.2024.40, author = {D\"{o}ttling, Nico and Mour, Tamer}, title = {{On the Black-Box Complexity of Correlation Intractability}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {40:1--40:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.40}, URN = {urn:nbn:de:0030-drops-195683}, doi = {10.4230/LIPIcs.ITCS.2024.40}, annote = {Keywords: Correlation Intractability, Fiat-Shamir, Black-box Complexity, Black-box Separations} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Zvika Brakerski, Ran Canetti, and Luowen Qian. On the Computational Hardness Needed for Quantum Cryptography. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 24:1-24:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{brakerski_et_al:LIPIcs.ITCS.2023.24, author = {Brakerski, Zvika and Canetti, Ran and Qian, Luowen}, title = {{On the Computational Hardness Needed for Quantum Cryptography}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {24:1--24:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.24}, URN = {urn:nbn:de:0030-drops-175278}, doi = {10.4230/LIPIcs.ITCS.2023.24}, annote = {Keywords: quantum cryptography, efi, commitment scheme, oblivious transfer, zero knowledge, secure multiparty computation} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Zvika Brakerski, Nico Döttling, Sanjam Garg, and Giulio Malavolta. Factoring and Pairings Are Not Necessary for IO: Circular-Secure LWE Suffices. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{brakerski_et_al:LIPIcs.ICALP.2022.28, author = {Brakerski, Zvika and D\"{o}ttling, Nico and Garg, Sanjam and Malavolta, Giulio}, title = {{Factoring and Pairings Are Not Necessary for IO: Circular-Secure LWE Suffices}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {28:1--28:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.28}, URN = {urn:nbn:de:0030-drops-163699}, doi = {10.4230/LIPIcs.ICALP.2022.28}, annote = {Keywords: Cryptography, Obfuscation} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Zvika Brakerski and Vinod Vaikuntanathan. Lattice-Inspired Broadcast Encryption and Succinct Ciphertext-Policy ABE. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{brakerski_et_al:LIPIcs.ITCS.2022.28, author = {Brakerski, Zvika and Vaikuntanathan, Vinod}, title = {{Lattice-Inspired Broadcast Encryption and Succinct Ciphertext-Policy ABE}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {28:1--28:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.28}, URN = {urn:nbn:de:0030-drops-156243}, doi = {10.4230/LIPIcs.ITCS.2022.28}, annote = {Keywords: Theoretical Cryptography, Broadcast Encryption, Attribute-Based Encryption, Lattice-Based Cryptography} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Zvika Brakerski, Noah Stephens-Davidowitz, and Vinod Vaikuntanathan. On the Hardness of Average-Case k-SUM. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 29:1-29:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{brakerski_et_al:LIPIcs.APPROX/RANDOM.2021.29, author = {Brakerski, Zvika and Stephens-Davidowitz, Noah and Vaikuntanathan, Vinod}, title = {{On the Hardness of Average-Case k-SUM}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {29:1--29:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.29}, URN = {urn:nbn:de:0030-drops-147223}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.29}, annote = {Keywords: k-SUM, fine-grained complexity, average-case hardness} }
Published in: LIPIcs, Volume 199, 2nd Conference on Information-Theoretic Cryptography (ITC 2021)
Gal Arnon and Guy N. Rothblum. On Prover-Efficient Public-Coin Emulation of Interactive Proofs. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{arnon_et_al:LIPIcs.ITC.2021.3, author = {Arnon, Gal and Rothblum, Guy N.}, title = {{On Prover-Efficient Public-Coin Emulation of Interactive Proofs}}, booktitle = {2nd Conference on Information-Theoretic Cryptography (ITC 2021)}, pages = {3:1--3:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-197-9}, ISSN = {1868-8969}, year = {2021}, volume = {199}, editor = {Tessaro, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2021.3}, URN = {urn:nbn:de:0030-drops-143226}, doi = {10.4230/LIPIcs.ITC.2021.3}, annote = {Keywords: Interactive Proofs, Computational complexity, Cryptography} }
Published in: LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)
Zvika Brakerski, Venkata Koppula, Umesh Vazirani, and Thomas Vidick. Simpler Proofs of Quantumness. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{brakerski_et_al:LIPIcs.TQC.2020.8, author = {Brakerski, Zvika and Koppula, Venkata and Vazirani, Umesh and Vidick, Thomas}, title = {{Simpler Proofs of Quantumness}}, booktitle = {15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)}, pages = {8:1--8:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-146-7}, ISSN = {1868-8969}, year = {2020}, volume = {158}, editor = {Flammia, Steven T.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.8}, URN = {urn:nbn:de:0030-drops-120677}, doi = {10.4230/LIPIcs.TQC.2020.8}, annote = {Keywords: Proof of Quantumness, Random Oracle, Learning with Errors} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Benny Applebaum, Zvika Brakerski, Sanjam Garg, Yuval Ishai, and Akshayaram Srinivasan. Separating Two-Round Secure Computation From Oblivious Transfer. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 71:1-71:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{applebaum_et_al:LIPIcs.ITCS.2020.71, author = {Applebaum, Benny and Brakerski, Zvika and Garg, Sanjam and Ishai, Yuval and Srinivasan, Akshayaram}, title = {{Separating Two-Round Secure Computation From Oblivious Transfer}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {71:1--71:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.71}, URN = {urn:nbn:de:0030-drops-117560}, doi = {10.4230/LIPIcs.ITCS.2020.71}, annote = {Keywords: Oracle Separation, Oblivious Transfer, Secure Multiparty Computation} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Ben Berger and Zvika Brakerski. Brief Announcement: Zero-Knowledge Protocols for Search Problems. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 105:1-105:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{berger_et_al:LIPIcs.ICALP.2018.105, author = {Berger, Ben and Brakerski, Zvika}, title = {{Brief Announcement: Zero-Knowledge Protocols for Search Problems}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {105:1--105:5}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.105}, URN = {urn:nbn:de:0030-drops-91099}, doi = {10.4230/LIPIcs.ICALP.2018.105}, annote = {Keywords: Zero-Knowledge, Search Problems, Interactive Proofs} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Zvika Brakerski, Nishanth Chandran, Vipul Goyal, Aayush Jain, Amit Sahai, and Gil Segev. Hierarchical Functional Encryption. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 8:1-8:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{brakerski_et_al:LIPIcs.ITCS.2017.8, author = {Brakerski, Zvika and Chandran, Nishanth and Goyal, Vipul and Jain, Aayush and Sahai, Amit and Segev, Gil}, title = {{Hierarchical Functional Encryption}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {8:1--8:27}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-029-3}, ISSN = {1868-8969}, year = {2017}, volume = {67}, editor = {Papadimitriou, Christos H.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.8}, URN = {urn:nbn:de:0030-drops-81992}, doi = {10.4230/LIPIcs.ITCS.2017.8}, annote = {Keywords: Functional Encryption, Delegatable Encryption, Cryptography} }