Intro

Authentication

Protocols

Poker Protocol

End

Complexity and Cryptography
Thomas Zeugmann
Hokkaido University
Laboratory for Algorithmics
https://www-alg.ist.hokudai.ac.jp/∼thomas/COCRB/

Lecture 14: Authentication, Cryptographic Protocols

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Motivation I
QuestionWhy do we need authentication?

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Motivation I
QuestionWhy do we need authentication?

We finished the last lecture by showing how realize the idea to
use a bag with two locks. Though our solution looked good, it
is not perfect. The problem is a possible attack by a third party
in the middle between Alice and Bob. Thus, we needauthentication.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Motivation I
QuestionWhy do we need authentication?

We finished the last lecture by showing how realize the idea to
use a bag with two locks. Though our solution looked good, it
is not perfect. The problem is a possible attack by a third party
in the middle between Alice and Bob. Thus, we needauthentication.
Looking again at the bag with two locks, it is easy to see that
Alice must have a possibility to verify that the lock on the bag isreally Bob’s lock, since otherwise a third party (Claire) could
pretend to be Bob and thus get access to the message in the bag.
Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Motivation II
This leads us directly to the problem of authentication. By
authentication we mean a method ensuring that a message
received indeed originates from the source it pretends to be
have sent off.
In classical communication via letters, this problem has beensolved by using hand written signatures (in the western
hemisphere) or a “hanko,” i.e., a personal seal (e.g. in China,
Japan). Thus, we need something equivalent, i.e., an electronic
signature.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Motivation II
This leads us directly to the problem of authentication. By
authentication we mean a method ensuring that a message
received indeed originates from the source it pretends to be
have sent off.
In classical communication via letters, this problem has beensolved by using hand written signatures (in the western
hemisphere) or a “hanko,” i.e., a personal seal (e.g. in China,
Japan). Thus, we need something equivalent, i.e., an electronic
signature.
That is, we are looking for a method that may serve as a digital
signature but it should be more resistant to forgery than theusually used hand written signatures.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Motivation III
As we shall see, mathematically, it works beautifully. But there
are several points of concern which we shortly address here
and which must be taken into consideration wheneverapplications are concerned.
A digital signature authenticates the document by using acomputer. What is not authenticated is the link between thatcomputer and the person for whom authentication is done.
This is a subtle point. It is a matter of faith that my computer issigning the document I intend it to. It is also a matter of faiththat my computer is not sending my private key used forsigning a document to someone else who can then signwhatever she whishes in my name.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Motivation III
As we shall see, mathematically, it works beautifully. But there
are several points of concern which we shortly address here
and which must be taken into consideration wheneverapplications are concerned.
A digital signature authenticates the document by using acomputer. What is not authenticated is the link between thatcomputer and the person for whom authentication is done.
This is a subtle point. It is a matter of faith that my computer issigning the document I intend it to. It is also a matter of faiththat my computer is not sending my private key used forsigning a document to someone else who can then signwhatever she whishes in my name.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Motivation III
As we shall see, mathematically, it works beautifully. But there
are several points of concern which we shortly address here
and which must be taken into consideration wheneverapplications are concerned.
A digital signature authenticates the document by using acomputer. What is not authenticated is the link between thatcomputer and the person for whom authentication is done.
This is a subtle point. It is a matter of faith that my computer issigning the document I intend it to. It is also a matter of faiththat my computer is not sending my private key used forsigning a document to someone else who can then signwhatever she whishes in my name.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Authentication I
Next, we describe a principal mathematical solution. The
following method is due to Taher Elgamal (1985) and based on
the Diffie-Hellman public key cryptosystem:

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Authentication I
Next, we describe a principal mathematical solution. The
following method is due to Taher Elgamal (1985) and based on
the Diffie-Hellman public key cryptosystem:
Recall that q is a huge prime, and that g is a generator of Z∗q .
Furthermore, Bob’s public key is yB .
To send his signature S, Bob chooses a random integer k withgcd(k, q − 1) = 1. Then Bob calculates r = gk mod q, solves
the following congruence for the unknown x:
gS ≡ yrB rx mod q ,(1)

and sends Alice the pair (r, x) along with S.
Now, Alice can verify that gS ≡ yrB rx mod q, and she is happy,
secure in her confidence that Bob did send the message S.
Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Authentication II
It remains to argue that Bob can perform efficiently all thecomputations necessary, and that Alice can be really happy.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Authentication II
It remains to argue that Bob can perform efficiently all thecomputations necessary, and that Alice can be really happy.
Obviously, r and gS can be efficiently computed by using ourmodular exponention Algorithm EXP.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Authentication II
It remains to argue that Bob can perform efficiently all thecomputations necessary, and that Alice can be really happy.
Obviously, r and gS can be efficiently computed by using ourmodular exponention Algorithm EXP.
But what about solving gS ≡ yrB rx mod q?

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Authentication II
It remains to argue that Bob can perform efficiently all thecomputations necessary, and that Alice can be really happy.
Obviously, r and gS can be efficiently computed by using ourmodular exponention Algorithm EXP.
But what about solving gS ≡ yrB rx mod q?
Taking into account that yB ≡ gxB mod q, we obtain, by
putting it all together:gS = gxB r gkx ≡ gxB r+kx mod q(2)

