Introduction

Advanced DS

Undeniable DS

Disavowal

End

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

Lecture 16: Digital Signatures

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Motivation I
We consider two parties A and B with possibly conflicting
interests. Typically, the parties could be a bank and its customer,
any two parties wishing to do business over the internet,
diplomats from countries with different interests, and so on.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Motivation I
We consider two parties A and B with possibly conflicting
interests. Typically, the parties could be a bank and its customer,
any two parties wishing to do business over the internet,
diplomats from countries with different interests, and so on.
If we are doing business on the internet we require security andtrust, since we cannot see the person we are dealing with; wecannot see any document proving the partner’s identity, andwe cannot even know if the web site we are connected tobelongs to the society it says.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Motivation I
We consider two parties A and B with possibly conflicting
interests. Typically, the parties could be a bank and its customer,
any two parties wishing to do business over the internet,
diplomats from countries with different interests, and so on.
If we are doing business on the internet we require security andtrust, since we cannot see the person we are dealing with; wecannot see any document proving the partner’s identity, andwe cannot even know if the web site we are connected tobelongs to the society it says.
To answer these juridical demands, the European Union
adopted a community framework for electronic signatures
some time ago (directive 1999/93/EC of the European
Parliament and the council of December 13, 1999, on acommunity framework for electronic signatures) that has been
implemented in various European countries.
Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Motivation II

The European directive is used for business in which European
partners (persons or societies) or public administrations are
involved. It also means that if a Japanese or an Americanorganization enters into an electronic contract with a European
society it has to respect European requirements to ensure thecontract is valid.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Motivation II

The European directive is used for business in which European
partners (persons or societies) or public administrations are
involved. It also means that if a Japanese or an Americanorganization enters into an electronic contract with a European
society it has to respect European requirements to ensure thecontract is valid.
Japan also has an e-Signature Law that formally took effect inApril 2001. We shall focus here on important general
requirements. For all details, please study the correspondinglaws.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Motivation III
Important: If we copy a conventionally signed document, thenthere are usually ways for distinguishing the copied document
and the original one. But a copy of a signed digital document is
identical to the original one.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Motivation III
Important: If we copy a conventionally signed document, thenthere are usually ways for distinguishing the copied document
and the original one. But a copy of a signed digital document is
identical to the original one.
So, if A sends a message to B authorizing B to withdraw 1000 €form A’s bank account then the intention is usually that B isdoing it once and not all the time B feels the need ofgetting 1000 €.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Motivation III
Important: If we copy a conventionally signed document, thenthere are usually ways for distinguishing the copied document
and the original one. But a copy of a signed digital document is
identical to the original one.
So, if A sends a message to B authorizing B to withdraw 1000 €form A’s bank account then the intention is usually that B isdoing it once and not all the time B feels the need ofgetting 1000 €.
Since the identity of the digital copy and the digital originalcannot be prevented, the message itself should contain thenecessary information such as a date, the clear statement once,and so on.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Motivation IV
A digital signature is usually based on public-key
cryptographic systems. European law distinguishes between
an electronic signature (also called weak digital signature) and an
advanced electronic signature.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Motivation IV
A digital signature is usually based on public-key
cryptographic systems. European law distinguishes between
an electronic signature (also called weak digital signature) and an
advanced electronic signature.
QuestionWhy do we have to distinguish between a weak digital
signature and an advanced electronic signature?

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Motivation IV
A digital signature is usually based on public-key
cryptographic systems. European law distinguishes between
an electronic signature (also called weak digital signature) and an
advanced electronic signature.
QuestionWhy do we have to distinguish between a weak digital
signature and an advanced electronic signature?

