Project topics and materials
Get Complete Project Material File(s) Now! »
From One-Way Functions to Pseudorandom Functions
Before the notion of pseudorandom functions was introduced by Goldreich, Goldwasser, and Micali in [GGM84], cryptographers studied the notion of pseudorandom generator. Broadly speaking, a pseudorandom generator with `-bit stretch is a function G : {0, 1}κ → {0, 1}κ+`, with ` ≥ 1, that takes as input a bitstring s ∈ {0, 1}κ , called the seed, and outputs a longer bitstring G(s) ∈ {0, 1}κ+`. Furthermore, we require the following property: assuming s is taken uniformly at random, it is computationally hard to distinguish G(s) from a uniformly random string taken from {0, 1}κ+` without the knowledge of s. Thus, a pseudorandom generator is simply a function that takes as input a small random bitstring and outputs an `-bit longer pseudorandom bitstring.
Fundamental results in this area were shown by Goldreich and Levin in [GL89]. Specifically, they prove the following two results:
• Pseudorandom generators with 1-bit stretch exist if and only if one-way functions exist.
• For any ` = poly(κ), pseudorandom generators with `-bit stretch exist if and only if pseudorandom generators with 1-bit stretch exist.
Then, putting these results together, we obtain that pseudorandom generators with polynomial stretch exist if and only if one-way functions exist. In particular, considering length-doubling pseudorandom generators, so with domain {0, 1}κ and range {0, 1}2κ, we immediately have:
Length-doubling pseudorandom generators exist if and only if one-way functions exist.
The above statements are not detailed further in this manuscript, as we focus on con-structions of pseudorandom functions, but let us explain how length-doubling pseudorandom generators can then be used to build pseudorandom functions, as shown by Goldreich, Gold-wasser, and Micali in their seminal work [GGM84]. Specifically, let us briefly sketch a proof of the following statement: Pseudorandom functions exist if and only if length-doubling pseudorandom generators exist.
Assume the existence of a length-doubling pseudorandom generator G: {0, 1}κ → {0, 1}2κ, for κ ≥ 1. Then, one can build a pseudorandom function F : {0, 1}κ × {0, 1}n → {0, 1}κ as follows, for any n = poly(κ).
For a key K ∈ {0, 1}κ and a bitstring x ∈ {0, 1}`, 0 ≤ ` ≤ n, we recursively define Kx as:
• Kε = K, where ε denotes the empty string;
• Kx k 0 k Kx k 1 = G(Kx), with |Kx k 0| = |Kx k 1| = κ.
Then, the GGM pseudorandom function is defined via F (K, x) = Kx.
Intuitively, this corresponds to following a path in a binary tree of depth n whose root is labeled by K and such that the two siblings of any internal node labeled by a string s are respectively labeled by the first and second half of G(s). Computing F (K, x) then simply corresponds in outputting the label of the x-th leaf of this tree. Please refer to Figure 1.1 for further details about this computation.
The security of this pseudorandom function follows from the security of the pseudorandom generator. Let us assume that the adversary makes only one query x = 0n . That is, to compute F (K, x), one first evaluates G(K ) and evaluate G again on the first half of G (K), and so on. Then, assuming the security of G, if K is chosen uniformly at random, one can change G(K) = K0 k K1 to a uniformly random string of length 2κ. This change is computationally indistinguishable due to the security of G. Then, one can change G(K0) to a uniformly random string of length 2κ under the security of G, as K0 is now a uniformly random bitstring. By repeating n times this process, one change the output F (K, 0n) to a uniformly random bitstring of length κ, and this change is computationally indistinguishable assuming the security of G. In the case of multiple queries, one just needs to reiterate this process on each path of the tree that is used to answer the (polynomial number of) queries made by the adversary.
The other direction is immediate, as, given a pseudorandom function F : {0, 1}κ × D → {0, 1}`, one can just construct a length-doubling pseudorandom generator by evaluating F on fixed inputs with the seed as a key, and concatenate (or truncate) the outputs to obtain a bitstring of length 2κ.
Number-Theoretic Constructions
Despite its elegance, the original construction of pseudorandom functions by Goldreich, Goldwasser, and Micali based on pseudorandom generators is not very efficient. In order to improve its efficiency while still being able to prove its security under reasonable complexity assumptions, Naor and Reingold [NR97] proposed a new construction based on the Decisional Diffie-Hellman assumption (DDH). Let a = (a0, . . . , an) ∈ (Zp∗)n+1
be the key and x = x1 k . . . k xn ∈ {0, 1}n be the input of the pseudorandom function. Let g be a fixed public generator of a group G of prime order p. The Naor-Reingold pseudorandom function is then defined as NR( a , x) = » a0 n ai i # , where for any a ∈ Zp, [a] stands for ga, as defined in [EHK+13].
As mentioned in [BMR10], the algebraic nature of the Naor-Reingold pseudorandom function has led to many applications, such as verifiable random functions [ACF09; HW10], distributed pseudorandom functions [NR97], and related-key secure pseudorandom func-tions [BC10b], which are hard to obtain from generic pseudorandom functions. Hence, due to its importance, several other extensions of the Naor-Reingold pseudorandom function have been proposed [LW09; BMR10] based on different assumptions, such as the Decision Linear assumption (DLin) [BBS04] and the d-DDHI assumption [BMR10; GOR11].
An important part of this work is to study the algebraic structure of such pseudorandom functions, as well as extensions of these constructions, such as related-key secure, aggregate, and multilinear pseudorandom functions. Let us then define more formally these primitives.
Extensions of Pseudorandom Functions
Pseudorandom functions have been extended in different directions, either to add functionali-ties, for instance with the notions of aggregate or verifiable pseudorandom functions, or to strengthen their security. In particular, due to their central role in constructing block-ciphers, building pseudorandom functions that resist to real-world attacks has been an important area of research. An aspect of this area corresponds to related-key security. In this thesis, we focus on aggregate, multilinear, and related-key secure pseudorandom functions and briefly introduce these notions below.
Related-Key Security
As already explained, a common approach to prove the security of a cryptographic scheme, known as provable security, is to relate its security to one of its underlying primitives or to an accepted hard computational problem. While this approach is now standard and widely accepted, there is still a significant gap between the existing models used in security proofs and the actual environment in which these cryptosystems are deployed. For example, most of the existing security models assume that the adversary has no information about the user’s secret key. However, it is well known that this is not always true in practice: the adversary may be able to learn partial information about the secrets using different types of side-channel attacks, such as the study of energy consumption, fault injection, or timing analysis. In the particular case of fault injection, for instance, an adversary can learn not only partial information about the secret key, but it may also be able to force a cryptosystem to work with different but related secret keys. Then, if it can observe the outcome of this cryptosystem, it may be able to break it. This is what is known in the literature as a related-key attack (RKA).
Most primitives are designed without taking related-key attacks into consideration so their security proofs do not provide any guarantee against such attacks. Hence, a cryptographic scheme that is perfectly safe in theory may be completely vulnerable in practice. Indeed, many such attacks were found during the last decade, especially against practical block-ciphers [BDK05; BDK08; BDK+10; BK09; BKN09; KHP07]. Inspired by this cryptanalytic work, some years ago, theoreticians started to develop appropriate security models and search for cryptographic primitives which can be proven related-key secure.
Though related-key attacks were first introduced by Biham and Knudsen [Bih94; Knu93] in the early 1990’s, it was only in 2003 that Bellare and Kohno [BK03] began the formalization of the theoretical foundations for related-key security. We recall their security definition of related-key security for pseudorandom functions here. Let F : K × D → R be a family of functions for a security parameter κ, and let Φ = {φ: K → K} be a set of functions on the key space K, called a related-key deriving (RKD) function set. We say that F is a Φ-related-key secure pseudorandom function if for any polynomial-time adversary, its advantage in the following game is negligible. The game starts by picking a random challenge bit b, a random target key K ∈ K and a random function G: K × D → R. The adversary can repeatedly query an oracle that, given a pair (φ, x) ∈ Φ × D, returns either F (φ(K), x), if b = 1, or G(φ(K), x), if b = 0. Finally, the adversary outputs a bit b0, and its advantage is defined by 2 Pr [ b = b0 ] − 1. Note that if the class Φ of RKD functions contains only the identity function, then this notion matches standard PRF security.
In this work, Bellare and Kohno also proved that there are inherent limitations to security against related-key attacks. In particular, there exist simple classes of related-key deriving functions for which related-key security is impossible. For instance, it is impossible to achieve related-key security against any class of functions that contains a constant function, as it implies that the adversary is able to change the key to a fixed constant value. Hence, it is important to understand which classes of RKD functions can or cannot be handled.
It appears that pseudorandom functions are a central notion in related-key security. Indeed, it has been shown by Bellare, Cash, and Miller in [BCM11], that having related-key secure pseudorandom functions for a class of RKD functions is sufficient to transform several standard cryptographic primitives (including signatures, symmetric encryption, public-key encryption, identity-based encryption, . . . ) into related-key secure ones for the same class of functions. Therefore, studying pseudorandom functions, in the related-key setting, is of prime interest.
Yet, building related-key secure pseudorandom functions under standard assumptions has been a wide-open problem for years, until the seminal work by Bellare and Cash [BC10b], and achieving related-key security under standard assumptions for real-world classes, such as XOR relations, is still a major open problem.
Aggregate Pseudorandom Functions
Aggregate pseudorandom functions were introduced by Cohen, Goldwasser, and Vaikun-thanathan in [CGV15] The main interest of an aggregate pseudorandom function is to provide the user with the possibility of aggregating the values of the function over super-polynomially many outputs with only a polynomial-time computation, without enabling a polynomial-time adversary to distinguish the function from a truly random function. For instance, one such example of an aggregate query could be to compute the product of all the output values of the pseudorandom function corresponding to a given exponentially-sized interval of the input domain.
In addition to proposing the notion of aggregate pseudorandom functions, Cohen, Gold-wasser, and Vaikunthanathan [CGV15] also proposed first constructions for several different classes of aggregate queries, such as decision trees, hypercubes, and read-once boolean formu-las, achieving different levels of expressiveness. Unfortunately, for most of the constructions proposed in [CGV15], the proofs of security suffer from an exponential (in the input length) overhead in their running time and have to rely on the sub-exponential hardness of the Decisional Diffie-Hellman (DDH) problem.
Indeed, to prove the security of their constructions, the authors use a generic result which is simply saying the following: given an adversary A against the aggregate pseudorandom function security of a pseudorandom function F , one can build an adversary B against the standard pseudorandom function security of F . B just queries all the values required to compute the aggregate or output values, and computes the aggregate values itself before sending them to A .
Clearly, this reduction proves that any secure pseudorandom function is actually also a secure aggregate pseudorandom function. However, this reduction is not efficient, since to answer to only one aggregate query, the adversary B may have to query an exponential number of values to its oracle. Hence, as soon as we can aggregate in one query a super-polynomial number of PRF values, this generic reduction does not run in polynomial time.
Multilinear Pseudorandom Functions
In order to overcome the shortcomings of the work of Cohen, Goldwasser, and Vaikun-tanathan [CGV15], Cohen and Holmgren introduced the concept of multilinear pseudorandom functions in [CH15]. Informally speaking, a multilinear pseudorandom function is a variant of the standard notion of pseudorandom function, which works with vector spaces and which guarantees indistinguishability from random multilinear functions with the same domain and range. As shown in [CH15], multilinear pseudorandom functions can be used to prove the aggregate pseudorandom function security of the Naor-Reingold (NR) pseudorandom function [NR97] with a polynomial-time reduction for the case of hypercubes and decision trees aggregations. Unfortunately, their technique does not extend to the more general case of read-once formulas aggregation, which is the most expressive form of aggregation in [CGV15]
Our Contributions
Our main focus in this thesis is the study of pseudorandom functions and above extensions, and our main contributions in these areas are the following.
Extension and Correction of the Bellare-Cash Framework
As already mentioned, Bellare and Cash [BC10b] designed the first related-key secure pseudorandom functions based on standard assumptions. These foundational results are obtained by applying a single, elegant, general framework to the Naor-Reingold pseudorandom function and handle certain multiplicative and additive RKD function classes. Unfortunately, it was discovered later that the framework of [BC10b] had a minor bug that prevented its proof to go through. They corrected this bug by strengthening the requirements of their framework, but their new requirements did no longer allow the framework to be applied to additive classes.
In this thesis, our first contribution is to correct and extend this framework. Specifically, we provide a new proof of their framework that goes through assuming only the original requirements. Therefore, it allows us to apply our framework to the additive case, as originally done in [BC10b]. Moreover, we provide new tools that let us handle larger classes of relations and extend the framework. For instance, we are able to construct a related-key secure pseudorandom function for the class of affine relations.
Algebraic Framework for Pseudorandom Functions
The second contribution of this thesis is an algebraic framework, termed “polynomial linear pseudorandomness security”, that can be used to construct and prove the security of a wide variety of pseudorandom functions. Intuitively, we prove the following theorem: let G = hgi be a cyclic group of prime order p and let us denote by [a] the group element ga, for any a ∈ Zp. Let a1, . . . , an be n uniformly random secret scalars from Zp. Then, for any positive integer q and any multivariate polynomials P1, . . . , Pq defined over Zp and with indeterminates T1, . . . , Tn, the group elements:
[P1(a1, . . . , an)] , . . . , [Pq(a1, . . . , an)] are computationally indistinguishable, under some standard assumptions, from the group elements: [U(P1)] , . . . , [U(Pq)] , where U is a random linear map from the set of multivariate polynomials to Zp.
This theorem is straightforward in the generic group model, but we prove that it is also true assuming only the hardness of some standard assumptions (discussed below). Furthermore, this framework is general enough to encompass standard and related-key securities for pseudorandom functions as well as multilinear and aggregate pseudorandom functions, and allows us to solve various open questions in these areas. In particular, it let us define a fully algebraic framework for related-key security that only requires some basic algebraic properties to be applied, or to provide a polynomial-time reduction that proves the aggregate pseudorandom function security of the Naor-Reingold construction for read-once formulas aggregation.
Assumptions
Our algebraic framework is proven under different assumptions. In particular, depending on certain parameters, such as the degree of polynomials P1, . . . , Pq, we are able to prove our theorem assuming only the DDH assumption or a stronger assumption, such as the d-DDHI assumption (with d being a bound on the degree of polynomials).
We actually prove our framework under a new family of computational assumptions, termed Ek,d-MDDH assumptions (where d is a bound on the degree of polynomials and k is some parameter precised later), that encompasses in particular classical assumptions such as DDH, d-DDHI, k-Lin, . . . and a side contribution of this thesis is to prove the security of all our non-classical assumptions in the generic group model.
Related-Key Secure Pseudorandom Function for XOR Relations
The last contribution of this thesis is a construction of related-key secure pseudorandom functions for XOR relations, based on the existence of a weak form of multilinear maps. Indeed, even if the results discussed above in related-key security allow to handle different and large classes of RKD functions, the functions have to be algebraic transformations (such as multivariate polynomials), and thus do not really correspond to real-world attacks. Here, our construction is secure even assuming that the adversary has the capacity of flipping any bit of the key at each query, which is closer to the actual capacities of a real-world adversary.
However, our result should be seen as a proof of concept, as the existence of multilinear maps is still a very strong assumption, as revealed by the recent devastating attacks. Yet, despite the numerous attacks against current multilinear maps, our construction circumvents all the known attacks, and we only rely on the existence of a weak form of multilinear map. In particular, we hope that such weak form of multilinear maps might be instantiated in the future under standard assumptions, such as lattice-based assumptions.
Other Contributions
Independently from the work presented in this manuscript, we also worked on the following unrelated subjects.
Order-Revealing Encryption
In a collaboration resulting from an internship at Technicolor Research with Marc Joye, we study order-revealing encryption. An order-revealing encryption scheme is a private-key encryption scheme that provides anyone with the capacity of comparing plaintexts given only the ciphertexts, without revealing anything more about the plaintexts. The first construction of order-revealing encryption was proposed by Boneh et al. in [BLR+15] and relied on the existence of multilinear maps. In our work, we propose a first construction of order-revealing encryption assuming one-way functions exist, but only for polynomial-size domains. We also propose a construction that reveals the order but also a bit more, for exponential-sized domains, assuming the hardness of the DLin problem.
Private Circuits
In a joint work with Sonia Belaïd, Fabrice Benhamouda, Emmanuel Prouff, Adrian Thillard, and Damien Vergnaud, we study the construction of multiplication circuits in the probing model. This model has been introduced by Ishai, Sahai, and Wagner in [ISW03] to capture the security of implementations against side-channel attacks, such as attacks using the power consumption or the electromagnetic radiation of the device running the cryptosystem. When devices are not protected against such attacks, it is often possible to exploit these physical measures to retrieve sensitive data.
Specifically, this model assumes that the attacker can obtain a bounded number of inter-mediate values of the computation (called probes), and we call a private circuit a circuit that is secure in this model. The seminal work by Ishai, Sahai, and Wagner, shows how to transform any circuit into a private circuit, at the cost of extra randomness. The main tool for this transformation is the construction of the first private circuit for bit-multiplication.
In our work, we focus on studying the bit-multiplication and try to optimize the number of random bits used by the private circuit computing this operation. Letting d denote the bound on the number of probes that the attacker can make, we obtain the following results: on the theoretical side, we prove a linear lower bound (in d) on the number of additional random bits, and a quasi-linear upper bound (O(d • log d)). These bounds result from an algebraic characterization of the security of a private circuit, which relies on basic linear algebra. On the practical side, we construct a private circuit for bit-multiplication that halves the randomness complexity of the previous circuit by Ishai, Sahai, and Wagner, and also construct private circuits for small (real- world) cases (d ≤ 4) whose randomness complexity match our linear lower bound. Finally, we also implement a tool, based on our algebraic characterization of security, that allows to find attacks against multiplication circuits which is magnitude faster that previous known tools (such as [BBD+15]), but is not perfectly sound. That is, our tool might not always find attacks against a non-secure scheme so cannot serve for proving security of a scheme, but allows to discard quickly bad candidates.
Functional Encryption and Obfuscation
In a work with Nir Bitansky, Ryo Nishimaki, and Daniel Wichs, resulting from an internship at Northeastern University, we study the relation between private-key functional encryption and indistinguishability obfuscation. By designing different intermediate tools, we are able to construct a compact public-key functional encryption scheme from any unbounded-collusion private-key functional encryption scheme and any plain public-key encryption scheme. Putting this result together with the transform by Bitansky and Vaikunthanathan [BV15] or by Ananth and Jain [AJ15], we then obtain that private-key functional encryption is sufficient, combined with any plain public-key encryption scheme, to build indistinguishability obfuscation. In particular, this proves that private-key functional encryption is (almost) as powerful as public-key functional encryption.
Organization
The rest of this manuscript is organized as follows: Chapter 2 first introduces basic mathe-matical, computational, and cryptographic notions. Next, Chapter 3 introduces related-key security and corrects and extends the Bellare-Cash framework. Chapter 4 defines our new family of assumptions and either relates them to classical assumptions or proves their security in a generic-group model. Chapter 5 then uses the new family of assumptions to prove the security of our main algebraic framework. Next, Chapter 6 applies the new algebraic framework to pseudorandom functions, related-key secure pseudorandom functions, aggre-gate pseudorandom functions, and multilinear pseudorandom functions. Finally, Chapter 7 describes our construction of related-key secure pseudorandom function for XOR relations and Chapter 8 concludes this thesis
Table of contents :
1 Introduction
1.1 Pseudorandom Functions
1.1.1 From One-Way Functions to Pseudorandom Functions
1.1.2 Number-Theoretic Constructions
1.1.3 Extensions of Pseudorandom Functions
1.2 Our Contributions
1.2.1 Extension and Correction of the Bellare-Cash Framework
1.2.2 Algebraic Framework for Pseudorandom Functions
1.2.3 Assumptions
1.2.4 Related-Key Secure Pseudorandom Function for XOR Relations
1.3 Other Contributions
1.3.1 Order-Revealing Encryption
1.3.2 Private Circuits
1.3.3 Functional Encryption and Obfuscation
1.4 Organization
2 Preliminaries
2.1 Notation and Preliminaries
2.1.1 Mathematical Notions
2.1.2 Algorithmic Concepts
2.1.3 Provable Security
2.2 Classical Computational Assumptions
2.2.1 The Discrete Logarithm Problem
2.2.2 Classical Discrete-Logarithm-Based Assumptions
2.2.3 Building DDH-Hard Groups
2.3 Cryptographic Primitives
2.3.1 Collision-Resistant Hash Functions
2.3.2 Pseudorandom Functions
2.3.3 Aggregate Pseudorandom Functions
2.3.4 Multilinear Pseudorandom Functions
2.4 Multilinear Maps and the Generic Multilinear Map Model
2.4.1 Multilinear Maps
2.4.2 Generic Multilinear Map Model
3 Introduction to Related-Key Security
3.1 Definition and Security Model
3.2 First Impossibility and Feasibility Results
3.2.1 Impossibility Results
3.2.2 Feasibility Results
3.3 The Central Role of Pseudorandom Functions
3.4 The Bellare-Cash Framework, Revisited
3.4.1 Additional Notions
3.4.2 Dealing with Key-Collisions
3.4.3 The (Extended) Framework
3.5 Application: Related-Key Security for Affine Relations
3.5.1 Ingredients
3.5.2 Putting Everything Together
3.6 Further Generalization of the Bellare-Cash Framework
3.6.1 Relaxing the Requirements of the Framework
3.6.2 From Malleability to Unique-Input-Related-Key Security
3.7 Application: Related-Key Security for Affine Relations
4 A New Family of Assumptions
4.1 The Matrix-Decisional-Diffie-Hellman Assumptions
4.2 A New Family of Matrix-Diffie-Hellman Assumptions
4.3 Connexion with Standard Assumptions
4.3.1 Summary of Relations
4.3.2 Relation with the DDHI Assumption
4.4 Security in the Generic Multilinear Group Model
4.4.1 Definitions: Monomial Order and Leading Commutative Monomials
4.4.2 Main Lemma
4.4.3 Putting Everything Together
5 An Algebraic Framework for Pseudorandomness
5.1 Intuition and Subtleties
5.1.1 Intuition
5.1.2 Procedure for Testing Linear Dependence
5.1.3 Extension to Weaker Assumptions
5.1.4 On the Representation of Multivariate Polynomials
5.2 Formal Security Notion and Main Result
5.2.1 Formal Definition of the Polynomial Linear Pseudorandomness Security
5.2.2 The PLP Theorem
5.2.3 Immediate Corollary: the LIP Theorem
5.3 Proof of Theorem 5.2.2
5.3.1 Decomposition Lemmata
5.3.2 The Main Proof
6 Applications
6.1 Applications to Standard Pseudorandom Functions
6.1.1 Extended Number-Theoretic Pseudorandom Functions
6.1.2 Simple Proofs of Security
6.2 Applications to Related-Key Security
6.2.1 Direct Constructions
6.2.2 Constructions From Unique-Input-Related-Key Security, Algebraically
6.2.3 Other Applications to Related-Key Security
6.2.4 Extension to Weaker Assumptions
6.2.5 A Further Generalization of the Framework
6.3 Applications to Aggregate Pseudorandom Functions
6.3.1 Read-Once Formula Aggregation
6.3.2 Impossibility Results
6.3.3 Extension to Weaker Assumptions
6.4 Applications to Multilinear Pseudorandom Functions
6.4.1 Cohen-Holmgren Construction
6.4.2 Symmetric Multilinear Pseudorandom Functions
6.4.3 Skew-Symmetric Multilinear Pseudorandom Function
6.4.4 Extension to Weaker Assumptions
7 A Provably-Secure Pseudorandom Function For XOR-Relations
7.1 Additional Material
7.1.1 Related-Key Security for XOR Relations
7.1.2 Multilinear Maps
7.1.3 Straddling Sets
7.2 Our Construction
7.2.1 Intuition
7.2.2 Actual Construction
7.3 Security in the Generic Multilinear Map Model
7.4 Security under Non-Interactive Assumptions
7.4.1 Two Non-Interactive Assumptions
7.4.2 Security of our Construction
7.5 Security of the XY-DDH Assumption in the Generic Multilinear Map Model
7.6 Security of the Sel-Prod Assumption in the Generic Multilinear Map Model
7.6.1 Proof Ingredient: Index Sets and Profiles
7.6.2 Security of the Sel-Prod Assumption
8 Conclusion and Open Questions
8.1 Conclusion
8.2 Open Questions
Notation
Abbreviations
List of Illustrations
Bibliography
