Fields, Encodings, Semantics, and Probabilistic Results

While working with Cicada, it is important to keep in mind that the continuous values you are accustomed to working with are not the values being manipulated by secret shared operations. Our fixed-point arithmetic system maps a finite number of elements with fixed binary precision onto a finite number of elements that are a set of positive integers modulo some prime large enough to accommodate a range of interest. To see this directly, we will be looking in detail at instances of Field and FixedPoint.

Note

Protocol suites normally handle encoding and decoding values for you, so this information is for context only - you will almost never need to create instances of Field yourself.

In this example we are going to use an 8 bit field. The largest 8 bit prime is \(2^8-5=251\), which we will use as the order:

from cicada.arithmetic import Field

field = Field(order=251)
field

cicada.arithmetic.Field(order=251)

field.order

251

field.bits

8

To represent negative numbers, the field defines the posbound attribute, which is the threshold in the field above which values are interpreted as negative. It is equal to the floor of the order halved. In our example, posbound will be 125, meaning all field values in the range [126,250] will be interpreted as negative numbers. Thus, the field is split into two regions with the upper half dedicated to representing negative numbers while the lower half represents positive numbers:

field.posbound

125

Next, we’ll create our encoding, reserving 3 bits for fractional precision (i.e. the number of bits to the right of the radix), which is the precision argument provided to the initializer. Any fractional precision requiring more than 3 bits in the value to be encoded will be lost via the encoding process.

from cicada.encoding import FixedPoint

encoding = FixedPoint(precision=3)
encoding

cicada.encoding.FixedPoint(precision=3)

encoding.precision

3

When encoding and decoding fractional values, their bits are shifted left or right respectively, to map them to integers in the field. Conceptually, this can be thought of as multiplying or dividing by a scale value that is equal to \(2^{precision}\), or \(2^3=8\) in this case:

encoding._scale

8

Note

By convention in Python, objects whose name starts with an underscore (_scale) are private implementation details. You should never use them in your code, because they are subject to change at any time.

The mapping from fractional values to positive integers in the field have many follow-on implications. The first is that overflow and underflow can and will happen without any notice if code is not written with the field size in mind, since all operations occur obliviously. This may happen in unexpected situations and yield similarly unexpected results. For example, the addition of two positive values may yield a negative seemingly non-sensical result if their sum puts them into the upper half of the field which will later be decoded as a negative value. You will need to choose field sizes that are large enough to make this impossible (or at least unlikely).

Secondly, division is not directly possible in the context of the field since it is an integral field and no notion of values less than one exist in that context. We use field elements to represent fractional values, but these are semantics that have no significance to the field itself. We can get a stable and expected result for division by multiplying with an element’s multiplicative inverse in the context of the field, but this has the desired result if-and-only-if the intended dividend has the desired divisor as a factor. Otherwise the result will not yield any useful value for the external semantics. In general, we perform division via approximation, masking, and the like. The accuracy of the result from any division operation is heavily dependent on the precision available from the encoder with respect to the number of bits right of the radix.

Let’s try some examples using the field and encoding described above. For each of the following we will provide the example, work it out “by hand” and then show what it looks like in Cicada.

Encode and decode the value 3.25

• We multiply by the scale (in this case \(2^3\)) \(3.25\cdot8=26\). This is positive and less than the field order so there are no concerns here; we are done.

• To decode we check if the value (26) is greater than posbound (it isn’t) so we divide by the scale and return the value \(26/8=3.25\)

import numpy

value = numpy.array(3.25)
print(f"        Value: {value}")

encoded = encoding.encode(value, field)
print(f"Encoded Value: {encoded}")

decoded = encoding.decode(encoded, field)
print(f"Decoded Value: {decoded}")

        Value: 3.25
Encoded Value: 26
Decoded Value: 3.25

Encode and decode the value -3.25

• We multiply by the scale (in this case \(2^3\)) \(-3.25\cdot8=-26\). This is negative so we apply the modulus i.e., \(-26 \mod{251}=225\).

• To decode we check if the value (225) is greater than posbound (it is) so we compute the additive inverse of the difference between the modulus and the value i.e., \(-(251-225)=-26\), then divide by the scale and return the value \(-26/8=-3.25\).

value = numpy.array(-3.25)
print(f"        Value: {value}")

encoded = encoding.encode(value, field)
print(f"Encoded Value: {encoded}")

decoded = encoding.decode(encoded, field)
print(f"Decoded Value: {decoded}")

        Value: -3.25
