特許ウォッチ

公開番号2025118950
公報種別公開特許公報(A)
公開日2025-08-13
出願番号2025083820,2022569449
出願日2025-05-20,2021-05-14
発明の名称暗号化されたデータに対する単変数または多変数の実数値関数を評価するための暗号方法、システム、およびサービス
出願人ザマ・エス・ア・エス
代理人弁理士法人川口國際特許事務所
主分類G09C 1/00 20060101AFI20250805BHJP(教育;暗号方法;表示;広告;シール)
要約【課題】出力におけるノイズの制御を可能にしながら、関数の形式や定義の領域に関係なく、実数のLWE(Learning With Errors)型暗号文である入力に実数値変数を持つ関数の準同型評価を可能にする方法及びシステムを提供する。
【解決手段】方法は、多変数関数のそれぞれを、実数値を有する単変数関数の総和と合成で構成される単変数関数のネットワークに変換する事前計算ステップと、事前計算された単変数関数ネットワークにおいて、異なる型の冗長性を識別し、それらのすべてまたは一部を選択する事前選択ステップと、事前選択ステップで選択された冗長性が最適化された方法で評価される、単変数関数の事前計算されたネットワークのそれぞれの準同型評価を行うステップと、を含む。
【選択図】図1
特許請求の範囲【請求項１】
１つ以上の多変数実数値関数ｆ
１
，…，ｆ
ｑ
の評価を行うように特別にプログラムされた少なくとも１つの情報処理システムによってデジタル形式で実行される暗号方法であって、各関数は、変数ｘ
１
，…，ｘ
ｐ
の中から複数の実数値変数を入力として取り、前記関数の少なくとも１つは、入力として少なくとも２つの変数を取り、
１≦ｉ≦ｐの入力ｘ
ｉ
、Ｅ（ｅｎｃｏｄｅ（ｘ
ｉ
））のそれぞれの暗号化の暗号文を入力として取り、それらのそれぞれの入力に適用されたｆ
１
，…，ｆ
ｑ
の暗号化の複数の暗号文を返し、Ｅは準同型暗号化アルゴリズムであり、ｅｎｃｏｄｅは、Ｅの平文のネイティブ空間の要素を実数ｘ
ｉ
のそれぞれに関連付けるエンコーディング関数であり、
－ａ．前記多変数関数のそれぞれを、実数値を有する単変数関数の合成と総和から構成される単変数関数のネットワークに変換することである事前計算ステップ、
－ｂ．事前計算された単変数関数の前記ネットワークにおいて、３つの型：
○同じ引数に適用される同じ単変数関数、
○同じ引数に適用される異なる単変数関数、
○非ゼロの加算定数だけ異なる引数に適用される同じ単変数関数
のうちの１つの冗長性を識別し、その全部または一部を選択することである事前選択ステップ、
ｃ．事前計算された単変数関数のネットワークのそれぞれの準同型評価のステップであって、これらの単変数関数の１つ以上のすべてまたは一部が再利用されるとき、事前選択ステップで選択された冗長性が共有された方法で評価される、ステップを特徴とする、暗号方法。
続きを表示（約 2,300 文字）【請求項２】
ｆ
１
，…，ｆ
ｑ
の中から少なくとも１つの関数ｆ
ｊ
に対して、事前計算ステップの変換はｔ≦ｐおよびｊ
１
，…，ｊ
ｔ
∈｛１，…，ｐ｝で
TIFF
2025118950000306.tif
11
169
の形式で近似変換であり、係数ａ
ｉ
，
ｋ
は実数であり、ｇ
ｋ
は、実数で定義され実数値を有する単変数関数であり、前記関数ｇ
ｋ
と前記係数ａ
ｉ
，
ｋ
は、所与のパラメータＫに対してｆ
ｊ
に応じて決定されることを特徴とする、請求項１に記載の暗号方法。
【請求項３】
ｆ
１
，…，ｆ
ｑ
の中から少なくとも１つの関数ｆ
ｊ
に対して、事前計算ステップの変換は、
TIFF
2025118950000307.tif
9
169
、
TIFF
2025118950000308.tif
8
169
、ｔ≦ｐおよびｊ
１
，…，ｊ
ｔ
∈｛１，…，ｐ｝で
TIFF
2025118950000309.tif
9
169
の形式の近似変換であり、ベクトルａ
ｋ
は係数ａ
ｉ
，
ｋ
として実数を有し、ｇ
ｋ
は実数で定義された、実数値を有する単変数関数であり、前記関数ｇ
ｋ
および前記係数ａ
ｉ
，
ｋ
は、所与のパラメータＫおよび所与のノルム｜｜・｜｜に対して、ｆ
ｊ
に応じて決定されることを特徴とする、請求項１に記載の暗号方法。
【請求項４】
係数ａ
ｉ
，
ｋ
が固定であることを特徴とする、請求項２または３に記載の暗号方法。
【請求項５】
ｆ
１
，…，ｆ
ｑ
の中から少なくとも１つの関数ｆ
ｊ
に対して、事前計算ステップの変換は、ｔ≦ｐおよびｊ
１
，…，ｊ
ｔ
∈｛１，…，ｐ｝で
TIFF
2025118950000310.tif
10
169
の形式の近似変換であり、Ψは、実数で定義され実数値を有する単変数関数であり、
TIFF
2025118950000311.tif
9
169
は実定数であり、ｇ
ｋ
は実数で定義された実数値を有する単変数関数であり、前記関数ｇ
ｋ
は、所与のパラメータＫに対してｆ
ｊ
に応じて決定されることを特徴とする、請求項１に記載の暗号方法。
【請求項６】
事前計算ステップの変換が、形式的等価ｍａｘ（ｚ
１
，ｚ
２
）＝ｚ
２
＋（ｚ
１
－ｚ
２
）
＋
を使用して、関数
TIFF
2025118950000312.tif
8
169
を、単変数関数の総和と合成の組み合わせとして表現することを特徴とする、請求項１に記載の暗号方法。
【請求項７】
事前計算ステップの変換が、形式的等価ｍｉｎ（ｚ
１
，ｚ
２
）＝ｚ
２
＋（ｚ
１
－ｚ
２
）
－
を使用して、関数
TIFF
2025118950000313.tif
7
169
を、単変数関数の総和と合成の組み合わせとして表現することを特徴とする、請求項１に記載の暗号方法。
【請求項８】
事前計算ステップの変換が形式的等価ｚ
１
×ｚ
２
＝（ｚ
１
＋ｚ
２
）
２
／４－（ｚ
１
－ｚ
２
）
２
／４を使用して、関数
TIFF
2025118950000314.tif
9
169
を、単変数関数の総和と合成の組み合わせとして表現することを特徴とする、請求項１に記載の暗号方法。
【請求項９】
事前計算ステップの変換が、形式的等価｜ｚ
１
×ｚ
２
｜＝ｅｘｐ（ｌｎ｜ｚ
１
｜＋ｌｎ｜ｚ
２
｜）を使用して、関数
TIFF
2025118950000315.tif
9
169
を、単変数関数の総和と合成の組み合わせとして表現することを特徴とする、請求項１に記載の暗号方法。
【請求項１０】
関数が３変数以上を含むとき、前記関数について、２変数の形式的等価の反復から形式的等価を求めることを特徴とする、請求項６から９のいずれか一項に記載の暗号方法。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本発明は、事前に暗号化されたデータに適用される１つ以上の関数の準同型評価を改善することに関する。この技術分野は、最近の暗号研究に基づいており、機密性の制約が存在するすべての活動分野（これに限らず、プライバシー保護のもの、企業秘密のもの、または医療データのものなど）に多数の用途が含まれる可能性がある。
続きを表示（約 9,900 文字）【０００２】
より詳細には、本発明は、１つ以上の関数の準同型評価に必要な計算を、１つ以上の特別にプログラムされたコンピュータシステムによって自動完了できるようにするための方法に関する。したがって、限られた記憶と計算時間の容量または、クラウドコンピューティング型のリモート処理の場合は、この型の評価を行う必要がある情報処理システムにより知られ得る伝送容量を考慮する必要がある。
【０００３】
以下に説明するように、準同型暗号化方法の開発は、特に、様々な計算段階を実行するために実装されるマシンリソースとサポートされる計算時間に関して、コンピュータの処理容量に関連し、文献によって提案された方式のほとんどに固有の技術的制約によって、これまで大きく妨げられてきた。
【背景技術】
【０００４】
完全準同型暗号化方式（完全準同型暗号化、略してＦＨＥ）では、任意の参加者が暗号文の集合（平文ｘ
１
，…，ｘ
ｐ
に対応）を、この参加者が平文自体にアクセスすることなく、平文の所与の関数ｆ（ｘ
１
，…，ｘ
ｐ
）に対応する暗号文に公に変換できる。このような方式を使用して、私生活に準拠したプロトコルを構築できることはよく知られている（プライバシー保護）：ユーザは暗号化されたデータをサーバーに記憶し、データ自体をサーバーに公開する必要なく、暗号化されたデータに対する演算を行うことを第三者に許可できる。
【０００５】
第１の完全準同型暗号化方式は、Ｇｅｎｔｒｙ（２００９年の第１の出願に基づいて２０１４年に米国登録特許第８６３０４２２号を取得した）によって２００９年にようやく初めて提案された；［ＣｒａｉｇＧｅｎｔｒｙ、「Ｆｕｌｌｙｈｏｍｏｍｏｒｐｈｉｃｅｎｃｒｙｐｔｉｏｎｕｓｉｎｇｉｄｅａｌｌａｔｔｉｃｅｓ」、４１ｓｔＡｎｎｕａｌＡＣＭＳｙｍｐｏｓｉｕｍｏｎＴｈｅｏｒｙｏｆＣｏｍｐｕｔｉｎｇ、１６９－１７８頁、ＡＣＭＰｒｅｓｓ、２００９年］も参照されたい。Ｇｅｎｔｒｙの構築は現在では使用されていないが、導入された機能の１つである「ブートストラッピング」、特にその実装の１つは、その後提案された方式で広く使用されている。ブートストラッピングは、暗号文のノイズを減らすために使用される技術である。実際、知られているすべてのＦＨＥ方式では、暗号文にはセキュリティ上の理由から必要な少量のランダムノイズが含まれている。ノイジーな暗号文に対して演算を実行すると、ノイズが増加する。所与の数の演算を評価した後、このノイズは非常に高くなり、計算結果を危険にさらす可能性がある。したがって、ブートストラッピングは準同型暗号化方式の構築の基本であるが、この技術は使用メモリまたは計算時間の点で非常に高価である。
【０００６】
Ｇｅｎｔｒｙの公開に続く研究は、準同型暗号化を実際に実行可能にするために、新しい方式を提供し、ブートストラッピングを改善することを目的としている。最も有名な構築はＤＧＨＶ［ＭａｒｔｅｎｖａｎＤｉｊｋ、ＣｒａｉｇＧｅｎｔｒｙ、ＳｈａｉＨａｌｅｖｉ、およびＶｉｎｏｄＶａｉｋｕｎｔａｎａｔｈａｎ、「Ｆｕｌｌｙｈｏｍｏｍｏｒｐｈｉｃｅｎｃｒｙｐｔｉｏｎｏｖｅｒｔｈｅｉｎｔｅｇｅｒｓ」、ＡｄｖａｎｃｅｓｉｎＣｒｙｐｔｏｌｏｇｙ－ＥＵＲＯＣＲＹＰＴ２０１０、ＬｅｃｔｕｒｅＮｏｔｅｓｉｎＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅの第６１１０巻、２４－４３頁、Ｓｐｒｉｎｇｅｒ、２０１０年］、ＢＧＶ［ＺｖｉｋａＢｒａｋｅｒｓｋｉ、ＣｒａｉｇＧｅｎｔｒｙ、およびＶｉｎｏｄＶａｉｋｕｎｔａｎａｔｈａｎ、「（Ｌｅｖｅｌｌｅｄ）ｆｕｌｌｙｈｏｍｏｍｏｒｐｈｉｃｅｎｃｒｙｐｔｉｏｎｗｉｔｈｏｕｔｂｏｏｔｓｔｒａｐｐｉｎｇ」、ＩＴＣＳ２０１２；３ｒｄＩｎｎｏｖａｔｉｏｎｓｉｎＴｈｅｏｒｅｔｉｃａｌＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ、３０９－３２５頁、ＡＣＭＰｒｅｓｓ、２０１２年］、ＧＳＷ［ＣｒａｉｇＧｅｎｔｒｙ、Ｅｄｓ、ＡｍｉｔＳａｈａｉ、ＢｒｅｎｔＷａｔｅｒｓ、「Ｈｏｍｏｍｏｒｐｈｉｃｅｎｃｒｙｐｔｉｏｎｆｒｏｍｌｅａｒｎｉｎｇｗｉｔｈｅｒｒｏｒｓ：Ｃｏｎｃｅｐｔｕａｌｌｙｓｉｍｐｌｅｒ，ａｓｙｍｐｔｏｔｉｃａｌｌｙｆａｓｔｅｒ，Ａｔｔｒｉｂｕｔｅ－ｂａｓｅｄ」、ＡｄｖａｎｃｅｓｉｎＣｒｙｐｔｏｌｏｇｙ－ＣＲＹＰＴＯ２０１３、パートＩ、ＬｅｃｔｕｒｅＮｏｔｅｓｉｎＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅの第８０４２巻、７５－９２頁、Ｓｐｒｉｎｇｅｒ、２０１３年］およびその変形である。第１のＧｅｎｔｒｙの方式でのブートストラッピングの実行は実際には実行可能ではなかったが（計算を完了するには１回の寿命では不十分であった）、引き続いて提案された構築は、あまり実用的ではないが（各ブートストラッピングは数分続く）、この演算を実行可能にした。２０１５年にＤｕｃａｓとＭｉｃｃｉａｎｃｉｏによって、ＧＳＷ型の方式で実行される、より高速なブートストラッピングが提案された［ＬｅｏＤｕｃａｓとＤａｎｉｅｌｅＭｉｃｃｉａｎｃｉｏ、「ＦＨＥＷ：Ｂｏｏｔｓｔｒａｐｐｉｎｇｈｏｍｏｍｏｒｐｈｉｃｅｎｃｒｙｐｔｉｏｎｉｎｌｅｓｓｔｈａｎａｓｅｃｏｎｄ」、ＡｄｖａｎｃｅｓｉｎＣｒｙｐｔｏｌｏｇｙ－ＥＵＲＯＣＲＹＰＴ２０１５、パートＩ、ＬｅｃｔｕｒｅＮｏｔｅｓｉｎＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅの第９０５６巻、６１７－６４０頁、Ｓｐｒｉｎｇｅｒ、２０１５年］：ブートストラッピング演算は０．５秒強で実行される。２０１６年、Ｃｈｉｌｌｏｔｔｉ、Ｇａｍａ、Ｇｅｏｒｇｉａｖａ、およびＩｚａｂａｃｈｅｎｅは、ＴＦＨＥと呼ばれるＦＨＥ方式の新しい変形を提案した［ＩＩａｒｉａＣｈｉｌｌｏｔｔｉ、ＮｉｃｏｌａｓＧａｍａ、ＭａｒｉｙａＧｅｏｒｇｉｅｖａ、およびＭａｌｉｋａＩｚａｂａｃｈｅｎｅ、「Ｆａｓｔｅｒｆｕｌｌｙｈｏｍｏｍｏｒｐｈｉｃｅｎｃｒｙｐｔｉｏｎ：Ｂｏｏｔｓｔｒａｐｐｉｎｇｉｎｌｅｓｓｔｈａｎ０．１ｓｅｃｏｎｄｓ」、ＡｄｖａｎｃｅｓｉｎＣｒｙｐｔｏｌｏｇｙ－ＡＳＩＡＣＲＹＰＴ２０１６、パートＩ、ＬｅｃｔｕｒｅＮｏｔｅｓｉｎＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅの第１００３１巻、３－３３頁、Ｓｐｒｉｎｇｅｒ、２０１６年］。彼らのブートストラッピング技術は、その後の研究の基礎となっている。Ｂｏｕｒｓｅらの研究に言及することができる［ＦｌｏｒｉａｎＢｏｕｒｓｅ、ＭｉｃｈｅｌｅｓＭｉｎｅｌｌｉ、ＭａｔｔｈｉａｓＭｉｎｉｈｏｌｄおよびＰａｓｃａｌＰａｉｌｌｉｅｒ、「Ｆａｓｔｈｏｍｏｍｏｒｐｈｉｃｅｖａｌｕａｔｉｏｎｏｆｄｅｅｐｄｉｓｃｒｅｔｉｓｅｄｎｅｕｒａｌｎｅｔｗｏｒｋｓ」、ＡｄｖａｎｃｅｓｉｎＣｒｙｐｔｏｌｏｇｙ－ＣＲＹＰＴＯ２０１８、パートＩＩＩ、ＬｅｃｔｕｒｅＮｏｔｅｓｉｎＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅの第１０９９３巻、４８３－５１２頁、Ｓｐｒｉｎｇｅｒ、２０１８年］、Ｃａｒｐｏｖら［ＳｅｒｇｉｕＣａｒｐｏｖ、ＭａｌｉｋａＩｚａｂａｃｈｅｎｅおよびＶｉｃｔｏｒＭｏｌｌｉｍａｒｄ、「Ｎｅｗｔｅｃｈｎｉｑｕｅｓｆｏｒｍｕｌｔｉ－ｖａｌｕｅｉｎｐｕｔｈｏｍｏｍｏｒｐｈｉｃｅｖａｌｕａｔｉｏｎａｎｄａｐｐｌｉｃａｔｉｏｎｓ」、ＴｏｐｉｃｓｉｎＣｒｙｐｔｏｌｏｇｙ－ＣＴ－ＲＳＡ２０１９、ＬｅｃｔｕｒｅＮｏｔｅｓｉｎＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅの第１１４０５巻、１０６－１２６頁、Ｓｐｒｉｎｇｅｒ、２０１９年］、Ｂｏｕｒａら［ＣｈｒｉｓｔｉｎａＢｏｕｒａ、ＮｉｃｏｌａｓＧａｍａ、ＭａｒｉｙａＧｅｏｒｇｉｅｖａ、およびＤｉｍｉｔａｒＪｅｔｃｈｅｖ、「Ｓｉｍｕｌａｔｉｎｇｈｏｍｏｍｏｒｐｈｉｃｅｖａｌｕａｔｉｏｎｏｆｄｅｅｐｌｅａｒｎｉｎｇｐｒｅｄｉｃｔｉｏｎｓ」、ＣｙｂｅｒＳｅｃｕｒｉｔｙＣｒｙｐｔｏｇｒａｐｈｙａｎｄＭａｃｈｉｎｅＬｅａｒｉｎｇ（ＣＳＣＭＬ２０１９）、ＬｅｃｔｕｒｅＮｏｔｅｓｉｎＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅの第１１５２７巻、２１２－２３０頁、Ｓｐｒｉｎｇｅｒ、２０１９年］およびＣｈｉｌｌｏｔｔｉら［ＩｌａｒｉａＣｈｉｌｌｏｔｔｉ、ＮｉｃｏｌａｓＧａｍａ、ＭａｒｉｙａＧｅｏｒｇｉｅｖａおよびＭａｌｉｋａＩｚａｂａｃｈｅｎｅ、「ＴＦＨＥ：Ｆａｓｔｆｕｌｌｙｈｏｍｏｍｏｒｐｈｉｃｅｎｃｒｙｐｔｉｏｎｏｖｅｒｔｈｅｔｏｒｕｓ」、ＪｏｕｒｎａｌｏｆＣｒｙｐｔｏｌｏｇｙ、３１（１）、３４－９１頁、２０２０年］。ＴＦＨＥの性能は注目に値する。彼らは、この分野の研究の進歩と準同型暗号をより実用化することに貢献してきた。提案された新しい技術により、ブートストラッピングを数ミリ秒で計算できるようになった。
【先行技術文献】
【特許文献】
【０００７】
米国特許第８６３０４２２号明細書
【非特許文献】
【０００８】
ＣｒａｉｇＧｅｎｔｒｙ、「Ｆｕｌｌｙｈｏｍｏｍｏｒｐｈｉｃｅｎｃｒｙｐｔｉｏｎｕｓｉｎｇｉｄｅａｌｌａｔｔｉｃｅｓ」、４１ｓｔＡｎｎｕａｌＡＣＭＳｙｍｐｏｓｉｕｍｏｎＴｈｅｏｒｙｏｆＣｏｍｐｕｔｉｎｇ、１６９－１７８頁、ＡＣＭＰｒｅｓｓ、２００９年
ＭａｒｔｅｎｖａｎＤｉｊｋ、ＣｒａｉｇＧｅｎｔｒｙ、ＳｈａｉＨａｌｅｖｉ、およびＶｉｎｏｄＶａｉｋｕｎｔａｎａｔｈａｎ、「Ｆｕｌｌｙｈｏｍｏｍｏｒｐｈｉｃｅｎｃｒｙｐｔｉｏｎｏｖｅｒｔｈｅｉｎｔｅｇｅｒｓ」、ＡｄｖａｎｃｅｓｉｎＣｒｙｐｔｏｌｏｇｙ－ＥＵＲＯＣＲＹＰＴ２０１０、ＬｅｃｔｕｒｅＮｏｔｅｓｉｎＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅの第６１１０巻、２４－４３頁、Ｓｐｒｉｎｇｅｒ、２０１０年
ＺｖｉｋａＢｒａｋｅｒｓｋｉ、ＣｒａｉｇＧｅｎｔｒｙ、およびＶｉｎｏｄＶａｉｋｕｎｔａｎａｔｈａｎ、「（Ｌｅｖｅｌｌｅｄ）ｆｕｌｌｙｈｏｍｏｍｏｒｐｈｉｃｅｎｃｒｙｐｔｉｏｎｗｉｔｈｏｕｔｂｏｏｔｓｔｒａｐｐｉｎｇ」、ＩＴＣＳ２０１２；３ｒｄＩｎｎｏｖａｔｉｏｎｓｉｎＴｈｅｏｒｅｔｉｃａｌＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ、３０９－３２５頁、ＡＣＭＰｒｅｓｓ、２０１２年
ＣｒａｉｇＧｅｎｔｒｙ、Ｅｄｓ、ＡｍｉｔＳａｈａｉ、およびＢｒｅｎｔＷａｔｅｒｓ、「Ｈｏｍｏｍｏｒｐｈｉｃｅｎｃｒｙｐｔｉｏｎｆｒｏｍｌｅａｒｎｉｎｇｗｉｔｈｅｒｒｏｒｓ：Ｃｏｎｃｅｐｔｕａｌｌｙｓｉｍｐｌｅｒ，ａｓｙｍｐｔｏｔｉｃａｌｌｙｆａｓｔｅｒ，Ａｔｔｒｉｂｕｔｅ－ｂａｓｅｄ」、ＡｄｖａｎｃｅｓｉｎＣｒｙｐｔｏｌｏｇｙ－ＣＲＹＰＴＯ２０１３、パートＩ、ＬｅｃｔｕｒｅＮｏｔｅｓｉｎＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅの第８０４２巻、７５－９２頁、Ｓｐｒｉｎｇｅｒ、２０１３年
ＬｅｏＤｕｃａｓとＤａｎｉｅｌｅＭｉｃｃｉａｎｃｉｏ、「ＦＨＥＷ：Ｂｏｏｔｓｔｒａｐｐｉｎｇｈｏｍｏｍｏｒｐｈｉｃｅｎｃｒｙｐｔｉｏｎｉｎｌｅｓｓｔｈａｎａｓｅｃｏｎｄ」、ＡｄｖａｎｃｅｓｉｎＣｒｙｐｔｏｌｏｇｙ－ＥＵＲＯＣＲＹＰＴ２０１５、パートＩ、ＬｅｃｔｕｒｅＮｏｔｅｓｉｎＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅの第９０５６巻、６１７－６４０頁、Ｓｐｒｉｎｇｅｒ、２０１５年
ＩＩａｒｉａＣｈｉｌｌｏｔｔｉ、ＮｉｃｏｌａｓＧａｍａ、ＭａｒｉｙａＧｅｏｒｇｉｅｖａ、およびＭａｌｉｋａＩｚａｂａｃｈｅｎｅ、「Ｆａｓｔｅｒｆｕｌｌｙｈｏｍｏｍｏｒｐｈｉｃｅｎｃｒｙｐｔｉｏｎ：Ｂｏｏｔｓｔｒａｐｐｉｎｇｉｎｌｅｓｓｔｈａｎ０．１ｓｅｃｏｎｄｓ」、ＡｄｖａｎｃｅｓｉｎＣｒｙｐｔｏｌｏｇｙ－ＡＳＩＡＣＲＹＰＴ２０１６、パートＩ、ＬｅｃｔｕｒｅＮｏｔｅｓｉｎＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅの第１００３１巻、３－３３頁、Ｓｐｒｉｎｇｅｒ、２０１６年
ＦｌｏｒｉａｎＢｏｕｒｓｅ、ＭｉｃｈｅｌｅｓＭｉｎｅｌｌｉ、ＭａｔｔｈｉａｓＭｉｎｉｈｏｌｄおよびＰａｓｃａｌＰａｉｌｌｉｅｒ、「Ｆａｓｔｈｏｍｏｍｏｒｐｈｉｃｅｖａｌｕａｔｉｏｎｏｆｄｅｅｐｄｉｓｃｒｅｔｉｓｅｄｎｅｕｒａｌｎｅｔｗｏｒｋｓ」、ＡｄｖａｎｃｅｓｉｎＣｒｙｐｔｏｌｏｇｙ－ＣＲＹＰＴＯ２０１８、パートＩＩＩ、ＬｅｃｔｕｒｅＮｏｔｅｓｉｎＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅの第１０９９３巻、４８３－５１２頁、Ｓｐｒｉｎｇｅｒ、２０１８年
ＳｅｒｇｉｕＣａｒｐｏｖ、ＭａｌｉｋａＩｚａｂａｃｈｅｎｅ、およびＶｉｃｔｏｒＭｏｌｌｉｍａｒｄ、「Ｎｅｗｔｅｃｈｎｉｑｕｅｓｆｏｒｍｕｌｔｉ－ｖａｌｕｅｉｎｐｕｔｈｏｍｏｍｏｒｐｈｉｃｅｖａｌｕａｔｉｏｎａｎｄａｐｐｌｉｃａｔｉｏｎｓ」、ＴｏｐｉｃｓｉｎＣｒｙｐｔｏｌｏｇｙ－ＣＴ－ＲＳＡ２０１９、ＬｅｃｔｕｒｅＮｏｔｅｓｉｎＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅの第１１４０５巻、１０６－１２６頁、Ｓｐｒｉｎｇｅｒ、２０１９年
ＣｈｒｉｓｔｉｎａＢｏｕｒａ、ＮｉｃｏｌａｓＧａｍａ、ＭａｒｉｙａＧｅｏｒｇｉｅｖａ、およびＤｉｍｉｔａｒＪｅｔｃｈｅｖ、「Ｓｉｍｕｌａｔｉｎｇｈｏｍｏｍｏｒｐｈｉｃｅｖａｌｕａｔｉｏｎｏｆｄｅｅｐｌｅａｒｎｉｎｇｐｒｅｄｉｃｔｉｏｎｓ」、ＣｙｂｅｒＳｅｃｕｒｉｔｙＣｒｙｐｔｏｇｒａｐｈｙａｎｄＭａｃｈｉｎｅＬｅａｒｉｎｇ（ＣＳＣＭＬ２０１９）、ＬｅｃｔｕｒｅＮｏｔｅｓｉｎＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅの第１１５２７巻、２１２－２３０頁、Ｓｐｒｉｎｇｅｒ、２０１９年
ＩｌａｒｉａＣｈｉｌｌｏｔｔｉ、ＮｉｃｏｌａｓＧａｍａ、ＭａｒｉｙａＧｅｏｒｇｉｅｖａ、およびＭａｌｉｋａＩｚａｂａｃｈｅｎｅ、「ＴＦＨＥ：Ｆａｓｔｆｕｌｌｙｈｏｍｏｍｏｒｐｈｉｃｅｎｃｒｙｐｔｉｏｎｏｖｅｒｔｈｅｔｏｒｕｓ」、ＪｏｕｒｎａｌｏｆＣｒｙｐｔｏｌｏｇｙ、３１（１）、３４－９１頁、２０２０年
ＡｒｅｙＮ．Ｋｏｌｍｏｇｏｒｏｖ、「Ｏｎｔｈｅｒｅｐｒｅｓｅｎｔａｔｉｏｎｏｆｃｏｎｔｉｎｕｏｕｓｆｕｎｃｔｉｏｎｓｏｆｄｙｎａｍｉｃｖａｒｉａｂｌｅｓｂｙｓｕｐｅｒｐｏｓｉｔｉｏｎｏｆｃｏｎｔｉｎｕｏｕｓｆｕｎｃｔｉｏｎｓｏｆｏｎｅｖａｒｉａｂｌｅａｎｄａｄｄｉｔｉｏｎ」、Ｄｏｋｌ．Ａｋａｄ．ＮａｕｋＳＳＳＲ、１１４、９５３－９５６頁、１９５７年
ＤａｖｉｄＡ．Ｓｐｒｅｃｈｅｒ、「Ｏｎｔｈｅｓｔｒｕｃｔｕｒｅｏｆｃｏｎｔｉｎｕｏｕｓｆｕｎｃｔｉｏｎｓｏｆｓｅｖｅｒａｌｖａｒｉａｂｌｅｓ」、ＴｒａｎｓａｃｔｉｏｎｓｏｆｔｈｅＡｍｅｒｉｃａｎＭａｔｈｅｍａｔｉｃａｌＳｏｃｉｅｔｙ、１１５、３４０－３５５頁、１９６５年
Ｐｉｅｒｒｅ－ＥｍｍａｎｕｅｌＬｅｎｉ、ＹｏｈａｎＦｏｕｇｅｒｏｌｌｅ、およびＦｒｅｄｅｒｉｃＴｒｕｃｈｅｔｅｔ、「Ｋｏｍｏｇｏｒｏｖｓｕｐｅｒｐｏｓｉｔｉｏｎｔｈｅｏｒｙａｎｄｉｔｓａｐｐｌｉｃａｔｉｏｎｔｏｔｈｅｄｅｃｏｍｐｏｓｉｔｉｏｎｏｆｍｕｌｔｉｖａｒｉａｔｅｆｕｎｃｔｉｏｎｓ」、ＭａｊｅｃＳＴＩＣ’０８、２００８年１０月２９－３１日、Ｍａｒｓｅｉｌｌｅ、Ｆｒａｎｃｅ、２００８年
Ｂ．Ｆ．ＬｏｇａｎとＬ．Ａ．Ｓｈｅｐｐ、「Ｏｐｔｉｍａｌｒｅｃｏｎｓｔｒｕｃｔｉｏｎｏｆａｆｕｎｃｔｉｏｎｆｒｏｍｉｔｓｐｒｏｊｅｃｔｉｏｎｓ」、ＤｕｋｅＭａｔｈｅｍａｔｉｃａｌＪｏｕｒｎａｌ、４２（４）、６４５－６５９頁、１９７５年
ＡｌｌａｎＰｉｎｋｕｓ、「Ａｐｐｒｏｘｉｍａｔｉｎｇｂｙｒｉｄｇｅｆｕｎｃｔｉｏｎｓ」、Ａ．ＬｅＭｅｈａｕｔｅ、Ｃ．Ｒａｂｕｔ、およびＬ．Ｌ．Ｓｃｈｕｍａｋｅｒ（Ｅｄｓ．）、ＳｕｒｆａｃｅＦｉｔｔｉｎｇａｎｄＭｕｌｔｉｒｅｓｏｌｕｔｉｏｎＭｅｔｈｏｄｓ、２７９－２９２頁、ＶａｎｄｅｒｂｉｌｔＵｎｉｖｅｒｓｉｔｙＰｒｅｓｓ、１９９７年
ＪｅｒｏｍｅＨ．ＦｒｉｅｄｍａｎおよびＷｅｒｎｅｒＳｔｕｅｔｚｌｅ、「Ｐｒｏｊｅｃｔｉｏｎｐｕｒｓｕｉｔｒｅｇｒｅｓｓｉｏｎ」、ＪｏｕｒｎａｌｏｆｔｈｅＡｍｅｒｉｃａｎＳｔａｔｉｓｔｉｃａｌＡｓｓｏｃｉａｔｉｏｎ、７６（３７６）、８１７－８２３頁、１９８１年
Ｄ．Ｓ．ＢｒｏｏｍｈｅａｄとＤａｖｉｄＬｏｗｅ、「Ｍｕｌｔｉｖａｒｉａｂｌｅｆｕｎｃｔｉｏｎａｌｉｎｔｅｒｐｏｌａｔｉｏｎａｎｄａｄａｐｔｉｖｅｎｅｔｗｏｒｋｓ」、ＣｏｍｐｌｅｘＳｙｓｔｅｍｓ、２、３２１－３５５頁、１９８８年
ＯｄｅｄＲｅｇｅｖ、「Ｏｎｌａｔｔｉｃｅｓ，ｌｅａｒｎｉｎｇｗｉｔｈｅｒｒｏｒｓ，ｒａｎｄｏｍｌｉｎｅａｒｃｏｄｅｓ，ａｎｄｃｒｙｐｔｏｇｒａｐｈｙ」、３７ｔｈＡｎｎｕａｌＡＣＭＳｙｍｐｏｓｉｕｍｏｎＴｈｅｏｒｙｏｆＣｏｍｐｕｔｉｎｇ、８４－９３頁、ＡＣＭＰｒｅｓｓ、２００５年
ＤａｍｉｅｎＳｔｅｈｌｅ、ＲｏｎＳｔｅｉｎｆｅｌｄ、ＫｅｉｓｕｋｅＴａｎａｋａ、およびＫｅｉｔａＸａｇａｗａ「Ｅｆｆｉｃｉｅｎｔｐｕｂｌｉｃｋｅｙｅｎｃｒｙｐｔｉｏｎｂａｓｅｄｏｎｉｄｅａｌｌａｔｔｉｃｅｓ」、ＡｄｖａｎｃｅｓｉｎＣｒｙｐｔｏｌｏｇｙ－ＡＳＩＡＣＲＹＰＴ２００９、ＬｅｃｔｕｒｅＮｏｔｅｓｉｎＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅの第５９１２巻、６１７－６３５頁、Ｓｐｒｉｎｇｅｒ、２００９年
ＶａｄｉｍＬｙｕｂａｓｈｅｖｓｋｙ、ＣｈｒｉｓＰｅｉｋｅｒｔ、およびＯｄｅｄＲｅｇｅｖ、「Ｏｎｉｄｅａｌｌａｔｔｉｃｅｓａｎｄｌｅａｒｎｉｎｇｗｉｔｈｅｒｒｏｒｓｏｖｅｒｒｉｎｇｓ」、ＡｄｖａｎｃｅｓｉｎＣｒｙｐｔｏｌｏｇｙ－ＥＵＲＯＣＲＹＰＴ２０１０、ＬｅｃｔｕｒｅＮｏｔｅｓｉｎＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅの第６１１０巻、１－２３頁、Ｓｐｒｉｎｇｅｒ、２０１０年
ＲｏｎＲｏｔｈｂｌｕｍ、「Ｈｏｍｏｍｏｒｐｈｉｃｅｎｃｒｙｐｔｉｏｎ：Ｆｒｏｍｐｒｉｖａｔｅ－ｋｅｙｔｏｐｕｂｌｉｃ－ｋｅｙ」、ＴｈｅｏｒｙｏｆＣｒｙｐｔｏｇｒａｐｈｙ（ＴＣＣ２０１１）、ＬｅｃｔｕｒｅＮｏｔｅｓｉｎＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅの第６５９７巻、２１９－２３４頁、Ｓｐｒｉｎｇｅｒ、２０１１年
ＤａｖｉｄＡ．Ｓｐｒｅｃｈｅｒ、「ＡｎｕｍｅｒｉｃａｌｉｍｐｌｅｍｅｎｔａｔｉｏｎｏｆＫｏｌｍｏｇｏｒｏｖ’ｓｓｕｐｅｒｐｏｓｉｔｉｏｎｓ」、ＮｅｕｒａｌＮｅｔｗｏｒｋｓ、９（５）、７６５－７７２頁、１９９６年
ＤａｖｉｄＡ．Ｓｐｒｅｃｈｅｒ、「ＡｎｕｍｅｒｉｃａｌｉｍｐｌｅｍｅｎｔａｔｉｏｎｏｆＫｏｌｍｏｇｏｒｏｖ’ｓｓｕｐｅｒｐｏｓｉｔｉｏｎｓＩＩ」、ＮｅｕｒａｌＮｅｔｗｏｒｋｓ、１０（３）、４４７－４５７頁、１９９７年
ＪｕｅｒｇｅｎＢｒａｕｎおよびＭｉｃｈａｅｌＧｒｉｅｂｅｌ、「ＯｎａｃｏｎｓｔｒｕｃｔｉｖｅｐｒｏｏｆｏｆＫｏｌｍｏｇｏｒｏｖ’ｓｓｕｐｅｒｐｏｓｉｔｉｏｎｔｈｅｏｒｅｍ」、ＣｏｎｓｔｒｕｃｔｉｖｅＡｐｐｒｏｘｉｍａｔｉｏｎ、３０（３）、６５３－６７５頁、２００７年
【発明の概要】
【発明が解決しようとする課題】
【０００９】
達成した進歩にもかかわらず、暗号文の集合（平文ｘ
１
，…，ｘ
ｐ
に対応）を、平文の所与の関数ｆ（ｘ
１
，…，ｘ
ｐ
）に対応する暗号文に公に変換することが可能な、知られている計算手順は、いくつかの例に限定されているか、非実用的なままである。実際、現在の主な一般的な手段は、ＡＮＤ、ＮＯＴ、ＯＲ、またはＸＯＲ型の論理ゲートで構成されるブール回路の形式でこの関数を表し、次に、関数ｆの入力（平文）を表すビットの暗号文を入力として、この回路を準同型に評価することにある。ブール回路の複雑さの尺度は、計算結果を取得するために計算する必要がある連続するＡＮＤゲートの最大数として定義される、その乗算の深さである。この計算中にノイズを制御し続けるためには、その進行中に規則的にブートストラッピング演算を行う必要がある。上に示したように、最新の技術を使用しても、これらのブートストラッピング演算には複雑な計算が含まれ、乗算の深さが大きいため、計算全体がさらに遅くなる。このアプローチは、バイナリ入力上で演算し、単純なブール回路を有する関数に対してのみ実行可能である。
【００１０】
一般に、評価される関数は、入力として１つ以上の実数値変数ｘ
１
，…，ｘ
ｐ
を取る。実数値変数の集合で評価されるいくつかの関数ｆ
１
，…，ｆ
ｑ
さえあり得る。したがって、暗号文の集合（平文ｘ
１
，…，ｘ
ｐ
に対応）を、平文の複数の実数値関数ｆ
１
，…，ｆ
ｑ
に対応する暗号文の集合に公に変換する前述の演算を迅速に、過度に大規模な計算手段を動員することなく実行できる方法を見つけることには、大きな技術的および経済的関心がある。実際、２００９年にＧｅｎｔｒｙによってなされた理論上の進歩は、この技術的問題に対する効果的な解決策がないため、現在まで実際の具体化は知られていない。本発明が応答を提供するのは、この問題に対するものである。
【課題を解決するための手段】
（【００１１】以降は省略されています）

関連特許