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

[Ian Goldberg]

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

def exp(base,expon):
    a = base
    mask = 1
    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
	mask <<= 1
    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
    mask = 1
    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
	mask <<= 1
    until (mask is larger than the maximum possible expon)
    return (res1, res2)


The idea is that the squarings are common between the exps, and just the
multiplications have to be done separately.

   - Ian