On the security of a practical identification scheme (Q1819122)

An identification scheme is an interactive protocol in which one party, \(P\), the prover, attempts to convince another party, the verifier, \(V\), of its identity. The prover has a public and private key which are used to effect the protocol. Various types of attack of the system might be considered, from a passive attack where the adversary does not interact with the system before attempting impersonation, to an active attack where the adversary poses as \(V\) and interacts as \(V\) but not necessarily following the protocol. Other intermediate types of attack are also possible. For the \(2^m\)th root scheme of interest here, a modulus \(n\) is chosen as the product of two `Blum' primes, both equal to 3 modulo 4 (not an essential feature of the work). An element \(a\) is chosen at random and \(b\) is set to \(a^q,~q=2^m\) where \(m\) is such that \(2^m\) grows faster than any polynomial in the security parameter \(k\), and \(m = O(k)\). The public key is then \((b,n)\) and the secret key is \(a\). The protocol then executes the following steps once: 1. \(P\) chooses \(r\) at random, computes \(x = r^q\) and sends \(x\) to \(V\). 2. \(V\) chooses \(e \in \{ 0, \dots , q-1 \}\) at random and sends \(e\) to \(P\). 3. \(P\) computes \(y = r \cdot a^e\) and sends \(y\) to \(V\); \(V\) accepts if \(y^q = x \cdot b^e\) and rejects otherwise. The efficiency of this scheme is superior to the more usual square root scheme. It is shown here that the scheme is secure if factoring is hard, even against active attacks where the adversary is first allowed to pose as a verifier before attempting impersonation. Although this scheme is not new, its security was not apparently fully understood.