# US 12,192,354 B2 · Cryptographic method of secure comparison of two secret data x and y > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,192,354 B2 - Document ID: US12192354B2 - Status: Granted - Kind: B2 - Application number: 17/278,861 - Filed: 2019-09-20 - Published: 2022-02-03 - Granted: 2025-01-07 - Earliest claimed: 2018-09-24 - Assignees: Orange - Applicants: Orange - Inventors: Florian Bourse; Olivier Sanders; Jacques Traore - Web page: https://patentgrep.com/patent/US12192354B2 ## CPC - H04L 9/00: {Cryptographic mechanisms or cryptographic} arrangements for secret or secure communications; Network security protocols - H04L 9/302: {involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes} - H04L 9/0643: {Hash functions, e.g. MD5, SHA, HMAC or f9 MAC} - H04L 2209/046: of operations, operands or results of the operations - H04L 2209/46: Secure multiparty computation, e.g. millionaire problem - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## 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=gbaxh1, g being an element of sub-group G of order bd, 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=Cu·bd−ay(gh3)vh2, 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 (Df)f′, f′=1/f; obtaining based on (Df)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 ### Claim 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 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 1) 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 (Df)f′ computed. ### Claim 4 (depends on 2) The cryptographic method as claimed in claim 2 wherein: g is an element kept secret by the first computing device and h3=h4e 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 h4v; and the second fingerprint is obtained by applying the hash function to the number (Df)f′ computed, multiplied by D1e. ### Claim 5 (depends on 1) The cryptographic method as claimed in claim 1 wherein the integer a is chosen less than or equal to the integer d, and ba>2z where z denotes a predetermined security parameter. ### Claim 6 (depends on 1) The cryptographic method as claimed in claim 1 wherein the integer u is chosen at random in the interval [0; ba−1] and the integer v is chosen at random in the interval [0; bd−1]. ### Claim 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 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. ### Claim 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 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. ### Claim 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 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. ### Claim 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 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. ### Claim 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 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. ### Claim 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 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. ### Claim 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 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.