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

14 Dec 2022

Introduction

By definition, a one-way function is easy to compute but hard to invert. In other words, inverting a one-way function is equivalent to solving an intractable mathematical problem for which no computationally efficient algorithm is known. One-way functions represent the foundation of modern asymmetric (or public-key) cryptography. Indeed, most asymmetric cryptographic techniques base their security on the hardness of inverting these functions. However, this hardness is only assumed, since from a theoretical point of view it is still an open problem. A formal proof of the existence of one-way functions would have major implications in computational complexity theory and is closely related to one of the seven Millennium problems, namely the P vs NP problem. These problems were selected by the Clay Mathematics Institute in 2000 and consist of seven unsolved mathematical problems whose solutions would have a crucial impact on both theory and applications. A one million dollar prize has been offered for the solution of each problem. Among them, it is worth mentioning the Riemann Hypothesis, whose solution would have important consequences for the distribution of prime numbers and therefore for number theory and cryptanalysis. The only Millennium problem solved so far is the Poincaré conjecture; the others remain open. The fact that the existence of one-way functions is still conjectured means that none of them has been proven to be hard to invert. In theory, it is therefore possible that an efficient algorithm could be discovered in the future, breaking the hardness assumption and, with it, the security of many cryptographic schemes. Despite this lack of mathematical proof, the scientific community strongly believes that such a breakthrough is unlikely. This belief is motivated by the fact that many candidate one-way functions have withstood decades of cryptanalysis. Examples include cryptographic hash functions, integer multiplication of large primes, and modular exponentiation. In particular, the inversion problems associated with the last two — known as integer factorization and the discrete logarithm problem — form the basis of most cryptographic schemes currently in use, such as RSA and Diffie–Hellman.

One-way functions in public key cryptography

To build an intuition, a one-way function can be compared to a blender: starting from the input, it is easy to obtain the mixed output, while reconstructing the original input from the output is essentially impossible. More formally, let $f:A\rightarrow B$ be a function. The function $f$ is called one-way if:

given $a\in A$ , it is easy to compute $f(a)$ ;
given $b\in B$ , it is computationally hard to find $a\in A$ such that $f(a)=b$ .

Looking at modern public key cryptography, a typical example is provided by the modular exponentiation used in the Diffie-Hellman key exchange. Given a prime number $p$ and a positive integer $g$ less than $p$ , the following function is a one-way function candidate:

$f(x) = g^x \mod p.$

Observe that computing the $x$ -th power modulo $p$ is easy. On the other hand, given a positive integer $h$ less than $p$ , finding the element $x$ such that $g^x = h \mod p$ is an intractable problem. This problem is known as the discrete logarithm problem and forms the basis of many cryptographic schemes such as the Diffie-Hellman key exchange and the Elliptic Curve Digital Signature Algorithm (ECDSA). To better understand its role in public key cryptography, it is useful to discuss how the one-way function concept is related to the public–private key pair of a public key algorithm. Typically, given a one-way function $f$ , the public–private key pair can be defined as $(x, f(x))$ , where $x$ is a randomly chosen element. In the case of Diffie-Hellman, the secrecy of the private key $x$ is based on the difficulty of inverting the function $f(x) = g^x \mod p$ .

Trapdoor functions in public key cryptography

A special case of one-way functions is represented by trapdoor functions. These functions have the property of being easy to invert when additional secret information (the trapdoor) is known, while they behave as normal one-way functions otherwise. A trapdoor function can be compared to the closing mechanism of a lock: anyone is able to lock it, but only those who own the key (the trapdoor) can easily open it. Formally, a trapdoor function is a one-way function with the property that, if a secret information $k$ is known, then there exists an efficient function $f_k$ such that, given any $b\in B$ , $f(f_k(b)) = b$ . A famous example of a trapdoor function is the one on which the RSA cryptographic scheme is based. Let $p$ and $q$ be two prime numbers and let $N$ be their product. Let $e$ and $d$ be two positive integers coprime with $(p-1)(q-1)$ such that

$ed = 1 \mod (p-1)(q-1).$

The public key is given by $(N,e)$ , while the private key is $d$ . The one-way function is

$f(m) = m^e \mod N.$

Also in this case, computing $f(m)$ starting from $m$ is easy, while finding an $e$ -th root modulo $N$ of an integer $c = f(m)$ is assumed to be hard. The function $f$ is a trapdoor one-way function, where the trapdoor consists in the knowledge of the private key $d$ . Indeed, consider the function

$f_d(c) = c^d \mod N,$

since $ed = 1 \mod (p-1)(q-1)$ , it follows that, for any $x$ , $x^{ed} = x \mod N$ , and therefore

$f(f_d(c)) = f(c^d \mod N) = c^{ed} \mod N = c \mod N.$

In other words, $f_d(c)$ is exactly the original message $m$ .

One-way vs trapdoor

The main difference between one-way functions with and without a trapdoor is the presence of secret information that allows efficient inversion. This implies the existence of a hidden structure that could potentially leak some information about the secret key. Therefore, in the analysis of these schemes, it is crucial to address both the difficulty of inversion and the security of the trapdoor. In RSA, the inversion of $f$ consists of computing an $e$ -th root modulo $N$ , and the trapdoor security is based on the hardness of factoring $N = pq$ in order to obtain $d$ . In asymmetric cryptography, trapdoor functions are used to hide the message, allowing it to be recovered only by those who know the trapdoor. On the other hand, a simple one-way function is typically used to generate a public–private key pair. As already mentioned in previous articles, thanks to Shor’s Algorithm, a quantum computer is able to efficiently invert both prime multiplication and modular exponentiation, affecting the security of most asymmetric schemes currently in use. Therefore, it is crucial to study and analyze quantum-resistant one-way functions. Post-Quantum Cryptography is a response to the quantum computing threat, identifying new mathematical problems and therefore new one-way functions that are believed to be resistant even in the presence of quantum algorithms. In the next articles of this series, some examples of these constructions will be discussed in a post-quantum setting.

This article belongs to a series of contributions, edited by the Telsy Cryptography Research Group, devoted to quantum computing and its implications on Cryptography. For reference to other articles, please refer to the index.

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.