Thus, by applying Euler’s theorem to (2), we obtain theconditionS ≡ xB r + kx mod (q − 1) ,(3)and hence, x ≡ (S − xB r)k−1 mod (q − 1).
Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Authentication III
So we see why the number k has been required to satisfy
gcd(k, q − 1) = 1. Clearly, all the needed computations can be
efficiently performed by Bob.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Authentication III
So we see why the number k has been required to satisfy
gcd(k, q − 1) = 1. Clearly, all the needed computations can be
efficiently performed by Bob.
Finally, Alice can be sure to have obtained Bob’s signature,since solving the congruence gS ≡ yrB rx mod q in order todetermine x requires the knowledge of xB which is kept
secretly by Bob. Forging Bob’s signature is as complicated ascomputing discrete logarithms.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Authentication III
So we see why the number k has been required to satisfy
gcd(k, q − 1) = 1. Clearly, all the needed computations can be
efficiently performed by Bob.
Finally, Alice can be sure to have obtained Bob’s signature,since solving the congruence gS ≡ yrB rx mod q in order todetermine x requires the knowledge of xB which is kept
secretly by Bob. Forging Bob’s signature is as complicated ascomputing discrete logarithms.
Now, we also understand why the parties have to publish their
key y. It is either for using it for the key exchange described in
the previous lecture, or for performing the authentication as
described above.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Authentication IV
The only thing that kind of remains open is how S is chosen by
Bob.
Using the protocol provided above, the best choice is to use thewhole message Bob wishes to send as signature S. One
advantage of the protocol described above is the probabilistic
element introduced by the random choice of k. On the other
hand, there is also a serious disadvantage, since the ciphertext
to be send it now blown up.
So, in principal there is a beautiful mathematical solution to theauthentication problem. Next, we put authentication in the
more general context of cryptographic protocols.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Authentication IV
The only thing that kind of remains open is how S is chosen by
Bob.
Using the protocol provided above, the best choice is to use thewhole message Bob wishes to send as signature S. One
advantage of the protocol described above is the probabilistic
element introduced by the random choice of k. On the other
hand, there is also a serious disadvantage, since the ciphertext
to be send it now blown up.
So, in principal there is a beautiful mathematical solution to theauthentication problem. Next, we put authentication in the
more general context of cryptographic protocols.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Authentication IV
The only thing that kind of remains open is how S is chosen by
Bob.
Using the protocol provided above, the best choice is to use thewhole message Bob wishes to send as signature S. One
advantage of the protocol described above is the probabilistic
element introduced by the random choice of k. On the other
hand, there is also a serious disadvantage, since the ciphertext
to be send it now blown up.
So, in principal there is a beautiful mathematical solution to theauthentication problem. Next, we put authentication in the
more general context of cryptographic protocols.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Cryptographic Protocols I

Definition 1
Cryptographic protocols describe algorithms used for thecommunication between different parties, adversaries or not.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Cryptographic Protocols I

Definition 1
Cryptographic protocols describe algorithms used for thecommunication between different parties, adversaries or not.
By definition, cryptographic protocols apply cryptographictransformations. Consequently, they are at most as secure as
the underlying cryptosystem. Usually, we shall use public key
cryptosystems for cryptographic protocols.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Cryptographic Protocols I

Definition 1
Cryptographic protocols describe algorithms used for thecommunication between different parties, adversaries or not.
By definition, cryptographic protocols apply cryptographictransformations. Consequently, they are at most as secure as
the underlying cryptosystem. Usually, we shall use public key
cryptosystems for cryptographic protocols.
However, the goal of the protocol is usually something beyond
the simple secrecy of message transmission.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Cryptographic Protocols II

