A new NP-complete problem and public-key identification (Q1866023)

The theory of zero-knowledge made it possible to design secure identification schemes. However, as most of the proposed schemes are based on problems from number theory, practical implementations -- especially those for smart cards -- must deal with hard to perform modular operations using a large modulus. The paper presents an efficient identification scheme based on a combinatorial NP-complete problem -- the permuted perceptrons problem. First, the perceptrons problem is introduced and its NP-completeness is proved. Also it is shown that the problem is not only difficult to solve in the worst case, but also it cannot be efficiently approximated. From a general Goldreich-Micali-Wigderson result it follows that NP-completeness of the perceptrons problem is enough for the existence of zero-knowledge interactive proof of knowledge that can be subsequently turned into an identification protocol. However, for efficiency reasons the authors focus on a variant of the problem -- the permuted perceptrons problem and prove that the problem is also NP-complete. In the next section the practical security of both problems is analyzed. Several possible attacks are reviewed, and then practical sizes of problem instances are suggested. Then two schemes (three-pass and five-pass identification protocols) are proposed and thoroughly analyzed. The selection of the system parameters is then discussed, and a practical version of the three-pass identification scheme is described. Finally, the actual implementation of the protocol on a low-cost smart card is discussed. A brief comparison with other protocols is given as well.