tag:blogger.com,1999:blog-3722233.post4582047124333596102..comments2020-05-27T23:17:32.309-04:00Comments on Computational Complexity: Is Secret sharing REALLY REALLY REALLY used?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-3722233.post-5624913166787477812018-12-02T20:48:20.934-05:002018-12-02T20:48:20.934-05:00"Do you think Quantum computers that factor w..."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?"<br /><br />Yes.<br /><br />https://i.imgur.com/ytsjUPZ.jpgDaniel Aponnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21671998646415023502018-11-29T17:14:45.874-05:002018-11-29T17:14:45.874-05:00I think we can define RRR as ubiquitous use. In ...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.<br /><br />You 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<br /><br />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.<br /><br />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.<br /><br />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.Vladhttps://www.blogger.com/profile/02837523049357528241noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57911236964664675122018-11-28T15:35:28.158-05:002018-11-28T15:35:28.158-05:00I will agree and point out that the book
THE JOY O...I will agree and point out that the book<br />THE JOY OF FACTORING by Wagstaff <br />is a good place to learn some factoring algorithms<br />that work well in practice.<br /><br />I will disagree and point out that there are goldilocks<br />values of n where<br />a) What Alice and Bob want to do with number of length n<br />is EASY<br />b) Factoring numbers of length n is still HARD.<br /><br />GASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50684900357166568192018-11-28T14:51:15.585-05:002018-11-28T14:51:15.585-05:00I just saw your reply, Bill.
Let me clarify that...I just saw your reply, Bill. <br /><br />Let 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. <br /><br /><br />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).<br /><br />2. It's quantum polynomial time, and I have no clue whether the entire class is deterministic polynomial time. <br /><br />3. Its decision version is in UP, which again I don't know whether this entire class of problems lies.<br /><br />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.<br /><br />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.<br /><br />6. (Also related to #4 above): There are quite successful heuristics. <br /><br /><br />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.<br /><br />-- periklisPeriklishttps://www.blogger.com/profile/01566397324053760799noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67894968942774891912018-11-26T00:42:08.073-05:002018-11-26T00:42:08.073-05:00I"m surprised you don't teach RSA since
1...I"m surprised you don't teach RSA since<br />1) its being used now, and<br />2) if you teach lattice-based crypto it would be good for them to<br />know what it was an improvement of.<br /><br />Do you think Quantum computers that factor will become a reality or do you think that hard number theory and parallelism<br />will make factoring easy? <br /><br />bill g.GASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4776546783900130942018-11-25T11:09:19.953-05:002018-11-25T11:09:19.953-05:00Which wallets do this? Which wallets do this? Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44425906542958139302018-11-24T18:07:49.440-05:002018-11-24T18:07:49.440-05:00I don’t know if secret sharing is used in practice...I 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.Periklishttps://www.blogger.com/profile/15407906187375170002noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59373011288628977802018-11-23T07:56:43.820-05:002018-11-23T07:56:43.820-05:00Many cloud storage solutions use SSS internally to...Many 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/CleversafeMahdihttps://www.blogger.com/profile/12382401759237060260noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34013030222766631592018-11-21T17:24:24.142-05:002018-11-21T17:24:24.142-05:00Transactions themselves do not use Shamir secret s...Transactions themselves do not use Shamir secret sharing. It is the wallets that use Shamir to split their associated private keys.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75131006568936734092018-11-21T07:32:45.111-05:002018-11-21T07:32:45.111-05:00Most k-of-n outputs in bitcoin use the OP_CHECKMUL...Most k-of-n outputs in bitcoin use the OP_CHECKMULTISIG opcode as in this redeemScript for a 3 out of 5 output:<br />"3 022e4e71af627ea0e1635ffc6c2402093bf3fe9ef2cf8e5692771cd2b450545b22 02956c209d6a661f974c0ebaeb8e38a1b8fb272e53dac757a203379c205e813f76 0325635303e0f9755a5b4501b81be0d03fea7294d92625f7a07bb9991f213aa98c 03a69f8eb83003240fa19321a927887cfd0c67753e292cb155163fdc7610a9c193 03e16d2284518e15a51039ea677033c5038fcb42b033221e640dc236a6b59f6488 5 OP_CHECKMULTISIG"<br /><br />Can you point to a specific bitcoin transaction that used Shamir Secret Sharing?tromphttps://www.blogger.com/profile/16161842727664839561noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16712072069831582102018-11-20T15:50:34.374-05:002018-11-20T15:50:34.374-05:00The linux command line tool gfshare uses it. And ...The linux command line tool gfshare uses it. And Hashicorp's Vault uses it as well: https://www.vaultproject.io/docs/concepts/seal.htmlJared Corduannoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25887912090017670032018-11-20T01:51:20.100-05:002018-11-20T01:51:20.100-05:00Almost every bitcoin wallet uses Shamir sharing fo...Almost every bitcoin wallet uses Shamir sharing for splitting the secret key (this functionality is "ambiguously" called multisignature).Anonymousnoreply@blogger.com