1
$\begingroup$

The Needham-Schroeder-Lowe protocol works as follows between the initiator I and responder R:

$I \longrightarrow R : \text{Enc}_{pk_R}(r_I, I)$

$R \longrightarrow I : \text{Enc}_{pk_I}(r_I, r_R, R)$

$I \longrightarrow R : \text{Enc}_{pk_R}(r_R)$

(I assume throughout that the encryption scheme is CCA-secure.)

Upon receiving their messages, both parties decrypt using the corresponding private key and finally output $r_I$ as their session key.

I understand others have proven that this protocol is SK-secure protocol, based on the CK01 model for SK-security. (As a reminder, the protocol is secure in this model if no adversary can distinguish, with probability strictly greater than $1/2$, between the output $r_I$ of the protocol and a random bit.) Security was proven using formal methods. My question: is there a proof of this using an explicit reduction?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ I recommend that you flag this to be moved over to Crypto.SE. Also, I recommend that you provide a link to the specification of the NSL protocol, add a link to the CK01 paper, and, provide a definition of SK-security. Also, tell us what you've tried so far or how far you've gotten on your own, and why you think it "should be SK-secure". $\endgroup$
    – D.W.
    Feb 28, 2013 at 0:38
  • $\begingroup$ @D.W. NSL protocol has been shown to be secure using other techniques such as formal methods, e.g. see this(math.upenn.edu/~bana/NSL.pdf). It also achieves SK-security, so my question is that how can one use reduction to show it? $\endgroup$
    – Brian
    Feb 28, 2013 at 15:47
  • 1
    $\begingroup$ This question would benefit from a lot of additional work, to try to be clearer. I recommend you stick to standard notation/terminology. The protocol is commonly known as Needham-Schroeder-Lowe (I've never heard of anyone call it NSL). Normally we use $N_A$ for a nonce generated by $A$; you use $r_I$ but don't specify what that value is. You claim this has been proven to be SK-secure but don't provide any citation for this; the paper you cited never makes that claim. If you want a reduction, I suggest you specify what you want it reduced to (the CCA-security of the encryption scheme?). $\endgroup$
    – D.W.
    Mar 2, 2013 at 1:46

1 Answer 1

Reset to default
1
$\begingroup$

I am not an expert on this subject, but it looks to me like the question makes some assumptions that may or may not be valid. The question claims that the Needham-Schroeder-Lowe protocol is SK-secure. However, I don't know whether there is any known proof that Needham-Schroeder-Lowe is SK-secure. The paper that was cited in the question does not appear to claim that it is SK-secure. You might want to start by first checking whether there's a known proof of its SK-security.

It's possible you might find the following paper of some relevance:

It gives a computational, reduction-oriented proof of security for the Needham-Schroeder-Lowe protocol, assuming that the encryption algorithm is CCA-secure. However, I don't know what notion of security for key exchange algorithms this paper uses; I don't know if it proves SK-security, or something else.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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