# «Ðîññèéñêàÿ àêàäåìèÿ íàóê ÑÀÍÊÒ-ÏÅÒÅÐÁÓÐÃÑÊÎÅ ÎÒÄÅËÅÍÈÅ ÌÀÒÅÌÀÒÈ×ÅÑÊÎÃÎ ÈÍÑÒÈÒÓÒÀ ÈÌÅÍÈ Â.À. ÑÒÅÊËÎÂÀ ÐÀÍ ÓÄÊ 510.6 ÃÐÍÒÈ 27.03.19 Èíâ. ...»

the “tighter” (i.e., the closer to S0 ) T is, the more chances this assumption has to be correct. Thus, even though there might be many dierent separators for a given pair of sets, a good separator is hard for the adversary to nd without knowing the set S0.

The protocol itself is the following sequence of steps.

(1) Bob selects a tuple (x1,..., x2m ) of random elements from either S0 or S1, with exactly m elements from S0 and exactly m elements from S1, and sends it to Alice.

(2) Alice checks, using her private test, for every i, whether for the element xi corresponding to xi, one has xi S0. If her test fails, Alice assumes that / xi S0 (equivalently, xi S0 ). Then she sends a tuple of m “1”s to Bob, in m 2 randomly selected places corresponding to xi S0. She gives no indication of / the results of her test for the remaining 3m places.

(3) Bob, who knows the right answer, simply compares it to Alice’s response and accepts or rejects authentication accordingly.

To prevent the adversary from guessing the right answer with non-negligible prob ability, several rounds of this protocol may be run (depending on what probability is accepted as “negligible”);

this is similar to the Feige-Fiat-Shamir scheme [1]. We note that if, say, m = 40, then the probability of guessing the right answer in a single session is less than 106.

To conclude this section, we make a couple of remarks.

Remark 1. The protocol in this section can also be used for encryption. Namely, if Bob wants to transmit an encrypted bit to Alice, he sends her a random element from S0 in case he wants to transmit a “0”, and a random element from S1 in case he wants to transmit a “1”.

As we have already pointed out in the Introduction, we do not pursue this direction here, and in particular, we do not make any claims concerning security of relevant encryption schemes.

2.1. Correctness of the protocol. The protocol is perfectly correct in the sense that if Alice is in possession of her private key and both parties follow all steps of the protocol, then Alice will be able to answer all Bob’s challenges correctly with probability 1, and Bob will then accept Alice’s authentication with probability 1. Even if the intersection T S1 is not empty and Alice’s test fails for some elements sent by Bob, this will not – 184 – aect Alice’s response because her response only includes places where her test did not fail.

Also, since Bob does not obtain from Alice any information that he does not already know, he can construct by a deterministic algorithm any true authentication session transcript, without interacting with Alice. Thus, the following is obvious:

Proposition 1. No information about the prover’s private key is leaked during any authentication session with an honest verier in the above authentication scheme, i.e., it is a “no-leak” proof system in the sense of Denition 2.

In Sections 5 and 6, we give two particular realizations of our meta-protocol just to illustrate the diversity of possible applications of our main idea. We emphasize once again though that we avoid detailed technical discussions (in particular, making quantitative statements) in this paper and keep the focus on theoretical aspects.

3. Questions and answers In this section, we answer some questions/concerns that a reader may have at this point;

these questions have actually been asked by some of our colleagues. We thought that arranging this material in the “FAQ format” after describing our meta-protocol would be more helpful to the reader than if we made it part of the Introduction.

Q. Do you prove that recovering the prover’s private key from her public key in any of your particular realizations is computationally infeasible? In particular, do you prove the existence of one-way functions?

A. No and no. Moreover, our focus in this paper is on leak (or lack thereof) of infor mation during authentication session, rather than on security of the prover’s public key construction.

Q. If not, then what is the novelty of your proposal?

A. The main novelty is that in our authentication scheme, a verier who follows the pro tocol cannot possibly obtain from the prover any information that he does not already know. This is also true for a passive adversary, even computationally unbounded one.

(Of course, a computationally unbounded adversary can usually nd correct responses to the verier’s challenges by using “brute force”, but this is a dierent story.) Q. In that case, what is the dierence between your protocol and the classical zero knowledge Graph Non-ISO protocol [5] where the prover convinces the verier that two given graphs are non-isomorphic by giving to the verier only the information that he already knows?

A. In the Graph Non-ISO protocol [5] the prover is assumed to be computationally unbounded (i.e., there is no “trapdoor”). Therefore, the Graph Non-ISO protocol cannot be used for authentication purposes in any meaningful scenario in real life.

Q. Well then, how about well-known zero-knowledge protocols with trapdoor, such as Graph ISO, or quadratic residuosity, or Feige-Fiat-Shamir scheme?

– 185 – A. None of these protocols is “no-leak”;

we think it is best illustrated by analyzing the Graph ISO protocol;

this is what we do in the next Section 4.

Q. What about a verier who does not follow the protocol? What if he just produces some random challenges? Can he obtain some information about the prover’s private key from her responses in that case?

A. The answer to this question may depend on a particular realization of our meta protocol;

more specically, on the size of the sets S0 and S1 relative to the size of the “universal” set S from which a “frivolous” verier can pick up his random challenges.

Typically, the sets S0 and S1 are negligible in S, which implies that if a frivolous verier picks his challenges randomly from S, he will get the “not in S0 ” response for every random element from S. Whether or not this can give him any information about S0 other than S0 is negligible in S, is not entirely clear, although the common sense suggests that it cannot. We do not make any claims to that eect in the present paper.

4. Why is the Graph ISO proof system not “no-leak”?