A weak digital signature is used for authentication. That is, sucha signature should prove that the person who sent the text isthe electronic signature’s holder. However, we cannot be surethat the person who sent the message is also the key owner (cf.
Lecture 14).
Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Motivation V
The key owner does not only have the means to sign a message
appropriately but has also the explicit right to use it.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Motivation V
The key owner does not only have the means to sign a message
appropriately but has also the explicit right to use it.
For seeing the difference, we look at a typical example. Usuallya key holder would be a server that creates signatures on, forexample, a company’s software. The company or employee
would be the key owner. So, someone in the company could
hack the server and sign something contentious using thecompany’s authority.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Motivation V
The key owner does not only have the means to sign a message
appropriately but has also the explicit right to use it.
For seeing the difference, we look at a typical example. Usuallya key holder would be a server that creates signatures on, forexample, a company’s software. The company or employee
would be the key owner. So, someone in the company could
hack the server and sign something contentious using thecompany’s authority.
Also, an electronic signature does not guarantee the integrity ofthe message signed. That is, a third party may have altered thetext sent without having changed the signature. Of course, thisis usually not what we want. We also want to be sure that the
text received is the same that was sent, and that no hacker hadchanged it.
Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Motivation VI

To summarize, authentication guarantees that the message
received, say from A, has been really sent by A. It should be atleast very difficult if not impossible for a third party C topretend to be A.
Integrity guarantees that the message received is the same as
the message sent. So, no third party and also not the legal
recipient should be able to forge a message and to pretend tohave received it in properly signed form from A.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Motivation VI

To summarize, authentication guarantees that the message
received, say from A, has been really sent by A. It should be atleast very difficult if not impossible for a third party C topretend to be A.
Integrity guarantees that the message received is the same as
the message sent. So, no third party and also not the legal
recipient should be able to forge a message and to pretend tohave received it in properly signed form from A.
Putting these requirements together leads to an advanced
electronic signature.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Requirements to an advanced electronic signature(1) it is uniquely linked to the signatory;(2) it is capable of identifying the signatory;(3) it is created using means that the signatory can maintainunder his sole control; and(4) it is linked to the data to which it relates such that any
subsequent change of the data is detectable.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Requirements to an advanced electronic signature(1) it is uniquely linked to the signatory;(2) it is capable of identifying the signatory;(3) it is created using means that the signatory can maintainunder his sole control; and(4) it is linked to the data to which it relates such that any
subsequent change of the data is detectable.
In some sense, these requirements are contradictory. For
verifying that the message received is from A, as claimed, B
should know at least something about A’s signature. For B not
being able to manipulate a signed message received from A (orfor a third party C aiming the same), neither B nor any third
party should know too much about A’s signature.
Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Realizing Advanced Digital Signatures I

So, let us first see how these requirements can be fulfilledsimultaneously, at least in principle, when using a public-key
cryptosystem.
We denote by EA , EB , . . . , and DA , DB , . . . , the encryption anddecryption algorithms (keys) used by the parties A, B, . . . .
Then the following protocol can be used: Let us assume that A
sends a message to B.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Protocol DS
Step 1: First, A applies to message w she wants to send
her decryption algorithm DA obtainingb = DA (w). Then she computeswbc = EB (w)and sends c to B.
Step 2: First, B applies DB to the message c received, i.e.,
B computes ĉ = DB (c). Then B computes
w = EA (ĉ) .

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Protocol DS
Step 1: First, A applies to message w she wants to send
her decryption algorithm DA obtainingb = DA (w). Then she computeswbc = EB (w)and sends c to B.
Step 2: First, B applies DB to the message c received, i.e.,
B computes ĉ = DB (c). Then B computes
w = EA (ĉ) .
Observe that the protocol is correct, since by associativity wehave
EA (DB (EB (DA (w)))) = EA (DA (w)) = w .
Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of Protocol DS(1) Taking into account that only A knows DA neither B nor athird party C can forge A’s signature.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of Protocol DS(1) Taking into account that only A knows DA neither B nor athird party C can forge A’s signature.
(2) A cannot deny having sent the signed message to B, since
A is the only one knowing DA .

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of Protocol DS(1) Taking into account that only A knows DA neither B nor athird party C can forge A’s signature.
(2) A cannot deny having sent the signed message to B, since
A is the only one knowing DA .
(3) If the underlying public-key cryptosystem is indeed
satisfactory, then the application of DA changes the whole
text and not only the name of the sender A. Thus, even if
many messages are exchanged, it seems hard to get someknowledge concerning A’s signature.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of Protocol DS – continued
Question I
Why A first applies DA and then EB ?

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of Protocol DS – continued
Question I
Why A first applies DA and then EB ?

