Three-pass protocol

Last updated

In cryptography, 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 encryption keys. Such message protocols should not be confused with various other algorithms which use 3 passes for authentication.

Contents

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 Adi Shamir 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 encryption function E and a decryption function D. The encryption function uses an encryption key e to change a plaintext message m into an encrypted message, or ciphertext, . Corresponding to each encryption key e there is a decryption key d which allows the message to be recovered using the decryption function, . 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, . 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 for all encryption keys a and b and all messages m. Commutative encryptions satisfy .

The three-pass protocol works as follows:

  1. 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 to the receiver.
  2. The receiver chooses a private encryption key r and a corresponding decryption key q and super-encrypts the first message with the key r and sends the doubly encrypted message back to the sender.
  3. The sender decrypts the second message with the key t. Because of the commutativity property described above which is the message encrypted with only the receiver's private key. The sender sends this to the receiver.

The receiver can now decrypt the message using the key q, namely 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.

Shamir three-pass protocol

The first three-pass protocol was the Shamir three-pass protocol developed circa in 1980. It is also called the Shamir No-Key Protocol because the sender and the receiver do not exchange any keys, however the protocol requires the sender and receiver to have two private keys for encrypting and decrypting messages. The Shamir algorithm uses exponentiation modulo a large prime as both the encryption and decryption functions. That is E(e,m) = me mod p and D(d,m) = md mod p where p is a large prime. For any encryption exponent e in the range 1..p-1 with gcd(e,p-1) = 1. The corresponding decryption exponent d is chosen such that de ≡ 1 (mod p-1). It follows from Fermat's Little Theorem that D(d,E(e,m)) = mde mod p = m.

The Shamir protocol has the desired commutativity property since E(a,E(b,m)) = mab mod p = mba mod p = E(b,E(a,m)).

Massey–Omura cryptosystem

The Massey–Omura Cryptosystem was proposed by James Massey and Jim K. Omura in 1982 as a possible improvement over the Shamir protocol. The Massey–Omura method uses exponentiation in the Galois field GF(2n) as both the encryption and decryption functions. That is E(e,m)=me and D(d,m)=md where the calculations are carried out in the Galois field. For any encryption exponent e with 0<e<2n-1 and gcd(e,2n-1)=1 the corresponding decryption exponent is d such that de ≡ 1 (mod 2n-1). Since the multiplicative group of the Galois field GF(2n) has order 2n-1 Lagrange's theorem implies that mde=m for all m in GF(2n)* .

Each element of the Galois field GF(2n) is represented as a binary vector over a normal basis in which each basis vector is the square of the preceding one. That is, the basis vectors are v1, v2, v4, v8, ... where v is a field element of maximum order. By using this representation, exponentiations by powers of 2 can be accomplished by cyclic shifts. This means that raising m to an arbitrary power can be accomplished with at most n shifts and n multiplications. Moreover, several multiplications can be performed in parallel. This allows faster hardware realizations at the cost of having to implement several multipliers.

Security

A necessary condition for a three-pass algorithm to be secure is that an attacker cannot determine any information about the message m from the three transmitted messages , and .

For the encryption functions used in the Shamir algorithm and the Massey–Omura algorithm described above, the security relies on the difficulty of computing discrete logarithms in a finite field. If an attacker could compute discrete logarithms in GF(p) for the Shamir method or GF(2n) for the Massey–Omura method then the protocol could be broken. The key s could be computed from the messages mr and mrs. When s is known, it is easy to compute the decryption exponent t. Then the attacker could compute m by raising the intercepted message ms to the t power. K. Sakurai and H. Shizuya show that under certain assumptions breaking Massey–Omura cryptosystem is equivalent to the Diffie–Hellman assumption.

Authentication

The three-pass protocol as described above does not provide any authentication. Hence, without any additional authentication the protocol is susceptible to a man-in-the-middle attack if the opponent has the ability to create false messages, or to intercept and replace the genuine transmitted messages.

