Secure multi-party equality testing

{
  "publication_number": "US2026106743A1",
  "country": "US",
  "kind": "A1",
  "title": "Secure multi-party equality testing",
  "abstract": "The present disclosure involves methods, apparatus, and systems for processing equality testing in secure multi-party computation (MPC). In one aspect, a method includes, generating, by a first party of the secure MPC, a difference between a secret share of a first value and a secret share of a second value. During a first iteration, the difference is partitioned into N sections each including M bits. For each section, a random integer is generated, a group of 2 M integers are generated based on the random integer, and a selected interger from the group of 2 M integers is sent to a second party of the secure MPC based on oblivious transfer protocol. The random integers of the N sections are added as an input of a second iteration. The method further includes determining whether the first value equals the second value based on results of a plurality of iterations.",
  "claims": [
    "1. A computer-implemented method, comprising: generating, by a first party of a secure multi-party computation (MPC), a first difference between a first secret share of a first value and a first secret share of a second value; during a first iteration of the secure MPC: partitioning the first difference into N sections each comprising M bits, where N and M are positive integers; for each section of the N sections: generating a random integer between 0 and N; generating, based on the random integer, a group of 2 M integers; and sending, to a second party of the secure MPC and based on oblivious transfer (OT) protocol, a selected integer from the group of 2 M integers; and adding random integers of the N sections as a first input of a second iteration of the secure MPC; and determining whether the first value equals the second value based on performing a plurality of iterations of the secure MPC comprising at least the first iteration and the second iteration. 2. The computer-implemented method of claim 1, comprising: adding, by the second party, selected integers of the N sections as a second input of the second iteration. 3. The computer-implemented method of claim 1, wherein generating the group of 2 M integers comprises: generating an m th integer, (m=0, 1, 2,..., 2 M −1), of the group of 2 M integers as (1{x i,j ≠m}−r)mod(N+1), where x i,j is a target section of the first difference, r is the random integer. 4. The computer-implemented method of claim 3, wherein the selected integer is the Q th integer of the group of 2 M integers, wherein Q equals a value of a target section of a second difference corresponding to the target section of the first difference, wherein the second difference is between a second secret share of the second value and a second secret share of the first value. 5. The computer-implemented method of claim 4, wherein: a sum of the random integer and the selected integer is a multiple of (N+1) when the value of the target section of the first difference and the value of the target section of the second difference are equal; and the sum of the random integer and the selected integer is not a multiple of (N+1) when the value of the target section of the first difference and the value of the target section of the second difference are not equal. 6. The computer-implemented method of claim 2, comprising: during the second iteration: partitioning the first input into R sections each comprising K bits, where R and K are positive integers; for each section of the R sections: generating a random bit; generating, based on the random bit, a group of 2 K bits; and sending, to the second party based on the OT protocol, a selected bit from the group of 2 K bits. 7. The computer-implemented method of claim 6, wherein generating the group of 2 K bits comprises: generating a k th bit, (k=0, 1, 2,..., 2 M −1), of the group of 2 K bits by performing an exclusive OR (XOR) operation on the random bit and an indicator bit, wherein the indicator bit is 0 when a value of the section equals k, and the indicator bit is 1 when the value of the section is not equal to k. 8. The computer-implemented method of claim 7, wherein the selected bit is the Qu bit of the group of 2 K bits, wherein Q equals a value of a section of a second input corresponding to the section of the first input. 9. The computer-implemented method of claim 1, wherein determining whether the first value and the second value are equal comprises: performing one or more AND operations on a first input and a second input of a last iteration of the plurality of iterations. 10. The computer-implemented method of claim 1, wherein the first secret share of the first value and the second secret share of the first value are arithmetic shares of the first value, and wherein the first secret share of the second value and the second secret share of the second value are arithmetic shares of the second value. 11. The computer-implemented method of claim 1, wherein the secure MPC is a secure two-party computation. 12. One or more computer-readable storage media storing one or more instructions that, when executable by one or more computers, cause the one or more computers to perform operations comprising: generating, by a first party of a secure multi-party computation (MPC), a first difference between a first secret share of a first value and a first secret share of a second value; during a first iteration of the secure MPC: partitioning the first difference into N sections each comprising M bits, where N and M are positive integers; for each section of the N sections: generating a random integer between 0 and N; generating, based on the random integer, a group of 2 M integers; and sending, to a second party of the secure MPC based on oblivious transfer (OT) protocol, a selected integer from the group of 2 M integers; and adding random integers of the N sections as a first input of a second iteration of the secure MPC; and determining whether the first value equals the second value based on performing a plurality of iterations of the secure MPC comprising at least the first iteration and the second iteration. 13. The one or more computer-readable storage media of claim 12, wherein the operations comprises: adding, by the second party, selected integers of the N sections as a second input of the second iteration. 14. The one or more computer-readable storage media of claim 12, wherein generating the group of 2 M integers comprises: generating an m th integer, (m=0, 1, 2,..., 2 M −1), of the group of 2 M integers as (1{x i,j ≠m}−r)mod(N+1), where x i,j is a target section of the first difference, r is the random integer. 15. The one or more computer-readable storage media of claim 14, wherein the selected integer is the Q th integer of the group of 2 M integers, wherein Q equals a value of a target section of a second difference corresponding to the target section of the first difference, wherein the second difference is between a second secret share of the second value and a second secret share of the first value. 16. The one or more computer-readable storage media of claim 15, wherein: a sum of the random integer and the selected integer is a multiple of (N+1) when the value of the target section of the first difference and the value of the target section of the second difference are equal; and the sum of the random integer and the selected integer is not a multiple of (N+1) when the value of the target section of the first difference and the value of the target section of the second difference are not equal. 17. The one or more computer-readable storage media of claim 13, wherein the operations comprises: during the second iteration: partitioning the first input into R sections each comprising K bits, where R and K are positive integers; for each section of the R sections: generating a random bit; generating, based on the random bit, a group of 2 K bits; and sending, to the second party based on the OT protocol, a selected bit from the group of 2 K bits. 18. The one or more computer-readable storage media of claim 17, wherein generating the group of 2 K bits comprises: generating a k th bit, (k=0, 1, 2,..., 2 M −1), of the group of 2 K bits by performing an exclusive OR (XOR) operation on the random bit and an indicator bit, wherein the indicator bit is 0 when a value of the section equals k, and the indicator bit is 1 when the value of the section is not equal to k. 19. The one or more computer-readable storage media of claim 18, wherein the selected bit is the Q th bit of the group of 2 K bits, wherein Q equals a value of a section of a second input corresponding to the section of the first input. 20. A computer-implemented system comprising: one or more computers; and one or more computer memory devices interoperably coupled with the one or more computers and having computer-readable storage media storing one or more instructions that, when executed by the one or more computers, perform one or more operations comprising: generating, by a first party of a secure multi-party computation (MPC), a first difference between a first secret share of a first value and a first secret share of a second value; during a first iteration of the secure MPC: partitioning the first difference into N sections each comprising M bits, where N and M are positive integers; for each section of the N sections: generating a random integer between 0 and N; generating, based on the random integer, a group of 2 M integers; and sending, to a second party of the secure MPC based on oblivious transfer (OT) protocol, a selected integer from the group of 2 M integers; and adding random integers of the N sections as a first input of a second iteration of the secure MPC; and determining whether the first value equals the second value based on performing a plurality of iterations of the secure MPC comprising at least the first iteration and the second iteration."
  ],
  "cpc": [
    "H04L 9/0869"
  ],
  "filing_date": "2024-10-14",
  "publication_date": "2026-04-16",
  "application_number": "US-202418914844-A"
}