Seminal
The magazine and atlas of EU-funded researchA new publication from the web and AI team at Scott Charnley

Atlas / Israel

European Research Council grant · Running

KolmoCrypt Cryptography from Unstructured Hardness

Coordinator
Technion - Israel Institute of Technology, Israel
Runs
1 March 2025 to 28 February 2030
Status
Running
EU funding
€2.5m
Total cost
€2.5m
Partners
3 organisations in 1 countries
Type
European Research Council grant
Grant agreement
101142322

What the project is doing

In the project's own words, from its summary on CORDIS.

Cryptography—and its basic tasks such as encryption, authentication and key exchange—is essential for ensuring privacy and security on the Internet. The question of whether “unbreakable” encryption methods exist has fascinated mathematicians and cryptographers for thousands of years, and is closely related to the famous NP vs. P problem. This question is still wide open and consequently, Internet security today relies on cryptographic constructions based on the *conjectured* hardness of some computational problems (such as e.g., the factoring problem, the discrete logarithms problem or various noisy linear algebra problems).

However, these conjectured hard problems all contain significant (e.g., algebraic) *structure*, that may make them vulnerable to attacks. Furthermore, for tasks such as key exchange and public-key encryption, only a *handful* of candidate hard problems are known on which these tasks can be based. As a result, some unexpected algorithmic developments for structured problems could upend the whole infrastructure we rely on for communicating and transacting on the Internet.

In this project, we propose to develop an alternative approach: a foundation for provably-secure Cryptography from *unstructured hardness* assumptions. Towards resolving this long-standing challenge, we will leverage our recently-discovered connection between Cryptography and the seemingly unrelated area of Kolmogorov Complexity. Specifically, we will develop new hardness assumptions rooted in Kolmogorov Complexity on which the cryptographic tasks (e.g., private-key encryption, key-exchange, public-key encryption) can be based.

Critically, these assumptions will lack algebraic and other computational structure that may make them vulnerable to attacks. Overall, KolmoCrypt will provide a new theoretical foundation for the hardness assumptions on which Cryptography is based, and ultimately, a more secure foundation for the Internet (and beyond).

Topics

Who is involved

OrganisationCityCountryRole
Technion - Israel Institute of TechnologyHaifaIsraelCoordinator
Technion Research and Development Foundation LtdHaifaIsraelThird party
Tel Aviv UniversityTel AvivIsraelParticipant

Source: CORDIS, European Commission. Data of 5 Nov 2026, reused under the Commission's reuse policy. View on CORDIS · Grant DOI