Related papers: Quantum Lifting for Invertible Permutations and Ideal Ciphers

Quantum Lifting for Invertible Permutations and Ideal Ciphers

URL: http://arxiv.org/abs/2504.18188v1
Date: Fri, 25 Apr 2025 09:07:55 GMT
Title: Quantum Lifting for Invertible Permutations and Ideal Ciphers
Authors: Alexandru Cojocaru, Minki Hhan, Qipeng Liu, Takashi Yamakawa, Aaram Yun,
Abstract summary: 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.
Score: 47.33103206862089
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this work, we derive the first lifting theorems for establishing security in the quantum random permutation and ideal cipher models. 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. By applying these lifting theorems, we improve previous results and obtain new quantum query complexity bounds and post-quantum security results. Notably, we derive tight bounds for the quantum hardness of the double-sided zero search game and establish the post-quantum security for the preimage resistance, one-wayness, and multi-collision resistance of constant-round sponge, as well as the collision resistance of the Davies-Meyer construction.

Related papers

Quantum Indistinguishable Obfuscation via Quantum Circuit Equivalence [6.769315201275599]
Quantum computing solutions are increasingly deployed in commercial environments through delegated computing. One of the most critical issues is to guarantee the confidentiality and proprietary of quantum implementations. Since the proposal of general-purpose indistinguishability obfuscation (iO) and functional encryption schemes, iO has emerged as a seemingly versatile cryptography primitive.
arXiv Detail & Related papers (2024-11-19T07:37:24Z)
The multimode conditional quantum Entropy Power Inequality and the squashed entanglement of the extreme multimode bosonic Gaussian channels [53.253900735220796]
Inequality determines the minimum conditional von Neumann entropy of the output of the most general linear mixing of bosonic quantum modes. Bosonic quantum systems constitute the mathematical model for the electromagnetic radiation in the quantum regime.
arXiv Detail & Related papers (2024-10-18T13:59:50Z)
Quantum Query Lower Bounds for Key Recovery Attacks on the Even-Mansour Cipher [0.0]
Even-Mansour (EM) cipher is one of the famous constructions for a block cipher. Kuwakado and Morii demonstrated that a quantum adversary can recover its $n$-bit secret keys only with $O(n)$ nonadaptive quantum queries.
arXiv Detail & Related papers (2023-08-21T02:01:30Z)
Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
arXiv Detail & Related papers (2023-03-02T14:18:17Z)
Anticipative measurements in hybrid quantum-classical computation [68.8204255655161]
We present an approach where the quantum computation is supplemented by a classical result. Taking advantage of its anticipation also leads to a new type of quantum measurements, which we call anticipative. In an anticipative quantum measurement the combination of the results from classical and quantum computations happens only in the end.
arXiv Detail & Related papers (2022-09-12T15:47:44Z)
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)
Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier [73.70426431502803]
We prove that Kilian's four-message succinct argument system is post-quantum secure in the standard model. This yields the first post-quantum succinct argument system from any falsifiable assumption.
arXiv Detail & Related papers (2021-03-15T05:09:17Z)
Quantum Sampling for Optimistic Finite Key Rates in High Dimensional Quantum Cryptography [1.5469452301122175]
We revisit so-called sampling-based entropic uncertainty relations, deriving newer, more powerful, relations and applying them to source-independent quantum random number generators and high-dimensional quantum key distribution protocols. These sampling-based approaches to entropic uncertainty, and their application to quantum cryptography, hold great potential for deriving proofs of security for quantum cryptographic systems.
arXiv Detail & Related papers (2020-12-08T01:32:59Z)
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)

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