Millennium Breakthrough — Automatski Destroys “All” Lattice Based Cryptography.

Sep 20, 2019 · 5 min read

What is Post Quantum Cryptography?

Post-quantum cryptography (sometimes referred to as quantum-proof, quantum-safe or quantum-resistant) refers to cryptographic algorithms (usually public-key algorithms) that are thought to be secure against an attack by a quantum computer or by any conventional means.

What are the common types/flavours of PQC?

- Elliptic curves

- Lattices (***)

- Isogenies (***)

- Multivariate

- Codes

- Hash Functions, and

- Hybrids

*** Primary Focus at Automatski in terms of cryptography implementations.But in terms of breaking cryptography we break any and all cryptography any day any time.

What is Lattice Based Cryptography?

A lattice L is a discrete additive subgroup of Rm. It can be generated by integral combinations of , say n, linear independent vectors b1, . . . , bn in Rm, and the n vectors constitute the basis of the generated lattice.

The discreteness of lattices implies that there exists a nonzero vector with the smallest non-zero Euclidean norm in each lattice, denoted as λ1, and a lattice vector closest to a given target vector t in Rm. Finding the two special lattice vectors leads to the two famous computational problems regarding lattices:

Shortest Vector Problem (SVP): Given a lattice basis, find the shortest nonzero vector in the lattice;

Closest Vector Problem (CVP): Given a lattice basis and a target vector, find the lattice vector closest to the target.

The CVP has been proved to be NP-complete by van Emde Boas under Karp/Cook reduction in 1981 and refined by Micciancio and Goldwasser in 2002.

However, it is not known whether the SVP is NP-hard until 1998 when Ajtai proved the NP-hardness of SVP through randomized reduction.

The two main problems SVP and CVP are of prime importance to the cryptography in recent years. A variety of public-key cryptosystems are proposed in recent years, and their security is as hard as solving the worst-case hardness of the variants of SVP and CVP, which paves a way for the proposal of many lattice-based cryptosystems.

These newly-proposed schemes are said to be promising candidates for the post-quantum cryptography, which are believed to be secure against the attack of the quantum computers, even though algorithms on quantum computers have made widely-used cryptosystems nowadays based on factorization and discrete logarithm insecure again as forwarded by Shor in 1994. Therefore, the algorithms solving the two main problems are quite important for the research community.

What is learning with errors?

The learning with errors problem (LWE) is included in the lattice based cryptography.

The LWE problem is versatile (it can be used to construct a variety of cryptographic algorithms, shown above).

Despite the extremely complex math needed in both optimizations and security proofs for lattice cryptosystems, the foundational ideas only require basic linear algebra. Suppose you have a system of linear equations of the form

Solving for `x` is a classic linear algebra problem that can be solved quickly using Gaussian elimination. Another way to think about this is that we have a mystery function,

where given a vector `a`, we see the result of `ax`, without knowing `x`. After querying this function enough times we can learn `f` in a short amount of time (by solving the system of equations above). This way we can reframe a linear algebra problem as a machine learning problem.

Now, suppose we introduce a small amount of noise to our function, so that after multiplying `x` and `a`, we add an error term `e` and reduce the whole thing modulo a (medium-sized) prime `q`. Then our noisy mystery function looks like

Learning this noisy mystery function has been mathematically proven to be extremely difficult. The intuition is that at each step in the Gaussian elimination procedure we used in the non-noisy case, the error term gets bigger and bigger until it eclipses all useful information about the function. In the cryptographic literature this is known as the problem (LWE).

The reason cryptography based on LWE gets called lattice-based cryptography is because the proof that LWE is hard relies on the fact that finding the shortest vector in something called a lattice is known to be NP-Hard.

Conclusion

So What Have We Achieved? We have solved CVP, SVP and LWE Deterministically. Which means we can specifically crack “ALL” Lattice Based Cryptography.

And generically “All” existing and future possible Cryptography in the world as described below, earlier.

Now What?

Its a strange world. We have always presented all our inventions alongside ample independently verifiable proof. And we also offer private demos to ‘qualified’ prospective customers at anytime.

Yet people call our inventions a hoax. Push us to disclose our algorithms , part with our source code, publish academic papers, file patents and other nonsense, which basically means public disclosure of our hard work and inventions, which we are not interested in. So we have decided that we won’t try too hard. Its not worth it. We will be able to do reasonable business and won’t become Google which ideally we should be 100X times of by now.

So? We will let the world go ahead with their implementations. And we will keep the liberty of breaking any and all systems at anytime as per our exclusive discretion and will. How does that sound? Fair! Right??? ;-)

This is our website

Written by

More From Medium

More on Quantum Computing from Its42

Apr 4 · 6 min read