Michel Abdalla
email: michel.abdalla@ens.fr

Fabrice Benhamouda
email: fabrice.benhamouda@normalesup.org

Alain Passelègue
email: alain.passelegue@inria.fr

Algebraic XOR-RKA-Secure Pseudorandom Functions from Post-Zeroizing Multilinear Maps

Keywords: Pseudorandom Functions, Related-Key Security, Multilinear Maps, Post-Zeroizing Constructions

Due to the vast number of successful related-key attacks against existing block-ciphers, related-key security has become a common design goal for such primitives. In these attacks, the adversary is not only capable of seeing the output of a function on inputs of its choice, but also on related keys. At Crypto 2010, Bellare and Cash proposed the first construction of a pseudorandom function that could provably withstand such attacks based on standard assumptions. Their construction, as well as several others that appeared more recently, have in common the fact that they only consider linear or polynomial functions of the secret key over complex groups. In reality, however, most related-key attacks have a simpler form, such as the XOR of the key with a known value. To address this problem, we propose the first construction of RKA-secure pseudorandom function for XOR relations. Our construction relies on multilinear maps and, hence, can only be seen as a feasibility result. Nevertheless, we remark that it can be instantiated under two of the existing multilinear-map candidates since it does not reveal any encodings of zero. To achieve this goal, we rely on several techniques that were used in the context of program obfuscation, but we also introduce new ones to address challenges that are specific to the related-key-security setting.

Introduction

Context. Most of the security models used to prove the security of cryptographic schemes usually assume that an adversary has only a black-box access to the cryptosystem. In particular, the adversary has no information about the secret key, nor can it modify the latter. Unfortunately, it has been shown that this is not always true in practice. For instance, an adversary may learn information from physical measures such as the running time of the protocol or its energy consumption, or may also be able to inject faults in the cryptosystem. In the specific case of fault attacks, in addition to possibly being able to learn partial information about the key, the adversary may be able to force the cryptosystem to run with a different, but related, secret key. Then, by observing the outcomes of the cryptosystem with this new related key, an adversary may be able to break it. Such an attack is called a related-key attack (RKA) and has often been used against concrete blockciphers [Knu93, Bih94, BDK05, BDK + 10].

Formalization of RKA security. Following the seminal cryptanalytic works by Biham and Knudsen, theoreticians have defined new security models in order to capture such attacks. In 2003, Bellare and Kohno formalized the foundations for RKA security [BK03]. Specifically, let F : K × D → R be a pseudorandom function and let Φ ⊆ Fun(K, K) be a set of functions on the key space K, called a class of related-key deriving (RKD) functions.We say that F is Φ-RKA secure if it is hard to distinguish an oracle which, on input a pair (φ, x) ∈ Φ × D, outputs F (φ(K), x), from an oracle which, on the same input pair, outputs G(φ(K), x), where K ∈ K is a random target key and G: K × D → R is a random function.

Existing Constructions. Building provably RKA-secure pseudorandom functions in non-idealized model has been a long-standing open question until the work of [START_REF] Bellare | Pseudorandom functions and permutations provably secure against related-key attacks[END_REF]. Their construction is adapted from the Naor-Reingold PRF [NR97] and is obtained by applying a generic framework to it. This generic framework has led to other constructions based under different assumptions [LMR14] and been recently extended to circumvent its limitations [ABPP14, ABP15, ABPP18]. However, despite being simple and elegant, the existing frameworks crucially rely on the algebraic structure of the pseudorandom functions and thus only allow to build RKA-secure pseudorandom functions for algebraic classes of RKD functions. More precisely, existing constructions use a key whose components are elements in Z p , and are proven secure against an attacker that is given the capability to perform operations (additions, multiplications, or even polynomial evaluation) modulo p, with p super-polynomial in the security parameter for instantiations over cyclic or multilinear groups [BC10, LMR14, ABPP14, ABP15], or p polynomial but still much larger than 2, for instantiations based on lattices [LMR14,BP14].

Unfortunately, the algebraic classes of RKD functions above are not very natural as they seem difficult to implement from the perspective of an attacker5 . Moreover, they also do not seem to match attacks against concrete blockciphers such as AES (e.g., [BDK05, BDK + 10]). To address these shortcomings, we focus in this paper on the XOR class of RKD functions, which seems more relevant for practice, as suggested by Bellare and Kohno [BK03]. In this class, which corresponds to the class of functions Φ ⊕ = {φ s : K ∈ {0, 1} k → K ⊕ s ∈ {0, 1} k | s ∈ {0, 1} k } with K = {0, 1} k being the keyspace, the adversary is allowed to flip bits of the secret key.

In the context of pseudorandom functions, there have been a few proposals for protecting against weak versions of XOR-related-key attacks. In [AW14], for instance, Applebaum and Widder proposed several schemes that can provably resist XOR attacks by restricting the capabilities of the adversary. In particular, they consider models where the adversary only uses a bounded number of related keys or where it only performs random XOR operations. In [JW15], Jafargholi and Wichs proposed constructions of pseudorandom functions based on continuous non-malleable codes that can resist several forms of relatedkey attacks, including XOR-related-key attacks. Their solutions, however, only guarantee pseudorandomness under the original key and not under both the original and related keys as in standard notions of related-key security. Another advantage of our construction compared to theirs is that the key in our case is just a bit string.

In the random-oracle model, there is a straightforward construction of a pseudorandom function secure against XOR-related-key attacks: F (K, x) = H(K x), with H being a hash function modeled as a random oracle, and being the string concatenation operator. However, from a theoretical perspective, having a construction in the random-oracle model does not provide any guarantee that the primitive can be realized under non-interactive (and falsifiable) assumptions. To the best of our knowledge, building a pseudorandom function that provably resists XOR-related-key attacks in non-idealized models still remains a major open problem. Furthermore, we would like to point out that we do not know of any construction of a pseudorandom function secure against XOR-related-key attacks in the generic multilinear group model.

Our Contributions.

In this paper, we provide the first provably secure construction of an RKA-secure pseudorandom function for XOR relations. To achieve this goal, our construction departs significantly from previous RKA-secure pseudorandom functions in that the secret key no longer lies in an algebraic group. As in prior constructions (e.g., [BC10, ABPP14, ABP15, LMR14]), our new scheme also requires public parameters, such as generators of a cyclic group, which cannot be tampered with. However, unlike these constructions, the secret key in our scheme is just a bit string, whose values are used to select a subset of the common parameters which will be used in the evaluation of the pseudorandom function. 6 The evaluation is performed using an asymmetric multilinear map [GGH13a, CLT13, GGH15].

In particular, we prove our construction under two non-interactive assumptions. We further prove that it is hard to come up with encodings of zero (in the generic multilinear map model) given only the encodings revealed by these assumptions. Therefore these assumptions are plausible under some current instantiations of multilinear maps. To the best of our knowledge, this is the first construction using multilinear maps with such a level of security. In [BMSZ16], Badrinarayanan et al. were the first to take into account zeroizing attacks (i.e., attacks using encodings of zero) against current multilinear maps constructions into their constructions and to propose a scheme which is proven not to reveal encodings of zero, in the generic multilinear map model. But, contrary to us, they did not provide a proof of their scheme under a non-interactive assumption.

Overview of our techniques. As mentioned above, our construction is based on asymmetric multilinear maps [GGH13a, CLT13, GGH15]. Informally speaking, a multilinear map is a generalization of bilinear maps. It allows to "encode" scalars a (in some finite field Z p ) into some encodings [a] S with respect to an index set (also called an index) S ⊆ U , where S indicates the level of the encoding

F pp (K, x) =   k i=1 a i,Ki n j=1 c j,xj   U ,
where the public parameters pp include {â i,b } i∈[k],b∈{0,1} and {ĉ j,b } j∈[n],b∈{0,1} as well as the public parameters of the multilinear map.

Since the encodings of the scalars a i,b and c j,b are included in pp, it is not hard to see that the user in possession of the secret K can efficiently evaluate this function at any point x by computing the multilinear map function with the help of the encodings âi,Ki and ĉj,xj . To prove it secure and be able to instantiate the scheme with existing multilinear map candidates, however, is not straightforward as one needs to show that the adversary cannot mix too many existing encodings and create an encoding of zero.

