Cryptographic method of secure comparison of two secret data x and y

Abstract

A cryptographic method including: generating by a first device having a datum x an RSA module N; computing by the first device a number C=g.sup.b.sup.axh1, g being an element of sub-group G of order b.sup.d, h1 being an element of sub-group H of order f, and a, b, d, f being integers, b and f being mutually prime, and x and y being less than d/a; sending C to a second device having datum y; computing by the second device D=C.sup.u.Math.b.sup.d−ay(gh3).sup.vh2, u and v being random numbers and h2 and h3 being elements of H, and a first fingerprint (gh3).sup.v; sending to the first device, D and the first fingerprint; computing by the first device (D.sup.f).sup.f′, f′=1/f; obtaining based on (D.sup.f).sup.f′ a second fingerprint; and determining whether x is greater than or equal to y or x is less than y by comparing the first and the second fingerprints.

Claims

1. A cryptographic method of secure comparison of two integer secret data x and y, possessed by a first computing device and by a second computing device, respectively, said method comprising: generating, by the first computing device, an RSA module denoted N; computing, by the first computing device, a number C equal to g.sup.b.sup.axh1 where g is an element of a sub-group G of .sub.N of order b.sup.d h1 is an element of a sub-group H of .sub.N of order, and a, b, d, and f denote integers such that b and f are mutually prime, and the data x and y are less than d/a; sending, by the first computing device, the number C to the second computing device; computing, by the second computing device, at least: a number D equal to C.sup.u.Math.b.sup.d−ay(gh3).sup.vh2 where u and v denote two random integers, and h2 and h3 elements of the sub-group H; and a first fingerprint of (gh3).sup.v computed using a hash function; sending, by the second computing device to the first computing device, the number D and the first fingerprint; computing, by the first computing device, the number (D.sup.f).sup.f′ where f′ is the inverse of f modulo b.sup.d; obtaining, by the first computing device, on the basis of the number (D.sup.f).sup.f′ computed, a second fingerprint using the hash function; and determining, by the first computing device, that x is greater than or equal to y or that x is less than y as a function of the result of a comparison between the first fingerprint and the second fingerprint.

2. The cryptographic method as claimed in claim 1 further comprising computing, by the second computing device, a number D1 and sending D1 to the first computing device, which is used thereby to obtain the second fingerprint.

3. The cryptographic method as claimed in claim 1 wherein: g is a public element; h3=1; the second fingerprint is obtained by applying the hash function to the number (D.sup.f).sup.f′ computed.

4. The cryptographic method as claimed in claim 2 wherein: g is an element kept secret by the first computing device and h3=h4.sup.e where e is an integer kept secret by the first computing device and h4 denotes an element of the sub-group H; the first computing device sends to the second computing device a number h′=g.Math.h3, this number being used by the second computing device to compute the first fingerprint; the number D1 computed by the second computing device and sent to the first computing device is equal to h4.sup.v; and the second fingerprint is obtained by applying the hash function to the number (D.sup.f).sup.f′ computed, multiplied by D1.sup.e.

5. The cryptographic method as claimed in claim 1 wherein the integer a is chosen less than or equal to the integer d, and b.sup.a>2.sup.z where z denotes a predetermined security parameter.

6. The cryptographic method as claimed in claim 1 wherein the integer u is chosen at random in the interval [0; b.sup.a−1] and the integer v is chosen at random in the interval [0; b.sup.d−1].

7. A first computing device possessing and keeping secret an integer datum x, said first computing device comprising: a processor; and a non-transitory computer-readable medium comprising instructions stored thereon, which when executed by the processor configure the first computing device to: generate an RSA module denoted N; compute a number C equal to g.sup.b.sup.axh1 where g is an element of a sub-group G of .sub.N of order b.sup.d, h1 is an element of a sub-group H of .sub.N of order f, and a, b, d, and f denote integers such that b and f are mutually prime and the datum x is less than d/a; send the number C to a second computing device possessing and keeping secret an integer datum y, the datum y being less than d/a; receive from the second computing device at least: a number D equal to C.sup.u.Math.b.sup.d−ay(gh3).sup.vh2 where u and v denote two random integers, and h2 and h3 elements of the sub-group H; and a first fingerprint of (gh3).sup.v computed using a hash function; compute a number (D.sup.f).sup.f′ where f′ is the inverse of f modulo b.sup.d; obtain on the basis of the number (D.sup.f).sup.f′ computed a second fingerprint using the hash function; and determine that x is greater than or equal to y or that x is less than y as a function of the result of a comparison between the first fingerprint and the second fingerprint.

