I was trying to implement zero knowledge protocol for authentication based on the paper "A Practical Zero-Knowledge Protocol Fitted to Security Microprocessor Minimizing Both Transmission and Memory".

In that, the first step is…

each security device with identity $I$ receives an authentication value $B$ (The inverse of $A$ modulo $n$) computed by some authority from $A=J^{1/\mu} mod\ n$, where $J$ is the shadowed identity $I$

Also, they have defined “shadow” as…

Shadow: One first completes a short message (half the length of a public modulus $n$) with a similar sized redundancy, named shadow, then extracts the $\mu^{th}$ root of this element in the chosen ring based on the composite integer $n$.

From my point of view (being a programmer), I do not understand what this “shadow” is and how to calculate it.

Also there is a sentence…

then extracts the $\mu^{th}$ root of this element in the chosen ring based on the composite integer $n$

How I set the value of $\mu$? Can I take any arbitrary value? What is the significance of that value?

Also there is a step $t=r.B^d\ mod\ n$. This means $(r.B^d)\ mod\ n$ or $r.(B^d\ mod\ n)$?


1 Answer 1


The GQ identification scheme is essentially a zero-knowledge proof of a value $x$ such that $x^\mu \equiv J \pmod N$ where $N$ is an RSA modulus and $(\mu,N)$ are system parameters and $J$ is known to the verifier and $x$ only known to the prover.

Now your question is not directly concerned with the aforementioned proof where a user shows the possession of a credential, but with how credentials are issued to users by the authority.

Before going into the questions regarding the GQ identification scheme, I briefly recall existential forgeability of textbook RSA signatures.

Recall the RSA setting where we have an RSA modulus $N=pq$ being the product of two primes $p$ and $q$ and the public exponent $e$ being an invertible element of the multiplicative group $\mathbb{Z}_N^*$ (with order $\phi(N)$) and the private key $d$ it's multiplicative inverse, i.e., $d \equiv e^{-1} \pmod{\phi(N)}$. Now we may abuse the notation and write $d:=1/e$ (what is done in the GQ paper).

So, in texbook RSA signatures the computation of a signature for a message $m\in \mathbb{Z}_N$ amounts to computing $\sigma \equiv m^d \pmod{N}$ and verification amounts to checking $m\equiv \sigma^e \pmod{ N}$.

Observe, that by simply choosing $\sigma$ and computing the message $m$ as $m:= \sigma^e {\mod N}$ gives an existentially forged message signature pair $(m,\sigma)$ for the textbook RSA signature.

Observe, however, that the adversary cannot control the message $m$, since the adversary cannot predict what $\sigma^e$ will yield (consequently, it is a good idea to apply a cryptographic hash function $H$ to messages before signing, since then such an existential forgery would yield $H(m)$ and one would need to find $m$ which is firstly hard given a secure hash function and moreover will very likely not yield a meaningful message $m$ anyways. This is called the hash then sign paradigm).

Shadowed Identity

Now, exactly this is the purpose of a shadowed identity in GQ, i.e., we require the credential including identity $I$ to have some structure and thus the identity is shadowed to $J$. Consequently, it is not efficiently possible to choose a random element $A$, compute it's $\mu$'th power ($\mu$ is the public key $e$ from above) and obtain a valid shadowed identity $J$. Note, that one could choose $A$ randomly and compute $J\equiv A^\mu \pmod N$, but requiring $J$ to have some defined redundancy (being an shadowed identity), such a forgery will not lead to a valid identity $J$ under the redundancy scheme with very high probability.

Note that this prevents an adversary from computing a credential on its own without interacting with the authority (knowing the value $1/\mu$). The authority, however, can form the shadowed identity $J$ and then compute $A\equiv J^{1/\mu} \pmod N$. Observe that this is essentially a textbook RSA signature of the authority for message $J$.

Nevertheless, it is not exactly stated in the paper how this shadow should be chosen.

Extracting $\mu$'th roots

Note that $\mu$ plays to role of $e$ (the public exponent) in the RSA setting and note that computing the inverse $1/\mu$ from $(\mu,N)$ (which is equivalent to the private exponent $d$ in the RSA setting) requires to know the factorization of $N$. Observe that $1/\mu$ is computed as the multiplicative inverse of $\mu$ modulo $\phi(N)$ using the extended euclidian algorithm.

In the GQ identification scheme as described in their paper, the factorization of $N$ is only known to some authority and thus the identification tokens $A$ can only be computed by this party. Consequently, having this redundancy scheme (shadowed identities) and limiting the knowledge of the private key $1/\mu$ and the factorization of $N$ to some authority, $\mu$ and $N$ can be system parameters for many users.

The value $\mu$ can be chosen to be any value that is co-prime to $\phi(N)$ and for instance fixed to the prime $2^{16}+1$ as it is common in the RSA setting.

Last part of the question

You write

Also there is a step $t=r.B^d\ mod\ n$. This means $(r.B^d)\ mod\ n$ or $r.(B^d\ mod\ n)$?

It means $(r\cdot B^d)\ mod\ n$ and this is equivalent to $(r\cdot (B^d mod\ n))\ mod\ n$.

Final remark

Finally, I would like to suggest to read about the GQ identification scheme in another source such as chapter 10 of the freely available Handbook of Applied Cryptography, since the description is much easier accessible than in the original paper.

  • $\begingroup$ What is the recommended method for calculating shadow? $\endgroup$
    – user5507
    Dec 26, 2013 at 2:00
  • 1
    $\begingroup$ The method of choice to prevent such issues in practice is to use a hash function (as in the hash then sign paradigm). In this context you would compute the shadowed identity $J$ as being the hash value of the identity information. A widely used real world example for RSA signatures is for instance the encoding used in RSASSA-PKCS1-v1_5. $\endgroup$
    – DrLecter
    Dec 26, 2013 at 7:25
  • $\begingroup$ One last question. There is an equation in the text "$s_A=(J_A)^{−s}mod\ n$". How could I calculate that? Taking $(J_A)^{−s}$ and taking mod n? $\endgroup$
    – user5507
    Dec 27, 2013 at 14:35
  • $\begingroup$ I assume you refer to the chapter in the handbook of applied cryptography. You compute the value of $-s$ as $\phi(n)-s$, i.e., $-s$ is the additive inverse of $s$ in the group of order $\phi(n)$ and thus $\phi(n)-s$. Then you can use any fast exponentiation algorithm of your choice to compute the value $s_A$ by raising $J_A$ to the power of $\phi(n)-s$. Clearly, since you are working in $Z_n$ the value $s_A$ is in $Z_n$ and thus you always reduce modulo $n$, i.e., when doing multiplications and exponentiations. $\endgroup$
    – DrLecter
    Dec 27, 2013 at 15:13
  • 1
    $\begingroup$ Strange, even when adding $n$ to make it positive your result is wrong :/ However, I do not know your implementation. A quick check using WolframAlpha shows that it should be correct. $\endgroup$
    – DrLecter
    Dec 27, 2013 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.