WO2019176831A1 - 秘密表参照システム、方法、秘密計算装置及びプログラム - Google Patents

秘密表参照システム、方法、秘密計算装置及びプログラム Download PDF

Info

Publication number
WO2019176831A1
WO2019176831A1 PCT/JP2019/009596 JP2019009596W WO2019176831A1 WO 2019176831 A1 WO2019176831 A1 WO 2019176831A1 JP 2019009596 W JP2019009596 W JP 2019009596W WO 2019176831 A1 WO2019176831 A1 WO 2019176831A1
Authority
WO
WIPO (PCT)
Prior art keywords
vector
share
permutation
secret
elements
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/009596
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 JP2020506500A priority Critical patent/JP7031732B2/ja
Priority to CN201980018258.5A priority patent/CN111886642A/zh
Priority to AU2019234710A priority patent/AU2019234710B2/en
Priority to EP19768155.4A priority patent/EP3767609A4/en
Priority to US16/977,954 priority patent/US11480991B2/en
Publication of WO2019176831A1 publication Critical patent/WO2019176831A1/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
    • G06F1/00—Details not covered by groups G06F3/00 - G06F13/00 and G06F21/00
    • G06F1/02—Digital function generators
    • G06F1/03—Digital function generators working, at least partly, by table look-up
    • 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/008—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols involving homomorphic encryption
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/10—Complex mathematical operations
    • G06F17/16—Matrix or vector computation, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/22—Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc
    • G06F7/24—Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers sorting methods in general
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/76—Arrangements for rearranging, permuting or selecting data according to predetermined rules, independently of the content of the data
    • 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 referring to a lookup table while maintaining confidentiality.
  • Non-Patent Document 1 A technique described in Non-Patent Document 1 is known as a technique for referring to a lookup table while maintaining confidentiality.
  • Non-Patent Document 1 has a relatively large amount of communication.
  • This invention is to provide a secret table reference system, method, secret calculation apparatus, and program with a smaller communication volume than before.
  • a secret table reference system is a secret table reference system including a plurality of secret calculation devices, wherein F is an arbitrary field, m is an integer of 2 or more, and n t is 1 or more.
  • F is an arbitrary field
  • m is an integer of 2 or more
  • n t is 1 or more.
  • ⁇ is an arbitrary vector
  • [ ⁇ ] is a share where ⁇ is secretly distributed
  • ⁇ is an arbitrary permutation
  • ⁇ is a share where ⁇ is secretly distributed
  • v m-dimensional Vector v ⁇ F m
  • d is a vector d ⁇ F nt consisting of elements of a set of input values of a predetermined lookup table
  • r is a vector consisting of elements of a set of output values of a lookup table
  • the plurality of secret computing devices use the share [d] of the vector d and the share [v] of the vector v to calculate the share [v ′] of the vector v′ ⁇ F
  • the amount of communication can be reduced as compared with the prior art.
  • FIG. 1 is a diagram illustrating a functional configuration of the secret table reference 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 table reference method.
  • the secret table reference system includes N ( ⁇ 2) secret computing 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.
  • 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 a first combining unit 11 n , a difference calculating unit 12 n , a second combining unit 13 n , a replacement calculating unit 14 n, and a replacement applying unit 15. n , a vector generation unit 16 n , an inverse replacement application unit 17 n, and an output unit 18 n .
  • the secret table reference method of the embodiment is realized by performing processing of each step described later.
  • the processing of each step is performed by secret calculation. That is, the secret computing device 1 n performs the processing of each step without restoring the share, in other words, without knowing the contents of the share.
  • 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 S1> A share [d] of the vector d and a share [v] of the vector v are input to the first coupling units 11 1 ,..., 11 N.
  • the first combining units 11 1 ,..., 11 N combine the share [d] and the share [v] to generate a share [v ′] ⁇ [F] m + nt . More specifically, the first combining unit 11 1 ,..., 11 N uses the share [d] and the share [v] to share the vector v′ ⁇ F m + nt in which the vector d and the vector v are combined. [v ′] is generated (step S1).
  • the generated shared [v '] is substituted calculator 14 1, ..., and output to 14 N.
  • F is an arbitrary field
  • m is an integer of 2 or more
  • n t is an integer of 1 or more.
  • v is an m-dimensional vector v ⁇ F m
  • d is a vector d ⁇ F nt composed of elements of a set of input values of a predetermined lookup table.
  • the vector v is a vector composed of attribute values of certain attributes in a certain table, for example.
  • ⁇ is an arbitrary vector, and [ ⁇ ] is a share in which ⁇ is secretly distributed.
  • the vector d (0,1,2,3) T.
  • the difference calculation units 12 1 ,..., 12 N generate a share [r ′′] based on the share [r]. More specifically, the difference calculation units 12 1 ,..., 12 N use the share [r] as a difference between an element of the vector r and the element before the element as an element corresponding to the element. A share [r ′′] of the vector r ′′ is generated (step S2).
  • the generated shared [v '] is substituted calculator 14 1, ..., and output to 14 N.
  • R is a vector composed of elements of the set of output values of the lookup table.
  • the i-th element of the vector r '' is “i-th element of vector r” ⁇ “i-1-th element of vector r”.
  • i 1
  • the i-th element of the vector r ′′ is the i-th element of the vector r. That is, the first element of the vector r ′′ is the first element of the vector r.
  • the vector r (1,5,2,3) T.
  • the vector r ′′ (1,4, ⁇ 3,1) T.
  • the second combining units 13 1 ,..., 13 N combine the share [r ′′] and the zero vector to generate a share [r ′] ⁇ [F] m + nt . More specifically, the second combining unit 13 1 ,..., 13 N uses the share [r ′′] to generate a vector r′ ⁇ F m + nt in which the vector r ′′ and the m-dimensional zero vector are combined. Share [r '] is generated (step S3).
  • the generated shared [r '] is substituted applying section 15 1, ..., and output to 15 N.
  • the replacement calculation units 14 1 ,..., 14 N generate ⁇ of the share [v ′]. More specifically, permutation calculation units 14 1 ,..., 14 N use share [v ′] to generate a share ⁇ of permutation ⁇ that stably sorts vector v ′ in ascending order (step S4). ).
  • the generated shares ⁇ are output to the replacement application units 15 1 ,..., 15 N.
  • “Stable sort” means that the order of equivalent data before sorting is preserved after sorting. Where ⁇ is an arbitrary substitution, ⁇ is a share in which ⁇ is secretly shared.
  • Sort ⁇ can be generated, for example, by the method described in Reference Document 1 below.
  • the generated shared [s] is the vector generation unit 16 1, ..., and output to 16 N.
  • the vector generation units 16 1 ,..., 16 N generate a prefix-sum [s ′] of the share [s]. More specifically, the vector generation unit 16 1 ,..., 16 N uses the share [s] to have a vector s ′ having the sum from the first element of the vector s to a certain element as an element corresponding to the certain element. Share [s'] is generated (step S6).
  • the generated shared [s'] is inverse permutation application unit 17 1, ..., and output to 17 N.
  • the vector s (1,4,0,0, -3,1,0) T
  • the vector s ′ (1,5,5,5,2,3,3) T .
  • the inverse permutation application units 17 1 ,..., 17 N reversely apply ⁇ to the share [s ′] to generate the share [s ′′]. More specifically, the inverse permutation application unit 17 1 ,..., 17 N uses the share [s ′] and the share ⁇ to apply the vector s ′ with the inverse permutation ⁇ ⁇ 1 of the permutation ⁇ . A share [s ''] of s '' is generated (step S7).
  • the generated share [s ''] is output to the output units 18 1 ,..., 18 N.
  • the output units 18 1 ,..., 18 N output the n t + 1th and subsequent element strings of the share [s ′′]. More specifically, the output units 18 1 ,..., 18 N use the share [s ′′] to share the vector x ⁇ F m consisting of n t +1 and subsequent elements of the vector s ′′ [x ] Is generated (step S8).
  • the generated share [x] is output as the final calculation result by the secret table reference system.
  • the program describing the processing contents can be recorded on a computer-readable recording medium.
  • a computer-readable recording medium for example, 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)
  • General Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • Mathematical Physics (AREA)
  • Computational Mathematics (AREA)
  • Pure & Applied Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Data Mining & Analysis (AREA)
  • Signal Processing (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Computer Security & Cryptography (AREA)
  • Algebra (AREA)
  • Computing Systems (AREA)
  • Databases & Information Systems (AREA)
  • Software Systems (AREA)
  • Computer Hardware Design (AREA)
  • Complex Calculations (AREA)
  • Storage Device Security (AREA)

Abstract

秘密表参照システムは、d及びvが結合されたv'∈Fm+ntの[v']を生成する第一結合部１１nと、rのある要素とそのある要素の前の要素との差分をそのある要素に対応する要素として持つr''の[r'']を生成する差分計算部１２nと、r''及びm次元の零が結合されたr'∈Fm+ntの[r']を生成する第二結合部１３nと、v'を昇順に安定ソートする置換σの{{σ}}を生成する置換計算部１４nと、r'に置換σを適用したs:=σ(r')の[s]を生成する置換適用部１５nと、sのprefix-sum s'の[s']を生成するベクトル生成部１６nと、s'に置換σの逆置換σ-1を適用したs''の[s'']を生成する逆置換適用部と、s''のnt+1番目以降の要素からなるx∈Fmの[x]を生成する出力部１７nと、を備えている。

Description

秘密表参照システム、方法、秘密計算装置及びプログラム
　この発明は、秘密計算技術に関し、特に、秘匿性を保ったままルックアップテーブルを参照する技術に関する。
　秘匿性を保ったままルックアップテーブルを参照する技術として、非特許文献１に記載された技術が知られている。
濱田浩気，五十嵐大，千田浩司，"秘密計算一括写像計算の効率化"，2014年暗号と情報セキュリティシンポジウム
　しかしながら、非特許文献１に記載された技術では、通信量が比較的多かった。
　この発明は、通信量が従来よりも少ない秘密表参照システム、方法、秘密計算装置及びプログラムを提供することである。
　この発明の一態様による秘密表参照システムは、複数の秘密計算装置を含む秘密表参照システムであって、Fは任意の体であり、mは２以上の整数であり、ntは１以上の整数であり、αを任意のベクトルとして[α]はαが秘密分散されたシェアであり、βを任意の置換として{{β}}はβが秘密分散されたシェアであり、vはm次元ベクトルv∈Fｍであり、dは所定のルックアップテーブルの入力値の集合の要素からなるベクトルd∈Fntであり、rはルックアップテーブルの出力値の集合の要素からなるベクトルであり、複数の秘密計算装置は、ベクトルdのシェア[d]及びベクトルvのシェア[v]を用いて、ベクトルd及びベクトルvが結合されたベクトルv'∈Fm+ntのシェア[v']を生成する複数の第一結合部と、ベクトルrのシェア[r]を用いて、ベクトルrのある要素とそのある要素の前の要素との差分をそのある要素に対応する要素として持つベクトルr''のシェア[r'']を生成する複数の差分計算部と、シェア[r'']を用いて、ベクトルr''及びm次元の零ベクトルが結合されたベクトルr'∈Fm+ntのシェア[r']を生成する複数の第二結合部と、シェア[v']を用いて、ベクトルv'を昇順に安定ソートする置換σのシェア{{σ}}を生成する複数の置換計算部と、シェア[r']及びシェア{{σ}}を用いて、ベクトルr'に置換σを適用したベクトルs:=σ(r')のシェア[s]を生成する複数の置換適用部と、シェア[s]を用いて、ベクトルsの最初の要素からある要素までの総和をそのある要素に対応する要素として持つベクトルs'のシェア[s']を生成する複数のベクトル生成部と、シェア[s']及びシェア{{σ}}を用いて、ベクトルs'に置換σの逆置換σ-1を適用したベクトルs''のシェア[s'']を生成する複数の逆置換適用部と、シェア[s'']を用いて、ベクトルs''のnt+1番目以降の要素からなるベクトルx∈Fmのシェア[x]を生成する複数の出力部と、を備えている。
　この発明によれば、通信量を従来よりも少なくすることができる。
図１は、秘密表参照システムの機能構成を例示する図である。 図２は、秘密計算装置の機能構成を例示する図である。 図３は、秘密表参照方法の処理手続きを例示する図である。
　以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
　図１を参照して、実施形態の秘密表参照システムの構成例を説明する。秘密表参照システムは、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と、差分計算部１２nと、第二結合部１３nと、置換計算部１４nと、置換適用部１５nと、ベクトル生成部１６nと、逆置換適用部１７nと、出力部１８nとを備えている。この秘密計算装置１n（1≦n≦N）の各構成部が他の秘密計算装置１n'（n'=1, …, N、ただしn≠n'）の各構成部と協調しながら後述する各ステップの処理を行うことにより実施形態の秘密表参照方法が実現される。
　なお、各ステップの処理は、秘密計算により行われる。すなわち、秘密計算装置１nは、シェアを復元することなく、言い換えればシェアの中身を知ることなく、各ステップの処理を行う。
　秘密計算装置１nは、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。秘密計算装置１nは、例えば、中央演算処理装置の制御のもとで各処理を実行する。秘密計算装置１nに入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて中央演算処理装置へ読み出されて他の処理に利用される。秘密計算装置１nの各処理部は、少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。
　図３を参照して、実施形態の秘密表参照システムが実行する秘密表参照方法の処理手続きを説明する。
　＜ステップＳ１＞
　第一結合部１１1,…,１１Nに、ベクトルdのシェア[d]及びベクトルvのシェア[v]が入力される。
　第一結合部１１1,…,１１Nは、シェア[d]とシェア[v]を結合してシェア[v']∈[F]m+ntを生成する。より詳細には、第一結合部１１1,…,１１Nは、シェア[d]及びシェア[v]を用いて、ベクトルd及びベクトルvが結合されたベクトルv'∈Fm+ntのシェア[v']を生成する（ステップＳ１）。
　生成されたシェア[v']は、置換計算部１４1,…,１４Nに出力される。
　Fは任意の体であり、mは２以上の整数であり、ntは１以上の整数である。また、vはm次元ベクトルv∈Fｍであり、dは所定のルックアップテーブルの入力値の集合の要素からなるベクトルd∈Fntである。ベクトルvは、例えばある表のある属性の属性値からなるベクトルである。αを任意のベクトルとして、[α]はαが秘密分散されたシェアである。
　[F]m+nt,Fntの上付き文字の中のntは、「nt」を意味する。このように、上付き文字の中では、更なる上付き文字及び下付き文字の表現を省略することがある。
　例えば、ルックアップテーブルtがt:{0,1,2,3}→{1,5,2,3}である場合には、ベクトルd=(0,1,2,3)Tとなる。このとき、ベクトルv=(1,3,1)Tである場合には、ベクトルv'=(0,1,2,3,1,3,1)Tとなる。
　＜ステップＳ２＞
　差分計算部１２1,…,１２Nに、ベクトルrのシェア[r]が入力される。
　差分計算部１２1,…,１２Nは、シェア[r]に基づいてシェア[r'']を生成する。より詳細には、差分計算部１２1,…,１２Nは、シェア[r]を用いて、ベクトルrのある要素とそのある要素の前の要素との差分をそのある要素に対応する要素として持つベクトルr''のシェア[r'']を生成する（ステップＳ２）。
　生成されたシェア[v']は、置換計算部１４1,…,１４Nに出力される。
　rは、ルックアップテーブルの出力値の集合の要素からなるベクトルである。
　ベクトルr''のi番目の要素は、「ベクトルrのi番目の要素」-「ベクトルrのi-1番目の要素」である。ただし、i=1の場合には、ベクトルr''のi番目の要素は、ベクトルrのi番目の要素となる。すなわち、ベクトルr''の１番目の要素は、ベクトルrの１番目の要素となる。
　例えば、ルックアップテーブルtがt:{0,1,2,3}→{1,5,2,3}である場合には、ベクトルr=(1,5,2,3)Tとなる。この場合、ベクトルr''=(1,4,-3,1)Tとなる。
　＜ステップＳ３＞
　第二結合部１３1,…,１３Nに、シェア[r'']が入力される。
　第二結合部１３1,…,１３Nは、シェア[r'']と零ベクトルを結合してシェア[r']∈[F]m+ntを生成する。より詳細には、第二結合部１３1,…,１３Nは、シェア[r'']を用いて、ベクトルr''及びm次元の零ベクトルが結合されたベクトルr'∈Fm+ntのシェア[r']を生成する（ステップＳ３）。
　生成されたシェア[r']は、置換適用部１５1,…,１５Nに出力される。
　例えば、ベクトルr''=(1,4,-3,1)Tであり、m=3である場合には、ベクトルr'=(1,4,-3,1,0,0,0)Tとなる。
　＜ステップＳ４＞
　置換計算部１４1,…,１４Nに、シェア[v']が入力される。
　置換計算部１４1,…,１４Nは、シェア[v']の{{σ}}を生成する。より詳細には、置換計算部１４1,…,１４Nは、シェア[v']を用いて、ベクトルv'を昇順に安定ソートする置換σのシェア{{σ}}を生成する（ステップＳ４）。
　生成されたシェア{{σ}}は、置換適用部１５1,…,１５Nに出力される。
　安定ソートとは、同等なデータのソート前の順序が、ソート後も保存されるものをいう。βを任意の置換として、{{β}}はβが秘密分散されたシェアである。
　ソート{{σ}}の生成は、例えば以下の参考文献１に記載された方法で行うことができる。
　〔参考文献１〕五十嵐大，濱田浩気，菊池亮，千田浩司，"インターネット環境レスポンス1秒の統計処理を目指した, 秘密計算基数ソートの改良"，2014年暗号と情報セキュリティシンポジウム
　例えば、ベクトルv'=(0,1,2,3,1,3,1)Tである場合には、置換σは以下の式（１）のようになる。
Figure JPOXMLDOC01-appb-M000001
　＜ステップＳ５＞
　置換適用部１５1,…,１５Nに、シェア[r']及びシェア{{σ}}が入力される。
　置換適用部１５1,…,１５Nは、シェア[r']に{{σ}}を適用してシェア[s]:=[σ(r')]を生成する。より詳細には、置換適用部１５1,…,１５Nは、シェア[r']及びシェア{{σ}}を用いて、ベクトルr'に置換σを適用したベクトルs:=σ(r')のシェア[s]を生成する（ステップＳ５）。
　生成されたシェア[s]はベクトル生成部１６1,…,１６Nに出力される。
　置換{{σ}}の適用は、参考文献１に記載された方法で行うことができる。
　例えば、ベクトルr'=(1,4,-3,1,0,0,0)Tであり、置換σが式（１）で示される置換である場合には、ベクトルs=(1,4,0,0,-3,1,0)Tとなる。
　＜ステップＳ６＞
　ベクトル生成部１６1,…,１６Nに、シェア[s]が入力される。
　ベクトル生成部１６1,…,１６Nは、シェア[s]のprefix-sum [s']を生成する。より詳細には、ベクトル生成部１６1,…,１６Nは、シェア[s]を用いて、ベクトルsの最初の要素からある要素までの総和をそのある要素に対応する要素として持つベクトルs'のシェア[s']を生成する（ステップＳ６）。
　生成されたシェア[s']は、逆置換適用部１７1,…,１７Nに出力される。
　例えば、ベクトルs=(1,4,0,0,-3,1,0)Tである場合には、ベクトルs'=(1,5,5,5,2,3,3)Tとなる。
　＜ステップＳ７＞
　逆置換適用部１７1,…,１７Nに、シェア[s']及びシェア{{σ}}が入力される。
　逆置換適用部１７1,…,１７Nは、シェア[s']に{{σ}}を逆適用してシェア[s'']を生成する。より詳細には、逆置換適用部１７1,…,１７Nは、シェア[s']及びシェア{{σ}}を用いて、ベクトルs'に置換σの逆置換σ-1を適用したベクトルs''のシェア[s'']を生成する（ステップＳ７）。
　生成されたシェア[s'']は、出力部１８1,…,１８Nに出力される。
　逆置換{{σ-1}}の適用は、例えば以下の参考文献２に記載された方法で行うことができる。
　〔参考文献２〕桐淵直人，五十嵐大，諸橋玄武，濱田浩気，"属性情報と履歴情報の秘匿統合分析に向けた秘密計算による高速な等結合アルゴリズムとその実装"，2016年コンピュータセキュリティシンポジウム
　例えば、ベクトルs'=(1,5,5,5,2,3,3)Tであり、置換σが式（１）で示される置換である場合には、ベクトルs''=(1,5,2,3,5,3,5)Tとなる。
　なお、逆置換σ-1を適用とは、置換σを逆適用するということである。
　＜ステップＳ８＞
　出力部１８1,…,１８Nに、シェア[s'']が入力される。
　出力部１８1,…,１８Nは、シェア[s'']のnt+1番目以降の要素列を出力する。より詳細には、出力部１８1,…,１８Nは、シェア[s'']を用いて、ベクトルs''のnt+1番目以降の要素からなるベクトルx∈Fmのシェア[x]を生成する（ステップＳ８）。
　生成されたシェア[x]が、秘密表参照システムによる最終的な計算結果として出力される。
　例えば、ベクトルs''=(1,5,2,3,5,3,5)Tであり、nt=4である場合には、ベクトルx=(5,3,5)Tとなる。
　ルックアップテーブルtがt:{0,1,2,3}→{1,5,2,3}であり、ベクトルv=(1,3,1)Tである場合には、ベクトルx=(5,3,5)Tは、ベクトルv=(1,3,1)Tに対するルックアップテーブルtの参照結果となっている。
　このように、逆置換σ-1を用いることで、従来よりも通信量を少なくすることができる。
　以上、この発明の実施の形態について説明したが、具体的な構成は、これらの実施の形態に限られるものではなく、この発明の趣旨を逸脱しない範囲で適宜設計の変更等があっても、この発明に含まれることはいうまでもない。実施の形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
　［プログラム、記録媒体］
　上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
　この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
　また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
　このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
　また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
１1,…,１N　秘密計算装置
１１1,…,１１N　第一結合部
１２1,…,１２N　差分計算部
１３1,…,１３N　第二結合部
１４1,…,１４N　置換計算部
１５1,…,１５N　置換適用部
１６1,…,１６N　ベクトル生成部
１７1,…,１７N　逆置換適用部
１８1,…,１８N　出力部
２　通信網

Claims (4)

  1. 　複数の秘密計算装置を含む秘密表参照システムであって、
    　Fは任意の体であり、mは２以上の整数であり、ntは１以上の整数であり、αを任意のベクトルとして[α]はαが秘密分散されたシェアであり、βを任意の置換として{{β}}はβが秘密分散されたシェアであり、vはm次元ベクトルv∈Fｍであり、dは所定のルックアップテーブルの入力値の集合の要素からなるベクトルd∈Fntであり、rは上記ルックアップテーブルの出力値の集合の要素からなるベクトルであり、
    　上記複数の秘密計算装置は、
    　上記ベクトルdのシェア[d]及び上記ベクトルvのシェア[v]を用いて、上記ベクトルd及び上記ベクトルvが結合されたベクトルv'∈Fm+ntのシェア[v']を生成する複数の第一結合部と、
    　上記ベクトルrのシェア[r]を用いて、上記ベクトルrのある要素とそのある要素の前の要素との差分をそのある要素に対応する要素として持つベクトルr''のシェア[r'']を生成する複数の差分計算部と、
    　上記シェア[r'']を用いて、上記ベクトルr''及びm次元の零ベクトルが結合されたベクトルr'∈Fm+ntのシェア[r']を生成する複数の第二結合部と、
    　上記シェア[v']を用いて、上記ベクトルv'を昇順に安定ソートする置換σのシェア{{σ}}を生成する複数の置換計算部と、
    　上記シェア[r']及び上記シェア{{σ}}を用いて、上記ベクトルr'に上記置換σを適用したベクトルs:=σ(r')のシェア[s]を生成する複数の置換適用部と、
    　上記シェア[s]を用いて、上記ベクトルsの最初の要素からある要素までの総和をそのある要素に対応する要素として持つベクトルs'のシェア[s']を生成する複数のベクトル生成部と、
    　上記シェア[s']及び上記シェア{{σ}}を用いて、上記ベクトルs'に上記置換σの逆置換σ-1を適用したベクトルs''のシェア[s'']を生成する複数の逆置換適用部と、
    　上記シェア[s'']を用いて、上記ベクトルs''のnt+1番目以降の要素からなるベクトルx∈Fmのシェア[x]を生成する複数の出力部と、
    　を含む、
    　秘密表参照システム。
  2. 　請求項１の秘密表参照システムの秘密計算装置。
  3. 　Fは任意の体であり、mは２以上の整数であり、ntは１以上の整数であり、αを任意のベクトルとして[α]はαが秘密分散されたシェアであり、βを任意の置換として{{β}}はβが秘密分散されたシェアであり、vはm次元ベクトルv∈Fｍであり、dは所定のルックアップテーブルの入力値の集合の要素からなるベクトルd∈Fntであり、rは上記ルックアップテーブルの出力値の集合の要素からなるベクトルであり、
    　第一結合部が、上記ベクトルdのシェア[d]及び上記ベクトルvのシェア[v]を用いて、上記ベクトルd及び上記ベクトルvが結合されたベクトルv'∈Fm+ntのシェア[v']を生成する第一結合ステップと、
    　差分計算部が、上記ベクトルrのシェア[r]を用いて、上記ベクトルrのある要素とそのある要素の前の要素との差分をそのある要素に対応する要素として持つベクトルr''のシェア[r'']を生成する差分計算ステップと、
    　第二結合部が、上記シェア[r'']を用いて、上記ベクトルr''及びm次元の零ベクトルが結合されたベクトルr'∈Fm+ntのシェア[r']を生成する第二結合ステップと、
    　置換計算部が、上記シェア[v']を用いて、上記ベクトルv'を昇順に安定ソートする置換σのシェア{{σ}}を生成する置換計算ステップと、
    　置換適用部が、上記シェア[r']及び上記シェア{{σ}}を用いて、上記ベクトルr'に上記置換σを適用したベクトルs:=σ(r')のシェア[s]を生成する置換適用ステップと、
    　ベクトル生成部が、上記シェア[s]を用いて、上記ベクトルsの最初の要素からある要素までの総和をそのある要素に対応する要素として持つベクトルs'のシェア[s']を生成するベクトル生成ステップと、
    　逆置換適用部が、上記シェア[s']及び上記シェア{{σ}}を用いて、上記ベクトルs'に上記置換σの逆置換σ-1を適用したベクトルs''のシェア[s'']を生成する逆置換適用ステップと、
    　出力部が、上記シェア[s'']を用いて、上記ベクトルs''のnt+1番目以降の要素からなるベクトルx∈Fmのシェア[x]を生成する出力ステップと、
    　を含む秘密表参照方法。
  4. 　請求項３の秘密計算装置の各部としてコンピュータを機能させるためのプログラム。
PCT/JP2019/009596 2018-03-12 2019-03-11 秘密表参照システム、方法、秘密計算装置及びプログラム Ceased WO2019176831A1 (ja)

Priority Applications (5)

Application Number Priority Date Filing Date Title
JP2020506500A JP7031732B2 (ja) 2018-03-12 2019-03-11 秘密表参照システム、方法、秘密計算装置及びプログラム
CN201980018258.5A CN111886642A (zh) 2018-03-12 2019-03-11 秘密表参照系统、方法、秘密计算装置以及程序
AU2019234710A AU2019234710B2 (en) 2018-03-12 2019-03-11 Secret table reference system, method, secret calculation apparatus and program
EP19768155.4A EP3767609A4 (en) 2018-03-12 2019-03-11 SECRET TABLE REFERENCE SYSTEM, METHOD, DEVICE AND PROGRAM FOR SECRET CALCULATION
US16/977,954 US11480991B2 (en) 2018-03-12 2019-03-11 Secret table reference system, method, secret calculation apparatus and program

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP2018-043855 2018-03-12
JP2018043855 2018-03-12

Publications (1)

Publication Number Publication Date
WO2019176831A1 true WO2019176831A1 (ja) 2019-09-19

Family

ID=67906620

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2019/009596 Ceased WO2019176831A1 (ja) 2018-03-12 2019-03-11 秘密表参照システム、方法、秘密計算装置及びプログラム

Country Status (6)

Country Link
US (1) US11480991B2 (ja)
EP (1) EP3767609A4 (ja)
JP (1) JP7031732B2 (ja)
CN (1) CN111886642A (ja)
AU (1) AU2019234710B2 (ja)
WO (1) WO2019176831A1 (ja)

Families Citing this family (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US12524567B2 (en) * 2022-02-25 2026-01-13 BeeKeeperAI, Inc. Systems and methods for dataset selection optimization in a zero-trust computing environment

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2015107780A1 (ja) * 2014-01-17 2015-07-23 日本電信電話株式会社 要素複製装置、要素複製方法、およびプログラム

Family Cites Families (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH10107788A (ja) * 1996-10-01 1998-04-24 Bariafurii:Kk 電子データ置換法
EP1696601A1 (en) * 2005-02-28 2006-08-30 Bastien Chopard Symmetrical encryption method
US8103880B2 (en) * 2005-06-03 2012-01-24 Adobe Systems Incorporated Method for communication between computing devices using coded values
WO2010146139A1 (en) * 2009-06-19 2010-12-23 Irdeto B.V. White-box cryptographic system with configurable key using intermediate data modification
US9426652B2 (en) * 2010-09-09 2016-08-23 Joseph Nutaro High assurance authorization device
WO2013142980A1 (en) * 2012-03-30 2013-10-03 Irdeto Canada Corporation Securing accessible systems using variable dependent coding
JP5833757B2 (ja) * 2012-07-09 2015-12-16 日本電信電話株式会社 画像符号化方法、画像復号方法、画像符号化装置、画像復号装置、画像符号化プログラム、画像復号プログラム及び記録媒体
EP3057079A4 (en) * 2013-10-10 2017-06-07 Nippon Telegraph And Telephone Corporation Secret parallel processing device, secret parallel processing method, and program
EP3264396B1 (en) * 2016-06-28 2022-01-26 Eshard A method for protecting a substitution operation using a substitution table against a side-channel analysis

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2015107780A1 (ja) * 2014-01-17 2015-07-23 日本電信電話株式会社 要素複製装置、要素複製方法、およびプログラム

Non-Patent Citations (5)

* Cited by examiner, † Cited by third party
Title
DAI IKARASHIKOKI HAMADARYO KIKUCHIKOJI CHIDA: "An Improvement of Secure Sorting toward 1 sec. Response on Internet", SYMPOSIUM ON CRYPTOGRAPHY AND INFORMATION SECURITY, 2014
HAMADA, KOKI ET AL.: "A Batch Mapping Algorithm for Secure Function Evaluation", INFORMATION PROCESSING SOCIETY OF JAPAN RESEARCH REPORT 2012 (HEISEI 24) [CD-ROM], vol. J96-A, no. 4, 15 August 2012 (2012-08-15), XP008184067, ISSN: 0913-5707 *
KOKI HAMADADAI IKARASHIKOJI CHIDA: "Improved batch mapping algorithm for secure multi-party computation", SYMPOSIUM ON CRYPTOGRAPHY AND INFORMATION SECURITY, 2014
NAOTO KIRIBUCHIDAI IKARASHIGEMBU MOROHASHIKOKI HAMADA: "An Efficient Equi-join Algorithm for Secure Computation and Its Implementation toward Secure Comprehensive Analyses of Users' Attribute and History Information", COMPUTER SECURITY SYMPOSIUM, 2016
See also references of EP3767609A4

Also Published As

Publication number Publication date
CN111886642A (zh) 2020-11-03
JPWO2019176831A1 (ja) 2021-02-12
US20210041906A1 (en) 2021-02-11
EP3767609A4 (en) 2021-12-08
AU2019234710B2 (en) 2021-09-16
US11480991B2 (en) 2022-10-25
JP7031732B2 (ja) 2022-03-08
EP3767609A1 (en) 2021-01-20
AU2019234710A1 (en) 2020-10-01

Similar Documents

Publication Publication Date Title
EP3316235B1 (en) Device, method and program for secure multiparty comparison
US8891766B2 (en) Input consistency verification for two-party secure function evaluation
CN111898137A (zh) 一种联邦学习的隐私数据处理方法、设备及系统
US9473302B2 (en) Ciphertext processing device, ciphertext processing method, computer-readable recording medium, and information processing device
JP5872085B1 (ja) 分散値変換システム、分散値変換装置、分散値変換方法、およびプログラム
WO2017065123A1 (ja) 秘密乱数合成装置、秘密乱数合成方法、およびプログラム
JP6585846B2 (ja) 秘密計算システム、秘密計算装置、秘密計算方法、およびプログラム
US11329808B2 (en) Secure computation device, secure computation authentication system, secure computation method, and program
US11514192B2 (en) Secure reading apparatus, secure writing apparatus, method thereof, and program for reading and writing data in a sequence without revealing an access position
US12113890B2 (en) Homomorphic encryption using smart contracts
WO2019176831A1 (ja) 秘密表参照システム、方法、秘密計算装置及びプログラム
JPWO2019225531A1 (ja) 秘密一括近似システム、秘密計算装置、秘密一括近似方法、およびプログラム
JP7081663B2 (ja) 秘密結合システム、方法、秘密計算装置及びプログラム
JP7147840B2 (ja) 秘密重複排除フィルタ生成システム、秘密重複排除システム、これらの方法、秘密計算装置及びプログラム
Shin et al. Towards federated learning by kernels
Pamarthi et al. Exponential Ant-Lion Rider Optimization for Privacy Preservation in Cloud Computing
CN116401504A (zh) 奇异值分解方法、装置、计算机设备及介质
WO2020036125A1 (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: 19768155

Country of ref document: EP

Kind code of ref document: A1

ENP Entry into the national phase

Ref document number: 2020506500

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: 2019234710

Country of ref document: AU

Date of ref document: 20190311

Kind code of ref document: A

ENP Entry into the national phase

Ref document number: 2019768155

Country of ref document: EP

Effective date: 20201012