8. A second computing device possessing and keeping secret an integer datum y, said second computing device comprising: a processor; and a non-transitory computer-readable medium comprising instructions stored thereon, which when executed by the processor configure the second computer device to: receive from a first computing device possessing and keeping secret an integer datum x, a number C equal to g.sup.b.sup.axh1 where q is an element of a sub-group G of .sub.N of order b.sup.d, h1 is an element of a sub-group H of .sub.N of order f, and a, b, d, and f denote integer numbers such that b and f are mutually prime and the data x and y are less than d/a; compute at least: a number D equal to C.sup.u.Math.b.sup.d−ay(gh3).sup.vh2 where u and v denote two random integers, and h2 and h3 elements of the sub-group H; and a fingerprint of (gh3).sup.v computed using a hash function; send to the first computing device the number D and the computed fingerprint, to allow the first computing device to determine without knowing y if x is greater than or equal to y or if x is less than y.

9. A determining method, implemented by a first computing device, possessing and keeping secret an integer datum x, said determining method comprising: generating an RSA module denoted N; computing a number C equal to g.sup.b.sup.axh1 where g is an element of a sub-group G of .sup.N of order b.sup.d, h1 is an element of a sub-group H of .sub.N of order f, and a, b, d, and f denote integers such that b and f are mutually prime, and the datum x is less than d/a; sending the number C to a second computing device possessing and keeping secret an integer datum y, the datum y being less than d/a; receiving, from the second computing device, at least: a number D equal to C.sup.u.Math.d.sup.d−ay(gh3).sup.vh2 where u and v denote two random integers, and h2 and h3 elements of the sub-group H; and a first fingerprint of (gh3).sup.v computed using a hash function; computing, by the first computing device, the number (D.sup.f).sup.f′ where f′ is the inverse of f modulo b.sup.d; obtaining, by the first computing device, on the basis of the number (D.sup.f).sup.f′ computed, a second fingerprint using the hash function; and determining, by the first computing device, that x is greater than or equal to y or that x is less than y as a function of the result of a comparison between the first fingerprint and the second fingerprint.

10. A computing method, implemented by a second computing device, possessing and keeping secret an integer datum y, said computing method comprising: receiving, from a first computing device possessing and keeping secret an integer datum x, a number C equal to g.sup.b.sup.axh1 where g is an element of a sub-group G of .sub.N of order b.sup.d, h1 is an element of a sub-group H of .sub.N of order f, and a, b, d, and f denote integer numbers such that b and f are mutually prime and the data x and y are less than d/a; computing at least: a number D equal to C.sup.u.Math.b.sup.d−ay(gh3).sup.vh2 where u and v denote two random integers, and h2 and h3 elements of the sub-group H; and a fingerprint o(gh3).sup.v computed using a hash function; sending to the first computing device the number D and the computed fingerprint, to allow the first computing device to determine without knowing y if x is greater than or equal to y or if x is less than y.

11. A non-transitory computer-readable medium comprising instructions stored thereon for executing determining method when said program is executed by a processor of a first computing device, possessing and keeping secret an integer datum x, wherein the instructions configure the first computing device to: generate an RSA module denoted N; compute a number C equal to g.sup.b.sup.axh1 where g is an element of a sub-group G of .sub.N of order b.sup.d, h1 is an element of a sub-group H of .sub.N of order f, and a, b, d, and f denote integers such that b and f are mutually prime and the datum x is less than d/a; send the number C to a second computing device possessing and keeping secret an integer datum y, the datum y being less than d/a; receive from the second computing device at least: a number D equal to C.sup.u.Math.b.sup.d−ay(gh3).sup.vh2 where u and v denote two random integers, and h2 and h3 elements of the sub-group H; and a first fingerprint of (gh3).sup.v computed using a hash function; compute a number (D.sup.f).sup.f′ where f′ is the inverse off modulo b.sup.d; obtain on the basis of the number (D.sup.f).sup.f′ computed a second fingerprint using the hash function; and determine that x is greater than or equal to y or that x is less than y as a function of the result of a comparison between the first fingerprint and the second fingerprint.

12. (canceled)

