**Cryptanalysis of the quantum public-key cryptosystem OTU under heuristics from Szemerédi-type statements**

*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 able to break 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 cryptosystem. However, no known algorithm breaks the OTU cryptosystem.

In this paper, we introduced Szemerédi-type assumptions, which are the imitations of the statement of Szemerédi's theorem on arithmetic progressions. From this mathematical point of view, we make clear what the average case and the worst case are. For low density attacks, we give better heuristics for orthogonal lattices than Gaussian heuristics. Consequently, we show that the OTU scheme can be broken under some heuristic assumptions.

**Category / Keywords: **public-key cryptography / knapsack cryptography, subset sum problems, low density attacks, additive combinatorics, extremal combinatorics, combinatorial number theory and natural density.

**Date: **received 2 Mar 2021

**Contact author: **shoichi at tmu ac jp

**Available format(s): **PDF | BibTeX Citation

**Version: **20210303:194448 (All versions of this report)

**Short URL: **ia.cr/2021/257

[ Cryptology ePrint archive ]