[viff-devel] Floating point operation

[Martin Geisler]

"Amitabh Saxena" <amitabh123 at gmail.com> writes:

> Hi Martin,
>
>> > The functionality we need is the ability to work with floating
>> > point numbers.
>>
>> Do you mean local computations on such numbers or do you mean secret
>> shared floating point numbers?
>
> Say, if a and b are two floating point numbers that are secret-shared
> between members (e.g. additively), then we want to compute:
> c = a # b
> where # is one of { *, / , + , - }
>
> c should be computed to a desired degree of accuracy such that c is
> secret-shared between the members at the end of the protocol. its
> possible that one of {a, b} may be public but not always. It would be
> nice if this can be done locally without interaction.

Indeed, local computations are nice :-)

> Current approaches based on integers arithmetic to do floating point
> operations suffer from the problem of "bit-size expansion during
> intermediate computations" and I see problems in scaling up. I'd like
> some references that deal with this problem ('efficient MPC with
> rationals'). I found one related paper called "Cryptocomputing with
> rationals" published a while ago. I've not surveyed the very recent
> works yet.

I don't know that paper, I'll have to look at it at some point.

This did not lead to anything, but I don't think I have mentioned this
here before: One technique I looked at was to use continued fractions to
represent the floating point numbers. So 2.54 is represented by the
integer sequence "2 1 1 5 1 3", meaning

                       1
               2 + ---------
                           1
                   1 + ---------
                               1
                       1 + ---------
                                   1
                           5 + --------
                                     1
                               1 +  ---
                                     3

It turns out that one can do arithmetic with these sequences, and whats
more fun: given two input sequences, the first number in the result
sequence can be calculated before the entire input sequences have been
read. So "x = a # b" would be calculated in a streaming fashion, very
much like what VIFF already does.

Unfortunately the computation itself requires division and comparisons
between the numbers in the continued fraction sequence, so I abandoned
this approach. The algorithm for arithmetic with continued fractions is
called the Gosper algorithm, and the best reference I found is this one:

  http://perl.plover.com/yak/cftalk/

-- 
Martin Geisler

VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multi-Party Computation) to Python. See: http://viff.dk/.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 196 bytes
Desc: not available
URL: <http://lists.viff.dk/pipermail/viff-devel-viff.dk/attachments/20080915/2bcdaaae/attachment.pgp>