C language implementation of an indeterminate equation encryption scheme based on the approximate ideal GCD problem and fast implementation using Karatsuba method

IPSJ

Bibliographic Information

Other Title
  • 近似イデアルGCD問題に基づく不定方程式暗号のC言語による実装とKaratsuba法による高速化について

Description

米国にて NIST (米国国立標準技術研究所) による耐量子計算機暗号の標準化が進められている．その標準暗号方式として現在，格子暗号が選定されているが，鍵サイズが現行の公開鍵暗号より大きく，ローエンドデバイスへの搭載が懸念されている．そこで本稿では，鍵サイズが RSA 暗号より短い不定方程式暗号に着目し，その高速化検討のため C 言語で実装した結果を報告する．結果，128bit 安全性の下で暗号化を 0.8 ミリ秒以下で実行でき，高速多項式乗算アルゴリズムの１つである Karatsuba 法の導入により更に約 10% 高速化できることが分かった．

The National Institute of Standards and Technology (NIST) is working on the standardization of post-quantum cryptography in the United States. Lattice-based cryptography is currently selected as the standard cryptographic scheme, but their key size is larger than that of current public-key cryptography, and there are concerns about their use in low-end devices. In this paper, we focus on indeterminate equation cryptography, which has a shorter key size than the RSA encryption and report the results of its implementation in C language to study its speedup. As a result, it was found that encryption can be performed in less than 0.8 milliseconds with 128-bit security, and that the Karatsuba method, one of the fast polynomial multiplication algorithms, can further speed up the process by about 10%.

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top