JP7074363B2 - 準同型暗号下での安全な計算を加速するための準同型処理ユニット（ｈｐｕ） - Google Patents

Description

関連出願についての相互参照
本出願は、２０１７年４月１１日に出願された、Ａ ＨＯＭＯＭＯＲＰＨＩＣ ＰＲＯＣＥＳＳＩＮＧ ＵＮＩＴ （ＨＰＵ） ＦＯＲ ＡＣＣＥＬＥＲＡＴＩＮＧ ＳＥＣＵＲＥ ＣＯＭＰＵＴＡＴＩＯＮＳ ＵＮＤＥＲ ＦＵＬＬＹ ＨＯＭＯＭＯＲＰＨＩＣ ＥＮＣＲＹＰＴＩＯＮという名称の米国仮特許出願第６２／４８４，３０４号に対する優先権を主張する通常の出願であり、同仮特許出願全体を参照して本出願に援用する。

本開示は、本明細書においてハードウェアアクセラレータに関し、より詳細には準同型ハードウェアアクセラレータおよび関連方法に関する。

完全準同型暗号化は、サードパーティが、最初にデータを復号化する必要なく、暗号化されたデータ上で計算を実施することを可能にする。暗号化のこの形態は、ユーザが、自分の個人的な暗号化されたデータを例えばリモートサーバ上に保存し、同時に、データ記憶設備が暗号化されたデータを処理することができるようにすることを可能にする。完全準同型暗号化は、クラウドベースのコンピューティング環境に好適である。

データ所有者に関するプライバシーを維持することによって、大きな保証を提供している反面、暗号化されたデータを伴う演算は、それでもなお計算集約型である。

準同型プロセッサチップ、システム、および関連方法が開示される。１つの実施形態では、集積回路（ＩＣ：ｉｎｔｅｇｒａｔｅｄ ｃｉｒｃｕｉｔ）準同型プロセッサチップが開示される。ＩＣ準同型プロセッサチップは、少なくとも１つのプロセッサスライスを含む。各プロセッサスライスは、ローカル制御回路構成、数論変換（ＮＴＴ：ｎｕｍｅｒｉｃ ｔｈｅｏｒｅｔｉｃ ｔｒａｎｓｆｏｒｍ）バタフライユニット、およびオンチップメモリを含む。ＮＴＴバタフライユニットは、準同型暗号を使用して暗号化されたデータ上で演算を行うためのマルチプルモードで動作するためのローカル制御回路構成に応答する。各モードは、ＮＴＴバタフライユニットの異なる構成と関連付けられている。

別の実施形態では、ＮＴＴバタフライユニットは、完全準同型暗号化を伴う演算用のマルチプルモードで動作するためのローカル制御回路構成に応答する。

さらに別の実施形態では、ＮＴＴバタフライユニットは、部分的準同型暗号化を伴う演算用のマルチプルモードで動作するためのローカル制御回路構成に応答する。

別の実施形態では、ＮＴＴバタフライユニット用の第１の構成は、第１の暗号文（Ｃｔｘｔ）関数を実施するために第１の回路構成を使用する。ＮＴＴバタフライユニット用の第２の構成は、第２のＣｔｘｔ関数を実施するために第１の回路構成の少なくとも一部を再利用する。

別の実施形態では、第１の回路構成は、暗号文（Ｃ_ｔｘｔ）加算関数を実施し、一方、第２のＣ_ｔｘｔ関数は、Ｃ_ｔｘｔ乗算関数を備える。

さらに別の実施形態では、第１の回路構成は、モジュラ加算器を含む。

別の実施形態では、モジュラ加算器は、組合せモジュラ加算器を備える。

別の実施形態では、モジュラ加算器は、順次モジュラ加算器を備える。

さらに別の実施形態では、第２の構成は、モジュラ乗算器を備える第２の回路構成を含む。

さらなる実施形態では、モジュラ乗算器は、並列整数乗算器を備える。

別の実施形態では、モジュラ乗算器は、モジュラ約分ユニットをさらに備える。

さらに別の実施形態では、ＩＣ準同型プロセッサは、マルチプルプロセッサスライスを含み、ＩＣ準同型プロセッサは、マルチプルプロセッサスライスを外部プロセッサのインターフェースを介して外部メモリと接続するためのマスタ制御回路構成をさらに含む。

さらに別の実施形態では、ローカル制御回路構成は、１組のＣｔｘｔ係数値をメモリから取り出すようにとの命令をマスタ制御回路構成から受信する。数値の組は、次いで処理パイプラインの中にロードされる。少なくとも１つのＣｔｘｔ演算が、変換値を生成するために行われる。変換値は、次いで転送先メモリ位置に記憶される。

別の実施形態では、マスタ制御回路構成からの命令は、ＮＴＴドメインの中に対応する変換値を生成するために、ロードされた数値の組上でＮＴＴ変換を行うようにとの命令をさらに含む。

さらに別の実施形態では、マスタ制御回路構成からの、少なくとも１つのＣｔｘｔ演算を行うようにとの命令は、加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成るグループから少なくとも１つのＣｔｘｔ演算を行うようにとの命令を含む。

さらに別の実施形態では、ＮＴＴバタフライユニットは、単一ステージユニットとして認識される。

さらなる実施形態では、準同型暗号化システムが開示される。準同型暗号化システムは、集積回路（ＩＣ）準同型プロセッサチップ、およびＩＣ準同型プロセッサチップ外部の主メモリを含む。データパスは、主メモリとＩＣ準同型プロセッサチップとの間でデータを転送する。制御パスは、主メモリとＩＣ準同型プロセッサチップとの間の転送を制御する。ＩＣ準同型プロセッサチップは、マスタ制御回路構成およびマルチプルプロセッサスライスを含む。マスタ制御回路構成は、制御パスを介した主メモリとＩＣ準同型プロセッサチップとの間のデータの転送を制御する。マルチプルプロセッサスライスは、パイプライン深さに対応する。マルチプルプロセッサスライスのそれぞれは、ローカル制御回路構成、数論変換（ＮＴＴ）バタフライユニット、およびオンチップメモリを含む。ＮＴＴバタフライユニットは、準同型暗号化を使用しながら、暗号化されたデータ上で演算を行うためのマルチプルモードで動作するためのローカル制御回路構成に応答する。各モードは、ＮＴＴバタフライユニットの異なる構成と関連付けられている。オンチップメモリは、ローカル制御回路構成およびＮＴＴバタフライユニットに結合されている。

別の実施形態では、準同型暗号化は、完全準同型暗号化を含む。

さらに別の実施形態では、準同型暗号化は、部分的準同型暗号化を含む。

さらに別の実施形態では、マスタ制御回路構成は、マルチプルプロセッサスライスごとに、外部メモリから１組のＣｔｘｔ係数値を取り出して、数値の組を処理パイプラインへロードする動作をスケジュールする。少なくとも１つのＣｔｘｔ演算は、変換値を生成するために行われる。変換値は、次いで転送先メモリ位置に記憶される。

別の実施形態では、マスタ制御回路構成からのスケジュールされた演算は、マルチプルプロセッサスライスごとに、ＮＴＴドメインの中に対応する変換値を生成するために、ロードされた数値の組上でＮＴＴ変換を行う、スケジュールされた演算をさらに含む。

さらに別の実施形態では、マスタ制御回路構成からのスケジュールされた演算は、マルチプルプロセッサスライスごとに、加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成るグループから少なくとも１つのＣｔｘｔ演算を行うスケジュールされた演算をさらに備える。

別の実施形態では、ＮＴＴバタフライユニットのそれぞれは、単一ステージバタフライを備え、所与のＮＴＴ変換演算は、ＮＴＴバタフライユニットによる評価のログ（ｎ）－１ステージを伴い、「ｎ」は、係数値と関連付けられた多項式の次数を表す。

さらに別の実施形態では、数論変換（ＮＴＴ）バタフライ回路が開示される。ＮＴＴバタフライ回路は、第１の加算器／減算器、第１の乗算器、および第１の選択回路構成を含んでいる高入力語パスを含む。第１の選択回路構成は、第１の加算器／減算器および第１の乗算器に結合されており、第１の加算器／減算器および第１の乗算器を選択的に迂回するそれぞれのバイパスパスを含む。ＮＴＴバタフライ回路は、第２の加算器／減算器、第２の乗算器、および第２の選択回路構成を含んでいる低入力語パスを含む。第２の選択回路構成は、第２の加算器／減算器および第２の乗算器に結合されており、第２の加算器／減算器および第２の乗算器を選択的に迂回するそれぞれのバイパスパスを含む。高入力語パスおよび低入力語パスは、交差結合されており、第１および第２の選択回路構成は、異なるモード制御信号に応答して、低入力語パスおよび高入力語パスを異なる論理処理ユニットに再構成する。

さらに別の実施形態では、ＮＴＴバタフライ回路用の第１の構成は、暗号文（Ｃｔｘｔ）加算関数を実施するために、第１の回路構成を使用し、ＮＴＴバタフライ回路用の第２の構成は、Ｃｔｘｔ乗算関数を実施するために、第１の回路構成の少なくとも一部を再利用する。

さらに別の実施形態では、第１および第２の加算器／減算器のそれぞれは、組合せモジュラ加算器を備える。

別の実施形態では、第１および第２の乗算器のそれぞれは、並列整数乗算器を備える。

さらなる実施形態では、第１および第２の乗算器のそれぞれは、モジュラ約分ユニットをさらに含む。

さらに別の実施形態では、第１および第２の加算器／減算器、および乗算器のそれぞれは、関連付けられたクリティカルパスを含んでおり、関連付けられたクリティカルパスのそれぞれは、レジスタ回路構成に囲まれている。

別の実施形態では、ＮＴＴバタフライ回路は、単一ステージバタフライとして認識され、所与のＮＴＴ変換演算は、ＮＴＴバタフライ回路による評価のログ（ｎ）－１ステージを伴い、「ｎ」は、係数値と関連付けられた多項式の次数を表す。

さらに別の実施形態では、準同型プロセッサ集積回路（ＩＣ）チップ内での演算の方法が開示される。方法は、暗号文（Ｃｔｘｔ）記号を数論変換（ＮＴＴ）ドメインに変換することを含む。変換することは、所与のプロセッサスライスに対して、ローカル制御回路構成を用いてモード制御信号を生成することを含む。モード制御信号は、準同型暗号化を伴う演算のマルチプルモードの１つに対応する。ＮＴＴバタフライユニットは、モード制御信号に応答して構成される。

さらに別の実施形態では、準同型暗号化は、完全準同型暗号化を備える。

別の実施形態では、準同型暗号化は、部分的準同型暗号化を備える。

さらに別の実施形態では、モード制御信号は、演算の第１のモードに対応する第１のモード制御信号を備え、ＮＴＴバタフライユニットは、Ｃｔｘｔ加算関数を実施するためにＮＴＴバタフライユニットを構成することによって第１のモード制御信号に応答する。

別の実施形態では、モード制御信号は、演算の第２のモードに対応する第２のモード制御信号を含み、ＮＴＴバタフライユニットが、Ｃｔｘｔ乗算関数を実施するためにＮＴＴバタフライユニットを構成することによって、第２のモード制御信号に応答する。加算関数で利用されたＮＴＴバタフライユニットの一部は、乗算関数を実施するために再利用される。

