複数の計算量仮定を組み込んだメタ帰着技法による安全性解析:　ElGamal暗号の場合

摘要

Meta-reduction technique is the method that the security of single key factoring-based encryption or signature is analyzed. In the previous works, the meta-reduction technique was discussed only under single computational assumption. In this paper, we show that more rigorous security analysis is possible by using the meta-reduction under several computational assumptions. We discuss, as an example, the security analysis of ElGamal encryption using the meta-reduction under Computational Diffie-Hellman problem, Decisional Diffie-Hellman problem, and Strong Diffie-Hellman problem.%単一鍵素因数分解問題に基づく暗号・署名系の安全性を解析する手法としてメタ帰着技法が知られている.既存の研究では，メタ帰着技法をある1つの計算量的仮定の下でのみ用いて安全性解析を行っていた.本稿では，メタ帰着を用いた解析において，複数の計算量的仮定を用いることで，1つの仮定のみを用いた場合よりも厳密な解析が行える場合を示す.具体的な例として，ElGamal暗号方式の安全性をComputational Diffie-Hellman問題，Decisional Diffie-Hellman問題，Strong Diffie-Hellman問題の下で解析を行う.