WO2019225401A1 - 秘密集約関数計算システム、秘密計算装置、秘密集約関数計算方法、およびプログラム - Google Patents

秘密集約関数計算システム、秘密計算装置、秘密集約関数計算方法、およびプログラム Download PDF

Info

Publication number
WO2019225401A1
WO2019225401A1 PCT/JP2019/019093 JP2019019093W WO2019225401A1 WO 2019225401 A1 WO2019225401 A1 WO 2019225401A1 JP 2019019093 W JP2019019093 W JP 2019019093W WO 2019225401 A1 WO2019225401 A1 WO 2019225401A1
Authority
WO
WIPO (PCT)
Prior art keywords
share
secret
restored
group
sorted
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/JP2019/019093
Other languages
English (en)
French (fr)
Inventor
大 五十嵐
浩気 濱田
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
NTT Inc
Original Assignee
Nippon Telegraph and Telephone Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Nippon Telegraph and Telephone Corp filed Critical Nippon Telegraph and Telephone Corp
Priority to US17/057,120 priority Critical patent/US11593362B2/en
Priority to JP2020521167A priority patent/JP6989006B2/ja
Priority to EP19806536.9A priority patent/EP3806070B1/en
Priority to AU2019273208A priority patent/AU2019273208B2/en
Priority to CN201980032660.9A priority patent/CN112119442B/zh
Publication of WO2019225401A1 publication Critical patent/WO2019225401A1/ja
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/24—Querying
    • G06F16/242—Query formulation
    • G06F16/2433—Query languages
    • G06F16/244—Grouping and aggregation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
    • H04L9/0816—Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for subsequent use
    • H04L9/085—Secret sharing or secret splitting, e.g. threshold schemes
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
    • H04L2209/46—Secure multiparty computation, e.g. millionaire problem

