完全準同型暗号における計数ソートベースのソートプロトコル

• Item type: SIG Technical Reports(1)
• 公開日: 2024-03-11
• タイトル: 完全準同型暗号における計数ソートベースのソートプロトコル
• タイトル / 言語: en
• タイトル: Oblivious Radix Sort Based on Fully Homomorphic Encryption
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 暗号2
• 資源タイプ / 資源タイプ識別子: 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 において計数ソートベースのソートプロトコルを構成した．既存方式では配列長 N に対して，Bootstrap と呼ばれるサブルーチンを漸近的に O(N log2 N) 回呼び出すことが必要であったが，提案方式により O(N) 回の Bootstrap でのソートを可能にした．この提案方式は適用可能な配列長に上限があるが，上限を超える場合についても，漸近的な呼び出し回数は O(N log2 N) 回のまま変わらないものの，既存方式より高速にソート可能になる方法を示す．また，ライブラリを用いてこれらの提案方式の実装を行い，既存方式との比較を行った．特に，長さ 16 の 4 ビット符号なし整数配列のソートについては既存手法より 2.9 倍高速であることを確認し，提案方式の適用可能な配列長の上限を超える場合にも既存方式より高速にソート可能であることを確認した．
• 論文抄録(英) / 内容記述タイプ: 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 this paper, we construct a sorting protocol based on radix sort in TFHE, one of the fully homomorphic encryption schemes. Our protocol achieves sorting with asymptotic O(N) Bootstrap calls for an array length N, whereas existing methods require O(N log2 N) calls. Although our proposed method has an upper limit on the applicable array length, we propose methods which require O(N log2 N) Bootstrap calls but is faster than the existing sorting methods when the upper limit is exceeded. We also implemented the proposed methods using a library and compared them with existing methods. We confirmed that the proposed method is 2.9 times faster than the existing methods for sorting 4-bit unsigned integer arrays of length 16, and that the proposed method is also faster than the existing methods for sorting arrays exceeding the upper limit of the applicable array length.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11235941
• 書誌情報: 研究報告コンピュータセキュリティ（CSEC）; 巻 2024-CSEC-104, 号 69, p. 1-8, 発行日 2024-03-11
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8655
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会