13. A non-transitory computer-readable medium comprising instructions stored thereon for executing a computing method when said program is executed by a processor of a second computing device, possessing and keeping secret an integer datum y, wherein the instructions configure the second computing device to: receive from a first computing device possessing and keeping secret an integer datum x, a number C equal to g.sup.b.sup.axh1 where g is an element of a sub-group G of .sub.N of order b.sup.d, h1 is an element of a sub-group H of .sub.N of order f, and a, b, d, and f denote integer numbers such that b and f are mutually prime and the data x and y are less than d/a; compute at least: a number D equal to C.sup.u.Math.b.sup.d−ay(gh3).sup.vh2 where u and v denote two random integers, and h2 and h3 elements of the sub-group H; and a fingerprint of (gh3).sup.v computed using a hash function; send to the first computing device the number D and the computed fingerprint, to allow the first computing device to determine without knowing y if x is greater than or equal to y or if x is less than y.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0090] Other features and advantages of this invention will become apparent from the description given below, with reference to the appended drawings which illustrate an exemplary embodiment thereof devoid of any limitation. In the figures:

[0091] FIG. 1 schematically represents a cryptographic system in accordance with the invention, in a particular embodiment;

[0092] FIG. 2 schematically illustrates the hardware architecture of a first computing device and a second computing device of the cryptographic system of FIG. 1, in accordance with the invention, in a particular embodiment;

[0093] FIG. 3 represents in the form of a flow diagram the main steps of a comparison method according to the invention as it is implemented by the cryptographic system of FIG. 1, in a first embodiment; and

[0094] FIG. 4 represents in the form of a flow diagram the main steps of a comparison method according to the invention as it is implemented by the cryptographic system of FIG. 1, in a second embodiment.

DETAILED DESCRIPTION OF THE INVENTION

[0095] FIG. 1 represents, in its environment, a cryptographic system 1 in accordance with the invention, in a particular embodiment.

[0096] The cryptographic system 1 is designed so as to allow the production of two integer data x and y respectively possessed by two separate entities 2 and 3 while allowing each of these entities to keep secret the datum it possesses with regard to the other entity. In other words, the secret data can be compared thanks to the cryptographic system 1 without the entity 2 needing to reveal to the entity 3 the datum x and conversely, without the entity 3 needing to reveal to the entity 2 the datum y.

[0097] Here the two entities 2 and 3 are computing devices in accordance with the invention. In the example illustrated in FIG. 1, the entity 2 is a “first” computing device within the meaning of the invention, in the sense that it is this device that determines the result of the comparison of the two secret data x and y, and the entity 3 is a “second” computing device within the meaning of the invention.

[0098] No limitation is attached to the context in which the cryptographic system 1 and correspondingly the two entities 2 and 3 are led to make this comparison. As previously mentioned, the comparison of two secret integer data is a task that is found in many algorithms used in various fields (healthcare, cybersecurity, finance etc.) and particularly in machine learning algorithms based on ranking techniques requiring the comparison of integers in a secure manner. Other types of algorithm also make use of the comparison of integers, such as for example the algorithms used in certain electronic voting systems (in particular when it is desirable to determine who is the winner of an election without revealing the respective scores of the different candidates), or secret electronic auctions (the offers of the bidders are then encrypted to remain secret, and it is desirable to determine who has made the best bid but without having to reveal the bids of the other bidders etc.)

[0099] In the example envisioned in FIG. 1, the computing devices 2 and 3 are computers, the architecture of which is schematically illustrated in FIG. 2.

[0100] Each computing device comprises in particular a processor 4, a read-only memory 5, a random-access memory 6, a non-volatile memory 7 (in which is stored for example the secret datum x for the computing device 2 and y for the computing device 3) and communication means 8. The communication means 8 allow the devices 2 and 3 to communicate with one another, to exchange various elements with one another, described in more detail below. They may interchangeably comprise a wireless or wired interface etc.

[0101] The read-only memory 5 of the computing device 2 and the computing device 3 constitutes a recording medium in accordance with the invention, readable by the processor 4 and on which is recorded a computer program PROG2 and PROG3 respectively, in accordance with the invention, respectively including, for the computing device 2, instructions for executing the steps of the determining method according to the invention and for the computing device 3 instructions for executing the steps of the computing method according to the invention.

