The proof that P≠NP is not difficult

Collapse
X
 
  • Time
  • Show
Clear All
new posts
  • gaoming094
    New Member
    • Feb 2025
    • 1

    The proof that P≠NP is not difficult

    Firstly, we introduce a common proposition "the existence of one-way functions =>P≠NP", which is considered a fundamental theorem in general cryptography or computational complexity theory. one-way functions have two conditions:
    1) calculating f(x) can be completed in polynomial time.
    2) Calculating the inverse function f^{-1}(x) cannot be completed in polynomial time.
    If we find a one-way function, it means that the problem validated in polynomial time cannot be solved in polynomial time, which means P≠NP.

    Of course, P≠NP does not infer the existence of one-way functions (the existence of one-way functions is currently an open problem). We won't discuss this further.

    In fact, we have constructed a short key block symmetric cipher algorithm that satisfies the conditions of one-way functions to crack the key given any plaintext-ciphertext pairs:

    1. Verifying whether a given key is correct can be done in polynomial time (by comparing the plaintext decypted by the given key).

    2. Given any plaintext-ciphertext pair, there is no effective cracking method except for exhaustive search (the key space is exponential and cannot be exhaustively searched in polynomial time). This can be discussed in two situations:

    I) Given the plaintext-ciphertext pair of a single block, any key is equally probabilistic unknowable (this is different from all current encryption mechanisms, where existing encryption mechanisms theoretically have a uniquely determined key given the plaintext-ciphertext pairs of each block). In our encryption algorithm, given the plaintext-ciphertext pair of a single block, keys are indistinguishab le in combinatorial mathematical logic, so theoretically, knowing the plaintext-ciphertext pair of a single block, exhaustive search is ineffective for cracking the key.

    II) When knowing the plaintext-ciphertext pairs between any two or more blocks, the random parameters that any two blocks depend on are completely independently generated and the encryption process is also independent of each other. This theoretically proves that there is no other effective method to crack keys besides exhaustive search.

    In fact, throughout the entire construction process, the core is to demonstrate that for any given number of plaintext ciphertext pairs, there is no other method to crack the key except exhaustive search. As long as this characteristic is satisfied, the one-way function conditions hold, and thus P≠NP is a direct inference.

    Please refer to the paper: https://arxiv.org/pdf/2203.05022
  • Ramon cold
    New Member
    • Feb 2025
    • 2

    #2
    Checked your paper, good job.
    Do you think Eagle algorithm requires trial and error when decrypting, which is quite resource intensive? Will it slow down the decryption speed?
    We all know that nonlinear transformations are important in cryptography, but Eagle algorithm doesn't use them. So how can we resist linear and differential attacks?

    Comment

    • Ramon cold
      New Member
      • Feb 2025
      • 2

      #3
      Does the Eagle algorithm rely on the same probability of guessing each bit to prevent attacks? Is it really enough with so many attack methods now?

      Comment

      Working...