WO2022264237A1 - 累積計算装置、累積計算方法、及びプログラム - Google Patents

累積計算装置、累積計算方法、及びプログラム Download PDF

Info

Publication number
WO2022264237A1
WO2022264237A1 PCT/JP2021/022586 JP2021022586W WO2022264237A1 WO 2022264237 A1 WO2022264237 A1 WO 2022264237A1 JP 2021022586 W JP2021022586 W JP 2021022586W WO 2022264237 A1 WO2022264237 A1 WO 2022264237A1
Authority
WO
WIPO (PCT)
Prior art keywords
binary operation
new
cumulative
cumulative calculation
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/JP2021/022586
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 EP21945917.9A priority Critical patent/EP4358070B1/en
Priority to JP2023528779A priority patent/JP7544274B2/ja
Priority to PCT/JP2021/022586 priority patent/WO2022264237A1/ja
Priority to US18/568,542 priority patent/US20240281208A1/en
Priority to CN202180099278.7A priority patent/CN117480545A/zh
Publication of WO2022264237A1 publication Critical patent/WO2022264237A1/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/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
    • 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/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
    • 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/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
    • G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
    • G06F7/544—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices for evaluating functions by calculation

Definitions

  • the present invention relates to an accumulative calculation device, an accumulative calculation method, and a program.
  • Non-Patent Document 1 describes a three-party secret sharing technique.
  • Non-Patent Document 2 describes a method of calculating statistical values (average value, maximum value, aggregate, etc.) for each group of grouped data by secure calculation. Note that these statistics are realized by accumulating associative dyadic operations.
  • the conventional method is specially designed for secure computation so that group-by-group statistics can be calculated (i.e., the accumulation of binomial operations) while hiding the group, and ordinary data that is not secure computation is used. It was inefficient because the cumulative calculation method used in the process could not be used in the secure calculation as it is.
  • An embodiment of the present invention has been made in view of the above points, and aims to efficiently perform cumulative calculation for each group.
  • Let c ( c 1 , .
  • v 1 to v i′ are the first group
  • v i′+1 to v i′′ form the second group
  • v i′′+1 to v n form the third group.
  • the accumulative calculation device 10 calculates the total data (that is, n values v 1 ′, . . . , v n ′)), a new binary operation is created so that the accumulation for each group can be calculated by the above binary operation, and the accumulation of the entire data is calculated with this new binary operation. Since cumulative calculation of the entire data is used in normal data processing, the cumulative calculation device 10 according to the present embodiment, for example, even when performing cumulative calculation for each group by secure calculation, It is possible to perform the calculation
  • FIG. 1 shows the hardware configuration of the cumulative computing device 10 according to this embodiment.
  • the cumulative calculation device 10 according to the present embodiment is realized by the hardware configuration of a general computer or computer system, and includes an input device 101, a display device 102, an external I/F 103, a communication I /F 104 , processor 105 and memory device 106 . Each of these pieces of hardware is communicably connected via a bus 107 .
  • the input device 101 is, for example, a keyboard, mouse, touch panel, various physical buttons, and the like.
  • the display device 102 is, for example, a display. Note that the cumulative calculation device 10 may not have at least one of the input device 101 and the display device 102, for example.
  • the external I/F 103 is an interface with an external device such as the recording medium 103a.
  • the accumulative calculation device 10 can perform reading, writing, etc. of the recording medium 103 a via the external I/F 103 .
  • Examples of the recording medium 103a include CD (Compact Disc), DVD (Digital Versatile Disk), SD memory card (Secure Digital memory card), USB (Universal Serial Bus) memory card, and the like.
  • the communication I/F 104 is an interface for connecting the cumulative computing device 10 to a communication network.
  • the processor 105 is, for example, various arithmetic units such as a CPU (Central Processing Unit) and a GPU (Graphics Processing Unit).
  • the memory device 106 is, for example, various storage devices such as HDD (Hard Disk Drive), SSD (Solid State Drive), flash memory, RAM (Random Access Memory), and ROM (Read Only Memory).
  • the cumulative computing device 10 can implement various processes described later.
  • the hardware configuration shown in FIG. 1 is an example, and the cumulative calculation device 10 may have, for example, a plurality of processors 105 or a plurality of memory devices 106 .
  • the cumulative calculation device 10 may have various hardware other than the illustrated hardware.
  • FIG. 2 shows the functional configuration of the cumulative computing device 10 according to this embodiment.
  • the accumulative calculation device 10 has a value converter 201 , a binary operation generator 202 , an accumulative calculator 203 , an output unit 204 , and a storage unit 205 .
  • the value conversion unit 201, the binary operation creation unit 202, the cumulative calculation unit 203, and the output unit 204 are implemented by, for example, processing that one or more programs installed in the cumulative calculation device 10 cause the processor 105 to execute.
  • the storage unit 205 is realized by the memory device 106, for example. Note that the storage unit 205 may be implemented by, for example, a storage device or the like connected to the cumulative calculation device 10 via a communication network.
  • the binary operation creation unit 202 creates a new binary operation that can calculate the accumulation for each group based on the original binary operation through the accumulation calculation for the entire data.
  • the output unit 204 extracts the result of the cumulative calculation for each group by the original binary operation from the result of the cumulative calculation by the new binary operation, and outputs the extracted result.
  • the binary operation creating unit 202 can calculate the accumulation for each group according to the original binary operation by performing the accumulation calculation on the entire data (that is, the entire n values v 1 ', . . . , v n ').
  • step S102 a binary operation defined by the following is created (step S102).
  • w and y are variables that can take arbitrary values
  • x and z are variables that can take 0 or 1
  • OR is 1 when at least one of x and z is 1, and 0 otherwise. It is an operator (that is, an operator representing a logical sum).
  • i 1, . . . , n
  • the output destination of the output unit 204 may be arbitrary, but it is conceivable, for example, to store it in the storage unit 205 or transmit it to another device or device.
  • max(x, y) is a binary operation that outputs the maximum value of x and y.
  • the accumulation is computed with a new binary operation for the whole.
  • the accumulative calculation device 10 performs accumulative calculation by a binary operation in each group. Otherwise, a flag of 0 is given and a new binary operation is defined, and cumulative calculation is performed on the entire data (that is, the entire set of values and flags) by this new binary operation.
  • This new binary operation takes advantage of the fact that the top element of the group has already calculated the value of the accumulation, and regards the flag as indicating whether or not it has been calculated. It is an extension of binary operations to binary operations on pairs of values and flags.
  • the accumulative calculation device 10 can efficiently perform accumulative calculation for each group by, for example, secret calculation (including secret sharing). Become. This is because any method that applies the binary operations we want to compute the accumulations to in a given order allows us to compute the accumulations by group with secure computation in the same order. Therefore, for example, by using max or min as a binary operation, it is possible to efficiently implement group by max or group by min operations in secure calculation.
  • the cumulative computing device 10 according to the present embodiment can be used not only for normal data processing, but also, for example, for data processing and data analysis while keeping the data content confidential.
  • the cumulative computing device 10 according to the present embodiment creates learning data for a machine learning model that realizes a predetermined task (for example, prediction, classification, etc.) while keeping the data content confidential. It is possible to
  • the cumulative computing device 10 according to the present embodiment can perform various predictions and classifications by machine learning models learned with the learning data, and other devices, devices, systems, etc. based on the predictions or classification results. It may also be possible to control the

