Jannik Dreier
email: jannik.dreier@imag.fr

Florian Kerschbaum
email: florian.kerschbaum@sap.com

Practical Secure and Efficient Multiparty Linear Programming Based on Problem Transformation

Cryptographic solutions to privacy-preserving multiparty linear programming are slow. This makes them unsuitable for many economically important applications, such as supply chain optimization, whose size exceeds their practically feasible input range. In this paper we present a privacy-preserving transformation that allows secure outsourcing of the linear program computation in an efficient manner. We evaluate security by quantifying the leakage about the input after the transformation and present implementation results. Using this transformation, we can mostly replace the costly cryptographic operations and securely solve problems several orders of magnitude larger.

Introduction

Linear Programming (LP) can be used to solve many practical optimization problems, e.g. supply chain master planning [START_REF] Stadler | Supply chain management and advanced planning[END_REF]. Many practical problems are distributed and require protection of the input data. For example, in supply chain master planning, the participating companies need to exchange information about production costs and capacities. This is very sensitive data, since it directly impacts the negotiation position. Consequently no master planning solution will be adopted in practice that reveals this data [START_REF] Pibernik | An approach to inter-domain master planning in supply chains[END_REF].

1 Figure 1: Privacy-Preserving Linear Programming in the Cloud Secure multi-party computation (SMC) [START_REF] Ben-Or | Completeness theorems for non-cryptographic fault-tolerant distributed computation[END_REF][START_REF] Goldreich | How to play any mental game[END_REF][START_REF] Shamir | How to share a secret[END_REF][START_REF] Yao | Protocols for Secure Computations[END_REF] offers a cryptographic solution to the problem. Several parties can jointly compute a function, e.g. LP, without disclosing anything except what can be inferred by a party's input and output. In theory this offers an ideal solution to the conflict posed by these problems. There even exist a number of specialised protocols for secure LP [START_REF] Catrina | Secure multiparty linear programming using fixed-point arithmetic[END_REF][START_REF] Li | Secure and private collaborative linear programming[END_REF][START_REF] Toft | Solving linear programs using multiparty computation[END_REF].

Nevertheless these solutions suffer from a prohibitively bad computational performance. We estimate that our prototypical implementation of Toft's protocol [START_REF] Toft | Solving linear programs using multiparty computation[END_REF] requires 7 years in order to solve our use case LP problem with 282 variables. Supply chain planning problems can easily reach 4 million variables [START_REF] Braun | Optimization with grid computing[END_REF] and these are only single company planning problems while we consider cross-organizational optimization. These size of problems are currently solved every day by non-secure LP solvers. Assuming an average computation complexity of O(n 3 ) for LP and that Moore's Law continues to hold for the time being, it would still take roughly 80 years until these problems could be solved securely as fast as they can be solved non-securely today. Clearly, if we want to solve these problems today, we need a different approach.

In [START_REF] Vaidya | Privacy-preserving linear programming[END_REF] Vaidya presents a different approach to the problem. Instead of implementing a LP solver using SMC the problem is randomly transformed and then the problem is solved using a non-secure LP solver. Unfortunately as Bednarz already points out in [START_REF] Bednarz | Hiccups on the road to privacypreserving linear programming[END_REF] Vaidya's transformation is incorrect and may lead to solutions which are not admitted in the original problem. In this paper we present a new, correct transformation. Furthermore we do not settle for an informal assessment of its security, but instead evaluate it in the framework of leakage quantification. Finally, we present performance results from our implementation.

Let L be an instance of a LP problem where parties X i have input x i , e.g. variables, constraints or costs. The approach of [START_REF] Catrina | Secure multiparty linear programming using fixed-point arithmetic[END_REF][START_REF] Li | Secure and private collaborative linear programming[END_REF][START_REF] Toft | Solving linear programs using multiparty computation[END_REF] is to implement a LP solver for L using SMC where x i is the input of each party. Let g be our privacy-preserving transformation, then L = g(L) is another instance of a LP problem, but L reveals little information about L. We can outsource the solution of L to an untrusted service provider, e.g. the cloud. Either a single party computes g on its data, e.g. a single company instance of supply chain planning, or we can securely compute g using SMC for multiple parties. We show that computing g is much more efficient than implementing a LP solver and even present an optimized secure computation protocol for it. The solution computed by the cloud on L then needs to be transformed by g to the solution of L. Figure 1 depicts our approach to privacy-preserving linear programming in the cloud.

In summary this paper contributes

• a novel privacy-preserving transformation for linear programs regardless of their partitioning.

• a proof that differently from previous work the transformation is correct, i.e. an optimal solution to the transformed problem always corresponds to an optimal solution of the original problem.

• an analysis that the transformation is secure in the framework of leakage quantification. In our use case example the chances of guessing e.g. the optimal values x are less than 2.30 • 10 -1409 .

• a secure computation protocol to efficiently compute the transformation in a multiparty case.