In this section, we try to resolve the confusion that stems from taking the “perfect zero-knowledge” euphemism too literally. To that end, we recall the well-known Graph ISO protocol from [4]. Here Alice is the prover and Bob the verier.

(1) Alice’s public key consists of two isomorphic graphs, 0 and 1. Alice’s private key is an isomorphism : 1 0. Alice is supposed to prove to Bob that is isomorphic to 1.

(2) To begin a session, Alice selects a random bit b, a random isomorphism :

b H, and sends the “commitment” graph H to Bob.

(3) Bob chooses a random bit c and sends it to Alice.

(4) Alice responds with an isomorphism : c H.

(5) Bob veries that is, indeed, an isomorphism.

Obviously, if the same graph H appears as commitment in two dierent sessions, and if the corresponding challenge bits c are dierent, then Bob, who gets isomorphisms 0 : 0 H and 1 : 1 H, can recover the isomorphism 0 1 between 1 and 0.

Therefore, after two sessions, Bob can obtain, with non-zero probability, information that he did not have before he started to interact with Alice. Thus, it is easy to see that the above proof system is not “no-leak” in the sense of Denition 2. Indeed, if interaction between Bob Alice produces a sequence of, say, just two transcripts with the same commitment graph H and dierent corresponding challenge bits c, then to reproduce this sequence with probability 1 by a deterministic algorithm, Bob would need a lot more than just 2 attempts.

At the same time, this proof system is “perfect zero-knowledge” in the sense of Denition 1 because Bob can obtain the same information with the same probability (but not with probability 1!) if he simulates the protocol by himself, without interacting with Alice. Specically, by selecting random isomorphisms : 0 H1 and : 1 H2, he may end up, with non-zero probability, with H1 = H2, hence recovering an isomorphism between 1 and 0.

– 186 – 5. A particular realization: subset sum In this section, we oer a particular realization of the meta-protocol from Section 2, exploiting the hardness of the subset sum problem, see e.g. [2]. We note that the com plexity of this particular problem was previously used in [7] in dierent cryptographic contexts, namely for constructing a pseudo-random generator and a universal one-way hash function.

The “universal” set S in this section is the set of all m-tuples of m-dimensional vectors over Q.

Alice’s private key is a set S0 = {a1,..., am } of m random linearly independent (over Q) m-dimensional vectors with integer coordinates, which is therefore a basis of Qm.

However, the vector a1 is special: the g.c.d. of its coordinates is even.

Alice’s public key includes the vector a1 and a set of k m random vectors c1,..., ck from the Z+ -span of S0.

Now we give a description of the authentication protocol. To simplify the notation, we give an exposition where Bob challenges Alice with just a single element rather than with a tuple of elements, as in the meta-protocol in Section 2.

(1) Bob selects, with equal probabilities (see our subsection 5.1 for details), ei ther a random vector c SpanZ+ (a1, c1,..., ck ) or a random vector c SpanZ+ ( 1 a1, c1,..., ck ) and sends the vector c to Alice;

in the latter case, Bob takes care that the coecient at 1 a1 is odd. Here SpanZ+ denotes the set of all linear combinations of given vectors with nonnegative integer coecients.

(2) Alice, using standard linear algebra, nds (rational) coordinates of c in the basis S0. If at least one of these coordinates is not a nonnegative integer, she knows that c SpanZ+ (a1, c1,..., ck );

therefore, she sends “1” to Bob. If all coordi / nates are nonnegative integers, Alice assumes that c SpanZ+ (a1, c1,..., ck ), and sends “0” to Bob.

(3) Bob, who knows the right answer, simply compares it to Alice’s response and accepts or rejects authentication accordingly.

We note that there is a negligible probability for Bob to reject a legitimate Alice because it may happen that all coordinates of c in the basis S0 are nonnegative integers, but c SpanZ+ (a1, c1,..., ck ). It may, in fact, even happen (again, with negligible / probability) that c SpanZ+ (a1, c1,..., ck ), but Bob expected Alice to respond with a “1” because he selected his c SpanZ+ ( 2 a1, c1,..., ck ).

We also note that the reason for using a public vector a1 with g.c.d. of coordinates even is to have Bob’s vector c in SpanQ+ (a1, c1,..., ck ) in either case, because there is a polynomial-time test detecting whether or not a given vector belongs to the Q+ -span of other given vectors (cf. linear programming problem), see [8] or [12].

Finally, we note that the problem faced by the adversary who wants to impersonate the prover is the following: nd out whether or not the matrix equation Bx = c has a solution for x as a vector with nonnegative integer coordinates. Here B is the matrix made up of coordinates of the vectors a1, c1,..., ck, c is the challenge vector selected by Bob, and x is the vector unknown to both the prover and the adversary. A special case – 187 – of this problem, where B is just a vector with integer coordinates, x is a 0-1 vector, and c is just an integer, is known as the subset sum problem and is NP-complete, see e.g. [2]. Moreover, as pointed out, for example, in [3, p.41], it appears that the subset sum problem might be hard on random instances, not just on some carefully selected ones.

5.1. Suggested parameters and key generation. Suggested parameter values for the protocol above are:

(1) The dimension of vectors is m = 20.

(2) Coordinates of the vectors ai : random nonnegative integers 10. We note that m random m-dimensional vectors like that are going to be linearly independent with overwhelming probability.

(3) Vectors ci are constructed by Alice as random linear combinations of the vectors ai with nonnegative integer coecients 10. The number of vectors ci is k = 2m.

(4) At step (1) of the protocol, Bob constructs his vector c as a random linear com bination of the public vectors a1, c1,..., ck with nonnegative integer coecients 10, with one possible exception: according to the protocol description, he may choose the coecient at a1 to be of the form n, where n is odd, 1 n 19.

6. A particular realization: polynomial equations In this section, we oer another particular realization of the meta-protocol from Section 2.

