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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

From First Prize to Complete Break: Key Recovery in the NSU Fully Homomorphic Cryptosystem (RusCrypto 2015)

Andrei Lesin
Zenodo (CERN European Organization for Nuclear Research)
Cryptography and Data Security
preprint

From First Prize to Complete Break: Key Recovery in the NSU Fully Homomorphic Cryptosystem (RusCrypto 2015)

Andrei Lesin
preprint en

Abstract

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

Zenodo (CERN European Organization for Nuclear Research)
Cryptography and Data Security
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon