A realistic security analysis of identification schemes based on combinatorial problems
Guillaume Poupard · European Transactions on Telecommunications · 1997
Abstract In this paper, we analyze the security of two zero‐knowledge identification schemes based on combinatorial NP‐complete problems, PKP (Shamir [3]) and CLE (Stem [5]). We use two different approaches in order to determine, on the one hand, the theoretical limit to the efficiency of the known attacks and, on the other hand, the practical results they permit. Accordingly, we obtain a precise evaluation of which parameters should be chosen today for a secure use of these protocols.