Alice’s private key consists of: (i) a large prime p 3 (mod 4);

(ii) two random polynomials h(x1,..., xk ) and g(x1,..., xk ) over Zp ;

(iii) a random constant c Zp.

Alice’s public key includes: (i) polynomial f (x1,..., xk ) = (h(x1,..., xk )) c (mod p). (Polynomial f is published as a polynomial over Z, without specifying p.) Thus, for any x1,..., xk Z, there is u Z such that f (x1,..., xk )+c = u2 (mod p);

(ii) polynomial s(x1,..., xk ) = ((g(x1,..., xk ))2 + 1)2 c (mod p). (Again, polynomial s is published as a polynomial over Z, without specifying p.) Thus, a value of the polynomial s(x1,..., xk ) + c is never a square modulo p because -1 is not a square modulo p (since p 3 (mod 4)), and (g(x1,..., xk ))2 + 1 is never equal to 0 modulo p, for the same reason.

Now we give a description of the authentication protocol. Again, to simplify the notation, we give an exposition where Bob challenges Alice with just a single element rather than with a tuple of elements, as in the meta-protocol in Section 2.

(1) Bob selects (see our subsection 6.1 for details) random integers x1,..., xk and plugs them, with equal probabilities, into either f or s. He then sends the result, call it Bob(x1,..., xk ), to Alice.

(2) Alice computes a = Bob(x1,..., xk ) + c (mod p) and checks whether or not a is a square modulo p. If not, she knows that Bob(x1,..., xk ) = f (x1,..., xk ) and sends “1” to Bob. If it is, Alice assumes that Bob(x1,..., xk ) = f (x1,..., xk ) and sends “0” to Bob.

– 188 – (3) Bob, who knows the right answer, simply compares it to Alice’s response and accepts or rejects authentication accordingly.

The way Alice checks whether or not a is a square modulo p is as follows. She raises a to the power of p1. If the result is equal to 1 modulo p, then a is a square modulo p;

if not, then it is not.

6.1. Suggested parameters and key generation. Suggested parameter values for the protocol above are:

(1) The number k of variables: between 3 and 5.

(2) The value of p: on the order of 2t, where t is the security parameter.

(3) The degree of Alice’s private polynomials h, g: between 2 and 3.

(4) Bob generates his integers x1,..., xk uniformly randomly from the interval t [1, 2 k ].

Remark 2. The adversary may try to attack Bob’s challenge by solving one of the equations f (x1,..., xk ) = Bob(x1,..., xk ) or s(x1,..., xk ) = Bob(x1,..., xk ) for in tegers x1,..., xk, or just try to nd out whether either of these equations has integer solutions. The corresponding decision problem (the Diophantine problem, or Hilbert’s 10th problem) is known to be undecidable, see [9]. In our situation, however, adversary actually faces a promise problem since he/she knows that at least one of the equations has integer solutions. Furthermore, in our situation the range for the unknowns is bounded. Still, the “bounded” Diophantine problem is known to be NP-hard, see e.g.

[2], which makes this kind of attack look infeasible, although we avoid making such claims in this paper, as was explained in the Introduction.

Acknowledgement. Both authors are grateful to Max Planck Institut fr Mathematik, u Bonn for its hospitality during the work on this paper. We are also grateful to Nelly Fazio and William E. Skeith for useful discussions.

References [1] U. Feige, A. Fiat and A. Shamir, Zero knowledge proofs of identity, Journal of Cryptology (1987), 77–94.

[2] M. Garey, J. Johnson, Computers and Intractability, A Guide to NP-Completeness, W. H.

Freeman, 1979.

[3] O. Goldreich, Foundations of Cryptography: Volume 1, Basic Tools. Cambridge University Press, 2007.

[4] O. Goldreich, S. Micali, A. Wigderson, Proofs that Yield Nothing but their Validity, or All Languages in NP have Zero-Knowledge Proof Systems, J. ACM 38 (1991), 691–729.

[5] S. Goldwasser, S. Micali, and C. Racko, The Knowledge Complexity of Interactive Proof Sys tems, SIAM J. Comput. 18 (1) (1989), 186-208.

[6] D. Grigoriev, I. Ponomarenko, Constructions in public-key cryptography over matrix groups, Contemp. Math., Amer. Math. Soc. 418 (2006), 103–119.

[7] R. Impagliazzo, M. Naor, Ecient cryptographic schemes provably as secure as subset sum, J.

Cryptology 9 (1996), 199–216.

[8] L. G. Khatchyian, A polynomial algorithm in linear programming, Doklady Akad. Nauk USSR, 244 (1979), 1093–1096 (Russian). [Translated as Soviet Math. Doklady 20 (1979), 191–194.] [9] Yu. Matiyasevich, Hilbert’s 10th Problem (Foundations of Computing), The MIT Press, 1993.

– 189 – [10] A. Menezes, P. van Oorschot, and S. Vanstone, Handbook of Applied Cryptography, CRC-Press 1996.

[11] O. Pandey, R. Pass, A. Sahai, W. Tseng and M. Venkitasubramaniam, Precise concurrent zero knowledge, in: Eurocrypt 2008, Lecture Notes Comp. Sc. 4965 (2008), 397–414.

[12] A. Schrijver, Theory of Linear and Integer Programming, John Wiley 1998.

CNRS, Mathematiques, Universite de Lille, 59655, Villeneuve d’Ascq, France E-mail address: dmitry.grigoryev@math.univ-lille1.fr Department of Mathematics, The City College of New York, New York, NY E-mail address: shpil@groups.sci.ccny.cuny.edu – 190 – CONTINUOUS HARD-TO-INVERT FUNCTIONS WITH APPLICATIONS TO BIOMETRIC AUTHENTICATION D. YU. GRIGORIEV AND S. I. NIKOLENKO Abstract. We consider the problem of constructing continuous cryptographic primitives. We present several candidates for continuous hard-to-invert functions. To formulate these candidates, we introduce constructions based on tropical and supertropical circuits.

