特許ウォッチ

公開番号2025137177
公報種別公開特許公報(A)
公開日2025-09-19
出願番号2024036229
出願日2024-03-08
発明の名称方針違反検知装置、方針違反検知方法及び方針違反検知プログラム
出願人KDDI株式会社
代理人個人
主分類G09C 1/00 20060101AFI20250911BHJP(教育;暗号方法;表示;広告;シール)
要約【課題】参加者のプライバシを損なうことなく、割当結果が平等性を満たしているか否かを判定できる方針違反検知装置を提供すること。
【解決手段】検証サーバ1は、参加者の端末それぞれから、割当結果、及び割当結果の元となった評価値を、準同型暗号方式により暗号化された状態で受信する受信部11と、割当結果が平等か否かを判定するアルゴリズムを実行し、判定結果を示す値を暗号化された状態で算出する判定部12と、算出された値を、暗号化された状態で通知する送信部13と、を備え、アルゴリズムは、複数の資源それぞれに対する評価値を示すベクトルと、割当結果における割当資源を示すワンホットベクトルとの内積により、参加者それぞれの満足度を求めるステップと、前記満足度が等しい場合を1、異なる場合を0として、参加者の全ての組み合わせの論理積を、判定結果として算出するステップと、を条件分岐せずに実行させる。
【選択図】図2
特許請求の範囲【請求項１】
参加者それぞれの複数の資源それぞれに対する評価値に基づいて割当サーバにより処理された前記複数の資源の前記参加者への割当結果を取得した前記参加者の端末それぞれから、当該割当結果、及び当該割当結果の元となった前記評価値を、準同型暗号方式により暗号化された状態で受信する受信部と、
前記準同型暗号方式により、前記割当結果が平等か否かを判定するアルゴリズムを、暗号化された前記割当結果及び前記評価値に基づいて実行し、判定結果を示す値を暗号化された状態で算出する判定部と、
前記判定部により算出された値を、暗号化された状態で前記端末へ送信し、当該値を前記端末に復号させることにより前記割当結果が平等であるか否かを通知する送信部と、を備え、
前記アルゴリズムは、
前記複数の資源それぞれに対する評価値を示すベクトルと、前記割当結果における割当資源を示すワンホットベクトルとの内積により、前記参加者それぞれの満足度を求めるステップと、
前記参加者の組み合わせについて、前記満足度が等しい場合を１、異なる場合を０として、前記参加者の全ての組み合わせの論理積を、判定結果として算出するステップと、を条件分岐せずに前記判定部に実行させる方針違反検知装置。
続きを表示（約 630 文字）【請求項２】
参加者それぞれの複数の資源それぞれに対する評価値に基づいて割当サーバにより処理された前記複数の資源の前記参加者への割当結果を取得した前記参加者の端末それぞれから、当該割当結果、及び当該割当結果の元となった前記評価値を、準同型暗号方式により暗号化された状態で受信する受信ステップと、
前記準同型暗号方式により、前記割当結果が平等か否かを判定するアルゴリズムを、暗号化された前記割当結果及び前記評価値に基づいて実行し、判定結果を示す値を暗号化された状態で算出する判定ステップと、
前記判定ステップにおいて算出された値を、暗号化された状態で前記端末へ送信し、当該値を前記端末に復号させることにより前記割当結果が平等であるか否かを通知する送信ステップと、をコンピュータが実行し、
前記判定ステップにおいて、
前記複数の資源それぞれに対する評価値を示すベクトルと、前記割当結果における割当資源を示すワンホットベクトルとの内積により、前記参加者それぞれの満足度を求めるステップと、
前記参加者の組み合わせについて、前記満足度が等しい場合を１、異なる場合を０として、前記参加者の全ての組み合わせの論理積を、判定結果として算出するステップと、を条件分岐せずに実行する方針違反検知方法。
【請求項３】
請求項１に記載の方針違反検知装置としてコンピュータを機能させるための方針違反検知プログラム。

