Truncation protocol

[Kortekaasy]

Hi,

I was wondering which protocol MPyC uses for truncation in the mpyc/runtime.py, since I cannot seem to find it in the sourcecode itself.

Thanks in advance!

[lschoe]

Hi, good question. So the idea behind this protocol goes by the name "probabilistic rounding". The main advantage of the protocol is that a secure comparison is avoided, at the price of not always rounding down (truncating) but possibly rounding up instead. A number of the form $n+\alpha$ is truncated correctly to $n$ with probability $1-\alpha$. So, $n+0.25$ is truncated to $n$ with probability $0.75$ (and otherwise the result is rounded up to $n+1$). Similarly, $n+0.8$ is truncated to $n$ with probability $0.2$.

I've looked it up in the literature and probabilistic rounding goes back to Protocol 3.1 in the paper Secure Computation with Fixed-Point Numbers by Octavian Catrina and Amitabh Saxena.

[Kortekaasy]

Awesome, thanks! Is there a (public) overview somewhere that lists per operation in MPyC the literature that it was based on? Anyway, thanks for your help!

[lschoe]

Not that I know of;) Maybe something to include for the release of version 1.0, targeted for next year. The protocols behind the various operations are a mix of well-known solutions, sometimes solutions from specific publications and variants thereof, and solutions that are part of new, often ongoing, work of our own.

[Kortekaasy]

It would be nice to have such an overview, but I can imagine that it gets difficult when you have to account for application-specific variants of publications. Thanks for your detailed help and quick responses!