Learning with errors: Encrypting with unsolvable equations 

Linear algebra is not absurdly difficult. It’s high school level, at least in all high schools except in the US perhaps.

@@kosterix123 in all first world* high schools may be bro

I would assume it would depend on how big the error is. In the example with 44, if you sum the equations then you also sum the errors, and if the summation of errors gets you closer to 44 than to 0 (meaning >= 22) then it seems like it would become difficult to tell a 0 and a 1 apart. Since there are 10 equations in her example, if the errors are randomly generated and the equations they select are also randomly generated, then the error range could not be greater than +/- 2 because otherwise it would be technically possible (although highly unlikely), let's say it was +/- 3 that the private key holder's random number generator spit out 3 as the error for every equation and the public key holder's random number generator select to use every single equation, and the total error would be 30, making a 0 they encrypt falsely read as a 1 since it would be closer to 44 than to 0. That would mean you could make it absolutely impossible to run into such a scenario if, given m is the modulus and n is the number of equations in the public key and the +/- range of our error is e, that e < ⌊m/n/2⌋. I don't have any idea if this is how they actually do it but if this is satisfied it would not be possible in even the worst case scenario for the error to ever be too great to cause incorrect decryption. You could probably also just verify the errors aren't too large in the worst case and regenerate them if they are.

can you explain how?

I guess it's possible, but the receiver can always ask for a new point until the data is transmitted successfully. Thou I'm not sure if this can be exploited so the real lattice points can be eventually found.

GGH can be reduced to a special case of the closest vector problem, which makes it insecure. But in general the closest vector problem is thought to be a secure basis for cryptography

@@chalktalkmath GGH signatures are insecure but I don't think it reduces to a special case of CVP. The idea is that if you observe a bunch of signatures, then you can recover the fundamental domain of the good basis. This can actually be fixed with SIS and a version of Babai's nearest plane algorithm that is not deterministic. GGH encryption is not insecure afaik (but not really used).

Q is pubilcly known, but it doesn't mean that there are only two answers. The result of an equation can be any number, and that number mod 89 can go from 0 to 88, and to that number, 44 is added. the resulting number sent back to alice can be anything from 0 to 88, yes you added 44, but it doesn't mean that it's going to be closer to 88 or 0 since you are counting in mod 89. Since the equations chosen to mesh together by bob are random, the attacker doesn't know what that number should have been before adding 44 to it.

@@celivalg thank you for this answer, I assume when actually implementing this, new equations are to be made public everytime a new message is to be encrypted?

@@EastSideGameGuy I don't know for a fact, but I assume that this isn't the case, at least they don't need to. Here she showed it using a 4 dimensional vector, but imagine using a n dimensional vector, and sending thousands of equations, with Bob encrypting his message using dozens of equations. The shear combinations that makes are huge and an attacker won't be able to guess that in a reasonnable time. Now, I doubt they actually store those equations between communications, rather I think the base vector stays the same, but the public key can be regenerated from those at random between different communications. But I don't think they need to. Remember that the equations themselves don't allow to get the base vector, and that base vector might be 1024 dimensional. So no random guessing.

All symmetrical ciphers like AES and ChaCha20 are because they are not based on the discrete logarithm problem. Only asymmetrical cryptography is.

@@amihart9269 I appreciate that answer, and I understand why you gave it and where it comes from.... but strictly speaking its not what I asked. I still dont know if quantum algorithms can crack AES any faster than a traditional computer.

@@leesweets4110 I'm not an expert, but from what I read online, quantum algorithms shouldn't be able to crack AES. I've read there are some attacks that can reduce the cracking time with conventional computers, but you can just use a longer key to avoid those. That's not the real problem though. AES being secure doesn't solve the problem of online cryptography. You won't be able to communicate securely with people you don't know and don't have a pre-shared-key with. That's the real problem that public-key-crypthography solved. Meaning you won't be able to order stuff online or do online payments. That said nobody knows what algorithms are possible with quantum computers. So maybe everything can be cracked using a quantum computer. Maybe our understanding of the quantum phenomena is incomplete and cloning quantum information is possible, so even quantum cryptography is vulnerable. I highly doubt that though.

256bit AES is considered post-quantum given the best known quantum algorithms. 128bit AES is post-quantum for the "medium term."

@@MadocComadrin I dont believe the size of the number is relevant...

My guess is that in a real world scenario you would randomly pick the equations to sum and there would be a lot of them. So they could theoretically compute all possible combinations but if there's let's say 64 different equations then they'd have to compute about 18 quintillion unique combinations.

The proof of its hardness related to lattice problems (approximate Shortest Vector Problem in particular) isn't straightforward, so it makes sense it might appear easy at first.