特許ウォッチ

公開番号2023078774
公報種別公開特許公報(A)
公開日2023-06-07
出願番号2021192046
出願日2021-11-26
発明の名称暗号処理装置、暗号処理方法、及び暗号処理プログラム
出願人株式会社アクセル
代理人個人,個人,個人
主分類G09C 1/00 20060101AFI20230531BHJP(教育;暗号方法;表示;広告;シール)
要約【課題】Integer-wise型TFHEの四則演算を実現する。
【解決手段】暗号文は、所定の値に所定の分散を持つ誤差を与えた値を、整数に対応付けた平文として有し、復号することなく整数同士の所定の演算が可能な完全準同型暗号文であり、被除数としての第1暗号文から除数としての第2暗号文を準同型減算した減算結果に基づいて、減算結果の正負を判定する二値の第3暗号文を算出し、第1暗号文から、第3暗号文と第2暗号文の準同型乗算結果を準同型減算して、新たな暗号文を算出する演算処理を行い、演算処理の演算結果を新たな第1暗号文として新たな第3暗号文を算出し、新たな第1暗号文と、第2暗号文と新たな第3暗号文とを用いた演算処理を、繰り返し実行可能であり、演算処理を全体で所定回繰り返し実行したときに算出した新たな暗号文を、第1暗号文に対する第2暗号文の除算又は剰余算の結果として出力する。
【選択図】図2
特許請求の範囲【請求項１】
暗号文を処理する暗号処理装置であって、
前記暗号文は、所定の値に所定の分散を持つ誤差を与えた値を、整数に対応付けた平文として有し、復号することなく整数同士の所定の演算が可能な完全準同型暗号文であり、
被除数としての第１暗号文から除数としての第２暗号文を準同型減算した減算結果に基づいて、前記減算結果の正負を判定する二値の第３暗号文を算出し、
前記第１暗号文から、前記第３暗号文と前記第２暗号文の準同型乗算結果を準同型減算して、新たな暗号文を算出する演算処理を行い、
前記演算処理の演算結果を新たな前記第１暗号文として新たな前記第３暗号文を算出し、新たな前記第１暗号文と、前記第２暗号文と新たな前記第３暗号文とを用いた前記演算処理を繰り返し実行し、
前記演算処理を全体で所定回繰り返し実行したときに算出した新たな暗号文を、前記第１暗号文に対する前記第２暗号文の剰余算の結果として出力する、
ことを特徴とする暗号処理装置。
続きを表示（約 2,300 文字）【請求項２】
暗号文を処理する暗号処理装置であって、
前記暗号文は、所定の値に所定の分散を持つ誤差を与えた値を、整数に対応付けた平文として有し、復号することなく整数同士の所定の演算が可能な完全準同型暗号文であり、
被除数としての第１暗号文から除数としての第２暗号文を準同型減算した減算結果に基づいて、前記減算結果の正負を判定する二値の第３暗号文を算出し、
前記第１暗号文から、前記第３暗号文と前記第２暗号文の準同型乗算結果を準同型減算して、新たな暗号文を算出する演算処理を行い、
前記演算処理の演算結果を新たな前記第１暗号文として新たな前記第３暗号文を算出し、新たな前記第１暗号文と、前記第２暗号文と新たな前記第３暗号文とを用いた前記演算処理を繰り返し実行し、
前記第３暗号文を算出するごとに、所定の初期値に対して前記第３暗号文を累加して新たな暗号文を算出し、
前記演算処理を全体で前記所定回繰り返した時点で前記第３暗号文を累加した新たな暗号文を、前記第１暗号文に対する前記第２暗号文の除算の結果として出力する、
ことを特徴とする暗号処理装置。
【請求項３】
請求項２に記載の暗号処理装置において、
前記演算処理を全体で繰り返す回数は、ログオーダーの回数であることを特徴とする暗号処理装置。
【請求項４】
請求項１又は２に記載の暗号処理装置において、
前記演算処理を全体で繰り返す回数は、前記暗号文が取り得る整数の最大値であることを特徴とする暗号処理装置。
【請求項５】
請求項１乃至４の何れか一項に記載の暗号処理装置において、
暗号文に対して所定の演算に係る準同型演算を行う演算部と、
暗号文に対して所定の多項式を用いて新たな暗号文を算出する算出部と、を備え、
前記演算部による準同型演算の結果に対して、所定の多項式を用いて新たな暗号文を算出するまえに暗号文の係数の数を削減する処理を行う、
ことを特徴とする暗号処理装置。
【請求項６】
請求項１乃至５の何れか一項に記載の暗号処理装置において、
前記第１の暗号文は、前記第１の整数を区間毎に所定数に分割した結果を夫々暗号化した暗号文を有し、
前記第２の暗号文は、前記第２の整数を区間毎に前記所定数に分割した結果を夫々暗号化した暗号文を有し、
前記所定の演算を実行するときに、前記第１の暗号文と前記第２の暗号文との対応する暗号文同士を準同型演算して多倍長演算を実行する、
ことを特徴とする暗号処理装置。
【請求項７】
請求項１乃至６の何れか一項に記載の暗号処理装置において、
前記所定の演算を行うことにより、入力された前記暗号文を用いたファジー認証又はファジー検索に係る処理を行う、
ことを特徴とする暗号処理装置。
【請求項８】
請求項１乃至７の何れか一項に記載の暗号処理装置において、
前記所定の演算を行うことによって、入力された前記暗号文に基づく暗号化データベースに対するクエリを処理する、
ことを特徴とする暗号処理装置。
【請求項９】
プロセッサによって実行される、暗号文を処理する暗号処理方法であって、
前記暗号文は、所定の値に所定の分散を持つ誤差を与えた値を、整数に対応付けた平文として有し、復号することなく整数同士の所定の演算が可能な完全準同型暗号文であり、
被除数としての第１暗号文から除数としての第２暗号文を準同型減算した減算結果に基づいて、前記減算結果の正負を判定する二値の第３暗号文を算出し、
前記第１暗号文から、前記第３暗号文と前記第２暗号文の準同型乗算結果を準同型減算して新たな暗号文を算出する演算処理を行い、
前記演算処理の演算結果を新たな前記第１暗号文として、新たな前記第３暗号文を算出し、新たな新たな前記第１暗号文と、前記第２暗号文と、新たな前記第３暗号文と、を用いた前記演算処理を繰り返し実行し、
前記演算処理を全体で所定回繰り返し実行したときに出力した新たな暗号文を、前記第１暗号文に対する前記第２暗号文の除算又は剰余算の結果として出力する、
ことを特徴とする暗号処理方法。
【請求項１０】
暗号文を処理する暗号処理方法をプロセッサに実行させる暗号処理プログラムであって、
前記暗号文は、所定の値に所定の分散を持つ誤差を与えた値を、整数に対応付けた平文として有し、復号することなく整数同士の所定の演算が可能な完全準同型暗号文であり、
被除数としての第１暗号文から除数としての第２暗号文を準同型減算した減算結果に基づいて、前記減算結果の正負を判定する二値の第３暗号文を算出し、
前記第１暗号文から、前記第３暗号文と前記第２暗号文の準同型乗算結果を準同型減算して新たな暗号文を算出する演算処理を行い、
前記演算処理の演算結果を新たな前記第１暗号文として、新たな前記第３暗号文を算出し、新たな新たな前記第１暗号文と、前記第２暗号文と、新たな前記第３暗号文と、を用いた前記演算処理を繰り返し実行し、
前記演算処理を全体で所定回繰り返し実行したときに出力した新たな暗号文を、前記第１暗号文に対する前記第２暗号文の除算又は剰余算の結果として出力する、
ことを特徴とする暗号処理プログラム。

