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

[Ivan Bjerre Damgård]

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.

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
>
>