Improved Quantum Lifting by Coherent Measure-and-Reprogram

• URL: http://arxiv.org/abs/2509.09896v1
• Date: Thu, 11 Sep 2025 23:15:13 GMT
• Title: Improved Quantum Lifting by Coherent Measure-and-Reprogram
• Authors: Alexandru Cojocaru, Juan Garay, Qipeng Liu, Fang Song,
• Abstract summary: We give a tighter lifting theorem for security games in the quantum random model oracle.<n>At the core of our main result lies a novel measure-and-reprogram framework that we call coherent reprogramming.
• Score: 41.17296890645859
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We give a tighter lifting theorem for security games in the quantum random oracle model. At the core of our main result lies a novel measure-and-reprogram framework that we call coherent reprogramming. This framework gives a tighter lifting theorem for query complexity problems, that only requires purely classical reasoning. As direct applications of our lifting theorem, we first provide a quantum direct product theorem in the average case - i.e., an enabling tool to determine the hardness of solving multi-instance security games. This allows us to derive in a straightforward manner the hardness of various security games, for example (i) the non-uniform hardness of salted games, (ii) the hardness of specific cryptographic tasks such as the multiple instance version of one-wayness and collision-resistance, and (iii) uniform or non-uniform hardness of many other games.

Related papers

• Towards Simple and Useful One-Time Programs in the Quantum Random Oracle Model [0.0]
  We construct simulation-secure one-time memories (OTM) in the random oracle model.<n>We present a plausible argument for their security against quantum adversaries with bounded and adaptive depth.
  arXiv  Detail & Related papers  (2026-01-19T17:48:14Z)
• Decoding Rewards in Competitive Games: Inverse Game Theory with Entropy Regularization [52.74762030521324]
  We propose a novel algorithm to learn reward functions from observed actions.<n>We provide strong theoretical guarantees for the reliability and sample efficiency of our algorithm.
  arXiv  Detail & Related papers  (2026-01-19T04:12:51Z)
• NISQ Security and Complexity via Simple Classical Reasoning [41.17296890645859]
  We give novel lifting theorems for security games in the quantum random oracle model (QROM) in Noisy Intermediate-Scale Quantum (NISQ) settings.<n>We provide, for the first time, a hybrid lifting theorem for hybrid algorithms that can perform both quantum and classical queries.<n>We derive the first direct product theorems in the average case, in the hybrid setting-i.e., an enabling tool to determine the hybrid hardness of solving multi-instance security games.
  arXiv  Detail & Related papers  (2025-09-11T23:31:39Z)
• Quantum Lifting for Invertible Permutations and Ideal Ciphers [47.33103206862089]
  We derive the first lifting theorems for establishing security in the quantum random permutation and ideal cipher models.<n>These theorems relate the success probability of an arbitrary quantum adversary to that of a classical algorithm making only a small number of classical queries.
  arXiv  Detail & Related papers  (2025-04-25T09:07:55Z)
• (Quantum) Indifferentiability and Pre-Computation [50.06591179629447]
  Indifferentiability is a cryptographic paradigm for analyzing the security of ideal objects. Despite its strength, indifferentiability is not known to offer security against pre-processing attacks. We propose a strengthening of indifferentiability which is not only composable but also takes arbitrary pre-computation into account.
  arXiv  Detail & Related papers  (2024-10-22T00:41:47Z)
• A Dynamical System View of Langevin-Based Non-Convex Sampling [44.002384711340966]
  Non- sampling is a key challenge in machine learning, central to non-rate optimization in deep learning as well as to approximate its significance. Existing guarantees typically only hold for the averaged distances rather than the more desirable last-rate iterates. We develop a new framework that lifts the above issues by harnessing several tools from the theory systems.
  arXiv  Detail & Related papers  (2022-10-25T09:43:36Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs of Sequential Work [10.43571631715192]
  We revisit the so-called compressed oracle technique, introduced by Zhandry for analyzing quantum algorithms in the quantum random oracle model (QROM) Our main technical contribution is a framework that simplifies the use of the parallel-query generalization of the compressed oracle technique for proving query complexity results. As a concrete cryptographic application of our techniques, we prove that the "Simple Proofs of Sequential Work" proposed by Cohen and Pietrzak remains secure against quantum attacks.
  arXiv  Detail & Related papers  (2020-10-22T12:44:08Z)
• Post-Quantum Multi-Party Computation [32.75732860329838]
  We study multi-party computation for classical functionalities (in the plain model) with security against malicious-time quantum adversaries. We assume superpolynomial quantum hardness of learning with errors (LWE), and quantum hardness of an LWE-based circular security assumption. Along the way, we develop cryptographic primitives that may be of independent interest.
  arXiv  Detail & Related papers  (2020-05-23T00:42:52Z)
• Simpler Proofs of Quantumness [16.12500804569801]
  A proof of quantumness is a method for provably demonstrating that a quantum device can perform computational tasks that a classical device cannot. There are currently three approaches for exhibiting proofs of quantumness. We give a two-message (challenge-response) proof of quantumness based on any trapdoor claw-free function.
  arXiv  Detail & Related papers  (2020-05-11T01:31:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.