Topic: The existence of one-way function means P!=NP (Read 322 times)

The security of this encryption algorithm does not only depend on the arbitrariness of the initial state selection.
The final effect of our design in this way is that for each group, the plaintext has L bits, the ciphertext has L bits, and the key has 2L-1 bits. For any known group of plaintext-ciphertext pairs (total 2L bits), all The possible keys (2L-1 bits) can find the initial state S0 and the final state S1 that meet the conditions, and the initial state S0 and the final state S1 have nothing to do with the plaintext. In addition, the encryption of each packet is performed independently.
Therefore, the security of the algorithm is not brought about by the arbitrariness of the initial state selection, but by the algorithm itself, that is to say, you know the arbitrary grouping of plaintext M-ciphertext C pairs, and any key in the key space. K, you can find a correct encryption method (that is, find S0/S1 to M and use K to encrypt the ciphertext C). Therefore, any linear attack or differential attack method is theoretically invalid.

The security of this encryption  seems to stem from the arbitrariness of the initial state S0. What is the difference between using the existing encryption method and appending a piece of random information at the beginning of the plaintext?
But if you can't answer the above question, I can hardly see the significance of this research.

As in "Theorem 3". we construct an encryption algorithm, as the plaintext-ciphertext is known, the problem of guessing the key can be  transformed to another encryption algorithm,  when only the ciphertext is known, the problem of guessing the key, which satisfies the property of one-way function intuitively.
"Theorem 4" theoretically proves that the above-mentioned problem of guessing the key satisfies the property of one-way function through the calculation of conditional probability. this also proves that the one-way function exists.
The existence of one-way functions can directly prove p!=np, which is a question of common sense.

The encryption algorithm in this paper can be used in all symmetric encryption scheme that require high security.

He random number generator part has already been discussed earlier. The one-way function he presented is a good step towards a proof, it can possibly be used as a basis for a formal theorem of p!=np but I don't  see any such theorem in the paper.

I can't wait to hear about the use cases for this encryption scheme.

After reading your paper carefully, as a symmetric encryption algorithm, the security is indeed higher as to resist linear attacks and differential attacks.
But if you want to strictly prove p!=np, you should rely on some kind of random number generation algorithm. or maybe i haven't fully understood it.

The features of this algorithm are completely different from those of traditional AES/DES. For the same plaintext and the same key, each encryption will produce a different ciphertext.
For any plaintext-ciphertext pair, any key in the key space is correct. That is, according to any plaintext-ciphertext pair, it is impossible to obtain any characteristics of the key.

OK another question related to the decryption algorithm itself. We make L = ceil(log2(M)) rounds of XOR and cyclic shift encoding. However for small input data this means we're only running a few rounds. In addition to this, in each round we are also searching for the correct w0 and w1 parameters. Won't this be vulnerable to brute-forcing for both small and large L, since step 2 is essentially "find w0 and w1 that satisfy Si XOR w0 and Si XOR w1 respectively"?

Also by making the number of rounds dependent on the input size you are making this vulnerable to timing attacks. AES uses a constant number of rounds with word shuffling and shifting operations in each round so perhaps you can look into doing something like that to bullet-proof it.

I think you misunderstood what i wrote in my paper.
W0 and w1 have an odd number of different bits, which means that they are compared bit by bit, and there are odd numbers of different bits. Or it can be understood that w0 xor w1 has an odd bits of 1.

In addition, I have put the paper on https://www.researchgate.net/publication/348992129_Eagle_A_new_symmetric_encryption_algorithm_against_any_linear_attacks_and_differential_attacks_The_existence_of_one-way_function_means_PNP

Welcome to discuss.

Thanks, now this is starting to make sense.

A question though: presumably, since both w0 and w1 are known, we have both s1 xor w1 and s1 xor w0 already known. Meaning s0 xor (s0 >> 1) is left to be determined.

 A cyclic shift of A by n bits, can be represented as (A_i - 1) % n, according to Wikipedia. The paper says that a unique s0 can't be found if n is odd. Presumably it's because even n make the same modulus for the circular shift above and so an s0 can be found for it (example: w0 = 1100 and w1 = 1111, s1 = 0000, would give us 1100 and 1111 respectively for the xor. s0 could be set to 1000 which satisfies the equation) . But wouldn't w0 and w1 with odd, non-prime different number of bits also have some s0 that can be found for it, or am I going off on something completely unrelated?

You are right, but there is a problem, it should be S_i-1 XOR (S_i-1 >> 1) = S_i XOR w₁.

If the proof is stuck, you can put it away first.

for example.
w0=10010110, w1=01110101
s0=10100010
s0 >> 1 = 01000101
give m=0
s1=w0 xor (s0 xor (s0 >> 1)) = 10010110 xor (10100010 xor 01000101) = 10010110 xor 11100111 = 01110001.
suppose we know s1=01110001, we don't know whether m=0 or m=1, now we guess w=1, we have s0 xor (s0 >> 1) = s1 xor w1 = 00000100.
by the definition of cycle shift, no s0 can be found.

