[viff-devel] OrlandiRuntime implementation

Janus Dam Nielsen janus.nielsen at alexandra.dk
Thu Nov 5 00:38:23 PST 2009


Hi Claudio,

> If you have time, there are a lot of things that need to be done here.
> I already told Janus knows some of them, but said he can't work on
> them. Here is something nice we should do to reduce the online time of
> a factor (at least) 3:
>
> In the protocol there are Pedersen commitemnts with three base element
> g,h_1,h_2. To commit to x using randomness r_1,r_2 one computes
> g^xh_1^r_1h_2^r_2. The protocol now does it in the following way:
> 1) compute a=g^x
> 2) compute b=h_1^r_1
> 3) compute c=h_2^r_2
> 4) compute d=a*b*c
>
> The complexity is dominated by the three exponentiation, that one
> implements using some ladder (square and multiply)
>
> There is no need to do three exponentiation if one does something a  
> bit smarter:
> - precompute
> g001=g^0h_1^0h_2^1
> g010=g^0h_1^1h_2^0
> ...
> g010=g^1h_1^1h_2^1
>
> Now, to compute g^xh_1^r_1h_2^r_2 one does the ladder by looking
> comtemporarily at the i-th bit of x, r_1, r_2. The complexity of this
> is just one ladder, so virtually the same as just one of the above
> exponentiation.
>
> One can go further and precompute more elements, for instance
> g000
> ...
> g333
> And now you look at 2 bits of x,r_1,r_2 for every square in the
> square-and-multiply. This saves another factor 2 in time but you need
> to store a bigger table of size 8^2.
>
> What is the best strategy given our architecture? How many powers
> should we precompute?

The computations are done on an elliptic curve, and thus the  
exponentiations are done using multiplications, and the  
multiplications are done using additions on points on the curve.
I don't know how the improvements you suggests maps to this?

____________________________________________________

Janus Dam Nielsen

Research and Innovationspecialist, PhD.
CENTRE FOR IT-SECURITY

THE ALEXANDRA INSTITUTE LTD.

T +45 42 22 93 56
E janus.nielsen at alexandra.dk
W alexandra.dk
____________________________________________________

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.viff.dk/pipermail/viff-devel-viff.dk/attachments/20091105/4b070359/attachment-0002.htm>


More information about the viff-devel mailing list