search

amiller / viff

Clone of http://viff.dk/
GNU General Public License v3.0
2 stars 2 forks source link

Add Reed-Solomon decoding to online phase #1

Closed amiller closed 6 years ago

amiller commented 6 years ago

When opening a secret shared value, the shamir.recombine method uses la grange polynomial interpolation. This handles erasures, but errors result in an incorrect polynomial (too high a degree). This is detected in the verify_sharing method, but once detected, there's little else to do but fail.

To provide fault tolerance in the online phase, we should add Reed-Solomon decoding. This should require n>4t+1 (or possibly n>3t+1, I'm not sure) Here's a reference for RS decoding in pure python that seems nicely commented and instructional. https://github.com/tomerfiliba/reedsolomon/blob/master/reedsolo.py

amiller commented 6 years ago

There are several RS decoding algorithms. Many of the optimization guidelines are geared towards GF(2^k) operations whereas we're in GF(p) anyway. For large values of n, an FFT based algorithm might be the most scalable (O(n log n)) but maybe this is overkill for the 5 <= n <= 50 range we're targetting. Berlekamp-Welch seems like it may be the simplest (Tutorial by Jeremy Kun)

amiller commented 6 years ago

Closing, see https://github.com/initc3/HoneyBadgerMPC/pull/4