She could also first apply EB and then DA . This would requirethat B is also changing the order of applications, i.e., first EA
and then DB . Consequently, the protocol would be still correct.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of Protocol DS – continued
Question I
Why A first applies DA and then EB ?

She could also first apply EB and then DA . This would requirethat B is also changing the order of applications, i.e., first EA
and then DB . Consequently, the protocol would be still correct.
Question II
Does this mean that we have two possibilities for designing ouradvanced digital signature scheme?

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

AnswerFor seeing the difference let us assume that C is aneavesdropper.
So, C catches the message from A and makes sure that it is notdirectly delivered to B.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

AnswerFor seeing the difference let us assume that C is aneavesdropper.
So, C catches the message from A and makes sure that it is notdirectly delivered to B.
If we use the second version, then C may herself apply EA andhas now EB (w). This gives C the possibility to sign the message
with her own name by applying DC to it. If C transmits
DC (EB (w)) to B then B would verify to have received themessage from C instead of having received it from A.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

AnswerFor seeing the difference let us assume that C is aneavesdropper.
So, C catches the message from A and makes sure that it is notdirectly delivered to B.
If we use the second version, then C may herself apply EA andhas now EB (w). This gives C the possibility to sign the message
with her own name by applying DC to it. If C transmits
DC (EB (w)) to B then B would verify to have received themessage from C instead of having received it from A.
Thus, though the original plaintext remains unchanged theidentity of the sender (that is A) is gone.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

AnswerFor seeing the difference let us assume that C is aneavesdropper.
So, C catches the message from A and makes sure that it is notdirectly delivered to B.
If we use the second version, then C may herself apply EA andhas now EB (w). This gives C the possibility to sign the message
with her own name by applying DC to it. If C transmits
DC (EB (w)) to B then B would verify to have received themessage from C instead of having received it from A.
Thus, though the original plaintext remains unchanged theidentity of the sender (that is A) is gone.
Because of this potential difficulty, our Protocol DS was
designed in a way that sending happened before encryption.
Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of Protocol DS – continued

Our Protocol DS has also the advantage that only the legal
recipient can read it provided DB is kept secret. This property
is usually referred to as confidentiality.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of Protocol DS – continued

Our Protocol DS has also the advantage that only the legal
recipient can read it provided DB is kept secret. This property
is usually referred to as confidentiality.
But still, we have a problem.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of Protocol DS – continued

Our Protocol DS has also the advantage that only the legal
recipient can read it provided DB is kept secret. This property
is usually referred to as confidentiality.
But still, we have a problem.
The Protocol DS does not take care of two issues that are very
important:
A can still deny to have sent the message and B can deny to havereceived it.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of Protocol DS – continued

Our Protocol DS has also the advantage that only the legal
recipient can read it provided DB is kept secret. This property
is usually referred to as confidentiality.
But still, we have a problem.
The Protocol DS does not take care of two issues that are very
important:
A can still deny to have sent the message and B can deny to havereceived it.
In terms of law these two issues are summarized by the term
non-repudiation.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Undeniable Digital Signature

A digital signature satisfying authentication, integrity,
confidentiality and non-repudiation is usually called strong
digital signature or undeniable digital signature.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Undeniable Digital Signature

A digital signature satisfying authentication, integrity,
confidentiality and non-repudiation is usually called strong
digital signature or undeniable digital signature.
In order to arrive at undeniable digital signatures, one has tocombine the Protocol DS with a challenge response protocol as
described in Lecture 14.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

