Hacker News Reader

Comment by bgribble | Hacker News Reader

So given a start state and a library of valid transitions, it's easy to create a (target, path, destination) tuple that's valid (if you don't care what the destination is). It's easy to check if a (target, path, destination) tuple is valid. It's just really hard to find the path given just the target and the destination.

This sounds like it has properties in common with "multiply two very large primes to create a very large composite number". Could any of this math be used as the basis for a cryptosystem?

View on HN

Depending on your library of valid transition, it could be really easy to find a path. That's the issue: there are libraries of paths where finding a path is really hard, but libraries where finding a path is easy.

Say in another way, we know only the worst case complexity, not the complexity of a test case taken randomly.

Some latices-based cryptosystems have such properties: there are theorems showing that if there is an algorithm good at solving random cases, than you can derive from it an algorithm good at solving any cases, including the worst ones. So for those problems, the worst case complexity is the same than the "average/random case" complexity.

So you're saying the nsa will love it.

(I'm not an expert. Take all of this with a grain of salt and just imagine I'm sticking "I think" in front of every sentence.)

It's easy (O(path length)) to check if a (target, path, tuple) is valid, but the paths themselves are of phenomenal lengths:

"He developed a procedure for constructing systems in which the fastest way to determine whether one state is reachable from another is to map out a sequence of transitions between them. That allowed him to use the length of the shortest path between two carefully chosen states as a measure of the difficulty of the reachability problem."

That's the guarantee: we can prove you have to do a ton of computation because you have to traverse this huge path. That's why this whole area of study isn't tainted by the question of whether P=NP. (Formally, because it doesn't have a polynomial-size witness).

So I think you could make a cryptosystem out of this, but, since you'd (for practical reasons) use relatively short paths, you wouldn't get the difficulty guarantees of this research.

It might be possible to compute whether the start and end States are connected without constructing the actual path. As usual non trivial lower bounds on computation are basically non existent.

As an example, we can determine whether a number is composite (not prime) without computing its factors.

I read "He developed a procedure for constructing systems in which the fastest way to determine whether one state is reachable from another is to map out a sequence of transitions between them." as saying that there is a proof that there is not a way to compute whether the start and end States are connected without constructing the actual path.

I think this is the relevant paper (pdf): https://cpsc.yale.edu/sites/default/files/files/tr63.pdf

Without digging too much, I don't think such an argument could be made by this paper. A non trivial lower bound on a concrete problem in a general computation framework would be a marvel on its own.

As another example of what I mean, take sorting. There is an omega(n log n) lower bound that applies to a comparison based algorithm, but no lower bound other than trivial n is known for general computation.

It really boils down to how you define your search space. If you encode your input in a way that is already exponential on some parameter n, then even a linear algorithm would take at least exp(n) time just to read the input.

Let's say you have an algorithm, encoded in L characters, that can produce these extremely long paths, then a natural question is whether for any two vectors of n k-bit integers what is the complexity in terms of nk and L of determining whether they are connected? Note that I don't need to generate/read a huge state graph, I could do something smart by understanding the algorithm.

Reminds me of this: https://en.wikipedia.org/wiki/Lattice-based_cryptography

That's immediately what I thought of and was perplexed why the word "lattice" was nowhere in that article.

The classic example of this is diffusion. You can track and even reverse abstract data concepts like temperature but you can't invert particles (reverse but not invert). You can't create a bijective/isomorphic map unless you keep track of the forward time operation. So it's why we talk about entropy because there's many different identical states that lead to a particular end state but the paths are different so you have a uniqueness problem. You don't have identifiable elements even if you have independent components so you're always operating with a family of solutions. Basically, your calculus teacher wasn't being an asshole for stressing that you got the wrong solution when you forgot to add "+C".

If you're confused and wondering if I'm talking about ML or thermodynamics the answer is yes.

That description sounds similar to me of Elliptic Curve cryptography, as well. Pathfinding/curvefitting between two or more points in a curve without knowing other specifics of the curve.

Reply on news.ycombinator.com