• a theoretical analysis and performance results of our implementation that show that the transformation is efficient. In our use case example the solution only required 25 minutes (compared to 7 years for Toft's protocol).

The remainder of this paper is structured as follows. In the next Section we will review related work. In Section 3 we present our main result, the privacy-preserving transformation. We will prove the correctness of the transformation in Section 4 and analyze its performance in Section 5. In Section 6 we summarize our results from leakage quantification of this transformation. We show the protocol for securely computing the transformation in Section 7. The results from our use case example are described in Section 8. We conclude the paper in Section 9.

Related Work

Our work is related to secure multi-party LP solvers [START_REF] Catrina | Secure multiparty linear programming using fixed-point arithmetic[END_REF][START_REF] Li | Secure and private collaborative linear programming[END_REF][START_REF] Toft | Solving linear programs using multiparty computation[END_REF], secure outsourcing [START_REF] Atallah | Securely outsourcing linear algebra computations[END_REF][START_REF] Atallah | Secure outsourcing of scientific computations[END_REF][START_REF] Bednarz | Hiccups on the road to privacypreserving linear programming[END_REF][START_REF] Du | Privacy-preserving cooperative scientific computations[END_REF][START_REF] Mangasarian | Privacy-Preserving Horizontally-Partitioned Linear Programs[END_REF][START_REF] Mangasarian | Privacy-Preserving Linear Programming[END_REF][START_REF] Vaidya | Privacy-preserving linear programming[END_REF] and leakage quantification [START_REF] Braun | Quantitative notions of leakage for one-try attacks[END_REF][START_REF] Smith | On the Foundations of Quantitative Information Flow[END_REF][START_REF] Wibmer | Leakage Quantification of Cryptographic Protocols[END_REF].

Secure Multi-Party LP Solvers

As mentioned above, different distributed LP solvers based on secure multiparty computation have been developed. Toft [START_REF] Toft | Solving linear programs using multiparty computation[END_REF] used a distributed secure Simplex algorithm based on secret sharing. This is usable for any number of participants and provides information-theoretic security, but turned out to be too slow in practice for realistically sized problems in many applications such as Supply Chain Management.

Li and Atallah [START_REF] Li | Secure and private collaborative linear programming[END_REF] also used a distributed Simplex algorithm. In contrary to Toft [START_REF] Toft | Solving linear programs using multiparty computation[END_REF] they concentrated on the case where the data is shared among only two parties. It is unclear if their algorithm can be efficiently extended to the multi-party case.

Catrina and de Hoogh [START_REF] Catrina | Secure multiparty linear programming using fixed-point arithmetic[END_REF] developed a more efficient version of the distributed Simplex algorithm using fixed-point arithmetics. However, their solution still is only suitable for relatively small inputs as it suffers from a higher asymptotic and worst-case complexity than our transformation.

Secure Outsourcing

Vaidya [START_REF] Vaidya | Privacy-preserving linear programming[END_REF] used a transformation approach which is the basis for our transformation. He supposed a scenario where one party holds the objective function and the other party the constraints. As a consequence his transformation does not protect the entire Linear Program, which is not appropriate for most applications. Additionally, he did not provide a formal security analysis and his work suffers from correctness problems [START_REF] Bednarz | Hiccups on the road to privacypreserving linear programming[END_REF].

Mangasarian [START_REF] Mangasarian | Privacy-Preserving Horizontally-Partitioned Linear Programs[END_REF][START_REF] Mangasarian | Privacy-Preserving Linear Programming[END_REF] proposed similar transformations for special input distributions (horizontal or vertical partitioning). Supply chain optimization problems have a more complex distribution which combines both cases. Additionally, his approach for horizontal partitioning is limited to equality constraints. This is not sufficient for supply chain optimization either, as we have to deal with capacity constraints expressed as inequality constraints. Our transformation addresses both shortcomings and is suitable for more general data distributions. Moreover he does not provide a formal security analysis.

Furthermore there is work on related problems such as matrix multiplication and linear systems of equations [START_REF] Atallah | Securely outsourcing linear algebra computations[END_REF][START_REF] Atallah | Secure outsourcing of scientific computations[END_REF][START_REF] Du | Privacy-preserving cooperative scientific computations[END_REF].

Leakage Quantification

To give a formal security assessment of our transformation, we use methods of Leakage Quantification which measure how much information about the secret input is revealed to an attacker. In particular, we concentrate on the metric of "Multiplicative Advantage" which was first developed (but not called so) by Smith [START_REF] Smith | On the Foundations of Quantitative Information Flow[END_REF] based on entropy loss using a special type of min-entropy. Later on this was analyzed more closely by Braun et al. [START_REF] Braun | Quantitative notions of leakage for one-try attacks[END_REF] who proposed another, simpler definition -the one we use in this paper. Compared to other metrics such as entropy loss or channel capacity using the standard Shannon-entropy, it is particularly expressive for one-try attacks as it gives a worst-case evaluation. To assess complex operations we make use of some theorems by Wibmer et al. [START_REF] Wibmer | Leakage Quantification of Cryptographic Protocols[END_REF] on the leakage of combined channels (see Appendix A).

The Transformation

Linear Programming is a standard tool in business optimization. A Linear Program (LP) consists of a set of unknown variables x, a linear target function c(x) representing the costs which shall be minimized (or equivalently the gain which has to be maximized) and a set of constraints (linear equalities or inequalities). The standard form is

min c T x s.t. M x ≤ B x ≥ 0 (1)
As we will eventually transform all inequalities into equalities and as in our use case many of the input constraints are actually equalities, we will treat them separately. This reduces the size of the problem as we need less slack-variables 1 and thus increases performance as well as security. So let the input problem -without loss of generality -be

min c T x s.t. M 1 x = b 1 M 2 x ≤ b 2 x ≥ 0 (2)
We use a positive monomial matrix 2 Q to hide c (as proposed by [START_REF] Vaidya | Privacy-preserving linear programming[END_REF][START_REF] Bednarz | Hiccups on the road to privacypreserving linear programming[END_REF]):

min c T QQ -1 x M 1 QQ -1 x = b 1 M 2 QQ -1 x ≤ b 2 Q -1 x ≥ 0 (3)
and a positive vector r to hide x

min c T Q(Q -1 x + r) M 1 Q(Q -1 x + r) = b 1 + M 1 Qr M 2 Q(Q -1 x + r) ≤ b 2 + M 2 Qr (Q -1 x + r) ≥ r (4)
For z = Q -1 x + r and a strictly positive diagonal matrix S 3 we have

min c T Qz M 1 Qz = b 1 + M 1 Qr M 2 Qz ≤ b 2 + M 2 Qr Sz ≥ Sr (5)
Then we define

c T = c T Q, M =   M 1 Q 0 M 2 Q A -S   , b =   b 1 + M 1 Qr b 2 + M 2 Qr -Sr   ( 6
)
where A is a permutation matrix 4 representing slack-variables. This allows us to rewrite the program as follows:

min c T s z s s.t. M z s = b z s ≥ 0 ( 7
)
2 A monomial matrix contains exactly one non-zero entry per row and column. 3 A diagonal matrix where the entries on the main diagonal Ai,i are strictly positive. 4 A permutation matrix is a monomial matrix where the non-zero entries are "1".

where c s is c with added zeros for the slack-variables and z s is the variable vector (z with added slack-variables). To hide the contents of M and b we use a nonsingular matrix

As z = Q -1 x + r, the resulting x can be obtained from z by calculating x = Q(z -r).

Correctness

For the transformation to be useful in practice, we have to ensure that the transformed program can still be used to find a solution to the original problem. We will prove that any optimal (i.e. with minimal cost) and feasible (with respect to the constraints) solution to the transformed problem corresponds to an optimal and feasible solution of the original problem using the following two lemmas. More precisely, Lemma 1 gives the equivalence of the solution space of the original and the transformed problem, i.e. the fact that each feasible solution in the original problem corresponds to a feasible solution in the transformed problem and vice versa. Lemma 2 states that back-transforming an optimal solution of the transformed LP yields an optimal solution to the original LP.

Lemma 1. A solution x is feasible in the original problem if and only if z = Q -1 x + r is a feasible solution to the transformed problem.

Proof. This is true by construction. The multiplication by P does not change the solution set as P is invertible. Q is monomial (which gives correctness for this part of the transformation as shown by Bednarz et al. [START_REF] Bednarz | Hiccups on the road to privacypreserving linear programming[END_REF]) and r is positive to not interfere with z ≥ 0. As S is a strictly positive diagonal matrix, the multiplication by S is actually a multiplication of each row with a positive scalar which leaves the inequalities untouched.

Lemma 2. Let z be the solution that minimizes c T z in the transformed LP. Then x = Q(z -r) minimizes c T x in the original problem.

Proof. We will use a proof by contradiction. Suppose that there is a solution

x with c T x < c T x. Then c T x < c T Q(z -r) ⇔ c T x < c T Qz -c T Qr ⇔ c T QQ -1 x + c T Qr < c T Qz ⇔ c T (Q -1 x + r) < c T z (9)
Apparently z = Q -1 x +r is a valid solution for transformed LP with strictly lower cost than z. Hence z is not optimal.

Performance

Performance is a key aspect: The transformation has to be significantly less complex than solving the problem itself, otherwise outsourcing would not represent an efficiency gain to the clients. From a theoretical viewpoint this is easy to see, as the most expensive operation during the transformation is the multiplication by P . Let m 1 and m 2 denote the number of rows of M 1 and M 2 respectively, and n the number of variables. Then the multiplication using a naive algorithm is in

O((m 1 + m 2 + n) 2 × (2n + m 2 )
). This is more efficient than the simplex algorithm (on which the secure LP solvers [START_REF] Catrina | Secure multiparty linear programming using fixed-point arithmetic[END_REF][START_REF] Li | Secure and private collaborative linear programming[END_REF][START_REF] Toft | Solving linear programs using multiparty computation[END_REF] are built on) with exponential worst case complexity [START_REF] Victor | How good is the simplex algorithm? Inequalities[END_REF]. Even in the average case or compared to interior point methods performance will be better due to smaller constants.

We will discuss practical performance in more detail our use case example in Section 8.

Security

We will now analyze the security of our transformation in the following setting: An attacker wants to obtain the input data (the original LP). He knows the transformed LP and some abstract facts about the input, for example that the input values are within a certain range (this is described more precisely later on).

Ideally we would like to give a classical security proof. However, as our transformation is based on disguising using random noise, the classical cryptological security definitions are unsuitable as our transformation will probably leak some information since the transformed LP is somewhat linked to the input and thus not entirely random. Nevertheless this can be acceptable for many applications as long as the leakage is small and bounded, in particular as we get dramatic performance improvements in return. To formally evaluate this leakage and to show that it is "small and bounded", we use Leakage Quantification methods based on information theory.

We start by defining the metric "Multiplicative Advantage". Then we analyze the leakage of several elementary operations such as permutations and scalar as well as matrix multiplication. By combining these results we establish bounds on the leakage of different parts of the transformation. In the last part we discuss possible attacks.

Multiplicative Advantage

The disguising transformation is modeled as a communication channel as known from information theory (for an introduction to information theory see e.g. Cover and Thomas [START_REF] Cover | Elements of information theory[END_REF]).

Definition 1 (Channel). A discrete, noisy and memoryless channel C is given by

• A finite set X = x 1 , ..., x n called the input alphabet,
• a finite set Y = y 1 , ..., y n called the output alphabet,

• for each x ∈ X a random variable C|x that takes values in Y.

The input x ∈ X represents the data to hide, the output y ∈ Y is the "encrypted" or "disguised" data that is passed into the cloud. The definition of the input alphabet X is important as it reflects the attackers "abstract knowledge" about the input, for example that the input is a value within a certain range.

Braun et al. [START_REF] Braun | Quantitative notions of leakage for one-try attacks[END_REF] defined the notion of "advantage" based on a similar notion ("vulnerability") by Smith [START_REF] Smith | On the Foundations of Quantitative Information Flow[END_REF]. For a random variable X characterizing the input distribution let

P R priori (X) = max i p(X = x i ) ( 10
)
denote the a priori probability of a right guess (i.e. the probability of an attacker correctly guessing the input if it has not yet seen the output of the channel). Similarly let

P R posteriori (X) = j max i (p(y j |x i )p(X = x i )) (11)
denote the a posteriori probability of a right guess (i.e. the probability of an attacker correctly guessing the input after having seen the output of the channel). Then we define

L (X) = P R posteriori (X) P R priori (X) (12)
the factor by which the knowledge of the output of the channel increases the chances of a right guess for a given X6 .

Definition 2 (Multiplicative Advantage). The Multiplicative Advantage or Multiplicative Leakage of a channel C is defined as

L(C) = max X L (X) (13)
L(C) is independent of the input distribution, which is convenient if this distribution is not known. Additionally L (X) has the advantage of attaining its maximum for a uniform input distribution [START_REF] Braun | Quantitative notions of leakage for one-try attacks[END_REF][START_REF] Wibmer | Leakage Quantification of Cryptographic Protocols[END_REF] which yields

L(C) = j max i p(y j |x i ) ( 14
)
This result is very useful in practice as p(y j |x i ) are the entries of the channel matrix. Furthermore Wibmer et al. [START_REF] Wibmer | Leakage Quantification of Cryptographic Protocols[END_REF] showed that multiplicative leakage can be used to easily bound the leakage of compositions of independent channels which simplifies the analysis of complex protocols. A list of different channel compositions and their leakage can be found in Appendix A.

Building Blocks

We will now analyze the three main building blocks of our transformation: Permutations, scalar multiplications and matrix multiplications.

Permutation

To determine the leakage of a permutation, we model the "permutation channel" P n k as follows: The channel input and output are vectors with k elements from 0 to n each. More formally, let X = Y = {x|x = (x 1 , ..., x k )} where x i ∈ 0, ..., n. 7Theorem 1 (Leakage of a Permutation). The multiplicative leakage of a uniformly distributed permutation of a vector with k elements ranging from 0 to n is given by

L(P n k ) = (n + k)! k! * n! (15)
Proof. Idea: Partition all possible output vectors Y into classes of vectors Y i that are permutations of each other. If each permutation is equally likely, the channel matrix contains -for each class -|Y i | columns with a maximum of 1 |Y i | each. Hence the multiplicative leakage of a permutation is equal to the number of different classes. Each class can be characterized by the number of occurrences of each value in vector y. Counting these possibilities yields the result.

An intuitive interpretation of this result is that a permutation leaks the "class" to which a vector belongs, but nothing more since each vector inside this class is equally likely.

Scalar Multiplication

We use the following model: The channel inputs are values x ∈ {0, ..., n}, the output is a value y ∈ {0, ..., n k+1 } where k is the number of factors of f (i.e. y = x * f = x * k i=1 f i where f i ∈ {1, ..., n}). Let f (not the f i -s) be uniformly distributed among all the possible values8 and M k n denote the channel for parameters n and k.

Theorem 2 (Leakage of a Multiplication). The leakage of a Multiplication channel M k n is bounded by

L(M k n ) ≤ n + k k + 1 + 1 (16) Proof. Idea: Let A(n, k) denote the number of different values of f = k i=1 f i with f i ∈ 1..n.
Bearing in mind that input value 0 is always completely leaked (which adds 1 to the leakage) we have

L(M k n ) = A(n, k + 1) A(n, k) + 1 (17)
A(n, k) is bounded by the number of different combinations of the f i when only distinguishing number of occurrences of each value in 1, .., n (and ignoring their order):

A(n, k) ≤ n -1 + k k = (n + k -1)! k! * (n -1)! ( 18
)
Although this is only an upper bound, the quotient

(n + (k + 1) -1)! (k + 1)! * (n -1)! / (n + k -1)! k! * (n -1)! = n + k k + 1
is still a valid bound for A(n,k+1) A(n,k) as the "errors" in the denominator cancel out with the "errors" in the nominator.

Matrix Multiplication

We define a matrix multiplication channel M k,n,l as follows. Channel inputs are k × l-matrices (k ≤ l) X with rank k and elements from 0 to n, the output Y = P * X is the result of a multiplication by a randomly chosen invertible square matrix P of dimension k × k with elements from 0 to n.

Similarly we define another matrix multiplication channel M k,n,l as follows. Channel inputs are regular square k × k-matrices X with elements from 0 to n, the output Y = X * M is the result of a multiplication by a randomly chosen matrix M of dimension k × l (k ≤ l) with rank k and elements from 0 to n. 9To minimize the leakage, we choose P (and M respectively) uniformly among all possible matrices of the correct size and values. Figures 2 and3 show the resulting multiplicative leakage for different values of k, n and l.

The leakage grows with n and l for a fixed k. To obtain more meaningful values we calculated the resulting a-posteriori probability of a right guess for a uniform input distribution using the following equation

P R posteriori (X) ≤ L(M k n ) * P R priori (X) (19)
Note that these values coincide for M k,n,l and M k,n,l . Results are shown in Figure 4. The a-posteriori probability appears to converge to a constant value for each k but drops very quickly for growing k.

The Complete Protocol

After having analyzed the leakage of the basic operations, we will now establish bounds on the leakage of the three main parts of the transformation.

Leakage of the cost function c

In our transformation c is hidden by a monomial matrix Q, i.e. a permutation and a multiplication of each entry with a scalar value. Supposing independent channels and applying Theorems Figure 4: A posteriori probability of a right guess for a matrix multiplication channel [START_REF] Wibmer | Leakage Quantification of Cryptographic Protocols[END_REF] we can conclude that

L(c l n,k ) ≤ min L(M l n ) k , L(P A(n,l) k ) ≤ min n+l l+1 + 1 k , (A(n,l)+k)! k! * (A(n,l))! (20)
where c l n,k denotes the channel for a k-dimensional input vector c hidden by a multiplication by a monomial matrix and A(n, l) as defined above. Note that this is the leakage quantification of c only, although Q appears in other places in the transformation as well (in the constraint matrix, on the right hand side and in z). However, this simplification is realistic as the other occurrences are well-hidden (cf. Section 6.4.2).

Leakage of the variables x

The variable vector z s consists of two parts: The non-slack variables z and the slack-variables. The non-slack variables contain values z = Q -1 x + r.

Wibmer et al. [START_REF] Wibmer | Leakage Quantification of Cryptographic Protocols[END_REF] showed that for a channel y = rx+r with r < r ≤ r m and x ≤ x m the leakage is bounded between

(r m -1) log(x m + 2) r m + 1 ≤ L("y = rx + r ") ≤ 2 x m + 1 + (r m -1) log rm * (xm+2)-1 rm-1 r m + 1 (21) or for r m → +∞ log(x m + 2) ≤ L("y = rx + r ") ≤ 2 log(x m + 2) ( 22
)
The channel "z = Q -1 x + r" can be modeled as a permutation followed by the "y = rx + r "-channel as Q resp. Q -1 is a monomial matrix and thus we have

L("z = Q -1 x + r") ≤ min 2 log(x m + 2), (x m + k)! k! * x m ! (23)
As mentioned before, the matrix Q is also used in the hiding of c. This is not a problem, since the vector r prevents the search for common factors (cf. Section 6.4.2).

The slack variables contain potentially correlated values as well (S * Q -1 x), but since they are permuted it is hidden which variable belongs to which constraint (cf. Section 6.4.2). This further complicates exploiting correlation by common factors. The leakage of M 1 , M 2 , b 1 and b 2 is difficult to estimate due to the number and complexity of related transformation steps.

On the one hand, the following analysis shows that breaking the hiding with P almost completely reveals all other hiding operations: If P is known or can be guessed by the attacker, he can undo nearly the whole transformation (cf. Figure 5). First of all he can obtain S, which allows him to calculate r. This gives access to b 1 and b 2 . As Q is a monomial matrix, each row of M {1,2} Q is multiplied with the same factor which he can guess with very high probability when searching for common factors (see Section 6.4.2 for details). This then leaks a permutation of M 1 , M 2 and c, which may be a complete break if the attacker knows something about the structure of M 1 or M 2 which allows him to undo the permutation. This shows that the security of P is crucial for the security of the whole protocol. We will analyze attacks on P in more detail in Section 6.4.1. Thus we can say that the constraints are at most as safe as P .

On the other hand they are unlikely less safe than P , since conversely the knowledge of the constraints noticeably increases the chances of guessing P . We will now give an estimation of the leakage of P . To simplify the analysis, we use the following channel model: The input alphabet X are invertible square matrices of dimension (m 1 + m 2 + k) × (m 1 + m 2 + k) (where m 1 and m 2 are the number of rows of M 1 and M 2 ; k is the number of variables). The channel output is

P * B = P * B' 0 A ( 24
)
where A is a permutation matrix of dimension (m 2 + k) × (m 2 + k) and B a random matrix of dimension (m 1 + m 2 + k) × (k + 1). B represents the parts of M which contain M 1 Q, M 2 Q and -S as well as b (which can be seen as just another column of the matrix). The general idea is that A is responsible for most of the leaked information about P and that attackers have very limited knowledge about the other parts of the matrix, so that modeling them as random appears plausible. This model allows us to benefit from Definition 6 and Theorem 6 form Appendix A. We split the channel C P into a first channel C P,1 which calculates P * B

