Yukimasa Sugizaki

Profile

Affiliations

Personal internet accounts

Publications

Journal paper

  1. Yukimasa Sugizaki, Daisuke Takahashi, A Fast Algorithm for Computing the Number of Magic Series, Annals of Combinatorics, 2022, doi:10.1007/s00026-022-00584-5
    Abstract: We present a fast algorithm for computing the number of magic series, an enumeration problem of a certain integer partition. Kinnaes showed that the number appears as a coefficient in a Gaussian polynomial and that the exact value can be efficiently extracted with a finite variant of Cauchy’s integral formula. The algorithm requires a bit time complexity of O(m4 M(m log m)) and O(m log m)-bit space, where m is the order of the magic series and M(n) is the time complexity of multiplying two n-bit numbers. Through our analysis, we confirm that this is the most efficient among previously reported algorithms. In addition, we show that the number can be computed with a bit time complexity of O(m3 log m M(m log m)) by directly carrying out polynomial multiplication and division on the Gaussian polynomial. Though the space consumption increases to O(m3 log m) bits, we demonstrate that our method actually computes the number faster for large orders.

Conference proceedings with review

  1. Yukimasa Sugizaki, Hikaru Tsuchida, Takuya Hayashi, Koji Nuida, Akira Nakashima, Toshiyuki Isshiki, Kengo Mori, Threshold Fully Homomorphic Encryption Over the Torus, European Symposium on Research in Computer Security (ESORICS 2023), doi:10.1007/978-3-031-50594-2_3
    Abstract: Fully homomorphic encryption (FHE) enables arithmetic operations to be performed over plaintext by operations on undecrypted ciphertext. The Chillotti-Gama-Georgieva-Izabachene (CGGI) scheme is a typical FHE scheme, has attracted attention because of its fast bootstrapping and the availability of open-source implementation software. A threshold FHE (ThFHE) scheme has protocols for distributed key generation and distributed decryption that are executed cooperatively among the parties while keeping the decryption key distributed among them. It is useful for secure computations with inputs from multiple parties. However, a ThFHE scheme based on CGGI has yet to be proposed. In this paper, we propose a client-aided ThFHE scheme based on CGGI. Our scheme achieves the same bootstrapping as CGGI without affecting the noise analysis or any CGGI parameter. Therefore, existing open-source software implementing CGGI can easily be extended to our scheme, a ThFHE variant of the CGGI scheme, without changing the implementation part regarding homomorphic operations.
  2. Yukimasa Sugizaki, Daisuke Takahashi, Fast Computation of the Exact Number of Magic Series with an Improved Montgomery Multiplication Algorithm, International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP 2020), doi:10.1007/978-3-030-60239-0_25
    Abstract: The numbers of magic series of large orders are computed on Intel Xeon Phi processors with an improved and optimized Montgomery multiplication algorithm. The number of magic series can be efficiently computed by Kinnaes' formula, of which the most time-consuming element is modular multiplication. We use Montgomery multiplication for faster modular multiplication, and the number of operations is reduced through procedural simplifications. Modular addition, subtraction, and multiplication operations are vectorized by using the following instructions: Intel Advanced Vector Extensions (AVX), Intel Advanced Vector Extensions 2 (AVX2), and Intel Advanced Vector Extensions 512 (AVX-512). The number of magic series of order 8000 is computed on multiple nodes of an Intel Xeon Phi processor with a total execution time of 1806 days. Results are compared with salient studies in the literature to confirm the efficacy of the approach.

Oral presentation without review

  1. 中島 明, 林 卓也, 土田 光, 杉崎 行優, 森 健吾, 西出 隆志, 整数型準同型暗号におけるHomomorphic Linear Transformationを用いた任意二変数関数計算, 2024年 暗号と情報セキュリティシンポジウム, 2024
    Abstract: 本稿では，整数を平文とする準同型暗号方式における任意二変数関数計算の効率化を提案する．比較的大きな平文整数に対して任意二変数関数計算を行う先行研究として，前田らの方式 (WAHC’22) がある．本研究では，前田らの方式において支配的な処理である多項式評価計算を回避し，より高速なHomomorphic Linear Transformation処理に基づくテーブルルックアップを行うことで効率化を実現する．提案方式についてPALISADEを用いたC++による実装を行い，その結果を報告する．
  2. 伊藤 直也, 杉崎 行優, 土田 光, 高木 剛, ゲート数が少ないbinary adder treeとmulti-key TFHEを用いた性能評価, 2023年 暗号と情報セキュリティシンポジウム, 2023
    Abstract: 準同型暗号とは，暗号文を復号せずに，平文に対する演算が可能な暗号方式である．平文に対する加算と乗算を任意の回数だけ計算可能な準同型暗号を，完全準同型暗号という．代表的な完全準同型暗号として，TFHE が挙げられる．さらに，複数の暗号化鍵が存在可能な一般化されたTFHEとして，multi-key TFHE (MK-TFHE) が提案されている．TFHE は関数を論理回路で表現し，論理ゲートごとに準同型演算を行うことで，入力を明かさずに任意の関数を計算できる．代表的な関数として，総和計算が挙げられる．特に各入力が1ビットの総和計算は，ハミング距離計算や二値化ニューラルネットワークの推論で用いられる．総和計算の回路表現として，binary adder tree (BAT) が挙げられる．TFHE により総和計算を含む関数を計算する場合，BAT の計算時間を削減すること，関数全体の計算時間も削減できる．よって，BAT を少ないゲート数で構成することが望まれる．本稿では既存の BAT よりもゲート数が少ない BAT を提案する．また，MK-TFHE により提案方式を用いたハミング距離計算を実装し，実行時間を評価する．
  3. 林 卓也, 一色 寿幸, 森 健吾, 縫田 光司, 杉崎 行優, 土田 光, TFHEに基づくクライアント補助型閾値完全準同型暗号, 2023年 暗号と情報セキュリティシンポジウム, 2023
    Abstract: Fully homomorphic encryption (FHE) とは，暗号文を復号せずに，暗号文上の計算により平文に対する加算や乗算を任意の回数だけ計算可能な暗号方式である．特に復号鍵を複数の参加者にシェアとして分散したまま復元せずに，復号鍵に対応する暗号化鍵の生成や暗号文の復号が可能なFHEをthreshold FHE (ThFHE) という．ThFHEでは，復号鍵のシェアが一定数集まらない限り復号鍵を復元できないため，複数の参加者からの入力を用いた秘密計算に有用である．代表的なFHEとして，TFHEが挙げられる．TFHEは，暗号文に蓄積されたノイズを低減するbootstrappingが高速であることや，TFHEを実装したオープンソースソフトウェアが充実していることから，注目を集めている．しかし，TFHEに基づくThFHEは，我々が知る限り提案されていない．本稿では，TFHEに基づくクライアント補型のThFHEを提案する．提案方式は，TFHEと同じbootstrappingを実現しつつ，分散暗号化や分散復号が可能なため，複数の参加者からの入力を用いた秘密計算を実現できる．
  4. 杉﨑 行優, 高橋 大介, NVIDIA Volta GPU における浮動小数点演算を用いた剰余乗算の高速化, 日本応用数理学会 2020年 年会, 2020
    Abstract: 本研究では剰余乗算を効率的に計算するモンゴメリ乗算アルゴリズムを NVIDIA Volta GPU 向けに実装し性能を評価した．本講演では，整数と浮動小数点の演算器が独立に存在し動作するという NVIDIA Volta GPU の特性を活かし，整数演算と浮動小数点演算の両方を用いてモンゴメリ乗算を計算した場合の性能の向上について報告する．