Re: Compiler transformations

T.Toft <at> cwi.nl writes:

> Also, as if-statements are quite far from what's really going on,
> (mis)using them will cause some overhead. I'm just worried about the
> efficiency loss if programmers think of them as ordinary
> if-statements. I'm not trying to get you down, it's just that MPC is
> resource-intensive enough as it is, we don't need to introduce
> additional overhead 

I agree that we must not introduce extra overhead. And by making it
easy for the programmer you could say that encourage that. But on the
other hand I think this is no different from any other programming
language: solving a program by doing X costs something, and the
programmer must have a rough mental model of what is going on to judge
if it was better to do Y.

To make the difference clear we could introduce two constructs: the
normal 'if' and a 'secure-if'. It would then be a type error to branch
on a secret shared variable in a 'if', but okay with 'secure-if'.

> One a sidenote: How about adding a conditional selection, "b ? x :
> y"? Basically it's a simple if-statement, but it's slightly more
> involved if you really want to shoot yourself in the foot.

You mean because people traditionally wont nest such selections very
deep within each other?

>> * Rebalacing of associative operations. A program like this
>>
>>     x = a * b * c * d * e * f * g * h
>>
>>   is executed using 8 rounds, but it can be executed with 3 rounds if
>>   the compiler evaluates things as
>>
>>     x = ((a * b) * (c * d)) * ((e * f) * (g * h))
>>
>>   that is, as a tree. This should work for any associative operator.
>
> How about the constant-round solution of [BB89]?

Hehe, Rune actually suggested this to me also, but didn't send it to
the list.

> This could be desirable at times, however, as it only works for
> invertible inputs it might get difficult. There is of course also an
> overhead involved, so it might not always be desired -- perhaps a
> compiler flag is in order...

I guess so, that would be the easiest solution. The compiler could
also try to judge this by itself if we feed it with some cost figures
for each protocol.

--

-- 
Martin Geisler