and a second channel C P,2 which calculates

P * 0 A (26)
Then Theorem 6 from Appendix A (by Wibmer et al. [START_REF] Wibmer | Leakage Quantification of Cryptographic Protocols[END_REF]) gives that max {L(C P,1 ), L(C P,2 )} ≤ L(C P )

≤ L(C P,1 )L(C P,2 ) (27)

C P,1 corresponds to the matrix multiplication channel M k,n,l analyzed above.

The leakage of C P,2 can be bounded using the following theorem.

Theorem 3 (Leakage of Slack-Variables). Let A n,k,l denote the channel with invertible square matrices of dimension (k + l) × (k + l) with values between 0 and n as input X and a matrix Y of dimensions (k + l) × k as output so that

Y = X * 0 A ( 28
)
where A is a permutation matrix of dimensions k × k and 0 a l × k matrix containing zeros (0

≤ l ≤ k). Then k-1 i=0 ((n + 1) k+l -(n + 1) i ) k! ≤ L(A n,k,l ) ≤ k i=1 ((n + 1) k+l -i) k! (29)
Proof. Idea: The resulting matrix Y contains k vectors with k + l entries each. By following the same reasoning as in Theorem 1 we can show that the leakage is equal to the number of permutation classes. In this case each permutation class corresponds to a set of k linearly independent vectors of dimension k + l as X is invertible. Counting the number of possible sets yields the bounds.

Cryptanalysis

In this Section we will discuss several attacks on P and Q, the most important parts of the transformation.

Attacks on P

Attacks on P will probably be based on the structure of the matrices as this is the most promising approach. The biggest issue are the slack-variables as the following example illustrates. Consider these constraints:

M * x ≤ b x ≥ 0 ( 30
)
When adding slack-variables we obtain (I is the identity matrix)

M I * x = b x ≥ 0 (31)
If we multiply by P the result is

P * M P * x = P * b x ≥ 0 (32)
This means that the slack-variables completely reveal P . Unfortunately the most general type of matrix we can use instead of the identity matrix I is a monomial matrix A as A and A -1 have to be positive [START_REF] Kaczorek | Positive 1D and 2D systems[END_REF]. Yet this is only partly helpful as the knowledge of P * A allows an attacker to calculate

