Hello, I have an idea that has not been written down and implemented so I might as well write it to viff-devel. As you are trying to do a timing trial. It is constant round protocol for MPC comparison over Z_p, where p is an l-bit prime.
Using the assumptions that p is a Mersenne prime, and psaudo-random secret sharing the protocol uses 4,5 l multiplications. The comparison is [a] < [b], where [a] means that the value a is shared. The protocol builds on my earlier protocols, but the new thing is that I look at 2 and 2 bits at a time. What the protocol does is to start with the familiar trick of turning a comparison between two unknown values into a comparison between a known value and a bitwise shared random value. Based on the known value and the bitwise shared random value we look at 2 and 2 bits and compute a second value z, this value z has the last bit set to 0 or 1 based on whether the known value or the bitwise shared random value is bigger. We then use a highly effective method to extract the last bit of z as we can control which interval it is in. Assumtions: [a], [b] < p/4 (Means we are comparing [b]-[a] < p/2 instead) Psaudo-random secret sharing - makes the cost of generating random numbers negligible Mersenne primes - the cost of generating a random bitwise shared secret is only l + 2 multiplications when psaudo-random secret sharing is used Protocol: For comparison of [a] < [b] or [b] - [a] < p/2 1. Create two bitwise shared secret values [r]_B and [s]_B 2. Reveal c, where [c] = ([b] - [a]) + [r]_B The comparison now becomes a comparison between [r]_B and c, the individual bits of [r]_B and c are denoted [r_i] and c_i. 3. Compute [x] = \sum_i (1-[r_i]+c_i + \prod 2^(c_i xor [r_i])) but do it on 2 and 2-bit blocks at a time. 1-[r_i]+c_i becomes a table which is 1 if c_i <= r_i over the 2 bits, otherwise it is 0 e.g. if c_1 = 0, c_1 = 0, then the table should return 1 only if [r_0] and [r_1] is 0, in other words use 1 - ([r_0] + [r_1] - 2[r_0][r_1]). \prod 2^(c_i xor [r_i]) also becomes a table for (c_i xor [r_i]) where we look at 2 bits at a time. The table is 0 iff c_i = r_i for both bits. If c_i is not equal to r_i for both bits then the value should be 1. The nice thing about using 2 bits at a time is that we only need to compute [r_i]*[r_(i-1)] thereby using l/2 multiplications extra, but what we save is that the faun-in multiplication needed to compute the product now only becomes 2,5 l multiplications instead of 5 l. 4. For the final set and reveal x', where [x'] = [x] + 2^(l-1) - [s] and use my method for finding the lowest bit with only a constant number of multiplications. The trick is to use the highest bits of [s]. Since 2^(l-1) <= [x] < 2^(l-1) + 2^(l/2 + log(l)). Then [s] < [x] if the highest bit is not set, otherwise if the highest bit is set then [s] - 2^(l-1) < [x]. Therefore the lowest bit of [x] is equal to x'_0 xor [s_0] if the highest bit is not set. Otherwise it is equal to [s_0] xor (x' - 2^(l-1))_0, where (x' - 2^(l-1))_0 means the lowest bit of x' - 2^(l-1) when we are working over the field Z_p. Tord _______________________________________________ viff-devel mailing list (http://viff.dk/) [email protected] http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