別の実施形態では、変換することは、各プロセッサスライスが、ローカル制御回路構成のコピーおよびＮＴＴバタフライユニットのコピーを含むように、マルチプルプロセッサスライスを並行して動作させることを含む。

さらに別の実施形態では、方法は、マルチプルプロセッサスライスによって実施されたマルチプル演算をパイプラインで送ることをさらに含む。

さらに別の実施形態では、方法は、マルチプルプロセッサスライスを、外部プロセッサインターフェースを介して外部メモリと接続することをさらに含み、インターフェース接続は、マスタ制御回路構成によって制御される。

さらに別の実施形態では、マスタ制御回路構成は、マルチプルスライスのローカル制御回路構成に対する命令を生成する。ローカル制御回路構成は、メモリから１組のＣｔｘｔ係数数値を取り出すことと、数値の組を処理パイプラインへロードすることと、変換値を生成するために少なくとも１つのＣｔｘｔ演算を行うことと、変換値を外部メモリの中の転送先位置に記憶することとを含むステップを実施するようにという命令に応答する。

別の実施形態では、方法は、ＮＴＴドメインの中に対応する変換値を生成するために、ロードされた数値の組上でＮＴＴ変換を行うことをさらに含む。

さらに別の実施形態では、少なくとも１つのＣｔｘｔ演算は、加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成るグループから選択される。

さらに別の実施形態では、準同型暗号化システム内での演算の方法が開示される。方法は、設定可能な数論変換（ＮＴＴ）バタフライユニットを含んでいる準同型プロセッサ集積回路（ＩＣ）チップを提供することを含む。準同型プロセッサＩＣチップは、データパスおよび制御パスを介して外部メモリとインターフェース接続している。暗号文（Ｃｔｘｔ）記号は、ＮＴＴドメインに変換される。変換することは、所与のプロセッサスライスに対して、ローカル制御回路構成を用いてモード制御信号を生成することを含む。モード制御信号は、準同型暗号化を含む演算のマルチプルモードの１つに対応する。ＮＴＴバタフライユニットは、モード制御信号に応答して構成される。

さらに別の実施形態では、準同型暗号化は、完全準同型暗号化を備える。

さらに別の実施形態では、準同型暗号化は、部分的準同型暗号化を備える。

別の実施形態では、モード制御信号は、演算の第１のモードに対応する第１のモード制御信号を備え、ＮＴＴバタフライユニットは、Ｃｔｘｔ加算関数を実施するためにＮＴＴバタフライユニットを構成することによって第１のモード制御信号に応答する。

さらに別の実施形態では、モード制御信号は、演算の第２のモードに対応する第２のモード制御信号を含み、ＮＴＴバタフライユニットが、Ｃｔｘｔ乗算関数を実施するためにＮＴＴバタフライユニットを構成することによって第２のモード制御信号に応答する。加算関数で利用されるＮＴＴバタフライユニットの一部は、乗算関数を実施するために再利用される。

別の実施形態では、変換することは、各プロセッサスライスが、ローカル制御回路構成のコピーおよびＮＴＴバタフライユニットのコピーを含むように、マルチプルプロセッサスライスを並行して動作させることを含む。

別の実施形態では、方法は、マルチプルプロセッサスライスによって実施されたマルチプル演算をパイプラインで送ることをさらに含む。

さらに別の実施形態では、方法は、マルチプルプロセッサスライスを、外部プロセッサインターフェースを介して外部メモリと接続することをさらに含み、インターフェース接続は、マスタ制御回路構成によって制御される。

別の実施形態では、マスタ制御回路構成は、マルチプルスライスのローカル制御回路構成に対する命令を生成する。ローカル制御回路構成は、メモリから１組のＣｔｘｔ係数数値を取り出すことと、数値の組を処理パイプラインへロードすることと、変換値を生成するために少なくとも１つのＣｔｘｔ演算を行うことと、変換値を外部メモリの中の転送先位置に記憶することとを含むステップを実施するようにという命令に応答する。

別の実施形態では、方法は、ＮＴＴドメインの中に対応する変換値を生成するために、ロードされた数値の組上でＮＴＴ変換を行うことをさらに含む。

さらに別の実施形態では、少なくとも１つのＣｔｘｔ演算は、加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成るグループから選択される。

別の実施形態では、数論変換（ＮＴＴ）バタフライ回路内での演算の方法が開示される。回路は、高入力語パスおよび低入力語パスを含む。高入力語パスは、第１の加算器／減算器、および第１の乗算器を含む。低入力語パスは、第２の加算器／減算器、および第２の乗算器を含む。方法は、第２の加算器／減算器および第２の乗算器を選択的に迂回することと、異なるモード制御信号に応答して、低入力語パスおよび高入力語パスを異なる論理処理ユニットに再構成することとを含む。

さらに別の実施形態では、再構成することは、第１のモード制御信号を受信したことに応答して、暗号文（Ｃｔｘｔ）加算関数を実施するためにＮＴＴバタフライ回路を構成することと、第２のモード制御信号を受信したことに応答して、Ｃｔｘｔ乗算関数を実施するためにＮＴＴバタフライ回路を構成することとを含む。

別の実施形態では、方法は、第１および第２の加算器／減算器ごとに組み合せモジュラ加算器を利用することをさらに含む。

さらに別の実施形態では、方法は、第１および第２の乗算器ごとに並列整数乗算器を利用することをさらに含む。

さらに別の実施形態では、第１および第２の乗算器のそれぞれは、約分ユニットを含み、方法は、それぞれの約分ユニットを動作させることをさらに含む。

別の実施形態では、ＮＴＴバタフライ回路は、単一ステージバタフライとして認識され、変換することは、評価のログ（ｎ）－１ステージを通してＮＴＴバタフライ回路を動作させることを含み、「ｎ」は、係数値と関連付けられた多項式の次数を表す。

さらに別の実施形態では、準同型プロセッサ集積回路（ＩＣ）チップが開示される。ＩＣ準同型プロセッサチップは、少なくとも１つのプロセッサスライスを含む。少なくとも１つのプロセッサスライスは、ローカル制御回路構成、ＮＴＴバタフライユニット、およびオンチップメモリを含む。オンチップメモリは、制御回路構成およびＮＴＴバタフライユニットに結合されて、準同型処理関数用の別々にアクセス可能な記憶ユニットに区分化される。オンチップメモリは、マルチプル入出力（Ｉ／Ｏ：ｉｎｐｕｔ／ｏｕｔｐｕｔ）記憶ユニット、ビット分解多項式記憶ユニット、および回転因子メモリユニットを含む。

別の実施形態では、Ｉ／Ｏ記憶ユニットの第１のユニットは、暗号文（Ｃｔｘｔｓ）を行単位フォーマットで記憶し、Ｉ／Ｏ記憶ユニットの第２のユニットは、Ｃｔｘｔｓを列単位フォーマットで記憶する。

さらに別の実施形態では、Ｉ／Ｏ記憶ユニットの第３のユニットは、第１の記憶ユニットからの第１のＣｔｘｔが第２の記憶ユニットからの第２のＣｔｘｔに乗算されることを伴う乗算演算の結果生じる出力Ｃｔｘｔｓを記憶する。

さらに別の実施形態では、準同型プロセッサ集積回路（ＩＣ）チップは、第２のメモリユニットに結合されたメモリカウンタをさらに含む。

別の実施形態では、Ｉ／Ｏ記憶ユニットの第１のユニットの中の所与の行のＣｔｘｔの単列変換は、Ｉ／Ｏ記憶ユニットの第３のユニットの中の対応する結果的に生じた行になる。

さらに別の実施形態では、マルチプルＩ／Ｏ記憶ユニットの１つは、外部メモリに結合されたピンポンメモリとして構成される。

さらに別の実施形態では、ピンポンメモリは、第１のメモリ演算を実施する第１のサブアレイと、第１のメモリ演算と同時並行の第２の演算を実施する第２のサブアレイとを含む。

別の実施形態では、オンチップメモリは、ＤＲＡＭを備える。

さらに別の実施形態では、準同型プロセッサ集積回路（ＩＣ）チップ内での演算の方法が開示される。方法は、オンチップメモリを、準同型処理関数用の別々にアクセス可能な記憶ユニットに区分化することを含む。オンチップメモリは、マルチプル入出力（Ｉ／Ｏ）記憶ユニット、ビット分解多項式記憶ユニット、および回転因子メモリユニットを含む。少なくとも１つの暗号文（Ｃｔｘｔ）演算は、区分化されたオンチップメモリに結合された、構成可能な数論変換（ＮＴＴ）バタフライユニットを用いて、ロードされた数値の組上で行われる。

別の実施形態では、方法は、ＮＴＴドメインの中に対応する変換値を生成するために、ロードされた数値の組を変換することをさらに含む。

別の実施形態では、少なくとも１つのＣｔｘｔ演算は、加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成るグループから選択される。

さらに別の実施形態では、変換することは、第１の暗号文（Ｃｔｘｔ）をＩ／Ｏ記憶ユニットの第１のユニットから行単位フォーマットで読み込むことと、第２のＣｔｘｔをＩ／Ｏ記憶ユニットの第２のユニットから列単位フォーマットで読み込むこととをさらに含む。

別の実施形態では、変換することは、結果的に生じるＣｔｘｔを生成するために、第１のＣｔｘｔに第２のＣｔｘｔを乗算することと、結果的に生じたＣｔｘｔをＩ／Ｏ記憶ユニットの第３のユニットに書き込むこととをさらに含む。

さらに別の実施形態では、マルチプルＩ／Ｏ記憶ユニットの１つは、ピンポンメモリユニットとして構成されたそれぞれの第１および第２のサブアレイを含む。方法は、第１の演算を実施するために第１のサブアレイを動作させることと、第１の演算と同時並行の第２の演算を実施するために、第２のサブアレイを動作させることとをさらに含む。

別の実施形態では、準同型プロセッサ集積回路（ＩＣ）チップ内での演算の方法が開示される。方法は、行フォーマット読出演算を利用して第１の暗号文（Ｃｔｘｔ）を第１のオンチップメモリユニットから取り出すことを含む。第１のＣｔｘｔは、数論変換（ＮＴＴ）ドメインに変換される。第２の暗号文（Ｃｔｘｔ）は、列フォーマット読出演算を利用して第２のオンチップメモリユニットから取り出される。第２のＣｔｘｔは、ＮＴＴドメインに変換される。変換された第１のＣｔｘｔは、結果として生じるＣｔｘｔを生成するために、変換された第２のＣｔｘｔを乗算される。結果として生じたＣｔｘｔは、第３のメモリユニットの中に記憶される。

開示の実施形態は、類似の参照番号が類似要素を指している添付の図面の図中に例証として、制限を目的とせずに図解されている。

準同型暗号化システムの１つの実施形態を図示する。 図１Ａと類似のシステムの実施形態を図示する。 図１Ａと類似のシステムのさらなる実施形態を図示する。 図１に示す準同型暗号化システムの詳細を図示する。 図２の構成可能なＮＴＴ／ＩＮＴＴユニットの１つの実施形態を図示する。 図２のシステムによって行われた順ＮＴＴ演算のタイミング図を示す。 図２のシステムによって行われた逆ＮＴＴ（ＩＮＴＴ）演算のタイミング図を示す。 乗算および累積演算のタイミング図を図示する。 図６のタイミング図に対応するマトリックス行列乗算演算を図示する。 図２の構成可能なＮＴＴ／ＩＮＴＴユニット用の流れ制御に関するフローチャートの１つの実施形態を図示する。 演算の標準バタフライモードにあるＮＴＴ／ＩＮＴＴユニットの構成を図示する。 演算の加算／減算モードにあるＮＴＴ／ＩＮＴＴユニットの構成を図示する。 演算のマトリックス乗算モードにあるＮＴＴ／ＩＮＴＴユニットの構成を図示する。 演算のコピーモードにあるＮＴＴ／ＩＮＴＴユニットの構成を図示する。 部分的準同型コンテキストの１つの実施形態におけるＮＴＴバタフライユニットの使用を図示する。

