Thierry Mefenza
email: mefenza@di.ens.fr

Damien Vergnaud
email: damien.vergnaud@ens.fr

Polynomial Interpolation of the Naor-Reingold Pseudo-Random Function

Keywords: Naor-Reingold pseudo-random function, polynomial interpolation, finite fields, elliptic curves ,94A60

We prove lower bounds on the degree of polynomials interpolating the Naor-Reingold Pseudo-random Function over a finite field and over the group of points on an elliptic curve over a finite field.

Introduction

In cryptography, a pseudo-random function family is a collection of functions (that can be evaluated efficiently using a secret-key) with the property that an adversary cannot efficiently observe any significant difference between the input-output behavior of a random instance of the family or that of a random function.

More formally, we consider collections of functions {F n : K n × D n → R n } n∈N that can be evaluated by a (deterministic) polynomial-time Turing Machine. We define an adversary as a (non-uniform) probabilistic polynomialtime oracle Turing machine with either access to:

an oracle implementing a function F : D n → R n defined by picking uniformly at random a secret-key k ∈ K n such that F (m) = F n (k, m) for any m ∈ D n ; or an oracle simulating a truly random function F : D n → R n (i.e. whose outputs are sampled uniformly and independently at random).

This adversary can decide which queries to make to the oracle, perhaps based on answers received to previous queries and eventually, it outputs a single bit (which is its decision as to which function the oracle is implementing). The advantage of the adversary is the function of n defined as the difference of the probabilities (taken over the random choices made by the adversary and the oracle) that the adversary outputs 1 in the two cases. A collection of functions {F n : K n × D n → R n } n∈N is a pseudo-random function family if and only if no adversary with advantage asymptotically larger than the inverse of a polynomial exists.

In 1997, Naor and Reingold [START_REF] Naor | Number-theoretic constructions of efficient pseudo-random functions[END_REF][START_REF] Naor | Number-theoretic constructions of efficient pseudo-random functions[END_REF] proposed a (candidate) pseudo-random function family which takes inputs in {0, 1} n (for some parameter n) and outputs an element in some (multiplicatively written) group G of prime order with generator g. The secret key is an n-dimensional vector a = (a 1 , . . . , a n ) ∈ ((Z/ Z) * ) n and the Naor-Reingold function is defined as:

f a : {0, 1} n -→ G (x 1 , . . . , x n ) -→ f a (x 1 , . . . , x n ) = g n i=1 a x i i mod
The evaluation of f a is thus efficient 1 since it consists only in n modular multiplications in Z/ Z and one modular exponentiation in G. To lighten the notation, given an n-dimensional vector a = (a 1 , . . . , a n ) ∈ ((Z/ Z) * ) n and a variable x that will denote indifferently an n-bit string (x 1 , . . . , x n ) ∈ {0, 1} n or an integer x ∈ {0, 1, . . . , 2 n -1} (which implicitly defines (x 1 , . . . , x n ) ∈ {0, 1} n the bit representation of x with extra leading zeros if necessary), we denote a x the element in F defined by a x = a x1 1 • • • a xn n mod . With this notation, the Naor-Reingold function is simply defined by f a (x) = g a x .

It is shown in [START_REF] Naor | Number-theoretic constructions of efficient pseudo-random functions[END_REF][START_REF] Naor | Number-theoretic constructions of efficient pseudo-random functions[END_REF] that the Naor-Reingold function is pseudo-random provided that certain standard cryptographic assumptions about the hardness of breaking the Decision Diffie-Hellman assumption holds. In cryptography, two interesting choices for G are a subgroup of the multiplicative group of a (prime) finite field and a subgroup of the points of an elliptic curve defined over a finite field.

Since proving that the Decision Diffie-Hellman assumption holds seems currently to be out of reach, several number-theoretic properties and complexity measures have been studied for the Naor-Reingold pseudo-random functions over finite fields as well as over elliptic curves: distribution (see [START_REF] Ling | On the multidimensional distribution of the Naor-Reingold pseudo-random function[END_REF][START_REF] Shparlinski | On the Naor-Reingold pseudo-random function from elliptic curves[END_REF] and references therein), linear complexity (see [START_REF] Cruz | On the linear complexity of the Naor-Reingold sequence with elliptic curves[END_REF][START_REF] Domingo Gmez | lvar Ibeasi: On the linear complexity of the Naor-Reingold pseudorandom function[END_REF][START_REF] Shparlinski | Linear complexity of the Naor-Reingold pseudo-random function[END_REF][START_REF] Shparlinski | On the linear complexity of the Naor-Reingold pseudo-random function from elliptic curves[END_REF]) and non-linear complexity (see [START_REF] Banks | Non-linear complexity of the Naor-Reingold pseudo-random function[END_REF]). These results are incomparable but they all support the assumption of the pseudo-randomness of the Naor-Reingold function.

In order to break the security of the Naor-Reingold function, it would be sufficient to have a polynomial over a finite field of low degree which reveals information on the function values. From the known lower bounds on the polynomial interpolation on the discrete logarithm in the groups we considered (e.g. [START_REF] Coppersmith | On polynomial approximation of the discrete logarithm and the Diffie-Hellman mapping[END_REF][START_REF] Kiltz | Polynomial interpolation of cryptographic functions related to Diffie-Hellman and discrete logarithm problem[END_REF][START_REF] Lange | Polynomial interpolation of the elliptic curve and XTR discrete logarithm[END_REF][START_REF] Lange | Interpolation of the discrete logarithm in Fq by Boolean functions and by polynomials in several variables modulo a divisor of q -1[END_REF][START_REF] Meletiou | Interpolation of the double discrete logarithm[END_REF])), it is easy to prove that a low-degree t-variate polynomial cannot reveal the secret key a when evaluated at f a (x (1) ), f a (x (2) ), . . . , f a (x (k) ) (for integers x (1) , . . . , x (k) ∈ {0, 1, . . . , 2 n -1}) for many different vectors a. However, the security of the Naor-Reingold function would be broken if such low-degree polynomial revealing a value f a (x (0) ) were proved to exist (for some integer x (0) ∈ {0, 1, . . . , 2 n -1} \ {x (1) , . . . , x (k) }).The reduction of the Naor-Reingold function pseudo-randomness to the Decision Diffie-Hellman problem uses a so-called hybrid argument and known lower bounds on the polynomial interpolation on the Diffie-Hellman mapping (e.g. [START_REF] Kiltz | On the interpolation of bivariate polynomials related to the Diffie-Hellman mapping[END_REF][START_REF] El Mahassni | Polynomial representations of the Diffie-Hellman mapping[END_REF][START_REF] Lange | Interpolation of the elliptic curve Diffie-Hellman mapping[END_REF][START_REF] Winterhof | A note on the interpolation of the Diffie-Hellman mapping[END_REF])) are not strong enough to rule out the existence of such polynomials for k > 2.

The present article deals with the polynomial representation of the Naor-Reingold function over finite fields and elliptic curves and proves lower bounds on the degree of polynomials which interpolate these functions. Our results are of the following form: for most secret keys a, if a multivariate polynomial reveals the value f a (x (0) ) when evaluated at values f a (x (0) + t 1 ), f a (x (0) + t 2 ), . . . , f a (x (0) + t k ) for fixed values t 1 , . . . , t k and for many integers x (0) ∈ {0, 1, . . . , 2 n -1}, then this polynomial is of high degree. We consider univariate, bivariate and general multivariate polynomial representation of the Naor-Reingold function. These lower bounds do not have any immediate implications for the pseudo-randomness of the Naor-Reingold function but as the results mentioned above they support this assumption. In particular, the inverse statements of the existence of low degree polynomial representation of the function would completely break the security of many cryptographic schemes.

Preliminaries

Throughout the paper, log z denotes the binary logarithm of z. Let p be an odd prime number. We denote by F p the finite field with p elements and the elements of F p are identified with the set of integers {0, • • • , p -1}. Given g ∈ F * p with prime order (with | p -1) we can consider the Naor-Reingold pseudo-random function defined over G = g :

f a (x) = g a x ∈ G ⊂ F *
p , for a secret key a = (a 1 , . . . , a n ) ∈ (F * ) n where x will denote indifferently an n-bit string (x 1 , . . . , x n ) ∈ {0, 1} n or an integer x ∈ {0, 1, . . . , 2 n -1}.

In the following, we will use the following lemma where the weight w(F ) (or sparsity) of a polynomial F (X) ∈ F p [X] is the number of its non-zero coefficients.

Lemma 1 ( [START_REF] Lange | Polynomial interpolation of the elliptic curve and XTR discrete logarithm[END_REF]) Let γ ∈ F p be an element of order and F (X) ∈ F p [X] be a non-zero polynomial of degree at most -1 with at least b zeros of the form γ x with 0 ≤ x ≤ -1. The weight of F (X) satisfies

w(F ) ≥ -b
We will also consider the setting of an elliptic curve E defined over F p for p > 3, that is a rational curve given by the following Weierstrass equation

