WO2026009409A1 - Secure computation system and record extraction method - Google Patents

Abstract

This secure computation system is composed of one or more secure computation servers. Each secure computation server comprises a random number assignment unit, a combination unit, a sorting unit, a comparison unit, a shuffling unit, and a deletion unit. The random number assignment unit associates a share [r_n] obtained by secretly sharing a random number r_n with each record. The combination unit finds a share [c_n∥r_n] of a combination c_n∥r_n of a class c_n in the record and a random number r_n associated with the record. The sorting unit finds a sorted share [c_n∥r_n] obtained by sorting the combination c_n∥r_n. The comparison unit compares the sorted class c_n with a class c_n-k, and associates the share of a comparison result with the share of the record. The deletion unit deletes the share of the record with which the comparison result indicating a match is associated.

Description

Secure computing system, record extraction method

The present invention relates to a secure computation system consisting of multiple secure computation servers and a record extraction method.

While momentum for data utilization using AI and other technologies is growing, so too is the demand for privacy protection, creating a need for an environment where highly confidential data can be analyzed using proven AI algorithms in fields such as healthcare. Secure computing AI is a technology that brings together data accumulated by multiple companies and makes safe use of it. It enables the creation of models and inference (data manipulation in which no one can see anything but the calculation results) using extremely secure and diverse AI algorithms, while keeping the data confidential (secret distribution) and never restoring it. Secure computing AI can realize statistical analysis and machine learning services that can be used while keeping the data confidential, but because analysis and other processing is performed without seeing the data, it is extremely inefficient compared to plain text, and to date, there have been no examples of a system being implemented that operates under realistic usage conditions (acceptable calculation time).

It is difficult to implement secure computation AI in the form of secure computation itself. In other words, to perform fully secure computation, taking into account model type, parameter depth, structural information, etc., abstracting all learning would require lengthy calculations, which would impair usability and make it unrealistic. For this reason, there is a demand for technology that can perform secure computation at a practical calculation speed. To execute within an acceptable timeframe, it is necessary to extract and select records to be used for learning and perform an efficient search. For example, stratified sampling (Non-Patent Documents 1 and 2) is a method for thoroughly extracting data from classes with a small number of records.

Yoshizawa Hiroyuki, Yoshida Toshikazu, Nakajima Makoto, Yoshida Takuya, Harada Chika, "Effects of Neighborhood Commitment and Atmosphere on Youth Antisociality Mediated by Collective Efficacy: A Multilevel Study with Stratified Sampling," Applied Psychology Research, Vol. 45, No. 1, pp. 35-46, 2019. Sechidis, K., Tsoumakas, G., Vlahavas, I. "On the Stratification of Multi-label Data", In: Gunopoulos, D., Hofmann, T., Malerba, D., Vazirgiannis, M. (eds) Machine Learning and Knowledge Discovery in Databases. ECML PKDD 2011. Lecture Notes in Computer Science(), vol. 6913. Springer, Berlin, Heidelberg, [Retrieved June 13, 2024], Internet <https://doi.org/10.1007/978-3-642-23808-6_10>.

However, the methods for extracting data from classes with a small number of records without omission, as shown in Non-Patent Documents 1 and 2, cannot be simply applied to secure computing AI. Therefore, the present invention aims to provide a method for extracting data from classes with a small number of records without omission, using secure computing.

The secure computation system of the present invention is composed of one or more secure computation servers. Each secure computation server includes a recording unit, a random number assignment unit, a combining unit, a sorting unit, a comparison unit, a shuffling unit, and a deleting unit. The random number assignment unit associates a share [r _n ] obtained by secretly sharing a random number r _n with each record. The combining unit obtains a share [c n ∥r _n ] of the combination c _n ∥r _n between a class c _n in the record and the random number r _n associated with the record. The sorting unit obtains a post-sorted share [ _{c n} ∥r _n ] by sorting the combination c _n ∥r _n . The comparison unit compares the sorted class c _n with the class c _n-k and associates the share of the comparison result with the share of the record. The shuffling unit shuffles the comparison result and obtains the share of the shuffled comparison result. The deleting unit deletes the share of the record associated with a comparison result indicating a match. Any of the secure computation servers or a secure computation client device connected to the secure computation system includes a restoration unit that restores the post-shuffle comparison result using the share of the post-shuffle comparison result.

