特許ウォッチ

公開番号2025047194
公報種別公開特許公報(A)
公開日2025-04-03
出願番号2023155536
出願日2023-09-21
発明の名称安定マッチング問題の結果を検証するためのプロトコルに則った計算を行う検証装置、検証方法、検証プログラム及び検証システム
出願人KDDI株式会社
代理人個人,個人
主分類G09C 1/00 20060101AFI20250326BHJP(教育;暗号方法;表示;広告;シール)
要約【課題】悪意のある敵対者の設定における安定マッチング問題の効率的な検証プロトコル及び当該検証プロトコルに則った計算を行う検証装置、検証方法及び検証プログラムを提供すること。
【解決手段】
複数のクライアントにおける安定マッチング問題の結果を検証するためのプロトコルに則った計算を行う検証装置であって、前記プロトコルは、前記複数のクライアントと前記検証装置の間で実行される手順を定め、悪意のある敵対者の設定の場合でも機能し、二つの条件付き秘密開示(CDS)スキームから構成される。
【選択図】図1
特許請求の範囲【請求項１】
複数のクライアントにおける安定マッチング問題の結果を検証するためのプロトコルに則った計算を行う検証装置であって、
前記プロトコルは、
前記複数のクライアントと前記検証装置の間で実行される手順を定め、
悪意のある敵対者の設定の場合でも機能し、
二つの条件付き秘密開示（ＣＤＳ）スキームから構成される、
検証装置。
続きを表示（約 1,100 文字）【請求項２】
前記複数のクライアントは、
メンバ数が同じである集合Ａ又は集合Ｂのいずれかのメンバであり、
集合Ａのメンバである場合は集合Ｂの各メンバに対する選好順序を持ち、集合Ｂのメンバである場合は集合Ａの各メンバに対する選好順序を持ち、
前記検証装置に対し、前記選好順序及びマッチングペアの相手を示す情報、並びに、共通の秘密及びランダムネスの符号化出力を送信する、
請求項１に記載の検証装置。
【請求項３】
前記二つの条件付き秘密開示（ＣＤＳ）スキームは、不安定マッチングのためのＣＤＳスキーム及び安定マッチングためのＣＤＳスキームであり、
前記検証装置は、
前記不安定マッチングのためのＣＤＳスキームにおける手順の実行時には、前記複数のクライアント間のマッチングが不安定である場合に限り、前記共通の秘密に等しい値を出力し、
前記安定マッチングのためのＣＤＳスキームにおける手順の実行時には、前記複数のクライアント間のマッチングが安定である場合に限り、前記共通の秘密に等しい値を出力する、
請求項２に記載の検証装置。
【請求項４】
複数のクライアントにおける安定マッチング問題の結果を検証するためのプロトコルに則った計算を検証装置に行わせる検証方法であって、
前記プロトコルは、
前記複数のクライアントと前記検証装置の間で実行される手順を定め、
悪意のある敵対者の設定の場合でも機能し、
二つの条件付き秘密開示（ＣＤＳ）スキームから構成される、
検証方法。
【請求項５】
複数のクライアントにおける安定マッチング問題の結果を検証するためのプロトコルに則った計算をコンピュータに行わせる検証プログラムであって、
前記プロトコルは、
前記複数のクライアントと前記コンピュータの間で実行される手順を定め、
悪意のある敵対者の設定の場合でも機能し、
二つの条件付き秘密開示（ＣＤＳ）スキームから構成される、
検証プログラム。
【請求項６】
複数のクライアントにおける安定マッチング問題の結果を検証するためのプロトコルに則った処理と計算を行う検証システムであって、
前記検証システムは、前記複数のクライアントが操作する複数のクライアント端末と検証サーバとを備え、
前記プロトコルは、
前記複数のクライアント端末と前記検証サーバの間で実行される手順を定め、
悪意のある敵対者の設定の場合でも機能し、
二つの条件付き秘密開示（ＣＤＳ）スキームから構成される、
検証システム。