Let me see if I understand the security of this algorithm correctly.

It relies on the fact that there's no S_i+1 that satisfies S_i+1 XOR (S_i+1 >> 1) = S_i XOR w₁ is this right? So I want to make a proof of that.

- w₀ and w₁ are L-bit numbers with an odd number of different bits. S₀ and therefore 1, 2, etc are L-bit too.
- XOR is a commutative and associative operation so that makes some of the math easier. The >> is a right shift except it also rotates the bits from the end to the beginning. (XOR is 0 if bits are the same, 1 if they are different)
- S₀ is the initial state.

So that means S₁ = S₀ XOR (S₀ >> 1) XOR w₀, S₂ =  S₁ XOR (S₁ >> 1) XOR w₀, and so on.

In other words we are trying to prove S_i XOR (S_i >> 1) XOR w₀ XOR ([S_i XOR (S_i >> 1) XOR w₀] >> 1) != S_i XOR w₁ .

Which is just (S_i >> 1) XOR w₀ XOR ([S_i XOR (S_i >> 1) XOR w₀] >> 1) != w₁
=  (S_i >> 1) XOR ([S_i XOR (S_i >> 1) XOR w₀] >> 1) != w₁ XOR w₀

So we know that w₁ XOR w₀ = A is going to have an odd number of 1 bits.

And now I'm unable to simplify this further because while I know regular shifts are distributive, and can be distributed over XORs, cyclic shifts can't AFAIK unless there's away to simplify that C function in that Wikipedia link for cyclic shift.

Let me take another statement from the paper that is S₀ looks something like 000011111. Then S₀ >> 1 will be 100001111 (7 positions with different bits) XORing those two makes 011101111. This does correspond to the property mentioned in your paper that XOR of two numbers with N different positions will make a number with an 1s. But I'm unsure how to prove this for all numbers (or if someone has already done this). But at least I verified something from this part myself.

It should be noted that the construction of Eagle's algorithm only relies on uncertainty, not the quality of random numbers. As long as you take any number in the possible value space, using any random number generator will not affect the conclusion.

The quality of the random number generator is concerned with the quality of the random number sequence, which we don’t care about.

I don't think so. If you will use some poor random number generator, the whole thing will probably collapse. Also, if you use some constants as random numbers, it will work like any other function and it will be fully deterministic.

The whole problem of this paper is that it just made an assumption that generating truly random numbers is trivial. It is not, it was showed many times in practice that many random number generators are poor. And if you take randomness out of this scheme, this is just another function, maybe more complex than existing ones, but that's all about it.

Because of putting too much trust into random numbers being random, I doubt it truly proves that P!=NP.

if P = NP, then F P = FNP, and so any function that can be computed in polynomial time can be inverted in polynomial time, since there is a simple FNP algorithm that inverts it by nondeterministically enumerating all possible inputs.
However, it is not known whether P = NP implies the existence of one-way functions.

Yes, in this paper, we can replace "randomness" by "arbitrary" without affecting the correctness of the conclusion.

Good paper.

As NotATether said, the "randomness" of parameters should be called "arbitrary".

If your construction is correct, this will be a great discovery.

Nobody ever managed to prove before whether P equals or does not equal NP. As your paper mentioned that the existence of one-way functions opens up a proof to P!=NP, let's discuss that.

In that section you describe an encryption algorithm that uses language like:




Do you see the problem here? Your algorithms rely on certain parameters being generated randomly, but there is no practical implementation that can generate truly random numbers. All of them have varying levels of pseudorandomness either by using an equation or deriving bits of entropy from the keyboard, thermal heat conducted from the processor, etc etc and even if it is not practical to guess that data, it is still theoretically possible.

This algorithm in theory might be a one-way function (I didn't study the entire paper, sorry about that), but there is no practical way to implement the randomness to make it such.

What is the source of that randomness?

The existence of one-way function means P!=NP

Eagle: A new symmetric encryption algorithm against any linear attacks and differential attacks

Eagle is an encryption algorithm that can resist any linear attacks and differential attacks. Under the encryption mechanism, if any plaintext-ciphertext pair is known, an attacker wants to guess the possible key, he can only do trial-and-error, which satisfy the property of one-way function. In addition, we have also proved theoretically that this kind of problem satisfies the properties of one-way function, so that P!= NP. Since the design mechanism of the algorithm is brand new and can be proved by theory and practical engineering, I look forward to your discussion, thank you.

More details, see https://www.researchgate.net/publication/348992129_Eagle_A_new_symmetric_encryption_algorithm_against_any_linear_attacks_and_differential_attacks_The_existence_of_one-way_function_means_PNP

Welcome to email me for details: [email protected]