(57)【要約】  完全準同型暗号化集積回路（ＩＣ）チップ、システム、および関連方法が開示される。１つの実施形態では、集積回路（ＩＣ）準同型プロセッサチップが開示される。ＩＣ同形プロセッサチップは、少なくとも１つのプロセッサスライスを含む。各プロセッサスライスは、ローカル制御回路構成、数論変換（ＮＴＴ）バタフライユニット、およびオンチップメモリを含む。ＮＴＴバタフライユニットは、準同型暗号化を使用しながら、暗号化されたデータ上で演算を行うためのマルチプルモードで動作するためのローカル制御回路構成に応答する。各モードは、ＮＴＴバタフライユニットの異なる構成と関連付けられている。【選択図】図１Ａ
2020537756.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも１つのプロセッサスライスを備え、前記スライスが、
ローカル制御回路構成と、
準同型暗号を使用して暗号化されたデータ上で演算を行うためのマルチプルモードで動作するための前記ローカル制御回路構成に応答し、各モードは、前記ＮＴＴバタフライユニットの異なる構成と関連付けられている、数論変換（ＮＴＴ）バタフライユニットと、
前記制御回路構成および前記ＮＴＴバタフライユニットに結合されたオンチップメモリと
を含む、
集積回路（ＩＣ）準同型プロセッサチップ。
【請求項２】
前記ＮＴＴバタフライユニットが、完全準同型暗号化を伴う演算用のマルチプルモードで動作するための前記ローカル制御回路構成に応答する、請求項１に記載のＩＣ準同型プロセッサチップ。
【請求項３】
前記ＮＴＴバタフライユニットが、部分的準同型暗号化を伴う演算用のマルチプルモードで動作するための前記ローカル制御回路構成に応答する、請求項１に記載のＩＣ準同型プロセッサチップ。
【請求項４】
前記ＮＴＴバタフライユニット用の第１の構成が、第１の暗号文（Ｃｔｘｔ）関数を実施するために第１の回路構成を使用し、
前記ＮＴＴバタフライユニット用の第２の構成が、第２のＣｔｘｔ関数を実施するために前記第１の回路構成の少なくとも一部を再利用する、
請求項１〜３のいずれか一項に記載のＩＣ準同型プロセッサチップ。
【請求項５】
前記第１の回路構成が、暗号文（Ｃｔｘｔ）加算関数を実施し、
前記第２のＣｔｘｔ関数が、Ｃｔｘｔ乗算関数を備える、
請求項４に記載のＩＣ準同型プロセッサチップ。
【請求項６】
前記第１の回路構成が、モジュラ加算器を含む、
請求項５に記載のＩＣ準同型プロセッサチップ。
【請求項７】
前記モジュラ加算器が、組合せモジュラ加算器を備える、
請求項６に記載のＩＣ準同型プロセッサチップ。
【請求項８】
前記モジュラ加算器が、順次モジュラ加算器を備える、
請求項６に記載のＩＣ準同型プロセッサチップ。
【請求項９】
前記第２の構成が、モジュラ乗算器を備える第２の回路構成を含む、
請求項５に記載のＩＣ準同型プロセッサチップ。
【請求項１０】
前記モジュラ乗算器が、並列整数乗算器を備える、請求項９に記載のＩＣ準同型プロセッサチップ。
【請求項１１】
前記モジュラ乗算器が、
モジュラ約分ユニット
をさらに備える、請求項１０に記載のＩＣ準同型プロセッサチップ。
【請求項１２】
前記ＩＣ準同型プロセッサが、マルチプルプロセッサスライスを含み、前記ＩＣ準同型プロセッサが、
前記マルチプルプロセッサスライスを外部プロセッサのインターフェースを介して外部メモリと接続するためのマスタ制御回路構成
をさらに備える、請求項１〜１１のいずれかに記載のＩＣ準同型プロセッサチップ。
【請求項１３】
前記ローカル制御回路構成が、
前記マスタ制御回路構成から、１組のＣｔｘｔ係数値を前記メモリから取り出し、
数値の前記組を処理パイプラインへロードし、
変換値を生成するために少なくとも１つのＣｔｘｔ演算を行い、
前記変換値を転送先メモリ位置に記憶させる
ようにとの命令を受け取る、請求項１２に記載のＩＣ準同型プロセッサチップ。
【請求項１４】
前記マスタ制御回路構成からの前記命令が、
前記ＮＴＴドメインの中に対応する変換値を生成するために、前記ロードされた数値の組上でＮＴＴ変換を行う
ようにとの命令をさらに含む、請求項１３に記載のＩＣ準同型プロセッサチップ。
【請求項１５】
前記マスタ制御回路構成からの、少なくとも１つのＣｔｘｔ演算を行うようにとの前記命令が、
加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成る前記グループから少なくとも１つのＣｔｘｔ演算を行う
ようにとの命令を含む、請求項１３または１４に記載のＩＣ準同型プロセッサチップ。
【請求項１６】
前記ＮＴＴバタフライユニットが、単一ステージユニットとして認識される、
請求項１〜１６のいずれかに記載のＩＣ準同型プロセッサチップ。
【請求項１７】
集積回路（ＩＣ）準同型プロセッサチップと、
前記ＩＣ準同型プロセッサチップ外部の主メモリと、
前記主メモリと前記ＩＣ準同型プロセッサチップとの間でデータを転送するデータパスと、
前記主メモリと前記ＩＣ準同型プロセッサチップとの間の前記転送を制御する制御パスとを備え、
前記ＩＣ準同型プロセッサチップが、
前記制御パスを介した前記主メモリと前記ＩＣ準同型プロセッサチップとの間のデータの前記転送を制御するマスタ制御回路構成；および
パイプライン深さに対応するマルチプルプロセッサスライスであって、前記マルチプルプロセッサスライスのそれぞれが、
ローカル制御回路構成と、
準同型暗号化を使用しながら、暗号化されたデータ上で演算を行うためのマルチプルモードで動作するための前記ローカル制御回路構成に応答する数論変換（ＮＴＴ）バタフライユニットであって、各モードが、前記ＮＴＴバタフライユニットの異なる構成と関連付けられている数論変換（ＮＴＴ）バタフライユニットと、
前記ローカル制御回路構成および前記ＮＴＴバタフライユニットに結合されているオンチップメモリと
を含むマルチプルプロセッサスライスを備える、
準同型暗号化システム。
【請求項１８】
前記準同型暗号化が、完全準同型暗号化を備える、請求項１７に記載の準同型暗号化システム。
【請求項１９】
前記準同型暗号化が、部分的準同型暗号化を備える、請求項１７に記載の準同型暗号化システム。
【請求項２０】
前記マスタ制御回路構成が、
前記外部メモリから１組のＣｔｘｔ係数値を取り出し、
数値の前記組を処理パイプラインへロードし、
少なくとも１つのＣｔｘｔ演算を行い、
前記変換値を転送先メモリ位置に記憶させる
演算を、前記マルチプルプロセッサスライスごとにスケジュールする、請求項１７〜１９のいずれかに記載の準同型暗号化システム。
【請求項２１】
前記マスタ制御回路構成からの前記スケジュールされた演算が、前記マルチプルプロセッサスライスごとに、
前記ＮＴＴドメインの中に対応する変換値を生成するために、前記ロードされた数値の組上でＮＴＴ変換演算を行う
スケジュールされた演算をさらに備える、請求項２０に記載の準同型暗号化システム。
【請求項２２】
前記マスタ制御回路構成からのスケジュールされた演算が、前記マルチプルプロセッサスライスごとに、
加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成る前記グループから少なくとも１つのＣｔｘｔ演算を行う
スケジュールされた演算をさらに備える、請求項２０または２１に記載の準同型暗号化システム。
【請求項２３】
前記ＮＴＴバタフライユニットのそれぞれが、単一ステージバタフライを備え、
所与のＮＴＴ変換演算が、前記ＮＴＴバタフライユニットによる評価のログ（ｎ）−１ステージを伴い、「ｎ」が、前記係数値と関連付けられた多項式の次数を表す、
請求項２１に記載の準同型暗号化システム。
【請求項２４】
第１の加算器／減算器、
第１の乗算器、および
前記第１の加算器／減算器および前記第１の乗算器に結合されており、前記第１の加算器／減算器および前記第１の乗算器を選択的に迂回するそれぞれのバイパスパスを含む第１の選択回路構成
を含んでいる高入力語パスと、
第２の加算器／減算器、
第２の乗算器、および
前記第２の加算器／減算器および前記第２の乗算器に結合されており、前記第２の加算器／減算器および前記第２の乗算器を選択的に迂回するそれぞれのバイパスパスを含む第２の選択回路構成
を含んでいる低入力語パスと
を備え、
前記高入力語パスおよび低入力語パスが、交差結合されており、前記第１および第２の選択回路構成が、異なるモード制御信号に応答して、前記低入力語パスおよび高入力語パスを異なる論理処理ユニットに再構成する、
数論変換（ＮＴＴ）バタフライ回路。
【請求項２５】
前記ＮＴＴバタフライ回路用の第１の構成が、暗号文（Ｃｔｘｔ）加算関数を実施するために、第１の回路構成を使用し、
前記ＮＴＴバタフライ回路用の第２の構成が、Ｃｔｘｔ乗算関数を実施するために、前記第１の回路構成の少なくとも一部を再利用する、
請求項２４に記載のＮＴＴバタフライ回路。
【請求項２６】
前記第１および第２の加算器／減算器のそれぞれが、組合せモジュラ加算器を備える、
請求項２４に記載のＮＴＴバタフライ回路。
【請求項２７】
前記第１および第２の乗算器のそれぞれが、並列整数乗算器を備える、
請求項２４に記載のＮＴＴバタフライ回路。
【請求項２８】
前記第１および第２の乗算器のそれぞれが、
モジュラ約分ユニット
をさらに備える、請求項２４に記載のＮＴＴバタフライ回路。
【請求項２９】
前記第１および第２の加算器／減算器、および乗算器のそれぞれが、関連付けられたクリティカルパスを含んでおり、
前記関連付けられたクリティカルパスのそれぞれが、レジスタ回路構成に囲まれている、
請求項２４に記載のＮＴＴバタフライ回路。
【請求項３０】
前記ＮＴＴバタフライ回路が、単一ステージバタフライとして認識され、
所与のＮＴＴ変換演算が、前記ＮＴＴバタフライ回路による評価のログ（ｎ）−１ステージを伴い、「ｎ」が、前記係数値と関連付けられた多項式の次数を表す、
請求項２４に記載のＮＴＴバタフライ回路。
【請求項３１】
準同型プロセッサ集積回路（ＩＣ）チップ内での演算の方法であって、
暗号文（Ｃｔｘｔ）記号を数論変換（ＮＴＴ）ドメインに変換することを含み、前記変換することは、所与のプロセッサスライスに対して、
ローカル制御回路構成を用いてモード制御信号を生成することであって、前記モード制御信号は、準同型暗号化を伴う演算のマルチプルモードの１つに対応する、モード制御信号を生成することと、
前記モード制御信号に応答してＮＴＴバタフライユニットを構成することと
を含む、
準同型プロセッサ集積回路（ＩＣ）チップ内での演算の方法。
【請求項３２】
前記準同型暗号化が、完全準同型暗号化を備える、請求項３１に記載の準同型プロセッサＩＣチップ内での演算の方法。
【請求項３３】
前記準同型暗号化が、部分的準同型暗号化を備える、請求項３１に記載の準同型プロセッサＩＣチップ内での演算の方法。
【請求項３４】
前記モード制御信号が、演算の第１のモードに対応する第１のモード制御信号を備え、前記ＮＴＴバタフライユニットが、
Ｃｔｘｔ加算関数を実施するために前記ＮＴＴバタフライユニットを構成すること
によって前記第１のモード制御信号に応答する、請求項３１〜３３のいずれかに記載の方法。
【請求項３５】
前記モード制御信号が、演算の第２のモードに対応する第２のモード制御信号を備え、前記ＮＴＴバタフライユニットが、
Ｃｔｘｔ乗算関数を実施するために前記ＮＴＴバタフライユニットを構成することと、
前記乗算関数を実施するために前記加算関数で利用された前記ＮＴＴバタフライユニットの一部を再利用することと
によって前記第２のモード制御信号に応答する、請求項３４に記載の方法。
【請求項３６】
前記変換することが、
マルチプルプロセッサスライスを並行して動作させることを含み、各プロセッサスライスが、前記ローカル制御回路構成のコピーおよび前記ＮＴＴバタフライユニットのコピーを含む、
請求項３１〜３５のいずれかに記載の方法。
【請求項３７】
前記マルチプルプロセッサスライスによって実施されたマルチプル演算をパイプラインで送ること
をさらに含む、請求項３６に記載の方法。
【請求項３８】
前記マルチプルプロセッサスライスを、外部プロセッサインターフェースを介して外部メモリと接続することをさらに含み、前記インターフェース接続が、マスタ制御回路構成によって制御される、
請求項３７に記載の方法。
【請求項３９】
前記マスタ制御回路構成が、前記マルチプルスライスのローカル制御回路構成に対する命令を生成し、前記ローカル制御回路構成が、
前記メモリから１組のＣｔｘｔ係数数値を取り出すことと、
数値の前記組を処理パイプラインへロードすることと、
変換値を生成するために少なくとも１つのＣｔｘｔ演算を行うことと、
前記変換値を前記外部メモリの中の転送先位置に記憶することと
を含む前記ステップを実施するようにという前記命令に応答する、請求項３８に記載の方法。
【請求項４０】
前記ＮＴＴドメインの中に対応する変換値を生成するために、前記ロードされた数値の組上でＮＴＴ変換を行う前記ステップをさらに含む、請求項３９に記載の方法。
【請求項４１】
前記少なくとも１つのＣｔｘｔ演算が、加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成る前記グループから選択される、請求項３９または４０に記載の方法。
【請求項４２】
準同型暗号化システム内での演算の方法であって、
設定可能な数論変換（ＮＴＴ）バタフライユニットを含んでいる準同型プロセッサ集積回路（ＩＣ）チップを提供することと、
前記準同型プロセッサＩＣチップをデータパスおよび制御パスを介して外部メモリとインターフェース接続することと、
暗号文（Ｃｔｘｔ）記号をＮＴＴドメインに変換することであって、前記変換することは、
所与のプロセッサスライスに対して、ローカル制御回路構成を用いてモード制御信号を生成することであって、前記モード制御信号は、準同型暗号化を伴う演算のマルチプルモードの１つに対応する、モード制御信号を生成することと、
前記モード制御信号に応答して前記ＮＴＴバタフライユニットを構成することと
を含む暗号文（Ｃｔｘｔ）記号をＮＴＴドメインに変換することと
を含む、準同型暗号化システム内での演算の方法。
【請求項４３】
前記準同型暗号化が、完全準同型暗号化を備える、請求項４２に記載の準同型暗号化システム内での演算の方法。
【請求項４４】
前記準同型暗号化が、部分的準同型暗号化を備える、請求項４２に記載の準同型暗号化システム内での演算の方法。
【請求項４４】
前記モード制御信号が、演算の第１のモードに対応する第１のモード制御信号を備え、前記ＮＴＴバタフライユニットが、
Ｃｔｘｔ加算関数を実施するためにＮＴＴバタフライユニットを構成すること
によって前記第１のモード制御信号に応答する、請求項４２〜４４のいずれかに記載の方法。
【請求項４５】
前記モード制御信号が、演算の第２のモードに対応する第２のモード制御信号を備え、前記ＮＴＴバタフライユニットが、Ｃｔｘｔ乗算関数を実施するために前記ＮＴＴバタフライユニットを構成することと、
前記乗算関数を実施するために前記加算関数で利用される前記ＮＴＴバタフライユニットの一部を再利用することと
によって前記第２のモード制御信号に応答する、請求項４４に記載の方法。
【請求項４６】
前記変換することが、
マルチプルプロセッサスライスを並行して動作させることを含み、各プロセッサスライスが、ローカル制御回路構成のコピーおよび前記ＮＴＴバタフライユニットのコピーを含む、
請求項４２〜４５のいずれかに記載の方法。
【請求項４７】
前記マルチプルプロセッサスライスによって実施されたマルチプル演算をパイプラインで送ること
をさらに含む、請求項４６に記載の方法。
【請求項４８】
前記マルチプルプロセッサスライスを、外部プロセッサインターフェースを介して外部メモリと接続することをさらに含み、前記インターフェース接続が、マスタ制御回路構成によって制御される、
請求項４７に記載の方法。
【請求項４９】
前記マスタ制御回路構成が、前記マルチプルスライスの前記ローカル制御回路構成に対する命令を生成し、前記ローカル制御回路構成が、
前記メモリから１組のＣｔｘｔ係数数値を取り出すことと、
数値の前記組を処理パイプラインへロードすることと、
変換値を生成するために少なくとも１つのＣｔｘｔ演算を行うことと、
前記変換値を前記外部メモリの中の転送先位置に記憶することと
を含む前記ステップを実施するようにという前記命令に応答する、請求項４８に記載の方法。
【請求項５０】
前記ＮＴＴドメインの中に対応する変換値を生成するために、前記ロードされた数値の組上でＮＴＴ変換を行う前記ステップをさらに含む、請求項４９に記載の方法。
【請求項５１】
前記少なくとも１つのＣｔｘｔ演算が、加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成る前記グループから選択される、請求項４９または５０に記載の方法。
【請求項５２】
数論変換（ＮＴＴ）バタフライ回路内での演算の方法であって、前記回路が、高入力語パスおよび低入力語パスを含み、前記高入力語パスが、第１の加算器／減算器、および第１の乗算器を含み、前記低入力語パスが、第２の加算器／減算器、および第２の乗算器を含み、前記方法が、
前記第２の加算器／減算器および前記第２の乗算器を選択的に迂回することと、
異なるモード制御信号に応答して、前記低入力語パスおよび高入力語パスを異なる論理処理ユニットに再構成することと
を含む、数論変換（ＮＴＴ）バタフライ回路内での演算の方法。
【請求項５３】
前記再構成することが、
第１のモード制御信号を受信したことに応答して、暗号文（Ｃｔｘｔ）加算関数を実施するために前記ＮＴＴバタフライ回路を構成することと、
第２のモード制御信号を受信したことに応答して、Ｃｔｘｔ乗算関数を実施するために前記ＮＴＴバタフライ回路を構成することと
を含む、請求項５２に記載の方法。
【請求項５４】
前記第１および第２の加算器／減算器ごとに組み合せモジュラ加算器を利用すること
をさらに含む、請求項５２または５３に記載の方法。
【請求項５５】
前記第１および第２の乗算器ごとに並列整数乗算器を利用すること
をさらに含む、請求項５２〜５４のいずれかに記載の方法。
【請求項５６】
前記第１および第２の乗算器のそれぞれが、約分ユニットを含み、前記方法が、
それぞれの約分ユニットを動作させること
をさらに含む、請求項５２〜５５のいずれかに記載の方法。
【請求項５７】
前記ＮＴＴバタフライ回路が、単一ステージバタフライとして認識され、前記変換することが、
評価のログ（ｎ）−１ステージを通して前記ＮＴＴバタフライ回路を動作させることを含み、「ｎ」が、係数値と関連付けられた多項式の次数を表す、
請求項５２〜５６のいずれかに記載のＮＴＴバタフライ回路。
【請求項５８】
暗号文（Ｃｔｘｔ）記号を数論変換（ＮＴＴ）ドメインに変換するための準同型プロセッサ集積回路（ＩＣ）チップであって、前記ＩＣ準同型プロセッサチップは、
少なくとも１つのプロセッサスライスを備え、前記スライスは、
ローカル制御回路構成、
ＮＴＴバタフライユニット、および
前記制御回路構成および前記ＮＴＴバタフライユニットに結合されたオンチップメモリを含み、前記オンチップメモリは、準同型処理関数用の別々にアクセス可能な記憶ユニットに区分化されており、前記オンチップメモリは、
マルチプル入出力（Ｉ／Ｏ）記憶ユニット、
ビット分解多項式記憶ユニット、および
回転因子メモリユニット
を含む、
暗号文（Ｃｔｘｔ）記号を数論変換（ＮＴＴ）ドメインに変換するための準同型プロセッサ集積回路（ＩＣ）チップ。
【請求項５９】
前記Ｉ／Ｏ記憶ユニットの第１のユニットが、暗号文（Ｃｔｘｔｓ）を行単位フォーマットで記憶し、
前記Ｉ／Ｏ記憶ユニットの第２のユニットが、Ｃｔｘｔｓを列単位フォーマットで記憶する、
請求項５８に記載の準同型プロセッサＩＣチップ。
【請求項６０】
前記Ｉ／Ｏ記憶ユニットの第３のユニットが、前記第１の記憶ユニットからの第１のＣｔｘｔが前記第２の記憶ユニットからの第２のＣｔｘｔに乗算されることを伴う乗算演算の結果生じる出力Ｃｔｘｔｓを記憶する、
請求項５９に記載の準同型プロセッサＩＣチップ。
【請求項６１】
前記第２のメモリユニットに結合されたメモリカウンタ
をさらに備える、請求項６０に記載の準同型プロセッサＩＣチップ。
【請求項６２】
前記Ｉ／Ｏ記憶ユニットの前記第１のユニットの中の所与の行のＣｔｘｔの単列変換が、前記Ｉ／Ｏ記憶ユニットの前記第３のユニットの中の対応する結果的に生じた行になる、
請求項６０〜６１のいずれかに記載の準同型プロセッサＩＣチップ。
【請求項６３】
前記マルチプルＩ／Ｏ記憶ユニットの１つが、外部メモリに結合されたピンポンメモリとして構成される、
請求項５８〜６３のいずれかに記載の準同型プロセッサＩＣチップ。
【請求項６４】
前記ピンポンメモリが、
第１のメモリ演算を実施する第１のサブアレイと、
前記第１のメモリ演算と同時並行の第２の演算を実施する第２のサブアレイと
を含む、請求項６３に記載の準同型プロセッサＩＣチップ。
【請求項６５】
前記オンチップメモリが、ＤＲＡＭを備える、請求項５８〜６３のいずれかに記載の準同型プロセッサＩＣチップ。
【請求項６６】
準同型プロセッサ集積回路（ＩＣ）チップ内での演算の方法であって、
オンチップメモリを、準同型処理関数用の別々にアクセス可能な記憶ユニットに区分化することであって、前記オンチップメモリが、マルチプル入出力（Ｉ／Ｏ）記憶ユニット、ビット分解多項式記憶ユニット、および回転因子メモリユニットを含む、オンチップメモリを区分化することと、
少なくとも１つの暗号文（Ｃｔｘｔ）演算を、前記区分化されたオンチップメモリに結合された、構成可能な数論変換（ＮＴＴ）バタフライユニットを用いてロードされた数値の組上で行うことと
を含む、方法。
【請求項６７】
前記ＮＴＴドメインの中に対応する変換値を生成するために、前記ロードされた数値の組を変換すること
をさらに含む、請求項６６に記載の方法。
【請求項６８】
前記少なくとも１つのＣｔｘｔ演算が、加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成る前記グループから選択される、請求項６６または６７に記載の方法。
【請求項６９】
前記変換することが、
第１の暗号文（Ｃｔｘｔ）を前記Ｉ／Ｏ記憶ユニットの第１のユニットから行単位フォーマットで読み込むことと、
第２のＣｔｘｔを前記Ｉ／Ｏ記憶ユニットの第２のユニットから列単位フォーマットで読み込むことと
をさらに含む、請求項６７または６８に記載の方法。
【請求項７０】
前記変換することが、
結果的に生じるＣｔｘｔを生成するために、前記第１のＣｔｘｔに前記第２のＣｔｘｔを乗算することと、
前記結果的に生じたＣｔｘｔを前記Ｉ／Ｏ記憶ユニットの第３のユニットに書き込むことと
をさらに含む、請求項６９に記載の方法。
【請求項７１】
前記マルチプルＩ／Ｏ記憶ユニットの１つが、ピンポンメモリユニットとして構成されたそれぞれの第１および第２のサブアレイを含み、前記方法が、
第１の演算を実施するために前記第１のサブアレイを動作させることと、
前記第１の演算と同時並行の第２の演算を実施するために、前記第２のサブアレイを動作させることと
をさらに含む、請求項６６〜７０のいずれかに記載の方法。
【請求項７２】
準同型プロセッサ集積回路（ＩＣ）チップ内での演算の方法であって、
第１の暗号文（Ｃｔｘｔ）を第１のオンチップメモリユニットから取り出すことであって、前記第１のＣｔｘｔは、行フォーマット読出演算を利用して取り出される、第１の暗号文を取り出すことと、
前記第１のＣｔｘｔを数論変換（ＮＴＴ）ドメインに変換することと、
第２の暗号文（Ｃｔｘｔ）を第２のオンチップメモリユニットから取り出すことであって、前記第２のＣｔｘｔは、列フォーマット読出演算を利用して取り出される、第２の暗号文を取り出すことと、
前記第２のＣｔｘｔを前記ＮＴＴドメインに変換することと、
結果として生じるＣｔｘｔを生成するために、前記変換された第１のＣｔｘｔに、前記変換された第２のＣｔｘｔを乗算することと、
前記結果として生じたＣｔｘｔを第３のメモリユニットの中に記憶させることと
を含む、準同型プロセッサ集積回路（ＩＣ）チップ内での演算の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願についての相互参照
本出願は、２０１７年４月１１日に出願された、Ａ  ＨＯＭＯＭＯＲＰＨＩＣ  ＰＲＯＣＥＳＳＩＮＧ  ＵＮＩＴ  （ＨＰＵ）  ＦＯＲ  ＡＣＣＥＬＥＲＡＴＩＮＧ  ＳＥＣＵＲＥ  ＣＯＭＰＵＴＡＴＩＯＮＳ  ＵＮＤＥＲ  ＦＵＬＬＹ  ＨＯＭＯＭＯＲＰＨＩＣ  ＥＮＣＲＹＰＴＩＯＮという名称の米国仮特許出願第６２／４８４，３０４号に対する優先権を主張する通常の出願であり、同仮特許出願全体を参照して本出願に援用する。
【０００２】
本開示は、本明細書においてハードウェアアクセラレータに関し、より詳細には準同型ハードウェアアクセラレータおよび関連方法に関する。
【背景技術】
【０００３】
完全準同型暗号化は、サードパーティが、最初にデータを復号化する必要なく、暗号化されたデータ上で計算を実施することを可能にする。暗号化のこの形態は、ユーザが、自分の個人的な暗号化されたデータを例えばリモートサーバ上に保存し、同時に、データ記憶設備が暗号化されたデータを処理することができるようにすることを可能にする。完全準同型暗号化は、クラウドベースのコンピューティング環境に好適である。
【０００４】
データ所有者に関するプライバシーを維持することによって、大きな保証を提供している反面、暗号化されたデータを伴う演算は、それでもなお計算集約型である。
【発明の概要】
【０００５】
準同型プロセッサチップ、システム、および関連方法が開示される。１つの実施形態では、集積回路（ＩＣ：ｉｎｔｅｇｒａｔｅｄ  ｃｉｒｃｕｉｔ）準同型プロセッサチップが開示される。ＩＣ準同型プロセッサチップは、少なくとも１つのプロセッサスライスを含む。各プロセッサスライスは、ローカル制御回路構成、数論変換（ＮＴＴ：ｎｕｍｅｒｉｃ  ｔｈｅｏｒｅｔｉｃ  ｔｒａｎｓｆｏｒｍ）バタフライユニット、およびオンチップメモリを含む。ＮＴＴバタフライユニットは、準同型暗号を使用して暗号化されたデータ上で演算を行うためのマルチプルモードで動作するためのローカル制御回路構成に応答する。各モードは、ＮＴＴバタフライユニットの異なる構成と関連付けられている。
【０００６】
別の実施形態では、ＮＴＴバタフライユニットは、完全準同型暗号化を伴う演算用のマルチプルモードで動作するためのローカル制御回路構成に応答する。
【０００７】
さらに別の実施形態では、ＮＴＴバタフライユニットは、部分的準同型暗号化を伴う演算用のマルチプルモードで動作するためのローカル制御回路構成に応答する。
【０００８】
別の実施形態では、ＮＴＴバタフライユニット用の第１の構成は、第１の暗号文（Ｃｔｘｔ）関数を実施するために第１の回路構成を使用する。ＮＴＴバタフライユニット用の第２の構成は、第２のＣｔｘｔ関数を実施するために第１の回路構成の少なくとも一部を再利用する。
【０００９】
別の実施形態では、第１の回路構成は、暗号文（Ｃｔｘｔ）加算関数を実施し、一方、第２のＣｔｘｔ関数は、Ｃｔｘｔ乗算関数を備える。
【００１０】
さらに別の実施形態では、第１の回路構成は、モジュラ加算器を含む。
【００１１】
別の実施形態では、モジュラ加算器は、組合せモジュラ加算器を備える。
【００１２】
別の実施形態では、モジュラ加算器は、順次モジュラ加算器を備える。
【００１３】
さらに別の実施形態では、第２の構成は、モジュラ乗算器を備える第２の回路構成を含む。
【００１４】
さらなる実施形態では、モジュラ乗算器は、並列整数乗算器を備える。
【００１５】
別の実施形態では、モジュラ乗算器は、モジュラ約分ユニットをさらに備える。
【００１６】
さらに別の実施形態では、ＩＣ準同型プロセッサは、マルチプルプロセッサスライスを含み、ＩＣ準同型プロセッサは、マルチプルプロセッサスライスを外部プロセッサのインターフェースを介して外部メモリと接続するためのマスタ制御回路構成をさらに含む。
【００１７】
さらに別の実施形態では、ローカル制御回路構成は、１組のＣｔｘｔ係数値をメモリから取り出すようにとの命令をマスタ制御回路構成から受信する。数値の組は、次いで処理パイプラインの中にロードされる。少なくとも１つのＣｔｘｔ演算が、変換値を生成するために行われる。変換値は、次いで転送先メモリ位置に記憶される。
【００１８】
別の実施形態では、マスタ制御回路構成からの命令は、ＮＴＴドメインの中に対応する変換値を生成するために、ロードされた数値の組上でＮＴＴ変換を行うようにとの命令をさらに含む。
【００１９】
さらに別の実施形態では、マスタ制御回路構成からの、少なくとも１つのＣｔｘｔ演算を行うようにとの命令は、加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成るグループから少なくとも１つのＣｔｘｔ演算を行うようにとの命令を含む。
【００２０】
さらに別の実施形態では、ＮＴＴバタフライユニットは、単一ステージユニットとして認識される。
【００２１】
さらなる実施形態では、準同型暗号化システムが開示される。準同型暗号化システムは、集積回路（ＩＣ）準同型プロセッサチップ、およびＩＣ準同型プロセッサチップ外部の主メモリを含む。データパスは、主メモリとＩＣ準同型プロセッサチップとの間でデータを転送する。制御パスは、主メモリとＩＣ準同型プロセッサチップとの間の転送を制御する。ＩＣ準同型プロセッサチップは、マスタ制御回路構成およびマルチプルプロセッサスライスを含む。マスタ制御回路構成は、制御パスを介した主メモリとＩＣ準同型プロセッサチップとの間のデータの転送を制御する。マルチプルプロセッサスライスは、パイプライン深さに対応する。マルチプルプロセッサスライスのそれぞれは、ローカル制御回路構成、数論変換（ＮＴＴ）バタフライユニット、およびオンチップメモリを含む。ＮＴＴバタフライユニットは、準同型暗号化を使用しながら、暗号化されたデータ上で演算を行うためのマルチプルモードで動作するためのローカル制御回路構成に応答する。各モードは、ＮＴＴバタフライユニットの異なる構成と関連付けられている。オンチップメモリは、ローカル制御回路構成およびＮＴＴバタフライユニットに結合されている。
【００２２】
別の実施形態では、準同型暗号化は、完全準同型暗号化を含む。
【００２３】
さらに別の実施形態では、準同型暗号化は、部分的準同型暗号化を含む。
【００２４】
さらに別の実施形態では、マスタ制御回路構成は、マルチプルプロセッサスライスごとに、外部メモリから１組のＣｔｘｔ係数値を取り出して、数値の組を処理パイプラインへロードする動作をスケジュールする。少なくとも１つのＣｔｘｔ演算は、変換値を生成するために行われる。変換値は、次いで転送先メモリ位置に記憶される。
【００２５】
別の実施形態では、マスタ制御回路構成からのスケジュールされた演算は、マルチプルプロセッサスライスごとに、ＮＴＴドメインの中に対応する変換値を生成するために、ロードされた数値の組上でＮＴＴ変換を行う、スケジュールされた演算をさらに含む。
【００２６】
さらに別の実施形態では、マスタ制御回路構成からのスケジュールされた演算は、マルチプルプロセッサスライスごとに、加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成るグループから少なくとも１つのＣｔｘｔ演算を行うスケジュールされた演算をさらに備える。
【００２７】
別の実施形態では、ＮＴＴバタフライユニットのそれぞれは、単一ステージバタフライを備え、所与のＮＴＴ変換演算は、ＮＴＴバタフライユニットによる評価のログ（ｎ）−１ステージを伴い、「ｎ」は、係数値と関連付けられた多項式の次数を表す。
【００２８】
さらに別の実施形態では、数論変換（ＮＴＴ）バタフライ回路が開示される。ＮＴＴバタフライ回路は、第１の加算器／減算器、第１の乗算器、および第１の選択回路構成を含んでいる高入力語パスを含む。第１の選択回路構成は、第１の加算器／減算器および第１の乗算器に結合されており、第１の加算器／減算器および第１の乗算器を選択的に迂回するそれぞれのバイパスパスを含む。ＮＴＴバタフライ回路は、第２の加算器／減算器、第２の乗算器、および第２の選択回路構成を含んでいる低入力語パスを含む。第２の選択回路構成は、第２の加算器／減算器および第２の乗算器に結合されており、第２の加算器／減算器および第２の乗算器を選択的に迂回するそれぞれのバイパスパスを含む。高入力語パスおよび低入力語パスは、交差結合されており、第１および第２の選択回路構成は、異なるモード制御信号に応答して、低入力語パスおよび高入力語パスを異なる論理処理ユニットに再構成する。
【００２９】
さらに別の実施形態では、ＮＴＴバタフライ回路用の第１の構成は、暗号文（Ｃｔｘｔ）加算関数を実施するために、第１の回路構成を使用し、ＮＴＴバタフライ回路用の第２の構成は、Ｃｔｘｔ乗算関数を実施するために、第１の回路構成の少なくとも一部を再利用する。
【００３０】
さらに別の実施形態では、第１および第２の加算器／減算器のそれぞれは、組合せモジュラ加算器を備える。
【００３１】
別の実施形態では、第１および第２の乗算器のそれぞれは、並列整数乗算器を備える。
【００３２】
さらなる実施形態では、第１および第２の乗算器のそれぞれは、モジュラ約分ユニットをさらに含む。
【００３３】
さらに別の実施形態では、第１および第２の加算器／減算器、および乗算器のそれぞれは、関連付けられたクリティカルパスを含んでおり、関連付けられたクリティカルパスのそれぞれは、レジスタ回路構成に囲まれている。
【００３４】
別の実施形態では、ＮＴＴバタフライ回路は、単一ステージバタフライとして認識され、所与のＮＴＴ変換演算は、ＮＴＴバタフライ回路による評価のログ（ｎ）−１ステージを伴い、「ｎ」は、係数値と関連付けられた多項式の次数を表す。
【００３５】
さらに別の実施形態では、準同型プロセッサ集積回路（ＩＣ）チップ内での演算の方法が開示される。方法は、暗号文（Ｃｔｘｔ）記号を数論変換（ＮＴＴ）ドメインに変換することを含む。変換することは、所与のプロセッサスライスに対して、ローカル制御回路構成を用いてモード制御信号を生成することを含む。モード制御信号は、準同型暗号化を伴う演算のマルチプルモードの１つに対応する。ＮＴＴバタフライユニットは、モード制御信号に応答して構成される。
【００３６】
さらに別の実施形態では、準同型暗号化は、完全準同型暗号化を備える。
【００３７】
別の実施形態では、準同型暗号化は、部分的準同型暗号化を備える。
【００３８】
さらに別の実施形態では、モード制御信号は、演算の第１のモードに対応する第１のモード制御信号を備え、ＮＴＴバタフライユニットは、Ｃｔｘｔ加算関数を実施するためにＮＴＴバタフライユニットを構成することによって第１のモード制御信号に応答する。
【００３９】
別の実施形態では、モード制御信号は、演算の第２のモードに対応する第２のモード制御信号を含み、ＮＴＴバタフライユニットが、Ｃｔｘｔ乗算関数を実施するためにＮＴＴバタフライユニットを構成することによって、第２のモード制御信号に応答する。加算関数で利用されたＮＴＴバタフライユニットの一部は、乗算関数を実施するために再利用される。
【００４０】
別の実施形態では、変換することは、各プロセッサスライスが、ローカル制御回路構成のコピーおよびＮＴＴバタフライユニットのコピーを含むように、マルチプルプロセッサスライスを並行して動作させることを含む。
【００４１】
さらに別の実施形態では、方法は、マルチプルプロセッサスライスによって実施されたマルチプル演算をパイプラインで送ることをさらに含む。
【００４２】
さらに別の実施形態では、方法は、マルチプルプロセッサスライスを、外部プロセッサインターフェースを介して外部メモリと接続することをさらに含み、インターフェース接続は、マスタ制御回路構成によって制御される。
【００４３】
さらに別の実施形態では、マスタ制御回路構成は、マルチプルスライスのローカル制御回路構成に対する命令を生成する。ローカル制御回路構成は、メモリから１組のＣｔｘｔ係数数値を取り出すことと、数値の組を処理パイプラインへロードすることと、変換値を生成するために少なくとも１つのＣｔｘｔ演算を行うことと、変換値を外部メモリの中の転送先位置に記憶することとを含むステップを実施するようにという命令に応答する。
【００４４】
別の実施形態では、方法は、ＮＴＴドメインの中に対応する変換値を生成するために、ロードされた数値の組上でＮＴＴ変換を行うことをさらに含む。
【００４５】
さらに別の実施形態では、少なくとも１つのＣｔｘｔ演算は、加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成るグループから選択される。
【００４６】
さらに別の実施形態では、準同型暗号化システム内での演算の方法が開示される。方法は、設定可能な数論変換（ＮＴＴ）バタフライユニットを含んでいる準同型プロセッサ集積回路（ＩＣ）チップを提供することを含む。準同型プロセッサＩＣチップは、データパスおよび制御パスを介して外部メモリとインターフェース接続している。暗号文（Ｃｔｘｔ）記号は、ＮＴＴドメインに変換される。変換することは、所与のプロセッサスライスに対して、ローカル制御回路構成を用いてモード制御信号を生成することを含む。モード制御信号は、準同型暗号化を含む演算のマルチプルモードの１つに対応する。ＮＴＴバタフライユニットは、モード制御信号に応答して構成される。
【００４７】
さらに別の実施形態では、準同型暗号化は、完全準同型暗号化を備える。
【００４８】
さらに別の実施形態では、準同型暗号化は、部分的準同型暗号化を備える。
【００４９】
別の実施形態では、モード制御信号は、演算の第１のモードに対応する第１のモード制御信号を備え、ＮＴＴバタフライユニットは、Ｃｔｘｔ加算関数を実施するためにＮＴＴバタフライユニットを構成することによって第１のモード制御信号に応答する。
【００５０】
さらに別の実施形態では、モード制御信号は、演算の第２のモードに対応する第２のモード制御信号を含み、ＮＴＴバタフライユニットが、Ｃｔｘｔ乗算関数を実施するためにＮＴＴバタフライユニットを構成することによって第２のモード制御信号に応答する。加算関数で利用されるＮＴＴバタフライユニットの一部は、乗算関数を実施するために再利用される。
【００５１】
別の実施形態では、変換することは、各プロセッサスライスが、ローカル制御回路構成のコピーおよびＮＴＴバタフライユニットのコピーを含むように、マルチプルプロセッサスライスを並行して動作させることを含む。
【００５２】
別の実施形態では、方法は、マルチプルプロセッサスライスによって実施されたマルチプル演算をパイプラインで送ることをさらに含む。
【００５３】
さらに別の実施形態では、方法は、マルチプルプロセッサスライスを、外部プロセッサインターフェースを介して外部メモリと接続することをさらに含み、インターフェース接続は、マスタ制御回路構成によって制御される。
【００５４】
別の実施形態では、マスタ制御回路構成は、マルチプルスライスのローカル制御回路構成に対する命令を生成する。ローカル制御回路構成は、メモリから１組のＣｔｘｔ係数数値を取り出すことと、数値の組を処理パイプラインへロードすることと、変換値を生成するために少なくとも１つのＣｔｘｔ演算を行うことと、変換値を外部メモリの中の転送先位置に記憶することとを含むステップを実施するようにという命令に応答する。
【００５５】
別の実施形態では、方法は、ＮＴＴドメインの中に対応する変換値を生成するために、ロードされた数値の組上でＮＴＴ変換を行うことをさらに含む。
【００５６】
さらに別の実施形態では、少なくとも１つのＣｔｘｔ演算は、加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成るグループから選択される。
【００５７】
別の実施形態では、数論変換（ＮＴＴ）バタフライ回路内での演算の方法が開示される。回路は、高入力語パスおよび低入力語パスを含む。高入力語パスは、第１の加算器／減算器、および第１の乗算器を含む。低入力語パスは、第２の加算器／減算器、および第２の乗算器を含む。方法は、第２の加算器／減算器および第２の乗算器を選択的に迂回することと、異なるモード制御信号に応答して、低入力語パスおよび高入力語パスを異なる論理処理ユニットに再構成することとを含む。
【００５８】
さらに別の実施形態では、再構成することは、第１のモード制御信号を受信したことに応答して、暗号文（Ｃｔｘｔ）加算関数を実施するためにＮＴＴバタフライ回路を構成することと、第２のモード制御信号を受信したことに応答して、Ｃｔｘｔ乗算関数を実施するためにＮＴＴバタフライ回路を構成することとを含む。
【００５９】
別の実施形態では、方法は、第１および第２の加算器／減算器ごとに組み合せモジュラ加算器を利用することをさらに含む。
【００６０】
さらに別の実施形態では、方法は、第１および第２の乗算器ごとに並列整数乗算器を利用することをさらに含む。
【００６１】
さらに別の実施形態では、第１および第２の乗算器のそれぞれは、約分ユニットを含み、方法は、それぞれの約分ユニットを動作させることをさらに含む。
【００６２】
別の実施形態では、ＮＴＴバタフライ回路は、単一ステージバタフライとして認識され、変換することは、評価のログ（ｎ）−１ステージを通してＮＴＴバタフライ回路を動作させることを含み、「ｎ」は、係数値と関連付けられた多項式の次数を表す。
【００６３】
さらに別の実施形態では、準同型プロセッサ集積回路（ＩＣ）チップが開示される。ＩＣ準同型プロセッサチップは、少なくとも１つのプロセッサスライスを含む。少なくとも１つのプロセッサスライスは、ローカル制御回路構成、ＮＴＴバタフライユニット、およびオンチップメモリを含む。オンチップメモリは、制御回路構成およびＮＴＴバタフライユニットに結合されて、準同型処理関数用の別々にアクセス可能な記憶ユニットに区分化される。オンチップメモリは、マルチプル入出力（Ｉ／Ｏ：ｉｎｐｕｔ／ｏｕｔｐｕｔ）記憶ユニット、ビット分解多項式記憶ユニット、および回転因子メモリユニットを含む。
【００６４】
別の実施形態では、Ｉ／Ｏ記憶ユニットの第１のユニットは、暗号文（Ｃｔｘｔｓ）を行単位フォーマットで記憶し、Ｉ／Ｏ記憶ユニットの第２のユニットは、Ｃｔｘｔｓを列単位フォーマットで記憶する。
【００６５】
さらに別の実施形態では、Ｉ／Ｏ記憶ユニットの第３のユニットは、第１の記憶ユニットからの第１のＣｔｘｔが第２の記憶ユニットからの第２のＣｔｘｔに乗算されることを伴う乗算演算の結果生じる出力Ｃｔｘｔｓを記憶する。
【００６６】
さらに別の実施形態では、準同型プロセッサ集積回路（ＩＣ）チップは、第２のメモリユニットに結合されたメモリカウンタをさらに含む。
【００６７】
別の実施形態では、Ｉ／Ｏ記憶ユニットの第１のユニットの中の所与の行のＣｔｘｔの単列変換は、Ｉ／Ｏ記憶ユニットの第３のユニットの中の対応する結果的に生じた行になる。
【００６８】
さらに別の実施形態では、マルチプルＩ／Ｏ記憶ユニットの１つは、外部メモリに結合されたピンポンメモリとして構成される。
【００６９】
さらに別の実施形態では、ピンポンメモリは、第１のメモリ演算を実施する第１のサブアレイと、第１のメモリ演算と同時並行の第２の演算を実施する第２のサブアレイとを含む。
【００７０】
別の実施形態では、オンチップメモリは、ＤＲＡＭを備える。
【００７１】
さらに別の実施形態では、準同型プロセッサ集積回路（ＩＣ）チップ内での演算の方法が開示される。方法は、オンチップメモリを、準同型処理関数用の別々にアクセス可能な記憶ユニットに区分化することを含む。オンチップメモリは、マルチプル入出力（Ｉ／Ｏ）記憶ユニット、ビット分解多項式記憶ユニット、および回転因子メモリユニットを含む。少なくとも１つの暗号文（Ｃｔｘｔ）演算は、区分化されたオンチップメモリに結合された、構成可能な数論変換（ＮＴＴ）バタフライユニットを用いて、ロードされた数値の組上で行われる。
【００７２】
別の実施形態では、方法は、ＮＴＴドメインの中に対応する変換値を生成するために、ロードされた数値の組を変換することをさらに含む。
【００７３】
別の実施形態では、少なくとも１つのＣｔｘｔ演算は、加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成るグループから選択される。
【００７４】
さらに別の実施形態では、変換することは、第１の暗号文（Ｃｔｘｔ）をＩ／Ｏ記憶ユニットの第１のユニットから行単位フォーマットで読み込むことと、第２のＣｔｘｔをＩ／Ｏ記憶ユニットの第２のユニットから列単位フォーマットで読み込むこととをさらに含む。
【００７５】
別の実施形態では、変換することは、結果的に生じるＣｔｘｔを生成するために、第１のＣｔｘｔに第２のＣｔｘｔを乗算することと、結果的に生じたＣｔｘｔをＩ／Ｏ記憶ユニットの第３のユニットに書き込むこととをさらに含む。
【００７６】
さらに別の実施形態では、マルチプルＩ／Ｏ記憶ユニットの１つは、ピンポンメモリユニットとして構成されたそれぞれの第１および第２のサブアレイを含む。方法は、第１の演算を実施するために第１のサブアレイを動作させることと、第１の演算と同時並行の第２の演算を実施するために、第２のサブアレイを動作させることとをさらに含む。
【００７７】
別の実施形態では、準同型プロセッサ集積回路（ＩＣ）チップ内での演算の方法が開示される。方法は、行フォーマット読出演算を利用して第１の暗号文（Ｃｔｘｔ）を第１のオンチップメモリユニットから取り出すことを含む。第１のＣｔｘｔは、数論変換（ＮＴＴ）ドメインに変換される。第２の暗号文（Ｃｔｘｔ）は、列フォーマット読出演算を利用して第２のオンチップメモリユニットから取り出される。第２のＣｔｘｔは、ＮＴＴドメインに変換される。変換された第１のＣｔｘｔは、結果として生じるＣｔｘｔを生成するために、変換された第２のＣｔｘｔを乗算される。結果として生じたＣｔｘｔは、第３のメモリユニットの中に記憶される。
【００７８】
開示の実施形態は、類似の参照番号が類似要素を指している添付の図面の図中に例証として、制限を目的とせずに図解されている。
【図面の簡単な説明】
【００７９】
【図１Ａ】準同型暗号化システムの１つの実施形態を図示する。
【図１Ｂ】図１Ａと類似のシステムの実施形態を図示する。
【図１Ｃ】図１Ａと類似のシステムのさらなる実施形態を図示する。
【図２】図１に示す準同型暗号化システムの詳細を図示する。
【図３】図２の構成可能なＮＴＴ／ＩＮＴＴユニットの１つの実施形態を図示する。
【図４】図２のシステムによって行われた順ＮＴＴ演算のタイミング図を示す。
【図５】図２のシステムによって行われた逆ＮＴＴ（ＩＮＴＴ）演算のタイミング図を示す。
【図６】乗算および累積演算のタイミング図を図示する。
【図７】図６のタイミング図に対応するマトリックス行列乗算演算を図示する。
【図８】図２の構成可能なＮＴＴ／ＩＮＴＴユニット用の流れ制御に関するフローチャートの１つの実施形態を図示する。
【図９】演算の標準バタフライモードにあるＮＴＴ／ＩＮＴＴユニットの構成を図示する。
【図１０】演算の加算／減算モードにあるＮＴＴ／ＩＮＴＴユニットの構成を図示する。
【図１１】演算のマトリックス乗算モードにあるＮＴＴ／ＩＮＴＴユニットの構成を図示する。
【図１２】演算のコピーモードにあるＮＴＴ／ＩＮＴＴユニットの構成を図示する。
【図１３】部分的準同型コンテキストの１つの実施形態におけるＮＴＴバタフライユニットの使用を図示する。
【発明を実施するための形態】
【００８０】
ハードウェアアクセラレータおよび関連方法が
開示される。１つの実施形態では、暗号文（Ｃｔｘｔ）記号を数論変換（ＮＴＴ）ドメインに変換するための集積回路（ＩＣ）準同型プロセッサチップが開示される。ＩＣ準同型プロセッサチップは、少なくとも１つのプロセッサスライスを含む。各プロセッサスライスは、ローカル制御回路構成、ＮＴＴバタフライユニット、およびオンチップメモリを含む。ＮＴＴバタフライユニットは、完全同形暗号化を含んでいる演算用のマルチプルモードで動作するためのローカル制御回路構成に応答する。各モードは、ＮＴＴバタフライユニットの異なる構成と関連付けられている。再構成可能なＮＴＴバタフライユニットを利用することによって、異なる関数を達成する別個の回路は、回避されることができ、より効率的なサイクルタイムに寄与する。
【００８１】
図１Ａを参照すると、全体的に１００と称される完全準同型暗号化（ＦＨＥ）システムの１つの実施形態は、集積回路（ＩＣ）準同型処理ユニット（ＨＰＵ）１０２を利用する。ＨＰＵ１０２は、オンチップ暗号文（Ｃｔｘｔ）加算／減算ユニット１０４および乗算器ユニット１０６を含む。数論変換（ＮＴＴ）ユニット１０８は、Ｃｔｘｔ乗算を支援する。１つの実施形態では、加算／減算ユニット１０４、乗算器ユニット１０６、およびＮＴＴユニットは、協働して多機能バタフライユニット２０６を形成する。埋込メモリ１１０は、データを最適様式でコンピューティング機関に送給するために提供される。さらに、システム１００は、機関演算を統制して、外部メモリ１１４への／からのデータ転送を制御するために制御装置１１２を利用する。この全体的なアーキテクチャは、グラフィック処理装置（ＧＰＵ：ｇｒａｐｈｉｃｓ  ｐｒｏｃｅｓｓｉｎｇ  ｕｎｉｔ）などの、従来型のスキームによって示されるダイ面積の部分を使用することを５７×して現在の最高水準のＧＰＵより速い、準同型演算の計算のための（ＲｉｎｇベースのＦＨＥ暗号化スキームのための）ハードウェア加速を提供するサイクルの正確な準同型処理ユニット（ＨＰＵ）を提供する。
【００８２】
いくつかの実施形態では、多機能バタフライユニット２０６は、用途に応じて、異なる関数を行うために、異なる形態をとることができる。図１Ｂは、多機能バタフライユニット２０６を、ＮＴＴ／ＩＮＴＴユニット１０８、およびさまざまなＣｔｘｔ演算の少なくとも１つを実施するためのＣｔｘｔ演算回路構成１０９を含んでいるように図示している。そのような演算の例は、加算、減算、乗算、ＸＯＲ、ＸＮＯＲ、ＡＮＤ、等価、より小さい、より大きい、実体、コピー、および否定を含む。
【００８３】
図１Ｃに図示される１つの実施形態では、多機能バタフライユニット２０６は、上述した多様なＣｔｘｔ演算の少なくとも１つを実施するためのＣｔｘｔ演算回路構成１０９を含む。
【００８４】
図２は、図１に示すシステムに対応している、全体的に２００と称されるＦＨＥシステムの１つの特定の実施形態のさらなる詳細を図示する。システム２００は、処理速度および効率を最大にするために並行して動作することができる論理２０２ａ〜２０２ｎのマルチプル「スライス」で形成された特定用途向け集積回路（ＡＳＩＣ：ａｐｐｌｉｃａｔｉｏｎ  ｓｐｅｃｉｆｉｃ  ｉｎｔｅｇｒａｔｅｄ  ｃｉｒｃｕｉｔ）などの集積回路（ＩＣ）チップ２０１を含む。２０２ａなどでの各スライスは、多機能ＮＴＴバタフライユニット２０６を備えた準同型処理ユニット（ＨＰＵ）コアブロックを画定している。多機能バタフライユニット２０６は、再構成可能であり、ローカル制御ユニット２０８の形態をした分散された制御論理によって制御される。内部埋込記憶アーキテクチャ２１０は、大いに縮小されたフットプリントを呈し、一方同時に呼出し時間を最小化している。外部メモリ２１２は、データパス２１４および制御パス２１６を介してＨＰＵコアスライス２０２とインターフェース接続している。制御パス２１６は、グローバルレベルでシステム２００の演算を統制するためのマスタ制御ユニット２１８を含む。
【００８５】
さらに図２を参照すると、ＨＰＵコアスライス２０２は、大いに簡略化されたマスタ制御ユニット２１８を用いて、より大きいシステムの集積を簡単なタスクにするために、実質的に拡張可能であることができる。「Ｐｏｒｔ１Ｌ」、「Ｐｏｒｔ１Ｈ」および「Ｐｏｒｔ２Ｌ」および「Ｐｏｒｔ２Ｈ」などのコア入出力（Ｉ／Ｏ）は、各ＨＰＵコアスライス２０２の両側に構成される。「Ｈ」および「Ｌ」ポートは共に、ＨＰＵコアスライスに対する入出力ポートであることができる。ＮＴＴ−ドメインデータを暗号文データに変換する逆数論変換（ＩＮＴＴ：ｉｎｖｅｒｓｅ  ｎｕｍｅｒｉｃ  ｔｈｅｏｒｅｔｉｃ  ｔｒａｎｓｆｏｒｍ）エンジンが、ＮＴＴハードウェアと類似のハードウェアを、しかしながらインプレース水平フリッピングを用いて使用することができるので、このことは、有利である。事実上、出力ポートが、入力ポートとして、逆もまた同様に使用される場合、同ＮＴＴ機関は、ＩＮＴＴ関数を計算することができる。これは、さらに、ＮＴＴ機関用のルーティング資源を半分だけ削減し、このことは、それに応じて、設計面積および消費電力を最小化する。
【００８６】
さらに図２を参照すると、内部埋込メモリ２１０が、ＨＰＵコアスライス２０２を、全体的チップフットプリントおよび処理呼出し時間を最小化する様式で効率的にロードするために、提供されている。１つの実施形態では、内蔵メモリ２１０は、オンチップメモリの量を最小化するだけでなく、さらにシステム中の処理呼出し時間を最小化する様式で区分化されている。概括的には、区分化は、入出力（Ｉ／Ｏ）記憶用の４つのメモリユニットＭｅｍ０（２２０）、Ｍｅｍ１（２２２）、Ｍｅｍ２（２２４）、およびＭｅｍ３（２２６）、「ビット分解」（ＢＤ：ｂｉｔ  ｄｅｃｏｍｐｏｓｅｄ）多項式の一時記憶用の１つのメモリユニット２２８、および回転因子メモリユニット２３０を伴う。１対のシフトレジスタ２３２および２３４は、メモリユニット２２０、２２２、２２４、および２２６に接続されており、マルチプレクサＭ３およびＭ４を介してＨＰＵ高および低入力に選択的に結合されている。Ｍｅｍ０などの、４つのＩ／Ｏメモリユニットの１つは、暗号文ロードと関連付けられる遅延を外部メモリ２１２から効果的に隠すために、デュアルバッファ「ピンポン」メモリとして構成されることができる。いくつかの実施形態では、回転因子メモリユニット２３０は、ピンポン方位にさらに構成されることができる。
【００８７】
暗号文ロード遅延を補償するのにさらに役立つために、外部メモリ２１２を用いた内蔵メモリ２１０を接続するデータパス２１４は、Ｃｔｘｔロード命令用のクロックサイクルの数が、例えば加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、否定演算などのＣｔｘｔ演算に限定されないＣｔｘｔ演算を実施するクロックサイクルの数より小さいという条件を満たす幅を有することができる。クロックサイクル毎にデータパスに新しいデータを供給することによって、性能をさらに改善するために、１つの実施形態では、外部メモリインターフェースは、さまざまなＤＤＲＸおよび／またはＧＤＤＲＸメモリ規格のいずれか１つの下で画定されるような、高速ダイナミックランダムアクセスメモリ（ＤＲＡＭ）を利用する。記憶アーキテクチャによって実施されるさまざまな方法を含む、システムの演算が、下文にさらに記載される。
【００８８】
図３は、図２のＮＴＴバタフライユニット２０６に対応する、全体的に３００と称される、多機能バタフライユニットの１つの特定の実施形態を図示する。一般に、多機能バタフライユニット３００は、暗号文（Ｃｔｘｔ）を数論変換（ＮＴＴ）に変換するための回路構成を提供する。ある実施形態では、さらに、ユニットは、ＮＴＴを暗号文に変換して戻すＩＮＴＴ機関の役割をすることができる。一般的には、数論変換（ＮＴＴ）は、離散的フーリエ変換（ＤＦＴ：ｄｉｓｃｒｅｔｅ  Ｆｏｕｒｉｅｒ  ｔｒａｎｓｆｏｒｍ）の有限フィールド等価物である。ＮＴＴは、次数ｎ多項式用のＯ（ｎ２）からＯ（ｎｌｏｇ（ｎ））まで多項式乗算の計算費用を削減する。
【００８９】
さらに図３を参照すると、必須ビルディングブロックとして、多機能バタフライユニット３００は、バタフライトポロジに配列された２つのモジュラ加算器３０２および３０４と、２つのモジュラ乗算器３０６および３０８とを一般的に含む。モジュラ加算器は、用途に応じて、組合せ的であっても、または順次式であってもよい。一般的に言って、単一基数−２バタフライは、以下の一般的公式を有する：
【数１】
2020537756.tif 000003
上式において、ＴＬおよびＴＨは回転因子と呼ばれ、ｑはモジュラスである。
【００９０】
１つの実施形態では、ＮＴＴバタフライユニット３００は、ＦＨＥ暗号化で利用されるマルチプル関数を達成するために、再構成可能性およびさまざまな論理ブロックの再使用を提供する。したがって、ＮＴＴバタフライユニット３００は、モジュラ加算器／減算器論理３０２および３０４、ならびにモジュラ乗算器論理３０６および３０８を含む。モジュラ加算器／減算器ユニットは、一般的には、２つの部分、正規の加算／減算ユニットと、それに続くモジュラ約分ユニットとで構成される。モジュラ約分演算は、結果が、加算の場合にモジュラスｑより多いのか、または減算の場合には、０より小さいのかを調べて、それに応じて結果を調整する。いくつかの実施形態では、キャリールックアヘッド、並列プレフィクス、条件付きサム、またはキャリースキップの加算器のような並列加算器が、利用され得る。
【００９１】
さらに図３を参照すると、モジュラ乗算器３０６および３０８のそれぞれは単一のユニットとして、またはその後にモジュラ約分ユニットが続く整数乗算器として構成されることができる。モジュラ約分ユニットは、バレットモジュラ約分ユニット、特別なプライムモジュラ約分ユニットの形をしていても、またはモンゴメリーモジュラ乗算ユニットなどの、両方のユニットを１つにした単一のユニットとしていてもよい。モジュラ乗算器が、特定の実施形態において何度も繰り返される可能性がある、多機能バタフライの大部分を占めているので、特定の実施例は、特定のコンテキストにおいて、他より望ましい可能性がある。１つの実施形態では、特別なプライムをＳｏｌｉｎａｓプライムからのモジュラスと共に使用することは、ｑ＝２ｌ−２ｄ＋１で、都合よく機能し、ここでは、ｌ＝３１、ｄ＝１７であり、ｑは、モジュラスを表している。システムの性能を改善するために、並列整数乗算器が、利用されることができる。上で画定されたパラメータでは、整数乗算器は、結果的に２ｌ＝６２ビットの出力幅になる。これは、ｌの数値の２倍であり、これは、次いで約分ユニットによって約分されて３１ビットに戻される。
【００９２】
引き続き図３を参照すると、多機能バタフライユニット３００は、さまざまな加算／減算／乗算／コピー、および他のコンピューティング関数に関する論理再使用を効率的に可能にするために、上述した概念的モジュラ加算器およびモジュラ乗算器を、演算の特定のモードにおいて選択可能に交差結合されるそれぞれの低処理パスおよび高処理パス３１０および３１２に組み込んでいる。低処理パス３１０は、マルチプレクサＭ０、およびレジスタＲ０およびＲ８を含む論理の第１ステージを含む。マルチプレクサＭ０は、バタフライに提供される第１の入力ＩｎＬ、および加算器／減算器３０２からフィードバックされた第２の入力を受信する。レジスタＲ０は、Ｍ０から選択された出力を受信し、その一方で、レジスタＲ８は、第２の入力Ｉｎａｄｄ＿Ｌを受信する。レジスタＲ０およびＲ８は、ＮＴＴ演算用の低入力信号をパイプラインで送るために、ラッチまたはレジスタの第１ステージを提供する。加算器／減算器３０２は、実施されている関数に応じて、ローカル制御論理によって選択されたさまざまな入力を受信する。加算器／減算器３０２へのさまざまな入力は、レジスタＲ０からの出力およびレジスタＲ８から生じたＭ２からの選択された出力、または乗算器３０６からのフィードバック、またはレジスタＲ１から（対応する高パス３１２から）の交差結合出力を含むことができる。
【００９３】
さらに図３を参照すると、加算器／減算器３０２からの出力は、マルチプレクサＭ４の１つの入力を含む乗算パスを送給する。バイパスパス３１４は、加算／減算出力を、出力マルチプレクサＭ６に、さらにフィードバックパス３１６に沿って入力マルチプレクサＭ０に送給する。乗算器マルチプレクサＭ４は、入力ＩｎＬを、加算／減算器パスを迂回して、乗算器パスに直接接続するバイパスパス３１８からの第２の入力を含む。第２ステージレジスタＲ２は、Ｍ４から選択された出力を受信して、それを乗算器３０６に提供する。回転因子入力は、さらに、入力ＴＬを介してレジスタＲ４を通って乗算器３０６に適用されることができる。乗算器３０６の出力は、次いで出力マルチプレクサＭ６に送給されることができ、選択的な入力に関して、マルチプレクサＭ２に向かうパス３２０に沿って加算器／減算器３０２にフィードバックされ得る。第３ステージレジスタＲ６は、マルチプレクサＭ６から選択された出力を受信して、出力パッドＯｕｔＬに処理した出力を送給する。
【００９４】
引き続き図３を参照すると、第１ステージレジスタＲ１およびＲ９が、レジスタＲ０およびＲ８と同期して動作し、類似のパイプラインで送られたタイミングが、レジスタＲ３／Ｒ２とＲ７／Ｒ６との間で実施されて、上述した低パス３１０は、高パス３１２によって複製されることができる。上記したように、低パスおよび高パス３１０および３１２は、レジスタＲ０とマルチプレクサＭ３との間で、そしてレジスタＲ１とマルチプレクサＭ２との間で交差結合される。交差結合は、下文でさらに詳細に記載されるように、演算の特定のモードに関して、バタフライの利用可能な論理の機能的再構成可能性および再使用可能性を提供する。
【００９５】
演算では、図２のＦＨＥシステム２００は、Ｃｔｘｔ加算、Ｃｔｘｔ減算、Ｃｔｘｔ乗算、およびＮＴＴ／ＩＮＴＴ処理を含む計算を実施する。いくつかの実施形態では、さらに平文計算を実施する場合もある。特定の演算が、下文でさらに十分に説明されるように、スケジュールされて、処理される様式は、呼出し時間を最小化することによって、性能を大幅に向上させ、一方で、ＩＣチップフットプリントを大いに縮小させることに寄与する。
【００９６】
図４は、図２のシステムによって実施される一般的な演算のいくつかと関連付けられるさまざまなタイミングを示すタイミングチャートを図示する。演算のグループが、示されており、各グループは、利用されるパイプラインの奥行に応じて、ＨＰＵ論理のマルチプル「スライス」によって反復的に実施されるいくつかの同一の計算を伴う。クロックサイクルタイムは、左から右に進んで、ｘ軸に沿って反映されており、各六角形の演算記号は、単一のクロックサイクルで実施される演算を表す。
【００９７】
さらに図４を参照すると、暗号文のＮＴＴドメインへの変換を伴う、順ＮＴＴ演算の例として、３つの主な処理関数が、実施される：（１）ロードして、定数を乗算する、（２）ＮＴＴ、および（３）最終的なＮＴＴおよび記憶する。４０２に示される、第１の演算（ロードして、定数で乗算する）は、一般的には、４０４などで、ＨＰＵコアブロックパイプラインが充填されるまで、内蔵メモリからマルチプル多項式を読み込んで、４０６などで、それらに定数値を乗算する。出力は、次いで、４０８などで出力ポートに送られる。メモリから要素を読み取るように示される２サイクルは、メモリからコンテンツを得る１サイクルと、その後に続く、図２の低シフトレジスタおよび高シフトレジスタ２３２および２３４用の別のサイクルとで構成されることに留意されたい。このステージでの多項式当たりの遅延は、メモリ演算からロードするために２つのクロックサイクルを加えたパイプライン深さに等しい。
【００９８】
引き続き図４を参照すると、４１０に示されるＮＴＴ演算は、それ自体が、パイプラインの中のロードされた多項式上に繰り返し適用され、評価のｌｏｇ２（ｎ）−１ステージを行う。このステージでの多項式当たりの遅延は、パイプライン深さに相当する。次いで、４１２で最終的なＮＴＴ演算が、行われ、その後、結果は、４１４で転送先メモリに戻って記憶される。「新規ＮＴＴの開始」という標識で示されるように、その前の計算が、依然としてパイプラインの中にある一方で、多項式の新しい組のロードおよび変換が始まるので、この最終ステージでの多項式当たりの有効遅延は、２つのクロックサイクルを引いたパイプライン深さに相当する。３つの主な処理関数は、Ｃｔｘｔの中のすべての多項式が変換されるまで、繰り返される。逆ＮＴＴ（ＩＮＴＴ）変換の場合、主な処理関数は、定数乗算演算が、バタフライ演算の後行われること以外は、同様に実施される。
【００９９】
図５は、図４のＮＴＴ演算と同様に実施されるＩＮＴＴ演算の例に関するタイミングを図示する。ＩＮＴＴ関数をスケジューリングすることにおいて、３つの主な演算が、行われる：（１）５０２で、ＩＮＴＴをロードして、行う、（２）５０４で、ＩＮＴＴを行う、および（３）５０６で、定数で乗算して、記憶する。
【０１００】
図４が順ＮＴＴ演算の例に関するタイミングを図示するのに対して、図６は、２つの暗号文、Ｃｔｘｔ１およびＣｔｘｔ２の乗算を伴う暗号文乗算演算に関するタイミングチャートを図示する。処理の間、以下の３つの主な処理関数が実施される。（１）６０２では、第１の多項式のビット分解のためのＮＴＴ、（２）６１４では、第２の多項式のビット分解のためのＮＴＴ、および（３）６１８では、乗算して累算する。
【０１０１】
さらに図６を参照すると、６０２で、第１の多項式のビット分解のためのＮＴＴは、６０４でのように、メモリから第１の暗号文Ｃｔｘｔ１と関連付けられた多項式を読み込むことから始まる。６０６では、多項式の中の各整数の最下位ビットが、次いで、バタフライユニットに出力される。それに続くＬＳＢ出力は、高シフトレジスタおよび低シフトレジスタの数値のシフトを伴う。６１０では、ＮＴＴ変換が、（６０８で、バタフライの加算論理を迂回した後）６１２での定数演算および結果の出力による乗算を含む最下位ビットに関して始まる。
【０１０２】
引き続き図６を参照すると、６１２で、第１のＢＴＴビット分解の結果が出力されると、６１４で、第２の多項式ステップのＮＴＴ分解が、始まる。第２の暗号文Ｃｔｘｔ２と関連付けられた多項式は、次いで、６１６でのようにメモリから読み込まれることができ、第１の暗号文Ｃｔｘｔ１が処理された方法と同様に処理される。
【０１０３】
乗算および累算演算を含む第３のステップでは、６１８で、Ｃｔｘｔ１の変換された行およびＣｔｘｔ２の変換された列を処理して、結果として生じるＣｔｘｔ３の要素を計算する。これは、マトリックス乗算表を用いて図７に図解されており、７０２では、上左端マトリックスは、Ｃｔｘｔ３を表し、一方で、７０４では、中間マトリックスは、Ｃｔｘｔ１を表し、７０６では、右端マトリックスは、Ｃｔｘｔ２を表している。図６の６１８での第３のステップ、乗算および累算は、Ｃｔｘｔ１の別の行を変形して、Ｃｔｘｔ３結果を計算するために、上述した同じ乗算関数を繰り返す前に、Ｃｔｘｔ３の行を計算するために、２回繰り返される。
【０１０４】
１つの実施形態では、メモリコンテンツは、Ｃｔｘｔの行に沿った要素が、次の行に進む前に最初に読み込まれるように、メモリの内部に配置される。図７は、７０４でのＣｔｘｔ１、および７０２でのＣｔｘｔ３の要素は、正規順序で行に沿って読み込まれ、他方で、７０６でのＣｔｘｔ２の要素は、列に沿って読み込まれることを示す。これは、異なる順序で要素を再配置すること、またはこの状況を説明するためにメモリカウンタを利用することを伴う。１つの実施形態は、偶数および奇数のステップをカウントするメモリカウンタを利用する。７０６で、Ｃｔｘｔ２の第１の列を読み込むために、偶数のカウンタが、最初に起動されて、すべての列要素が読み込まれ、次いで、奇数のカウンタが、起動されて、第２の列の要素を取ってくる。
【０１０５】
上述した、図６および図７に示された演算は、Ｃｔｘｔ１の特定の行は、Ｃｔｘｔ３の第１の行を作成するのに、２回だけ必要であることを反映している。これは、Ｃｔｘｔ１のビット分解バージョンを記憶することができる容量の全メモリは、不必要であることを意味する。そのかわりに、１回に単列が、Ｃｔｘｔ３の対応行を計算するために、変換されることができる。その結果、内部埋込メモリの量は、最小化されて、集積回路チップの対応するフットプリントを大いに縮小することができる。
【０１０６】
図８は、上の記述に合った、さまざまな暗号文および平文関数を達成するために、図２に示される特定のメモリアーキテクチャによって実施されるステップのフローチャートを図解する。一般的には、システム２００によって使用される準同型暗号化は、以下の一般方程式を実施することを可能にする：
【数２】
2020537756.tif 000004
上式では、Ｃｉｊｋは、異なる暗号文を表し、Ｐｉｊｋは、平文を表す。図２の内蔵メモリの一部は、上記の方程式と関連付けられる部分結果を記憶するように構成される。
【０１０７】
さらに図２および図８を参照すると、図２のシステムによって利用される流れ制御方法は、ピンポンメモリをうまく活用して、下位メモリユニットでデータを処理して、一方で、デュアルバッファの使用と同様に、他の下位メモリユニットをロードする。これは、上記の一般方程式を効率的に満足するのに役立つ。流れ制御方法は、８０２で、データパス２１４を介して外部メモリ２１２からデータをピンポン下位メモリユニットの１つにロードすることから始まる。８０４では、ピンポンメモリのコンテンツは、次いでＭｅｍ２などの他の埋込メモリの１つにコピーされる。コンテンツをコピーした後、８０６では、ピンポンメモリは、外部メモリ２１２からデータを再ロードされ、８０８では、ピンポンメモリ選択は、切り替えられる。
【０１０８】
さらに図８を参照すると、８０８で、ピンポンメモリ選択を切り替えた後、流れ制御は、２つの並列パスに沿って進む。パスのうちの第１のパスは、８１０で外部メモリからピンポンメモリの１つをロードし、次いで、８２４でメモリ選択を切り替えることを伴う。
【０１０９】
引き続き図８を参照すると、上記の第１のパスによって実施されるステップと同時並行の、第２のパスは、８１２でＮＴＴ関数をピンポンメモリのその他のコンテンツに適用することを伴う。次いで、ＮＴＴビット分解演算は、８１４で、Ｍｅｍ２の２つのラインおよびＭｅｍ３の中に記憶された累算演算の結果に適用される。８１６では、ピンポンメモリおよびＭｅｍ３は次いで乗算され、結果が、Ｍｅｍ２の同じ２つのラインに戻して記憶される。８１８では、次いで、２ｌの繰返しが行われたかどうかが判定される。行われていなかった場合には、ＮＴＴビット分解および乗算ステップが、再び行われる。２ｌの繰返しが行われるまで、サブループが繰り返し適用される。閾値が満たされると、次いで、８２０では、逆ＮＴＴ演算が、Ｍｅｍ２のコンテンツに適用される。
【０１１０】
８２０でＩＮＴＴ演算が適用されると、並列する流れパスは、単一パスに戻り、８２４では、ピンポンメモリ選択が、再び切り替えられる。次いで、８２６では、「Ｋ」暗号文が乗算されたかどうかに関して判定される。乗算されていなかった場合には、８１２では、ＮＴＴ演算が、ピンポンメモリに適用され、ステップ８１４〜８２４が繰り返される。「Ｋ」暗号文が乗算されていた場合には、８２８では、結果が、Ｍｅｍ４に追加される。８３０では、アルゴリズムが完了されるかどうかに関して判定される。追加的な処理が必要とされる場合には、ステップ８０４〜８３０が繰り返される。そうでない場合、流れは、特定の組のデータに関して終了する。
【０１１１】
図９〜図１２は、図３の多機能バタフライユニットが、上述したように、Ｃｔｘｔ加算、減算、乗算、およびＮＴＴ／ＩＮＴＴ変換を含む計算関数を可能にするためにさまざまな方法でどのように構成され得るのかを図示する。
【０１１２】
図９は、演算の規格バタフライモード（太いパスによって示される）用に構成された図３の多機能バタフライユニットを図示する。構成を画定している接続部は、以下の一般公式を実施する、制御論理によってディスパッチされた制御信号に応答している。
【数３】
2020537756.tif 000005
これは、各マルチプレクサの出力に移動するある特定の入力の選択を可能にするために、適切な制御信号を生成して、マルチプレクサＭ０〜Ｍ７のそれぞれへ適用することによって達成される。その結果、低パス３１０では、Ｍ０は、信号ＩｎＬをＲ０への入力として通す。Ｒ０の出力は、減算器として構成される高パス加算器／減算器３０４への入力としてＭ３を通して送給されることになる。Ｒ０出力は、さらに、加算器として構成される低パス加算器／減算器３０２への入力に送給される。加算器３０２の出力は、Ｒ２への入力として、Ｍ４によって通される。Ｒ２の出力は、低パス乗算器３０６に送給される。回転因子ＴＬは、Ｒ４への入力として送給され、一方で、Ｒ４の出力は、乗算器３０６への第２の入力として送給される。乗算器３０６の出力は、Ｒ６への入力として、Ｍ６を通して送給される。Ｒ６の出力は、低パス３１０用の結果として生じる出力ＯｕｔＬになる。高パス３１２も、同様に構成されるが、簡潔にするために、各接続部の詳細な説明は省略する。
【０１１３】
図１０は、以下の一般公式を実施する演算の加算／減算モード用に構成された多機能バタフライユニット３００を図示する：
【数４】
2020537756.tif 000006
制御論理によって発せられる制御信号は、したがって、規格バタフライモードに類似しているけれども、低パスおよび高パス３１０および３１２が、モジュラ乗算器３０６および３０８を通常迂回するように、バタフライユニット３００にマルチプレクサを設定している。低パスおよび高パス３１０および３１２は、さらに、交差結合を実施しない。そのうえ、加算／減算モードでは、追加的な入力Ｉｎａｄｄ＿ＬおよびＩｎａｄｄ＿Ｈは、レジスタＲ８およびＲ９を介してモジュラ加算器／減算器ユニット３０２および３０４のそれぞれに供給される。
【０１１４】
図１１は、以下の一般公式を実施する演算のマトリックス乗算モード用に構成された、多機能バタフライユニット３００を図示する：
【数５】
2020537756.tif 000007
この構成は、加算器としてモジュラ加算器／減算器ユニット３０２および３０４と、パスを交差結合していない低パスおよび高パス３１０および３１２両方の乗算器ユニット３０８および３０６とを利用する、乗算および累算関数を実現する。低パス３１０は、Ｒ４を介して供給される回転因子入力ＴＬと乗算するためにＭ４を介してレジスタＲ２に入力ＩｎＬを供給することを伴う。加算器３０２は、Ｍ２を介して乗算器３０６の出力と、さらにＭ０を介してＲ０にフィードバックされる自体の出力とを受信する。加算器出力は、Ｍ６を通ってＲ６に送給され、それは、出力ＯｕｔＬとして示されている。高パス３１２も、同様に構成される。
【０１１５】
図１２は、以下の一般公式を実施する演算のコピーモード用に構成された、多機能バタフライユニット３００を図示する：
【数６】
2020537756.tif 000008
本質的には、コピーモードは、ただ入力ＩｎＬおよびＩｎＨを通って直接出力ＯｕｔＬおよびＯｕｔＨに移動する際に、モジュラ加算器／減算器３０２および３０４、およびモジュラ乗算器を迂回することを伴う。
【０１１６】
上述したＦＨＥシステムは、付随するハードウェア資源として、サードパーティデータを処理する必要があり得る一般的なコンピューティングプラットホームおよび／またはサーバプラットホームに好適である。そのような環境では、１つまたは複数のＨＰＵ集積回路チップは、サーバ演算と並列して行われることができる集中的な準同型処理タスクを実施するために、コプロセッサまたはハードウェアアクセラレータとして１つまたは複数のサーバユニットの中に据え付けられることができる。ＨＰＵがそのような特定のタスクを処理するように構成されている場合、サーバ処理資源は、サーバ特有のタスクに対して保存されるおよび／または開放されることができる。
【０１１７】
本開示は、これまで主として完全な準同型のコンテキストで実施形態を論じてきたが、本明細書に示されるさまざまな概念は、同様に部分的準同型のコンテキストにおいても利用されることができる。一例として、高スループット適用に関して、Ｐａｉｌｌｉｅｒ暗号化システムのような、部分的準同型暗号化システムをサポートするために、現在提案されている設計に付加的な再構成可能度を追加することが可能である。Ｐａｉｌｌｉｅｒ暗号化システムのような、これらの部分的準同型暗号化スキームは、通常、例えばＳｃｈｏｎｈａｇｅ−Ｓｔｒａｓｓｅｎ、Ｋａｒａｔｓｕｂａ、またはＴｏｏｍ−Ｃｏｏｋアルゴリズムを用いて実施されることができる大きな整数乗算器を伴う。普遍性を失わずに、これらのアルゴリズムを上述したＨＰＵハードウェアへインスタン化する一例として、Ｓｃｈｏｎｈａｇｅ−Ｓｔｒａｓｓｅｎアルゴリズムは、高速整数乗算を行うのに高速多項式乗算を使用する。２つの入力数字「ａ」および「ｂ」に大きい整数乗算を行うために、アルゴリズムの結果としておそらく生じる可能性がある最大整数を最初に計算し、次いで、オーバフローを回避するために、この最大である可能性のある結果より大きい整数「ｗ」を選択する。その後、以下の通りに「ａ」および「ｂ」を「ｗ」ビットの「ｍ」グループに分割する：
【０１１８】
【数７】
2020537756.tif 000009
【０１１９】
ｘ＝２ｗにすると、次いで、前の方程式は、同等になる。
【０１２０】
【数８】
2020537756.tif 000010
【０１２１】
次いで、以下のように述べることができる。
【０１２２】
【数９】
2020537756.tif 000011
【０１２３】
上記の方程式は、本明細書に記載され、図１３の部分的準同型コンテキストに示される数論変換（ＮＴＴ）機関などのＮＴＴユニットを用いて、効率的に計算されることができる。入力数字「ａ」および「ｂ」は、ＮＴＴユニット１３０２および１３０４のそれぞれに送給される。数字は、１３０６で乗算演算を受け、その後１３０８で、ＩＮＴＴ演算が続く。次いで、結果「ｃ」を達成するために、１３１０でキャリー演算が行われる。
【０１２４】
上述したＳｃｈｏｎｈａｇｅ−Ｓｔｒａｓｓｅｎアルゴリズムは、入力整数を、各部分が、隣接する多項式係数の中に記憶されるより小さい部分に区分化することによって、本明細書に記載されるＮＴＴ機関を使用して効率的に実施されることができる。その後、ＮＴＴ変換は、両方の多項式上に適用されることができ、係数に関する乗算は、変換された多項式上で行われる。最終的に、結果は、変換されて係数表示に戻されて、最終的なキャリー伝播が行われることになる。
【０１２５】
そのような実施例は、広範囲にわたる重要な適用、例えば、安全な投票システム、ブロックチェーン、安全な契約、特定の分散計算（ＭＰＣ：ｍｕｌｔｉ−ｐａｒｔｙ  ｃｏｍｐｕｔａｔｉｏｎ）アルゴリズム、および暗号の通用性で見つけられるものを加速することに有用性を見い出すことになる。
【０１２６】
当業者には理解されるように、上述したアーキテクチャは、単一の集積回路チップ上で準同型暗号化処理関数を実施する計算時間をかなり短縮する。さらに、効果的なメモリ使用量によって、チップのサイズおよび電源消費が、最小化される。
【０１２７】
１つまたは複数のコンピュータ可読媒体を介してコンピュータシステムの中で受信されるとき、上述された回路のそのようなデータおよび／または命令ベース表現式は、そのような回路の物理的発現の表示または画像を生成するために、ネットリスト生成プログラム、場所およびルートプログラム、および類似のもの、これらに限定するわけではないが、を含む、１つまたは複数の他のコンピュータプログラムの実行と関連したコンピュータシステムの中で、処理エンティティ（例えば１つまたは複数のプロセッサ）によって処理されることができる。そのような表示または画像は、その後、例えば、デバイス製造プロセスにおいて回路の各種構成要素を形成するのに使用される１つまたは複数のマスクの生成を可能にすることによって、デバイス製造で使用されることができる。
【０１２８】
前述の説明の中で、そして添付の図面において、特定の用語および図面記号が、本発明の十分な理解を提供するために示されてきた。いくつかの例では、用語および記号は、本発明を実施するのに必要とされない具体的な詳細を包含する場合もある。例えば、ビットの固有番号、信号パス幅、信号または動作周波数、構成要素回路、またはデバイスなどのいずれかが、代替実施形態では、上述したものとは異なる場合もある。さらに、多重導体信号回線として示される、または記載される回路要素または回路ブロックの間の相互接続が、代替的に単一導体信号回線である場合もあり、単一導体信号回線が、代替的に多重導体信号回線である場合もある。さらに、シングルエンド形であるように示される、または記載される信号および信号パスが、差別的ある場合もあり、逆もまた同様である。同様に、正論理または負論理レベルを有するように記載された、または描写された信号が、代替実施形態において逆の論理レベルを有する場合もある。集積回路装置の中の構成要素回路構成が、金属酸化膜半導体（ＭＯＳ：ｍｅｔａｌ  ｏｘｉｄｅ  ｓｅｍｉｃｏｎｄｕｃｔｏｒ）技術、バイポーラ技術、または論理回路およびアナログ回路が実装される場合のある何らかの他の技術を用いて、実装される場合もある。用語に関して、特定の状態を示すために、信号が低論理状態または高論理状態に駆動される（または高論理状態に充電される、もしくは低論理状態に放電される）とき、信号は、「アサート」されていると言われる。これとは逆に、信号は、信号が、アサートされた状態（高論理状態または低論理状態、または信号駆動回路が、オープンドレインまたはオープンコレクタ状態などの高インピーダンス状態に推移されるときに、発生する可能性がある浮動状態を含む）以外の状態に駆動される（充電されるまたは放電される）ことを示すために「デアサート」されていると言われる。信号駆動回路が、信号駆動回路と信号受信回路との間に結合された信号ライン上の信号をアサートする、（または、明示的に述べられる、またはコンテキストによって指示される場合にはデアサートする）とき、信号駆動回路は、信号受信回路に信号を「出力する」と言われる。信号が、信号ライン上にアサートされるとき、信号ラインは、「活性化される」と言われ、信号が、デアサートされるとき、「非活性化される」と言われる。その上、信号名に付加されるプレフィックス記号「／」は、信号が、有効低信号である（すなわちアサートされた状態は、論理ロー状態である）ことを示す。さらに、信号名の上のライン（例えば、
2020537756.tif 000012
）は、有効低信号を示すのに使用される。「結合される」という用語は、直接的な接続、ならびに１つまたは複数の介在回路または構造物を介した接続を表現するために本明細書では使用される。集積回路デバイス「プログラミング」は、例えば、そして限定するわけではなく、ホスト命令に応答して、制御値をデバイス内のレジスタまたは他の記憶回路の中にロードすること、したがって、デバイスの動作態様を制御することと、デバイス構成を確立すること、または１回限りのプログラミング動作によってデバイスの動作態様を制御すること（例えば、デバイス生産の間、構成回路内のヒューズをブローイングすること）と、および／または特定のデバイス構成またはデバイスの動作態様を確立するために、１つまたは複数の選択されたピンまたはデバイスの他の接続構造を、基準電圧ラインに結合すること（ストラッピングとも呼ばれる）とを含む場合がある。「例示的な」という用語は、優先傾向または要件ではなく、一例を表すのに使用される。
【０１２９】
実施形態によれば、ＨＰＵチップは、コンピュータカード、ＵＳＢスティックの形態、またはコンピュータプロセッサに接続される何らかの他の形態をしたシステム上に取り付けられてもよい。
【０１３０】
本明細書に開示される実施形態のさまざまな態様および特徴は、例えば、制限するわけではなく、以下の番号を付された条項で説明される：
１．
少なくとも１つのプロセッサスライスを備え、スライスが、
ローカル制御回路構成と、
準同型暗号を使用して暗号化されたデータ上で演算を行うためのマルチプルモードで動作するためのローカル制御回路構成に応答し、各モードは、ＮＴＴバタフライユニットの異なる構成と関連付けられている、数論変換（ＮＴＴ）バタフライユニットと、
制御回路構成およびＮＴＴバタフライユニットに結合されたオンチップメモリと
を含む、
集積回路（ＩＣ）準同型プロセッサチップ。
２．
ＮＴＴバタフライユニットが、完全準同型暗号化を伴う演算用のマルチプルモードで動作するためのローカル制御回路構成に応答する、条項１に記載のＩＣ準同型プロセッサチップ。
３．
ＮＴＴバタフライユニットが、部分的準同型暗号化を伴う演算用のマルチプルモードで動作するためのローカル制御回路構成に応答する、条項１に記載のＩＣ準同型プロセッサチップ。
４．
ＮＴＴバタフライユニット用の第１の構成が、第１の暗号文（Ｃｔｘｔ）関数を実施するために第１の回路構成を使用し、
ＮＴＴバタフライユニット用の第２の構成が、第２のＣｔｘｔ関数を実施するために第１の回路構成の少なくとも一部を再利用する、
条項１に記載のＩＣ準同型プロセッサチップ。
５．
第１の回路構成が、暗号文（Ｃｔｘｔ）加算関数を実施し、
第２のＣｔｘｔ関数が、Ｃｔｘｔ乗算関数を備える、
条項４に記載のＩＣ準同型プロセッサチップ。
６．
第１の回路構成が、モジュラ加算器を含む、
条項５に記載のＩＣ準同型プロセッサチップ。
７．
モジュラ加算器が、組合せモジュラ加算器を備える、
条項６に記載のＩＣ準同型プロセッサチップ。
８．
モジュラ加算器が、順次モジュラ加算器を備える、
条項６に記載のＩＣ準同型プロセッサチップ。
９．
第２の構成が、モジュラ乗算器を備える第２の回路構成を含む、
条項５に記載のＩＣ準同型プロセッサチップ。
１０．
モジュラ乗算器が、並列整数乗算器を備える、条項９に記載のＩＣ準同型プロセッサチップ。
１１．
モジュラ乗算器が、
モジュラ約分ユニット
をさらに備える、条項１０に記載のＩＣ準同型プロセッサチップ。
１２．
ＩＣ準同型プロセッサが、マルチプルプロセッサスライスを含み、ＩＣ準同型プロセッサが、
マルチプルプロセッサスライスを外部プロセッサのインターフェースを介して外部メモリと接続するためのマスタ制御回路構成
をさらに備える、条項１に記載のＩＣ準同型プロセッサチップ。
１３．
ローカル制御回路構成が、
マスタ制御回路構成から、１組のＣｔｘｔ係数値をメモリから取り出し、
数値の組を処理パイプラインへロードし、
少なくとも１つのＣｔｘｔ演算を行い、
変換値を転送先メモリ位置に記憶させる
ようにとの命令を受け取る、条項１２に記載のＩＣ準同型プロセッサチップ。
１４．
マスタ制御回路構成からの命令が、
ＮＴＴドメインの中に対応する変換値を生成するために、ロードされた数値の組上でＮＴＴ変換を行う
ようにとの命令をさらに含む、条項１３に記載のＩＣ準同型プロセッサチップ。
１５．
マスタ制御回路構成からの、少なくとも１つのＣｔｘｔ演算を行うようにとの命令が、
加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成るグループから少なくとも１つのＣｔｘｔ演算を行う
ようにとの命令を含む、条項１４に記載のＩＣ準同型プロセッサチップ。
１６．
ＮＴＴバタフライユニットが、単一ステージユニットとして認識される、
条項１に記載のＩＣ準同型プロセッサチップ。
１７．
集積回路（ＩＣ）準同型プロセッサチップと、
ＩＣ準同型プロセッサチップ外部の主メモリと、
主メモリとＩＣ準同型プロセッサチップとの間でデータを転送するデータパスと、
主メモリとＩＣ準同型プロセッサチップとの間の転送を制御する制御パスとを備え、
ＩＣ準同型プロセッサチップが、
制御パスを介した主メモリとＩＣ準同型プロセッサチップとの間のデータの転送を制御するマスタ制御回路構成；および
パイプライン深さに対応するマルチプルプロセッサスライスであって、マルチプルプロセッサスライスのそれぞれが、
ローカル制御回路構成と、
準同型暗号化を使用しながら、暗号化されたデータ上で演算を行うためのマルチプルモードで動作するためのローカル制御回路構成に応答する数論変換（ＮＴＴ）バタフライユニットであって、各モードが、ＮＴＴバタフライユニットの異なる構成と関連付けられている数論変換（ＮＴＴ）バタフライユニットと、
ローカル制御回路構成およびＮＴＴバタフライユニットに結合されているオンチップメモリと
を含むマルチプルプロセッサスライスを備える、
準同型暗号化システム。
１８．
準同型暗号化が、完全準同型暗号化を備える、条項１７に記載の準同型暗号化システム。
１９．
準同型暗号化が、部分的準同型暗号化を備える、条項１７に記載の準同型暗号化システム。
２０．
マスタ制御回路構成が、
外部メモリから１組のＣｔｘｔ係数値を取り出し、
数値の組を処理パイプラインへロードし、
変換値を生成するために少なくとも１つのＣｔｘｔ演算を行い、
変換値を転送先メモリ位置に記憶させる
演算を、マルチプルプロセッサスライスごとにスケジュールする、条項１７に記載の準同型暗号化システム。
２１．
マスタ制御回路構成からのスケジュールされた演算が、マルチプルプロセッサスライスごとに、
ＮＴＴドメインの中に対応する変換値を生成するために、ロードされた数値の組上でＮＴＴ変換を行う
スケジュールされた演算をさらに備える、条項２０に記載の準同型暗号化システム。
２２．
マスタ制御回路構成からのスケジュールされた演算が、マルチプルプロセッサスライスごとに、
加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成るグループから少なくとも１つのＣｔｘｔ演算を行う
スケジュールされた演算をさらに備える、条項２１に記載の準同型暗号化システム。
２３．
ＮＴＴバタフライユニットのそれぞれが、単一ステージバタフライを備え、
所与のＮＴＴ変換演算が、ＮＴＴバタフライユニットによる評価のログ（ｎ）−１ステージを伴い、「ｎ」が、係数値と関連付けられた多項式の次数を表す、
条項２０に記載の準同型暗号化システム。
２４．
第１の加算器／減算器、
第１の乗算器、および
第１の加算器／減算器および第１の乗算器に結合されており、第１の加算器／減算器および第１の乗算器を選択的に迂回するそれぞれのバイパスパスを含む第１の選択回路構成
を含んでいる高入力語パスと、
第２の加算器／減算器、
第２の乗算器、および
第２の加算器／減算器および第２の乗算器に結合されており、第２の加算器／減算器および第２の乗算器を選択的に迂回するそれぞれのバイパスパスを含む第２の選択回路構成
を含んでいる低入力語パスと
を備え、
高入力語パスおよび低入力語パスが、交差結合されており、第１および第２の選択回路構成が、異なるモード制御信号に応答して、低入力語パスおよび高入力語パスを異なる論理処理ユニットに再構成する、数論変換（ＮＴＴ）バタフライ回路。
２５．
ＮＴＴバタフライ回路用の第１の構成が、暗号文（Ｃｔｘｔ）加算関数を実施するために、第１の回路構成を使用し、
ＮＴＴバタフライ回路用の第２の構成が、Ｃｔｘｔ乗算関数を実施するために、第１の回路構成の少なくとも一部を再利用する、
条項２４に記載のＮＴＴバタフライ回路。
２６．
第１および第２の加算器／減算器のそれぞれが、組合せモジュラ加算器を備える、条項２４に記載のＮＴＴバタフライ回路。
２７．
第１および第２の乗算器のそれぞれが、並列整数乗算器を備える、条項２４に記載のＮＴＴバタフライ回路。
２８．
第１および第２の乗算器のそれぞれが、
モジュラ約分ユニット
をさらに備える、条項２４に記載のＮＴＴバタフライ回路。
２９．
第１および第２の加算器／減算器、および乗算器のそれぞれが、関連付けられたクリティカルパスを含んでおり、
関連付けられたクリティカルパスのそれぞれが、レジスタ回路構成に囲まれている、条項２４に記載のＮＴＴバタフライ回路。
３０．
ＮＴＴバタフライ回路が、単一ステージバタフライとして認識され、
所与のＮＴＴ変換演算が、ＮＴＴバタフライ回路による評価のログ（ｎ）−１ステージを伴い、「ｎ」が、係数値と関連付けられた多項式の次数を表す、
条項２４に記載のＮＴＴバタフライ回路。
３１．
準同型プロセッサ集積回路（ＩＣ）チップ内での演算の方法であって、
暗号文（Ｃｔｘｔ）記号を数論変換（ＮＴＴ）ドメインに変換することを含み、変換することは、所与のプロセッサスライスに対して、
ローカル制御回路構成を用いてモード制御信号を生成することであって、モード制御信号は、準同型暗号化を伴う演算のマルチプルモードの１つに対応する、モード制御信号を生成することと、
モード制御信号に応答してＮＴＴバタフライユニットを構成することと
を含む、
準同型プロセッサ集積回路（ＩＣ）チップ内での演算の方法。
３２．
準同型暗号化が、完全準同型暗号化を備える、条項３１に記載の準同型プロセッサＩＣチップ内での演算の方法。
３３．
準同型暗号化が、部分的準同型暗号化を備える、条項３１に記載の準同型プロセッサＩＣチップ内での演算の方法。
３４．
モード制御信号が、演算の第１のモードに対応する第１のモード制御信号を備え、ＮＴＴバタフライユニットが、
Ｃｔｘｔ加算関数を実施するためにＮＴＴバタフライユニットを構成することによって第１のモード制御信号に応答する、条項３１に記載の方法。
３５．
モード制御信号が、演算の第２のモードに対応する第２のモード制御信号を備え、ＮＴＴバタフライユニットが、
Ｃｔｘｔ乗算関数を実施するためにＮＴＴバタフライユニットを構成することと、
乗算関数を実施するために加算関数で利用されたＮＴＴバタフライユニットの一部を再利用することと
によって第２のモード制御信号に応答する、条項３４に記載の方法。
３６．
変換することが、
マルチプルプロセッサスライスを並行して動作させることを含み、各プロセッサスライスが、ローカル制御回路構成のコピーおよびＮＴＴバタフライユニットのコピーを含む、条項３１に記載の方法。
３７．
マルチプルプロセッサスライスによって実施されたマルチプル演算をパイプラインで送ること
をさらに含む、条項３６に記載の方法。
３８．
マルチプルプロセッサスライスを、外部プロセッサインターフェースを介して外部メモリと接続することをさらに含み、インターフェース接続が、マスタ制御回路構成によって制御される、
条項３７に記載の方法。
３９．
マスタ制御回路構成が、マルチプルスライスのローカル制御回路構成に対する命令を生成し、ローカル制御回路構成が、
メモリから１組のＣｔｘｔ係数数値を取り出すことと、
数値の組を処理パイプラインへロードすることと、
変換値を生成するために少なくとも１つのＣｔｘｔ演算を行うことと、
変換値を外部メモリの中の転送先位置に記憶することと
を含むステップを実施するようにという命令に応答する、条項３８に記載の方法。
４０．
ＮＴＴドメインの中に対応する変換値を生成するために、ロードされた数値の組上でＮＴＴ変換を行うステップをさらに含む、条項３９に記載の方法。
４１．
少なくとも１つのＣｔｘｔ演算が、加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成るグループから選択される、条項４０に記載の方法。
４２．
準同型暗号化システム内での演算の方法であって、
設定可能な数論変換（ＮＴＴ）バタフライ論理を含んでいる準同型プロセッサ集積回路（ＩＣ）チップを提供することと、
準同型プロセッサＩＣチップをデータパスおよび制御パスを介して外部メモリとインターフェース接続することと、
暗号文（Ｃｔｘｔ）記号をＮＴＴドメインに変換することであって、変換することは、
所与のプロセッサスライスに対して、ローカル制御回路構成を用いてモード制御信号を生成することであって、モード制御信号は、準同型暗号化を伴う演算のマルチプルモードの１つに対応する、モード制御信号を生成することと、
モード制御信号に応答してＮＴＴバタフライユニットを構成することと
を含む暗号文（Ｃｔｘｔ）記号をＮＴＴドメインに変換することと
を含む、準同型暗号化システム内での演算の方法。
４３．
準同型暗号化が、完全準同型暗号化を備える、条項４２に記載の準同型暗号化システム内での演算の方法。
４４．
準同型暗号化が、部分的準同型暗号化を備える、条項４２に記載の準同型暗号化システム内での演算の方法。
４４．
モード制御信号が、演算の第１のモードに対応する第１のモード制御信号を備え、ＮＴＴバタフライユニットが、
Ｃｔｘｔ加算関数を実施するためにＮＴＴバタフライユニットを構成すること
によって第１のモード制御信号に応答する、条項４２に記載の方法。
４５．
モード制御信号が、演算の第２のモードに対応する第２のモード制御信号を備え、ＮＴＴバタフライユニットが、Ｃｔｘｔ乗算関数を実施するためにＮＴＴバタフライユニットを構成することと、
乗算関数を実施するために加算関数で利用されるＮＴＴバタフライユニットの一部を再利用することと
によって第２のモード制御信号に応答する、条項４４に記載の方法。
４６．
変換することが、
マルチプルプロセッサスライスを並行して動作させることを含み、各プロセッサスライスが、ローカル制御回路構成のコピーおよびＮＴＴバタフライユニットのコピーを含む、条項４２に記載の方法。
４７．
マルチプルプロセッサスライスによって実施されたマルチプル演算をパイプラインで送ること
をさらに含む、条項４６に記載の方法。
４８．
マルチプルプロセッサスライスを、外部プロセッサインターフェースを介して外部メモリと接続することをさらに含み、インターフェース接続が、マスタ制御回路構成によって制御される、条項４７に記載の方法。
４９．
マスタ制御回路構成が、マルチプルスライスのローカル制御回路構成に対する命令を生成し、ローカル制御回路構成が、
メモリから１組のＣｔｘｔ係数数値を取り出すことと、
数値の組を処理パイプラインへロードすることと、
変換値を生成するために少なくとも１つのＣｔｘｔ演算を行うことと、
変換値を外部メモリの中の転送先位置に記憶することと
を含むステップを実施するようにという命令に応答する、条項４８に記載の方法。
５０．
ＮＴＴドメインの中に対応する変換値を生成するために、ロードされた数値の組上でＮＴＴ変換を行うステップをさらに含む、条項４９に記載の方法。
５１．
少なくとも１つのＣｔｘｔ演算が、加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成るグループから選択される、条項５０に記載の方法。
５２．
数論変換（ＮＴＴ）バタフライ回路内での演算の方法であって、回路が、高入力語パスおよび低入力語パスを含み、高入力語パスが、第１の加算器／減算器、および第１の乗算器を含み、低入力語パスが、第２の加算器／減算器、および第２の乗算器を含み、方法が、
第２の加算器／減算器および第２の乗算器を選択的に迂回することと、
異なるモード制御信号に応答して、低入力語パスおよび高入力語パスを異なる論理処理ユニットに再構成することと
を含む、数論変換（ＮＴＴ）バタフライ回路内での演算の方法。
５３．
再構成することが、
第１のモード制御信号を受信したことに応答して、暗号文（Ｃｔｘｔ）加算関数を実施するためにＮＴＴバタフライ回路を構成することと、
第２のモード制御信号を受信したことに応答して、Ｃｔｘｔ乗算関数を実施するためにＮＴＴバタフライ回路を構成することと
を含む、条項５２に記載の方法。
５４．
第１および第２の加算器／減算器ごとに組み合せモジュラ加算器を利用すること
をさらに含む、条項５２に記載の方法。
５５．
第１および第２の乗算器ごとに並列整数乗算器を利用すること
をさらに含む、条項５２に記載の方法。
５６．
第１および第２の乗算器のそれぞれが、約分ユニットを含み、方法が、
それぞれの約分ユニットを動作させること
をさらに含む、条項５２に記載の方法。
５７．
ＮＴＴバタフライ回路が、単一ステージバタフライとして認識され、変換することが、
評価のログ（ｎ）−１ステージを通してＮＴＴバタフライ回路を動作させることを含み、「ｎ」が、係数値と関連付けられた多項式の次数を表す、
条項５２に記載のＮＴＴバタフライ回路。
５８．
暗号文（Ｃｔｘｔ）記号を数論変換（ＮＴＴ）ドメインに変換するための準同型プロセッサ集積回路（ＩＣ）チップであって、ＩＣ準同型プロセッサチップは、
少なくとも１つのプロセッサスライスを備え、スライスは、
ローカル制御回路構成、
ＮＴＴバタフライユニット、および
制御回路構成およびＮＴＴバタフライユニットに結合されたオンチップメモリを含み、オンチップメモリは、準同型処理関数用の別々にアクセス可能な記憶ユニットに区分化されており、オンチップメモリは、
マルチプル入出力（Ｉ／Ｏ）記憶ユニット、
ビット分解多項式記憶ユニット、および
回転因子メモリユニット
を含む、
暗号文（Ｃｔｘｔ）記号を数論変換（ＮＴＴ）ドメインに変換するための準同型プロセッサ集積回路（ＩＣ）チップ。
５９．
Ｉ／Ｏ記憶ユニットの第１のユニットが、暗号文（Ｃｔｘｔｓ）を行単位フォーマットで記憶し、
Ｉ／Ｏ記憶ユニットの第２のユニットが、Ｃｔｘｔｓを列単位フォーマットで記憶する、
条項５８に記載の準同型プロセッサＩＣチップ。
６０．
Ｉ／Ｏ記憶ユニットの第３のユニットが、第１の記憶ユニットからの第１のＣｔｘｔが第２の記憶ユニットからの第２のＣｔｘｔに乗算されることを伴う乗算演算の結果生じる出力Ｃｔｘｔｓを記憶する、
条項５９に記載の準同型プロセッサＩＣチップ。
６１．
第２のメモリユニットに結合されたメモリカウンタ
をさらに備える、条項６０に記載の準同型プロセッサＩＣチップ。
６２．
Ｉ／Ｏ記憶ユニットの第１のユニットの中の所与の行のＣｔｘｔの単列変換が、Ｉ／Ｏ記憶ユニットの第３のユニットの中の対応する結果的に生じた行になる、
条項６０に記載の準同型プロセッサＩＣチップ。
６３．
マルチプルＩ／Ｏ記憶ユニットの１つが、外部メモリに結合されたピンポンメモリとして構成される、
条項５８に記載の準同型プロセッサＩＣチップ。
６４．
ピンポンメモリが、
第１のメモリ演算を実施する第１のサブアレイと、
第１のメモリ演算と同時並行の第２の演算を実施する第２のサブアレイと
を含む、条項６３に記載の準同型プロセッサＩＣチップ。
６５．
オンチップメモリが、ＤＲＡＭを備える、条項６３に記載の準同型プロセッサＩＣチップ。
６６．
準同型プロセッサ集積回路（ＩＣ）チップ内での演算の方法であって、
オンチップメモリを、準同型処理関数用の別々にアクセス可能な記憶ユニットに区分化することであって、オンチップメモリが、マルチプル入出力（Ｉ／Ｏ）記憶ユニット、ビット分解多項式記憶ユニット、および回転因子メモリユニットを含む、オンチップメモリを区分化することと、
少なくとも１つの暗号文（Ｃｔｘｔ）演算を、区分化されたオンチップメモリに結合された、構成可能な数論変換（ＮＴＴ）バタフライユニットを用いてロードされた数値の組上で行うことと
を含む、方法。
６７．
ＮＴＴドメインの中に対応する変換値を生成するために、ロードされた数値の組を変換すること
をさらに含む、条項６６に記載の方法。
６８．
少なくとも１つのＣｔｘｔ演算が、加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成るグループから選択される、条項６７に記載の方法。
６９．
変換することが、
第１の暗号文（Ｃｔｘｔ）をＩ／Ｏ記憶ユニットの第１のユニットから行単位フォーマットで読み込むことと、
第２のＣｔｘｔをＩ／Ｏ記憶ユニットの第２のユニットから列単位フォーマットで読み込むことと
をさらに含む、条項６７に記載の方法。
７０．
変換することが、
結果的に生じるＣｔｘｔを生成するために、第１のＣｔｘｔに第２のＣｔｘｔを乗算することと、
結果的に生じたＣｔｘｔをＩ／Ｏ記憶ユニットの第３のユニットに書き込むことと
をさらに含む、条項６９に記載の方法。
７１．
マルチプルＩ／Ｏ記憶ユニットの１つが、ピンポンメモリユニットとして構成されたそれぞれの第１および第２のサブアレイを含み、方法が、
第１の演算を実施するために第１のサブアレイを動作させることと、
第１の演算と同時並行の第２の演算を実施するために、第２のサブアレイを動作させることと
をさらに含む、条項６６に記載の方法。
７２．
準同型プロセッサ集積回路（ＩＣ）チップ内での演算の方法であって、
第１の暗号文（Ｃｔｘｔ）を第１のオンチップメモリユニットから取り出すことであって、第１のＣｔｘｔは、行フォーマット読出演算を利用して取り出される、第１の暗号文を取り出すことと、
第１のＣｔｘｔを数論変換（ＮＴＴ）ドメインに変換することと、
第２の暗号文（Ｃｔｘｔ）を第２のオンチップメモリユニットから取り出すことであって、第２のＣｔｘｔは、列フォーマット読出演算を利用して取り出される、第２の暗号文を取り出すことと、
第２のＣｔｘｔをＮＴＴドメインに変換することと、
結果として生じるＣｔｘｔを生成するために、変換された第１のＣｔｘｔに、変換された第２のＣｔｘｔを乗算することと、
結果として生じたＣｔｘｔを第３のメモリユニットの中に記憶させることと
を含む、準同型プロセッサ集積回路（ＩＣ）チップ内での演算の方法。
【０１３１】
本発明は、その特定の実施形態を参照しながら、説明されてきたが、本発明のより広い趣旨および範囲を逸脱しない範囲で、それにさまざまな変更態様および改変を加えることができることは明白である。例えば、少なくとも、実施形態の他のどれかと組み合わせて、またはその対応する特徴または態様の代わりに実行可能である場合には、実施形態のいずれかの特徴または態様は、適用されることができる。したがって、明細書および図面は、制限的な意味ではなく例証的なものとみなされるべきである。
【図１Ａ】
2020537756.tif 000013
【図１Ｂ】
2020537756.tif 000014
【図１Ｃ】
2020537756.tif 000015
【図２】
2020537756.tif 000016
【図３】
2020537756.tif 000017
【図４】
2020537756.tif 000018
【図５】
2020537756.tif 000019
【図６】
2020537756.tif 000020
【図７】
2020537756.tif 000021
【図８】
2020537756.tif 000022
【図９】
2020537756.tif 000023
【図１０】
2020537756.tif 000024
【図１１】
2020537756.tif 000025
【図１２】
2020537756.tif 000026
【図１３】
2020537756.tif 000027
【手続補正書】
【提出日】令和2年8月11日(2020.8.11)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
集積回路（ＩＣ）準同型プロセッサチップであって、前記プロセッサチップが、
少なくとも１つのプロセッサスライスであって、前記プロセッサスライスが、
ローカル制御回路構成と、
準同型暗号を使用して暗号化されたデータ上で演算を行うためのマルチプルモードで動作するために前記ローカル制御回路構成に応答する数論変換（ＮＴＴ）バタフライユニットであって、各モードは、前記ＮＴＴバタフライユニットの異なる構成と関連付けられている、ＮＴＴバタフライユニットと、
前記制御回路構成および前記ＮＴＴバタフライユニットに結合されたオンチップメモリと、
を含む、プロセッサスライス
を備える、ＩＣ準同型プロセッサチップ。
【請求項２】
前記ＮＴＴバタフライユニットが、完全準同型暗号化を伴う演算用のマルチプルモードで動作するために前記ローカル制御回路構成に応答する、請求項１に記載のＩＣ準同型プロセッサチップ。
【請求項３】
前記ＮＴＴバタフライユニットが、部分的準同型暗号化を伴う演算用のマルチプルモードで動作するために前記ローカル制御回路構成に応答する、請求項１に記載のＩＣ準同型プロセッサチップ。
【請求項４】
前記ＮＴＴバタフライユニット用の第１の構成が、第１の暗号文（Ｃｔｘｔ）関数を実施するために第１の回路構成を使用し、
前記ＮＴＴバタフライユニット用の第２の構成が、第２のＣｔｘｔ関数を実施するために前記第１の回路構成の少なくとも一部を再利用する、
請求項１〜３のいずれか一項に記載のＩＣ準同型プロセッサチップ。
【請求項５】
前記第１の回路構成が、暗号文（Ｃｔｘｔ）加算関数を実施し、
前記第２のＣｔｘｔ関数が、Ｃｔｘｔ乗算関数を備える、
請求項４に記載のＩＣ準同型プロセッサチップ。
【請求項６】
前記第１の回路構成が、モジュラ加算器を含む、
請求項５に記載のＩＣ準同型プロセッサチップ。
【請求項７】
前記モジュラ加算器が、組合せモジュラ加算器を備える、
請求項６に記載のＩＣ準同型プロセッサチップ。
【請求項８】
前記モジュラ加算器が、順次モジュラ加算器を備える、
請求項６に記載のＩＣ準同型プロセッサチップ。
【請求項９】
前記第２の構成が、モジュラ乗算器を備える第２の回路構成を含む、
請求項５に記載のＩＣ準同型プロセッサチップ。
【請求項１０】
前記モジュラ乗算器が、並列整数乗算器を備える、請求項９に記載のＩＣ準同型プロセッサチップ。
【請求項１１】
前記モジュラ乗算器が、
モジュラ約分ユニット
をさらに備える、請求項１０に記載のＩＣ準同型プロセッサチップ。
【請求項１２】
前記ＩＣ準同型プロセッサが、マルチプルプロセッサスライスを含み、前記ＩＣ準同型プロセッサが、
前記マルチプルプロセッサスライスを外部プロセッサのインターフェースを介して外部メモリと接続するためのマスタ制御回路構成
をさらに備える、請求項１〜１１のいずれか一項に記載のＩＣ準同型プロセッサチップ。
【請求項１３】
前記ローカル制御回路構成が、
前記マスタ制御回路構成から、１組のＣｔｘｔ係数値を前記メモリから取り出し、
前記１組のＣｔｘｔ係数値を処理パイプラインへロードし、
変換値を生成するために少なくとも１つのＣｔｘｔ演算を行い、
前記変換値を転送先メモリ位置に記憶させる
ようにとの命令を受け取る、請求項１２に記載のＩＣ準同型プロセッサチップ。
【請求項１４】
前記マスタ制御回路構成からの命令が、
前記ＮＴＴドメインの中に対応する変換値を生成するために、前記ロードされた数値の組上でＮＴＴ変換を行う
ようにとの命令をさらに含む、請求項１３に記載のＩＣ準同型プロセッサチップ。
【請求項１５】
前記マスタ制御回路構成からの、少なくとも１つのＣｔｘｔ演算を行うようにとの命令が、
加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成るグループから少なくとも１つのＣｔｘｔ演算を行う
ようにとの命令を含む、請求項１３または１４に記載のＩＣ準同型プロセッサチップ。
【請求項１６】
前記ＮＴＴバタフライユニットが、単一ステージユニットとして認識される、
請求項１〜１５のいずれか一項に記載のＩＣ準同型プロセッサチップ。
【請求項１７】
準同型暗号化システムであって、前記システムが、
集積回路（ＩＣ）準同型プロセッサチップと、
前記ＩＣ準同型プロセッサチップ外部の主メモリと、
前記主メモリと前記ＩＣ準同型プロセッサチップとの間でデータを転送するデータパスと、
前記主メモリと前記ＩＣ準同型プロセッサチップとの間の転送を制御する制御パスと、
を備え、
前記ＩＣ準同型プロセッサチップが、
前記制御パスを介した前記主メモリと前記ＩＣ準同型プロセッサチップとの間のデータの転送を制御するマスタ制御回路構成、および
パイプライン深さに対応するマルチプルプロセッサスライスであって、前記マルチプルプロセッサスライスのそれぞれが、
ローカル制御回路構成と、
準同型暗号化を使用しながら、暗号化されたデータ上で演算を行うためのマルチプルモードで動作するために前記ローカル制御回路構成に応答する数論変換（ＮＴＴ）バタフライユニットであって、各モードが、前記ＮＴＴバタフライユニットの異なる構成と関連付けられている数論変換（ＮＴＴ）バタフライユニットと、
前記ローカル制御回路構成および前記ＮＴＴバタフライユニットに結合されているオンチップメモリと、
を含むマルチプルプロセッサスライスを備える、
準同型暗号化システム。
【請求項１８】
前記準同型暗号化が、完全準同型暗号化を備える、請求項１７に記載の準同型暗号化システム。
【請求項１９】
前記準同型暗号化が、部分的準同型暗号化を備える、請求項１７に記載の準同型暗号化システム。
【請求項２０】
前記マスタ制御回路構成が、
前記外部メモリから１組のＣｔｘｔ係数値を取り出し、
前記１組のＣｔｘｔ係数値を処理パイプラインへロードし、
少なくとも１つのＣｔｘｔ演算を行い、
前記変換値を転送先メモリ位置に記憶させる
演算を、前記マルチプルプロセッサスライスごとにスケジュールする、請求項１７〜１９のいずれか一項に記載の準同型暗号化システム。
【請求項２１】
前記マスタ制御回路構成からのスケジュールされた演算が、前記マルチプルプロセッサスライスごとに、
前記ＮＴＴドメインの中に対応する変換値を生成するために、前記ロードされた数値の組上でＮＴＴ変換演算を行う
スケジュールされた演算をさらに備える、請求項２０に記載の準同型暗号化システム。
【請求項２２】
前記マスタ制御回路構成からのスケジュールされた演算が、前記マルチプルプロセッサスライスごとに、
加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成るグループから少なくとも１つのＣｔｘｔ演算を行う
スケジュールされた演算をさらに備える、請求項２０または２１に記載の準同型暗号化システム。
【請求項２３】
前記ＮＴＴバタフライユニットのそれぞれが、単一ステージバタフライを備え、
所与のＮＴＴ変換演算が、前記ＮＴＴバタフライユニットによる評価のログ（ｎ）−１ステージを伴い、式中、「ｎ」が、前記係数値と関連付けられた多項式の次数を表す、
請求項２１に記載の準同型暗号化システム。
【請求項２４】
数論変換（ＮＴＴ）バタフライ回路であって、前記バタフライ回路が、
高入力語パスであって、
第１の加算器／減算器、
第１の乗算器、および
前記第１の加算器／減算器および前記第１の乗算器に結合されており、前記第１の加算器／減算器および前記第１の乗算器を選択的に迂回するそれぞれのバイパスパスを含む第１の選択回路構成
を含んでいる、高入力語パスと、
低入力語パスであって、
第２の加算器／減算器、
第２の乗算器、および
前記第２の加算器／減算器および前記第２の乗算器に結合されており、前記第２の加算器／減算器および前記第２の乗算器を選択的に迂回するそれぞれのバイパスパスを含む第２の選択回路構成
を含んでいる、低入力語パスと、
を備え、
前記高入力語パスおよび前記低入力語パスが、交差結合されており、前記第１の選択回路構成および前記第２の選択回路構成が、異なるモード制御信号に応答して、前記低入力語パスおよび前記高入力語パスを異なる論理処理ユニットに再構成する、ＮＴＴバタフライ回路。
【請求項２５】
前記ＮＴＴバタフライ回路用の第１の構成が、暗号文（Ｃｔｘｔ）加算関数を実施するために、第１の回路構成を使用し、
前記ＮＴＴバタフライ回路用の第２の構成が、Ｃｔｘｔ乗算関数を実施するために、前記第１の回路構成の少なくとも一部を再利用する、
請求項２４に記載のＮＴＴバタフライ回路。
【請求項２６】
前記第１の加算器／減算器および前記第２の加算器／減算器のそれぞれが、組合せモジュラ加算器を備える、
請求項２４に記載のＮＴＴバタフライ回路。
【請求項２７】
前記第１の乗算器および前記第２の乗算器のそれぞれが、並列整数乗算器を備える、
請求項２４に記載のＮＴＴバタフライ回路。
【請求項２８】
前記第１の乗算器および前記第２の乗算器のそれぞれが、
モジュラ約分ユニット
をさらに備える、請求項２４に記載のＮＴＴバタフライ回路。
【請求項２９】
前記第１の加算器／減算器および前記第２の加算器／減算器、ならびに前記第１の乗算器および前記第２の乗算器のそれぞれが、関連付けられたクリティカルパスを含んでおり、
前記関連付けられたクリティカルパスのそれぞれが、レジスタ回路構成に囲まれている、
請求項２４に記載のＮＴＴバタフライ回路。
【請求項３０】
前記ＮＴＴバタフライ回路が、単一ステージバタフライとして認識され、
所与のＮＴＴ変換演算が、前記ＮＴＴバタフライ回路による評価のログ（ｎ）−１ステージを伴い、式中、「ｎ」が、前記係数値と関連付けられた多項式の次数を表す、
請求項２４に記載のＮＴＴバタフライ回路。
【請求項３１】
準同型プロセッサ集積回路（ＩＣ）チップ内での演算の方法であって、前記方法が、
暗号文（Ｃｔｘｔ）記号を数論変換（ＮＴＴ）ドメインに変換することであって、前記変換することは、所与のプロセッサスライスに対して、
ローカル制御回路構成を用いてモード制御信号を生成することであって、前記モード制御信号は、準同型暗号化を伴う演算のマルチプルモードの１つに対応することと、
前記モード制御信号に応答してＮＴＴバタフライユニットを構成することと、
を含むこと
を含む、方法。
【請求項３２】
前記準同型暗号化が、完全準同型暗号化または部分的準同型暗号化のどちらかを備える、請求項３１に記載の方法。
【請求項３３】
前記モード制御信号が、演算の第１のモードに対応する第１のモード制御信号を備え、前記ＮＴＴバタフライユニットが、
Ｃｔｘｔ加算関数を実施するために前記ＮＴＴバタフライユニットを構成すること
によって前記第１のモード制御信号に応答する、請求項３１〜３２のいずれか一項に記載の方法。
【請求項３４】
前記モード制御信号が、演算の第２のモードに対応する第２のモード制御信号を備え、前記ＮＴＴバタフライユニットが、
Ｃｔｘｔ乗算関数を実施するために前記ＮＴＴバタフライユニットを構成することと、
前記乗算関数を実施するために前記加算関数で利用された前記ＮＴＴバタフライユニットの一部を再利用することと、
によって前記第２のモード制御信号に応答する、請求項３３に記載の方法。
【請求項３５】
前記変換することが、
マルチプルプロセッサスライスを並行して動作させることであって、各プロセッサスライスが、前記ローカル制御回路構成のコピーおよび前記ＮＴＴバタフライユニットのコピーを含むこと
を含む、請求項３１〜３４のいずれか一項に記載の方法。
【請求項３６】
前記マルチプルプロセッサスライスによって実施されたマルチプル演算をパイプラインで送ること
をさらに含む、請求項３５に記載の方法。
【請求項３７】
前記マルチプルプロセッサスライスを、外部プロセッサインターフェースを介して外部メモリと接続することであって、前記インターフェース接続が、マスタ制御回路構成によって制御されること
をさらに含む、請求項３６に記載の方法。
【請求項３８】
前記マスタ制御回路構成が、前記マルチプルスライスのローカル制御回路構成に対する命令を生成し、前記ローカル制御回路構成が、
前記メモリから１組のＣｔｘｔ係数値を取り出すことと、
前記１組のＣｔｘｔ係数値を処理パイプラインへロードすることと、
変換値を生成するために少なくとも１つのＣｔｘｔ演算を行うことと、
前記変換値を前記外部メモリの中の転送先位置に記憶することと、
を含むステップを実施するようにという前記命令に応答する、請求項３７に記載の方法。
【請求項３９】
前記ＮＴＴドメインの中に対応する変換値を生成するために、前記ロードされた数値の組上でＮＴＴ変換を行う前記ステップをさらに含む、請求項３８に記載の方法。
【請求項４０】
前記少なくとも１つのＣｔｘｔ演算が、加算演算、減算演算、乗算演算、ＸＯＲ演算、ＸＮＯＲ演算、ＡＮＤ演算、等価演算、より小さい演算、より大きい演算、実体演算、コピー演算、および否定演算から成るグループから選択される、請求項３８または３９に記載の方法。
【請求項４１】
準同型暗号化システム内での演算の方法であって、前記方法が、
設定可能な数論変換（ＮＴＴ）バタフライユニットを含んでいる準同型プロセッサ集積回路（ＩＣ）チップを提供することと、
前記準同型プロセッサＩＣチップをデータパスおよび制御パスを介して外部メモリとインターフェース接続することと、
暗号文（Ｃｔｘｔ）記号をＮＴＴドメインに変換することであって、前記変換することは、
所与のプロセッサスライスに対して、ローカル制御回路構成を用いてモード制御信号を生成することであって、前記モード制御信号は、準同型暗号化を伴う演算のマルチプルモードの１つに対応することと、
前記モード制御信号に応答して前記ＮＴＴバタフライユニットを構成することと、
を含む暗号文（Ｃｔｘｔ）記号をＮＴＴドメインに変換することと、
を含む、方法。
【請求項４２】
前記準同型暗号化が、完全準同型暗号化または部分的準同型暗号化のどちらかを備える、請求項４１に記載の方法。
【請求項４３】
前記モード制御信号が、演算の第１のモードに対応する第１のモード制御信号を備え、前記ＮＴＴバタフライユニットが、
Ｃｔｘｔ加算関数を実施するためにＮＴＴバタフライユニットを構成すること
によって前記第１のモード制御信号に応答する、請求項４１または４２に記載の方法。
【請求項４４】
前記モード制御信号が、演算の第２のモードに対応する第２のモード制御信号を備え、前記ＮＴＴバタフライユニットが、Ｃｔｘｔ乗算関数を実施するために前記ＮＴＴバタフライユニットを構成することと、
前記乗算関数を実施するために前記加算関数で利用される前記ＮＴＴバタフライユニットの一部を再利用することと、
によって前記第２のモード制御信号に応答する、請求項４３に記載の方法。
【請求項４５】
前記変換することが、
マルチプルプロセッサスライスを並行して動作させることであって、各プロセッサスライスが、ローカル制御回路構成のコピーおよび前記ＮＴＴバタフライユニットのコピーを含むこと
を含む、請求項４１〜４４のいずれか一項に記載の方法。
【請求項４６】
前記マルチプルプロセッサスライスによって実施されたマルチプル演算をパイプラインで送ること
をさらに含む、請求項４５に記載の方法。
【請求項４７】
前記マルチプルプロセッサスライスを、外部プロセッサインターフェースを介して外部メモリと接続することであって、前記インターフェース接続が、マスタ制御回路構成によって制御されること
をさらに含む、請求項４６に記載の方法。
【請求項４８】
前記マスタ制御回路構成が、前記マルチプルスライスの前記ローカル制御回路構成に対する命令を生成し、前記ローカル制御回路構成が、
前記メモリから１組のＣｔｘｔ係数値を取り出すことと、
前記１組のＣｔｘｔ係数値を処理パイプラインへロードすることと、
変換値を生成するために少なくとも１つのＣｔｘｔ演算を行うことと、
前記変換値を前記外部メモリの中の転送先位置に記憶することと、
を含むステップを実施するようにという前記命令に応答する、請求項４７に記載の方法。
【請求項４９】
前記ＮＴＴドメインの中に対応する変換値を生成するために、前記ロードされた数値の組上でＮＴＴ変換を行う前記ステップをさらに含む、請求項４８に記載の方法。
【請求項５０】
数論変換（ＮＴＴ）バタフライ回路内での演算の方法であって、前記回路が、高入力語パスおよび低入力語パスを含み、前記高入力語パスが、第１の加算器／減算器、および第１の乗算器を含み、前記低入力語パスが、第２の加算器／減算器、および第２の乗算器を含み、前記方法が、
前記第２の加算器／減算器および前記第２の乗算器を選択的に迂回することと、
異なるモード制御信号に応答して、前記低入力語パスおよび前記高入力語パスを異なる論理処理ユニットに再構成することと、
を含む、方法。
【請求項５１】
前記再構成することが、
第１のモード制御信号を受信したことに応答して、暗号文（Ｃｔｘｔ）加算関数を実施するために前記ＮＴＴバタフライ回路を構成することと、
第２のモード制御信号を受信したことに応答して、Ｃｔｘｔ乗算関数を実施するために前記ＮＴＴバタフライ回路を構成することと、
を含む、請求項５０に記載の方法。
【請求項５２】
前記第１の加算器／減算器および前記第２の加算器／減算器ごとに組み合せモジュラ加算器を利用すること
をさらに含む、請求項５０〜５１のいずれか一項に記載の方法。
【請求項５３】
前記第１の乗算器および前記第２の乗算器ごとに並列整数乗算器を利用すること
をさらに含む、請求項５０〜５２のいずれか一項に記載の方法。
【請求項５４】
前記第１の乗算器および前記第２の乗算器のそれぞれが、約分ユニットを含み、前記方法が、
それぞれの約分ユニットを動作させること
をさらに含む、請求項５０〜５３のいずれか一項に記載の方法。
【請求項５５】
前記ＮＴＴバタフライ回路が、単一ステージバタフライとして認識され、前記変換することが、
評価のログ（ｎ）−１ステージを通して前記ＮＴＴバタフライ回路を動作させることであって、式中、「ｎ」が、係数値と関連付けられた多項式の次数を表すこと
を含む、請求項５０〜５４のいずれか一項に記載の方法。
【請求項５６】
暗号文（Ｃｔｘｔ）記号を数論変換（ＮＴＴ）ドメインに変換するための準同型プロセッサ集積回路（ＩＣ）チップであって、前記準同型プロセッサＩＣチップが、
少なくとも１つのプロセッサスライスを備え、前記スライスは、
ローカル制御回路構成、
ＮＴＴバタフライユニット、および
前記制御回路構成および前記ＮＴＴバタフライユニットに結合されたオンチップメモリを含み、前記オンチップメモリは、準同型処理関数用の別々にアクセス可能な記憶ユニットに区分化されており、前記オンチップメモリは、
マルチプル入出力（Ｉ／Ｏ）記憶ユニット、
ビット分解多項式記憶ユニット、および
回転因子メモリユニット
を含む、
準同型プロセッサＩＣチップ。
【請求項５７】
前記Ｉ／Ｏ記憶ユニットの第１のユニットが、暗号文（Ｃｔｘｔｓ）を行単位フォーマットで記憶し、
前記Ｉ／Ｏ記憶ユニットの第２のユニットが、Ｃｔｘｔｓを列単位フォーマットで記憶する、
請求項５６に記載の準同型プロセッサＩＣチップ。
【請求項５８】
前記Ｉ／Ｏ記憶ユニットの第３のユニットが、前記第１の記憶ユニットからの第１のＣｔｘｔが前記第２の記憶ユニットからの第２のＣｔｘｔに乗算されることを伴う乗算演算の結果生じる出力Ｃｔｘｔｓを記憶する、
請求項５７に記載の準同型プロセッサＩＣチップ。
【請求項５９】
前記第２のメモリユニットに結合されたメモリカウンタ
をさらに備える、請求項５８に記載の準同型プロセッサＩＣチップ。
【請求項６０】
前記Ｉ／Ｏ記憶ユニットの第１のユニットの中の所与の行のＣｔｘｔの単列変換が、前記Ｉ／Ｏ記憶ユニットの第３のユニットの中の対応する結果的に生じた行になる、
請求項５８または５９に記載の準同型プロセッサＩＣチップ。
【請求項６１】
前記マルチプルＩ／Ｏ記憶ユニットの１つが、外部メモリに結合されたピンポンメモリとして構成される、
請求項５６〜６０のいずれか一項に記載の準同型プロセッサＩＣチップ。
【請求項６２】
前記ピンポンメモリが、
第１のメモリ演算を実施する第１のサブアレイと、
前記第１のメモリ演算と同時並行の第２の演算を実施する第２のサブアレイと、
を含む、請求項６１に記載の準同型プロセッサＩＣチップ。
【請求項６３】
準同型プロセッサ集積回路（ＩＣ）チップ内での演算の方法であって、前記方法が、
オンチップメモリを、準同型処理関数用の別々にアクセス可能な記憶ユニットに区分化することであって、前記オンチップメモリが、マルチプル入出力（Ｉ／Ｏ）記憶ユニット、ビット分解多項式記憶ユニット、および回転因子メモリユニットを含むことと、
少なくとも１つの暗号文（Ｃｔｘｔ）演算を、前記区分化されたオンチップメモリに結合された、構成可能な数論変換（ＮＴＴ）バタフライユニットを用いてロードされた数値の組上で行うことと、
を含む、方法。
【請求項６４】
前記ＮＴＴドメインの中に対応する変換値を生成するために、前記ロードされた数値の組を変換すること
をさらに含む、請求項６３に記載の方法。
【請求項６５】
前記変換することが、
第１の暗号文（Ｃｔｘｔ）を前記Ｉ／Ｏ記憶ユニットの第１のユニットから行単位フォーマットで読み込むことと、
第２のＣｔｘｔを前記Ｉ／Ｏ記憶ユニットの第２のユニットから列単位フォーマットで読み込むことと、
をさらに含む、請求項６４に記載の方法。
【請求項６６】
前記変換することが、
結果的に生じるＣｔｘｔを生成するために、前記第１のＣｔｘｔに前記第２のＣｔｘｔを乗算することと、
前記結果的に生じたＣｔｘｔを前記Ｉ／Ｏ記憶ユニットの第３のユニットに書き込むことと、
をさらに含む、請求項６５に記載の方法。
【請求項６７】
前記マルチプルＩ／Ｏ記憶ユニットの１つが、ピンポンメモリユニットとして構成されたそれぞれの第１のサブアレイおよび第２のサブアレイを含み、前記方法が、
第１の演算を実施するために前記第１のサブアレイを動作させることと、
前記第１の演算と同時並行の第２の演算を実施するために、前記第２のサブアレイを動作させることと、
をさらに含む、請求項６３〜６６のいずれか一項に記載の方法。
【請求項６８】
準同型プロセッサ集積回路（ＩＣ）チップ内での演算の方法であって、前記方法が、
第１の暗号文（Ｃｔｘｔ）を第１のオンチップメモリユニットから取り出すことであって、前記第１のＣｔｘｔは、行フォーマット読出演算を利用して取り出されることと、
前記第１のＣｔｘｔを数論変換（ＮＴＴ）ドメインに変換することと、
第２の暗号文（Ｃｔｘｔ）を第２のオンチップメモリユニットから取り出すことであって、前記第２のＣｔｘｔは、列フォーマット読出演算を利用して取り出されることと、
前記第２のＣｔｘｔを前記ＮＴＴドメインに変換することと、
結果として生じるＣｔｘｔを生成するために、前記変換された第１のＣｔｘｔに、前記変換された第２のＣｔｘｔを乗算することと、
前記結果として生じるＣｔｘｔを第３のメモリユニットの中に記憶させることと、
を含む、方法。
【請求項６９】
回路であって、
数論変換（ＮＴＴ）論理であって、
高入力語パス、
低入力語パス、および
制御信号入力を有する選択回路構成
を含む、ＮＴＴ論理
を備える、回路であり、
演算の第１のモードに関しては、
前記選択回路構成が、第１の制御信号に応答して、前記高入力語パスおよび前記低入力語パスを第１の論理処理ユニットに構成し、
演算の第２のモードに関しては、
前記選択回路構成が、第２の制御信号に応答して、前記高入力語パスおよび前記低入力語パスを、前記第１の論理処理ユニットとは異なる第２の論理処理ユニットに構成する、
回路。
【請求項７０】
設定可能な数論変換（ＮＴＴ）バタフライユニットであって、前記バタフライユニットが、
高入力語パスと、
低入力語パスと、
第１のモード制御信号に応答して、ＮＴＴ変換演算を実施するために前記高入力語パスおよび前記低入力語パスを構成する交差結合論理であって、所与のＮＴＴ変換演算は、前記ＮＴＴバタフライユニットによる評価のログ２（ｎ）−１ステージが続く始めのＮＴＴステップを伴い、式中、「ｎ」は、係数値と関連付けられた多項式の次数を表す、交差結合論理と、
を備え、
前記交差結合論理が、第２のモード制御信号に応答して、前記高入力語パスおよび前記低入力語パスを、第１の論理処理ユニットとは異なる第２の論理処理ユニットに構成する、ＮＴＴバタフライユニット。
【請求項７１】
高入力語パス、低入力語パス、および制御信号入力を有する選択回路構成を含む数論変換（ＮＴＴ）バタフライユニットのための演算の方法であって、前記方法が、
演算の第１のモードに関しては、
前記選択回路構成が第１の制御信号を受信することに応答して、前記高入力語パスおよび前記低入力語パスを第１の論理処理ユニットに構成することと、
演算の第２のモードに関しては、
前記高入力語パスおよび前記低入力語パスを、前記第１の論理処理ユニットとは異なる第２の論理処理ユニットに構成することであって、前記構成することが、前記第１の制御信号とは異なる第２の制御信号を受信することに応答して、前記選択回路構成によって実施されることと、
を含む、方法。
【請求項７２】
数論変換（ＮＴＴ）バタフライユニットを動作させる方法であって、前記方法は、
高入力語パスを有効にすることと、
低入力語パスを有効にすることと、
第１のモード制御信号に応答して前記高入力語パスおよび前記低入力語パスを交差結合し、第１のモードでＮＴＴ変換演算を実施するために前記高入力語パスおよび前記低入力語パスを構成することであって、所与のＮＴＴ変換演算は、前記ＮＴＴバタフライユニットによる評価のログ２（ｎ）−１ステージが続く始めのＮＴＴステップを伴い、式中、「ｎ」は、係数値と関連付けられた多項式の次数を表すことと、
第２のモードの間における使用のために、前記高入力語パスおよび前記低入力語パスを第２の論理処理ユニットに再構成することであって、前記第２の論理処理ユニットが、第１の論理処理ユニットとは異なり、前記再構成することが、第２のモード制御信号に応答して実施されることと、
を含む、方法。
【国際調査報告】
2020537756.tif 000028
2020537756.tif 000029
2020537756.tif 000030