y 2 = x 3 + Ax + B, A, B ∈ F p , 4A 3 + 27B 2 = 0.
The set E(F p ) of the points of the curve defined over F p (including the special point O at infinity) has a group structure (denoted additively) with an appropriate composition rule where O is the neutral element. Given P a point of the curve E with prime order (with | #E(F p )), we denote [r]P the scalar multiplication, i.e. in fact the adding of the point P to itself r times (for n ≥ 0):

[r]P = P + • • • + P r times

(and [r]P = -([-r]P ) for r ≤ 0). We also define the function fa (x) = [a x ]P ∈ E ⊂ F 2 p , for a secret key a = (a 1 , . . . , a n ) ∈ (F * ) n where again x will denote indifferently an n-bit string (x 1 , . . . , x n ) ∈ {0, 1} n or an integer x ∈ {0, 1, . . . , 2 n -1}. Because of the algebraic structure of E, this function is not pseudo-random and the Naor-Reingold pseudo-random function over E(F p ) is thus defined as, f a (x) = X( fa (x)), where X(P ) denotes the abscissa of P ∈ E.

We recall some basic facts on division polynomials of elliptic curves (see [START_REF] Washington | Elliptic curves. Number theory and cryptography[END_REF] and [START_REF] Blake | Elliptic curves in cryptography[END_REF]). They provide a way to calculate multiples of points on elliptic curves. The division polynomials ψ m (X, Y ) ∈ F p [X, Y ]/(Y 2 -X 3 -AX -B), m ≥ 0, are recursively defined by:

ψ 0 = 0 ψ 1 = 1 ψ 2 = 2Y ψ 3 = 3X 4 + 6AX 2 + 12BX -A 2 ψ 4 = 4Y (X 6 + 5AX 4 + 20BX 3 -5A 2 X 2 -4ABX -8B 2 -A 3 ) ψ 2m+1 = ψ m + 2ψ 3 m -ψ m-1 ψ 3 m+1 , m ≥ 2 ψ 2m = ψ m (ψ m+2 ψ 2 m-1 -ψ m-2 ψ 2 m+1 )/ψ 2 , m ≥ 3,
where

ψ m is an abbreviation for ψ m (X, Y ). If m is odd, then ψ m (X, Y ) ∈ F p [X] is univariate and if m is even then ψ m (X, Y ) ∈ ψ 2 (X, Y )F p [X] = 2Y F p [X]. Therefore, as ψ 2 2 (X, Y ) = 4(X 3 + AX + B), we have ψ 2 m (X, Y ) ∈ F p [X] and ψ m-1 (X, Y )ψ m+1 (X, Y ) ∈ F p [X].
In particular, we may write ψ 2m+1 (X) and ψ 2 m (X).

As mentioned above, the division polynomials can be used to calculate multiples of a point on the elliptic curve E. Let P = (x, y) ∈ E with P = O, then the abscissa of [m]P if [m]P = O is given by

θ m (x) ψ 2 m (x)
, where θ m (X) = Xψ 2 m -ψ m-1 ψ m+1 .

The zeros of the denominator ψ 2 m (X) are exactly the first coordinates of the non-trivial m-torsion points, i.e, the points

Q = (x, y) ∈ F p 2 \ {O} on E with [m]Q = O.
Note, that these points occur in pairs Q = (x, y) and -Q = (x, -y), which coincide only if 2Q = O, i.e, if x is a zero of ψ 2 2 (X). We recall that the group of m-torsion points E[m], for an elliptic curve E defined over a field of characteristic p, is isomorphic to (Z/mZ) 2 if p m and to a proper subgroup of (Z/mZ)

2 if p | m. If m is a power of p then E[m] is either isomorphic to (Z/mZ) or to {O}. Accordingly, the degree of ψ 2 m (X) is m 2 -1 if p | m
and strictly less than m 2 -1 otherwise. In particular, for p = 2 and m a power of 2 we have deg(

ψ 2 m ) = m -1 if E is not supersingular and deg(ψ 2 m ) = 0 otherwise. By induction one can show that θ m (X) ∈ F p [X] is monic of degree m 2 .
In the following, we will make use of the two following technical lemmas (where F p denotes as usual the algebraic closure of F p ).

Lemma 2 Let E : y 2 = x 3 + Ax + B be an elliptic curve over F p with A = 0 and B = 0. Let F (X) ∈ F p [X] be a non-constant polynomial with F (X) = X and deg(F ) < p. Then there exists α ∈ F p such that ψ 2 2 (F (α)) = 0 and ψ 2 2 (α) = 0. Proof There are exactly three distinct zeros α 1 , α 2 , α 3 ∈ F p of ψ 2 2 (X)
. For all index i ∈ {1, 2, 3}, there exists at least one β i ∈ F p such that F (β i ) = α i , because F is not a constant polynomial. Since for all i, j ∈ {1, 2, 3}, i = j, we have α i = α j , then the system F (X) = α i and F (X) = α j has no solution. It follows that the polynomial ψ 2 2 (F (X)) has at least three different zeros. Let d < p denote the degree of F and let us suppose that there does not exist α ∈ F p such that ψ 2 2 (F (α)) = 0 and ψ 2 2 (α) = 0. Then we have that ψ 2 2 (F (X)) has exactly three zeros which are the zeros of ψ 2 2 (X). If d = 1, putting F (X) = aX + b, we obtain that the polynomials X 3 + AX + B and a 3 X 3 + 3a 2 bX 2 + (3ab 2 + aA)X + b 3 + Ab + B have exactly the same three zeros. We then have 3a 2 b = 0 and a = 0. Thus b = 0, and if we suppose A = 0 and B = 0, we have a = 1 which is impossible since F (X) = X. If d ≥ 2, for all i ∈ {1, 2, 3}, the equation F (X) = α i has exactly one solution γ i of multiplicity d which is one of {α 1 , α 2 , α 3 }. Then γ 1 and γ 2 are the zeros of the (d -1)-derivative of F (X) which is of degree 1 and this is impossible because

γ 1 = γ 2 .
Hence in all cases, we obtain a contradiction. So there exists α ∈ F p such that:

ψ 2 2 (F (α)) = 0 and ψ 2 2 (α) = 0. Lemma 3 Let E : y 2 = x 3 + Ax + B be an elliptic curve over F p . Let k = 2 i for i > 0 an integer. Let F (X) ∈ F p [X] be a non-constant polynomial with deg(F ) ≥ 2. Then there exists α ∈ F p such that ψ 2 k (F (α)) = 0 and ψ 2 k (α) = 0.
Proof The univariate polynomial ψ 2 k (X) has at least k 2 /2 distinct zeros because p k. For all α such that ψ 2 k (α) = 0, there exists at least one β ∈ F p such that F (β) = α and two such roots β (corresponding to two different α) are different. Since deg(F ) ≥ 2, it follows that the equation F (X) = α, for α zero of ψ 2 k (X) has at least two different solutions. Hence, the polynomial ψ 2 k (F (X)) has at least k 2 distinct zeros and the result follows.

We also need the following lemmas from [START_REF]On the linear complexity of the Naor-Reingold pseudo-random number generator[END_REF] and [START_REF] Domingo Gmez | lvar Ibeasi: On the linear complexity of the Naor-Reingold pseudorandom function[END_REF] about the distribution of products a x in F * . Lemma 4 ( [START_REF]On the linear complexity of the Naor-Reingold pseudo-random number generator[END_REF]) Let m ≥ 1 be an integer. For any ∆ > 0 and for all but at most 2 -m ∆ -1 ( -1) m+2 vectors a = (a 1 , . . . , a m ) ∈ (F * ) m , the products a x for x ∈ {0, 1} m take at least -1 -∆ values in F * . Lemma 5 ([6]) Let n ≥ j > 0 be two integers. For all but at most

(3 j -1)( -1) n-1 /2 vectors a = (a 1 , . . . , a n ) ∈ (F * ) n the products a x for x ∈ {0, 1} n take at least 2 j values in F * .
3 Polynomial Interpolation of the Naor-Reingold Pseudo-Random Function over Finite Fields In this section, p is an odd prime number, n is an integer and g ∈ F * p is an element of prime order (with | p -1). We prove results on the univariate and multivariate polynomial interpolation of the Naor-Reingold pseudorandom function over finite fields. We consider polynomials that interpolates values of the Naor-Reingold pseudo-random function for a fixed secret key a ∈ (F * ) n . The values considered are evaluation of the function at integers x ∈ {0, • • • , 2 n -1} and translates of these values by some fixed constants

t 1 , t 2 , • • • , t k ∈ N.
This setting is interesting for applications in cryptography. Note that if one value x + t i is larger than 2 n for some i ∈ {1, . . . , k} then, the Naor-Reingold function is not defined at x + t i . In the following, we consider simple sets where all translates belong to the Naor-Reingold function domain but our method can be adapted to other settings.

First, we consider multivariate polynomial interpolation over large sets of values.

Theorem 1 Let t ≥ 1 be an integer. Let t 1 , t 2 , • • • , t k be fixed distinct integers such that t 1 , t 2 , • • • , t k < 2 t and let A ⊆ {0, • • • , 2 n -1}. For some a ∈ (F * ) n , let F a (X 1 , . . . , X k ) ∈ F p [X 1 , • • • , X k ] such that F a (f a (x), f a (x + t 1 ), • • • , f a (x + t k-1 )) = f a (x + t k ) (1)
for all x ∈ A. For all but at most 2k( -1) n-1 vectors a ∈ (F * ) n , we have

     deg(F a ) + k k ≥ 2∆ + 1 -1 w(F a ) ≥ 2∆ + 1 -1 where ∆ = -1 -S for the set S = {a 2 t x ∈ F * : 2 t x ∈ A},
It is worth noting that the conclusion of Theorem 1 cannot hold for all vectors a ∈ (F * ) n . For instance, if we consider a secret key a = (a 1 , . . . , a n ) ∈ (F * ) n such that a n-1 = a n and the simple case k = 1 and t 1 = 1, we have f a (x + t 1 ) = f a (x) for all integer x in the set A = {x ∈ {0, • • • , 2 n -1}, x ≡ 1 mod 4}, (since x = (x 1 , x 2 , . . . , x n-2 , 0, 1) and x+t 1 = (x 1 , x 2 , . . . , x n-2 , 1, 0)). The polynomial F a (X 1 ) = X 1 of degree 1 and weight 1 therefore satisfies (1) for all x ∈ A where the set A is very large since A = 2 n/4 . However, Theorem 1 ensures that the lower bounds on the degree and the weight of F hold with probability 1 -2k/( -1) when the secret key a is picked uniformly at random (and hence with overwhelming probability for k polynomial in the security parameter).

In Theorem 1 statement, it is also necessary to consider the cardinality of a subset of {a x ∈ F * , x ∈ A} and not the cardinality of A itself since it is possible that for some secret key a, the latter is "large" while the former is "small". For instance, for a secret key a = (a, . . . , a) ∈ (F * ) n (where all components are equal to some constant value a ∈ F * ), we have f a (x) = g a x = g a hw(x) where hw(x) denotes x's Hamming weight (i.e., its number of non-zero coordinates). In this case, even if the set A is very large, {a x ∈ F * , x ∈ A} is of cardinality at most n and one can construct a small degree multivariate polynomial that interpolates the values of the Naor-Reingold pseudo-random function.

Proof Since t 1 , t 2 , • • • , t k < 2 t , we have a 2 t x+ti = a 2 t x a ti for all x ∈ A such that 2 t x ≤ 2 n -1 and i ∈ {1, • • • , k}. The relation (1) thus becomes F a (g u , g ua t 1 , • • • , g ua t k-1 ) = g ua t k ,
for all u ∈ S. Let R = {u ∈ S|u(a t k ) -1 ∈ S}. We put ∆ = -1 -S and, by the union bound, we have R ≥ -1 -2∆ and

F a (g u(a t k ) -1 , • • • , g ua t k-1 (a t k ) -1 ) = g u , for all u ∈ R. Let H a (X) = F a (X (a t k ) -1 , • • • , X a t k-1 (a t k ) -1 ) -X ∈ F p [X]
and K a (X) the polynomial obtained from H a (X) by considering the degree of monomials of H a (X) modulo .

Claim The polynomial K a (X) is not a zero polynomial for all but at most 2k( -

1) n-1 vectors a ∈ (F * ) n . Proof (Claim.) Indeed if K a (X) is a zero polynomial, then -either F a is a monomial of the form X α1 1 • • • X α k k , with (α 1 , • • • , α k ) = (0, • • • , 0)
or F a would be a sum of at least two monomials

X α1 1 • • • X α k k and X β1 1 • • • X β k k and there would exist (α 1 , • • • , α k ) = (β 1 , • • • , β k ) such that α 1 (a t k ) -1 + • • • + α k a t k-1 (a t k ) -1 = β 1 (a t k ) -1 + • • • + β k a t k-1 (a t k ) -1 in F . If F a is of the form X α1 1 • • • X α k k , then from (1), it will follows that α 1 a x + • • • + α k a x+t k-1 = a x+t k in F , for all x ∈ A. (2)
Let x such that (2) is satisfied. Then we can easily prove for all n ≥ 1 by induction in k that the number of a ∈ (F * ) n solutions of (2) does not exceed k( -1) n-1 .

1. For k = 0, the equation a x+t k = 0 has no solution and the statement is clearly true. 2. Otherwise, let j = max({i ∈ {1 . . . , k}|α i = 0}). Because x + t k = x + t j , there exists i such that i-th component of x + t k is different from the i-th component of x + t j . Then the above equation can be written in the form T 1 = T 2 a i where T 1 and T 2 do not depend on a i . If T 2 = 0, then for any vector (a

1 , • • • , a i-1 , a i+1 , • • • , a n ) ∈ (F * ) n-1
, the value of a i is defined uniquely. If T 2 = 0, then by induction, the number of (a

1 , • • • , a i-1 , a i+1 , • • • , a n ) ∈ (F * ) n-1 does not exceed (k -1)( -1) n-1 .
Therefore, the number of solutions does not exceed (k -1)( -

1) n-1 + ( - 1) n-1 = k( -1) n-1
, and the result follows.

In the second case, if there exists (α

1 , • • • , α k ) = (β 1 , • • • , β k ) such that α 1 (a t k ) -1 + • • • + α k a t k-1 (a t k ) -1 = β 1 (a t k ) -1 + • • • + β k a t k-1 (a t k ) -1
in F then we have

(α 1 -β 1 )a 0 + • • • + (α k -β k )a t k-1 = 0 in F .
Then by proceeding as previously by induction on k, for all n, one can see that the number of solutions a ∈ (F * ) n does not exceed (k -1)( -1) n-1 .

For a ∈ (F * ) n such that K a (X) is not a zero polynomial, we have by Lemma 1, that w(K a (X)) ≥ -( -1-2∆) , since deg(K a (X)) ≤ -1 and K a (X) has at least -1 -2∆ roots of the g u . Therefore, by Lemma 1, we have

     deg(F a ) + k k ≥ 2∆ + 1 w(F a ) ≥ 2∆ + 1 -1
for all but at most 2k( -1) n-1 vectors a ∈ (F * ) n and the result follows.

Remark 1 Theorem 1 is non-trivial only when S ≥ (3 -2)/4. Since S ≤ 2 n-t , Theorem 1 only applies to settings where the message length n is greater than the sum of the bit-length of the underlying group order and t.

The cardinality of the set S depends on A and on the secret key a = (a 1 , . . . , a n ) ∈ (F * ) n . In the following lemma for certain condition on A and on n, we show that S is close to for almost all secret key a. This allows us to obtain Corollary 1 and for the forthcoming theorems in this paper to obtain non trivial lower bounds.

Lemma 6 Let γ > δ > 0 such that n ≥ (1 + γ) log( -1). Let t = min (1, (γ -δ)/2) log( -1) -1 and let A ⊆ {0, • • • , 2 n -1} such that {2 t x : x ∈ {0, . . . , 2 n-t -1}} ⊆ A. Putting Γ = ( -1)2 -t , we obtain: S ≥ -1 -Γ,
for all but at most ( -1) n-δ vectors a ∈ (F * ) n .

Proof We denote again S = {a 2 t x ∈ F * : 2 t x ∈ A}.

Putting Γ = ( -1)2 -t and applying Lemma 4, we have S ≥ -1 -Γ for all but at most 2 t-n Γ -1 ( -1) n+2 ≤ ( -1) n-δ vectors a ∈ (F * ) n .

We apply Lemma 6 to Theorem 1 to obtain the following corollary:

Corollary 1 Let γ > δ > 0 such that n ≥ (1 + γ) log( -1). Let t = min (1, (γ -δ)/2) log( -1) -1 and t 1 , t 2 , • • • , t k be fixed distinct integers such that t 1 , t 2 , • • • , t k < 2 t and let A ⊆ {0, • • • , 2 n -1}. For some a ∈ (F * ) n , let F a (X 1 , . . . , X k ) ∈ F p [X 1 , • • • , X k ] such that Relation (1) holds for all x ∈ A. If {2 t x : x = 0, . . . , 2 n-t -1} ⊆ A, we have      deg(F a ) + k k ≥ 1 8 ( -1) min(1,(γ-δ)/2) w(F a ) ≥ 1 8 ( -1) min(1,(γ-δ)/2) -1
for all but at most 2k( -

1) n-1 + ( -1) n-δ vectors a ∈ (F * ) n .
The proof is straightforward since, with the previous notation, we have in this case ∆ < Γ . Likewise Lemma 6 can be applied to the next theorems of this paper to obtain non-trivial lower bounds for almost all vectors a ∈ (F * ) n .

For the cases where the cardinality of the set S is smaller than (3 -2)/4, Theorem 1 does not give a non-trivial lower bound on F 's degree. In the next theorem, we obtain such a lower bound for much smaller sets S with #S ∈ [ √ + 1, (3 -2)/4]. Theorem 2 only applies for univariate interpolation (i.e. k = 1).

Theorem 2 Let t ≥ 1 be a fixed integer and let

A ⊆ {0, • • • , 2 n -1}. For some a ∈ (F * ) n , let F a (X) ∈ F p [X] such that F a (f a (x)) = f a (x + t) (3)
for all x ∈ A. For all but at most 2( -1) n-1 vectors a ∈ (F * ) n , we have

deg(F a ) ≥ S( S -1) -1 .
where S = {a 2 t x ∈ F * : 2 t x ∈ A}.

Proof As in the previous proof, we have F a (g u ) = g ua t for all u ∈ S.

Consider D = {1 ≤ b ≤ -1 : b ≡ y -x mod , x, y ∈ S}.
There exists b ∈ D such that there are at least

S( S -1) D ≥ S( S -1) - 1
representations b ≡ y -x mod , with x, y ∈ S. We choose this b and put

R = {x ∈ S : b + x ≡ y mod , y ∈ S}.
Then we have

R ≥ S( S -1) -1 .
For u ∈ R, (since g x = g x+ , for all x), we have

F a (g u+b ) = g (u+b)a t = g ua t × g ba t = F a (g u ) × g ba t Let H a (X) = F a (g b X) -g ba t F a (X)
. Then H a (X) has at least R zeros. As in the previous proof, H a (X) = 0 for all but at most 2( -1) n-1 vectors a ∈ (F * for all but at most 2( -1) n-1 vectors a ∈ (F * ) n .

In the following lemma, we show that that there exists numerous sets A and corresponding S such that #S ∈ [ √ + 1, (3 -2)/4]. For such sets Theorem 1 does not give a non-trivial lower bound on F 's degree.

Lemma 7 Let 1 log(3) -1 2 > δ > 0 (with 1 log(3) -1 2 0.1309 . . .). Let t ≥ 1 and n be integers such that n = t + (1/2 + δ) log( -1) + s for some integer s such that 0 ≤ s ≤ log(3 -2) -2 -(1/2 + δ) log( -1) . Let A ⊆ {0, • • • , 2 n -1} such that {2 t x : x ∈ {0, . . . , 2 n-t -1}} ⊆ A. Putting γ = 1 -log(3)(1/2 + δ) we obtain: (3 -2)/4 ≥ S ≥ ( -1) (1/2+δ)
for all but at most 3/2( -1) n-γ vectors a ∈ (F * ) n .

Proof We denote again S = {a 2 t x ∈ F * : 2 t x ∈ A}. Putting j = (1/2 + δ) log( -1) and applying Lemma 5, we obtain readily S ≥ ( -1) (1/2+δ) for all but at most (3 j -1)( -1) n-1 ≤ 3/2( -1) n-γ vectors a ∈ (F * ) n . Since S ≤ 2 j+s ≤ (3 -2)/4, we obtain the desired result.

For such sets A and S and parameters n, t, s given in Lemma 7, we have (using the notation of Theorem 2), that the degree of of polynomial F a satisfying (3) verifies deg(F a ) ≥ c • 2δ for all but at most 2( -1) n-1 + 3/2( -1) n-γ vectors a ∈ (F * ) n (where c is an absolute constant close to 1).

Remark 2 This proof technique cannot be used to obtain a lower bound on the weight of a univariate polynomial F or on the degree of a multivariate polynomial F for k ≥ 2 and it remains an open problem to improve Theorem 1 for smaller sets S with #S ≤ (3 -2)/4 in these settings.

Univariate Interpolation of the Naor-Reingold Pseudo-Random Function over Elliptic Curves

In this section, p is an odd prime number, n is an integer, E is an elliptic curve over F p and P is a point of the curve E with prime order (with | #E(F p )). We prove results on the univariate polynomial interpolation of the Naor-Reingold pseudo-random function from elliptic curves defined by f a (x) = X([a x ]P ) for a secret key a ∈ (F * ) n and an integer x ∈ {0, 1, . . . , 2 n -1} (where X(Q) denotes the abscissa of a point Q ∈ E(F p )). First, we consider interpolation over large sets of values.

Theorem 3 Let E : y 2 = x 3 + γx + δ be an elliptic curve over F p with γδ = 0. Let t ≥ 1 be a fixed integer and let

A ⊆ {0, • • • , 2 n -1}. For some a ∈ (F * ) n , let F a (X) ∈ F p [X] such that F a (f a (x)) = f a (x + t) (4)
for all x ∈ A. For all but at most 2( -1) n-1 vectors a ∈ (F * ) n , we have

deg(F a ) ≥ 2 S -( -1) 14 .
where S = {a 2 t x ∈ F * : 2 t x ∈ A}.

Proof We have F a (x u ) = x ua t for all u ∈ S, where x t = X([t]P ), for all t ∈ F . We consider the R = {u ∈ S : 2u ∈ S} with R ≥ -1 -2∆. For all u ∈ R, 2u ∈ S and [2u]P = O and F a (x 2u ) = x 2ua t is well-defined in F p and x ua t is thus not a root of ψ 2 . Therefore, we have:

F a (x 2u ) = x 2ua t = θ 2 (x ua t )/ψ 2 2 (x ua t ) = θ 2 (F a (x u ))/ψ 2 2 (F a (x u )), for all u ∈ R.
We thus get

F a θ 2 (x u ) ψ 2 2 (x u ) = θ 2 (F a (x u )) ψ 2 2 (F a (x u
)) for all u ∈ R. Finally, we consider the polynomial:

H a (X) = ψ 2d 2 (X)ψ 2 2 (F a (X)) F a θ 2 (X) ψ 2 2 (X) - θ 2 (F a (X)) ψ 2 2 (F a (X))
,

where d = deg(F a ).
The polynomial H a (X) has at least R/2 zeros. If a t = ±1, we will have F a (X) = X and by Lemma 2, it will imply that there exists α ∈ F p such that ψ 2 2 (F a (α)) = 0 and ψ 2 2 (α) = 0. Hence, we have H a (α) = -θ 2 (F a (α))ψ 2d 2 (α) = 0, since θ 2 (X) and ψ 2 2 (X) have no common zeros. Therefore, H a (X) is a non-zero polynomial and deg(H a ) ≤ 7d. Then we get that 7d ≥ R/2 and then d ≥ -1-2∆

14

. Since a t = ±1 for all but at most 2( -1) n-1 vectors a ∈ (F * ) n , the result follows.

Theorem 3 is only non-trivial if S ≥ ( + 13)/2. Again, the cardinality of the set S depends on A and on the secret key a = (a 1 , . . . , a n ) ∈ (F * ) n , but using again Lemma 6, we can easily obtain (as in Corollary 1) non-trivial lower bounds for specific sets A and parameter n.

In the following theorem, we obtain a lower bound for smaller sets S.

Theorem 4 Let t ≥ 1 be a fixed integer, A ⊆ {0, • • • , 2 n -1}, 0 < < 1 and S = {a 2 t x ∈ F * : 2 t x ∈ A} with S ≥ 2( -1) log( ) . For some a ∈ (F * ) n , let F a (X) ∈ F p [X] such that F a (f a (x)) = f a (x + t) (5)
for all x ∈ A. For all but at most 2( -1) n-1 vectors a ∈ (F * ) n , we have

deg(F a ) ≥ S 4 log( ) × 2 .
Proof We have F a (x u ) = x ua t for all u ∈ S where, as above, we denote x t = X([t]P ), for all t ∈ F . Let K be an integer and let us consider the sets

S i = {1 ≤ b ≤ -1 : 2 i m ≡ b mod , m ∈ S},
for 0 ≤ i ≤ K, and R i,j = S i ∩ S j for 0 ≤ i < j ≤ K. We have

(K + 1) S - 0≤i<j≤K R i,j ≤ K i=0 S i ≤ -1.
Therefore, there is a pair 0

≤ i < j ≤ K such that R 0,j-i = R i,j ≥ 2((K + 1) S -( -1)) K(K + 1) .
For u ∈ R 0,j-i , there exists a unique m ∈ S such that 2 j-i m ≡ u mod , with u ∈ S and the corresponding m's are distinct for two different u's. Since

x k = x k+l for all k, then we have F a (x 2 j-i m ) = x 2 j-i ma t for at least R 0,j-i different m ∈ S. For each such m, we have

F a θ 2 j-i (xm) ψ 2 2 j-i (xm) = x 2 j-i ma t = θ 2 j-i (x ma t )/ψ 2 2 j-i (x ma t ) = θ 2 j-i (F a (x m ))/ψ 2 2 j-i (F a (x m
)), since m ∈ S. Finally, we consider the polynomial

H a (X) = ψ 2d 2 j-i (X)ψ 2 2 j-i (F a (X)) F a θ 2 j-i (X) ψ 2 2 j-i (X) - θ 2 j-i (F a (X)) ψ 2 2 j-i (F a (X))
,

where d = deg(F a ).
The polynomial H a (X) has at least R 0,j-i zeros. Since d ≥ 2 and 2 j-i and p are coprime, then by Lemma 3, there exists α ∈ F p such that ψ 2 2 j-i (F a (α)) = 0 and ψ 2 2 j-i (α) = 0. Hence, we have H a (α) = -θ 2 j-i (F a (α))ψ 2d 2 j-i (α) = 0, since θ 2 j-i (X) and ψ 2 2 j-i (X) have no common zeros. Therefore H a (X) is a non-zero polynomial and deg(H a ) ≤ d(2(2 j-i ) 2 -1) and we get

d ≥ R 0,j-i 2(2 2(j-i)+1 -1) ≥ (K + 1) S -( -1) K(K + 1)(2 2(j-i)+1 -1)
.

Since j -i ≤ K, then we have

d ≥ (K + 1) S -( -1) K(K + 1)(2 2K+1 -1) ≥ 1 2 2K+1 -1 S K - -1 K(K + 1) ≥ S K(2 2K+1 -1) 1 - -1 S(K + 1)
.

Letting K = log( ) , for any 0 < < 1, we have

d ≥ S 2 log( ) × 2 1 - -1 S log( ) ≥ S 4 log( ) × 2 .
Theorem 4 also applies to numerous sets A and S for which Theorem 3 does not apply. For instance, we can consider parameters n, t, s given in Lemma 7 such that 2 n-t-s ≥ 2( -1) log( ) .

5 Bivariate Interpolation of the Naor-Reingold Pseudo-Random Function over Elliptic Curves It seems rather difficult to obtain an analogue of Theorem 1 in the case of elliptic curves. In this section, we use the methods from [START_REF] Lange | Interpolation of the elliptic curve Diffie-Hellman mapping[END_REF] and we prove results on bivariate interpolation of the Naor-Reingold pseudo-random function from elliptic curves (but in a slightly different setting). We use the notation from the previous section and, as before, we consider first interpolation over large sets of values.

Theorem 5 Let A 1 , A 2 ⊆ {0, • • • , 2 n -1} and t ≥ 1 be an integer. For some a ∈ (F * ) n , let F a (X, Y ) ∈ F p [X, Y ] such that F a (f a (x), f a (x )) = f a (x + x ) (6)
for all (x, x ) ∈ A 1 × A 2 . We have

deg(F a ) ≥ min ( -1)/∆ -2; ( S 2 -1) 1/3 -2 .
where ∆ = -1 -S 1 for the set S 1 = {a x : x ∈ A 1 , x < 2 t } and where

S 2 = {a 2 t x ∈ F * : 2 t x ∈ A 2 }.
Proof We may suppose S 2 ≥ 10 since otherwise the result is trivial. We denote

d = min ( -1)/∆ -2; ( S 2 -1) 1/3 -2 .
We have F a (x u , x u ) = x uu , for all u ∈ S 1 and u ∈ S 2 .

Let R be the set of u ∈ S 1 such that

ia mod ∈ S 1 , ∀i ∈ {1, • • • , d + 1}.
The cardinality of R is at least -1 -∆(d + 1). Let u ∈ R, then we have

F a (x (i+1)u , x vj ) = x (i+1)uvj , for all 0 ≤ i, j ≤ d, where v 0 , • • • , v d are any distinct elements of S 2 . Let us suppose that deg X (F a ), deg Y (F a ) ≤ d namely F a (X, Y ) = d i,j=0 c i,j X i Y j ,
then we have for 0 ≤ k, ≤ d,

x (k+1)uv = d i,j=0 c i,j x i (k+1)u x j v .
Then F a 's coefficients are determined by the following matrix equation:

C =    c 0,0 . . . c 0,d . . . . . . c d,0 . . . c d,d    =    x 0 u . . . x d u . . . . . . x 0 (d+1)u . . . x d (d+1)u    -1    x uv0 . . . x uv d . . . . . . x (d+1)uv0 . . . x (d+1)uv d       x 0 v0 . . . x 0 v d . . . . . . x d v0 . . . x d v d   
The matrix C is non-singular if and only if the middle matrix on the right hand is non-singular. A subset {v 0 ,

d k x kub = 0, b ∈ S 2 .
As at most two points with first coordinate equal to 0 exist on the elliptic curve and S 2 ≥ 3, we get ω ≥ 2. Since x kub = θ k (x ub )/ψ 2 k (x ub ), the polynomial

H(X) = ω k=1 d k θ k (X) ω j=1,j =k ψ 2 j (X)
has at least S 2 /2 zeros and degree at most

1 + ω k=1 (k 2 -1) = (2ω 3 + 3ω 2 -5ω + 6)/6 ≤ ω 3 /2 ≤ (d + 1) 3 /2.
Since p ω, then points of order ω on E exist over F p . Let α ∈ F p be the first coordinate of a point of order ω. Then we have ψ 2 ω (α) = 0 and

H(α) = d ω θ ω (α) ω-1 j=1 ψ 2 j (α) = 0.
The polynomial H(X) is a non-zero polynomial and we have (d + 1) 3 /2 ≥ S 2 /2 in contradiction with the definition of d. This shows that C is not singular and in particular each row of C has at least one non-zero entry and we have deg

(F a ) ≥ deg X (F a ) ≥ d.
Theorem 5 is non-trivial only for S 1 ≥ ( -1)/2 and we can obtain (as in Corollary 1) non-trivial lower bounds on the degree of the interpolating polynomial for specific sets A 1 and A 2 and parameter t.

Lemma 8 Let m ≥ 1 be an integer, δ > 0 and t be an integer such that t ≥ (1 + δ) log( -1) + m + 1 and n

-t ≥ (1 + δ) log( -1) + 2. Let A 1 , A 2 ⊆ {0, • • • , 2 n -1} be two sets such that {0, . . . , 2 t -1} ⊆ A 1 and {2 t x : x ∈ {0, . . . , 2 n-t -1}} ⊆ A 2 . Let S 1 = {a x : x ∈ A 1 , x < 2 t } and S 2 = {a 2 t x ∈ F * : 2 t x ∈ A 2 }, we have S 1 ≥ -1 -( -1)2 -m and S 2 ≥ ( -1)/2 + 1,
for all but at most 2( -1) n-δ vectors a ∈ (F * ) n .

Proof Let ∆ = ( -1)2 -m . Applying Lemma 4, we have

S 1 ≥ -1 -∆ for all but at most 2 -t ∆ -1 ( -1) t+2 ( -1) n-t ≤ ( -1) n-δ vectors a ∈ (F * ) n . Likewise, applying Lemma 4 with ∆ = ( -1)/2 -1 , we have S 2 ≥ ( -1)/2 + 1 for all but at most 2 t-n ∆ -1 ( -1) n-t+2 ( -1) t ≤ ( -1) n-δ vectors a ∈ (F * ) n .
We apply Lemma 8 to Theorem 5 to obtain the following corollary:

Corollary 2 Let m ≥ 1 be an integer and δ > 0 such that t ≥ (1 + δ) log( -

1) + m + 1 and n -t ≥ (1 + δ) log( -1) + 2. Let A 1 ⊆ {0, • • • , 2 n -1} such that {0, . . . , 2 t -1} ⊆ A 1 and A 2 ⊆ {0, • • • , 2 n -1} such that {2 t x : x ∈ {0, . . . , 2 n-t -1}} ⊆ A 2 . For some a ∈ (F * ) n , let F a (X, Y ) ∈ F p [X, Y ] such that F a (f a (x), f a (x )) = f a (x + x ) (7)
for all (x, x ) ∈ A 1 × A 2 . We have

deg(F a ) ≥ min 2 m -2; (( -1)/2) 1/3 -2 ,
for all but at most 2( -1) n-δ vectors a ∈ (F * ) n .

The proof is straightforward since, with the of notation of Theorem 5, we have in this case ∆ ≤ ( -1)2 -m and S 2 -1 ≥ ( -1)/2.

To conclude the paper, we obtain a simple result for smaller sets S 1 .

Theorem 6 Let A 1 , A 2 ⊆ {0, • • • , 2 n -1} and t ≥ 1 be an integer. For some a ∈ (F * ) n , let F a (X, Y ) ∈ F p [X, Y ] such that F a (f a (x), f a (x )) = f a (x + x ) (8) for all (x, x ) ∈ A 1 × A 2 . We have deg(F a ) ≥ S 1 8
.

where

S 1 = {a x : x ∈ A 1 , x < 2 t } and S 2 = {a 2 t x ∈ F * : 2 t x ∈ A 2 } if there exists v ∈ S 2 such that 2v ∈ S 2 .
Proof We have F a (x u , x v ) = x uv and F a (x u , x 2v ) = x 2uv for all u ∈ S 1 .

Hence

F a x u , θ 2 (x v ) ψ 2 2 (x v ) = θ 2 (x uv ) ψ 2 2 (x uv ) = θ 2 (F a (x u , x v )) ψ 2 2 (F a (x u , x v ))
for all u ∈ S 1 .

Finally, we consider the polynomial

U (X) = ψ 2 2 (F a (X, x v )) F a (X, θ 2 (x v ) ψ 2 2 (x v ) ) - θ 2 (F a (X, x v )) ψ 2 2 (F a (X, x v ))
.

We The condition on S 2 in the statement of Theorem 6 is achieved trivially when S 2 > -1 2 . It is worth mentioning that Theorem 6 also applies to many other sets. In the following lemma, we show that that there exists numerous sets A 1 , A 2 and corresponding S 1 , S 2 such that S 1 ∈ [ √ + 1, ( -1)/2] and S 2 > ( -1)/2. For such sets Theorem 6 gives a non-trivial lower bound on the degree of the interpolating polynomial while Theorem 5 does not give a non-trivial lower bound on it. We apply Lemmas 4 and 5 like in the proof of Lemmas 6, 7 and 8 to obtain the following lemma: Lemma 9 Let 1 log(3) -1 2 > δ 1 > 0 (with 1 log(3) -1 2 0.1309 . . .) and δ 2 > 0. Let t and n be integers such that t = (1/2 + δ 1 ) log( -1) + s for some integer s such that 0 ≤ s ≤ log( -1) -1 -(1/2 + δ 1 ) log( -1) and n -t ≥ (1 + δ 2 ) log( -1) + 2. Let A 1 ⊆ {0, • • • , 2 n -1} such that {0, . . . , 2 t -1}} ⊆ A 1 and A 2 ⊆ {0, • • • , 2 n -1} such that {2 t x : x ∈ {0, . . . , 2 n-t -1}} ⊆ A 2 . Putting γ = 1 -log(3)(1/2 + δ 1 ) we obtain:

( -1)/2 ≥ S 1 ≥ ( -1) (1/2+δ1) and S 2 ≥ ( -1)/2 + 1, for all but at most 3/2( -1) n-γ + ( -1) n-δ2 vectors a ∈ (F * ) n .

We then apply Lemma 9 to Theorem 6 to obtain the following corollary: Corollary 3 Let 1 log(3) -1 2 > δ 1 > 0, δ 2 > 0 and γ = 1 -log(3)(1/2 + δ 1 ). Let t and n be integers such that t = (1/2 + δ 1 ) log( -1) + s for some integer s such that 0 ≤ s ≤ log( -1) -1 -(1/2 + δ 1 ) log( -1) and n -t ≥ (1 + δ 2 ) log( -1) + 2. Let A 1 ⊆ {0, • • • , 2 n -1} such that {0, . . . , 2 t -1}} ⊆ A 1 and A 2 ⊆ {0, • • • , 2 n -1} such that {2 t x : x ∈ {0, . . . , 2 n-t -1}} ⊆ A 2 . For some a ∈ (F * ) n , let F a (X, Y ) ∈ F p [X, Y ] such that F a (f a (x), f a (x )) = f a (x + x ) [START_REF] Kiltz | On the interpolation of bivariate polynomials related to the Diffie-Hellman mapping[END_REF] for all (x, x ) ∈ A 1 × A 2 . We have deg(F a ) ≥ ( -1) (1/2+δ1) /8, for all but at most 3/2( -1) n-γ + ( -1) n-δ2 vectors a ∈ (F * ) n .

The proof is straightforward since, with the notation of Theorem 6, we have in this case S 1 ≥ ( -1) (1/2+δ1) and there exists v ∈ S 2 such that 2v ∈ S 2 since S 2 > ( -1)/2

Conclusion

In this paper, we proved lower bounds on the degree of multivariate polynomial representations of the Naor-Reingold function over a finite field and over the group of points on an elliptic curve over a finite field. Many open problems remain: the first being naturally to generalize our bounds to smaller interpolating sets. Known lower bounds on the polynomial interpolation of the Diffie-Hellman mapping (e.g. [START_REF] Kiltz | On the interpolation of bivariate polynomials related to the Diffie-Hellman mapping[END_REF][START_REF] El Mahassni | Polynomial representations of the Diffie-Hellman mapping[END_REF][START_REF] Lange | Interpolation of the elliptic curve Diffie-Hellman mapping[END_REF][START_REF] Winterhof | A note on the interpolation of the Diffie-Hellman mapping[END_REF])) can rule out the existence of low degree polynomials that interpolate the Naor-Reingold function in two fixed points for many keys. It is desirable to extend these results to give lower bounds on the degree of general multivariate polynomials that interpolate the Naor-Reingold function in several fixed points for many keys. Such results would be related to the polynomial interpolation of the so-called group Diffie-Hellman problems [START_REF] Bresson | The group Diffie-Hellman problems[END_REF].

  ) n and deg(H a ) ≤ deg(F a ), we have deg(F a ) ≥ S( S -1) -1 .

  have deg(U ) ≤ 4 deg(F a ). Let γ be a root of ψ 2 2 (X) and β such that F a (β, x v ) = γ. Then U (β) = -θ 2 (F a (β, x v )) = 0,and U is non-zero polynomial. Since U has at least S 1 /2 zeros, it follows that 4 deg(F a ) ≥ S 1 /2 i.e. deg(F a ) ≥ S1 8 .

  • • • , v d } of S 2 with this property exists if and only if the vectors T k = (x kub ) b∈S2 for k ∈ {1, • • • , d + 1} are linearly independent. If these vectors were linearly dependent, then there would exist an integer ω with 1 ≤ ω ≤ d + 1 and coefficients d 1 , • • • , d ω ∈ F p , d ω = 0, such that

	ω
	k=1