The secure computation system of the present invention extracts records so that the class ratio of the specified attribute is equal, providing a method for using secure computation to thoroughly extract data from classes with a small number of records.

FIG. 1 is a diagram showing an example of the configuration of a secure computation system made up of multiple secure computation servers connected via a network and a secure computation client device. FIG. 2 is a diagram showing an example of the functional configuration of a secure computation server. FIG. 4 is a diagram showing the processing flow of the record extraction method according to the first embodiment. FIG. 10 is a diagram for explaining an image of a record extraction method. FIG. 10 is a diagram showing an example of a record. FIG. 10 is a diagram showing an example in which a random number is generated for each record and is linked to data of attribute Y. FIG. 10 shows the results of sorting records based on the join c _n ∥r _n . FIG. 10 is a diagram showing the results of comparison with k previous data after sorting. FIG. 10 is a diagram showing an example in which records with a comparison result of "1" are deleted without shuffling. FIG. 10 is a diagram showing the processing flow of a record extraction method according to Modification 1. FIG. 2 is a diagram showing an example of the functional configuration of a computer.

Before explaining the embodiments, we will explain the basic technical concepts used in this disclosure.

[Secret sharing technology]
Secret sharing is a technique in which data is converted into multiple shares, allowing the original data to be restored using a certain number of shares or more, but making it impossible to restore the original data using shares less than the certain number. (k,n)-secret sharing, a type of secret sharing, divides an input plaintext into n shares, distributes the shares to n computing entities, and allows the plaintext to be restored using any k shares, but no information about the plaintext can be obtained using shares less than k. Here, n and k are integers greater than or equal to 1, and n≧k. A typical example of (k,n)-secret sharing is Shamir secret sharing, described in A. Shamir, "How to share a secret," Communications of the ACM, Volume 22, Issue 11, pp. 612-613, 1979 (Reference 1). The secret sharing used in this disclosure may be any method that can utilize secure computation, as described below.

[Secret computing technology]
Secure computation is a technology in which data to be computed is secretly shared and stored among multiple computing entities, and the computing entities cooperate to calculate the shared values of functions of the original data without recovering the original data.Secure computation uses secret sharing as an elemental technology.

The secure computation used in the first embodiment of the present disclosure may be one that allows the various operations required for the desired data processing to be performed on shared values obtained by a specific secret sharing method. A secure computation technique that performs basic operations such as addition and multiplication on secret shared values is described, for example, in "Koji Senda, Hiroki Hamada, Dai Igarashi, Katsumi Takahashi, "Rethinking Lightly Verifiable Three-Party Secure Function Computation," Computer Security Symposium 2010, 2010 (Reference 2)." A secret matching technique that searches for information from the secret shared values of a data string while keeping it secret is described, for example, in "Koji Senda, Masayuki Terada, Takayasu Yamaguchi, Dai Igarashi, Hiroki Hamada, Katsumi Takahashi, "Secure Matching Protocol Considering Statistical Disclosure Control," Information Processing Society of Japan Research Report, 2011-CSEC-52(12), 2011 (Reference 3)." A secret sorting technique that sorts data strings while keeping their secret sharing values secret is described, for example, in "Hamada Hiroki, Igarashi Dai, Senda Koji, Takahashi Katsumi, "Linear Time Sorting on Secure Function Computation," Computer Security Symposium 2011, 2011 (Reference 4)."

The following describes in detail an embodiment of the present invention. Components with the same functions are assigned the same numbers, and duplicate explanations will be omitted.

First embodiment

