# A reduction proof of SK-security for the Needham-Schroeder-Lowe protocol

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?

• 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". – D.W. Feb 28 '13 at 0:38
• @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? – Brian Feb 28 '13 at 15:47
• 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?). – D.W. Mar 2 '13 at 1:46