Acknowledgements. The authors would like to thank the anonymous reviewers for their helpful and constructive comments that led to substantial improvements in this paper.

MSC Codes 11T71

The authors are supported in part by the French ANR JCJC ROMAnTIC project (ANR-12-JS02-0004) and by the Simons foundation Pole PRMAIS.


Benoît Bonnet
email: benoit.bonnet@inria.fr

Patrick Bas
email: patrick.bas@centralelille.fr

What if Adversarial Samples were Digital Images?

Keywords: security and privacy architectures, Intrusion/anomaly detection and malware mitigation, Malware and its mitigation, Image classification, neural networks, adversarial samples

Although adversarial sampling is a trendy topic in computer vision, very few works consider the integral constraint: The result of the attack is a digital image whose pixel values are integers. This is not an issue at first sight since applying a rounding after forging an adversarial sample trivially does the job. Yet, this paper shows theoretically and experimentally that this operation has a big impact. The adversarial perturbations are fragile signals whose quantization destroys its ability to delude an image classifier.

This paper presents a new quantization mechanism which preserves the adversariality of the perturbation. Its application outcomes to a new look at the lessons learnt in adversarial sampling.

CCS CONCEPTS

• Security and privacy → Domain-specific

INTRODUCTION

Adversarial samples [START_REF] Szegedy | Intriguing properties of neural networks[END_REF] are small, usually imperceptible perturbations of images (or other data) that can arbitrarily modify the prediction of a classifier. The Computer Vision community has extended adversarial samples to other tasks than image classification like optical flow computation [START_REF] Ranjan | Attacking Optical Flow[END_REF], object tracking [START_REF] Rey | Physical Adversarial Textures That Fool Visual Object Tracking[END_REF], captioning [START_REF] Xu | Exact Adversarial Attack to Image Captioning via Structured Output Learning With Latent Variables[END_REF], face recognition [START_REF] Dong | Efficient Decision-Based Black-Box Adversarial Attacks on Face Recognition[END_REF], and image retrieval [START_REF] Li | Universal Perturbation Attack Against Image Retrieval[END_REF][START_REF] Tolias | Targeted Mismatch Adversarial Attack: Query With a Flower to Retrieve the Tower[END_REF]. These perturbations are not random but carefully crafted by an attacker. In a white-box setting, the attacker has full knowledge of the classifier internals and uses the gradient of the model to find the appropriate perturbation for a given image. They are becoming increasingly important because they reveal the sensitivity of neural networks to their inputs. That sensitivity is a vulnerability when the system is deployed in security application.

