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 (?)(adsbygoogle = window.adsbygoogle || []).push({});

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?

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Cryptographic attacks as minimization of degree 4 polynomial

Tags:

Loading...

Similar Threads - Cryptographic attacks minimization | Date |
---|---|

Minimization of many-variable function | Oct 14, 2015 |

GSL Multidim Minimizer - How to handle unphyiscal values | Jul 8, 2015 |

Numerical Minimization of many-variable function in Fortran | Dec 10, 2013 |

Cryptographically secure code obfuscation | Sep 26, 2011 |

What the best online resource to learn about SQL injection attacks? | Jul 3, 2010 |

**Physics Forums - The Fusion of Science and Community**