1. Introduction Many important cryptographic applications require the underlying primitives to possess some continuity properties. This eect is especially prominent in biometrics: ngerprints, retina scans, and human voices change a little over time, and the conditions are also never exactly the same.

However, the system still needs to let the slightly changed human being pass and still needs to deny access for other human beings who have “changed” substantially more. Thus, for biometric applications continuous cryptographic primitives would be of great interest.

In biometrics, approaches to continuous cryptography have already been proposed. In [22], a fuzzy vault scheme was put forward. In fuzzy vault schemes, continuity is understood in a discrete, set-theoretic sense: a set of features (minutae) is close to another set if their intersection is large and their set dierence is small;

however, the features themselves remain discrete and must match perfectly, just not all of them. The fuzzy vault scheme of [22] was recently criticized and found vulnerable to certain plausible attacks [37, 38];

however, the general problem of nding continuous primitives remains interesting.

In this work, we propose several candidates for continuous hard-to-invert functions, as intro duced in [15]1. We understand continuity in the regular mathematical sense: a continuous function maps close points of a Euclidean space to close points of another Euclidean space. This setting makes perfect sense for biometric applications. For example, voice features – spectral and cep stral coecients and related characteristics – are multidimensional real vectors;

a vault signed by somebody’s voice should forgive small variations in these integral characteristics.

Our basic cryptographic construction, corresponding to biometric needs, is an authentication scheme based on a one-way function. There exist many secure authentication protocols based on one-way functions, e.g. the Lamport’s scheme and the X.509 mechanism based on digital signatures, as well as password schemes [31]. Their exact details are unimportant for our present work;

what is important is which function to use as the underlying hard-to-invert function. Suppose that f : X Y is a function which is easy to compute but hard to invert, and a participant of the authentication protocol Alice has a secret x X (her biometric data). We aim to nd a continuous function f : X Y so that even if Alice’s biometrics changed a little over time to some x X, the distance (x, x ) being small, the value of f (x ) would nevertheless be close to f (x), and the other participant of the protocol would be able to authenticate Alice. On the other hand, an impostor We deliberately do not use the term “one-way” here, as it has a precise mathematical meaning [12], which we obviously cannot prove for our candidate functions. Hard-to-invert functions are functions which are polynomially easy to compute, but for which there is no known algorithm for inverting them in polynomial time. This is, obviously, not a mathematical denition, as it relies on our state of knowledge rather than formal concepts;

nevertheless, this is the best we can hope for at present.

– 191 – Charlie with biometrics y X on a relatively large distance (x, y) should not be authenticated, and f (y) should be far from f (x) in Y.

Continuous one-way functions (better to say, function candidates) have already appeared in literature, but examples and discussion have been limited to the eld of physical one-way functions, i.e. hard-to-invert physical processes and their mathematical models. There are continuous maps based on the second law of thermodynamics that are presumably hard to invert [20];

other physical processes, often naturally continuous, have been proposed as one-way candidates [35, 36]. Our candidates are much simpler, but still do not allow for known ecient inversion algorithms although much thought has been spent on their underlying problems.

For now, no one knows whether there exist functions which are much harder to invert than to compute, especially in the formal cryptographic setting of one-way functions. The hardest results we have without additional assumptions are linear lower bounds (no better explicit lower bounds exist for circuit complexity anyway) [18, 19]. However, we can formulate an open question in theoretical cryptography, which may (or may not, one never knows for sure) turn out to be easier than overcoming these foundational obstacles.

Open question. Provided that one-way functions exist, does there exist a continuous one-way function?

The paper is organized as follows. In Section 2, we consider a polynomial mapping as a one way candidate. In Section 3, we propose a candidate tropical construction. In Section 4, we give constructions of interactive protocols based on our candidate functions.

2. Polynomial candidates 2.1. The general idea. Our rst candidate is a polynomial mapping f : Rn Rm for m n (for example, m = n + 1) for some ring R (we usually take R = R or R = C and assume that f has integer coecients). Inverting this one-way function is equivalent to solving a (slightly) overdetermined system of polynomial equations:

f1 (x1,..., xn ) = y1, f2 (x2,..., xn ) = y2,......

fm (x1,..., xn ) = ym.

Solving systems of polynomial equations has naturally attracted much attention in algebraic geometry. It is well-known that in the worst-case, solving even a system of multivariate quadratic equations is NP-complete, both over a nite eld in the Turing machine model and in the Blum Shub-Smale model over an arbitrary ring or eld, including R and C [2]. It is known that, over a nite eld, if m is much larger than n (the system is very much overdetermined), there are ecient heuristics for solving such systems based on linearization, namely the XSL method which was used in a much acclaimed method of breaking block ciphers [6, 8].

Ecient algorithms for solving overdetermined systems on average (which are more relevant in the cryptographic setting) are not known to date. For systems of n homogeneous polynomial equations in exactly n + 1 variables (functions f : Cn+1 Cn ), Shub and Smale have developed an ingenious path following (homotopy) method that nds one of their non-zero solutions in average subexponential time [39–43].

However, this method suers from several restrictions. First, its running time is subexponential in the dimension N of the vector space H(d) of all homogeneous polynomial maps f : Cn+1 Cn with f = (f1,..., fn ), deg fi = di ;

