An efficient statistical zero-knowledge authentication protocol for smart cards

Abstract

We construct an efficient statistical zero-knowledge authentication protocol for smart cards based on general assumptions. We show how it can be instantiated using lattice-based primitives, which are conjectured to be secure against quantum attacks. We illustrate the practicality of our protocol on smart cards in terms of storage, computation, communication, and round complexities. Furthermore, we compare it to other lattice-based authentication protocols, which are either zero-knowledge or have a similar structure. The comparison shows that our protocol improves the best previous protocol in several aspects.

Keywords:

• statistical zero knowledge
• authentication
• post-quantum cryptography
• smart cards
• lattice-based cryptography

2010 AMS Subject Classifications:

• 94A60
• 94A62
• 81P94

Acknowledgments

We would like to thank Dr Vincenzo Iovino and Prof. Mohammad Mahmoody, as well as the anonymous reviewers of the International Journal of Computer Mathematics, for their insightful comments.

Disclosure statement

No potential conflict of interest was reported by the authors.

Funding

This work is partially supported by ITRC.

ORCID

Mohammad Sadeq Dousti http://orcid.org/0000-0002-2330-8388

Rasool Jalili http://orcid.org/0000-0002-9853-1955

Notes

1. That is, the size of preimages for any element in the range of the function is polynomial in the security parameter. See Okamoto et al. [31] for more information.

2. To prevent notational confusion, we chose the Greek letter corresponding to the initial letter of the English name: α, β, and ι are mnemonics for authentication, binding, and inverting, respectively. Notice the difference between ι (Greek letter ‘iota’) and i.

3. Fiat and Shamir [12] suggest that the attacker can make at most 1000 forgery attempts per day. Thus, with a security level of $2^{-30}$, she will succeed (with constant probability) in masquerading once in every 3000 years. Therefore, our assumption that the adversary can make a forgery attempt once per second is very conservative, but it shows that even with such power, she cannot succeed in a reasonable amount of time.

4. [37] reduces ${\mathbf{S}\mathbf{I}\mathbf{S}}_{q,m,n,\sqrt{m}}^2$ to breaking the computational-binding property of the commitment, which is a weaker reduction. It also requires that q be a prime, but as we will see in Lemma 3, recent results relaxed this requirement.

5. While a semantically secure variant of McEliece is proposed by Kobara and Imai, the original McEliece is a TDP, as described in [13, footnote 2].

6. Implementations using the Java Card is much slower due to Java code being executed in a virtual machine. However, no smart-card manufacturer implements cryptography libraries in Java; they all use the native language of the card. For this reason, results obtained from the AVR microcontroller are much more considerable.