In the following explanation, N is the number of records to be used for machine learning, n is an integer between 1 and N, and k is a predetermined positive integer. Figure 1 shows an example configuration of a secure computation system and a secure computation client device, which are composed of multiple secure computation servers connected via a network. Figure 2 shows an example functional configuration of a secure computation server. Figure 3 shows the processing flow of the record extraction method of Example 1. Figure 4 is a diagram for explaining an image of the record extraction method.

The secure computation system 10 is composed of X secure computation servers 100-1, ..., X. X may be, for example, 3 or greater, but can be any number greater than 1 as long as the method allows for secure computation, as described below. Existing technology can be used for the secure computation system 10 (such as the technology disclosed in WO2012/046692 (family U.S. Patent US8,989,391B2) (Reference 5)). For example, when X = 3, one piece of data is converted into three shares, and the three secure computation servers 100-1, 100-2, and 100-3 each record one share. Two shares are required to restore the data. In the secure computation system 10, calculations can be performed while maintaining the data in a secretly shared state (anonymized state), and the results are also recorded anonymously as shares of the results on each secure computation server 100-x. If the results are statistics, the statistics can be known by obtaining and restoring two or more shares, while maintaining the confidentiality of the original data.

The secure computation client device 200 comprises a secure computation client unit 210, an AutoML unit 220, a communication unit 280, and a recording unit 290. The communication unit 280 may be connected to the user device 300. In this case, encryption technology may be used for communication between the communication unit 280 and the user device 300. The recording unit 290 records records used for training the AI model. Each record consists of data with multiple attributes. Attributes include, for example, age, gender, basic medical information (such as the values of blood components), and disease name.

The secure computation client unit 210 is connected to a secure computation system consisting of multiple secure computation servers 100-1,...,X, and has a secret sharing unit 211 and a restoration unit 212. The secure computation client unit 210 transmits shares of records and shares of instruction information to the secure computation system 10, and receives shares of calculation results and shares of evaluation values from the secure computation system 10. Here, "transmitting shares to the secure computation system 10" means transmitting shares corresponding to each secure computation server 100-x, and "receiving shares from the secure computation system 10" means receiving shares recorded by each secure computation server 100-x. In other words, the secret sharing unit 211 converts records, instruction information, etc. into multiple shares and transmits shares corresponding to each secure computation server 100-x. The instruction information is information such as which attributes to use for machine learning of the AI model. The restoration unit 212 receives shares of calculation results and shares of evaluation values from the secure computation system 10, and acquires plaintext calculation results and evaluation values.

The secret sharing unit 211 converts the records used for machine learning of the AI model into multiple shares in advance, and transmits the corresponding shares to each secure computation server 100-x. Each secure computation server 100-x records the shares of attribute data that make up the record in the recording unit 190.

As shown in Figure 2, the secure computation server 100-x comprises a recording unit 190, a random number assignment unit 110, a combining unit 120, a sorting unit 130, a comparison unit 140, a shuffling unit 150, a deletion unit 160, and a restoration unit 180. In the present invention, records are extracted from a collection of records so that records of the same class with a specified attribute are evenly distributed. The collection in Figure 4 contains four types of circles, but there is a bias in their numbers. If circles are extracted randomly from the collection, more circles that are present in large numbers in the collection will be extracted, and the number of circles that are rare will decrease. On the other hand, if the four types of circles are extracted in an equal distribution, it is possible to extract both abundant and rare circles evenly.

For example, consider the use of AI in medical diagnosis. In the case of health checkup data, the most common result is that no further examination is necessary, and even when further examination is necessary, there are diseases that are common and diseases that are rare. In order to perform effective machine learning, it is necessary to avoid deleting records (data) for diseases with few cases when extracting records. Furthermore, when using AI to make an initial judgment on the need for further examination based on the results of a health checkup, it is desirable to output more results indicating that further examination may be necessary. Therefore, in this invention, secret computation is used to extract records so that the class ratios of specified attributes are equal, thereby extracting data from classes with few records without omission.

