TFHEを用いた高速な否認可能完全準同型暗号

完全準同型暗号（Fully Homomorphic Encryption：FHE）とは，暗号文に対する何らかの演算を行うことで，中身の平文に対する任意の演算を復号することなく行うことのできる暗号方式である．FHEはデータベースや機械学習などに対するプライバシー保護技術への関心の高まりとともに注目を集めている．プライバシー保護技術の観点から，否認可能暗号も重要な暗号技術である．否認可能暗号は，公開された暗号文に対応する平文を明らかにするよう強制されたあるユーザが，どのメッセージを暗号化したかについて嘘をつくことを可能にする．AgrawalらはFHEと否認可能暗号を組み合わせた否認可能完全準同型暗号（Deniable FHE：DFHE）のモデルを提案し，いくつかの条件を満たすFHE（Special FHE）をDFHEへ変換する方法，及びBGV（Brakerski-Gentry-Vaikuntanathan）方式に基づくSpecial FHEの構成法を提案した（CRYPTO 2021）．しかし，Agrawalらの構成では実行に時間がかかるBootstrappingと呼ばれる操作が実行速度のボトルネックになっている．本発表ではBootstrappingが高速なFHEとして知られているTFHE（Chillotti et al., J. Cryptol., 2020; Joye, CT-RSA 2024）がSpecial FHEの条件を満たすことを示すことで，AgrawalらのBGVベースの構成よりも高速なDFHEを実現できることを示す．

Fully Homomorphic Encryption (FHE) is a cryptographic scheme that can take ciphertexts as inputs and compute a new ciphertext of a function of the underlying plaintexts without decryption. FHE has been attracting attention along with the growing interest in privacy-preserving technologies. In terms of privacy-preserving technology, deniable encryption is also important. Deniable encryption enables a user, who may be forced to reveal the plaintexts corresponding to the user's public ciphertexts, to lie about which messages the user encrypted. Agrawal et al. introduced Deniable FHE (DFHE) that combines FHE with deniable encryption, and proposed a transformation from an FHE scheme that satisfies specific special requirements, called special FHE, to a DFHE scheme. They also showed a construction of a special FHE scheme based on the BGV (Brakerski-Gentry-Vaikuntanathan) scheme (CRYPTO 2021). However, in the construction of Agrawal et al., a bootstrapping operation, which takes a long time to execute, is a bottleneck in execution speed. In this paper, we show that TFHE (Chillotti et al., J. Cryptol., 2020; Joye, CT-RSA 2024), which is known as a FHE scheme with fast bootstrapping, satisfies the requirements of special FHE, and thus can realize a faster DFHE scheme than the BGV-based construction.