Re: [cryptography] Grover's Algo Beaten?
On Sun, Jul 28, 2013 at 3:49 PM, Russell Leidich pke...@gmail.com wrote: Thanks, Noon. It's good to know that some searches are still hard in the sense of square root as opposed to log of classical. So based on his actual claims in the papers you cited, when the EE Times article says: And he claims the process worked so well that even the largest data set of all -- every bit in the universe, which he describes in his book *Programming the Universe* http://www.amazon.com/books/dp/1400033861, would only require a quantum computer with 300 q-bits to query in real-time. I don't know exactly what they mean by this. I guess he's just saying something like suppose I know that the number of bits of information the universe is less than some number K, then I only need log2(K) qubits to represent that many bits of information in a quantum computer. I'm not sure it's particularly interesting. ...they don't mean query in the literal sense of a text search for an exact match of Joe Smith. What they really mean is more like: given a database of billions of car photos (support vectors), then look at my new car photo, and tell me what brand it is. In short, a vector classifier. In the recent machine learning paper[1], they describe an algorithm that does supervised machine learning (i.e. deciding whether a thing is either truck-like or car-like, two choices for simplicity) in O(log (N M)) on a quantum computer, instead of O(poly (N M)) on a classical computer, where M is the number of samples from each of the clusters you're trying to assign to (say M truck-like things, and M car-like things), and N is the dimension of vector you're trying to assign (i.e. a thing that is either truck-like or car-like). Nevertheless, his putative exponential speedup over classical methods would be astounding, if it could be implemented, even if it really doesn't relate to Grover. It's a cool result, no doubt. But you'll note that the classical algorithm is already in P. The trouble is to find a quantum algorithm that solves a problem that is hard classically, but easy quantumly. More technically, it would be really astounding if we could separate BPP[2] and BQP[3]. -- Noon [1] http://arxiv.org/abs/1307.0411 [2] http://en.wikipedia.org/wiki/BPP_%28complexity%29 [3] http://en.wikipedia.org/wiki/BQP ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Grover's Algo Beaten?
On Sun, Jul 28, 2013 at 1:29 PM, Russell Leidich pke...@gmail.com wrote: Is this to be taken seriously... Massachusetts Institute of Technology professor Seth Lloyd claims to have developed a quantum search algo which can search 2^N (presumably unsorted) records in O(N) time. (This is the subtext of this mundane article about VC funding for search engines.) No, he doesn't make any such claim (even if your claim was well-formed...) The papers on machine learning can be found here: - http://arxiv.org/abs/1307.0411 - http://arxiv.org/abs/1307.0471 Grover's algorithm is known to be optimal: - http://arxiv.org/abs/quant-ph/9711070 - http://arxiv.org/abs/quant-ph/9605034 -- Noon http://www.eetimes.com/document.asp?doc_id=1319059 http://www.amazon.com/books/dp/1400033861 Reading between the lines, it sounds like the input is a binary pattern, and the output is a record number where said pattern is found, assuming that it exists in the database. (If it exists in multiple records, then each of those matches will be returned with essentially equal probability.) To the quantum computing notice, this invention is unsurprising. After all, N qubits in superposition assume 2^N states across multiverses, which obviously means that shortly after the computer starts up, it will already have found the desired record if it exists. But methinks this is all wrong. Grover's algo can only search 2^N unsorted records in O(2^(0.5N)) time. If I'm not mistaken, this derives from the difficulty of amplifying the correct result, in the presence of large numbers of near matches. For its part, DWave's operating manual goes into detail about this issue, involving Maxwell-Boltzmann energy distributions, providing practical evidence of this severe acceleration impediment. So it sounds like Lloyd is claiming that he's found a way to amplify the correct record with 100% probability -- in other words, to exploit quantum mechanics on a quantum system to mimic classical behavior. If he's right, then that would appear to be evidence that quantum computers can provide exponential, as opposed to merely square, acceleration of at least this one algo, if not others. I wish I could procure a copy of his book, but I'm geographically challenged. So nevermind his apparent egomaniacism. Is he right? Is EE Times just confused about his supposed invention? Aside: There's another subtle implication here, which is that multiverse density is for all practical purposes, infinite. In other words, you can in fact superimpose 2^N multiverse bubbles into the physical space occupied by N qubits, even if N is big enough to subsume all Landauer limit bit flips that could ever have occurred with all the energy in the universe (very roughly, N=400). This is a cornerstone of quantum theory which appears very difficult to test, absent a classically verifiable result like a Shor's factorization. There's something unsettling about the assumption that information density can be infinite despite finite systemic energy, when even inside black holes, that's not allowed (says Mr. Hawking). Maybe the maximum spatial density of multiverses is just really big, so that experiments to date would have not have run up against the limit. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] NSA breakthrough
On Fri, Jun 14, 2013 at 11:20 PM, jamescho...@austin.rr.com wrote: DWave comes to mind. Sure yeah, under the list of things that can't possibly be useful in any way for the problem described. The DWave machine is widely considered to not be a universal quantum computer[1], and *even if it was*, which it isn't, there are no known quantum algorithms which offer any serious benefit in this arena. [1] See for instance: http://www.scottaaronson.com/blog/?p=1400 -- -- -- -- -- Venimus, Vidimus, Dolavimus jamescho...@austin.rr.com jcho...@confusionresearchcenter.org rav...@ssz.com james.cho...@g.austincc.edu jchoate00...@gmail.com james.cho...@twcable.com h: 512-657-1279 w: 512-845-8989 http://hackerspaces.org/wiki/Confusion_Research_Center http://confusionresearchcenter.org http://arbornet.org (ravage) Adapt, Adopt, Improvise -- -- -- -- ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography -- Noon Silk Fancy a quantum lunch? https://sites.google.com/site/quantumlunch/ Every morning when I wake up, I experience an exquisite joy — the joy of being this signature. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
[cryptography] keyserver
so what's the go-to keyserver to look people up these days? i've tried http://keyserver.rayservers.com/, it times out upon searching, so does http://pgp.mit.edu/ am i missing some obvious places? -- Noon Silk ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] keyserver
On Thu, Jun 13, 2013 at 10:53 AM, Jeremy Stanley fu...@yuggoth.org wrote:
On 2013-06-13 10:49:25 +1000 (+1000), Noon Silk wrote:
so what's the go-to keyserver to look people up these days?
[...]
I use hkps://hkps.pool.sks-keyservers.net quite happily. I generally
point people to this extremely well-written article...
https://we.riseup.net/debian/openpgp-best-practices
Excellent thank you, just what I wanted!
--
{ PGP( 48F9961143495829 ); FINGER( fu...@cthulhu.yuggoth.org );
WWW( http://fungi.yuggoth.org/ ); IRC( fu...@irc.yuggoth.org#ccl );
WHOIS( STANL3-ARIN ); MUD( kin...@katarsis.mudpy.org:6669 ); }
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
--
Noon Silk
___
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Well, that's depressing. Now what?
On Sat, Jan 28, 2012 at 6:55 PM, Nico Williams n...@cryptonector.com wrote: [BTW, I held off saying anything until the first post. I'd wanted to see how long we could collectively avoid the same old QKD thread. It took five hours to the first post, fourteen to get to the first significant disagreement.] On Fri, Jan 27, 2012 at 8:43 PM, Noon Silk noonsli...@gmail.com wrote: I think it's important to note that it's obviously completely wrong to say QKD is snake-oil, what you *can* say is that someone *selling* *any* demonstratably-insecure crypto device as a secure one, is snake oil. So, that is to say, you can only claim snake-oil in reference to a vendor and a device, not a field of research. This has been covered to death by now, both today and in the past (search the archives of this and similar lists). Until we see scalable quantum authenticated quantum secrecy / key distribution, QKD is not suitable for production deployment. Right, but two things: 1) who disagrees with that? not me, 2) this isn't what my original comment was about. [...] , but QKD as a product sure is. Again, this is a useless statement in it's general form; you need to be specific. Nico -- -- Noon Silk Fancy a quantum lunch? https://sites.google.com/site/quantumlunch/ Every morning when I wake up, I experience an exquisite joy — the joy of being this signature. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Well, that's depressing. Now what?
On Sun, Jan 29, 2012 at 1:23 AM, Steven Bellovin s...@cs.columbia.edu wrote: On Jan 27, 2012, at 8:22 PM, Noon Silk wrote: On Sat, Jan 28, 2012 at 6:01 AM, Steven Bellovin s...@cs.columbia.edu wrote: Or at least that's what everyone thought. More recently, various groups have begun to focus on a fly in the ointment: the practical implementation of this process. While quantum key distribution offers perfect security in practice, the devices used to send quantum messages are inevitably imperfect. This is only surprising if you assume large values of everyone. Anyone in the real world has long since worried about implementations. Remember Bob Morris' Rule 1 of cryptanalysis: check for plaintext. (http://www.ieee-security.org/Cipher/ConfReports/conf-rep-Crypto95.html) So why didn't one of these real world people point this out, to researchers? It's a bit too easy to claim something as obvious when someone just told you. https://www.cs.columbia.edu/~smb/blog/2007-06/2007-06-29.html is something I wrote 4.5 years ago. You'll note that it mentions the issue of sending more than one photon per bit. Bruce Schneier has often written on it: http://www.schneier.com/blog/archives/2010/09/successful_atta.html http://www.schneier.com/blog/archives/2009/12/quantum_cryptog_1.html http://www.wired.com/politics/security/commentary/securitymatters/2008/10/securitymatters_1016 If you go to http://www.mail-archive.com/cryptography@metzdowd.com/msg07680.html you'll see a whole thread that I, among many others, participated in. Right, but I said *specifically about the mentioned issue, in the original post*. Of course it would be ridiculous and wrong to claim the non-research world hasn't spoken about the issue with QKD in general, and commented on specific proposals. In your original post it looked to me that you claimed the found issue was obvious; not that side channel attacks were obvious (I addressed this in an earlier email). --Steve Bellovin, https://www.cs.columbia.edu/~smb -- Noon Silk Fancy a quantum lunch? https://sites.google.com/site/quantumlunch/ Every morning when I wake up, I experience an exquisite joy — the joy of being this signature. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Well, that's depressing. Now what?
On Sun, Jan 29, 2012 at 4:22 AM, Nico Williams n...@cryptonector.com wrote: On Sat, Jan 28, 2012 at 2:33 AM, Noon Silk noonsli...@gmail.com wrote: On Sat, Jan 28, 2012 at 6:55 PM, Nico Williams n...@cryptonector.com wrote: Until we see scalable quantum authenticated quantum secrecy / key distribution, QKD is not suitable for production deployment. Right, but two things: 1) who disagrees with that? not me, 2) this isn't what my original comment was about. [...] , but QKD as a product sure is. Again, this is a useless statement in it's general form; you need to be specific. I don't see how I could have been much more specific given the two things you quoted from me. As I said, you could point to specific products that you have issues with, not QKD at large (a collection of potential protocols and implementations). Let's turn it around: what QKD products do you think are not snake oil today? Please be specific (list products currently on sale) and back up the assertion with a rationale, remembering that this is in comparison to classical cryptography technology. Feel free to also point to literature about QKD technologies perhaps not yet on the market but which might change everything, and again, back up your assertions. Nice try, but I'm not the one making general claims about it. My original comment to you was, it's not sensible to say QKD is snake oil, without direct reference to something. I didn't say I want to argue about which products are or aren't (frankly, I don't know anywhere near enough about them or their implementations to comment on that). Nico -- -- Noon Silk Fancy a quantum lunch? https://sites.google.com/site/quantumlunch/ Every morning when I wake up, I experience an exquisite joy — the joy of being this signature. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] obfuscating symbols without increasing their size
On Thu, Jan 20, 2011 at 12:44 PM, travis+ml-rbcryptogra...@subspacefield.org wrote: So, there's an interesting problem I ran into: Suppose you need to obfuscate symbols in a symbol file, and to be able to look them up later to analyze crash dumps. Suppose further that the symbol file format is kinda weird, and so you can't re-create the symbol file from scratch. IOW, the obfuscated symbols have to be changed in-place. Since many symbols may be less than 160 bits, hashes are right out, and those anyway would be limited since the input space is small enough that one could easily guess all symbols, and hash them - classic dictionary attack. Hardening against guessing might help some, but to store any salt would only make matters worse. One could assign ordinal numbers to them, but for other, procedural reasons one cannot do this - namely, the obfuscated value should not change from release to release, and propogating the old ordinal values with each release is a pain. The simple answer seems to be encryption, which can operate without adding any metadata, but there's a catch; the symbol file format expects the values to be symbols - not arbitrary octets. Sounds to me like the simplist solution is just a one-time pad[1]. It won't increase the size, and from the sounds of your environment, you can just keep the keys locally, and use them only when you do the debugging. But perhaps I'm misunderstanding your question. [...] -- Effing the ineffable since 1997. | http://www.subspacefield.org/~travis/ My emails do not usually have attachments; it's a digital signature that your mail program doesn't understand. If you are a spammer, please email j...@subspacefield.org to get blacklisted. -- [1] http://en.wikipedia.org/wiki/One-time_pad Noon Silk http://dnoondt.wordpress.com/ (Noon Silk) | http://www.mirios.com.au:8081 Every morning when I wake up, I experience an exquisite joy — the joy of being this signature. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] obfuscating symbols without increasing their size
On Thu, Jan 20, 2011 at 1:31 PM, travis+ml-rbcryptogra...@subspacefield.org wrote: On Thu, Jan 20, 2011 at 12:49:26PM +1100, Noon Silk wrote: Sounds to me like the simplist solution is just a one-time pad[1]. It won't increase the size, and from the sounds of your environment, you can just keep the keys locally, and use them only when you do the debugging. But perhaps I'm misunderstanding your question. Yeah, I knew people would tend not to answer my question and simply provide solutions which won't work due to the context. But possibly someone will give me something I haven't thought of, so let me explain further. Hah. I'm not sure how to take that; if you knew people wouldn't get the idea from your original message why wouldn't you clarify it up front? OTP won't work - simply XORing a printable character with a non-printable won't guarantee a printable, for example, and symbols have to be printable. Well no, it won't, but it's surely obvious that you could make it such that it was in the printable range? It'd be much simpler to just map symbols to ordinal values, but that has the following problem: The releases may have different sets of symbols, in different orders. Furthermore, the symbols have to map to the same thing on subsequent releases so crashes can be correlated across releases. This last point is just a function of your decoding process. You're implying that you want to match pre-decryption, not post-decryption. I'd expect you'd want to match post-decryption, otherwise it would be trivial to correlate your obfuscation anyway, no? Finally, it's a burden for data to have to be propogated from the obfuscation run on one release to the next. They might be done by different groups who don't normally communicate, for example, or there could be release of different branches so no strict ordering in place (apart from temporal, and that's kinda hard to enforce; one person fails to update the obfuscated symbol mapping, or whatever shared state is supposed to be passed along, and everything's hosed). Do you actually have a workflow where this needs to be used or is it theoretical? Do you have tools around it? (i.e. make it part of your build process and also symbol server, etc). -- Effing the ineffable since 1997. | http://www.subspacefield.org/~travis/ My emails do not usually have attachments; it's a digital signature that your mail program doesn't understand. If you are a spammer, please email j...@subspacefield.org to get blacklisted. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography -- Noon Silk http://dnoondt.wordpress.com/ (Noon Silk) | http://www.mirios.com.au:8081 Every morning when I wake up, I experience an exquisite joy — the joy of being this signature. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] obfuscating symbols without increasing their size
On Thu, Jan 20, 2011 at 2:30 PM, travis+ml-rbcryptogra...@subspacefield.org wrote: On Thu, Jan 20, 2011 at 01:36:55PM +1100, Noon Silk wrote: Hah. I'm not sure how to take that; if you knew people wouldn't get the idea from your original message why wouldn't you clarify it up front? It's hard to know in what ways people will misunderstand you, for the same reason it's hard to see bugs in code you wrote. But there's a funny thing about cryptographers: If you just state the formal problem, namely my last question(s), they might give you an answer, but you probably won't get any answers (possibly out of lack of a practical purpose), or you might get answers that fail due to lack of context. But if you try and provide some context, often they'll try to provide alternatives, rather than answering the question, often due to misunderstanding the context or inadequacy of explanation. The problem with this is that you then have to go back and re-clarify, unless you rather tediously define all your terms, assumptions and constraints a priori. The problem with that is it wastes time on things that might not need explaining. But sometimes the process can be elucidating, not only in what they don't understand from your explanation, which teaches you how to explain when you want to be better understood, but also because they sometimes present alternatives which might actually work. So this time I just tried my best to explain context, and now I'm having to shore it up, but I have spare time on my hands. ;-) OTP won't work - simply XORing a printable character with a non-printable won't guarantee a printable, for example, and symbols have to be printable. Well no, it won't, but it's surely obvious that you could make it such that it was in the printable range? That woudl make the obfuscated symbol larger than the non-obfuscated, and that would require altering the structure of the container file, which I can't do. If you use the OTP to generate a number in the printable range, and swap on that basis, I fail to see how it will go to non-printable. I also fail to see how it alters the structure if it is a direct character-for-character replacement. The constraint is not a maximum length, but that the function be length-preserving. Furthermore, the symbols have to map to the same thing on subsequent releases so crashes can be correlated across releases. This last point is just a function of your decoding process. You're implying that you want to match pre-decryption, not post-decryption. I'm saying if the symbol is plaintext and the obfuscated symbol is obfuscate, it has to be that way for every release, without sharing a database of mappings between releases. This is so that crash dumps across releases can be correlated. I'd expect you'd want to match post-decryption, otherwise it would be trivial to correlate your obfuscation anyway, no? Obviously, the once you invert the obfuscation, then you should have the original value. I'm not quite following you here, possibly you said decryption instead of obfuscation, in which case I must clarify that we do actually want people to know where the symbols migrated across releases. That is necessary for crash log analysis, though not ideal from a security perspective. No, I said the right thing. I must admit I'm having a bit of trouble understanding exactly how you will be implementing this practically. I agree with you that the system I'm proposing is only good post-decryption. It's clearly more than obfuscating, but it satisfies your requirements, and gives a better level of security. But it's only practical if you have the development setup to allow it to be automated. If you don't have that, then I agree it's not practical and I leave to you come up with something else. PS: Since you might be interested in OTPs, I run the OTP mailing list: http://lists.bitrot.info/mailman/listinfo/OTP -- Effing the ineffable since 1997. | http://www.subspacefield.org/~travis/ My emails do not usually have attachments; it's a digital signature that your mail program doesn't understand. If you are a spammer, please email j...@subspacefield.org to get blacklisted. -- Noon Silk http://dnoondt.wordpress.com/ (Noon Silk) | http://www.mirios.com.au:8081 Every morning when I wake up, I experience an exquisite joy — the joy of being this signature. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