An Undeniable Digital Signature Scheme I
We describe here an undeniable digital signature scheme thatwas introduced by Chaum and van Antwerpen in 1989. It
consists of three components:
a signing algorithm sig,
a verification protocol, anda disavowal protocol.
Again we assume that A sends a message to B.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

An Undeniable Digital Signature Scheme I
We describe here an undeniable digital signature scheme thatwas introduced by Chaum and van Antwerpen in 1989. It
consists of three components:
a signing algorithm sig,
a verification protocol, anda disavowal protocol.
Again we assume that A sends a message to B.
The new point is that A’s cooperation is required to verify asignature made by the signer A. This protects A against thepossibility that documents signed by her are duplicated anddistributed electronically without her approval.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

An Undeniable Digital Signature Scheme II
Question
But what prevents A from disavowing a signature made by her
at an earlier time?

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

An Undeniable Digital Signature Scheme II
Question
But what prevents A from disavowing a signature made by her
at an earlier time?
Participant A might claim that a valid signature is a forgery,and either refuse to verify it, or carry out the verification in away such that the valid signature will not be verified.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

An Undeniable Digital Signature Scheme II
Question
But what prevents A from disavowing a signature made by her
at an earlier time?
Participant A might claim that a valid signature is a forgery,and either refuse to verify it, or carry out the verification in away such that the valid signature will not be verified.
That is the point where the disavowal protocol comes into play.
Using this disavowal protocol, A can prove that a signature notmade by her is indeed a forgery. Now, if A refuses to take part inthis disavowal protocol, court will take this as evidence that thesignature given has been made by A.
Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Protocol CvA
Let p = 2q + 1 be a prime such that q is prime and the discrete
log problem in Zp is intractible. Let α ∈ Z∗p be an element oforder q. Let 1 6 a 6 q − 1 and define β = αa mod p.
Furthermore, by G we denote the multiplicative subgroupof Z∗p of order q. Note that G consists of the quadratic residues
modulo p.
The values p, α and β are public and a is kept secret by A.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Protocol CvA
Let p = 2q + 1 be a prime such that q is prime and the discrete
log problem in Zp is intractible. Let α ∈ Z∗p be an element oforder q. Let 1 6 a 6 q − 1 and define β = αa mod p.
Furthermore, by G we denote the multiplicative subgroupof Z∗p of order q. Note that G consists of the quadratic residues
modulo p.
The values p, α and β are public and a is kept secret by A.
The plaintext messages x are assumed to be elements of G and
so are the ciphers (as we shall see in a moment).

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Protocol CvA
Let p = 2q + 1 be a prime such that q is prime and the discrete
log problem in Zp is intractible. Let α ∈ Z∗p be an element oforder q. Let 1 6 a 6 q − 1 and define β = αa mod p.
Furthermore, by G we denote the multiplicative subgroupof Z∗p of order q. Note that G consists of the quadratic residues
modulo p.
The values p, α and β are public and a is kept secret by A.
The plaintext messages x are assumed to be elements of G and
so are the ciphers (as we shall see in a moment).
A signs the plaintext message x by computing
y = sig(x) = xa

mod p

Then she sends (y, x) to B.
Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Verification Protocol
The verification (for x, y ∈ G) is done by executing thefollowing steps:
Step 1: B chooses randomly e1 , e2 ∈ Z∗q .
Step 2: B computes (the challenge) c = ye1 βe2 mod p and sends it
to A.
Step 3: A computes the modular inverse a−1 of a modulo q and−1then d = ca
mod p and sends it to B.
Step 4: B accepts y as a valid signature if and only ifd ≡ xe1 αe2mod p .

end

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Remarks