Adversarial samples are typically evaluated by the probability of success, i.e. the probability that the attack deludes the classifier, and by the distortion between the original and the attacked images. State-of-the-art white-box attacks lead to a probability of success near one combined with a small distortion. This shows that the perturbation is almost imperceptible and reflects the difficulty with -, -, -2020. 978-x-xxxx-xxxx-x/YY/MM. . . $15.00 https://doi.org/10.1145/nnnnnnn.nnnnnnn which adversarial samples can be detected. The speed of an attack is another criterion recently introduced. The fast single-step FGSM attack [START_REF] Goodfellow | Explaining and Harnessing Adversarial Examples[END_REF] produces high-distortion examples where adversarial patterns can easily be recognized. At the other extreme, the Carlini & Wagner (CW) attack [START_REF] Carlini | Towards evaluating the robustness of neural networks[END_REF], considered state of the art, is notoriously expensive. Decoupling direction and norm (DDN) [START_REF] Rony | Decoupling Direction and Norm for Efficient Gradient-Based L2 Adversarial Attacks and Defenses[END_REF] has recently shown impressive progress in the trade-off between distortion and speed. Speed is important for adversarial retraining [START_REF] Madry | Towards Deep Learning Models Resistant to Adversarial Attacks[END_REF]. This procedure robustifies a network by training it with many adversarial samples.

A perusal of the 25 papers dealing with this topic and recently published in the 2019 editions of the well known conferences CVPR and ECCV shows the following fact: 88% of these research works propose attacks forging adversarial samples which are not images! Their outputs are adversarial samples in the form of matrices with continuous variables (implemented with float point single precision in 4 Bytes). This paper challenges this working assumption and investigates what happens if attacks are constrained to forge digital images with discrete pixel values encoded with a depth of 8 bits. Several works have addressed this issue using quantized steps within their iterative attacks [START_REF] Rony | Decoupling Direction and Norm for Efficient Gradient-Based L2 Adversarial Attacks and Defenses[END_REF][START_REF] Tondi | Pixel-domain adversarial examples against CNN-based manipulation detectors[END_REF]. Our goal is however not to propose a new attack, but to see how to quantify adversarial samples at best. This is not trivial : Rounding each pixel value is an obvious but inefficient solution that almost always turns an adversarial sample into a non adversarial image.

The paper contains four contributions:

• A theoretical explanation why quantization by rounding fails.

• A near optimal quantization procedure that keeps the adversarial nature and the small distortion of the perturbation

• A review which analyses whether well-known facts in the adversarial sample literature still hold with near optimal quantization.

• The integration of our quantization scheme into an iterative attack.

The outline of the paper is the following. Section 2 first challenges the working assumption in literature that adversarial samples need not to be quantized. Section 3 shows that simply rounding the adversarial samples does not yield adversarial images. Section 4 presents our near optimal quantization procedure. Section 5 reports experimental results over ImageNet when quantization is applied after some classical attacks against 'natural' and 'robust' networks. Section 6 exposes how to integrate our quantization inside an iterative attack.

MOTIVATION

Adversarial attacks in the literature usually output real numbers stored in matrices. We call them adversarial samples in contrast to digital images that are tables of integers. There are many preprocessing recipes adapting the input image before feeding it to the neural network. This section argues that these steps cannot explain the assumption of working with unquantized adversarial samples too easily admitted in this literature.

Over the 25 publications dealing with adversarial attacks in CVPR 2019 and ECCV 2019, almost all of them define a pixel as a real value unquantized. They consider the problem of find a real matrix close to the original image and whose prediction is wrong. The words 'quantization' or 'discrete' are never mentioned. The images included in these papers as illustration of adversarial samples have been quantized for publication purpose. Therefore, it is not sure that these published images indeed are adversarial.

Only three of these 25 papers are clearly working with quantized images. Two of them indeed investigate attacks in the physical world to delude optical flow reconstruction in autonomous cars [START_REF] Ranjan | Attacking Optical Flow[END_REF] or object tracking in video surveillance [START_REF] Rey | Physical Adversarial Textures That Fool Visual Object Tracking[END_REF]. They obviously deal with quantized images because they print patches on stickers or they display patterns on a screen present in the scene. The only reference coping with digital adversarial samples which are truly images proposes the so-called DDN attack: In [START_REF] Rony | Decoupling Direction and Norm for Efficient Gradient-Based L2 Adversarial Attacks and Defenses[END_REF]Sect. 3], one reads "Besides this step, we can also consider quantizing the image in each iteration, to ensure the attack is a valid image". It is very surprising that the authors compares DDN with state-of-the-art but unconstrained attacks issuing adversarial samples not images.

In the same way, the report [START_REF] Kurakin | Adversarial Attacks and Defences Competition[END_REF] on the "Adversarial Attacks and Defences Competition" organised at NIPS 2017 clearly states that "the adversary has direct access to the actual data fed into the model.

