Cryptographic attacks as minimization of degree 4 polynomial

In summary, the conversation discusses the use of cryptography and its potential vulnerabilities. While hash functions are difficult to reverse due to the loss of information, decomposing them into simpler relations like 3-SAT clauses may make it easier to reverse them. This can potentially lead to faster collision search and break symmetric cryptography. However, encryption is still considered secure due to the size and factorial number of possible permutations.
  • #1
jarekduda
82
5
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?
 
Technology news on Phys.org
  • #2
jarekduda said:
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.

jarekduda said:
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.
 
  • Like
Likes jarekduda
  • #3
Baluncore said:
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.
 
  • #4
jarekduda said:
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.

jarekduda said:
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.
 
  • #5
Baluncore said:
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).
 
  • #7
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?
 
  • #8
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.
 

Related to Cryptographic attacks as minimization of degree 4 polynomial

1. What is a cryptographic attack?

A cryptographic attack is a method used by hackers to exploit vulnerabilities in an encryption system and gain unauthorized access to sensitive information. It involves using mathematical algorithms and techniques to decipher encrypted data and reveal its contents.

2. What is a degree 4 polynomial?

A degree 4 polynomial is a mathematical expression with the highest power of the variable being 4. It can be written in the form of ax^4 + bx^3 + cx^2 + dx + e, where a, b, c, d, and e are constants and x is the variable.

3. How does a cryptographic attack minimize a degree 4 polynomial?

A cryptographic attack minimizes a degree 4 polynomial by finding the smallest possible value for the polynomial, which is known as the minimum degree. This is done by manipulating the coefficients of the polynomial using various mathematical techniques, ultimately reducing the degree of the polynomial and making it easier to solve.

4. What is the significance of minimizing a degree 4 polynomial in cryptographic attacks?

Minimizing a degree 4 polynomial in cryptographic attacks can make the encryption system more vulnerable to attacks. It can reduce the complexity of solving the polynomial, making it possible for hackers to decipher the encrypted data and gain access to sensitive information.

5. How can organizations protect against cryptographic attacks that minimize degree 4 polynomials?

To protect against cryptographic attacks that minimize degree 4 polynomials, organizations can use strong and robust encryption algorithms, implement proper key management protocols, and regularly update their encryption systems to fix any known vulnerabilities. It is also important to regularly train employees on cybersecurity best practices to prevent social engineering attacks that could lead to the compromise of encryption keys.

Similar threads

  • Programming and Computer Science
Replies
5
Views
2K
  • Calculus and Beyond Homework Help
Replies
6
Views
281
  • Programming and Computer Science
Replies
15
Views
1K
  • Precalculus Mathematics Homework Help
Replies
7
Views
2K
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
3K
  • Precalculus Mathematics Homework Help
Replies
11
Views
1K
  • Classical Physics
Replies
7
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
Back
Top