Definitions

  • the present invention relates to a secret calculation technique, and more particularly to a technique for calculating an aggregate function while maintaining confidentiality.
  • the aggregate function is an operation for obtaining a statistical value grouped based on the value of the key attribute when the table has the key attribute and the value attribute.
  • Aggregate functions are also called group-by operations.
  • the key attribute is an attribute used for grouping the records in the table, and examples thereof include a job title and sex.
  • the value attribute is an attribute used to calculate a statistical value, and examples thereof include salary and height.
  • the group-by operation is, for example, an operation for obtaining an average height for each gender when the key attribute is gender.
  • the key attribute may be a composite key with a plurality of attributes. For example, when the key attribute is gender and age, the average height of males in teens, the average height of males in their 20s, etc. There may be.
  • Non-Patent Document 1 describes a method of performing a group-by operation by a secret calculation.
  • the group-by operation specifically includes group-by count, group-by sum, group-by maximum / minimum value, group-by median, and rank within the group.
  • the group-by count is a cross tabulation, and is an operation of tabulating the number of records in each group when the table is grouped based on the value of the key attribute.
  • the group-by sum is a sum of desired value attributes in each group.
  • the group-by maximum value / minimum value is the maximum value / minimum value of a desired value attribute in each group.
  • the group-by median is the median value of the desired value attribute in each group.
  • the rank in the group is a function for acquiring the value of the value attribute of each record in the group.
  • intermediate data may be obtained during the calculation process. Some of the intermediate data is commonly found among different types of group-by operations. If a plurality of group-by operations are calculated simultaneously or successively while maintaining confidentiality, the amount of calculation may increase due to duplication of processing for obtaining common intermediate data.
  • an object of the present invention is to efficiently use intermediate data used in group-by operations when calculating a plurality of group-by operations simultaneously or successively while maintaining confidentiality. To provide technology that can be sought after.
  • a secret aggregation function calculation system is a secret aggregation function calculation system including a plurality of secret calculation devices, wherein F is an arbitrary ring, and m is 2 or more N k is an integer greater than or equal to 1, and [k 0 ],..., [k nk-1 ] is a share in which the key attributes k 0 ,..., k nk-1 ⁇ F m are secretly distributed
  • F is an arbitrary ring
  • m is 2 or more N k is an integer greater than or equal to 1
  • [k 0 ],..., [k nk-1 ] is a share in which the key attributes k 0 ,..., k nk-1 ⁇ F m are secretly distributed
  • a group sort generator for generating a share ⁇ 0 ⁇ that becomes a replacement ⁇ 0 that stably sorts the bit string b in ascending order from the share ⁇ b ⁇ that becomes m ⁇ 1 , and a share ⁇ b ⁇ And the share ⁇ 0 ⁇ , the restored bit string b ': b' 0 ,..., b ' m-1 that has been sorted by the replacement ⁇ 0 is restored.
  • the secret aggregation function technique of the present invention it is possible to efficiently obtain intermediate data used in a group-by operation while maintaining secrecy. By using the intermediate data, when calculating a plurality of group-by operations simultaneously or successively, the total calculation amount can be reduced.
  • FIG. 1 is a diagram illustrating a functional configuration of a secret aggregation function calculation system.
  • FIG. 2 is a diagram illustrating a functional configuration of the secret computing device.
  • FIG. 3 is a diagram illustrating a processing procedure of the secret aggregation function calculation method.
  • [x] ⁇ [F] represents that a certain value x is concealed by secret sharing on an arbitrary ring F.
  • ⁇ b ⁇ ⁇ ⁇ B ⁇ represents that a certain value b of 1 bit is concealed by secret sharing on ring B that can represent 1 bit.
  • ⁇ s ⁇ ⁇ ⁇ S m ⁇ represents that a certain substitution s belonging to the m element substitution set S m is concealed by secret sharing or the like.
  • the secret-distributed value is also referred to as “share”.
  • sorting described in Reference Document 1 below can be used.
  • the hybrid substitution ⁇ described in Reference Document 1 below may be used.
  • the secret aggregation function calculation system 100 includes N ( ⁇ 2) secret calculation devices 1 1 ,..., 1 N.
  • the secret computing devices 1 1 ,..., 1 N are each connected to the communication network 2.
  • the communication network 2 is a circuit-switched or packet-switched communication network configured such that connected devices can communicate with each other.
  • the Internet a LAN (Local Area Network), or a WAN (Wide Area Network). Etc. can be used.
  • Each device does not necessarily need to be able to communicate online via the communication network 2.
  • secure computing apparatus 1 1, ..., and stores information to be input to the 1 N in a portable recording medium such as a magnetic tape or a USB memory, secure computing apparatus 1 1 from the portable recording medium, ..., offline to 1 N You may comprise so that it may input.
  • a portable recording medium such as a magnetic tape or a USB memory
  • the secret computing device 1 n includes an input unit 10, a bit decomposition unit 11, a group sort generation unit 12, a bit string sort unit 13, a flag generation unit 14, a key aggregation sort generation unit 15, a deduplication Section 16, key sort section 17, value sort section 18, and output section 19.
  • the secret aggregation function calculation method of the embodiment is realized.
  • the secret computing device 1 n is configured, for example, by loading a special program into a known or dedicated computer having a central processing unit (CPU), a main storage (RAM), and the like. It is a special device.
  • the secret computing device 1 n executes each process under the control of the central processing unit.
  • the data input to the secret computing device 1 n and the data obtained by each processing are stored in, for example, the main storage device, and the data stored in the main storage device is read out to the central processing unit as necessary. Used for other processing.
  • At least a part of each processing unit of the secret computing device 1 n may be configured by hardware such as an integrated circuit.
  • step S10 the input unit 10 of each secret computing device 1 n uses n k key attributes k 0 ,..., K nk-1 ⁇ F m to share [k 0 ],. k nk-1 ] ⁇ [F] m and n a value attributes v 0 ,..., v na-1 ⁇ F m are concealed by secret sharing [v 0 ],..., [v na-1 ] ⁇ [F] m is received as input.
  • n k, n a represents an integer of 1 or more
  • m is an integer of 2 or more.
  • the input unit 10 outputs the shares [k 0 ],..., [K nk-1 ] of the key attributes k 0 ,..., K nk-1 to the bit decomposition unit 11 and the deduplication unit 16.
  • the input unit 10 the value attribute v 0, ..., v na- 1 share [v 0], ..., and outputs it to the value sorting section 18 [v na-1].
  • ⁇ b i ⁇ is the i-th element [k 0, i ],..., each of the shares [k 0 ],..., [k nk-1 ] of the key attributes k 0 ,..., k nk-1 . It is a bit string that combines the bit representations of [k nk-1, i ].
  • the bit decomposition unit 11 outputs the share ⁇ b ⁇ of the bit string b to the group sort generation unit 12.
  • step S12 the group sort generation unit 12 of each secret computing device 1 n uses the share ⁇ b ⁇ of the bit string b to restore the share ⁇ that becomes the replacement ⁇ 0 for stably sorting the bit string b in ascending order. 0 ⁇ ⁇ ⁇ S m ⁇ is generated.
  • the stable sort is an operation that preserves the order of elements having the same value when elements having the same value exist in the sort operation. For example, if a table sorted in order of employee numbers is stably sorted by gender, a sort result in which the order of employee numbers is maintained in each gender is obtained.
  • the replacement ⁇ 0 is made so that records having the same value of the key attributes k 0 ,..., k nk-1 are consecutive. It can be said that it is an operation of rearranging and grouping.
  • the group sort generation unit 12 outputs the share ⁇ b ⁇ of the bit string b and the share ⁇ 0 ⁇ of the replacement ⁇ 0 to the bit string sort unit 13. Further, the group sort generation unit 12 outputs the share ⁇ 0 ⁇ of the replacement ⁇ 0 to the key sort unit 17 and the value sort unit 18.
  • the bit string sorting unit 13 outputs the share ⁇ b ′ ⁇ of the sorted bit string b ′ to the flag generation unit 14.
  • ⁇ e i ⁇ : ⁇
  • a share ⁇ e ⁇ ⁇ ⁇ B ⁇ m is generated.
  • Flag e i because true is set when the sorted bit sequence b 'i th element b of' i is i + 1 th element b 'i + 1 is different from the last element of each group (i.e., Group It is a flag indicating the element immediately before the boundary between them.
  • the flag generation unit 14 outputs the share ⁇ e ⁇ of the flag e to the key aggregation sort generation unit 15, the deduplication unit 16, and the output unit 19.
  • step S15 the key aggregation sort generation unit 15 of each secret computing device 1 n first uses the share ⁇ e ⁇ of the flag e to restore the share ⁇ e that becomes the flag e ′ that is a negative e of the flag e when restored.
  • the key aggregation / sort generation unit 15 uses the share ⁇ e ′ ⁇ of the flag e ′ to restore a share ⁇ ⁇ ⁇ that becomes a replacement ⁇ for stably sorting the flag e ′ in ascending order when restored.
  • S m The key aggregation / sort generation unit 15 outputs the share ⁇ of the replacement ⁇ to the key sort unit 17 and the output unit 19.
  • the deduplicated key attribute k " 0 ,..., k" nk-1 is only the element corresponding to the last element of each group A key attribute value is set, and the other elements are vectors set with predetermined values that cannot be taken by the key attribute.
  • the deduplication unit 16 outputs the shares [k “ 0 ], ..., [k" nk-1 ] of the deduplicated key attributes k " 0 , ..., k” nk-1 to the key sort unit 17.
  • Kisoto section 17 of each secret computing apparatus 1 n is, deduplicated key attribute k "0, ..., k" nk-1 share [k “0], ..., [k” and nk-1]
  • the deduplicated key attributes k " 0 ,..., k" nk-1 are replaced with the replacement ⁇ 0
  • a share [k ′ 0 ],..., [k ′ nk-1 ] is generated that becomes sorted key attributes k ′ 0 ,..., k ′ nk ⁇ 1 sorted in order by ⁇ .
  • the key sort unit 17 outputs the shares [k ′ 0 ],..., [K ′ nk ⁇ 1 ] of the sorted key attributes k ′ 0 ,..., K ′ nk ⁇ 1 to the output unit 19.
  • the value sort unit 18 of the secure computing apparatus 1 n is the value attribute v 0, ..., v na- 1 share [v 0], ..., [ v na-1] and substituted sigma 0 Share ⁇ ⁇ 0 ⁇ is used to restore the value attribute v 0 ,..., v na-1 as a sorted value attribute v ′ 0 ,..., v ′ na-1 sorted by replacement ⁇ 0 [v ' 0 ],..., [v' na-1 ] are generated.
  • the value sort unit 18 outputs the shares [v ′ 0 ],..., [V ′ na ⁇ 1 ] of the sorted value attributes v ′ 0 ,..., V ′ na ⁇ 1 to the output unit 19.
  • step S19 the output unit 19 of the secure computing apparatus 1 n is sorted key attribute k '0, ..., k' nk-1 share [k '0], ..., [k' nk-1], sorting It requires value attribute v '0, ..., v' na-1 share [v '0], ..., [v' na-1], share ⁇ e ⁇ flag e, and substituted sigma share ⁇
  • Output at least one of the following.
  • the information to be output by the output unit 19 is selected so as to satisfy intermediate data required for one or more group-by operations to be calculated subsequently.
  • the group-by count is an operation of counting the number of records in each group when the table is grouped based on the value of the key attribute.
  • the group-by count can be obtained as follows using the share ⁇ e ⁇ of the flag e output from the secret aggregation function calculation system 100 and the share ⁇ of the replacement ⁇ .
  • g is the maximum number of groups, and is the number of combinations of values that the key attribute can take, that is, the number of types of values that the key attribute can take.
  • the share ⁇ e ⁇ ⁇ ⁇ B ⁇ m of the flag e is converted into a share [e] ⁇ [F] m by secret sharing on an arbitrary ring F.
  • the i-th element ⁇ (x) i of the sorted vector ⁇ (x) is set to the total value of the number of records in each group from the 0th to the i-th, so the i-th element of the vector c c i is set to the number of records of the i-th group. Since the key attribute is kept secret, min (g, m) is the maximum value that the number of groups can take, and the actual number of groups is known to each secret computing device 1 n that is less than min (g, m). An unobtainable value (hereinafter, the actual number of groups is g ′).
  • the group-by sum is an operation of summing up the sum of desired value attributes for each group when the table is grouped based on the value of the key attribute.
  • group-by summation it is possible to calculate a group-by product sum for obtaining the sum of multiplications for each group and a group-by sum of squares for obtaining the sum of squares for each group. If it is a group-by product sum, a group-by sum may be obtained for the result of multiplying the value attribute of each record. In the case of a group-by sum of squares, similarly, a group-by sum may be obtained for the result of squaring the value attribute of each record.
  • the group-by sum is the share [v ' 0 ], ..., [v' na-1 ] of the sorted value attributes v ' 0 , ..., v' na-1 output by the secret aggregation function calculation system 100 and the flag e Using the share ⁇ e ⁇ and the replacement ⁇ share ⁇ , the following can be obtained.
  • v is a desired value attribute for which a group-by sum is to be obtained among the sorted value attributes v ′ 0 ,..., V ′ na ⁇ 1 .
  • prefix-sum is the length of the input vector v, and for each integer i between 0 and m-1, the i-th element v ' i of the output vector v' is the 0th element v of the input vector v This is an operation for setting the sum of values from 0 to the i-th element v i .
  • the share ⁇ e ⁇ ⁇ ⁇ B ⁇ m of the flag e is converted into a share [e] ⁇ [F] m by secret sharing on an arbitrary ring F.
  • records with the same key attribute value are sorted into the same group when the table is stably sorted by the key attribute, and the sum of the values of the value attribute before that element is set to the last element of each group.
  • the element is a vector in which the sum of the value attribute values of the entire table is set.
  • the i-th element ⁇ (t) i of the sorted vector ⁇ (t) is set to the i-th element of the vector t because the sum of the values of the value attribute v belonging to each of the groups 0 to i is set.
  • the sum of the values of the value attribute v belonging to the i-th group is set.
  • the group-by maximum value is an operation for obtaining a maximum value of a desired value attribute for each group when the table is grouped based on the value of the key attribute.
  • the group-by maximum value is the share [v ' 0 ],..., [v' na-1 ] and flag of the sorted value attributes v ' 0 ,..., v' na-1 output by the secret aggregation function calculation system 100 Using e share ⁇ e ⁇ and permutation ⁇ share ⁇ , it can be obtained as follows. Note that v is a desired value attribute for which a group-by maximum value is to be obtained among the sorted value attributes v ′ 0 ,..., V ′ na ⁇ 1 .
  • the share ⁇ e ⁇ ⁇ ⁇ B ⁇ m of the flag e is converted into a share [e] ⁇ [F] m by secret sharing on an arbitrary ring F.
  • the value of the last element when sorting for each group is set to the element of the number of groups from the top (that is, the maximum value of each group), and 0 is set to the elements after that Vector.
  • the group-by minimum value is an operation for obtaining a minimum value of a desired value attribute for each group when the table is grouped based on the value of the key attribute.
  • the group-by minimum value is the share [v ' 0 ],..., [v' na-1 ] of the sorted value attributes v ' 0 , ..., v' na-1 output by the secret aggregation function calculation system 100 Using e share ⁇ e ⁇ and permutation ⁇ share ⁇ , it can be obtained as follows. Note that v is a desired value attribute for which a group-by minimum value is to be obtained among the sorted value attributes v ′ 0 ,..., V ′ na ⁇ 1 .
  • the value of the first element when sorting for each group is set to the element of the number of groups from the top (that is, the minimum value of each group), and 0 is set to the subsequent elements Vector.
  • a vector x ′: ⁇ (f ′) 0 ,..., ⁇ (f ′) representing the minimum value of each group when restored from the share [ ⁇ (f ′)] of the sorted vector ⁇ (f ′)
  • the ascending order within a group is an operation that, when the table is grouped based on the value of the key attribute, obtains what number the value is in the group when the desired value attribute is sorted in ascending order. is there.
  • the ascending order within the group can be obtained as follows using the share ⁇ e ⁇ of the flag e and the share ⁇ of the replacement ⁇ output from the secret aggregation function calculation system 100.
  • c is a group-by count result (hereinafter referred to as “cross tabulation”).
  • the cross tabulation c can be obtained, for example, using the share ⁇ e ⁇ of the flag e and the share ⁇ of the replacement ⁇ according to the above-described procedure of “group-by count”.
  • the cross tabulation c is a vector in which the number of records of each group is set to the elements from the head to the number of groups, and the replacement ⁇ is a replacement in which the last element of each group is arranged in order from the head, so
  • the reverse permuted cross tabulation u obtained by reversely applying is a vector in which the number of records of the group is set as the last element of each group.
  • prefix-sum is the length of the input vector u, and for each integer i between 0 and m-1, the i-th element s i of the output vector s is from the 0th element u 0 of the input vector u This is an operation for setting the sum of values up to the i-th element u i .
  • the descending order within a group is an operation that, when the table is grouped based on the value of the key attribute, obtains what number the value is in the group when the desired value attribute is sorted in descending order. is there.
  • the descending order within the group can be obtained as follows using the share ⁇ e ⁇ of the flag e and the share ⁇ of the replacement ⁇ output from the secret aggregation function calculation system 100.
  • c is a group-by count result (hereinafter referred to as “cross tabulation”).
  • the cross tabulation c can be obtained, for example, using the share ⁇ e ⁇ of the flag e and the share ⁇ of the replacement ⁇ according to the above-described procedure of “group-by count”.
  • the shifted cross tabulation c ′ is a vector obtained by shifting the cross tabulation c, which is a vector representing the number of records in each group, forward one by one.
  • the shifted cross tabulation c ' is a vector obtained by shifting the cross tabulation c in which the number of records of each group is set to the elements from the head to the number of groups one by one, and the replacement ⁇ is the head of the last element of each group Since the permutation is arranged in order, the reverse permuted cross tabulation u ′ obtained by reversely applying the permutation ⁇ to the shifted cross tabulation c ′ is a vector in which the number of records of the next group is set as the last element of each group. Become.
  • postfix-sum is the i-th element s' i of the output vector s' for the integer i between 0 and m-1 where m is the length of the input vector u '. This operation sets the sum of the values from the element u ′ i to the m ⁇ 1 th element u ′ m ⁇ 1 .
  • the group-by median value is an operation for obtaining a median value of a desired value attribute for each group when the table is grouped based on key attribute values.
  • the group-by median is the share [v ' 0 ], ..., [v' na-1 ] of the value attributes v ' 0 , ..., v' na-1 output by the secret aggregation function calculation system 100 and the flag e.
  • c is a group-by count result (hereinafter referred to as “cross tabulation”).
  • the cross tabulation c can be obtained, for example, using the share ⁇ e ⁇ of the flag e and the share ⁇ of the replacement ⁇ according to the above-described procedure of “group-by count”. Further, v is a desired value attribute for which a group-by median value is to be obtained among the sorted value attributes v ′ 0 ,..., V ′ na ⁇ 1 .
  • a vector a: a 0 ,..., a m ⁇ 1 that represents the ascending order within the group when restored using the share [c] of the cross tabulation c and the share ⁇ of the replacement ⁇ .
  • a share [a] ⁇ [F] m with ⁇ F and a vector d: d 0 ,..., d m-1 ⁇ F representing a descending order within the group when restored [d] ⁇ [F] m Is generated.
  • the ascending order and descending order are one start.
  • the ascending order within the group can be obtained, for example, according to the above-described procedure of ⁇ ascending order within the group >>.
  • the descending order within the group can be obtained, for example, according to the above-described procedure of ⁇ descending order within the group >>.
  • a ′ is a bit string excluding the least significant bit of ad
  • d ′ is a bit string excluding the least significant bit of da.
  • each secret computing device 1 n has the sorted key attributes k ′ 0 ,..., K ′ nk ⁇ 1 shares [k ′ 0 ] ,. At least the share [v ' 0 ],..., [v' na-1 ] of attribute v ' 0 ,..., v' na-1 , share of flag e ⁇ e ⁇ , and share of substitution ⁇ ⁇
  • a processing unit to be provided may be selected and configured depending on the type of group-by operation to be calculated subsequently.
  • the group-by count and the group-by median are group-by operations that require a share ⁇ e ⁇ of flag e and a share ⁇ of replacement ⁇ .
  • the group-by sum and group-by maximum / minimum values are the share [v ' 0 ],..., [v' na-1 ] of the sorted value attributes v ' 0 ,..., v' na-1 , flag e Is a group-by operation that requires a share ⁇ e ⁇ and a share ⁇ of replacement ⁇ .
  • the rank in the group is a group-by operation that requires the share ⁇ e ⁇ of the flag e and the share ⁇ of the replacement ⁇ .
  • each secret computing device 1 n includes, for example, an input unit 10, a bit decomposition unit 11, a group sort generation unit 12, a bit string sort unit 13, a flag generation unit 14, a key aggregation sort generation unit 15, and an output unit 19.
  • the deduplication unit 16, the key sort unit 17, and the value sort unit 18 can be configured not to be provided.
  • the program describing the processing contents can be recorded on a computer-readable recording medium.
  • a computer-readable recording medium any recording medium such as a magnetic recording device, an optical disk, a magneto-optical recording medium, and a semiconductor memory may be used.
  • this program is distributed, for example, by selling, transferring, or lending a portable recording medium such as a DVD or CD-ROM in which the program is recorded. Furthermore, the program may be distributed by storing the program in a storage device of the server computer and transferring the program from the server computer to another computer via a network.
  • a computer that executes such a program first stores a program recorded on a portable recording medium or a program transferred from a server computer in its own storage device. When executing the process, this computer reads the program stored in its own storage device and executes the process according to the read program.
  • the computer may directly read the program from a portable recording medium and execute processing according to the program, and the program is transferred from the server computer to the computer. Each time, the processing according to the received program may be executed sequentially.
  • the program is not transferred from the server computer to the computer, and the above processing is executed by a so-called ASP (Application Service Provider) type service that realizes the processing function only by the execution instruction and result acquisition. It is good.
  • ASP Application Service Provider
  • the program in this embodiment includes information that is used for processing by an electronic computer and that conforms to the program (data that is not a direct command to the computer but has a property that defines the processing of the computer).
  • the present apparatus is configured by executing a predetermined program on a computer.
  • a predetermined program on a computer.
  • at least a part of these processing contents may be realized by hardware.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Databases & Information Systems (AREA)
  • General Physics & Mathematics (AREA)
  • Data Mining & Analysis (AREA)
  • General Engineering & Computer Science (AREA)
  • Computational Linguistics (AREA)
  • Mathematical Physics (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Computer Security & Cryptography (AREA)
  • Storage Device Security (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Library & Information Science (AREA)
  • Quality & Reliability (AREA)
  • Complex Calculations (AREA)

Abstract

秘匿性を保ったまま集約関数で用いる中間データを効率的に求める。ビット分解部（１１）は、キー属性をビット分解して結合したビット列のシェアを生成する。グループソート生成部（１２）は、ビット列を昇順に安定ソートする第一の置換のシェアを生成する。ビット列ソート部（１３）は、ビット列を第一の置換でソートしたソート済みビット列のシェアを生成する。フラグ生成部（１４）は、グループの境界を示すフラグのシェアを生成する。キー集約ソート生成部（１５）は、フラグの否定を昇順に安定ソートする第二の置換のシェアを生成する。重複排除部（１６）は、重複排除済みキー属性のシェアを生成する。キーソート部（１７）は、重複排除済みキー属性を第一の置換と第二の置換とで順にソートしたソート済みキー属性のシェアを生成する。バリューソート部（１８）は、バリュー属性を第一の置換でソートしたソート済みバリュー属性のシェアを生成する。

Description

秘密集約関数計算システム、秘密計算装置、秘密集約関数計算方法、およびプログラム
　この発明は秘密計算技術に関し、特に、秘匿性を保ったまま集約関数を計算する技術に関する。
　集約関数は、テーブルにキー属性とバリュー属性があるときに、キー属性の値に基づいてグループ分けした統計値を得る演算である。集約関数は、group-by演算とも呼ばれる。キー属性は、テーブルのレコードをグループ分けするために用いる属性であり、例えば、役職や性別などが挙げられる。バリュー属性は、統計値を計算するために用いる属性であり、例えば、給料や身長などが挙げられる。group-by演算は、例えば、キー属性が性別のときに、男女別の平均身長を求める演算などである。キー属性は複数の属性による複合キーであってもよく、例えば、キー属性が性別と年齢のときに、10代男性の平均身長、20代男性の平均身長、・・・を得るような演算であってもよい。非特許文献１には、group-by演算を秘密計算で行う方法が記載されている。
　group-by演算は、具体的には、group-byカウント、group-by総和、group-by最大値／最小値、group-by中央値、グループ内の順位などがある。group-byカウントは、クロス集計のことであり、テーブルをキー属性の値に基づいてグループ分けしたときに、各グループのレコード数を集計する演算である。group-by総和は、各グループにおける所望のバリュー属性の総和である。group-by最大値／最小値は、各グループにおける所望のバリュー属性の最大値／最小値である。group-by中央値は、各グループにおける所望のバリュー属性の中央値である。グループ内の順位は、各レコードのバリュー属性の値がグループ内で何番目の値であるかを取得する関数である。
五十嵐大，千田浩司，濱田浩気，高橋克巳，"軽量検証可能３パーティ秘匿関数計算の効率化及びこれを用いたセキュアなデータベース処理"，２０１１年暗号と情報セキュリティシンポジウム
　group-by演算では計算の過程で中間データを求めることがある。この中間データの中には、異なる種類のgroup-by演算の間で共通に求めるものがある。秘匿性を保ったまま複数のgroup-by演算を同時にまたは連続して計算すると、共通の中間データを求める処理が重複することで、計算量が増大する場合がある。
　この発明の目的は、上記のような技術的課題に鑑みて、秘匿性を保ったまま複数のgroup-by演算を同時にまたは連続して計算するときに、group-by演算で用いる中間データを効率的に求めることができる技術を提供することである。
　上記の課題を解決するために、この発明の一態様の秘密集約関数計算システムは、複数の秘密計算装置を含む秘密集約関数計算システムであって、Fは任意の環であり、mは２以上の整数であり、nkは１以上の整数であり、[k0], …, [knk-1]はキー属性k0, …, knk-1∈Fmを秘密分散したシェアであり、秘密計算装置は、シェア[k0], …, [knk-1]を用いて、復元するとキー属性k0, …, knk-1をビット分解して結合したビット列b:=b0, …, bm-1となるシェア{b}から、復元するとビット列bを昇順に安定ソートする置換σ0となるシェア{{σ0}}を生成するグループソート生成部と、シェア{b}とシェア{{σ0}}とを用いて、復元するとビット列bを置換σ0でソートしたソート済みビット列b':=b'0, …, b'm-1となるシェア{b'}を生成するビット列ソート部と、シェア{b'}を用いて、0以上m-2以下の各整数iについて{ei}:={b'i≠b'i+1}を設定し、かつ、{em-1}:={1}を設定して、復元するとフラグe:=e0, …, em-1となるシェア{e}を生成するフラグ生成部と、シェア{e}を用いて、復元するとフラグeの否定￢eを昇順に安定ソートする置換σとなるシェア{{σ}}を生成するキー集約ソート生成部と、を含む。
　この発明の秘密集約関数技術によれば、秘匿性を保ったままgroup-by演算で用いる中間データを効率的に求めることができる。その中間データを用いることで、複数のgroup-by演算を同時にまたは連続して計算するときに、全体の計算量を削減することができる。
図１は、秘密集約関数計算システムの機能構成を例示する図である。 図２は、秘密計算装置の機能構成を例示する図である。 図３は、秘密集約関数計算方法の処理手続きを例示する図である。
　以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
　[x]∈[F]は、ある値xが任意の環F上の秘密分散等により秘匿されていることを表す。{b}∈{B}は、１ビットのある値bが１ビットを表せる環B上の秘密分散等により秘匿されていることを表す。{{s}}∈{{Sm}}は、m個の要素の置換の集合Smに属するある置換sが秘密分散等により秘匿されていることを表す。以下、秘密分散された値を「シェア」とも呼ぶ。
　実施形態中で用いる秘密計算におけるソート（安定ソートを含む）は、例えば、下記参考文献１に記載されたソートを用いることができる。置換sのシェア{{s}}については下記参考文献１に記載されたハイブリッド置換{{π}}を用いればよい。
　〔参考文献１〕五十嵐大，濱田浩気，菊池亮，千田浩司，“超高速秘密計算ソートの設計と実装: 秘密計算がスクリプト言語に並ぶ日”，ＣＳＳ２０１７
　＜実施形態＞
　図１を参照して、実施形態の秘密集約関数計算システム１００の構成例を説明する。秘密集約関数計算システム１００は、N（≧2）台の秘密計算装置１1, …, １Nを含む。本形態では、秘密計算装置１1, …, １Nはそれぞれ通信網２へ接続される。通信網２は、接続される各装置が相互に通信可能なように構成された回線交換方式もしくはパケット交換方式の通信網であり、例えばインターネットやLAN（Local Area Network）、WAN（Wide Area Network）などを用いることができる。なお、各装置は必ずしも通信網２を介してオンラインで通信可能である必要はない。例えば、秘密計算装置１1, …, １Nへ入力する情報を磁気テープやUSBメモリなどの可搬型記録媒体に記憶し、その可搬型記録媒体から秘密計算装置１1, …, １Nへオフラインで入力するように構成してもよい。
　図２を参照して、秘密集約関数計算システム１００に含まれる秘密計算装置１n（n=1, …, N）の構成例を説明する。秘密計算装置１nは、例えば、図２に示すように、入力部１０、ビット分解部１１、グループソート生成部１２、ビット列ソート部１３、フラグ生成部１４、キー集約ソート生成部１５、重複排除部１６、キーソート部１７、バリューソート部１８、および出力部１９を含む。この秘密計算装置１n（1≦n≦N）が他の秘密計算装置１n'（n'=1, …, N、ただしn≠n'）と協調しながら後述する各ステップの処理を行うことにより実施形態の秘密集約関数計算方法が実現される。
　秘密計算装置１nは、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。秘密計算装置１nは、例えば、中央演算処理装置の制御のもとで各処理を実行する。秘密計算装置１nに入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて中央演算処理装置へ読み出されて他の処理に利用される。秘密計算装置１nの各処理部は、少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。
　図３を参照して、実施形態の秘密集約関数計算システム１００が実行する秘密集約関数計算方法の処理手続きを説明する。
　ステップＳ１０において、各秘密計算装置１nの入力部１０は、nk個のキー属性k0, …, knk-1∈Fmそれぞれを秘密分散により秘匿したシェア[k0], …, [knk-1]∈[F]mと、na個のバリュー属性v0, …, vna-1∈Fmそれぞれを秘密分散により秘匿したシェア[v0], …, [vna-1]∈[F]mとを入力として受け取る。ただし、nk, naは１以上の整数であり、mは２以上の整数である。以下、[kj]∈[F]m（j=0, …, nk-1）の各要素は、[kj,i]∈[F]（i=0, …, m-1）で参照することもある。また、[vh]∈[F]m（h=0, …, na-1）の各要素は、[vh,i]∈[F]（i=0, …, m-1）で参照することもある。入力部１０は、キー属性k0, …, knk-1のシェア[k0], …, [knk-1]をビット分解部１１と重複排除部１６へ出力する。また、入力部１０は、バリュー属性v0, …, vna-1のシェア[v0], …, [vna-1]をバリューソート部１８へ出力する。
　ステップＳ１１において、各秘密計算装置１nのビット分解部１１は、キー属性k0, …, knk-1のシェア[k0], …, [knk-1]をビット分解して結合し、復元するとキー属性k0, …, knk-1のビット表現を結合したビット列b:=b0, …, bm-1∈Bλとなるシェア{b}∈{B}λを得る。ただし、λはビット列bのビット長であり、各bi（i=0, …, m-1）のビット長の総和である。言い替えると、{bi}は、キー属性k0, …, knk-1のシェア[k0], …, [knk-1]それぞれのi番目の要素[k0,i], …, [knk-1,i]のビット表現を結合したビット列である。ビット分解部１１は、ビット列bのシェア{b}をグループソート生成部１２へ出力する。
　ステップＳ１２において、各秘密計算装置１nのグループソート生成部１２は、ビット列bのシェア{b}を用いて、復元するとビット列bを昇順で安定ソートするための置換σ0となるシェア{{σ0}}∈{{Sm}}を生成する。安定ソートとは、ソート演算のうち、同じ値の要素が存在した場合に、同じ値の要素同士の順序を保存する演算である。例えば、社員番号順でソートされたテーブルに対して性別で安定ソートすると、各性別の中で社員番号順が保たれているソート結果が得られる。ビット列bはキー属性k0, …, knk-1のビット表現を結合したものであるため、置換σ0はキー属性k0, …, knk-1の値が等しいレコードを連続するように並び替えてグループ分けする操作であるとも言える。グループソート生成部１２は、ビット列bのシェア{b}と置換σ0のシェア{{σ0}}とをビット列ソート部１３へ出力する。また、グループソート生成部１２は、置換σ0のシェア{{σ0}}をキーソート部１７とバリューソート部１８へ出力する。
　ステップＳ１３において、各秘密計算装置１nのビット列ソート部１３は、ビット列bのシェア{b}と置換σ0のシェア{{σ0}}とを用いて、復元するとビット列bを置換σ0でソートしたソート済みビット列b':=b'0, …, b'm-1∈Bλとなるシェア{b'}∈{B}λを得る。ビット列ソート部１３は、ソート済みビット列b'のシェア{b'}をフラグ生成部１４へ出力する。
　ステップＳ１４において、各秘密計算装置１nのフラグ生成部１４は、ソート済みビット列b'のシェア{b'}を用いて、0以上m-2以下の各整数iについて{ei}:={b'i≠b'i+1}を設定し、かつ、{em-1}:={1}を設定して、復元するとフラグe:=e0, …, em-1∈Bmとなるシェア{e}∈{B}mを生成する。フラグeiはソート済みビット列b'のi番目の要素b'iがi+1番目の要素b'i+1と異なる場合に真が設定されるため、各グループの最後の要素（すなわち、グループ間の境界の直前の要素）を示すフラグとなる。フラグ生成部１４は、フラグeのシェア{e}をキー集約ソート生成部１５と重複排除部１６と出力部１９へ出力する。
　ステップＳ１５において、各秘密計算装置１nのキー集約ソート生成部１５は、まず、フラグeのシェア{e}を用いて、復元するとフラグeの否定￢eであるフラグe'となるシェア{e'}∈{B}mを生成する。すなわち、0以上m-1以下の各整数iについて{e'i}:={￢ei}を設定する。次に、キー集約ソート生成部１５は、フラグe'のシェア{e'}を用いて、復元するとフラグe'を昇順に安定ソートするための置換σとなるシェア{{σ}}∈{{Sm}}を生成する。キー集約ソート生成部１５は、置換σのシェア{{σ}}をキーソート部１７と出力部１９へ出力する。
　ステップＳ１６において、各秘密計算装置１nの重複排除部１６は、フラグeのシェア{e}とキー属性k0, …, knk-1のシェア[k0], …, [knk-1]とを用いて、[k"j,i]:=[ei?kj,i:null]を設定し、復元すると重複排除済みキー属性k"0, …, k"nk-1となるシェア[k"0], …, [k"nk-1]を生成する。ここで、「?」は条件演算子（または三項演算子）である。すなわち、{ei}が真（例えば、{ei}={1}）のときは[k"j,i]:=[kj,i]を設定し、{ei}が偽（例えば、{ei}={0}）のときは[k"j,i]:=nullを設定する。{ei}={0}のときに設定する値はnullでなくともよく、キー属性k0, …, knk-1が取り得ない値であればどのような値でもよい。フラグeは各グループの最後の要素のみに真が設定されたフラグであるため、重複排除済みキー属性k"0, …, k"nk-1は、各グループの最後の要素に対応する要素のみキー属性の値が設定され、それ以外の要素はキー属性が取り得ない所定の値が設定されたベクトルとなる。重複排除部１６は、重複排除済みキー属性k"0, …, k"nk-1のシェア[k"0], …, [k"nk-1]をキーソート部１７へ出力する。
　ステップＳ１７において、各秘密計算装置１nのキーソート部１７は、重複排除済みキー属性k"0, …, k"nk-1のシェア[k"0], …, [k"nk-1]と置換σ0のシェア{{σ0}}と置換σのシェア{{σ}}とを用いて、復元すると重複排除済みキー属性k"0, …, k"nk-1を置換σ0と置換σとで順にソートしたソート済みキー属性k'0, …, k'nk-1となるシェア[k'0], …, [k'nk-1]を生成する。キーソート部１７は、ソート済みキー属性k'0, …, k'nk-1のシェア[k'0], …, [k'nk-1]を出力部１９へ出力する。
　ステップＳ１８において、各秘密計算装置１nのバリューソート部１８は、バリュー属性v0, …, vna-1のシェア[v0], …, [vna-1]と置換σ0のシェア{{σ0}}とを用いて、復元するとバリュー属性v0, …, vna-1を置換σ0でソートしたソート済みバリュー属性v'0, …, v'na-1となるシェア[v'0], …, [v'na-1]を生成する。バリューソート部１８は、ソート済みバリュー属性v'0, …, v'na-1のシェア[v'0], …, [v'na-1]を出力部１９へ出力する。
　ステップＳ１９において、各秘密計算装置１nの出力部１９は、ソート済みキー属性k'0, …, k'nk-1のシェア[k'0], …, [k'nk-1]、ソート済みバリュー属性v'0, …, v'na-1のシェア[v'0], …, [v'na-1]、フラグeのシェア{e}、および置換σのシェア{{σ}}の少なくとも１つを出力する。出力部１９が出力すべき情報は、後に続いて計算する１つ以上のgroup-by演算で必要とされる中間データを満たすように選択する。
　以下、秘密集約関数計算システム１００が出力する中間データを用いて、各種の集約関数を計算する具体的な手順を説明する。
　≪group-byカウント≫
　group-byカウントは、テーブルをキー属性の値に基づいてグループ分けしたときに、各グループのレコード数を集計する演算である。group-byカウントは、秘密集約関数計算システム１００が出力するフラグeのシェア{e}と置換σのシェア{{σ}}とを用いて、以下のように求めることができる。なお、gは最大グループ数であり、キー属性が取り得る値の組み合わせの数、すなわち、キー属性が取り得る値の種類の数である。
　第一に、フラグeのシェア{e}∈{B}mを任意の環F上の秘密分散によるシェア[e]∈[F]mに変換する。
　第二に、フラグeのシェア[e]を用いて、0以上m-1以下の各整数iについて[xi]:=[ei?i+1:m]を設定し、復元するとベクトルx:=x0, …, xm-1∈Fとなるシェア[x]∈[F]mを生成する。ベクトルxは、テーブルをキー属性で安定ソートしたときに同じキー属性の値をもつレコードを同じグループとして、各グループの最後の要素には次の要素の先頭からの位置が設定され、その他の要素にはテーブル全体のレコード数が設定されたベクトルとなる。言い替えると、各グループの最後の要素には、先頭のグループからそのグループまでの各グループのレコード数を積み上げた合計値が設定されることになる。
　第三に、ベクトルxのシェア[x]と置換σのシェア{{σ}}とを用いて、復元するとベクトルxを置換σでソートしたソート済みベクトルσ(x)となるシェア[σ(x)]∈[F]mを生成する。以下、[σ(x)]∈[F]mの各要素は、[σ(x)i]∈[F]（i=0, …, m-1）で参照することもある。
　最後に、ソート済みベクトルσ(x)のシェア[σ(x)]を用いて、1以上min(g,m)-1以下の各整数iについて[ci]:=[σ(x)i-σ(x)i-1]を設定し、かつ、[c0]:=[σ(x)0]を設定して、復元すると各グループのレコード数を表すベクトルc:=c0, …, cmin(g,m)-1∈Fとなるシェア[c]∈[F]min(g,m)を生成する。ソート済みベクトルσ(x)のi番目の要素σ(x)iは、0番目からi番目までの各グループのレコード数を積み上げた合計値が設定されているため、ベクトルcのi番目の要素ciには、i番目のグループのレコード数が設定されることになる。なお、キー属性は秘匿されているため、min(g,m)はグループ数が取り得る最大値であり、実際のグループ数はmin(g,m)以下の各秘密計算装置１nには知り得ない値（以下、実際のグループ数をg'とする）となる。したがって、min(g,m)個のシェア[ci]の中で実際のグループ数を超えるもの（すなわち、i≧g'）には、復元後に有効な値と識別可能となる無効な値を設定しておく必要がある。本形態では、[ei]が偽のシェア[xi]もしくは[ei]が真のうち最後のシェア[xi]には[xi]=mを設定している。これにより、cg', …, cmin(g,m)-1にはσ(x)i-σ(x)i-1=m-m=0が設定される。レコードが存在するグループのカウント数は１以上であるため、０は有効な値と識別可能となる無効な値として成立している。
　≪group-by総和≫
　group-by総和は、テーブルをキー属性の値に基づいてグループ分けしたときに、グループごとに所望のバリュー属性の総和を集計する演算である。group-by総和を用いれば、グループごとに乗算の和を求めるgroup-by積和や、グループごとに二乗の和を求めるgroup-by二乗和も計算することができる。group-by積和であれば、各レコードのバリュー属性に乗算を施した結果に対してgroup-by総和を求めればよい。また、group-by二乗和であれば、同様に、各レコードのバリュー属性に二乗を施した結果に対してgroup-by総和を求めればよい。group-by総和は、秘密集約関数計算システム１００が出力するソート済みバリュー属性v'0, …, v'na-1のシェア[v'0], …, [v'na-1]とフラグeのシェア{e}と置換σのシェア{{σ}}とを用いて、以下のように求めることができる。なお、vはソート済みバリュー属性v'0, …, v'na-1のうちgroup-by総和を求めたい所望のバリュー属性である。
　第一に、バリュー属性vのシェア[v]を用いて、[v']:=prefix-sum([v])を計算し、復元するとベクトルv':=v'0, …, v'm-1∈Fとなるシェア[v']∈[F]mを生成する。prefix-sumは、mを入力ベクトルvの長さとして、0以上m-1以下の各整数iについて、出力ベクトルv'のi番目の要素v'iには入力ベクトルvの0番目の要素v0からi番目の要素viまでの値の総和を設定する演算である。
　第二に、フラグeのシェア{e}∈{B}mを任意の環F上の秘密分散によるシェア[e]∈[F]mに変換する。
　第三に、ベクトルv'のシェア[v']とフラグeのシェア[e]とを用いて、0以上m-1以下の各整数iについて[ti]:=[ei?v'i:v'm-1]を設定し、復元するとベクトルt:=t0, …, tm-1∈Fとなるシェア[t]∈[F]mを生成する。ベクトルtは、テーブルをキー属性で安定ソートしたときに同じキー属性の値をもつレコードを同じグループとして、各グループの最後の要素にはその要素以前のバリュー属性の値の総和が設定され、その他の要素にはテーブル全体のバリュー属性の値の総和が設定されたベクトルとなる。
　第四に、ベクトルtのシェア[t]と置換σのシェア{{σ}}とを用いて、復元するとベクトルtを置換σでソートしたソート済みベクトルσ(t)となるシェア[σ(t)]∈[F]mを生成する。以下、[σ(t)]∈[F]mの各要素は、[σ(t)i]∈[F]（i=0, …, m-1）で参照することもある。
　最後に、ソート済みベクトルσ(t)のシェア[σ(t)]を用いて、1以上min(g,m)-1以下の各整数iについて[si]:=[σ(t)i-σ(t)i-1]を設定し、かつ、[t0]:=[σ(t)0]を設定して、復元するとグループ毎のバリュー属性vの総和s:=s0, …, smin(g,m)-1∈Fとなるシェア[s]∈[F]min(g,m)を生成する。ソート済みベクトルσ(t)のi番目の要素σ(t)iは、0番目からi番目までの各グループに属するバリュー属性vの値の総和が設定されているため、ベクトルtのi番目の要素tiには、i番目のグループに属するバリュー属性vの値の総和が設定されることになる。
　≪group-by最大値≫
　group-by最大値は、テーブルをキー属性の値に基づいてグループ分けしたときに、グループごとに所望のバリュー属性の最大値を得る演算である。group-by最大値は、秘密集約関数計算システム１００が出力するソート済みバリュー属性v'0, …, v'na-1のシェア[v'0], …, [v'na-1]とフラグeのシェア{e}と置換σのシェア{{σ}}とを用いて、以下のように求めることができる。なお、vはソート済みバリュー属性v'0, …, v'na-1のうちgroup-by最大値を求めたい所望のバリュー属性である。
　第一に、フラグeのシェア{e}∈{B}mを任意の環F上の秘密分散によるシェア[e]∈[F]mに変換する。
　第二に、バリュー属性vのシェア[v]とフラグeのシェア[e]とを用いて、0以上m-1以下の各整数iについて[fi]:=[ei?vi:0]を設定し、復元するとベクトルf:=f0, …, fm-1∈Fとなるシェア[f]∈[F]mを生成する。ベクトルfは、テーブルをキー属性で安定ソートしたときに同じキー属性の値をもつレコードを同じグループとして、各グループの最後の要素fiにはその要素に対応するバリュー属性の値viが設定され、その他の要素には０が設定されたベクトルとなる。すなわち、各グループの最大値と０とを要素としてもつベクトルとなる。
　第三に、ベクトルfのシェア[f]と置換σのシェア{{σ}}とを用いて、復元するとベクトルfを置換σでソートしたソート済みベクトルσ(f)となるシェア[σ(f)]∈[F]mを生成する。以下、[σ(f)]∈[F]mの各要素は、[σ(f)i]∈[F]（i=0, …, m-1）で参照することもある。ソート済みベクトルσ(f)は、先頭からグループ数の要素にグループ毎にソートしたときの最後の要素の値（すなわち、各グループの最大値）が設定され、それ以降の要素に０が設定されたベクトルとなる。
　最後に、ソート済みベクトルσ(f)のシェア[σ(f)]から、復元すると各グループの最大値を表すベクトルx:=σ(f)0, …, σ(f)min(g,m)-1となるシェア[x]∈[F]min(g,m)を生成する。
　≪group-by最小値≫
　group-by最小値は、テーブルをキー属性の値に基づいてグループ分けしたときに、グループごとに所望のバリュー属性の最小値を得る演算である。group-by最小値は、秘密集約関数計算システム１００が出力するソート済みバリュー属性v'0, …, v'na-1のシェア[v'0], …, [v'na-1]とフラグeのシェア{e}と置換σのシェア{{σ}}とを用いて、以下のように求めることができる。なお、vはソート済みバリュー属性v'0, …, v'na-1のうちgroup-by最小値を求めたい所望のバリュー属性である。
　第一に、フラグeのシェア{e}を用いて、1以上m-1以下の各整数iについて{e'i}:={ei-1}を設定し、かつ、{e'0}:={1}を設定して、復元するとフラグe':=e'0, …, e'm-1∈Bmとなるシェア{e'}∈{B}mを生成する。フラグe'は各グループの最後の要素を示すフラグeを一つずつ後方へシフトしたフラグであるため、各グループの最初の要素（すなわち、グループ間の境界の直後の要素）を示すフラグとなる。
　第二に、フラグe'のシェア{e'}∈{B}mを任意の環F上の秘密分散によるシェア[e']∈[F]mに変換する。
　第三に、バリュー属性vのシェア[v]とフラグe'のシェア[e']とを用いて、0以上m-1以下の各整数iについて[f'i]:=[e'i?vi:0]を設定し、復元するとベクトルf':=f'0, …, f'm-1∈Fとなるシェア[f']∈[F]mを生成する。ベクトルf'は、テーブルをキー属性で安定ソートしたときに同じキー属性の値をもつレコードを同じグループとして、各グループの最初の要素f'iにはその要素に対応するバリュー属性の値viが設定され、その他の要素には０が設定されたベクトルとなる。すなわち、各グループの最小値と０とを要素としてもつベクトルとなる。
　第四に、ベクトルf'のシェア[f']と置換σのシェア{{σ}}とを用いて、復元するとベクトルf'を置換σでソートしたソート済みベクトルσ(f')となるシェア[σ(f')]∈[F]mを生成する。以下、[σ(f')]∈[F]mの各要素は、[σ(f')i]∈[F]（i=0, …, m-1）で参照することもある。ソート済みベクトルσ(f')は、先頭からグループ数の要素にグループ毎にソートしたときの最初の要素の値（すなわち、各グループの最小値）が設定され、それ以降の要素に０が設定されたベクトルとなる。
　最後に、ソート済みベクトルσ(f')のシェア[σ(f')]から、復元すると各グループの最小値を表すベクトルx':=σ(f')0, …, σ(f')min(g,m)-1となるシェア[x']∈[F]min(g,m)を生成する。
　≪グループ内の昇順順位≫
　グループ内の昇順順位は、テーブルをキー属性の値に基づいてグループ分けしたときに、所望のバリュー属性を昇順でソートしたときにその値がグループ内で何番目の値であるかを得る演算である。グループ内の昇順順位は、秘密集約関数計算システム１００が出力するフラグeのシェア{e}と置換σのシェア{{σ}}とを用いて、以下のように求めることができる。なお、cはgroup-byカウントの結果（以下、「クロス集計」と呼ぶ）である。クロス集計cは、例えば、上述の≪group-byカウント≫の手順に従って、フラグeのシェア{e}と置換σのシェア{{σ}}とを用いて求めることができる。
　第一に、クロス集計cのシェア[c]と置換σのシェア{{σ}}とを用いて、復元するとクロス集計cに置換σを逆適用した逆置換済みクロス集計u:=σ-1(c)となるシェア[u]:=[σ-1(c)]∈[F]mを生成する。クロス集計cは先頭からグループ数までの要素に各グループのレコード数が設定されたベクトルであり、置換σは各グループの最後の要素を先頭から順に並べる置換であるため、クロス集計cに置換σを逆適用した逆置換済みクロス集計uは各グループの最後の要素にそのグループのレコード数が設定されたベクトルとなる。以下、[u]∈[F]mの各要素は、[ui]∈[F]（i=0, …, m-1）で参照することもある。
　第二に、逆置換済みクロス集計uのシェア[u]を用いて、[s]:=prefix-sum([u])を計算し、復元するとベクトルs:=s0, …, sm-1∈Fとなるシェア[s]∈[F]mを生成する。prefix-sumは、mを入力ベクトルuの長さとして、0以上m-1以下の各整数iについて、出力ベクトルsのi番目の要素siには入力ベクトルuの0番目の要素u0からi番目の要素uiまでの値の総和を設定する演算である。
　最後に、ベクトルsのシェア[s]を用いて、1以上m-1以下の各整数iについて[ai]:=[i-si-1]を設定し、かつ、[a0]:=[0]を設定して、復元するとグループ内での昇順順位a:=a0, …, am-1∈Fとなるシェア[a]∈[F]mを生成する。なお、グループ内での昇順順位は０スタートとなることに注意されたい。１スタートの順位を得たいのであれば、各順位に１を加算すればよい。すなわち、1以上m-1以下の各整数iについて[ai]:=[i-si-1+1]を設定し、かつ、[a0]:=[1]を設定して、昇順順位aを生成すればよい。
　≪グループ内の降順順位≫
　グループ内の降順順位は、テーブルをキー属性の値に基づいてグループ分けしたときに、所望のバリュー属性を降順でソートしたときにその値がグループ内で何番目の値であるかを得る演算である。グループ内の降順順位は、秘密集約関数計算システム１００が出力するフラグeのシェア{e}と置換σのシェア{{σ}}とを用いて、以下のように求めることができる。なお、cはgroup-byカウントの結果（以下、「クロス集計」と呼ぶ）である。クロス集計cは、例えば、上述の≪group-byカウント≫の手順に従って、フラグeのシェア{e}と置換σのシェア{{σ}}とを用いて求めることができる。
　第一に、クロス集計cのシェア[c]を用いて、0以上m-2以下の各整数iについて[c'i]:=[ci+1]を設定し、かつ、[c'm-1]:=[0]を設定して、復元するとシフト済みクロス集計c':=c'0, …, c'm-1∈Fmとなるシェア[c']∈[F]mを生成する。シフト済みクロス集計c'は各グループのレコード数を表すベクトルであるクロス集計cを一つずつ前方へシフトしたベクトルとなる。
　第二に、シフト済みクロス集計c'のシェア[c']と置換σのシェア{{σ}}とを用いて、復元するとシフト済みクロス集計c'に置換σを逆適用した逆置換済みクロス集計u':=σ-1(c')となるシェア[u']:=[σ-1(c')]∈[F]mを生成する。シフト済みクロス集計c'は先頭からグループ数までの要素に各グループのレコード数が設定されたクロス集計cを一つずつ前方へシフトしたベクトルであり、置換σは各グループの最後の要素を先頭から順に並べる置換であるため、シフト済みクロス集計c'に置換σを逆適用した逆置換済みクロス集計u'は各グループの最後の要素に一つ後方のグループのレコード数が設定されたベクトルとなる。以下、[u']∈[F]mの各要素は、[u'i]∈[F]（i=0, …, m-1）で参照することもある。
　第三に、逆置換済みクロス集計u'のシェア[u']を用いて、[s']:=postfix-sum([u'])を計算し、復元するとベクトルs':=s'0, …, s'm-1∈Fとなるシェア[s']∈[F]mを生成する。postfix-sumは、mを入力ベクトルu'の長さとして、0以上m-1以下の各整数iについて、出力ベクトルs'のi番目の要素s'iには入力ベクトルu'のi番目の要素u'iからm-1番目の要素u'm-1までの値の総和を設定する演算である。
　最後に、ベクトルs'のシェア[s']を用いて、0以上m-1以下の各整数iについて[di]:=[m-i-s'i-1]を設定して、復元するとグループ内での降順順位d:=d0, …, dm-1∈Fとなるシェア[d]∈[F]mを生成する。なお、グループ内での降順順位は０スタートとなることに注意されたい。１スタートの順位を得たいのであれば、各順位に１を加算すればよい。すなわち、0以上m-1以下の各整数iについて[di]:=[m-i-s'i]を設定して、降順順位dを生成すればよい。
　≪group-by中央値≫
　group-by中央値は、テーブルをキー属性の値に基づいてグループ分けしたときに、グループごとに所望のバリュー属性の中央値を得る演算である。group-by中央値は、秘密集約関数計算システム１００が出力するバリュー属性v'0, …, v'na-1のシェア[v'0], …, [v'na-1]とフラグeのシェア{e}と置換σのシェア{{σ}}とを用いて、以下のように求めることができる。なお、cはgroup-byカウントの結果（以下、「クロス集計」と呼ぶ）である。クロス集計cは、例えば、上述の≪group-byカウント≫の手順に従って、フラグeのシェア{e}と置換σのシェア{{σ}}とを用いて求めることができる。また、vはソート済みバリュー属性v'0, …, v'na-1のうちgroup-by中央値を求めたい所望のバリュー属性である。
　第一に、クロス集計cのシェア[c]と置換σのシェア{{σ}}とを用いて、復元するとグループ内での昇順順位を表すベクトルa:=a0, …, am-1∈Fとなるシェア[a]∈[F]mおよび復元するとグループ内での降順順位を表すベクトルd:=d0, …, dm-1∈Fとなるシェア[d]∈[F]mを生成する。ここで、昇順順位および降順順位は１スタートとする。グループ内での昇順順位は、例えば、上述の≪グループ内の昇順順位≫の手順に従って求めることができる。グループ内での降順順位は、例えば、上述の≪グループ内の降順順位≫の手順に従って求めることができる。
　第二に、昇順順位aのシェア[a]と降順順位dのシェア[d]とを用いて、2λ>mを満たすλに対して、[2λ+a-d], [2λ+d-a]を計算し、[2λ+a-d], [2λ+d-a]をλビットにビット分解して、復元するとビット列a-dなるシェア{a-d}∈{Bλ}mと、復元するとビット列d-aとなるシェア{d-a}∈{Bλ}mとを生成する。
　第三に、a-dのシェア{a-d}とd-aのシェア{d-a}とから最下位ビットを除いて、復元するとa', d'となるシェア{a'}, {d'}∈{Bλ-1}mを生成する。a'はa-dの最下位ビットを除いたビット列であり、d'はd-aの最下位ビットを除いたビット列である。
　第四に、a'のシェア{a'}とd'のシェア{d'}とを用いて、{a"}:={|a'=0|}, {d"}:={|d'=0|}を計算し、復元するとフラグa", d"∈Bmとなるシェア{a"}, {d"}∈{B}mを生成する。なお、|・|は等式・の真偽を返却する記号である。フラグa", d"は、a-d, d-aそれぞれが0以上1以下であるかどうかを表す。さらに、a"はそのレコードが大きい方の中央値であるかどうか、d"はそのレコードが小さい方の中央値であるかどうかを表す。
　第五に、フラグa", d"のシェア{a"}, {d"}∈{B}mを任意の環F上の秘密分散によるシェア[a"], [d"]∈[F]mに変換する。
　第六に、バリュー属性vのシェア[v]とフラグa", d"のシェア{a"}, {d"}とを用いて、[va]:=[va"], [vd]:=[vd"]を計算し、復元するとベクトルva, vd∈Fmとなるシェア[va], [vd]∈[F]mを生成する。
　第七に、フラグa", d"のシェア{a"}, {d"}を用いて、復元するとフラグa", d"の否定￢a", ￢d"となるシェア{￢a"}, {￢d"}∈{B}mを生成する。次に、フラグa", d"の否定￢a", ￢d"のシェア{￢a"}, {￢d"}を用いて、復元するとフラグa", d"の否定￢a", ￢d"をソートする置換σa, σdとなるシェア{{σa}}, {{σd}}∈{{Sm}}を生成する。
　最後に、ベクトルva, vdのシェア[va], [vd]と置換σa, σdのシェア{{σa}}, {{σd}}とを用いて、[x]:=[σa(va)+σd(vd)]を計算し、復元すると各グループの中央値を表すベクトルxとなるシェア[x]∈[F]mを生成する。
　＜変形例＞
　上記の実施形態では、各秘密計算装置１nが、ソート済みキー属性k'0, …, k'nk-1のシェア[k'0], …, [k'nk-1]、ソート済みバリュー属性v'0, …, v'na-1のシェア[v'0], …, [v'na-1]、フラグeのシェア{e}、および置換σのシェア{{σ}}の少なくとも１つを出力するように構成する例を説明したが、後に続いて計算するgroup-by演算の種類によって、備えるべき処理部を選択して構成してもよい。例えば、group-byカウントやgroup-by中央値は、フラグeのシェア{e}および置換σのシェア{{σ}}を必要とするgroup-by演算である。group-by総和やgroup-by最大値／最小値は、ソート済みバリュー属性v'0, …, v'na-1のシェア[v'0], …, [v'na-1]、フラグeのシェア{e}、および置換σのシェア{{σ}}を必要とするgroup-by演算である。グループ内の順位は、フラグeのシェア{e}および置換σのシェア{{σ}}を必要とするgroup-by演算である。すなわち、group-byカウント、group-by中央値、またはグループ内の順位を計算するが、group-by総和やgroup-by最大値／最小値を計算することがない状況であれば、秘密集約関数計算システム１００は、少なくともフラグeのシェア{e}および置換σのシェア{{σ}}が出力できればよい。このとき、各秘密計算装置１nは、例えば、入力部１０、ビット分解部１１、グループソート生成部１２、ビット列ソート部１３、フラグ生成部１４、キー集約ソート生成部１５、および出力部１９を備え、重複排除部１６、キーソート部１７、およびバリューソート部１８は備えないように構成することができる。
　以上、この発明の実施の形態について説明したが、具体的な構成は、これらの実施の形態に限られるものではなく、この発明の趣旨を逸脱しない範囲で適宜設計の変更等があっても、この発明に含まれることはいうまでもない。実施の形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
　［プログラム、記録媒体］
　上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
　この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
　また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
　このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
　また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。

Claims (5)

  1. 　複数の秘密計算装置を含む秘密集約関数計算システムであって、
    　Fは任意の環であり、mは２以上の整数であり、nkは１以上の整数であり、[k0], …, [knk-1]はキー属性k0, …, knk-1∈Fmを秘密分散したシェアであり、
    　上記秘密計算装置は、
    　上記シェア[k0], …, [knk-1]を用いて、復元すると上記キー属性k0, …, knk-1をビット分解して結合したビット列b:=b0, …, bm-1となるシェア{b}から、復元すると上記ビット列bを昇順に安定ソートする置換σ0となるシェア{{σ0}}を生成するグループソート生成部と、
    　上記シェア{b}と上記シェア{{σ0}}とを用いて、復元すると上記ビット列bを上記置換σ0でソートしたソート済みビット列b':=b'0, …, b'm-1となるシェア{b'}を生成するビット列ソート部と、
    　上記シェア{b'}を用いて、0以上m-2以下の各整数iについて{ei}:={b'i≠b'i+1}を設定し、かつ、{em-1}:={1}を設定して、復元するとフラグe:=e0, …, em-1となるシェア{e}を生成するフラグ生成部と、
    　上記シェア{e}を用いて、復元すると上記フラグeの否定￢eを昇順に安定ソートする置換σとなるシェア{{σ}}を生成するキー集約ソート生成部と、
    　を含む秘密集約関数計算システム。
  2. 　請求項１に記載の秘密集約関数計算システムであって、
    　naは１以上の整数であり、[v0], …, [vna-1]はバリュー属性v0, …, vna-1∈Fmを秘密分散したシェアであり、
    　上記秘密計算装置は、
    　上記シェア{e}を用いて、0以上m-1以下の各整数iおよび0以上nk-1以下の各整数jについて、{ei}={1}ならば[k"j,i]に[kj,i]を設定し、{ei}≠{1}ならば[k"j,i]に所定の固定値を設定して、復元すると重複排除済みキー属性k"0, …, k"nk-1となるシェア[k"0], …, [k"nk-1]を生成する重複排除部と、
    　上記シェア[k"0], …, [k"nk-1]と上記シェア{{σ0}}と上記シェア{{σ}}とを用いて、
    復元すると上記重複排除済みキー属性k"0, …, k"nk-1を上記置換σ0と上記置換σとで順にソートしたソート済みキー属性k'0, …, k'nk-1となるシェア[k'0], …, [k'nk-1]を生成するキーソート部と、
    　上記シェア[v0], …, [vna-1]と上記シェア{{σ0}}とを用いて、復元すると上記バリュー属性v0, …, vna-1を上記置換σ0でソートしたソート済みバリュー属性v'0, …, v'na-1となるシェア[v'0], …, [v'na-1]を生成するバリューソート部と、
    　を含む秘密集約関数計算システム。
  3. 　Fは任意の環であり、mは２以上の整数であり、nkは１以上の整数であり、[k0], …, [knk-1]はキー属性k0, …, knk-1∈Fmを秘密分散したシェアであり、
    　上記シェア[k0], …, [knk-1]を用いて、復元すると上記キー属性k0, …, knk-1をビット分解して結合したビット列b:=b0, …, bm-1となるシェア{b}から、復元すると上記ビット列bを昇順に安定ソートする置換σ0となるシェア{{σ0}}を生成するグループソート生成部と、
    　上記シェア{b}と上記シェア{{σ0}}とを用いて、復元すると上記ビット列bを上記置換σ0でソートしたソート済みビット列b':=b'0, …, b'm-1となるシェア{b'}を生成するビット列ソート部と、
    　上記シェア{b'}を用いて、0以上m-2以下の各整数iについて{ei}:={b'i≠b'i+1}を設定し、かつ、{em-1}:={1}を設定して、復元するとフラグe:=e0, …, em-1となるシェア{e}を生成するフラグ生成部と、
    　上記シェア{e}を用いて、復元すると上記フラグeの否定￢eを昇順に安定ソートする置換σとなるシェア{{σ}}を生成するキー集約ソート生成部と、
    　を含む秘密計算装置。
  4. 　複数の秘密計算装置を含む秘密集約関数計算システムが実行する秘密集約関数計算方法であって、
    　Fは任意の環であり、mは２以上の整数であり、nkは１以上の整数であり、[k0], …, [knk-1]はキー属性k0, …, knk-1∈Fmを秘密分散したシェアであり、
    　上記秘密計算装置のグループソート生成部が、上記シェア[k0], …, [knk-1]を用いて、復元すると上記キー属性k0, …, knk-1をビット分解して結合したビット列b:=b0, …, bm-1となるシェア{b}から、復元すると上記ビット列bを昇順に安定ソートする置換σ0となるシェア{{σ0}}を生成し、
    　上記秘密計算装置のビット列ソート部が、上記シェア{b}と上記シェア{{σ0}}とを用いて、復元すると上記ビット列bを上記置換σ0でソートしたソート済みビット列b':=b'0, …, b'm-1となるシェア{b'}を生成し、
    　上記秘密計算装置のフラグ生成部が、上記シェア{b'}を用いて、0以上m-2以下の各整数iについて{ei}:={b'i≠b'i+1}を設定し、かつ、{em-1}:={1}を設定して、復元するとフラグe:=e0, …, em-1となるシェア{e}を生成し、
    　上記秘密計算装置のキー集約ソート生成部が、上記シェア{e}を用いて、復元すると上記フラグeの否定￢eを昇順に安定ソートする置換σとなるシェア{{σ}}を生成する、
    　秘密集約関数計算方法。
  5. 　請求項３に記載の秘密計算装置としてコンピュータを機能させるためのプログラム。
PCT/JP2019/019093 2018-05-25 2019-05-14 秘密集約関数計算システム、秘密計算装置、秘密集約関数計算方法、およびプログラム Ceased WO2019225401A1 (ja)

Priority Applications (5)

Application Number Priority Date Filing Date Title
US17/057,120 US11593362B2 (en) 2018-05-25 2019-05-14 Secure aggregate function computation system, secure computation apparatus, secure aggregate function computation method, and program
JP2020521167A JP6989006B2 (ja) 2018-05-25 2019-05-14 秘密集約関数計算システム、秘密計算装置、秘密集約関数計算方法、およびプログラム
EP19806536.9A EP3806070B1 (en) 2018-05-25 2019-05-14 Secret aggregate function calculation system, secret calculation device, secret aggregate function calculation method, and program
AU2019273208A AU2019273208B2 (en) 2018-05-25 2019-05-14 Secure aggregate function computation system, secure computation apparatus, secure aggregate function computation method, and program
CN201980032660.9A CN112119442B (zh) 2018-05-25 2019-05-14 秘密聚合函数计算系统及方法、秘密计算装置、记录介质

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP2018-100626 2018-05-25
JP2018100626 2018-05-25

Publications (1)

Publication Number Publication Date
WO2019225401A1 true WO2019225401A1 (ja) 2019-11-28

Family

ID=68616723

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2019/019093 Ceased WO2019225401A1 (ja) 2018-05-25 2019-05-14 秘密集約関数計算システム、秘密計算装置、秘密集約関数計算方法、およびプログラム

Country Status (6)

Country Link
US (1) US11593362B2 (ja)
EP (1) EP3806070B1 (ja)
JP (1) JP6989006B2 (ja)
CN (1) CN112119442B (ja)
AU (1) AU2019273208B2 (ja)
WO (1) WO2019225401A1 (ja)

Cited By (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2022264237A1 (ja) * 2021-06-14 2022-12-22 日本電信電話株式会社 累積計算装置、累積計算方法、及びプログラム
JPWO2023062834A1 (ja) * 2021-10-15 2023-04-20
WO2023157117A1 (ja) * 2022-02-16 2023-08-24 日本電信電話株式会社 秘密計算装置、秘密計算方法、プログラム
JPWO2023157118A1 (ja) * 2022-02-16 2023-08-24
JP2024515332A (ja) * 2021-08-18 2024-04-08 テンセント・テクノロジー・（シェンジェン）・カンパニー・リミテッド 秘匿マルチパーティ計算に基づく極値の決定方法、装置、コンピュータ機器及びコンピュータプログラム
WO2024228294A1 (ja) * 2023-05-01 2024-11-07 エヌ・ティ・ティ・コミュニケーションズ株式会社 分析装置、分析方法及び分析プログラム
WO2025062484A1 (ja) * 2023-09-19 2025-03-27 日本電信電話株式会社 秘密パーセンタイル値計算装置、秘密パーセンタイル値計算方法

Families Citing this family (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US11307860B1 (en) * 2019-11-22 2022-04-19 Blaize, Inc. Iterating group sum of multiple accumulate operations
CN114153854B (zh) * 2022-02-09 2022-05-10 支付宝(杭州)信息技术有限公司 一种基于秘密分享的多键分组信息获取方法和系统
JP7740543B2 (ja) * 2022-06-02 2025-09-17 Ｎｔｔ株式会社 秘密計算装置、秘密計算方法、プログラム

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH0581337A (ja) * 1991-09-21 1993-04-02 Toshiba Corp データ処理装置
JP2012154968A (ja) * 2011-01-21 2012-08-16 Nippon Telegr & Teleph Corp <Ntt> セキュア集合関数システム、秘密集合関数装置、セキュア集合関数処理方法、セキュア集合関数プログラム
WO2015107951A1 (ja) * 2014-01-17 2015-07-23 日本電信電話株式会社 秘密計算方法、秘密計算システム、ソート装置及びプログラム

Family Cites Families (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH03210684A (ja) * 1990-01-12 1991-09-13 Mitsubishi Electric Corp 神経回路網装置
JP3601719B2 (ja) * 1997-04-18 2004-12-15 富士通株式会社 相関のあるデータ組み合わせの数え上げ方式
US7761450B1 (en) * 2003-12-24 2010-07-20 Teradata Us, Inc. Computing percentages in a database system
JP5506705B2 (ja) * 2011-01-24 2014-05-28 日本電信電話株式会社 秘密マッチングシステム、秘密マッチング装置、秘密マッチング方法、秘密マッチングプログラム
JP5689826B2 (ja) * 2012-01-26 2015-03-25 日本電信電話株式会社 秘密計算システム、暗号化装置、秘密計算装置及びその方法、プログラム
JP5860378B2 (ja) * 2012-10-16 2016-02-16 日本電信電話株式会社 秘密計算システム、集約関数装置、秘密計算方法、およびプログラム
JP5907902B2 (ja) * 2013-01-21 2016-04-26 日本電信電話株式会社 秘密計算による表の等結合システム、方法
WO2015107780A1 (ja) * 2014-01-17 2015-07-23 日本電信電話株式会社 要素複製装置、要素複製方法、およびプログラム
EP3278491A4 (en) * 2015-03-15 2019-05-15 David Chaum PREPARED AND TRANSACTIONAL MIXTURE
JP5968484B1 (ja) * 2015-03-18 2016-08-10 日本電信電話株式会社 シェア復旧システム、シェア復旧方法、およびプログラム
EP3384424A4 (en) * 2015-12-03 2019-07-24 Unbound Tech Ltd SECURITY OF SQL-BASED DATABASES WITH CRYPTOGRAPHIC PROTOCOLS

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH0581337A (ja) * 1991-09-21 1993-04-02 Toshiba Corp データ処理装置
JP2012154968A (ja) * 2011-01-21 2012-08-16 Nippon Telegr & Teleph Corp <Ntt> セキュア集合関数システム、秘密集合関数装置、セキュア集合関数処理方法、セキュア集合関数プログラム
WO2015107951A1 (ja) * 2014-01-17 2015-07-23 日本電信電話株式会社 秘密計算方法、秘密計算システム、ソート装置及びプログラム

Non-Patent Citations (4)

* Cited by examiner, † Cited by third party
Title
DAI IKARASHIKOJI CHIDAKOKI HAMADAKATSUMI TAKAHASHI: "Secure Database Operations Using An Improved 3-party Verifiable Secure Function Evaluation", THE 2011 SYMPOSIUM ON CRYPTOGRAPHY AND INFORMATION SECURITY, 2011
DAI IKARASHIKOKI HAMADARYO KIKUCHIKOJI CHIDA: "A Design and an Implementation of Super-highspeed Multi-party Sorting: The Day When Multi-party Computation Reaches Scripting Languages", COMPUTER SECURITY SYMPOSIUM, 2017
KIRIBUCHI, NAOTO ET AL.: "Programmable secure computation library MEVAL3", THE 2018 SYMPOSIUM ON CRYPTOGRAPHY AND INFORMATION SECURITY(SCIS2018, 23 January 2018 (2018-01-23), pages 1 - 8, XP009524184 *
See also references of EP3806070A4

Cited By (17)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP7544274B2 (ja) 2021-06-14 2024-09-03 日本電信電話株式会社 累積計算装置、累積計算方法、及びプログラム
JPWO2022264237A1 (ja) * 2021-06-14 2022-12-22
WO2022264237A1 (ja) * 2021-06-14 2022-12-22 日本電信電話株式会社 累積計算装置、累積計算方法、及びプログラム
JP7651816B2 (ja) 2021-08-18 2025-03-27 テンセント・テクノロジー・（シェンジェン）・カンパニー・リミテッド 秘匿マルチパーティ計算に基づく極値の決定方法、装置、コンピュータ機器及びコンピュータプログラム
US12506603B2 (en) 2021-08-18 2025-12-23 Tencent Technology (Shenzhen) Company Limited Method, device, and storage medium for determining extremum based on secure multi-party computation
JP2024515332A (ja) * 2021-08-18 2024-04-08 テンセント・テクノロジー・（シェンジェン）・カンパニー・リミテッド 秘匿マルチパーティ計算に基づく極値の決定方法、装置、コンピュータ機器及びコンピュータプログラム
WO2023062834A1 (ja) * 2021-10-15 2023-04-20 日本電信電話株式会社 秘密分割装置、秘密分割方法、及びプログラム
JP7694684B2 (ja) 2021-10-15 2025-06-18 日本電信電話株式会社 秘密分割装置、秘密分割方法、及びプログラム
JPWO2023062834A1 (ja) * 2021-10-15 2023-04-20
JPWO2023157117A1 (ja) * 2022-02-16 2023-08-24
WO2023157117A1 (ja) * 2022-02-16 2023-08-24 日本電信電話株式会社 秘密計算装置、秘密計算方法、プログラム
WO2023157118A1 (ja) * 2022-02-16 2023-08-24 日本電信電話株式会社 秘密計算装置、秘密計算方法、プログラム
JP7768330B2 (ja) 2022-02-16 2025-11-12 Ｎｔｔ株式会社 秘密計算装置、秘密計算方法、プログラム
JP7768329B2 (ja) 2022-02-16 2025-11-12 Ｎｔｔ株式会社 秘密計算装置、秘密計算方法、プログラム
JPWO2023157118A1 (ja) * 2022-02-16 2023-08-24
WO2024228294A1 (ja) * 2023-05-01 2024-11-07 エヌ・ティ・ティ・コミュニケーションズ株式会社 分析装置、分析方法及び分析プログラム
WO2025062484A1 (ja) * 2023-09-19 2025-03-27 日本電信電話株式会社 秘密パーセンタイル値計算装置、秘密パーセンタイル値計算方法

Also Published As

Publication number Publication date
EP3806070A1 (en) 2021-04-14
AU2019273208B2 (en) 2021-09-16
AU2019273208A1 (en) 2020-12-10
US11593362B2 (en) 2023-02-28
JPWO2019225401A1 (ja) 2021-05-27
CN112119442B (zh) 2024-07-12
US20210191927A1 (en) 2021-06-24
EP3806070A4 (en) 2022-01-26
JP6989006B2 (ja) 2022-01-05
EP3806070B1 (en) 2023-07-19
CN112119442A (zh) 2020-12-22

Similar Documents

Publication Publication Date Title
JP6989006B2 (ja) 秘密集約関数計算システム、秘密計算装置、秘密集約関数計算方法、およびプログラム
JP6973633B2 (ja) 秘密集約最大値システム、秘密集約最小値システム、秘密計算装置、秘密集約最大値方法、秘密集約最小値方法、およびプログラム
JP6973632B2 (ja) 秘密集約総和システム、秘密計算装置、秘密集約総和方法、およびプログラム
JP6605746B2 (ja) 秘密等結合システム、秘密等結合装置、秘密等結合方法、プログラム
JP6973634B2 (ja) 秘密集約中央値システム、秘密計算装置、秘密集約中央値方法、およびプログラム
JP6973629B2 (ja) 秘密集約順位システム、秘密計算装置、秘密集約順位方法、およびプログラム
JP7017178B2 (ja) 秘密クロス集計システム、秘密計算装置、秘密クロス集計方法、およびプログラム
JP7081663B2 (ja) 秘密結合システム、方法、秘密計算装置及びプログラム
WO2023281693A1 (ja) 秘密計算システム、装置、方法及びプログラム

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 19806536

Country of ref document: EP

Kind code of ref document: A1

ENP Entry into the national phase

Ref document number: 2020521167

Country of ref document: JP

Kind code of ref document: A

NENP Non-entry into the national phase

Ref country code: DE

ENP Entry into the national phase

Ref document number: 2019273208

Country of ref document: AU

Date of ref document: 20190514

Kind code of ref document: A

ENP Entry into the national phase

Ref document number: 2019806536

Country of ref document: EP

Effective date: 20210111