Tag Info

Hot answers tagged


The original 1986 Fiat-Shamir paper can be found here. The subsequent Feige-Fiat-Shamir 1988 paper can be found here, and contains the answer (Section 3): The $S_j$ (which are witnesses to the quadratic residuosity character of the $I_j$) are effectively hidden by the difficulty of extracting square roots $\bmod n$, and thus A can establish his ...


The problem is one of notation for modular arithmetic, at the point of the question reading if y^2 equals (x * v^e) % n then.. Likely the textbook is about if $y^2\equiv x\cdot v^e\pmod n$ then.. By definition of $a\equiv b\pmod n$, that holds if and only if $n$ divides $a-b$ (or equivalently: $|b-a|$ is a multiple of $n$). In the question, 437 ...


Without a sign the verifier learns that the number he received is a QR modulo n. Whether a number is a QR is a hard problem as he does not know the factors of n.


A just has to calculate $y=(x*v^e)^{\frac{1}{2}}$ and send it to B. Yes, if that was easy, the protocol would be breakable. However, finding square roots modulo a composite number is as difficult as factoring that number. See: Quadratic residue problem on composite integers


No, it wouldn't. Very simply put: If you can compute square roots wrt. a composite modulus, then you can calculate other fixed roots, too. This is based on the fact, that being able to compute square roots allows you to factor the modulus: Choose random $x$. Compute $x^2$. apply your square root algorithm to $x^2$. The result $y$ will be a different ...


Because we are working modulo $n$. There's not much more to say. There's no reason why any honest user would ever want to use a larger value. You might want to review modular arithmetic and its use in cryptography.

Only top voted, non community-wiki answers of a minimum length are eligible