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 b ax h1, g being an element of sub-group G of order b 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 u·b d−ay (gh3) v h2, u and v being random numbers and h2 and h3 being elements of H, and a first fingerprint (gh3) v ; sending to the first device, D and the first fingerprint; computing by the first device (D f ) f ′, f′=1/f; obtaining based on (D f ) 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.

The invention claimed is: 
     
       1. A cryptographic method of securely comparing two secret integer 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, a Rivest Shamir Adleman (RSA) module denoted N; 
 computing, by the first computing device, a number C equal to g b     ax   h1 where g is an element of a sub-group G of    N  of order b d , h1 is an element of a sub-group H of    N  of order f, 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 u·b     d−ay   (gh3) v h2 where u and v denote two random integers, and h2 and h3 elements of the sub-group H; and 
 a first fingerprint of (gh3) 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 f ) f ′ where f′ is the inverse of f modulo b d ; 
 obtaining, by the first computing device, on the basis of the number (D f ) f ′ computed, a second fingerprint using the hash function; and 
 determining, by the first computing device, that the data x is greater than or equal to the data y or that the data x is less than the data y as a function of the result of a comparison between the first fingerprint and the second fingerprint and without revealing the data x to the second computing device and the data y to the first computing device. 
 
     
     
       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; and 
 the second fingerprint is obtained by applying the hash function to the number (D f ) 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 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·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 v ; and 
 the second fingerprint is obtained by applying the hash function to the number (D f ) f ′ computed, multiplied by D1 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 a >2 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 a −1] and the integer v is chosen at random in the interval [0; b 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: 
 generates a Rivest Shamir Adleman (RSA) module denoted N; 
 compute a number C equal to g b     ax   h1 where g is an element of a sub-group G of    N  of order b d , h1 is an element of a sub-group H of    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 u·b     d−ay   (gh3) v h2 where u and v denote two random integers, and h2 and h3 elements of the sub-group H; and 
 a first fingerprint of (gh3) v  computed using a hash function; 
 compute a number (D f ) f ′ where f′ is the inverse of f modulo b d ; 
 obtain on the basis of the number (D f ) 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 and without possessing the data y and without revealing the data x to the second computing device. 
 
     
     
       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 computing device to: 
 receive from a first computing device possessing and keeping secret an integer datum x, a number C equal to g b     ax   h1 where g is an element of a sub-group G of    N  of order b d , h1 is an element of a sub-group H of    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 u·b     d−ay   (gh3) v h2 where u and v denote two random integers, and h2 and h3 elements of the sub-group H; and 
 a fingerprint of (gh3) v  computed using a hash function; and 
 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 a Rivest Shamir Adleman (RSA) module denoted N; 
 computing a number C equal to g b     ax   h1 where g is an element of a sub-group G of    N  of order b d , h1 is an element of a sub-group H of    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 u·b     d−ay   (gh3) v h2 where u and v denote two random integers, and h2 and h3 elements of the sub-group H; and 
 a first fingerprint of (gh3) v  computed using a hash function; 
 
 computing, by the first computing device, the number (D f ) f ′ where f′ is the inverse of f modulo b d ; 
 obtaining, by the first computing device, on the basis of the number (D f ) 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 and without possessing the data y and without revealing the data x to the second computing device. 
 
     
     
       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 b     ax   h1 where g is an element of a sub-group G of    N  of order b d , h1 is an element of a sub-group H of    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 u·b     d−ay   (gh3) v h2 where u and v denote two random integers, and h2 and h3 elements of the sub-group H; and 
 a fingerprint o(gh3) v  computed using a hash function; and 
 
 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:
 generates a Rivest Shamir Adleman (RSA) module denoted N; 
 compute a number C equal to g b     ax   h1 where g is an element of a sub-group G of    N  of order b d , h1 is an element of a sub-group H of    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 u·b     d−ay   (gh3) v h2 where u and v denote two random integers, and h2 and h3 elements of the sub-group H; and 
 a first fingerprint of (gh3) v  computed using a hash function; 
 
 compute a number (D f ) f ′ where f′ is the inverse of f modulo b d ; 
 obtain on the basis of the number (D f ) 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 and without possessing the data y and without revealing the data x to the second computing device. 
 
     
     
       12. 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 b     ay   h1 where g is an element of a sub-group G of    N  of order b d , h1 is an element of a sub-group H of    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 u·b     d−ay   (gh3) v h2 where u and v denote two random integers, and h2 and h3 elements of the sub-group H; and 
 a fingerprint of (gh3) v  computed using a hash function; and 
 
 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. 
 
     
     
       13. A data processing method of securely comparing two secret integer 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, a Rivest Shamir Adleman (RSA) module denoted N; 
 computing, by the first computing device, a number C equal to g b     ax   h1 where g is an element of a sub-group G of    N  of order b d , h1 is an element of a sub-group H of    N  of order f, 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 u·b     d−ay   (gh3) v h2 where u and v denote two random integers, and h2 and h3 elements of the sub-group H; and 
 a first fingerprint of (gh3) 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 f ) f ′ where f′ is the inverse of f modulo b d ; 
 obtaining, by the first computing device, on the basis of the number (D f ) f ′ computed, a second fingerprint using the hash function; and 
 determining, by the first computing device, that the data x is greater than or equal to the data y or that the data x is less than the data y as a function of the result of a comparison between the first fingerprint and the second fingerprint and without revealing the data x to the second computing device and the data y to the first computing device.