Granted Patent B2

US 12,476,788 · App. 18/629,394 · Granted Nov 18, 2025

Inventors: Ramy Masalha (Kafr Qari, IL); Allon Adir (Kiryat Tivon, IL); Ehud Aharoni (Kfar Saba, IL); Eyal Kushnir (Kfar Vradim, IL)

Assignee: International Business Machines Corporation

H04L9/008

Abstract

Claims (38)

1 . A method, in a data processing system, for performing a tournament-league comparison process of a computer function, the method comprising:

receiving a request to execute the computer function on at least one input vector data structure, wherein a result of the computer function is provided by executing a tournament-league comparison process, and wherein the at least one input vector data structure comprises a plurality of values, each value corresponding to a vector slot of the at least one input vector data structure;

executing at least one iteration of a tournament comparison operation to generate a first intermediate ciphertext and indicator matrix, wherein the first intermediate ciphertext comprises fewer vector slots than the at least one input vector data structure;

executing a plurality of iterations of a league comparison operation based on the first intermediate ciphertext and one or more second intermediate ciphertexts generated at each iteration of the league comparison operation;

executing a final iteration of the league comparison operation that outputs a final result of the tournament-league comparison process; and

performing the requested computer function based on the result of the tournament-league comparison process,

wherein the plurality of iterations of the league comparison process comprises generating a combined matrix from a first matrix of a first input vector data structure of the at least one input vector data structure, and a second matrix of a second input vector data structure of the at least one input vector data structure, wherein the combined matrix comprises an upper triangle of the first matrix and a lower triangle of the second matrix.

2 . The method of claim 1 , wherein the input vector data structure is a single ciphertext data structure, and wherein executing the at least one iteration of the tournament comparison process comprises performing local selection operations between pairs of slots within the single ciphertext data structure based on the requested computer function.

3 . The method of claim 1 , wherein the computer function is one of a max function, an argmax function, a min function, an argmin function, or a candidate selection operation in which criteria for selection is specified in the computer function.

4 . The method of claim 1 , wherein the at least one iteration of the tournament comparison process comprises two iterations of the tournament comparison process, and wherein the plurality of iterations of the league comparison process comprises three iterations of the league comparison process and the final iteration of the league comparison process.

5 . The method of claim 1 , wherein the at least one iteration of the tournament comparison process comprises a single iteration of the tournament comparison process, and wherein the plurality of iterations of the league comparison process comprises three iterations of the league comparison process and the final iteration of the league comparison process.

6 . The method of claim 1 , wherein each iteration of the league comparison process is executed using a different league size than other iterations of the league comparison in the plurality of iterations of the league comparison process.

7 . The method of claim 6 , wherein a first league size for a first iteration of the league comparison is 4, a second league size for a second iteration of the league comparison is 16, and a third league size for a third iteration of the league comparison is 256.

8 . The method of claim 1 , wherein executing the plurality of iterations of the league comparison process comprises executing two iterations of the league comparison process as a single operation based on the combined matrix.

9 . The method of claim 1 , wherein the computer function implements a computer function in a homomorphic encrypted operation.

10 . A computer program product comprising a computer readable storage medium having a computer readable program stored therein, wherein the computer readable program, when executed on a computing device, causes the computing device to:

receive a request to execute the computer function on at least one input vector data structure, wherein a result of the computer function is provided by executing a tournament-league comparison process, and wherein the at least one input vector data structure comprises a plurality of values, each value corresponding to a vector slot of the at least one input vector data structure;

execute at least one iteration of a tournament comparison operation to generate a first intermediate ciphertext and indicator matrix, wherein the first intermediate ciphertext comprises fewer vector slots than the at least one input vector data structure;

execute a plurality of iterations of a league comparison operation based on the first intermediate ciphertext and one or more second intermediate ciphertexts generated at each iteration of the league comparison operation;

execute a final iteration of the league comparison operation that outputs a final result of the tournament-league comparison process; and

perform the requested computer function based on the result of the tournament-league comparison process,

wherein the plurality of iterations of the league comparison process comprises generating a combined matrix from a first matrix of a first input vector data structure of the at least one input vector data structure, and a second matrix of a second input vector data structure of the at least one input vector data structure, wherein the combined matrix comprises an upper triangle of the first matrix and a lower triangle of the second matrix.

11 . The computer program product of claim 10 , wherein the input vector data structure is a single ciphertext data structure, and wherein executing the at least one iteration of the tournament comparison process comprises performing local selection operations between pairs of slots within the single ciphertext data structure based on the requested computer function.

12 . The computer program product of claim 10 , wherein the computer function is one of a max function, an argmax function, a min function, an argmin function, or a candidate selection operation in which criteria for selection is specified in the computer function.

13 . The computer program product of claim 10 , wherein the at least one iteration of the tournament comparison process comprises two iterations of the tournament comparison process, and wherein the plurality of iterations of the league comparison process comprises three iterations of the league comparison process and the final iteration of the league comparison process.

14 . The computer program product of claim 10 , wherein the at least one iteration of the tournament comparison process comprises a single iteration of the tournament comparison process, and wherein the plurality of iterations of the league comparison process comprises three iterations of the league comparison process and the final iteration of the league comparison process.

15 . The computer program product of claim 10 , wherein each iteration of the league comparison process is executed using a different league size than other iterations of the league comparison in the plurality of iterations of the league comparison process.

16 . The computer program product of claim 15 , wherein a first league size for a first iteration of the league comparison is 4, a second league size for a second iteration of the league comparison is 16, and a third league size for a third iteration of the league comparison is 256.

17 . The computer program product of claim 10 , wherein executing the plurality of iterations of the league comparison process comprises executing two iterations of the league comparison process as a single operation based on the combined matrix.

18 . An apparatus comprising:

at least one processor; and

at least one memory coupled to the at least one processor, wherein the at least one memory comprises instructions which, when executed by the at least one processor, cause the at least one processor to:

receive a request to execute the computer function on at least one input vector data structure, wherein a result of the computer function is provided by executing a tournament-league comparison process, and wherein the at least one input vector data structure comprises a plurality of values, each value corresponding to a vector slot of the at least one input vector data structure;

execute at least one iteration of a tournament comparison operation to generate a first intermediate ciphertext and indicator matrix, wherein the first intermediate ciphertext comprises fewer vector slots than the at least one input vector data structure;

execute a plurality of iterations of a league comparison operation based on the first intermediate ciphertext and one or more second intermediate ciphertexts generated at each iteration of the league comparison operation;

execute a final iteration of the league comparison operation that outputs a final result of the tournament-league comparison process; and

perform the requested computer function based on the result of the tournament-league comparison process,

wherein the plurality of iterations of the league comparison process comprises generating a combined matrix from a first matrix of a first input vector data structure of the at least one input vector data structure, and a second matrix of a second input vector data structure of the at least one input vector data structure, wherein the combined matrix comprises an upper triangle of the first matrix and a lower triangle of the second matrix.

Assignments (1)

Continuity (1)

References Cited (30)