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$.

Thanks for reading.

  • 1
    $\begingroup$ 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. $\endgroup$ – 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.

Part of the challenge is that NP-complete problems are generally hard, but that's not enough for cryptography. Public-key cryptography also requires that there be a "trapdoor" that makes them easy. So, you'll need to find a way to encode a secret trapdoor in the 3-partition instance that makes it easy to solve the 3-partition problem if you know the trapdoor -- but where you can prove that the existence of the trapdoor doesn't make the problem any easier for people who don't know the trapdoor. It's not clear how to do that. There are ways to embed a trapdoor, but then they require choosing 3-partition instances with a particular structure/format, and then solving those special instances might be easy (might be doable in polynomial time).

You might be interested in knapsack cryptography (see the knapsack tag on Crypto.SE), Impagliazzo's five worlds, this question on Crypto.SE, and Impagliazzo and Rudich's black-box separation between one-way functions and key exchange, which provides some kind of evidence that it's likely not going to be easy to do what you want (e.g., there's no black-box way to convert a NP-complete problem to a public-key encryption algorithm).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.