In other words, the adversary can choose specific float32 values as input for the model". There is clearly here a misconception in the threat analysis. In the white box scenario, the attacker knows all the internals of the targeted network. She/He can reproduce it in her/his garage and has "direct access" into this copy. Yet, the goal is to produce an adversarial image that will delude the same classifier outside the garage, where access inside is forbidden. For example, if the attacker knows the source code of the classifier used to tag images on a social network platform, he still needs to publish the attacked image in a format readable by the platform, for example in tiff or jpeg format for images. Note that a common procedure in image classification is to apply a transformation to the pixel values of the query image before feeding the neural network. Contrary to the vast majority of adversarial examples represented in the continuous domain, these processed inputs remain discrete. This is an affine scaling ranging from V := {0, 1, . . . , 255} to [0, 1] (or [-1, 1] depending on the neural network). Even if the output is encoded as float, this bijection results in 255 discretized possible values in [0, 1]. Yet, most of papers explicitly state that the attack aims at finding the adversarial sample anywhere in [0, 1] 𝑛 with the smallest distortion.

Another practice is to perform an object (ImageNet dataset) or a character (MNIST dataset) detection first and then to query the network with the cropped image framing the object. If the bounding box is too large, a stretching is performed (see the CIFAR dataset). The result of this downscaling need not to be quantized and again can be encoded as float. Nevertheless, this process is done inside the image classifier, and the attacker has no direct access to this auxiliary data outside the garage. Consequently, the aim of the attacker is to modify the image before it is transmitted to the classifier, and therefore before any of these pre-processing tasks.

The report [START_REF] Kurakin | Adversarial Attacks and Defences Competition[END_REF] states that "In a real world setting, this might occur when an attacker uploads a PNG file to a web service, and intentionally designs the file to be read incorrectly." This motivates the choice of the floating point representation for unquantized pixel values. On one hand, this community has well accepted that these values should only lie in [0, 1]. So, if the attacker is so powerful that she/he can inject any floating point value, then why should we restrict the range to [0, 1]? On the other hand, we argue here that this is a security threat not targeting the classifier but the image loader software that decodes the received file into a matrix of pixel values. There are known conception rules in computer security to avoid hacks like buffer overflows.

There are almost as many defense papers as attack papers in this literature. Authors validate that their defense does not degrade the classifier accuracy on the original images of the test dataset, which are of course quantized. In the same time, they measure the defense ability on the attacked versions of these images, which are not quantized. It is funny to notice that detecting whether the input is quantized would be the simplest defense able to block most of the attacks.

The next section shows that quantization is not an inoffensive processing step: it can strongly impact the success rate of an attack.

PROBLEM FORMULATION

This section introduces basic notations of image classification with neural network, briefly presents some well known white-box attacks, and exposes the impact of quantization when rounding weak perturbations.

Background

3.1.1 Notations. Let X := {0, 1, . . . , 255} 𝑛 denote the set of images. This means that, for sake of clarity, an image is a flattened vector x ∈ X whose length 𝑛 is the total number of pixels (grayscale like MNIST dataset) times 3 color channels (ImageNet or CIFAR dataset). The classifier usually pre-processes the input image by a function a : X → S where S := [0, 1] 𝑛 (or S := [-1, 1] 𝑛 for some implementations of ResNet). We call s := a(x) ∈ S a sample. A classifier is a function f : S → P 𝐶 where P 𝐶 is the simplex of dimension 𝐶: p = f(s) is a vector of 𝐶 positive components summing up to 1, 𝑝 (𝑘) being the predicted probability that sample s belongs to class 𝑘 ∈ [𝐶] (with [𝑛] := {1, 2, . . . , 𝑛}). The classifier top-1 prediction 𝜋 : S → [𝐶] maps the sample s to the class label having the maximum probability:

𝜋 (s) := arg max 𝑘 ∈ [𝐶 ]
𝑝 (𝑘).

(

) 1
The prediction is correct if 𝜋 (s) = t(s), the true label of sample s.

Problem formulation.

In the untargeted scenario, the aim of the attacker is to delude the classifier in whatever manner, i.e. its predicted class is not the true label.

In the literature, an adversarial sample s 𝑎 is a quasi-copy of a given original sample s 𝑜 where 𝜋 (s 𝑎 ) ≠ t(s 𝑜 ) although ∥s 𝑎 -s 𝑜 ∥ 𝐿 is small (the 𝐿-norm of S, with 𝐿 ∈ {0, 1, 2, +∞}).

In this paper, an adversarial image x 𝑞 is a quasi-copy of an original image x 𝑜 where 𝜋 (a(x 𝑞 )) ≠ t(a(x 𝑜 )). The constraint is that x 𝑞 is a digital image, i.e. it belongs to X. The distortion in this paper is measured by the Euclidean norm in the image pixel domain X (and not in S as in many papers).

The framework considers an original image x 𝑜 , the output of an attack x 𝑎 which is not a priori a digital image, and the quantization of x 𝑎 into x 𝑞 ∈ X. We denote by u the unquantized perturbation, q the quantization noise and by e the final adversarial perturbation:

u := x 𝑎 -x 𝑜 , (2)
q := x 𝑞 -x 𝑎 , (3)
e := x 𝑞 -x 𝑜 = u + q.

(4)

3.1.3 The classification loss. In a white-box scenario, the attacker gauges how close he/she is from his/her goal with a measure called the classification loss. This is typically the negative crossentropy L 𝐴 (s 𝑎 ) = log 𝑝 𝑎 (t(s 𝑜 )) (with p 𝑎 := f(s 𝑎 )) or whatever increasing function of 𝑝 𝑎 (t(s 𝑜 )). The role of the attack is to decrease this loss so that 𝑝 𝑎 (t(s 𝑜 )) is so small that the sample is no longer classified as the ground truth. In other words, s 𝑎 is repelled from the original class region.

Another option is to attract s 𝑎 to another class region, for instance the most likely other prediction:

L 𝐴 (s 𝑎 ) = log 𝑝 𝑎 (t(s 𝑜 )) -log max 𝑘≠t(s 𝑜 ) 𝑝 𝑎 (𝑘). (5)
This has the advantage of indicating by L 𝐴 (s 𝑎 ) < 0 that the attack succeeds. Indeed, if L 𝐴 (s 𝑎 ) = 𝑚 < 0 then 𝑝 𝑎 (t(s 𝑜 )) is 𝑒 𝑚 smaller than the estimated probability of the predicted class.

Well known attacks

This section summarizes well-known attacks in the literature, which we consider in the experimental body in Sect. 5. The linear preprocessing a(•) mapping each pixel to S is integrated in the neural network, and hence in the loss L 𝐴 . This allows to describe the attacks in the domain [0, 255] 𝑛 .

Fast Gradient Sign Method. FGSM is the oldest and simplest attack [START_REF] Goodfellow | Explaining and Harnessing Adversarial Examples[END_REF]. It has one unique parameter 𝜖 > 0. Its expression is simply:

x 𝑎 = cl x 𝑜 -𝜖sign ∇ x L 𝐴 (x)| x 𝑜 , (6)
where cl clips the pixel values to

[0, 255]. Note that x 𝑎 ∈ X if and only if 𝜖 ∈ N. The final distortion is ∥x 𝑎 -x 𝑜 ∥ 2 = 𝑛𝜖 2 (neglecting the clipping).
Iterative FGSM.. This is the iterated version of FGSM introduced in [START_REF] Kurakin | Adversarial examples in the physical world[END_REF]. We consider the version that repeats the update:

x (𝑖+1) 𝑎 = cl x (𝑖) 𝑎 -𝛼sign ∇ x L 𝐴 (x)| x (𝑖 ) 𝑎 , (7)
until a maximum number 𝑁 of iterations is met or until x

(𝑖)
𝑎 is adversarial. It has two parameters 𝛼 and 𝑁 . The distortion is at most 𝑛(𝛼𝑁 ) 2 (achieved if the gradient is a constant vector).

Projected Gradient Descent. We refer to PGD 2 as the Euclidean version of the projected gradient descent [START_REF] Madry | Towards Deep Learning Models Resistant to Adversarial Attacks[END_REF]. Its update is given by

x (𝑖+1) 𝑎 = cl proj 𝜖 x (𝑖) 𝑎 -𝛼 ∇ x L 𝐴 (x)| x (𝑖 ) 𝑎 ∥ ∇ x L 𝐴 (x)| x (𝑖 ) 𝑎 ∥ (8)
where proj 𝜖 is the projection on the ball of center x 𝑜 and radius 𝜖.

It means that the update is scaled back onto the sphere of radius 𝜖 if it goes outside that ball. This attack has three parameters: 𝛼, 𝜖 and the maximum number 𝑁 of iterations. Usually, we set 𝜖 as a fraction of 𝛼𝑁 .

Carlini and Wagner. We refer to CW as the attack invented by Carlini and Wagner, authors of [START_REF] Carlini | Towards evaluating the robustness of neural networks[END_REF]. It uses the ADAM solver to find the minimum of the Lagrangian formulation:

𝐽 (x, 𝜇) = ∥x -x 𝑜 ∥ 2 + 𝜇 |L 𝐴 (x) -𝑚| + , (9)
where 𝑚 ≤ 0 is a margin and |𝑎| + = 𝑎 if 𝑎 > 0, and 0 otherwise. Then, an outer loop tests different values of 𝜇 in a line search. The adversarial sample with the lowest distortion is the final output.

The parameters are usually the number of iterations for the inner loop (ADAM) and for the outer loop.

Decoupling Direction and Norm. This attack denoted DDN is defined in [START_REF] Rony | Decoupling Direction and Norm for Efficient Gradient-Based L2 Adversarial Attacks and Defenses[END_REF] by its update:

x (𝑖+1) 𝑡 = x (𝑖) 𝑎 -𝛼 ∇ x L 𝐴 (x)| x (𝑖 ) 𝑎 ∥ ∇ x L 𝐴 (x)| x (𝑖 ) 𝑎 ∥ , (10)
x

(𝑖+1) 𝑎 = cl x 𝑜 + 𝜌 (𝑖+1) x (𝑖+1) 𝑡 -x 𝑜 ∥x (𝑖+1) 𝑡 -x 𝑜 ∥ . ( 11
)
where

𝜌 (𝑖+1) = (1 + 𝛾)𝜌 (𝑖) if x (𝑖)
𝑎 is not adversarial and

𝜌 (𝑖) = (1 - 𝛾)𝜌 (𝑖) otherwise (with 𝜌 (1) = 𝛼). Since 𝛾 > 0, DDN increases (resp. decreases) the budget distortion 𝜌 (𝑖+1) if x (𝑖)
𝑎 is still not adversarial (resp. is already adversarial). In its quantized version, the function cl(•) not only clips to [0, 255] but also rounds each component to the nearest integer. This is done at the end of each iteration. The adversarial sample with the lowest distortion is the final output. This attack has 3 parameters: 𝛼, 𝛾, and 𝑁 .

Why rounding fails

We suppose that an attack produces x 𝑎 = x 𝑜 + u which a priori does not belong to the set of discrete values X. A solution is then to quantize back onto X by applying the rounding to the nearest integer R(•):

x 𝑞 = R(x 𝑜 + u) = x 𝑜 + R(u), (12)
where we make the abuse of notation: R(x) means rounding each component of the vector x. We also assume that x 𝑜 + R(u) ∈ X without clipping. The last equality comes from the fact that x 𝑜 ∈ X.

The following study aims at predicting the norm of the update after quantization, assuming that rounding is independent from the computation of the perturbation. Denote by e := R(u). Pixel 𝑗 is quantized to

𝑥 𝑞 ( 𝑗) = 𝑥 𝑜 ( 𝑗) + 𝑒 ( 𝑗), (13)
when 𝑢 ( 𝑗) ∈ (𝑒 𝑗 -1/2, 𝑒 𝑗 + 1/2] for some 𝑒 ( 𝑗) ∈ Z. Border effects where 𝑥 ( 𝑗) + 𝑒 ( 𝑗) ∉ X are neglected here. We now take a statistical point of view where the update is modelled by a random vector U uniformly distributed over the hypersphere of radius 𝜌. That parameter 𝜌 is the norm of the perturbation before quantization. This yields random quantized values, denoted by 𝐸 ( 𝑗) ∈ Z for pixel 𝑗. The distortion after the quantization is given by:

𝐷 2 = ∥E∥ 2 = 𝑛 𝑗=1 𝐸 ( 𝑗) 2 . (14)
A common approach in source coding theory is the additive noise model for quantization error in the high resolution regime [START_REF] Gersho | Vector Quantization and Signal Compression[END_REF]. It states that 𝐸 ( 𝑗) = 𝑈 ( 𝑗) + 𝑄 ( 𝑗) where 𝑄 ( 𝑗) ∈ (-1/2, 1/2] is the quantization error. In the high resolution regime where 𝜌 ≫ 1, 𝑄 becomes uniformly distributed (s.t. E(𝑄 ( 𝑗)) = 0 and E(𝑄 ( 𝑗) 2 ) = 1/12) and independent of 𝑈 ( 𝑗) (s.t. E(𝑈 ( 𝑗)𝑄 ( 𝑗)) = E(𝑈 ( 𝑗))E(𝑄 ( 𝑗)) = 0). Under these assumptions, Eq. ( 14) simplifies in expectation to:

E(𝐷 2 ) = E 𝑛 𝑗=1 𝑈 ( 𝑗) 2 + 𝑄 ( 𝑗) 2 + 2𝑈 ( 𝑗)𝑄 ( 𝑗) = 𝜌 2 + 𝑛 12 . (15)
This shows that rounding increases the distortion on expectation. Yet, this simple analysis is wrong outside the high resolution regime, and we need to be more careful. The expectation of a sum is always the sum of the expectations, whatever the dependence between the summands:

E(𝐷 2 ) = 𝑛 𝑗=1 E(𝐸 ( 𝑗) 2 ) = 𝑛E(𝐸 ( 𝑗) 2 ) with E(𝐸 ( 𝑗) 2 ) = 255 ℓ=0 ℓ 2 P(|𝐸 𝑗 | = ℓ). (16)
We need the distribution of 𝐸 ( 𝑗) to compute the expected distortion after rounding. This random variable 𝐸 ( 𝑗) takes a value depending on the scalar product 𝑈 ( 𝑗) := U ⊤ c 𝑗 , where c 𝑗 is the 𝑗-th canonical vector. This scalar product lies in [-𝜌, 𝜌], so that

