Slashdot Mirror

Two datacenters owned by the same company using MPC is a really dumb use case. That won't help at all. The point of Google encrypting cross-dc communications is a forcing manoeuvre - it forces intelligence agencies to go via Google Legal to get information where the request can be analyzed and pushed back on. Even in countries where the legal system is flimsy and corrupt, that's an issue that can be improved significantly just with a single act of Congress or Parliament, whereas undoing their wiretapping infrastructure will prove somewhat harder because there's no adversarial lawyer standing in the way.

A better example might be two datacenters owned by different companies, where they don't mutually trust each other. Or, to give an actual use case, the OTR chat encryption protocol uses MPC to authenticate connections. They call it the socialist millionaires protocol. The two parties agree on a secret word (typically by one user posing a question to the other), and then a variant of MPC is used to verify that both parties selected the same word. The word itself never transits the wire and it's only used for authentication, so it's relatively strong even if the secret word is short or predictable.

Now, for some background. The paper can be found here if you want to skip the million+1 links and registration crap.

The basic idea behind MPC is that you write your shared computation in the form of a boolean circuit, made up of logic gates as if you were making an electronic circuit. The inputs to the program are represented as if they were electronic signals (i.e. as one and zero bits on wires). Once done, there are two protocols you can follow. The original one is by a guy named Andrew Yao. Each wire in the circuit is assigned a pair of keys. The details I'll gloss over now, but basically given the circuit (program) as a template, lots of random keys are created by party A, then the entire "garbled circuit" is sent to party B who will run it. Party A also selects the keys for his input wires and sends them to party B, who doesn't know whether they represent 0 or 1, only party A knows that.

Now party B wants to run the program with his input, but he doesn't want party A to know what his input is. So they use a separate protocol called an oblivious transfer protocol to get party A to cough up the right keys for B's input wires, without A finding out what they were. Finally, party B can run the program by progressively decrypting the wires until the output is arrived at.

What I described above is Yao's protocol. There is also a slightly different protocol called BGV. In BGV you don't send the entire program all at once. Instead, as party B runs through the program, each time they encounter an AND gate they do an oblivious transfer with party A. XOR gates are "free" and don't require any interaction. I forgot what happens for other kinds of gates. Basically, BGV involves both parties interacting throughout the computation, however, it can result in much less network traffic being required if your OT protocol is cheap, because if your circuit is very wide and shallow then most of the garbled program never has to even get transferred at all.

From what I can tell, most of the best results in MPC these days are coming from BGV coupled with new, highly efficient OT protocols. SPDZ appears to work on yet another design, but the basic reliance on circuit form remains.

The summary claims that

Though the concept was introduced in 1982, ways to accomplish it with more than two parties, or with standardized protocols and procedures, has not become practical in commercial environments.

