Join Log in
Score:1
Pedro Campones avatar Crypto

Can I use Additive Secret Sharing without Finite Fields without introducing an exploitable bias?

cm flag
Pedro Campones

As far as I know Additive Secret Sharing uses a finite field to generate its shares. The gist of the scheme is that the shares $A_{shares}$ = {$A_1, A_2, ..., A_n$} of a value $A$ on a finite field $N$ can be attained by:

$A\ mod\ N = \sum_{A_i \in A_{shares}} (A_i\ mod\ N)$

If all shares in $A_{shares}$ are positive and no finite field was used, an adversary could infer from any given share that the target $A$ is greater than the observed share. The use of the field stops the adversary from learning that.

Alternatively, I believe we could also use negative shares to compensate. If the shares can be negative, others could be greater than the original value and the adversary would learn nothing from them.

I tested this by sampling shares using a uniform distribution over a large range of positive and negative numbers. I found no bias in the results or clues about the value of $A$ from summing and averaging random shares, however I could be missing something.

Everywhere I searched the use of a finite field was used; however I don't understand if it is mandatory (and if so, why).

My question is: Is the use negative valued shares viable as an alternative to computing the Additive Secret Sharing scheme over a finite field, or does it introduce some exploitable bias and is not secure?

96
1 + 0
Score:2
poncho avatar Crypto
my flag
poncho

I tested this by sampling shares using a uniform distribution over a large range of positive and negative numbers.

Actually, unless you limit the number of possible values to a finite range, that's actually impossible.

It turns out to be impossible to do a uniform sampling over a set of size $\aleph_0$ (and that's the size of the set of integers); there will inevitably be some values that have a higher probability of being sampled than others. And, because of this nonuniformity, the adversary would obtain some information about the shared secret, given less than $n$ shares.

And, of course, if you do select from a finite range, you still leak information. For example, if the adversary has $n-1$ shares and they sum to -993, then (if the range you select is from $[-1000...1000]$, then he can deduce that the secret is no more than 7.

Now, if we work with a finite field (or group; you don't need a field for what you're doing), this is not an issue; we can select from a finite set uniformly.

+ 1
Pedro Campones avatar
cm flag
Pedro Campones
Thank you for your answer, with regards to the penultimate paragraph, we could have that the share values were selected from an interval between [-1000 ... 1000], however we could impose no restrictions on their sum. That is, I could sum two shares resulting in a value over 1000, even tough each is smaller than a thousand. As a result the "last" share that settles the difference between $A$ and the remaining shares could have a value outside the boundaries which could leak something. However even this could be mitigated by offloading some of its "excess" to the other shares.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.