8
$\begingroup$

I am researching post quantum cryptography and I've stumbled upon this article which presents a PKC with an np-complete (SAT) trapdoor.

I was wondering if someone could help me understand the way the encryption works. From what I understand the cipher text is a formula which consist of a bit (the message) which is then xored with variables taken from the public key. Doesn't it mean that the bit is actually in "plain sight" inside the cipher text ?

Surely I am missing something.

| improve this question | |
$\endgroup$
  • $\begingroup$ From what I understand the public key and ciphertext are both boolean formulas, where the values of $x_{1..i}$ are known only to the holder of the secret key. The ciphertext formula is evaluated by substituting in the secret values $x_{1..i}$ to recover the bit $y$. Note that the actual values of the variables are not held in the public key. $\endgroup$ – puzzlepalace Jun 29 '16 at 20:51
  • $\begingroup$ This is what bothers me. Since the actual values of the variables are the private key the formula generated from the encryption is just the value 1 or 0 which is then covered by random variables. If you were to look at the cipher text and look for the only value which is not a variable you would be able to recover the message. $\endgroup$ – Yuon Jun 30 '16 at 10:14
  • $\begingroup$ But if the clauses of the public key are randomly chosen, then each clause in will have a constant with probabiliy $\frac12$. Each such constant will be multiplied with some random $R_i$ and added to the plaintext bit. $\endgroup$ – Carl Löndahl Jun 30 '16 at 10:44
10
$\begingroup$

There are known impossibility results regarding basis public-key cryptography on NP-complete problems. In this paper by Goldreich and Goldwasser they show that under common types of reductions, it is not possible to base public-key cryptography on NP-hardness.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ In particular, in the "SAT-based-trapdoor" cryptosystem, deriving the private key is equivalent to SAT (they don't prove it, but it's pretty obvious). However, they don't show that the problem of rederiving the plaintext given the ciphertext and the public key can be reduced to SAT, hence their claim to be "based on SAT" is misleading... $\endgroup$ – poncho Jun 30 '16 at 19:06
  • 4
    $\begingroup$ Actually, Goldreich and Goldwasser don't show that it's impossible to base a public key cryptosystem on a NP-hard problem; they show that if you do have one, you've just proven $NP = coNP$, which would be a bit surprising (but certainly not impossible) $\endgroup$ – poncho Jun 30 '16 at 19:08
  • 2
    $\begingroup$ Of course, this is what I meant. But, $NP=coNP$ would not be a "bit" surprising, it would be a computational complexity tsunami! $\endgroup$ – Yehuda Lindell Jun 30 '16 at 20:01
  • $\begingroup$ This might be a naive question but if we cannot base public-key on NP-hardness what is the correct approach when trying to come up with a new public-key system ? Especially coming from a post-quantum point of view. (Asumming BQP doesn't include NP-Complete than a PKC based on that should always be quantum resistant) $\endgroup$ – Yuon Jul 1 '16 at 12:26
  • $\begingroup$ We need to try to base it on "minimal assumptions". For public-key crypto, there isn't that much that we can say (unlike private-key crypto which is known to be equivalent to one-way functions). We therefore try and go for specific assumptions that have been heavily studied. For PQC, we typically use lattice-based assumptions. $\endgroup$ – Yehuda Lindell Jul 1 '16 at 15:01
2
$\begingroup$

I do not have enough high reputation to comment so I am writing here. I have also looked at the paper so I would like to share my thoughts. I think that in order to understand whether the bit is in the "plain sight" one has to ask the question: Is it possible to recover the bit $y$ from the cipher

$$g=y\oplus \bigoplus _{i=1}^{\alpha}\bigoplus_{a=1}^{\beta}{\bar{c}}_{J(i,a)}\land R_{i,a}$$

Well, it seems difficult. In the context of the paper recovering the bit $y$ from the cipher should be at least as hard as solving SAT.

| improve this answer | |
$\endgroup$
  • $\begingroup$ They do not give a proof of that in the paper IIRC . $\endgroup$ – Yuon Jul 5 '16 at 14:55
  • $\begingroup$ Yes, that is right. They do not give a proof but It seems intuitive. $\endgroup$ – Kristina Dedndreaj Jul 5 '16 at 15:01
  • 4
    $\begingroup$ @Kristinadedndreaj: the field of cryptography is littered with examples of things that, at first glance, appeared intuitively to be secure, but turned out not to be... $\endgroup$ – poncho Jul 5 '16 at 15:16
  • $\begingroup$ @poncho: Completely agree, there is needed rigorous Mathematical foundation in order to ensure security. $\endgroup$ – Kristina Dedndreaj Jul 5 '16 at 19:23
1
$\begingroup$

I think, the original question has been well answered by Carl Löndahl in the comments. Each of the terms you add does not only consist of "random variables" but may well contain a constant (1).

In fact, section 3.1.2 Constant Term Probability Attack in the paper exactly addresses your question, by proposing the attack of just looking at the constant term (0 or 1).

When considering the encryption scheme from the article, please also have a look at this article which references a similar SAT based scheme which has a known vulnerability. It is currently unclear whether the same vulnerability also exist in the scheme from the arxive.

Unfortunately, I may not comment:

@Kristina dedndreaj: Deriving the private from the public key is (exactly) the SAT Problem, hence NP hard, but, whether deriving the clear text from the cipher and public key is hard in any sense is an open question. Showing that this is NP hard is very difficult and there are no-go theorems around (see Yehuda Lindell's Answer).

EDIT (thanks to clarification by Occams_Trimmer in comments):

There are a few schemes which are currently believed to be "post-quantum". This may or may not mean that some NP-Hard Problem is utilized for the cryptosystem in some way. See e.g. https://en.wikipedia.org/wiki/Post-quantum_cryptography . A better Referenz is Bernstein, Buchmann, and Dahmen: Post-Quantum Cryptography which e.g. has this quote:

A multivariate public key cryptosystem (MPKCs for short) have a set of (usually) quadratic polynomials over a finite field as its public map. Its main security assumption is backed by the NP-hardness of the problem to solve nonlinear equations over a finite field. This family is considered as one of the major families of PKCs that could resist potentially even the powerful quantum computers of the future.

in the abstract of Multivariate Public Key Cryptography by Ding and Yang.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ The parameters for which the lattices problems are useful in cryptography belong to a regime for which the problem is believed (strongly) not to be $\mathsf{NP}$-hard (c.f. here for details and here for a figure). So, it is not accurate to say that cryptography is based on $\mathsf{NP}$-hardness. $\endgroup$ – Occams_Trimmer Aug 14 '17 at 20:46

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.