We explain the roles of p and q in this scheme.
The scheme lives in Zp but we need to be able to perform
computations in a multiplicative subgroup G of Z∗p of prime
order.
In particular, we need to be able to compute inverses
modulo |G|. This is the reason why |G| should be prime. It isconvenient to take a prime p such that p = 2q + 1, where q isprime, i.e., q is a Sophie Germain prime. In this way, thesubgroup is as large as possible. This is desirable, since
plaintexts and ciphers are both elements of G.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of the Verification Protocol I
Claim 1. B will accept a valid signature y.
Proof. In the following computations, all exponents are assumed
to be reduced modulo p:First, observe that−1d ≡ ca−1−1≡ ye1 a βe2 a

mod p .

Since β ≡ αa mod p we have−1βa

≡ α mod p .
−1

Similarly, y = xa mod p implies that ya
d ≡ xe 1 αe 2

≡ x mod p. Hence,

mod p

as desired. This proves Claim 1.
Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Example 1
We take p = 467. Thus, q = (467 − 1)/2 = 233. Then 2 is a
generator of Z∗p . We can conclude that 22 = 4 is a generatorof G, the quadratic residues modulo p. Thus, we take α = 4.
Let a = 101 be A’s secret number. Thenβ = 4101 ≡ 449

Complexity and Cryptography

mod 467 .

c Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Example 1
We take p = 467. Thus, q = (467 − 1)/2 = 233. Then 2 is a
generator of Z∗p . We can conclude that 22 = 4 is a generatorof G, the quadratic residues modulo p. Thus, we take α = 4.
Let a = 101 be A’s secret number. Thenβ = 4101 ≡ 449

mod 467 .

A wishes to sign the message x = 119.
Thus she computes
y = 119101 ≡ 129 mod 467 .

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Example 2 (continued)
Next, suppose B wants to verify the signature 129. Suppose, B
has chosen at random e1 = 38 and e2 = 397. Then B computesc = 12938 · 449397 ≡ 13 mod 467 .
A in turn first computes the modular inverse a−1 of 101
modulo 233 which is 30. Then she calculates−1

d = camod 467 ≡ 1330 ≡ 9 mod 467 .

Finally, B checks the response by verifying that
11938 · 4397 ≡ 9 mod 467 .
Hence, B accepts A’s signature as valid.
Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of the Verification Protocol II
Next, we prove that A cannot fool B into accepting a fraudulent
signature as valid, except with a very small probability.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of the Verification Protocol II
Next, we prove that A cannot fool B into accepting a fraudulent
signature as valid, except with a very small probability.
Theorem 1
If y . xa mod p, then B will accept y as a valid signature for x
with probability 1/q.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of the Verification Protocol II
Next, we prove that A cannot fool B into accepting a fraudulent
signature as valid, except with a very small probability.
Theorem 1
If y . xa mod p, then B will accept y as a valid signature for x
with probability 1/q.
Proof. First we observe that each possible challenge ccorresponds to exactly q ordered pairs (e1 , e2 ). This is because
y and β are both elements of the multiplicative group G ofprime order q.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of the Verification Protocol II
Next, we prove that A cannot fool B into accepting a fraudulent
signature as valid, except with a very small probability.
Theorem 1
If y . xa mod p, then B will accept y as a valid signature for x
with probability 1/q.
Proof. First we observe that each possible challenge ccorresponds to exactly q ordered pairs (e1 , e2 ). This is because
y and β are both elements of the multiplicative group G ofprime order q. Now, when A receives the challenge c she has
no way of knowing which of the q possible pairs (e1 , e2 ) B has
been used to construct c.
Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of the Verification Protocol III
Claim 2. If y . xa mod p, then any possible response d ∈ Gthat A might make is consistent with exactly one of the qpossible ordered pairs (e1 , e2 ).

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of the Verification Protocol III
Claim 2. If y . xa mod p, then any possible response d ∈ Gthat A might make is consistent with exactly one of the qpossible ordered pairs (e1 , e2 ).
Proof. Since α generates G, we can write any element g of G as a
power of α, say g = αz where the exponent z is determineduniquely modulo q. So, we can writec = αid = αjx = αkand y = α` ,where i, j, k, ` ∈ Zq and all arithmetic is done modulo q.
Consider the following two congruences:c ≡ ye1 βe2 mod pd ≡ xe1 αe2 mod p

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of the Verification Protocol IV
The system above is equivalent to the following system:i ≡ `e1 + ae2 mod q
j ≡ ke1 + e2 mod q .
Now, we are assuming thaty . xa mod p ,so it follows that
` . ak mod q .
Hence, the coefficient matrix of this system of congruences
modulo q has non-zero determinant. Therefore, there is aunique solution to the system. That is, every d ∈ G is thecorrect response for exactly one of the q possible orderedpairs (e1 , e2 ).
Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of the Verification Protocol IV

