A new NP-complete problem and public-key identification
type: Item
instance of: scholarly article
title: A new NP-complete problem and public-key identification
zbMATH Open document ID: 1024.94007
DOI: 10.1023/A:1021835718426
author: David Pointcheval
author: Guillaume Poupard
published in: Designs, Codes and Cryptography
publication date: 2003-04-03T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1892215
zbMATH Keywords: zero-knowledge
zbMATH Keywords: permuted perceptrons problem
zbMATH Keywords: NP-completeness
zbMATH Keywords: secure identification scheme
reviewed by: Jozef Vyskoč
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1892215