[0102] More precisely, the computer program PROG2 defines via its instructions a number of functional modules of the computing device 2 able to implement the steps of the determining method and relying on the hardware elements 4-8 of the computing device 2. These functional modules in particular comprise, in the embodiment described here, as illustrated in FIG. 1, a generating module 2A, a first computing module 2B, a sending module 2C, a receiving module 2D, a second computing module 2E, an obtaining module 2F, and a determining module 2G.

[0103] Similarly, the computer program PROG3 defines via its instructions a number of functional modules of the computing device 3 able to implement the steps of the computing method and relying on the hardware elements 4-8 of the computing device 3. These functional modules in particular comprise, in the embodiment described here, as illustrated in FIG. 1, a receiving module 3A, a computing module 3B and a sending module 3C.

[0104] The functions of the different modules of the computing device 2 and of the computing device 3 are further specified below.

[0105] In another embodiment, one and/or the other of the computing devices 2 and 3 incorporate a silicon chip and means for communicating with the other devices of the cryptographic system 1 in particular. The silicon chip comprises transistors suitable for constituting logic gates of a non-programmable wired logic device for executing the steps of the determining method and/or the computing method according to the invention.

[0106] We will now describe, with reference to FIGS. 3 and 4, the main steps of the cryptographic comparison method according to the invention, in two particular embodiments. This cryptographic method relies on the steps of the determining method implemented by the computing device 2 (subsequently referred to in the description as Exx or Exx′) and on the steps of the computing method implemented by the computing device 3 (referred to in the rest of the description as Fxx or Fxx′). It makes it possible, as previously emphasized, for the computing device 2 to determine the position of the secret data x and y with respect to one another without the computing device 2 and the computing device 3 having to reveal the secret datum x or y that it possesses, and does this in only two passes of exchanges between these two devices.

[0107] The two embodiments illustrated in FIGS. 3 and 4 correspond to two different versions of the cryptographic comparison method which take into account the public or secret nature of one of the parameters of the method, and more particularly of the element g further described below.

[0108] Thus, FIG. 3 represents the main steps of the cryptographic comparison method according to the invention in a first embodiment in which the element g is public.

[0109] In accordance with the invention, the computing device 2, via its generating module 2A, generates an RSA module denoted N (step E10), the product of two natural integers (i.e. belonging to the set N of positive or non-zero integers) p and q, which are primes, and which the computing device 2 keeps secret. The term “secret” is understood to mean in this description that the computing device 2 does not make the element in question public and in particular that the computing device 3 does not have knowledge of it (and conversely when an element is kept secret by the computing device 3).

[0110] In the embodiment described here, the computing device 2, for example by way of its generating module 2A, further chooses natural integers denoted a, b, d, and f here verifying the following conditions (step E20): [0111] a≤d and b.sup.a>2.sup.z where z denotes a predetermined security parameter. For example, z=128 to comply with the security recommendations recommended in the document titled “Recommendation for Key Management”, NIST Special Publication 800-57 Part 1 Revision 4; [0112] the data x and y to be compared are less than d/a; and [0113] f is prime with b.

[0114] Note that the first condition is optional and has the aim of guaranteeing a level of security given to the secure comparison carried out using the invention (corresponding to the value of the parameter z chosen).

[0115] It is supposed that the RSA module N as well as the integers a, b, and d are made public by the computing device 2 (and therefore in particular shared with the computing device 3).

[0116] The integer f is however kept secret by the computing device 2.

[0117] Note that it is still possible reduce the data to be compared to less than

[00001]$\frac{d}{a}.$

If this is not the case of the data initially considered, these can be segmented into several blocks each representing an integer less than

[00002]$\frac{d}{a},$

for example similar or identical to that described in the document by Carlton and al. previously cited. The comparison of the initial data is then made by the pairwise comparison of the data corresponding to each block in accordance with the invention.

[0118] In a variant, the integers a, b, and d can be chosen by another entity than the computing device 2 and be made public by this entity so that the computing devices 2 and 3 have knowledge thereof.

[0119] The computing device 2 also selects, here still by way of its generating module 2A, an element g of a sub-group G of .sub.N of order b.sup.d and an element h of a sub-group H of .sub.N of order f (step E30). Thus, by definition, the elements g and h verify the following equalities:

g.sup.b.sup.d mod N=1

h.sup.f mod N=1

where mod means modulo.

[0120] In the first embodiment described here, as mentioned previously, the element g is public, and therefore shared by the computing device 2 with the computing device 3. The element h is however kept secret by the computing device 3, particularly with regard to the computing device 2. It allows the first computing device 2 to mask its secret datum x, as detailed hereinafter.

