Score:0

Giving a continuous fractional (e.g. irrational) part of a secret to someone

in flag

In secret sharing schemes, we usually give rational fractional parts of a secret out. E.g. Alice gets 4/10ths of the secret, Bob gets 7/10ths, Charlie gets 5/10ths, David gets 1/10th, etc., and you need 10/10ths total to unlock the secret.

My question is: is there a scheme that allows for an irrational fraction of shares to be distributed to someone? E.g. Alice gets $\frac{1}{\pi}$ shares, Bob gets $\frac{2}{e}$ shares, etc.. I know that you can approximate these values with a rational fraction to arbitrary accuracy, but I want a scheme that can truly allot someone an irrational fraction of the secret.

My thought is that the answer might be similar to how binary 50-50 coin clips can be used to simulate any arbitrary probability $p$ (like $\frac{1}{\pi}$) exactly by considering the binary expansion of $p$

Score:0
ng flag

First, your coin-flipping analogy is simultaneously

  1. true, and
  2. not cryptographically relevant.

I'll briefly explain why by giving a formal statement of the coin-flipping result. Then I'll attempt to answer the secret sharing answer, which similarly has a relatively-straightforward (negative) answer.

Let $p\in[0,1]$ be arbitrary. Then, there exists a procedure to sample from a $\mathsf{Bern}(p)$ that uses $\leq H(p)+2$ binary coinflips in expectation, where $H(x)$ is the binary entropy function.

This is from appealing to "Knuth-Yao Sampling" (at least to get a bound of $H(p) + 2$). It is relatively hard to track down the initial paper on this, but iirc is in some of Knuth's collected works.

The most important part of the aforementioned theorem is the in expectation statement. While one can perfectly sample a $\mathsf{Bern}(p)$, one cannot perfectly sample from this distribution if there is some worst-case upper bound on the number of coinflips used. One can sample from an exceedingly good (rational) approximation to $\mathsf{Bern}(p)$, but you have mentioned this isn't what you want.

Does this matter? The answer is yes --- if the number of coinflips one uses is variable, then (in principle) it may open up a side-channel. Concretely, someone who can observe how many coinflips were used to sample the $\mathsf{Bern}(p)$ may uncover non-trivial information about the result of the $\mathsf{Bern}(p)$, which may break security. This is bad, and why people generally sample from a (high quality) approximation of some desired distribution, rather than exactly sample from some distribution.


As for secret sharing, the answer is no. The easiest reason is for a "boring" reason, although I will speculate a bit about more exciting reasons why the answer is likely "no". A secret sharing scheme is formally parameterized by two numbers

  1. $t$, the threshold for share reconstruction, and
  2. $n$, the total number of shares.

Sometimes there is a third parameter (for a certain notion of "approximate" secret sharing), but I won't cover this here. Anyway, a $(t,n)$-secret sharing scheme is parameterized by two natural number parameters $(t, n)$. Then, the fraction needed for reconstruction if $\frac{t}{n}$, which is (trivially) a rational threshold. As $t, n$ are always given as natural numbers, there is a significant obstacle to implementing your idea. This is somewhat boring though, as it just says that the current definition of secret sharing precludes your idea from working.

For a more exciting reason, real numbers do not mix well with computation. To see why, I'll briefly talk about encodings.

An encoding is a injective function $\phi : A\to B$.

We want encoding different things to lead to different encodings, i.e. $a\neq b\implies \phi(a)\neq\phi(b)$, which is what being "injective" means.

Anyway

Let $X$ be a finite set. Then for any other set $A$, any encoding $\phi : A\to X$ has $|A|\geq |X|$.

This is often called the "pidgeonhole principle". Anyway, this result can be seen as saying that if we want our encoding to be into some finite set $X$, we can only have finitely many "things to encode" $A$. This means that if, for some reason, we used irrational numbers $\alpha$ in our encoding, we could only consider finitely many distinct ones. When one makes this restriction, its not clear how things are different from the standard situation (finitely many pairs of natural numbers, i.e. rational numbers).

Why would we want $X$ to be finite? For the same reason why we can't exactly sample from $\mathsf{Bern}(p)$. If $X$ was infinite, then the lengths of each encoded thing $\varphi(x)$ would have to either be

  1. "infinite length" (i.e. cannot be used on an actual computer), or
  2. variable length.

But if the encoding is variable length, it leaks information about what was encoded, which is not suitable for cryptography.

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.