# Finding a trapdoor function for the 3-partition problem

I am working on a cryptography project. Let's say I want to build a public key cryptosystem using the 3-partition problem, which is NP-Complete, as a basis (just like RSA uses integer factorization).

Now, I am having trouble coming up with a trapdoor function that helps me enconde it. Let's say I have $T=\{t_{1}, t_{2},...,t_{3n}\}$ and a solution $S=\{S_{1}, S_{2}, ..., S_{n}\}$, where every $S_{i}$ contains 3 elements of $T$ and $\sum_{k=1}^{3} S_{ik} = \sum_{k=1}^{3} S_{jk}=x$.

Now, let's assume the user creates $T$ and $S$, and of course also knows $x$. He can use either $x$ or $S$, or both, as a private key, and send $T$ and the public key for enconding.

I want to find a "function" that in one way requires finding $S$ or $x$ from $T$, and the other way can be done only with $T$. That is, given a plaintext $p$, $f(p, T)=c$ and $g(c, S)=p$ (I don't know if $f$ and $g$ have to be inverse of each other necessarily).

The cryptisystem does not have to be super-secure or have no flaws, I'm just looking for a function/encoding that does this in whatever way. For example, the MH knapsack cryptosystem uses some kind of alternate way to write the subset sum problem as a sum like $V=a_1x_1,..., a_nx_n$.

• As far as I understand, it is an open question to base cryptography on the $\mathsf{P} \neq \mathsf{NP}$ hypthesis rather than on stronger ones. – Yuval Filmus May 30 '17 at 14:30
As Yuval says, it's an open question whether one can build a public-key cryptosystem whose security is based on the assumption that $\textsf{P} \ne \textsf{NP}$. There is no known public-key cryptosystem with that property, though many cryptographers have tried to find one. So, you're trying to solve a problem that is likely to be extremely hard to solve.