search

initc3 / HoneyBadgerMPC

Robust MPC-based confidentiality layer for blockchains
GNU General Public License v3.0
131 stars 64 forks source link

fixed point algorithm explanation #450

Open amiller opened 4 years ago

amiller commented 4 years ago

This explanation looks off - what does it mean to leak an information theoretic bit? Fix this issue with a more informative comment explaining the function of the fixed point operations https://github.com/initc3/HoneyBadgerMPC/blob/46dd3d449d0829ced7b54474c11d9a7d12fa63ca/honeybadgermpc/progs/fixedpoint.py#L26

amitgtx commented 4 years ago

How does this explanation look:

This library provides basic arithmetic functionalities which are needed when the underlying types are real values. To enable that, it uses fixed point representation of real numbers. Note that the implementation of fixed point operations in this library is only statistically (and not perfectly) hiding. This means that whenever a fixed point operation from this library is invoked, the resulting output is only statistically (and not perfectly) indistinguishable from a uniformly random output, and the statistical distance is O(1/(2^Kappa)). In simple terms, increasing the Kappa parameter would make the output look more close to uniform random but also incur higher computational/communication cost.

amiller commented 4 years ago

It is not correct to say these are real values, since only a subset of real values can be represented. It would be closer to accurate to say rational rather than real, although only some rationals can be represented as well

amiller commented 4 years ago

Which operation leaks information, could you point more specifically to where / how this can occur? Which operations are perfectly hiding and which are statistical?