Related Research Articles

Public-key cryptography Cryptographic system with public and private keys

Public-key cryptography, or asymmetric cryptography, is a cryptographic system that uses pairs of keys: public keys, which may be disseminated widely, and private keys, which are known only to the owner. The generation of such keys depends on cryptographic algorithms based on mathematical problems to produce one-way functions. Effective security only requires keeping the private key private; the public key can be openly distributed without compromising security.

RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem that is widely used for secure data transmission. It is also one of the oldest. The acronym RSA comes from the surnames of Ron Rivest, Adi Shamir, and Leonard Adleman, who publicly described the algorithm in 1977. An equivalent system was developed secretly, in 1973 at GCHQ, by the English mathematician Clifford Cocks. That system was declassified in 1997.

The Merkle–Hellman knapsack cryptosystem was one of the earliest public key cryptosystems. It was published by Ralph Merkle and Martin Hellman in 1978. A polynomial time attack was published by Adi Shamir in 1984. As a result, the cryptosystem is now considered insecure.

In cryptography, a block cipher mode of operation is an algorithm that uses a block cipher to provide information security such as confidentiality or authenticity. A block cipher by itself is only suitable for the secure cryptographic transformation of one fixed-length group of bits called a block. A mode of operation describes how to repeatedly apply a cipher's single-block operation to securely transform amounts of data larger than a block.

Ciphertext

In cryptography, ciphertext or cyphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext that is unreadable by a human or computer without the proper cipher to decrypt it. Decryption, the inverse of encryption, is the process of turning ciphertext into readable plaintext. Ciphertext is not to be confused with codetext because the latter is a result of a code, not a cipher.

ID-based encryption, or identity-based encryption (IBE), is an important primitive of ID-based cryptography. As such it is a type of public-key encryption in which the public key of a user is some unique information about the identity of the user. This means that a sender who has access to the public parameters of the system can encrypt a message using e.g. the text-value of the receiver's name or email address as a key. The receiver obtains its decryption key from a central authority, which needs to be trusted as it generates secret keys for every user.

Blind signature

In cryptography a blind signature, as introduced by David Chaum, is a form of digital signature in which the content of a message is disguised (blinded) before it is signed. The resulting blind signature can be publicly verified against the original, unblinded message in the manner of a regular digital signature. Blind signatures are typically employed in privacy-related protocols where the signer and message author are different parties. Examples include cryptographic election systems and digital cash schemes.

The Rabin cryptosystem is an asymmetric cryptographic technique, whose security, like that of RSA, is related to the difficulty of integer factorization. However the Rabin cryptosystem has the advantage that it has been mathematically proven to be computationally secure against a chosen-plaintext attack as long as the attacker cannot efficiently factor integers, while there is no such proof known for RSA. It has the disadvantage that each output of the Rabin function can be generated by any of four possible inputs; if each output is a ciphertext, extra complexity is required on decryption to identify which of the four possible inputs was the true plaintext.

The Paillier cryptosystem, invented by and named after Pascal Paillier in 1999, is a probabilistic asymmetric algorithm for public key cryptography. The problem of computing n-th residue classes is believed to be computationally difficult. The decisional composite residuosity assumption is the intractability hypothesis upon which this cryptosystem is based.

In cryptography, an oblivious transfer (OT) protocol is a type of protocol in which a sender transfers one of potentially many pieces of information to a receiver, but remains oblivious as to what piece has been transferred.

Ciphertext indistinguishability is a property of many encryption schemes. Intuitively, if a cryptosystem possesses the property of indistinguishability, then an adversary will be unable to distinguish pairs of ciphertexts based on the message they encrypt. The property of indistinguishability under chosen plaintext attack is considered a basic requirement for most provably secure public key cryptosystems, though some schemes also provide indistinguishability under chosen ciphertext attack and adaptive chosen ciphertext attack. Indistinguishability under chosen plaintext attack is equivalent to the property of semantic security, and many cryptographic proofs use these definitions interchangeably.