発明の詳細な説明【技術分野】
【０００１】
本発明は、安定マッチング問題の分野に関し、特に安定マッチング問題の結果を検証するためのプロトコルに則った計算を行う検証装置、検証方法、検証プログラム及び検証システムの分野に関する。
続きを表示（約 2,000 文字）【背景技術】
【０００２】
安定マッチング問題のために、集合Ａ（Ａ＝｛a
１
，…，ａ
ｎ
｝）と集合Ｂ（Ｂ＝｛ｂ
１
，…，ｂ
ｎ
｝）の二つの集合を設定する。集合Ａの各メンバａ
ｉ
は選好順序（ｂ
ｉ＿１
，…，ｂ
ｉ＿ｎ
）を持ち、集合Ｂの各メンバｂ
ｊ
は選好順序（ａ
ｊ＿１
，…，ａ
ｊ＿ｎ
）を持つ。選好順序（「プリファレンス」ともいう。）は、相手側集合のメンバに対する好みの順を表す。すなわち、選好順序で先に現れるメンバは、後に現れるメンバよりも好まれる。
【０００３】
マッチングＭは、集合Ａと集合Ｂの間の双射影である。（ａ
ｉ
，ｂ
ｊ
）がマッチングＭのペアである場合、Ｍ（ａ
ｉ
）＝ｂ
ｊ
、Ｍ（ｂ
ｊ
）＝ａ
ｉ
と記述する。安定マッチング問題における目標は、以下の定義に従って、集合Ａと集合Ｂの間の安定マッチングを見つけることである。
【０００４】
定義１（ブロッキングペア）：
集合ＡとＢ、集合ＡとＢにおける各メンバの選好順序、及びマッチングＭが与えられたとき、Ａ×Ｂにおけるペア（ａ
ｉ
，ｂ
ｊ
）は、以下の二つの条件を満たす場合にブロッキングペア（「不安定対」ともいう。）となる。
（１）ａ
ｉ
はＭ（ａ
ｉ
）よりもｂ
ｊ
を好む。
（２）ｂ
ｊ
はＭ（ｂ
ｊ
）よりもａ
ｉ
を好む。
【０００５】
定義２（安定マッチング）：
集合ＡとＢ、及び集合ＡとＢにおける各メンバの選好順序が与えられたとき、ブロッキングペアがない場合、マッチングＭは安定（安定マッチング）である。
【０００６】
非特許文献１は、安定マッチング問題に対して以下のプロトコルを提案した。２ｎ人のクライアントがおり、それぞれが集合Ａ又は集合Ｂのメンバを表している。各クライアントは、自身の選好順序を平文で計算サーバに送信する。計算サーバは、安定マッチングを計算し、割り当てられたペアを各クライアントに返す。
【０００７】
計算サーバによって計算されたマッチングが安定していることを確認するために、クライアントは検証プロトコルを実行する。各クライアントは自分の選好順序と割り当てられたペアを暗号文として検証サーバに送信する。検証サーバは完全準同型暗号を用いて暗号文を計算し、検証結果を各クライアントに返す。
【先行技術文献】
【非特許文献】
【０００８】
Toru Nakamura, Hiroki Okada, Kazuhide Fukushima and Takamasa Isohara, “Achieving Private Verification in Multi-stakeholder Environment and Application to Stable Matching”, Proceedings of the 25th International Conference on Enterprise Information Systems (ICEIS 2023), Volume 1, pp. 768-775
【０００９】
Kittiphop Phalakarn, Nuttapong Attrapadung and Kanta Matsuura, “Efficient Oblivious Evaluation Protocol and Conditional Disclosure of Secrets for DFA”, Proceedings of the International Conference on Applied Cryptography and Network Security (2022), pp. 605-625
【００１０】
Adi Shamir, “How to Share a Secret”, Communications of the ACM, November 1979, Volume 22, Number 11, pp. 612-613
【発明の概要】
【発明が解決しようとする課題】
（【００１１】以降は省略されています）

関連特許