(57)【要約】【課題】アップデート可能なランダム関数を提供すること。【解決手段】方法は、セットアップ関数により、アップデート可能なランダム関数に関連付けられる公開パラメータを生成するステップを含み得る。前記方法は、初期化関数により、前記セットアップ関数により生成された前記公開パラメータに少なくとも部分的に基づいて、第１のランダム要素及び第１の状態を生成するステップをさらに含み得る。前記方法は、アップデート関数により、前記セットアップ関数により生成された前記公開パラメータに少なくとも部分的に基づいて、第３のランダム要素及び第２の状態を生成するステップをさらに含み得る。前記アップデート関数の入力は、前記初期化関数により生成された前記第１の状態及び第２のランダム要素を含み得る。【選択図】図２
2018156079.tif 000002
【特許請求の範囲】
【請求項１】
セットアップ関数により、アップデート可能なランダム関数に関連付けられる公開パラメータを生成するステップと、
初期化関数により、前記セットアップ関数により生成された前記公開パラメータに少なくとも部分的に基づいて、第１のランダム要素及び第１の状態を生成するステップと、
アップデート関数により、前記セットアップ関数により生成された前記公開パラメータに少なくとも部分的に基づいて、第３のランダム要素及び第２の状態を生成するステップであって、前記アップデート関数の入力は、前記初期化関数により生成された前記第１の状態及び第２のランダム要素を含む、ステップと、
を含む方法。
【請求項２】
前記公開パラメータを生成することは、前記セットアップ関数により、２つの入力文字列に少なくとも部分的に基づいて、ランダム文字列出力を生成するよう構成されるランダムオラクルを生成することを含む、請求項１に記載の方法。
【請求項３】
前記初期化関数により、第１のランダム文字列を生成し、前記第１のランダム文字列の値を、前記第１のランダム要素及び前記第１の状態に割り当てるステップ
をさらに含む、請求項２に記載の方法。
【請求項４】
前記アップデート関数により、第２のランダム文字列を生成するステップと、
前記第２のランダム文字列の値を、前記第２のランダム要素に割り当てるステップと、
前記ランダムオラクルの出力を、前記第３のランダム要素及び前記第２の状態に割り当てるステップであって、前記ランダムオラクルの入力は、前記初期化関数により生成された前記第１の状態及び前記第２のランダム要素を含む、ステップと、
をさらに含む、請求項３に記載の方法。
【請求項５】
前記公開パラメータを生成することは、前記セットアップ関数により、第１の群に関連付けられる第１の生成元、第２の群に関連付けられる第２の生成元、第３の群に関連付けられる第３の生成元、前記第１の生成元及び前記第２の生成元の入力に少なくとも部分的に基づいて、前記第３のランダム要素を出力するよう構成される双線形写像関数、及び、前記第３の生成元の入力に少なくとも部分的に基づいて、前記第１の生成元を出力するよう構成される全単射写像関数を生成することを含む、請求項１に記載の方法。
【請求項６】
前記初期化関数により、前記第１の群に関連付けられる第１のランダム群要素を選択するステップと、
前記第１のランダム群要素の値を、前記第１の状態及び前記第１のランダム要素に割り当てるステップと、
をさらに含む、請求項５に記載の方法。
【請求項７】
前記アップデート関数により、前記第２の群に関連付けられる第２のランダム群要素を選択するステップと、
前記アップデート関数により、前記全単射写像関数の出力の値を、第２の状態及び第２のランダム要素に割り当てるステップであって、前記全単射写像関数は、前記双線形写像関数の出力を入力として含み、前記双線形写像関数は、前記第１の状態及び前記第２のランダム群要素を入力として含む、ステップと、
をさらに含む、請求項６に記載の方法。
【請求項８】
アップデート可能なランダム関数の動作をシステムに実行させるよう構成されているコンピュータ読み取り可能な媒体であって、前記動作は、
セットアップ関数により、アップデート可能なランダム関数に関連付けられる公開パラメータを生成することと、
初期化関数により、前記セットアップ関数により生成された前記公開パラメータに少なくとも部分的に基づいて、第１のランダム要素及び第１の状態を生成することと、
アップデート関数により、前記セットアップ関数により生成された前記公開パラメータに少なくとも部分的に基づいて、第３のランダム要素及び第２の状態を生成することであって、前記アップデート関数の入力は、前記初期化関数により生成された前記第１の状態及び第２のランダム要素を含む、生成することと、
を含む、コンピュータ読み取り可能な媒体。
【請求項９】
前記公開パラメータを生成することは、前記セットアップ関数により、２つの入力文字列に少なくとも部分的に基づいて、ランダム文字列出力を生成するよう構成されるランダムオラクルを生成することを含む、請求項８に記載のコンピュータ読み取り可能な媒体。
【請求項１０】
前記動作は、
前記初期化関数により、第１のランダム文字列を生成し、前記第１のランダム文字列の値を、前記第１のランダム要素及び前記第１の状態に割り当てること
をさらに含む、請求項９に記載のコンピュータ読み取り可能な媒体。
【請求項１１】
前記動作は、
前記アップデート関数により、第２のランダム文字列を生成することと、
前記第２のランダム文字列の値を、前記第２のランダム要素に割り当てることと、
前記ランダムオラクルの出力を、前記第３のランダム要素及び前記第２の状態に割り当てることであって、前記ランダムオラクルの入力は、前記初期化関数により生成された前記第１の状態及び前記第２のランダム要素を含む、割り当てることと、
をさらに含む、請求項１０に記載のコンピュータ読み取り可能な媒体。
【請求項１２】
前記公開パラメータを生成することは、前記セットアップ関数により、第１の群に関連付けられる第１の生成元、第２の群に関連付けられる第２の生成元、第３の群に関連付けられる第３の生成元、前記第１の生成元及び前記第２の生成元の入力に少なくとも部分的に基づいて、前記第３のランダム要素を出力するよう構成される双線形写像関数、及び、前記第３の生成元の入力に少なくとも部分的に基づいて、前記第１の生成元を出力するよう構成される全単射写像関数を生成することを含む、請求項８に記載のコンピュータ読み取り可能な媒体。
【請求項１３】
前記動作は、
前記初期化関数により、前記第１の群に関連付けられる第１のランダム群要素を選択することと、
前記第１のランダム群要素の値を、前記第１の状態及び前記第１のランダム要素に割り当てることと、
をさらに含む、請求項１２に記載のコンピュータ読み取り可能な媒体。
【請求項１４】
前記動作は、
前記アップデート関数により、前記第２の群に関連付けられる第２のランダム群要素を選択することと、
前記アップデート関数により、前記全単射写像関数の出力の値を、第２の状態及び第２のランダム要素に割り当てることであって、前記全単射写像関数は、前記双線形写像関数の出力を入力として含み、前記双線形写像関数は、前記第１の状態及び前記第２のランダム群要素を入力として含む、割り当てることと、
をさらに含む、請求項１３に記載のコンピュータ読み取り可能な媒体。
【請求項１５】
アップデート可能なランダム関数であって、
前記アップデート可能なランダム関数に関連付けられる公開パラメータを生成するよう構成されているセットアップ関数と、
前記セットアップ関数により生成された前記公開パラメータに少なくとも部分的に基づいて、第１のランダム要素及び第１の状態を生成するよう構成されている初期化関数と、
前記セットアップ関数により生成された前記公開パラメータ、前記初期化関数により生成された前記第１の状態、及び第２のランダム要素に少なくとも部分的に基づいて、第３のランダム要素及び第２の状態を生成するよう構成されているアップデート関数と、
を含むアップデート可能なランダム関数
を有するブロックチェーンシステム。
【請求項１６】
前記アップデート可能なランダム関数は、ランダムオラクルタイプのアップデート可能な関数を含み、前記セットアップ関数により生成された前記公開パラメータは、２つの入力文字列に少なくとも部分的に基づいて、ランダム文字列出力を生成するよう構成されるランダムオラクルを含む、請求項１５に記載のブロックチェーンシステム。
【請求項１７】
前記初期化関数は、第１のランダム文字列を生成し、前記第１のランダム文字列の値を、前記第１のランダム要素及び前記第１の状態に割り当てるようさらに構成されている、請求項１６に記載のブロックチェーンシステム。
【請求項１８】
前記アップデート関数は、第２のランダム文字列を生成し、前記第２のランダム文字列の値を、前記第２のランダム要素に割り当て、前記ランダムオラクルの出力を、前記第３のランダム要素及び前記第２の状態に割り当てるようさらに構成されており、前記ランダムオラクルの入力は、前記初期化関数により生成された前記第１の状態及び前記第２のランダム要素を含む、請求項１７に記載のブロックチェーンシステム。
【請求項１９】
前記アップデート可能なランダム関数は、双線形ペアリングタイプのアップデート可能な関数を含み、前記セットアップ関数により生成された前記公開パラメータは、第１の群に関連付けられる第１の生成元、第２の群に関連付けられる第２の生成元、第３の群に関連付けられる第３の生成元、前記第１の生成元及び前記第２の生成元の入力に少なくとも部分的に基づいて、前記第３のランダム要素を出力するよう構成される双線形写像関数、及び、前記第３の生成元の入力に少なくとも部分的に基づいて、前記第１の生成元を出力するよう構成される全単射写像関数を含む、請求項１５に記載のブロックチェーンシステム。
【請求項２０】
前記初期化関数は、前記第１の群に関連付けられる第１のランダム群要素を選択し、前記第１のランダム群要素の値を、前記第１の状態及び前記第１のランダム要素に割り当てるようさらに構成されており、
前記アップデート関数は、前記第２の群に関連付けられる第２のランダム群要素を選択し、前記全単射写像関数の出力の値を、第２の状態及び第２のランダム要素に割り当てるようさらに構成されており、前記全単射写像関数は、前記双線形写像関数の出力を入力として含み、前記双線形写像関数は、前記第１の状態及び前記第２のランダム群要素を入力として含む、請求項１９に記載のブロックチェーンシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書に記載の実施形態は、アップデート可能なランダム関数に関する。
【背景技術】
【０００２】
ランダム関数は、文字からなるランダム文字列等のランダム出力を生成することができる。システム及びプロセスは、多くの理由でランダム出力を使用することがある。
【０００３】
本出願において特許請求される主題は、あらゆる欠点を解決する実施形態又は上記のような環境においてのみ動作する実施形態に限定されるものではない。そうではなく、この背景技術の記載は、本明細書に記載のいくつかの実施形態が実施され得る１つの例示的な技術領域を示すために提供されているに過ぎない。
【発明の概要】
【０００４】
一実施形態の一態様に従うと、方法は、セットアップ関数により、アップデート可能なランダム関数に関連付けられる公開パラメータを生成するステップを含み得る。前記方法は、初期化関数により、前記セットアップ関数により生成された前記公開パラメータに少なくとも部分的に基づいて、第１のランダム要素及び第１の状態を生成するステップをさらに含み得る。前記方法は、アップデート関数により、前記セットアップ関数により生成された前記公開パラメータに少なくとも部分的に基づいて、第３のランダム要素及び第２の状態を生成するステップをさらに含み得る。前記アップデート関数の入力は、前記初期化関数により生成された前記第１の状態及び第２のランダム要素を含み得る。
【０００５】
実施形態の目的及び利点が、少なくとも請求項において特に示される要素、特徴、及び組合せにより実現及び達成される。
【０００６】
前述の総括的な説明及び以下の詳細な説明の両方ともが、例示的で説明的なものであり、請求項を限定するものではない。
【図面の簡単な説明】
【０００７】
例示的な実施形態が、添付の図面を使用して、より具体的且つ詳細に記載及び説明される。
【図１】いくつかの実施形態が使用され得るネットワーク化されたコンピュータ環境を示す図。
【図２】例示的なアップデート可能なランダム関数のフローチャートを示す図。
【図３Ａ】例示的なランダムオラクルタイプのアップデート可能なランダム関数のためのセットアッププロセスを示す図。
【図３Ｂ】例示的なランダムオラクルタイプのアップデート可能なランダム関数のための初期化プロセスを示す図。
【図３Ｃ】例示的なランダムオラクルタイプのアップデート可能なランダム関数のためのアップデートプロセスを示す図。
【図４Ａ】例示的なランダムオラクルタイプのアップデート可能なランダム関数のためのセットアッププロセスを示す図。
【図４Ｂ】例示的なランダムオラクルタイプのアップデート可能なランダム関数のための初期化プロセスを示す図。
【図４Ｃ】例示的なランダムオラクルタイプのアップデート可能なランダム関数のためのアップデートプロセスを示す図。
【発明を実施するための形態】
【０００８】
いくつかのシステム及びプロセスは、ランダム出力が正当に生成されたことをユーザの群（グループ）が信頼し得るように、ランダム出力を使用することがある。例えば、いくつかのシステム及びプロセスは、ユーザの群がシステム又はプロセスに参加することを伴うマルチパーティ計算を用いて、ランダム出力を生成することがある。マルチパーティ計算に参加したユーザは、結果として得られたランダム出力が正当に生成されたことを信頼することがある。そのようなマルチパーティ計算は、実行するのに比較的コストが高いものであり得る。さらに、いくつかのシステム及びプロセスは、ランダム出力の比較的頻繁な生成を誘発することがある。例えば、頻繁に変化するユーザ群を有するシステム及びプロセスは、ランダム出力が正当に生成されたことを群における各ユーザが信頼し得るように、群構成の各変化に従う新たなランダム出力を生成することがある。
【０００９】
いくつかの実施形態は、アップデート可能なランダム関数を含み得る。アップデート可能なランダム関数は、アップデート可能なランダム関数の出力が十分にランダムであるという信頼性を促進することができる。したがって、例えば、ランダム文字列、乱数（ランダムナンバー）、又は他のランダム入力を使用するシステム又はプロセスは、ランダム入力が十分にランダムであるという信頼性をもって使用され得る。
【００１０】
例えば、アップデート可能なランダム関数は、いわゆる暗号通貨システム、デジタル通貨システム等において使用され得るような、ブロックチェーンプロセスにおいて使用され得る。いくつかの実施形態において、アップデート可能なランダム関数は、ブロックチェーン上でのゼロ知識証明において使用され得る。比較的高い頻度でブロックチェーンを離れブロックチェーンに参加することを選択し得る参加者を有するブロックチェーンは、アップデート可能でないランダム関数に対して、アップデート可能なランダム関数により改善され得る。
【００１１】
いくつかの実施形態において、アップデート可能なランダム関数は、２つの入力を受け取ることができる。これらの入力のうちのいずれかが十分にランダムである場合、アップデート可能なランダム関数の出力は十分にランダムであり得る。入力が、正当に生成されたランダム入力を含む場合、この入力は十分にランダムであり得る。したがって、例えば、アップデート可能なランダム関数は、ランダム入力を使用するプロセス又はシステムのユーザらに対する共有ランダム性を促進することができる。例えば、アップデート可能なランダム関数は、非対話ゼロ知識（ＮＩＺＫ）証明において使用され得、これは、ユーザが、何らかの証拠の知識を非対話的に検証することを可能にし得、証拠に関する情報を漏らさない。代替的又は追加的に、アップデート可能なランダム関数は、プルーフ・オブ・ワークアルゴリズムにおいて使用されてもよく、これは、ユーザのインセンティブを調整することにより、ブロックチェーン上での良い挙動を促進することができる。
【００１２】
共有ランダム性は、ＮＩＺＫ証明を使用するシステム及びプロセスの機能に寄与し得る。ユーザが、このランダム性を不正操作する能力を有する場合、ゼロ知識性は保たれないであろう。従来のシステムは、システム又はプロセスのユーザのセットが変化するたびに、ランダム入力が計算又は再計算されることを誘発することがある。ブロックチェーンシステム等のいくつかのシステム及びプロセスに関して、ユーザのセットは、頻繁に変化することがある。したがって、例えば、マルチパーティ計算が、頻繁に誘発されることがある。マルチパーティ計算は、比較的計算コストが高い、金銭コストが高い等であり得る。例えば、マルチパーティ計算は、例えば、金銭的に軽減するのが難しいものであり得るように、特定のアプリケーションの使用を妨げ得るように等、ネットワークの速度を落としてしまうことがある。
【００１３】
ランダム入力を生成するために比較的コストが高いマルチパーティ計算を頻繁に誘発することは、コンピュータ及びネットワーク業界、暗号通貨及びデジタル通貨業界等、又はこれらの任意の組合せといった業界における技術的問題を表し得る。例えば、マルチパーティ計算により生成された共有ランダム性を使用するシステム又はプロセスは、動作するのに比較的コストが高いものであり得る。代替的又は追加的に、システム及びプロセスは、関連するコストを回避するために、共有ランダム性を使用しないことがあり、これは、システム及びプロセスを比較的セキュアでないものに促進してしまうことがある。代替的又は追加的に、アップデート可能なランダム関数を使用して、パスワード認証型鍵交換、コミットメントスキーム、匿名クレデンシャル、認証型放送暗号化等、又はこれらの任意の組合せといった他のシステム及びプロセスにおける共有ランダム性を生成することができる。
【００１４】
いくつかの実施形態において、アップデート可能なランダム関数を使用して、従来の共有ランダム性によって生じた技術的問題を解決することができる。例えば、アップデート可能なランダム関数は、マルチパーティ計算が誘発される頻度を低減させることができ、これは、ＮＩＺＫ証明等の共有ランダム性を使用するシステム又はプロセスを動作させるコストを低減させることができる。代替的又は追加的に、アップデート可能なランダム関数は、そうでなければ共有ランダム性を使用し得ないシステム及びプロセスにおいて、共有ランダム性が使用されるように促進することができ、これは、よりセキュアなシステム及びプロセスを促進することができる。
【００１５】
実施形態が、添付の図面を参照して説明される。
【００１６】
図１は、いくつかの実施形態が使用され得るネットワーク化されたコンピュータ環境１００を示している。環境１００は、コンピュータ１０２ａ、コンピュータ１０２ｂ、及びコンピュータ１０２ｃ（集合的に「コンピュータ１０２」）を含む複数のコンピュータを含み得る。省略記号で示されているように、コンピュータ１０２の群は、さらなるコンピュータを含み得る。コンピュータ１０２は、ネットワーク１０４を介して通信することができ、何らかの機能を実行するための群を形成することができる。
【００１７】
いくつかの構成において、コンピュータ１０２は、ビットコイン（登録商標）ブロックチェーン等の、暗号通貨のためのブロックチェーンを維持するよう構成され得る。ブロックチェーンは、承認済みのトランザクションのリストを利用可能にする共有公開台帳を表し得る。ブロックチェーンは、コンピュータ１０２によりホストされ得る。暗号通貨の移転は、２つ以上の口座の間でなされ得る。いくつかの例において、口座は、コンピュータ１０２のうちの１つ以上、又は、他のコンピュータ若しくはデバイスに関連付けられ得る。コンピュータ１０２は、コンピュータ１０２が、暗号通貨の移転を検証し、ブロックチェーンにおいて記録された以前の移転の変更を防止することを一般に可能にする暗号ルールを使用して、暗号通貨の移転を承認することができる。
【００１８】
ランダム出力は、ブロックチェーンを維持する際に使用され得る。いくつかの例において、ランダム出力は、ランダム出力が正当に生成されたことをコンピュータ１０２が確認することを可能にするやり方で生成され得る。コンピュータ１０２の群の構成が変化するたびに、新たなランダム出力が生成され得る。例えば、コンピュータ１０２ｃ等の新たなコンピュータが群に参加するたびに、新たなランダム出力が生成され得る。従来では、群におけるコンピュータ１０２の各々は、ネットワーク１０４を介して通信し、計算的に初期ランダム出力を生成し新たなランダム出力を生成するように参加するであろう。さらに、従来のランダム出力を生成するときにコンピュータ１０２間で交換される通信の数は、群におけるコンピュータ１０２の数につれて対数的に増加・減少するであろう。
【００１９】
いくつかの実施形態において、コンピュータ１０２は、アップデート可能なランダム関数を使用して、初期ランダム出力を生成し、新たなランダム出力を生成する（本明細書において、「ランダム出力をアップデートする」とも記載されている）ことができる。ランダム出力は、コンピュータ１０２の群の構成の変化に応じてアップデートされ得る。いくつかの実施形態において、ランダム出力は、コンピュータが群に参加したことに応じてアップデートされ得るが、コンピュータが群を離れたことに応じてはアップデートされなくてよい。ランダム出力をアップデートすることは、従来のマルチパーティ計算を通じて新たなランダム出力を生成するよりも、相対的にコストが低いものであり得る。この実施形態及び他の実施形態において、アップデート可能なランダム関数は、マルチパーティ計算を用いずに、初期ランダム出力を生成してよい。代替的又は追加的に、コンピュータ１０２のうちの１つ以上が、ランダム出力をアップデートし得るが、群における他のコンピュータは、ネットワーク１０４を介して通信しなくてよい。いくつかの構成において、ランダム出力をアップデートするコンピュータは、ランダム出力がアップデートされることを、１つの通信を介して、群における他のコンピュータに通信することができる。
【００２０】
いくつかの構成において、共有公開ランダム性が、暗号通貨ブロックチェーン上で複数の暗号アプリケーションにおいて使用され得る。例えば、共有公開ランダム性が、ゼロ知識証明及びＳＮＡＲＫ（succinct  non-interactive  argument  of  knowledge）により使用され得、これは、暗号通貨ブロックチェーン上で非公開のコンフィデンシャルなトランザクションをセキュアに構築するために使用され得る。１つのパーティ又はパーティの群が、ランダム性に不当に影響を及ぼすことができ得る場合、ゼロ知識証明及びＳＮＡＲＫに関連するセキュリティ保証はないことがあり、プロセスはセキュアでないことがある。いくつかの実施形態は、共有公開ランダム性を、セキュアに生成することができる。
【００２１】
図２は、例示的なアップデート可能なランダム関数のフローチャート２００を示している。いくつかの実施形態において、アップデート可能なランダム関数は、セットアップ関数、初期化関数、及びアップデート関数を含み得る。フローチャート２００は、ブロック２０２で開始し得、ブロック２０２において、アップデート可能なランダム関数は、セットアップ関数を実行することができる。セットアップ関数は、以下の定義を含み得る：
Ｓｅｔｕｐ：＝１λ→ＰＰ
【００２２】
上記において、ＰＰは、公開パラメータを表し得、λは、セキュリティパラメータを表し得る。公開パラメータは、望まれるセキュリティレベルに基づいて選択され得る。セットアップ関数は、公開されたアルゴリズムセットアップを含み得る。したがって、例えば、アルゴリズムセットアップが不正利用可能な関数又はトラップドアを含み得ないことを、ユーザに保証することができる。
【００２３】
フローチャート２００は、ブロック２０４に進み得、ブロック２０４において、アップデート可能なランダム関数は、初期化関数を実行することができる。初期化関数は、以下の定義を含み得る：
Ｉｎｉｔｉａｌｉｚｅ：＝ＰＰ→Ｘ１×Ｓ
【００２４】
上記において、Ｘ１は第１の領域を表し得、Ｓは状態領域を表し得る。初期化関数は、Ｘ１領域におけるｘ１により表されるランダム要素と、Ｓ領域におけるｓにより表される状態と、を出力することができる。例えば、初期化関数は、以下のように表現され得る：
ＩｎｉｔｉａｌｉｚｅＰＰ（）→ｓ，ｘ１
【００２５】
フローチャート２００は、ブロック２０６に進み得、ブロック２０６において、アップデート可能なランダム関数は、アップデート関数を実行することができる。アップデート関数は、以下の定義を含み得る：
Ｕｐｄａｔｅ：＝ＰＰ×Ｓ×Ｘ２→Ｘ１×Ｓ
【００２６】
上記において、Ｘ２は第２の領域を表し得る。アップデート関数は、ＰＰにより表される公開パラメータと、初期化関数により出力された、ｓにより表される現在状態と、Ｘ２領域におけるｘ２により表される新たな要素と、を、入力として受け取ることができる。アップデート関数は、Ｘ１領域におけるｘ１により再度表される新たなランダム要素と、Ｓ領域におけるｓにより再度表される新たな状態と、を出力することができる。例えば、アップデート関数は、以下のように表現され得る：
ＵｐｄａｔｅＰＰ（ｓ，ｘ２）→ｓ，ｘ１
【００２７】
いくつかの実施形態において、アップデート関数の特性は、ｓが、領域Ｓにおける任意であるが妥当な状態であり、ｘ２が、領域Ｘ２においてランダムに一様にサンプリングされるときには、アップデート関数により出力される新たなランダム要素が、Ｘ１において統計的にほぼ一様に分布し得るということを含み得る。
【００２８】
代替的又は追加的に、アップデート関数の特性は、ＰＰ及びｓが与えられたときに、効率的な敵が、ＵｐｄａｔｅＰＰ（ｓ，・）を置換するオラクルにおける真のランダム関数に問い合わせることにより実現され得るよりも速く領域Ｘ２における何らかのｘ２を見つけ出すことができないということを含み得る。例えば、ｓは、領域Ｓにおける正当に選択された状態、例えば、一様にランダムな出力に対応する状態、であり得る。さらに、Ｔは、Ｔにおける要素であることが効率的にテスト可能であり得るように、領域Ｘ１にわたる何らかの要素の集合を表し得る。アップデート関数は、ＵｐｄａｔｅＰＰ（ｓ，ｘ２）→ｘ１（ｘ１は領域Ｔにおけるものである）であるように、効率的な敵が、領域Ｘ２における何らかのｘ２を見つけ出すことができないという特性を含み得る。
【００２９】
いくつかの実施形態において、フローチャート２００は、ブロック２０６に戻って、アップデート関数をさらに実行し、領域Ｘ１におけるｘ１により同様に表され得るさらなる新たなランダム要素を生成することができる。したがって、例えば、新たなランダム要素が、必要に応じて生成され得る。例えば、新たなランダム要素は、コンピュータ１０２の群の構成の変化に応じて、図１のコンピュータ１０２の群により生成され得る。
【００３０】
図３Ａは、例示的なランダムオラクルタイプのアップデート可能なランダム関数のためのセットアッププロセス３００を示している。図３Ｂは、この例示的なランダムオラクルタイプのアップデート可能なランダム関数のための初期化プロセス３３０を示している。図３Ｃは、この例示的なランダムオラクルタイプのアップデート可能なランダム関数のためのアップデートプロセス３６０を示している。
【００３１】
図３Ａを参照すると、セットアッププロセス３００は、ブロック３０２で開始し得、ブロック３０２において、Ｈ（）により表されるランダムオラクルが生成され得る。ランダムオラクルは、以下のように定義され得る：
Ｈ：＝｛０，１｝ｌ×｛０，１｝ｌ→｛０，１｝ｌ
【００３２】
上記において、ｌは入力／出力長を表し得る。例えば、ｌは、ランダムオラクルＨの２つの入力及び１つの出力のビット長を表し得る。
【００３３】
図３Ｂを参照すると、初期化プロセス３３０は、ブロック３３２で開始し得、ブロック３３２において、ランダム文字列が生成され得る。ランダム文字列は、ｒにより表され得、領域｛０，１｝ｌにおけるものであり得る。
【００３４】
初期化プロセス３３０は、ブロック３３４に進み得、ブロック３３４において、状態が設定され得る。いくつかの実施形態において、ランダム文字列が、この状態に設定され得る。状態は、ｓにより表され得る。
【００３５】
初期化プロセス３３０は、ブロック３３６に進み得、ブロック３３６において、ランダム出力が設定され得る。いくつかの実施形態において、ランダム文字列が、このランダム出力に設定され得る。ランダム出力は、ｘ１により表され得る。
【００３６】
図３Ｃを参照すると、アップデートプロセス３６０は、ブロック３６２で開始し得、ブロック３６２において、状態ｓが、旧状態に設定され得る。アップデートプロセスは、ブロック３６４に進み得、ブロック３６４において、新たなランダム文字列が生成され得る。新たなランダム文字列は、ｘ２により表され得、領域｛０，１｝ｌにおけるものであり得る。
【００３７】
アップデートプロセス３６０は、ブロック３６６に進み得、ブロック３６６において、状態及び新たなランダム文字列が、ランダムオラクル関数に入力されて、Ｈ（ｓ，ｘ２）により表され得る結果が計算され得る。
【００３８】
アップデートプロセス３６０は、ブロック３６８に進み得、ブロック３６８において、Ｈ（ｓ，ｘ２）が、状態ｓに設定され得る。
【００３９】
アップデートプロセス３６０は、ブロック３７０に進み得、ブロック３７０において、Ｈ（ｓ，ｘ２）が、さらに、ランダム出力ｘ１に設定され得る。
【００４０】
本出願において開示される上記プロセス及び他のプロセス並びに方法に関して、これらのプロセス及び方法において実行される関数は、異なる順序で実施されることがある。さらに、説明された動作は、例として提供されているに過ぎず、動作のうちの一部は、実施形態の本質を損なうことなく、任意的であることもあるし、より少ない動作に組み合わされることもあるし、追加の動作に拡張されることもある。
【００４１】
図４Ａは、例示的なランダムオラクルタイプのアップデート可能なランダム関数のためのセットアッププロセス４００を示している。図４Ｂは、この例示的なランダムオラクルタイプのアップデート可能なランダム関数のための初期化プロセス４３０を示している。図４Ｃは、この例示的なランダムオラクルタイプのアップデート可能なランダム関数のためのアップデートプロセス４６０を示している。
【００４２】
図４Ａを参照すると、セットアッププロセス４００は、ブロック４０２で開始し得、ブロック４０２において、群パラメータが生成され得る。群パラメータは、Ｇ１、Ｇ２、ＧＴ、ｇ１、ｇ２、ｇＴ、ｅ（）、及びｆ（）を含み得る。いくつかの実施形態において、Ｇ１、Ｇ２、及びＧＴは、同じ位数の群であり得る。代替的又は追加的に、ｇ１は、群Ｇ１におけるものであり得、ｇ２は、群Ｇ２におけるものであり得、ｇＴは、群ＧＴにおけるものであり得る。関数ｅ（）は、効率的に計算可能な双線形写像であり得、以下のように定義され得る：
ｅ：＝Ｇ１×Ｇ２→ＧＴ
【００４３】
関数ｆ（）は、効率的に計算可能な全単射写像であり得、以下のように定義され得る：
ｆ：＝ＧＴ→Ｇ１
【００４４】
いくつかの実施形態において、ｇ１、ｇ２、及びｇＴは、生成元であり得、以下の特性を含み得る：
ｅ（ｇ１，ｇ２）＝ｇＴ
【００４５】
図４Ｂを参照すると、初期化プロセス４３０は、ブロック４３２で開始し得、ブロック４３２において、ｇにより表され得るランダム群要素が選択され得る。ランダム群要素ｇは、群Ｇ１におけるものであり得る。
【００４６】
初期化プロセス４３０は、ブロック４３４に進み得、ブロック４３４において、ｇが、ｓとして表され得る状態に設定され得る。
【００４７】
初期化プロセス４３０は、ブロック４３６に進み得、ブロック４３６において、ｇが、さらに、ｘ１として表され得るランダム出力に設定され得る。したがって、例えば、初期化プロセス４３０は、ランダム出力ｘ１及び状態ｓを生成することができ、これらはそれぞれ、群Ｇ１における生成元ｇ１に等しいものであり得る。
【００４８】
図４Ｃを参照すると、アップデートプロセス４６０は、ブロック４６２で開始し得、ブロック４６２において、状態ｓが、旧状態に設定され得る。アップデートプロセス４６０は、ブロック４６４に進み得、ブロック４６４において、新たなランダム要素が選択され得る。新たなランダム要素は、ｇ’により表され得、群Ｇ２におけるものであり得る。
【００４９】
アップデートプロセス４６０は、ブロック４６６に進み得、ブロック４６６において、関数ｅ（）が、状態ｓ及び新たなランダム要素ｇ’を使用して計算され得、関数ｆ（）が、この結果を入力として使用して計算され得る。別の表現をすると、全単射写像関数の出力として表されｙにより表され得る出力が、以下の式に従って計算され得る：
ｙ＝ｆ（ｅ（ｓ，ｇ’））
【００５０】
アップデートプロセス４６０は、ブロック４６８に進み得、ブロック４６８において、出力ｙが、ｓ’により表され得る新状態に設定され得る。
【００５１】
アップデートプロセス４６０は、ブロック４７０に進み得、ブロック４７０において、出力ｙが、ｘ１により表され得る新たなランダム出力に設定され得る。
【００５２】
本明細書に記載の実施形態は、以下でより詳細に説明されるような、様々なコンピュータハードウェア又はソフトウェアモジュールを含む専用コンピュータ又は汎用コンピュータを含み得る。
【００５３】
本明細書に記載の実施形態は、コンピュータ実行可能な命令又はデータ構造を運ぶ又は記憶するためのコンピュータ読み取り可能な媒体を使用して実施され得る。そのようなコンピュータ読み取り可能な媒体は、汎用コンピュータ又は専用コンピュータによりアクセスされ得る任意の利用可能な媒体であり得る。限定ではなく例として、そのようなコンピュータ読み取り可能な媒体は、ランダムアクセスメモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、電気的に消去可能なプログラム可能な読み取り専用メモリ（ＥＥＰＲＯＭ）、コンパクトディスク読み取り専用メモリ（ＣＤ−ＲＯＭ）若しくは他の光ディスクストレージ、磁気ディスクストレージ若しくは他の磁気記憶デバイス、フラッシュメモリデバイス（例えば、ソリッドステートメモリデバイス）、又は、コンピュータ実行可能な命令又はデータ構造の形で所望のプログラムコードを運ぶ又は記憶するために使用され得る任意の他の記憶媒体であって、汎用コンピュータ又は専用コンピュータによりアクセスされ得る任意の他の記憶媒体を含む非一時的なコンピュータ読み取り可能な記憶媒体を含み得る。これらの組合せも、コンピュータ読み取り可能な媒体の範囲に含まれ得る。
【００５４】
コンピュータ実行可能な命令は、例えば、所定の機能又は機能群を、汎用コンピュータ、専用コンピュータ、又は専用処理デバイス（例えば、１つ以上のプロセッサ）に実行させる命令及びデータを含み得る。主題が、構造的特徴及び／又は方法的動作に特有の言葉で説明されているが、請求項において定められる主題は、上述した特定の特徴又は動作に必ずしも限定されるものではないことを理解されたい。そうではなく、上述した特定の特徴又は動作は、請求項を実施する例示的な形態として開示されている。
【００５５】
いくつかの実施形態において、本明細書に記載の異なるシステム及びプロセスは、コンピューティングシステム上で実行されるオブジェクト又はプロセスとして（例えば、別個のスレッドとして）実装され得る。本明細書に記載のシステム及び方法の一部は、概して、（汎用ハードウェアに記憶される且つ／又は汎用ハードウェアにより実行される）ソフトウェアにより実装されるとして説明されるが、特定のハードウェア実装又はソフトウェアと特定のハードウェア実装との組合せも可能であり企図されている。
【００５６】
本明細書に記載されている全ての例及び条件付き文言は、当該技術を促進させることに寄与するコンセプト及び実施形態を読者が理解するのを助ける教育上の目的のために意図され、そのような具体的に記載されている例及び条件に限定されるものではないとして解釈されるべきである。実施形態が詳細に説明されているが、様々な変形、置換、及び変更が、実施形態の範囲から逸脱することなく可能である。
【００５７】
以上の実施形態に関し、さらに以下の付記を開示する。
【００５８】
（付記１）
セットアップ関数により、アップデート可能なランダム関数に関連付けられる公開パラメータを生成するステップと、
初期化関数により、前記セットアップ関数により生成された前記公開パラメータに少なくとも部分的に基づいて、第１のランダム要素及び第１の状態を生成するステップと、
アップデート関数により、前記セットアップ関数により生成された前記公開パラメータに少なくとも部分的に基づいて、第３のランダム要素及び第２の状態を生成するステップであって、前記アップデート関数の入力は、前記初期化関数により生成された前記第１の状態及び第２のランダム要素を含む、ステップと、
を含む方法。
【００５９】
（付記２）
前記公開パラメータを生成することは、前記セットアップ関数により、２つの入力文字列に少なくとも部分的に基づいて、ランダム文字列出力を生成するよう構成されるランダムオラクルを生成することを含む、付記１に記載の方法。
【００６０】
（付記３）
前記初期化関数により、第１のランダム文字列を生成し、前記第１のランダム文字列の値を、前記第１のランダム要素及び前記第１の状態に割り当てるステップ
をさらに含む、付記２に記載の方法。
【００６１】
（付記４）
前記アップデート関数により、第２のランダム文字列を生成するステップと、
前記第２のランダム文字列の値を、前記第２のランダム要素に割り当てるステップと、
前記ランダムオラクルの出力を、前記第３のランダム要素及び前記第２の状態に割り当てるステップであって、前記ランダムオラクルの入力は、前記初期化関数により生成された前記第１の状態及び前記第２のランダム要素を含む、ステップと、
をさらに含む、付記３に記載の方法。
【００６２】
（付記５）
前記公開パラメータを生成することは、前記セットアップ関数により、第１の群に関連付けられる第１の生成元、第２の群に関連付けられる第２の生成元、第３の群に関連付けられる第３の生成元、前記第１の生成元及び前記第２の生成元の入力に少なくとも部分的に基づいて、前記第３のランダム要素を出力するよう構成される双線形写像関数、及び、前記第３の生成元の入力に少なくとも部分的に基づいて、前記第１の生成元を出力するよう構成される全単射写像関数を生成することを含む、付記１に記載の方法。
【００６３】
（付記６）
前記初期化関数により、前記第１の群に関連付けられる第１のランダム群要素を選択するステップと、
前記第１のランダム群要素の値を、前記第１の状態及び前記第１のランダム要素に割り当てるステップと、
をさらに含む、付記５に記載の方法。
【００６４】
（付記７）
前記アップデート関数により、前記第２の群に関連付けられる第２のランダム群要素を選択するステップと、
前記アップデート関数により、前記全単射写像関数の出力の値を、第２の状態及び第２のランダム要素に割り当てるステップであって、前記全単射写像関数は、前記双線形写像関数の出力を入力として含み、前記双線形写像関数は、前記第１の状態及び前記第２のランダム群要素を入力として含む、ステップと、
をさらに含む、付記６に記載の方法。
【００６５】
（付記８）
アップデート可能なランダム関数の動作をシステムに実行させるよう構成されているコンピュータ読み取り可能な媒体であって、前記動作は、
セットアップ関数により、アップデート可能なランダム関数に関連付けられる公開パラメータを生成することと、
初期化関数により、前記セットアップ関数により生成された前記公開パラメータに少なくとも部分的に基づいて、第１のランダム要素及び第１の状態を生成することと、
アップデート関数により、前記セットアップ関数により生成された前記公開パラメータに少なくとも部分的に基づいて、第３のランダム要素及び第２の状態を生成することであって、前記アップデート関数の入力は、前記初期化関数により生成された前記第１の状態及び第２のランダム要素を含む、生成することと、
を含む、コンピュータ読み取り可能な媒体。
【００６６】
（付記９）
前記公開パラメータを生成することは、前記セットアップ関数により、２つの入力文字列に少なくとも部分的に基づいて、ランダム文字列出力を生成するよう構成されるランダムオラクルを生成することを含む、付記８に記載のコンピュータ読み取り可能な媒体。
【００６７】
（付記１０）
前記動作は、
前記初期化関数により、第１のランダム文字列を生成し、前記第１のランダム文字列の値を、前記第１のランダム要素及び前記第１の状態に割り当てること
をさらに含む、付記９に記載のコンピュータ読み取り可能な媒体。
【００６８】
（付記１１）
前記動作は、
前記アップデート関数により、第２のランダム文字列を生成することと、
前記第２のランダム文字列の値を、前記第２のランダム要素に割り当てることと、
前記ランダムオラクルの出力を、前記第３のランダム要素及び前記第２の状態に割り当てることであって、前記ランダムオラクルの入力は、前記初期化関数により生成された前記第１の状態及び前記第２のランダム要素を含む、割り当てることと、
をさらに含む、付記１０に記載のコンピュータ読み取り可能な媒体。
【００６９】
（付記１２）
前記公開パラメータを生成することは、前記セットアップ関数により、第１の群に関連付けられる第１の生成元、第２の群に関連付けられる第２の生成元、第３の群に関連付けられる第３の生成元、前記第１の生成元及び前記第２の生成元の入力に少なくとも部分的に基づいて、前記第３のランダム要素を出力するよう構成される双線形写像関数、及び、前記第３の生成元の入力に少なくとも部分的に基づいて、前記第１の生成元を出力するよう構成される全単射写像関数を生成することを含む、付記８に記載のコンピュータ読み取り可能な媒体。
【００７０】
（付記１３）
前記動作は、
前記初期化関数により、前記第１の群に関連付けられる第１のランダム群要素を選択することと、
前記第１のランダム群要素の値を、前記第１の状態及び前記第１のランダム要素に割り当てることと、
をさらに含む、付記１２に記載のコンピュータ読み取り可能な媒体。
【００７１】
（付記１４）
前記動作は、
前記アップデート関数により、前記第２の群に関連付けられる第２のランダム群要素を選択することと、
前記アップデート関数により、前記全単射写像関数の出力の値を、第２の状態及び第２のランダム要素に割り当てることであって、前記全単射写像関数は、前記双線形写像関数の出力を入力として含み、前記双線形写像関数は、前記第１の状態及び前記第２のランダム群要素を入力として含む、割り当てることと、
をさらに含む、付記１３に記載のコンピュータ読み取り可能な媒体。
【００７２】
（付記１５）
アップデート可能なランダム関数であって、
前記アップデート可能なランダム関数に関連付けられる公開パラメータを生成するよう構成されているセットアップ関数と、
前記セットアップ関数により生成された前記公開パラメータに少なくとも部分的に基づいて、第１のランダム要素及び第１の状態を生成するよう構成されている初期化関数と、
前記セットアップ関数により生成された前記公開パラメータ、前記初期化関数により生成された前記第１の状態、及び第２のランダム要素に少なくとも部分的に基づいて、第３のランダム要素及び第２の状態を生成するよう構成されているアップデート関数と、
を含むアップデート可能なランダム関数
を有するブロックチェーンシステム。
【００７３】
（付記１６）
前記アップデート可能なランダム関数は、ランダムオラクルタイプのアップデート可能な関数を含み、前記セットアップ関数により生成された前記公開パラメータは、２つの入力文字列に少なくとも部分的に基づいて、ランダム文字列出力を生成するよう構成されるランダムオラクルを含む、付記１５に記載のブロックチェーンシステム。
【００７４】
（付記１７）
前記初期化関数は、第１のランダム文字列を生成し、前記第１のランダム文字列の値を、前記第１のランダム要素及び前記第１の状態に割り当てるようさらに構成されている、付記１６に記載のブロックチェーンシステム。
【００７５】
（付記１８）
前記アップデート関数は、第２のランダム文字列を生成し、前記第２のランダム文字列の値を、前記第２のランダム要素に割り当て、前記ランダムオラクルの出力を、前記第３のランダム要素及び前記第２の状態に割り当てるようさらに構成されており、前記ランダムオラクルの入力は、前記初期化関数により生成された前記第１の状態及び前記第２のランダム要素を含む、付記１７に記載のブロックチェーンシステム。
【００７６】
（付記１９）
前記アップデート可能なランダム関数は、双線形ペアリングタイプのアップデート可能な関数を含み、前記セットアップ関数により生成された前記公開パラメータは、第１の群に関連付けられる第１の生成元、第２の群に関連付けられる第２の生成元、第３の群に関連付けられる第３の生成元、前記第１の生成元及び前記第２の生成元の入力に少なくとも部分的に基づいて、前記第３のランダム要素を出力するよう構成される双線形写像関数、及び、前記第３の生成元の入力に少なくとも部分的に基づいて、前記第１の生成元を出力するよう構成される全単射写像関数を含む、付記１５に記載のブロックチェーンシステム。
【００７７】
（付記２０）
前記初期化関数は、前記第１の群に関連付けられる第１のランダム群要素を選択し、前記第１のランダム群要素の値を、前記第１の状態及び前記第１のランダム要素に割り当てるようさらに構成されており、
前記アップデート関数は、前記第２の群に関連付けられる第２のランダム群要素を選択し、前記全単射写像関数の出力の値を、第２の状態及び第２のランダム要素に割り当てるようさらに構成されており、前記全単射写像関数は、前記双線形写像関数の出力を入力として含み、前記双線形写像関数は、前記第１の状態及び前記第２のランダム群要素を入力として含む、付記１９に記載のブロックチェーンシステム。
【符号の説明】
【００７８】
１０２ａ  コンピュータ
１０２ｂ  コンピュータ
１０２ｃ  コンピュータ
１０４    ネットワーク
【図１】
2018156079.tif 000003
【図２】
2018156079.tif 000004
【図３Ａ】
2018156079.tif 000005
【図３Ｂ】
2018156079.tif 000006
【図３Ｃ】
2018156079.tif 000007
【図４Ａ】
2018156079.tif 000008
【図４Ｂ】
2018156079.tif 000009
【図４Ｃ】
2018156079.tif 000010