Consequently, the probability that A gives B a response d thatwill be verified is is exactly 1/q, and the theorem is shown.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of the Verification Protocol IV

Consequently, the probability that A gives B a response d thatwill be verified is is exactly 1/q, and the theorem is shown.
Finally, we turn our attention to the disavowal protocol. This
protocol consists of two runs of the verification protocol.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

The Disavowal Protocol
Step 1: B chooses e1 , e2 ∈ Z∗q at random.
Step 2: B computes c = ye1 βe2 mod p and sends it to A.
Step 3: A computes a−1 modulo q and then d = ca
it to B.

−1

mod p and sends

Step 4: B verifies that d . xe1 αe2 mod p.
Step 5: B chooses f1 , f2 ∈ Z∗q at random.
Step 6: B computes C = yf1 βf2 mod p and sends it to A.
Step 7: A computes a−1 modulo q and then D = Casends it to B.

−1

mod p andStep 8: B verifies that D . xf1 αf2 mod p.
Step 9: B concludes that y is a forgery if and only iff e1
dα−e2 1 ≡ Dα−f2
mod p .
Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Example 3
Again, we take p = 467, q = 233, α = 4, a = 101 and β = 449.
Let message x = 286 be signed with the bogus signature y = 83.
A wants to convince B that the signature is invalid.
Furthermore, suppose B begins choosing at random values
e1 = 45 and e2 = 237. B then computesc = ye1 βe2 ≡ 8345 449237 ≡ 305

mod 467 ,and A responds with−1

d = ca≡ 30530 ≡ 109 mod 467 .

Then B computes 28645 4237 ≡ 149 mod 467 .
Since 149 , 109, B proceeds to Step 5 of the protocol.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Example 4 (continued)
Now, B chooses at random f1 = 125 and f2 = 9, and computes
C = 83125 4499 ≡ 270

mod 467 ,and A responds with−1

D = Ca≡ 27030 ≡ 68

mod 467 .

Now B verifies that 68 . 286125 49 ≡ 25 mod 467 .
Thus, B performs the consistency check in Step 9 and obtains

125

45
109 · 4−237≡ 188 ≡ 68 · 4−9

mod 467 .

Thus, the consistency check succeeds and B is convinced thatthe signature is not valid.
Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Remarks

Steps 1 through 4 and Steps 5 through 8 comprise two
unsuccessful runs of the verification protocol. Step 9 is a“consistency check” that enables B to determine if A is forming
her responses in the manner specified in the protocol.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Remarks

Steps 1 through 4 and Steps 5 through 8 comprise two
unsuccessful runs of the verification protocol. Step 9 is a“consistency check” that enables B to determine if A is forming
her responses in the manner specified in the protocol.
We have to show two things at this point.
(1) A can convince B that an invalid signature is a forgery.
(2) A cannot make B believe that a valid signature is a forgery
except with a very small probability.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Remarks

