Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

木状相互通信パターンにおける秘密計算プロトコル

美歩 三宅

Published Mar 1, 2023• 0 citations
OpenAlex

Abstract

近年, 情報技術はさまざまな分野で使用されている. 特に企業では, 顧客や社会のニーズに応えるために人工知能などの先端技術や自社のデータの有効活用などが重要視されている. しかし, 顧客のパーソナルデータや企業の独自技術といった機密情報の利活用には, 情報漏洩や不正利用など安全面に課題がある. そこで, データを秘匿化したまま任意の計算が可能な秘密計算(secure multi-party computation, MPC) と呼ばれる暗号技術が注目されている. MPC とは, n人の入力x1, . . . , xn を持つパーティP₁, . . . , Pn が, 入力を秘匿したまま関数f(x1, . . . , xn) を共同計算する暗号技術である. MPC に関するほとんどの先行研究では, 全てのパーティが他の全てのパーティと通信できることが前提となっている. このようなプロトコルでは, プロトコルの実行中, 全てのパーティが常にオンラインである必要があり, これは現実的な設定ではない. 例えば, 無線通信では無線機器間の物理的距離によって直接通信ができない可能性がある. そのため, パーティ間の通信が制限されたMPC を考える必要がある. Halevi, Lindell, Pinkas はこの問題に対して, 全てのパーティが同時にオンラインであるという制約をなくしたプロトコルを提案した. また, Beimel らとGoldwasser らは, 各パーティが独立してメッセージをサーバへ送信し, サーバが関数の出力を計算するプロトコルを提案した. その後, Halevi らがこれらを一般化し, 相互通信パターン(interaction pattern)という概念を導入したMPC プロトコルを提案した. 相互通信パターンは, 各パーティが送信するメッセージの依存関係を表す有向非巡回グラフによって与えられる. 彼らのプロトコルは事前計算モデルであり, パーティ間で通信を行う前に, 各パーティに相関乱数 を与えることで任意の相互通信パターンを持つMPC プロトコルを実現している. また, 彼らは対称関数に対してチェーン型の相互通信パターンを持つ情報理論的に安全なプロトコルを提案している. このプロトコルでは, 相関乱数はn(n +1)²ビット, 総通信量は高々n(n +1)²ビットである. 本研究では, 対称関数に対応したアーベルプログラムに対するチェーン型と木状相互通信パターンを持つプロトコルを提案する. 提案プロトコルでは, 相関乱数はO(n log n) ビット, 総通信量はO(n log n) ビットである. アーベルプログラムとは, 入力はアーベル群G上の要素であり, 関数f : G → {0, 1}を用いてh(x1, . . . , xn) = f(Σi∈[n] xi) で表される関数である. 入力領域をG = Zn+1 とすることで, 対称関数が表現できる. 対称関数は出力が入力のハミング重みにのみ依存する関数であり, 具体的には, OR, AND, 多数決関数などの実用的な関数がある. また, 木状相互通信パターンを持つプロトコルは有用である. 通信ネットワーク上のルーティングは木構造となっている. そのため, 木状相互通信パターンを持つプロトコルを提案することで, パーティ間の通信が任意に制限されている通信ネットワーク上でのMPC を実現可能とする.

Related papers

連続ウェーブレット変換に関連した「個数状態」とそれに関する「生成消滅演算子」について(第6回『非平衡系の統計物理』シンポジウム,研究会報告)

Fuminori Sakaguchi

作用素Q-ikP^<-1>(Q:位置作用素)、P:運動量作用素)の固有状態の波動関数が信号処理で用いられる過剰完全なコーシー・ウェーブレット関数系になることが知られているが、この関係は、ボゾン消滅作用素の固有状態がコヒーレント状態の過剰完全系となることとアナロジーをなすが、後者については、それに対応する個数状態や消滅生成関係がよく知られている。そこで、本研究では、前者におけるその対応物について考察する。前者においては、作用素Q-ikP^<-1>そのものが消滅作用素にはならず、この作用素のある種の有理関数として得られる作用素が消滅作用素となる。また、個数作用素は、単純に生成作用素と消滅作用素の積にはならず、その非線形関数となることが示される。また、個数状態の波動関数はラゲール倍多項式と密接な関係があり、エルミート多項式と関連するボゾンの場合とは異なっている。

