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?



Proving that a function is a trapdoor function
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](https://cims.nyu.edu/%7Eregev/papers/lwesurvey.pdf) 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](https://drops.dagstuhl.de/opus/volltexte/2022/16597/) and [this](https://drops.dagstuhl.de/opus/volltexte/2022/16598/)) 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](https://eprint.iacr.org/2015/907) criticizing the practice, which is perhaps a good place to look for what some cryptographers view as "standard" (and "non-standard") assumptions.


