Clarification on `sfix` range behavior

[mhchia]

Based on the documentation Compiler.types.sfix and the discussion in GitHub Issue #512, the range of sfix is [-2**(k-f-1), 2**(k-f-1)).

I've tried the following scenarios:

1. When sfix is initialized with a value outside the range, a CompilerError: Value out of fixed-point range is raised as expected.

from Compiler.types import sfix

f = 16
k = 31
sfix.set_precision(f, k)
# This fails as expected, with the error: Compiler.exceptions.CompilerError: Value out of fixed-point range [-16384, 16384)
too_large_sfix = sfix(2 ** (k - f - 1))

2. When sfix is initialized with a value within the range, but the result exceeds the range after operations, no error is raised.

# Example 1:
largest_sfix = sfix(2 ** (k - f - 1) - 1)
# The value is outside the range, but no error occurs. Is this safe?
too_large = largest_sfix + sfix(1)

# Example 2:
# The value is out of the range, but no error occurs. Is this safe?
largest_sfix_computed = sfix(2) ** sfix(k - f - 1)

Is it the intended behavior that no error is raised when sfix contains a value larger than the range after operations? If so, is it still safe to use this out-of-range sfix, or should we implement checks to prevent this overflow from happening?

Thank you!

[mkskeller]

This is indeed the intended behavior. It would not make sense trying to predict the range of operations as even the product of two numbers within the standard range can be outside: 1000*1000. As to whether it's safe depends on the application and the protocol as there are a number of questions:

• In computation modulo a power of two, a standard technique is to "erase" bits by multiplying by a power of two. This hides whether a number was within the range in the first places, and the output of the operation can be expected to be within the range again, albeit not with the correct result.
• When using computation modulo an unknown prime, numbers outside the range violate the pre-condition for statistical masking that used for non-linear computation.
• In some application scenarios, one can make an informal argument: for example, if the training in deep learning converges, all values should stay within a clearly defined range. If not, this can easily be tested by a secure comparison on the loss without revealing any results. However, I'm not aware of a formal treatment of this issue.

Lastly, what do you mean by preventing overflow? If the result of an operation is outside the range, there is no way to prevent this as the correct result simply does not fit. The only solution I can think of is to compute a secret correctness bit from range checks akin to the NaN bit in the common floating-point representation. However, even for this you would need to increase the range to the point that it could fit the correct result of possible operations as the check would be incorrect if the result of an operation is outside the range in the first place.

[mhchia]

Thank you for the detailed explanation.

Lastly, what do you mean by preventing overflow?

Ah, I meant detecting whether sfix falls out of the range after an operation.

Just wanted to confirm further: if we know the inputs are within a certain range and we know the computation, is it a standard approach to configure f so that the range will be sufficient? For example, if the computation is x^2 and we expect every input x to be less than 1000, should we set f to something like 10 to make the range [-2^20, 2^20) so that results don't fall out of range?

[mkskeller]

Reducing f does increase the range but it does so at the cost of precision. With f=10, the smallest non-zero value is about 0.001 (1/1024), which might too much depending on the application. I've found that even simple deep learning applications require f=14 and more, but yours might be different. The other way of increasing the range is of course increasing k. MP-SPDZ is well-prepared for k up to 48, but you can further increase by following the instructions when you try higher values.

[mhchia]

Thanks for the answer. We're implementing statistics operations so it should be pretty similar to the case of ML I think. One more question:

MP-SPDZ is well-prepared for k up to 48

I set k to be 48 and it just works with the default bit length of sint modulo prime (-F). If I wanted to set k to be larger, would I need set a larger bit length?

[mkskeller]

The k parameter is independent of -F. If k becomes too large, you will get an error message telling you to recompile the virtual machine, for example after putting MOD = -DRING_SIZE=512 into CONFIG.mine.

[mhchia]

Ah I saw in sfix.set_precision

Generally, 2*k must be at most the integer length for rings and at most m-s-1 for computation modulo an m-bit prime and statistical security s (default 40).

Does this "the integer length for rings" refer to -R? And should we care about this only if we're using a MPC protocol that uses rings instead of fields?

What's the tradeoff if we're using a larger k?

[mkskeller]

Does this "the integer length for rings" refer to -R? And should we care about this only if we're using a MPC protocol that uses rings instead of fields?

Yes in both cases.

What's the tradeoff if we're using a larger k?

What do you mean by trade-off?

[mhchia]

What do you mean by trade-off?

I meant if we're using a larger k, would there be more computation overhead?

Generally, 2*k must be at most the integer length for rings and at most m-s-1 for computation modulo an m-bit prime and statistical security s (default 40).

Sorry, I think I'm a bit confused and wanted to clarify again. According to the description above:

• If I choose a protocol with a field (e.g., MASCOT) with the default bit length of 64 bits and statistical security of 40 bits, should I ensure k is at most m-s-1 (64-40-1=23)? This seems smaller than the default k=31. Did I misunderstand the bit length, or did I use the wrong default bit length?
• For a protocol with rings and a default bit length of 64 bits, should k be ≤ 64/2 = 32?

[mkskeller]

What do you mean by trade-off?

I meant if we're using a larger k, would there be more computation overhead?

Yes, that's usually the case even if the computation modulus doesn't change.

Generally, 2*k must be at most the integer length for rings and at most m-s-1 for computation modulo an m-bit prime and statistical security s (default 40).

Sorry, I think I'm a bit confused and wanted to clarify again. According to the description above:

* If I choose a protocol with a field (e.g., MASCOT) with the default bit length of 64 bits and statistical security of 40 bits, should I ensure k is at most m-s-1 (64-40-1=23)? This seems smaller than the default k=31. Did I misunderstand the bit length, or did I use the wrong default bit length?

The default bit length for primes is 128 to accommodate for the default parameters.

* For a protocol with rings and a default bit length of 64 bits, should k be ≤ 64/2 = 32?

Yes, if using division.

[mhchia]

Thank you for the clarification, I appreciate your help. I'll look into it more thoroughly.