M = (P * A) -1 * (P * M ) = A -1 * P -1 * P * M = A -1 * M (33)
As A is a monomial matrix, A -1 * M is a permutation of M where each column is multiplied with the same value -which can be obtained with very high probability when searching for common factors. Not transforming the inequalities into equalities is not an option, as this would reduce our choice of P to monomial matrices for correctness reasons. This would turn P * M into an easy target for factorization attacks and thus not provide enough security.

To solve the problem, we treat equality constraints separately. This reduces the size of A, as we need less slack-variables. If A is smaller than P , it only leaks a permutation of some columns of P and not the entire matrix. However, this requires that in the input problem some of the constraints are equations, which is not always the case. Yet in our target application Supply Chain Management most of the constraints are actually equations, which turns this into a very well-suited solution.

If the input problem contains only inequality constraints, we can still improve security by assigning non-zero costs to slack-variables and permuting the variables to hide them among the real variables. A possible way to do this without changing the optimal solution is by analyzing the dual problem [START_REF] Sierksma | Linear and Integer Programming: Theory and Practice[END_REF].

Attacks on Q

Q is a positive monomial matrix, i.e. it can be written as Q = D * E where D is a diagonal matrix and E a permutation matrix (i.e. a matrix with exactly one entry equal to 1 per row and column). Thus

Q -1 = (D * E) -1 = E -1 * D -1 = E T * D -1 where D =    D 1 • • • 0 . . . . . . . . . 0 • • • D n    , D -1 =    1 D 1 • • • 0 . . . . . . . . . 0 • • • 1 Dn   
Q appears in several places in the transformation. This can be an issue if the resulting products of Q and Q -1 with M 1 , M 2 , c etc. allow the search for common factors. Since two random numbers have an asymptotic probability 6/π 2 ≈ 61% of being coprime [START_REF] Kiltz | Secure computation of the mean and related statistics[END_REF] and this rapidly increases for three or more numbers, this search is very likely to be successful if we have access to several numbers containing the same factor. Thus we have to ensure that there are no two or more values which contain the same factor.

We will now analyze all occurrences of Q inside the transformation.

• The cost function

c = c T * Q = c T * (D * E) = c 1 * D 1 c 2 * D 2 • • • c n * D n * E
contains all the factors of D, but each factor appears only once inside one of the entries.

• M {1,2} Q has the following structure

M 1 * Q = M 1 * (D * E) =    M 1,1 * D 1 • • • M 1,n * D n . . . . . . M m 1 ,1 * D 1 • • • M m 1 ,n * D n    * E
This is open for attack as there are lots of values containing the same factor. However, since inside M there is -S below (cf. Eq. 6), M = P * M has a different structure. For example

M 1,1 = m 1 i=1 P 1,i * (M 1 Q) i,1 + m 2 i=1 P 1,i+m 1 * (M 2 Q) i,1 -P 1,m 1 +m 2 +1 * S 1
contains a common factor D j in all summands except for the last. This is enough to make the values unusable for factorization attacks.

• M {1,2} Qr is secure against factorization attacks since

(M 1 Qr) 1 = n i=1 (M 1 Q) 1,i * r i
where each (M 1 Q) 1,i contains a different D j .

• z = Q -1 x + r is protected against factorization attacks by r.

• The slack-variables could also leak the factors inside Q as the i-th constraint concerning S has the form

-S i * z i + Z s i = -S i * r i which gives Z s i = S i * (z i -r i ) = S i * ((Q -1 x) i + r i -r i ) = S i * (Q -1 x) i
This would allow the search for common factors. However, the slackvariables are permuted independently of Q so that it is unknown which variable belongs to which constraint. To find possible matches an attacker could search for pairs of variable whose difference is smaller than the maximum of r. However, this is made harder by S as Z s i -

z i = S i * z i -S i * r i -z i = (S i -1)z i -S i * r i (
and not -r i as it would be the case if S i = 1 for all i).

Overall only in c the factors inside Q are easily accessible. Thus the search for common factors is difficult, if possible at all, which is of great importance for the security of c.

Going Multi-Party

To be able use the transformation in a multi-party scenario we have to find a way to apply the transformation on the distributed data without exchanging it in clear. We propose to use secure computations based on Shamir-shared values as developed by Ben-Or et al. [START_REF] Ben-Or | Completeness theorems for non-cryptographic fault-tolerant distributed computation[END_REF].

In short, this allow us to share values among the p parties in a way that the knowledge of less than k < p/2 of the p shares does not reveal any information about the secret value. Yet these shares can be used to make computations (additions, multiplications etc.) on the secret values. After finishing the computations, we can put the shares of the result together and reconstruct it -whereas all input and intermediate values remain secret.

Thus -once we have shares of all necessary data (M {1,2} , b {1,2} , c, P , Q, S, A, r) -we can use secure computations to perform the transformation. We still have to find a way to assembly the data (M {1,2} , b {1,2} , c) and a way to jointly choose the random values (P , Q, S, A, r).

The assembly of the data depends on the initial partitioning in the problem. However -as long as each value is clearly "owned" by one party (which is usually the case) -the assembly is not a problem: Each party shares its values and the matrices and vectors are filled with the shares 10 .

The choice of the random matrices and vectors is more complicated. We have to guarantee the randomness and the correct form of the result, i.e. we have to make sure that Q is a monomial matrix, A a permutation matrix and that P is invertible. Moreover we need to ensure that no party knows the resulting values, because they would allow the parties to undo the transformation and access the secret data.

The basic idea is that each party randomly chooses its random values (i.e. party i chooses matrices P i , Q i , S i , A i and a vector r i ) and we combine them to have jointly and fairly chosen random values. Ideally, even the knowledge of p -1 of these p input values should not leak any information about the result.

To achieve this we rely on secure computations again. After each party has chosen its input, we calculate

P = p-1 i=0 P i , Q = p-1 i=0 Q i , S = p-1 i=0 S i , A = p-1
i=0 A i and r = p-1 i=0 r i . As these computations take place in a finite field, the result is random, and even knowing p -1 of the p input values does not reveal anything about the output.

An overview of the complete protocol:

1. Each party i chooses a random invertible matrix P i , a random positive monomial matrix Q i , a random positive diagonal Matrix S i , a random permutation Matrix A i and a random positive vector r i .

2. Each party i securely shares its parts of M 1 , M 2 , b 1 , b 2 and c as well as P i , Q i , S i , A i and r i .

3. Secure computation of P , Q, S, A and r as described above. Assembly of M 1 , M 2 , b 1 , b 2 and c. Transformation:

Calculation of M = P *   M 1 Q 0 M 2 Q A -S   , b = P *   b 1 + M 1 Qr b 2 + M 2 Qr -Sr   and c T s = c T * Q 0 . . . 0 .

Optimization: Fast Matrix Multiplication

Matrix multiplication is the key operation of our transformation as it is used in many places. When using secure computations on Shamir-shared values multiplications are expensive due to the overhead caused by the degreereducing step on the secret shares. Therefore we want to reduce this overhead as much as possible.

A naive implementation (see Algorithm 7.1) of the multiplication of a shared (m × k) matrix A and a (k × n) matrix B will result in a time complexity of O(mkn), a round complexity (i.e. the number of points in time when communication is necessary) of O(mkn) and a communications complexity (i.e. the number of messages exchanged) of O(mknp 2 ) as each degree-reducing step requires one round and O(p 2 ) messages [START_REF] Ben-Or | Completeness theorems for non-cryptographic fault-tolerant distributed computation[END_REF]. We will now describe how to reduce this to one round and O(mnp 2 ) messages.

The idea is to postpone the degree-reducing step as much as possible. If A x,y and B y,z are shares of a polynomial with degree k, then temp is of degree 2k, but, as adding two shares does not increase the degree of the polynomial, we can calculate C x,z = k-1 y=0 A x,y * B y,z without exceeding a degree of 2k. Thus we can postpone the degree-reducing step until the end of all calculations and execute it in parallel on the whole matrix to reduce round complexity to 1 and communication complexity to O(mnp 2 ) (see Algorithm 7.2 11 ). for z = 0 to n -1 do end for 9: end for 10: execute degree-reducing step on all m * n entries of C in parallel 8 Use Case: Supply Chain Optimization Supply Chain Optimization problems can easily be expressed as linear problems [START_REF] Stadler | Supply chain management and advanced planning[END_REF]. Each variable corresponds either to the number of units to produce at a certain factory at a certain time, to the inventory (per factory and time) or to transported units (between two factories). The constraints are flow constraints (e.g. "all produced units are either shipped to the next stage in the chain or remain in the inventory"), capacity constraints (e.g. "factory X can produce at most n units of product Y in period i") and demand constraints (e.g. "in period i exactly k units of product Z are sold to customers"). The cost function is composed of production costs (per produced unit), shipping costs (price of shipping one unit from factory X to factory Y ) and inventory costs (the price of stocking products or intermediate components at a factory).

This means that variable is "owned" either by one company (for production an inventory variables) or by two companies (for transport variables). Hence we have a simple structure which allows us to easily set up the distributed linear program as discussed above. Furthermore, most of the constraints (the flow and demand constraints) are expressed as equations, which is convenient for our transformation.

Experimental Results

