[go: up one dir, main page]

WO2018008545A1 - 秘密計算システム、秘密計算装置、秘密計算方法、およびプログラム - Google Patents

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

Info

Publication number
WO2018008545A1
WO2018008545A1 PCT/JP2017/024140 JP2017024140W WO2018008545A1 WO 2018008545 A1 WO2018008545 A1 WO 2018008545A1 JP 2017024140 W JP2017024140 W JP 2017024140W WO 2018008545 A1 WO2018008545 A1 WO 2018008545A1
Authority
WO
WIPO (PCT)
Prior art keywords
secret
array
row
column
calculation
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/JP2017/024140
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 US16/309,034 priority Critical patent/US11121868B2/en
Priority to CN201780037589.4A priority patent/CN109328377B/zh
Priority to EP17824150.1A priority patent/EP3483866B1/en
Priority to JP2018526338A priority patent/JP6534778B2/ja
Publication of WO2018008545A1 publication Critical patent/WO2018008545A1/ja
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Images

Classifications

    • 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/0861—Generation of secret information including derivation or calculation of cryptographic keys or passwords
    • 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/18—Complex mathematical operations for evaluating statistical data, e.g. average values, frequency distributions, probability functions, regression analysis
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F21/00—Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
    • G06F21/60—Protecting data
    • G06F21/602—Providing cryptographic facilities or services
    • G—PHYSICS
    • G09—EDUCATION; CRYPTOGRAPHY; DISPLAY; ADVERTISING; SEALS
    • G09C—CIPHERING OR DECIPHERING APPARATUS FOR CRYPTOGRAPHIC OR OTHER PURPOSES INVOLVING THE NEED FOR SECRECY
    • G09C1/00—Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system
    • 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/0861—Generation of secret information including derivation or calculation of cryptographic keys or passwords
    • H04L9/0869—Generation of secret information including derivation or calculation of cryptographic keys or passwords involving random numbers or seeds
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F21/00—Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
    • G06F21/70—Protecting specific internal or peripheral components, in which the protection of a component leads to protection of the entire computer
    • G06F21/71—Protecting specific internal or peripheral components, in which the protection of a component leads to protection of the entire computer to assure secure computing or processing of information
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F21/00—Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
    • G06F21/70—Protecting specific internal or peripheral components, in which the protection of a component leads to protection of the entire computer
    • G06F21/71—Protecting specific internal or peripheral components, in which the protection of a component leads to protection of the entire computer to assure secure computing or processing of information
    • G06F21/72—Protecting specific internal or peripheral components, in which the protection of a component leads to protection of the entire computer to assure secure computing or processing of information in cryptographic circuits
    • 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
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L63/00—Network architectures or network communication protocols for network security
    • H04L63/04—Network architectures or network communication protocols for network security for providing a confidential data exchange among entities communicating through data packet networks
    • H04L63/0407—Network architectures or network communication protocols for network security for providing a confidential data exchange among entities communicating through data packet networks wherein the identity of one or more communicating identities is hidden
    • H04L63/0421—Anonymous communication, i.e. the party's identifiers are hidden from the other party or parties, e.g. using an anonymizer
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L63/00—Network architectures or network communication protocols for network security
    • H04L63/04—Network architectures or network communication protocols for network security for providing a confidential data exchange among entities communicating through data packet networks
    • H04L63/0428—Network architectures or network communication protocols for network security for providing a confidential data exchange among entities communicating through data packet networks wherein the data content is protected, e.g. by encrypting or encapsulating the payload