物性研究•Jun 20, 1999•0 citations

秘密量子信号処理

勇人 西窪

量子計算は古典計算と比較して，特定の問題について優位に計算を行うことができることが様々な研究で立証されており，現在注目を集めている．中でも，量子信号処理(QSP) というLow とChuang によって提案された，1 量子ビットの回転行列の回転角を変換する技術は一際注目が集められている．この技術は元来，核磁気共鳴における信号強度を増幅するための手法であったが，量子情報科学における重要な問題の一つであるハミルトニアンシミュレーションに対して最適なアルゴリズムを提供することなども証明されており，その応用可能性について広く研究が行われている．具体的にはMaslov らによる1 量子ビットメモリ上での対称ブール関数の計算などがある．古典計算では1 ビットメモリ上で対称ブール関数を計算することは不可能であることが知られており，この結果は量子計算の優位性を示していることが分かる．この計算プロトコルにおいて，QSP は1 量子ビットメモリで計算するための核を担っている． 本研究ではQSP について暗号理論の観点からその応用可能性について検討し，その結果，新たな応用として秘密量子信号処理(PQSP) を提案する．PQSP は秘密同時通信(PSM) と呼ばれる計算モデルにおいてQSP を実行するプロトコルである．具体的には，それぞれがQSP の回転角に関する秘密の入力をもつn 人の参加者が，一人の独立した評価者を通じてQSP の出力ユニタリ行列を計算するというものである．PQSP では評価者に対して各参加者が持つ秘密の入力が，出力から洩れる情報以上に洩れることがないことを保証しつつ，参加者から評価者へ送信されるメッセージの通信量が無限の場合は完全に正しい計算結果を得ることができる．ただし，通信量を有限とするためには各参加者の送信するメッセージを有限精度で表現する必要があり，その際にはPQSP が最終的に出力する行列に誤りが発生する．よって，本研究ではこの精度と誤りのトレードオフについての評価も行う． PQSP の応用例として，先述のMaslov らによる1 量子ビットメモリ上での対称ブール関数の計算が挙げられる．本研究では，Maslov らの手法で使用されているQSP をPQSP と置換することで，1 量子ビットメモリ上で対称ブール関数を計算することができるという優位性はそのままに，PSM モデルにおいて評価者に対して出力情報以上を洩らさずに計算が可能であることを示した． また，本研究ではCosentino らによって提案された1 量子ビットプロトコルに対してPQSPで用いる秘匿化手法を適用することで，PSM モデルにおいて1 量子ビットメモリ上で任意のブール関数を計算することが可能なプロトコルである秘密1 量子ビットプログラム(P1QP)を提案する．P1QP はPQSP の応用で計算可能な対称ブール関数より大きな関数クラスに属する任意のブール関数を計算可能であることから，より一般的であるといえる．

•Mar 1, 2024•0 citations

Secure Multiparty Computation with General Interaction Patterns

Shai Halevi, Yuval Ishai, Abhishek Jain +2 more

Extended abstract of this work published in ITCS 2016 We present a unified framework for studying secure multi-party computation (MPC) with arbitrarily restricted interaction patterns. Our study generalizes both standard MPC and recent models for MPC with specific restricted interaction patterns (such as a chain or a star), which were studied by Halevi et al. (Crypto 2011), Goldwasser et al. (Eurocrypt 2014), and Beimel et al. (Crypto 2014). Since restricted interaction patterns cannot always yield full security for MPC, we start by formalizing the notion of “best possible security ” for any interaction pattern. We then obtain the following results: • Completeness theorem. We prove that the star interaction pattern is complete for the problem of MPC with general interaction patterns. • Positive results. We present both information-theoretic and computationally secure protocols for computing arbitrary functions with general interaction patterns. We also present more efficient protocols for computing symmetric functions and for computing

