Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 1 down vote favorite

This is a trivial question, but I had to ask:

since each generated share in a Shamir's secret sharing scheme initially consists of a pair of values (representing the coordinates of a point on the plane), how do I reduce the two values to one, so that the share that I eventually hand out will consist of only one value?

The way this is normally done is:

Share #1: (1, 65428) Share #2: (2, 935747) Share #3: (3, 3524)

But this does not seem very satisfactory to me, because the share still consists of two values, as the share's number (which could be seen as a metadata) is still one of two values. This way of doing is also inconvenient in the sense that if a share is marked as Share #7, this normally implies that there are at least 7 shares, possibly more.

The solution I am looking for is a way to have shares with totally random x values, such as (324,4634634) (23, 945) (8, 45634) (944, 356345) and no serial number on a share (e.g. Share #8), so that by intercepting one share, and adversary cannot even try to guess how many shares there are. Of course, the share generating mechanism is exactly the same. The only difference is that the x values, instead of being 1, 2, 3, 4... are random numbers.

So, now the question is: assuming I decide to use random x numbers, how can I conflate the two values of each share into one value, also assuming that no external (metadata) markings of the share (e.g. share #3) will be used?

share|improve this question
Concatenation; perhaps with a separator, or fixed-width fields. – fgrieu Mar 12 at 14:10
I had already thought of concatenation, but it does not seem a very elegant solution. – Penn Mar 12 at 14:33
If shares are bound to some ID, you could consider using a hash function to map that ID to an x-value. It is fine for the x-values to be predictable, so there's no problem there, and the hash's collision resistance should guarantee that you choose distinct x-values. The holder of the share can then simply recompute x. – Maeher Mar 12 at 15:58
Shamir's secret-sharing scheme does not need to have share #$3$ be the value of that polynomial $f(x)$ at $x=3$; the $n$ share-values are the values of $f(x)$ at $x_1, x_2, \ldots, x_n$ where the $x_i$ are $n$ distinct nonzero elements of the field. One does not have to choose $x_i = i$. But, of course, what each share holder is given is $(x_i, f(x_i))$, or, possibly, $(g(x_i), f(x_i))$ where $g(x_i)$ is the result of encrypting $x_i$ via an encryption scheme known to the trusted authority who will reconstruct the secret. – Dilip Sarwate Mar 12 at 23:13

1 Answer

up vote 2 down vote accepted

Well, Shamir Secret Sharing is done using a field $GF(p^k)$, for some prime $p$ and some integer $k$. A share consists of two integers $(x, y)$, where $0 \le x, y < p^k$.

So, the obvious way to express a single share $(x, y)$ as a single value would be to use the value $x p^k + y$ (using integer arithmetic, not field operations); each potential share would map to a distinct value, and during reconstruction, each value can easily be mapped by to the $(x, y)$ format.

Yes, this is just another way of doing concatination; you might find this somewhat more elegant.

share|improve this answer
Thanks, Poncho. This is what I was looking for. One more thing: you said that by using xp^k+y each share would map to a distinct value. So, how would I get back the two values of x and y from the 'unified' share? That is, what is the inverse operation? – Penn Mar 12 at 16:01
@Penn: the inverse operation mapping $value = xp^k + y$ back to $(x,y)$ would be $x = value / p^k$ (round down), and $y = value \bmod p^k$. – poncho Mar 12 at 16:05
Thanks again, Poncho! – Penn Mar 12 at 16:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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