latest progress in this area brings the average complexity down to N O(log log N ) [3]. This dimension is polynomial in the number of variables if the degree is constant, and polynomial in the degree if the number of variables is constant, but not both. Second, the path following method is restricted to maps f : Cn+1 Cn. For overdetermined systems f : Cn Cm, – 192 – m n, the method does not work, and we have to fall back on the Newton’s method [9], which only nds a root if one begins in a small enough disc around a zero;

see an estimate of the disc radius in [9, Theorem 1].

In order to obtain a small representation of a polynomial with large N, we dene a polynomial mapping by an arithmetic circuit. In essence, we allow parentheses in the denition of the poly nomial and do not require the system to open them. Arithmetic circuits are able to “conceal” the number of monomials N, specifying a polynomial with an exponential number of monomials by a polynomial size circuit. Even polynomials of exponential degree can sometimes be computed in polynomial time, e.g. the value of (x + y)2 is easy to compute by repeated squaring (in the n Blum-Shub-Smale model, in the bit model the result may have exponential length). Note, however, that many natural questions about circuits in this representation become computationally hard.

For example, in [28] it is shown that deciding whether a given polynomial is zero is hard for P#P.

2.2. Continuity modulus. To use a continuous hard-to-invert function, we also have to specify an estimate on the continuity modulus (f, ) = sup |f (u) f (v)|, |uv| where is the maximum distance from the exact stored “password” that should still admit le gitimate authentication. For a polynomial, the continuity modulus is bounded only if we restrict our attention to a compact set. Fortunately, in all practical applications there is a compact set X on which it is meaningful to consider the function f (e.g., the set of all reasonably possible ngerprint minutae or mel-frequency cepstral coecients), so in what follows we assume that all inputs will come from a compact domain.

There are dierent approaches for computing the continuity modulus. It is easy to compute the continuity modulus of a polynomial. However, we do not know the polynomial’s coecients, we only know its circuit (and remember, computing coecients may be very hard). We list several ideas.

(1) For a compact set X, we can estimate the continuity modulus inductively. For input variables (resp, constants) the continuity modulus is 1 (resp., 0). For a summation gate, wf +g wf + wg, so we get a new upper bound by summing the incoming upper bounds.

For a multiplication gate, wf g wf sup g(x) + wg sup f (x).

x x The supremum can also be estimated inductively in the obvious way:

sup(f + g) sup f + sup g, sup(f g) sup f sup g.

However, this estimate loses precision very fast as the size of the circuit grows, so in certain cases it can result in an unacceptably forgiving system.

(2) For a specic x, exceedingly imprecise supremum estimates are not necessary, as the continuity modulus reduces to the derivative at point x which can be computed recursively in the obvious way:

(f + g) (x) = f (x) + g (x), (f g) (x) = f (x)g(x) + f (x)g (x).

(3) The continuity modulus can be estimated even better with the ideas of interval analysis developed by Moore [33], Hansen [17], and Matiyasevich [29];

see also recent surveys of the subject [7, 10]. Application of interval analysis to this particular case, especially in the (super)tropical case, may warrant a separate study, so we do not go into details here and note it as an interesting open problem.

– 193 – In what follows we do not choose a specic approach to computing the continuity modulus but assume that some approach is chosen, and wf is computed at each node and propagated through the entire circuit.

2.3. Random key generation. In order to randomly generate a specic hard-to-invert function candidate, we have to generate a random directed acyclic graph with at least n vertices of indegree zero (inputs and eld constants), m vertices of outdegree zero (outputs), and internal vertices with indegree 2 labeled by either “+” or “”. There exist generation models for random directed acyclic graphs, both uniform [30] and based on the ordered graphs model [25]. For use with our protocols, we prefer the latter model for random ordered graph generation, especially given that arithmetic circuits are naturally random ordered graphs. However, in order to keep the output polynomial sized and to control the continuity modulus we want to produce polynomials of degree nO(1), and random circuits, as noted above, may have exponential degree.

Therefore, we modify the generation model of [25] in order to control the degree. Fix a number n of inputs, a number m of outputs, a degree upper bound D, a number of constant inputs c (all constant inputs in the circuit equal either 1 or 1, and larger constants should be generated from them), and an upper bound on the outdegree K 2. The indegree of each non-input vertex is 2 (all gates represent either + or ), and the outdegree is generated randomly when the node is generated. We build a random circuit node by node. Each node is labeled by a pair (s, d), where s is one of xi, +, or, and d is a natural number representing the “formal degree” of this node.

The generation proceeds as follows.

(1) Generate the graph (G, E) with n + c vertices – n with labels (xi, 1) and c with labels (±1, 0) (the sign is chosen uniformly) – and no edges. Choose outdegrees ki uniformly from 1..K for each vertex and initialize ki “stubs” for each potential outgoing edge (see [25] for a detailed discussion of these “stubs”).

(2) Until m outputs are generated:

(a) Add a new node x, G := G {x}, select its label uniformly from {+, }, select two parents y and z uniformly from the “stubs” available at previous vertices, add the corresponding edges E := E {(y, x), (z, x)}, and delete one “stub” from y and z each.

(b) Compute the formal degree fdeg(x):

max{fdeg(y), fdeg(z)}, if x is a +-vertex, fdeg(x) = fdeg(y) + fdeg(z), if x is a -vertex.

(c) Compute the continuity modulus wx (see 2.2).

(d) If fdeg(x) D + 1, mark x as an output and do not generate outgoing “stubs” for it. Otherwise, generate k outgoing “stubs”, where k is chosen uniformly from 1..K.

(3) Delete remaining “stubs” and output (G, E).

Obviously, this generation model will, with overwhelming probability, generate m outputs of formal degree from D to D in time polynomial in n + m + c.

Note that the “formal degree” fdeg(x) is merely an upper bound on the actual degrees of the generated polynomials;

the actual degree may be much lower due to cancellations. However, each output will have a degree deg fi D;

