Tag Info

Hot answers tagged

4

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 ...


3

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 ...


2

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


2

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.


1

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