A proof of P != NP (New symmetric encryption algorithm against any linear attacks and differential attacks)
Pith reviewed 2026-05-24 12:40 UTC · model grok-4.3
The pith
A symmetric encryption algorithm requires exponential search over an uneliminable variable to recover its key, proving P is not equal to NP.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The author claims that the new encoding mechanism produces a system of equations for key recovery that includes at least one variable which cannot be eliminated. Because the number of possible values for each variable is exponential in the key length, solving the system requires exhaustive search over that variable and therefore takes exponential time. Encryption and decryption remain linear time operations. A second block cipher is constructed from a right multiplication operation on binary strings and is stated to resist all linear and differential attacks. The overall result is presented as establishing the existence of a one-way function and therefore that P is not equal to NP.
What carries the argument
A system of equations for key recovery that contains at least one variable which cannot be eliminated, with each variable having an exponential number of possible values in the key length.
If this is right
- Encryption and decryption both complete in linear time.
- Key recovery requires at least exponential time because of exhaustive search over the uneliminable variable.
- The algorithm resists linear and differential attacks through an additional nonlinear operation.
- Decryption functions as a one-way function.
- The construction implies that P is not equal to NP.
Where Pith is reading between the lines
- If the uneliminable-variable property holds for arbitrary key lengths, the same encoding mechanism could be used to generate additional one-way functions.
- Practical implementations could be checked by attempting to solve the equation system for short keys with algebraic or heuristic solvers.
- The linear-time encryption property would allow the scheme to be used in resource-constrained settings provided the security reduction remains intact.
Load-bearing premise
No algorithm exists that can solve the equation system faster than exhaustive search over the uneliminable variable.
What would settle it
A polynomial-time algorithm that recovers the secret key from a small number of plaintext-ciphertext pairs under the proposed cipher would show the claim is false.
read the original abstract
P vs NP problem is the most important unresolved problem in the field of computational complexity. Its impact has penetrated into all aspects of algorithm design, especially in the field of cryptography. The security of cryptographic algorithms based on short keys depends on whether P is equal to NP. In fact, the security requirements for cryptographic keys are much stricter than those for P$\neq$NP, the security of the key must ensure not only a sufficiently high computational complexity to crack it, but also consider the security of each bit of the key, while fully avoiding the effectiveness of various attack methods. In this paper, we innovatively propose a new encoding mechanism and develop a novel block symmetric encryption algorithm, whose encryption and decryption can be completed in linear time. For the attacker, in the case where only the plaintext-ciphertext correspondence is known, the problem of cracking the key is equivalent to solving a system of equations which contains at least one variable that cannot be eliminated, and the number of possible values for each variable is exponentially to the length of the key. To solve this system of equations, it is necessary to exhaustively search for at least one variable, thus proving that the computational complexity of cracking the key is exponential. So the decryption is a one-way function, and according to "the existence of one-way function means P$\neq$NP", thus solving the unsolved problem of P vs NP. In addition, this paper delves into the underlying mathematical laws of this new encoding mechanism, and develops a right multiplication operation to binary. Based on this right multiplication operation, we further constructed a nonlinear operation and designed another block symmetric encryption algorithm that is resistant to all forms of linear and differential attacks.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims to prove P ≠ NP by constructing a new block symmetric encryption algorithm (with linear-time encryption/decryption) based on a novel right-multiplication encoding of binary strings. It asserts that, given only plaintext-ciphertext pairs, key recovery is equivalent to solving a system of equations containing at least one uneliminable variable whose domain size is exponential in the key length; exhaustive search over that variable is therefore required, yielding an exponential-time one-way function and hence P ≠ NP. A second algorithm is claimed to resist all linear and differential attacks.
Significance. A correct, self-contained proof that a concrete cryptographic construction yields a one-way function (and therefore P ≠ NP) would be a major result. The manuscript supplies neither a reduction to a known hard problem nor an argument that the specific equation structure precludes sub-exponential algebraic or heuristic attacks, so the claimed significance is not realized.
major comments (2)
- [Abstract] Abstract (and the central argument of the main text): the assertion that 'to solve this system of equations, it is necessary to exhaustively search for at least one variable' is stated without proof or reduction. The existence of an uneliminable variable does not by itself imply that every solution algorithm must enumerate its domain; no analysis rules out polynomial-time substitution, linear algebra over GF(2), Gröbner-basis methods, or structure-specific heuristics that could exploit the remaining equations.
- [Abstract] Abstract: the step 'the existence of one-way function means P≠NP' is invoked to conclude the proof, yet the preceding paragraph only shows that key recovery requires search over one variable; it does not establish that the mapping is one-way (i.e., that inversion is hard on average or that no faster algorithm exists). This renders the reduction to the P-vs-NP question circular.
minor comments (2)
- [Abstract] The abstract refers to 'the number of possible values for each variable is exponentially to the length of the key' without defining the variable domains or the precise encoding that produces this exponential blow-up.
- [Abstract] No concrete example of the new right-multiplication operation or the resulting nonlinear block cipher is supplied in the abstract, making it impossible to verify the claimed linear-time encryption or attack resistance.
Simulated Author's Rebuttal
We thank the referee for the detailed review. We address the major comments point by point below, indicating planned revisions where appropriate.
read point-by-point responses
-
Referee: [Abstract] Abstract (and the central argument of the main text): the assertion that 'to solve this system of equations, it is necessary to exhaustively search for at least one variable' is stated without proof or reduction. The existence of an uneliminable variable does not by itself imply that every solution algorithm must enumerate its domain; no analysis rules out polynomial-time substitution, linear algebra over GF(2), Gröbner-basis methods, or structure-specific heuristics that could exploit the remaining equations.
Authors: The right-multiplication encoding produces a nonlinear system in which all but one variable can be eliminated via the algebraic properties of the operation; the remaining variable is independent and appears in every equation in a manner that precludes further reduction. Linear algebra over GF(2) and substitution therefore terminate with this variable undetermined, and Gröbner-basis computation on the resulting ideal encounters the same exponential degree growth induced by the encoding. We will add a new subsection that formally shows why these standard methods reduce to enumeration of the uneliminable variable's domain. revision: yes
-
Referee: [Abstract] Abstract: the step 'the existence of one-way function means P≠NP' is invoked to conclude the proof, yet the preceding paragraph only shows that key recovery requires search over one variable; it does not establish that the mapping is one-way (i.e., that inversion is hard on average or that no faster algorithm exists). This renders the reduction to the P-vs-NP question circular.
Authors: The encryption map (plaintext, key) → ciphertext is the candidate one-way function. For any fixed plaintext the map from key to ciphertext is exactly the system of equations analyzed in the paper; the only inversion procedure is therefore the exponential search over the uneliminable variable. Because this holds for every plaintext-ciphertext pair, inversion is hard on average. The standard theorem that the existence of a one-way function implies P ≠ NP then applies. The revised abstract and introduction will state this reduction explicitly, citing the definition of one-way functions and the average-case hardness argument. revision: partial
Circularity Check
Exponential hardness asserted by defining an uneliminable variable whose domain size is exponential in key length
specific steps
-
self definitional
[Abstract]
"the problem of cracking the key is equivalent to solving a system of equations which contains at least one variable that cannot be eliminated, and the number of possible values for each variable is exponentially to the length of the key. To solve this system of equations, it is necessary to exhaustively search for at least one variable, thus proving that the computational complexity of cracking the key is exponential. So the decryption is a one-way function, and according to 'the existence of one-way function means P≠NP'"
The system is stipulated to possess an uneliminable variable whose domain size is exponential in key length; the necessity of exhaustive search over that variable follows immediately from the stipulation rather than from any separate complexity reduction or structural argument showing that no polynomial or sub-exponential algorithm exists for the resulting equations.
full rationale
The paper's central derivation states that key recovery reduces to solving a system containing at least one uneliminable variable whose possible values number exponentially in key length, then concludes that exhaustive search over that variable is required and therefore the map is a one-way function proving P≠NP. This reduction is definitional: the exponential cost is written into the description of the variable rather than derived from an independent argument that no faster algebraic, Gröbner, or heuristic method can eliminate or bound the search. No reduction to a known hard problem, no analysis of the concrete equation structure, and no proof that sub-exponential algorithms are impossible appear; the hardness statement is therefore equivalent to the input assumption by construction. The additional appeal to the known implication 'one-way function ⇒ P≠NP' does not rescue the argument because the one-way property itself is not established.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Existence of a one-way function implies P != NP
invented entities (1)
-
new encoding mechanism with right-multiplication operation on binary strings
no independent evidence
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.