the worst case is a product of two gates of degree D.

In what follows, we assume that there exists a polynomial-time procedure Gen(n, m, D) that produces an arithmetic circuit for a polynomial map f : Cn Cm of degrees deg fi D.

2.4. The resulting protocol. To make a precise example, let us specify a simple secret-key authentication protocol. Suppose that agent A (Alice) wants to authenticate with a server S using her biometric data. At the beginning of the protocol, S stores the biometric data x, and Alice – 194 – possesses her data x, presumably close to x. The algorithm parameters include n (dimension) and (authentication precision).

(1) A initiates the protocol and represents her biometric data as a vector x Cn.

(2) S randomly selects an arithmetic circuit f with n input variables as shown in 2.3 and sends a representation of this circuit to A.

(3) A randomly selects a vector r Cn and a scalar C (this is analogous to random padding), computes f (r + x ) and transmits (r,, y) for y = f (r + x ).

(4) S computes, the continuity modulus at point r + x, with any method from Section 2. and checks that ||y f (r + x)||. If so, S accepts the authentication of A.

A passive adversary in this protocol is faced with the problem of solving a system of polynomial equations f (r + x) = a with respect to the unknown x for f specied as an arithmetic circuit. If a passive adversary has observed k runs of this protocol for the same server and agent, he faces a problem of solving a system f 1 (r1 + 1 x) = a1, f 2 (r2 + 2 x) = a2,..., f k (rk + k x) = ak.

Note that it is hard for an adversary to apply the methods of [6, 8] because the monomials of the polynomial f are unknown, and there are a lot of them.

It would be desirable for the server S to store only images of f, i.e., y rather than x;

this would reduce the danger of identity theft. However, in this simple protocol it is near impossible 3. Supertropical candidates Exact algebraic approaches to solving a system of nonlinear equations include the resultant approach and Grbner bases. Computing the resultant, despite recent advances [5], is impractical o for large multivariate cases [23, 24]. Grbner bases provide a more practical framework [11, 24], but o still, the complexity of exact (symbolic) methods for solving large systems of polynomial equations is too large.

However, in our case it would suce to nd an approximate solution;

for approximate solutions, there are also the Newton’s method (the homotopy continuation method is based on it), and optimization approaches (see, e.g., [34] that combines several of these methods). To spoil the Newton’s method, it is enough, in theory, to make the number of equations not equal to the number of variables, and we have done so in the previous section. However, to avoid both Newton’s method in practice and optimization approaches, one would like the system’s function f to have many local minima;

it would be even better if the function had many kinks and/or breaks so that there would be no gradient to follow or it would be misleading.

Both of these properties come together in tropical constructions [4,21,32];

moreover, counterparts of symbolic methods are not known for the tropical case. Tropical algebras are based on the tropical semiring (also known as the min-plus algebra) which is a subset of reals with an innity point closed under addition, with two operations:

x y = min(x, y), x y = x + y.

A tropical monomial m = a xi1... xin = a + xi1 +... + xin, 1 ij n, is simply a linear function, while a tropical polynomial p = m1... mk = min(m1,..., mk ) is a minimum of several linear functions, i.e., a concave piecewise linear function with several discontinuity regions.

Several cryptographic constructions based on tropical algebras have been recently presented in [16]. For the purposes of continuous cryptographic constructions, however, we would like to extend the tropical semiring by one more operation, namely regular multiplication (we do not introduce a special symbol for it and use · and juxtaposition). We call the resulting extended semiring (A, ·,, ), A R {}, a supertropical algebra. In the supertropical algebra, a supertropical – 195 – monomial is in fact a polynomial m(x1,..., xn ) = xi11 xi12... xi1n... xim1 xim2... ximn, n n 1 2 1 and a supertropical polynomial p(x1,..., xn ) = m1 (x1,..., xn )... mk (x1,..., xn ) is a minimum of several polynomial functions, i.e., a piecewise polynomial function which is not necessarily concave anymore and still has a lot of discontinuity regions.

We represent a supertropical polynomial system of n variables with a directed acyclic graph with at least n vertices of indegree zero (inputs and eld constants), m vertices of outdegree zero (outputs), and internal vertices with indegree 2 labeled by either “·”, “”, or “”. The generation protocol remains the same with the following additions: for an -gate x with parents y and z that compute functions f and g, respectively, fdeg(x) = max{fdeg(y), fdeg(z)}, wf g = max{wf, wg };

the multiplication and -gates (i.e., the usual addition) are treated in the same way as their polynomial counterparts. The protocol from Section 2.4 works in a similar fashion. The continuity modulus computation and random key generation are done similar to the algorithms presented in subsections 2.2 and 2.3, respectively.

As for the hardness of the resulting protocol, little is known, but there are reasons to believe that it is hard to solve systems of polynomial tropical equations. In [16], it has been shown that it is NP-hard to nd a solution of a system of tropical polynomial equations. This does not mean that there are no algorithms ecient on average, in the generic case, or for our particular choice of key generation, but it is usually an indicator that this is indeed a hard problem. For example, only very recently D. Grigoriev has presented an algorithm for solving a system of linear tropical equations [13];

complexity of the algorithm is suspected to be polynomial, but at present only weakly polynomial upper bounds have been proven. In an independent result, Akian, Gaubert, and Guterman presented several weakly polynomial algorithms for this problem [1]. Many important invariants of tropical systems (varieties) are hard to compute [26, 27, 44]. As for the supertropical case, the outlook is even bleaker;

we do not know of any works in this direction, but it is obvious that solving a supertropical system is at least as hard as solving a tropical system and at least as hard as solving a polynomial system. Based on all of the above, we recommend our supertropical candidate for use with the protocol of Section 2.4.

