2
$\begingroup$

It looks like that only difference between two of them the variables. But it does not make sense for me and I could not find exact definition of arithmetic secret sharing scheme. I mean what exactly this is? (Most of you understand that I am really new in these stuff.) Thank you.

$\endgroup$

1 Answer 1

4
$\begingroup$

As far as I can tell, it seems that the term "arithmetic secret sharing" was coined by Cascudo, Cramer and Xing in their 2011 paper "The Torsion-Limit for Algebraic Function Fields and Its Application to Arithmetic Secret Sharing". Certainly, all the mentions of the term in the crypto literature that I could find with a few minutes of searching seem to cite this paper, and the term does not seem to appear in the literature (or, really, anywhere on the web) before 2011. So if you want an exact and authoritative definition of what it means, that paper seems like the obvious place to look.


Indeed, the introduction to the paper by Cascudo et al. cited above provides the following, unfortunately rather technical, definition:

An $(n, t, d, n - t)$-arithmetic secret sharing scheme (with uniformity) for $\mathbb F_q^k$ over $\mathbb F_q$ is an $\mathbb F_q$-linear secret sharing scheme where $k, n, t ≥ 1$, $d ≥ 2$, the secret is selected from $\mathbb F_q^k$ and each of the $n$ shares is an element of $\mathbb F_q$. Moreover, there is $t$-privacy (in addition, any $t$ shares are uniformly random in $\mathbb F_q^t$) and, if one considers the $d$-fold “component-wise” product of any $d$ sharings, then the $d$-fold component-wise product of the $d$ respective secrets is $(n - t)$-wise uniquely determined by it.

Almost the exact same definition, with the omission of only some conditions on the parameters $k$, $n$, $t$ and $d$, is also given directly in the abstract. In section 5 of the paper, the authors also give the following alternative (and unfortunately even more technical) definition:

DEFINITION 10 (ARITHMETIC SECRET SHARING SCHEME).
An $(n, t, d, r)$-arithmetic secret sharing scheme for $\mathbb F_q^k$ (over $\mathbb F_q$) is an $n$-code $C$ for $\mathbb F_q^k$ such that $t ≥ 1$, $d ≥ 2$, $C$ is $t$-disconnected, $C^{∗d}$ is in fact an $n$-code for $\mathbb F_q^k$, and $C^{∗d}$ is $r$-reconstructing. $C$ has uniformity if, in addition, it is $t$-uniform.


So, what exactly is an arithmetic secret sharing scheme, and what are they good for?

After quickly skimming the paper, I'm not yet 100% sure myself. Certainly, they seem to be information-theoretically secure threshold secret sharing schemes constructed using finite field arithmetic, much like Shamir's secret sharing scheme. Based on just my cursory reading of the paper, I'm not 100% sure whether Shamir's scheme itself falls within the scope of "arithmetic secret sharing", or whether it's merely possible to somehow construct arithmetic secret sharing schemes based on Shamir's scheme. In any case, "arithmetic secret sharing", in the general sense, seems to be a fairly broad umbrella term that encompasses a number of schemes independently introduced in earlier papers by other authors, as cited by Cascudo et al.

As for what they're good for, apparently, one major application is secure multi-party computation, and specifically secure multiplication. According to the paper's introduction, they can also be used for constructing error-tolerant secret sharing schemes, as well as for verifiable secret sharing.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.