FIG. 5 shows an example of records. There are 20 records, and each record has data of attribute Y. There are five classes of attribute Y: "0", "1", "2", "3", and "4". The random number assigning units 110 of the secure computation servers 100-1, ..., X cooperatively generate random numbers r _n and associate the shares [r _n ] obtained by secretly sharing the random numbers r _n with each record (S110). The "cooperation" is the same as the existing secure computation technology (the technology disclosed in WO2012/046692 (US Patent US8,989,391B2 of the same family) (Reference 5)), so any existing technology may be used. The combining units 120 of the secure computation servers 100-1, ..., X cooperatively calculate the shares [c _n ∥r _n ] of the combination c _n ∥r _n between the class c _n in the record and the random number r _n associated with the record (S120). FIG. 6 shows an example in which a random number is generated for each record and linked to the data of attribute Y.

The sorting units 130 of the secure computation servers 100-1,...,X cooperate to sort the join _{cn∥r n} and obtain the post-sort share [ _{cn∥r n} ] (S130). Fig. 7 shows the results of sorting records based on the _join cn∥r _n . In other words, when sorting the join _{cn∥r n} , the data _cn is also sorted.

The comparison units 140 of the secure computation servers 100-1,...,X cooperate to compare the sorted class c _n with the class c _n-k , and associate the share of the comparison result with the share of the record (S140). k is an integer specified by the secure computation client device 200 to the secure computation system 10, and indicates how many records of the same class are to be left. FIG. 8 is a diagram showing the result of a comparison with the k-th data after sorting. If the sorted data is different from the k-th data before it, "0" is output as the comparison result, and if the data is the same, "1" is output as the comparison result. In the example of FIG. 8, k=2.

The shuffling units 150 of the secure computation servers 100-1, ..., X cooperatively shuffle the comparison results and determine the share of the comparison results after shuffling (S150). The restoration unit 180 of one of the secure computation servers 100-x, or the restoration unit 212 of the secure computation client device 200 connected to the secure computation system 10, restores the comparison results after shuffling using the share of the comparison results after shuffling (S212). Only the comparison results are restored; the data of attribute Y itself is not restored. The example in Figure 3 is an example restored by the restoration unit 212 of the secure computation client device 200.

Then, the deletion units 160 of the secure computation servers 100-1, ..., X cooperatively delete the shares of records associated with comparison results indicating a match (S160). Figure 9 shows an example in which records with a comparison result of "1" are deleted without shuffling. In the example of Figure 8, k = 2 and there were five types of classes, so in Figure 9, 10 records remain.

The data for attribute Y is secretly distributed and recorded on secure computation servers 100-1,...,X, and records are extracted using secure computation. This allows records to be extracted so that the attribute class ratio is equal while maintaining the confidentiality of the data. Furthermore, the equal allocation method equalizes the class ratio of specified attributes, eliminating the impact of attribute bias on AI learning. This allows for faster processing of AI analysis while ensuring that data from classes with a small number of records is extracted without omission.

As described above, this invention compares two records and eliminates duplicates, making it possible to implement the equal distribution method with secure computing AI, thereby reducing the number of records to be learned and enabling faster AI analysis. Stratified sampling can extract any number of records by ensuring a range of the number k you want to extract and comparing them instead of just before. Equal distribution, one of the stratified sampling methods, can eliminate the impact of attribute bias by equalizing the class ratio of a specified attribute. Equal distribution only determines whether the current record is of the same class as the k records before it, in other words, whether there are k consecutive records of the same class, so it can extract data from classes with a small number of records without omitting anything. The only thing that needs to be determined is whether they are "same class" or "different class," and there is no need to determine which class the contents of the different class are, and there is no need to change the processing, allowing for high-speed processing.