4. An interactive protocol In this section, we describe one more class of protocols that can be implemented in a continuous fashion with polynomial and supertropical circuits. The basic protocol relies upon the hardness of the matrix conjugation problem. The protocol has been presented in [14];

it is an interactive authentication scheme that goes, for an underlying matrix ring G, as follows.

(1) Alice’s public key is a pair of matrices (A, X 1 AX), where A G, X G;

Alice’s secret key is the matrix X.

(2) For his challenge, Bob selects a random matrix B G and a random non-invertible endo morphism of the ring G. Bob sends B and to Alice.

(3) Alice responds with random positive integers p and q and asks Bob to send back random nonzero constants c1, c2, and c3 so that the new (better randomized) challenge is B = c1 A + c2 B + c3 Ap B q.

(4) Alice responds with (X 1 B X).

– 196 – (5) Bob selects a random word w(x, y) (without negative exponents), evaluates M2 = w (X 1 AX), (X 1 B X), M1 = w (A), (B ), and computes their traces. If tr(M1 ) is suciently close to tr(M2 ), Bob accepts authenti cation, otherwise he rejects.

In [14], Grigoriev and Shpilrain propose to use the ring of n n matrices over sparse truncated k-variate polynomials over a nite eld (in [14], Z11 is suggested). We propose to use the key generation process of Section 2.3 to generate matrices over k-variate polynomials over an innite eld F. Note that for an innite eld itself, there would be another way for the adversary: compute the private key X from the public key (A, C), nd the space of solutions for the equation AX = XC and sample a matrix X at random;

with probability 1, X will be nondegenerate. Thus, the protocol in this section would be insecure for innite elds. For polynomial rings, this is not a problem because a matrix can be invertible only if the determinant of the matrix is a constant polynomial (has degree zero), an event of probability zero. Note also that this protocol does not work over the (super)tropical semiring at all: the only invertible tropical matrices are diagonal ones, which would make the break trivial [4].

Each matrix element can be represented as an arithmetic circuit;

matrix products involve a linear number of additions and multiplications and can be implemented without signicantly increasing the circuit size. The following remarks should be made about this process.

(1) In the protocol, the matrices A and B do not have to be invertible, so no problems arise with its generation. The matrix X, however, has to be invertible, and therefore we propose to generate it as a product of elementary matrices, i.e., matrices that have exactly one non-zero element. The non-zero element is generated as in Section 2.3.

(2) To generate a random endomorphism, one can generate : xi fi, where fi are random truncated k-variate polynomials over F with zero constant term.

(3) To dene what “suciently close” means on step 5 of the protocol, Bob uses the continuity moduli for each element of M1 and M2 and computes tr(M1 ) and tr(M2 ) as the continuity moduli of the corresponding sums of elements.

To break this protocol, an adversary would have to solve a system of n2 polynomial equations given as arithmetic circuits. Note that it would be hard even for an innite eld because the size of a linearization grows exponentially and, as shown in [14], even for a reasonable choice of protocol parameters the linear system becomes too large to solve.

5. Conclusion In this paper, we have presented two hard-to-invert candidates that share a common desirable property: they are continuous. When preserved in an authentication protocol, this property allows for small changes in the secret information so that a suciently close authentication request (e.g., slightly modied biometrics) is still accepted. We have also introduced supertropical algebras as a platform for cryptographic protocols.

We have presented the ideas of two protocols. Further work about these protocols should deal with their specic implementations and tuning the parameters in order to test their properties and modify them to be as secure and ecient in practice as possible.

Acknowledgements. This work has resulted from the cooperation organized under the Federal Target Programme “Scientic and scientic-pedagogical personnel of the innovative Russia”. Work of the second author has also been supported by the Russian Presidential Grant Programme for Young Ph.D.’s, grant no. MK-4089.2010.1, for Leading Scientic Schools, grant no. NSh 5282.2010.1, and Russian Fund for Basic Research grants.

– 197 – References [1] Akian, M., Gaubert, S., and Guterman, A. Tropical polyhedra are equivalent to mean payo games. Inter national Journal on Algebra and Computations To appear (2011).

[2] Blum, L., Shub, M., and Smale, S. On a theory of computation and complexity over the real numbers: Np completeness, recursive functions and universal machines. Bulletin of the American Mathematical Society 21, (1989), 1–46.

[3] Burgisser, P., and Cucker, F. Solving polynomial equations in smoothed polynomial time and a near solution to Smale’s 17th problem. In Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (2010), pp. 503–512.

[4] Butkovic, P. Max-linear systems: theory and algorithms. Springer-Verlag London, 2010.

[5] Chtcherba, A. D. A new Sylvester-type resultant method based on the Dixon-Bezout formulation. PhD thesis, The University of New Mexico, 2003.

[6] Cid, C., and Leurent, G. An analysis of the XSL algorithm. In Proceedings of the 11th ASIACRYPT, Inter national Conference on the Theory and Application of Cryptology and Information Security, Lecture Notes in Computer Science (2005), vol. 3788, pp. 333–352.

[7] Cloud, M. J., Moore, R. E., and Kearfott, R. B. Introduction to Interval Analysis. Society for Industrial and Applied Mathematics, Philadelphia, 2009.

[8] Courtois, N., and Pieprzyk, J. Cryptanalysis of block ciphers with overdened systems of equations. In Proceedings of the 8th ASIACRYPT, International Conference on the Theory and Application of Cryptology and Information Security, Lecture Notes in Computer Science (2002), vol. 2501, pp. 323–337.

[9] Dedieu, J. P., and Shub, M. Newton’s method for overdetermined systems of equations. Mathematics of Computation 69, 231 (1999), 1099–1115.

[10] Didrit, O., Jaulin, L., and Kieffer, M. Applied Interval Analysis. Springer, Berlin, 2001.

