Cryptographic attacks as minimization of degree 4 polynomial

[jarekduda]

Cryptography is based on reason-result chains like hash functions: which are inexpensive to propagate in the intended direction, but seem hard to reverse. However, decomposing them into satisfaction of simple (direction-agnostic) relations like 3-SAT clauses, may bring a danger of existence of methods being able to effectively propagate this information also in the opposite direction, e.g. to reverse a hash function (?)

For example it turns out that 3-SAT problem can be translated into minimization of multivariate degree 4 real polynomial ( https://arxiv.org/pdf/1703.04456 ), allowing to take the search from discrete {0,1}^n final set of boolean values, inside its continuous [0,1]^n hypercube, exploiting (inexpensive) local gradients depending on the entire problem and leading toward a near minimum.
Specifically, 'x or y or z' can be translated into zeroing of
(x+y+z-1)^2 (x+y+z-2)^2 (x+y+z-3)^2
degree 6 polynomial. Sum of such polynomials over all clauses (using 1-x instead of x for negated variables) plus sum of x^2 (x-1)^2 over all variables to enforce final boolean values, gives a nonnegative polynomial which is zero if and only if all clauses are fulfilled. This degree 6 can be reduced to 4 (minimal nontrivial) by introducing one additional variable per clause.

Any Turing machine can be translated into a set of 3-SAT clauses: into a problem of finding values for variables such that all alternatives of triples of binary variables (like x or y or z, variables can be negated) are satisfied. For transformations based on OR, AND, XOR, SUM and permutations (like standard hashes and symmetric cryptography) this translation is straightforward.
So we could for example translate a hash function into a set of 3-SAT clauses, fix a final bit sequence and ask for the initial bit sequence leading to this final value. Then translate this 3-SAT into degree 4 polynomial, and e.g try gradient descent from multiple random initial points, or some more sophisticated numerical optimization (e.g. adding laplacian for smoothening).
Reaching the global minimum: zero, would mean finding a collision (or satisfying nonce for bitcoin mining).

Efficient 3-SAT solving could also break e.g. symmetric cryptography: find the only key for which decoded block contains correlations (wrong keys should lead to i.i.d. Pr(0)=Pr(1)=1/2). Or asymmetric by decomposing numbers (RSA) or solving discrete logarithm (ECC).
However, hashing seems simpler as there is often only a single way to reverse its reason-result chain, and this way should be suggested by gradients of the minimized polynomial (?)
If so, for protection there could be used some complexity barrier: elongating this reason-result chain.

The question is if could lead to essentially faster collision search (or proof-of-work in bitcoin mining) than brute force - exploiting the original reason-result chain in the opposite direction?
Have you seen this kind of cryptographic attacks - like through a continuous optimization of a polynomial?

 

[Baluncore]

Cryptography is based on reason-result chains like hash functions: which are inexpensive to propagate in the intended direction, but seem hard to reverse. However, decomposing them into satisfaction of simple (direction-agnostic) relations like 3-SAT clauses, may bring a danger of existence of methods being able to effectively propagate this information also in the opposite direction, e.g. to reverse a hash function (?)

A hash function greatly reduces the amount of information present, but comes with provision for collision resolution. A hash cannot be reversed because information has been lost in the hashing process. If information was not lost, there would be no advantage in using the hash function.

A code reduces the volume of information by replacing expected common phrases with shorter sequences. It is a compression technique that can be reversed given the code book. Cryptanalysts “recover” an enemy's code book by finding alternative sources of the same communicated information and working away over time.

An encryption does not reduce the amount of information present. Given the key it can be reversed. Without the key, there is an enormous search tree requiring a lifetime to search, many possible messages may be found but it is often hard to tell which was the original. Any encryption is breakable if it is simple enough and you know the algorithm but not the key. It is the size and the factorial number of permutations that will protect the message for a some time.

Have you seen this kind of cryptographic attacks - like through a continuous optimization of a polynomial?

Yes. But it quickly bogs down due to the factorial time required. Secure encryption employs repeated multiplication, or the XOR function, because that is non-linear, so is divergent and very hard to reverse.

 

[jarekduda]

A hash function greatly reduces the amount of information present, but comes with provision for collision resolution. A hash cannot be reversed because information has been lost in the hashing process. If information was not lost, there would be no advantage in using the hash function.

Basically you are right: even hashing a sequence shorter than the hash length, it couldn't be directly reversed as e.g. SHA-256 increases (padding) it to 512 bit block first to finally produce 256 bit hash.
However, (probably wrongfully) assuming existence of efficient 3-SAT solver, realizing the hash as 3-SAT formula with fixed finally value and more than 256 zeroes in the input (padding), there usually should exist only a single way to fill the remaining bits - solving the 3-SAT problem would reverse the hash.
Intuitively, such solver would need to propagate the information backward: from the output to input ... what the gradient descent seems to do (translating to minimization of polynomial).
But sure, for longer sequences we can only think about collision attacks - finding a different sequence (maybe fulfilling some constraints), which leads to the same hash.

An encryption does not reduce the amount of information present. Given the key it can be reversed. Without the key, there is an enormous search tree requiring a lifetime to search, many possible messages may be found but it is often hard to tell which was the original. Any encryption is breakable if it is simple enough and you know the algorithm but not the key. It is the size and the factorial number of permutations that will protect the message for a some time.

The real question is existence of a smarter way than such brute force search among all possibilities.

Sure it seems too good to be true, but formulation as minimization of degree 4 polynomial might have a potential to be a smarter way ... at least comparing with the brute force.
One example of brute force is testing many random {0,1}^n boolean points.
Polynomial minimization formulation could take many random initial points in let say [1/4,3/4]^n, perform a few steps of gradient descent for each of them (with large steps), then test such final points rounded to boolean values. Gradients suggest local direction toward minimum basing on the entire problem - such brute force supported by gradient descent might be essentially better than just brute force (?)

Another approach is using smoothening of the polynomial by adding its laplacian (analogous to evolution by diffusion equation):
f -> f + lambda * laplacian f
For lambda -> infinity we get degree 2 polynomial: just a paraboloida with unique minimum which can be cheaply found (e.g. conjugated gradients).
Such minimum depending on the entire problem might be already an essential hint where to look for the solution of our problem.
For example we can perform analogous process like in adiabatic quantum computers: go with lambda from infinity to zero, continuously tracing a local minimum.

Anyway, there are lots of numerical tricks for minimization of such relatively simple: degree 4 polynomial.
I am planning to test it for integer factorization (RSA) - which seems relatively simple (the only broken by QC), is easy to translate into minimization of polynomial, and can be easily scaled to evolve optimal parameters for optimization.

 

[Baluncore]

The real question is existence of a smarter way than such brute force search among all possibilities.

Lateral thinking finds smarter ways since each system does have weaknesses. But with a technically strong cryptosystem, game theory becomes more important and it is usually easier to steal the keys, or to eliminate an operator by arranging an unfortunate accident.

Gradients suggest local direction toward minimum basing on the entire problem - such brute force supported by gradient descent might be essentially better than just brute force (?)

Anything is better than brute force. But gradients do not work in multiplicative or XOR logic based cryptosystems. It rapidly becomes a nightmare, like trying to find the highest point in a field full of camouflaged seesaws, (teeter-totters), at night.

 

[jarekduda]

Anything is better than brute force. But gradients do not work in multiplicative or XOR logic based cryptosystems. It rapidly becomes a nightmare, like trying to find the highest point in a field full of camouflaged seesaws, (teeter-totters), at night.

Indeed, the question is how much better?

We are talking about minimization of just degree 4 polynomial here, e.g.
"z = x and y" -> (z - xy)^2
"z = x or y" -> (1-z - (1-x)(1-y))^2
"z = x xor y" -> (z - (x-y)^2)^2
plus x^2(1-x) for all variables to enforce final boolean values.
The only interesting is [0,1]^n hypercube.
If there is a unique solution of 3-SAT, this polynomial is 0 in only a single corner of hypercube, and has value at least 1 in the remaining corners.
And it is relatively simple and smooth function.

The only source of essential difficulty I can imagine here is possibility of exponentially large number of nonzero local minima - but I don't know if it is true for specific e.g. cryptographic problems?
Otherwise, convergence problems should be solvable (?)
And the adiabatic approach seems promising: start with lambda=infinity, where we can calculate the unique minimum, and carefully perform lambda->zero, continuously tracing a minimum.
Gradients seem a helpful local hint basing on the entire problem ... or we could use more sophisticated hints from e.g. degree 2 Taylor (cheaply minimized).

 

[Baluncore]

If you think your technique has merit, test it on something trivial like the old 64 bit DES.
https://en.wikipedia.org/wiki/Data_Encryption_Standard#Attacks_faster_than_brute-force

 

[jarekduda]

Sure, I am planning to work on such attack, but for integer factorization (a few reasons) ... and probably give it up if turn out hopeless.

However, you have written that you have seen this kind of attacks and seem certain that it's not a good idea - do you know some sources supporting problems with approaches through continuous optimization?

 

[mfb]

Physicsforums is not the right place to develop new methods. If it works, publish it, then we can discuss it here.
A fast integer factorization would certainly be revolutionary.