Improving Efficiency of an 'On the Fly' Identification Scheme by Perfecting Zero Knowledgeness

摘要

In this paper, we present a new methodology for constructing an efficient identification scheme, and based on it, we propose a lightweight identification scheme whose computational and storage costs are sufficiently low for even cheap devices such as RFID tags. More specifically, we point out that the efficiency of an identification scheme satisfying statistical zero-knowledgeness can be significantly improved by enhancing its zero-knowledgeness to perfect zero-knowledge, and apply this technique to the Girault-Poupard-Stern (GPS) scheme which has been standardized by ISO/IEC. Using standard recommended parameters, in the resulting scheme, the computational cost is as low as GPS, i.e., it is estimated only differs 0.8 ms on a CMOS technology with 100 kHz clock rate, and compared to GPS, both the communication cost and storage cost are approximately 28% reduced, i.e., prover's response is shortened from 276 bits to 196 bits (80 bits reduced) and for application with coupons, memory for 20 coupons is reduced from 8700 bits to 7120 bits (1580 bits reduced).