(57)【要約】  ＰｉとＰ＋がａ＋∈｛ａ０，ａ１，ａ２｝およびｂ＋∈｛ｂ０，ｂ１，ｂ２｝を格納しており、ＰｉとＰ−がａ−∈Ａ−およびｂ−∈Ｂ−を格納している。ただし、Ｐ＋＝Ｐ（ｉ＋１）ｍｏｄ３、Ｐ−＝Ｐ（ｉ−１）ｍｏｄ３、ａ，ｂが任意値であり、ａ＝ａ０＋ａ１＋ａ２およびｂ＝ｂ０＋ｂ１＋ｂ２を満たし、Ａ−は｛ａ０，ａ１，ａ２｝におけるａ＋の補集合、Ｂ−は｛ｂ０，ｂ１，ｂ２｝におけるｂ＋の補集合である。ＰｉとＰ＋がｒ＋を共有し、ＰｉとＰ−がｒ−を共有し、Ｐｉがｃ＋＝（ａ＋＋ａ−）（ｂ＋＋ｂ−）−ａ−ｂ−＋ｒ＋−ｒ−を計算する。ＰｉはＰ＋にｃ＋を送る。
2019009180.tif 000002
【特許請求の範囲】
【請求項１】
秘密計算装置Ｐ０と秘密計算装置Ｐ１と秘密計算装置Ｐ２とを有し、
ｉ∈｛０，１，２｝であり、Ｐ＋がＰ（ｉ＋１）ｍｏｄ３であり、Ｐ−がＰ（ｉ−１）ｍｏｄ３であり、ａ，ｂが任意値であり、ａ０，ａ１，ａ２がａ＝ａ０＋ａ１＋ａ２を満たすサブシェアであり、ｂ０，ｂ１，ｂ２がｂ＝ｂ０＋ｂ１＋ｂ２を満たすサブシェアであり、
前記秘密計算装置Ｐｉの記憶部と前記秘密計算装置Ｐ＋の記憶部とが前記サブシェアａ＋∈｛ａ０，ａ１，ａ２｝およびｂ＋∈｛ｂ０，ｂ１，ｂ２｝を格納しており、
前記秘密計算装置Ｐｉの記憶部と前記秘密計算装置Ｐ−の記憶部とが前記サブシェアａ−∈Ａ−およびｂ−∈Ｂ−を格納しており、Ａ−は｛ａ０，ａ１，ａ２｝におけるａ＋の補集合であり、Ｂ−は｛ｂ０，ｂ１，ｂ２｝におけるｂ＋の補集合であり、
前記秘密計算装置Ｐｉの共有部と前記秘密計算装置Ｐ＋の共有部とが任意値ｒ＋を共有し、
前記秘密計算装置Ｐｉの共有部と前記秘密計算装置Ｐ−の共有部とが任意値ｒ−を共有し、
前記秘密計算装置Ｐｉの演算部がｃ＋＝（ａ＋＋ａ−）（ｂ＋＋ｂ−）−ａ−ｂ−＋ｒ＋−ｒ−を計算し、
前記秘密計算装置Ｐｉの出力部が前記秘密計算装置Ｐ＋に対してｃ＋を出力し、前記秘密計算装置Ｐ＋の入力部にｃ＋が入力される、秘密計算システム。
【請求項２】
秘密計算装置Ｐ０と秘密計算装置Ｐ１と秘密計算装置Ｐ２とを有し、
ｉ∈｛０，１，２｝であり、Ｐ＋がＰ（ｉ＋１）ｍｏｄ３であり、Ｐ−がＰ（ｉ−１）ｍｏｄ３であり、ａ（ｎ），ｂ（ｎ）が任意値であり、ａ０（ｎ），ａ１（ｎ），ａ２（ｎ）がａ（ｎ）＝ａ０（ｎ）＋ａ１（ｎ）＋ａ２（ｎ）を満たすサブシェアであり、ｂ０（ｎ），ｂ１（ｎ），ｂ２（ｎ）がｂ（ｎ）＝ｂ０（ｎ）＋ｂ１（ｎ）＋ｂ２（ｎ）を満たすサブシェアであり、Ｎが正整数であり、ｎ＝０，…，Ｎ−１であり、
前記秘密計算装置Ｐｉの記憶部と前記秘密計算装置Ｐ＋の記憶部とが前記サブシェアａ＋（ｎ）∈｛ａ０（ｎ），ａ１（ｎ），ａ２（ｎ）｝およびｂ＋（ｎ）∈｛ｂ０（ｎ），ｂ１（ｎ），ｂ２（ｎ）｝を格納しており、
前記秘密計算装置Ｐｉの記憶部と前記秘密計算装置Ｐ−の記憶部とが前記サブシェアａ−（ｎ）∈Ａ−（ｎ）およびｂ−（ｎ）∈Ｂ−（ｎ）を格納しており、Ａ−（ｎ）は｛ａ０（ｎ），ａ１（ｎ），ａ２（ｎ）｝におけるａ＋（ｎ）の補集合であり、Ｂ−（ｎ）は｛ｂ０（ｎ），ｂ１（ｎ），ｂ２（ｎ）｝におけるｂ＋（ｎ）の補集合であり、
前記秘密計算装置Ｐｉの共有部と前記秘密計算装置Ｐ＋の共有部とが任意値ｒ＋を共有し、
前記秘密計算装置Ｐｉの共有部と前記秘密計算装置Ｐ−の共有部とが任意値ｒ−を共有し、
前記秘密計算装置Ｐｉの演算部が
【数６】
2019009180.tif 000008
を計算し、
前記秘密計算装置Ｐｉの出力部が前記秘密計算装置Ｐ＋に対してｃ＋を出力し、前記秘密計算装置Ｐ＋の入力部にｃ＋が入力される、秘密計算システム。
【請求項３】
ｉ∈｛０，１，２｝であり、Ｐ＋がＰ（ｉ＋１）ｍｏｄ３であり、Ｐ−がＰ（ｉ−１）ｍｏｄ３であり、ａ，ｂが任意値であり、ａ０，ａ１，ａ２がａ＝ａ０＋ａ１＋ａ２を満たすサブシェアであり、ｂ０，ｂ１，ｂ２がｂ＝ｂ０＋ｂ１＋ｂ２を満たすサブシェアであり、
秘密計算装置Ｐ＋に格納された前記サブシェアａ＋∈｛ａ０，ａ１，ａ２｝およびｂ＋∈｛ｂ０，ｂ１，ｂ２｝、ならびに、秘密計算装置Ｐ−に格納された前記サブシェアａ−∈Ａ−およびｂ−∈Ｂ−を格納する記憶部と（ただし、Ａ−は｛ａ０，ａ１，ａ２｝におけるａ＋の補集合であり、Ｂ−は｛ｂ０，ｂ１，ｂ２｝におけるｂ＋の補集合である）、
前記秘密計算装置Ｐ＋との間で任意値ｒ＋を共有し、前記秘密計算装置Ｐ−との間で任意値ｒ−を共有する共有部と、
ｃ＋＝（ａ＋＋ａ−）（ｂ＋＋ｂ−）−ａ−ｂ−＋ｒ＋−ｒ−を計算する演算部と、
ｃ＋を前記秘密計算装置Ｐ＋に対して出力する出力部と、
を有する秘密計算装置。
【請求項４】
ｉ∈｛０，１，２｝であり、Ｐ＋がＰ（ｉ＋１）ｍｏｄ３であり、Ｐ−がＰ（ｉ−１）ｍｏｄ３であり、ａ（ｎ），ｂ（ｎ）が任意値であり、ａ０（ｎ），ａ１（ｎ），ａ２（ｎ）がａ（ｎ）＝ａ０（ｎ）＋ａ１（ｎ）＋ａ２（ｎ）を満たすサブシェアであり、ｂ０（ｎ），ｂ１（ｎ），ｂ２（ｎ）がｂ（ｎ）＝ｂ０（ｎ）＋ｂ１（ｎ）＋ｂ２（ｎ）を満たすサブシェアであり、
秘密計算装置Ｐ＋に格納された前記サブシェアａ＋（ｎ）∈｛ａ０（ｎ），ａ１（ｎ），ａ２（ｎ）｝およびｂ＋（ｎ）∈｛ｂ０（ｎ），ｂ１（ｎ），ｂ２（ｎ）｝、ならびに、秘密計算装置Ｐ−に格納された前記サブシェアａ−（ｎ）∈Ａ−（ｎ）およびｂ−（ｎ）∈Ｂ−（ｎ）を格納する記憶部と（ただし、Ａ−（ｎ）は｛ａ０（ｎ），ａ１（ｎ），ａ２（ｎ）｝におけるａ＋（ｎ）の補集合であり、Ｂ−（ｎ）は｛ｂ０（ｎ），ｂ１（ｎ），ｂ２（ｎ）｝におけるｂ＋（ｎ）の補集合である）、
前記秘密計算装置Ｐ＋との間で任意値ｒ＋を共有し、前記秘密計算装置Ｐ−との間で任意値ｒ−を共有する共有部と、
【数７】
2019009180.tif 000009
を計算する演算部と、
ｃ＋を前記秘密計算装置Ｐ＋に対して出力する出力部と、
を有する秘密計算装置。
【請求項５】
請求項４の秘密計算装置であって、前記任意値ｒ＋がｒ＋（ｎ）であり、前記任意値ｒ−がｒ−（ｎ）である、秘密計算装置。
【請求項６】
ｉ∈｛０，１，２｝であり、Ｐ＋がＰ（ｉ＋１）ｍｏｄ３であり、Ｐ−がＰ（ｉ−１）ｍｏｄ３であり、ａ，ｂが任意値であり、ａ０，ａ１，ａ２がａ＝ａ０＋ａ１＋ａ２を満たすサブシェアであり、ｂ０，ｂ１，ｂ２がｂ＝ｂ０＋ｂ１＋ｂ２を満たすサブシェアであり、
秘密計算装置Ｐ＋に格納された前記サブシェアａ＋∈｛ａ０，ａ１，ａ２｝およびｂ＋∈｛ｂ０，ｂ１，ｂ２｝、ならびに、秘密計算装置Ｐ−に格納された前記サブシェアａ−∈Ａ−およびｂ−∈Ｂ−が秘密計算装置Ｐｉの記憶部に格納されており、Ａ−は｛ａ０，ａ１，ａ２｝におけるａ＋の補集合であり、Ｂ−は｛ｂ０，ｂ１，ｂ２｝におけるｂ＋の補集合であり、
前記秘密計算装置Ｐｉの共有部が、前記秘密計算装置Ｐ＋との間で任意値ｒ＋を共有し、前記秘密計算装置Ｐ−との間で任意値ｒ−を共有するステップと、
前記秘密計算装置Ｐｉの演算部が、ｃ＋＝（ａ＋＋ａ−）（ｂ＋＋ｂ−）−ａ−ｂ−＋ｒ＋−ｒ−を計算するステップと、
前記秘密計算装置Ｐｉの出力部が前記秘密計算装置Ｐ＋に対してｃ＋を出力するステップと、
を有する秘密計算方法。
【請求項７】
ｉ∈｛０，１，２｝であり、Ｐ＋がＰ（ｉ＋１）ｍｏｄ３であり、Ｐ−がＰ（ｉ−１）ｍｏｄ３であり、ａ（ｎ），ｂ（ｎ）が任意値であり、ａ０（ｎ），ａ１（ｎ），ａ２（ｎ）がａ（ｎ）＝ａ０（ｎ）＋ａ１（ｎ）＋ａ２（ｎ）を満たすサブシェアであり、ｂ０（ｎ），ｂ１（ｎ），ｂ２（ｎ）がｂ（ｎ）＝ｂ０（ｎ）＋ｂ１（ｎ）＋ｂ２（ｎ）を満たすサブシェアであり、
秘密計算装置Ｐ＋に格納された前記サブシェアａ＋（ｎ）∈｛ａ０（ｎ），ａ１（ｎ），ａ２（ｎ）｝およびｂ＋（ｎ）∈｛ｂ０（ｎ），ｂ１（ｎ），ｂ２（ｎ）｝、ならびに、秘密計算装置Ｐ−に格納された前記サブシェアａ−（ｎ）∈Ａ−（ｎ）およびｂ−（ｎ）∈Ｂ−（ｎ）が秘密計算装置Ｐｉの記憶部に格納されており、Ａ−（ｎ）は｛ａ０（ｎ），ａ１（ｎ），ａ２（ｎ）｝におけるａ＋（ｎ）の補集合であり、Ｂ−（ｎ）は｛ｂ０（ｎ），ｂ１（ｎ），ｂ２（ｎ）｝におけるｂ＋（ｎ）の補集合であり、
前記秘密計算装置Ｐｉの共有部が、前記秘密計算装置Ｐ＋との間で任意値ｒ＋を共有し、前記秘密計算装置Ｐ−との間で任意値ｒ−を共有するステップと、
前記秘密計算装置Ｐｉの演算部が、
【数８】
2019009180.tif 000010
を計算するステップと、
前記秘密計算装置Ｐｉの出力部が前記秘密計算装置Ｐ＋に対してｃ＋を出力するステップと、
を有する秘密計算方法。
【請求項８】
請求項３または４の秘密計算装置としてコンピュータを機能させるためのプログラム。
【請求項９】
請求項３または４の秘密計算装置としてコンピュータを機能させるためのプログラムを格納したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号技術分野に関し、特に秘密計算技術分野に関する。
【背景技術】
【０００２】
複数の秘密計算装置間で値の受け渡しを行い、各秘密計算装置が他の秘密計算装置から受け取った値を用いて秘密乗算や秘密積和などの秘密計算を行う方式がある（例えば、特許文献１等参照）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特許６００６８４２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、特許文献１に記載された方式は加減乗算数回数およびメモリアクセス回数が多いという課題がある。【０００５】
本発明の目的は、従来よりも少ない加減乗算数回数およびメモリアクセス回数で秘密乗算または秘密積和を行う技術を提供することである。
【課題を解決するための手段】
【０００６】
本発明の秘密乗算は次のように行われる。秘密計算装置Ｐｉの記憶部と秘密計算装置Ｐ＋の記憶部とがサブシェアａ＋∈｛ａ０，ａ１，ａ２｝およびｂ＋∈｛ｂ０，ｂ１，ｂ２｝を格納しており、秘密計算装置Ｐｉの記憶部と秘密計算装置Ｐ−の記憶部とがサブシェアａ−∈Ａ−およびｂ−∈Ｂ−を格納している。ただし、ｉ∈｛０，１，２｝であり、Ｐ＋がＰ（ｉ＋１）ｍｏｄ３であり、Ｐ−がＰ（ｉ−１）ｍｏｄ３であり、ａ，ｂが任意値であり、ａ０，ａ１，ａ２がａ＝ａ０＋ａ１＋ａ２を満たすサブシェアであり、ｂ０，ｂ１，ｂ２がｂ＝ｂ０＋ｂ１＋ｂ２を満たすサブシェアであり、Ａ−は｛ａ０，ａ１，ａ２｝におけるａ＋の補集合であり、Ｂ−は｛ｂ０，ｂ１，ｂ２｝におけるｂ＋の補集合である。秘密計算装置Ｐｉの共有部と秘密計算装置Ｐ＋の共有部とが任意値ｒ＋を共有し、秘密計算装置Ｐｉの共有部と秘密計算装置Ｐ−の共有部とが任意値ｒ−を共有し、秘密計算装置Ｐｉの演算部がｃ＋＝（ａ＋＋ａ−）（ｂ＋＋ｂ−）−ａ−ｂ−＋ｒ＋−ｒ−を計算する。各秘密計算装置Ｐｉの出力部は秘密計算装置Ｐ＋に対してｃ＋を出力し、秘密計算装置Ｐ＋の入力部にｃ＋が入力される。【０００７】
本発明の秘密積和は次のように行われる。秘密計算装置Ｐｉの記憶部と秘密計算装置Ｐ＋の記憶部とがサブシェアａ＋（ｎ）∈｛ａ０（ｎ），ａ１（ｎ），ａ２（ｎ）｝およびｂ＋（ｎ）∈｛ｂ０（ｎ），ｂ１（ｎ），ｂ２（ｎ）｝を格納しており、秘密計算装置Ｐｉの記憶部と秘密計算装置Ｐ−の記憶部とがサブシェアａ−（ｎ）∈Ａ−（ｎ）およびｂ−（ｎ）∈Ｂ−（ｎ）を格納している。ただし、ｉ∈｛０，１，２｝であり、Ｐ＋がＰ（ｉ＋１）ｍｏｄ３であり、Ｐ−がＰ（ｉ−１）ｍｏｄ３であり、ａ（ｎ），ｂ（ｎ）が任意値であり、ａ０（ｎ），ａ１（ｎ），ａ２（ｎ）がａ（ｎ）＝ａ０（ｎ）＋ａ１（ｎ）＋ａ２（ｎ）を満たすサブシェアであり、ｂ０（ｎ），ｂ１（ｎ），ｂ２（ｎ）がｂ（ｎ）＝ｂ０（ｎ）＋ｂ１（ｎ）＋ｂ２（ｎ）を満たすサブシェアであり、Ｎが正整数であり、ｎ＝０，…，Ｎ−１であり、Ａ−（ｎ）は｛ａ０（ｎ），ａ１（ｎ），ａ２（ｎ）｝におけるａ＋（ｎ）の補集合であり、Ｂ−（ｎ）は｛ｂ０（ｎ），ｂ１（ｎ），ｂ２（ｎ）｝におけるｂ＋（ｎ）の補集合である。秘密計算装置Ｐｉの共有部と秘密計算装置Ｐ＋の共有部とが任意値ｒ＋を共有し、秘密計算装置Ｐｉの共有部と秘密計算装置Ｐ−の共有部とが任意値ｒ−を共有し、秘密計算装置Ｐｉの演算部が
【数１】
2019009180.tif 000003
を計算する。各秘密計算装置Ｐｉは秘密計算装置Ｐ＋に対してｃ＋を出力し、秘密計算装置Ｐ＋の入力部にｃ＋が入力される。
【発明の効果】
【０００８】
これにより、従来よりも少ない加減乗算数回数およびメモリアクセス回数で秘密乗算または秘密積和を行うことができる。
【図面の簡単な説明】
【０００９】
【図１】図１は実施形態の秘密計算システムを例示したブロック図である。
【図２】図２は実施形態の秘密計算装置を例示したブロック図である。
【図３】図３は実施形態の秘密乗算を説明するための概念図である。
【図４】図４は実施形態の秘密計算方法を説明するためのフロー図である。
【図５】図５は実施形態の秘密積和を説明するための概念図である。
【図６】図６は実施形態の秘密計算方法を説明するためのフロー図である。
【発明を実施するための形態】
【００１０】
以下、図面を用いて本発明の実施形態を説明する。
【００１１】
［第１実施形態］
第１実施形態では、任意値ａ，ｂ∈Ｆの乗算ａｂ∈Ｆを秘密計算で行う（秘密乗算）。ただし、Ｆは有限体を表す。この秘密乗算では、任意値ａの秘密分散値（シェア）と任意値ｂの秘密分散値とから乗算結果ａｂの秘密分散値を得る。以下に詳細に説明する。
【００１２】
＜構成＞
図１に例示するように、本形態の秘密計算システム１は、３個の秘密計算装置１１−Ｐ０，１１−Ｐ１，１１−Ｐ２（秘密計算装置Ｐ０，Ｐ１，Ｐ２）を有する。秘密計算装置１１−Ｐ０，１１−Ｐ１，１１−Ｐ２は、インターネットなどの通信網を通じた通信が可能なように構成されている。図２に例示するように、本形態の秘密計算装置１１−Ｐ（ただし、Ｐ∈｛Ｐ０，Ｐ１，Ｐ２｝）は、記憶部１１１−Ｐ（ストレージおよびメモリ）、演算部１１２−Ｐ、制御部１１３−Ｐ、共有部１１４−Ｐ、および通信部１１５−Ｐを有する。秘密計算装置１１−Ｐは、制御部１１３−Ｐの制御のもとで各処理を実行し、各処理で得られたデータは、逐一、記憶部１１１−Ｐに格納され、必要に応じて読み出される。
【００１３】
＜事前処理＞
事前処理により、任意値ａがａ＝ａ０＋ａ１＋ａ２∈Ｆを満たすサブシェアａ０，ａ１，ａ２∈Ｆに秘密分散されており、任意値ｂがｂ＝ｂ０＋ｂ１＋ｂ２∈Ｆを満たすサブシェアｂ０，ｂ１，ｂ２∈Ｆに秘密分散されている。秘密計算装置１１−Ｐｉの記憶部１１１−Ｐｉはサブシェアａ＋∈｛ａ０，ａ１，ａ２｝およびｂ＋∈｛ｂ０，ｂ１，ｂ２｝を格納しており、秘密計算装置１１−Ｐ＋の記憶部１１１−Ｐ＋もサブシェアａ＋およびｂ＋を格納している。サブシェアａ＋は｛ａ０，ａ１，ａ２｝の何れか１つの要素であり、サブシェアｂ＋は｛ｂ０，ｂ１，ｂ２｝の何れか１つの要素である。秘密計算装置１１−Ｐｉの記憶部１１１−Ｐｉはサブシェアａ−∈Ａ−およびｂ−∈Ｂ−を格納しており、秘密計算装置１１−Ｐ−の記憶部１１１−Ｐ−もサブシェアａ−およびｂ−を格納している。サブシェアａ−はＡ−の何れか１つの要素であり、サブシェアｂ−はＢ−の何れか１つの要素である。ただし、Ａ−は｛ａ０，ａ１，ａ２｝におけるａ＋の補集合であり（Ａ−＝｛ａ０，ａ１，ａ２｝−｛ａ＋｝）、Ｂ−は｛ｂ０，ｂ１，ｂ２｝におけるｂ＋の補集合である（Ｂ−＝｛ｂ０，ｂ１，ｂ２｝−｛ｂ＋｝）。また、ｉ∈｛０，１，２｝であり、Ｐ＋はＰ（ｉ＋１）ｍｏｄ３であり、Ｐ−はＰ（ｉ−１）ｍｏｄ３である。図３の例では、秘密計算装置１１−Ｐ０の記憶部１１１−Ｐ０にサブシェア（ａ０，ａ１）および（ｂ０，ｂ１）が格納されており、秘密計算装置１１−Ｐ１の記憶部１１１−Ｐ１にサブシェア（ａ１，ａ２）および（ｂ１，ｂ２）が格納されており、秘密計算装置１１−Ｐ２の記憶部１１１−Ｐ２にサブシェア（ａ２，ａ０）および（ｂ２，ｂ０）が格納されている。なお、（ａ０，ａ１）（ａ１，ａ２）（ａ２，ａ０）はａの秘密分散値であり、（ｂ０，ｂ１）（ｂ１，ｂ２）（ｂ２，ｂ０）はｂの秘密分散値である。
【００１４】
＜秘密計算＞
この事前処理が行われたことを前提に、各秘密計算装置１１−Ｐｉ（ただし、ｉ∈｛０，１，２｝）は以下の秘密計算を行う（図３および図４）。
【００１５】
各秘密計算装置１１−Ｐｉの共有部１１４−Ｐｉと秘密計算装置１１−Ｐ＋の共有部１１４−Ｐ＋とが任意値ｒ＋∈Ｆを共有する。すなわち、共有部１１４−Ｐｉおよび共有部１１４−Ｐ＋は互いに同一の任意値ｒ＋を得る。共有された任意値ｒ＋は記憶部１１１−Ｐｉおよび記憶部１１１−Ｐ＋に格納される。任意値ｒ＋の例は、擬似乱数、真正乱数、予め定められた複数の値から選択された値、入力値、別処理で得られた値などである。任意値ｒ＋の共有は公知の方法によって実現できる。例えば、共有部１１４−Ｐｉから共有部１１４−Ｐ＋に任意値ｒ＋または任意値ｒ＋を特定するための情報を送ることで、共有部１１４−Ｐｉと共有部１１４−Ｐ＋との間で任意値ｒ＋が共有されてもよい。逆に、共有部１１４−Ｐ＋から共有部１１４−Ｐｉに任意値ｒ＋または任意値ｒ＋を特定するための情報を送ることで、共有部１１４−Ｐｉと共有部１１４−Ｐ＋との間で任意値ｒ＋が共有されてもよい。予め共有部１１４−Ｐｉと共有部１１４−Ｐ＋との間でシード値を共有しておき、共有部１１４−Ｐｉおよび共有部１１４−Ｐ＋がこのシード値を用いて予め定められた処理を行うことで、共有部１１４−Ｐｉと共有部１１４−Ｐ＋との間で任意値ｒ＋が共有されてもよい。公知の鍵交換アルゴリズムを用いて共有部１１４−Ｐｉと共有部１１４−Ｐ＋との間で任意値ｒ＋が共有されてもよい（ステップＳ１１）。
【００１６】
各秘密計算装置１１−Ｐｉの共有部１１４−Ｐｉと秘密計算装置１１−Ｐ−の共有部１１４−Ｐ−とが任意値ｒ−∈Ｆを共有する。すなわち、共有部１１４−Ｐｉおよび共有部１１４−Ｐ−は互いに同一の任意値ｒ−を得る。共有された任意値ｒ−は記憶部１１１−Ｐｉおよび記憶部１１１−Ｐ−に格納される。任意値ｒ−の例は、擬似乱数、真正乱数、予め定められた複数の値から選択された値、入力値、別処理で得られた値などである。任意値ｒ−の共有は公知の方法によって実現できる。例えば、共有部１１４−Ｐｉから共有部１１４−Ｐ−に任意値ｒ−または任意値ｒ−を特定するための情報を送ることで、共有部１１４−Ｐｉと共有部１１４−Ｐ＋との間で任意値ｒ−が共有されてもよい。逆に、共有部１１４−Ｐ−から共有部１１４−Ｐｉに任意値ｒ−または任意値ｒ−を特定するための情報を送ることで、共有部１１４−Ｐｉと共有部１１４−Ｐ＋との間で任意値ｒ−が共有されてもよい。あるいは、予め共有部１１４−Ｐｉと共有部１１４−Ｐ−との間でシード値を共有しておき、共有部１１４−Ｐｉおよび共有部１１４−Ｐ−がこのシード値を用いて予め定められた処理を行うことで、共有部１１４−Ｐｉと共有部１１４−Ｐ−との間で任意値ｒ−が共有されてもよい。公知の鍵交換アルゴリズムを用いて共有部１１４−Ｐｉと共有部１１４−Ｐ−との間で任意値ｒ−が共有されてもよい（ステップＳ１２）。
【００１７】
図３の例では、ステップＳ１１およびＳ１２の処理により、共有部１１４−Ｐ０と共有部１１４−Ｐ１とが任意値ｒ０１∈Ｆを共有し、共有部１１４−Ｐ１と共有部１１４−Ｐ２とが任意値ｒ１２∈Ｆを共有し、共有部１１４−Ｐ２と共有部１１４−Ｐ０とが任意値ｒ２０∈Ｆを共有する。
【００１８】
各秘密計算装置１１−Ｐｉの演算部１１２−Ｐｉが、記憶部１１１−Ｐから読み込んだａ＋，ａ−，ｂ＋，ｂ−，ｒ＋，ｒ−を用い、ｃ＋＝（ａ＋＋ａ−）（ｂ＋＋ｂ−）−ａ−ｂ−＋ｒ＋−ｒ−∈Ｆを計算して出力する。図３の例では、秘密計算装置１１−Ｐ０の演算部１１２−Ｐ０がｃ１＝（ａ０＋ａ１）（ｂ０＋ｂ１）−ａ０ｂ０＋ｒ０１−ｒ２０∈Ｆを計算して出力し、秘密計算装置１１−Ｐ１の演算部１１２−Ｐ１がｃ２＝（ａ１＋ａ２）（ｂ１＋ｂ２）−ａ１ｂ１＋ｒ１２−ｒ０１∈Ｆを計算して出力し、秘密計算装置１１−Ｐ２の演算部１１２−Ｐ２がｃ０＝（ａ２＋ａ０）（ｂ２＋ｂ０）−ａ２ｂ２＋ｒ２０−ｒ１２∈Ｆを計算して出力する（ステップＳ１３）。
【００１９】
各秘密計算装置１１−Ｐｉの通信部１１５−Ｐｉは秘密計算装置１１−Ｐ＋に対してｃ＋を送信する（ｃ＋を出力する）（ステップＳ１４）。ｃ＋は秘密計算装置１１−Ｐ＋の通信部１１５−Ｐ＋で受信（入力）される。秘密計算装置１１−Ｐ−の演算部１１２−Ｐ−で計算されて通信部１１５−Ｐ−から送信された値をｃ−と表記すると、各秘密計算装置１１−Ｐｉの通信部１１５−Ｐｉはｃ−を受信する（ステップＳ１５）。図３の例では、秘密計算装置１１−Ｐ０の通信部１１５−Ｐ０が秘密計算装置１１−Ｐ１に対してｃ１を送信し、ｃ１が秘密計算装置１１−Ｐ１の通信部１１５−Ｐ１で受信される。秘密計算装置１１−Ｐ１の通信部１１５−Ｐ１が秘密計算装置１１−Ｐ２に対してｃ２を送信し、ｃ２が秘密計算装置１１−Ｐ２の通信部１１５−Ｐ２で受信される。秘密計算装置１１−Ｐ２の通信部１１５−Ｐ２が秘密計算装置１１−Ｐ０に対してｃ０を送信し、ｃ０が秘密計算装置１１−Ｐ０の通信部１１５−Ｐ０で受信される（ステップＳ１４，Ｓ１５）。
【００２０】
ステップＳ１５で受信されたｃ−、および、ステップＳ１３で得られたｃ＋は、各秘密計算装置１１−Ｐｉの記憶部１１１−Ｐｉに格納される。図３の例では、（ｃ０，ｃ１）が秘密計算装置１１−Ｐ０の記憶部１１１−Ｐ０に格納され、（ｃ１，ｃ２）が秘密計算装置１１−Ｐ１の記憶部１１１−Ｐ１に格納され、（ｃ２，ｃ０）が秘密計算装置１１−Ｐ２の記憶部１１１−Ｐ２に格納される。
【００２１】
本形態のｃ０，ｃ１，ｃ２はａｂ＝ｃ０＋ｃ１＋ｃ２∈Ｆを満たす乗算結果ａｂのサブシェアであり、（ｃ０，ｃ１）（ｃ１，ｃ２）（ｃ２，ｃ０）は乗算結果ａｂの秘密分散値である。これらの秘密分散値（ｃ０，ｃ１）（ｃ１，ｃ２）（ｃ２，ｃ０）の何れか２個が得られれば乗算結果ａｂを復元できる。すなわち、ｃ０＋ｃ１＋ｃ２＝ａｂを満たす。図３の例では、
ｃ０＋ｃ１＋ｃ２
＝（ａ０＋ａ１）（ｂ０＋ｂ１）−ａ０ｂ０＋ｒ０１−ｒ２０＋（ａ１＋ａ２）（ｂ１＋ｂ２）−ａ１ｂ１＋ｒ１２−ｒ０１＋（ａ２＋ａ０）（ｂ２＋ｂ０）−ａ２ｂ２＋ｒ２０−ｒ１２
＝ａ０ｂ１＋ａ１ｂ０＋ａ１ｂ１＋ａ１ｂ２＋ａ２ｂ１＋ａ２ｂ２＋ａ２ｂ０＋ａ０ｂ２＋ａ０ｂ０
＝（ａ０＋ａ１＋ａ２）（ｂ０＋ｂ１＋ｂ２）
＝ａｂ
となる。
【００２２】
各秘密計算装置１１−Ｐｉの記憶部１１１−Ｐｉに格納された（ｃ−，ｃ＋）はさらに別の秘密計算装置（図示せず）の入力とされてもよいし、乗算結果ａｂの復元を行う復元装置（図示せず）の入力とされて乗算結果ａｂが復元されて出力されてもよい。
【００２３】
＜本形態の特徴＞
以上のように本形態では、特許文献１に記載された従来方式よりも少ない加減乗算数回数およびメモリアクセス回数で秘密乗算を行うことができる。すなわち、特許文献１に記載された従来方式では、各秘密計算装置は、メモリに格納された秘密分散値等を用いて自ら加減乗算を行って得た値をメモリに保存しておき、他の秘密計算装置で加減乗算を行って得られた値を受信してメモリに保存し、メモリに保存されたこれらの値を用いてさらに加減乗算を行う必要があった。そのため、特許文献１の方式は、加減乗算数回数およびメモリアクセス回数が多かった。これに対し、本形態では、メモリに格納された秘密分散値等を用いて自ら加減乗算を行って得た値、および、他の秘密計算装置で加減乗算を行って得られた値がそのまま演算結果のサブシェアとなるため、特許文献１の方式よりも加減乗算数回数およびメモリアクセス回数が少ない。特に、演算速度の速い秘密計算ではメモリへのアクセス時間が全体の演算速度を向上する上でのボトルネックとなるが、本形態の方式ではメモリアクセス回数を削減できるため、演算速度を大幅に向上できる。例えば、従来技術の秘密乗算では、ｃＸＹ＝ａ−ｂ＋＋ａ＋ｂ−−ｒＺＸを計算するときにａ−，ｂ＋，ａ＋，ｂ−を読み込み、得られたｃＸＹを書き込む。これには乗算を２回、加減算を２回行う必要がある。さらに、従来技術の秘密乗算では、ｃ−＝ａ−ｂ−＋ｃＺＸ＋ｒＺＸを計算するときにａ−，ｂ−，ｃＺＸを読み込み、ｃ−を書き込む。これには乗算を１回、加減算を３回行う必要がある。またさらに、従来技術の秘密乗算では、ｃ＋＝ａ＋ｂ＋＋ｃＸＹ＋ｒＸＹを計算するときにａ＋，ｂ＋，ｃＸＹを読み込み、得られたｃ＋を書き込む。これには乗算を１回、加減算を３回行う必要がある。そのため、パーティあたりで合計、読込を１０回、書込を３回、乗算を４回、加減算を８回行う必要があった。これに対し、本形態の場合、秘密計算装置１０−Ｐｉはｃ＋＝（ａ＋＋ａ−）（ｂ＋＋ｂ−）−ａ−ｂ−＋ｒ＋−ｒ−を計算するときにａ−，ｂ＋，ａ＋，ｂ−を読み込み、得られたｃ＋を書き込む。そのため、パーティあたり、合計で読込４回、書込１回、乗算２回、加減算５回を行えばよい。従来技術と比較した場合、本形態では読込回数を４０％、書込回数を３３％、乗算回数を５０％、加減算回数を６３％にできる。
【００２４】
［第２実施形態］
第２実施形態では、任意値ａ（０），…，ａ（Ｎ−１）およびｂ（０），…，ｂ（Ｎ−１）に対する積和ａ（０）ｂ（０）＋…＋ａ（Ｎ−１）ｂ（Ｎ−１）∈Ｆを秘密計算で行う（秘密積和）。ただし、Ｆは有限体を表し、Ｎは正整数（例えば、２以上の整数）である。この秘密積和では、ｎ＝０，…，Ｎ−１についての任意値ａ（ｎ）の秘密分散値と任意値ｂ（ｎ）の秘密分散値とから積和結果ａ（０）ｂ（０）＋…＋ａ（Ｎ−１）ｂ（Ｎ−１）の秘密分散値を得る。以下に詳細に説明する。
【００２５】
＜構成＞
図１に例示するように、本形態の秘密計算システム２は、３個の秘密計算装置２１−Ｐ０，２１−Ｐ１，２１−Ｐ２（秘密計算装置Ｐ０，Ｐ１，Ｐ２）を有する。秘密計算装置２１−Ｐ０，２１−Ｐ１，２１−Ｐ２は、インターネットなどの通信網を通じた通信が可能なように構成されている。図２に例示するように、本形態の秘密計算装置２１−Ｐ（ただし、Ｐ∈｛Ｐ０，Ｐ１，Ｐ２｝）は、記憶部２１１−Ｐ（ストレージおよびメモリ）、演算部２１２−Ｐ、制御部２１３−Ｐ、共有部１１４−Ｐ、および通信部１１５−Ｐを有する。秘密計算装置２１−Ｐは、制御部２１３−Ｐの制御のもとで各処理を実行し、各処理で得られたデータは、逐一、記憶部２１１−Ｐに格納され、必要に応じて読み出される。
【００２６】
＜事前処理＞
事前処理により、ｎ＝０，…，Ｎ−１（ただし、Ｎは正整数、例えば、Ｎは２以上の整数）についての任意値ａ（ｎ）がａ（ｎ）＝ａ０（ｎ）＋ａ１（ｎ）＋ａ２（ｎ）∈Ｆを満たすサブシェアａ０（ｎ），ａ１（ｎ），ａ２（ｎ）∈Ｆに秘密分散されており、任意値ｂ（ｎ）がｂ（ｎ）＝ｂ０（ｎ）＋ｂ１（ｎ）＋ｂ２（ｎ）∈Ｆを満たすサブシェアｂ０（ｎ），ｂ１（ｎ），ｂ２（ｎ）∈Ｆに秘密分散されている。秘密計算装置２１−Ｐｉの記憶部２１１−Ｐｉは、ｎ＝０，…，Ｎ−１についてのサブシェアａ＋（ｎ）∈｛ａ０（ｎ），ａ１（ｎ），ａ２（ｎ）｝およびｂ＋（ｎ）∈｛ｂ０（ｎ），ｂ１（ｎ），ｂ２（ｎ）｝を格納しており、秘密計算装置２１−Ｐ＋の記憶部２１１−Ｐ＋も、ｎ＝０，…，Ｎ−１についてのサブシェアａ＋（ｎ）およびｂ＋（ｎ）を格納している。各サブシェアａ＋（ｎ）は｛ａ０（ｎ），ａ１（ｎ），ａ２（ｎ）｝の何れか１つの要素であり、各サブシェアｂ＋（ｎ）は｛ｂ０（ｎ），ｂ１（ｎ），ｂ２（ｎ）｝の何れか１つの要素である。秘密計算装置２１−Ｐｉの記憶部２１１−Ｐｉは、ｎ＝０，…，Ｎ−１についてのサブシェアａ−（ｎ）∈Ａ−（ｎ）およびｂ−（ｎ）∈Ｂ−（ｎ）を格納しており、秘密計算装置２１−Ｐ−の記憶部２１１−Ｐ−も、ｎ＝０，…，Ｎ−１についてのサブシェアａ−（ｎ）およびｂ−（ｎ）を格納している。各サブシェアａ−（ｎ）はＡ−（ｎ）の何れか１つの要素であり、各サブシェアｂ−（ｎ）はＢ−（ｎ）の何れか１つの要素である。ただし、Ａ−（ｎ）は｛ａ０（ｎ），ａ１（ｎ），ａ２（ｎ）｝におけるａ＋（ｎ）の補集合であり（Ａ−（ｎ）＝｛ａ０（ｎ），ａ１（ｎ），ａ２（ｎ）｝−｛ａ＋（ｎ）｝）、Ｂ−（ｎ）は｛ｂ０（ｎ），ｂ１（ｎ），ｂ２（ｎ）｝におけるｂ＋（ｎ）の補集合である（Ｂ−（ｎ）＝｛ｂ０（ｎ），ｂ１（ｎ），ｂ２（ｎ）｝−｛ｂ＋（ｎ）｝）。また、ｉ∈｛０，１，２｝であり、Ｐ＋はＰ（ｉ＋１）ｍｏｄ３であり、Ｐ−はＰ（ｉ−１）ｍｏｄ３である。図５の例では、秘密計算装置２１−Ｐ０の記憶部２１１−Ｐ０に、ｎ＝０，…，Ｎ−１についてのサブシェア（ａ０（ｎ），ａ１（ｎ））および（ｂ０（ｎ），ｂ１（ｎ））が格納されており、秘密計算装置２１−Ｐ１の記憶部２１１−Ｐ１に、ｎ＝０，…，Ｎ−１についてのサブシェア（ａ１（ｎ），ａ２（ｎ））および（ｂ１（ｎ），ｂ２（ｎ））が格納されており、秘密計算装置２１−Ｐ２の記憶部２１１−Ｐ２に、ｎ＝０，…，Ｎ−１についてのサブシェア（ａ２（ｎ），ａ０（ｎ））および（ｂ２（ｎ），ｂ０（ｎ））が格納されている。なお、（ａ０（ｎ），ａ１（ｎ））（ａ１（ｎ），ａ２（ｎ））（ａ２（ｎ），ａ０（ｎ））はａ（ｎ）の秘密分散値であり、（ｂ０（ｎ），ｂ１（ｎ））（ｂ１（ｎ），ｂ２（ｎ））（ｂ２（ｎ），ｂ０（ｎ））はｂ（ｎ）の秘密分散値である。
【００２７】
＜秘密計算＞
この事前処理が行われたことを前提に、各秘密計算装置２１−Ｐｉ（ただし、ｉ∈｛０，１，２｝）は以下の秘密計算を行う（図５および図６）。
【００２８】
各秘密計算装置２１−Ｐｉの共有部１１４−Ｐｉと秘密計算装置２１−Ｐ＋の共有部１１４−Ｐ＋とが任意値ｒ＋∈Ｆを共有する。共有された任意値ｒ＋は記憶部２１１−Ｐｉおよび記憶部２１１−Ｐ＋に格納される。任意値ｒ＋およびその共有処理の具体例は第１実施形態で説明した通りである（ステップＳ２１）。
【００２９】
各秘密計算装置２１−Ｐｉの共有部１１４−Ｐｉと秘密計算装置２１−Ｐ−の共有部１１４−Ｐ−とが任意値ｒ−∈Ｆを共有する。共有された任意値ｒ−は記憶部２１１−Ｐｉおよび記憶部２１１−Ｐ−に格納される。任意値ｒ−およびその共有処理の具体例は第１実施形態で説明した通りである（ステップＳ２２）。
【００３０】
図５の例では、ステップＳ２１およびＳ２２の処理により、共有部１１４−Ｐ０と共有部１１４−Ｐ１とが任意値ｒ０１∈Ｆを共有し、共有部１１４−Ｐ１と共有部１１４−Ｐ２とが任意値ｒ１２∈Ｆを共有し、共有部１１４−Ｐ２と共有部１１４−Ｐ０とが任意値ｒ２０∈Ｆを共有する。
【００３１】
各秘密計算装置２１−Ｐｉの演算部２１２−Ｐｉが、記憶部２１１−Ｐから読み込んだ、ｎ＝０，…，Ｎ−１についてのａ＋（ｎ），ａ−（ｎ），ｂ＋（ｎ），ｂ−（ｎ），ｒ＋，ｒ−を用い、
【数２】
2019009180.tif 000004
を計算して出力する。図５の例では、秘密計算装置２１−Ｐ０の演算部２１２−Ｐ０が
【数３】
2019009180.tif 000005
を計算して出力し、秘密計算装置２１−Ｐ１の演算部２１２−Ｐ１が
【数４】
2019009180.tif 000006
を計算して出力し、秘密計算装置２１−Ｐ２の演算部２１２−Ｐ２が
【数５】
2019009180.tif 000007
を計算して出力する（ステップＳ２３）。
【００３２】
各秘密計算装置２１−Ｐｉの通信部１１５−Ｐｉは秘密計算装置２１−Ｐ＋に対してｃ＋を送信する（ｃ＋を出力する）（ステップＳ２４）。ｃ＋は秘密計算装置２１−Ｐ＋の通信部１１５−Ｐ＋で受信（入力）される。秘密計算装置２１−Ｐ−の演算部２１２−Ｐ−で計算されて通信部１１５−Ｐ−から送信された値をｃ−と表記すると、各秘密計算装置２１−Ｐｉの通信部１１５−Ｐｉはｃ−を受信する（ステップＳ２５）。図５の例では、秘密計算装置２１−Ｐ０の通信部１１５−Ｐ０が秘密計算装置２１−Ｐ１に対してｃ１を送信し、ｃ１が秘密計算装置２１−Ｐ１の通信部１１５−Ｐ１で受信される。秘密計算装置２１−Ｐ１の通信部１１５−Ｐ１が秘密計算装置２１−Ｐ２に対してｃ２を送信し、ｃ２が秘密計算装置２１−Ｐ２の通信部１１５−Ｐ２で受信される。秘密計算装置２１−Ｐ２の通信部１１５−Ｐ２が秘密計算装置２１−Ｐ０に対してｃ０を送信し、ｃ０が秘密計算装置２１−Ｐ０の通信部１１５−Ｐ０で受信される（ステップＳ２４，Ｓ２５）。
【００３３】
ステップＳ２５で受信されたｃ−、および、ステップＳ２３で得られたｃ＋は、各秘密計算装置２１−Ｐｉの記憶部２１１−Ｐｉに格納される。図５の例では、（ｃ０，ｃ１）が秘密計算装置２１−Ｐ０の記憶部２１１−Ｐ０に格納され、（ｃ１，ｃ２）が秘密計算装置２１−Ｐ１の記憶部２１１−Ｐ１に格納され、（ｃ２，ｃ０）が秘密計算装置２１−Ｐ２の記憶部２１１−Ｐ２に格納される。
【００３４】
本形態のｃ０，ｃ１，ｃ２はａ（０）ｂ（０）＋…＋ａ（Ｎ−１）ｂ（Ｎ−１）＝ｃ０＋ｃ１＋ｃ２∈Ｆを満たす積和結果ａ（０）ｂ（０）＋…＋ａ（Ｎ−１）ｂ（Ｎ−１）のサブシェアである。（ｃ０，ｃ１）（ｃ１，ｃ２）（ｃ２，ｃ０）は積和結果ａ（０）ｂ（０）＋…＋ａ（Ｎ−１）ｂ（Ｎ−１）の秘密分散値である。これらの秘密分散値（ｃ０，ｃ１）（ｃ１，ｃ２）（ｃ２，ｃ０）の何れか２個が得られれば積和結果ａ（０）ｂ（０）＋…＋ａ（Ｎ−１）ｂ（Ｎ−１）を復元できる。すなわち、ｃ０＋ｃ１＋ｃ２＝ａ（０）ｂ（０）＋…＋ａ（Ｎ−１）ｂ（Ｎ−１）を満たす。
【００３５】
各秘密計算装置２１−Ｐｉの記憶部２１１−Ｐｉに格納された（ｃ−，ｃ＋）はさらに別の秘密計算装置（図示せず）の入力とされてもよいし、積和結果ａ（０）ｂ（０）＋…＋ａ（Ｎ−１）ｂ（Ｎ−１）の復元を行う復元装置（図示せず）の入力とされて積和結果ａ（０）ｂ（０）＋…＋ａ（Ｎ−１）ｂ（Ｎ−１）が復元されて出力されてもよい。
【００３６】
＜本形態の特徴＞
以上のように本形態では、特許文献１に記載された従来方式よりも少ない加減乗算数回数およびメモリアクセス回数で秘密積和を行うことができる。
【００３７】
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。また、第２実施形態の任意値ｒ＋がｎ＝０，…，Ｎ−１のそれぞれに対応するｒ＋（ｎ）であってもよいし、任意値ｒ−がｎ＝０，…，Ｎ−１のそれぞれに対応するｒ−（ｎ）であってもよい。例えば、図５の例において、任意値ｒ０１がｎ＝０，…，Ｎ−１のそれぞれに対応するｒ０１（ｎ）∈Ｆであってもよいし、任意値ｒ２０がｎ＝０，…，Ｎ−１のそれぞれに対応するｒ２０（ｎ）∈Ｆであってもよい。
【００３８】
上記の各装置は、例えば、ＣＰＵ（central processing unit）等のプロセッサ（ハードウェア・プロセッサ）およびＲＡＭ（random-access memory）・ＲＯＭ（read-only memory）等のメモリ等を備える汎用または専用のコンピュータが所定のプログラムを実行することで構成される。このコンピュータは１個のプロセッサやメモリを備えていてもよいし、複数個のプロセッサやメモリを備えていてもよい。このプログラムはコンピュータにインストールされてもよいし、予めＲＯＭ等に記録されていてもよい。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路（circuitry）ではなく、プログラムを用いることなく処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。１個の装置を構成する電子回路が複数のＣＰＵを含んでいてもよい。
【００３９】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００４０】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００４１】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【００４２】
コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されるのではなく、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【００４３】
１，２  秘密計算システム
１１−Ｐ  秘密計算装置
【図１】
2019009180.tif 000011
【図２】
2019009180.tif 000012
【図３】
2019009180.tif 000013
【図４】
2019009180.tif 000014
【図５】
2019009180.tif 000015
【図６】
2019009180.tif 000016
【手続補正書】
【提出日】令和1年12月5日(2019.12.5)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００１６
【補正方法】変更
【補正の内容】
【００１６】
各秘密計算装置１１−Ｐｉの共有部１１４−Ｐｉと秘密計算装置１１−Ｐ−の共有部１１４−Ｐ−とが任意値ｒ−∈Ｆを共有する。すなわち、共有部１１４−Ｐｉおよび共有部１１４−Ｐ−は互いに同一の任意値ｒ−を得る。共有された任意値ｒ−は記憶部１１１−Ｐｉおよび記憶部１１１−Ｐ−に格納される。任意値ｒ−の例は、擬似乱数、真正乱数、予め定められた複数の値から選択された値、入力値、別処理で得られた値などである。任意値ｒ−の共有は公知の方法によって実現できる。例えば、共有部１１４−Ｐｉから共有部１１４−Ｐ−に任意値ｒ−または任意値ｒ−を特定するための情報を送ることで、共有部１１４−Ｐｉと共有部１１４−Ｐ−との間で任意値ｒ−が共有されてもよい。逆に、共有部１１４−Ｐ−から共有部１１４−Ｐｉに任意値ｒ−または任意値ｒ−を特定するための情報を送ることで、共有部１１４−Ｐｉと共有部１１４−Ｐ−との間で任意値ｒ−が共有されてもよい。あるいは、予め共有部１１４−Ｐｉと共有部１１４−Ｐ−との間でシード値を共有しておき、共有部１１４−Ｐｉおよび共有部１１４−Ｐ−がこのシード値を用いて予め定められた処理を行うことで、共有部１１４−Ｐｉと共有部１１４−Ｐ−との間で任意値ｒ−が共有されてもよい。公知の鍵交換アルゴリズムを用いて共有部１１４−Ｐｉと共有部１１４−Ｐ−との間で任意値ｒ−が共有されてもよい（ステップＳ１２）。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００３１
【補正方法】変更
【補正の内容】
【００３１】
各秘密計算装置２１−Ｐｉの演算部２１２−Ｐｉが、記憶部２１１−Ｐｉから読み込んだ、ｎ＝０，…，Ｎ−１についてのａ＋（ｎ），ａ−（ｎ），ｂ＋（ｎ），ｂ−（ｎ），ｒ＋，ｒ−を用い、
【数２】
2019009180.tif 000017
を計算して出力する。図５の例では、秘密計算装置２１−Ｐ０の演算部２１２−Ｐ０が
【数３】
2019009180.tif 000018
を計算して出力し、秘密計算装置２１−Ｐ１の演算部２１２−Ｐ１が
【数４】
2019009180.tif 000019
を計算して出力し、秘密計算装置２１−Ｐ２の演算部２１２−Ｐ２が
【数５】
2019009180.tif 000020
を計算して出力する（ステップＳ２３）。
【国際調査報告】
2019009180.tif 000021
2019009180.tif 000022
2019009180.tif 000023
2019009180.tif 000024