For example, the communicating parties may want to shareparts of their secrets to achieve a common goal, or they like toconvince the other parties that they know a particular secretwithout providing even a single bit of the secret on hand.
Protocols realizing such goals have considerably changed ourunderstanding about what is impossible when several parties,
adversaries or not, communicate with each other.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Cryptographic Protocols III
To see how digital signatures fit into the domain of protocols let
us consider the following very general task: A private
conversation should be established between two individual
users of an information system or a communication network.
We do not make any assumption concerning whether or notthese two individual users have ever communicated with eachother before.
Having a public key cryptosystem on hand, we can solve thisproblem. First, our users publish their public key. Then,
messages send to user A are encrypted by using A’s public key.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Cryptographic Protocols III
To see how digital signatures fit into the domain of protocols let
us consider the following very general task: A private
conversation should be established between two individual
users of an information system or a communication network.
We do not make any assumption concerning whether or notthese two individual users have ever communicated with eachother before.
Having a public key cryptosystem on hand, we can solve thisproblem. First, our users publish their public key. Then,
messages send to user A are encrypted by using A’s public key.
But even if the cryptosystem is considered to be secure, we still
have to deal with the problem that a user C might pretend to be
the user B when sending a message to A. To prevent theoccurrence of such situations, some convention of signingmessages has to be added to the protocol.
Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Cryptographic Protocols IV
One always has to separate security properties of the underlying
cryptosystem from those of the protocol. When doing this, thepossible adversaries should be kept in mind. In mostcommunication protocols, an adversary belongs to one of thefollowing three types:

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Cryptographic Protocols IV
One always has to separate security properties of the underlying
cryptosystem from those of the protocol. When doing this, thepossible adversaries should be kept in mind. In mostcommunication protocols, an adversary belongs to one of thefollowing three types:(1) Communicating parties who try to cheat. Later we shallmeet two types of cheaters, i.e., passive and active.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Cryptographic Protocols IV
One always has to separate security properties of the underlying
cryptosystem from those of the protocol. When doing this, thepossible adversaries should be kept in mind. In mostcommunication protocols, an adversary belongs to one of thefollowing three types:(1) Communicating parties who try to cheat. Later we shallmeet two types of cheaters, i.e., passive and active.
(2) Passive eavesdroppers. They may obtain information notintended for them, but are otherwise harmless.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Cryptographic Protocols IV
One always has to separate security properties of the underlying
cryptosystem from those of the protocol. When doing this, thepossible adversaries should be kept in mind. In mostcommunication protocols, an adversary belongs to one of thefollowing three types:(1) Communicating parties who try to cheat. Later we shallmeet two types of cheaters, i.e., passive and active.
(2) Passive eavesdroppers. They may obtain information notintended for them, but are otherwise harmless.
(3) Active eavesdroppers. Besides obtaining secret
information (as passive eavesdroppers do), they may messup the whole protocol.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Cryptographic Protocols V
In our problem above, where C tries to impersonate B, we havean adversary of Type (3), i.e., an active eavesdropper. To havean example for Type (1), just imagine that some people like toplay poker by telephone. Clearly, somebody might be tempted
to cheat. We shall come back to this point below. Looking at
typical applications of cryptography, it should be also clear thatadversaries of Type (2) may cause huge trouble, e.g., in militaryor diplomatic applications, or in banking.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Cryptographic Protocols V
In our problem above, where C tries to impersonate B, we havean adversary of Type (3), i.e., an active eavesdropper. To havean example for Type (1), just imagine that some people like toplay poker by telephone. Clearly, somebody might be tempted
to cheat. We shall come back to this point below. Looking at
typical applications of cryptography, it should be also clear thatadversaries of Type (2) may cause huge trouble, e.g., in militaryor diplomatic applications, or in banking.
For the sake of illustrating the difference between an active andpassive eavesdropper let us look at the RSA cryptosystem. We
claim that it vulnerable against attacks with chosen ciphertext.
This can be seen as follows:

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Cryptographic Protocols VI
Suppose an eavesdropper E has received
c = me mod n .

(4)

The eavesdropper E wishes to know m. Let A be the legal
receiver of m. Clearly, A will not decrypt c for E.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Cryptographic Protocols VI
Suppose an eavesdropper E has received
c = me mod n .

(4)

The eavesdropper E wishes to know m. Let A be the legal
receiver of m. Clearly, A will not decrypt c for E. But E canmodify c by using a randomly chosen x ∈ Z∗n and computingĉ = cxe ≡ m̂e mod n .

(5)Then, the eavesdropper E can send ĉ to A.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Cryptographic Protocols VI
Suppose an eavesdropper E has received
c = me mod n .

(4)

The eavesdropper E wishes to know m. Let A be the legal
receiver of m. Clearly, A will not decrypt c for E. But E canmodify c by using a randomly chosen x ∈ Z∗n and computingĉ = cxe ≡ m̂e mod n .

(5)Then, the eavesdropper E can send ĉ to A.
If E succeeds to get A to decrypt this message for him, then E
gets m̂, and thus he knows the original message m, too, sinceĉ = cxe mod n = me xe mod n = (mx)e mod n .

(6)

