Designing Identification Schemes with Keys of Short Size

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.