Difficulty understanding 'random square root' in enhancement to fiat-shamir This was published in 1986 and I'm trying to reproduce it in an assignment. It's a small variation on fiat-shamir, by the original author, which does away with a public key (and supposedly drastically improves performance) by doing:


  Our improvement comes about from choosing the ${v_{i}}'s$ to be the first $k$ prime numbers
  $(v_1=2,v_2=3,v_3=5)$, etc. The ${s_{i}}'s$ will then be set to be a random square root of the corresponding $v_i \bmod n$


In the paper, ${v_{i}}'s$ are the public key, ${s_{i}}'s$ are the private key.

But I'm a bit lost with the wording. It says to set the ${s_{i}}'s$ to the random square root of the corresponding $v_i \bmod n$.

So the corresponding $v_i$ for $s_1$ would be 2. If $n=pq=11*19=209$, then does this mean that $s_i = \sqrt{2} \bmod n$? 

Obviously this isn't correct, so I'm sure I'm missing an assumption somewhere. Any help would be really appreciated.

Nb. For reference, there's a paper which isn't behind a paywall which looks at this enhancement. There's also a patent for the scheme here.



edit: After poncho's post, I plugged his two example values into the algorithm and the scheme doesn't seem to work.

p=11
q=19
n=p*q # 209

r = 123 # random 
e= 1.234 # random challenge

v = 5 # public key
s = 29 # secret key
y = (r)*(s**e) % n 

rhs = (y**2)*(v**e) % n 
x = r**2 % n 
assert x == rhs
So the corresponding $v_i$ for $s_1$ would be 2. If $n=pq=11∗19=209$, then does this mean that $s_i = \sqrt{2} \bmod n$?


What they mean by "square-root of $x$" is the value $y$ that is a solution to $y^2 \equiv x \pmod n$; as there are multiple solutions (in the cases that at least one solution exists), then by a random solution, they mean to pick one randomly.

Now, in the case of $n=209$, it turns out that there isn't a solution for $v_i = 2$ or $3$.  However, there are four solutions for $v_i = 5$, namely 29, 48, 161, 180 (and for $n$ which is a product of two distinct odd primes and with $v_i$ nonzero and small (that is, $&lt; p, q$), there will always be either zero or four solutions); the algorithm is to set $s_i$ to one of the four randomly.

As for how to compute the square root of $x$, the procedure is:


Compute $x_p = x \bmod p$ and $x_q = x \bmod q$
Compute the values $y_p$ that satisfies $y_p^2 \equiv x_p \bmod p$ and the values $y_q$ that satisfies $y_q^2 \equiv x_q \bmod q$; and if there doesn't exist either a $y_p$ or a $y_q$ that satisfies the above equations, then there doesn't exist such a $y$.  This computation can be done in the general case by the Tonelli–Shanks algorithm (and with simpler algorithms in the case that $p, q \not\equiv 1 \pmod 8$)
Usually, the above will give two possible values for $y_p, y_q$; pick one randomly (this will perform the 'random selection' logic specified.
Use the Chinese remainder theorem to find the value $y$ with $y \equiv y_p \pmod p$ and $y \equiv y_q \pmod q$; you're done