From First Prize to Complete Break: Key Recovery in the NSU Fully Homomorphic Cryptosystem (RusCrypto 2015)
The Rise and Fall of the NSU "Fully Homomorphic" Cryptosystem In 2015, at RusCrypto (the main cryptographic conference in Russia, the central industry event for information security), a paper by Vera Egorova and Darya Chechulina from the Laboratory of Modern Computer Technologies at Novosibirsk State University (NSU) took first place by a wide margin in the paper competition. They beat out approximately 50 submissions, primarily from leading Moscow universities (MSU, MEPhI, MIPT, Bauman). The work presented a public-key cryptosystem built on top of a "fully homomorphic encryption" (FHE) scheme, which was later cited in Russian surveys (e.g., Minakov 2020; Babenko-Rusalovsky 2021) and academic databases as an example of a domestic fully homomorphic system. The original scheme gained attention for its claimed properties: a public multiplication table, non-deterministic encryption, and no growth in ciphertext dimension under multiplication. This preprint presents a complete break. We show that the public key of the NSU scheme determines the secret vector k up to a linear system over Z_m. The public parameters w1, w2, u1, u2 yield two linear equations on k, while the public multiplication table gamma yields linear equations whose right-hand sides are the monomials k_i * k_j. For n = 2 the secret key is recovered by inverting a public 2x2 matrix; for n > 2 the resulting overdetermined system is solved by Gaussian elimination over Z_m (or after recovering m from determinants). Once k is known, every ciphertext is decrypted by a single inner product, and ciphertexts for arbitrary plaintexts can be forged. The attack runs in polynomial time in n and log m and requires no oracle access. Significance: The vulnerability is structural, not a mere implementation error. Properties presented as security features—the public table gamma, non-commutativity, non-associativity, and "non-determinism"—are the very source of the leak. This work demonstrates that the NSU construction cannot serve as a basis for secure cloud computing, despite its claimed applicability and its first-prize award at RusCrypto 2015. Reference implementation: The full Python code, including tests and numerical examples, is available at https://github.com/kawoshinerr/nsu-fhe-key-recovery
Authors
- Andrei Lesin (ORCID: https://orcid.org/0009-0000-2208-547X)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-15
- DOI
- https://doi.org/10.5281/zenodo.24237052
- Primary Topic
- Cryptography and Data Security
- Type
- preprint