Definitions

  • This invention relates to a cryptographic application technique, and more particularly to a technique for calculating a Fisher's exact test without revealing input data.
  • Fischer's exact test is widely known as one of the statistical tests that test hypotheses regarding whether or not there is an association between an explanatory variable given as a 2 ⁇ 2 contingency table and an objective variable.
  • Non-Patent Document 1 describes a genome-wide association analysis (GWAS: Genome-Wide Association Study) as an application example of the Fisher exact test.
  • the following table is an example of a 2 ⁇ 2 contingency table in which n subjects were classified and counted according to the presence or absence of mutations and the occurrence of specific diseases.
  • a, b, c, d are frequencies
  • n 1 ⁇ , n 2 ⁇ , n ⁇ 1 , n ⁇ 2 are subtotals
  • a, b, c, d, n 1 ⁇ , n 2 ⁇ , n ⁇ 1 , n ⁇ 2 are all non-negative integers.
  • the probability p i defined by the equation (1) is calculated for the non-negative integer i, and the explanation is given by the magnitude relationship between the probability p shown in the equation (2) and a predetermined value ⁇ called a significance level. Investigate whether there is an association between the variable (in the above table, the presence or absence of mutation) and the target variable (in the above table, the presence or absence of disease).
  • p a is the probability value calculated by the equation (1) for contingency table for a, b, c, and power and d is the actual aggregate value.
  • Non-Patent Document 2 As a method of obtaining a specific calculation result without restoring the encrypted numerical value, there is a method called secret calculation (see Non-Patent Document 2, for example).
  • encryption is performed such that numerical fragments are distributed to three secret calculation devices, and the three secret calculation devices perform cooperative calculation, thereby performing addition / subtraction and constant addition without restoring the numerical values.
  • Multiplication, constant multiplication, logical operation (negation, logical product, logical sum, exclusive logical sum), data format conversion (integer, binary number) results distributed to three secret computing devices, ie encrypted Can be held as is.
  • Non-Patent Document 3 proposes a method of performing chi-square test while keeping genome information secret.
  • the purpose of the secret calculation technique of the present invention is to efficiently calculate the Fisher exact test by secret calculation in view of the above points.
  • the function values f (a i ), f (b i ), f of the frequencies to be calculated without revealing the frequencies a, b, c, d of the contingency table that is the input for the Fisher exact test. (c i ) and f (d i ) can be obtained efficiently. Therefore, the Fisher exact test can be efficiently calculated by the secret calculation. Furthermore, the Fisher exact test can be executed while keeping the genome information secret. For example, it is possible to obtain the results of Fisher's exact test of integrated data without secretly disclosing the genome data possessed by multiple research institutions, and to perform genome analysis with extremely high security level. It can be expected that this will lead to the provision of the environment, and further development of medical care.
  • FIG. 1 is a diagram illustrating a functional configuration of a secret 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 calculation method.
  • a value obtained by concealing a value a by encryption, secret sharing, or the like is called a secret sentence of a, and is expressed as ⁇ a>.
  • A is called the plaintext of ⁇ a>.
  • the concealment is secret sharing, a set of secret sharing fragments of each party is referred to by ⁇ a>.
  • An array of secret text ⁇ a '> ( ⁇ a [d + 1]>,..., ⁇ a [n-1]>, with ⁇ a> shifted left by d
  • the process of calculating ⁇ a [0]>, ⁇ a [1]>, ..., ⁇ a [d-1]>) is called a concealment shift and is described by the following equation.
  • the batch reading algorithm is described by the following equation.
  • the collective reading algorithm can be more efficiently executed by implementing the above-described secret shift as follows.
  • the batch reading algorithm applicable in the present invention is not limited to this, and any algorithm can be used as long as it can realize the above-described input / output.
  • an array of secret text of size n ⁇ a> ( ⁇ a [0]>, ⁇ a [1]>,..., ⁇ a [n-1]>), an integer between 0 and less than n representing the position
  • a secret sentence ⁇ x> of x and m plaintexts j 0 ,..., j m ⁇ 1 representing a relative position from x are input.
  • the secret calculation system includes n ( ⁇ 3) secret calculation devices 1 1 ,..., 1 n as illustrated in FIG.
  • the secret computing devices 1 1 ,..., 1 n are each connected to the communication network 2.
  • the communication network 2 is a circuit-switching or packet-switching-type communication network configured such that the secret computing devices 1 1 ,..., 1 n can communicate with each other, for example, the Internet, a LAN (Local Area Network), A WAN (Wide Area Network) or the like can be used.
  • Each device does not necessarily need to be able to communicate online via the communication network 2.
  • information input to the secret computing device 1 i i ⁇ ⁇ 1,..., N ⁇
  • a portable recording medium such as a magnetic tape or a USB memory, and is input offline from the portable recording medium. It may be configured.
  • the secret computing device 1 includes an input unit 11, a calculation range determining unit 12, a pre-calculating unit 13, a concealing unit 14, a batch reading unit 15, and an output unit 16, as illustrated in FIG.
  • the secret calculation apparatus 1 performs the process of each step illustrated in FIG. 3 to realize the secret calculation method of the first embodiment.
  • the secret computing device 1 is, for example, a special computer configured by reading a special program into a known or dedicated computer having a central processing unit (CPU: Central Processing Unit), a main storage device (RAM: Random Access Memory), and the like. Device.
  • the secret computing device 1 executes each process under the control of the central processing unit.
  • the data input to the secret computing device 1 and the data obtained in each process 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 may be configured by hardware such as an integrated circuit.
  • step S11 the secret text ( ⁇ a>, ⁇ b>, ⁇ c>, ⁇ d>) of the frequency set (a, b, c, d) of the 2 ⁇ 2 contingency table is input to the input unit 11.
  • the 2 ⁇ 2 contingency table is defined in the following table, and a, b, c, and d are non-negative integers.
  • step S12 the calculation range determination unit 12 determines values i 0 , i 1 , x 0 , x 1 that satisfy i 0 ⁇ i 1 , x 0 ⁇ x 1 .
  • i 0 ⁇ n
  • i 1 n
  • x 0 ⁇ n
  • x 1 2n.
  • the values x 0 and x 1 are sent to the precalculation unit 13.
  • the values i 0 and i 1 are sent to the batch reading unit 15.
  • the secret text array ⁇ M> is sent to the batch reading unit 15.
  • step S16 the secret text ( ⁇ f (a i )>, ⁇ f (b i )>, ⁇ f (c i )>, ⁇ f (d i )>) is output from the output unit 16.
  • the point of the present invention is that even if the difference between the inputs a i0 , a i0 + 1 , ..., a i1 of the function values f (a i0 ), f (a i0 + 1 ), ..., f (a i1 ) is disclosed.
  • 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 recording 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.
  • the secret calculation technique of the present invention can be applied to, for example, performing Fisher's exact test by secret calculation while keeping genome information secret in genome-wide association analysis that handles sensitive information.

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Data Mining & Analysis (AREA)
  • Mathematical Analysis (AREA)
  • Computational Mathematics (AREA)
  • Mathematical Physics (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Computer Security & Cryptography (AREA)
  • General Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Databases & Information Systems (AREA)
  • Algebra (AREA)
  • Probability & Statistics with Applications (AREA)
  • Operations Research (AREA)
  • Evolutionary Biology (AREA)
  • Bioinformatics & Computational Biology (AREA)
  • Bioinformatics & Cheminformatics (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Bioethics (AREA)
  • Health & Medical Sciences (AREA)
  • General Health & Medical Sciences (AREA)
  • Computer Hardware Design (AREA)
  • Complex Calculations (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Document Processing Apparatus (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)
  • Storage Device Security (AREA)

Abstract

フィッシャー正確検定を秘密計算により効率よく計算する。計算範囲決定部１２は、i0, i1, x0, x1を決定する。事前計算部１３は、f(x0), …, f(x1)を計算し、配列M=(f(x0), …, f(x1))を生成する。秘匿化部１４は、配列Mを秘匿化して秘匿文の配列<M>=(<f(x0)>, …, <f(x1)>)を生成する。一括読み込み部１５は、次式を実行して、関数値の秘匿文(<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>)（i0≦i≦i1）を生成する。

Description

秘密計算システム、秘密計算装置、秘密計算方法、およびプログラム
　この発明は、暗号応用技術に関し、特に、入力データを明かすことなくフィッシャー正確検定（Fisher's exact test）を計算する技術に関する。
　2×2の分割表として与えられた説明変数と目的変数との関連の有無に関して仮説検定を行う統計学的検定法の一つとして、フィッシャーの正確検定が広く知られている。非特許文献１には、フィッシャー正確検定の利用例として、ゲノムワイド関連解析（GWAS: Genome-Wide Association Study）が記載されている。
　フィッシャー正確検定について説明する。次表はn人の被験者を変異の有無と特定の疾患の発症の有無で分類および数え上げした2×2分割表の例である。
Figure JPOXMLDOC01-appb-T000006
 表中のa, b, c, dは度数を、n1●, n2●, n●1, n●2は小計を表し、n1●=a+b, n2●=c+d, n●1=a+c, n●2=b+dである。a, b, c, d, n1●, n2●, n●1, n●2はすべて非負整数である。
　このとき、非負整数iについて、式（１）で定義される確率piを計算し、式（２）に示す確率の和pと、有意水準と呼ばれる所定の値αとの大小関係により、説明変数（上表の例では変異の有無）と目的変数（上表の例では疾患の有無）との関連の有無を調査する。ここで、paは実際の集計値であるa, b, c, dを度数とする分割表について式（１）により算出した確率値である。
Figure JPOXMLDOC01-appb-M000007
　暗号化された数値を復元すること無く特定の演算結果を得る方法として、秘密計算と呼ばれる方法がある（例えば非特許文献２参照）。非特許文献２の方法では、３つの秘密計算装置に数値の断片を分散させるという暗号化を行い、３つの秘密計算装置が協調計算を行うことにより、数値を復元すること無く、加減算、定数加算、乗算、定数倍、論理演算（否定、論理積、論理和、排他的論理和）、データ形式変換（整数、二進数）の結果を３つの秘密計算装置に分散された状態、すなわち暗号化されたまま保持させることができる。
　ゲノム情報の機微性や機密性から、ゲノム情報を暗号技術によって秘匿しつつゲノムワイド関連解析を行う先行研究がある（例えば非特許文献３参照）。非特許文献３ではゲノム情報を秘匿しつつカイ二乗検定を行う方法が提案されている。
Konrad Karczewski, "How to do a GWAS", Lecture note in GENE 210: Genomics and Personalized Medicine, 2015. 千田浩司、濱田浩気、五十嵐大、高橋克巳、"軽量検証可能3パーティ秘匿関数計算の再考"、CSS2010、2010 Yihua Zhang, Marina Blanton, and Ghada Almashaqbeh, "Secure distributed genome analysis for gwas and sequence comparison computation", BMC medical informatics and decision making, Vol. 15, No. Suppl 5, p. S4, 2015.
　フィッシャー正確検定で各確率piを計算する際には、x!やlog(x!)などの同じ計算が多数現れる。この計算を関数f(x)として、関数f(x)の計算結果…, f(-1), f(0), f(1), f(2), …をあらかじめ計算しておいて、必要に応じて計算結果の値を参照することで効率化することができる。しかしながら、従来技術はai=a+i, bi=b-i, ci=c-i, di=d+iとして、f(a+b), f(c+d), f(a+c), f(b+d), f(a+b+c+d), f(ai), f(bi), f(ci), f(di)を計算する際に計算結果の値をm種類、計算する確率piをn種類（すなわち、i=0, …, n-1）とすると、大きさmの表の参照を4n+5回行う必要があった。特に、秘密計算でこれを実現しようとする場合、大きさmの表の参照にO(m)の計算量を要するため、全体の計算量がO(mn)となっていた。
　この発明の秘密計算技術は、上述のような点に鑑みて、フィッシャー正確検定を秘密計算により効率よく計算することを目的とする。
　上記の課題を解決するために、この発明の秘密計算システムは、3台以上の秘密計算装置を含む秘密計算システムであって、秘密計算装置は、a, b, c, dを非負整数とし、aを2×2の分割表における第1行第1列の度数とし、bを分割表における第1行第2列の度数とし、cを分割表における第2行第1列の度数とし、dを分割表における第2行第2列の度数とし、<a>, <b>, <c>, <d>をそれぞれ度数a, b, c, dの秘匿文とし、BatchRead(<α>; <β>; j0, …, jm-1)は大きさnの配列の秘匿文<α>=(<α[0]>,<α[1]>, …, <α[n-1]>)から大きさmの配列の秘匿文(<α[β+j0mod n]>, …, <α[β+jm-1 mod n]>)を生成する関数を表し、i0≦i1, x0≦x1を満たすi0, i1, x0, x1を決定する計算範囲決定部と、任意の関数f(x)について、f(x0), …, f(x1)を計算し、配列M=(f(x0), …, f(x1))を生成する事前計算部と、配列Mを秘匿化して秘匿文の配列<M>=(<f(x0)>, …, <f(x1)>)を生成する秘匿化部と、次式を実行して、関数値の秘匿文(<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>)（i0≦i≦i1）を生成する一括読み込み部と、を含むものである。
Figure JPOXMLDOC01-appb-M000008
　この発明によれば、フィッシャー正確検定の入力となる分割表の度数a, b, c, dを明かすことなく、計算対象となる度数の関数値f(ai), f(bi), f(ci), f(di)を効率よく求めることができる。したがって、フィッシャー正確検定を秘密計算により効率よく計算することができる。さらには、ゲノム情報を秘匿しつつフィッシャー正確検定を実行することができる。これは例えば、複数の研究機関が所持するゲノムデータを秘匿したまま相互に開示することなく、統合されたデータのフィッシャー正確検定の実行結果を得ることができ、極めてセキュリティレベルの高いゲノム解析の実行環境の提供、ひいては医療の更なる発展へとつながることが期待できる。
図１は、秘密計算システムの機能構成を例示する図である。 図２は、秘密計算装置の機能構成を例示する図である。 図３は、秘密計算方法の処理手続きを例示する図である。
　実施形態の説明に先立ち、この明細書における表記方法およびこの明細書において用いる用語の定義について説明する。
　＜表記方法＞
　ある値aを暗号化や秘密分散などにより秘匿化した値をaの秘匿文と呼び、<a>と表記する。また、aを<a>の平文と呼ぶ。秘匿化が秘密分散である場合は、<a>により各パーティが持つ秘密分散の断片の集合を参照する。
　＜秘匿シフト＞
　大きさnの秘匿文の配列<a>=(<a[0]>, <a[1]>, …, <a[n-1]>)とシフト量dの秘匿文<d>とを入力とし、<a>を左にdだけシフトした秘匿文の配列<a'>=(<a[d]>, <a[d+1]>, …, <a[n-1]>, <a[0]>, <a[1]>, …, <a[d-1]>)を計算する処理を秘匿シフトと呼び、次式で記述する。
Figure JPOXMLDOC01-appb-M000009
　秘匿シフトを実現する方法は、下記参考文献１に記載されている。
〔参考文献１〕濱田浩気、桐淵直人、五十嵐大、“ラウンド効率のよい秘密計算パターンマッチング”、コンピュータセキュリティシンポジウム2014論文集、第2014巻、pp. 674-681、2014年10月
　＜一括読み込みアルゴリズム＞
　一括読み込みアルゴリズムは、大きさnの秘匿文の配列<a>=(<a[0]>, <a[1]>, …, <a[n-1]>)、位置を表す自然数xの秘匿文<x>、およびxからの相対的な位置を表すm個の平文j0,j1, …, jm-1を入力とし、xやa[0], a[1], …, a[n-1]の値を明らかにすることなく、m個の秘匿文<b>=(<a[x+j0 mod n]>, <a[x+j1 mod n]>, …, <a[x+jm-1mod n]>)を得る方法である。以下、一括読み込みアルゴリズムは次式で記述する。
Figure JPOXMLDOC01-appb-M000010
　一括読み込みアルゴリズムは上記の秘匿シフトを用いて以下のように実装することで、より効率的に実行することができる。ただし、この発明で適用可能な一括読み込みアルゴリズムはこれに限定されず、上述の入出力を実現することができるアルゴリズムであればどのようなものであってもよい。まず、大きさnの秘匿文の配列<a>=(<a[0]>, <a[1]>, …, <a[n-1]>)、位置を表す0以上n未満の整数xの秘匿文<x>、およびxからの相対的な位置を表すm個の平文j0, …, jm-1が入力される。次に、<a'>←Shift(<a>, <x>)により、配列<a>を<x>だけ左シフトした配列<a'>=(<a'[0]>, <a'[1]>, …, <a'[n-1]>)を得る。そして、<b[k]>=<a'[jk]>（0≦k<m）として、秘匿文の配列<b>=(<b[0]>, <b[1]>, …, <b[m-1]>)=(<a'[j0]>, <a'[j1]>, …, <a'[jm-1]>)を生成する。
　以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
　＜第一実施形態＞
　第一実施形態の秘密計算システムは、図１に例示するように、n（≧3）台の秘密計算装置１1, …, １nを含む。この実施形態では、秘密計算装置１1, …, １nはそれぞれ通信網２へ接続される。通信網２は、秘密計算装置１1, …, １nそれぞれが相互に通信可能なように構成された回線交換方式もしくはパケット交換方式の通信網であり、例えばインターネットやLAN（Local Area Network）、WAN（Wide Area Network）などを用いることができる。なお、各装置は必ずしも通信網２を介してオンラインで通信可能である必要はない。例えば、秘密計算装置１i（i∈{1, …, n}）へ入力する情報を磁気テープやUSBメモリなどの可搬型記録媒体に記憶し、その可搬型記録媒体からオフラインで入力するように構成してもよい。
　秘密計算装置１は、図２に例示するように、入力部１１、計算範囲決定部１２、事前計算部１３、秘匿化部１４、一括読み込み部１５、および出力部１６を含む。この秘密計算装置１が、図３に例示する各ステップの処理を行うことにより第一実施形態の秘密計算方法が実現される。
　秘密計算装置１は、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。秘密計算装置１は、例えば、中央演算処理装置の制御のもとで各処理を実行する。秘密計算装置１に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて中央演算処理装置へ読み出されて他の処理に利用される。秘密計算装置１の各処理部は、少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。
　図３を参照して、第一実施形態の秘密計算方法の処理手続きを説明する。
　ステップＳ１１において、入力部１１へ、2×2分割表の度数の組(a, b, c, d)の秘匿文(<a>, <b>, <c>, <d>)が入力される。ここで、2×2分割表は次表で定義され、a, b, c, dは非負整数である。
Figure JPOXMLDOC01-appb-T000011
　ステップＳ１２において、計算範囲決定部１２は、i0≦i1, x0≦x1を満たす値i0, i1, x0, x1を決定する。ここでは、i0=-n, i1=n, x0=-n, x1=2nと決定するものとする。値x0,x1は事前計算部１３へ送られる。値i0, i1は一括読み込み部１５へ送られる。
　ステップＳ１３において、事前計算部１３は、関数f(x)について、f(x0), f(x0+1),…,f(x1)を計算し、配列M=(f(x0), f(x0+1),…, f(x1))を生成する。第一実施形態では、次式で定義される確率pi（i0≦i≦i1）を計算するために、関数f(x)はf(x):=x!とする。
Figure JPOXMLDOC01-appb-M000012
　ステップＳ１４において、秘匿化部１４は、配列Mを秘匿化した秘匿文の配列<M>=(<f(x0)>, <f(x0+1)>, …, <f(x1)>)を生成する。秘匿文の配列<M>は一括読み込み部１５へ送られる。
　ステップＳ１５において、一括読み込み部１５は、次式を実行して、関数値の秘匿文(<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>)（i=i0, …, i1）を生成する。
Figure JPOXMLDOC01-appb-M000013
　ステップＳ１６において、出力部１６から、関数値の秘匿文(<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>)が出力される。
　＜第二実施形態＞
　図３を参照して、第二実施形態の秘密計算方法の処理手続きを説明する。以下では、上述の第一実施形態との相違点を中心に説明する。
　ステップＳ１３において、事前計算部１３は、関数f(x)について、f(x0), f(x0+1),…,f(x1)を計算し、配列M=(f(x0), f(x0+1),…, f(x1))を生成する。第二実施形態では、次式で定義される確率log pi（i0≦i≦i1）を計算した後に確率pi=exp(log pi)を計算するために、関数f(x)はf(x):=log(x!)とする。
Figure JPOXMLDOC01-appb-M000014
　この発明のポイントは、関数値f(ai0), f(ai0+1), …, f(ai1)の入力ai0, ai0+1, …, ai1の差が公開してもよい情報であることを利用して、関数値の秘匿文<f(ai0)>, <f(ai0+1)>, …, <f(ai1)>の計算を、一括読み込みアルゴリズムを使って効率よく実現することである。
　このように構成することにより、この発明の秘密計算技術によれば、複数の表参照を一括で実行することにより、フィッシャー正確検定を秘密計算で効率的に計算できる。大きさnの配列からの一括読み込みがO(n)の計算量であるので、1+i1-i0=K, 1+x1-x0=Lとして、全体の計算量がO(KL)からO(L)に改善される。
　以上、この発明の実施の形態について説明したが、具体的な構成は、これらの実施の形態に限られるものではなく、この発明の趣旨を逸脱しない範囲で適宜設計の変更等があっても、この発明に含まれることはいうまでもない。実施の形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
［プログラム、記録媒体］
　上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
　この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
　また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
　このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
　また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
　この発明の秘密計算技術は、例えば、機微情報を取り扱うゲノムワイド関連解析において、ゲノム情報を秘匿したまま秘密計算によりフィッシャー正確検定を行うことに適用することが可能である。

Claims (6)

  1. 　3台以上の秘密計算装置を含む秘密計算システムであって、
    　上記秘密計算装置は、
    　　a, b, c, dを非負整数とし、aを2×2の分割表における第1行第1列の度数とし、bを上記分割表における第1行第2列の度数とし、cを上記分割表における第2行第1列の度数とし、dを上記分割表における第2行第2列の度数とし、<a>, <b>, <c>, <d>をそれぞれ度数a, b, c, dの秘匿文とし、BatchRead(<α>; <β>; j0, …, jm-1)は大きさnの配列の秘匿文<α>=(<α[0]>, <α[1]>, …, <α[n-1]>)から大きさmの配列の秘匿文(<α[β+j0mod n]>, …, <α[β+jm-1 mod n]>)を生成する関数を表し、
    　　i0≦i1, x0≦x1を満たすi0, i1, x0, x1を決定する計算範囲決定部と、
    　　任意の関数f(x)について、f(x0), …, f(x1)を計算し、配列M=(f(x0), …, f(x1))を生成する事前計算部と、
    　　上記配列Mを秘匿化して秘匿文の配列<M>=(<f(x0)>, …, <f(x1)>)を生成する秘匿化部と、
    　　次式を実行して、関数値の秘匿文(<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>)（i0≦i≦i1）を生成する一括読み込み部と、
    Figure JPOXMLDOC01-appb-M000001
    　を含むものである秘密計算システム。
  2. 　請求項１に記載の秘密計算システムであって、
    　上記事前計算部は、上記関数f(x)をf(x):=x!として、次式で定義される確率pi（i0≦i≦i1）を計算するためにf(x0), …, f(x1)を計算するものである、
    Figure JPOXMLDOC01-appb-M000002
    　秘密計算システム。
  3. 　請求項１に記載の秘密計算システムであって、
    　上記事前計算部は、上記関数f(x)をf(x):=log(x!)として、次式で定義されるlog pi（i0≦i≦i1）を計算した後に確率pi=exp(log pi)を計算するためにf(x0), …, f(x1)を計算するものである、
    Figure JPOXMLDOC01-appb-M000003
    　秘密計算システム。
  4. 　a, b, c, dを非負整数とし、aを2×2の分割表における第1行第1列の度数とし、bを上記分割表における第1行第2列の度数とし、cを上記分割表における第2行第1列の度数とし、dを上記分割表における第2行第2列の度数とし、<a>, <b>, <c>, <d>をそれぞれ度数a, b, c, dの秘匿文とし、BatchRead(<α>; <β>; j0, …, jm-1)は大きさnの配列の秘匿文<α>=(<α[0]>, <α[1]>, …, <α[n-1]>)から大きさmの配列の秘匿文(<α[β+j0mod n]>, …, <α[β+jm-1 mod n]>)を生成する関数を表し、
    　i0≦i1, x0≦x1を満たすi0, i1, x0, x1を決定する計算範囲決定部と、
    　任意の関数f(x)について、f(x0), …, f(x1)を計算し、配列M=(f(x0), …, f(x1))を生成する事前計算部と、
    　上記配列Mを秘匿化して秘匿文の配列<M>=(<f(x0)>, …, <f(x1)>)を生成する秘匿化部と、
    　次式を実行して、関数値の秘匿文(<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>)（i0≦i≦i1）を生成する一括読み込み部と、
    Figure JPOXMLDOC01-appb-M000004
    　を含む秘密計算装置。
  5. 　a, b, c, dを非負整数とし、aを2×2の分割表における第1行第1列の度数とし、bを上記分割表における第1行第2列の度数とし、cを上記分割表における第2行第1列の度数とし、dを上記分割表における第2行第2列の度数とし、<a>, <b>, <c>, <d>をそれぞれ度数a, b, c, dの秘匿文とし、BatchRead(<α>; <β>; j0, …, jm-1)は大きさnの配列の秘匿文<α>=(<α[0]>, <α[1]>, …, <α[n-1]>)から大きさmの配列の秘匿文(<α[β+j0mod n]>, …, <α[β+jm-1 mod n]>)を生成する関数を表し、
    　計算範囲決定部が、i0≦i1, x0≦x1を満たすi0, i1, x0, x1を決定し、
    　事前計算部が、任意の関数f(x)について、f(x0), …, f(x1)を計算し、配列M=(f(x0), …, f(x1))を生成し、
    　秘匿化部が、上記配列Mを秘匿化して秘匿文の配列<M>=(<f(x0)>, …, <f(x1)>)を生成し、
    　一括読み込み部が、次式を実行して、関数値の秘匿文(<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>)（i0≦i≦i1）を生成する、
    Figure JPOXMLDOC01-appb-M000005
    　秘密計算方法。
  6. 　請求項４に記載の秘密計算装置としてコンピュータを機能させるためのプログラム。
PCT/JP2017/024140 2016-07-06 2017-06-30 秘密計算システム、秘密計算装置、秘密計算方法、およびプログラム Ceased WO2018008545A1 (ja)

Priority Applications (4)

Application Number Priority Date Filing Date Title
US16/309,034 US11121868B2 (en) 2016-07-06 2017-06-30 Secure computation system, secure computation device, secure computation method, and program
CN201780037589.4A CN109328377B (zh) 2016-07-06 2017-06-30 秘密计算系统、秘密计算装置、秘密计算方法、以及程序
EP17824150.1A EP3483866B1 (en) 2016-07-06 2017-06-30 Secure computation system, secure computation device, secure computation method, and program
JP2018526338A JP6534778B2 (ja) 2016-07-06 2017-06-30 秘密計算システム、秘密計算装置、秘密計算方法、およびプログラム

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP2016-134089 2016-07-06
JP2016134089 2016-07-06

Publications (1)

Publication Number Publication Date
WO2018008545A1 true WO2018008545A1 (ja) 2018-01-11

Family

ID=60912177

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2017/024140 Ceased WO2018008545A1 (ja) 2016-07-06 2017-06-30 秘密計算システム、秘密計算装置、秘密計算方法、およびプログラム

Country Status (5)

Country Link
US (1) US11121868B2 (ja)
EP (1) EP3483866B1 (ja)
JP (1) JP6534778B2 (ja)
CN (1) CN109328377B (ja)
WO (1) WO2018008545A1 (ja)

Families Citing this family (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2018034079A1 (ja) * 2016-08-18 2018-02-22 日本電気株式会社 秘密計算システム、秘密計算方法、秘密計算装置、分散情報生成装置およびそれらの方法とプログラム
WO2019009180A1 (ja) * 2017-07-05 2019-01-10 日本電信電話株式会社 秘密計算システム、秘密計算装置、秘密計算方法、プログラム、および記録媒体
CN112805770B (zh) * 2018-10-10 2023-10-03 日本电信电话株式会社 秘密右移位运算系统及方法、秘密除法运算系统及方法、秘密计算装置以及记录介质
WO2020184127A1 (ja) * 2019-03-11 2020-09-17 日本電信電話株式会社 データ一般化装置、データ一般化方法、プログラム
JP7205623B2 (ja) * 2019-06-07 2023-01-17 日本電信電話株式会社 秘密共役勾配法計算システム、秘密計算装置、共役勾配法計算装置、秘密共役勾配法計算方法、共役勾配法計算方法、およびプログラム
US12401494B2 (en) * 2019-08-14 2025-08-26 Nippon Telegraph And Telephone Corporation Machine learning using secure gradient descent computation

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2009086739A (ja) * 2007-09-27 2009-04-23 Hitachi Software Eng Co Ltd ２×ｎ型分割表の総数数え上げ処理装置
JP2014139640A (ja) * 2013-01-21 2014-07-31 Nippon Telegr & Teleph Corp <Ntt> 秘密計算による表の等結合システム、方法

Family Cites Families (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP4651681B2 (ja) * 2006-01-10 2011-03-16 富士通株式会社 端末装置およびコンピュータプログラム
US20090182797A1 (en) * 2008-01-10 2009-07-16 Microsoft Corporation Consistent contingency table release
US8577030B2 (en) * 2009-11-20 2013-11-05 Mitsubishi Electric Corporation Cryptographic processing system, key generation device, key delegation device, encryption device, decryption device, cryptographic processing method, and cryptographic processing program
US9946810B1 (en) * 2010-04-21 2018-04-17 Stan Trepetin Mathematical method for performing homomorphic operations
US9064123B2 (en) * 2011-03-10 2015-06-23 Nippon Telegraph And Telephone Corporation Secure product-sum combination system, computing apparatus, secure product-sum combination method and program therefor
JP5668191B2 (ja) * 2011-12-20 2015-02-12 三菱電機株式会社 暗号化データ管理装置、暗号化データ管理方法及び暗号化データ管理プログラム
JP6016948B2 (ja) * 2013-01-17 2016-10-26 日本電信電話株式会社 秘匿計算システム、演算装置、秘匿計算方法、およびプログラム
EP3057079A4 (en) * 2013-10-10 2017-06-07 Nippon Telegraph And Telephone Corporation Secret parallel processing device, secret parallel processing method, and program
US9524392B2 (en) * 2013-11-30 2016-12-20 Microsoft Technology Licensing, Llc Encrypting genomic data for storage and genomic computations
US10496638B2 (en) * 2016-12-07 2019-12-03 City University Of Hong Kong Systems and methods for privacy-assured similarity joins over encrypted datasets

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2009086739A (ja) * 2007-09-27 2009-04-23 Hitachi Software Eng Co Ltd ２×ｎ型分割表の総数数え上げ処理装置
JP2014139640A (ja) * 2013-01-21 2014-07-31 Nippon Telegr & Teleph Corp <Ntt> 秘密計算による表の等結合システム、方法

Non-Patent Citations (7)

* Cited by examiner, † Cited by third party
Title
KOJI CHIDA; KOKI HAMADA; DAI IKARASHI; KATSUMI TAKAHASHI: "A Three-Party Secure Function Evaluation with Lightweight Verifiability Revisited", CSS 2010, 2010
KOKI HAMADA ET AL.: "Privacy Preserving Fisher's Exact Test(2) - For Large Samples", IPSJ SIG NOTES, vol. 2016, no. 38, 7 July 2016 (2016-07-07), pages 1 - 6, XP009513204, ISSN: 0919-6072 *
KOKI HAMADA; NAOTO KIRIBUCHI; DAI IKARASHI: "A round-efficient pattern matching algorithm for secure multi-party computation", COMPUTER SECURITY SYMPOSIUM 2014, vol. 2014, October 2014 (2014-10-01), pages 674 - 681, XP003032484
KONRAD KARCZEWSKI: "How to do a GWAS", LECTURE NOTE IN GENE 210: GENOMICS AND PERSONALIZED MEDICINE, 2015
MASASHI GOTO ET AL.: "Evalutation of exact probability on some statistical models by network algorithm", BULLETIN OF THE COMPUTATIONAL STATISTICS OF JAPAN, vol. 1, no. 1, 1 January 1988 (1988-01-01), pages 23 - 35, XP055588272, DOI: 10.20551/jscswabun.1.1_23 *
TOMOKI SATO ET AL.: "Implementation and Evaluation of Privacy-Preserving Epidemic Analysis System", IEICE TECHNICAL REPORT, vol. 112, no. 315, 15 November 2012 (2012-11-15), pages 61 - 66, XP055588277 *
YIHUA ZHANG; MARINA BLANTON; GHADA ALMASHAQBEH: "Secure distributed genome analysis for gwas and sequence comparison computation", BMC MEDICAL INFORMATICS AND DECISION MAKING, vol. 15, no. 5, 2015, pages S4

Also Published As

Publication number Publication date
CN109328377A (zh) 2019-02-12
JPWO2018008545A1 (ja) 2019-04-04
US11121868B2 (en) 2021-09-14
JP6534778B2 (ja) 2019-06-26
CN109328377B (zh) 2021-12-21
EP3483866A1 (en) 2019-05-15
US20190229904A1 (en) 2019-07-25
EP3483866B1 (en) 2020-12-23
EP3483866A4 (en) 2020-01-15

Similar Documents

Publication Publication Date Title
JP6534778B2 (ja) 秘密計算システム、秘密計算装置、秘密計算方法、およびプログラム
EP3573039B1 (en) Secure computing system, secure computing device, secure computing method, and program
JP7067632B2 (ja) 秘密シグモイド関数計算システム、秘密ロジスティック回帰計算システム、秘密シグモイド関数計算装置、秘密ロジスティック回帰計算装置、秘密シグモイド関数計算方法、秘密ロジスティック回帰計算方法、プログラム
JP6583970B2 (ja) 秘密乱数合成装置、秘密乱数合成方法、およびプログラム
Ibarrondo et al. Banners: Binarized neural networks with replicated secret sharing
JP6585846B2 (ja) 秘密計算システム、秘密計算装置、秘密計算方法、およびプログラム
JP6541048B2 (ja) 秘密計算システム、秘密計算装置、秘密計算方法、およびプログラム
JP6977882B2 (ja) 秘密一括近似システム、秘密計算装置、秘密一括近似方法、およびプログラム
JP7173328B2 (ja) 秘密除算システム、秘密計算装置、秘密除算方法、およびプログラム
WO2019059042A1 (ja) 秘密読み込み装置、秘密書き込み装置、それらの方法、およびプログラム
Gribov et al. Medical diagnostics based on encrypted medical data
WO2016056503A1 (ja) 部分文字列位置検出装置、部分文字列位置検出方法及びプログラム
Adir et al. Homomorphic Encryption for Data Science (HE4DS)
JP7359225B2 (ja) 秘密最大値計算装置、方法及びプログラム
Buchanan et al. Evaluation of Privacy-aware Support Vector Machine (SVM) Learning using Homomorphic Encryption
Goldenberg et al. Private epigenetic pacemaker detector using homomorphic encryption
JP6682105B2 (ja) フィッシャー正確検定計算装置、方法及びプログラム
de Arruda Botelho et al. Privacy-preserving AUC computation in distributed machine learning with PHT-meDIC

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

Country of ref document: EP

Kind code of ref document: A1

ENP Entry into the national phase

Ref document number: 2018526338

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

Country of ref document: EP

Effective date: 20190206