Quantum Truncated Differential and Boomerang Attack
- URL: http://arxiv.org/abs/2407.15126v1
- Date: Sun, 21 Jul 2024 11:34:29 GMT
- Title: Quantum Truncated Differential and Boomerang Attack
- Authors: Huiqin Xie, Li Yang,
- Abstract summary: In this article, we concentrate on truncated differential and boomerang cryptanalysis.
We first present a quantum algorithm which is designed for finding truncated differentials of symmetric ciphers.
We prove that, with a overwhelming probability, the truncated differentials output by our algorithm must have high differential probability for the vast majority of keys in key space.
- Score: 10.853582091917236
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Facing the worldwide steady progress in building quantum computers, it is crucial for cryptographic community to design quantum-safe cryptographic primitives. To achieve this, we need to investigate the capability of cryptographic analysis tools when used by the adversaries with quantum computers. In this article, we concentrate on truncated differential and boomerang cryptanalysis. We first present a quantum algorithm which is designed for finding truncated differentials of symmetric ciphers. We prove that, with a overwhelming probability, the truncated differentials output by our algorithm must have high differential probability for the vast majority of keys in key space. Afterwards, based on this algorithm, we design a quantum algorithm which can be used to find boomerang distinguishers. The quantum circuits of both quantum algorithms contain only polynomial quantum gates. Compared to classical tools for searching truncated differentials or boomerang distinguishers, our algorithms fully utilize the strengths of quantum computing, and can maintain the polynomial complexity while fully considering the impact of S-boxes and key scheduling.
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 curse of random quantum data [62.24825255497622]
We quantify the performances of quantum machine learning in the landscape of quantum data.
We find that the training efficiency and generalization capabilities in quantum machine learning will be exponentially suppressed with the increase in qubits.
Our findings apply to both the quantum kernel method and the large-width limit of quantum neural networks.
arXiv Detail & Related papers (2024-08-19T12:18:07Z) - A Quantum Automatic Tool for Finding Impossible Differentials [12.997422492640766]
We propose two quantum automatic tools for searching impossible differentials.
The proposed quantum algorithms exploit the idea of miss-in-the-middle and the properties of truncated differentials.
arXiv Detail & Related papers (2024-07-14T03:00:24Z) - Supervised binary classification of small-scale digits images with a trapped-ion quantum processor [56.089799129458875]
We show that a quantum processor can correctly solve the basic classification task considered.
With the increase of the capabilities quantum processors, they can become a useful tool for machine learning.
arXiv Detail & Related papers (2024-06-17T18:20:51Z) - Tailoring Fault-Tolerance to Quantum Algorithms [3.836669717540222]
We develop a solve-and-stitch algorithm to synthesize physical realizations of Clifford Trotter circuits.
We achieve fault-tolerance for these circuits using flag gadgets, which add minimal overhead.
arXiv Detail & Related papers (2024-04-18T07:15:15Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
Quantum computing sets the foundation for new ways of designing algorithms.
New challenges arise concerning which field quantum speedup can be achieved.
Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
arXiv Detail & Related papers (2024-02-26T09:32:07Z) - Revocable Cryptography from Learning with Errors [61.470151825577034]
We build on the no-cloning principle of quantum mechanics and design cryptographic schemes with key-revocation capabilities.
We consider schemes where secret keys are represented as quantum states with the guarantee that, once the secret key is successfully revoked from a user, they no longer have the ability to perform the same functionality as before.
arXiv Detail & Related papers (2023-02-28T18:58:11Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
We design, implement, and evaluate three hybrid quantum k-Means algorithms.
We exploit quantum phenomena to speed up the computation of distances.
We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
arXiv Detail & Related papers (2022-12-13T16:04:16Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - Variational Quantum Cloning: Improving Practicality for Quantum
Cryptanalysis [2.064612766965483]
We propose variational quantum cloning (VQC), a machine learning based cryptanalysis algorithm.
VQC allows an adversary to obtain optimal (approximate) cloning strategies with short depth quantum circuits.
We derive attacks on two protocols as examples, based on quantum cloning and facilitated by VQC.
arXiv Detail & Related papers (2020-12-21T15:28:09Z) - Quantum Ciphertext Dimension Reduction Scheme for Homomorphic Encrypted
Data [4.825895794318393]
Proposed quantum principal component extraction algorithm (QPCE)
A quantum homomorphic ciphertext dimension reduction scheme (QHEDR)
A quantum ciphertext dimensionality reduction scheme implemented in the quantum cloud.
arXiv Detail & Related papers (2020-11-19T07:16:22Z)
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.