ハードウェアアクセラレータおよび関連方法が
開示される。１つの実施形態では、暗号文（Ｃ_ｔｘｔ）記号を数論変換（ＮＴＴ）ドメインに変換するための集積回路（ＩＣ）準同型プロセッサチップが開示される。ＩＣ準同型プロセッサチップは、少なくとも１つのプロセッサスライスを含む。各プロセッサスライスは、ローカル制御回路構成、ＮＴＴバタフライユニット、およびオンチップメモリを含む。ＮＴＴバタフライユニットは、完全同形暗号化を含んでいる演算用のマルチプルモードで動作するためのローカル制御回路構成に応答する。各モードは、ＮＴＴバタフライユニットの異なる構成と関連付けられている。再構成可能なＮＴＴバタフライユニットを利用することによって、異なる関数を達成する別個の回路は、回避されることができ、より効率的なサイクルタイムに寄与する。

図１Ａを参照すると、全体的に１００と称される完全準同型暗号化（ＦＨＥ）システムの１つの実施形態は、集積回路（ＩＣ）準同型処理ユニット（ＨＰＵ）１０２を利用する。ＨＰＵ１０２は、オンチップ暗号文（Ｃｔｘｔ）加算／減算ユニット１０４および乗算器ユニット１０６を含む。数論変換（ＮＴＴ）ユニット１０８は、Ｃｔｘｔ乗算を支援する。１つの実施形態では、加算／減算ユニット１０４、乗算器ユニット１０６、およびＮＴＴユニットは、協働して多機能バタフライユニット２０６を形成する。埋込メモリ１１０は、データを最適様式でコンピューティング機関に送給するために提供される。さらに、システム１００は、機関演算を統制して、外部メモリ１１４への／からのデータ転送を制御するために制御装置１１２を利用する。この全体的なアーキテクチャは、グラフィック処理装置（ＧＰＵ：ｇｒａｐｈｉｃｓ ｐｒｏｃｅｓｓｉｎｇ ｕｎｉｔ）などの、従来型のスキームによって示されるダイ面積の部分を使用することを５７×して現在の最高水準のＧＰＵより速い、準同型演算の計算のための（ＲｉｎｇベースのＦＨＥ暗号化スキームのための）ハードウェア加速を提供するサイクルの正確な準同型処理ユニット（ＨＰＵ）を提供する。

いくつかの実施形態では、多機能バタフライユニット２０６は、用途に応じて、異なる関数を行うために、異なる形態をとることができる。図１Ｂは、多機能バタフライユニット２０６を、ＮＴＴ／ＩＮＴＴユニット１０８、およびさまざまなＣｔｘｔ演算の少なくとも１つを実施するためのＣｔｘｔ演算回路構成１０９を含んでいるように図示している。そのような演算の例は、加算、減算、乗算、ＸＯＲ、ＸＮＯＲ、ＡＮＤ、等価、より小さい、より大きい、実体、コピー、および否定を含む。

図１Ｃに図示される１つの実施形態では、多機能バタフライユニット２０６は、上述した多様なＣｔｘｔ演算の少なくとも１つを実施するためのＣｔｘｔ演算回路構成１０９を含む。

図２は、図１に示すシステムに対応している、全体的に２００と称されるＦＨＥシステムの１つの特定の実施形態のさらなる詳細を図示する。システム２００は、処理速度および効率を最大にするために並行して動作することができる論理２０２ａ～２０２ｎのマルチプル「スライス」で形成された特定用途向け集積回路（ＡＳＩＣ：ａｐｐｌｉｃａｔｉｏｎ ｓｐｅｃｉｆｉｃ ｉｎｔｅｇｒａｔｅｄ ｃｉｒｃｕｉｔ）などの集積回路（ＩＣ）チップ２０１を含む。２０２ａなどでの各スライスは、多機能ＮＴＴバタフライユニット２０６を備えた準同型処理ユニット（ＨＰＵ）コアブロックを画定している。多機能バタフライユニット２０６は、再構成可能であり、ローカル制御ユニット２０８の形態をした分散された制御論理によって制御される。内部埋込記憶アーキテクチャ２１０は、大いに縮小されたフットプリントを呈し、一方同時に呼出し時間を最小化している。外部メモリ２１２は、データパス２１４および制御パス２１６を介してＨＰＵコアスライス２０２とインターフェース接続している。制御パス２１６は、グローバルレベルでシステム２００の演算を統制するためのマスタ制御ユニット２１８を含む。

さらに図２を参照すると、ＨＰＵコアスライス２０２は、大いに簡略化されたマスタ制御ユニット２１８を用いて、より大きいシステムの集積を簡単なタスクにするために、実質的に拡張可能であることができる。「Ｐｏｒｔ１Ｌ」、「Ｐｏｒｔ１Ｈ」および「Ｐｏｒｔ２Ｌ」および「Ｐｏｒｔ２Ｈ」などのコア入出力（Ｉ／Ｏ）は、各ＨＰＵコアスライス２０２の両側に構成される。「Ｈ」および「Ｌ」ポートは共に、ＨＰＵコアスライスに対する入出力ポートであることができる。ＮＴＴ－ドメインデータを暗号文データに変換する逆数論変換（ＩＮＴＴ：ｉｎｖｅｒｓｅ ｎｕｍｅｒｉｃ ｔｈｅｏｒｅｔｉｃ ｔｒａｎｓｆｏｒｍ）エンジンが、ＮＴＴハードウェアと類似のハードウェアを、しかしながらインプレース水平フリッピングを用いて使用することができるので、このことは、有利である。事実上、出力ポートが、入力ポートとして、逆もまた同様に使用される場合、同ＮＴＴ機関は、ＩＮＴＴ関数を計算することができる。これは、さらに、ＮＴＴ機関用のルーティング資源を半分だけ削減し、このことは、それに応じて、設計面積および消費電力を最小化する。

さらに図２を参照すると、内部埋込メモリ２１０が、ＨＰＵコアスライス２０２を、全体的チップフットプリントおよび処理呼出し時間を最小化する様式で効率的にロードするために、提供されている。１つの実施形態では、内蔵メモリ２１０は、オンチップメモリの量を最小化するだけでなく、さらにシステム中の処理呼出し時間を最小化する様式で区分化されている。概括的には、区分化は、入出力（Ｉ／Ｏ）記憶用の４つのメモリユニットＭｅｍ０（２２０）、Ｍｅｍ１（２２２）、Ｍｅｍ２（２２４）、およびＭｅｍ３（２２６）、「ビット分解」（ＢＤ：ｂｉｔ ｄｅｃｏｍｐｏｓｅｄ）多項式の一時記憶用の１つのメモリユニット２２８、および回転因子メモリユニット２３０を伴う。１対のシフトレジスタ２３２および２３４は、メモリユニット２２０、２２２、２２４、および２２６に接続されており、マルチプレクサＭ３およびＭ４を介してＨＰＵ高および低入力に選択的に結合されている。Ｍｅｍ０などの、４つのＩ／Ｏメモリユニットの１つは、暗号文ロードと関連付けられる遅延を外部メモリ２１２から効果的に隠すために、デュアルバッファ「ピンポン」メモリとして構成されることができる。いくつかの実施形態では、回転因子メモリユニット２３０は、ピンポン方位にさらに構成されることができる。

暗号文ロード遅延を補償するのにさらに役立つために、外部メモリ２１２を用いた内蔵メモリ２１０を接続するデータパス２１４は、Ｃｔｘｔロード命令用のクロックサイクルの数が、例えば加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、否定演算などのＣｔｘｔ演算に限定されないＣｔｘｔ演算を実施するクロックサイクルの数より小さいという条件を満たす幅を有することができる。クロックサイクル毎にデータパスに新しいデータを供給することによって、性能をさらに改善するために、１つの実施形態では、外部メモリインターフェースは、さまざまなＤＤＲＸおよび／またはＧＤＤＲＸメモリ規格のいずれか１つの下で画定されるような、高速ダイナミックランダムアクセスメモリ（ＤＲＡＭ）を利用する。記憶アーキテクチャによって実施されるさまざまな方法を含む、システムの演算が、下文にさらに記載される。

図３は、図２のＮＴＴバタフライユニット２０６に対応する、全体的に３００と称される、多機能バタフライユニットの１つの特定の実施形態を図示する。一般に、多機能バタフライユニット３００は、暗号文（Ｃ_ｔｘｔ）を数論変換（ＮＴＴ）に変換するための回路構成を提供する。ある実施形態では、さらに、ユニットは、ＮＴＴを暗号文に変換して戻すＩＮＴＴ機関の役割をすることができる。一般的には、数論変換（ＮＴＴ）は、離散的フーリエ変換（ＤＦＴ：ｄｉｓｃｒｅｔｅ Ｆｏｕｒｉｅｒ ｔｒａｎｓｆｏｒｍ）の有限フィールド等価物である。ＮＴＴは、次数ｎ多項式用のＯ（ｎ^２）からＯ（ｎｌｏｇ（ｎ））まで多項式乗算の計算費用を削減する。

さらに図３を参照すると、必須ビルディングブロックとして、多機能バタフライユニット３００は、バタフライトポロジに配列された２つのモジュラ加算器３０２および３０４と、２つのモジュラ乗算器３０６および３０８とを一般的に含む。モジュラ加算器は、用途に応じて、組合せ的であっても、または順次式であってもよい。一般的に言って、単一基数－２バタフライは、以下の一般的公式を有する：

上式において、Ｔ_ＬおよびＴ_Ｈは回転因子と呼ばれ、ｑはモジュラスである。

１つの実施形態では、ＮＴＴバタフライユニット３００は、ＦＨＥ暗号化で利用されるマルチプル関数を達成するために、再構成可能性およびさまざまな論理ブロックの再使用を提供する。したがって、ＮＴＴバタフライユニット３００は、モジュラ加算器／減算器論理３０２および３０４、ならびにモジュラ乗算器論理３０６および３０８を含む。モジュラ加算器／減算器ユニットは、一般的には、２つの部分、正規の加算／減算ユニットと、それに続くモジュラ約分ユニットとで構成される。モジュラ約分演算は、結果が、加算の場合にモジュラスｑより多いのか、または減算の場合には、０より小さいのかを調べて、それに応じて結果を調整する。いくつかの実施形態では、キャリールックアヘッド、並列プレフィクス、条件付きサム、またはキャリースキップの加算器のような並列加算器が、利用され得る。

