0
$\begingroup$

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$

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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