本稿ではNP完全問題に基づく2つの公開鍵認証方式を提案する.1つは格子に関連した問題であるNELVPに基づく認証方式,もう1つは部分和問題に基づく認証方式である.これらの方式の安全性に関しては,ゼロ知識性の代わりに証拠秘匿性と呼ばれる性質を有していることを示す.証拠秘匿性は認証方式の安全性を保障するためには十分であると考えられているため,我々の提案方式も安全であると考えられる.また,我々の方式と様々な既存方式の効率を比較した結果,我々の方式は安全性を保障するために必要な繰り返しの回数,または,プロトコル1回の実行における計算量の点で優れていることが分かった.