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}$:
- $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$.
- $c$ is some hashed value
- $z\leftarrow Sc+y$, where $S$ is the signing key.
- 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!