By construction, m̂ = mx mod n, thus m ≡ m̂x−1 mod n.
Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Cryptographic Protocols VII
In the preceding example we have not said how E succeeds to
get A to decrypt ĉ for him.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Cryptographic Protocols VII
In the preceding example we have not said how E succeeds to
get A to decrypt ĉ for him.
Assuming A is unexperienced, E may have pretended to be B
(the original sender). Then, after having encrypted ĉ, the legal
receiver A was confused, since m̂ did not make any sense toher. Thus, A sent m̂ back to E instead of sending it to B. As wehave seen, this is very dangerous and should be avoided at all.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Cryptographic Protocols VII
In the preceding example we have not said how E succeeds to
get A to decrypt ĉ for him.
Assuming A is unexperienced, E may have pretended to be B
(the original sender). Then, after having encrypted ĉ, the legal
receiver A was confused, since m̂ did not make any sense toher. Thus, A sent m̂ back to E instead of sending it to B. As wehave seen, this is very dangerous and should be avoided at all.
A much better way to recover from such a confusion is to senda request to B to resend the message.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Cryptographic Protocols VII
In the preceding example we have not said how E succeeds to
get A to decrypt ĉ for him.
Assuming A is unexperienced, E may have pretended to be B
(the original sender). Then, after having encrypted ĉ, the legal
receiver A was confused, since m̂ did not make any sense toher. Thus, A sent m̂ back to E instead of sending it to B. As wehave seen, this is very dangerous and should be avoided at all.
A much better way to recover from such a confusion is to senda request to B to resend the message.
To make the need of protocols more transparent, we provide
two more examples of weak points that may occur when using
plain RSA which also apply mutatis mutandis to many otherplain public key cryptosystems.
Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Buy, Sell, or Hold
Suppose Alice wants to send orders to her stock broker Bob. An
eavesdropper would like to know Alice’s order. Furthermore,
suppose the eavesdropper has good reason to belive that m isone of the following three messages:
m1 = “buy IBM”
m2 = “sell IBM”
m3 = “hold IBM”

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Buy, Sell, or Hold
Suppose Alice wants to send orders to her stock broker Bob. An
eavesdropper would like to know Alice’s order. Furthermore,
suppose the eavesdropper has good reason to belive that m isone of the following three messages:
m1 = “buy IBM”
m2 = “sell IBM”
m3 = “hold IBM”
The eavesdropper can compute the encryptions c1 , c2 , and c3 ofthe three messages for himself, and when Alice is sending an
encryption of one of these three messages, say m2 , theeavesdropper simple compares the ciphers and knows it is m2 .
This example shows that plain RSA can leak partial information.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Making the Lowest Bid
Suppose Alice wants to submit a number m, representing herbid, to Bob. Bob is accepting many bids, and will choose thelowest bid.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Making the Lowest Bid
Suppose Alice wants to submit a number m, representing herbid, to Bob. Bob is accepting many bids, and will choose thelowest bid.
Suppose the eavesdropper is a competitor, too, and wants tounderbid Alice by 10%. We make the reasonable assumptionthat Alice’s bid is made in round numbers and thus amounts tobe a multiple of 10. Then the eavesdropper can intercept Alice’s
encrypted message c. Now, he computeseĉ = c · 9 · 10−1 mod n ,(7)where 10−1 is the modular inverse of 10 modulo n. This inverse
exists, since n is the product of two large primes and 10 = 2 · 5.
Hence gcd(10, n) = 1. So, we have m̂ = 0.9 · m. In this way,
Alice’s competitor can underbid Alice by 10%, without knowing
anything about the value of Alice’s bid.
Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Cryptographic Protocols VIII
The property observed above that flipping some bits in the
ciphertext will also flip some bits in the message is a weakness
usually called malleability which should not occur.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Cryptographic Protocols VIII
The property observed above that flipping some bits in the
ciphertext will also flip some bits in the message is a weakness
usually called malleability which should not occur.
More generally speaking, encryption is often identified with“secure envelope” or a locked box that cannot be opened
without destroying it.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Cryptographic Protocols VIII
The property observed above that flipping some bits in the
ciphertext will also flip some bits in the message is a weakness
usually called malleability which should not occur.
More generally speaking, encryption is often identified with“secure envelope” or a locked box that cannot be opened
without destroying it.
This metaphor has a very compelling and convenient touch andis often used by engineers. However, an encryption scheme canat best approximate a “secure envelope.”

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Cryptographic Protocols VIII
The property observed above that flipping some bits in the
ciphertext will also flip some bits in the message is a weakness
usually called malleability which should not occur.
More generally speaking, encryption is often identified with“secure envelope” or a locked box that cannot be opened
without destroying it.
This metaphor has a very compelling and convenient touch andis often used by engineers. However, an encryption scheme canat best approximate a “secure envelope.”
QuestionWhy can we at best only approximate a “secure envelope?”

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Answers I
Ciphertexts are bit strings (electronically represented) and not
physical envelopes.
This has several consequences:
First, the bit string representing a ciphertext can be observedby an eavesdropper. An ideal “secure envelope” leaks no
information about the message it contains. For example, if
Alice sends two messages to Bob by using a “secureenvelope,” an eavesdropper cannot tell whether or notthese messages are identical or not. The same should holdthen for an encryption scheme. But this requirement alone
rules out any deterministic encryption scheme, i.e.,encryption schemes that encrypt the same message always
in the same way.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Answers I
Ciphertexts are bit strings (electronically represented) and not
physical envelopes.
This has several consequences:
First, the bit string representing a ciphertext can be observedby an eavesdropper. An ideal “secure envelope” leaks no
information about the message it contains. For example, if
Alice sends two messages to Bob by using a “secureenvelope,” an eavesdropper cannot tell whether or notthese messages are identical or not. The same should holdthen for an encryption scheme. But this requirement alone
rules out any deterministic encryption scheme, i.e.,encryption schemes that encrypt the same message always
in the same way.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Answers II
Second, ciphertexts can easily be replicated, whereas
messages contained in “secure envelopes” cannot. There isreally nothing we can do about this. Thus, higher levelprotocols using encryption must deal with the fact that thiscan happen.
Third, ciphertexts can easily be modified, creating otherciphertexts as we have seen above. We can do many things
to a ciphertext such as flipping some bits from ‘1’ to ‘0’ orvice versa. Even if an encryption scheme is secure, as wehave seen, flipping bits in the ciphertext may flip bits in themessage. Using the terminology introduced above, we seethat malleability cannot be tolerated in many applications.
Obviously, malleability has no counterpart in the world ofideal “secure envelopes.”
Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Answers II
Second, ciphertexts can easily be replicated, whereas
messages contained in “secure envelopes” cannot. There isreally nothing we can do about this. Thus, higher levelprotocols using encryption must deal with the fact that thiscan happen.
Third, ciphertexts can easily be modified, creating otherciphertexts as we have seen above. We can do many things
to a ciphertext such as flipping some bits from ‘1’ to ‘0’ orvice versa. Even if an encryption scheme is secure, as wehave seen, flipping bits in the ciphertext may flip bits in themessage. Using the terminology introduced above, we seethat malleability cannot be tolerated in many applications.
Obviously, malleability has no counterpart in the world ofideal “secure envelopes.”
Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Answers III and a New Question