To analyze the practical performance of our approach in Supply Chain Management, we implemented a prototype. Each party is simulated by a separate Java thread which communicates using the network interface. The experiments were conducted on an 8 core AMD Opteron 1800 machine with 16 GB RAM running under Linux (SuSE Enterprise Server 11 64 bit). This setup is reasonably realistic as each thread runs on a separate core and has roughly as much computational power available as if it was running alone on a standard office PC.

The test data we used is a sample supply chain structure with five companies. To scale the size of the problem, this optimization was done for different numbers of planning periods which increases the number of variables and constraints. The measured timings include sharing of the values, performing the transformation, reconstructing the transformed LP, solving it using a standard LP solver 12 and back-transforming the solution using secure computation again. The results (see Figure 8.1) are promising: The standard test case (six periods: 180 constraints, 282 variables) is solved in approximately 25 minutes (which are nearly entirely due to the secure computation for applying the transformation, solving the transformed LP in clear takes just a few seconds) and even the bigger test cases are completed within two hours. This is sufficiently fast for practical usage and much quicker than the distributed Simplex algorithms.

We also calculated the numerical values for the a-posteriori probabilities of a right guess in the six-period case for a uniform input distribution based on the bounds established in Section 6 and Eq. 19:

• cost function c: P R posteriori ≤ 3.76 • 10 -220

• values x: P R posteriori ≤ 2.30 • 10 -1409

As explained above, there is no easily calculable bound on the leakage of the constraints, but the chances of guessing P only based on A are less than 2.34 • 10 -746370 .

Conclusion

In this paper we proposed a disguising transformation for linear programs. We proved correctness and analyzed security in the framework of leakage quantification by estimating the leakage of building blocks (permutation, scalar and matrix multiplication) and combining these results to establish bounds on the entire transformation. Subsequently we developed a secure multi-party protocol to make the transformation usable in a distributed case.

Based on this protocol we implemented a prototype for secure supply chain optimization. We conducted experiments which show significant performance gains compared to entirely distributed secure simplex algorithms.

Overall the proposed algorithm seems to be well-suited for the initial supply chain optimization problem as well as general outsourcing purposes. It is correct, fast and sufficiently secure for many applications.

Additionally, the basic ideas of the transformation can easily be extended and generalized to fit other problems as e.g. systems of linear equations. This underlines the power of disguising approaches.

Future Work

We have thought of several extensions to the transformations which can enhance security. Possibilities include splitting variables or creating fake variables in order to protect c. These measures have to be checked for their security as well as their impact on performance.

Furthermore the numerical stability of the transformation should be examined. During our experiments a standard LP-Solver was always able to find the correct solution, however rounding errors and performance deterioration could be observed from time to time. This also is of interest as numerical effects could lead to attacks.

We conducted the performance measurements under ideal network conditions and ignored common problems such as latencies, failures or packet loss. For a comprehensive performance analysis they should be re-run under more realistic networks conditions. Nevertheless we stress that the competing approaches based on secure LP solvers were benchmarked under the same ideal conditions. Furthermore, our transformation has a quasi-constant (only depending on the number of parties) round and small communication complexity compared to these approaches. Therefore it can be expected that our relative performance advantage will even further increase.

The security analysis should also be refined in some parts. In particular the interconnections between the different parts of the transformation should be examined more precisely as this is one of the most probable entrance point for attacks. Additionally it would be desirable to refine the bounds on the leakage of combined channels (i.e. to show that for example the combination of a multiplication and a permutation is strictly better than the best of them alone) and give -if possible -a closed-form bound on the leakage of a matrix multiplication.

As our security analysis currently supposes a Honest-but-Curious-Scenario, it could also be extended to analyze the possible influence of malicious participants with byzantine behavior (i.e. participants that give wrong input data or do not follow the protocol) on the results, in particular in the case of distributed supply chain management.

A Leakage of Combined Channels

We use the following definitions and theorems by Wibmer et al.

5 P

 5 and with M = P * M and b = P * b we have min c T s z s.t. M z s = b z s ≥ 0

Figure 2 :

 2 Figure 2: Leakage of a matrix multiplication channel M k,n,l

Figure 3 :

 3 Figure 3: Leakage of a matrix multiplication channel M k,n,l

6. 3 . 3

 33 Leakage of the Constraints (M 1 , M 2 , b 1 and b 2 )

Figure 5 :

 5 Figure 5: An overview of a possible attack

4 5 .b z s ≥ 0 6 .

 56 . c T s , M and b are reconstructed from the shares and passed into the cloud. The Cloud solves the Linear Program min c T s z s s.t. M z s = Secure sharing of the solutions z 7. Secure distributed computing of x = Q(z -r) 8. Output of values of x to their respective owner.

Algorithm 7 . 1

 71 Matrix Multiplication C = A * B, naive 1: for x = 0 to m -1 do 2:

for y = 0 to k -1 do 5 : 6 : 2 2 : 3 :← 0 4 : 5 :

 5622345 temp ← A x,y * B y,z execute degree-reducing step on temp 7: sum ← sum + temp Matrix Multiplication C = A * B, optimized communication 1: for x = 0 to m -1 do for z = 0 to n -1 do sum for y = 0 to k -1 do sum ← sum + A x,y * B y,z

Figure 6 :

 6 Figure 6: Performance in Distributed Supply Chain Management Case

1 -→ Y and Y C 2 - 1 -→ Y and Y C 2 -Theorem 5 (

 12125 [START_REF] Wibmer | Leakage Quantification of Cryptographic Protocols[END_REF]:Definition 3 (Independent Channels). Two channels X C -→ Y and X C -→ Y are independent if C|x is independent from C |x for every x ∈ X and x ∈ X .Definition 4 (Composition of Channels). Let X C → Z be two channels. Then we can define the composition channel XC 2 •C 1 ---→ Z by (C 2 • C 1 |x)(ω) = (C 2 |(C 1 |x)(ω))(ω)for every x ∈ X and ω ∈ Ω (the event space).Theorem 4 (Leakage of a Composition). Let X C → Z be two independent channels. ThenL × (C 2 • C 1 ) ≤ min{L × (C 1 ), L × (C 2 )} Definition 5 (Direct Product of Channels). Let X C -→ Y and X C -→ Y be two channels. Then we can define the direct product channel X × X C×C ---→ Y × Y by (C × C )(x, x ) = (C|x, C |x ) for x ∈ X and x ∈ X . Leakage of a Direct Product). Let X C -→ Y and X C -→ Y be two independent channels. Then L × (C × C ) = L × (C) • L × (C ) Definition 6 (Product of Channels). Let X C -→ Y and X C -→ Y be two channels. Then we can define the direct product channel X C•C --→ Y × Y by (C • C )|x = (C|x, C |x) for x ∈ X .Theorem 6 (Leakage of a Product). Let X C -→ Y and X C -→ Y be two independent channels. Then max L × (C), L × (C ) ≤ L × (C • C ) ≤ L × (C)L × (C )

A slack-variable is used to express inequality constraints as equality constraints. The idea is to introduce an additional variable for each constraint which takes up the "remainder" or "slack". For example, instead of 3x1 ≤ 10 we can write 3x1 + s1 = 10 for s1 ≥ 0.

A (n × n)-matrix A is called nonsingular if there exists another (n × n)-matrix B so that AB = BA = I where I is the identity matrix of dimension (n × n).

Braun et al. [5] call this value the Multiplicative Leakage. The interesting point is the maximum of this value over all X, which we will call Multiplicative Leakage.

Here we assume only positive values, but the result remains correct for negative values too. In fact, it works for any n + 1 distinguishable symbols.

This strangely looking choice reduces the leakage and allows us to give a simple closedform bound. It can be difficult to implement in practice; a simpler alternative would be to choose the fi-s uniformly which slightly increases the leakage.

This corresponds to M k,n,l with inverted roles: P is now the input to hide and M the randomness. We use this channel in the security analysis of P later on.

Another option is that each party shares -e.g. for the cost vector c -a vector ci where all values that are not owned by itself are set to zero. Then all parties calculate c = p-1 i=0 ci using secure computations which merges the data.

This algorithm is somewhat similar to the inner product algorithm of Catrina and de Hoogh[START_REF] Catrina | Secure multiparty linear programming using fixed-point arithmetic[END_REF], but generalized to a complete matrix multiplication.

We used LP Solve which is licensed under LGPL and available at http://lpsolve.sourceforge.net/


Patrick Lacharme
email: patrick.lacharme@ensicaen.frchristophe.rosenberger@ensicaen.fr

Christophe Rosenberger

Synchronous One Time Biometrics With Pattern Based Authentication

Keywords: Authentication, BioHashing, behavioral biometrics

One time passwords are commonly used for authentication purposes in electronic transactions. Nevertheless, providing such a one time password is not really a strong authentication proof because the token generating the passwords can be given by an impostor. In order to cope with this problem, biometric recognition is more and more employed. Even if biometric data are strongly linked with the user, their revocability nor diversity is possible, without an adapted postprocessing. Biometric template protection schemes, including the BioHashing algorithm, are used to manage the underlying privacy and security issues. These schemes are used for the protection of several biometric modalities, but are not necessary adapted for all of them. In this paper, we propose a new protocol combining protected biometric data and a classical synchronous one time password to enhance the security of user authentication while preserving usability and privacy. Behavioral biometrics is used to provide a fast and a usable solution for users. We show through experimental results the efficiency of the proposed method.

I. INTRODUCTION