発明の詳細な説明【技術分野】
【０００１】
本発明は、暗号文を処理する暗号処理装置、暗号処理方法、及び暗号処理プログラムに関する。
続きを表示（約 3,300 文字）【背景技術】
【０００２】
準同型暗号（Homomorphic Encryption）は、暗号化したデータを復号せず、暗号化したままデータ処理を行うことが出来る暗号方式である。
平文同士での加算に対応する暗号文同士の演算が存在する暗号が加法準同型暗号であり、平文同士での乗算に対応する暗号文同士の演算が存在する暗号が乗法準同型暗号である。
有限巡回群を整数に見立てて、加法演算（加算、減算）のみを行う加法準同型暗号と、乗法演算（乗算）のみを行う乗法準同型暗号とが以前から知られていた。
有限巡回群は、加算を繰り返せば整数倍が出来るので、平文の整数倍ができ、乗算を繰り返せば平文のべき乗計算をすることも出来る。
また、加法演算と乗法演算の両方を暗号化したまま処理する完全準同型暗号（Fully Homomorphic Encryption，FHE）がある。
完全準同型暗号の一つとして、暗号化時に復号には問題のない程度の小さな誤差を平文に加えることで構成される、LWE（Learning with Errors）問題に基づく完全準同型暗号が知られている。
【０００３】
LWE問題に基づく完全準同型暗号では、演算を行うとともに誤差が蓄積していくので、誤差が大きくなりすぎて復号ができなくなる前に、暗号化したまま誤差成分を縮小するbootstrappingが実行される。
bootstrappingの計算時間は、完全準同型暗号に含まれる計算時間の大部分を占める。また、bootstrappingでは膨大なデータを扱うため、その計算量は膨大である。したがって、完全準同型暗号の演算においては、実用的な時間内で演算結果を得ることができないことがある。
この問題を劇的に改善した手法が、非特許文献１（以下の説明において、上記論文として参照される）に示されるTFHE（Fast Fully Homomorphic Encryption over the Torus）である。
準同型暗号には、平文として二値を有し論理演算をベースとするBit-wise型の準同型暗号と、平文として整数を丸ごと一暗号文とするInteger-wise型の準同型暗号と、があり、非特許文献１に示されるTFHEはBit-wise型である。
なおTFHEの平文は円周群に対応づけられた０～１の実数である。よって、円周群の値域０～１を区切った区間を順番に整数と対応付けることにより、整数を平文として有するInteger-wise型の準同型暗号として応用することが出来る（非特許文献２参照）。
【先行技術文献】
【特許文献】
【０００４】
TFHE:Fast Fully Homomorphic Encryption over the Torus. Journal of Cryptology, 33:34-91, 2020, I.Chillotti, N.Gama, M.Georgieva, and M.Izabachene
Integerwise Functional Bootstrapping on TFHE, 2020, Hiroki Okada, Shinsaku Kiyomoto, and Carlos Cid
【発明の概要】
【発明が解決しようとする課題】
【０００５】
Integer-wiseでの四則演算が可能な準同型暗号としてTFHEを利用することができれば、1ビットずつ計算するよりも効率的に処理を行うことができる。
なおTFHEで用いるTLWE暗号文は、円周群の平文に対して加法準同型であることが上記論文によって示されており、加算（減算）の演算ができることは自明である。
一方、乗算に関しては、円周群に乗法演算が定義されていないため自明とは言えない。円周群はＺ加群であるため、円周群上での整数倍のみが定義される。従って、区間で区切った数を法とする逆元を乗算することで平文に対する逆元を求めうる。しかしながら、元の値が割りきれる値である保証がない限り逆元と除算は一致しない。すなわち、余りを有する除算を行うことが出来ない。また、暗号文同士の除算も剰余算も提案されていない。
本発明は、一側面としてInteger-wise型TFHEの四則演算をより完全に実現することを目的とする。
【課題を解決するための手段】
【０００６】
本発明は、暗号文を処理する暗号処理装置であって、前記暗号文は、所定の値に所定の分散を持つ誤差を与えた値を、整数に対応付けた平文として有し、復号することなく整数同士の所定の演算が可能な完全準同型暗号文であり、被除数としての第１暗号文から除数としての第２暗号文を準同型減算した減算結果に基づいて、前記減算結果の正負を判定する二値の第３暗号文を算出し、前記第１暗号文から、前記第３暗号文と前記第２暗号文の準同型乗算結果を準同型減算して、新たな暗号文を算出する演算処理を行い、前記演算処理の演算結果を新たな前記第１暗号文として新たな前記第３暗号文を算出し、新たな前記第１暗号文と、前記第２暗号文と新たな前記第３暗号文とを用いた前記演算処理を、繰り返し実行し、前記演算処理を全体で所定回繰り返し実行したときに算出した新たな暗号文を、前記第１暗号文に対する前記第２暗号文の除算又は剰余算の結果として出力する、暗号処理装置を特徴とする。
【発明の効果】
【０００７】
本発明によれば、一側面として、Integer-wise型TFHEの四則演算をより完全に実現することが出来る。
【図面の簡単な説明】
【０００８】
本実施形態の暗号処理装置の機能構成を説明する図である。
図１の機能構成に基づく演算プロセスを詳しく説明する図である。
TLWE暗号が平文として有する円周群を説明するイメージ図である。
２値Gate Bootstrappingの動作イメージ図である。
Integer-wise型に適用したTFHEを説明する図である。
除算・剰余算処理を説明するフローチャートである。
変形例に係る除算処理を説明するフローチャートである。
多倍長整数の除算・剰余算を行う暗号処理装置の機能構成を説明する図である。
図８の機能構成に基づく演算プロセスを詳しく説明する図である。
暗号処理装置が実行するスカラ除算処理の流れを示すフローチャートである。
暗号処理装置が実行するスカラ剰余算処理の流れを示すフローチャートである。
暗号処理装置が実行する多倍長演算処理の流れを示すフローチャートである。
本実施形態のGate Bootstrappingに入出力される暗号文を示す図である。
コンピュータ装置の一実施例を示すブロック図である。
【発明を実施するための形態】
【０００９】
以下に、図面を参照して本発明の実施の形態を詳細に説明する。
なお、以下の説明において、[]で囲まれた英数字はそれがベクトルであることを示す。{}で囲まれた英数字はそれが集合であることを示す。
また、本明細書において、「論理演算」と記す場合は２値もしくは多値の論理演算のことを指すものとする。
【００１０】
図１は、本実施形態の暗号処理装置の機能構成を説明する図である。
暗号処理装置１は、制御部１０と、記憶部２０と、通信部２５と、入力部２６と、を備える。
制御部１０は、受付部１１と、第１演算部１２と、第２演算部１３と、第３演算部１４と、Bootstrapping部（算出部）１５と、出力部１８と、を備えている。
（【００１１】以降は省略されています）

関連特許