[0121] The computing device 2 then computes, by means of its first computing module 2B, a number C defined by (step E40):

C=g.sup.b.sup.axh1

where h1 is an element of the sub-group H (consequently of order f).

[0122] Note that as the secret datum x is by definition less than d/a, the number C is sure to not have a value of one, which makes it possible to ensure the correct operation of the protocol.

[0123] In the example envisioned here, the first computing module 2B chooses h1 equal to h.sup.r1 where r1 is a natural integer chosen at random by the first computing module 2B. Of course this example is only given by way of illustration. The random integer r1 is kept secret by the computing device 2 with regard to the computing device 3. Note that for this purpose, it can be quite simply erased from the memory of the computing device 2 just after being used for the computation of the number C.

[0124] The computing device 2 then sends, via its sending module 2C and its communication means 8, the number C thus computed to the computing device 3 (step E50).

[0125] On receiving the number C via its receiving module 3A and its communication means 8 (step F10), the computing device 3 computes, by way of its computing module 3B, a number D equal to (step F20):

D=C.sup.u.Math.b.sup.d−ay(gh3).sup.vh2

where u and v denote two random natural integers, and h2 and h3 elements of the sub-group H.

[0126] In the first embodiment described here, h3=1 and h2=h.sup.r2 where r2 is a random natural integer chosen in the interval [0; b.sup.4z−1]. Note however that this example for the choice of h2 and h3 is only given by way of illustration, and is not limiting per se. In particular, in the first embodiment, given the public nature of the element g, by taking h3=1, it is chosen not to mask this element for the sake of simplicity. However, this hypothesis is not limiting per se and other strategies can be envisioned.

[0127] Note that the choice of the interval [0; b.sup.4z−1] for selecting the unknown r2 is not limiting per se and other intervals may be envisioned. This interval does however make it possible to guarantee a certain security of the comparison method, compatible with the recommendations made in the document “Recommendation for Key Management”, mentioned previously.

[0128] The random integers u, v, and r2 are kept secret by the computing device 2 with regard to the computing device 3. Note that for this purpose, like the unknown r1 previously, they can be quite simply erased from the memory of the computing device 3 just after being used for the computation of the number D.

[0129] In the first embodiment described here wherein the element g is public and h3=1, the number D computed by the computing module 3B is therefore defined in an equivalent manner by:

D=C.sup.u.Math.b.sup.d−ayg.sup.vh.sup.r2

[0130] The computing module 3B also computes, during the step F20, a fingerprint denoted E1 (first fingerprint withing the meaning of the invention) of the number (gh3).sup.v=g.sup.v using, in a manner known per se, a hash function denoted HASH. Such a function is known to those skilled in the art and is not described in further detail here. Examples of hash functions are the functions SHA 256 and SHA 512 as defined in the document “Secure Hash Standard”, FIPS PUB 180-4 published in August 2015 by the NIST.

[0131] More particularly, to compute the fingerprint E1, the computing module 3B here directly applies the hash function HASH on the number g.sup.v, i.e.:

E1=HASH(g.sup.v)

[0132] Then the computing device 3 sends, via its sending module 3C and its communicating means 8, the number D and the fingerprint E1 to the computing device 2 (step F30).

[0133] Note that the sending steps E50 and F30 respectively constitute a first and a second pass between the computing devices 2 and 3 of the comparing method according to the invention.

[0134] On receiving the number D and the fingerprint E1 via its receiving module 2D and its communication means 8 (step E60), the computing device 2 performs various mathematic manipulations on the number D via its second computing module 2E for computing a fingerprint E2 (second fingerprint within the meaning of the invention), which it can compare with the fingerprint E1 supplied by the second computing device 3 to determine if x is greater than or equal to y or if x is less than y.

[0135] More specifically, the second computing module 2E first raises the number D to the power f, f denoting, as a reminder, the order of the elements of the sub-group of H (step E70). It then obtains:

D.sup.f=(C.sup.u.Math.b.sup.d−ayg.sup.vh.sup.r2).sup.f

i.e. by replacing C by g.sup.b.sup.axh.sup.r1 and writing (g.sup.n1).sup.n2=g.sup.n1.Math.n2=(g.sup.n2).sup.n1 if n1 and n2 denote two numbers:

D.sup.f=(g.sup.f).sup.ub.sup.d+ax−ay+v(h.sup.f).sup.r1ub.sup.d−ay.sup.+r2

