Paper 2021/257

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

Shoichi Kamada


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.

Available format(s)
Public-key cryptography
Publication info
Preprint. Minor revision.
knapsack cryptographysubset sum problemslow density attacksadditive combinatoricsextremal combinatorics
Contact author(s)
shoichi @ tmu ac jp
2022-03-30: revised
2021-03-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shoichi Kamada},
      title = {Cryptanalysis of the quantum public-key cryptosystem OTU  under heuristics from combinatorial statements},
      howpublished = {Cryptology ePrint Archive, Paper 2021/257},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.