Search

JP-2026077533-A - 再帰的サムチェックプロトコルを活用した多項式コミットメント方法およびこれを遂行するシステム

JP2026077533AJP 2026077533 AJP2026077533 AJP 2026077533AJP-2026077533-A

Abstract

【課題】再帰的サムチェックプロトコルを活用した多項式コミットメント方法並びにテンソルコード及び多重線形拡張を活用した多項式コミットメント方法を提供する。 【解決手段】本方法は、多項式の係数に対応する第１ターゲット行列に対して第１検証を遂行する段階、前記第１検証で活用した行列のうち少なくとも一部を抽出することによって第２ターゲット行列を獲得する段階、前記第２ターゲット行列に対して第２検証を遂行する段階、前記第２ターゲット行列を活用してコミット値を生成する段階及び前記多項式に対するゼロ知識証明のために前記コミット値を伝送する段階を含む。 【選択図】図４

Inventors

  • オ、ヒョノク

Assignees

  • ジクリプト インコーポレイテッド

Dates

Publication Date
20260513
Application Date
20241223
Priority Date
20241025

Claims (11)

  1. 少なくとも一つのプロセッサによって遂行される再帰的サムチェックプロトコルを活用した多項式コミットメント方法において、 多項式の係数に対応する第１ターゲット行列に対して第１検証を遂行する段階； 前記第１検証で活用した行列のうち少なくとも一部を抽出することによって第２ターゲット行列を獲得する段階； 前記第２ターゲット行列に対して第２検証を遂行する段階； 前記第２ターゲット行列を活用してコミット値を生成する段階；および 前記多項式に対するゼロ知識証明のために前記コミット値を伝送する段階；を含む、多項式コミットメント方法。
  2. 前記第１検証を遂行する段階は、 前記第１ターゲット行列に対するエンコーディングを遂行することによって第１エンコーディング行列を生成する段階； 前記第１ターゲット行列をフォールディングすることによって第１フォールディングターゲット行列を生成する段階； 前記第１エンコーディング行列をフォールディングすることによって第１フォールディングエンコーディング行列を生成する段階；および 前記第１フォールディングターゲット行列をエンコーディングした値と前記第１フォールディングエンコーディング行列を比較することによって前記第１ターゲット行列に対する検証を遂行する段階；を含む、請求項１に記載の多項式コミットメント方法。
  3. 前記第１フォールディングエンコーディング行列を生成する段階は、 前記第１エンコーディング行列のうち複数の第１単位エンコーディング行列を抽出する段階；および 前記複数の第１単位エンコーディング行列に対するフォールディングを通じて前記第１フォールディングエンコーディング行列のうち少なくとも一部を生成する段階；を含む、請求項２に記載の多項式コミットメント方法。
  4. 前記第１ターゲット行列に対する検証を遂行する段階は、 前記第１ターゲット行列に含まれた少なくとも一つの行列をエンコーディングすることによって複数の第１単位エンコーディングフォールディングターゲット行列を生成する段階； 前記複数の第１単位エンコーディングフォールディングターゲット行列と、前記第１フォールディングエンコーディング行列のうち少なくとも一部を比較する段階； 前記比較結果が一致すれば前記検証を通過したと判断する段階；を含む、請求項３に記載の多項式コミットメント方法。
  5. 前記第１エンコーディング行列を生成する段階は、 前記第１ターゲット行列に第１ランダム行列をかけることによって前記第１エンコーディング行列を生成する段階を含み、 前記第１フォールディングターゲット行列を生成する段階は、 前記第１ターゲット行列に検証ターゲットとなるターゲットポイント行列をかけることによって前記第１フォールディングターゲット行列を生成する段階を含む、請求項３に記載の多項式コミットメント方法。
  6. 前記第２ターゲット行列を獲得する段階は、 前記第１ランダム行列のうち前記複数の第１単位エンコーディング行列に対応する複数の第１単位ランダム行列を獲得する段階； 前記第１ターゲット行列に検証ターゲットではなくランダムポイント行列をかけることによって第１フォールディングサブ行列を獲得する段階；および 前記複数の第１単位エンコーディング行列、前記複数の第１単位ランダム行列、前記第１フォールディングターゲット行列および前記第１フォールディングサブ行列を利用して前記第２ターゲット行列を生成する段階；を含む、請求項５に記載の多項式コミットメント方法。
  7. 前記第２検証で活用した行列のうち少なくとも一部を抽出することによって第Ｎ（Ｎは３以上の自然数）ターゲット行列を獲得する段階； 前記第Ｎターゲット行列に対して、テンソルコードを活用した第Ｎ検証を遂行する段階； 前記第Ｎ検証で活用した行列のうち少なくとも一部を抽出して第Ｎ＋１ターゲット行列を獲得する段階； 前記第Ｎ＋１ターゲット行列の大きさが予め決定された値未満であるかを確認する段階； 前記第Ｎ＋１ターゲット行列の大きさが前記予め決定された値未満でない場合、第Ｎ＋１検証を遂行する段階；および 前記第Ｎ＋１ターゲット行列の大きさが前記予め決定された値以下である場合、前記第Ｎ＋１ターゲット行列を活用して前記コミット値を生成する段階；をさらに含む、請求項１に記載の多項式コミットメント方法。
  8. 前記第２検証を遂行する段階は、 前記第２ターゲット行列および第２ランダム行列を利用して第２エンコーディング行列を生成する段階； 前記第２ターゲット行列およびターゲットポイント行列を利用して第２フォールディングターゲット行列を生成する段階； 前記第２エンコーディング行列のうち複数の第２単位エンコーディング行列をフォールディングし、前記第２フォールディングターゲット行列と比較することによって前記第２ターゲット行列に対する検証を遂行する段階；を含む、請求項７に記載の多項式コミットメント方法。
  9. 前記第Ｎ＋１ターゲット行列を獲得する段階は、 前記第２ランダム行列のうち前記複数の第２単位エンコーディング行列に対応する複数の第２単位ランダム行列を獲得する段階； 前記複数の第２単位エンコーディング行列、前記複数の第２単位ランダム行列および前記第２フォールディングターゲット行列を利用して前記第Ｎ＋１ターゲット行列を生成する段階；を含む、請求項８に記載の多項式コミットメント方法。
  10. 前記第Ｎ＋１ターゲット行列を活用して前記コミット値を生成する段階は、 前記第Ｎ＋１ターゲット行列の複数の要素値をマークルハッシュツリー（Ｍｅｒｋｅｌ Ｈａｓｈ Ｔｒｅｅ）に適用することによって前記コミット値を生成する段階；を含む、請求項７に記載の多項式コミットメント方法。
  11. 多項式コミットメント方法を保存するコンピュータで読み取り可能な記録媒体において、 前記多項式コミットメント方法は、 多項式の係数に対応する第１ターゲット行列に対して第１検証を遂行する段階； 前記第１検証で活用した行列のうち少なくとも一部を抽出することによって第２ターゲット行列を獲得する段階； 前記第２ターゲット行列に対して第２検証を遂行する段階； 前記第２検証で活用した行列のうち少なくとも一部を活用してコミット値を生成する段階；および ゼロ知識証明方法を利用して前記コミット値を証明する段階；を含むことを特徴とする、コンピュータで読み取り可能な記録媒体。