By implementing the equipartition method as a record extraction method for secure computation AI and speeding up processing, it is now possible to implement secure computation AI under realistic conditions (within acceptable computation time), which was previously unattainable, and keep data confidential as a whole. Improving efficiency by using simple random sampling to extract records risks not extracting data from classes with a small number of records. However, the equipartition method allows for extraction without simply deleting all records when the number of records is k or less. Data accumulated by multiple companies can be pooled and used safely. Furthermore, it expands the applicability of secure computation AI (e.g., data analysis using AI) and improves ease of implementation (e.g., business asset integration), enabling deployment to a wide range of users.
[Modification 1]

However, if there are fewer than k records of the same class, the number of remaining records will be less than the number obtained by multiplying the class type by k. In this case, it is possible to determine how many records of the same class there are that have fewer than k records. Therefore, in variant 1, a process is added that determines whether or not there is data with fewer than k records of the same class. As shown in Figure 2, the secure computation server 100-x also includes a record number acquisition unit 170, a shortage number calculation unit 175, and a dummy addition unit 185. Figure 10 shows the processing flow of the record extraction method of variant 1.

Steps S110 to S140 are the same as in FIG. 3. The record number acquisition units 170 of the secure computation servers 100-1, ..., X cooperatively calculate the shares [m _L ] of the number of records m _L of the same class for each class c _n (S170). The shortage calculation units 175 of the secure computation servers 100-1, ..., X cooperatively calculate the shares [si] of the shortage si = k - m _L for classes where the number of records m _L of the same class is less than k, and calculate the shares [S] of the total S of all the calculated shortages si (S175). The dummy addition units 185 of the secure computation servers 100-1, ..., X cooperatively add S shares of dummy data to the shares of the records (S185). Steps S150 and S212 are the same as in the first embodiment.

Then, the deletion units 160 of the secure computation servers 100-1, ..., X cooperatively delete the shares of the records associated with the comparison results indicating a match, and the shares of the dummy data (S161). Note that if it is desired to proactively notify the total number of missing shares, S, the restoration unit 180 of any of the secure computation servers 100-x, or the restoration unit 212 of the secure computation client device 200 connected to the secure computation system 10, may restore the total S using the shares [S].

In this modified example, as in Example 1, records can be extracted so that the class ratio of attributes is equal while maintaining data confidentiality. Furthermore, the equal allocation method can eliminate the impact of attribute bias on AI learning by equalizing the class ratio of specified attributes. This makes it possible to extract data from classes with a small number of records without omission, while also processing AI analysis more quickly.

[Processor, program, recording medium]
The functions performed by the components described herein may be implemented in circuitry or processing circuitry, including general-purpose processors, application-specific processors, integrated circuits, ASICs (Application Specific Integrated Circuits), a CPU (a Central Processing Unit), conventional circuits, and/or combinations thereof, programmed to perform the described functions. A processor includes transistors and other circuits and is considered to be circuitry or processing circuitry. A processor may also be a programmed processor that executes programs stored in memory.

In this specification, a circuit, unit, or means refers to hardware that is programmed to realize or executes the described functions. The hardware may be any hardware disclosed in this specification or any hardware known to be programmed to realize or execute the described functions.

If the hardware is a processor, which is considered to be a type of circuitry, the circuitry, means, or unit is the combination of the hardware and the software used to configure the hardware and/or processor.

The various processes described above can be implemented by loading a program that executes each step of the above method into the recording unit 2020 of the computer 2000 shown in FIG. 11 and operating the control unit 2010, input unit 2030, output unit 2040, display unit 2050, etc.

The program describing this processing can be recorded on a computer-readable recording medium. Examples of computer-readable recording media include magnetic recording devices, optical disks, magneto-optical recording media, and semiconductor memory.

In addition, this program may be distributed, for example, by selling, transferring, or lending portable recording media such as DVDs or CD-ROMs on which the program is recorded. Furthermore, the program may be stored in a storage device on a server computer, and then transferred from the server computer to other computers via a network, thereby distributing the program.