さらに図３を参照すると、モジュラ乗算器３０６および３０８のそれぞれは単一のユニットとして、またはその後にモジュラ約分ユニットが続く整数乗算器として構成されることができる。モジュラ約分ユニットは、バレットモジュラ約分ユニット、特別なプライムモジュラ約分ユニットの形をしていても、またはモンゴメリーモジュラ乗算ユニットなどの、両方のユニットを１つにした単一のユニットとしていてもよい。モジュラ乗算器が、特定の実施形態において何度も繰り返される可能性がある、多機能バタフライの大部分を占めているので、特定の実施例は、特定のコンテキストにおいて、他より望ましい可能性がある。１つの実施形態では、特別なプライムをＳｏｌｉｎａｓプライムからのモジュラスと共に使用することは、ｑ＝２^ｌ－２^ｄ＋１で、都合よく機能し、ここでは、ｌ＝３１、ｄ＝１７であり、ｑは、モジュラスを表している。システムの性能を改善するために、並列整数乗算器が、利用されることができる。上で画定されたパラメータでは、整数乗算器は、結果的に２ｌ＝６２ビットの出力幅になる。これは、ｌの数値の２倍であり、これは、次いで約分ユニットによって約分されて３１ビットに戻される。

引き続き図３を参照すると、多機能バタフライユニット３００は、さまざまな加算／減算／乗算／コピー、および他のコンピューティング関数に関する論理再使用を効率的に可能にするために、上述した概念的モジュラ加算器およびモジュラ乗算器を、演算の特定のモードにおいて選択可能に交差結合されるそれぞれの低処理パスおよび高処理パス３１０および３１２に組み込んでいる。低処理パス３１０は、マルチプレクサＭ０、およびレジスタＲ０およびＲ８を含む論理の第１ステージを含む。マルチプレクサＭ０は、バタフライに提供される第１の入力ＩｎＬ、および加算器／減算器３０２からフィードバックされた第２の入力を受信する。レジスタＲ０は、Ｍ０から選択された出力を受信し、その一方で、レジスタＲ８は、第２の入力Ｉｎａｄｄ＿Ｌを受信する。レジスタＲ０およびＲ８は、ＮＴＴ演算用の低入力信号をパイプラインで送るために、ラッチまたはレジスタの第１ステージを提供する。加算器／減算器３０２は、実施されている関数に応じて、ローカル制御論理によって選択されたさまざまな入力を受信する。加算器／減算器３０２へのさまざまな入力は、レジスタＲ０からの出力およびレジスタＲ８から生じたＭ２からの選択された出力、または乗算器３０６からのフィードバック、またはレジスタＲ１から（対応する高パス３１２から）の交差結合出力を含むことができる。

さらに図３を参照すると、加算器／減算器３０２からの出力は、マルチプレクサＭ４の１つの入力を含む乗算パスを送給する。バイパスパス３１４は、加算／減算出力を、出力マルチプレクサＭ６に、さらにフィードバックパス３１６に沿って入力マルチプレクサＭ０に送給する。乗算器マルチプレクサＭ４は、入力Ｉｎ_Ｌを、加算／減算器パスを迂回して、乗算器パスに直接接続するバイパスパス３１８からの第２の入力を含む。第２ステージレジスタＲ２は、Ｍ４から選択された出力を受信して、それを乗算器３０６に提供する。回転因子入力は、さらに、入力Ｔ_Ｌを介してレジスタＲ４を通って乗算器３０６に適用されることができる。乗算器３０６の出力は、次いで出力マルチプレクサＭ６に送給されることができ、選択的な入力に関して、マルチプレクサＭ２に向かうパス３２０に沿って加算器／減算器３０２にフィードバックされ得る。第３ステージレジスタＲ６は、マルチプレクサＭ６から選択された出力を受信して、出力パッドＯｕｔ_Ｌに処理した出力を送給する。

引き続き図３を参照すると、第１ステージレジスタＲ１およびＲ９が、レジスタＲ０およびＲ８と同期して動作し、類似のパイプラインで送られたタイミングが、レジスタＲ３／Ｒ２とＲ７／Ｒ６との間で実施されて、上述した低パス３１０は、高パス３１２によって複製されることができる。上記したように、低パスおよび高パス３１０および３１２は、レジスタＲ０とマルチプレクサＭ３との間で、そしてレジスタＲ１とマルチプレクサＭ２との間で交差結合される。交差結合は、下文でさらに詳細に記載されるように、演算の特定のモードに関して、バタフライの利用可能な論理の機能的再構成可能性および再使用可能性を提供する。

演算では、図２のＦＨＥシステム２００は、Ｃｔｘｔ加算、Ｃｔｘｔ減算、Ｃｔｘｔ乗算、およびＮＴＴ／ＩＮＴＴ処理を含む計算を実施する。いくつかの実施形態では、さらに平文計算を実施する場合もある。特定の演算が、下文でさらに十分に説明されるように、スケジュールされて、処理される様式は、呼出し時間を最小化することによって、性能を大幅に向上させ、一方で、ＩＣチップフットプリントを大いに縮小させることに寄与する。

図４は、図２のシステムによって実施される一般的な演算のいくつかと関連付けられるさまざまなタイミングを示すタイミングチャートを図示する。演算のグループが、示されており、各グループは、利用されるパイプラインの奥行に応じて、ＨＰＵ論理のマルチプル「スライス」によって反復的に実施されるいくつかの同一の計算を伴う。クロックサイクルタイムは、左から右に進んで、ｘ軸に沿って反映されており、各六角形の演算記号は、単一のクロックサイクルで実施される演算を表す。

さらに図４を参照すると、暗号文のＮＴＴドメインへの変換を伴う、順ＮＴＴ演算の例として、３つの主な処理関数が、実施される：（１）ロードして、定数を乗算する、（２）ＮＴＴ、および（３）最終的なＮＴＴおよび記憶する。４０２に示される、第１の演算（ロードして、定数で乗算する）は、一般的には、４０４などで、ＨＰＵコアブロックパイプラインが充填されるまで、内蔵メモリからマルチプル多項式を読み込んで、４０６などで、それらに定数値を乗算する。出力は、次いで、４０８などで出力ポートに送られる。メモリから要素を読み取るように示される２サイクルは、メモリからコンテンツを得る１サイクルと、その後に続く、図２の低シフトレジスタおよび高シフトレジスタ２３２および２３４用の別のサイクルとで構成されることに留意されたい。このステージでの多項式当たりの遅延は、メモリ演算からロードするために２つのクロックサイクルを加えたパイプライン深さに等しい。

引き続き図４を参照すると、４１０に示されるＮＴＴ演算は、それ自体が、パイプラインの中のロードされた多項式上に繰り返し適用され、評価のｌｏｇ_２（ｎ）－１ステージを行う。このステージでの多項式当たりの遅延は、パイプライン深さに相当する。次いで、４１２で最終的なＮＴＴ演算が、行われ、その後、結果は、４１４で転送先メモリに戻って記憶される。「新規ＮＴＴの開始」という標識で示されるように、その前の計算が、依然としてパイプラインの中にある一方で、多項式の新しい組のロードおよび変換が始まるので、この最終ステージでの多項式当たりの有効遅延は、２つのクロックサイクルを引いたパイプライン深さに相当する。３つの主な処理関数は、Ｃｔｘｔの中のすべての多項式が変換されるまで、繰り返される。逆ＮＴＴ（ＩＮＴＴ）変換の場合、主な処理関数は、定数乗算演算が、バタフライ演算の後行われること以外は、同様に実施される。

図５は、図４のＮＴＴ演算と同様に実施されるＩＮＴＴ演算の例に関するタイミングを図示する。ＩＮＴＴ関数をスケジューリングすることにおいて、３つの主な演算が、行われる：（１）５０２で、ＩＮＴＴをロードして、行う、（２）５０４で、ＩＮＴＴを行う、および（３）５０６で、定数で乗算して、記憶する。

図４が順ＮＴＴ演算の例に関するタイミングを図示するのに対して、図６は、２つの暗号文、Ｃｔｘｔ_１およびＣｔｘｔ_２の乗算を伴う暗号文乗算演算に関するタイミングチャートを図示する。処理の間、以下の３つの主な処理関数が実施される。（１）６０２では、第１の多項式のビット分解のためのＮＴＴ、（２）６１４では、第２の多項式のビット分解のためのＮＴＴ、および（３）６１８では、乗算して累算する。

さらに図６を参照すると、６０２で、第１の多項式のビット分解のためのＮＴＴは、６０４でのように、メモリから第１の暗号文Ｃｔｘｔ１と関連付けられた多項式を読み込むことから始まる。６０６では、多項式の中の各整数の最下位ビットが、次いで、バタフライユニットに出力される。それに続くＬＳＢ出力は、高シフトレジスタおよび低シフトレジスタの数値のシフトを伴う。６１０では、ＮＴＴ変換が、（６０８で、バタフライの加算論理を迂回した後）６１２での定数演算および結果の出力による乗算を含む最下位ビットに関して始まる。

引き続き図６を参照すると、６１２で、第１のＢＴＴビット分解の結果が出力されると、６１４で、第２の多項式ステップのＮＴＴ分解が、始まる。第２の暗号文Ｃｔｘｔ_２と関連付けられた多項式は、次いで、６１６でのようにメモリから読み込まれることができ、第１の暗号文Ｃｔｘｔ_１が処理された方法と同様に処理される。

乗算および累算演算を含む第３のステップでは、６１８で、Ｃｔｘｔ_１の変換された行およびＣｔｘｔ_２の変換された列を処理して、結果として生じるＣｔｘｔ_３の要素を計算する。これは、マトリックス乗算表を用いて図７に図解されており、７０２では、上左端マトリックスは、Ｃｔｘｔ_３を表し、一方で、７０４では、中間マトリックスは、Ｃｔｘｔ_１を表し、７０６では、右端マトリックスは、Ｃｔｘｔ_２を表している。図６の６１８での第３のステップ、乗算および累算は、Ｃｔｘｔ_１の別の行を変形して、Ｃｔｘｔ_３結果を計算するために、上述した同じ乗算関数を繰り返す前に、Ｃｔｘｔ_３の行を計算するために、２回繰り返される。

１つの実施形態では、メモリコンテンツは、Ｃｔｘｔの行に沿った要素が、次の行に進む前に最初に読み込まれるように、メモリの内部に配置される。図７は、７０４でのＣｔｘｔ_１、および７０２でのＣｔｘｔ_３の要素は、正規順序で行に沿って読み込まれ、他方で、７０６でのＣｔｘｔ_２の要素は、列に沿って読み込まれることを示す。これは、異なる順序で要素を再配置すること、またはこの状況を説明するためにメモリカウンタを利用することを伴う。１つの実施形態は、偶数および奇数のステップをカウントするメモリカウンタを利用する。７０６で、Ｃｔｘｔ_２の第１の列を読み込むために、偶数のカウンタが、最初に起動されて、すべての列要素が読み込まれ、次いで、奇数のカウンタが、起動されて、第２の列の要素を取ってくる。

上述した、図６および図７に示された演算は、Ｃｔｘｔ_１の特定の行は、Ｃｔｘｔ_３の第１の行を作成するのに、２回だけ必要であることを反映している。これは、Ｃｔｘｔ_１のビット分解バージョンを記憶することができる容量の全メモリは、不必要であることを意味する。そのかわりに、１回に単列が、Ｃｔｘｔ_３の対応行を計算するために、変換されることができる。その結果、内部埋込メモリの量は、最小化されて、集積回路チップの対応するフットプリントを大いに縮小することができる。

図８は、上の記述に合った、さまざまな暗号文および平文関数を達成するために、図２に示される特定のメモリアーキテクチャによって実施されるステップのフローチャートを図解する。一般的には、システム２００によって使用される準同型暗号化は、以下の一般方程式を実施することを可能にする：

