Laplace Sampler Implementaion

Stream: SampCert

[Markus de Medeiros]

Looking for a sanity check-- are DiscreteLaplaceSampleLoop' (link) and DiscreteLaplaceSampleLoop (link) meant to implement the same distribution? I'm assuming the latter is an optimization of the former (which I saw in the "Discrete Gaussian for Differential Privacy" paper) however I'm finding it subtle to prove that they're equivalent on paper.

There's also a comment about needing to generate and test both of them. Why is that?

[John Tristan]

Good question. Indeed, both implement the same distribution, and proving so is not trivial. Both are useful because they have incomparable runtime behaviors for different values of the scale. DiscreteLaplaceSampleLoop is more efficient for small scales, and vice versa.

Currently, we use only DiscreteLaplaceSampleLoop but eventually, we will use both and we will need to make sure that both are tested and proved. I may prove the correctness of DiscreteLaplaceSampleLoop' in the weeks to come.