A computer that executes such a program, for example, first stores the program recorded on a portable recording medium or transferred from a server computer in its own storage device. Then, when executing processing, the computer reads the program stored on its own recording medium and executes processing in accordance with the read program. As another form of execution of this program, the computer may read the program directly from the portable recording medium and execute processing in accordance with that program, or it may execute processing in accordance with the received program each time a program is transferred to this computer from the server computer. Alternatively, the server computer may not transfer the program to this computer, but rather executes processing using a so-called ASP (Application Service Provider) type service, which realizes processing functions simply by issuing execution instructions and obtaining results. Furthermore, the computer may be configured to execute terminal processing using a so-called SaaS (Software as a Service) type service, which allows users to use part of a server computer along with the program. In this embodiment, the program includes information used for processing by an electronic computer that is equivalent to a program (such as data that is not a direct command to a computer but has properties that dictate computer processing).

In addition, in this embodiment, the device is configured by executing a specific program on a computer, but at least part of the processing may also be implemented in hardware.

REFERENCE SIGNS LIST 10 Secure computation system 100 Secure computation server 110 Random number assignment unit 120 Combination unit 130 Sorting unit 140 Comparison unit 150 Shuffling unit 160 Deletion unit 170 Record number acquisition unit 175 Deficiency number calculation unit 180 Restoration unit 185 Dummy addition unit 190 Recording unit 200 Secure computation client device 210 Secure computation client unit 211 Secret sharing unit 212 Restoration unit 220 AutoML unit 280 Communication unit 290 Recording unit 300 User device

Claims (4)

A secure computation system comprising one or more secure computation servers,
N is the number of records to be used for machine learning, n is an integer between 1 and N, and k is a predetermined positive integer.
Each secure computation server:
a recording unit that records the secretly shared shares of the record;
a random number assigning unit that associates a share [ _rn ] obtained by secretly sharing a random number _rn with each record;
a combining unit that calculates a share [c _n ∥r _n ] of a combining c _n ∥r _n between a class c _n in a record and a random number r _n associated with the record;
a sorting unit that sorts the join c _n ∥r _n to obtain a sorted share [c _n ∥r _n ];
a comparison unit that compares the sorted class c _n with the class c _n−k and associates the share of the comparison result with the share of the record;
a shuffling unit that shuffles the comparison results and determines a share of the comparison results after shuffling;
a deletion unit that deletes a share of a record associated with a comparison result indicating a match,
A secure computation system characterized in that any of the secure computation servers or a secure computation client device connected to the secure computation system comprises a restoration unit that restores the post-shuffle comparison result using the share of the post-shuffle comparison result. 2. The secure computing system according to claim 1,
Each secure computation server:
a record number obtaining unit that obtains a share [m _L ] of the number of records m _L of the same class for each class c _n ;
a shortage calculation unit that calculates a share [si] of the shortage si=k-m _L for classes where the number of records m _L of the same class is less than k, and calculates a share [S] of the total S of all the calculated shortages si;
A secure computing system further comprising a dummy adding unit that adds S shares of dummy data to the shares of the record. 3. The secure computing system according to claim 1,
The secure computation system further comprises a secure computation client device for using the secure computation system via a network. A record extraction method using a secure computation system configured with one or more secure computation servers,
N is the number of records to be used for machine learning, n is an integer between 1 and N, and k is a predetermined positive integer.
Each secure computation server records the secretly shared shares in the recorder.
Each secure computation server cooperates to
A share [ _rn ] obtained by secretly sharing the random number _rn is associated with each record,
A share [c _n ∥r _n ] of the connection c _n ∥r _n between the class c _n in the record and the random number r _n associated with the record is calculated.
The combined c _n ∥r _n is sorted to obtain the post-sort share [c _n ∥r _n ].
The sorted class c _n is compared with the class c _n−k , and the share of the comparison result is associated with the share of the record;
shuffling the comparison results and determining a share of the comparison results after shuffling;
A record extraction method that deletes the share of records for which the comparison result indicates a match.