Encoded Value: 225
Decoded Value: -3.25

Encode and decode the value 3.0625

• We multiply by the scale \(3.0625*8=24.5\). This is positive and less than the modulus, but not an integral value so we truncate to 24. We are done.

• To decode we check if the value (24) is greater than posbound (it isn’t) so we divide by the scale and return the value \(24/8=3\)

• Checking against the original value it is clear to see that we have lost the fractional part of the original (0.0625). This is due to the fact that in binary it is represented as 0.0001 and we have only 3 bits of binary precision available. Specifically, this happened at the point where we truncated 24.5 to 24, which is a necessary step to make sure every value is both consistent in semantics and compatible with representation in our integral field.

value = numpy.array(3.0625)
print(f"        Value: {value}")

encoded = encoding.encode(value, field)
print(f"Encoded Value: {encoded}")

decoded = encoding.decode(encoded, field)
print(f"Decoded Value: {decoded}")

        Value: 3.0625
Encoded Value: 24
Decoded Value: 3.0

Encode, add, and decode 15 and 2

• In a similar manner to the preceding, the encoding of 15 and 2 is 120 and 16 respectively.

• The sum of these is 136

• Decoding 136 yields -14.375, not the answer we were expecting as the sum of 15 and 2, due to overflow of the representable positive range in our semantic mapping onto the field. In practice much larger fields are used so that incidents such as this are far easier to avoid. For example, a 64 bit field is used in Cicada by default, and you are free to create larger fields, within practical limits.

value1 = numpy.array(15)
print(f"        Value1: {value1}")

value2 = numpy.array(2)
print(f"        Value2: {value2}")

encoded1 = encoding.encode(value1, field)
print(f"Encoded Value1: {encoded1}")

encoded2 = encoding.encode(value2, field)
print(f"Encoded Value2: {encoded2}")

encoded_sum = field.add(encoded1, encoded2)
print(f"   Encoded Sum: {encoded_sum}")

decoded_sum = encoding.decode(encoded_sum, field)
print(f"   Decoded Sum: {decoded_sum}")

        Value1: 15
        Value2: 2
Encoded Value1: 120
Encoded Value2: 16
   Encoded Sum: 136
   Decoded Sum: -14.375

Min and Max

Another area of concern with respect to such issues are the min and max functions. Given the semantic meaning we are mapping onto the field, problems may arise at the border. Our implementation of these functions is based on the following algebraic expressions:

\[min(x, y)=(x+y+abs(x-y))/2\]

\[max(x, y)=(x+y+abs(x-y))/2\]

This will behave as expected much of the time; however, if the difference between \(x\) and \(y\) wraps around an end of the field more than once then problems can occur. Given a field \(\mathbb{Z}_p\), as long as both operands are of the same sign or both satisfy the (in our opinion reasonable) constraint that \(abs(x)<p//4\), then the min and max functions should behave as anticipated.

Probabilistic Results

There are some functions in Cicada whose results will be off from the true answer by some relatively negligible margin. For example, when shifting a value to the right, the value to be shifted is masked with a random field element; an overflow in the least significant bits of the result is possible, depending on the random value.

In the following example, we shift the carefully chosen value 65536.6 one hundred times, and report the minimum, mean, and maximum of the resulting values. The expected value for the shifted result is 1. As you can see, the actual results vary between 1 and 1.0000152587890625, with the average result off by less than \(10^{-5}\).

import logging

from cicada.additive import AdditiveProtocolSuite
from cicada.communicator import SocketCommunicator
from cicada.logging import Logger

logging.basicConfig(level=logging.INFO)

def main(communicator):
    log = Logger(logging.getLogger(), communicator)
    protocol = AdditiveProtocolSuite(communicator)

    value = numpy.array(65536.5)
    value_share = protocol.share(src=0, secret=value, shape=value.shape)
    shifted = []
    for i in range(100):
        shifted_share = protocol.right_shift(value_share, bits=protocol.encoding.precision)
        shifted.append(protocol.reveal(shifted_share))
    shifted = numpy.array(shifted)

    log.info(f"Truncated value  min: {shifted.min()}", src=0)
    log.info(f"Truncated value mean: {shifted.mean()}", src=0)
    log.info(f"Truncated value  max: {shifted.max()}", src=0)

SocketCommunicator.run(world_size=3, fn=main);

INFO:root:Truncated value  min: 1.0
INFO:root:Truncated value mean: 1.0000070190429688
INFO:root:Truncated value  max: 1.0000152587890625