上式では、Ｃ_ｉｊｋは、異なる暗号文を表し、Ｐ_ｉｊｋは、平文を表す。図２の内蔵メモリの一部は、上記の方程式と関連付けられる部分結果を記憶するように構成される。

さらに図２および図８を参照すると、図２のシステムによって利用される流れ制御方法は、ピンポンメモリをうまく活用して、下位メモリユニットでデータを処理して、一方で、デュアルバッファの使用と同様に、他の下位メモリユニットをロードする。これは、上記の一般方程式を効率的に満足するのに役立つ。流れ制御方法は、８０２で、データパス２１４を介して外部メモリ２１２からデータをピンポン下位メモリユニットの１つにロードすることから始まる。８０４では、ピンポンメモリのコンテンツは、次いでＭｅｍ２などの他の埋込メモリの１つにコピーされる。コンテンツをコピーした後、８０６では、ピンポンメモリは、外部メモリ２１２からデータを再ロードされ、８０８では、ピンポンメモリ選択は、切り替えられる。

さらに図８を参照すると、８０８で、ピンポンメモリ選択を切り替えた後、流れ制御は、２つの並列パスに沿って進む。パスのうちの第１のパスは、８１０で外部メモリからピンポンメモリの１つをロードし、次いで、８２４でメモリ選択を切り替えることを伴う。

引き続き図８を参照すると、上記の第１のパスによって実施されるステップと同時並行の、第２のパスは、８１２でＮＴＴ関数をピンポンメモリのその他のコンテンツに適用することを伴う。次いで、ＮＴＴビット分解演算は、８１４で、Ｍｅｍ２の２つのラインおよびＭｅｍ３の中に記憶された累算演算の結果に適用される。８１６では、ピンポンメモリおよびＭｅｍ３は次いで乗算され、結果が、Ｍｅｍ２の同じ２つのラインに戻して記憶される。８１８では、次いで、２ｌの繰返しが行われたかどうかが判定される。行われていなかった場合には、ＮＴＴビット分解および乗算ステップが、再び行われる。２ｌの繰返しが行われるまで、サブループが繰り返し適用される。閾値が満たされると、次いで、８２０では、逆ＮＴＴ演算が、Ｍｅｍ２のコンテンツに適用される。

８２０でＩＮＴＴ演算が適用されると、並列する流れパスは、単一パスに戻り、８２４では、ピンポンメモリ選択が、再び切り替えられる。次いで、８２６では、「Ｋ」暗号文が乗算されたかどうかに関して判定される。乗算されていなかった場合には、８１２では、ＮＴＴ演算が、ピンポンメモリに適用され、ステップ８１４～８２４が繰り返される。「Ｋ」暗号文が乗算されていた場合には、８２８では、結果が、Ｍｅｍ４に追加される。８３０では、アルゴリズムが完了されるかどうかに関して判定される。追加的な処理が必要とされる場合には、ステップ８０４～８３０が繰り返される。そうでない場合、流れは、特定の組のデータに関して終了する。

図９～図１２は、図３の多機能バタフライユニットが、上述したように、Ｃｔｘｔ加算、減算、乗算、およびＮＴＴ／ＩＮＴＴ変換を含む計算関数を可能にするためにさまざまな方法でどのように構成され得るのかを図示する。

図９は、演算の規格バタフライモード（太いパスによって示される）用に構成された図３の多機能バタフライユニットを図示する。構成を画定している接続部は、以下の一般公式を実施する、制御論理によってディスパッチされた制御信号に応答している。

これは、各マルチプレクサの出力に移動するある特定の入力の選択を可能にするために、適切な制御信号を生成して、マルチプレクサＭ０～Ｍ７のそれぞれへ適用することによって達成される。その結果、低パス３１０では、Ｍ０は、信号ＩｎＬをＲ０への入力として通す。Ｒ０の出力は、減算器として構成される高パス加算器／減算器３０４への入力としてＭ３を通して送給されることになる。Ｒ０出力は、さらに、加算器として構成される低パス加算器／減算器３０２への入力に送給される。加算器３０２の出力は、Ｒ２への入力として、Ｍ４によって通される。Ｒ２の出力は、低パス乗算器３０６に送給される。回転因子ＴＬは、Ｒ４への入力として送給され、一方で、Ｒ４の出力は、乗算器３０６への第２の入力として送給される。乗算器３０６の出力は、Ｒ６への入力として、Ｍ６を通して送給される。Ｒ６の出力は、低パス３１０用の結果として生じる出力ＯｕｔＬになる。高パス３１２も、同様に構成されるが、簡潔にするために、各接続部の詳細な説明は省略する。

図１０は、以下の一般公式を実施する演算の加算／減算モード用に構成された多機能バタフライユニット３００を図示する：

制御論理によって発せられる制御信号は、したがって、規格バタフライモードに類似しているけれども、低パスおよび高パス３１０および３１２が、モジュラ乗算器３０６および３０８を通常迂回するように、バタフライユニット３００にマルチプレクサを設定している。低パスおよび高パス３１０および３１２は、さらに、交差結合を実施しない。そのうえ、加算／減算モードでは、追加的な入力Ｉｎ_{ａｄｄ＿Ｌ}およびＩｎ_{ａｄｄ＿Ｈ}は、レジスタＲ８およびＲ９を介してモジュラ加算器／減算器ユニット３０２および３０４のそれぞれに供給される。

図１１は、以下の一般公式を実施する演算のマトリックス乗算モード用に構成された、多機能バタフライユニット３００を図示する：

この構成は、加算器としてモジュラ加算器／減算器ユニット３０２および３０４と、パスを交差結合していない低パスおよび高パス３１０および３１２両方の乗算器ユニット３０８および３０６とを利用する、乗算および累算関数を実現する。低パス３１０は、Ｒ４を介して供給される回転因子入力Ｔ_Ｌと乗算するためにＭ４を介してレジスタＲ２に入力Ｉｎ_Ｌを供給することを伴う。加算器３０２は、Ｍ２を介して乗算器３０６の出力と、さらにＭ０を介してＲ０にフィードバックされる自体の出力とを受信する。加算器出力は、Ｍ６を通ってＲ６に送給され、それは、出力Ｏｕｔ_Ｌとして示されている。高パス３１２も、同様に構成される。

図１２は、以下の一般公式を実施する演算のコピーモード用に構成された、多機能バタフライユニット３００を図示する：

本質的には、コピーモードは、ただ入力Ｉｎ_ＬおよびＩｎ_Ｈを通って直接出力Ｏｕｔ_ＬおよびＯｕｔ_Ｈに移動する際に、モジュラ加算器／減算器３０２および３０４、およびモジュラ乗算器を迂回することを伴う。

上述したＦＨＥシステムは、付随するハードウェア資源として、サードパーティデータを処理する必要があり得る一般的なコンピューティングプラットホームおよび／またはサーバプラットホームに好適である。そのような環境では、１つまたは複数のＨＰＵ集積回路チップは、サーバ演算と並列して行われることができる集中的な準同型処理タスクを実施するために、コプロセッサまたはハードウェアアクセラレータとして１つまたは複数のサーバユニットの中に据え付けられることができる。ＨＰＵがそのような特定のタスクを処理するように構成されている場合、サーバ処理資源は、サーバ特有のタスクに対して保存されるおよび／または開放されることができる。

本開示は、これまで主として完全な準同型のコンテキストで実施形態を論じてきたが、本明細書に示されるさまざまな概念は、同様に部分的準同型のコンテキストにおいても利用されることができる。一例として、高スループット適用に関して、Ｐａｉｌｌｉｅｒ暗号化システムのような、部分的準同型暗号化システムをサポートするために、現在提案されている設計に付加的な再構成可能度を追加することが可能である。Ｐａｉｌｌｉｅｒ暗号化システムのような、これらの部分的準同型暗号化スキームは、通常、例えばＳｃｈｏｎｈａｇｅ－Ｓｔｒａｓｓｅｎ、Ｋａｒａｔｓｕｂａ、またはＴｏｏｍ－Ｃｏｏｋアルゴリズムを用いて実施されることができる大きな整数乗算器を伴う。普遍性を失わずに、これらのアルゴリズムを上述したＨＰＵハードウェアへインスタン化する一例として、Ｓｃｈｏｎｈａｇｅ－Ｓｔｒａｓｓｅｎアルゴリズムは、高速整数乗算を行うのに高速多項式乗算を使用する。２つの入力数字「ａ」および「ｂ」に大きい整数乗算を行うために、アルゴリズムの結果としておそらく生じる可能性がある最大整数を最初に計算し、次いで、オーバフローを回避するために、この最大である可能性のある結果より大きい整数「ｗ」を選択する。その後、以下の通りに「ａ」および「ｂ」を「ｗ」ビットの「ｍ」グループに分割する：

ｘ＝２^ｗにすると、次いで、前の方程式は、同等になる。

次いで、以下のように述べることができる。

上記の方程式は、本明細書に記載され、図１３の部分的準同型コンテキストに示される数論変換（ＮＴＴ）機関などのＮＴＴユニットを用いて、効率的に計算されることができる。入力数字「ａ」および「ｂ」は、ＮＴＴユニット１３０２および１３０４のそれぞれに送給される。数字は、１３０６で乗算演算を受け、その後１３０８で、ＩＮＴＴ演算が続く。次いで、結果「ｃ」を達成するために、１３１０でキャリー演算が行われる。

上述したＳｃｈｏｎｈａｇｅ－Ｓｔｒａｓｓｅｎアルゴリズムは、入力整数を、各部分が、隣接する多項式係数の中に記憶されるより小さい部分に区分化することによって、本明細書に記載されるＮＴＴ機関を使用して効率的に実施されることができる。その後、ＮＴＴ変換は、両方の多項式上に適用されることができ、係数に関する乗算は、変換された多項式上で行われる。最終的に、結果は、変換されて係数表示に戻されて、最終的なキャリー伝播が行われることになる。

そのような実施例は、広範囲にわたる重要な適用、例えば、安全な投票システム、ブロックチェーン、安全な契約、特定の分散計算（ＭＰＣ：ｍｕｌｔｉ－ｐａｒｔｙ ｃｏｍｐｕｔａｔｉｏｎ）アルゴリズム、および暗号の通用性で見つけられるものを加速することに有用性を見い出すことになる。

当業者には理解されるように、上述したアーキテクチャは、単一の集積回路チップ上で準同型暗号化処理関数を実施する計算時間をかなり短縮する。さらに、効果的なメモリ使用量によって、チップのサイズおよび電源消費が、最小化される。

１つまたは複数のコンピュータ可読媒体を介してコンピュータシステムの中で受信されるとき、上述された回路のそのようなデータおよび／または命令ベース表現式は、そのような回路の物理的発現の表示または画像を生成するために、ネットリスト生成プログラム、場所およびルートプログラム、および類似のもの、これらに限定するわけではないが、を含む、１つまたは複数の他のコンピュータプログラムの実行と関連したコンピュータシステムの中で、処理エンティティ（例えば１つまたは複数のプロセッサ）によって処理されることができる。そのような表示または画像は、その後、例えば、デバイス製造プロセスにおいて回路の各種構成要素を形成するのに使用される１つまたは複数のマスクの生成を可能にすることによって、デバイス製造で使用されることができる。

