Dima Grigoriev
email: dmitry.grigoryev@math.univ-lille1.fr

Sergey Nikolenko
email: sergey@logic.pdmi.ras.ru

CONTINUOUS HARD-TO-INVERT FUNCTIONS AND BIOMETRIC AUTHENTICATION

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. This is, obviously, not a mathematical definition, as it relies on our state of knowledge rather than formal concepts; nevertheless, this is the best we can hope for at present.

Introduction

Many important cryptographic applications require the underlying primitives to possess some continuity properties. This effect is especially prominent in biometrics: fingerprints, 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 [START_REF] Juels | A fuzzy vault scheme[END_REF], 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 difference is small; however, the features themselves remain discrete and must match perfectly, just not all of them. The fuzzy vault scheme of [START_REF] Juels | A fuzzy vault scheme[END_REF] was recently criticized and found vulnerable to certain plausible attacks [START_REF] Ting | A collusion attack on the fuzzy vault scheme[END_REF][START_REF] Walter | Cracking fuzzy vaults and biometric encryption[END_REF]; however, the general problem of finding continuous primitives remains interesting.

In this work, we propose several candidates for continuous hardto-invert functions, as introduced in [START_REF] Grigoriev | Zero-knowledge authentication schemes from actions on graphs, groups, or rings[END_REF] 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 cepstral coefficients 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 [START_REF] Menezes | Handbook of Applied Cryptography[END_REF]. 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 find 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 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 field of physical one-way functions, i.e. hard-toinvert physical processes and their mathematical models. There are continuous maps based on the second law of thermodynamics that are presumably hard to invert [START_REF] Hungerbühler | A one-way function from thermodynamics and applications to cryptography[END_REF]; other physical processes, often naturally continuous, have been proposed as one-way candidates [START_REF] Srinivasa | Physical One-Way Functions[END_REF][START_REF] Srinivasa | Physical one-way functions[END_REF]. Our candidates are much simpler, but still do not allow for known efficient 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) [START_REF] Hiltgen | Constructions of feebly-one-way families of permutations[END_REF][START_REF] Hirsch | A feebly secure trapdoor function[END_REF]. 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.

Polynomial candidates

2.1. The general idea. Our first candidate is a polynomial mapping f : R n → R m for m > n (for example, m = n + 1) for some ring R. In theory, we usually take R = R or R = C and assume that f has integer coefficients; in practice, the corresponding real or rational numbers will all be rational; we denote the rational points of C by Q C = Q + iQ. Inverting this one-way function is equivalent to solving a (slightly) overdetermined system of polynomial equations:

f 1 (x 1 , . . . , x n ) = y 1 , f 2 (x 2 , . . . , x n ) = y 2 , . . . . . . f m (x 1 , . . . , x n ) = y m .
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 NPcomplete, both over a finite field in the Turing machine model and in the Blum-Shub-Smale model over an arbitrary ring or field, including R and C [START_REF] Blum | On a theory of computation and complexity over the real numbers: Np-completeness, recursive functions and universal machines[END_REF]. It is known that, over a finite field, if m is much larger than n (the system is very much overdetermined), there are efficient heuristics for solving such systems based on linearization, namely the XSL method which was used in a much acclaimed method of breaking block ciphers [START_REF] Cid | An analysis of the XSL algorithm[END_REF][START_REF] Courtois | Cryptanalysis of block ciphers with overdefined systems of equations[END_REF].

Efficient 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 : C n+1 → C n ), Shub and Smale have developed an ingenious path following (homotopy) method that finds one of their non-zero solutions in average subexponential time [START_REF] Shub | Complexity of Bezout's theorem I: Geometric aspects[END_REF][START_REF] Shub | Complexity of Bezout's theorem II: Volumes and probabilities[END_REF][START_REF] Shub | Complexity of Bezout's theorem III: Condition number and packing[END_REF][START_REF] Shub | Complexity of Bezout's theorem V: Polynomial time[END_REF][START_REF] Shub | Complexity of Bezout's theorem IV: Probability of success; extensions[END_REF].

However, this method suffers 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 :

C n+1 → C n with f = (f 1 , . . . , f n ), deg f i = d i ;
latest progress in this area brings the average complexity down to N O(log log N ) [START_REF] Bürgisser | Solving polynomial equations in smoothed polynomial time and a near solution to Smale's 17th problem[END_REF]. 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 : C n+1 → C n . For overdetermined systems f : C n → C m , m > n, the method does not work, and we have to fall back on Newton's method [START_REF] Dedieu | Newton's method for overdetermined systems of equations[END_REF], which only finds a root if one begins in a small enough disc around a zero; see an estimate of the disc radius in [10, Theorem 1].

