Quote from: JorgeStolfi on September 26, 2014, 06:09:17 PM

Quote from: TheFascistMind on September 26, 2014, 05:20:06 PM

a large NP space can be reduced to P by using localized randomness to act as a proxy for the large search space.

I think I understand what you are trying to say, but P and NP are not the right terms. Those concepts are irrelevant for practical cryptography. Going strictly by the definitions, since the output has fixed size, inverting SHA256 is not only P, but actually O(1).

Complexity theory (where one defines P and NP) has nothing useful to say about computations in a finite domain, no matter how big.

Size of the solution space isn't the right word. I mean the function of the size changes from exponential (n^k) to polynomial (n^O(1)).

If it is possible to convert the computation time (resource cost) from an exponential function of to a polynomial function of the inputs of the algorithm, then the complexity has been reduced from NP to P.

I cited a link which I believe demonstrated this, although I may be mistaken.

The search space for brute force inversion of SHA256 is 2^bits, e.g. a 128-bit hash has 2¹²⁸ possible outputs. All known methods for inverting SHA256 are NP relative to bits, and often cryptanalysis attacks remain in NP and only reduce the exponent by a factor that makes them practical solve for certain n. For example for finding collisions, the birthday attack is 2^bits/2. However, some attacks may reduce the complexity to P, e.g. a quantum computer (Shor's algorithm) on RSA reduces integer factorization from sub-exponential to polynomial.

NP requires that the solution can be verified in polynomial time. For example, the verification that the input to a hash produces a certain output.

Please feel free to correct me if I am still wrong.

Despite seeing some signs for hope from AHCC treatment, the symptoms affecting my head and nausea have worsened, and especially so in past 2 - 3 days. And today especially so to the point I'm become very worried that I have brain cancer. I will retire from the forum for a while to look into getting a brain scan. In the past 36 hours or so, I have become nearly incapable of functioning normally.

My feeling of well being (symptoms) has (have) been a rollercoaster ride, so there is always the chance I might feel better again. Nevertheless I feel I may have reached that defining moment when a person realizes they are not going to get better.

I traded several PMs with jl777 and my interpretation is his teleport design attempts to be at least an improved Tor for the basic case of his design. I don't have any comment on other aspects of his designs at this time. I make no endorsement, only to make a statement as to what I think minimally it could provide if he gets all the details done correctly. I am simply not close enough to all the details of the ongoing design and implementation to make any determination of an endorsement or criticism. Also I'd prefer not to play that role. My objective was to try to help. I made at least two minor tweak suggestions to him.