Fourth, any bit string is potentially a ciphertext, i.e., theencryption of some message. As we have seen, the fact canalso be misused by an adversary who actively participatesin a protocol by sending its own messages to other parties.
Such a chosen ciphertext attack has also no counterpart in
the world of ideal “secure envelopes.”
Question
Can we overcome these difficulties?

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Answers III and a New Question

Fourth, any bit string is potentially a ciphertext, i.e., theencryption of some message. As we have seen, the fact canalso be misused by an adversary who actively participatesin a protocol by sending its own messages to other parties.
Such a chosen ciphertext attack has also no counterpart in
the world of ideal “secure envelopes.”
Question
Can we overcome these difficulties?

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Cryptographic Protocols IX

Hopefully, but it is very difficult to prove something.
For example, when thinking about avoiding attacks from a manin the middle, one can start from the idea that a receiver should
acknowledge the receipt of the encrypted message. Thus, if athird party has pretended to be A and has send a message to B,
but B is acknowledging it to A, A can immediately inform B
that something is wrong.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Cryptographic Protocols IX

Hopefully, but it is very difficult to prove something.
For example, when thinking about avoiding attacks from a manin the middle, one can start from the idea that a receiver should
acknowledge the receipt of the encrypted message. Thus, if athird party has pretended to be A and has send a message to B,
but B is acknowledging it to A, A can immediately inform B
that something is wrong.
Suppose EA , EB , EC , . . . are the public encryption algorithms ofparties A, B, C, . . . and DA , DB , DC , . . . are the decryption
algorithms kept secretly by A, B, C, . . . . Furthermore, let thefollowing protocol be agreed upon:Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Cryptographic Protocols X
For sending a message w from A to B the following steps haveto be performed:(1) A sends the triple (A, EB (w), B) to B.
(2) B deciphers w by using DB and sends the triple(B, EA (w), A) back to A.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Cryptographic Protocols X
For sending a message w from A to B the following steps haveto be performed:(1) A sends the triple (A, EB (w), B) to B.
(2) B deciphers w by using DB and sends the triple(B, EA (w), A) back to A.
At first glance, this protocol looks well designed. But there aresome dangers with it.
Let C be an active eavesdropper who has caught the message
for B. Since he knows the structure, he changes the triple(A, EB (w), B) to (C, EB (w), B) and sends it to B. Following theprotocol, B returns the message (B, EC (w), C) to C.
Consequently, C can decipher it and knows w. Since A is
waiting for the acknowledgment, she informs B that it did not
arrive. Now, B and A realize that something went wrong, but it
is too late. Party C already does possess w.
Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Cryptographic Protocols XI

