> Hi Tomas (and viff-devel), Hi all
> We have two comparison protocols in VIFF: > > * ComparisonToft05Mixin which gives a result in GF256. It is described > in your progress report: > > http://www.daimi.au.dk/~tomas/publications/progress.pdf > > * ComparisonToft07Mixin where the result is a Zp element. As far as I > know it is not described in any published material. True. And on a sidenote: it bugs me that the comparisons return things differently, and therefore cannot be interchanged. It shouldn't be too costly to move the GF(256) back to Zp though. Alternatively, the '05 could be written entirely in Zp avoiding GF(256) all together. The XORs in the diamond operator can still be local by replacing them with addition and subtraction. bot = top_b * (bot_a - bot_b) + bot_b rather than bot = top_b * (bot_a ^ bot_b) ^ bot_b This does the same and avoids the conversion to GF(256), but may be more expensive online (IIRC GF(256) computation is /really/ fast). > I talked with Rune Thorbek yesterday, and he asked why we have not > implemented your comparison protocol from your PhD thesis: > > http://www.daimi.au.dk/~tomas/publications/dissertation.pdf > > Is there any good reason why we haven't done that? Is the constants > much worse than the ones implemented? Short answer: Yes. Longer Answer: You need to do lots of tricks to go to constant-rounds. The logarithmic solutions do not give (much) worse round complexity, but require notably fewer multiplications. The best one published that I know of is Tord's and mine from ICITS07. This is reasonable to implement (complexity-wise), but trust me, you don't want to :-) Regards, Tomas _______________________________________________ viff-devel mailing list (http://viff.dk/) [email protected] http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
