Proposal for Piece in Hand Matrix : General Concept for Enhancing Security of Multivariate Public Key Cryptosystems(<Special Section>Discrete Mathematics and Its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
It is widely believed to take exponential time to find a solution of a system of random multivariate polynomials because of the NP-completeness of such a task. On the other hand, in most of multivariate public key cryptosystems proposed so far, the computational complexity of cryptanalysis is polynomial time due to the trapdoor structure. In this paper, we introduce a new concept, piece in hand (soldiers in hand) matrix, which brings the computational complexity of cryptanalysis of multivariate public key cryptosystems close to exponential time by adding random polynomial terms to original cryptosystems. This is a general concept which can be applicable to any type of multivariate public key cryptosystems for the purpose of enhancing their security. As an implementation of the concept, we propose the linear PH matrix method with random variables. In 2003 Faugere and Joux broke the first HFE challenge (80 bits), where HFE is one of the major variants of multivariate public key cryptosystem, by computing a Grobner basis of the public key of the cryptosystem. We show, in an experimental manner, that the linear PH matrix method with random variables can enhance the security of HFE even against the Grobner basis attack. In what follows, we consider the strength of the linear PH matrix method against other possible attacks.
- 社団法人電子情報通信学会の論文
- 2007-05-01
著者
-
TADAKI Kohtaro
Research and Development Initiative, Chuo University
-
TSUJII Shigeo
Research and Development Initiative, Chuo University
-
Tsujii S
Institute Of Information Security
-
Tsujii Shigeo
Institute Of Information Security
-
Fujita Ryou
Research And Development Initiative Chuo University
-
FUJITA Ryou
Institute of Information Security
-
TADAKI Kohtaro
21st Century Center Of Excellence Program, Chuo University
-
Tsujii S
Graduate School Of Information Security Institute Of Information Security:research And Development I
関連論文
- Key-Generation Algorithms for Linear Piece In Hand Matrix Method
- Anonymous Query Language Retrieval (ライフインテリジェンスとオフィス情報システム)
- Anonymous Query Language Retrieval (情報セキュリティ)
- Key-Generation Algorithms for Linear Piece In Hand Matrix Method
- Dually-Perturbed Matsumoto-Imai Signature (DPMS) Scheme
- Security Enhancement of Various MPKCs by 2-Layer Nonlinear Piece in Hand Method
- Proposal for Piece in Hand Matrix : General Concept for Enhancing Security of Multivariate Public Key Cryptosystems(Discrete Mathematics and Its Applications)
- A Subspace Blind Identification Algorithm with Reduced Computational Complexity : Colored Noise Case(Digital Signal Processing)
- A Practical Subspace Blind Identification Algorithm with Reduced Computational Complexity : Colored Noise Case
- A Practical Subspace Blind Identification Algorithm with Reduced Computational Complexity(Digital Signal Processing)
- Improvements of Addition Algorithm on Genus 3 Hyperellipic Curves and Their Implementation(Public Key Cryptography)(Cryptography and Information Security)
- Baby Step Giant Step Algorithms in Point Counting of Hyperelliptic Curves
- Robust noise suppression algorithm using the only Kalman filter theory for white and colored noises (Speech) -- (国際ワークショップ"Asian workshop on speech science and technology")
- Robust Noise Suppression Algorithm with the Kalman Filter Theory for White and Colored Disturbance
- Robust noise suppression algorithm using the only Kalman filter theory for white and colored noises
- A CGM APPROACH TO SUBSPACE BASED BLIND CHANNEL IDENTIFICATION