Steps 1 through 4 and Steps 5 through 8 comprise two
unsuccessful runs of the verification protocol. Step 9 is a“consistency check” that enables B to determine if A is forming
her responses in the manner specified in the protocol.
We have to show two things at this point.
(1) A can convince B that an invalid signature is a forgery.
(2) A cannot make B believe that a valid signature is a forgery
except with a very small probability.
First, we show the following:

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of the Disavowal Protocol I
Theorem 2
If y . xa mod p, and B and A follow the disavowal protocol, thene(dα−e2 )f1 ≡ Dα−f2 1 mod p .

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of the Disavowal Protocol I
Theorem 2
If y . xa mod p, and B and A follow the disavowal protocol, thene(dα−e2 )f1 ≡ Dα−f2 1 mod p .
Proof. Using the facts that
d
c
β
dα−e2

Complexity and Cryptography

−1

≡ ca
mod p
≡ ye1 βe2 mod p
≡ α
f 1

≡

a

mod p ,
andwe have that(ye1 βe2 )a

−1

α−e2

f 1

mod p

−1

≡
≡

ye1 f1 βe2 a f1 α−e2 f1 mod p
ye1 f1 αe2 f1 α−e2 f1 mod p≡

ye1 f1 mod p .
c Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of the Disavowal Protocol II

Using the facts that−1

D ≡ Ca

mod p

f1

f2

a

mod p ,C ≡ y ββ ≡ αmod p anda similar computation establishes that
Dα−f2

 e1

≡ ye1 f1

mod p ,and therefore the consistency check in Step 9 succeeds.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of the Disavowal Protocol III

Now we look at the possibility that A might attempt to disavow
a valid signature.
In this situation we do not assume that A follows the protocol.
That is, A might not construct d and D as specified by the
protocol.
Hence, in the following theorem, we only assume that A is able
to produce values d and D which satisfy the conditions in Steps
4, 8, and 9 of the Disavowal Protocol presented above.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of the Disavowal Protocol IV
Theorem 3
Suppose y ≡ xa mod p and B follows the Disavowal Protocol. If
d . xe 1 αe 2

mod p

D . xf 1 αf 2

mod p

and
then the probability that
dα−e2

f1

. Dα−f2

 e1

mod p

is 1 − 1/q.
Proof. The proof is done indirectly.
Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of the Disavowal Protocol V
Suppose the following is satisfied:y ≡ xa mod p
d . xe1 αe2 mod p
D . xf1 αf2 mod pefdα−e2 1 ≡ Dα−f2 1 mod p .
We shall derive a contradiction as follows:
The consistency check (cf. Step 9) can be rewritten in thefollowing form:D ≡ df01 αf2 mod p ,where
d0 = d1/e1 α−e2 /e1

mod p

is a value that depends only on steps 1 through 4 of the
Disavowal protocol.
Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of the Disavowal Protocol V
Suppose the following is satisfied:y ≡ xa mod p
d . xe1 αe2 mod p
D . xf1 αf2 mod pefdα−e2 1 ≡ Dα−f2 1 mod p .
We shall derive a contradiction as follows:
The consistency check (cf. Step 9) can be rewritten in thefollowing form:D ≡ df01 αf2 mod p ,where
d0 = d1/e1 α−e2 /e1

mod p

is a value that depends only on steps 1 through 4 of the
Disavowal protocol.
Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of the Disavowal Protocol VI
Applying Theorem 1, we conclude that y is a valid signature ford0 with probability 1 − 1/q. But we are assuming that y is avalid signature for x. That is, with high probability we havex a ≡ da0

mod pwhich implies that x = d0 .

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of the Disavowal Protocol VI
Applying Theorem 1, we conclude that y is a valid signature ford0 with probability 1 − 1/q. But we are assuming that y is avalid signature for x. That is, with high probability we havex a ≡ da0

mod pwhich implies that x = d0 .
However, the fact thatd . xe1 αe2

mod pmeans that thatx . d1/e1 α−e2 /e1Complexity and Cryptography

mod p .

c Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Properties of the Disavowal Protocol VII

Since
d0 ≡ d1/e1 α−e2 /e1

mod p

we conclude that x , d0 , and we have a contradiction.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Advanced DS

Undeniable DS

Disavowal

End

Thank you!

Complexity and Cryptographyc Thomas Zeugmann