[11] Froberg, R. An Introduction to Grbner Bases. Wiley & Sons, 1997.

o [12] Goldreich, O. Foundations of Cryptography. Basic Tools. Cambridge University Press, 2001.

[13] Grigoriev, D. Complexity of solving tropical linear systems. MPI Preprint 2010-60, 2010.

[14] Grigoriev, D., and Shpilrain, V. Authentication from matrix conjugation. Groups, Complexity, and Cryp tology 1 (2009), 199–205.

[15] Grigoriev, D., and Shpilrain, V. Zero-knowledge authentication schemes from actions on graphs, groups, or rings. Annals of Pure and Applied Logic 162 (2010), 194–200.

[16] Grigoriev, D., and Shpilrain, V. Tropical cryptography. Preprint, 2011.

[17] Hansen, E. R. A generalized interval arithmetic. In Interval Mathematics, Lecture Notes in Computer Science (1978), vol. 29, Springer-Verlag, Berlin, pp. 7–18.

[18] Hiltgen, A. P. Constructions of feebly-one-way families of permutations. In Proc. of AsiaCrypt ’92 (1992), pp. 422–434.

[19] Hirsch, E. A., and Nikolenko, S. I. A feebly secure trapdoor function. In Proceedings of the 4th Computer Science Symposium in Russia, Lecture Notes in Computer Science (2009), vol. 5675, pp. 129–142.

[20] Hungerbuhler, N., and Struwe, M. A one-way function from thermodynamics and applications to cryptog raphy. Elemente der Mathematik 58, 2 (2003), 2026–2030.

[21] Itenberg, I., Mikhalkin, G., and Shustin, E. Tropical algebraic geometry, vol. 35 of Oberwolfach Seminars.

Birkhuser, Basel, 2007.

a [22] Juels, A., and Sudan, M. A fuzzy vault scheme. Designs, Codes and Cryptography 38, 2 (2006), 237–257.

[23] Kapur, D., and Lakshman, Y. N. Elimination methods: an introduction. In Symbolic and Numerical Compu tation for Articial Intelligence, B. Donald, D. Kapur, and J. Mundy, Eds. Academic Press, 1992.

[24] Kapur, D., and Saxena, T. Comparison of various multivariate resultant formulations. In Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation (1995), ACM Press, pp. 187–195.

[25] Karrer, B., and Newman, M. E. J. Random acyclic networks. Physical Review Letters 102, 12 (2009), 128701.

[26] Kim, K. H., and Roush, F. W. Factorization of polynomials in one variable over the tropical semiring. ArXiv preprint math/0501167, 2005.

[27] Kim, K. H., and Roush, F. W. Kapranov rank vs. tropical rank. Proceedings of the American Mathematical Society 134 (2006), 2487–2494.

[28] Koiran, P., and Perifel, S. The complexity of two problems on arithmetic circuits. Theoretical Computer Science 389, 1–2 (2007), 172–181.

[29] Matiyasevich, Y. V. A posteriori interval analysis. In Proceedings of the EUROCAL’85, Lecture Notes in Computer Science (1985), vol. 204, pp. 328–334.

[30] Melancon, G., Dutour, I., and Bousquet-Melou, M. Random generation of directed acyclic graphs. Elec tronic Notes in Discrete Mathematics 10 (2001), 202–207.

– 198 – [31] Menezes, A., van Oorschot, P., and Vanstone, S. Handbook of Applied Cryptography. Boca Raton, Florida:

CRC Press, 1997.

[32] Mikhalkin, G. Tropical geometry and its applications. In Proceedings of the International Congress of Mathe maticians (2006), vol. 2, pp. 827–852.

[33] Moore, R. E. Interval Analysis. Prentice-Hall, Englewood Cli, New Jersey, 1966.

[34] Pan, V. Y., and Zheng, A.-L. New progress in real and complex polynomial root-nding. Computers & Mathematics with Applications 61, 5 (2011), 1305–1334.

[35] Pappu, S. R. Physical One-Way Functions. PhD thesis, Massachusetts Institute of Technology, 2001.

[36] Pappu, S. R., Recht, B., Taylor, J., and Gershenfeld, N. Physical one-way functions. Science 297, (2002), 2026–2030.

[37] Poon, H. T., and Miri, A. A collusion attack on the fuzzy vault scheme. The ISC International Journal of Information Security 1, 1 (2009), 27–34.

[38] Schreier, W. J., and Boult, T. E. Cracking fuzzy vaults and biometric encryption. In Proceedings of the Bio metrics Symposium 2007 at The Biometric Consortium Conference (BCC), Baltimore, Maryland, USA (2007).

[39] Shub, M., and Smale, S. Complexity of Bezout’s theorem I: Geometric aspects. Journal of the American Mathematical Society 6 (1993), 459–501.

[40] Shub, M., and Smale, S. Complexity of Bezout’s theorem II: Volumes and probabilities. In Computational Algebraic Geometry, F. Eyssette and A. Galligo, Eds., vol. 109 of Progress in Mathematics. Bikrhuser, 1993, a pp. 267–285.

[41] Shub, M., and Smale, S. Complexity of Bezout’s theorem III: Condition number and packing. Journal of Complexity 9 (1993), 4–14.

[42] Shub, M., and Smale, S. Complexity of Bezout’s theorem V: Polynomial time. Theoretical Computer Science 134 (1994), 141–164.

[43] Shub, M., and Smale, S. Complexity of Bezout’s theorem IV: Probability of success;

extensions. SIAM Journal of Numerical Analysis 33 (1996), 128–148.

[44] Theobald, T. On the frontiers of polynomial computations in tropical geometry. Journal of Symbolic Compu tation 41 (2006), 1360–1375.

– 199 –