Is it possible that a signing algorithm produces no output?

Question

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!

Answer 1

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