1
$\begingroup$

I am reading Vadim Lyubashevsky's paper on Lattice Signatures without Trapdoors and I came across a somehow counter-intuitive part where he defined an algorithm $\mathcal{A}$:

  1. $y\leftarrow D_\sigma^m$, where $D_\sigma^m$ is the discrete Gaussian distribution centered at $0$ with standard deviation $\sigma$ on $\mathbb{Z}^m$.
  2. $c$ is some hashed value
  3. $z\leftarrow Sc+y$, where $S$ is the signing key.
  4. output $(z,c)$ with some probability.

The pair $(z,c)$ is the potential signature and can only be output with the given probability in step $4$. He also mentioned that if nothing was output, the signer runs the signing algorithm again until some signature is outputted.

I just can't imagine an algorithm that doesn't give an output wherein the algorithm above, it seems that it will always produce a certain output. It also seems to violate the definition of an algorithm by Knuth. Am I missing something here?

Thanks!

Improve this question
$\endgroup$
2
$\begingroup$

I just can't imagine an algorithm that doesn't give an output wherein the algorithm above, it seems that it will always produce a certain output.

Actually, step 1 is randomized; that is, it will select a value of $r$ randomly (from some probability distribution). If step 4 decides to rerun the procedure, then step 1 will likely generate some different value, and so the output would be different.

It also seems to violate the definition of an algorithm by Knuth.

Well, by Knuth's definition, it's a "computational method" rather than "an algorithm". I don't think, in this case, the distinction is important, as the algorithm will terminate with probability 1 (and terminate quickly with high probability). I don't believe that Knuth had randomized procedures (like this one) in mind when he wrote his definitions...

Improve this answer
$\endgroup$
5
  • $\begingroup$ So this procedure needs to run at some number of times before the pair can be outputted just to make sure that the output fits to the specified criteria. Is that right? $\endgroup$ – Chito Miranda Mar 2 '20 at 22:12
  • $\begingroup$ @HabagatMaliksi: no, the procedure has a loop that runs a number of times (depending on when the probability allows the output to be generated). The fact that Lyubashevsky didn't write an explicit loop doesn't mean that one isn't there $\endgroup$ – poncho Mar 2 '20 at 22:21
  • $\begingroup$ Can you expand a little bit more about the loop? What exactly is the loop doing in this procedure? I cannot seem to understand it completely. $\endgroup$ – Chito Miranda Mar 2 '20 at 22:52
  • $\begingroup$ @HabagatMaliksi: you perform steps 1-4 of the procedure until step 4 generates an output $\endgroup$ – poncho Mar 3 '20 at 1:32
  • $\begingroup$ Thanks @poncho! When I read the paper multiple times, I finally understood what Lyubashevsky was trying to do. $\endgroup$ – Chito Miranda Mar 6 '20 at 5:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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