(I presume it's quoting the article, but samzenpus has managed to make the link self-referential).

That just isn't true. I've read a very interesting paper about "massively multiplayer" commercial use of MPC back in 2008. It involved Danish researchers, so it may be the same team, and there may be improvements, but it would be good to limit the claims to the actual novelties.

Google for "Related-Key Attack on the Full AES-256"

http://eprint.iacr.org/2009/317.pdf

Okay, here's the slides from a talk:
https://www.cryptolux.org/mediawiki-esc2013/images/c/cd/Joux-EM-multiuser-ESC2013.pdf

And a paper which is related:
http://eprint.iacr.org/2013/095.pdf

Basically, from my first read, this is just a better sieve, a system which should find smooth numbers faster by choosing better starting points and using faster tests. I wouldn't call it a general break in RSA, and while it might certainly be a better sieve than GNFS, it's no silver bullet either. I can't imagine anyone breaking RSA numbers like this unless they're very well funded.

Just skimmed the paper...

The scope of this is very limited. It applies primarily to functions that encapsulate a secret (not a general piece of code). From reading the paper, it appears that the goal is to attempt to frustrate folks that that want to disassemble software routines to look for small secrets buried in the code.

Example: Let's say you have a function that decrypts a message from a server with a key and you want to say embed that code in javascript. You don't, however, want someone figure out the key by just looking at the javascript, you want it to be a black box.

This technique allegedly can obfuscate the code so that it is just as hard to figure out how the secret is used as it is to infer the secret from sending in values and building a lookup table. Of course you could just cut-out the obfuscated code and use it as an oracle (because you can still run it), but it continues to effectively hide the secret as best as possible.

As I understand it, the basic techique is to create a function (from a class of functions with certain properties) that cuts the input domain into a large number sets and for each set finds a cheap multi-linear function that maps the correct output values for that small set of the input values but is don't care for the rest of the input values. The "trick" is that the class functions that cut the input domain are not fixed, but depend on the input so it is a hard problem to figure out which maps are used without just searching them all. Thus every obfucation instance of a function that encapsulates the same secret could look different and still compute the same result, or conversely, encapsulate different secrets, yet look very similar, but produce the correct result.

The downside of course is that small multi-linear functions aren't the best implementation for actual encryption functions. For example, something very simple like 128-bit AES, might be considered a function with 2^128 entry 128bit table. Unless I'm mistaken, it will be very hard to chop up a 2^128 bit table using their method (even the authors concede the fact that thier construction isn't efficient enough for practical problems).

However, they make a "bold" assertion, that they can apply their technique to stuff like crippleware by obfuscating the function that enables/disables various program features. I'll go out on a limb and say most folks that hack stuff like that don't bother to figure out ways to turn on/off features, but just go for attempting to bypass calls to such a function or disable the function altogether.

The other "bold" assertion they make is that it might be used by software vendors to deploy a patch without tipping off the black-hats about the nature of the vunerablity before all systems can be patched. This is wishful thinking as functions are generally not vunerable (since they by definiton have no-side effects), but procedures (the function-like modules that render side-effects) are the modules that tend to have the bugs. This technique of theirs really only applies to functions, not procedures so it's hard to see how this would help in many circumstances.

Show me the maths

Sure, here you go.

Meh. Anyone who can talk up their work can present a paper at a conference; all you need to do is convince a couple of referees that what you're doing is interesting.

Yeah like totally. I mean look at that crapolla, you havta have a PhD in math or somthng just to read it!!!! I'm like, just let me at the code dude. I shove it in my perl byte-code decompiler and like it's source in 10 mins, I rulez!!!

I can't really comment on the slashdot summary, but take a look at the actual abstract: http://eprint.iacr.org/2013/451

"In functional encryption, ciphertexts encrypt inputs x and keys are issued for circuits C. Using the key SK_C to decrypt a ciphertext CT_x = Enc(x), yields the value C(x) but does not reveal anything else about x. Furthermore, no collusion of secret key holders should be able to learn anything more than the union of what they can each learn individually."

In other words, it seems that their technique allows you to encrypt some secret data, then (provably) only release the result of some arbitrary function of that data. It sounds like this means you could (in principle) release health data in encrypted form, then allow researchers to study some ensemble properties of it by giving out the appropriate keys. This aspect of it certainly seems pretty cool.

You mean a link to the paper, like the one in the third paragraph of the article?

I call BS on the notion that you have already read and digested TFP and are in a position to make anything close to an informed comment about the methodology proposed. In particular you seem to be completely unaware that your concern about performance penalties is specifically addressed.

Cryptology ePrint Archive: Report 2013/451

Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits

Sanjam Garg and Craig Gentry and Shai Halevi and Mariana Raykova and Amit Sahai and Brent Waters

Abstract: In this work, we study indistinguishability obfuscation and functional encryption for general circuits:

Indistinguishability obfuscation requires that given any two equivalent circuits C_0 and C_1 of similar size, the obfuscations of C_0 and C_1 should be computationally indistinguishable.

In functional encryption, ciphertexts encrypt inputs x and keys are issued for circuits C. Using the key SK_C to decrypt a ciphertext CT_x = Enc(x), yields the value C(x) but does not reveal anything else about x. Furthermore, no collusion of secret key holders should be able to learn anything more than the union of what they can each learn individually.

We give constructions for indistinguishability obfuscation and functional encryption that supports all polynomial-size circuits. We accomplish this goal in three steps:

- We describe a candidate construction for indistinguishability obfuscation for NC1 circuits. The security of this construction is based on a new algebraic hardness assumption. The candidate and assumption use a simplified variant of multilinear maps, which we call Multilinear Jigsaw Puzzles.

- We show how to use indistinguishability obfuscation for NC1 together with Fully Homomorphic Encryption (with decryption in NC1) to achieve indistinguishability obfuscation for all circuits.

- Finally, we show how to use indistinguishability obfuscation for circuits, public-key encryption, and non-interactive zero knowledge to achieve functional encryption for all circuits. The functional encryption scheme we construct also enjoys succinct ciphertexts, which enables several other applications.

Category / Keywords: public-key cryptography / Obfuscation, Functional Encryption, Multilinear Maps

Date: received 20 Jul 2013, last revised 21 Jul 2013

Contact author: amitsahai at gmail com

Available format(s): PDF | BibTeX Citation

Cryptology ePrint Archive: Report 2013/451

Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits

Sanjam Garg and Craig Gentry and Shai Halevi and Mariana Raykova and Amit Sahai and Brent Waters

Abstract: In this work, we study indistinguishability obfuscation and functional encryption for general circuits:

Indistinguishability obfuscation requires that given any two equivalent circuits C_0 and C_1 of similar size, the obfuscations of C_0 and C_1 should be computationally indistinguishable.

In functional encryption, ciphertexts encrypt inputs x and keys are issued for circuits C. Using the key SK_C to decrypt a ciphertext CT_x = Enc(x), yields the value C(x) but does not reveal anything else about x. Furthermore, no collusion of secret key holders should be able to learn anything more than the union of what they can each learn individually.

We give constructions for indistinguishability obfuscation and functional encryption that supports all polynomial-size circuits. We accomplish this goal in three steps:

- We describe a candidate construction for indistinguishability obfuscation for NC1 circuits. The security of this construction is based on a new algebraic hardness assumption. The candidate and assumption use a simplified variant of multilinear maps, which we call Multilinear Jigsaw Puzzles.

- We show how to use indistinguishability obfuscation for NC1 together with Fully Homomorphic Encryption (with decryption in NC1) to achieve indistinguishability obfuscation for all circuits.

- Finally, we show how to use indistinguishability obfuscation for circuits, public-key encryption, and non-interactive zero knowledge to achieve functional encryption for all circuits. The functional encryption scheme we construct also enjoys succinct ciphertexts, which enables several other applications.

Category / Keywords: public-key cryptography / Obfuscation, Functional Encryption, Multilinear Maps

Date: received 20 Jul 2013, last revised 21 Jul 2013

Contact author: amitsahai at gmail com

Available format(s): PDF | BibTeX Citation

Cryptology ePrint Archive: Report 2013/451

Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits

Sanjam Garg and Craig Gentry and Shai Halevi and Mariana Raykova and Amit Sahai and Brent Waters

Abstract: In this work, we study indistinguishability obfuscation and functional encryption for general circuits:

Indistinguishability obfuscation requires that given any two equivalent circuits C_0 and C_1 of similar size, the obfuscations of C_0 and C_1 should be computationally indistinguishable.

In functional encryption, ciphertexts encrypt inputs x and keys are issued for circuits C. Using the key SK_C to decrypt a ciphertext CT_x = Enc(x), yields the value C(x) but does not reveal anything else about x. Furthermore, no collusion of secret key holders should be able to learn anything more than the union of what they can each learn individually.

We give constructions for indistinguishability obfuscation and functional encryption that supports all polynomial-size circuits. We accomplish this goal in three steps:

- We describe a candidate construction for indistinguishability obfuscation for NC1 circuits. The security of this construction is based on a new algebraic hardness assumption. The candidate and assumption use a simplified variant of multilinear maps, which we call Multilinear Jigsaw Puzzles.

- We show how to use indistinguishability obfuscation for NC1 together with Fully Homomorphic Encryption (with decryption in NC1) to achieve indistinguishability obfuscation for all circuits.

- Finally, we show how to use indistinguishability obfuscation for circuits, public-key encryption, and non-interactive zero knowledge to achieve functional encryption for all circuits. The functional encryption scheme we construct also enjoys succinct ciphertexts, which enables several other applications.

Category / Keywords: public-key cryptography / Obfuscation, Functional Encryption, Multilinear Maps

Date: received 20 Jul 2013, last revised 21 Jul 2013

Contact author: amitsahai at gmail com

Available format(s): PDF | BibTeX Citation

It's not, actually. There are already asymmetric crypto algorithms which are believed to be quantum-resistant. They are typically based on the hardness of vector problems in n-dimensional integer lattices, or problems that have been proven reducible to such problems such as learning with errors.

Interesting read, but it doesn't address the questions at hand:
Are cryptography advances and computer advances hand-in-hand? I believe the answer to that question is still no.
Are big crypto advances in a next generation public key algorithm limited by our knowledge? I believe the answer to that question is still yes.

For example, the McEliece-like crypto system (which seems suspiciously analogus to your LWE paper) did not appear to have any major advances for many years (probably because sending around huge matrices is a real bummer and attempts to reduces this reduced the security parameters). We also have no direct knowledge about its quantum resistance other than some assumptions. Who knows, but its security profile may be very entwined with algorithms for error-correction of quantum states for quantum computers (which is an interesting topic apparently still in it's infancy). Unlike the study of factoring and discrete logarithms which have undergone lots of study and has a huge knowledge base, we have likely only scratched the surface on other computationally hard algorithms to use as a basis for a public key system. Maybe they aren't really hard at all. At this point, we don't really know. For example, the McElice system's security parameters needed to be updated after some advances in classical information theory knowledge like this...

In contrast, if we knew about this wonderful system but computers to do it aren't big/powerful enough yet to implement it practically, that would be one thing. I think we actually lack the knowledge base to meaningfully change our public key infrastructure today (which should keep all those researcher employed for a good while longer).

Except what they obviously intend to use it for - large scale decryption of SSL traffic so the data can be mined by Google (for profit) and the Government (to oppress).

If that's their intent, they'll be sorely disappointed, since D-Wave's machine has only 512 qubits (where as all new SSL certificates are at least 1024 bits). More importantly, the machine is not a general purpose quantum computer and can't run Shor's algorithm.

Besides, NSA is already able to break 1024 bit RSA using conventional computing (not to mention the possibility of much cheaper side channel attacks). See e.g. Schneier.

If we are optimistic, it may be possible to factor a 1024-bit RSA modulus [before 2020] by means of an academic effort on [a] limited scale.

- Kleinjung et al., 2010, my emphasis

The same paper gives an estimated difficulty of 2 million CPU years for factoring 1024 bit RSA. Sure, that's about $500 million on Amazon EC2, but the NSA have dedicated data centers, dedicated ASICs, smarter algorithms, and money to burn. Realistically, breaking 1024 bit RSA may be as cheap as $50,000 a pop to the NSA... and remember, they only have to break it once per HTTPS certificate, not once per connection.

(As for Google, they're already have your email and knows every page you visit that contains a YouTube video, a +1 button, or Google Analytics... Why would they waste time breaking RSA when the sidechannel attacks are cheap and plentiful?)

It seems that Julian Assange is a hardcore Bitcoin fanboy... he spent about a third of his interview talking about it.

That said, if he took his own advice and invested heavily in Bitcoin back in 2011 when they were less than a $1 each, he'd be a wealthy guy right now.

Yes, you are very correct, at least as of May 13th 2012.

Quantitative Analysis of the Full Bitcoin Transaction Graph page 5
--
...can estimate with our methodology that WikiLeaks owns at least 83 addresses, that it was involved in at least 1088 transactions, and that it had an accumulated income in all these addresses of 2605.25 BTC's.
--

Please keep in mind that convincing me isn't less difficult than convincing the whole network. You still need to produce hashes lower than the target, and even if I am only connected to you and perfectly believe you, every block you need to produce needs the same amount of work as the rest of the network.

I don't see how that follows yet. Rolling back transactions or double spending is more than enough to sink everything. I merely need to fool you for long enough to engage in another transaction - perhaps including converting the currency out of bitcoins. Bitcoin's own vulnerability FAQ (which openly discloses several fatal looking flaws I hadn't thought of besides this one) indicates segmentation is not a practical attack because "any leakage" will carry the whole network state. Which I don't understand at all - because in many scenarios it is more work to create segmentation with leakage than without?

The attack presumes I can control your communications with the rest of the world - indeed, for most internet users this is the status quo via several entities, such as their ISP and their repressive government (leaving aside the various other ways it can happen). A split sounds like a good term - splinter, probably more accurate. In such a case, the difficulty of the attack must be reducible, or how can the rest of the world, which we are not communicating with (for long enough for me to defraud you) still be a factor in the CPU spend for the attack? Shannon will wake from his grave to hear the explanation.

Once I have my stolen cash, I'm perfectly happy for the splinter to heal - in fact, I want it to, so I can steal from you again later.

Bitcoin is not anonymous

In discussions I am having here today, this is still news to others, I'm afraid. In fact I think it is hardly redundant. For instance, I would like to address your assertion that, If you wish to remain anonymous, trusted 3rd parties have any relevance.

First of all, the concept is enormously troubling on its face - enough so that no one seriously advising others about anonymity should speak of it. But let us say there are really 3rd parties you would like to trust, and you have a desire to perform anonymous transactions.

I think we need to make it clear what we are talking about here: Bitcoin is the least anonymous, most transparent currency ever invented. Nothing else in existence is more law-enforcement-friendly.

Your trusted third party scenario is my dream if I am an FBI agent. As an intermediary for someone else, you buy something with account Y. Associating your real identity with your cryptographic identity is policework - let us admit that it can and will be done. From there on out I can see every transaction you have ever made with Y. You may make multiple identities - so much the better. With surveillance of your net connection (which even in the US I can do without a warrant) I will learn any identity you use to conduct business. That's leaving aside that, soon, wallet Y will be empty and wallet X will be full. What will you do then? It is impossible to indefinitely segment your payables from your receivables, for reasons found in elementary accounting.

You have all the same problems as a traditional money launderer and many new ones that no money launderer has ever had before.

Anyone who wishes to perform anonymous transactions (the right of every hard cash holder since the invention of money) should run screaming from Bitcoin.

Because the transaction data you need isn't in the chain.

If I cannot tell who owns what, then I can double-spend. If I can tell, then I can see transaction data. No amount of complex dressing can hide this simple wound.

In fact the chain is exactly the transaction data I need, unless I have totally misunderstood the chain, and so did the many security researchers that have been creating transaction graphs from it, i.e. http://eprint.iacr.org/2012/584

that is an inevitable consequence of any p2p system, simply because the participants are the network

That is not true; see e.g.:

http://eprint.iacr.org/2012/441

Here is a layman's translation:

• It is a peer-to-peer system for computing a function over inputs from N parties
• The privacy of each party's input is protected i.e. no party will learn any other party's input beyond what the function's output reveals
• The privacy of each party's output is protect in the same fashion as the input
• The outputs are guaranteed to be correct if the protocol terminates (an attacker might just stop the protocol early, in which case there is no output)
• All of the above holds if the attacker can take over a majority of the participants (e.g. like the attack I described above)
• All of the above holds if the attacker can choose which parties to corrupt after observing some part of the protocol

In other words, this is a system that protects against an even more sophisticated version of the attack I described above.

Okay, how could it be improved?

Drop the idea of not having any banks, and then create the sort of system described in this line of research:

http://www.cs.ut.ee/~lipmaa/crypto/link/protocols/ecash.php

Not really, even if you power off, the memory will still hold its contents for many minutes. Some bits may flip but that is not such a problem, because even with some flipped bits you can still recovery the key. Most of the time the memory image contains not just the key, but also an AES key schedule which is an expanded version of the key with huge amounts of redundancy. Even if a little bit more than 70% of the bits contain random values instead of bits from real key schedule the real key can still be recovered within a few minutes: Applications of SAT Solvers to AES key Recovery from Decayed Key Schedule Images

As best we currently know, it is Not Possible to deduce subsequent token outputs merely given access to previous token outputs. However, it is trivial to do so given access to the seed value. And yet, RSA's last big security fuckup was because they weren't purging seed values for tokens sold to customers. And now it turns out that their software 'tokens' retain their seed values in local storage forever.

With the hardware tokens, there is a class of attack that is only feasible if you have the hardware token for a long time and closely monitor the numbers it produces. Every once in a while (on average, around one third of keys will experience this once a year) it will repeat a number for two lots of 90 seconds - a vanishing differential. Knowing this vanishing differential, it then becomes computationally feasible to recover the keyfob's secret key.

This class of attack doesn't really help to break a single targeted keyfob - there's a good chance you'll watch it for 12 months straight and not see a single vanishing differential - but if you happen to have, for example an employer-provided keyfob that while it's in legitimately your possession for a long enough time to observe such an event, and then the keyfob is recycled (such as if you finish the job for which you were given the keyfob and it's then handed on to someone else) then you can predict future output of that individual keyfob.

More info for those who are interested is here:
http://eprint.iacr.org/2003/162.pdf

http://eprint.iacr.org/2012/248

Bitcoins are the tender of the future

No they are not; the demand for Bitcoin is microscopic by comparison with the demand for other currencies, and when the hype dies down people are going to be selling Bitcoin more than they will buy. Without the ability to pay taxes etc. with Bitcoin, it is doomed -- and there is no incentive for any government to accept Bitcoin for tax payment, nor for any court to assess damages in terms of Bitcoin, nor for any bank to issue a Bitcoin loan, etc. The economic shortcomings alone are enough to kill Bitcoin; it is riding on hype about anonymous payments (which is really just hype -- anonymous Bitcoin payments are hard to get right) and badly thought out theories about the value of deflationary currencies.

Bitcoin's technical shortcomings do not help either. Without a central authority, Bitcoin cannot offer secure offline transactions (see Chaum's extensive work on digital cash if you are curious why), which basically means you will never see Bitcoin compete with paper money (and do not think for a second that people are going to invest in fast Internet connections just to accept Bitcoin payments). Even worse, it was recently shown that online transactions in Bitcoin are not secure:

http://eprint.iacr.org/2012/248

Now, can we stop giving digital cash a bad name, and start deploying better developed digital cash systems (yes, the ones that involve banks / currency issuing authorities)?

There also systems based on elliptic curve isogenies, but a new quantum algorithm comes somewhat close to breaking them.

I'm one of the authors of that algorithm. You might be interested in my latest work: an improved cryptosystem based on elliptic curve isognies which seems to be more secure against quantum computers than previous isogeny-based schemes. (In particular, my algorithm for breaking the old isogeny-based schemes doesn't work against this new scheme.) Since posting the paper, we have improved the performance of the new scheme to the point where it is faster than RSA for the same (conjectured) level of security, even against classical computers (never mind quantum computers).

I am obviously biased, but I think my new scheme is the best candidate for quantum-resistant key exchange. It's faster than RSA, it uses shorter keys than RSA, and it's security is based on relatively standard results in elliptic curve theory compared to other systems that involve difficult-to-analyze problems on lattices. It is very much a classical cryptosystem with some nice features, which happens to be quantum-resistant. It's not some kind of cumbersome scheme which you would use only if you cared about quantum computers.

In general, I've given up on replying to Slashdot crypto articles, unless I have a personally relevant reason to do so (your post certainly qualifies). The general level of ignorance in the discussion is so stratospheric that it is painful to read. Even worse, the vast majority of commenters think that they know what they're talking about (they don't), and the vast majority of moderators mod up ignorant (but plausible sounding) drivel while ignoring the comments made by actual cryptographers.

The correct answer to the submitter's question is what you just said: there are plenty of quantum-resistant key-exchange protocols available, among them NTRU, McEliece, learning with errors, and my scheme. The submitter should also have asked about quantum-resistant digital signature schemes. Here the answer is much less reassuring: there is only one, namely, NTRU. This is a huge problem for crypto if we ever build a quantum computer, since authentication is at least as important as encryption. It's a real shame that this entire discussion is based on the wrong question.

Discrete logarithm is also covered by Shor's quantum algorithm that covers the hidden subgroup problem (http://en.wikipedia.org/wiki/Hidden_subgroup_problem) for finite abelian groups, so Diffie-Hellman and El-Gamal are no Good.
There exists cryptosystems that do not fall under this umbrella, based on "Learning with Error" (LWE - http://en.wikipedia.org/wiki/Learning_with_error) (that reduces to certain worst-case Lattice problems, cool stuff). For example http://eprint.iacr.org/2010/613.pdf

Recently even Fully Homomorphic Encryption based on solely on LWE was found: http://eprint.iacr.org/2011/344.pdf

Other problems that people have basing public key cryptography on that might not be exponentially faster with a quantum computer are "Subset Sum" (http://eprint.iacr.org/2009/576.pdf) and "hardness of decoding general linear codes" (http://en.wikipedia.org/wiki/McEliece_cryptosystem).

The topic is called "post-quantum cryptography" in litterature.

Discrete logarithm is also covered by Shor's quantum algorithm that covers the hidden subgroup problem (http://en.wikipedia.org/wiki/Hidden_subgroup_problem) for finite abelian groups, so Diffie-Hellman and El-Gamal are no Good.
There exists cryptosystems that do not fall under this umbrella, based on "Learning with Error" (LWE - http://en.wikipedia.org/wiki/Learning_with_error) (that reduces to certain worst-case Lattice problems, cool stuff). For example http://eprint.iacr.org/2010/613.pdf

Recently even Fully Homomorphic Encryption based on solely on LWE was found: http://eprint.iacr.org/2011/344.pdf

Other problems that people have basing public key cryptography on that might not be exponentially faster with a quantum computer are "Subset Sum" (http://eprint.iacr.org/2009/576.pdf) and "hardness of decoding general linear codes" (http://en.wikipedia.org/wiki/McEliece_cryptosystem).

The topic is called "post-quantum cryptography" in litterature.

Discrete logarithm is also covered by Shor's quantum algorithm that covers the hidden subgroup problem (http://en.wikipedia.org/wiki/Hidden_subgroup_problem) for finite abelian groups, so Diffie-Hellman and El-Gamal are no Good.
There exists cryptosystems that do not fall under this umbrella, based on "Learning with Error" (LWE - http://en.wikipedia.org/wiki/Learning_with_error) (that reduces to certain worst-case Lattice problems, cool stuff). For example http://eprint.iacr.org/2010/613.pdf

Recently even Fully Homomorphic Encryption based on solely on LWE was found: http://eprint.iacr.org/2011/344.pdf

Other problems that people have basing public key cryptography on that might not be exponentially faster with a quantum computer are "Subset Sum" (http://eprint.iacr.org/2009/576.pdf) and "hardness of decoding general linear codes" (http://en.wikipedia.org/wiki/McEliece_cryptosystem).

The topic is called "post-quantum cryptography" in litterature.

It took more than just seeing a couple of the token codes... Cryptanalysis of the Alleged SecurID Hash Function extended version: http://eprint.iacr.org/2003/162.pdf

256 bit AES was shown just over a year ago to have structural weaknesses that render it potentially crackable, better not take the bet.

http://eprint.iacr.org/2009/374.pdf

The next news you here on the subject will be someone who has implemented actual crack.

Here's the actual research paper if anyone is interested: http://eprint.iacr.org/2010/332.pdf

djb has released some stuff:

http://eprint.iacr.org/2010/623.pdf

No details at all, but .. certainly .. heh .. provoking. :)

That assumes that an 8-character password will contain 8 characters each equally likely to be any of 128 characters. If so, that would be an incredibly strong 8-character password, suitable for almost any application where SHA-1 would be used to hash a password.

In addition, this attack cannot (yet) be used where the original input to the hash function is unknown, so it wouldn't affect the use of SHA-1 for this purpose. (It does affect digital signature applications.) And the current status of this attack is that it has defects that may or may not be fixable -- so the attack may not even exist.

http://eprint.iacr.org/2009/259
(See the last paragraph)

What about http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.7206? Seems that fits your bill; in essence, there are certain statistical biases in many of the encryption schemes that can be calculated quite quickly.

See http://eprint.iacr.org/2002/149.pdf.

You (and the submitter) might want to have a look at http://eprint.iacr.org/2009/531 which talks about "known-key attacks" on "AES-like permutations". The goal of these types of attacks is to distinguish AES-encrypted data from random noise. Right now, all they can do is break 8 rounds of AES-128, so the answer to OP's question is "right now, AES-encrypted data is indistinguishable from noise".

---linuxrocks123

Feel secure again. Only a variant was broken.

The date of your document July 2008 precedes the successful decryption in October 2008.

Feel secure again. Only a variant was broken.

On the impossibility of cryptography alone for privacy-preserving cloud computing

The technique enables them to recover a full key by using a tactic known as a related-hey attack ...

Certainly you meant related-key attack since the paper by and large discusses related key attacks before explaining their sandwich attack.

These complexities are so small that we have actually simulated the attack in less than two hours on a single PC, and experimentally verified its correctness and complexity.

To give you more specific numbers from the conclusion of the paper:

By using this distinguisher and analyzing the single remaining round, we can derive the complete 128 bit key of the full KASUMI by using only 4 related keys, 226 data, 230 bytes of memory, and 232 time.

Er, I believe you meant to say 4 related keys, 2^26 data, 2^30 bytes of memory and 2^32 time. As you will see in the conclusion of the paper:

In this paper we develop a new sandwich attack on iterated block ciphers, and use it to reduce the time complexity of the best known attack on the full KASUMI from an impractical 2^76 to the very practical 2^32.

After all a time complexity of 232 should take any computer at most a few seconds while 2^32 approaches the two hour-ish mark.

Improvments to Craig's original work are already starting to come out. Smart and Vercauteren use integer arithmetic to obtain a more efficient scheme (though still not widly practical yet). Dijk, Gentry, Halevi and Vaikuntanathan show an even simpler (though not more efficient) scheme using integer arithmetics. In fact it's probably a good first paper to read for cryptographers interested in the area.

In light of these developments hardly a year since craig first released his results i see reason to hope for more improvments also towards efficiency (and basing the security on different and more common assumptions).

never the less for cloud computing applications where resource usage is carefully counted out and billed its hard to imagen such encryption technology being for a long time to come. neiche markets and applications could be another matter. for example something like a freenets/cloud where you can securely (privatly and correctly) farm out computation to be accessed from any client device with your key (for a comparable hit to performance). still, like freenet today the extent of the performance hit will most likely force it to remain generally unused for quite a while still.

Improvments to Craig's original work are already starting to come out. Smart and Vercauteren use integer arithmetic to obtain a more efficient scheme (though still not widly practical yet). Dijk, Gentry, Halevi and Vaikuntanathan show an even simpler (though not more efficient) scheme using integer arithmetics. In fact it's probably a good first paper to read for cryptographers interested in the area.

In light of these developments hardly a year since craig first released his results i see reason to hope for more improvments also towards efficiency (and basing the security on different and more common assumptions).

never the less for cloud computing applications where resource usage is carefully counted out and billed its hard to imagen such encryption technology being for a long time to come. neiche markets and applications could be another matter. for example something like a freenets/cloud where you can securely (privatly and correctly) farm out computation to be accessed from any client device with your key (for a comparable hit to performance). still, like freenet today the extent of the performance hit will most likely force it to remain generally unused for quite a while still.

Say File A is one block big. File A is publicly available on the server, not writable by users. Eve produces a SHA256 hash collision of file A

The whole point of a cryptographic hash function is that you're not supposed to be able to produce input matching a given hash value other than by brute force - that is, 2^N evaluations, where N is the digest size in bits. That's an ideal state - in practice, number of evaluations can be reduced, and this is also the case for SHA256, but for this particular scenario (finding a message corresponding to a known hash, rather than just any two messages that collide with a random hash), it is still way beyond the number that is practical for a successful real-world attack.

Does anyone know if there is any practical and non-quantum ENCRYPTION method that is potentially safe from quantum cryptanalysis?

There is research going on in that area. I haven't been following it, but I know about one article that touches the subject. I haven't read the article, but if you are interested in that kind of stuff, you could read it and tell us what you think. http://eprint.iacr.org/2009/391.pdf

Are one-time pads (assuming they could be copied around safely) proof against these techniques?

They are safe against eavesdropping the line. Of course you need to transport and store the pads safely, and correctly destroy them afterwards. Quantum cryptography is a way to exchange the pads safely almost on the fly. You are going to need a little bit of already exchanged pad in order to exchange more using quantum cryptography. If you have a few thousand bits already exchanged, you could use that with quantum cryptography to exchange a few millions of bits. And quantum encryption is more practical than quantum factoring.

Actually, /dev/random and /dev/urandom have their own, separate secondary pools that are fed off of a main pool when entropy is "depleted" in the second level pools. This is an area of research for us as well, since Linux's entropy estimation algorithm fails in situations where the timing deltas of entropy gathering events (IRQs and disk IOs) are actually predictable, so it's possible that the second level pools are not being refreshed at appropriate times.

If you write to /dev/urandom, it goes into the primary pool by tradition. This is what the rc scripts do on bootup with the random seed file on disk.

BTW, it's absolutely the wrong solution to get entropy from another source on the network (for many reasons, but one is that you can't do a secure HTTPS handshake without, you guessed it, unguessable random numbers). The whole point here is that we are looking for a way for 500 Linux instances on EC2 to have different entropy pools before the kernel completes boot. The only possible solution is for the hypervisor (Xen for Amazon) to provide a simulated HW RNG that pulls entropy from a real HW RNG or from an entropy daemon in the hypervisor.

The best way to learn about Linux RNG basics is Gutterman et. al. Analysis of the Linux Random Number Generator. Several of the issues they describe have been addressed, such as their PFS concerns, but their description of the entropy pools is still accurate.

He seems to be contradicting himself there - in CTR mode you can easily flip bits of the cyphertext then make a new MAC.

Your "attack" works against any plain hash used a MAC. Good MACs, like HMAC, are not vulnerable to such trivial tampering: because an attacker does not have the secret key used to construct the original MAC, he can't create a valid MAC for his modified ciphertext.

The paper the author is implicitly mentioning, by the way, is Hugo Krawczyk's "The Order of Encryption and Authentication for Protecting Communications".

No, the point is that the authorities can't (in practice) read the individual votes, only the sum of all the votes. This works because:

1. using certain encryption schemes, it is possible to calculate an encryption of the sum of the encrypted votes without knowing the decryption key;
2. it is further possible to set up an encryption system where no one party knows the decryption key but a number of parties (the authorities in this case) can cooperate to decrypt a message; and
3. the authorities can (collectively) be trusted enough to cooperate to decrypt the total, but not to cooperate to decrypt any individual vote; and

See, for example, this paper.

Other solutions to the problem involve authorities cooperating to ensure that votes are anonymous but they don't seem as elegant to my mind.

it is more difficult for two files of the same size to have the same hash by chance.

This is false. Case in point: the first MD5 collision announced by Wang and his team in 2004 affected 2 data blocks of the same size. More generally, all cryptographically secure hashing algorithms are designed to output a hash as random as possible, no matter what the input size is.

Yeah, it was stupid. On the other hand, it didn't require a costly reverse-engineering effort to find and fix the stupidity.

It was actually been posted already here somewhere, here is the description of Quantum based PKI: http://www.iacr.org/archive/crypto2000/18800147/18800147.pdf

If it gets easy to break because of quantum encryption, then no problem! There already exists a quantum version of public key encryption. What this means is that in ~30 years, every computer will need, at the very least, a quantum co-processor. No need to panic.
http://www.iacr.org/archive/crypto2000/18800147/18800147.pdf

MD5?

http://eprint.iacr.org/2006/105

I've a question: it seems that nanowire and nanotube are the same objects. In that case, nothing so new. See http://www.geobacter.org/ and a paper in the June 23, 2005 issue of Nature about the geobacter bacteria. I did a funny use of it during the rump session of CRYPTO 2005 at UCSB, see http://www.iacr.org/conferences/crypto2005/rumpSchedule.html "The geobacter attack: when nanotechnology meets chips" with the slides and the video.