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.