Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Cryptanalysis of the quantum public-key cryptosystem OTU under heuristics from combinatorial statements

Shoichi Kamada

Published Aug 3, 2022• 0 citations
Publisher

Abstract

Abstract The knapsack cryptography is the public-key cryptography whose security depends mainly on the hardness of the subset sum problem. Many of knapsack schemes were broken by low-density attacks, which are attack methods to use the situation that a shortest vector or a closest vector in a lattice corresponds to a solution of the subset sum problem. For the case when the Hamming weight of a solution for a random instance of the subset sum problem is arbitrary, if the density is less than 0.9408, then the instance can be solvable almost surely by a single call of lattice oracle. This fact was theoretically shown by Coster et al. In Crypto 2000, Okamoto, Tanaka and Uchiyama introduced the concept of quantum public key cryptosystems and proposed a knapsack cryptosystem, so-called OTU scheme. However, no known algorithm breaks the OTU scheme. In this paper, we introduce some combinatorial statements to describe necessary condition for the failure of low density attacks. More precisely, we give better heuristics than Gaussian heuristics for minimum norms of orthogonal lattices. Consequently, we show that the OTU scheme can be broken under these heuristics.

DOI
10.21203/rs.3.rs-1504750/v1

Related papers

Public-key cryptosystems from the worst-case shortest vector problem: extended abstract

Chris Peikert

We construct public-key cryptosystems that are secure assuming theworst-case hardness of approximating the minimum distance on n-dimensional lattices to within small Poly(n) factors. Prior cryptosystems with worst-case connections were based either on the shortest vector problem for a special class of lattices (Ajtai and Dwork, STOC 1997; Regev, J. ACM 2004), or on the conjectured hardness of lattice problems for quantum algorithms (Regev, STOC 2005). Our main technical innovation is a reduction from variants of the shortest vector problem to corresponding versions of the "learning with errors" (LWE) problem; previously, only a quantum reduction of this kind was known. As an additional contribution, we construct a natural chosen ciphertext-secure cryptosystem having a much simpler description and tighter underlying worst-case approximation factor than prior schemes.

ACM Symposium on Theory of Computing (STOC)•May 31, 2009•849 citations

Lattice-Based Cryptosystems and Quantum Cryptanalysis

Bruce Schneier

Lattice-Based Cryptosystems and Quantum CryptanalysisQuantum computers are probably coming, though we don't know when-and when they arrive, they will, most likely, be able to break our standard public-key cryptography algorithms.In anticipation of this possibility, cryptographers have been working on quantum-resistant public-key algorithms.The National Institute for Standards and Technology (NIST) has been hosting a competition a since 2017, and there already are several proposed standards.b Most of these are based on lattice problems.The mathematics of lattice cryptography revolve around combining sets of vectors-that's the lattice-in a multi-dimensional space.These lattices are filled with multi-dimensional periodicities.The hard problem c that's used in cryptography is to find the shortest periodicity in a large, random-looking lattice.This can be turned into d a public-key cryptosystem in a variety of different ways.Research has been ongoing since 1996, and there has been some really great work since then-including many practical public-key algorithms.On April 10, Yilei Chen from Tsinghua University in Beijing posted a paper describing a new quantum attack on that shortest-path lattice problem.It's a very dense mathematical paper-63 pages long-and my guess is that only a few cryptographers are able to understand all of its details.(I was not one of them.)But the conclusion was pretty devastating, breaking essentially all of the lattice-based fully homomorphic encryption schemes and coming significantly closer to attacks against the recently proposed (and NIST-approved) lattice key-exchange and signature schemes.However, there was a small but critical mistake in the paper, on the bottom of page 37.It was independently discovered by Hongxun Wu from Berkeley and Thomas Vidick from the Weizmann Institute in Israel eight days later.The attack algorithm in its current form doesn't work.This was discussed last week at the Cryptographers' Panel e at the RSA Conference.Adi Shamir, the "S" in RSA and a 2002 recipient of ACM's A.M. Turing award, described the result as psychologically significant because it shows that there is still a lot to be discovered about quantum

Communications of the ACM•Jun 6, 2024•25 citations

Parameter security characterization of knapsack public-key crypto under quantum computing

Xiang-Qun Fu, Wan‐Su Bao, Jianhong Shi +2 more

In order to research the security of the knapsack problem under quantum algorithm attack, we study the quantum algorithm for knapsack problem over Z_r based on the relation between the dimension of the knapsack vector and r. First, the oracle function is designed based on the knapsack vector B and S, and the quantum algorithm for the knapsack problem over Z_r is presented. The observation probability of target state is not improved by designing unitary transform, but oracle function. Its complexity is polynomial. And its success probability depends on the relation between n and r. From the above discussion, we give the essential condition for the knapsack problem over Z_r against the existing quantum algorithm attacks, i.e. r