•Aug 10, 2016•0 citations

量子情報処理(第48回物性若手夏の学校(2003年度),講義ノート)

信之 井元

量子情報処理は量子力学と情報通信が結婚して出来たミュータントともいうべき新しい分野である。これは量子力学の原理に基づくデバイスを使って現在のコンピューターや通信の速度を上げようという話ではなく、論理演算のあり方そのものが従来のものと異なり、量子力学の原理に基づく新しい方法である。そのために従来の情報処理や通信と質的に異なる、新しい情報処理や通信を可能にすることが理論的に明らかになって来ており、その絶大な潜在能力の故に最近にわかに注目されている研究分野である。このサブゼミではこの分野について概観することを目的とする。予備知識としては線形代数のみを仮定するが、量子力学の初歩的言葉使いも多少用いる。

物性研究•Feb 20, 2004•0 citations

Secure Multiparty Computation Goes Live

Peter Bogetoft, Dan Lund Christensen, Ivan Damgård +9 more

Abstract. In this note, we report on the first large-scale and practical application of multiparty computation, which took place in January 2008. We also report on the novel cryptographic protocols that were used. 1 Introduction and History In multiparty computation (MPC), we consider a number of players P1,..., Pn, who initially each hold inputs x1,..., xn, and we then want to securely compute some function f on these inputs, where f(x1,..., xn) = (y1,..., yn), such that Pi learns yi but no other information. This should hold, even if players exhibit some amount of adversarial behavior. The goal can be accomplished by an interactive

•Jan 1, 2008•3 citations

量子情報処理(第48回物性若手夏の学校(2003年度),講義ノート)

Nobuyuki Imoto

量子情報処理は量子力学と情報通信が結婚して出来たミュータントともいうべき新しい分野である。これは量子力学の原理に基づくデバイスを使って現在のコンピューターや通信の速度を上げようという話ではなく、論理演算のあり方そのものが従来のものと異なり、量子力学の原理に基づく新しい方法である。そのために従来の情報処理や通信と質的に異なる、新しい情報処理や通信を可能にすることが理論的に明らかになって来ており、その絶大な潜在能力の故に最近にわかに注目されている研究分野である。このサブゼミではこの分野について概観することを目的とする。予備知識としては線形代数のみを仮定するが、量子力学の初歩的言葉使いも多少用いる。

