- #1

jarekduda

- 82

- 5

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?