Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:18:59 ADT
burt rosenberg (burt@passaic.cs.miami.edu)
Wed, 24 Jun 1998 15:33:42 -0400 (EDT)
>
> >
> > given y, compute y^x (n) by selecting a random splitting
> > of x as x_1 + x_2 = x (or x + k phi(n) if x is uncomfortably
> > small) and use the property:
> >
> > y^x = y^(x_1+x_2) = y^(x_1) y^(x_2) (n)
> >
>
> A simpler solution is to fill the time so a bit set or clear in x doesn't
> change the overall timing.
>
> Dr. mike
>
this solution, to fill time, is most likely faster, and possibly
simpler, but it doesn't fully cover the calculation's tracks.
i do not see how to prove that no information is then leaked
through timing analysis. this will make the timing data more
subtle, perhaps to the point of uselessness, but perhaps not.
kocher provides the thought experiment of a certain squaring
that takes a grotesquely long time. by chosing y correctly,
you can tickle this squaring and check that the i-th bit of x is 0.
however, we can take this thought experiment one step further
and assume that for a certain x all y^x's take a longer time
on average than other x's. then kocher's proposed solution,
premultiply y by a random number before exponentiation, also fails.
on the other hand, randomly splitting x will not disclose information
_unless_ y^x' and y^{x-x'} somehow correlate, for randomly drawn x'.
that is, they are not like y^x' and y^x'' drawn independently at random.
assuming independence, a proof of no information leakage might be possible.
do y_x' and y^{x-x'} act as independent algorithms, for random x'?
gee ...
-burt
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:18:59 ADT