•Feb 20, 2004•0 citations
近年, 情報技術はさまざまな分野で使用されている. 特に企業では, 顧客や社会のニーズに応えるために人工知能などの先端技術や自社のデータの有効活用などが重要視されている. しかし, 顧客のパーソナルデータや企業の独自技術といった機密情報の利活用には, 情報漏洩や不正利用など安全面に課題がある. そこで, データを秘匿化したまま任意の計算が可能な秘密計算(secure multi-party computation, MPC) と呼ばれる暗号技術が注目されている. MPC とは, n人の入力x1, . . . , xn を持つパーティP₁, . . . , Pn が, 入力を秘匿したまま関数f(x1, . . . , xn) を共同計算する暗号技術である. MPC に関するほとんどの先行研究では, 全てのパーティが他の全てのパーティと通信できることが前提となっている. このようなプロトコルでは, プロトコルの実行中, 全てのパーティが常にオンラインである必要があり, これは現実的な設定ではない. 例えば, 無線通信では無線機器間の物理的距離によって直接通信ができない可能性がある. そのため, パーティ間の通信が制限されたMPC を考える必要がある. Halevi, Lindell, Pinkas はこの問題に対して, 全てのパーティが同時にオンラインであるという制約をなくしたプロトコルを提案した. また, Beimel らとGoldwasser らは, 各パーティが独立してメッセージをサーバへ送信し, サーバが関数の出力を計算するプロトコルを提案した. その後, Halevi らがこれらを一般化し, 相互通信パターン(interaction pattern)という概念を導入したMPC プロトコルを提案した. 相互通信パターンは, 各パーティが送信するメッセージの依存関係を表す有向非巡回グラフによって与えられる. 彼らのプロトコルは事前計算モデルであり, パーティ間で通信を行う前に, 各パーティに相関乱数 を与えることで任意の相互通信パターンを持つMPC プロトコルを実現している. また, 彼らは対称関数に対してチェーン型の相互通信パターンを持つ情報理論的に安全なプロトコルを提案している. このプロトコルでは, 相関乱数はn(n +1)²ビット, 総通信量は高々n(n +1)²ビットである. 本研究では, 対称関数に対応したアーベルプログラムに対するチェーン型と木状相互通信パターンを持つプロトコルを提案する. 提案プロトコルでは, 相関乱数はO(n log n) ビット, 総通信量はO(n log n) ビットである. アーベルプログラムとは, 入力はアーベル群G上の要素であり, 関数f : G → {0, 1}を用いてh(x1, . . . , xn) = f(Σi∈[n] xi) で表される関数である. 入力領域をG = Zn+1 とすることで, 対称関数が表現できる. 対称関数は出力が入力のハミング重みにのみ依存する関数であり, 具体的には, OR, AND, 多数決関数などの実用的な関数がある. また, 木状相互通信パターンを持つプロトコルは有用である. 通信ネットワーク上のルーティングは木構造となっている. そのため, 木状相互通信パターンを持つプロトコルを提案することで, パーティ間の通信が任意に制限されている通信ネットワーク上でのMPC を実現可能とする.
作用素Q-ikP^<-1>(Q:位置作用素)、P:運動量作用素)の固有状態の波動関数が信号処理で用いられる過剰完全なコーシー・ウェーブレット関数系になることが知られているが、この関係は、ボゾン消滅作用素の固有状態がコヒーレント状態の過剰完全系となることとアナロジーをなすが、後者については、それに対応する個数状態や消滅生成関係がよく知られている。そこで、本研究では、前者におけるその対応物について考察する。前者においては、作用素Q-ikP^<-1>そのものが消滅作用素にはならず、この作用素のある種の有理関数として得られる作用素が消滅作用素となる。また、個数作用素は、単純に生成作用素と消滅作用素の積にはならず、その非線形関数となることが示される。また、個数状態の波動関数はラゲール倍多項式と密接な関係があり、エルミート多項式と関連するボゾンの場合とは異なっている。
量子計算は古典計算と比較して，特定の問題について優位に計算を行うことができることが様々な研究で立証されており，現在注目を集めている．中でも，量子信号処理(QSP) というLow とChuang によって提案された，1 量子ビットの回転行列の回転角を変換する技術は一際注目が集められている．この技術は元来，核磁気共鳴における信号強度を増幅するための手法であったが，量子情報科学における重要な問題の一つであるハミルトニアンシミュレーションに対して最適なアルゴリズムを提供することなども証明されており，その応用可能性について広く研究が行われている．具体的にはMaslov らによる1 量子ビットメモリ上での対称ブール関数の計算などがある．古典計算では1 ビットメモリ上で対称ブール関数を計算することは不可能であることが知られており，この結果は量子計算の優位性を示していることが分かる．この計算プロトコルにおいて，QSP は1 量子ビットメモリで計算するための核を担っている． 本研究ではQSP について暗号理論の観点からその応用可能性について検討し，その結果，新たな応用として秘密量子信号処理(PQSP) を提案する．PQSP は秘密同時通信(PSM) と呼ばれる計算モデルにおいてQSP を実行するプロトコルである．具体的には，それぞれがQSP の回転角に関する秘密の入力をもつn 人の参加者が，一人の独立した評価者を通じてQSP の出力ユニタリ行列を計算するというものである．PQSP では評価者に対して各参加者が持つ秘密の入力が，出力から洩れる情報以上に洩れることがないことを保証しつつ，参加者から評価者へ送信されるメッセージの通信量が無限の場合は完全に正しい計算結果を得ることができる．ただし，通信量を有限とするためには各参加者の送信するメッセージを有限精度で表現する必要があり，その際にはPQSP が最終的に出力する行列に誤りが発生する．よって，本研究ではこの精度と誤りのトレードオフについての評価も行う． PQSP の応用例として，先述のMaslov らによる1 量子ビットメモリ上での対称ブール関数の計算が挙げられる．本研究では，Maslov らの手法で使用されているQSP をPQSP と置換することで，1 量子ビットメモリ上で対称ブール関数を計算することができるという優位性はそのままに，PSM モデルにおいて評価者に対して出力情報以上を洩らさずに計算が可能であることを示した． また，本研究ではCosentino らによって提案された1 量子ビットプロトコルに対してPQSPで用いる秘匿化手法を適用することで，PSM モデルにおいて1 量子ビットメモリ上で任意のブール関数を計算することが可能なプロトコルである秘密1 量子ビットプログラム(P1QP)を提案する．P1QP はPQSP の応用で計算可能な対称ブール関数より大きな関数クラスに属する任意のブール関数を計算可能であることから，より一般的であるといえる．
Extended abstract of this work published in ITCS 2016 We present a unified framework for studying secure multi-party computation (MPC) with arbitrarily restricted interaction patterns. Our study generalizes both standard MPC and recent models for MPC with specific restricted interaction patterns (such as a chain or a star), which were studied by Halevi et al. (Crypto 2011), Goldwasser et al. (Eurocrypt 2014), and Beimel et al. (Crypto 2014). Since restricted interaction patterns cannot always yield full security for MPC, we start by formalizing the notion of “best possible security ” for any interaction pattern. We then obtain the following results: • Completeness theorem. We prove that the star interaction pattern is complete for the problem of MPC with general interaction patterns. • Positive results. We present both information-theoretic and computationally secure protocols for computing arbitrary functions with general interaction patterns. We also present more efficient protocols for computing symmetric functions and for computing
量子情報処理は量子力学と情報通信が結婚して出来たミュータントともいうべき新しい分野である。これは量子力学の原理に基づくデバイスを使って現在のコンピューターや通信の速度を上げようという話ではなく、論理演算のあり方そのものが従来のものと異なり、量子力学の原理に基づく新しい方法である。そのために従来の情報処理や通信と質的に異なる、新しい情報処理や通信を可能にすることが理論的に明らかになって来ており、その絶大な潜在能力の故に最近にわかに注目されている研究分野である。このサブゼミではこの分野について概観することを目的とする。予備知識としては線形代数のみを仮定するが、量子力学の初歩的言葉使いも多少用いる。
Abstract. In this note, we report on the first large-scale and practical application of multiparty computation, which took place in January 2008. We also report on the novel cryptographic protocols that were used. 1 Introduction and History In multiparty computation (MPC), we consider a number of players P1,..., Pn, who initially each hold inputs x1,..., xn, and we then want to securely compute some function f on these inputs, where f(x1,..., xn) = (y1,..., yn), such that Pi learns yi but no other information. This should hold, even if players exhibit some amount of adversarial behavior. The goal can be accomplished by an interactive
量子情報処理は量子力学と情報通信が結婚して出来たミュータントともいうべき新しい分野である。これは量子力学の原理に基づくデバイスを使って現在のコンピューターや通信の速度を上げようという話ではなく、論理演算のあり方そのものが従来のものと異なり、量子力学の原理に基づく新しい方法である。そのために従来の情報処理や通信と質的に異なる、新しい情報処理や通信を可能にすることが理論的に明らかになって来ており、その絶大な潜在能力の故に最近にわかに注目されている研究分野である。このサブゼミではこの分野について概観することを目的とする。予備知識としては線形代数のみを仮定するが、量子力学の初歩的言葉使いも多少用いる。