P(𝐸 ( 𝑗) ≥ ℓ) = 0 if 𝜌 < ℓ -1/2. Otherwise, |𝐸 ( 𝑗)| ≥ ℓ when |𝑈 ( 𝑗)| ≥ ℓ -1/2,
which happens when U lies inside the dual hypercone of axis c 𝑗 and semi-angle 𝜃 (ℓ) = arccos(𝑐 (ℓ)) with 𝑐 (ℓ) := (2ℓ -1)/2𝜌 as shown in Fig. 1.

Since U is uniformly distributed over an hypersphere, the probability of the event {|𝑈 ( 𝑗)| ≥ ℓ -1/2} is equal to the ratio of the solid angles of this dual hypercone and the full space R 𝑛 . This quantity can be expressed via the incomplete regularized beta function 𝐼 . In

0 1 2 3 -1 -2 -3 𝜌 𝜃 (1) 𝜃 (2)
Figure 1: The dual hypercones related to ℓ = 1 and 2. Since 𝜌 < 3 -1/2, the other hypercones do not exist. the end, ∀ℓ ∈ {0, . . . , 𝐿 -1},

P(|𝐸 ( 𝑗)| ≥ ℓ) =          1, if ℓ = 0 1 -𝐼 𝑐 (ℓ) 2 (1/2, (𝑛 -1)/2), if 0 ≤ 𝑐 (ℓ) ≤ 1 0, otherwise
Note that it approximately equals 2Φ( √ 𝑛𝑐 (ℓ)/2) for large 𝑛, where Φ is the cumulative distribution function.

Computing E(𝐷 2 ) is now possible with the simple trick for discrete r.v.:

P(|𝐸 ( 𝑗)| = ℓ) = P(|𝐸 ( 𝑗)| ≥ ℓ) -P(|𝐸 ( 𝑗)| ≥ ℓ + 1)
. This expected distortion after rounding depends on 𝑛 and 𝜌, the norm of the perturbation before rounding. Figure 2 shows that rounding reduces the distortion outside the high resolution regime. Indeed, the distortion after quantization is smaller than before quantization when 𝜌 2 /𝑛 < 0.08 for 𝑛 = 3 * 299 2 (i.e. the dimension of images from ImageNet). When the adversarial perturbation has a smaller norm 𝜌, rounding is likely to kill it and R(x 𝑎 ) = x 𝑜 , or at least to drastically decrease its amplitude. Since known attacks achieve rather low distortion, we are not in the high resolution regime and the rounding likely pulls down the attack. This is a statistical study working on expectation. This phenomenon happens systematically on some attacks when the perturbation on each pixel value has a small amplitude. For instance with FGSM (6), we have 𝑢 ( 𝑗) = ±𝜖, ∀𝑗 ∈ [𝑛] which gives 𝜌 = 𝜖 √ 𝑛. Then, each pixel perturbation is rounded to 𝑒 ( 𝑗) = ±R(𝜖) so that

𝐷 2 = 𝑛R 2 𝜌 √ 𝑛 . ( 17
)
As shown in Fig. 2, rounding systematically cancels FGSM for 𝜖 < 1/2, whereas it amplifies it a lot for 1/2 < 𝜖 < 1.

OUR APPROACH

Our approach considers quantization as a post-processing independent of the attack. The quantization does not interfere with the attack, which is a state-of-art implementation taken off-the-shelf as a black-box. From an original image x 𝑜 ∈ X, this attack has produced a sample x 𝑎 which does not a priori belong to X. This sample may or may not be adversarial depending whether the attack succeeded or not. We aim at finding the best quantization process producing x 𝑞 = Q (x 𝑎 ) ∈ X adversarial with high probability.

We make the following assumptions. Since we are in a white-box setting, the quantization mechanism has access to:

• the original image x 𝑜 , • the sample x 𝑎 = x 𝑜 + u produced by the attack,

• the prediction function of the classifier,

• the gradient of this function. Our approach constrains the quantization to consider only two options per pixel1 : ∀𝑗 ∈ [𝑛], 𝑥 𝑞 ( 𝑗) ∈ {⌈𝑥 𝑎 ( 𝑗)⌉, ⌊𝑥 𝑎 ( 𝑗)⌋}. This can be rewritten as 𝑥 𝑞 ( 𝑗) ∈ x 𝑜 ( 𝑗) + {⌈𝑢 ( 𝑗)⌉, ⌊𝑢 ( 𝑗)⌋}. Note that if 𝑢 ( 𝑗) ∈ Z, ⌈𝑢 ( 𝑗)⌉ = ⌊𝑢 ( 𝑗)⌋ = 𝑢 ( 𝑗). Assuming this special case rarely occurs, this leaves almost 2 𝑛 possibilities in total.

As in Sect. 3, the quantization is modelled by the addition of a noise q as follows

x 𝑞 = x 𝑎 + q = x 𝑜 + u + q. ( 18
)
For each pixel, we see that 𝑞( 𝑗) takes the value ⌈𝑢 ( 𝑗)⌉ -𝑢 ( 𝑗) ≥ 0 or ⌊𝑢 ( 𝑗)⌋ -𝑢 ( 𝑗) ≤ 0.

Distortion based quantization

We define the function D of q as the final distortion after quantization w.r.t. x 𝑜 :

D(q) := ∥x 𝑞 -x 𝑜 ∥ 2 = ∥u + q∥ 2 . ( 19
)
We define Q 0 the quantization that minimises the distortion. For the 𝑗-th pixel, it makes 𝑞( 𝑗)

+ 𝑢 ( 𝑗) = ⌈𝑢 ( 𝑗)⌉ if ⌈𝑢 ( 𝑗)⌉ 2 < ⌊𝑢 ( 𝑗)⌋ 2 , i.e. if 𝑢 ( 𝑗) < 0. Q 0 (𝑥 𝑎 ( 𝑗)) := 𝑥 𝑜 ( 𝑗) + ⌈𝑢 ( 𝑗)⌉ if 𝑢 ( 𝑗) ≤ 0, ⌊𝑢 ( 𝑗)⌋ if 𝑢 ( 𝑗) > 0. ( 20
)
Note that the distortion is lower after this quantization: ∥x 𝑎x 𝑜 ∥2 ≥ ∥Q 0 (x 𝑎 ) -x 𝑜 ∥ 2 . However, we don't have any guarantee that

Q 0 (x 𝑎 ) is adversarial. For instance, if |𝑢 ( 𝑗)| < 1, ∀𝑗 ∈ [𝑛],
then either ⌈𝑢 ( 𝑗)⌉ or ⌊𝑢 ( 𝑗)⌋ equals 0, and Q 0 (x 𝑎 ) = x 𝑜 , which is not adversarial.

Gradient based quantization

Another option is to quantize in order to strengthen the adversariality of the image. We define a new classifier loss as follows:

L 𝑄 (q) := 𝑝 𝑞 (𝑡 (x 𝑜 )) -𝑝 𝑞 (𝜅 𝑎 ), (21)
p 𝑞 := f(a(x 𝑎 + q)), (22)
𝜅 𝑎 := arg max

𝑘≠𝑡 (x 𝑜 ) 𝑝 𝑎 (𝑘). (23)
In words, the loss is the difference between the predicted probabilities that x 𝑞 belongs to the true class of x 𝑜 minus the one of a given class 𝜅 𝑎 ∈ [𝐶]. That class 𝜅 𝑎 is indeed the class region where the attack tried to drive sample x 𝑎 to, with or without success. Our quantization works with this loss function whatever the loss L 𝐴 used by the attack before. We define quantization Q ∞ which aims at getting 2 L 𝑄 (q) < 0, indicating that x 𝑞 is adversarial. Since q is a small quantization noise, we approximate this loss to the first order:

L 𝑄 (q) ≈ L 𝑄 (0) + q ⊤ g, (24)
where L 𝑄 (0) is the classifier loss computed at q = 0 (i.e. when x 𝑞 = x 𝑎 , it is lower than 0 if the previous attack succeeded), and g := ∇L 𝑄 (q) 0 is its gradient computed at q = 0. Quantization Q ∞ minimizes the classifier loss through its approximation which is a correlation over the pixels. Therefore, it makes the signs of 𝑞( 𝑗) and 𝑔( 𝑗) opposite:

Q ∞ (𝑥 𝑎 ( 𝑗)) := 𝑥 𝑜 ( 𝑗) +          ⌈𝑢 ( 𝑗)⌉ if 𝑔( 𝑗) < 0, Q 0 (𝑥 𝑎 ( 𝑗)) if 𝑔( 𝑗) = 0, ⌊𝑢 ( 𝑗)⌋ if 𝑔( 𝑗) > 0. ( 25
)
Since the quantization is not impacting the approximation loss when 𝑔( 𝑗) = 0, we choose the option that minimizes the distortion.

Our approach: Lagrangian quantization

In our approach, the quantization Q 𝜆 minimizes a linear combination of the distortion and the classifier loss: For 𝜆 ≥ 0:

Q 𝜆 (x 𝑎 ) := x 𝑜 + u + arg min q D(q) + 𝜆L 𝑄 (q), (26)
under the constraint that 𝑞( 𝑗)

∈ {⌈𝑢 ( 𝑗)⌉, ⌊𝑢 ( 𝑗)⌋} -𝑢 ( 𝑗), ∀𝑗 ∈ [𝑛].
Thanks to the first order approximation (24) of the classifier loss, the functional to be minimized in (26) becomes a sum over all pixels. The optimization problem can be solved by considering the quantization of each pixel independently, ∀𝑗 ∈ [𝑛]:

𝑞( 𝑗) = arg min 𝑞 ∈ { ⌈𝑢 ( 𝑗) ⌉, ⌊𝑢 ( 𝑗) ⌋ }-𝑢 ( 𝑗) (𝑢 ( 𝑗) + 𝑞) 2 + 𝜆𝑔( 𝑗)𝑞. (27)
Consequently the complexity of the quantization breaks down from 𝑂 (2 𝑛 ) to 𝑂 (𝑛) by solving 𝑛 trivial optimization problems: When 𝑢 ( 𝑗) ∉ Z then ⌊𝑢 ( 𝑗)⌋ = ⌈𝑢 ( 𝑗)⌉ -1, and the solution is found as:

Q 𝜆 (𝑥 𝑎 ( 𝑗)) = 𝑥 𝑜 ( 𝑗) + ⌈𝑢 ( 𝑗)⌉ if 1 -2⌈𝑢 ( 𝑗)⌉ ≥ 𝜆𝑔( 𝑗) ⌊𝑢 ( 𝑗)⌋ otherwise. ( 28
)
Note that we find back the previous rule (20) when 𝜆 = 0 because

(1 -2⌈𝑢 ( 𝑗)⌉) > 0 if and only if 𝑢 ( 𝑗) ≤ 0. In the same way, Q 𝜆 converges to mechanism Q ∞ (25) because only the sign of 𝑔( 𝑗) matters when 𝜆 → +∞. Figure 3 illustrates the three quantization schemes in the domain (𝑔( 𝑗), ⌈𝑢 ( 𝑗)⌉). Note that there are pixels which are always quantized in the same way whatever the value of 𝜆 ≥ 0. This is the case when one quantization value minimizes both the distortion and the classifier loss:

• for all indices where 𝑔( 𝑗) < 0 and ⌈𝑢 ( 𝑗)⌉ < 1/2, 𝑞( 𝑗) is always quantized to ⌈𝑢 ( 𝑗)⌉ -𝑢 ( 𝑗),

• for all indices where 𝑔( 𝑗) > 0 and ⌈𝑢 ( 𝑗)⌉ > 1/2, 𝑞( 𝑗) is always quantized to ⌊𝑢 ( 𝑗)⌋ -𝑢 ( 𝑗).

We denote by J ⊂ [𝑛] the (complementary) subset of indices whose quantization depends on 𝜆. It is defined as:

J := { 𝑗 ∈ [𝑛] : 𝑔( 𝑗) ≠ 0, sign(𝑔( 𝑗)) ≠ sign(⌈𝑢 ( 𝑗)⌉ -1/2)} . ( 29
)
We assume that this subset is not empty. Sect. 5.2 empirically shows that J gathers around three fourths of the pixels.

Choice of Lagrange multiplier 𝜆

We now look for the best value of 𝜆 > 0. When 𝜆 increases, the quantization trades the distortion against the classifier loss. The distortion is the lowest for 𝜆 = 0 and increases, whereas the classifier loss (at least its approximation (24)) is a decreasing function of 𝜆. Therefore, if Q ∞ fails forging an adversarial image, so does Q 𝜆 whatever the value of 𝜆. Otherwise, it is worth looking for the best value 𝜆 ★ giving the smallest distortion while succeeding to delude the classifier. For all indices in J , we define the following ratio:

𝑟 ( 𝑗) := 1 -2⌈𝑢 ( 𝑗)⌉ 𝑔( 𝑗) > 0, (30)
so that the quantization rule (28) becomes

Q 𝜆 (𝑥 𝑎 ( 𝑗)) = 𝑥 𝑜 ( 𝑗) + ⌈𝑢 ( 𝑗)⌉ if 𝑟 ( 𝑗) > 𝜆 and Q 𝜆 (𝑥 𝑎 ( 𝑗)) = 𝑥 𝑜 ( 𝑗) + ⌊𝑢 ( 𝑗)⌋
otherwise. An index 𝑗 in J sees 𝑞( 𝑗) moving from one value to another when 𝜆 has increased up to the value 𝑟 ( 𝑗). Note that it is useless to explore 𝜆 ∈ (max 𝑗 𝑟 ( 𝑗), +∞) in the sense that values of 𝜆 in this interval gives birth to the same results as Q ∞ . Therefore, we carry on a search of the minimal value of 𝜆 ★ ∈ [0, max 𝑗 𝑟 ( 𝑗)] giving an adversarial image, i.e. L 𝑄 (q) ≤ 0. To do this, we rank the ratios (𝑟 ( 𝑗)) 𝑗 ∈ J by increasing order. Pixels ranked first offer a better trade-off: they yield a valuable loss decrease for a modest distortion increase. We perform a binary search on this sorted set, so that 𝜆 ★ = 𝑟 ( 𝑗 ★ ) the smallest ratio giving an adversarial image. This has a complexity in 𝑂 (log 𝑛) since |J | ≤ 𝑛.

Calls to the network

