Join Log in
Score:0
Hunger Learn avatar Crypto

How can I use a secret sharing scheme when the secret is not a number but a statement?

ua flag
Hunger Learn

I want to use a secret sharing scheme, where every player $i\in N$ has to share a pair of secrets $(l_i,\nu_{l_i})$, where $l_i$ is a unique code (positive integer) for every player, but $\nu_{l_i}$ is a secret like a statement. For example when player $i$ reports to the other players $\nu_{l_i}$ is like making a statement of the form "My name is $i$ and I know the information $\nu_i$."

My initial thoughts were that I need one polynomial function of degree $k-1$ for every player $i$ to share the code $l_i$ with every other player $j=-i$, but knowing l_i must imply that another player will also learn $\nu_{l_i}$ after reconstruction the code $l_i$. How could I make this work with secret sharing?

101
0 + 0
Hunger Learn avatar
ua flag
Hunger Learn
Well one idea although I do not not how could this be apploed is to define a cipher mathematically that can translate every word of your statement to a number. So then you will have a splitting code and a codified message too I think.
0
Reply
ar flag
Ilmari Karonen
Closely related: [Shamir's secret sharing for vectors](https://crypto.stackexchange.com/questions/70024/shamirs-secret-sharing-for-vectors)
0
Reply
Score:1
avatar Crypto
ar flag
Ilmari Karonen

The simplest solution is to:

  1. encode the secret phrase into one or more numbers, and
  2. then share each of those numbers using a secret sharing scheme.

In fact, if your secret phrase is stored on a computer, the first part is already taken care of: computers typically store data, including text, as sequences of 8-bit bytes — i.e. numbers from 0 to 255.

As long as you don't need to generate more than 255 shares of any secret, you can just treat those bytes as elements of GF(28) and share them using Shamir's secret sharing scheme (or any other similar secret sharing scheme you prefer).

You can even safely use the same share ID (i.e. $x$ coordinate) for each byte of the shared phrase, so that your shares will only be one byte longer than the secret phrase. (They'll be random binary data, though, so you may need to e.g. Base64 encode them for transport as text.) And Shamir's secret sharing over GF(28) can be made very fast, since all the math is done using just single bytes. For these reasons, quite a few implementations of Shamir's secret sharing do just this.

The byte-by-byte sharing method described above does have a few disadvantages:

  1. It reveals the byte length of the secret phrase. If this is an issue, the phrase should be somehow reversibly padded to a fixed length before sharing.

  2. For mathematical reasons (i.e. because each share needs a distinct non-zero field element as its $x$ coordinate) it cannot be used to generate more that 255 distinct shares for each secret. If this is not enough, you can e.g. split the share into pairs of bytes and share it using Shamir's scheme over GF(216) for up to 65535 shares, or split it into groups of four bytes and share them over GF(232) for up to about 4 million shares.

(Of course you could use even bigger field sizes, or even sizes that are not powers of 2, if you wanted to. But there's generally little reason to do so, at least not when sharing binary data, which all data stored on a binary computer ultimately is.)

Of course, if you don't insist of perfect information-theoretic security, another practical option is to generate a random key (of e.g. 128 or 256 bits) for a symmetric encryption scheme such as AES,* encrypt your secret using the key, and then share the key.

This can be advantageous if your actual secret is very long (say, a video file) and if you can publish the encrypted secret on some shared channel, since then the only thing you'll need to send separately to each shareholder is their share of the key (which will only be a few bytes long).

*) Using a secure mode of operation, of course. I'd generally recommend an authenticated encryption mode like SIV, but even a classic non-authenticated mode like CBC or CTR may be sufficient for your needs. Just don't use ECB.

0 + 0
Hunger Learn avatar
ua flag
Hunger Learn
so you mean that this statement which has 10 words, we could have 10 spaces for every secret say $S=\times_{i=1}S_i^{10}$ and use 10 polynomial functions for each one of them?
0
Reply
Hunger Learn avatar
ua flag
Hunger Learn
well I have no idea how to model this mathematically...the authentication scheme and how to define the mode of operations....I need the maths structure....
0
Reply
ar flag
Ilmari Karonen
It would help to know which of the two steps in my answer above you're having trouble with. They're completely separate steps: step 1 involves no secret sharing (and thus no polynomials etc.), while step 2 involves only one secret number (or, rather, you apply it separately to each of the numbers you obtained in step 1). It's probably simpler than you think it is.
0
Reply
Score:0
Hunger Learn avatar Crypto
ua flag
Hunger Learn

Solution $1$: Every word is translated into a number with the help of a cipher. Say that $C$ is such a mapping that takes a word and translate it to a number, namely $C:A\to\mathbb{N}$, where $A$ is an alphabet. In your statement "My name is $i$ and I know the information $\nu_i$." You have $10$ words namely 10 codes $x_1,..,x_{10}$. Then every player could send 10 different shares $(a_{j,k},b_{j,k})_{k=1}^{10}$ to every other player $j$ where each pair is one point of a specific polynomial function of degree $t-1$, $(f_{i,k})_{k=1}^{10}$. If the players collaborate and share their parts of every polynomial function they will reconstruct the $10$ functions of $i$. Then the will learn the $10$ numbers that can reconstruct the statement. Use a decryption scheme for every one of the $10$ numbers and you will take what you want.

Solution $2$: Another idea that has meaning from a mathematical perspective. Say that $E_i(k_i,\nu_{l_i})=l_i$ is the encryption function such that

$$E_i:K_i\times N_{L_i}\to L_i$$

and every pair $(k_i,l_i)$ is associated with only one $\nu_{l_i}$, namely bijective $E_i$. Furthermore, the decryption function is $$D_i:K_i\times L_i\to N_{L_i}$$

and hence $D(k_i,l_i)=D(k_i,E_i(k_i,\nu_{l_i}))=\nu_{l_i}$

For the code you can use a simple application of the Shamir scheme as you said. First the players will learn $(x_i,y_i)$ that are points of the polynomial function of degree $t-1$ and the code $k_i$, that is also a key and hence after they collaborate to compute the secret $l_i$ this $l_i$ is useful to decrypt $\nu_{l_i}$. That is how you could calculate the one from the other. In the part that you say, that $l_i$ is a code and $\nu_{l_i}$ a statement, note that every word of the statement is translated into this code. Hence by learning $l_i$, this means that the whole statement is decrypted.

0 + 0
Hunger Learn avatar
ua flag
Hunger Learn
I do not know if anything of what I am saying makes sense. But, I think there is a logical explanation in my thoughts. Please, any criticism is very welcome. It will help me as well to understand if I am right or wrong.
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.