多変数二次多項式に基づく公関鍵認証方式

概要

論文の詳細を見る
多変数二次多項式の求解問題(MQ問題)は暗号技術への応用が期待されている問題の1つである.しかし,MQ問題を利用する従来の公関鍵暗号方式の安全性はMQ問題のみならず別の数学的問題であるIP問題の困難性にも依存していた.本講演では著者等がCRYPT0 2011において発表した論文"Public-Key Identification Schemes Based on Multivariate Quadratic Polynomials"の紹介と解説を行う.その論文はMQ問題に基づく公関鍵認証方式を提案するものである.提案方式の特長の1つは,従来方式とは異なり,その安全性がIP問題の困難性に依存しないことである.提案方式の公開鍵サイズ及び認証に必要な通信データサイズはPermuted Kernels問題,Syndrome Decoding問題,Constrained Linear Equations問題,Permuted Perceptions問題などに基づく従来の公関鍵認証方式より小さい.
2011-12-07