発明の詳細な説明【技術分野】
【０００１】
本発明は、割当問題における処理結果が事前に提示された方針に違反していないかを検知する方針違反検知装置、方針違反検知方法及び方針違反検知プログラムに関する。
続きを表示（約 3,200 文字）【背景技術】
【０００２】
従来、ある種の公平な割当を実現することを目的とした、公平割当問題が研究されている（例えば、非特許文献１及び２参照）。割当問題における公平性については、比例性（proportionality）や無羨望性（envy-freeness）など、多くの概念が提案されている。一部の公平性概念については、割当処理を実行するサーバが公平であると詐称して公平でない割当結果を提示してきたとき、各参加者の好みを公開しない限り、その詐称を検知することが困難である。
【０００３】
例えば、マッチング問題に関しては、マッチングアルゴリズムが公開されている場合に、自身の好みを他の参加者に公開することなく方針違反の有無を判定する手法が特許文献１で示された。また、マッチングアルゴリズムが非公開であるが、方針違反の有無を判定するアルゴリズムが存在する場合に、自身の好みを他の参加者に公開することなく方針違反の有無を判定する手法が特許文献２で示された。
さらに、特許文献３では、安定マッチングを提供するサーバにおける方針違反の有無を、自身の好みを他の参加者に公開することなく検知する手法が示された。
【先行技術文献】
【特許文献】
【０００４】
特開２０２３－０５５５１２号公報
特願２０２２－１５２６３０号明細書
特願２０２３－１７７０３６号明細書
【非特許文献】
【０００５】
Sylvain Bouveret, Yann Chevaleyre, Nicolas Maudet, and Herve Moulin, "Fair Allocation of Indivisible Goods", 2016.
Ariel D Procaccia, "Cake Cutting Algorithms", 2016.
Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan, "(Leveled) Fully Homomorphic Encryption without Bootstrapping", ACM Transactions on Computation Theory (TOCT), 6(3):1-36, 2014.
Zvika Brakerski and Vinod Vaikuntanathan, "Efficient Fully Homomorphic Encryption from (Standard) LWE", 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pp. 97-106, 2011.
Abbas Acar, Hidayet Aksu, A Selcuk Uluagac, and Mauro Conti, "A Survey on Homomorphic Encryption Schemes: Theory and Implementation", ACM Computing Surveys (Csur), 51(4):1-35, 2018.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
従来技術では、マッチング問題について、プライバシ保護のため準同型暗号を用いて方針違反を検知する手法を提案している。
完全準同型暗号は、例えば非特許文献３のＢＧＶ方式のように、格子暗号を用いることが一般的である。格子暗号では、乗算を行う場合にノイズの増加が問題となり、ノイズ量が一定以上になると、正しく復号することができなくなる。ＢＧＶ方式は、Ｌｅｖｅｌｅｄ準同型暗号と呼ばれるカテゴリの準同型暗号で、事前に設定するパラメータによって、一つの暗号文に対し乗算を行うことが可能な回数を設定することができる。乗算を行うことが可能な回数を増やすと、一般に暗号文は大きくなり、処理時間も増加する。
また、ＢＧＶ方式での実装を提供するライブラリの一つであるＨＥＬｉｂでは、暗号化したまま様々な基本演算を行う関数が提供されている。基本演算の一つにビット列のＯＲ演算があるが、この演算は乗算と同様にノイズが増加する。
【０００７】
準同型暗号の使用を前提としてアルゴリズムを構築する場合には、これらに配慮して個別に設計する必要があるため、単純な組み合わせでは解決できない。
しかしながら、従来技術は、マッチング問題について、準同型暗号を用いて方針違反を検知する手法のため、これを割当問題に適用することはできなかった。
【０００８】
本発明は、割当問題における平等性（equitability）に注目し、参加者のプライバシを損なうことなく、割当結果が平等性を満たしているか否かを判定できる方針違反検知装置、方針違反検知方法及び方針違反検知プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明に係る方針違反検知装置は、参加者それぞれの複数の資源それぞれに対する評価値に基づいて割当サーバにより処理された前記複数の資源の前記参加者への割当結果を取得した前記参加者の端末それぞれから、当該割当結果、及び当該割当結果の元となった前記評価値を、準同型暗号方式により暗号化された状態で受信する受信部と、前記準同型暗号方式により、前記割当結果が平等か否かを判定するアルゴリズムを、暗号化された前記割当結果及び前記評価値に基づいて実行し、判定結果を示す値を暗号化された状態で算出する判定部と、前記判定部により算出された値を、暗号化された状態で前記端末へ送信し、当該値を前記端末に復号させることにより前記割当結果が平等であるか否かを通知する送信部と、を備え、前記アルゴリズムは、前記複数の資源それぞれに対する評価値を示すベクトルと、前記割当結果における割当資源を示すワンホットベクトルとの内積により、前記参加者それぞれの満足度を求めるステップと、前記参加者の組み合わせについて、前記満足度が等しい場合を１、異なる場合を０として、前記参加者の全ての組み合わせの論理積を、判定結果として算出するステップと、を条件分岐せずに前記判定部に実行させる。
【００１０】
本発明に係る方針違反検知方法は、参加者それぞれの複数の資源それぞれに対する評価値に基づいて割当サーバにより処理された前記複数の資源の前記参加者への割当結果を取得した前記参加者の端末それぞれから、当該割当結果、及び当該割当結果の元となった前記評価値を、準同型暗号方式により暗号化された状態で受信する受信ステップと、前記準同型暗号方式により、前記割当結果が平等か否かを判定するアルゴリズムを、暗号化された前記割当結果及び前記評価値に基づいて実行し、判定結果を示す値を暗号化された状態で算出する判定ステップと、前記判定ステップにおいて算出された値を、暗号化された状態で前記端末へ送信し、当該値を前記端末に復号させることにより前記割当結果が平等であるか否かを通知する送信ステップと、をコンピュータが実行し、前記判定ステップにおいて、前記複数の資源それぞれに対する評価値を示すベクトルと、前記割当結果における割当資源を示すワンホットベクトルとの内積により、前記参加者それぞれの満足度を求めるステップと、前記参加者の組み合わせについて、前記満足度が等しい場合を１、異なる場合を０として、前記参加者の全ての組み合わせの論理積を、判定結果として算出するステップと、を条件分岐せずに実行する。
（【００１１】以降は省略されています）

関連特許