Three-pass protocol

In <a href="/facts/Cryptography/e94PEVau">cryptography</a>, a three-pass protocol for sending messages is a framework which allows one party to securely send a message to a second party without the need to exchange or distribute <a href="/facts/Key_(cryptography)/5W5PAmT4">encryption keys</a>. Such message protocols should not be confused with various other algorithms which use 3 passes for <a href="/facts/Authentication/64y4S69b">authentication</a>. 
It is called a three-pass protocol because the sender and the receiver exchange three encrypted messages. The first three-pass protocol was developed by <a href="/facts/Adi_Shamir/CTnaUeP6">Adi Shamir</a> circa 1980, and is described in more detail in a later section. The basic concept of the three-pass protocol is that each party has a private encryption key and a private decryption key. The two parties use their keys independently, first to encrypt the message, and then to decrypt the message.
The protocol uses an <a href="/facts/Encryption/16q29Fdv">encryption function</a> E and a decryption function D. The encryption function uses an <a href="/facts/Encryption_key/5W5PAmT4">encryption key</a> e to change a <a href="/facts/Plaintext/tWnBDCgE">plaintext</a> message m into an encrypted message, or <a href="/facts/Ciphertext/luNTs4sY">ciphertext</a>, ⁠
 
 
 
 E
 (
 e
 ,
 m
 )
 
 
 {\displaystyle E(e,m)}
 
⁠. Corresponding to each encryption key e there is a decryption key d which allows the message to be recovered using the decryption function, ⁠
 
 
 
 D
 (
 d
 ,
 E
 (
 e
 ,
 m
 )
 )
 =
 m
 
 
 {\displaystyle D(d,E(e,m))=m}
 
⁠. Sometimes the encryption function and decryption function are the same.
In order for the encryption function and decryption function to be suitable for the three-pass protocol they must have the property that for any message m, any encryption key e with corresponding decryption key d and any independent encryption key k, ⁠
 
 
 
 D
 (
 d
 ,
 E
 (
 k
 ,
 E
 (
 e
 ,
 m
 )
 )
 )
 =
 E
 (
 k
 ,
 m
 )
 
 
 {\displaystyle D(d,E(k,E(e,m)))=E(k,m)}
 
⁠. In other words, it must be possible to remove the first encryption with the key e even though a second encryption with the key k has been performed. This will always be possible with a commutative encryption. A commutative encryption is an encryption that is order-independent, i.e. it satisfies ⁠
 
 
 
 E
 (
 a
 ,
 E
 (
 b
 ,
 m
 )
 )
 =
 E
 (
 b
 ,
 E
 (
 a
 ,
 m
 )
 )
 
 
 {\displaystyle E(a,E(b,m))=E(b,E(a,m))}
 
⁠ for all encryption keys a and b and all messages m. Commutative encryptions satisfy ⁠
 
 
 
 D
 (
 d
 ,
 E
 (
 k
 ,
 E
 (
 e
 ,
 m
 )
 )
 )
 =
 D
 (
 d
 ,
 E
 (
 e
 ,
 E
 (
 k
 ,
 m
 )
 )
 )
 
 
 {\displaystyle D(d,E(k,E(e,m)))=D(d,E(e,E(k,m)))}
 
⁠.
The three-pass protocol works as follows:

<ol><li>The sender chooses a private encryption key s and a corresponding decryption key t. The sender encrypts the message m with the key s and sends the encrypted message ⁠
 
 
 
 E
 (
 s
 ,
 m
 )
 
 
 {\displaystyle E(s,m)}
 
⁠ to the receiver.</li>
<li>The receiver chooses a private encryption key r and a corresponding decryption key q and <a href="/facts/Superencryption/MVN9Jz66">super-encrypts</a> the first message ⁠
 
 
 
 E
 (
 s
 ,
 m
 )
 
 
 {\displaystyle E(s,m)}
 
⁠ with the key r and sends the doubly encrypted message ⁠
 
 
 
 E
 (
 r
 ,
 E
 (
 s
 ,
 m
 )
 )
 
 
 {\displaystyle E(r,E(s,m))}
 
⁠ back to the sender.</li>
<li>The sender decrypts the second message with the key t. Because of the commutativity property described above ⁠
 
 
 
 D
 (
 t
 ,
 E
 (
 r
 ,
 E
 (
 s
 ,
 m
 )
 )
 )
 =
 E
 (
 r
 ,
 m
 )
 
 
 {\displaystyle D(t,E(r,E(s,m)))=E(r,m)}
 
⁠ which is the message encrypted with only the receiver's private key. The sender sends this to the receiver.</li></ol>
The receiver can now decrypt the message using the key q, namely ⁠
 
 
 
 D
 (
 q
 ,
 E
 (
 r
 ,
 m
 )
 )
 =
 m
 
 
 {\displaystyle D(q,E(r,m))=m}
 
⁠ the original message.
Notice that all of the operations involving the sender's private keys s and t are performed by the sender, and all of the operations involving the receiver's private keys r and q are performed by the receiver, so that neither party needs to know the other party's keys.

Three-pass protocol open-in-new

Three-pass protocol