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 local gradients depending on the entire problem.

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.

So we could for example translate a hash function into a set of 3-SAT clauses, fix a final value and ask for the initial value 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?

Tweet This+ 1 thisPost To Linkedin