Proving that a function is a trapdoor function

Question

I am working on a problem that involves an iterative application of a function I think might be a trapdoor function.

Formally, I have a function $f:X \to X$ that can be described as

$$ [x_{1,N+1}, ..., x_{s,N+1}]=f([x_{1,N},...,x_{s,N}])\\ \forall_{i<s-1}x_{i,N}=x_{i+1,N+1} $$ and $x_{s, N+1}$ is probabilistically sampled and corresponds to an integer vector in high dimension.

If we know the starting state of the function ($[x_{1,0},...,x_{s,0}]$), calculating the forward propagation of the function is straightforward and we can get to $[x_{1,N},...,x_{s,N}]$ by performing $f \circ f$ $N$ times, meaning that for N<s, we can easily verify that the sequence [x_{1,N}, ..., x_{s,N}] was indeed sampled by $f$.

However, without ($[x_{1,0},...,x_{s,0}]$), there is no trivial way to revert the function but to sample all the possible values for $x_{1,N}$.

I have a hunch that if $f$ was deterministic, it would correspond to a trapdoor function, with $[x_{1,0},...,x_{s,0}]$ acting as a secret $t$, but I have no clear idea as to how to prove such an equivalence.

Coming from a CS background, if I wanted to prove a problem was $NP$-hard, I would try to prove an equivalence to a known $NP$-hard problem. Could a similar approach work for trapdoor functions?

If yes, is there a list of known/suspected trapdoor functions?

Answer 1

First, there is a site crypto.stackexchange.com that is typically better for questions like this.

Second,

Coming from a CS background, if I wanted to prove a problem was NP-hard, I would try to prove an equivalence to a known NP-hard problem. Could a similar approach work for trapdoor functions?

The answer is sort of. There are no known ways of building trapdoor functions that are secure assuming the worst case hardness of an NP-hard problem. There are two lines of work that are formally "close" (not in the sense with "given enough time they will achieve this goal though").

1. Lattice-based Cryptography: Regev established that a certain useful cryptographic assumption (the "Learning with Errors problem") is average-case hard as long as certain lattice problems are hard in the worst case. These lattice problems are not NP hard (in fact, they are in NP and coNP), but they are still somehow "close" --- they are approximation problems for approximation factor $\gamma$ where for:

   a. $\gamma = O(1)$ (actually slightly higher, but still) the problem is NP hard

   b. for $\gamma = O(\sqrt{n})$ the problem is in NP and coNP, but we can (start to) build useful cryptography for it

   c. we can solve the problems in polynomial time for sub-exponential approximation factors.

   So we are somehow much closer to the "NP hard" side of things than the "known poly-time algorithms" side of things, but it seems unlikely $\gamma$ can be reduced further.

2. Recently, Pass and Liu have had some work (this and this) that shows that the existence of one-way functions (not equivalent to the existence of trapdoor functions, but sufficient to build much of cryptography, known as "minicrypt" primitives) is equivalent to establishing average-case hardness of an explicit NP hard problem, i.e. it suffices to prove worst-case to average-case reductions for this explicit problem.

That all being said, most cryptography doesn't concern itself with connections to worst-case hardness. Instead, average-case hardness is the main thing needed. Most books in cryptography will cover how to construct various cryptosystems assuming the average-case hardness of underlying computational problems. A popular (undergraduate-level) cryptography textbook is Katz and Lindell's Introduction to Modern Cryptography. I'd suggest reading through that. If you want a list of "standard" cryptographic problems, it of course changes semi-frequently, but there was a time period ~10 years ago when there were many more used commonly than there are now. This led to the following paper criticizing the practice, which is perhaps a good place to look for what some cryptographers view as "standard" (and "non-standard") assumptions.