arXiv:1402.7032•Feb 24, 2014•0 citations

Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem

Chris Peikert

We construct public-key cryptosystems that are secure assuming the *worst-case* hardness of approximating the shortest vector problem on lattices. Prior cryptosystems with worst-case connections (e.g., the Ajtai-Dwork system) were based either on a *special case* of the shortest vector problem, or on the conjectured hardness of lattice problems for *quantum* algorithms. Our main technical innovation is a reduction from certain variants of the shortest vector problem to corresponding versions of the "learning with errors" (LWE) problem; previously, only a quantum reduction of this kind was known. In addition, we construct new cryptosystems based on LWE, including a very natural chosen ciphertext-secure system that has a much simpler description and tighter underlying worst-case approximation factor than prior constructions. (Duration: 30 minutes, on or before Wednesday.)

Dagstuhl Seminar Proceedings•Jan 1, 2009•194 citations

Estimates of Implementation Complexity for Quantum Cryptanalysis of Post-Quantum Lattice-Based Cryptosystems

Alexander Olegovich Bakharev

Abstract Due to the development of quantum computing, there is a need for the development and analysis of cryptosystems resistant to attacks using a quantum computer (post-quantum cryptography algorithms). The security of many well-known post-quantum cryptosystems based on lattice theory depends on the complexity of solving the shortest vector problem (SVP). In this paper, a model of quantum oracle developed from Grover’s algorithm is described to implement a hybrid quantum–classical algorithm based on GaussSieve. This algorithm can be used for attacks on cryptosystems whose security depends on solving the SVP. Upper bounds for the number of qubits and the depth of the circuit were obtained for two implementations of the proposed quantum oracle model: minimizing the number of qubits and minimizing the circuit depth. The complexity of implementing the proposed quantum oracle model to attack post-quantum lattice-based cryptosystems that are finalists of the NIST post-quantum cryptography competition is analyzed.

Journal of Applied and Industrial Mathematics•Sep 1, 2023•1 citation

Post-Quantum Cryptosystems: Open Problems and Solutions. Lattice-Based Cryptosystems

Ekaterina Sergeevna Malygina, A. V. Kutsenko, S. A. Novoselov +5 more

Abstract The paper provides an overview of the main approaches to the construction of post-quantum cryptographic systems that are currently used. The area of lattice-based cryptography is analyzed in detail. We give the description and characterization of some known lattice-based cryptosystems whose resilience is based on the complexity of the shortest vector problem, learning with errors problem, and their variations. The main approaches to solving the problems from lattice theory, on which attacks on the corresponding cryptosystems are based, are analyzed. In particular, some known theoretical estimates of time and memory complexity of lattice basis reduction and lattice sieving algorithms are presented.