User authentication with mobile device is more and more envisaged for applications on the Internet and electronic transactions. One Time Password (OTP) is a popular solution for user authentication applications. In 2011, the total revenue of such solutions was estimated to 770 millions dollars [START_REF] Martinez | An overview and competitive analysis of the one-time password (otp) market[END_REF]. The classical form factor is a physical token but more and more OTP are provided as a software application on mobile devices and are asynchronous (based on the use of a challenge). Even if this solution is secure and usable, it does not constitute a strong identity proof as anybody finding the OTP token could use it. In order to solve this problem, biometrics is more and more used to increase the level of confidence of user authentication. Nevertheless, a static biometric authentication possesses the same vulnerabilities than a standard static authentication if the exchanged data are eavesdropped and replayed. Moreover, biometric data are sensitive and require a particular attention in terms of security and privacy. Biometric data protection should be realized during all the life cycle of the data including the storage and the handling. A biometric authentication is realized in two steps : the enrollment and the verification phases, where a query biometric template is compared to the reference one. Standard cryptography as symmetric encryption (or hash functions) does not ensure the data protection during the comparison step because two biometric data from the same individual are not exactly identical and, consequently, the comparison can not be realized on the encrypted domain. Several ways are proposed to achieve the protection of biometric data, including adapted cryptographic schemes (fuzzy commitment, homomorphic encryption) and feature transformations (including the Biohashing algorithm). All these schemes should ensure security, diversity and revocability of the biometric data. The objective of this paper is not to propose a new scheme for biometric template protection. For more details on these schemes, we refer the reader to the detailed survey [START_REF] Rathgeb | A survey on biometric cryptosystems and cancelable biometrics[END_REF].

The first contribution of this paper is to propose a generalization of the synchronous one time passwords by adding a biometric feature protected by a biometric template protection scheme. A patent in 2007 [START_REF] Fouquet | Time synchronous biometric authentication[END_REF] proposed to define a preliminary version of synchronous one time biometrics while protecting the biometric data with a classical encryption scheme. This approach has an important drawback because the matching of biometric templates requires a decryption that is a very sensitive step. We extend in this paper this solution through the feature transformation of biometric template. Second, we use for the first time to our knowledge a specific biometric modality with the Biohashing algorithm: biometric pattern drawn on a touch screen. This solution has the advantage to be very simple to use and very quick. Experiments are carried out on a home made benchmark dataset composed of 34 users with 15 samples for each and show the benefit of the proposed solution. This paper is organized as follows. Section 2 provides a presentation of feature transformation template protection schemes, with a description of the Biohashing algorithm. The computation of biometric features from pattern drawing is described in Section 3. Section 4 presents the proposed solution to compute the synchronous one time biometrics. Section 5 illustrates through experimental results the benefit of the proposed solution. Finally, we conclude and give some perspectives in section 6.

II. FEATURE TRANSFORMATION AND BIOHASHING

A feature transformation is a function F using a key K (that is typically a random seed or a password), applied to a biometric template T . The transformed template F K (T ) is stored in a database or in a personal device. The Biohashing algorithm, described below, belongs to this class of transformation. During the authentication step, the same transformation is applied to the query template T with the same key K and a comparison is realized between F K (T ) and F K (T ). It is generally considered that, given the transformed template F K (T ) and the key K, it is possible to recover the original template T (or a close approximation) as presented in [START_REF] Nagar | Biometric template transformation: A security analysis[END_REF]. Thus it is preferable to store this key in a second support, even if the reconstruction of the original template depends strongly to the used biometric modality. The performance of the authentication system is generally estimated with FMR (False Match Rate computing the ratio of false negative verification) FNMR (False Non Match Rate calculating the ratio of false positive verification) rates and the feature transformation should not decline the performance of the system. In fact, this approach tends to improve the performance of the biometric system without any protection (but a the key K is necessary).

The Biohashing algorithm is applied to biometric templates, represented by real-valued vector of fixed length (the metric used to evaluate the similarity between two biometric features is the Euclidean distance) and generates binary templates of length lower or equal to the original length (the metric used to evaluate the similarity between two transformed templates is the Hamming distance). This algorithm has been originally proposed for face and fingerprints by Teoh et al. in [START_REF] Teoh | Biohashing: two factor authentication featuring fingerprint data and tokenised random number[END_REF], where the fingerprint features are, in a first time, transformed in a real-values vector of fixed length, called Fingercode (this step is not useful and not described in this paper). The Biohashing algorithm is applied, in a second time, on this fingercode and generates a binary template called BioCode. At the end of the enrollement phase, the fingercode is discarded and the BioCode (with the associated seed) is stored. The biohashing algorithm can be applied on any biometric modalities, that can be represented by a real values vector of fixed length.

The Biohashing algorithm transforms the biometric template T = (T 1 , . . . T n ) in a binary template B = (B 1 , . . . B m ), with m ≤ n, as following (see Figure 1) :

1) m pseudorandom orthonormal vectors V 1 , . . . , V m of
length n are generated from the random seed (typically with the Gram Schmidt algorithm). 2) For i = 1, . . . , m, compute the scalar product x i =< T, V i >. 3) Compute the binary template B = (B 1 , . . . , B m ) with the quantization process:

B i = 0 if x i < τ 1 if x i ≥ τ,
where τ is a given threshold, generally equal to 0.

The performance of this algorithm is ensured by the scalar products with the orthonormal vectors, as detailed in [START_REF] Teoh | Cancellable biometrics and annotations on biohash[END_REF]. The quantization process of the last step ensures the non-invertibility of the data (even if n = m, because each coordinate of the input T is a real value, whereas the coordinates of the output B is a single bit). Finally, the random seed guarantees the diversity and revocability properties. We present in the next section the biometric modality we use as input of the Biohashing algorithm.

III. BIOMETRIC PATTERN BASED AUTHENTICATION

In the literature, biometric based mobile authentication is an emerging issue, with relatively few references. The NIST report [START_REF] Orandi | Mobile id device. best practice recommendation[END_REF] details some recommendations concerning portable biometric acquisition station and considers the following modalities: fingerprint, face and iris. Most of papers are devoted to a particular modality. We can mention the references [START_REF] Kounoudes | Combined speech recognition and speaker verification over the fixed and mobile telephone networks[END_REF] and more recently [START_REF] Roy | A fast partsbased approach to speaker verification using boosted slice classifiers[END_REF] focused on speaker verification for mobile devices. The first deals with textdependent speaker verification, while the latter proposes a new method to extract features from speech spectra called slice features.

Face recognition is dealt with in the paper [START_REF] Hadid | Face and eye detection for person authentication in mobile phones[END_REF], along with eye detection, or in [START_REF] Choi | Realtime training on mobile devices for face recognition applications[END_REF], where a real time training algorithm is developed for mobile devices. The authors propose to extract local face features using some local random bases and then to incrementally train a neural network. Image processing also concerns hand biometrics on mobile as in the reference [START_REF] De Santos-Sierra | Hand Biometrics in Mobile Devices[END_REF], where hand images are acquired by a mobile device without any constraint in orientation, distance to camera or illumination. The author of [START_REF] Kang | Mobile iris recognition systems: An emerging biometric technology[END_REF] details an iris recognition system, based on a three-step pre-processing method relying on (a) automatic segmentation for pupil region, (b) helper data extraction and pupil detection and (c) eyelids detection and feature matching.

Apart from the literature dedicated to biometric solutions for mobile authentication related to a specific modality, some papers propose an overview on the underlying topic. We can mention the recent paper [START_REF] Wang | Biometrics on Mobile Phone[END_REF]. The authors focus on biometrics on mobile phone through some standard modalities (fingerprint, speaker recognition, iris recognition, gait) and propose a new application to ECG measurement and remote telecardiology, with an extra portable heart monitoring device. Some recent papers [START_REF] Clarke | Advanced user authentication for mobile devices[END_REF], [START_REF] Hwang | Keystroke dynamics-based authentication for mobile devices[END_REF], and [START_REF] Changa | A graphical-based password keystroke dynamic authentication system for touch screen handheld mobile devices[END_REF] deal with keystroke dynamics based recognition. The first paper makes a study about user identification using keystroke dynamics-based authentication (KDA) on mobile devices, relying on 11-digit telephone numbers and text messages as well as 4-digit PINs to classify users. The second develops a more efficient KDA process, with optimized enrollment and verification steps, whose principle is extended in the latter paper for touch screen handled mobile devices, along with a pressure feature measurement. Many recent papers propose to use touch screen to capture biometric data [START_REF] Sae-Bae | Investigating multitouch gestures as a novel biometric modality[END_REF]. Most of these studies use methods used for keystroke or signature dynamics. As for example, the notion of TapPrint has been proposed by Miluzzo et al. [START_REF] Miluzzo | Tapprints: your finger taps have fingerprints[END_REF] where the concept of keystroke dynamics is generalized to touch screen. The proposed method is based on the location of the tap on the key associated to a letter or by analyzing gyroscope information. The system has been tested on 10 volunteers with a total number of 40000 taps. The recognition efficiency is between 80% and 90%. The work done by Luca et al. [START_REF] Luca | Touch me once and i know it's you!: implicit authentication based on touch screen patterns[END_REF] is very interesting because it combines pattern based password and biometrics. They proposed a system and test it with 34 users. They obtained a performance of 19% for the FRR value (False Rejection Rate) and 21% for the FAR (False Acceptance Rate). A method in 2013 has been proposed [START_REF] Beton | Biometric secret path for mobile user authentication: A preliminary study[END_REF] combining multiple information compared with the Pearson Correlation and the Dynamic Time warping (DTW) methods. The equal error rate (EER) is near 17% which the best result for this biometric modality. We can see that many works have been done to propose biometric systems for user authentication on mobile devices. Most of solutions used classical modalities (such as fingerprint or face) implemented on a mobile device. The user experience is in general not good and not very well fitted for a mobile device.

