Patent ID: 12192354

DETAILED DESCRIPTION OF THE INVENTION

FIG.1represents, in its environment, a cryptographic system1in accordance with the invention, in a particular embodiment.

The cryptographic system1is designed so as to allow the production of two integer data x and y respectively possessed by two separate entities2and3while 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 system1without the entity2needing to reveal to the entity3the datum x and conversely, without the entity3needing to reveal to the entity2the datum y.

Here the two entities2and3are computing devices in accordance with the invention. In the example illustrated inFIG.1, the entity2is 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 entity3is a “second” computing device within the meaning of the invention.

No limitation is attached to the context in which the cryptographic system1and correspondingly the two entities2and3are 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.)

In the example envisioned inFIG.1, the computing devices2and3are computers, the architecture of which is schematically illustrated inFIG.2.

Each computing device comprises in particular a processor4, a read-only memory5, a random-access memory6, a non-volatile memory7(in which is stored for example the secret datum x for the computing device2and y for the computing device3) and communication means8. The communication means8allow the devices2and3to 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.

The read-only memory5of the computing device2and the computing device3constitutes a recording medium in accordance with the invention, readable by the processor4and on which is recorded a computer program PROG2 and PROG3 respectively, in accordance with the invention, respectively including, for the computing device2, instructions for executing the steps of the determining method according to the invention and for the computing device3instructions for executing the steps of the computing method according to the invention.

More precisely, the computer program PROG2 defines via its instructions a number of functional modules of the computing device2able to implement the steps of the determining method and relying on the hardware elements4-8of the computing device2. These functional modules in particular comprise, in the embodiment described here, as illustrated inFIG.1, a generating module2A, a first computing module2B, a sending module2C, a receiving module2D, a second computing module2E, an obtaining module2F, and a determining module2G.

Similarly, the computer program PROG3 defines via its instructions a number of functional modules of the computing device3able to implement the steps of the computing method and relying on the hardware elements4-8of the computing device3. These functional modules in particular comprise, in the embodiment described here, as illustrated inFIG.1, a receiving module3A, a computing module3B and a sending module3C.

The functions of the different modules of the computing device2and of the computing device3are further specified below.

In another embodiment, one and/or the other of the computing devices2and3incorporate a silicon chip and means for communicating with the other devices of the cryptographic system1in 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.

We will now describe, with reference toFIGS.3and4, 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 device2(subsequently referred to in the description as Exx or Exx′) and on the steps of the computing method implemented by the computing device3(referred to in the rest of the description as Fxx or Fxx′). It makes it possible, as previously emphasized, for the computing device2to determine the position of the secret data x and y with respect to one another without the computing device2and the computing device3having to reveal the secret datum x or y that it possesses, and does this in only two passes of exchanges between these two devices.

The two embodiments illustrated inFIGS.3and4correspond 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.

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

In accordance with the invention, the computing device2, via its generating module2A, 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 device2keeps secret. The term “secret” is understood to mean in this description that the computing device2does not make the element in question public and in particular that the computing device3does not have knowledge of it (and conversely when an element is kept secret by the computing device3).

In the embodiment described here, the computing device2, for example by way of its generating module2A, further chooses natural integers denoted a, b, d, and f here verifying the following conditions (step E20):a≤d and ba>2zwhere 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;the data x and y to be compared are less than d/a; andf is prime with b.

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).

It is supposed that the RSA module N as well as the integers a, b, and d are made public by the computing device2(and therefore in particular shared with the computing device3).

The integer f is however kept secret by the computing device2.

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

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

da,
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.

In a variant, the integers a, b, and d can be chosen by another entity than the computing device2and be made public by this entity so that the computing devices2and3have knowledge thereof.

The computing device2also selects, here still by way of its generating module2A, an element g of a sub-group G ofNof order bdand an element h of a sub-group H ofNof order f (step E30). Thus, by definition, the elements g and h verify the following equalities:
gbdmodN=1
hfmodN=1
where mod means modulo.

In the first embodiment described here, as mentioned previously, the element g is public, and therefore shared by the computing device2with the computing device3. The element h is however kept secret by the computing device3, particularly with regard to the computing device2. It allows the first computing device2to mask its secret datum x, as detailed hereinafter.

The computing device2then computes, by means of its first computing module2B, a number C defined by (step E40):
C=gbaxh1
where h1 is an element of the sub-group H (consequently of order f).

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.

In the example envisioned here, the first computing module2B chooses h1 equal to hr1where r1 is a natural integer chosen at random by the first computing module2B. Of course this example is only given by way of illustration. The random integer r1 is kept secret by the computing device2with regard to the computing device3. Note that for this purpose, it can be quite simply erased from the memory of the computing device2just after being used for the computation of the number C.

The computing device2then sends, via its sending module2C and its communication means8, the number C thus computed to the computing device3(step E50).