Landscapes

  • Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Computing Systems (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • Computational Mathematics (AREA)
  • Computer Security & Cryptography (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Complex Calculations (AREA)

Abstract

一実施形態に係る累積計算装置は、グループに分けられたｎ個の値の列ｖ＝（ｖ１，・・・，ｖｎ）に関して、結合的な二項演算により前記グループごとの累積を計算する累積計算装置であって、ｖの各要素ｖ１，・・・，ｖｎのうち、前記グループの先頭の要素には１、前記先頭以外の要素には０を対応させた値の列をｃ＝（ｃ１，・・・，ｃｎ）として、ｖをｖ'＝（ｖ１'，・・・，ｖｎ'）（ただし、ｖｉ'＝（ｖｉ，ｃｉ））に変換する値変換部と、前記二項演算を用いて、２つの対（ｗ，ｘ）と（ｙ，ｚ）（ただし、ｘ，ｚ∈｛０，１｝）に対して新しい対（ｐ，ｑ）を計算する新たな二項演算を作成する二項演算作成部と、ｉ＝１，・・・，ｎについて、前記新たな二項演算により累積ｓｉ'（ただし、ｓｉ'は前記新たな二項演算によるｖ１'からｖｉ'までの累積）を計算する累積計算部と、各ｓｉ'（ｉ＝１，・・・，ｎ）から前記グループごとの累積を示す値の列ｕ＝（ｕ１，・・・，ｕｎ）を取り出し、取り出したｕを出力する出力部と、を有し、前記新たな二項演算は、ｚ＝０である場合は前記二項演算によるｗとｙの演算結果をｐ、ｚ＝１である場合はｙをｐとし、ｘとｚの論理和をｑとする。

Description

累積計算装置、累積計算方法、及びプログラム
　本発明は、累積計算装置、累積計算方法、及びプログラムに関する。
　暗号化された数値を復元すること無く特定の演算結果を得る方法として、秘密計算と呼ばれる技術が従来から知られている。例えば、非特許文献１には、３パーティの秘密分散技術が記載されている。
　また、データ処理技術の１つとして、グループ分けされたデータの集計を行う技術が従来から知られている。例えば、非特許文献２には、グループ分けされたデータのグループごとの統計値（平均値、最大値、集計等）を秘密計算により計算する方法が記載されている。なお、これらの統計値は結合的な２項演算の累積により実現される。
千田浩司, 濱田浩気, 五十嵐大, 高橋克巳. 軽量検証可能3 パーティ秘匿関数計算の再考. In CSS, 2010. 五十嵐大, 千田浩司, 濱田浩気, 高橋克巳. 軽量検証可能3 パーティ秘匿関数計算の効率化及びこれを用いたセキュアなデータベース処理. In SCIS, pp. 1-8, 2011.
　しかしながら、従来の方法は秘密計算向けにグループを隠しながらグループごとの統計値の計算（つまり、２項演算の累積の計算）を行えるように専用に設計されており、秘密計算ではない通常のデータ処理で使われる累積の計算方法をそのまま秘密計算で用いることができないため効率が悪かった。
　本発明の一実施形態は、上記の点に鑑みてなされたもので、グループ別の累積計算を効率的に行うことを目的とする。
　上記目的を達成するため、一実施形態に係る累積計算装置は、グループに分けられたｎ個の値の列ｖ＝（ｖ１，・・・，ｖｎ）に関して、結合的な二項演算により前記グループごとの累積を計算する累積計算装置であって、ｖの各要素ｖ１，・・・，ｖｎのうち、前記グループの先頭の要素には１、前記先頭以外の要素には０を対応させた値の列をｃ＝（ｃ１，・・・，ｃｎ）として、ｖをｖ'＝（ｖ１'，・・・，ｖｎ'）（ただし、ｖｉ'＝（ｖｉ，ｃｉ））に変換する値変換部と、前記二項演算を用いて、２つの対（ｗ，ｘ）と（ｙ，ｚ）（ただし、ｘ，ｚ∈｛０，１｝）に対して新しい対（ｐ，ｑ）を計算する新たな二項演算を作成する二項演算作成部と、ｉ＝１，・・・，ｎについて、前記新たな二項演算により累積ｓｉ'（ただし、ｓｉ'は前記新たな二項演算によるｖ１'からｖｉ'までの累積）を計算する累積計算部と、各ｓｉ'（ｉ＝１，・・・，ｎ）から前記グループごとの累積を示す値の列ｕ＝（ｕ１，・・・，ｕｎ）を取り出し、取り出したｕを出力する出力部と、を有し、前記新たな二項演算は、ｚ＝０である場合は前記二項演算によるｗとｙの演算結果をｐ、ｚ＝１である場合はｙをｐとし、ｘとｚの論理和をｑとする。
　グループ別の累積計算を効率的に行うことができる。
本実施形態に係る累積計算装置のハードウェア構成の一例を示す図である。 本実施形態に係る累積計算装置の機能構成の一例を示す図である。 本実施形態に係る累積計算処理の流れの一例を示すフローチャートである。
　以下、本発明の一実施形態について説明する。本実施形態では、グループ別の累積計算を効率的に行うことができる累積計算装置１０について説明する。
　ここで、ｎ個の値の列をｖ＝（ｖ１，・・・，ｖｎ）とし、ｖの各要素ｖｉ（ｉ＝１，・・・，ｎ）はいくつかのグループに分けられており、同一グループ内の要素は連続するインデックス（要素番号）を持つように並べられているものとする。
　例えば、３つのグループに分けられている場合、或るｉ'，ｉ''（ただし、１≦ｉ'＜ｉ''＜ｎ）が存在し、ｖ１～ｖｉ'が１つ目のグループ、ｖｉ'＋１～ｖｉ''が２つ目のグループ、ｖｉ''＋１～ｖｎが３つ目のグループとなる。
　また、
Figure JPOXMLDOC01-appb-M000001
 を二項演算とする。
　このとき、本実施形態に係る累積計算装置１０は、各グループ内で上記の二項演算による累積の計算を行う際に、データ全体（つまり、後述するｎ個の値ｖ１'，・・・，ｖｎ'全体）に対する累積計算により上記の二項演算によるグループ別の累積を計算できるような新たな二項演算を作成し、この新たな二項演算でデータ全体の累積を計算する。データ全体の累積計算は通常のデータ処理で使用されているものであるため、本実施形態に係る累積計算装置１０は、例えば、秘密計算によりグループ別の累積計算を行う場合であっても、効率的にその計算を行うことが可能となる。
　＜累積計算装置１０のハードウェア構成＞
　本実施形態に係る累積計算装置１０のハードウェア構成を図１に示す。図１に示すように、本実施形態に係る累積計算装置１０は一般的なコンピュータ又はコンピュータシステムのハードウェア構成で実現され、入力装置１０１と、表示装置１０２と、外部Ｉ／Ｆ１０３と、通信Ｉ／Ｆ１０４と、プロセッサ１０５と、メモリ装置１０６とを有する。これらの各ハードウェアは、それぞれがバス１０７により通信可能に接続される。
　入力装置１０１は、例えば、キーボードやマウス、タッチパネル、各種物理ボタン等である。表示装置１０２は、例えば、ディスプレイ等である。なお、累積計算装置１０は、例えば、入力装置１０１及び表示装置１０２のうちの少なくとも一方を有していなくてもよい。
　外部Ｉ／Ｆ１０３は、記録媒体１０３ａ等の外部装置とのインタフェースである。累積計算装置１０は、外部Ｉ／Ｆ１０３を介して、記録媒体１０３ａの読み取りや書き込み等を行うことができる。なお、記録媒体１０３ａとしては、例えば、ＣＤ（Compact Disc）、ＤＶＤ（Digital Versatile Disk）、ＳＤメモリカード（Secure Digital memory card）、ＵＳＢ（Universal Serial Bus）メモリカード等が挙げられる。
　通信Ｉ／Ｆ１０４は、累積計算装置１０を通信ネットワークに接続するためのインタフェースである。プロセッサ１０５は、例えば、ＣＰＵ（Central Processing Unit）やＧＰＵ（Graphics Processing Unit）等の各種演算装置である。メモリ装置１０６は、例えば、ＨＤＤ（Hard Disk Drive）やＳＳＤ（Solid State Drive）、フラッシュメモリ、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）等の各種記憶装置である。
　本実施形態に係る累積計算装置１０は、図１に示すハードウェア構成を有することにより、後述する各種処理を実現することができる。なお、図１に示すハードウェア構成は一例であって、累積計算装置１０は、例えば、複数のプロセッサ１０５を有していてもよいし、複数のメモリ装置１０６を有していてもよい。また、累積計算装置１０は、図示したハードウェア以外にも様々なハードウェアを有していてもよい。
　＜累積計算装置１０の機能構成＞
　本実施形態に係る累積計算装置１０の機能構成を図２に示す。図２に示すように、本実施形態に係る累積計算装置１０は、値変換部２０１と、二項演算作成部２０２と、累積計算部２０３と、出力部２０４と、記憶部２０５とを有する。値変換部２０１、二項演算作成部２０２、累積計算部２０３、及び出力部２０４は、例えば、累積計算装置１０にインストールされた１以上のプログラムがプロセッサ１０５に実行させる処理により実現される。また、記憶部２０５は、例えば、メモリ装置１０６により実現される。なお、記憶部２０５は、例えば、累積計算装置１０と通信ネットワークを介して接続される記憶装置等により実現されていてもよい。
　値変換部２０１は、ｖの各要素のうちグループ内での先頭の要素には１、それ以外の要素には０を対応させた値の列をｃ＝（ｃ１，・・・，ｃｎ）として、ｖをｖ'＝（ｖ１'，・・・，ｖｎ'）（ただし、ｖｉ'＝（ｖｉ，ｃｉ））に変換する。
　二項演算作成部２０２は、データ全体に対する累積計算によって元の二項演算によるグループ別の累積を計算できるような新たな二項演算を作成する。
　累積計算部２０３は、ｖ'＝（ｖ１'，・・・，ｖｎ'）全体に対して新たな二項演算による累積計算を行う。
　出力部２０４は、新たな二項演算による累積計算の結果から、元の二項演算によるグループ別の累積計算の結果を取り出し、その取り出した結果を出力する。
　記憶部２０５は、累積計算の対象であるｎ個の値の列ｖ＝（ｖ１，・・・，ｖｎ）や累積計算の途中結果、累積計算結果等を記憶する。
　＜累積計算処理の流れ＞
　本実施形態に係る累積計算処理の流れについて図３を参照しながら説明する。
　まず、値変換部２０１は、ｖの各要素のうちグループ内での先頭の要素には１、それ以外の要素には０を対応させた値の列をｃ＝（ｃ１，・・・，ｃｎ）として、ｖをｖ'＝（ｖ１'，・・・，ｖｎ'）（ただし、ｖｉ'＝（ｖｉ，ｃｉ））に変換する（ステップＳ１０１）。
　次に、二項演算作成部２０２は、データ全体（つまり、ｎ個の値ｖ１'，・・・，ｖｎ'全体）に対する累積計算によって元の二項演算によるグループ別の累積を計算できるような新たな二項演算
Figure JPOXMLDOC01-appb-M000002
 として、以下により定義される二項演算を作成する（ステップＳ１０２）。
Figure JPOXMLDOC01-appb-M000003
 　ここで、ｗ，ｙは任意の値を取り得る変数、ｘ，ｚは０又は１を取り得る変数、ＯＲはｘとｚの少なくとも一方が１のときに１、それ以外のときに０となる演算子（つまり、論理和を表す演算子）である。
　次に、累積計算部２０３は、ｖ'＝（ｖ１'，・・・，ｖｎ'）全体に対して新たな二項演算により累積を計算する（ステップＳ１０３）。すなわち、累積計算部２０３は、新たな二項演算によりｖ'の累積ｓ'＝（ｓ１'，・・・，ｓｎ'）を計算する。ここで、各ｉ＝１，・・・，ｎに対して、
Figure JPOXMLDOC01-appb-M000004
 である。
　そして、出力部２０４は、各ｓｉ'をｓｉ'＝（ｕｉ，ｄｉ）とするとき、値の列ｕ＝（ｕ１，・・・，ｕｎ）を取り出し、元の二項演算の累積結果として出力する（ステップＳ１０４）。このとき、各ｕｉが、元の二項演算によるｖ１，・・・，ｖｉの累積計算の結果となる。また、各ｉ＝１，・・・，ｎについて、ｄｉ＝１である。
　なお、出力部２０４による出力先は任意としてよいが、例えば、記憶部２０５に保存する、他の装置又は機器に送信する、等とすることが考えられる。
　＜実施例＞
　以下では、上記の累積計算処理の実施例について説明する。
　　≪実施例１≫
　本実施例では、先頭から４、２、１、３個ずつの４つのグループに分けられた値の列ｖ＝（３，５，１，２，４，６，１，３，２，８）が与えられ、二項演算ｍａｘ（ｘ，ｙ）によるグループごとの累積計算を行う場合について説明する。なお、ｍａｘ（ｘ，ｙ）はｘとｙの最大値を出力する二項演算である。
　まず、上記のステップＳ１０１では、グループの先頭の要素には１、それ以外の要素には０を対応させた値の列ｃ＝（１，０，０，０，１，０，１，１，０，０）が作成され、ｖが以下のｖ'に変換される。
　ｖ'＝（（ｖ１，ｃ１），・・・，（ｖ１０，ｃ１０））＝（（３，１），（５，０），（１，０），（２，０），（４，１），（６，０），（１，１），（３，１），（２，０），（８，０））
　上記のステップＳ１０２では、上記の数３で定義される新たな二項演算が作成され、上記のステップＳ１０３で、ｖ'＝（（ｖ１，ｃ１），・・・，（ｖ１０，ｃ１０））全体に対して新たな二項演算により累積が計算される。
　例えば、
Figure JPOXMLDOC01-appb-M000005
 を左から順に計算していく累積計算方法を用いると、ｓ'＝（ｓ１'，・・・，ｓ１０'）は以下のように計算できる。
Figure JPOXMLDOC01-appb-M000006
 　したがって、上記のステップＳ１０４ではｕ＝（３，５，５，５，４，６，１，３，３，８）が取り出され、それが出力される。このｕにより、元の二項演算ｍａｘ（ｘ，ｙ）によるグループごとの累積計算（つまり、グループ内の各要素までの累積の最大値の計算）ができていることがわかる。
　　≪実施例２≫
　上記の実施例１では、ステップＳ１０３で新たな二項演算によりｓ１'，・・・，ｓ１０'を左から順に計算したが、その代わりに、本実施例ではｓ１'，・・・，ｓ１０'を並列に計算する。これにより、実施例１よりも効率的に累積の計算を行うことが可能となる。なお、結合的な二項演算が並列に計算可能であることは既知である。
　＜まとめ＞
　以上のように、本実施形態に係る累積計算装置１０は、各グループ内で二項演算による累積の計算を行う際に、累積対象の各値に対してグループの先頭の要素には１、それ以外には０となるフラグを付与すると共に新たな二項演算を定義し、この新たな二項演算によりデータ全体（つまり、値とフラグの組の全体）に対して累積計算を行う。この新たな二項演算は、グループの先頭の要素は累積の値が計算済みであることを利用して、当該フラグを計算済みであるか否かを表すものと見做することで、元の二項演算を、値とフラグの組に対する二項演算に拡張したものである。
　これにより、本実施形態に係る累積計算装置１０は、例えば、秘密計算（秘密分散も含む。）によりグループ別の累積計算を行う場合であっても、効率的にその計算を行うことが可能となる。これは、累積の計算を行いたい二項演算を決められた順序で適用する任意の方法を使って、同じ順序で秘密計算によりグループ別の累積の計算が可能となるためである。このため、例えば、二項演算としてｍａｘ又はｍｉｎを用いることで、秘密計算でのｇｒｏｕｐ　ｂｙ　ｍａｘ又はｇｒｏｕｐ　ｂｙ　ｍｉｎ操作等を効率的に実現することが可能となる。
　したがって、本実施形態に係る累積計算装置１０は、通常のデータ処理に用いられるだけでなく、例えば、データ内容を秘匿化したままデータ処理やデータ分析を行う場合に適用することが可能である。具体例を挙げれば、本実施形態に係る累積計算装置１０は、データ内容を秘匿化したまま所定のタスク（例えば、何等かの予測、分類等）を実現する機械学習モデルの学習用データを作成することが可能である。また、それに加えて、本実施形態に係る累積計算装置１０は、その学習用データで学習された機械学習モデルにより種々の予測や分類、それら予測又は分類結果に基づく他の機器、装置、システム等の制御等を行うことも可能であってもよい。
　本発明は、具体的に開示された上記の実施形態に限定されるものではなく、請求の範囲の記載から逸脱することなく、種々の変形や変更、既知の技術との組み合わせ等が可能である。
　１０　　　　累積計算装置
　１０１　　　入力装置
　１０２　　　表示装置
　１０３　　　外部Ｉ／Ｆ
　１０３ａ　　記録媒体
　１０４　　　通信Ｉ／Ｆ
　１０５　　　プロセッサ
　１０６　　　メモリ装置
　１０７　　　バス
　２０１　　　値変換部
　２０２　　　二項演算作成部
　２０３　　　累積計算部
　２０４　　　出力部
　２０５　　　記憶部

Claims (5)

  1. 　グループに分けられたｎ個の値の列ｖ＝（ｖ１，・・・，ｖｎ）に関して、結合的な二項演算により前記グループごとの累積を計算する累積計算装置であって、
    　ｖの各要素ｖ１，・・・，ｖｎのうち、前記グループの先頭の要素には１、前記先頭以外の要素には０を対応させた値の列をｃ＝（ｃ１，・・・，ｃｎ）として、ｖをｖ'＝（ｖ１'，・・・，ｖｎ'）（ただし、ｖｉ'＝（ｖｉ，ｃｉ））に変換する値変換部と、
    　前記二項演算を用いて、２つの対（ｗ，ｘ）と（ｙ，ｚ）（ただし、ｘ，ｚ∈｛０，１｝）に対して新しい対（ｐ，ｑ）を計算する新たな二項演算を作成する二項演算作成部と、
    　ｉ＝１，・・・，ｎについて、前記新たな二項演算により累積ｓｉ'（ただし、ｓｉ'は前記新たな二項演算によるｖ１'からｖｉ'までの累積）を計算する累積計算部と、
    　各ｓｉ'（ｉ＝１，・・・，ｎ）から前記グループごとの累積を示す値の列ｕ＝（ｕ１，・・・，ｕｎ）を取り出し、取り出したｕを出力する出力部と、
    　を有し、
    　前記新たな二項演算は、ｚ＝０である場合は前記二項演算によるｗとｙの演算結果をｐ、ｚ＝１である場合はｙをｐとし、ｘとｚの論理和をｑとする、累積計算装置。
  2. 　前記二項演算作成部は、
    　前記二項演算によるｗとｙの演算結果をｒ、論理和を表す演算子をＯＲとして、前記新たな二項演算による（ｗ，ｘ）と（ｙ，ｚ）の演算結果を（ｚｙ＋（１－ｚ）ｒ，ｘＯＲｚ）と定義することで、前記新たな二項演算を作成する、請求項１に記載の累積計算装置。
  3. 　前記出力部は、
    　ｓｉ'＝（ｕｉ，ｄｉ）として、ｕ＝（ｕ１，・・・，ｕｎ）を取り出し、取り出したｕを出力する、請求項１又は２に記載の累積計算装置。
  4. 　グループに分けられたｎ個の値の列ｖ＝（ｖ１，・・・，ｖｎ）に関して、結合的な二項演算により前記グループごとの累積を計算する累積計算装置が、
    　ｖの各要素ｖ１，・・・，ｖｎのうち、前記グループの先頭の要素には１、前記先頭以外の要素には０を対応させた値の列をｃ＝（ｃ１，・・・，ｃｎ）として、ｖをｖ'＝（ｖ１'，・・・，ｖｎ'）（ただし、ｖｉ'＝（ｖｉ，ｃｉ））に変換する値変換手順と、
    　前記二項演算を用いて、２つの対（ｗ，ｘ）と（ｙ，ｚ）（ただし、ｘ，ｚ∈｛０，１｝）に対して新しい対（ｐ，ｑ）を計算する新たな二項演算を作成する二項演算作成手順と、
    　ｉ＝１，・・・，ｎについて、前記新たな二項演算により累積ｓｉ'（ただし、ｓｉ'は前記新たな二項演算によるｖ１'からｖｉ'までの累積）を計算する累積計算手順と、
    　各ｓｉ'（ｉ＝１，・・・，ｎ）から前記グループごとの累積を示す値の列ｕ＝（ｕ１，・・・，ｕｎ）を取り出し、取り出したｕを出力する出力手順と、
    　を実行し、
    　前記新たな二項演算は、ｚ＝０である場合は前記二項演算によるｗとｙの演算結果をｐ、ｚ＝１である場合はｙをｐとし、ｘとｚの論理和をｑとする、累積計算方法。
  5. 　コンピュータを、請求項１乃至３の何れか一項に記載の累積計算装置として機能させるプログラム。
PCT/JP2021/022586 2021-06-14 2021-06-14 累積計算装置、累積計算方法、及びプログラム Ceased WO2022264237A1 (ja)

Priority Applications (5)

Application Number Priority Date Filing Date Title
EP21945917.9A EP4358070B1 (en) 2021-06-14 2021-06-14 Cumulative calculation device, cumulative calculation method, and program
JP2023528779A JP7544274B2 (ja) 2021-06-14 2021-06-14 累積計算装置、累積計算方法、及びプログラム
PCT/JP2021/022586 WO2022264237A1 (ja) 2021-06-14 2021-06-14 累積計算装置、累積計算方法、及びプログラム
US18/568,542 US20240281208A1 (en) 2021-06-14 2021-06-14 Cumulative calculation apparatus, cumulative calculation method, and program
CN202180099278.7A CN117480545A (zh) 2021-06-14 2021-06-14 累积计算装置、累积计算方法和程序

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
PCT/JP2021/022586 WO2022264237A1 (ja) 2021-06-14 2021-06-14 累積計算装置、累積計算方法、及びプログラム

Publications (1)

Publication Number Publication Date
WO2022264237A1 true WO2022264237A1 (ja) 2022-12-22

Family

ID=84526861

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2021/022586 Ceased WO2022264237A1 (ja) 2021-06-14 2021-06-14 累積計算装置、累積計算方法、及びプログラム

Country Status (5)

Country Link
US (1) US20240281208A1 (ja)
EP (1) EP4358070B1 (ja)
JP (1) JP7544274B2 (ja)
CN (1) CN117480545A (ja)
WO (1) WO2022264237A1 (ja)

Families Citing this family (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP7279796B2 (ja) * 2019-08-14 2023-05-23 日本電信電話株式会社 秘密勾配降下法計算方法、秘密深層学習方法、秘密勾配降下法計算システム、秘密深層学習システム、秘密計算装置、およびプログラム

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2014081475A (ja) * 2012-10-16 2014-05-08 Nippon Telegr & Teleph Corp <Ntt> 秘密計算システム、集約関数装置、秘密計算方法、およびプログラム
WO2019208486A1 (ja) * 2018-04-26 2019-10-31 日本電信電話株式会社 秘密集約中央値システム、秘密計算装置、秘密集約中央値方法、およびプログラム
WO2019208484A1 (ja) * 2018-04-25 2019-10-31 日本電信電話株式会社 秘密集約総和システム、秘密計算装置、秘密集約総和方法、およびプログラム
WO2019208485A1 (ja) * 2018-04-25 2019-10-31 日本電信電話株式会社 秘密集約最大値システム、秘密集約最小値システム、秘密計算装置、秘密集約最大値方法、秘密集約最小値方法、およびプログラム
WO2019225401A1 (ja) * 2018-05-25 2019-11-28 日本電信電話株式会社 秘密集約関数計算システム、秘密計算装置、秘密集約関数計算方法、およびプログラム

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2014081475A (ja) * 2012-10-16 2014-05-08 Nippon Telegr & Teleph Corp <Ntt> 秘密計算システム、集約関数装置、秘密計算方法、およびプログラム
WO2019208484A1 (ja) * 2018-04-25 2019-10-31 日本電信電話株式会社 秘密集約総和システム、秘密計算装置、秘密集約総和方法、およびプログラム
WO2019208485A1 (ja) * 2018-04-25 2019-10-31 日本電信電話株式会社 秘密集約最大値システム、秘密集約最小値システム、秘密計算装置、秘密集約最大値方法、秘密集約最小値方法、およびプログラム
WO2019208486A1 (ja) * 2018-04-26 2019-10-31 日本電信電話株式会社 秘密集約中央値システム、秘密計算装置、秘密集約中央値方法、およびプログラム
WO2019225401A1 (ja) * 2018-05-25 2019-11-28 日本電信電話株式会社 秘密集約関数計算システム、秘密計算装置、秘密集約関数計算方法、およびプログラム

Non-Patent Citations (3)

* Cited by examiner, † Cited by third party
Title
DAI IKARASHIKOJI CHIDAKOKI HAMADAKATSUMI TAKAHASHI: "Efficiency of Lightweight Verifiable Three-Party Secret Function Computation and Secure Database Processing Using the Same", SCIS, 2011, pages 1 - 8
KOJI CHIDAKOKI HAMADADAI IKARASHIKATSUMI TAKAHASHI: "Reconsideration of Lightweight Verifiable Three-Party Secret Function Calculation", CSS, 2010
See also references of EP4358070A4

Also Published As

Publication number Publication date
US20240281208A1 (en) 2024-08-22
EP4358070A1 (en) 2024-04-24
EP4358070B1 (en) 2026-03-25
CN117480545A (zh) 2024-01-30
JP7544274B2 (ja) 2024-09-03
EP4358070A4 (en) 2025-03-26
JPWO2022264237A1 (ja) 2022-12-22

Similar Documents

Publication Publication Date Title
EP3316235A1 (en) Secret calculation device, secret calculation method, and program
JP6111543B2 (ja) 類似サブ時系列の抽出方法及び装置
CN109328377A (zh) 秘密计算系统、秘密计算装置、秘密计算方法、以及程序
CN116109121A (zh) 基于大数据分析的用户需求挖掘方法及系统
WO2022264237A1 (ja) 累積計算装置、累積計算方法、及びプログラム
WO2021214833A1 (ja) 学習装置、異常検知装置、学習方法及び異常検知方法
CN111381768B (zh) 一种数据监控的方法和装置
Purnaye et al. BiSHM: Evidence detection and preservation model for cloud forensics
JP7476715B2 (ja) 情報処理装置及び重複率見積もりプログラム
CN106796764B (zh) 部分字符串位置检测装置、方法及记录介质
JP2020027547A (ja) テンソルデータ計算装置、テンソルデータ計算方法及びプログラム
CN109478381A (zh) 秘密计算系统、秘密计算装置、秘密计算方法以及程序
JP6142878B2 (ja) 情報システムの性能評価装置、方法およびプログラム
CN111679959A (zh) 计算机性能数据确定方法、装置、计算机设备及存储介质
JP7548450B2 (ja) 安全性評価指標計算装置、安全性評価指標計算方法、及びプログラム
WO2022264238A1 (ja) 累積計算装置、累積計算方法、及びプログラム
JP7694684B2 (ja) 秘密分割装置、秘密分割方法、及びプログラム
JP7491390B2 (ja) 秘密グループ分け装置、秘密グループ分けシステム、秘密グループ分け方法、及びプログラム
US20230325304A1 (en) Secret decision tree test apparatus, secret decision tree test system, secret decision tree test method, and program
JP6831307B2 (ja) 解算出装置、解算出方法及び解算出プログラム
WO2022259489A1 (ja) プライベートべき乗変換装置、プライベートべき乗変換方法、及びプログラム
CN113223612B (zh) 基因组的特征提取方法
JP7452700B2 (ja) 疑似データ生成装置、疑似データ生成方法及びプログラム
JP2023038481A (ja) 解釈方法、解釈装置、及びプログラム
WO2025177386A1 (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: 21945917

Country of ref document: EP

Kind code of ref document: A1

WWE Wipo information: entry into national phase

Ref document number: 2023528779

Country of ref document: JP

WWE Wipo information: entry into national phase

Ref document number: 18568542

Country of ref document: US

WWE Wipo information: entry into national phase

Ref document number: 202180099278.7

Country of ref document: CN

WWE Wipo information: entry into national phase

Ref document number: 2021945917

Country of ref document: EP

NENP Non-entry into the national phase

Ref country code: DE

ENP Entry into the national phase

Ref document number: 2021945917

Country of ref document: EP

Effective date: 20240115

WWG Wipo information: grant in national office

Ref document number: 2021945917

Country of ref document: EP