damarquis
damarquis on Hacker News
I like the design. However, save draft button is not working for me.
A fast algorithm for parity would be interesting. There is currently no better way to compute parity than factoring N.
There is a well known hand wavy-argument that computing any function on the prime factors of arbitrary integers should be difficult. Very roughly the idea is that if you can compute such a function over the integers you can probably also compute it over other rings. Applying it over certain number fields would let you get information about the low bits of the prime factors which is thought to be hard.
There is a bit more information given in Terrence Tao's answer here
http://mathoverflow.net/questions/3820/how-hard-is-it-to-com...
His answer is about counting the number of distinct prime factors but I think that it can extended to the parity of this value as well.
"..that many people suspect of being compromisable by NSA etc."
If it was a backdoor you certainly can't count it among the NSAs successes. It is never used.
I agree this is a good idea but I think using the words "encrypt" and "decrypt" confuses the goal a little bit as this idea is still useful even if the message aren't required to be confidential form anyone. I think "encapsule" and "release" describe it better. These operations can be used in combination with encrypt and decrypt if encryption is needed.
"So post a PGP key and say, if you really want anonymity, use this."
PGP only provides confidentiality, not anonymity. To get anonymity as well would require TOR.
The only reason to use one-time pads is an extraordinary level of paranoia. If you are paranoid enough to need a one-time pad then it makes little sense for you as a private citizen to trust that hardware you take into public places hasn't been compromised. Manual creation and transmission of the encrypted message is the only approach that makes sense.
If lots of people adopted one-time pads it might hinder NSA et al but this would be akin to trying to convince people to wear masks whenever they are in public to hinder monitoring with CCTV.
I think it is mainly a logistical issue. The problem is that encryption keys are a single point of failure. IT practices at most businesses would have to be very rigorous before a design with a single point of failure for any significant part of the IT infrastructure could even be remotely considered.
Changing business practices to decrease the risk of using end-to-encryption to an acceptable level has an associated cost which, at most companies, probably dwarfs the cost of its technical implementation.
Nitpick: RSA isn't known to be backed by factoring. More precisely, there is no proof that if textbook-RSA encrypted messages could be decrypted quickly that integer factorization could also be done quickly. (Of course if you can factor integers you can decrypt RSA messages quickly).
http://en.wikipedia.org/wiki/RSA_problem
There are encryption schemes where decyption of an encrypted message is provably equivalent to factoring.
http://en.wikipedia.org/wiki/Rabin_encryption
The author's argument is that the probability of impact on ECC of this line of research is less than probability of an impact on factoring. Post-quantum cryptography has to avoid ECC since the elliptic curve discrete log problem is easily solved by quantum computers.
Regarding the possible solutions other than ECC: There are no hash-based encryption schemes, only hash based signatures. I believe there is little faith in any multivariate scheme to remain secure under serious scrutiny. Many such schemes have been broken. The outlook on lattice cryptography, and some coding theory based schemes is slightly more positive. Apparently ECC has received much more attention and study than either of these.
It makes no sense to argue that a non-existent product is vulnerable to a current exploit without a precise definition or specification of that product.
Its an obvious mistake but not so obvious that the author can't get away with choosing to make it.
Don't forget that when decrypted the result must match the operation performed on the corresponding plaintexts.
I don't see a reason this argument would apply to simulated rape but not simulated murder. A large number of people enjoy watching realistic simulated murder in movies, in TV, and in video games.
Your argument predicts that murder rates would rise after the arrival of the internet as people who enjoy simulated murder use online echo chambers to validate their belief that murder should be acceptable (it's highly unlikely that they are watching simulated murder for pleasure).
Except murder rates haven't risen since the arrival of the internet.
Why?
Of course anyone can follow you in public, the alternative would be impossible to enforce.
The problem is that the cost of getting that data could be made unacceptably low. For example, I think most people would object having their government uploaded their coordinates to a public website. The interesting question is what is the right tradeoff between transparency and cost.
You are comfortable relying on stalkers not being persistent enough to search a list, save some metadata, and use google maps?
"you don't need scientific evidence to know"
"but it seems as intuitive"
Knowledge can come only from reasoning based upon observations. You cannot know anything by intuition. You can believe your intuitions and feel that they must be true, but you cannot know they are true.
I love some of the SO sites but they have a lot of communities that have been lingering in beta limbo for ages.
I would be interested in more detail on how they reached the conclusion that pump priming is not useful. Do you have a link?
It is not clear that's what it is being said.
I'm not arguing that there aren't situations where then spreading the belief that their capabilities are less than actual would be a good thing. If the goal is to break a specific subset of all encrypted messages then this is exactly what they would want.
But there are also situations where they would want the opposite. For example, suppose the NSA has no advantage in breaking RSA over public knowledge, but can easily break NTRU and their goal is to read as many encrypted messages as possible. Then if they can get everyone to believe they can break RSA but not any cryptosystem based on lattices then some people will switch to NTRU. Now its much cheaper for the NSA to achieve their goal of breaking lots of encrypted messages since they have a very efficient algorithm for reading NTRU encryptions.
(This belief could be spread simply by having an "anonymous but very senior" official talk to Wired about how the US government has made a major step towards building the first scalable quantum computer)
In short, what they should want the world to believe depends on their capabilities and goals. Without knowing those anything is possible.
Cryptography software is
usually critical but I think unlike the code for planes and nuclear power plants it doesn't necessarily have to be. Typically cryptography software is advertised as secure against an adversary has unlimited resources. However, the designers of the software can choose whatever threat model they want as long as they make that clear to their users.
I am thinking of a disclaimer like "We believe our product is secure enough that the minimum cost for to an adversary to decrypt a message is at least $ 10^k" for some k and the cost is an estimate of the total cost of factors like number of hours of cryptanalysis, number of cycles, etc.
This way, if the code is found to be completely broken at some point then the error is considered relative to the level of security the designers intended.
Anonymous sources might be supplying real information but they could also be trying to manage beliefs.
Undoubtedly the NSA is ahead of everyone else in cryptanalysis but I think it is also advantageous for the NSA to have foreign governments think the NSA has a bigger lead than they actually do. This belief would cause foreign governments to use larger key sizes, and so drive up their costs, or switch to less well tested encryption methods that the NSA might be able to break.
"it's just a matter of time before RSA offers zero security"
This is not the only possible outcome. Scalable quantum computing could turn out to be impractical due to cost. Or new physics could be found that rules out scalable quantum computing. Personally, I find both of these outcomes unlikely, the second more than the first, but they do exist.
So either the NSA wanted a backdoor, in which case we learn that even the NSA can't build a backdoor that academic cryptographers can't detect.
Or, much more likely I think, it was just a project that some NSA employees had sitting around and they wanted to get something out of it. In that case we learn that the NSA isn't so far ahead of academic cryptographers that their designs will always be better.
Either way I don't find this as scary a story as Schneier does.
I agree that if the game is fun people will play it. The problem is getting them to try the game for long enough to know if it is fun. Popularity is obviously a factor in achieving that since lots of people associate mass marketed products with blandness, juvenility, etc.
The camp of people are both feminists and who care about making arguments based on good science called to say they want you to stop pretending they don't exist.
AES yes, PGP no. Anything based on the difficulty of discrete logs is done for. There are 2 types that remain secure, schemes based on the difficulty of solving problems in lattices and problems in coding theory. Lattice based cryptography is particularly interesting since all known fully homomorphic encryption schemes use it. If this remains the case, and if FHE matures faster than quantum computers (and it actually has been as far as I can tell) that everyone will switch to lattice based cryptography making quantum computers a little less useful and interesting.
I believe it has even been proved that for most computational problems quantum computers cannot give an exponential speedup.
The a video of the talk those slides are from is online
http://vimeo.com/18417770Worth watching even if you don't care much about DNSSEC, Bernstein is a good speaker.
Cryptographers seem to have a thing for misleading names. A big one is "provable security" which really means "is at least as hard as another more old and famous problem that we are all guessing is hard to solve efficiently." In any case "provable security" alone is often too difficult to prove so more assumptions are added to make the proof go through. Saying you've obtained provable security under some assumptions doesn't sound very good though, so the assumptions are called "models" instead.
I agree that all the short term updates don't have relevance to larger issues. However, if discovering the truth about what the government is doing does matter to you then Snowden's long term fate should be important. There are likely a few people in government agencies contemplating leaking vital information about these programs. The extent to which the US government can make the rest of Snowden's life unpleasant will determine what they do.
I would love if all filenames were human readable but it seems like too many people have a great desire to use bad scripts that can't handle spaces.