<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">Hi Claudio,<div><div><br><blockquote type="cite"><div>If you have time, there are a lot of things that need to be done here.<br>I already told Janus knows some of them, but said he can't work on<br>them. Here is something nice we should do to reduce the online time of<br>a factor (at least) 3:<br><br>In the protocol there are Pedersen commitemnts with three base element<br>g,h_1,h_2. To commit to x using randomness r_1,r_2 one computes<br>g^xh_1^r_1h_2^r_2. The protocol now does it in the following way:<br>1) compute a=g^x<br>2) compute b=h_1^r_1<br>3) compute c=h_2^r_2<br>4) compute d=a*b*c<br><br>The complexity is dominated by the three exponentiation, that one<br>implements using some ladder (square and multiply)<br><br>There is no need to do three exponentiation if one does something a bit smarter:<br>- precompute<br>g001=g^0h_1^0h_2^1<br>g010=g^0h_1^1h_2^0<br>...<br>g010=g^1h_1^1h_2^1<br><br>Now, to compute g^xh_1^r_1h_2^r_2 one does the ladder by looking<br>comtemporarily at the i-th bit of x, r_1, r_2. The complexity of this<br>is just one ladder, so virtually the same as just one of the above<br>exponentiation.<br><br>One can go further and precompute more elements, for instance<br>g000<br>...<br>g333<br>And now you look at 2 bits of x,r_1,r_2 for every square in the<br>square-and-multiply. This saves another factor 2 in time but you need<br>to store a bigger table of size 8^2.<br><br>What is the best strategy given our architecture? How many powers<br>should we precompute?<br></div></blockquote></div><div>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.</div><div>I don't know how the improvements you suggests maps to this?</div><br><div apple-content-edited="true"> <span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font-family: Nuri; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7px; line-height: normal; "><font class="Apple-style-span" face="Arial" size="2"><b><font class="Apple-style-span" color="#f05a23">____________________________________________________</font></b></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font-family: Nuri; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7px; line-height: normal; "><font class="Apple-style-span" face="Arial"><b><font class="Apple-style-span" size="2"><font class="Apple-style-span" color="#f05a23"><br></font></font></b></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font-family: Nuri; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7px; line-height: normal; "><font class="Apple-style-span" face="Arial"><b><font class="Apple-style-span" size="2"><font class="Apple-style-span" color="#f05a23">Janus Dam Nielsen</font></font></b></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font-family: Nuri; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7px; line-height: normal; min-height: 8px; "><font class="Apple-style-span" face="Arial"><b><font class="Apple-style-span" size="2"><br></font></b></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font-family: Nuri; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7px; line-height: normal; "><span class="Apple-style-span" style="font-family: Arial; font-size: 10px; font-weight: bold; "><font class="Apple-style-span" color="#5a5a5a">Research and Innovationspecialist, PhD.</font></span></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font-family: Nuri; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7px; line-height: normal; "><font class="Apple-style-span" face="Arial"><span class="Apple-style-span" style="font-family: Helvetica; "><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font-family: Nuri; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7px; line-height: normal; "><font class="Apple-style-span" face="Arial"><font class="Apple-style-span" size="2"><font class="Apple-style-span" color="#5a5a5a">CENTRE FOR IT-SECURITY</font></font></font></div></span></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font-family: Nuri; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7px; line-height: normal; "><font class="Apple-style-span" size="2"><font class="Apple-style-span" color="#5a5a5a"><br></font></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font-family: Nuri; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7px; line-height: normal; "><span class="Apple-style-span" style="font-family: Helvetica; "><font class="Apple-style-span" size="2"><font class="Apple-style-span" color="#5a5a5a">THE ALEXANDRA INSTITUTE LTD.</font></font><span class="Apple-tab-span" style="white-space: pre; "><font class="Apple-style-span" size="2"><font class="Apple-style-span" color="#5a5a5a"> </font></font></span></span></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font-family: Nuri; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7px; line-height: normal; min-height: 8px; "><font class="Apple-style-span" face="Arial"><span class="Apple-style-span" style="font-family: Helvetica; "><div><font class="Apple-style-span" size="2"><font class="Apple-style-span" color="#5a5a5a"><br></font></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font-family: Nuri; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7px; line-height: normal; "><span style="letter-spacing: 0.1px; "><font class="Apple-style-span" face="Arial"><font class="Apple-style-span" size="2"><font class="Apple-style-span" color="#5a5a5a">T</font></font></font><span class="Apple-tab-span" style="white-space: pre; "><font class="Apple-style-span" face="Arial"><font class="Apple-style-span" size="2"><font class="Apple-style-span" color="#5a5a5a"> </font></font></font></span><font class="Apple-style-span" face="Arial"><font class="Apple-style-span" size="2"><font class="Apple-style-span" color="#5a5a5a">+45 42 22 93 56</font></font></font></span></div><div><font class="Apple-style-span" color="#5A5A5A" face="Arial" size="2"><span class="Apple-style-span" style="font-size: 10px; ">E<span class="Apple-converted-space"> </span><span class="Apple-style-span" style="color: rgb(240, 90, 35); "><a href="mailto:janus.nielsen@alexandra.dk">janus.nielsen@alexandra.dk</a></span></span></font></div><div><span class="Apple-style-span" style="color: rgb(213, 61, 33); font-family: Arial; "><font class="Apple-style-span" size="2"><font class="Apple-style-span" color="#5a5a5a">W</font></font><span class="Apple-tab-span" style="white-space: pre; "><font class="Apple-style-span" size="2"> </font></span><font class="Apple-style-span" size="2"><font class="Apple-style-span" color="#f05a23">alexandra.dk</font></font></span></div></span></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font-family: Nuri; font-style: normal; font-variant: normal; font-weight: normal; font-size: 7px; line-height: normal; "><span class="Apple-style-span" style="font-family: Arial; font-weight: bold; "><font class="Apple-style-span" size="2"><font class="Apple-style-span" color="#f05a23">____________________________________________________</font></font></span></div></div></div></span></div></span></div></span></div></span></div></span></div></span></div></span></div></span></div></span> </div><br></div></body></html>