@techreport{oai:ipsj.ixsq.nii.ac.jp:00233353,
 author = {西村, 拓海 and 戸澤, 一成 and 定兼, 邦彦 and Takumi, Nishimura and Kazunari, Tozawa and Kunihiko, Sadakane},
 issue = {69},
 month = {Mar},
 note = {完全準同型暗号は，データを暗号化したまま計算する秘密計算の実現方式の一つであり，サーバー一台で計算が完結するが計算時間に課題がある．本稿では，完全準同型暗号の一方式である TFHE において計数ソートベースのソートプロトコルを構成した．既存方式では配列長 N に対して，Bootstrap と呼ばれるサブルーチンを漸近的に O(N log2 N) 回呼び出すことが必要であったが，提案方式により O(N) 回の Bootstrap でのソートを可能にした．この提案方式は適用可能な配列長に上限があるが，上限を超える場合についても，漸近的な呼び出し回数は O(N log2 N) 回のまま変わらないものの，既存方式より高速にソート可能になる方法を示す．また，ライブラリを用いてこれらの提案方式の実装を行い，既存方式との比較を行った．特に，長さ 16 の 4 ビット符号なし整数配列のソートについては既存手法より 2.9 倍高速であることを確認し，提案方式の適用可能な配列長の上限を超える場合にも既存方式より高速にソート可能であることを確認した．, 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.},
 title = {完全準同型暗号における計数ソートベースのソートプロトコル},
 year = {2024}
}