Solving problem (26) for a given 𝜆 a priori needs 𝑂 (2 𝑛 ) calls to the network. By replacing the loss by its linear approximation (24), 𝑔( 𝑗) the complexity is reduced to 𝑂 (1) calls to get the gradient g := ∇L 𝑄 (q) 0 . The gradient is computed by backpropagation and thanks to auto-differentiation, its complexity is roughly twice the complexity of one forward pass in the network. The above-mentioned binary search over 𝜆 can also resort to the approximated classifier loss. This avoids any call to the network. Nevertheless, this first order approximation is sometimes not accurate (see Fig. 4). An idea is to compensate this by a margin: The binary search ends with a value of 𝜆 for which the approximated loss ( 24) is below that margin. Setting the value of that margin s.t. the real loss is below zero with high probability is however difficult.

⌈𝑢 ( 𝑗)⌉ 𝜆 = 0 𝜆 > 0 𝜆 = +∞ 1 2
Another option is that the binary search uses the true classification loss (21) by calling the network to check whether L 𝑄 (q) ≤ 0. The complexity of the search now dominates the cost of the quantization: It scales as 𝑂 (log 𝑛) calls to the forward pass of the network (since |J | ≤ 𝑛). In our simulation over ImageNet, the search ends within at most 18 calls. To summarize, the first order approximation ( 24) is used to quantize pixels (28) and to rank the pixels according to ratio (30), but the search of 𝜆 uses the true classification loss (21).

EXPERIMENTAL WORK

This section presents experimental investigations about the impact of the quantization, and then a benchmark of several attacks. We first present the experimental protocol.

Experimental Protocol

Dataset and Networks.

Our experiments are based on the dataset of images used for the NeurIPS competition [START_REF] Kurakin | Adversarial Attacks and Defences Competition[END_REF]. This is indeed a subsection of 1,000 images from ImageNet. We test several versions of the ResNet neural network [START_REF] He | Deep Residual Learning for Image Recognition[END_REF]: the basic ResNet-18, the deeper ResNet-50, and ResNet-50R, its version robustified by adversarial retraining with PGD 2 [START_REF] Madry | Towards Deep Learning Models Resistant to Adversarial Attacks[END_REF].

Table 1 shows that ResNet-50 is more powerful than ResNet-18 enjoying a better accuracy with a higher confidence. On the contrary, adversarial retraining has notably spoiled the accuracy of this network.

Evaluation procedure.

Comparing attacks is difficult because they have different purposes. FGSM (6) and PGD 2 [START_REF] Li | Universal Perturbation Attack Against Image Retrieval[END_REF] are constrained on the distortion: the main parameter is the allocated distortion budget. In the literature, these attacks are gauged by measuring the probability of success for a given distortion budget. In contrast, CW [START_REF] Madry | Towards Deep Learning Models Resistant to Adversarial Attacks[END_REF] and DDN [START_REF] Ranjan | Attacking Optical Flow[END_REF] are forging an adversarial sample Table 1: Accuracy and confidence of the image classifiers measured on the NeurIPS competition [START_REF] Kurakin | Adversarial Attacks and Defences Competition[END_REF] dataset. Confidence is gauged as the mean of the estimated probability of the ground truth class as provided in the dataset, knowing that the prediction is correct.

Accuracy Confidence

ResNet-18 [START_REF] He | Deep Residual Learning for Image Recognition[END_REF] 84.1% 0.79 ResNet-50 [START_REF] He | Deep Residual Learning for Image Recognition[END_REF] 92.7% 0.88 ResNet-50R [START_REF] Madry | Towards Deep Learning Models Resistant to Adversarial Attacks[END_REF] 69.1% 0.60 almost surely (if the total number of iterations is large enough). These attacks are usually gauged by the average distortion. For a fair comparison, we adopt the methodology of [START_REF] Zhang | Walking on the Edge: Fast, Low-Distortion Adversarial Examples[END_REF] comparing operating characteristics. This characteristic is the function relating a distortion measure d to the probability of success 𝑃 𝑠𝑢𝑐 . Here, we measure the square root of the perturbation power (which is also the standard deviation in the pixel domain):

d(x 𝑞 , x 𝑜 ) := ∥x 𝑞 -x 𝑜 ∥/ √ 𝑛. ( 31
)
For example, FGSM gives d(x 𝑞 , x 𝑜 ) = 𝜖 since all pixels are modified by ±𝜖.

For CW and DDN (with or without quantization), the attack is mounted over the 𝑀 images {x 𝑜,𝑚 } 𝑀 𝑚=1 of the dataset. Images for which the attack failed are discarded. We measure the distortion for the adversarial images and construct the characteristic d → 𝑃 𝑠𝑢𝑐 ( d) with:

𝑃 𝑠𝑢𝑐 ( d) := 𝑀 -1 {𝑚 : d(x 𝑞,𝑚 , x 𝑜,𝑚 ) < d } . ( 32
)
For FGSM, IFGSM, and PGD 2 (with or without quantization), several parameter values are tested. For each image, we record the lowest distortion obtained for a success. This is what the attacker would do in a white-box scenario. For instance, with FGSM, we run a line search over 𝜖 in [START_REF] Kurakin | Adversarial examples in the physical world[END_REF] for each image in order to get the smallest possible value that succeeds in deluding the classifier. Then, the operating characteristic is constructed as mentioned above.

Illustration of our approach

This section gives some illustrations of our quantization mechanism Q 𝜆 ★ . Table 2 first offers some statistics counting how many pixels are quantized s.t. it induces a loss decrease. This concerns two populations of indices:

• indices in [𝑛]\J . Their quantization does not depend on 𝜆 ★ because it decreases both the distortion and the approximated loss (24). Their couple (𝑔( 𝑗), ⌈𝑢 ( 𝑗)⌉) lies in the hashed regions depicted in Fig. 3.This roughly corresponds to one fourth of the pixels (see Table 2).

• indices in J whose ratio (30) 𝑟 ( 𝑗) is lower than 𝜆 ★ . Q 𝜆 ★ quantizes these pixels because they offer a more interesting loss decrease at a rather small distortion increase.

The global percentage reflects the robustness of the classifier. A more robust classifier implies more pixels quantized to reduce the loss at the expense of more distortion. We clearly see that ResNet-18 is less robust than ResNet-50 less than ResNet-50R. This global percentage also reflects the power of the attack: PGD 2 is more powerful than FGSM.

Table 2: Percentage of quantization contributing to a loss decrease. The first number is the percentage of quantization decreasing both loss and distortion (see hashed regions in Fig. 3), the second number depends on the value of 𝜆 ★ . Figure 4 illustrates how we set the value of 𝜆 ★ by showing how the classifier loss and the distortion evolves as 𝜆 increases for a given image. The x-axis represent the pixel indices of J once sorted by their ratios {𝑟 ( 𝑗)} in ascending order. Our approach finds the index 𝑗 ★ for which the loss cancels and which defines 𝜆 ★ = 𝑟 ( 𝑗 ★ ). From the experiments we conducted, we have noticed that (24) is often a poor approximation of the true loss (21) of ResNet-18 and ResNet-50. This justifies the use of (21) in the line search for finding the value of 𝜆 ★ . The approximation (24) is then only used for ranking the pixels by the trade-off between distortion and classifier loss they individually provide. Yet, the approximation is much better for ResNet-50R. We suspect that this is due to the small norm gradient of the loss of this robust network.

Attacks

Experimental investigations

In this section, the attacks are conducted with the "best efforts", in the sense that their complexity is not limited. The total number 𝑁 of iterations is high, the step 𝛼 is small, many 𝜖 values are tested (see Sect. 3.2). The goal is to forge for each image its adversarial counterpart offering the best quality with the purpose of revealing the intrinsic power each attack. 𝜆 = +∞ (Sect. 4.2), and the optimal strategy where the best value 𝜆 ★ is found for each image (Sect. 4.4). The classifier is ResNet-18 and the attack is FGSM (6).

Figure 5 shows the operating characteristics when 𝜖 ∈ [0, 1]. For 𝜖 < 1, the pixel perturbation has an amplitude smaller than 1 and its quantization has the following two options: either {0, 1} or {-1, 0} depending on the sign of the perturbation. Therefore, for minimizing the distortion, Q 0 (x 𝑎 ) = x 𝑜 systematically. For 𝜖 = 1 exactly, the quantization has only one option (either {1} or {-1} depending on the sign of the perturbation). Then, d(Q 0 (x 𝑎 ), x 𝑜 ) = 1 and it happens that almost all the images are adversarial. Therefore, the operating characteristic for Q 0 is almost an all-or-nothing function.

𝑃 𝑠𝑢𝑐 ( d) > 0 for d ≲ 1 due to the border effect clipping the pixel values to the range [0, 255].

The rounding to the nearest integer R has the same operating characteristic in Fig. 5 . For 𝜖 < 0.5 the perturbation is rounded to 0 for all pixels. For 𝜖 > 0.5 the perturbation is rounded to ±1 and the result is the same as for 𝜖 = 1 Q 0 .

The operating characteristic for Q ∞ is more interesting. Suppose that for the 𝑗-th pixel, 0 < 𝑢 ( 𝑗) = 𝜖 < 1. According to [START_REF] Kurakin | Adversarial examples in the physical world[END_REF], this is due to the fact that the gradient of the loss at x 𝑜 has a negative component at index 𝑗. According to (28), Q ∞ quantizes this perturbation back to 0 if 𝑔( 𝑗) > -1/𝜆. Yet, that 𝑔( 𝑗) is the 𝑗-th component of the gradient computed at x 𝑎 . Hence for 𝜆 large enough, when these two gradients do not agree on the sign of the same component, that perturbation pixel is quantized to 0. We would expect this event to be seldom. However, since the operating characteristic is peaky around d = 0.7 ≈ 1/ √ 2 and that all the other perturbation pixels are quantized to ±1, it means that 50% of the pixels are quantized back to the original value.

From theses different results we can see that our approach Q 𝜆 ★ provides a huge improvement. Indeed, its operating characteristic is as good as the one of the unquantized FGSM. Quantization is especially more effective at middle range distortion: For d = 0.4, the success rate is higher by 10 points. Its operating characteristic also converges to a higher level.

5.3.2

With or without quantization. Figure 6 compares the operating characteristics for the attacks FGSM, IFGSM, PGD 2 , and CW with and without quantization (by rounding or by our approach) against ResNet-18.

Without quantization, we find back the hierarchy well-known in the literature: CW is better than PGD 2 better than IFGSM better than FGSM. Note that the difference between CW and PGD 2 is not tangible in this Fig. 6 (dashed plots) because we use a super-fine step for PGD 2 . Rounding completely spoils these attacks because the distortion before quantizing is too low (dotted plots). This illustrates the theoretical study of Sect. 3.3. Our approach almost preserves the operating characteristics without rounding (plain curves). Indeed, our quantization mechanism improves FGSM but slightly degrades the other attacks. The hierarchy is preserved but the differences are now tiny. 5.3.3 Natural vs. robust network. Figure 7 shows operating characteristics against a deeper network (ResNet-50) and its robust version (ResNet-50R) fine-tuned by adversarial retraining with PGD 2 .

Attacking a deeper network does not change much the performances except for the rudimentary FGSM: 𝜖 must be bigger than 1 to reach 90% in success rate. Note that our approach fixes this as 𝑃 𝑠𝑢𝑐 ( d) > 90% for d = 0.5. As for the other attacks, our approach preserves the operating characteristics.

Attacking the robust network is another story. For a given level of 𝑃 𝑠𝑢𝑐 , the necessary distortion is much bigger. Note that the range of the x-axis in Fig. 7 is not the same as the one of Fig. 6. CW and PGD 2 are attacks more powerful than FGSM and IFGSM.

For FGSM, our approach produces an operating characteristic with 'leaps'. One leap corresponds to a range (𝑘, 𝑘 + 1] with 𝑘 ∈ N for the parameter 𝜖. This is due to the fact that our approach is constrained: For any value inside that range, it quantizes |𝑢 ( 𝑗)| to {𝑘, 𝑘 +1}. Indeed, for 𝜖 ∈ N, the quantization introduces no changes: Q 𝜆 (x 𝑎 ) = x 𝑎 . This is where the operating characteristic touches back the one without quantization. As for the other attacks, our approach improves or at least preserves the operating characteristic without quantization. For each image, the original is shown in the first column. For both network, the image on the left corresponds to the rounding that occurred when saving an adversarial sample x 𝑎 forged by PGD 2 in the 'png' format. This rounded image is no longer adversarial except for the zebra on ResNet-50R. The image on the right shows the result when quantizing PGD 2 with our approach.

When quantized with our method, the four images remain adversarial. On ResNet-50 our method increases the distortion in order to remain adversarial. On ResNet-50R our method actually slightly decreases the distortion and returns an adversarial image.

Although distortions are different in between the two images, they remain visually similar. On ResNet-50 the perturbation is imperceptible while it is very much is on ResNet-50R. This illustrates how the adversarial training defends the network against an attack.

Benchmark

This section now compares the attacks with our quantization to DDN [START_REF] Ranjan | Attacking Optical Flow[END_REF], one of the rare attack 'natively' producing quantized digital images in the recent literature For a fair comparison w.r.t. complexity, the attacks are mounted against the robust network ResNet-50R but with a limited complexity (contrary to the previous study): they all compute 100 gradients. In other words, the total number of iterations is 𝑁 = 100.

The setup is the following:

• FGSM (6). 𝑁 = 100 × 1: We test a hundred values ranging in 0.15 * {1, 2, . . . , 100} for parameter 𝜖.

• IFGSM [START_REF] Kurakin | Adversarial Attacks and Defences Competition[END_REF]. 𝑁 = 5 × 20: Parameter 𝜖 is set to dmax /𝑁 with 𝑁 = 20 and dmax is given by a 5-step binary search over [0, 15]. • PGD 2 [START_REF] Li | Universal Perturbation Attack Against Image Retrieval[END_REF]. 𝑁 = 2 × 5 × 10. For ResNet-50, 𝛼 ∈ {1, 5}. For ResNet-50R, 𝛼 ∈ {50, 100}. A 5-step binary search finds the correct 𝜖 to produce an adversarial example after 10 iterations.

• CW [START_REF] Madry | Towards Deep Learning Models Resistant to Adversarial Attacks[END_REF]. 𝑁 = 5 × 20: 5 iterations for the outer loop, 20 for the ADAM inner loop, and a margin 𝑚 = 0. The learning rate is 0.005 (resp. 0.01) and 𝜇 is initialized to 1000 (resp. 5000) for ResNet-50 (resp. ResNet-50R).

