Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Quantum Automating TC0-Frege Is LWE-Hard

Arteche, Noel LU ; Carenini, Gaia and Gray, Matthew (2024) 39th Computational Complexity Conference, CCC 2024 In Leibniz International Proceedings in Informatics, LIPIcs 300.
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 TC0-Frege. This extends the line of results of Krajíček and Pudlák (Information and Computation, 1998), Bonet, Pitassi, and Raz (FOCS, 1997), and Bonet, Domingo, Gavaldà, Maciel, and Pitassi (Computational Complexity, 2004), who showed that Extended Frege, TC0-Frege and AC0-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... (More)

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 TC0-Frege. This extends the line of results of Krajíček and Pudlák (Information and Computation, 1998), Bonet, Pitassi, and Raz (FOCS, 1997), and Bonet, Domingo, Gavaldà, Maciel, and Pitassi (Computational Complexity, 2004), who showed that Extended Frege, TC0-Frege and AC0-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.

(Less)
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
automatability, feasible interpolation, post-quantum cryptography
host publication
39th Computational Complexity Conference, CCC 2024
series title
Leibniz International Proceedings in Informatics, LIPIcs
editor
Santhanam, Rahul
volume
300
article number
15
publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
conference name
39th Computational Complexity Conference, CCC 2024
conference location
Ann Arbor, United States
conference dates
2024-07-22 - 2024-07-25
external identifiers
  • scopus:85199394442
ISSN
1868-8969
ISBN
9783959773317
DOI
10.4230/LIPIcs.CCC.2024.15
language
English
LU publication?
yes
id
b366628d-0546-484f-bea5-ea277aff68b9
date added to LUP
2024-09-30 15:12:45
date last changed
2025-04-04 15:12:41
@inproceedings{b366628d-0546-484f-bea5-ea277aff68b9,
  abstract     = {{<p>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 TC<sup>0</sup>-Frege. This extends the line of results of Krajíček and Pudlák (Information and Computation, 1998), Bonet, Pitassi, and Raz (FOCS, 1997), and Bonet, Domingo, Gavaldà, Maciel, and Pitassi (Computational Complexity, 2004), who showed that Extended Frege, TC<sup>0</sup>-Frege and AC<sup>0</sup>-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.</p>}},
  author       = {{Arteche, Noel and Carenini, Gaia and Gray, Matthew}},
  booktitle    = {{39th Computational Complexity Conference, CCC 2024}},
  editor       = {{Santhanam, Rahul}},
  isbn         = {{9783959773317}},
  issn         = {{1868-8969}},
  keywords     = {{automatability; feasible interpolation; post-quantum cryptography}},
  language     = {{eng}},
  publisher    = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}},
  series       = {{Leibniz International Proceedings in Informatics, LIPIcs}},
  title        = {{Quantum Automating TC<sup>0</sup>-Frege Is LWE-Hard}},
  url          = {{http://dx.doi.org/10.4230/LIPIcs.CCC.2024.15}},
  doi          = {{10.4230/LIPIcs.CCC.2024.15}},
  volume       = {{300}},
  year         = {{2024}},
}