Welcome to the resource topic for 2021/257
Title:
Cryptanalysis of the quantum public-key cryptosystem OTU under heuristics from combinatorial statements
Authors: Shoichi Kamada
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.
ePrint: https://eprint.iacr.org/2021/257
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .