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