Freak Posted May 29, 2020 Share Posted May 29, 2020 (edited) With the advent of quantum computers (and even the first claimed instance of quantum supremacy) there are innumerable crytosystems that will be obsolete in the coming decades or sooner. Asymmetric algorithms like RSA, ElGamal, and the Diffie-Hellman key exchange rely on the difficulty of the Integer Factorization Problem and Discrete Logarithm Problem, and are particularly vulnerable because of Shor's Algorithm. Shor's Algorithm is essentially a set of algorithms for solving the Hidden Subgroup Problem for certain groups (which is analogous to the previously stated problems) on a quantum computer in polynomial time. The arXiv paper on the Hidden Subgroup Problem does a full examination of Shor's algorithm, but it involves using a classical function in tandem with a quantum fourier transform applied as a logic gate to quantum registers in order to find the periodicity of the classical function. It is worth noting, however, that asymmetric cryptosystems are not the only ones vulnerable to quantum computers as there exists Grover's algorithm which is capable of reducing the time to break AES (though not to polynomial time complexity). There is some advanced math in the next paragraph, but even if you don't understand it, the example at the end should be easy to follow. Here I will examine only one potential algorithm which is suspected to be quantum resistant, however there are many more. The algorithm utilizes an abstract algebraic construct known as Lie groups (pronounced Lee). A Lie group could be summarized as a "smooth manifold that is also a group". Smoothness is a property in calculus meaning that it is differentiable at every point. A group is a set that also has a binary operation—an operation on two elements of the set to form a third—such that the properties of identity, invertibility, and associativity are satisfied. A manifold is topological space for which there exists a neighborhood around each point which is homeomorphic to Euclidean space. For a topological space: "Let X be a nonempty set, and let τ be a collection of subsets of X. We say that τ defines a topology on X if the empty set ∅ and X itself lie in τ, if the union of any family of elements of τ is again an element of τ, and if the intersection of any finite collection of elements of τ is also an element of τ. The combination of X and τ is called a topological space." The reason that Lie groups are important is because they are non-abelian or non-commutative, and for such groups there is no known solution to the hidden subgroup problem, and thus Shor's algorithm cannot break it. The algorithm relies on the difficulty of two problems. The (NAF) Non-Abelian Factoring problem and the (NAI) Non-Abelian Insertion problem. The NAF problem is to factor the product "exp(xS)*exp(yT)" into the pair (exp(xS), exp(yT)) where x,y are integers, and S,T are nilpotent matrices in the set of all nxn matrices with elements in the field Zp where p is a large prime number, and where exp denotes the matrix exponential which is computed with: Where n is the nilpotent index of the matrix. The NAI problem is to recover exp((a+c)S)*exp((b+d)T) from the pair (exp(aS)*exp(bT), exp(cS)*exp(dT)) which can clearly be easily solved if the NAF problem is solved. ------------------------------------- The public key consists of (p, S, T, ∆, H1, H2, H3) where ∆=exp(sS)*exp(tT) and s,t are random integers, and H1..3 are cryptographically secure hash functions. The private key consists simply of (exp(sS), exp(tT)) The algorithm is demonstrated below where I encrypt the word "this" and then decrypt it again. Here I've decided that H1..3 are the "identity hashes" which is to say that, since this is merely a proof of concept, I did not use hashes, and just made sure that the lengths of the relevant binary strings would be the correct length without them. The ciphertext is the collection of the 3 starred items on the first page. Edited May 29, 2020 by Freak Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now