Comparisons and other operations from Viff

[amiller]

Viff comes with support for several useful operations, such as comparing greater than / less than / equality for integers, splitting integers into parts, etc. see this for example https://github.com/amiller/viff/blob/master/apps/compare.py

~- [ ] Bit decomposition~

• [x] Equality testing
• [x] Comparison

[hanyunx]

For Equality Testing, a potential way is [NO07]. It provides the following solutions:

• Simplified BD with complexity of (2+23) R + (93 L + 47L logL) M.
• Without BD
  • Deterministic Equality Test Protocol with complexity of (2+6) R + 81L M (ongoing)
  • Probabilistic Equality Test Protocol with complexity of (2+2) R + 12k M, k - secure parameter
    • p = 3 mod 4 -> (-1 / p) = -1, bj \in { -1, 1 } which is implemented in viff
    • p = 5 mod 8 -> (2 / p) = -1, bj' = -(bj - 3) / 2 \in { 2, 1 }
    • To extend to arbitrary primes -> (y/p) = -1
      • [ ] p = 1 mod 8 -> let y = 5, s.t. (y / p) = -1, bj' = -2 * (bj - 3/2) \in { 5, 1 }

[amiller]

https://github.com/initc3/HoneyBadgerMPC/blob/4dc26133030aebe31d70b239d502fac6a8c8afa5/honeybadgermpc/passive.py#L393 work in progress