前述の説明の中で、そして添付の図面において、特定の用語および図面記号が、本発明の十分な理解を提供するために示されてきた。いくつかの例では、用語および記号は、本発明を実施するのに必要とされない具体的な詳細を包含する場合もある。例えば、ビットの固有番号、信号パス幅、信号または動作周波数、構成要素回路、またはデバイスなどのいずれかが、代替実施形態では、上述したものとは異なる場合もある。さらに、多重導体信号回線として示される、または記載される回路要素または回路ブロックの間の相互接続が、代替的に単一導体信号回線である場合もあり、単一導体信号回線が、代替的に多重導体信号回線である場合もある。さらに、シングルエンド形であるように示される、または記載される信号および信号パスが、差別的ある場合もあり、逆もまた同様である。同様に、正論理または負論理レベルを有するように記載された、または描写された信号が、代替実施形態において逆の論理レベルを有する場合もある。集積回路装置の中の構成要素回路構成が、金属酸化膜半導体（ＭＯＳ：ｍｅｔａｌ ｏｘｉｄｅ ｓｅｍｉｃｏｎｄｕｃｔｏｒ）技術、バイポーラ技術、または論理回路およびアナログ回路が実装される場合のある何らかの他の技術を用いて、実装される場合もある。用語に関して、特定の状態を示すために、信号が低論理状態または高論理状態に駆動される（または高論理状態に充電される、もしくは低論理状態に放電される）とき、信号は、「アサート」されていると言われる。これとは逆に、信号は、信号が、アサートされた状態（高論理状態または低論理状態、または信号駆動回路が、オープンドレインまたはオープンコレクタ状態などの高インピーダンス状態に推移されるときに、発生する可能性がある浮動状態を含む）以外の状態に駆動される（充電されるまたは放電される）ことを示すために「デアサート」されていると言われる。信号駆動回路が、信号駆動回路と信号受信回路との間に結合された信号ライン上の信号をアサートする、（または、明示的に述べられる、またはコンテキストによって指示される場合にはデアサートする）とき、信号駆動回路は、信号受信回路に信号を「出力する」と言われる。信号が、信号ライン上にアサートされるとき、信号ラインは、「活性化される」と言われ、信号が、デアサートされるとき、「非活性化される」と言われる。その上、信号名に付加されるプレフィックス記号「／」は、信号が、有効低信号である（すなわちアサートされた状態は、論理ロー状態である）ことを示す。さらに、信号名の上のライン（例えば、

）は、有効低信号を示すのに使用される。「結合される」という用語は、直接的な接続、ならびに１つまたは複数の介在回路または構造物を介した接続を表現するために本明細書では使用される。集積回路デバイス「プログラミング」は、例えば、そして限定するわけではなく、ホスト命令に応答して、制御値をデバイス内のレジスタまたは他の記憶回路の中にロードすること、したがって、デバイスの動作態様を制御することと、デバイス構成を確立すること、または１回限りのプログラミング動作によってデバイスの動作態様を制御すること（例えば、デバイス生産の間、構成回路内のヒューズをブローイングすること）と、および／または特定のデバイス構成またはデバイスの動作態様を確立するために、１つまたは複数の選択されたピンまたはデバイスの他の接続構造を、基準電圧ラインに結合すること（ストラッピングとも呼ばれる）とを含む場合がある。「例示的な」という用語は、優先傾向または要件ではなく、一例を表すのに使用される。

実施形態によれば、ＨＰＵチップは、コンピュータカード、ＵＳＢスティックの形態、またはコンピュータプロセッサに接続される何らかの他の形態をしたシステム上に取り付けられてもよい。

