Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR24-029 | 24th May 2024 20:10

Quantum Automating $\mathbf{TC}^0$-Frege Is LWE-Hard

RSS-Feed




Revision #1
Authors: Noel Arteche, Gaia Carenini, Matthew Gray
Accepted on: 24th May 2024 20:10
Downloads: 80
Keywords: 


Abstract:

We prove the first hardness results against efficient proof search by quantum algorithms. We show that under Learning with Errors (LWE), the standard lattice-based cryptographic assumption, no quantum algorithm can weakly automate ${\mathbf{TC}^0\text{-Frege}}$. This extends the line of results of Krají?ek and Pudlák (\emph{Information and Computation}, 1998), Bonet, Pitassi, and Raz (\emph{FOCS}, 1997), and Bonet, Domingo, Gavaldà, Maciel, and Pitassi (\emph{Computational Complexity}, 2004), who showed that Extended Frege, $\mathbf{TC}^0$-Frege and $\mathbf{AC}^0$-Frege, respectively, cannot be weakly automated by classical algorithms if either the RSA cryptosystem or the Diffie-Hellman key exchange protocol are secure. To the best of our knowledge, this is the first interaction between quantum computation and propositional proof search.



Changes to previous version:

Missing axioms have been added to the definition of LAQ in Section 4.3. Section 4.3.2 contains now more detailed proofs and a few mistakes have been fixed.


Paper:

TR24-029 | 16th February 2024 00:42

Quantum Automating $\mathbf{TC}^0$-Frege Is LWE-Hard





TR24-029
Authors: Noel Arteche, Gaia Carenini, Matthew Gray
Publication: 20th February 2024 13:38
Downloads: 221
Keywords: 


Abstract:

We prove the first hardness results against efficient proof search by quantum algorithms. We show that under Learning with Errors (LWE), the standard lattice-based cryptographic assumption, no quantum algorithm can weakly automate $\mathbf{TC}^0$-Frege. This extends the line of results of Kraí?ek and Pudlák (Information and Computation, 1998), Bonet, Pitassi, and Ray (FOCS, 1997), and Bonet et al. (Computational Complexity, 2004), who showed that Extended Frege, $\mathbf{TC}^0$-Frege and $\mathbf{AC}^0$-Frege, respectively, cannot be weakly automated by classical algorithms if either the RSA cryptosystem or the Diffie-Hellman key exchange protocol are secure. To the best of our knowledge, this is the first interaction between quantum computation and propositional proof search.



ISSN 1433-8092 | Imprint