A better variant might be the following Challenge-Response
protocol:Assumption: A and B have a common secret key k and haveagreed to use the cryptosystem f.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Cryptographic Protocols XI

A better variant might be the following Challenge-Response
protocol:Assumption: A and B have a common secret key k and haveagreed to use the cryptosystem f.
A is communicating with someone from whom she expects it
is B. For verifying this, the following protocol is used:

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

The Challenge-Response Protocol(1) A randomly generates a number r and sends it to B.
(2) The communication partner (hopefully B) encrypts r byusing the secret key k in the cryptosystem f and sends
f(r, k) back to A.
(3) A computes f(r, k) by herself and compares the computed
value with the received one. If they are identical, A
assumes that she is indeed communicating with B. If thevalues are not equal, A concludes that her partner is not B.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

The Challenge-Response Protocol(1) A randomly generates a number r and sends it to B.
(2) The communication partner (hopefully B) encrypts r byusing the secret key k in the cryptosystem f and sends
f(r, k) back to A.
(3) A computes f(r, k) by herself and compares the computed
value with the received one. If they are identical, A
assumes that she is indeed communicating with B. If thevalues are not equal, A concludes that her partner is not B.
Please think about this protocol and its security.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Playing Poker per Telephone IFirst, we have to think about the demands that such a protocol
should fulfill.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Playing Poker per Telephone IFirst, we have to think about the demands that such a protocol
should fulfill.
(i) All hands (sets of five cards) are equally likely.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Playing Poker per Telephone IFirst, we have to think about the demands that such a protocol
should fulfill.
(i) All hands (sets of five cards) are equally likely.
(ii) The hands of player A and B are disjoint.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Playing Poker per Telephone IFirst, we have to think about the demands that such a protocol
should fulfill.
(i) All hands (sets of five cards) are equally likely.
(ii) The hands of player A and B are disjoint.
(iii) Both players know their own cards but have no
information about the opponent’s hand.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Playing Poker per Telephone IFirst, we have to think about the demands that such a protocol
should fulfill.
(i) All hands (sets of five cards) are equally likely.
(ii) The hands of player A and B are disjoint.
(iii) Both players know their own cards but have no
information about the opponent’s hand.
(iv) It is possible for each of the players to find out the eventual
cheating of the other player.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Playing Poker per Telephone IFirst, we have to think about the demands that such a protocol
should fulfill.
(i) All hands (sets of five cards) are equally likely.
(ii) The hands of player A and B are disjoint.
(iii) Both players know their own cards but have no
information about the opponent’s hand.
(iv) It is possible for each of the players to find out the eventual
cheating of the other player.
We do not claim this list to be exhaustive.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Playing Poker per Telephone II
Next, we propose a protocol. A cryptosystem, classical or
public-key is used. However, neither the encryption methods
EA and EB nor the decryption methods DA and DB are
publicized. Furthermore, we assume commutativity in any
composition of E’s and D’s. The mutual order is immaterial.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Playing Poker per Telephone II
Next, we propose a protocol. A cryptosystem, classical or
public-key is used. However, neither the encryption methods
EA and EB nor the decryption methods DA and DB are
publicized. Furthermore, we assume commutativity in any
composition of E’s and D’s. The mutual order is immaterial.
Before the actual play, both players A and B agree about thenames w1 , . . . , w52 of the 52 cards. The names are chosen in away such that the cryptosystem is applicable in the sense
needed in the sequel. For instance, if EA and EB operate on
integers in a certain range then each wi , i = 1, . . . , 52, should be
an integer in this range.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Playing Poker per Telephone II
Next, we propose a protocol. A cryptosystem, classical or
public-key is used. However, neither the encryption methods
EA and EB nor the decryption methods DA and DB are
publicized. Furthermore, we assume commutativity in any
composition of E’s and D’s. The mutual order is immaterial.
Before the actual play, both players A and B agree about thenames w1 , . . . , w52 of the 52 cards. The names are chosen in away such that the cryptosystem is applicable in the sense
needed in the sequel. For instance, if EA and EB operate on
integers in a certain range then each wi , i = 1, . . . , 52, should be
an integer in this range.
Player A acts as the dealer but the roles of A and B can beinterchanged.
Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Protocol Poker
Step 1: B shuffles the cards, encrypts them using EB , and sends them toA, i.e., A receives a random permutation of EB (w1 ), . . . , EB (w52 ).
(* A can now only verify that all cards are in the game *)Step 2: A chooses 5 cards from the sequence received at random andsends them back to B as they are. (* this is B’s hand. *) A also
encrypts them by using EA and sends them to B. (* B can check *)Step 3: A again chooses 5 cards from the remaining cards and encrypts
them by using EA . The result is sent to B, i.e., B receives
EA (EB (wij )), j = 1, . . . , 5. (* this is A’s hand. *)Step 4: B applies to these five cards EA (EB (wij )), j = 1, . . . , 5, its own
deciphering algorithm DB and sends the result back to A, i.e., A
receives DB (EA (EB (wij ))) = EA (DB (EB (wij ))) = EA (wij ) .
(* that is the point where we need commutativity *)Step 5: Player A applies its own deciphering algorithm DA to the fivecards EA (wij ). Now, he also nows his hand and the game starts.
Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Protocol Poker
Step 1: B shuffles the cards, encrypts them using EB , and sends them toA, i.e., A receives a random permutation of EB (w1 ), . . . , EB (w52 ).
(* A can now only verify that all cards are in the game *)Step 2: A chooses 5 cards from the sequence received at random andsends them back to B as they are. (* this is B’s hand. *) A also
encrypts them by using EA and sends them to B. (* B can check *)Step 3: A again chooses 5 cards from the remaining cards and encrypts
them by using EA . The result is sent to B, i.e., B receives
EA (EB (wij )), j = 1, . . . , 5. (* this is A’s hand. *)Step 4: B applies to these five cards EA (EB (wij )), j = 1, . . . , 5, its own
deciphering algorithm DB and sends the result back to A, i.e., A
receives DB (EA (EB (wij ))) = EA (DB (EB (wij ))) = EA (wij ) .
(* that is the point where we need commutativity *)Step 5: Player A applies its own deciphering algorithm DA to the fivecards EA (wij ). Now, he also nows his hand and the game starts.
Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Protocol Poker
Step 1: B shuffles the cards, encrypts them using EB , and sends them toA, i.e., A receives a random permutation of EB (w1 ), . . . , EB (w52 ).
(* A can now only verify that all cards are in the game *)Step 2: A chooses 5 cards from the sequence received at random andsends them back to B as they are. (* this is B’s hand. *) A also
encrypts them by using EA and sends them to B. (* B can check *)Step 3: A again chooses 5 cards from the remaining cards and encrypts
them by using EA . The result is sent to B, i.e., B receives
EA (EB (wij )), j = 1, . . . , 5. (* this is A’s hand. *)Step 4: B applies to these five cards EA (EB (wij )), j = 1, . . . , 5, its own
deciphering algorithm DB and sends the result back to A, i.e., A
receives DB (EA (EB (wij ))) = EA (DB (EB (wij ))) = EA (wij ) .
(* that is the point where we need commutativity *)Step 5: Player A applies its own deciphering algorithm DA to the fivecards EA (wij ). Now, he also nows his hand and the game starts.
Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Protocol Poker
Step 1: B shuffles the cards, encrypts them using EB , and sends them toA, i.e., A receives a random permutation of EB (w1 ), . . . , EB (w52 ).
(* A can now only verify that all cards are in the game *)Step 2: A chooses 5 cards from the sequence received at random andsends them back to B as they are. (* this is B’s hand. *) A also
encrypts them by using EA and sends them to B. (* B can check *)Step 3: A again chooses 5 cards from the remaining cards and encrypts
them by using EA . The result is sent to B, i.e., B receives
EA (EB (wij )), j = 1, . . . , 5. (* this is A’s hand. *)Step 4: B applies to these five cards EA (EB (wij )), j = 1, . . . , 5, its own
deciphering algorithm DB and sends the result back to A, i.e., A
receives DB (EA (EB (wij ))) = EA (DB (EB (wij ))) = EA (wij ) .
(* that is the point where we need commutativity *)Step 5: Player A applies its own deciphering algorithm DA to the fivecards EA (wij ). Now, he also nows his hand and the game starts.
Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Protocol Poker
Step 1: B shuffles the cards, encrypts them using EB , and sends them toA, i.e., A receives a random permutation of EB (w1 ), . . . , EB (w52 ).
(* A can now only verify that all cards are in the game *)Step 2: A chooses 5 cards from the sequence received at random andsends them back to B as they are. (* this is B’s hand. *) A also
encrypts them by using EA and sends them to B. (* B can check *)Step 3: A again chooses 5 cards from the remaining cards and encrypts
them by using EA . The result is sent to B, i.e., B receives
EA (EB (wij )), j = 1, . . . , 5. (* this is A’s hand. *)Step 4: B applies to these five cards EA (EB (wij )), j = 1, . . . , 5, its own
deciphering algorithm DB and sends the result back to A, i.e., A
receives DB (EA (EB (wij ))) = EA (DB (EB (wij ))) = EA (wij ) .
(* that is the point where we need commutativity *)Step 5: Player A applies its own deciphering algorithm DA to the fivecards EA (wij ). Now, he also nows his hand and the game starts.
Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Playing Poker per Telephone III
Let us now see how Requirements (i) through (iv) are fulfilled.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Playing Poker per Telephone III
Let us now see how Requirements (i) through (iv) are fulfilled.
Both players know their own hand and the hands are disjoint,since B can check that the items given in Step 3 are different
from those received in Step 2.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Playing Poker per Telephone III
Let us now see how Requirements (i) through (iv) are fulfilled.
Both players know their own hand and the hands are disjoint,since B can check that the items given in Step 3 are different
from those received in Step 2.
No conclusive evidence can be presented concerning theremaining Requirements from (i) through (iv). The matterlargely depends on how truly one-way functions have beenchosen for the encryption algorithms EA and EB . For example,
it might be impossible to find wi on the basis of EB (wi ) but,still, some partial information about wi could be found.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Playing Poker per Telephone III
Let us now see how Requirements (i) through (iv) are fulfilled.
Both players know their own hand and the hands are disjoint,since B can check that the items given in Step 3 are different
from those received in Step 2.
No conclusive evidence can be presented concerning theremaining Requirements from (i) through (iv). The matterlargely depends on how truly one-way functions have beenchosen for the encryption algorithms EA and EB . For example,
it might be impossible to find wi on the basis of EB (wi ) but,still, some partial information about wi could be found.
These reflections also show why all algorithms EA and EB as
well as DA and DB must be kept secretly. Otherwise, A could
also compute EB (w1 ), . . . , EB (w52 ) and would have perfectknowledge about the cards.
Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Playing Poker per Telephone IV