本明細書に開示される実施形態のさまざまな態様および特徴は、例えば、制限するわけではなく、以下の番号を付された条項で説明される：
１．
少なくとも１つのプロセッサスライスを備え、スライスが、
ローカル制御回路構成と、
準同型暗号を使用して暗号化されたデータ上で演算を行うためのマルチプルモードで動作するためのローカル制御回路構成に応答し、各モードは、ＮＴＴバタフライユニットの異なる構成と関連付けられている、数論変換（ＮＴＴ）バタフライユニットと、
制御回路構成およびＮＴＴバタフライユニットに結合されたオンチップメモリと
を含む、
集積回路（ＩＣ）準同型プロセッサチップ。
２．
ＮＴＴバタフライユニットが、完全準同型暗号化を伴う演算用のマルチプルモードで動作するためのローカル制御回路構成に応答する、条項１に記載のＩＣ準同型プロセッサチップ。
３．
ＮＴＴバタフライユニットが、部分的準同型暗号化を伴う演算用のマルチプルモードで動作するためのローカル制御回路構成に応答する、条項１に記載のＩＣ準同型プロセッサチップ。
４．
ＮＴＴバタフライユニット用の第１の構成が、第１の暗号文（Ｃ_ｔｘｔ）関数を実施するために第１の回路構成を使用し、
ＮＴＴバタフライユニット用の第２の構成が、第２のＣ_ｔｘｔ関数を実施するために第１の回路構成の少なくとも一部を再利用する、
条項１に記載のＩＣ準同型プロセッサチップ。
５．
第１の回路構成が、暗号文（Ｃ_ｔｘｔ）加算関数を実施し、
第２のＣ_ｔｘｔ関数が、Ｃ_ｔｘｔ乗算関数を備える、
条項４に記載のＩＣ準同型プロセッサチップ。
６．
第１の回路構成が、モジュラ加算器を含む、
条項５に記載のＩＣ準同型プロセッサチップ。
７．
モジュラ加算器が、組合せモジュラ加算器を備える、
条項６に記載のＩＣ準同型プロセッサチップ。
８．
モジュラ加算器が、順次モジュラ加算器を備える、
条項６に記載のＩＣ準同型プロセッサチップ。
９．
第２の構成が、モジュラ乗算器を備える第２の回路構成を含む、
条項５に記載のＩＣ準同型プロセッサチップ。
１０．
モジュラ乗算器が、並列整数乗算器を備える、条項９に記載のＩＣ準同型プロセッサチップ。
１１．
モジュラ乗算器が、
モジュラ約分ユニット
をさらに備える、条項１０に記載のＩＣ準同型プロセッサチップ。
１２．
ＩＣ準同型プロセッサが、マルチプルプロセッサスライスを含み、ＩＣ準同型プロセッサが、
マルチプルプロセッサスライスを外部プロセッサのインターフェースを介して外部メモリと接続するためのマスタ制御回路構成
をさらに備える、条項１に記載のＩＣ準同型プロセッサチップ。
１３．
ローカル制御回路構成が、
マスタ制御回路構成から、１組のＣｔｘｔ係数値をメモリから取り出し、
数値の組を処理パイプラインへロードし、
少なくとも１つのＣｔｘｔ演算を行い、
変換値を転送先メモリ位置に記憶させる
ようにとの命令を受け取る、条項１２に記載のＩＣ準同型プロセッサチップ。
１４．
マスタ制御回路構成からの命令が、
ＮＴＴドメインの中に対応する変換値を生成するために、ロードされた数値の組上でＮＴＴ変換を行う
ようにとの命令をさらに含む、条項１３に記載のＩＣ準同型プロセッサチップ。
１５．
マスタ制御回路構成からの、少なくとも１つのＣｔｘｔ演算を行うようにとの命令が、
加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成るグループから少なくとも１つのＣｔｘｔ演算を行う
ようにとの命令を含む、条項１４に記載のＩＣ準同型プロセッサチップ。
１６．
ＮＴＴバタフライユニットが、単一ステージユニットとして認識される、
条項１に記載のＩＣ準同型プロセッサチップ。
１７．
集積回路（ＩＣ）準同型プロセッサチップと、
ＩＣ準同型プロセッサチップ外部の主メモリと、
主メモリとＩＣ準同型プロセッサチップとの間でデータを転送するデータパスと、
主メモリとＩＣ準同型プロセッサチップとの間の転送を制御する制御パスとを備え、
ＩＣ準同型プロセッサチップが、
制御パスを介した主メモリとＩＣ準同型プロセッサチップとの間のデータの転送を制御するマスタ制御回路構成；および
パイプライン深さに対応するマルチプルプロセッサスライスであって、マルチプルプロセッサスライスのそれぞれが、
ローカル制御回路構成と、
準同型暗号化を使用しながら、暗号化されたデータ上で演算を行うためのマルチプルモードで動作するためのローカル制御回路構成に応答する数論変換（ＮＴＴ）バタフライユニットであって、各モードが、ＮＴＴバタフライユニットの異なる構成と関連付けられている数論変換（ＮＴＴ）バタフライユニットと、
ローカル制御回路構成およびＮＴＴバタフライユニットに結合されているオンチップメモリと
を含むマルチプルプロセッサスライスを備える、
準同型暗号化システム。
１８．
準同型暗号化が、完全準同型暗号化を備える、条項１７に記載の準同型暗号化システム。
１９．
準同型暗号化が、部分的準同型暗号化を備える、条項１７に記載の準同型暗号化システム。
２０．
マスタ制御回路構成が、
外部メモリから１組のＣｔｘｔ係数値を取り出し、
数値の組を処理パイプラインへロードし、
変換値を生成するために少なくとも１つのＣｔｘｔ演算を行い、
変換値を転送先メモリ位置に記憶させる
演算を、マルチプルプロセッサスライスごとにスケジュールする、条項１７に記載の準同型暗号化システム。
２１．
マスタ制御回路構成からのスケジュールされた演算が、マルチプルプロセッサスライスごとに、
ＮＴＴドメインの中に対応する変換値を生成するために、ロードされた数値の組上でＮＴＴ変換を行う
スケジュールされた演算をさらに備える、条項２０に記載の準同型暗号化システム。
２２．
マスタ制御回路構成からのスケジュールされた演算が、マルチプルプロセッサスライスごとに、
加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成るグループから少なくとも１つのＣｔｘｔ演算を行う
スケジュールされた演算をさらに備える、条項２１に記載の準同型暗号化システム。
２３．
ＮＴＴバタフライユニットのそれぞれが、単一ステージバタフライを備え、
所与のＮＴＴ変換演算が、ＮＴＴバタフライユニットによる評価のログ（ｎ）－１ステージを伴い、「ｎ」が、係数値と関連付けられた多項式の次数を表す、
条項２０に記載の準同型暗号化システム。
２４．
第１の加算器／減算器、
第１の乗算器、および
第１の加算器／減算器および第１の乗算器に結合されており、第１の加算器／減算器および第１の乗算器を選択的に迂回するそれぞれのバイパスパスを含む第１の選択回路構成
を含んでいる高入力語パスと、
第２の加算器／減算器、
第２の乗算器、および
第２の加算器／減算器および第２の乗算器に結合されており、第２の加算器／減算器および第２の乗算器を選択的に迂回するそれぞれのバイパスパスを含む第２の選択回路構成
を含んでいる低入力語パスと
を備え、
高入力語パスおよび低入力語パスが、交差結合されており、第１および第２の選択回路構成が、異なるモード制御信号に応答して、低入力語パスおよび高入力語パスを異なる論理処理ユニットに再構成する、数論変換（ＮＴＴ）バタフライ回路。
２５．
ＮＴＴバタフライ回路用の第１の構成が、暗号文（Ｃ_ｔｘｔ）加算関数を実施するために、第１の回路構成を使用し、
ＮＴＴバタフライ回路用の第２の構成が、Ｃ_ｔｘｔ乗算関数を実施するために、第１の回路構成の少なくとも一部を再利用する、
条項２４に記載のＮＴＴバタフライ回路。
２６．
第１および第２の加算器／減算器のそれぞれが、組合せモジュラ加算器を備える、条項２４に記載のＮＴＴバタフライ回路。
２７．
第１および第２の乗算器のそれぞれが、並列整数乗算器を備える、条項２４に記載のＮＴＴバタフライ回路。
２８．
第１および第２の乗算器のそれぞれが、
モジュラ約分ユニット
をさらに備える、条項２４に記載のＮＴＴバタフライ回路。
２９．
第１および第２の加算器／減算器、および乗算器のそれぞれが、関連付けられたクリティカルパスを含んでおり、
関連付けられたクリティカルパスのそれぞれが、レジスタ回路構成に囲まれている、条項２４に記載のＮＴＴバタフライ回路。
３０．
ＮＴＴバタフライ回路が、単一ステージバタフライとして認識され、
所与のＮＴＴ変換演算が、ＮＴＴバタフライ回路による評価のログ（ｎ）－１ステージを伴い、「ｎ」が、係数値と関連付けられた多項式の次数を表す、
条項２４に記載のＮＴＴバタフライ回路。
３１．
準同型プロセッサ集積回路（ＩＣ）チップ内での演算の方法であって、
暗号文（Ｃｔｘｔ）記号を数論変換（ＮＴＴ）ドメインに変換することを含み、変換することは、所与のプロセッサスライスに対して、
ローカル制御回路構成を用いてモード制御信号を生成することであって、モード制御信号は、準同型暗号化を伴う演算のマルチプルモードの１つに対応する、モード制御信号を生成することと、
モード制御信号に応答してＮＴＴバタフライユニットを構成することと
を含む、
準同型プロセッサ集積回路（ＩＣ）チップ内での演算の方法。
３２．
準同型暗号化が、完全準同型暗号化を備える、条項３１に記載の準同型プロセッサＩＣチップ内での演算の方法。
３３．
準同型暗号化が、部分的準同型暗号化を備える、条項３１に記載の準同型プロセッサＩＣチップ内での演算の方法。
３４．
モード制御信号が、演算の第１のモードに対応する第１のモード制御信号を備え、ＮＴＴバタフライユニットが、
Ｃｔｘｔ加算関数を実施するためにＮＴＴバタフライユニットを構成することによって第１のモード制御信号に応答する、条項３１に記載の方法。
３５．
モード制御信号が、演算の第２のモードに対応する第２のモード制御信号を備え、ＮＴＴバタフライユニットが、
Ｃｔｘｔ乗算関数を実施するためにＮＴＴバタフライユニットを構成することと、
乗算関数を実施するために加算関数で利用されたＮＴＴバタフライユニットの一部を再利用することと
によって第２のモード制御信号に応答する、条項３４に記載の方法。
３６．
変換することが、
マルチプルプロセッサスライスを並行して動作させることを含み、各プロセッサスライスが、ローカル制御回路構成のコピーおよびＮＴＴバタフライユニットのコピーを含む、条項３１に記載の方法。
３７．
マルチプルプロセッサスライスによって実施されたマルチプル演算をパイプラインで送ること
をさらに含む、条項３６に記載の方法。
３８．
マルチプルプロセッサスライスを、外部プロセッサインターフェースを介して外部メモリと接続することをさらに含み、インターフェース接続が、マスタ制御回路構成によって制御される、
条項３７に記載の方法。
３９．
マスタ制御回路構成が、マルチプルスライスのローカル制御回路構成に対する命令を生成し、ローカル制御回路構成が、
メモリから１組のＣｔｘｔ係数数値を取り出すことと、
数値の組を処理パイプラインへロードすることと、
変換値を生成するために少なくとも１つのＣｔｘｔ演算を行うことと、
変換値を外部メモリの中の転送先位置に記憶することと
を含むステップを実施するようにという命令に応答する、条項３８に記載の方法。
４０．
ＮＴＴドメインの中に対応する変換値を生成するために、ロードされた数値の組上でＮＴＴ変換を行うステップをさらに含む、条項３９に記載の方法。
４１．
少なくとも１つのＣｔｘｔ演算が、加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成るグループから選択される、条項４０に記載の方法。
４２．
準同型暗号化システム内での演算の方法であって、
設定可能な数論変換（ＮＴＴ）バタフライ論理を含んでいる準同型プロセッサ集積回路（ＩＣ）チップを提供することと、
準同型プロセッサＩＣチップをデータパスおよび制御パスを介して外部メモリとインターフェース接続することと、
暗号文（Ｃｔｘｔ）記号をＮＴＴドメインに変換することであって、変換することは、
所与のプロセッサスライスに対して、ローカル制御回路構成を用いてモード制御信号を生成することであって、モード制御信号は、準同型暗号化を伴う演算のマルチプルモードの１つに対応する、モード制御信号を生成することと、
モード制御信号に応答してＮＴＴバタフライユニットを構成することと
を含む暗号文（Ｃｔｘｔ）記号をＮＴＴドメインに変換することと
を含む、準同型暗号化システム内での演算の方法。
４３．
準同型暗号化が、完全準同型暗号化を備える、条項４２に記載の準同型暗号化システム内での演算の方法。
４４．
準同型暗号化が、部分的準同型暗号化を備える、条項４２に記載の準同型暗号化システム内での演算の方法。
４４．
モード制御信号が、演算の第１のモードに対応する第１のモード制御信号を備え、ＮＴＴバタフライユニットが、
Ｃｔｘｔ加算関数を実施するためにＮＴＴバタフライユニットを構成すること
によって第１のモード制御信号に応答する、条項４２に記載の方法。
４５．
モード制御信号が、演算の第２のモードに対応する第２のモード制御信号を備え、ＮＴＴバタフライユニットが、Ｃｔｘｔ乗算関数を実施するためにＮＴＴバタフライユニットを構成することと、
乗算関数を実施するために加算関数で利用されるＮＴＴバタフライユニットの一部を再利用することと
によって第２のモード制御信号に応答する、条項４４に記載の方法。
４６．
変換することが、
マルチプルプロセッサスライスを並行して動作させることを含み、各プロセッサスライスが、ローカル制御回路構成のコピーおよびＮＴＴバタフライユニットのコピーを含む、条項４２に記載の方法。
４７．
マルチプルプロセッサスライスによって実施されたマルチプル演算をパイプラインで送ること
をさらに含む、条項４６に記載の方法。
４８．
マルチプルプロセッサスライスを、外部プロセッサインターフェースを介して外部メモリと接続することをさらに含み、インターフェース接続が、マスタ制御回路構成によって制御される、条項４７に記載の方法。
４９．
マスタ制御回路構成が、マルチプルスライスのローカル制御回路構成に対する命令を生成し、ローカル制御回路構成が、
メモリから１組のＣｔｘｔ係数数値を取り出すことと、
数値の組を処理パイプラインへロードすることと、
変換値を生成するために少なくとも１つのＣｔｘｔ演算を行うことと、
変換値を外部メモリの中の転送先位置に記憶することと
を含むステップを実施するようにという命令に応答する、条項４８に記載の方法。
５０．
ＮＴＴドメインの中に対応する変換値を生成するために、ロードされた数値の組上でＮＴＴ変換を行うステップをさらに含む、条項４９に記載の方法。
５１．
少なくとも１つのＣｔｘｔ演算が、加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成るグループから選択される、条項５０に記載の方法。
５２．
数論変換（ＮＴＴ）バタフライ回路内での演算の方法であって、回路が、高入力語パスおよび低入力語パスを含み、高入力語パスが、第１の加算器／減算器、および第１の乗算器を含み、低入力語パスが、第２の加算器／減算器、および第２の乗算器を含み、方法が、
第２の加算器／減算器および第２の乗算器を選択的に迂回することと、
異なるモード制御信号に応答して、低入力語パスおよび高入力語パスを異なる論理処理ユニットに再構成することと
を含む、数論変換（ＮＴＴ）バタフライ回路内での演算の方法。
５３．
再構成することが、
第１のモード制御信号を受信したことに応答して、暗号文（Ｃ_ｔｘｔ）加算関数を実施するためにＮＴＴバタフライ回路を構成することと、
第２のモード制御信号を受信したことに応答して、Ｃ_ｔｘｔ乗算関数を実施するためにＮＴＴバタフライ回路を構成することと
を含む、条項５２に記載の方法。
５４．
第１および第２の加算器／減算器ごとに組み合せモジュラ加算器を利用すること
をさらに含む、条項５２に記載の方法。
５５．
第１および第２の乗算器ごとに並列整数乗算器を利用すること
をさらに含む、条項５２に記載の方法。
５６．
第１および第２の乗算器のそれぞれが、約分ユニットを含み、方法が、
それぞれの約分ユニットを動作させること
をさらに含む、条項５２に記載の方法。
５７．
ＮＴＴバタフライ回路が、単一ステージバタフライとして認識され、変換することが、
評価のログ（ｎ）－１ステージを通してＮＴＴバタフライ回路を動作させることを含み、「ｎ」が、係数値と関連付けられた多項式の次数を表す、
条項５２に記載のＮＴＴバタフライ回路。
５８．
暗号文（Ｃ_ｔｘｔ）記号を数論変換（ＮＴＴ）ドメインに変換するための準同型プロセッサ集積回路（ＩＣ）チップであって、ＩＣ準同型プロセッサチップは、
少なくとも１つのプロセッサスライスを備え、スライスは、
ローカル制御回路構成、
ＮＴＴバタフライユニット、および
制御回路構成およびＮＴＴバタフライユニットに結合されたオンチップメモリを含み、オンチップメモリは、準同型処理関数用の別々にアクセス可能な記憶ユニットに区分化されており、オンチップメモリは、
マルチプル入出力（Ｉ／Ｏ）記憶ユニット、
ビット分解多項式記憶ユニット、および
回転因子メモリユニット
を含む、
暗号文（Ｃ_ｔｘｔ）記号を数論変換（ＮＴＴ）ドメインに変換するための準同型プロセッサ集積回路（ＩＣ）チップ。
５９．
Ｉ／Ｏ記憶ユニットの第１のユニットが、暗号文（Ｃｔｘｔｓ）を行単位フォーマットで記憶し、
Ｉ／Ｏ記憶ユニットの第２のユニットが、Ｃｔｘｔｓを列単位フォーマットで記憶する、
条項５８に記載の準同型プロセッサＩＣチップ。
６０．
Ｉ／Ｏ記憶ユニットの第３のユニットが、第１の記憶ユニットからの第１のＣｔｘｔが第２の記憶ユニットからの第２のＣｔｘｔに乗算されることを伴う乗算演算の結果生じる出力Ｃｔｘｔｓを記憶する、
条項５９に記載の準同型プロセッサＩＣチップ。
６１．
第２のメモリユニットに結合されたメモリカウンタ
をさらに備える、条項６０に記載の準同型プロセッサＩＣチップ。
６２．
Ｉ／Ｏ記憶ユニットの第１のユニットの中の所与の行のＣｔｘｔの単列変換が、Ｉ／Ｏ記憶ユニットの第３のユニットの中の対応する結果的に生じた行になる、
条項６０に記載の準同型プロセッサＩＣチップ。
６３．
マルチプルＩ／Ｏ記憶ユニットの１つが、外部メモリに結合されたピンポンメモリとして構成される、
条項５８に記載の準同型プロセッサＩＣチップ。
６４．
ピンポンメモリが、
第１のメモリ演算を実施する第１のサブアレイと、
第１のメモリ演算と同時並行の第２の演算を実施する第２のサブアレイと
を含む、条項６３に記載の準同型プロセッサＩＣチップ。
６５．
オンチップメモリが、ＤＲＡＭを備える、条項６３に記載の準同型プロセッサＩＣチップ。
６６．
準同型プロセッサ集積回路（ＩＣ）チップ内での演算の方法であって、
オンチップメモリを、準同型処理関数用の別々にアクセス可能な記憶ユニットに区分化することであって、オンチップメモリが、マルチプル入出力（Ｉ／Ｏ）記憶ユニット、ビット分解多項式記憶ユニット、および回転因子メモリユニットを含む、オンチップメモリを区分化することと、
少なくとも１つの暗号文（Ｃｔｘｔ）演算を、区分化されたオンチップメモリに結合された、構成可能な数論変換（ＮＴＴ）バタフライユニットを用いてロードされた数値の組上で行うことと
を含む、方法。
６７．
ＮＴＴドメインの中に対応する変換値を生成するために、ロードされた数値の組を変換すること
をさらに含む、条項６６に記載の方法。
６８．
少なくとも１つのＣｔｘｔ演算が、加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成るグループから選択される、条項６７に記載の方法。
６９．
変換することが、
第１の暗号文（Ｃｔｘｔ）をＩ／Ｏ記憶ユニットの第１のユニットから行単位フォーマットで読み込むことと、
第２のＣｔｘｔをＩ／Ｏ記憶ユニットの第２のユニットから列単位フォーマットで読み込むことと
をさらに含む、条項６７に記載の方法。
７０．
変換することが、
結果的に生じるＣｔｘｔを生成するために、第１のＣｔｘｔに第２のＣｔｘｔを乗算することと、
結果的に生じたＣｔｘｔをＩ／Ｏ記憶ユニットの第３のユニットに書き込むことと
をさらに含む、条項６９に記載の方法。
７１．
マルチプルＩ／Ｏ記憶ユニットの１つが、ピンポンメモリユニットとして構成されたそれぞれの第１および第２のサブアレイを含み、方法が、
第１の演算を実施するために第１のサブアレイを動作させることと、
第１の演算と同時並行の第２の演算を実施するために、第２のサブアレイを動作させることと
をさらに含む、条項６６に記載の方法。
７２．
準同型プロセッサ集積回路（ＩＣ）チップ内での演算の方法であって、
第１の暗号文（Ｃｔｘｔ）を第１のオンチップメモリユニットから取り出すことであって、第１のＣｔｘｔは、行フォーマット読出演算を利用して取り出される、第１の暗号文を取り出すことと、
第１のＣｔｘｔを数論変換（ＮＴＴ）ドメインに変換することと、
第２の暗号文（Ｃｔｘｔ）を第２のオンチップメモリユニットから取り出すことであって、第２のＣｔｘｔは、列フォーマット読出演算を利用して取り出される、第２の暗号文を取り出すことと、
第２のＣｔｘｔをＮＴＴドメインに変換することと、
結果として生じるＣｔｘｔを生成するために、変換された第１のＣｔｘｔに、変換された第２のＣｔｘｔを乗算することと、
結果として生じたＣｔｘｔを第３のメモリユニットの中に記憶させることと
を含む、準同型プロセッサ集積回路（ＩＣ）チップ内での演算の方法。