Journal of Applied and Industrial Mathematics•Sep 1, 2023•13 citations
Abstract The knapsack cryptography is the public-key cryptography whose security depends mainly on the hardness of the subset sum problem. Many of knapsack schemes were broken by low-density attacks, which are attack methods to use the situation that a shortest vector or a closest vector in a lattice corresponds to a solution of the subset sum problem. For the case when the Hamming weight of a solution for a random instance of the subset sum problem is arbitrary, if the density is less than 0.9408, then the instance can be solvable almost surely by a single call of lattice oracle. This fact was theoretically shown by Coster et al. In Crypto 2000, Okamoto, Tanaka and Uchiyama introduced the concept of quantum public key cryptosystems and proposed a knapsack cryptosystem, so-called OTU scheme. However, no known algorithm breaks the OTU scheme. In this paper, we introduce some combinatorial statements to describe necessary condition for the failure of low density attacks. More precisely, we give better heuristics than Gaussian heuristics for minimum norms of orthogonal lattices. Consequently, we show that the OTU scheme can be broken under these heuristics.
We construct public-key cryptosystems that are secure assuming theworst-case hardness of approximating the minimum distance on n-dimensional lattices to within small Poly(n) factors. Prior cryptosystems with worst-case connections were based either on the shortest vector problem for a special class of lattices (Ajtai and Dwork, STOC 1997; Regev, J. ACM 2004), or on the conjectured hardness of lattice problems for quantum algorithms (Regev, STOC 2005). Our main technical innovation is a reduction from variants of the shortest vector problem to corresponding versions of the "learning with errors" (LWE) problem; previously, only a quantum reduction of this kind was known. As an additional contribution, we construct a natural chosen ciphertext-secure cryptosystem having a much simpler description and tighter underlying worst-case approximation factor than prior schemes.
Lattice-Based Cryptosystems and Quantum CryptanalysisQuantum computers are probably coming, though we don't know when-and when they arrive, they will, most likely, be able to break our standard public-key cryptography algorithms.In anticipation of this possibility, cryptographers have been working on quantum-resistant public-key algorithms.The National Institute for Standards and Technology (NIST) has been hosting a competition a since 2017, and there already are several proposed standards.b Most of these are based on lattice problems.The mathematics of lattice cryptography revolve around combining sets of vectors-that's the lattice-in a multi-dimensional space.These lattices are filled with multi-dimensional periodicities.The hard problem c that's used in cryptography is to find the shortest periodicity in a large, random-looking lattice.This can be turned into d a public-key cryptosystem in a variety of different ways.Research has been ongoing since 1996, and there has been some really great work since then-including many practical public-key algorithms.On April 10, Yilei Chen from Tsinghua University in Beijing posted a paper describing a new quantum attack on that shortest-path lattice problem.It's a very dense mathematical paper-63 pages long-and my guess is that only a few cryptographers are able to understand all of its details.(I was not one of them.)But the conclusion was pretty devastating, breaking essentially all of the lattice-based fully homomorphic encryption schemes and coming significantly closer to attacks against the recently proposed (and NIST-approved) lattice key-exchange and signature schemes.However, there was a small but critical mistake in the paper, on the bottom of page 37.It was independently discovered by Hongxun Wu from Berkeley and Thomas Vidick from the Weizmann Institute in Israel eight days later.The attack algorithm in its current form doesn't work.This was discussed last week at the Cryptographers' Panel e at the RSA Conference.Adi Shamir, the "S" in RSA and a 2002 recipient of ACM's A.M. Turing award, described the result as psychologically significant because it shows that there is still a lot to be discovered about quantum
In order to research the security of the knapsack problem under quantum algorithm attack, we study the quantum algorithm for knapsack problem over Z_r based on the relation between the dimension of the knapsack vector and r. First, the oracle function is designed based on the knapsack vector B and S, and the quantum algorithm for the knapsack problem over Z_r is presented. The observation probability of target state is not improved by designing unitary transform, but oracle function. Its complexity is polynomial. And its success probability depends on the relation between n and r. From the above discussion, we give the essential condition for the knapsack problem over Z_r against the existing quantum algorithm attacks, i.e. r
We construct public-key cryptosystems that are secure assuming the *worst-case* hardness of approximating the shortest vector problem on lattices. Prior cryptosystems with worst-case connections (e.g., the Ajtai-Dwork system) were based either on a *special case* of the shortest vector problem, or on the conjectured hardness of lattice problems for *quantum* algorithms. Our main technical innovation is a reduction from certain variants of the shortest vector problem to corresponding versions of the "learning with errors" (LWE) problem; previously, only a quantum reduction of this kind was known. In addition, we construct new cryptosystems based on LWE, including a very natural chosen ciphertext-secure system that has a much simpler description and tighter underlying worst-case approximation factor than prior constructions. (Duration: 30 minutes, on or before Wednesday.)
Abstract Due to the development of quantum computing, there is a need for the development and analysis of cryptosystems resistant to attacks using a quantum computer (post-quantum cryptography algorithms). The security of many well-known post-quantum cryptosystems based on lattice theory depends on the complexity of solving the shortest vector problem (SVP). In this paper, a model of quantum oracle developed from Grover’s algorithm is described to implement a hybrid quantum–classical algorithm based on GaussSieve. This algorithm can be used for attacks on cryptosystems whose security depends on solving the SVP. Upper bounds for the number of qubits and the depth of the circuit were obtained for two implementations of the proposed quantum oracle model: minimizing the number of qubits and minimizing the circuit depth. The complexity of implementing the proposed quantum oracle model to attack post-quantum lattice-based cryptosystems that are finalists of the NIST post-quantum cryptography competition is analyzed.
Abstract The paper provides an overview of the main approaches to the construction of post-quantum cryptographic systems that are currently used. The area of lattice-based cryptography is analyzed in detail. We give the description and characterization of some known lattice-based cryptosystems whose resilience is based on the complexity of the shortest vector problem, learning with errors problem, and their variations. The main approaches to solving the problems from lattice theory, on which attacks on the corresponding cryptosystems are based, are analyzed. In particular, some known theoretical estimates of time and memory complexity of lattice basis reduction and lattice sieving algorithms are presented.