Mental poker is the common name for a set of cryptographic problems that concerns playing a fair game over distance without the need for a trusted third party. The term is also applied to the theories surrounding these problems and their possible solutions. The name comes from the card game poker which is one of the games to which this kind of problem applies. Similar problems described as two party games are Blum's flipping a coin over a distance, Yao's Millionaires' Problem, and Rabin's oblivious transfer.

The Blum–Goldwasser (BG) cryptosystem is an asymmetric key encryption algorithm proposed by Manuel Blum and Shafi Goldwasser in 1984. Blum–Goldwasser is a probabilistic, semantically secure cryptosystem with a constant-size ciphertext expansion. The encryption algorithm implements an XOR-based stream cipher using the Blum-Blum-Shub (BBS) pseudo-random number generator to generate the keystream. Decryption is accomplished by manipulating the final state of the BBS generator using the private key, in order to find the initial seed and reconstruct the keystream.

Homomorphic encryption A form of encryption that allows computation on ciphertexts

Homomorphic encryption is a form of encryption allowing one to perform calculations on encrypted data without decrypting it first. The result of the computation is in an encrypted form, when decrypted the output is the same as if the operations had been performed on the unencrypted data.

In cryptography, Galois/Counter Mode (GCM) is a mode of operation for symmetric-key cryptographic block ciphers widely adopted for its performance. GCM throughput rates for state-of-the-art, high-speed communication channels can be achieved with inexpensive hardware resources. The operation is an authenticated encryption algorithm designed to provide both data authenticity (integrity) and confidentiality. GCM is defined for block ciphers with a block size of 128 bits. Galois Message Authentication Code (GMAC) is an authentication-only variant of the GCM which can form an incremental message authentication code. Both GCM and GMAC can accept initialization vectors of arbitrary length.

The Benaloh Cryptosystem is an extension of the Goldwasser-Micali cryptosystem (GM) created in 1985 by Josh (Cohen) Benaloh. The main improvement of the Benaloh Cryptosystem over GM is that longer blocks of data can be encrypted at once, whereas in GM each bit is encrypted individually.

The Damgård–Jurik cryptosystem is a generalization of the Paillier cryptosystem. It uses computations modulo where is an RSA modulus and a (positive) natural number. Paillier's scheme is the special case with . The order of can be divided by . Moreover, can be written as the direct product of . is cyclic and of order , while is isomorphic to . For encryption, the message is transformed into the corresponding coset of the factor group and the security of the scheme relies on the difficulty of distinguishing random elements in different cosets of . It is semantically secure if it is hard to decide if two given elements are in the same coset. Like Paillier, the security of Damgård–Jurik can be proven under the decisional composite residuosity assumption.

A threshold cryptosystem, the basis for the field of threshold cryptography, is a cryptosystem that protects information by encrypting it and distributing it among a cluster of fault-tolerant computers. The message is encrypted using a public key, and the corresponding private key is shared among the participating parties. With a threshold cryptosystem, in order to decrypt an encrypted message or to sign a message, several parties must cooperate in the decryption or signature protocol.

The Sakai–Kasahara scheme, also known as the Sakai–Kasahara key encryption algorithm (SAKKE), is an identity-based encryption (IBE) system proposed by Ryuichi Sakai and Masao Kasahara in 2003. Alongside the Boneh–Franklin scheme, this is one of a small number of commercially implemented identity-based encryption schemes. It is an application of pairings over elliptic curves and finite fields. A security proof for the algorithm was produced in 2005 by Chen and Cheng. SAKKE is described in Internet Engineering Task Force (IETF) RFC 6508.

Garbled circuit is a cryptographic protocol that enables two-party secure computation in which two mistrusting parties can jointly evaluate a function over their private inputs without the presence of a trusted third party. In the garbled circuit protocol, the function has to be described as a Boolean circuit.

References

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.