[viff-devel] [issue55] Speedup for ComparisonToft07Mixin

[Martin Geisler]

New submission from Martin Geisler <mg at daimi.au.dk>:

In http://article.gmane.org/gmane.comp.cryptography.viff.devel/241
Tomas Toft writes:

  [...] Nice speedup. It's also possible to do a similar thing for
  ComparisonToft07Mixin. In the two-fields variation we need the same
  bit in Zp and Zq, where q<<p, say p is 500-bit and q=3001.

  Similarly to generating the same random bit in Zp and GF(256), we
  can

  1) generate a random bit [b]_p in Zp

  2) generate a pseudorandom number [r]_p (of limited size) in Zp and
     the same number mod q in Zq [r mod q]_q (similar to the present
     case, where q "implicitly" is two)

  3) c <- open([b]_p + [r]_p)

  4) [b]_q = ((c mod q) - [r mod q]_q)

I believe this was never implemented.

----------
messages: 142
nosy: mg
status: unread
title: Speedup for ComparisonToft07Mixin

____________________________________
VIFF Issue Tracker <tracker at viff.dk>
<http://tracker.viff.dk/issue55>
____________________________________