GGH系格子暗号に対する復号誤り確率とその評価式の提案

摘要

The GGH cryptosystem is a public key cryptosystem proposed by O. Goldreich, S. Goldwasser and S. Halevil in 1997. This cryptosystem is based on computationally hard problem; the closest vector problem(CVP) and the shortest vector problem(SVP). Recently, several cryptosystems improved from the GGH cryptosystem were proposed. We call these cryptosystems GGH series. However, the evaluation for decryption failure about GGH series is insufficient. Then, we consider the existing evaluation and propose new evaluation in this paper. Our proposal evaluation can give an efficient upper bound of decryption failure about GGH series. Namely, we can strictly evaluate decryption failure about GGH series by using our proposal evaluation.%GGH暗号は1997年にO．Goldreich，S．Goldwasser，S．Haleviによって提案された公開鍵暗号である.GGH暗号は格子の最近ベクトル問題（CVP）と最短ベクトル問題（SVP）を安全性の根拠としており，現在ではGGH暗号をより効率的に使用するための改良暗号も多数提案されている．しかしGGH系格子暗号に対する復号誤り確率の評価に関しては多く議論されていない．よって本稿ではGGH系格子暗号に対する復号誤り確率に関して考察を与え，GGH系格子暗号において復号誤り確率を議論することの重要性を示す．次に既存の復号誤り確率の評価方法より効率のよい評価方法を提案する．提案方法を用いることでGGH系格子暗号の復号誤りを効率的に抑えることが可能であり，より厳密な復号誤り確率の評価を可能とする．