One-Way and Trapdoor Functions: The Heart Of Modern Encryption

Introduction

A one-way function is, by definition, a mathematical function that is easy to calculate but computationally difficult to invert. In other words, inverting a one-way function is equivalent to solving an intractable mathematical problem, i.e. for which no computationally efficient solution algorithm is known.

One-way functions are the foundation of modern asymmetric (or public key) cryptography. In fact, all of the asymmetric cryptographic techniques used to protect data and communications base their security on the difficulty of inverting these objects.

Note, however, that this difficulty is only presumed. Indeed, from a theoretical point of view, this is still an open conjecture, never formally demonstrated. A proof would involve solving the main unsolved question of theoretical computer science, as well as one of the seven Millennium problems, P vs NP.

These were identified by the Clay Mathematics Institute in 2000 and consist of seven unsolved mathematical problems whose solution would have a crucial impact on both their theoretical implications and their practical applications. For each of these, a prize of one million dollars has been put up for grabs if proof is provided.

Among the seven questions, the Riemann hypothesis is mentioned, the resolution of which would lead to consequences on the distribution of prime numbers and would therefore have profound repercussions in pure mathematics and cryptanalysis. The only one that has been solved is the Poincaré conjecture, the rest still remain open problems today.

The fact that the existence of one-way functions is still an open conjecture means that none of these functions are demonstrably difficult to invert. It is theoretically possible, therefore, that one day an algorithm will be discovered that can efficiently reverse one of these, making the protection offered by cryptographic schemes based on it useless.

Although there is no mathematical certainty, the scientific community deeply believes that this will not happen, and has always placed the security of cryptographic schemes on this assumption.

Adding to the confidence in one-way functions is the fact that several candidates have withstood decades of research looking for an inversion algorithm. Some examples are hash functions, multiplying two primes, and modular exponentiation.

In particular, the inversion problems of the latter two are better known as integer factorization and the discrete logarithm, problems on which most of the asymmetric cryptographic schemes in use today, such as RSA and Diffie-Hellman, rely their security.

Click the link to read the full article.

For other articles related to Quantum and Cryptography topics, please refer to the related categories in the blog.

The authors

Veronica Cristiano, a bachelor’s degree in Mathematics from the University of Pisa and a master’s degree in Mathematics with a specialization in Cryptography at the University of Trento, joined the Telsy Cryptography research group in mid-2021.

Giuseppe D’Alconzo, graduated in Mathematics with a specialization in Cryptography at the University of Trento, in 2019 he carried out an internship at Telsy, dealing with Multiparty Computation and Attribute-Based Encryption. He is currently a PhD student in Pure and Applied Mathematics at the Politecnico di Torino, with a “Post-Quantum Cryptography” scholarship within the UniversiTIM program and in collaboration with the Telsy Research Group.