A Key-Recovery Attack on the GTLN Knapsack Cryptosystem via Continued Fractions

What it is

A continued-fraction key-recovery attack on the GTLN knapsack public-key cryptosystem (Gómez-Torrecillas, Lobillo, Navarro), posted as ePrint 2026/2543 in October 2026 by Shiyi Zhou, Yingpu Deng and Shi Ying. It is a preprint. The attack needs only the public key.

How it works

The attack rests on one observation: ratios of public-key differences closely approximate rational numbers with small denominators. Continued fraction convergents recover those rationals exactly. Divisibility relations among the recovered fractions give, through gcd computations, multiples of two private-key integers.

A bounded cofactor search then pins down those two integers. Once they are known, all other private-key integers are uniquely determined, except the modulus and the shift. More gcd computations, cofactor enumeration and a modular inversion recover those two.

flowchart TD
    A[Public key differences] --> B[Convergents give small-denominator ratios]
    B --> C[gcds give multiples of two secret integers]
    C --> D[Bounded cofactor search]
    D --> E[Other secret integers determined]
    E --> F[gcd, enumeration, inversion]
    F --> G[Modulus and shift]

Preconditions / Affected

• Any deployment of GTLN using its recommended parameter sets. The paper tested 24 sets.
• The attacker needs no oracle, ciphertexts or side channel.
• Running time is polynomial in the public-key bit length, for fixed cofactor bounds.

What to do

The page names no patch or fixed variant. Treat GTLN as broken with the recommended parameters and do not rely on it for confidentiality. Anyone who has deployed it should assume the private key can be derived from the public key.

Caveats

• The experiments used prime-based key generation. Keys generated another way were not reported.
• Success is backed by a heuristic analysis, not a proof. Experiments recovered the full key in 2,400 of 2,400 trials, each under 0.05 seconds in Python.
• The cofactor search is bounded, so the polynomial-time claim holds only for fixed bounds.
• Only the abstract was available for this write-up. Exact parameter values and the cofactor bounds are not stated there.