本発明は、その特定の実施形態を参照しながら、説明されてきたが、本発明のより広い趣旨および範囲を逸脱しない範囲で、それにさまざまな変更態様および改変を加えることができることは明白である。例えば、少なくとも、実施形態の他のどれかと組み合わせて、またはその対応する特徴または態様の代わりに実行可能である場合には、実施形態のいずれかの特徴または態様は、適用されることができる。したがって、明細書および図面は、制限的な意味ではなく例証的なものとみなされるべきである。

Claims (23)

1. 集積回路（ＩＣ）準同型プロセッサチップであって、前記プロセッサチップが、
   少なくとも１つのプロセッサスライスであって、前記プロセッサスライスが、
   ローカル制御回路構成と、
   準同型暗号を使用して暗号化されたデータ上で演算を行うためのマルチプルモードで動作するために前記ローカル制御回路構成に応答する数論変換（ＮＴＴ）バタフライユニットであって、各モードは、前記ＮＴＴバタフライユニットの異なる構成と関連付けられている、ＮＴＴバタフライユニットと、
   前記ローカル制御回路構成および前記ＮＴＴバタフライユニットに結合されたオンチップメモリと、
   を含み、
   所与のＮＴＴ変換演算が、前記ＮＴＴバタフライユニットによる評価のｌｏｇ _２ （ｎ）－１ステージが続く始めのＮＴＴステップを伴い、式中、「ｎ」が、１組の暗号文（Ｃ _ｔｘｔ ）係数値と関連付けられた多項式の次数を表す、
   プロセッサスライス
   を備える、ＩＣ準同型プロセッサチップ。
2. 前記ＮＴＴバタフライユニットが、完全準同型暗号化を伴う演算用のマルチプルモードで動作するために前記ローカル制御回路構成に応答する、請求項１に記載のＩＣ準同型プロセッサチップ。
3. 前記ＮＴＴバタフライユニットが、部分的準同型暗号化を伴う演算用のマルチプルモードで動作するために前記ローカル制御回路構成に応答する、請求項１に記載のＩＣ準同型プロセッサチップ。
4. 前記ＮＴＴバタフライユニット用の第１の構成が、第１の暗号文（Ｃ_ｔｘｔ）関数を実施するために第１の回路構成を使用し、
   前記ＮＴＴバタフライユニット用の第２の構成が、第２のＣ_ｔｘｔ関数を実施するために前記第１の回路構成の少なくとも一部を再利用する、
   請求項１～３のいずれか一項に記載のＩＣ準同型プロセッサチップ。
5. 前記第１の回路構成が、暗号文（Ｃ_ｔｘｔ）加算関数を実施し、
   前記第２のＣ_ｔｘｔ関数が、Ｃ_ｔｘｔ乗算関数を備える、
   請求項４に記載のＩＣ準同型プロセッサチップ。
6. 前記第１の回路構成が、モジュラ加算器を含む、
   請求項５に記載のＩＣ準同型プロセッサチップ。
7. 前記モジュラ加算器が、組合せモジュラ加算器を備える、
   請求項６に記載のＩＣ準同型プロセッサチップ。
8. 前記モジュラ加算器が、順次モジュラ加算器を備える、
   請求項６に記載のＩＣ準同型プロセッサチップ。
9. 前記第２の構成が、モジュラ乗算器を備える第２の回路構成を含む、
   請求項５に記載のＩＣ準同型プロセッサチップ。
10. 前記モジュラ乗算器が、並列整数乗算器を備える、請求項９に記載のＩＣ準同型プロセッサチップ。
11. 前記モジュラ乗算器が、
    モジュラ約分ユニット
    をさらに備える、請求項１０に記載のＩＣ準同型プロセッサチップ。
12. 前記ＩＣ準同型プロセッサが、マルチプルプロセッサスライスを含み、前記ＩＣ準同型プロセッサが、
    前記マルチプルプロセッサスライスを外部プロセッサのインターフェースを介して外部メモリと接続するためのマスタ制御回路構成
    をさらに備える、請求項１～１１のいずれか一項に記載のＩＣ準同型プロセッサチップ。
13. 前記ローカル制御回路構成が、
    前記マスタ制御回路構成から、１組のＣ_ｔｘｔ係数値を前記メモリから取り出し、
    前記１組のＣ_ｔｘｔ係数値を処理パイプラインへロードし、
    変換値を生成するために少なくとも１つのＣ_ｔｘｔ演算を行い、
    前記変換値を転送先メモリ位置に記憶させる
    ようにとの命令を受け取る、請求項１２に記載のＩＣ準同型プロセッサチップ。
14. 前記マスタ制御回路構成からの命令が、
    ＮＴＴドメインの中に対応する変換値を生成するために、前記ロードされた数値の組上でＮＴＴ変換を行う
    ようにとの命令をさらに含む、請求項１３に記載のＩＣ準同型プロセッサチップ。
15. 前記マスタ制御回路構成からの、少なくとも１つのＣ_ｔｘｔ演算を行うようにとの命令が、
    加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成るグループから少なくとも１つのＣ_ｔｘｔ演算を行う
    ようにとの命令を含む、請求項１３または１４に記載のＩＣ準同型プロセッサチップ。
16. 前記ＮＴＴバタフライユニットが、単一ステージユニットとして認識される、
    請求項１～１５のいずれか一項に記載のＩＣ準同型プロセッサチップ。
17. 準同型暗号化システムであって、前記システムが、
    集積回路（ＩＣ）準同型プロセッサチップと、
    前記ＩＣ準同型プロセッサチップ外部の主メモリと、
    前記主メモリと前記ＩＣ準同型プロセッサチップとの間でデータを転送するデータパスと、
    前記主メモリと前記ＩＣ準同型プロセッサチップとの間の転送を制御する制御パスと、
    を備え、
    前記ＩＣ準同型プロセッサチップが、
    前記制御パスを介した前記主メモリと前記ＩＣ準同型プロセッサチップとの間のデータの転送を制御するマスタ制御回路構成、および
    パイプライン深さに対応するマルチプルプロセッサスライスであって、前記マルチプルプロセッサスライスのそれぞれが、
    ローカル制御回路構成と、
    準同型暗号化を使用しながら、暗号化されたデータ上で演算を行うためのマルチプルモードで動作するために前記ローカル制御回路構成に応答する数論変換（ＮＴＴ）バタフライユニットであって、各モードが、前記ＮＴＴバタフライユニットの異なる構成と関連付けられている数論変換（ＮＴＴ）バタフライユニットと、
    前記ローカル制御回路構成および前記ＮＴＴバタフライユニットに結合されているオンチップメモリと、
    を含むマルチプルプロセッサスライスを備える、
    準同型暗号化システム。
18. 前記準同型暗号化が、完全準同型暗号化を備える、請求項１７に記載の準同型暗号化システム。
19. 前記準同型暗号化が、部分的準同型暗号化を備える、請求項１７に記載の準同型暗号化システム。
20. 前記マスタ制御回路構成が、
    前記外部メモリから１組のＣ_ｔｘｔ係数値を取り出し、
    前記１組のＣ_ｔｘｔ係数値を処理パイプラインへロードし、
    少なくとも１つのＣ_ｔｘｔ演算を行い、
    前記変換値を転送先メモリ位置に記憶させる
    演算を、前記マルチプルプロセッサスライスごとにスケジュールする、請求項１７～１９のいずれか一項に記載の準同型暗号化システム。
21. 前記マスタ制御回路構成からのスケジュールされた演算が、前記マルチプルプロセッサスライスごとに、
    ＮＴＴドメインの中に対応する変換値を生成するために、前記ロードされた数値の組上でＮＴＴ変換演算を行う
    スケジュールされた演算をさらに備える、請求項２０に記載の準同型暗号化システム。
22. 前記マスタ制御回路構成からのスケジュールされた演算が、前記マルチプルプロセッサスライスごとに、
    加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成るグループから少なくとも１つのＣ_ｔｘｔ演算を行う
    スケジュールされた演算をさらに備える、請求項２０または２１に記載の準同型暗号化システム。
23. 前記ＮＴＴバタフライユニットのそれぞれが、単一ステージバタフライを備える、
    請求項２１に記載の準同型暗号化システム。

Images