Issue55

Title Speedup for ComparisonToft07Mixin
Type wish Status chatting
Importance
Superseder Nosy List mg, t.toft
Assigned To Keywords

Created on 2008-07-25.22:55:03 by mg, last changed 2008-09-23.17:36:57 by mg.

Messages
msg209 (view) Author: mg Date: 2008-09-23.17:36:57
Would you have time to implement this?
msg142 (view) Author: mg Date: 2008-07-25.22:55:03
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.
History
Date User Action Args
2008-09-23 17:36:57mgsetstatus: unread -> chatting
type: feature -> wish
messages: + msg209
2008-09-23 16:23:18tpjsettype: feature
2008-07-28 14:45:14mgsetpriority: None
nosy: + t.toft
2008-07-25 22:55:03mgcreate
Note:
The indicated property no longer exists