While a proof in the generic multilinear map model [Sho97, GGH + 13b, BR14, BGK + 14, Zim15] is possible, we would like to rely on non-interactive complexity assumptions over multilinear maps which are likely to hold in existing multilinear map constructions. To achieve this goal, we change the way in which the index sets are defined using techniques from program obfuscation [GGH + 13b, BGK + 14, Zim15]. More precisely, we make use of the notion of strong straddling sets [BGK + 14, MSW14, Zim15, BMSZ16], which informally allows to partition a set into two disjoint sets of subsets so that they cannot be mixed. As in [MSW14, Zim15, BMSZ16], we first construct strong straddling set systems over sets S i of k 2 fresh symbols, for i ∈ {0, . . . , k} and use S i for i ≥ 1 to prevent the adversary from mixing an exponential number of inputs. In addition to that, and unlike [MSW14, Zim15, BMSZ16], we use S 0 in the proof to prevent the adversary from mixing an internal private representation of the key (used by the reduction) with the parameters.

As we show in Section 4, the resulting scheme can be proven secure in the generic multilinear map model. In particular, we are actually able to prove that no polynomial-time adversary can construct a (non-trivial) encoding of zero. 7 In addition to that, as we show in Section 5, one benefit of using (strong) straddling sets is that it allows us to prove the security of our construction under noninteractive assumptions and avoid the use of idealized models.8 Finally, we also prove the plausibility of these new assumptions in the full version [ABP17] by showing that they hold in the generic multilinear map model.

We would like to stress that the security proof in Section 5 is a much stronger result qualitatively than a direct proof in the generic multilinear map model since the latter model is only used to show that our (non-interactive) assumptions are plausible.

Concrete Instantiations. The security of our scheme relies on two new noninteractive assumptions on multilinear maps. However, contrary to most classical assumptions (such as the Decisional Diffie-Hellman assumption for low-level group elements) or the multilinear subgroup assumption used to construct witness encryption and indistinguishable obfuscation in [GLW14, GLSW15], our new assumptions do not reveal any encoding of zero. More precisely, similarly to what Badrinarayanan et al. did in [BMSZ16], we show in the ideal multilinear map model, that given an instance for one of our assumptions, the adversary cannot construct any encoding of zero (even at the top level). In particular, this implies that our assumptions holds in the hybrid graded encoding model [GMM + 16], as this model just restricts the shape of the encodings of zero that the adversary can construct, while we prove that the adversary cannot construct any such encoding.

Our assumptions are therefore not broken by most of the attacks against multilinear maps [GGH13a,CHL + 15,CGH + 15,HJ16,CLLT16] including the annihilation attacks [MSZ16,CGH17] and recent attacks such as [CLLT17,CVW18], Hence, while the GGH13 and CLT15 multilinear map candidates [GGH13a,CLT15] might not be used for our construction because of recent attacks without encodings of zero [CFL + 16, ABD16, CJL16], our assumptions are plausible when implemented with the GGH159 or the CLT13 multilinear map candidates [GGH15, CLT13].

Additional Related Work. In addition to the work mentioned above, a few other constructions of pseudorandom functions against related-key attacks for linear and polynomial functions have been proposed in [BLMR13,LMR14]. While their RKA-secure pseudorandom functions also require multilinear maps, their security proofs are based on assumptions which reveal encodings of zero and hence are subject to the multiple attacks mentioned above. Moreover, these works do not consider XOR-related-key attacks.

Related-key security with respect to XOR relations has also been considered in the context of Even-Mansour ciphers [CS15,FP15,Men16,WLZZ16]. Unlike our work, which aims to prove security under well specified non-interactive complexity assumptions, all these works rely on idealized models, which we want to avoid.

In [FX15], the authors proposed efficient constructions of identity-based encryption and key encapsulation schemes that remain secure against related-key attacks for a large class of functions, which include XOR relations. While their results are interesting, we remark that achieving RKA security for randomized primitives appears to be significantly easier than for deterministic ones, as already noted by Bellare and Cash [BC10].

Finally, it is worth mentioning here that, due to the results of Bellare,Cash,and Miller [BCM11], RKA security for pseudorandom functions can be transferred to several other primitives, including identity-based encryption, signatures, and chosen-ciphertext-secure public-key encryption.

Organization. The rest of the paper is organized as follows. Section 2 presents standard definitions of (related-key) pseudorandom functions and multilinear maps. It also introduces the generic multilinear map model and the notion of straddling set system. Section 3 explains our construction of XOR-RKA PRF. Section 4 provides a first security proof of our new scheme in the generic multilinear map model. It also shows that is not feasible for an adversary to generate non-trivial encodings of zero. Finally, Section 5 describes our main result, which is a proof of security for our new construction under two new non-interactive assumptions. The formal proof of security, as well as the proofs of our assumptions are detailed in the appendix. In particular, we prove that our assumptions are not only secure in the generic multilinear map model, but also that it is not feasible for an adversary to generate (non-trivial) encodings of zero. Hence, our assumptions are plausible given some current instantiations of multilinear maps. obfuscation candidate. A clean exposition of how to implement straddling sets for GGH15 is given in [Hal15,Sec. 4.2]. Note also that we consider multilinear maps with plaintext space corresponding to a prime-order finite field. This can be obtained using [Hal15,Sec. 4.1]. Attacks such as [CHKL18] do not apply in this setting.

Definitions

Notation and Games

Notation. We denote by κ the security parameter. Let F : K × D → R be a function that takes a key K ∈ K and an input x ∈ D and returns an output F (K, x) ∈ R. The set of all functions F : K × D → R is then denoted by Fun(K, D, R). Likewise, Fun(D, R) denotes the set of all functions mapping D to R. If S is a set, then we denote by s $ ← S the operation of picking at random s in S. If #" x is a vector then we denote by

| #" x | its length, so #" x = (x 1 , . . . , x | #" x | ).
For a binary string x, we denote its length by |x|, x i its i-th bit, so x ∈ {0, 1} |x| and x = x 1 . . . x n .

Games [BR06].

Most of our definitions and proofs use the code-based gameplaying framework, in which a game has an Initialize procedure, procedures to respond to adversary oracle queries, and a Finalize procedure. To execute a game G with an adversary A , we proceed as follows. First, Initialize is executed and its outputs become the input of A . When A executes, its oracle queries are answered by the corresponding procedures of G. When A terminates, its outputs become the input of Finalize. The output of the latter, denoted G A is called the output of the game, and we let "G A ⇒ 1" denote the event that this game output takes the value 1. The running time of an adversary by convention is the worst case time for the execution of the adversary with any of the games defining its security, so that the time of the called game procedures is included.

Pseudorandom Functions

Our definitions of pseudorandom functions and related-key secure pseudorandom functions include a Setup algorithm that is used to generate public parameters. For classical PRFs, the public parameters could actually just be included in the key. However, to our knowledge, all the known proven RKA-secure PRFs [BC10, ABPP14, LMR14, ABP15], use public parameters. Contrary to the key itself, the public parameters cannot be modified by the related-key deriving function. In our case, the Setup algorithm is specified explicitly in the construction for clarity.

PRFs [GGM86, BC10

]. Consider a pseudorandom function F pp : K × D → R with public parameters pp. The advantage of an adversary A in attacking the standard PRF security of a function F pp is defined via

Adv prf Fpp (A ) = Pr PRFReal A Fpp ⇒ 1 -Pr PRFRand A Fpp ⇒ 1 .
Game PRFReal Fpp first runs the Setup algorithm to generate the public parameters pp which it outputs. It then picks K $ ← K at random, and responds to oracle query Fn(x) via F pp (K, x). Game PRFRand Fpp runs Setup and outputs the public parameters pp. It then picks f $ ← Fun(D, R) and responds to oracle query Fn(x) via f (x).