The biometric system we propose to use in this work intends to increase security for a quick logical access control to the mobile device. It is composed of a two factor approach. We intend to first recognize the user by the knowledge of a password represented by a pattern. We use the classical Android unlock screen approach (see Figure 2). This approach to enter a password is quicker and is more usable for a mobile device. Second, the behavior of the user while drawing the pattern is analyzed. Many information are collected during the capture process:

• X position: the X position of the finger on the touch As the time needed to draw the same pattern can be different for each capture, signals are undersampled to a fixed length.

A constant size description is necessary to use this template as input in the BioHashing algorithm.

IV. SYNCHRONOUS ONE TIME BIOMETRICS

A. Description of the solution

The proposed method combines biometric data acquired with the previous biometric system and a classical synchronous one time password. A biometric feature transformation is used for the protection of the biometric template and the generation of dynamic BioCodes (to avoid the replay attack). In the rest of this section, we use the Biohashing terminology for the feature transformation for simplicity and without loss of generality. Like all biometric systems, two steps are necessary to be defined: enrollment and verification.

The enrollment step for the user consists in generating a Reference BioCode given its behavior when drawing a chosen pattern (biometric data) and the pattern code (that is considered as the seed value of the BioHashing algorithm). This Reference BioCode is sent to the service provider (bank, identity provider. . . ). The user obtains from the service provider a synchronous OTP (as a software application on the mobile device). This OTP is personalized for the user The verification step (described in Figure 3 consists in computing in the user side the Capture BioCode from the biometric template and the pattern code as a seed with the Biohashing algorithm. The Biohashing algorithm is applied once more with the Capture BioCode as input and the OTP value at the considered event (time or counter) to generate the Dynamic Capture BioCode. On the service provider side, the Reference BioCode (stored during the enrollment step) is combined with the OTP related to the user with the BioHashing algorithm in order to generate the Dynamic Reference BioCode. The Hamming distance between the Dynamic Reference BioCode and the the Dynamic Capture BioCode allows the service provider to decide if the user is authenticated or not.

B. Discussion

The proposed method meets many requirements:

• Usability: it is very easy and quick for a client to provide an identity proof within the proposed method. Moreover, it is possible to use the same pattern for several service provider by concatenating the pattern code with a number related to the service provider as for example during the generation of the Reference BioCode.

• Security: the client send its identity proof to the service provider through the Dynamic Capture BioCode. As we use an OTP as seed in the BioHashing algorithm, the replay attack is not anymore possible. Note that this identity proof could be verified a posteriori given the value of the OTP, this aspect guarantees non repudiation. • Revocability : is possible for a client to revoke its biometric data by changing its pattern. • Linkability : the use of an OTP generator permits to generate dynamic BioCodes to avoid linkability attacks (given different BioCodes). Previous studies have shown that the mutual information of BioCodes generated from the same template and different seeds is low and cannot be used to link identities [START_REF] Belguechi | How to evaluate transformation based cancelable biometric systems?[END_REF]. • Non-invertibility : it is not possible to recover the biometric raw data (given different BioCodes) as the BioHashing is non invertible function if the seed is unknown. The non-invertibility is ensured even if the pattern data is known by an attacker (as long as the OTP generator is secure).

V. EXPERIMENTAL RESULTS

We define in this section experimental results for the validation of the proposed method.

A. Protocol

We detail the protocol we followed in this study.

1) Biometric data:

In this work, we used a biometric dataset of data captured when users draw a single pattern:

• Data have been collected on a Nexus 7 mobile phone with Android 4.4.2 with a touch screen having a resolution of 800 x 1280 pixels. We developed an Android application to collect data mentioned in the paper, • The pattern was the same for all users and is defined by the following pattern code "1235987". This experimental setup can be considered as the worst case where an attacker knows the pattern to draw. 2) BioHashing parameters: Considering the BioHashing setup, we set the parameter values as following (when using notations defined in Section 2):

• Template size: n=1000, • BioCode size: m=750 for the Reference BioCode and Capture BioCode and m=512 for Dynamic Reference BioCode and Dynamic Capture BioCode, • As the pattern is the same for all users, in the computation of the Reference BioCode, the pattern code is set to "1235987" for all users, • Matching algorithm: Hamming distance.

3) Performance analysis:

In order to evaluate the performance of the proposed method, we use the following methodology:

• We use the first sample of each user as reference template, the Reference BioCode is computed from this biometric data, • We run a simulation with 1000 generations of OTP, • For each OTP generation, we choose randomly one of the 14 left samples of the user to simulate a legitimate verification. We compare the Dynamic Reference BioCode and Dynamic Capture BioCode to generate an intraclass score. We obtain 1000 × 34 = 34, 000 intraclass scores, • We have a similar process to simulate impostor attack by choosing a biometric sample from another user and we obtain at the end the same number of interclass scores, • Given these two sets of scores, we can compute their distribution in order to estimate in which measure impostor scores are different than legitimate ones. Second, we compute the Equal Error Rate (EER) value that is a well known metric in biometrics that measures the behavior of the biometric system when the decision threshold is set to have the same number of false rejected users and false accepted ones.

B. Results

Figure 5 presents the distribution of scores we obtained using this biometric dataset (genuine or intraclass scores are represented in red, impostor or interclass ones in blue). This figure shows clearly that the two distributions are separated without any overlapping. For the 34.000 intraclass scores, the maximal value is 0.29 meaning that in the worst case, 29% of the bits were different between the Dynamic Reference BioCode and Dynamic Capture BioCode. By looking at this curve, we can expect on this database to have no recognition error that is confirmed by the EER value that equals 0% (without the BioHashing, the touch screen verification performance is estimated to 15%). This is an excellent result considering we use a behavioral biometric modality. The use of the BioHashing algorithm is known to increase the performance of biometric system (if the seed is unknown). This shows the benefit of the proposed method even when the pattern is the same for each user (and the usability of the authentication system).

VI. CONCLUSION AND PERSPECTIVES

The proposed solution permits to generalize the concept of synchronous one time passwords with the use of biometric data. We showed in this paper that the biometric modality can be not only a fingerprint but also a behavioral approach without loosing performance. We believe this solution can be very usable for clients and could be used in many applications. The feature transformation combined with the OTP ensures the security of the biometric data. Moreover, the possibility of reverse or approximate the used biometric data, if the seed is known, is not clear in the case of our pattern and the advantage of an attacker with such approximation would be relatively modest in terms of user's privacy. Indeed, by definition, the behavior when drawing a pattern on a touch screen can be easily revoked by changing the pattern. As perspectives, we intend to generalize the proposed concept to multi-biometrics. We also would like to use this approach for continuous authentication schemes by providing dynamic BioCodes as identity proof.

Figure 1 .

 1 Figure 1. General principle of the BioHashing algorithm

Figure 2 .

 2 Figure 2. Classical Android unlock screen

Figure 4 .

 4 Figure 4. Pattern drawing biometric features

  • 34 users participated to this experiment, • Each user provided 15 samples described by 5 signals undersampled to 200 values (time normalization). Figure 4 presents the data of the first sample for user 1. The x-axis corresponds to the time and the y-axis to feature value. So, the template size is 1000 (by concatenating all undersampled signals), In total, we have a subset of 34 × 15 = 510 biometric templates of size 1000 real values.

Figure 3 .

 3 Figure 3. General principle of synchronous one time biometrics (with Biohashing)

Figure 5 .

 5 Figure 5. Distribution of scores for 1000 generations of OTP.


Z Yao

C Charrier

J M Le Bars

C Rosenberger
email: christophe.rosenberger@ensicaen.fr

Pixel Pruning for Fingerprint Quality Assessment

I. INTRODUCTION

Fingerprint quality assessment (FQA) works as a toll-gate to ensure that poor quality samples are rejected before sending them to next stage. This is very important to guarantee the performance of a biometric system [START_REF] Grother | Performance of biometric quality measures[END_REF], especially during the enrollment step. Therefore, this problem has attracted attentions from both academic and industrial areas, and a lot of studies had been made. Prior studies in estimating fingerprint quality could be classified into several categories:

1) Assessment approaches that rely on segmentation tasks, which could be either implemented by dividing the foreground area into several classes [START_REF] Bolle | System and method for determining the quality of fingerprint images[END_REF], [START_REF] Shen | Quality measures of fingerprint images[END_REF], [START_REF] Lee | A novel measure of fingerprint image quality using the Fourier spectrum[END_REF] or carried out via an approximation of the informative regions by using minutiae template only [START_REF] Yao | Quality assessment of fingerprints with minutiae delaunay triangulation[END_REF], 2) Quality indexes represented by a single feature [START_REF] Lee | A novel measure of fingerprint image quality using the Fourier spectrum[END_REF], [START_REF] Chen | Fingerprint quality indices for predicting authentication performance[END_REF],

which can be indicated by either the feature itself or an observed regularity of the employed feature [START_REF] Lee | Fingerprint-quality index using gradient components[END_REF], 3) Solutions carried out by using multi-feature fusion, which can be achieved via a linear fusion or classification and both of them might involve in a priorknowledge of matching performance [START_REF] Abed | Fingerprint quality assessment using a no-reference image quality metric[END_REF], [START_REF] Tabassi | NIST fingerprint image quality[END_REF].

