素因数分解の困難性に依拠したTSK型多変数公開鍵暗号の構成法

摘要

素因数分解の困難性と等価な安全性を有する多変数公開鍵暗号（MPKC）を提案する．一般に，MPKCは，RSA暗号などと異なり，量子コンピュータが実用化された場合にも解読されない安全性を期待できること，及び，変数の2乗計算でRSA暗号のようなべき乗計算が不要であり，変数の2乗計算で済むため暗号化·復号が高速に行えることが利点とされている．しかし，量子コンピュータに対する安全性証明を付すことは難しい課題である．本文では，現在のコンピュータによる解読を前提として，素因数分解と等価な安全性を有する順序解法型MPKCを提案する．