RKA-PRFs [BK03, BC10

]. Consider a pseudorandom function F pp : K × D → R with public parameters pp. Let Φ ⊆ Fun(K, K); the members of Φ are called RKD (Related-Key Deriving) functions. An adversary is said to be Φ-restricted if its oracle queries (φ, x) satisfy φ ∈ Φ. The advantage of a Φ-restricted adversary A in attacking the RKA-PRF security of F pp is defined via

Adv prf-rka Φ,Fpp (A ) = Pr RKPRFReal A Fpp ⇒ 1 -Pr RKPRFRand A Fpp ⇒ 1 .
Game RKPRFReal Fpp first runs the Setup algorithm to generate the public parameters which it outputs. It then picks a key K $ ← K at random, and responds to oracle query RKFn(φ, x) via F pp (φ(K), x). Game RKPRFRand Fpp runs Setup to generate the public parameters pp and outputs them. It then picks G $ ← Fun(K, D, R) and K $ ← K at random, and responds to oracle query RKFn(φ, x) via G(φ(K), x). We say that F pp is a Φ-RKA-secure PRF if for any Φ-restricted adversary, its advantage in attacking the RKA-PRF security is negligible.

XOR-RKA-PRFs. Let F pp : K × D → R be a pseudorandom function with public parameters pp and K = {0, 1} k for some integer k ≥ κ. We say that

F pp is XOR-RKA-secure if it is a Φ ⊕ -RKA-secure PRF according to the above definition, where Φ ⊕ = {φ s : K ∈ {0, 1} k → K ⊕ s ∈ {0, 1} k | s ∈ {0, 1} k }.

Multilinear Maps

We informally introduced multilinear maps in the introduction. Let us now introduce formal definitions, following the notations of [Zim15].

Definition 1 (Formal Symbol).

A formal symbol is a bitstring in {0, 1} * . Distinct variables denote distinct bitstrings, and we call a fresh formal symbol any bitstring in {0, 1} * that has not already been assigned to a formal symbol.

Definition 2 (Index Sets). An index set (also called index) is a set of formal symbols. This extraction is necessary for our proof under non-interactive assumptions in Section 5 to work. For our proof in the generic multilinear map model, this is not required. For this reason, our generic multilinear map model does not support extraction for the sake of simplicity. Actually, this only strengthens the result, as before extraction, the adversary still has to possibility to add top-level group elements while extracted values are not necessarily homomorphic.