• DDN [START_REF] Ranjan | Attacking Optical Flow[END_REF]. 𝑁 = 2 × 50: For ResNet-50, 𝛼 ∈ {100, 500}. For ResNet-50R, 𝛼 ∈ {1000, 5000}. Each value of 𝛼 is tested with 𝑁 = 50 iterations and 𝛾 = 0.05. Fig. 9 shows that CW and PGD 2 are now on par when under limited complexity (CW is slightly better at low distortion but PGD 2 is better when d ≥ 4 against ResNet-50R). DDN is not performing well as it is worse than CW, PGD 2 , and even IFGSM for ResNet-50. The next section investigates on this difficulty.

INTEGRATION INSIDE AN ITERATIVE ATTACK

So far, our quantization mechanism is decoupled from the attack forging x 𝑎 . This is in strong contrast with the quantized version of DDN in [START_REF] Rony | Decoupling Direction and Norm for Efficient Gradient-Based L2 Adversarial Attacks and Defenses[END_REF] where a rounding concludes each iteration. This section proposes a proof of concept on how to integrate our quantization mechanism inside an iterative attack like DDN.

The main message is that this integration must follow the spirit of the attack. In DDN, the iteration (10) is driven by a distortion budget parametrized by 𝜌 (𝑖) . This budget is adaptively scheduled over the iterations in the following way: it is increased if the sample x (𝑖-1) 𝑎

is not yet adversarial, it is decreased if that sample is already adversarial. However, the rounding concluding the iteration may spoil this fine-tuning of the distortion as seen in Sect. 3.3.

Our approach is able to better handle this distortion scheduling. It amounts to change the setting of the Lagrangian parameter in (26). We will define it by 𝛿 ★ , not to confuse with 𝜆 ★ . As illustrated in Fig. 4, the distortion from x 𝑜 is an increasing function of 𝜆. Therefore, we set 𝛿 ★ as the value of 𝜆 which gives the scheduled distortion.

Once the pixels of J (29) are ranked according to their ratios {𝑟 ( 𝑗)} defined in (30), the line search finds the first (resp. last) index 𝑘 ★ s.t. 𝛿 ★ = 𝑟 (𝑘 ★ ) produces a distortion bigger (resp. smaller) than the targeted budget when the previous sample x (𝑖-1) 𝑎

is not yet (resp. is already) adversarial. This defines the quantization Q 𝛿 ★ which minimizes the approximated classifier loss while fulfilling the scheduled distortion. This has to be done for each iteration. However, since the stopping condition is defined via the distortion, the line search no longer calls the classification network. Usually, the complexity of an attack is measured by the number of calls to the classifier. Our integration inside DDN does not spoil its low complexity as it only consumes one gradient computation. This gradient information is used to compute ratios {𝑟 ( 𝑗)} defined in (30). Fig. 10 shows operating characteristics of three versions of DDN:

• The original version of the quantized DDN which concludes each iteration by a rounding R,

• The original version of the unquantized DDN followed at the end by our quantization Q 𝜆 ★ ,

• Our integrated version of DDN which concludes each iteration by quantization Q 𝛿 ★ .

This comparison shows that the last two variants are better than the original scheme. This outlines that the quantification mechanism is of utmost importance. The last integrated version is the best. This tends to prove that quantizing at each iteration is better than quantizing only at the end provided that the quantization mechanism is appropriate. This is not surprising: by integrating the quantization inside the iterative process, we allows the upcoming iterations to compensate for the drift due to the quantization.

CONCLUSION

This paper proposes a new quantification mechanism of adversarial samples. It has two main features: i) It is a post-processing independent of the attack, ii) Its complexity adds an extra cost of 𝑂 (log 𝑛) calls to the network which is small compared to the complexity of the attack. Another point is that this mechanism can also be integrated inside an iterative attack like DDN. Overall, thanks to our quantification, the integral constraint no longer spoil the operating characteristic of the attacks against natural and robust classifiers. The main difference is that the attacks CW, PGD 2 , and DDN are more or less equally efficient under this constraint.

Figure 8 shows that the perturbation is clearly visible on some adversarial images against robust classifier. Our future work aims at taking into account a distortion metric better reflecting human perceptibility than the Euclidean distance.

Figure 2 :

 2 Figure 2: Expected power E(𝐷 2 )/𝑛 after rounding as a function of the perturbation power 𝜌 2 /𝑛 before rounding.

Figure 3 :

 3 Figure 3: Quantizing with Q 𝜆 the domain (𝑔( 𝑗), ⌈𝑢 ( 𝑗)⌉). The colored regions show when 𝑞( 𝑗) is quantized to ⌈𝑢 ( 𝑗)⌉ -𝑢 ( 𝑗), i.e. Q 𝜆 (𝑥 𝑎 ( 𝑗)) = 𝑥 𝑜 ( 𝑗) + ⌈𝑢 ( 𝑗)⌉, depending on 𝜆. In the complementary half-plane, 𝑞( 𝑗) = ⌊𝑢 ( 𝑗)⌋ -𝑢 ( 𝑗) and Q 𝜆 (𝑥 𝑎 ( 𝑗)) = 𝑥 𝑜 ( 𝑗) + ⌊𝑢 ( 𝑗)⌋. In the hashed areas, quantization is always the same, independently of 𝜆.

Figure 4 :

 4 Figure 4: Trade-off between the classifier and the distortion as 𝜆 𝑟 ( 𝑗) for increasing sorted index 𝑗. (Top) ResNet-50, (Bottom) ResNet-50R.

5. 3 . 1 Figure 5 :

 315 Figure 5: Operating characteristic of FGSM against classifier ResNet-18 for 𝜖 ∈ [0, 1].

Figure 6 :

 6 Figure 6: Operating characteristic for FGSM, IFGSM, PGD 2 , and CW against ResNet-18. (dashed) without quantization, (dotted) with rounding, (plain) with our approach.

  -𝜆 = 𝜆 ★ Natural -unquantized Robust -𝜆 = 𝜆 ★ Robust -unquantized

Figure 7 :

 7 Figure 7: Operating characteristics against a natural network (ResNet-50) or a robust network (ResNet-50R) with and without quantization for the attacks (Top) FGSM and IFGSM, (Bottom) PGD 2 and CW.

Figure 8

 8 Figure 8 displays some of the worst case examples with visible distortion against ResNet-50R and their equivalent on ResNet-50.For each image, the original is shown in the first column. For both network, the image on the left corresponds to the rounding that occurred when saving an adversarial sample x 𝑎 forged by PGD 2 in the 'png' format. This rounded image is no longer adversarial except for the zebra on ResNet-50R. The image on the right shows the result when quantizing PGD 2 with our approach.When quantized with our method, the four images remain adversarial. On ResNet-50 our method increases the distortion in order to remain adversarial. On ResNet-50R our method actually slightly decreases the distortion and returns an adversarial image.Although distortions are different in between the two images, they remain visually similar. On ResNet-50 the perturbation is imperceptible while it is very much is on ResNet-50R. This illustrates how the adversarial training defends the network against an attack.

Figure 8 :

 8 Figure 8: Examples of adversarial images against natural ResNet-50 and its robust version ResNet-50R. They are created with PGD 2 followed by a rounding (2nd and 4th columns) or our approach (3rd and 5th columns).

Figure 9 :

 9 Figure 9: Benchmark of the attacks against natural (ResNet-50 -thin lines) and robust (ResNet-50R -thick lines) networks with limited complexity and quantization.

Figure 10 :

 10 Figure 10: Operating characteristics of three DDN mentations against natural (ResNet50 -thin lines) and robust (ResNet-50R -thick lines) networks with limited complexity.

⌈𝑥 ⌉ is defined as the unique integer s.t. ⌈𝑥 ⌉ -1 < 𝑥 ≤ ⌈𝑥 ⌉. ⌊𝑥 ⌋ is defined as the unique integer s.t. ⌊𝑥 ⌋ ≤ 𝑥 < ⌊𝑥 ⌋ + 1.

A margin 𝑚 ≤ 0 can be also be enforced with L 𝑄 (q) < 𝑚 < 0.

ACKNOWLEDMENTS

This work has been funded in part by the French National Research Agency (ANR-18-ASTR-0009), ALASKA project: https:// alaska.utt.fr, by the French ANR DEFALS program (ANR-16-DEFA-0003) and by the ANR chaire IAD SAIDA.


Damien Vergnaud
email: damien.vergnaud@ens.fr

Keywords:

Zheng, Xiang and Zhou published in Journal of Computer and System Sciences in 2015 a "strong provably secure IBE scheme without bilinear map". In this note, we provide two very simple attacks on their scheme.

Introduction

Identity-based cryptography was introduced by Shamir in [START_REF] Shamir | Identity-Based Cryptosystems and Signature Schemes, Advances in Cryptology -Crypto[END_REF]. It aims tosimplify key management by removing the need for digital certificates used in traditional public-key infrastructures. In such systems, users' public keys are public identifiers (e.g. email addresses) and the matching private keys are derived by a trusted party (called the private key generator). The first practical constructions for Identity-Based Encryption (IBE) was proposed by Boneh and Franklin [START_REF] Boneh | Identity-Based Encryption from the Weil Pairing[END_REF] and relies on the existence of efficient bilinear maps on specific groups. Since then, a large body of work has been devoted to the design of schemes with additional properties or relying on different algorithmic assumptions (e.g. [START_REF] Cocks | An Identity Based Encryption Scheme Based on Quadratic Residues[END_REF][START_REF] Gentry | Trapdoors for hard lattices and new cryptographic constructions[END_REF]).

It is desirable for cryptosystems based on the discrete logarithm problem to be constructed without relying on bilinear maps. In [START_REF] Zheng | A strong provably secure IBE scheme without bilinear map[END_REF], Zheng, Xiang and Zhou proposed a "strong provably secure IBE scheme without bilinear map". They claimed that their proposal achieves the so-called IND-ID-CCA security assuming the classical computational Diffie-Hellman assumption. In this note, we show that this claim is wrong and we show two very simple polynomialtime attacks on their scheme: the first one is against the one-wayness of the scheme and uses only the public parameters and the second one is a key-recovery attack that requires a few extraction queries (i.e. users' private keys for chosen identities).

Cryptanalysis of Zheng-Xiang-Zhou scheme

Description of Zheng-Xiang-Zhou scheme. Let (G, +) be a group of primeorder q (following [START_REF] Zheng | A strong provably secure IBE scheme without bilinear map[END_REF], we use additive notation for the group law). Given two generators P and Q = [a]P of G, the private key generator picks uniformly and independently at random h scalars r 1 , . . . , r h in Z * q for some integer h. It publishes the points [r i ]P and [r i ]Q for i ∈ {1, . . . , h} as the public parameters and keeps the values r i for i ∈ {1, . . . , h} as its secret key.

From a user public-key ID, a binary string of length h is derived using a hash function H id whose security properties are not specified in [START_REF] Zheng | A strong provably secure IBE scheme without bilinear map[END_REF]. Given this binary string H id (ID) = a 1 . . . a h ∈ {0, 1} h , the user secret key is derived by the privatekey generator as SK ID = h i=1 a i • r i mod q and we denote

P ID = h i=1 [a i r i ]P and Q ID = h i=1 [a i r i ]Q two elements in G that
can be publicly computed from ID and the public parameters.

The encryption algorithm uses two additional hash functions H 1 : G → {0, 1} k and H 2 : {0, 1} * → Z * q modelled as random oracles in the (flawed) secutity analysis. Given a message m ∈ {0, 1} k and an identity ID, the encryption algorithm picks at random σ ∈ {0, 1} k , computes r = H 2 (σ, ID), and outputs

c = ([r]P, H 1 ([r]P ID ) ⊕ σ, H 1 ([r]Q ID ) ⊕ m, H 2 (σ, ID)
) as the ciphertext. The decryption algorithm is described in [START_REF] Zheng | A strong provably secure IBE scheme without bilinear map[END_REF] (but is not relevant for the attacks). Description of the attack on the one-wayness. Given a ciphertex c = (c 1 , c 2 , c 3 , c 4 ), an adversary can trivially recover r as c 4 = H 2 (σ, ID) and then the associated plaintext as c 3 ⊕ H 1 ([r]Q ID . This attack is actually more efficient than the decryption algorithm described in [START_REF] Zheng | A strong provably secure IBE scheme without bilinear map[END_REF]. It comes from the use of a very poor redundancy scheme in order to achieve CCA-security that actually weakens the security of the IBE scheme. Even if this can be easily fixed, our second attack demonstrates that the scheme is broken beyond repair. Description of the key-recovery attack. For the key-recovery attack, we consider an adversary that is allowed to query only h times the Extract algorithm in order to obtain secret keys of users of its choice (and in particular is legitimate in the IND-ID-CCA security game describe in [START_REF] Zheng | A strong provably secure IBE scheme without bilinear map[END_REF]).

Even if H id is a strong cryptographic hash function or a random oracle (see [START_REF] Bellare | Random Oracles are Practical: A Paradigm for Designing Efficient Protocols[END_REF]), a very simple attack can be mounted. The adversary can simply pick iteratively identities ID j for j ∈ {1, . . . , h} at random such that the matrix A t = (a (j) i ) i∈{1,...,h},j∈{1,...,t} is of rank t in Z h×t q for t ∈ {1, . . . , h} (where

H id (ID j ) = a (j) 1 . . . a (j)
h for j ∈ {1, . . . , h}). If H id is a random oracle, then A h is a random binary matrix over Z q . It is well-known that a random (h × h)-matrix over Z q where each entry is chosen independently and uniformly at random in Z q is non-singular with at least some constant probability [START_REF] Landsberg | Über eine Anzahlbestimmung und eine damit zusammenhängende Reihe[END_REF]. The problem is less studied for random binary matrices over finite fields but one can easily prove (e.g. [2, Lemma 4]) that if one concatenates a random binary vector of length h to a binary (h × n)-matrix of rank r < h, then the rank of the resulting (h × n + 1)-matrix is r + 1 with probability at least 1/2. Therefore, by picking on average only 2h identities ID, the adversary can construct an invertible matrix A h as described and it can recover the secret key vector (r 1 , . . . , r h ) as (SK ID1 , . . . , SK ID h ) • t (A -1 ) (by quering the Extract algorithm on the h identities ID j for j ∈ {1, . . . , h}).