Since I am teaching Cryptography this semester I am teaching things people REALLY REALLY REALLY (RRR) use. For some topics this is RRR true, like RSA (that it is used to transmit a private key that is then used is FINE.)
I was wondering if Information-Theoretic Secret Sharing is RRR used. I am asking non-cynically and non-rhetorically. So I want to be taken seriously AND literally.
I Googled and got some answers but could not verify them.
1) At this site: here we can read
Every modern HSM (hardware secure module, for crypto applications) uses Shamir's secret sharing.
I tried to verify this but was unable to.
I also read
The DNSSEC root key is 5-out-of-7 shared see, e.g., here or here
The link leads to a story about how there are 7 people and if any 5 get together they can shut down the internet. The story does not say they use secret sharing.
2) Threshold cryptography (see here) would seem to use it, but is Threshold crypto used? There is a startup who is trying to use it: see here. I don't count that as RRR since they don't have customers yet. Not sure what the threshold is for whether I count it.
3) Some papers mention that secret sharing COULD be used if you want to make sure nuclear missiles are not launched unless x out of y people say so. But I doubt it really is used. If so this might be very hard to verify.
4) Shamir's secret sharing scheme is pretty simple and does not have big constants so if there is a need it really could be used. But is there a need?
I am not quite sure what I count as proof that someone RRR using it. A random person at a random website just saying that HSM uses it does not seem convincing. A Wikipedia article saying its being used I would find convincing (should I? Until recently Wikipedia couldn't even get my year of birth straight, see here)
If some companies website said they used Shamir's Secret Sharing I would believe that-- but a companies website is not likely to say that. NOT for reasons of company secrets but because its not what most customers go to the website to find.
SO- if someone RRR knows that Secret Sharing is RRR being used then please leave a comment.
Almost every bitcoin wallet uses Shamir sharing for splitting the secret key (this functionality is "ambiguously" called multisignature).
ReplyDeleteMost k-of-n outputs in bitcoin use the OP_CHECKMULTISIG opcode as in this redeemScript for a 3 out of 5 output:
Delete"3 022e4e71af627ea0e1635ffc6c2402093bf3fe9ef2cf8e5692771cd2b450545b22 02956c209d6a661f974c0ebaeb8e38a1b8fb272e53dac757a203379c205e813f76 0325635303e0f9755a5b4501b81be0d03fea7294d92625f7a07bb9991f213aa98c 03a69f8eb83003240fa19321a927887cfd0c67753e292cb155163fdc7610a9c193 03e16d2284518e15a51039ea677033c5038fcb42b033221e640dc236a6b59f6488 5 OP_CHECKMULTISIG"
Can you point to a specific bitcoin transaction that used Shamir Secret Sharing?
Transactions themselves do not use Shamir secret sharing. It is the wallets that use Shamir to split their associated private keys.
DeleteWhich wallets do this?
DeleteThe linux command line tool gfshare uses it. And Hashicorp's Vault uses it as well: https://www.vaultproject.io/docs/concepts/seal.html
ReplyDeleteMany cloud storage solutions use SSS internally to protect data. For example, I think this company (which was bought by IBM) uses the technology: https://en.wikipedia.org/wiki/Cleversafe
ReplyDeleteI don’t know if secret sharing is used in practice. I think Vlad Koleshnikov would be the appropriate authority on this (I did a reduction). However, in my crypto class I don’t teach RSA, because I want students to know things that may continue to be believed as cryptographically secure in the future.
ReplyDeleteI"m surprised you don't teach RSA since
Delete1) its being used now, and
2) if you teach lattice-based crypto it would be good for them to
know what it was an improvement of.
Do you think Quantum computers that factor will become a reality or do you think that hard number theory and parallelism
will make factoring easy?
bill g.
I just saw your reply, Bill.
DeleteLet me clarify that my comment was about Factoring. It's because I don't think there is a reason to believe otherwise. On the contrary, there are plenty of things that may make Factoring easier than what is currently commonly conjectured.
1. It's a natural problem in the intersection of P and NP (and we have a prior regarding the fate of other natural problems with the same property).
2. It's quantum polynomial time, and I have no clue whether the entire class is deterministic polynomial time.
3. Its decision version is in UP, which again I don't know whether this entire class of problems lies.
4. I don't know how to ask a meaningful question about it in a black-box (oracle) setting. I mean, it's hard for me to think about the computation of algorithms for Factoring in a structured way. I suspect that more profound knowledge of the number-theoretic properties of the integers may change our view of the computational complexity of Factoring.
5. Above 1--4 is true for its worst case. For crypto the average case is of relevance. Even if we identify any kind of worst-case hardness in the problem, I don't know what will this say about it's average-case version.
6. (Also related to #4 above): There are quite successful heuristics.
Beliefs are about psychology. Collecting reasons such as the above ones (even though they are in a sense dependent to each other) makes the cryptographic hardness of the problem less believable.
-- periklis
I will agree and point out that the book
DeleteTHE JOY OF FACTORING by Wagstaff
is a good place to learn some factoring algorithms
that work well in practice.
I will disagree and point out that there are goldilocks
values of n where
a) What Alice and Bob want to do with number of length n
is EASY
b) Factoring numbers of length n is still HARD.
I think we can define RRR as ubiquitous use. In this case I'd say RRR is only AES, HMAC, RSA, DH, DSA, etc – the algorithms used to secure communications (web, VPN, etc.). In other words, whatever is inside TLS and IPSec.
ReplyDeleteYou can discuss whether something like secret sharing, which is probably used in protecting Verisign root keys is RRR. It is not used per se almost at all (the root key is inactive in daily operations and exists to handle emergencies to do with revoking a compromised lower-level key etc. As such, the secret sharing/reconstruction is not really run). However, the fact that secret sharing is employed greatly increases our confidence in security of the web. Ergo, with every web transaction, we benefit from it. I am not sure whether DNSSEC is already gained ubiquity: you can achieve good security with just end-user authentication. I think DNSSEC helps with DoS-like attacks. I followed Bill's links, but did not find rock-solid evidence that DNSSEC keys are secret-shared. I am certain they are; otherwise some of the manipulations they discuss don’t make sense. Bruce Schneier agrees: https://www.schneier.com/blog/archives/2010/07/dnssec_root_key.html
Threshold crypto became popularized due to blockchain. I believe it is widely used, e.g. to distribute your signing key to protect against loss AND theft.
And then there are newfangled fancy crypto: Secure computation (MPC), zero-knowledge proofs (ZKP), which are not yet big, but I believe are growing. One very interesting application I worked on (with Jon Katz and his former student Xiao Wang) is a post-quantum-secure signature scheme, built from MPC, which in turn uses secret-sharing.
So, in sum, I would say secret sharing is already RRR, and is going to be even more so, as crypto which goes beyond channel security gains prominence.
"Do you think Quantum computers that factor will become a reality or do you think that hard number theory and parallelism will make factoring easy?"
ReplyDeleteYes.
https://i.imgur.com/ytsjUPZ.jpg
check out fragmentix.com - they use Shamir perfect secret sharing to store data - not "only" keys
ReplyDelete