5 ms·

Practical P=NP is a very real possibility (I am just testing a new algorithm) and (IMHO) not that scary. I am of the opinion that the advantages of P=NP far out

by js8 3y ago

Practical P=NP is a very real possibility (I am just testing a new algorithm) and (IMHO) not that scary. I am of the opinion that the advantages of P=NP far outweigh the disadvantages. People tend to focus on the latter, because that's the world we currently live in. Even if we focus on crypto only, from the perspective of people being oppressed around the world, it would be far better for them to be able to see what is being done by the powerful publicly rather than not. This is essential for transparency, which is essential for democracy. I don't reject the ideals of e.g. https://en.wikipedia.org/wiki/A_Declaration_of_the_Independence_of_Cyberspace https://en.wikipedia.org/wiki/A_Declaration_of_the_Independe..., but I believe that the technological solution through cryptography is not tenable, and if we got rid of cryptography, it would actually level the playing field.

GTP 3y ago
I'm not sure whether I agree or not, as without cryptography the only way to have a private discussion with someone, which I think is equally important to transparency, as people usually are "transparent" about personal stuff with close friends/family members only under the condition that other people don't have access to the information, would be to have such conversation in person behind closed doors. Which it isn't always easy, think people living far apart. Consider also that having no cryptography isn't by itself enough to have a transparent government: they can still lock important documents in a physically secure place and have a long jail sentence as a deterrent for people thinking about leaking them.
- js8 3y ago
  > Consider also that having no cryptography isn't by itself enough to have a transparent government: they can still lock important documents in a physically secure place and have a long jail sentence as a deterrent for people thinking about leaking them. But here you say that: Security can depend on social contract and not technology. But the same argument can be applied to your original objection. We can mandate (in the social contract) that people have the right to privacy. (And there are some analogs where we do that, for example, we could have Gattaca-like dystopia where people's access to health care is based on genetics, yet all developed countries have a ban on such discrimination.) I think it's far more dangerous that the government or adversary is technologically capable of being non-transparent than if ordinary people don't have capability to be non-transparent. It's because I believe power ultimately thrives on information asymetry, and the encryption only amplifies this asymetry.
  - red1reaper 3y ago
    I am going to be pedantic as i am perfectly aware that you do not mean it this way but here we go: > Security can depend on social contract and not technology. Social contracts are technology, laws are technology, law as a concept is technology, Society is technology.
    - js8 3y ago
      If you really want to be pedantic, you should recognize there is a difference between technology as implemented (the social contract as it's implemented now) and choice of technology (all the different ways how the social contract could be different, reflecting history and geography).
  - kientuong114 3y ago
    > It's because I believe power ultimately thrives on information asymetry, and the encryption only amplifies this asymetry. Quite the opposite, I find. In fact, the government has the infrastructure and political power necessary for surveillance of people. The reverse is definitely not true. Regardless, assume you are in an authoritarian state with a powerful state police: how would you even attempt fighting it if you do not have a way of coordinating with the other people being oppressed? How can you trust communications if the government can interfere?
    - js8 3y ago
      I simply don't believe that in an actual authoritarian state, private (Internet) communications are a neccessity for fighting back. I was born in Czechoslovakia, and if I look at what actual dissidents did, it seems that once your goal is to fight back, you just have to get used to that you're gonna be surveilled no matter what. Because if you want to convince many others that the system is oppressive, you will have to make yourself known. Vaclav Havel discusses some of the strategies in the Power of the Powerless, and it also goes to Gramsci, who observed that it's mostly ideology that keeps the systems of power. I think privacy is important in democracy, but if you're taking on an authoritarian state, that some police knows what you had yesterday for dinner, that's the least of your problems. To clarify: The harsh truth is, in an authoritarian state, the police doesn't really need your communications; they already know what you're up to: no good. That's enough for some of them to justify any action they want against you.
eru 3y ago
Sorry, this sounds like serious crackpot territory. Btw, if your polynomial algorithm for NP is any good, you should be able to break any encryption at all. The problem of breaking cryptographic systems is typically inside of both NP and co-NP. That intersection is suspected to be substantial smaller than NP by itself. (Of course, if it all collapses to P, that wouldn't make a difference.)
- js8 3y ago
  If everybody considers P=NP a crackpot territory, then it will never happen, by definition. On the contrary, I think to believe that the sets described by NP-complete instances are somehow inherently "undescribable" (as is implied by naturalization) is crackpottery also. But regardless, it's important to realize that modern cryptography relies on a hypothesis. It might be effectively true for now, but it might not in the future. > Btw, if your polynomial algorithm for NP is any good, you should be able to break any encryption at all. In theory, yes, in practice, there is a pretty big difference between "I think I just discovered how to do Gaussian elimination to solve linear equations" and "I can routinely solve sparse linear systems with millions of variables". Historically, it wasn't done by a single individual in a span of couple years.
  - eru 3y ago
    > If everybody considers P=NP a crackpot territory, then it will never happen, by definition. Oh, sorry, that's not what I meant to say. To be less vague, 'Practical P=NP is a very real possibility' is fine. 'Practical P=NP is a very real possibility (I am just testing a new algorithm)' is crackpot territory. > But regardless, it's important to realize that modern cryptography relies on a hypothesis. It might be effectively true for now, but it might not in the future. Different parts of modern cryptography rely on different sets of hypotheses. Eg the discrete logarithm problem being hard for some specific groups is one popular hypothesis. > In theory, yes, in practice, there is a pretty big difference [...] That's a valid point, but to make that point the approach you defend has to be more mathematically rigorous. Basically, if you say '(I am just testing a new algorithm)', then that algorithm better be fast in order to convince anyone. Otherwise, you say something like 'I'm working on a proof for my new approach.' or 'I'm working proving sub-exponential runtime for a new algorithm'. Ideally, if you don't want to be a crackpot, it helps to be well versed with the literature, and what has been done before and why it does or doesn't work. (The former is especially important, if you want to claim you have a new proof for P != NP, because researchers have already formally ruled out lots of different approaches; so you better be able to explain why your approach does not fall under any of the ones that have already been proven not to work.)
noitpmeder 3y ago
This is an insane take. If encryption is broken I _guarantee_ that the public will still be as in-the-dark as they are now. The government (and telcos) are the only ones who control the infrastructure needed to inspect this kind of traffic.
- js8 3y ago
  I am not suggesting that, in an encryption-free world, the advantage for the public is in being able to inspect all government traffic. Rather, it makes it easier for whistleblowers to bypass the government protections and get relevant documents that cover some atrocities. I really like Assange's essay on the topic, where he describes that every big operation requires a sort of paper or document trail (which is used to coordinate many people), and this fact makes whistleblowing always an option. However, I believe, encryption (and related things like trusted computing) helps to minimize the exposure of this trail even to internal actors, and in doing so, it makes whistleblowing more difficult.

by js8 3y ago

GTP 3y ago

I'm not sure whether I agree or not, as without cryptography the only way to have a private discussion with someone, which I think is equally important to transparency, as people usually are "transparent" about personal stuff with close friends/family members only under the condition that other people don't have access to the information, would be to have such conversation in person behind closed doors. Which it isn't always easy, think people living far apart. Consider also that having no cryptography isn't by itself enough to have a transparent government: they can still lock important documents in a physically secure place and have a long jail sentence as a deterrent for people thinking about leaking them.

js8 3y ago
> Consider also that having no cryptography isn't by itself enough to have a transparent government: they can still lock important documents in a physically secure place and have a long jail sentence as a deterrent for people thinking about leaking them. But here you say that: Security can depend on social contract and not technology. But the same argument can be applied to your original objection. We can mandate (in the social contract) that people have the right to privacy. (And there are some analogs where we do that, for example, we could have Gattaca-like dystopia where people's access to health care is based on genetics, yet all developed countries have a ban on such discrimination.) I think it's far more dangerous that the government or adversary is technologically capable of being non-transparent than if ordinary people don't have capability to be non-transparent. It's because I believe power ultimately thrives on information asymetry, and the encryption only amplifies this asymetry.
- red1reaper 3y ago
  I am going to be pedantic as i am perfectly aware that you do not mean it this way but here we go: > Security can depend on social contract and not technology. Social contracts are technology, laws are technology, law as a concept is technology, Society is technology.
  - js8 3y ago
    If you really want to be pedantic, you should recognize there is a difference between technology as implemented (the social contract as it's implemented now) and choice of technology (all the different ways how the social contract could be different, reflecting history and geography).
- kientuong114 3y ago
  > It's because I believe power ultimately thrives on information asymetry, and the encryption only amplifies this asymetry. Quite the opposite, I find. In fact, the government has the infrastructure and political power necessary for surveillance of people. The reverse is definitely not true. Regardless, assume you are in an authoritarian state with a powerful state police: how would you even attempt fighting it if you do not have a way of coordinating with the other people being oppressed? How can you trust communications if the government can interfere?
  - js8 3y ago
    I simply don't believe that in an actual authoritarian state, private (Internet) communications are a neccessity for fighting back. I was born in Czechoslovakia, and if I look at what actual dissidents did, it seems that once your goal is to fight back, you just have to get used to that you're gonna be surveilled no matter what. Because if you want to convince many others that the system is oppressive, you will have to make yourself known. Vaclav Havel discusses some of the strategies in the Power of the Powerless, and it also goes to Gramsci, who observed that it's mostly ideology that keeps the systems of power. I think privacy is important in democracy, but if you're taking on an authoritarian state, that some police knows what you had yesterday for dinner, that's the least of your problems. To clarify: The harsh truth is, in an authoritarian state, the police doesn't really need your communications; they already know what you're up to: no good. That's enough for some of them to justify any action they want against you.

eru 3y ago

Sorry, this sounds like serious crackpot territory. Btw, if your polynomial algorithm for NP is any good, you should be able to break any encryption at all. The problem of breaking cryptographic systems is typically inside of both NP and co-NP. That intersection is suspected to be substantial smaller than NP by itself. (Of course, if it all collapses to P, that wouldn't make a difference.)

js8 3y ago
If everybody considers P=NP a crackpot territory, then it will never happen, by definition. On the contrary, I think to believe that the sets described by NP-complete instances are somehow inherently "undescribable" (as is implied by naturalization) is crackpottery also. But regardless, it's important to realize that modern cryptography relies on a hypothesis. It might be effectively true for now, but it might not in the future. > Btw, if your polynomial algorithm for NP is any good, you should be able to break any encryption at all. In theory, yes, in practice, there is a pretty big difference between "I think I just discovered how to do Gaussian elimination to solve linear equations" and "I can routinely solve sparse linear systems with millions of variables". Historically, it wasn't done by a single individual in a span of couple years.
- eru 3y ago
  > If everybody considers P=NP a crackpot territory, then it will never happen, by definition. Oh, sorry, that's not what I meant to say. To be less vague, 'Practical P=NP is a very real possibility' is fine. 'Practical P=NP is a very real possibility (I am just testing a new algorithm)' is crackpot territory. > But regardless, it's important to realize that modern cryptography relies on a hypothesis. It might be effectively true for now, but it might not in the future. Different parts of modern cryptography rely on different sets of hypotheses. Eg the discrete logarithm problem being hard for some specific groups is one popular hypothesis. > In theory, yes, in practice, there is a pretty big difference [...] That's a valid point, but to make that point the approach you defend has to be more mathematically rigorous. Basically, if you say '(I am just testing a new algorithm)', then that algorithm better be fast in order to convince anyone. Otherwise, you say something like 'I'm working on a proof for my new approach.' or 'I'm working proving sub-exponential runtime for a new algorithm'. Ideally, if you don't want to be a crackpot, it helps to be well versed with the literature, and what has been done before and why it does or doesn't work. (The former is especially important, if you want to claim you have a new proof for P != NP, because researchers have already formally ruled out lots of different approaches; so you better be able to explain why your approach does not fall under any of the ones that have already been proven not to work.)

noitpmeder 3y ago

This is an insane take. If encryption is broken I _guarantee_ that the public will still be as in-the-dark as they are now. The government (and telcos) are the only ones who control the infrastructure needed to inspect this kind of traffic.

js8 3y ago
I am not suggesting that, in an encryption-free world, the advantage for the public is in being able to inspect all government traffic. Rather, it makes it easier for whistleblowers to bypass the government protections and get relevant documents that cover some atrocities. I really like Assange's essay on the topic, where he describes that every big operation requires a sort of paper or document trail (which is used to coordinate many people), and this fact makes whistleblowing always an option. However, I believe, encryption (and related things like trusted computing) helps to minimize the exposure of this trail even to internal actors, and in doing so, it makes whistleblowing more difficult.