On receiving the number C via its receiving module3A and its communication means8(step F10), the computing device3computes, by way of its computing module3B, a number D equal to (step F20):
D=Cu·bd−ay(gh3)vh2
where u and v denote two random natural integers, and h2 and h3 elements of the sub-group H.

In the first embodiment described here, h3=1 and h2=hr2where r2 is a random natural integer chosen in the interval [0; b4z−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.

Note that the choice of the interval [0; b4z−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.

The random integers u, v, and r2 are kept secret by the computing device2with regard to the computing device3. Note that for this purpose, like the unknown r1 previously, they can be quite simply erased from the memory of the computing device3just after being used for the computation of the number D.

In the first embodiment described here wherein the element g is public and h3=1, the number D computed by the computing module3B is therefore defined in an equivalent manner by:
D=Cu·bd−aygvhr2

The computing module3B also computes, during the step F20, a fingerprint denoted E1 (first fingerprint withing the meaning of the invention) of the number (gh3)v=gvusing, 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.

More particularly, to compute the fingerprint E1, the computing module3B here directly applies the hash function HASH on the number gv, i.e.:
E1=HASH(gv)

Then the computing device3sends, via its sending module3C and its communicating means8, the number D and the fingerprint E1 to the computing device2(step F30).

Note that the sending steps E50and F30respectively constitute a first and a second pass between the computing devices2and3of the comparing method according to the invention.

On receiving the number D and the fingerprint E1 via its receiving module2D and its communication means8(step E60), the computing device2performs various mathematic manipulations on the number D via its second computing module2E 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 device3to determine if x is greater than or equal to y or if x is less than y.

More specifically, the second computing module2E 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:
Df=(Cu·bd−aygvhr2)f
i.e. by replacing C by gbaxhr1and writing (gn1)n2=gn1·n2=(gn2)n1if n1 and n2 denote two numbers:
Df=(gf)ubd+ax−ay+v(hf)r1ubd−ay+r2

The element h being of order f, this means that hf=1, in other words, after the computing step E70, the second computing module2E obtains the number Dr which can be written in the form:
Df=(g)ubd+ax−ay+v

The raising to the power f of the number D also allows the second computing module2E 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).

The second computing module2E then raises the result obtained for the computation of Dr to the power f′ where f′ denotes the inverse of f modulo bd(step E80). In other words:
ff′=1 modbd

It then obtains a result that can be written in the form:
(Df)f′=((gf)ubd+ax−ay+v)f′=(gf,f′)ubd+ax−ay+v=gubd+ax−ay+v

Then the obtaining module2F of the computing device2computes a fingerprint, denoted E2 of the result obtained using the hash function HASH (step E90), i.e.:
E2=HASH((Df)f′)
which can be written in an equivalent manner in the form:
E2=HASH(gubd+ax−ay+v)  (1)

Note that the computing step E80can be carried out interchangeably by the computing module2E or by the obtaining module2F of the computing device2.

By relying on the relationship (1) above, the comparing module2G of the computing device2compares 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 module2G determines here, with the conventions adopted, that:x is greater than or equal to y if E1=E2; or thatx is less than y if E1≠E2.

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 gubd+ax−ay+vreduces to gv, g being of order bd. Computing the fingerprint E2 therefore equates to computing the fingerprint gv, which by definition corresponds to the fingerprint E1 computed and transmitted by the computing device3.

Conversely, the relationship (1), if x is less than y, it cannot be concluded that gubd+ax−ay=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.

In the first embodiment described here, we have supposed that the element g selected by the computing device2is public, and known to the computing device3.FIG.4represents 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 device2and is therefore not known to the computing device3. InFIG.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.

In the second embodiment as in the first embodiment, the computing device2, via its generating module2A, generates an RSA module denoted N (step E10), the product of two mutually prime natural integers p and q and which the computing device2keeps secret.

The computing device2moreover chooses natural integers denoted a, b, d, and f verifying the following hypotheses (step E20):a≤d and ba>2zwhere 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;the data x and y to be compared are less than d/a; andf is prime with b.

The RSA module N and the integers a, b, and d are made public by the computing device2and the integer f is kept secret.

The computing device2also selects, here still by way of its generating module2A, an element g of a sub-group G ofNof order bdand an element h of a sub-group H ofNof order f (step E30). By definition, the elements g and h verify the following equalities:
gbdmodN=1
hfmodN=1
where mod means modulo.

In the second embodiment, the element g is kept secret by the computing device2just like the element h. To take into account this restriction, the computing device2, for example via its generating module2A, generates on the basis of the element g an element h′ verifying the following relationship (step E35′):
h′=gh4e
where h4 is an element of the sub-group H, and e denotes an integer selected and kept secret by the computing device2. In the example envisioned here, for the sake of simplicity, the generating module2A takes h4=h, but this example is only given as an illustration.

Next, the computing device2computes, by means of its first computing module2B, as in the first embodiment, the number C defined by (step E40):
C=gbaxh1
where h1 is an element of the sub-group H (consequently of order f). In the example envisioned here, the first computing module2B chooses h1 equal to hr1where r1 is a natural integer chosen at random. The random integer r1 is kept secret by the computing device2with regard to the computing device3(for example by being quite simply erased from its memory after being used to compute C).

The computing device2then sends via its sending module2C and its communication means8the number C and the number h′ to the computing device3(step E50′).

On receiving the numbers C and h′ via its receiving module3A and its communication means8(step F10′), the computing device3computes as in the first embodiment, by way of its computing module3B, a number D defined by (step F20′):
D=Cu·bd−ay(gh3)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 module3B chooses h3=h4e(which allows it to directly reuse h′ received from the computing device2) and h2=hr2where r2 is a random integer chosen in the interval [0; b4z−1].

Note that the condition according to which the datum y is less than d/a guarantees that the computing device3is still capable of computing the element D.

The random integers u, v, and r2 are kept secret by the computing device2with regard to the computing device3as in the first embodiment.

In the second embodiment described here where the element g is secret and therefore not known to the computing device3, the number D computed by the computing module3B is therefore defined in an equivalent manner by:
D=Cu·bd−ay(gh4e)vhr2

Moreover, in the second embodiment, the computing module3B also computes in the step F20a fingerprint denoted E1′ (first fingerprint within the meaning of the invention) of the number (gh3)v=(gh4e)vusing a hash function HASH. More specifically, the computing module3B computes the fingerprint E1′ by directly applying the hash function HASH to the number (gh4e)vthat it has received from the computing device2, i.e.:
E1′=HASH((gh4e)v)

In this second embodiment, to “compensate” for the fact that the element g is kept secret by the computing device2, the computing device3computes an additional number, denoted D1. As will be described in more detail below, this number D1 is intended to allow the computing device2to 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=h4e, the number D1 is defined by:
D1=h4v;

Then the computing device3sends, via its sending module3C and its communication means8, the numbers D and D1, and the fingerprint E1′ to the computing device2(step F30′).

On receiving the numbers D and D1 as well as the fingerprint E1 via its receiving module2D and its communication means8(step E60′), the computing device2performs various mathematical manipulations on the number D via its second computing module2E 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 device3to determine if x is greater than or equal to y or if x is less than y.

More specifically, the second computing module2E 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:
Df=(Cu·bd−ay(gh4e)vhr2)f
either by replacing C by hr1and by writing (gn1)n2=gn1·n2=(gn2)n1if n1 and n2 denote two integer numbers:
Df=(gf)ubd+ax−ay+v(hf)r1ubd−ay+r2+ev

The element h being of order f this means that hf=1, in other words, after the computing step E70, the second computing module2E obtains the number Dfwhich can be written in the form:
Df=(gf)ubd+ax−ay+v

The raising to the power f of the number D thus allows the second computing module2E 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.

As in the first embodiment, the second computing module2E then raises the result obtained for the computation of Dr to the power f′ where f′ denotes the inverse of f modulo bd(step E80′). In other words:
ff′=1 modbd

It then obtains a result that can be written in the form:
(Df)f′=((gf)ubd+ax−ay+v)f′=(gf·f′)ubd+ax−ay+v=gubd+ax−ay+v

Then the second computing module2E multiplies the result obtained for (Df)f′ by the number (D1)e(step E90′). This multiplication allows the computing device2to compensate for the lack of knowledge by the computing device3of the element g and to take into account the fingerprint computed thereby, no longer on the element gvas in the first embodiment, but on the element (gh4e)v=(ghe)v.

Then the obtaining module2F of the computing device2computes a fingerprint, denoted E2′ by applying the hash function HASH to the result obtained (step E95′), i.e.
E2′=HASH((Df)f′(D1)e)
which can be written in an equivalent manner in the form:
E2′=HASH(gubd+ax−ay(ghe)v)  (2)

By relying on the relationship (2) above, the comparing module2G of the computing device2compares 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 module2G here determines, with the conventions adopted, that:x is greater than or equal to y if E1′=E2′; or thatx is less than y if E1′≠E2′.

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 gubd+ax−ayreduces to 1, g being of order bd. Computing the fingerprint E2′ therefore equates to computing the fingerprint of (ghe)v, which by definition corresponds to the fingerprint E1′ computed and transmitted by the computing device3.

Conversely, the relationship (2), if x is less than y, it cannot be concluded that gubd+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.

In the preceding description, two embodiments are envisioned according to whether the element g is kept secret or not by the computing device2. 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.

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 bd<N1/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.

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 bd·2256<N1/2. But it is also preferable in this case that the prime integers p and q chosen by the computing device2to 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.

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.