[viff-devel] Mystery of the quadratic running time solved?

[Mikkel Krøigård]

Citat af Ivan Bjerre Damgård <ivan at cs.au.dk>:

> Very interesting!
>
> So if things are as they seem here, the explanation for the strange  
> behavior would be that the precomputing phase, being more involved  
> than the online phase, is punished by Twisted (when unhacked). And  
> this is of course not included in the analysis in the paper.

Yes. Very interesting, and nice work Marcel. Indeed we did not know  
(well I didn't) back then that the data was not sent immediately by  
Twisted, and I was starting to think yesterday whether the hack would  
make a difference. Lucky for us, it apparently does :)

> regards, Ivan
>
> Quoting Marcel Keller <mkeller at cs.au.dk>:
>
>> Hello friends of VIFF,
>>
>> I've now run the benchmark of actively secure multiplications with  
>> hyperinvertible matrices together with my hack. Here are my results  
>> (column 1 and 2) compared to the results in the paper "Asynchronous  
>> Multiparty Computation: Theory and Implementation" (column 3 and 4):
>>
>> (n,t)	online	preprocessing	online	preprocessing
>> (4,1)	5	18		4	20
>> (7,2)	7	30		6	42
>> (10,3)	9	43		8	82
>> (13,4)	12	56		10	136
>>
>> The preprocessing time now seems to be linear whereas the online  
>> time is slightly increased. I didn't benchmark bigger thresholds  
>> because it's difficult enough find 13 camels which are not hard  
>> ridden yet. I think I  also fixed the increased online time, but I  
>> couldn't test the fix thoroughly because the active adversaries  
>> continuously change the corrupted camels.
>>
>> Again, there are two patches in the attachement, and again, the  
>> patch for VIFF is against the current tip of my repository:  
>> http://hg.viff.dk/mkeller/rev/e2759515f57f
>>
>> Best regards,
>> Marcel
>>
>>
>
> _______________________________________________
> viff-devel mailing list (http://viff.dk/)
> viff-devel at viff.dk
> http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
>