#1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2007
    Posts
    51
    Rep Power
    10

    Cryptographic attacks as minimization of degree 4 polynomial (through 3-SAT problem)


    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?
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2007
    Posts
    51
    Rep Power
    10
    I have implemented in Mathematica generation of degree 4 polynomial for product of two integers in their binary representations - attached:
    For z=x*y the polynomial is sum over digits n of
    (sum_i x_i y_{n-i} - z_i + "previous carry bits" - "carry bits forward")^2
    plus sum of x^2 (1-x)^2 over all variables to enforce final boolean values.

    Fixing value of the product (z), gradient descent allows to literally propagate this information back to digits of the two factors (x and y) - being able to efficiently find the global minimum of this degree 4 polynomial would solve the integer factorization problem, breaking RSA ...
    ... however, as I have suspected, this polynomial has huge number of local minimia - where the gradient descent stucks.
    So while it allows to propagate information backward: from product to factors, it usually leads to a trap.

    The question is if there exists a smarter continuous global optimization procedure to handle the local minima problem here, or a better way of translating into a polynomial?
    Attached Files

IMN logo majestic logo threadwatch logo seochat tools logo