Description

本発明は再帰的サムチェックプロトコルを活用した多項式コミットメント方法およびこれを遂行するシステムに関する。 多項式コミットメント方法（Ｐｏｌｙｎｏｍｉａｌ Ｃｏｍｍｉｔｍｅｎｔ Ｓｃｈｅｍｅ、ＰＣＳ）は計算の完全性を証明し検証するのに使われる暗号学的技法である。主にブロックチェーンおよびゼロ知識証明（ＺＫ Ｐｒｏｏｆ）システム、暗号通貨、ｚｋ－ｒｏｌｌｕｐなどの環境でデータの信頼性を保障するのに活用されるが、この方法は特定多項式の評価結果を効率的に約定（ｃｏｍｍｉｔ）し検証できるプロトコルを提供する。 多項式コミットメント方法はコミット（Ｃｏｍｍｉｔ）－評価／証明－検証段階からなるが、約定段階で、証明者（Ｐｒｏｖｅｒ）は特定多項式ｆ（ｘ）と該当多項式の評価値ｆ（ａ）を検証者（Ｖｅｒｉｆｉｅｒ）に証明しようとする。このために証明者は多項式ｆ（ｘ）を約定（ｃｏｍｍｉｔ）する。約定は多項式の情報が含まれた暗号化された値であって、後ほど評価値を検証する時に使うことができる。評価／証明段階で、証明者は多項式のターゲットポイントａでの評価結果ｆ（ａ）を計算し、この値を検証者に提供する。証明者はまた検証者がこの評価値が正しいかどうかを確認できるように評価証明（ｅｖａｌｕａｔｉｏｎ ｐｒｏｏｆ）またはコミット値も提供する。検証段階で、検証者は証明者が提供した評価証明を約定された多項式と比較してｆ（ａ）が正確であるかを確認する。この時、検証者は多項式全体を知る必要はなく、約定された情報と証明だけで評価結果が正しいかどうかを判断することができる。 このような多項式コミットメント方法は、多項式の次数（Ｎ）が大きくなるにつれて検証および証明するための時間が長くかかる問題点が発生した。これに伴い、多項式コミットメント方法において検証および証明のための時間を減らすための努力が続いてきた。 本開示の例示的な実施例に係るシステムを示すブロック図である。本開示の例示的な実施例に係る多項式コミットメント方法を示すフローチャートである。本開示の例示的な実施例に係る多項式コミットメント方法を示すコードである。本開示の例示的な実施例に係る多項式コミットメント方法を示すコードである。本開示の例示的な実施例に係る多項式コミットメント方法を示すコードである。本開示の例示的な実施例に係る多項式コミットメント方法を示すフローチャートである。本開示の例示的な実施例に係る多項式コミットメント方法を示すブロック図である。本開示の例示的な実施例に係る多項式コミットメント方法を示すブロック図である。本開示の例示的な実施例に係る多項式コミットメント方法を示すブロック図である。本開示の例示的な実施例に係る多項式コミットメント方法を示すブロック図である。本開示の例示的な実施例に係るコンピューティングシステムを示すブロック図である。 以下、添付された図面を参照して本発明の好ましい実施例を詳細に説明する。本発明の利点および特徴、そしてそれらを達成する方法は添付される図面と共に詳細に後述されている実施例を参照すれば明確となるであろう。しかし、本発明の技術的思想は以下の実施例に限定されるものではなく互いに異なる多様な形態で具現され得、ただし以下の実施例は本発明の技術的思想を完全なものとし、本発明が属する技術分野で通常の知識を有する者に本発明の範疇を完全に知らせるために提供されるものであり、本発明の技術的思想は請求項の範疇によって定義されるのみである。 各図面の構成要素に参照符号を付加するにおいて、同一の構成要素に対してはたとえ他の図面上に表示されてもできるだけ同一の符号を有するようにしていることに留意しなければならない。また、本発明の説明において、関連した公知の構成または機能に対する具体的な説明が本発明の要旨を曖昧にさせ得る恐れがあると判断される場合にはその詳細な説明は省略する。 特に定義されない限り、本明細書で使われるすべての用語（技術および科学的用語を含む）は本発明が属する技術分野で通常の知識を有する者に共通して理解され得る意味で使われ得る。また、一般的に使われる辞書に定義されている用語は明白に特に定義されていない限り、理想的にまたは過度に解釈されない。本明細書で使われた用語は実施例を説明するためのものであり本発明を制限しようとするものではない。本明細書で、単数型は文面で特に言及しない限り複数型も含む。 また、本発明の構成要素を説明するにあたって、第１、第２、Ａ、Ｂ、（ａ）、（ｂ）等の用語を使うことができる。このような用語はその構成要素を他の構成要素と区別するためのものに過ぎず、その用語によって該当構成要素の本質や順番または順序などが限定されない。或る構成要素が他の構成要素に「連結」、「結合」または「接続」されると記載された場合、その構成要素はその他の構成要素に直接的に連結されたりまたは接続され得るが、各構成要素の間にさらに他の構成要素が「連結」、「結合」または「接続」され得ると理解されるべきである。 本発明で使われる「含む（ｃｏｍｐｒｉｓｅｓ）」および／または「含む（ｃｏｍｐｒｉｓｉｎｇ）」は言及された構成要素、段階、動作および／または素子は一つ以上の他の構成要素、段階、動作および／または素子の存在または追加を排除しない。 いずれか一つの実施例に含まれた構成要素と、共通の機能を含む構成要素は、他の実施例で同じ名称を用いて説明され得る。反対の記載がない限り、いずれか一つの実施例に記載された説明は他の実施例にも適用され得、重複する範囲または当該技術分野に属した通常の技術者が自明に理解できる範囲内で具体的な説明は省略され得る。 以下、本発明のいくつかの実施例について、添付された図面により詳細に説明する。 以下、本発明の好ましい実施例および添付した図面を参照して本発明について詳細に説明する。 図１は、本開示の例示的な実施例に係るシステムを示すブロック図である。 図１を参照すると、システム１０は多項式コミットメント方法を遂行するシステムであって、システム１０に含まれた構成は複数の端末で構成され得る。一例示において、証明者１００および検証者２００はそれぞれ少なくとも一つの端末で構成され得、少なくとも一つの端末はセルラーフォン（Ｃｅｌｌｕｌａｒ Ｐｈｏｎｅ）、スマートフォン（Ｓｍａｒｔ ｐｈｏｎｅ）、ラップトップ（Ｌａｐｔｏｐ）、ＰＣ（Ｐｅｒｓｏｎａｌ Ｃｏｍｐｕｔｅｒ）、ナビゲーション、ＰＣＳ（Ｐｅｒｓｏｎａｌ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｓｙｓｔｅｍ）、ＧＳＭ（Ｇｌｏｂａｌ Ｓｙｓｔｅｍ ｆｏｒ Ｍｏｂｉｌｅ ｃｏｍｍｕｎｉｃａｔｉｏｎｓ）、ＰＤＣ（Ｐｅｒｓｏｎａｌ Ｄｉｇｉｔａｌ Ｃｅｌｌｕｌａｒ）、ＰＨＳ（Ｐｅｒｓｏｎａｌ Ｈａｎｄｙｐｈｏｎｅ Ｓｙｓｔｅｍ）、ＰＤＡ（Ｐｅｒｓｏｎａｌ Ｄｉｇｉｔａｌ Ａｓｓｉｓｔａｎｔ）、ＩＭＴ（Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｍｏｂｉｌｅ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎ）－２０００、ＣＤＭＡ（Ｃｏｄｅ Ｄｉｖｉｓｉｏｎ Ｍｕｌｔｉｐｌｅ Ａｃｃｅｓｓ）－２０００、Ｗ－ＣＤＭＡ（Ｗ－Ｃｏｄｅ Ｄｉｖｉｓｉｏｎ Ｍｕｌｔｉｐｌｅ Ａｃｃｅｓｓ）、Ｗｉｂｒｏ（Ｗｉｒｅｌｅｓｓ Ｂｒｏａｄｂａｎｄ Ｉｎｔｅｒｎｅｔ）端末、スマートパッド（Ｓｍａｒｔｐａｄ）、タブレットＰＣ（Ｔａｂｌｅｔ ＰＣ）などの通信可能な各種端末装置を含むことができる。さらに他の例示において、証明者１００および検証者２００それぞれはサーバーで具現され得る。 証明者１００および検証者２００は有線／無線で互いに通信可能なネットワークを通じて連結され得、有線で連結される場合に、ネットワークはシリアル方式を利用でき、無線で連結される場合に、ネットワークは無線通信網を利用して通信することができる。無線通信網には近距離通信網（ＬＡＮ：Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）、広域通信網（ＷＡＮ：Ｗｉｄｅ Ａｒｅａ Ｎｅｔｗｏｒｋ）、インターネット（ＷＷＷ：Ｗｏｒｌｄ Ｗｉｄｅ Ｗｅｂ）、有線／無線データ通信網、電話網、有線／無線テレビ通信網、３Ｇ、４Ｇ、５Ｇ、３ＧＰＰ（登録商標）（３ｒｄ Ｇｅｎｅｒａｔｉｏｎ Ｐａｒｔｎｅｒｓｈｉｐ Ｐｒｏｊｅｃｔ）、５ＧＰＰ（５ｔｈ Ｇｅｎｅｒａｔｉｏｎ Ｐａｒｔｎｅｒｓｈｉｐ Ｐｒｏｊｅｃｔ）、ＬＴＥ（Ｌｏｎｇ Ｔｅｒｍ Ｅｖｏｌｕｔｉｏｎ）、ＷＩＭＡＸ（Ｗｏｒｌｄ Ｉｎｔｅｒｏｐｅｒａｂｉｌｉｔｙ ｆｏｒ Ｍｉｃｒｏｗａｖｅ Ａｃｃｅｓｓ）、ワイファイ（Ｗｉ－Ｆｉ）、インターネット（Ｉｎｔｅｒｎｅｔ）、ＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）、Ｗｉｒｅｌｅｓｓ ＬＡＮ（Ｗｉｒｅｌｅｓｓ Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ Ａｒｅａ Ｎｅｔｗｏｒｋ）、ＰＡＮ（Ｐｅｒｓｏｎａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）、ＲＦ（Ｒａｄｉｏ Ｆｒｅｑｕｅｎｃｙ）、ブルートゥース（登録商標）（Ｂｌｕｅｔｏｏｔｈ）ネットワーク、ＮＦＣ（Ｎｅａｒ－Ｆｉｅｌｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎ）ネットワーク、衛星放送ネットワーク、アナログ放送ネットワーク、ＤＭＢ（Ｄｉｇｉｔａｌ Ｍｕｌｔｉｍｅｄｉａ Ｂｒｏａｄｃａｓｔｉｎｇ）ネットワーク、ブロックチェーンネットワーク（Ｂｌｏｃｋｃｈａｉｎ Ｎｅｔｗｏｒｋ）等が含まれるがこれに限定されはしない。 本明細書でシステム１０およびシステム１０に含まれた各構成の動作は各構成に含まれた保存装置に保存された少なくとも一つの命令語を含むコンピュータプログラムに基づいて、各構成に含まれたプロセッサが遂行する動作を意味し得、前記保存装置は不揮発性メモリ、揮発性メモリ、フラッシュメモリ（ｆｌａｓｈ－ｍｅｍｏｒｙ）、ハードディスクドライブ（ＨＤＤ）またはソリッドステートドライブ（ＳＳＤ）等を含むことができる。また、前記プロセッサはＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）、ＧＰＵ（Ｇｒａｐｈｉｃ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）、ＮＰＵ（Ｎｅｕｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）、ラム（ＲＡＭ）、ロム（ＲＯＭ）、システムバスおよびアプリケーションプロセッサのうち少なくとも一つを含むことができる。 証明者１００は多項式に対する証明を遂行し、証明値に該当するコミット値ｃｍを生成することができる。検証者２００はゼロ知識証明アルゴリズムを利用してコミット値ｃｍを検証することによって、多項式に対する内容を公開せずに証明者１００が多項式を知っていることを検証することができる。 本開示の一実施例によると、証明者１００がコミット値ｃｍを生成する時にターゲット行列に対する縮小を遂行することによってターゲット行列のサイズを減らすことができ、結果的にコミット値ｃｍに対する証明および検証に所要する時間と容量が画期的に減少され得る。 図２は本開示の例示的な実施例に係る多項式コミットメント方法を示すフローチャートであり、図３ａ～図３ｃは本開示の例示的な実施例に係る多項式コミットメント方法を示すコードである。 図２を参照すると、本発明に係る多項式コミットメント方法はマークルハッシュツリーコミットメントと多重線形拡張を使って計算のセキュリティー性と効率性を保障する多項式コミットメントプロトコルに関するもので、サムチェックプロトコルを再帰的に活用して検証者の複雑度を低くし、証明の大きさをログスケール水準に減少させることを目標とする。プロトコルは大きく設定段階（Ｓ１０）、証明－検証段階（Ｓ２０）を含むことができ、証明－検証段階（Ｓ２０）は評価段階（Ｓ２１）、縮小段階（Ｓ２２）を含むことができる。 図３ａを参照すると、設定段階（Ｓ１０）は全体プロトコルのために必要な共通媒介変数と初期コミットを生成することができる。具体的