In order to obtain a small representation of a polynomial with large N , we define a polynomial mapping by an arithmetic circuit. In essence, we allow parentheses in the definition of the polynomial 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 n is easy to compute by repeated squaring (in the 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 [START_REF] Koiran | The complexity of two problems on arithmetic circuits[END_REF] it is shown that deciding whether a given polynomial is zero is hard for P #P .

Continuity modulus.

To use a continuous hard-to-invert function, we also have to specify an estimate on the continuity modulus

ω(f, δ) = sup |u-v|<δ |f (u) -f (v)| ,
where δ is the maximum distance from the exact stored "password" that should still admit legitimate 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 fingerprint minutae or melfrequency cepstral coefficients), so in what follows we assume that all inputs will come from a compact domain Ω.

There are different 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 coefficients, we only know its circuit (and remember, computing coefficients 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, w f +g ≤ w f + w g , so we get a new upper bound by summing the incoming upper bounds. For a multiplication gate,

w f g ≤ w f sup x∈Ω g(x) + w g sup x∈Ω f (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 specific 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 [START_REF] Moore | Interval Analysis[END_REF], Hansen [START_REF] Hansen | A generalized interval arithmetic[END_REF], and Matiyasevich [START_REF] Matiyasevich | A posteriori interval analysis[END_REF]; see also recent surveys of the subject [START_REF] Michael | Introduction to Interval Analysis[END_REF][START_REF] Didrit | Applied Interval Analysis[END_REF]. 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. In what follows we do not choose a specific approach to computing the continuity modulus but assume that some approach is chosen, and w f is computed at each node and propagated through the entire circuit.

2.3.

Random key generation. In order to randomly generate a specific hard-to-invert function candidate, we have to generate a random directed acyclic graph with at least n vertices of indegree zero (inputs and field 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 [START_REF] Melançon | Random generation of directed acyclic graphs[END_REF] and based on the ordered graphs model [START_REF] Karrer | Random acyclic networks[END_REF]. 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 n O (1) , and random circuits, as noted above, may have exponential degree. Therefore, we modify the generation model of [START_REF] Karrer | Random acyclic networks[END_REF] 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 x i , +, 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 (x i , 1) and c with labels (±1, 0) (the sign is chosen uniformly)and no edges. Choose outdegrees k i uniformly from 1..K for each vertex and initialize k i "stubs" for each potential outgoing edge (see [START_REF] Karrer | Random acyclic networks[END_REF] 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): fdeg(x) = max{fdeg(y), fdeg(z)}, if x is a +-vertex, fdeg(y) + fdeg(z), if x is a ×-vertex.

(c) Compute the continuity modulus w x (see 2.2). (d) If fdeg(x) ≥ ⌊ D 2 ⌋ + 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 2 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 f i ≤ D; the worst case is a product of two gates of degree

⌊ D 2 ⌋.
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 :

Q n C → Q m C of degrees deg f i ≤ 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 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 ′ ∈ Q n C . (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 ∈ Q n C and a scalar α ∈ Q 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.2 and checks that ||yf (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 specified 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 (r 1 + α 1 x) = a 1 , f 2 (r 2 + α 2 x) = a 2 , . . . , f k (r k + α k x) = a k .
Note that it is hard for an adversary to apply the methods of [START_REF] Cid | An analysis of the XSL algorithm[END_REF][START_REF] Courtois | Cryptanalysis of block ciphers with overdefined systems of equations[END_REF] 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

Supertropical candidates

Exact algebraic approaches to solving a system of nonlinear equations include the resultant approach and Gröbner bases. Computing the resultant, despite recent advances [START_REF] Chtcherba | A new Sylvester-type resultant method based on the Dixon-Bezout formulation[END_REF], is impractical for large multivariate cases [START_REF] Kapur | Elimination methods: an introduction[END_REF][START_REF] Kapur | Comparison of various multivariate resultant formulations[END_REF]. Gröbner bases provide a more practical framework [START_REF] Fröberg | An Introduction to Gröbner Bases[END_REF][START_REF] Kapur | Comparison of various multivariate resultant formulations[END_REF], but still, the complexity of exact (symbolic) methods for solving large systems of polynomial equations is too large. However, in our case it would suffice to find an approximate solution; for approximate solutions, there are also Newton's method (the homotopy continuation method is based on it), and optimization approaches (see, e.g., [START_REF] Victor | New progress in real and complex polynomial root-finding[END_REF] that combines several of these methods). To spoil 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 [START_REF] Butkovic | Max-linear systems: theory and algorithms[END_REF][START_REF] Itenberg | Tropical algebraic geometry[END_REF][START_REF] Mikhalkin | Tropical geometry and its applications[END_REF]; 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 infinity point closed under addition, with two operations:

x ⊕ y = min(x, y), x ⊗ y = x + y. A tropical monomial m = a⊗x i 1 ⊗. . .⊗x in = a+x i 1 +. . .+x in , 1 ≤ i j ≤ n, is simply a linear function, while a tropical polynomial p = m 1 ⊕. . .⊕ m k = min(m 1 , . . . , m k
) 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 [START_REF] Grigoriev | Tropical cryptography[END_REF]. 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 monomial is in fact a polynomial

m(x 1 , . . . , x n ) = x i 11 1 x i 12 2 . . . x i 1n n ⊗ . . . ⊗ x i m1 1 x i m2 2 .
. . x imn n , and a supertropical polynomial

p(x 1 , . . . , x n ) = m 1 (x 1 , . . . , x n ) ⊕ . . . ⊕ m k (x 1 , . . . , x n )
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 field 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)},

w f ⊕g = max{w f , w g };
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 [START_REF] Grigoriev | Tropical cryptography[END_REF], it has been shown that it is NP-hard to find a solution of a system of tropical polynomial equations. This does not mean that there are no algorithms efficient 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 [START_REF] Grigoriev | Complexity of solving tropical linear systems[END_REF]; this problem is known to be in NP∩co-NP, and it is suspected to have polynomial complexity, but Grigoriev's algorithm has been recently shown to require superpolynomial time in the worst case [START_REF] Davydow | Complexity bounds on Grigoriev's algorithm for solving tropical linear systems[END_REF]. In an independent result, Akian, Gaubert, and Guterman presented several weakly polynomial algorithms for this problem [START_REF] Akian | Tropical polyhedra are equivalent to mean payoff games[END_REF]. Many important invariants of tropical systems (varieties) are hard to compute [START_REF] Kim | Factorization of polynomials in one variable over the tropical semiring[END_REF][START_REF] Kim | Kapranov rank vs. tropical rank[END_REF][START_REF] Theobald | On the frontiers of polynomial computations in tropical geometry[END_REF]. 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.

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 [START_REF] Grigoriev | Authentication from matrix conjugation[END_REF]; 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 endomorphism ϕ 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 c 1 , c 2 , and c 3 so that the new (better randomized) challenge is

B ′ = c 1 A+c 2 B + c 3 A p B q . ( 4
) Alice responds with ϕ(X -1 B ′ X).

(5) Bob selects a random word w(x, y) (without negative exponents), evaluates

M 1 = w (ϕ(A), ϕ(B ′ )) , M 2 = w ϕ(X -1 AX), ϕ(X -1 B ′ X) ,
and computes their traces. If tr(M 1 ) is sufficiently close to tr(M 2 ), Bob accepts authentication, otherwise he rejects.

In [START_REF] Grigoriev | Authentication from matrix conjugation[END_REF], Grigoriev and Shpilrain propose to use the ring of n × n matrices over sparse truncated k-variate polynomials over a finite field (in [START_REF] Grigoriev | Authentication from matrix conjugation[END_REF], Z 11 is suggested). We propose to use the key generation process of Section 2.3 to generate matrices over k-variate polynomials over an infinite field F. Note that for an infinite field itself, there would be another way for the adversary: compute the private key X from the public key (A, C), find 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 infinite fields. 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 since the only invertible tropical matrices are monomial matrices, i.e., products of a diagonal and a permutation matrix, which would make the break trivial [START_REF] Butkovic | Max-linear systems: theory and algorithms[END_REF].

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 significantly 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 ϕ :

x i → f i , where f i are random truncated k-variate polynomials over F with zero constant term. [START_REF] Bürgisser | Solving polynomial equations in smoothed polynomial time and a near solution to Smale's 17th problem[END_REF] To define what "sufficiently close" means on step 5 of the protocol, Bob uses the continuity moduli for each element of M 1 and M 2 and computes ω tr(M 1 ) and ω tr(M 2 ) as the continuity moduli of the corresponding sums of elements. To break this protocol, an adversary would have to solve a system of n 2 polynomial equations given as arithmetic circuits. Note that it would be hard even for an infinite field because the size of a linearization grows exponentially and, as shown in [START_REF] Grigoriev | Authentication from matrix conjugation[END_REF], even for a reasonable choice of protocol parameters the linear system becomes too large to solve.

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 sufficiently close authentication request (e.g., slightly modified 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 specific implementations and tuning the parameters in order to test their properties and modify them to be as secure and efficient in practice as possible.

We deliberately do not use the term "one-way" here, as it has a precise mathematical meaning[START_REF] Goldreich | Foundations of Cryptography. Basic Tools[END_REF], 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.1

Acknowledgements. This work has resulted from the cooperation organized under the Federal Target Programme "Scientific and scientificpedagogical personnel of the innovative Russia". The first author is grateful to the Max-Planck Institut für Mathematik, Bonn for its hospitality during writing this paper. Work of the second author has been supported by the Russian Presidential Grant Programme for Young Ph.D.'s, grant no. MK-6628.2012.1, for Leading Scientific Schools, grant no. NSh-3229.2012.1, and Russian Fund for Basic Research grants 11-01-12135-ofi-m-2011 and 11-01-00760-a.