特許ウォッチ

公開番号2025067536
公報種別公開特許公報(A)
公開日2025-04-24
出願番号2023177596
出願日2023-10-13
発明の名称多項式環ベクトル内積計算回路、計算処理回路、および制御方法
出願人キオクシア株式会社
代理人弁理士法人スズエ国際特許事務所
主分類G06F 17/16 20060101AFI20250417BHJP(計算;計数)
要約【課題】多項式環ベクトル同士の計算を効率的に実行することができる多項式環ベクトル内積計算回路を実現する。
【解決手段】多項式環ベクトル内積計算回路は、多項式X^N+1をイデアルとする整数係数多項式環上の第一の多項式環ベクトルの各成分が1個以上の定数多項式の線形和である場合、1個以上の定数多項式の各々に1/Nを乗じる処理と数論変換を施す処理とを予め実行することによって得られる第一の周波数領域多項式環ベクトルに基づいて、第一の周波数領域多項式環ベクトルと、第二の多項式環ベクトルの各成分に数論変換を施した第2の周波数領域多項式環ベクトルとの内積を計算し、計算された内積に逆数論変換を施した時間領域多項式を、第1の多項式環ベクトルと第2の多項式環ベクトルの内積として出力する。
【選択図】図17
特許請求の範囲【請求項１】
多項式Ｘ
Ｎ
＋１をイデアルとする整数係数多項式環上の第一の多項式環ベクトルと第二の多項式環ベクトルのうち少なくとも前記第一の多項式環ベクトルの各成分が１個以上の定数多項式の線形和であるような前記第一の多項式環ベクトルと前記第二の多項式環ベクトルの内積を計算するように構成された多項式環ベクトル内積計算回路であって、前記Ｎは２のべき乗数であり、
多項式環ベクトルの各成分に数論変換を施すことによって得られる周波数領域多項式環ベクトルを計算する数論変換処理回路と、
前記１個以上の定数多項式の各々に１／Ｎを乗じる処理と数論変換を施す処理とを予め実行することによって得られる周波数領域定数多項式の線形和を各成分に持つ第一の周波数領域多項式環ベクトルに基づいて、前記第一の周波数領域多項式環ベクトルと、前記数論変換処理回路によって前記第二の多項式環ベクトルの各成分に数論変換を施すことによって得られた第二の周波数領域多項式環ベクトルとのアダマール積を計算し、前記計算されたアダマール積の成分同士の和を算出することによって周波数領域多項式である第一の内積を計算するアダマール内積計算回路と、
前記第一の内積に逆数論変換を施すことによって得られる時間領域多項式を計算する逆数論変換処理回路と、
前記計算された時間領域多項式を出力する内積出力回路と、を具備する多項式環ベクトル内積計算回路。
続きを表示（約 2,900 文字）【請求項２】
前記１個以上の定数多項式の各々に１／Ｎを乗じる処理と前記数論変換を施す処理とを予め実行することによって前記第一の周波数領域多項式環ベクトルを事前計算する事前計算回路をさらに具備し、
前記アダマール内積計算回路は、前記事前計算回路によって事前計算された前記第一の周波数領域多項式環ベクトルに基づいて、前記第一の周波数領域多項式環ベクトルと前記第二の周波数領域多項式環ベクトルとのアダマール内積を前記第一の内積として計算する、請求項１に記載の多項式環ベクトル内積計算回路。
【請求項３】
前記多項式環ベクトル内積計算回路は、ＮＶＭＥｘｐｒｅｓｓ規格に基づいてホストとの通信を実行するように構成されたコンピューティングストレージデバイスに含まれるアクセラレータの内部に含まれており、
前記アダマール内積計算回路は、前記ホストにおいて事前計算され且つ前記ホストから受信された前記第一の周波数領域多項式環ベクトルに基づいて、前記第一の周波数領域多項式環ベクトルと前記第二の周波数領域多項式環ベクトルとのアダマール内積を前記第一の内積として計算する、請求項１に記載の多項式環ベクトル内積計算回路。
【請求項４】
前記多項式環ベクトル内積計算回路は、ＮＶＭＥｘｐｒｅｓｓ規格に基づいてホストとの通信を実行するように構成されたコンピューティングストレージデバイスに含まれるアクセラレータの内部に含まれており、
前記コンピューティングストレージデバイスは、不揮発性メモリと、前記不揮発性メモリを制御するように構成されたコントローラとを含み、
前記アクセラレータは、前記コントローラの内部に含まれている、請求項１に記載の多項式環ベクトル内積計算回路。
【請求項５】
前記多項式環ベクトル内積計算回路は、ＮＶＭＥｘｐｒｅｓｓｏｖｅｒＦａｂｒｉｃｓプロトコルに基づいてホストとの通信を実行するように構成されたコンピューティングストレージデバイスに含まれるアクセラレータの内部に含まれている、請求項１に記載の多項式環ベクトル内積計算回路。
【請求項６】
第一の平文を暗号化したトーラス完全準同型暗号（ＴＦＨＥ）の暗号文である第一のＴＲＬＷＥサンプル、第二の平文を暗号化した前記ＴＦＨＥの暗号文である第二のＴＲＬＷＥサンプル、及び０または１を暗号化した前記ＴＦＨＥの暗号文である周波数領域ＴＲＧＳＷサンプルを入力し、前記周波数領域ＴＲＧＳＷサンプルが０を暗号化したものである場合に前記第一の平文を暗号化した前記ＴＦＨＥの暗号文である第三のＴＲＬＷＥサンプルを出力し、前記周波数領域ＴＲＧＳＷサンプルが１を暗号化したものである場合に前記第二の平文を暗号化した前記ＴＦＨＥの暗号文である前記第三のＴＲＬＷＥサンプルを出力するＣＭｕｘ関数を計算するように構成された計算処理回路であって、
前記第二のＴＲＬＷＥサンプルの各成分から前記第一のＴＲＬＷＥサンプルの各成分を引くことによって得られる第四のＴＲＬＷＥサンプルを計算する成分毎減算回路と、
前記第四のＴＲＬＷＥサンプルをガジェット分解することによって得られる整数係数多項式環ベクトルを計算するガジェット分解処理回路と、
多項式環ベクトル内積計算回路と、
成分毎加算回路と、を具備し、
前記周波数領域ＴＲＧＳＷサンプルは、多項式Ｘ
Ｎ
＋１をイデアルとする整数係数多項式環上の多項式環ベクトルであるブートストラッピング鍵または非公開関数型鍵切替鍵の各成分である１個以上の定数多項式の各々に１／Ｎを乗じる処理と数論変換を施す処理とを予め実行することによって得られる１個以上の周波数領域定数多項式の線形和を各成分に持つ第一の周波数領域多項式環ベクトルであり、前記Ｎは２のべき乗数であり、
前記多項式環ベクトル内積計算回路は、
前記整数係数多項式環ベクトルの各成分に数論変換を施すことによって得られる第二の周波数領域多項式環ベクトルを計算し、
前記第一の周波数領域多項式環ベクトルに基づいて、前記第一の周波数領域多項式環ベクトルと前記第二の周波数領域多項式環ベクトルとのアダマール積を計算し、
前記計算されたアダマール積の成分同士の和を算出することによって周波数領域多項式である第一の内積を計算し、
前記第一の内積に逆数論変換を施すことによって得られる時間領域多項式を計算し、
前記成分毎加算回路は、前記計算された時間領域多項式の各成分に前記第一のＴＲＬＷＥサンプルの各成分を加算することによって得られる前記第三のＴＲＬＷＥサンプルを出力するように構成されている、計算処理回路。
【請求項７】
前記１個以上の定数多項式の各々に１／Ｎを乗じる処理と前記数論変換を施す処理とを予め実行することによって前記第一の周波数領域多項式環ベクトルを事前計算する事前計算回路をさらに具備し、
前記多項式環ベクトル内積計算回路は、前記事前計算回路によって事前計算された前記第一の周波数領域多項式環ベクトルに基づいて、前記第一の周波数領域多項式環ベクトルと前記第二の周波数領域多項式環ベクトルとのアダマール内積を前記第一の内積として計算する、請求項６に記載の計算処理回路。
【請求項８】
前記計算処理回路は、ＮＶＭＥｘｐｒｅｓｓ規格に基づいてホストとの通信を実行するように構成されたコンピューティングストレージデバイスに含まれるアクセラレータの内部に含まれており、
前記多項式環ベクトル内積計算回路は、前記ホストにおいて事前計算され且つ前記ホストから受信された前記第一の周波数領域多項式環ベクトルに基づいて、前記第一の周波数領域多項式環ベクトルと前記第二の周波数領域多項式環ベクトルとのアダマール内積を前記第一の内積として計算する、請求項６に記載の計算処理回路。
【請求項９】
前記計算処理回路は、ＮＶＭＥｘｐｒｅｓｓ規格に基づいてホストとの通信を実行するように構成されたコンピューティングストレージデバイスに含まれるアクセラレータの内部に含まれており、
前記コンピューティングストレージデバイスは、不揮発性メモリと、前記不揮発性メモリを制御するように構成されたコントローラとを含み、
前記アクセラレータは、前記コントローラの内部に含まれている、請求項６に記載の計算処理回路。
【請求項１０】
前記計算処理回路は、ＮＶＭｏｖｅｒＦａｂｒｉｃｓプロトコルに基づいてホストとの通信を実行するように構成されたコンピューティングストレージデバイスに含まれるアクセラレータの内部に含まれている、請求項６に記載の計算処理回路。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本発明の実施形態は、多項式環ベクトルの計算を制御する、多項式環ベクトル内積計算回路、計算処理回路、および制御方法に関する。
続きを表示（約 2,700 文字）【背景技術】
【０００２】
近年、データの保護のために暗号化されたデータのうち、準同型暗号に基づいて暗号化されたデータは、暗号化された状態のままで計算を実行可能である。つまり、準同型暗号によって暗号化されたデータは、復号せずに計算すること（秘密計算）が可能なデータである。
【０００３】
さらに、準同型暗号の中でも完全準同型暗号によって暗号化されたデータは、任意の秘密計算を実行することが可能なデータである。完全準同型暗号によって暗号化されたデータおよび暗号鍵は、多項式環ベクトルによって表され得る。そのため、完全準同型暗号によって暗号化されたデータの秘密計算等では、多項式環ベクトル同士の計算が実行される。
【０００４】
多項式環ベクトル同士の計算では、これら多項式環ベクトルのサイズに応じて、計算量が増大し、計算に係る時間が増大する。
【０００５】
そのため、多項式環ベクトル同士の計算を効率的に実行することによって、暗号化されたデータの計算を効率的に実行するための技術が必要とされている。
【先行技術文献】
【特許文献】
【０００６】
米国特許出願公開第２０２３／０１７１０８４号明細書
米国特許出願公開第２０２３／０１６３９４５号明細書
米国特許出願公開第２０２１／００７３３１６号明細書
米国特許出願公開第２０２２／０２９３２２２号明細書
【非特許文献】
【０００７】
Tomas、外２名、"High-Performance Ideal Lattice-Based Cryptography on 8-bit ATxmwga Microcontrollers Extended Version"、[online]、［令和５年９月２１日検索］、インターネット<URL: https://eprint.iacr.org/2015/382.pdf>
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明の実施形態が解決しようとする課題は、多項式環ベクトル同士の計算を効率的に実行することができる多項式環ベクトル内積計算回路、計算処理回路、および制御方法を提供することである。
【課題を解決するための手段】
【０００９】
実施形態によれば、多項式環ベクトル内積計算回路は、多項式Ｘ
Ｎ
＋１をイデアルとする整数係数多項式環上の第一の多項式環ベクトルと第二の多項式環ベクトルのうちの少なくとも前記第一の多項式環ベクトルの各成分が１個以上の定数多項式の線形和であるような前記第一の多項式環ベクトルと前記第二の多項式環ベクトルの内積を計算するように構成される。前記Ｎは２のべき乗数である。前記多項式環ベクトル内積計算回路は、数論変換処理回路と、アダマール内積計算回路と、逆数論変換処理回路と、内積出力回路とを具備する。前記数論変換処理回路は、多項式環ベクトルの各成分に数論変換を施すことによって得られる周波数領域多項式環ベクトルを計算する。前記アダマール内積計算回路は、前記１個以上の定数多項式の各々に１／Ｎを乗じる処理と数論変換を施す処理とを予め実行することによって得られる１個以上の周波数領域定数多項式の線形和を各成分に持つ第一の周波数領域多項式環ベクトルに基づいて、前記第一の周波数領域多項式環ベクトルと、前記数論変換処理回路によって前記第二の多項式環ベクトルの各成分に数論変換を施すことによって得られた第二の周波数領域多項式環ベクトルとのアダマール積を計算し、前記計算されたアダマール積の成分同士の和を算出することによって周波数領域多項式である第一の内積を計算する。前記逆数論変換処理回路は、前記第一の内積に逆数論変換を施すことによって得られる時間領域多項式を計算する。前記内積出力回路は、前記計算された時間領域多項式を出力する。
【図面の簡単な説明】
【００１０】
ＣｏｏｌｅｙＴｕｋｅｙ（ＣＴ）型バタフライ演算の処理フローを示す図。
ＧｅｎｔｌｅｍａｎＳａｎｄｅ（ＧＳ）型バタフライ演算処理フローを示す図。
ＣＴ型バタフライ演算を使用した高速フーリエ変換の処理フローの第１の例を示す図。
ＣＴ型バタフライ演算を使用した高速フーリエ変換の処理フローの第２の例を示す図。
ＧＳ型バタフライ演算を使用した高速フーリエ変換の処理フローの第１の例を示す図。
ＧＳ型バタフライ演算を使用した高速フーリエ変換の処理フローの第２の例を示す図。
数論変換（ＮｕｍｂｅｒＴｈｅｏｒｅｔｉｃＴｒａｎｓｆｏｒｍ（ＮＴＴ））の処理フローを示す図。
逆数論変換（ＩｎｖｅｒｓｅＮＴＴ）の処理フローを示す図。
実施形態において実行されるブートストラッピング鍵設定処理の手順を示すフローチャート。
実施形態において実行される非公開関数型鍵切替鍵設定処理の手順を示すフローチャート。
実施形態において実行される非公開関数型鍵切替鍵の非公開関数型鍵切り替え処理の手順を示すフローチャート。
実施形態において実行されるＣＭｕｘ関数の処理の手順を示すフローチャート。
実施形態に係るＣＭｕｘ演算回路の構成を示すブロック図。
実施形態に係るアクセラレータを含むコンピューティングストレージデバイスの構成例を示すブロック図。
実施形態に係るアクセラレータが使用する秘密計算命令セットの一例を示す図。
実施形態に係る仮想レジスタ番号の計算方法の一例について説明するための図。
実施形態において実行される鍵設定処理と、ＣＭｕｘ関数の処理の手順の例を示す図。
実施形態においてＮＶＭｅ規格に基づいてホストとの通信を実行するように構成されたコンピューティングストレージデバイスの構成について説明するための図。
実施形態に係るアクセラレータがＳＳＤコントローラの内部に配置される構成について説明するための図。
実施形態に係るアクセラレータがＮＶＭｅ－ｏＦターゲットモジュールの内部に配置される構成について説明するための図。
【発明を実施するための形態】
（【００１１】以降は省略されています）

関連特許