In addition, studies proposed in recent years have made attempt by learning [START_REF] Olsen | Gabor filters as candidate quality measure for NFIQ 2.0[END_REF] a multi-layer neural network. The quality feature in [START_REF] Olsen | Gabor filters as candidate quality measure for NFIQ 2.0[END_REF] is also indicated by a regularity of a histogram obtained from the best-matching unit assigned to fingerprint block. Likewise, the quality index is also involved in a classification that relies on a prior-knowledge of genuine matching scores. In this paper, we propose a new metric based on pixel pruning. We show its benefit using the Enrollment Selection (ES) approach on different databases.

II. QUALITY ASSESSMENT FRAMEWORK

As the specialty of the biometric application, fingerprint quality is not only a problem of image distortion determination. The purpose of FQA is to guarantee the reliability of the feature extracted from the image and hence benefits the matching performance. In this case, segmentation is initially a choice to determine the useful and reliable area of the ridge-valley pattern, which somehow indicates fingerprint's availability in a quantitative manner [START_REF] Yao | Quality assessment of fingerprints with minutiae delaunay triangulation[END_REF].

A. Feature given by Morphology Segmentation

The first step of the proposed framework is to obtain a measure of fingerprint foreground area as we have just mentioned before. To do this, a coarse segmentation is adopted in this study, which is achieved via morphological processing of images. Such a processing mainly consists of two tasks: dilation and erosion. Fingerprint image is composed by parallel run ridge-valley pattern with relatively stable frequency. With this property, it is able to connect the edges formed by the ridge-valley pattern (see Figure 1). Four images in Figure 1 illustrate a morphology processing of a fingerprint image with several iterations, where image 1(a) is the original fingerprint pattern, 1(b) is the image after erosion processing(s), 1(c) is the enhanced version of image 1(b), and 1(d) is the segmented mask. In this study, we use the approach in [START_REF]Fingerprint enhancement using STFT analysis[END_REF] to perform the first coarse segmentation. The first feature for indicating fingerprint quality is hence a pixel ratio of the foreground area to the entire image.

B. Pixel-pruning based on Coherence

In this task, we propose a pixel-pruning approach by using an existing feature of oriented pattern namely coherence [START_REF] Bazen | Systematic methods for the computation of the directional fields and singular points of fingerprints[END_REF]. The coherence is initially applied onto directional field estimation of oriented patterns and has been used as one of the features [START_REF] Bazen | Systematic methods for the computation of the directional fields and singular points of fingerprints[END_REF] for classification-based fingerprint segmentation approaches. The feature is to indicate the uniformity of the foreground gradients. In our experiments, we found that this feature is sensitive to the variation of the ridge-valley direction in a local area. Because of this, in this study, we customize an approach by using this feature to extensively remove foreground pixels in a local region where the directional information of the ridge-valley pattern changes abruptly. The definition of the coherence is given by gradient measures of pixel intensity. In a local window W , it is defined by:

Coh = (G xx -G yy ) 2 + 4G 2 xy G xx + G yy (1)
where In Figure 2, image 2(b) is the coherence image calculated from the original fingerprint illustrate by 2(a), while image 2(c) is the region mask obtained by using our pixel-pruning method which is carried out via a thresholding operation to the coherence image.

G xx = W G 2 x , G yy = W G 2 y , G xy = W G x G y and (G x , G y ) is the local gradient.
In our study, the coherence image is first normalized into [0,1], and then divided into non-overlapped blocks which is followed by thresholding operations with a baseline value of 0.5. The block size is 16 in this study, and both the block size and the threshold are all empirical values in our study. Finally, the quality feature is also a ratio of the light pixels number to the pixel number of the entire image.

C. Metric Generation

The proposed framework of fingerprint quality assessment is essentially implemented by fusing two (or more) features in the segmentation phase, i.e. the binary images of mask obtained in the segmentation stage and pixel-pruning session would be combined together. Considering score-based fusion in biometrics [START_REF] Jain | Score normalization in multimodal biometric systems[END_REF], one can observe that there are several ways to achieve fusion task such as 'min' and 'max' rules. In the proposed framework, we simply use the logical 'and' rule to fuse two binary mask images, which is actually equivalent to fusing two features (obtained by two steps) in terms of the 'add' rule. An example of such a fusion is given in Figure 3. In Figure 3, one can note that the morphology approach is to coarsely generate an entire foreground area, where the pixelpruning approach is used for removing pixels in terms of the mean value of coherence at block-wise. The pruning task is particularly effective for bad quality images that contain some abrupt changes of the direction of the ridge-valley flow.

III. EVALUATION

The validation approach adopted in this study is based on the Enrollment Selection (ES) approach defined in [START_REF] Yao | Utility validation of a new fingerprint quality metric[END_REF], [START_REF] Yao | A literature review of fingerprint quality assessment and its evaluation[END_REF]. The ES measures a quality metric via a statistically computed global EER value, indicating the contribution of the quality metric in reducing the overall error rate. Figure 4(a) shows a typical dataset with different samples for may individuals. In order to quantify the performance of biometric system, we have to choose the sample to be used as reference. For each individual, this choice can be done by taking account the worst sample (associated to the lowest performance), the best sample (minimizing the global EER). Given a FQA metric, one can make the choice of the reference sample. We can plot the ROC curve by making all the choices for the reference samples. Figure 4(b) presents a typical result where in this case, the Metric 1 outperforms Metric 2 as it allows a global better performance. We used this validation approach with NFIQ as reference FQA metric.

In the experiments, we use several different datasets to perform the evaluation of the proposed FQA metric. Five of Fingerprint Verification Competition (FVC) [START_REF] Maio | Fvc2004: Third fingerprint verification competition[END_REF] database (Set A) are adopted, including FVC2000DB2, FVC2002DB2, and three of FVC2004 datasets. Each of the FVC datasets includes 100 individuals and 8 samples per individual, 800 images in total. The detail of each dataset is given in table I.

DB

Sensor Dim.

Resolution 00DB2A Low-cost Capacitive 256×364 500dpi 02DB2A Optical 296×560 569dpi 04DB1A Optical 640×480 500dpi 04DB2A Optical 328×364 500dpi 04DB3A Thermal 300×480 512dpi
The image size of each dataset is different from one another and the resolution is over 500-dpi. A glance of the datasets are given by several samples in Figure 5. In Figure 6 (a), when NBIS matcher is involved, MSEG (red plot) respectively generates 16.54% and 14.05% on 04DB1 and 04DB2 which are relatively bad results in comparison with the reference metric (blue plot), while MSEG shows better results on the other 3 datasets. On the other hand, MSEG (Figure 6 (b)) performs relative bad on 02DB2 only and better on the other 4 datasets when a vendorfree matcher (SDK) is used. This is due to the difference of the matching performance between the two algorithms. In addition, the NFIQ is involved in a prior-knowledge of matching performance, which could more probably result in a different evaluation result. The global EERs of MSEG and NFIQ obtained from 02DB2 are 0.2% and 0.12%, respectively. The global EERs obtained by sample utility [START_REF] Yao | Utility validation of a new fingerprint quality metric[END_REF] are plotted via green points in each figure. The sample utility is simply an approximation of the groundtruth (with respect to the employed matcher) of the original sample. The utility-based global EERs are illustrated as a reference, indicating how much the quality metric is close to the best case that one matching algorithm can obtain from a trial dataset. The CIs given in table II are also consistent with these global EERs, indicating the validity of the proposed MSEG. Meanwhile, the experimental result also shows that the MSEG is commonly available for multiple image specifications, at least the employed image types.

IV. CONCLUSION

We presented a new FQA metric based on pixel pruning. We used the ES validation approach as objective and operational approach. The proposed metric shows a good behavior when compared to NFIQ.

Fig. 1 .

 1 Fig. 1. Example of segmentation with morphology operation.

  Figure 2 illustrates an example of the pixel-pruning result of a fingerprint image.

Fig. 2 .

 2 Fig. 2. Example of segmentation with Coherence.

Fig. 3 .

 3 Fig. 3. Example of segmentation with Coherence

Fig. 4 .

 4 Fig. 4. Explanation of the ES validation approach

Fig. 6 .

 6 Fig. 6. Global EER plots. UtilityBoz and UtilitySDK in (a) and (b): global EER obtained with NBIS-based sample utility and SDK-based sample utility. Lower EER means better result.

TABLE II THE

 II 95% CI OF THE GLOBAL EER OF EACH METRIC.

	DB	QM	NFIQ	MSEG
	00DB2A (NBIS) [0.0490 0.0500] [0.0450 0.0461]
	02DB2A (NBIS) [0.1326 0.1340] [0.1068 0.1084]
	04DB1A (NBIS) [0.1540 0.1557] [0.1645 0.1662]
	04DB2A (NBIS) [0.1312 0.1334] [0.1396 0.1413]
	04DB3A (NBIS) [0.0745 0.0756] [0.0712 0.0723]
	00DB2A (SDK) [0.0022 0.0024] [0.0009 0.0011]
	02DB2A (SDK) [0.0011 0.0013] [0.0019 0.0021]
	04DB1A (SDK) [0.0266 0.0275] [0.0189 0.0196]
	04DB2A (SDK) [0.0384 0.0397] [0.0319 0.0328]
	04DB3A (SDK) [0.0189 0.0195] [0.0148 0.0153]