[0136] The element h being of order f, this means that h.sup.f=1, in other words, after the computing step E70, the second computing module 2E obtains the number Dr which can be written in the form:

D.sup.f=(g).sup.ub.sup.d+ax−ay.sup.+v

[0137] The raising to the power f of the number D also allows the second computing module 2E to eliminate the h terms of the number D, or more generally all the elements contained in the number D belonging to the sub-group H. In other words here, it removes from the number D all the h elements raised to a certain power by relying on the knowledge of the order f elements of the sub-group H. Note that the order f elements of the sub-group H can, in a known manner, be obtained on the basis of the prime numbers p and q of the RSA module N (and more precisely the factorization of p−1 and q−1).

[0138] The second computing module 2E then raises the result obtained for the computation of Dr to the power f′ where f′ denotes the inverse of f modulo b.sup.d (step E80). In other words:

ff′=1 mod b.sup.d

[0139] It then obtains a result that can be written in the form:

(D.sup.f).sup.f′=((g.sup.f).sup.ub.sup.d+ax−ay.sup.+v).sup.f′=(g.sup.f,f′).sup.ub.sup.d+ax−ay.sup.+v=g.sup.ub.sup.d+ax−ay.sup.+v

[0140] Then the obtaining module 2F of the computing device 2 computes a fingerprint, denoted E2 of the result obtained using the hash function HASH (step E90), i.e.:

E2=HASH((D.sup.f).sup.f′)

which can be written in an equivalent manner in the form:

E2=HASH(g.sup.ub.sup.d+ax−ay.sup.+v)  (1)

[0141] Note that the computing step E80 can be carried out interchangeably by the computing module 2E or by the obtaining module 2F of the computing device 2.

[0142] By relying on the relationship (1) above, the comparing module 2G of the computing device 2 compares the fingerprints E1 and E2 (step E100), and as a function of the result of the comparison determines how the secret datum x is situated with respect to the secret datum y without the first and the second device needing to reveal the data x and y. More precisely, the comparing module 2G determines here, with the conventions adopted, that: [0143] x is greater than or equal to y if E1=E2; or that [0144] x is less than y if E1≠E2.

[0145] Specifically, starting from the relationship (1), it appears that if x is greater than or equal to y, then d+ax−ay≤d and the term g.sup.ub.sup.d+ax−ay.sup.+v reduces to g.sup.v, g being of order b.sup.d. Computing the fingerprint E2 therefore equates to computing the fingerprint g.sup.v, which by definition corresponds to the fingerprint E1 computed and transmitted by the computing device 3.

[0146] Conversely, the relationship (1), if x is less than y, it cannot be concluded that g.sup.ub.sup.d+ax−ay.sup.+v=1. But the collision resistance property of the hash functions, which ensures that two fingerprints of separate values have a negligible probability of being equal, does however make it possible to conclude that if E1≠E2, this means that x is indeed less than y.

[0147] In the first embodiment described here, we have supposed that the element g selected by the computing device 2 is public, and known to the computing device 3. FIG. 4 represents the main steps of the cryptographic comparison method according to the invention in a second embodiment wherein the element g is kept secret by the computing device 2 and is therefore not known to the computing device 3. In FIG. 4, the steps of the second embodiment which are identical to those of the first embodiment are given the same reference number and will not be described again in detail.

[0148] In the second embodiment as in the first embodiment, the computing device 2, via its generating module 2A, generates an RSA module denoted N (step E10), the product of two mutually prime natural integers p and q and which the computing device 2 keeps secret.

[0149] The computing device 2 moreover chooses natural integers denoted a, b, d, and f verifying the following hypotheses (step E20): [0150] a≤d and b.sup.a>2.sup.z where z denotes a predetermined security parameter (integer). For example z=128 to comply with the security recommendations in the document titled “Recommendation for Key Management”, NIST Special Publication 800-57 Part 1 Revision 4; [0151] the data x and y to be compared are less than d/a; and [0152] f is prime with b.

[0153] The RSA module N and the integers a, b, and d are made public by the computing device 2 and the integer f is kept secret.

[0154] The computing device 2 also selects, here still by way of its generating module 2A, an element g of a sub-group G of .sub.N of order b.sup.d and an element h of a sub-group H of .sub.N of order f (step E30). By definition, the elements g and h verify the following equalities:

g.sup.b.sup.d mod N=1

h.sup.f mod N=1

where mod means modulo.

[0155] In the second embodiment, the element g is kept secret by the computing device 2 just like the element h. To take into account this restriction, the computing device 2, for example via its generating module 2A, generates on the basis of the element g an element h′ verifying the following relationship (step E35′):

h′=gh4.sup.e

where h4 is an element of the sub-group H, and e denotes an integer selected and kept secret by the computing device 2. In the example envisioned here, for the sake of simplicity, the generating module 2A takes h4=h, but this example is only given as an illustration.

[0156] Next, the computing device 2 computes, by means of its first computing module 2B, as in the first embodiment, the number C defined by (step E40):

C=g.sup.b.sup.axh1

where h1 is an element of the sub-group H (consequently of order f). In the example envisioned here, the first computing module 2B chooses h1 equal to h.sup.r1 where r1 is a natural integer chosen at random. The random integer r1 is kept secret by the computing device 2 with regard to the computing device 3 (for example by being quite simply erased from its memory after being used to compute C).

[0157] The computing device 2 then sends via its sending module 2C and its communication means 8 the number C and the number h′ to the computing device 3 (step E50′).

[0158] On receiving the numbers C and h′ via its receiving module 3A and its communication means 8 (step F10′), the computing device 3 computes as in the first embodiment, by way of its computing module 3B, a number D defined by (step F20′):

D=C.sup.u.Math.b.sup.d−ay(gh3).sup.vh2

where u and v denote two random natural integers, and h2 and h3 elements of the sub-group H. More specifically, in the second embodiment described here, for the sake of simplicity, the computing module 3B chooses h3=h4.sup.e(which allows it to directly reuse h′ received from the computing device 2) and h2=h.sup.r2 where r2 is a random integer chosen in the interval [0; b.sup.4z−1].

[0159] Note that the condition according to which the datum y is less than d/a guarantees that the computing device 3 is still capable of computing the element D.

[0160] The random integers u, v, and r2 are kept secret by the computing device 2 with regard to the computing device 3 as in the first embodiment.

[0161] In the second embodiment described here where the element g is secret and therefore not known to the computing device 3, the number D computed by the computing module 3B is therefore defined in an equivalent manner by:

D=C.sup.u.Math.b.sup.d−ay(gh4.sup.e).sup.vh.sup.r2

[0162] Moreover, in the second embodiment, the computing module 3B also computes in the step F20 a fingerprint denoted E1′ (first fingerprint within the meaning of the invention) of the number (gh3).sup.v=(gh4.sup.e).sup.v using a hash function HASH. More specifically, the computing module 3B computes the fingerprint E1′ by directly applying the hash function HASH to the number (gh4.sup.e).sup.v that it has received from the computing device 2, i.e.:

E1′=HASH((gh4.sup.e).sup.v)

[0163] In this second embodiment, to “compensate” for the fact that the element g is kept secret by the computing device 2, the computing device 3 computes an additional number, denoted D1. As will be described in more detail below, this number D1 is intended to allow the computing device 2 to compute a second fingerprint comparable with the fingerprint E1′ without knowing the unknown v which allows it to determine the order of the secret data x and y. More precisely, in the example envisioned here where h3=h4.sup.e, the number D1 is defined by:

D1=h4.sup.v;

[0164] Then the computing device 3 sends, via its sending module 3C and its communication means 8, the numbers D and D1, and the fingerprint E1′ to the computing device 2 (step F30′).

[0165] On receiving the numbers D and D1 as well as the fingerprint E1 via its receiving module 2D and its communication means 8 (step E60′), the computing device 2 performs various mathematical manipulations on the number D via its second computing module 2E to compute a fingerprint E2′ (second fingerprint within the sense of the invention), that it can compare with the fingerprint E1′ supplied by the second computing device 3 to determine if x is greater than or equal to y or if x is less than y.

[0166] More specifically, the second computing module 2E first raises the number D to the power f, f denoting as a reminder the order of the elements of the sub-group of H (step E70′). It then obtains:

D.sup.f=(C.sup.u.Math.b.sup.d−ay(gh4.sup.e).sup.vh.sup.r2).sup.f

either by replacing C by h.sup.r1 and by writing (g.sup.n1).sup.n2=g.sup.n1.Math.n2=(g.sup.n2).sup.n1 if n1 and n2 denote two integer numbers:

D.sup.f=(g.sup.f).sup.ub.sup.d+ax−ay.sup.+v(h.sup.f).sup.r1ub.sup.d−ay.sup.+r2+ev

[0167] The element h being of order f this means that h.sup.f=1, in other words, after the computing step E70, the second computing module 2E obtains the number D.sup.f which can be written in the form:

D.sup.f=(g.sup.f).sup.ub.sup.d+ax−ay.sup.+v

[0168] The raising to the power f of the number D thus allows the second computing module 2E to eliminate the h terms in the number D, or more generally all the elements contained in the number D belonging to the sub-group H.

[0169] As in the first embodiment, the second computing module 2E then raises the result obtained for the computation of Dr to the power f′ where f′ denotes the inverse of f modulo b.sup.d (step E80′). In other words:

ff′=1 mod b.sup.d

[0170] It then obtains a result that can be written in the form:

(D.sup.f).sup.f′=((g.sup.f).sup.ub.sup.d+ax−ay.sup.+v).sup.f′=(g.sup.f.Math.f′).sup.ub.sup.d+ax−ay.sup.+v=g.sup.ub.sup.d+ax−ay.sup.+v

[0171] Then the second computing module 2E multiplies the result obtained for (D.sup.f).sup.f′ by the number (D1).sup.e (step E90′). This multiplication allows the computing device 2 to compensate for the lack of knowledge by the computing device 3 of the element g and to take into account the fingerprint computed thereby, no longer on the element g.sup.v as in the first embodiment, but on the element (gh4.sup.e).sup.v=(gh.sup.e).sup.v.

[0172] Then the obtaining module 2F of the computing device 2 computes a fingerprint, denoted E2′ by applying the hash function HASH to the result obtained (step E95′), i.e.

E2′=HASH((D.sup.f).sup.f′(D1).sup.e)

which can be written in an equivalent manner in the form:

E2′=HASH(g.sup.ub.sup.d+ax−ay(gh.sup.e).sup.v)  (2)

[0173] By relying on the relationship (2) above, the comparing module 2G of the computing device 2 compares the fingerprints E1′ and E2′ (step E100′), and as a function of the result of the comparison determines how the secret datum x is situated with respect to the secret datum y without the first and the second device needing to reveal the data x and y. More precisely, the comparing module 2G here determines, with the conventions adopted, that: [0174] x is greater than or equal to y if E1′=E2′; or that [0175] x is less than y if E1′≠E2′.

[0176] Specifically, starting from the relationship (2), it appears that if x is greater than or equal to y, then d+ax−ay≥d and the term g.sup.ub.sup.d+ax−ay reduces to 1, g being of order b.sup.d. Computing the fingerprint E2′ therefore equates to computing the fingerprint of (gh.sup.e).sup.v, which by definition corresponds to the fingerprint E1′ computed and transmitted by the computing device 3.

[0177] Conversely, the relationship (2), if x is less than y, it cannot be concluded that g.sup.ub.sup.d+ax−a=1. But the collision resistance property of the hash functions, which ensures that two fingerprints of separate values have a negligible probability of being equal, does however make it possible to conclude that if E1′≠E2′, this means that x is indeed less than y.

[0178] In the preceding description, two embodiments are envisioned according to whether the element g is kept secret or not by the computing device 2. Note that the choice to keep g secret or otherwise can have consequences on the different parameters of the comparison method and on its efficiency.

[0179] By way of illustration, in the first embodiment where the element g is public, the guarantee of a certain level of security, typically that recommended by the recommendations mentioned previously, can impose certain conditions on the choice of the parameters. Thus, for example, it is preferable to make sure that b.sup.d<N.sup.1/4, which can limit the value of the integer d, and therefore correspondingly the size of the secret data x and y that can be compared.

[0180] In the second embodiment where the element g is kept secret, the restriction on the integer d to achieve a similar level of security is less heavy, i.e. it is preferable to make sure that b.sup.d.2.sup.256<N.sup.1/2. But it is also preferable in this case that the prime integers p and q chosen by the computing device 2 to generate the RSA module N are of sufficient size, for example 3072 bits, which is double the standard size of the integers generally considered for generating an RSA module. With comparable parameters, this second embodiment therefore makes it possible to process numbers twice as large as the first embodiment but entails more computation than the first embodiment.

[0181] The choice of keeping the element g secret or not is thus a result of a trade-off between security, the size of the data that can be compared and computational complexity.