3 ms·

I'm sorry to be slightly short of knowledge here, but could you elaborate on why encryption algorithms don't rely on the fact that brute force is physically not

I'm sorry to be slightly short of knowledge here, but could you elaborate on why encryption algorithms don't rely on the fact that brute force is physically not meaningful? And indeed, it goes without saying that if we follow the same computational paradigm, we might just as well scale up the values that we currently use. My question was more around what if computational paradigms change. As the example you mentioned, the problem becomes solvable in polynomial time. What could be the basis of the next generation of encryption/hashing?

BertMacklin 10y ago
> could you elaborate on why encryption algorithms don't rely on the fact that brute force is physically not meaningful I didn't mean that the infeasability of brute forcing an encrypted text is not useful, I was rather suggesting that it is precisely the definition of encryption. I was trying to differentiate between: 1. Using brute force method to convert an encrypted text to the original text without considering the encryption method. This is an inherent property of encryption, and does not pose a problem as you can scale up encrypted values to make brute-forcing infeasible on the fast computers * 2. Breaking the algorithm instead. > As the example you mentioned, the problem becomes solvable in polynomial time I think the issue in the example is not that the computing methods changed, but that the particular algorithm we use for encryption (prime factorization) has a polynomial solution on those computers. The point is that this shift in computing does not break all the encryption algorithms, there are other algorithms you can use that don't have a known solution (yet): https://en.wikipedia.org/wiki/Lattice-based_cryptography https://en.wikipedia.org/wiki/Lattice-based_cryptography. * All of this is assuming that everyone has access to the same class of computers. Obviously if someone gets their hands on a drastically faster computer while everyone else is still using smaller keys/prime numbers, then you have a problem.

BertMacklin 10y ago

> could you elaborate on why encryption algorithms don't rely on the fact that brute force is physically not meaningful I didn't mean that the infeasability of brute forcing an encrypted text is not useful, I was rather suggesting that it is precisely the definition of encryption. I was trying to differentiate between: 1. Using brute force method to convert an encrypted text to the original text without considering the encryption method. This is an inherent property of encryption, and does not pose a problem as you can scale up encrypted values to make brute-forcing infeasible on the fast computers * 2. Breaking the algorithm instead. > As the example you mentioned, the problem becomes solvable in polynomial time I think the issue in the example is not that the computing methods changed, but that the particular algorithm we use for encryption (prime factorization) has a polynomial solution on those computers. The point is that this shift in computing does not break all the encryption algorithms, there are other algorithms you can use that don't have a known solution (yet): https://en.wikipedia.org/wiki/Lattice-based_cryptography https://en.wikipedia.org/wiki/Lattice-based_cryptography. * All of this is assuming that everyone has access to the same class of computers. Obviously if someone gets their hands on a drastically faster computer while everyone else is still using smaller keys/prime numbers, then you have a problem.