We can also derive a conclusion concerning the plaintext spaceof any public-key cryptosystem. It must be so huge that no one
can encrypt the possible plaintexts in advance and can perform
decryption by simply searching through all resulting
ciphertexts.
For further illustration of the difficulties to prove that ourrequirements are fulfilled, let us consider a more concrete
scenario.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

ExampleLet us assume that A and B have agreed about a huge prime pand to represent the cards as numbers chosen from {2, . . . , p − 1}.
Each player chooses secretly for himself an encryption anddecryption exponent eA , dA and eB , dB , respectively, such thateA · dA ≡ eB · dB ≡ 1

mod p − 1 .

Then encryption and decryption are done in an RSA likefashion, i.e., EI (w) = weI mod p for I = A, B and decryptionof a cipher c is done by computing DI (w) = cdI mod p for
I = A, B.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Example - Continued
We can prove the following claim:
Claim. The property to be or not to be a quadratic residue is inherited
when using this type of encryption.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Example - Continued
We can prove the following claim:
Claim. The property to be or not to be a quadratic residue is inherited
when using this type of encryption.
Proof.
residue modulo p. Then we have  Let w be a quadratic w
w= 1, where
denotes the Legendre symbol. By thepptheorem of Euler, we then know
 
p−1
w
≡ w 2 ≡ 1 mod p .
pComplexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Example - Continued
We can prove the following claim:
Claim. The property to be or not to be a quadratic residue is inherited
when using this type of encryption.
Proof.
residue modulo p. Then we have  Let w be a quadratic w
w= 1, where
denotes the Legendre symbol. By thepptheorem of Euler, we then know
 
p−1
w
≡ w 2 ≡ 1 mod p .
pTherefore, we also have e 
 p−1 eA
p−1
w A
≡ (weA ) 2 ≡ w 2≡ 1eA ≡ 1p

mod p .

That is, weA is a quadratic residue modulo p if and only if w isa quadratic residue modulo p.
Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Conclusion

If one player has discovered this property she can cheat theother player. For example, the numerical values of the four aces
may be all a quadratic residue modulo p. When using theprotocol above, clearly A will never send a quadratic residue
modulo p to B. Again, the hands are no longer equally likely
and (iii) is also violated.
This simple example shows that one cannot take too much care.
It is very complicated to prove non-trivial theorems about the
security of protocols.

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Thank you!

Complexity and Cryptographyc Thomas Zeugmann

IntroAuthentication

Protocols

Poker Protocol

End

Taher Elgamal
Complexity and Cryptographyc Thomas Zeugmann