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

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 gbaxh1 where g is an element of a sub-group G of N of order bd, 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 Cu·bd−ay(gh3)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)v computed using a hash function;
• compute a number (Df)f′ where f′ is the inverse of f modulo bd;
• obtain on the basis of the number (Df)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.

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 gbaxh1 where g is an element of a sub-group G of N of order bd, 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 Cu·bd−ay(gh3)vh2 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.

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 gbaxh1 where g is an element of a sub-group G of N of order bd, 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 Cu·bd−ay(gh3)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)v computed using a hash function;
• computing, by the first computing device, the number (Df)f′ where f′ is the inverse of f modulo bd;
• obtaining, by the first computing device, on the basis of the number (Df)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.

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 gbaxh1 where g is an element of a sub-group G of N of order bd, 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 Cu·bd−ay(gh3)vh2 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.

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 gbaxh1 where g is an element of a sub-group G of N of order bd, 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 Cu·bd−ay(gh3)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)v computed using a hash function;
• compute a number (Df)f′ where f′ is the inverse of f modulo bd;
• obtain on the basis of the number (Df)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.

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 gbayh1 where g is an element of a sub-group G of N of order bd, 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 Cu·bd−ay(gh3)vh2 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.

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 gbaxh1 where g is an element of a sub-group G of N of order bd, 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 Cu·bd−ay(gh3)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)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 (Df)f′ where f′ is the inverse of f modulo bd;
• obtaining, by the first computing device, on the basis of the number (Df)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.