# [tor-dev] New paper by Goldberg, Stebila, and Ustaoglu with proposed circuit handshake

Ian Goldberg iang at cs.uwaterloo.ca
Thu May 12 00:33:09 UTC 2011

```On Wed, May 11, 2011 at 08:01:28PM -0400, Nick Mathewson wrote:
> On Wed, May 11, 2011 at 6:10 PM, Ian Goldberg <iang at cs.uwaterloo.ca> wrote:
>  [...]
> > Remember also that if you have non-black-box access to the
> > exponentiation routine, the server can compute X^y and X^b
> > simultaneously.  That will make a bigger difference in time, but is not
> > really relevant from a spec-level standpoint.
>
> Can you expand on how this would work?  I didn't ask the first time
> you told me this, on the theory that I could figure it out if I
> thought about it for long enough, but several days later I still don't
> have it.  All the ways I can think of are inefficient,
> non-constant-time, or both.

Use right-to-left exponentiation.  This is totally off the top of my

def exp(base,expon):
a = base
res = 1
# Invariant: a = base^mask
do:
# Be a little cleverer about the if if you
# care about constant-time; just save the output
# somewhere useless
if (expon & mask): # bitwise and
res = res*a
a *= a
until (mask is larger than the maximum possible expon)
return res

Then exp2(base, expon1, expon2) will be:

def exp2(base,expon1, expon2):
a = base
res1 = 1
res2 = 1
# Invariant: a = base^mask
do:
# Be a little cleverer about the if if you
# care about constant-time; just save the output
# somewhere useless
if (expon1 & mask): # bitwise and
res1 = res1*a
if (expon2 & mask): # bitwise and
res2 = res2*a
a *= a