Abstract
In the last few years, there have been several attempts to build identification protocols that do not rely on arithmetical operations with large numbers but only use simple operations (see [10, 8]). One was presented at the CRYPTO 89 rump session ([8]) and depends on the so-called Permuted Kernel problem (PKP). Another appeared in the CRYPTO 93 proceedings and is based on the syndrome decoding problem (SD) form the theory of error correcting codes ([11]). In this paper, we introduce a new scheme of the same family with the distinctive character that both the secret key and the public identification key can be taken to be of short length. By short, we basically mean the usual size of conventional symmetric cryptosystems. As is known, the possibility of using short keys has been a challenge in public key cryptography and has practical applications. Our scheme relies on a combinatorial problem which we call Constrained Linear Equations (CLE in short) and which consists of solving a set of linear equations modulo some small prime q, the unknowns being subject to belong to a specific subset of the integers mod q. Thus, we enlarge the set of tools that can be used in cryptography.
PATENT CAUTION: This document may reveal patentable subject matter
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
T. Baritaud, M. Campana, P. Chauvaud and H. Gilbert: On the security of the permuted kernel identification scheme. In: Proceedings of Crypto 92. Lecture Notes in Computer Science 740. Berlin: Springer 1993, pp. 305–311.
M. Bellare and P. Rogaway: Random oracles are practical: a paradigm for designing efficient protocols. In: Proceedings of the 1st ACM Conference on Computer and Communications Security, 1993, pp. 62–73.
F. Chabaud: On the security of some cryptosystems based on error-correcting codes. In: Proceedings of Eurocrypt 94. Lecture Notes in Computer Science, to appear.
A. Fiat and A. Shamir: How to prove yourself: Practical solutions to identification and signature problems. In: Proceedings of Crypto 86. Lecture Notes in Computer Science 263. Berlin: Springer 1987, pp. 181–187.
U. Feige, A. Fiat and A. Shamir: Zero-knowledge proofs of identity. In: Proc. 19th ACM Symp. Theory of Computing, 1987, pp. 210–217 and J. Cryptology 1, 77–95 (1988).
S. Goldwasser, S. Micali and C. Rackoff: The knowledge complexity of interactive proof systems. In: Proc. 17th ACM Symp. Theory of Computing, 1995, pp.291–304.
J. Patarin and P. Chauvaud: Improved algorithms for the permuted kernel problem. In: Proceedings of Crypto 93, Lecture Notes in Computer Science 773. Berlin: Springer 1994, pp. 391–402.
A. Shamir: An efficient identification scheme based on permuted kernels. In: Proceedings of Crypto 89. Lecture Notes in Computer Science 435. Berlin: Springer 1990, pp. 606–609.
R. L. Rivest: The MD5 Message Digest Algorithm. In: Proceedings of Crypto 90. Lecture Notes in Computer Science 537. Berlin: Springer 1991, pp. 303–311.
J. Stern: An alternative to the Fiat-Shamir protocol. In: Proceedings of Eurocrypt 89. Lecture Notes in Computer Science 434. Berlin: Springer 1990, pp. 173–180.
J. Stern: A new identification scheme based on syndrome decoding. In: Proceedings of Crypto 93. Lecture Notes in Computer Science 773. Berlin: Springer 1994, pp. 13–21.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Stern, J. (1994). Designing Identification Schemes with Keys of Short Size. In: Desmedt, Y.G. (eds) Advances in Cryptology — CRYPTO ’94. CRYPTO 1994. Lecture Notes in Computer Science, vol 839. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48658-5_18
Download citation
DOI: https://doi.org/10.1007/3-540-48658-5_18
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58333-2
Online ISBN: 978-3-540-48658-9
eBook Packages: Springer Book Archive