Definition 3 (Multilinear Map

Conventions.

In order to ease the reading, we adopt the following conventions in the rest of the paper:

-Scalars are noted with lowercase letter, e.g. a, b, . . . -Encodings are noted either as their encoding at index set S, [a] S or simply with a hat, when the index set is clear from the context, e.g. â, b, . . . In particular, â is an encoding of the scalar a. -Index sets as well as formal variables are noted with uppercase letters, e.g.

X, S, S , . . . . -We denote by S 1 • S 2 or S 1 S 2 the union of sets S 1 and S 2 . This notation implicitly assumes that the two sets are disjoint. If S 1 is an element, then

S 1 • S 2 stands for {S 1 } • S 2 . -The top-level index set is refered as U .
We also naturally extend these notations when clear from the context, so for instance â + b = MM.Add(mm.pp, â, b) and â • b = MM.Mult(mm.pp, â, b).

Generic Multilinear Map Model

Our construction is proven secure under two non-interactive assumptions. One is very classical and is a variant of DDH. The other is relatively simple but is not classical and we prove it in the generic multilinear map model to show its plausibility. That is why we need to introduce the generic multilinear map model, in addition to the fact that we also prove in this model that our construction does not enable the adversary to produce encodings of zero.

The generic multilinear map model is similar to the generic group model [Sho97]. Roughly speaking, the adversary has only the capability to apply operations (add, multiply, and zero-test) of the multilinear map to encodings. A scheme is secure in the generic multilinear map model if for any adversary breaking the real scheme, there is a generic adversary that breaks a modified scheme in which encodings are replaced by fresh nonces, called handles, that it can supply to a stateful oracle M , defined as follows: Remark 6. In order to ease the reading, we actually use a slightly different and more intuitive characterization of the generic multilinear map oracle in our proofs.

Definition 5 (Generic Multilinear Map Oracle

Informally, instead of considering encodings as nonces, we consider these as formal polynomials (that can be computed easily), whose formal variables are substituted with their join value distribution from the real game. In our construction, formal variables are âi,b , ĉj,b , ẑi1,i2,b1,b2 -please refer to the construction in Section 3 for details. This variant characterization follows the formalization from [Zim15, Appendix B], please refer to this section for more formal definitions.

Actual Instantiations

While Definition 3 is a very natural definition and is what we actually would like as a multilinear map, up to now, we still do not know any such construction.

Known constructions [GGH13a, CLT13, GGH15, CLT15] of multilinear maps are actually "noisy" variants of our formal definition. That is, each encoding includes a random error term, and similarly to what happens for lattice-based constructions, this error term grows when performing operations (addition or multiplication). Eventually, this error term becomes too big and the MM.ZeroTest can no longer recover the correct answer. This noise implicitly restricts the number of operations that can be performed. Intuitively, in current constructions, the errors are added when performing an addition and multiplied when performing a multiplication. However, the fact that current instantiations are noisy does not pose any problem regarding our construction, as the number of operations for evaluating our pseudorandom function is fixed and independent from the instantiation of the multilinear map.

Straddling Sets

Our construction and its proofs use strong straddling sets [BGK + 14, MSW14, Zim15, BMSZ16], in order to prevent the adversary from mixing too many encodings and creating encodings of zero. We recall their definition below. We first recall that, for a set S , we say that {S 1 , . . . , S k }, for some integer k, is a partition of S , if and only if ∪ k i=1 S i = S , S i = ∅ and S i ∩ S j = ∅, for any 1 ≤ i, j ≤ k, i = j.

Definition 7 ((Strong) Straddling Set System).

For k ∈ N, a k-straddling set system over a set S consists of two partitions S 0 = {S 0,1 , . . . , S 0,k } and S 1 = {S 1,1 , . . . , S 1,k } of S such that the following holds: for any T ⊆ S , if T 0 , T 1 are distinct subsequences of S 0,1 , . . . , S 0,k , S 1,1 , . . . , S 1,k such that T 0 and T 1 are partitions of T , then T = S and T 0 = S b and T 1 = S 1-b for some b ∈ {0, 1}.

Moreover, we say that S 0 , S 1 is a strong k-straddling set system if for any

1 ≤ i, j ≤ k, S 0,i ∩ S 1,j = ∅.
A strong k-straddling set system is clearly also a k-straddling set system. Intuitively, a k-straddling set system ensures that the only two solutions to build a partition of S from combining sets in S 0 or S 1 are to use either every element in S 0 or every element in S 1 .

We are only using strong straddling set systems in this paper, for the sake of simplicity. However, we only rely on the straddling set property in all our proofs, except the proof of one of our non-interactive assumptions, namely the Sel-Prod

S 0,i = {k(i -1) + 1, k(i -1) + 2, . . . , ki} S 1,i = {i, k + i, 2k + i, . . . , k(k -1) + i} .
This construction naturally extends to any set with k 2 elements. Strong straddling set systems also satisfy the following lemma. Please refer to [BMSZ16] for proofs of constructions and lemma.

Lemma 9. Let S 0 , S 1 be a strong k-straddling set system over a set U. Then for any T U that can be written as a disjoint union of sets from S 0 , S 1 , there is a unique b ∈ {0, 1} such that T = ∪ i∈I S b,i for some I ⊆ {1, . . . , k}.

Our Construction

Let us now describe our construction of an XOR-RKA-secure pseudorandom function, for security parameter κ, key set K = {0, 1} k , with k = 2κ, and domain D = {0, 1} n for some integer n.

Intuition

Construction Overview. The starting point of our construction is the Naor-Reingold pseudorandom function, defined as

NR : ( #" a , x) ∈ Z 2n p × {0, 1} n → g n i=1
ai,x i , where #" a is the secret key. As we are interested in XOR relations, we want the key to be a bitstring. A simple solution is to tweak this construction by

considering the function f #" a , #" c : (K, x) ∈ {0, 1} k ×{0, 1} n → g k i=1 a i,K i • n j=1 ci,x i , with #" a ∈ Z k p and #" c ∈ Z n p .
It is easy to see that without knowing #" a nor #" c , the outputs of this function are computationally indistinguishable from random (they correspond to NR evaluations with key ( #" a , #" c ) and on input (K, x)). However, given a key K ∈ {0, 1} k , one needs the values #" a , #" c in order to be able to evaluate this function, so these values need to be made public. Then, it becomes very easy, even without knowing K, to distinguish this function from a random one.

That is why we use a multilinear map: this allows us to publicly reveal lowlevel encodings of elements in #" a and #" c . These encodings let anyone evaluate the function on any key K and any input x, while keeping the outputs of the function computationally indistinguishable from random to an adversary that does not know the secret key K. Formally, we let U = {1, . . . , k + n} be the set of indices for a multilinear map, (a i,b ) i∈{1,...,k},b∈{0,1} and (c j,b ) j∈{1,...,n},b∈{0,1} be random scalars in Z p and âi,b = [a i,b ] {i} be an encoding of a i,b at index index i and ĉj,b = [c j,b ] {j+k} be an encoding of c j,b at index level j + k. We then consider the function:

F pp (K, x) =   k i=1 a i,Ki n j=1 c j,xj   U = k i=1 âi,Ki • n j=1 ĉj,xj ,
with public parameters pp including the public parameters of the multilinear map as well as {â i,b } i∈{1,...,k},b∈{0,1} and (ĉ j,b ) j∈{1,...,n},b∈{0,1} .

This construction can be easily proven to be an XOR-RKA secure pseudorandom function in the generic multilinear map model, and it is also easy to show that it does not let an adversary create encodings of zero. However, it seems very hard to prove that this construction is secure under a non-interactive assumption 10 . Hence, we modify this construction by using a more complex set of indices and straddling sets. While this makes the proof in the generic multilinear map model a bit harder, this allows us to prove the security of our construction under non-interactive assumptions, whose hardness seems plausible even with current instantiations of multilinear maps. In particular, we prove in the full version [ABP17] that these assumptions are secure in the generic multilinear map model and do not let an adversary generate (non-trivial) encodings of zero.

Proof Overview. In the proof, we need to show that an oracle (s, x) → F pp (K ⊕ s, x) (where K is chosen secretly uniformly at random) looks indistinguishable from a random oracle. We first remark that we can write F pp (K ⊕ s, x) as: 10 In particular, the strategy we would like to use (replacing âi,b by independent random elements γi when evaluating the function) does not work, as the adversary would be able to distinguish between the two games by comparing âi, 0 and âi, 1 to γi (by computing the differences and applying MM.ZeroTest).

F pp (K ⊕ s, x) = k i=1 γi,si • n j=1 ĉj,xj ,
where γi,b = [a i,Ki⊕b ] {i} is an encoding of a i,Ki⊕b for i ∈ {1, . . . , k} Thus, instead of using K ∈ {0, 1} k as the key, we can use an alternative private representation: (γ i,b ) i∈{1,...,k} .

The main idea of our reduction is to be able to replace this private representation of the key, by completely random group elements, independent of the public parameters. We remark that the function

((γ i,b ) i∈{1,...,k} , s) → k i=1 γi,si ,
is a slight variant of the Naor-Reingold pseudorandom function with (γ i,b ) i∈{1,...,k} being the key and s ∈ {0, 1} k the input. It is actually possible to prove it is a pseudorandom function under a DDH-like assumption, and from that to prove that our construction is XOR-RKA-secure.

Unfortunately, it is obviously not true that given the public parameters (â i,b ) i∈{1,...,k},b∈{0,1} (which are encodings of a i,b ), the real group elements (γ i,b ) i∈{1,...,k} (which are encodings a i,Ki⊕b ) are indistinguishable from encodings of independent uniform values: it is straightforward to check that âi,b corresponds to the same scalar as γi,b or γi,1-b (depending whether K i = 0 or 1), using MM.ZeroTest (and after multiplying these group elements by the same group elements to get a top-level encodings). Our solution is to use more complex index sets based on strong straddling sets to solve this issue.

The first step consists in using a first strong k-straddling set S 0 : we use the indices of the first partition for âi,0 and âi,1 (for each i, âi,0 and âi,1 get the same index), and the indices of the second partition for γi,0 and γi,1 . This prevents the adversary from comparing one group element âi,b with a group element γi,b directly. But this is not sufficient, as the adversary still could check whether:

k i=1 (â i,0 + âi,1 ) = k i=1
(γ i,0 + γi,1 ) , for example. When (γ i,b ) i∈{1,...,k} are correctly generated, the equality is satisfied, while otherwise, it is not with overwhelming probability. More generally, the adversary can generate expression which contains an exponential number of monomials when expanded. We do not know how to prove anything reasonable on these expressions, so instead, we are using k additional strong k-straddling sets to prevent this from happening, in a similar way as they are used in [Zim15].

Actual Construction

Index set. First, similarly to [Zim15], for each i ∈ {0, . . . , k}, we construct a strong k-straddling set system over a set S i of 2k -1 fresh formal symbols. We denote by S i,b the two partitions forming each of this straddling set, for b ∈ {0, 1}, and by S i,b,j their elements, for 1 ≤ j ≤ k. We also define:

BitCommit i,b = S i,b,i BitFill i1,i2,b1,b2 = S i1,b1,i2 • S i2,b2,i1
for any i, i 1 , i 2 ∈ {1, . . . , k} and b, b 1 , b 2 ∈ {0, 1}. Intuitively, the straddling set systems S i for i ≥ 1 play the same role as in [Zim15] (preventing the adversary from mixing an exponential number of inputs), while S 0 is used in the proof to prevent the adversary from mixing the private representation of the key with the public parameters. Let X j be fresh formal symbols for j ∈ {1, . . . , n}. We then define the top-level index set as follows:

U = k i=0 S i n j=1 X j .
Setup. The algorithm Setup first generates the parameters (mm.pp, mm.sp, p) for the multilinear map by running MM.Setup(1 κ , U ). Then it generates the following elements:

a i,b $ ← Z p for i ∈ {1, . . . , k} and b ∈ {0, 1} âi,b ← [a i,b ] S0,0,iBitCommit i,b for i ∈ {1, . . . , k} and b ∈ {0, 1} c j,b $ ← Z p for j ∈ {1, . . . , n} and b ∈ {0, 1} ĉj,b ← [c j,b ] Xj for j ∈ {1, . . . , n} and b ∈ {0, 1} ẑi1,i2,b1,b2 ← [1] BitFill i 1 ,i 2 ,b 1 ,b 2 for i 1 , i 2 ∈ {1, . . . , k} and b 1 , b 2 ∈ {0, 1} with i 1 < i 2 ,
and outputs the following parameters:

pp = mm.pp, (â i,b ) i,b , (ĉ j,b ) j,b , (ẑ i1,i2,b1,b2 ) i1,i2,b1,b2 .
Intuitively, BitCommit i,b = S i,b,i is associated to the (public) encoding used to evaluate the function if the i-th bit of the key is b. By definition of a straddling set, the only way to reach the top-level U , which contains S i , once we have used an encoding with index S i,b,i is to use every index S i,b,j with j = i. These is done by multiplying the terms ẑi,j,Ki,Kj . Therefore, using K i = b is like "committing" to the partition S i,b of S i , and terms ẑi,j,Ki,Kj are then used to "fill" this partition.

Remark 10. For the sake of simplicity, we set ẑi1,i2,b1,b2 to be encodings of 1, but one could also simply set it to encodings of a random value, as long as they are all encodings of the same value.

Evaluation. The output of the PRF on a key K ∈ {0, 1} k and an input x ∈ {0, 1} n is

F pp (K, x) = MM.Extract   k i=1 âi,Ki n j=1 ĉj,xj k i1=1 k i2=i1+1 ẑi1,i2,Ki 1 ,Ki 2   .
We can re-write it as:

F pp (K, x) = MM.Extract     k i=1 a i,Ki n j=1 c j,xi   U   .
Extraction. As explained in Remark 4, the role of extraction (MM.Extract) is dual. First, it ensures the correctness of the PRF, as in currently known instantiations of multilinear maps [GGH13a, CLT13, GGH15, CLT15], a scalar has many different encodings. Second, it is used in our proof of security under non-interactive assumptions in Section 5, as in the security proof we change the way the group element

k i=1 âi,Ki n j=1 ĉj,xj k i1=1 k i2=i1+1 ẑi1,i2,Ki 1 ,Ki 2
is computed. We indeed recall that due to the fact that a scalar has many different encodings, any group element (as the above one) leaks information on the exact computation used to obtain it, instead of just depending on its discrete logarithm. The usual way to solve this issue is to randomize the resulting group element using encodings of zero. However, in this paper, we do not want to use any encoding of zeros, hence the requirement for this extraction. For the proof in the generic multilinear map model in Section 4, this is not an issue, and we just ignore the extraction (see Remark 4).

Security in the Generic Multilinear Map Model

In this section, we prove the security of our construction in the generic multilinear map model. As already explained at the end of Section 3, we suppose in this section that no extraction is performed. We actually even prove that no polynomialtime adversary can construct a (non-trivial) encoding of zero, in any of the two experiments RKPRFReal and RKPRFRand, with non-negligible probability. This implies, in particular, that these two experiments cannot be distinguished by a polynomial-time adversary, in the generic multilinear map model, as an adversary only sees handles which only leak information when two of them correspond to the same (top-level) element.

This section is mainly a warm-up to familiarize with the model, since the fact that we prove our construction under some assumptions that are proven secure in the generic multilinear map model and proven to not let an adversary generate encodings of zero also implies the results below. However, it is very simple to modify the proof below in order to prove the security of the simplified construction proposed in Section 3.1, which is of independent interest.

We first need to formally define the notion of (non-trivial) encoding of zero. We follow the definition of Badrinarayanan et al. [BMSZ16].

Definition 11 ((Non-trivial) encoding of zero). An adversary A in the generic multilinear map model with multilinear map oracle M returns a (nontrivial) encoding of zero if it returns a handle h (output by M

) such that h corresponds to the element 0 in M 's table and the polynomial corresponding to the handle is not identically null.

Theorem 12 (Impossibility of constructing encodings of zero). In the generic multilinear map model with oracle M , for any adversary A making at most q M queries to the oracle M and q RKFn queries to the oracle RKFn, we have:

Pr PRFReal A Fpp ⇒ an encoding of 0 ≤ q M q RKFn 2 k + k + n p and Pr PRFRand A Fpp ⇒ an encoding of 0 ≤ q M k + n p .
Proof (Theorem 12). We first introduce a technical lemma, whose proof is given in the full version [ABP17].

Lemma 13. Let k and n be two positive integers. Let U be the index defined in Section 3. Let ẑi1,i2,b1,b2

= [1] BitFill i 1 ,i 2 ,b 1 ,b 2 for 1 ≤ i 1 < i 2 ≤ k and b 1 , b 2 ∈ {0, 1}. Let Z 1 and Z 2 be two subsets of {(i 1 , i 2 ) | 1 ≤ i 1 < i 2 ≤ k} × {0, 1} 2 . If t 1 = (i1,i2,b1,b2)∈Z1 ẑi1,i2,b1,b2 and t 2 = (i1,i2,b1,b2)∈Z2 ẑi1,i2,b1,b2 have the same index set, then Z 1 = Z 2 .
We need to show that the adversary cannot generate a non-trivial encoding of zero.

RKPRFRand A

Fpp . We start by proving it in the game RKPRFRand A Fpp . In this game, except for ẑi1,i2,b1,b2 , all the handles the adversary sees correspond to fresh new formal variables, as the oracle RKFn only returns fresh new formal variables (of index U ). The only polynomials the adversary can generate are therefore of the form:

P = L =1 Q (i1,i2,b1,b2)∈Z ẑi1,i2,b1,b2 ,
where Q are polynomials over all the elements except ẑi1,i2,b1,b2 , and Z are distinct subsets of

{(i 1 , i 2 ) | 1 ≤ i 1 < i 2 ≤ k} × {0, 1} 2 (L might be exponential in q M ,
but that does not matter for what follows).

Let us now show that if P is not the zero polynomial, then when replacing ẑi1,i2,b1,b2 by 1, the resulting polynomial is still a non-zero polynomial. From Lemma 13, one can assume that elements (i1,i2,b1,b2)∈Z ẑi1,i2,b1,b2 all have distinct indices. Therefore, the polynomials Q all have distinct indices too. No monomial in two different Q of the sum Q (when forgetting the indices) can therefore cancel out, otherwise this would mean that the adversary can construct two equal monomials (without ẑi,b ) with two different indices. This is impossible as, except for ẑi,b , two distinct handles correspond to two fresh variables (or in other words, all the handles except ẑi,b are encodings of scalars chosen uniformly and independently at random).

We therefore simulate the oracle M as follows: we do everything as normal, but we make the zero-testing oracle always output "non-zero" except when its input corresponds to the zero polynomial. The Schwarz-Zippel lemma ensures that any non-zero polynomial of degree at most k + n and whose variables are fixed to uniformly random values in Z p does not evaluate to zero, except with probability at most (k + n)/p. In other words, the zero-testing oracle outputs "zero" on a non-zero polynomial with probability at most (k + n)/p, as this polynomial remains non-zero and has degree at most (k + n), when we replace ẑi1,i2,b1,b2 by 1. As we can suppose that the zero-testing oracle is queried with the output of the adversary without loss of generality, using at most q M hybrid games (replacing one-by-one every output of the zero-testing oracle with "non-zero") we get that:

Pr PRFRand A Fpp ⇒ an encoding of 0 ≤ q M k + n p .
RKPRFReal A Fpp . Let us now look at the game RKPRFReal A Fpp . The analysis is more complicated as the adversary has access to new formal variables ŷs,x = F pp (K ⊕ s, x) returned by queries RKFn(φ s , x).

We use the same simulator as in the previous case. We need to show that if a polynomial P produced by the adversary is not zero, it remains non-zero when ẑi1,i2,b1,b2 is replaced by 1 and ŷs,x is replaced by its value.

We first consider the case where P is not a top-level polynomial. In this case, P cannot contain these new variables ŷs,x as these variables are top-level. Then, as in RKPRFRand A Fpp , the zero-testing oracle outputs "non-zero" except with probability at most (k + n)/p.

Let us now suppose that P is a top-level polynomial. This polynomial has the form:

P = L =1 Q k i=1 âi,K ,i k i1=1 k i2=i1+1 ẑi1,i2,K ,i 1 ,K ,i 2 + q j=1 λ j ŷsj,xj ,
with L being a non-negative integer (possibly exponential in q M ), Q being non-zero polynomials in the formal variables ĉj,b , K being distinct bitstrings in {0, 1} k (chosen by the adversary), q an integer less or equal to q RKFn , (s 1 , x 1 ), . . . , (s q , x q ) queries to RKFn, and λ j some scalar in Z p . Indeed, the adversary can ask for an encoding of any polynomial of the form Q k i=1 âi,K ,i , and by definition of straddling set systems, the unique way to obtain a toplevel encoding from such a polynomial is by multiplying it with an encoding of

k i1=1 k i2=i1+1 ẑi1,i2,K ,i 1 ,K ,i 2
. Let us suppose that P is not zero but becomes zero when ẑi1,i2,b1,b2 is replaced by 1 and ŷs,x is replaced by its value. In this case, in particular, the first monomial (for any order) of the term

Q 1 k i=1 âi,K 1,i k i1=1 k i2=i1+1 ẑi1,i2,K 1,i 1 ,K 1,i 2
necessarily needs to be canceled out by some ŷsj,xj . The probability over K $ ← {0, 1} k that this happens is at most:

Pr [ ∃j ∈ {1, . . . , q }, K 1 = K ⊕ s j ] ≤ q 2 k ≤ q RKFn 2 k .
As before, thanks to the Schwarz-Zippel lemma, we get that the zero-testing oracle outputs "zero", on input a non-zero polynomial, with probability at most:

q RKFn 2 k + k + n p .
This concludes the proof of Theorem 12.

Remark 14. We never use the properties of the straddling set system S 0 in this proof. These properties are only used in our proof under non-interactive assumptions in Section 5.

We obtain the following immediate corollary.

Corollary 15 (Security in the generic multilinear map model). Let A be an adversary in the generic multilinear map model with oracle M against the XOR-RKA security of the PRF F defined in Section 3. If A makes at most q M queries to the oracle M and q RKFn queries to the oracle RKFn, then:

Adv prf-rka Φ⊕,Fpp (A ) ≤ q M q RKFn 2 k + 2q M (k + n) p .
Proof (Corollary 15). We just consider an intermediate game where we simulate everything as before except the zero-testing oracle which always outputs "nonzero" unless its input is zero, as a polynomial. This game is indistinguishable from both RKPRFReal A Fpp and RKPRFRand A Fpp according to Theorem 12 (up to the bounds in this lemma). Corollary 15 follows.

Security Under Non-Interactive Assumptions

In this section, we show that our construction is an XOR-RKA PRF under two non-interactive assumptions defined below.

Assumptions

We use two assumptions that we call the (k, n, X, Y )-XY-DDH assumption, which is roughly a generalization of the standard DDH assumption, and the (k, n)-Sel-Prod assumption. We show in the full version [ABP17] that both these assumptions are secure in the generic multilinear map model, and even that an adversary against these assumptions cannot generate encodings of zero. As explained in the "concrete instantiations" paragraph of Section 1, contrary to most assumptions considered on multilinear maps (e.g., classical DDH-like assumptions and the multilinear subgroup assumption [GLW14, GLSW15]), these assumptions are therefore plausible at least with two current instantiations of multilinear maps [CLT13, GGH15].

To ensure the impossibility of generating encodings of zero, in these two assumptions, we restrict the adversary's capabilities as follows: it is only provided parameters mm.pp, so it can only run MM.Add, MM.Mult and MM.ZeroTest (and of course use the elements generated by the assumption), but we do not allow the adversary to generate new encodings of a chosen scalar. In particular, this forces us to let the assumption contain the group elements ẑi1,i2,b1,b2 . It is straightforward to get rid of these additional elements by allowing the adversary to generate any element of the multilinear map, at the cost of getting an implausible assumption under current instantiations of multilinear maps.

Finally, our assumption implicitly contains a list L of a polynomial number of encodings of independent uniform random values at non-zero index, index being implicit parameters of the assumption. We could avoid this artifact with the previous proposition as well, or by giving a sufficient number of encodings of 0 and 1, but once again, in that case, the assumption would most likely not hold with currently known multilinear maps instantiations. We believe this is a small price to pay to get plausible assumptions, as the resulting assumptions are still non-interactive.

We insist on the fact that the encodings in L are encodings of independent uniformly random scalars. At least in the generic multilinear group model, our assumptions hold whatever the list of indices of these encodings is. We do not have any constraint on this list of indices. This assumption is very close to the classical DDH assumption with indices, with two main differences: the presence of elements ẑi1,i2,b1,b2 which are necessary to prove our construction and the implicit presence of encodings of random values at non-zero indices (list L described previously) instead of a polynomial number of encodings of 0 and 1. Without the elements ẑi1,i2,b1,b2 , the proof of this assumption in the generic multilinear map model would be completely straightforward. The difficulty of the proof is to deal with these elements.

In the security proof of our construction, this assumption is used in a similar way as the DDH assumption in the proof of the Naor-Reingold PRF. Definition 17 ((k, n)-Sel-Prod). Let k and n be two positive integers. The advantage of an adversary D against the (k, n, X, Y )-Sel-Prod problem is:

(k, n, X, Y )-XY-DDH-L D (k, n, X, Y )-XY-DDH-R D proc Initialize (mm.sp, mm.pp) $ ← MM.Setup(1 κ , U ) d0, d1, e $ ← Zp d0 ← [d0] X ; d1 ← [d1] X ê0 ← [ed0] XY ; ê1 ← [ed1] XY For i1, i2 ∈ {1, . . . , k} and b1, b2 ∈ {0, 1} ẑi 1 ,i 2 ,b 1 ,b 2 ← [1] BitFill i 1 ,i 2 ,b 1 ,b 2 Return (L, mm.pp, d0, d1, ê0, ê1, (ẑ i 1 ,i 2 ,b 1 ,b 2 )) proc Finalize(b) Return b proc Initialize (mm.sp, mm.pp) $ ← MM.Setup(1 κ , U ) d0, d1, e0, e1 $ ← Zp d0 ← [d0] X ; d1 ← [d1] X ê0 ← [e0] XY ; ê1 ← [e1] XY For i1, i2 ∈ {1, . . . , k} and b1, b2 ∈ {0, 1} ẑi 1 ,i 2 ,b 1 ,b 2 ← [1] BitFill i 1 ,i 2 ,b 1 ,b 2 Return (L, mm.pp, d0, d1, ê0, ê1, (ẑ i 1 ,i 2 ,b 1 ,b 2 )) proc Finalize(b) Return b (k, n)-Sel-Prod-L D (k, n)-Sel-Prod-R D proc Initialize (mm.sp, mm.pp) $ ← MM.Setup(1 κ , U ) K $ ← {0, 1} k For i ∈ {1, . . . , k} and b ∈ {0, 1} a i,b $ ← Zp; γ i,K i ⊕b ← a i,b âi,b ← [a i,b ] S 0,0,i BitCommit i,b γi,K i ⊕b ← [γ i,K i ⊕b ] S 0,1,i BitCommit i,K i ⊕b For i1, i2 ∈ {1, . . . , k} and b1, b2 ∈ {0, 1} ẑi 1 ,i 2 ,b 1 ,b 2 ← [1] BitFill i 1 ,i 2 ,b 1 ,b 2 Return (L, mm.pp, (â i,b ), (γ i,b ), (ẑ i 1 ,i 2 ,b 1 ,b 2 )) proc Finalize(b) Return b proc Initialize (mm.sp, mm.pp) $ ← MM.Setup(1 κ , U ) For i ∈ {1, . . . , k} and b ∈ {0, 1} a i,b $ ← Zp; γ i,b $ ← Zp âi,b ← [a i,b ] S 0,0,i BitCommit i,b γi,b ← [γ i,b ] S 0,1,i BitCommit i,b For i1, i2 ∈ {1, . . . , k} and b1, b2 ∈ {0, 1} ẑi 1 ,i 2 ,b 1 ,b 2 ← [1] BitFill i 1 ,i 2 ,b 1 ,b 2 Return (L, mm.pp, (â i,b ), (γ i,b ), (ẑ i 1 ,i 2 ,b 1 ,b 2 )) proc
Adv (k,n)-Sel-Prod (D) = Pr (k, n)-Sel-Prod-L D ⇒ 1 - Pr (k, n)-Sel-Prod-R D ⇒ 1 ,
where the games (k, n)-Sel-Prod-L D and (k, n)-Sel-Prod-R D are defined in Fig. 2. The (n, k)-Sel-Prod assumption holds when this advantage is negligible for any polynomial-time adversary D.

Intuitively, this assumption states that, given a low-level encodings of a i,0 and a i,1 at indices S 0,i from the first partition of the straddling set S , where i ∈ {1, . . . , k}, then it is hard to distinguish low-level encodings of γ i,0 = a i,Ki and γ i,1 = a i,1-Ki (where K i is a random bit) at indices S 1,i from encodings of fresh random values (at the same index). The hardness of this assumption crucially relies on two facts: First, one can only compare top-level encodings, and thus, the only way to compare elements whose index is in the first partition of S with elements whose index is in the second partition is to combine k such elements to reach the same index. Second, the latter can be hard only if k, the size of the partitions, is big. Indeed, assume k = 2, then one can just guess K 1 and K 2 and check if the relation carries on between encodings of a i,b and encodings of γ i,b . Therefore, we show that if k is big enough, this assumption holds in the generic multilinear map model.

As explained in Section 3.1, this assumption is used to switch from the key K to a private independent key represented by the encodings γ i,b . More precisely, under this assumption, we can replace the encodings âi,Ki⊕si at index from the first partition of the straddling set S 0 , used in the computation of the output with relation s, to encodings of uniformly random scalars at index from the second partition of S 0 . In particular, doing this change, we no longer need to know the key K to simulate correctly the output, but only the relations s for each query.

Remark 18. For the sake of simplicity, we do not explicitly specify the noise level in our assumptions. It can easily be made to work with our proof.

Security of our Construction

In this whole section, we set S = k i=0 S i and S = k i=1 S i , so S = S 0 • S . Please refer to Section 3 for notation.

Theorem 19 (Security under non-interactive assumptions).

Let A be a polynomial-time adversary against the XOR-RKA security of the PRF F defined in Section 3. We suppose that A makes at most q RKFn queries to the oracle RKFn. We can define an adversary D against the (k, n)-Sel-Prod problem, (k -1) adversaries B i against the (k, n, S i -1 i=1 S 0,1,i , S 0,1,i )-XY-DDH problem for i ∈ {2, . . . , k}, and n adversaries C j against the (k, n, S j -1 j=1 X j , X j )-XY-DDH problem for j ∈ {1, . . . , n}, such that:

Adv prf-rka Φ⊕,Fpp (A ) ≤ Adv (k,n)-Sel-Prod (D)+ k i =2 q RKFn • Adv (k,n,S i -1 i=1 S0,1,i,S 0,1,i )-XY-DDH (B i )+ n j =1 q RKFn • Adv (k,n,S j -1 j=1 Xj ,X j )-XY-DDH (C j ) .
Furthermore, all these adversaries run in polynomial time (their running time is approximately the same as A ).

Below, we provide a sketch of the proof. The full proof is given in the full version [ABP17].

Sketch of proof.

The proof follows a sequence of hybrid games. The first hybrid corresponds exactly to RKPRFReal A F , while the last game corresponds to RKPRFRand A F . Here is how we proceed. First, instead of computing the output using encodings âi,b of a i,b with index S 0,0,i BitCommit i,b , we use encodings γi,b of a i,Ki⊕b with index S 0,1,i BitCommit i,Ki⊕b . That is, we use the second partition S 0,1 of the straddling set S 0 instead of the first one (S 0,0 ) to reach top-level index (which contains S 0 ). Also, we now compute the output using only the relation s instead of the key K. More precisely, the output on a query (s, x) is computed as: which can be computed without knowing K. This does not change anything regarding the output (thanks to the extraction), so these two games are indistinguishable.

However, using the (k, n)-Sel-Prod assumption, we can now switch the encodings γi,b to encodings of fresh random scalars γ i,b ∈ Z p . The rest of the proof is very similar to the proof of the Naor-Reingold pseudorandom function. We do k + n hybrid games, where in the j-th hybrid, we just switch products of encodings j i=1 γi,si to encodings of uniformly fresh random values using the XY-DDH assumption with the proper indices. These modifications are done in a lazy fashion to obtain a polynomial-time reduction. of this work was done while the second author was at École normale supérieure, Paris, France, and at IBM Research, Yorktown Heights, NY, USA. Part of this work was done while the third author was at École normale supérieure, Paris, France, and at UCLA, Los Angeles, CA, USA.

  [a] S and U denotes the top-level index set. We can add two elements [a] S and [b] S belonging to the same index set S to obtain [a + b] S . We can also multiply elements [a] S1 and [b] S2 to compute [a • b] S1∪S2 to obtain the encoding of a • b with respect to the index set S 1 ∪ S 2 , as long as the two index sets are disjoint (S 1 ∩ S 2 = ∅). Finally, it is possible to test whether an element at level U is an encoding of 0. Let k and n be the lengths of the secret key K and input x, respectively, and let U = {1, . . . , k + n}. Next, let {a i,b } i∈[k],b∈{0,1} and {c j,b } j∈[n],b∈{0,1} be random scalars in Z p and let âi,b = [a i,b ] {i} be the encoding of a i,b at index level {i} and ĉj,b = [c j,b ] {j+k} be the encoding of c j,b at index level {j + k}. The starting point of our construction is the function

  assumption. Let us now recall the construction of strong straddling set systems from[MSW14]. For the sake of completeness, we also recall the construction of straddling set systems from [BGK + 14] in the full version [ABP17].Constructions 8 (Strong Straddling Set Systems [MSW14]). Let k be a fixed integer and let S = {1, . . . , k 2 }. Then the following partitions S b = (S b,1 , . . . , S b,k ), for b ∈ {0, 1}, form a strong k-straddling set system over S :

Fig. 1 .

 1 Fig. 1. Construction of strong 5-straddling set systems

Definition 16 (

 16 (k, n, X, Y )-XY-DDH). Let k and n be two positive integers. Let X and Y be two non-empty and disjoint indices in the index set U of our construction in Section 3. The advantage of an adversary D against the (k, n, X, Y )-XY-DDH problem is:Adv (k,n,X,Y )-XY-DDH (D) = Pr (k, n, X, Y )-XY-DDH-L D ⇒ 1 -Pr (k, n, X, Y )-XY-DDH-R D ⇒ 1 ,where the games (k, n, X, Y )-XY-DDH-L D and (k, n, X, Y )-XY-DDH-R D are defined in Fig.2. The (n, k, X, Y )-XY-DDH assumption holds when this advantage is negligible for any polynomial-time adversary D.

FinalizeFig. 2 .

 2 Fig. 2. Games defining the advantage of an adversary D against the XY-DDH and Sel-Prod problems.

  ). A generic multilinear map oracle is a stateful oracle M that responds to queries as follows:

-On a query MM.Setup(1 κ , U ), M generates a prime number p and parameters mm.pp, mm.sp as fresh nonces chosen uniformly at random from {0, 1} κ . It also initializes an internal table T ← [] that it uses to store queries and handles. It finally returns (mm.pp, mm.sp, p) and set internal state so that subsequent MM.Setup queries fail. -On a query MM.Encode(z, x, S), with z ∈ {0, 1} κ and x ∈ Z p , it checks that z = mm.sp and S ⊆ U and outputs ⊥ if the check fails, otherwise it generates a fresh handle h $ ← {0, 1} κ , adds h → (x, S) to T , and returns h. -On a query MM.Add(z, h 1 , h 2 ), with z, h 1 , h 2 ∈ {0, 1} κ , it checks that z = mm.pp, that h 1 and h 2 are handles in T which are mapped to values (x 1 , S 1 ) and (x 2 , S 2 ) such that S 1 = S 2 = S ⊆ U , and returns ⊥ if the check fails. If it passes, it generates a fresh handle h $ ← {0, 1} κ , adds h → (x 1 + x 2 , S) to T , and returns h. -On a query MM.Mult(z, h 1 , h 2 ), with z, h 1 , h 2 ∈ {0, 1} κ , it checks z = mm.pp, that h 1 and h 2 are handles in T which are mapped to values (x 1 , S 1 ) and (x 2 , S 2 ) such that S 1 ∪S 2 ⊆ U and S 1 ∩S 2 = ∅, and returns ⊥ if the check fails. If it passes, it generates a fresh handle h $ ← {0, 1} κ , adds h → (x 1 x 2 , S 1 ∪ S 2 ) to T , and returns h. -On a query MM.ZeroTest(z, h), with z, h ∈ {0, 1} κ , it checks z = mm.pp, that h is a handle in T such that it is mapped to a value (x, U ), and returns ⊥ if the check fails. If it passes, it returns "zero" if x = 0 and "non-zero" otherwise.

  inCryptology -EUROCRYPT 2010, volume 6110 of Lecture Notes in Computer Science, pages 299-319. Springer, Heidelberg, May / June 2010. BGK + 14. Boaz Barak, Sanjam Garg, Yael Tauman Kalai, Omer Paneth, and Amit Sahai. Protecting obfuscation against algebraic attacks. In Phong Q. Nguyen and Elisabeth Oswald, editors, Advances in Cryptology -EURO-CRYPT 2014, volume 8441 of Lecture Notes in Computer Science, pages 221-238. Springer, Heidelberg, May 2014. Bih94. Eli Biham. New types of cryptanalytic attacks using related keys (extended abstract). In Tor Helleseth, editor, Advances in Cryptology -EU-ROCRYPT'93, volume 765 of Lecture Notes in Computer Science, pages 398-409. Springer, Heidelberg, May 1994. BK03. Mihir Bellare and Tadayoshi Kohno. A theoretical treatment of related-key attacks: RKA-PRPs, RKA-PRFs, and applications. In Eli Biham, editor, Advances in Cryptology -EUROCRYPT 2003, volume 2656 of Lecture Notes in Computer Science, pages 491-506. Springer, Heidelberg, May 2003. BLMR13. Dan Boneh, Kevin Lewi, Hart William Montgomery, and Ananth Raghunathan. Key homomorphic PRFs and their applications. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology -CRYPTO 2013, Part I, volume 8042 of Lecture Notes in Computer Science, pages 410-428. Springer, Heidelberg, August 2013. BMSZ16. Saikrishna Badrinarayanan, Eric Miles, Amit Sahai, and Mark Zhandry. Post-zeroizing obfuscation: New mathematical tools, and the case of evasive circuits. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology -EUROCRYPT 2016, Part II, volume 9666 of Lecture Notes in Computer Science, pages 764-791. Springer, Heidelberg, May 2016. BP14. Abhishek Banerjee and Chris Peikert. New and improved key-homomorphic pseudorandom functions. In Juan A. Garay and Rosario Gennaro, editors, Advances in Cryptology -CRYPTO 2014, Part I, volume 8616 of Lecture Notes in Computer Science, pages 353-370. Springer, Heidelberg, August 2014. BR06. Mihir Bellare and Phillip Rogaway. The security of triple encryption and a framework for code-based game-playing proofs. In Serge Vaudenay, editor, Advances in Cryptology -EUROCRYPT 2006, volume 4004 of Lecture Notes in Computer Science, pages 409-426. Springer, Heidelberg, May / June 2006. BR14. Zvika Brakerski and Guy N. Rothblum. Virtual black-box obfuscation for all circuits via generic graded encoding. In Yehuda Lindell, editor, TCC 2014: 11th Theory of Cryptography Conference, volume 8349 of Lecture Notes in Computer Science, pages 1-25. Springer, Heidelberg, February 2014. CFL + 16. Jung Hee Cheon, Pierre-Alain Fouque, Changmin Lee, Brice Minaud, and Hansol Ryu. Cryptanalysis of the new CLT multilinear map over the integers. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology -EUROCRYPT 2016, Part I, volume 9665 of Lecture Notes in Computer Science, pages 509-536. Springer, Heidelberg, May 2016. CGH + 15. Jean-Sébastien Coron, Craig Gentry, Shai Halevi, Tancrède Lepoint, Hemanta K. Maji, Eric Miles, Mariana Raykova, Amit Sahai, and Mehdi Tibouchi. Zeroizing without low-level zeroes: New MMAP attacks and their limitations. In Rosario Gennaro and Matthew J. B. Robshaw, editors, Advances in Cryptology -CRYPTO 2015, Part I, volume 9215 of Lecture

In practice, laser fault attacks can be used to switch bits inside a chip, but it seems unlikely that such a fault attack can be used to apply an operation modulo some prime number on a register.

Please note that these common parameters are public and can therefore be stored in a non-secure read-only part of the memory which can potentially more easily be made tamper-proof.

Note that, to prove that two games are indistinguishable in the generic multilinear map model, it suffices to prove that the adversary cannot generate encodings of zeros in either game as it would only obtain random handles which carry no information.

The security result in Section 4 is therefore implied by the security result in Section 5. Section 4 should be seen as a warm-up for Section 5.

The GGH15 multilinear map is defined over a graph. Index sets (and in particular straddling set indexes) are defined independently of the graph structure of GGH15, hence they can be implemented as on GGH13. Specifically, index sets are based on the zi's, as for GGH13, and not on the graph structure. More precisely, the construction relies on distinct zi's for every index and an encoding with index set S depends on i∈S zi, exactly as on GGH13. This is completely independent of the graph structure and then we can use a simple chain as a graph, as in the case of indistinguishable

Acknowledgements

. The first author was supported in part by the European Research Council under the European Union's Seventh Framework Programme (FP7/2007-2013 Grant Agreement 339563 -CryptoCloud). The second author was supported in part by the Defense Advanced Research Projects Agency (DARPA) and Army Research Office (ARO) under Contract No. W911NF-15-C-0236. Part

Notes in Computer Science, pages 247-266. Springer, Heidelberg, August 2015. CGH17. Yilei Chen, Craig Gentry, and Shai Halevi. Cryptanalyses of candidate branching program obfuscators. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, Advances in Cryptology -EUROCRYPT 2017, Part III, volume 10212 of Lecture Notes in Computer Science, pages 278-307. Springer, Heidelberg, April / May 2017. CHKL18. Jung Hee Cheon, Minki Hhan, Jiseung Kim, and Changmin Lee. Cryptanalysis on the hhss obfuscation arising from absence of safeguards. IEEE Access, 6:40096-40104, 2018. CHL + 15. Jung Hee Cheon, Kyoohyung Han, Changmin Lee, Hansol Ryu, and Damien Stehlé. Cryptanalysis of the multilinear map over the integers. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology -EURO-CRYPT 2015, Part I, volume 9056 of Lecture Notes in Computer Science, pages 3-12. Springer, Heidelberg, April 2015. CJL16. Jung Hee Cheon, Jinhyuck Jeong, and Changmin Lee. An algorithm for ntru problems and cryptanalysis of the ggh multilinear map without a low-level encoding of zero. LMS Journal of Computation and Mathematics, 19(A):255-266, 2016. CLLT16. Jean-Sébastien Coron, Moon Sung Lee, Tancrède Lepoint, and Mehdi Tibouchi. Cryptanalysis of GGH15 multilinear maps. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology -CRYPTO 2016, Part II, volume 9815 of Lecture Notes in Computer Science, pages 607-628. Springer, Heidelberg, August 2016. CLLT17. Jean-Sébastien Coron, Moon Sung Lee, Tancrède Lepoint, and Mehdi Tibouchi. Zeroizing attacks on indistinguishability obfuscation over CLT13. In Serge Fehr, editor, PKC 2017: 20th International Conference on Theory and Practice of Public Key Cryptography, Part I, volume 10174 of Lecture Notes in Computer Science, pages 41-58. Springer, Heidelberg, March 2017. CLT13. Jean-Sébastien Coron, Tancrède Lepoint, and Mehdi Tibouchi. Practical multilinear maps over the integers. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology -CRYPTO 2013, Part I, volume 8042 of Lecture Notes in Computer Science, pages 476-493. Springer, Heidelberg, August 2013. CLT15. Jean-Sébastien Coron, Tancrède Lepoint, and Mehdi Tibouchi. New multilinear maps over the integers. In Rosario Gennaro and Matthew J. B. Robshaw, editors, Advances in Cryptology -CRYPTO 2015, Part I, volume 9215 of Lecture Notes in Computer Science, pages 267-286. Springer, Heidelberg, August 2015. CS15. Benoit Cogliati and Yannick Seurin. On the provable security of the iterated Even-Mansour cipher against related-key and chosen-key attacks. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology -EUROCRYPT 2015, Part I, volume 9056 of Lecture Notes in Computer Science, pages 584-613. Springer, Heidelberg, April 2015. CVW18. Yilei Chen, Vinod Vaikuntanathan, and Hoeteck Wee. GGH15 beyond permutation branching programs: Proofs, attacks, and candidates. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology -CRYPTO 2018, Part II, volume 10992 of Lecture Notes in Computer Science, pages 577-607. Springer, Heidelberg, August 2018.