完全準同型暗号TFHEにおけるLarge LookUp Tableの効率的な評価

• Item type: SIG Technical Reports(1)
• 公開日: 2024-05-23
• タイトル: 完全準同型暗号TFHEにおけるLarge LookUp Tableの効率的な評価
• タイトル / 言語: en
• タイトル: Evaluating Large LookUp Table Efficiently in TFHE
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: CSEC1
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学
• 著者所属: 東京大学
• 著者所属: 東京大学
• 著者所属(英): en
• 著者所属(英): The University of Tokyo
• 著者所属(英): en
• 著者所属(英): The University of Tokyo
• 著者所属(英): en
• 著者所属(英): The University of Tokyo
• 著者名: 西村, 拓海; 戸澤, 一成; 定兼, 邦彦
• 著者名(英): Takumi, Nishimura; Kazunari, Tozawa; Kunihiko, Sadakane
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 完全準同型暗号は，データを暗号化したまま計算する秘密計算方式の一つである．他の秘密計算方式と異なり，サーバー一台で計算が完結する一方で，計算時間に課題がある．完全準同型暗号の一方式である TFHE では，ほとんどの演算を一変数関数評価の組み合わせにより実現するため，一変数関数評価は重要な処理である．TFHE では，LookUp Table と呼ばれる入力値と関数値の対応表の暗号文に対して演算をすることで一変数関数が評価される．関数の入力ビット長が大きい一変数関数評価は Large LookUp Table の評価と呼ばれる．本稿では，TFHE において Large LookUp Table を効率的に評価する方法を構成した．既存方式では，入力ビット長が W の一変数関数評価は，Blind Rotate と呼ばれる重いサブルーチンを漸近的に O(2W) 回呼び出すことが必要であった．提案方式により O(W2) 回の Blind Rotate での一変数関数評価を可能にした．また，LookUp Table の評価と双対的な操作である One-hot Encode についても考察し，O(W2) 回のBlind Rotate でベクトル長 2W の One-hot ベクトルを構成する方法を示した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Fully homomorphic encryption realizes secure computation in which operations are performed under encryption. Computations can be completed on a single server, but there is a problem with computation time. In TFHE, which is one of the fully homomorphic encryption schemes, univariate function evaluation is an important operation. Univariate functions are evaluated by performing operations on the ciphertext of a correspondence table between input values and function values called a LookUp Table. Univariate function evaluation with a large input bit length is called Large LookUp Table evaluation. In this paper, we construct a method for efficiently evaluating Large LookUp Tables in TFHE. In existing methods, evaluation of univariate functions with an input bit length of W requires asymptotically O(2W) calls of a heavy subroutine called Blind Rotate. The proposed method enables univariate function evaluation with O(W2) Blind Rotate. By the way, One-hot Encoding is an operation that returns a vector with only the i-th element 1 and other elements 0 for input value i. Large One-hot Encode can be evaluated in 2W of vector length in O(W2) Blind Rotate by the same method as that for Large LookUp Table evaluation.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11235941
• 書誌情報: 研究報告コンピュータセキュリティ（CSEC）; 巻 2024-CSEC-105, 号 10, p. 1-8, 発行日 2024-05-23
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8655
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会