Low-Size Coupons for Low-Cost IC Cards
Marc Girault · 2000
We address the challenging issue of authenticating a (very) low-cost IC card in a (very) short period of time with public key techniques. Such a need is growing, e.g. in public transport area, where the requirements are very tight, due to a contactless interface and a very short transaction time. Zero-knowledge discrete-logarithm-based authentication schemes with “use and throw coupons” (i.e. commitments which are precomputed, stored in the card and used only once) are well suited to this problem, but state of the art provides coupons which are still too large in many applications (namely 85–90 bits, by Girault and Stern [GS94]). In this paper, we first observe that the [GS94] paradigm allows to derive a better bound than the one above (about 64 bits), but turns out to be too restrictive, as it only considers off-line attackers (those who perform exhaustive trials prior to the authentication process). This leads us to propose a more realistic environment, in which both off-line and on-line attacks can take place. Then we show that the length of the coupons can nonetheless be still significantly decreased (down to 32 bits!), just by assuming that both time and computational power of the enemy are limited during authentication process. Combined with self-certification or elliptic curve techniques, this allows us to store more than 200 coupons in the IC card, if (only) 1 Kbyte of the E 2 PROM memory is occupied by the whole cryptographic material.