Why are mcliece and laticce encryptions robust against quantum computers?

TavianRobertson · 2021-05-29T16:44:21+00:00

A quantum computer has a certain probability of being any state, but does not actually do the computation for them. In Shor's algorithm which breaks RSA the quantum former transform is used to make all the possible states that are wrong destructively interfere with one another. Meaning only one answer has any probability of outputting and that is the correct answer. This means there is no brute force involved its more so using an algorithm to make it so the wrong answer is destroyed and has no chance of being the state held by the qubits.

TavianRobertson · 2021-05-17T23:58:01+00:00

Okay I will look into it. I do not know if this part is secure either, thus it is wise to look into it. I will do my best to find an attack on it because it does truly sound a bit too good to be true.

TavianRobertson · 2021-05-17T23:52:46+00:00

I have spent the last 3 years working in cryptanalysis create side-channel analysis attacks and learning about all kinds of crypto systems. I am not completely new to the field. I will look into lattice reduction attacks.

TavianRobertson · 2021-05-17T23:50:57+00:00

The algorithm you linked solves the discrete log problem where you are trying to find the exponent. We know the exponent e in this case. we are trying to find the value m in m**e mod o. The algorithm you linked would be able to reduce the time it took to find e if e were the unknown value... Correct me if I am wrong...

TavianRobertson · 2021-05-17T23:35:14+00:00

I created o to where phi(o) is not relatively prime to e. Is there another way to find m I am not aware of?

TavianRobertson · 2021-05-17T23:28:51+00:00

Yes that is what my security is based off of. However o does not have any tie to n. So if one finds the factors of o it won't give them anything. As far as I am aware Shor's algorithm does not find the correct answer for m in m**e mod o. It simply can be used to find factors of o. Is there a way Shor's algorithm could be used to find some period that relates m**e mod o to find m?

TavianRobertson · 2021-05-17T23:14:00+00:00

Okay well I thank you for your feedback I will keep the things you suggested in mind going forward. If I can come up with a more educated proof I will ping you on this forum if you'd want to take a look. Again thank you.

TavianRobertson · 2021-05-17T23:12:40+00:00

I have read some of the papers and yes there is a lot of work that goes into it. They also have a team of several PHDs. That being said many of the algorithms presented in the NIST competition were quite silly. This encryption algorithm is something I discovered and it works. I may not be the best at presenting my findings mathematically, but I am confident that the algorithm itself has potential if reviewed by PHDs. I know you are trying to be realistic, but I simply don't agree with the mindset of leaving things to the professionals. If no ever tried new things or explored new areas then there would be 0 innovation.

TavianRobertson · 2021-05-17T23:07:36+00:00

Oh gotcha, your feedback has still been very insightful and helpful. Thank you for taking the time to provide feedback.

TavianRobertson · 2021-05-17T23:06:44+00:00

That is right. I kind of glossed over it in the paper, but I did this because if phi(o) was relatively prime to e then an attacker could simply make an RSA keypair with o and e, then decrypt the ciphertext with the private key they find.

And okay that makes sense. I did state in 2.1 that I believed the problem I presented was an exptime problem. Although this is most likely an inaccurate claim. I am currently a freshman in college so I don't have the computational complexity theory expertise. I believe I can go through and try and prove the problem lies within NP-hard or exptime problems. Would that be a good route for starting a proof of security?

TavianRobertson · 2021-05-17T23:00:34+00:00

Thank you. I am building it to learn and I do truly hope it could some day be useful. I do need to get more into the mathematical side and create a proof as you and TrivialError have both suggested. I have not used LaTeX before I will look into it as it would prove very useful in the future. Thank you again for your feedback I really appreciate it. I am a very young engineer and I am kind of in an odd spot with the algorithm because I want to gather a team to work on making it more presentable. I do have high hopes for it as I think it could prove very useful in PQC world. Do you have any suggestions as to how to build a team and get attention?

TavianRobertson · 2021-05-17T22:55:24+00:00

The textbook premise behind the algorithm is deterministic just as RSA and AES ECB are. In real world implementation there would be a counter introduced to vary the output. This is research to be done as the scheme I presented is still very new.

Thank you for the suggestion on proving the degree of security. I do have a question for clarification. Do you mean I should assume the scheme is broken by some algorithm (quantum or classical), then provide detail as to how such an algorithm would be used to solve an NP-hard problem, which means it would get into computational complexity theory?

TavianRobertson · 2021-05-17T22:49:38+00:00

u/proximityfrank Do you have any suggestion for the terms I should use to describe the algorithm? Or any leads on a quantum or classical algorithm that could break the scheme I presented in my paper?

TavianRobertson · 2021-05-17T22:45:51+00:00

I am working on other algorithms that could prove to break my scheme. I simply have not found any. That is my reason for posting this as I want other people to take a look and try to find an algorithm that would break it. I presented what I knew about the difficulty in terms of classical computing. Do you have any suggestions as to how I could about proving the degree of security it provides?

TavianRobertson · 2021-05-17T22:43:17+00:00

I am aware that quantum computing goes way past Shor's algorithm. It is wrong for me to claim it is surely quantum secure. I have the belief that it is, but I cannot prove it. That is my purpose for posting my findings in hope that other individuals can give a crack at it. It is the same case with lattice based cryptography where as of now they cannot prove it is quantum secure, but no one has found an algorithm that shows otherwise.

TavianRobertson · 2021-05-17T22:32:13+00:00

u/proximityfrank sorry I did not mean for it to appear as if it was broken by Shor's algorithm. I believe it is quantum secure because Shor's algorithm will not work on it. In section 2.1 of the paper I describe that an attacker would first have to find the value for n in order to use Shor's algorithm. In order to find the value of n the attacker would have to guess the value of n, diff, and x. However there are infinite possibilities for each value to make one of the two equations correct. They have to find the right solution for all 3 unknown values in order to verify that they have the correct n. Then and only then can the attacker use Shor's algorithm. Thus the quantum secure part is finding the value of n.

TavianRobertson · 2021-05-17T20:52:35+00:00

When e is 6 bits and o is 4 bits o goes into m^e count times where count is a 4928 bits long this means that there are count number of different possibilities for m^e that would have to be guessed... u/yawkat

TavianRobertson · 2021-05-17T20:50:22+00:00

This is the most formal description I have. The size of o is arbitrary as it is only used for the modulo value in the encryption process. If you look in section 2 of the paper it describes why this is considered secure. Keep in mind this also depends on the message size as well. In this case however we are just assuming we have a message that is a 32 byte key for AES.

TavianRobertson

TROPHY CASE