Appendix D: Technical and Advanced Details - Codes: The Guide to Secrecy from Ancient to Modern Times - page 538

(3) Alice computes the responses,

r 1 = s 1 + s 2 c (mod q ); r 2 ≡ t 1 + t 2 c (mod q ); and r 3 ≡ u 1 + u 2 c (mod q )

which she sends to the merchant.

(4) The merchant verifies that g r 1 g r 2 A r 3

≡

XY c (mod p ) holds and if so ac-

cepts the payment. D.6

(5) The merchant sends ( X,Y, sig( X,Y ) ,T M ,c,r 1 ,r 2 ) to the bank.

(6) The bank verifies the signature sig( X,Y ), that no double spending has
occurred, and that c and r 1 ,r 2 are valid challenge response protocols. If
all holds true, the bank pays the merchant.

Deposit Protocol:

(1) The merchant sends ( X,Y, sig( X,Y ) ,T M ,c,r 1 ,r 2 ) to the bank.

(2) The bank checks that sig( X,Y ) is valid, that the coin has not already been
spent, and that the merchant's challenge and Alice's responses r 1 ,r 2 are
valid. If all of this holds true, the bank pays the merchant.

As with the ECash scheme discussed in Section 5.8, Brands' scheme requires
the customer to reveal enough information without revealing identity. However,
if Alice tries to double-spend, we now show she will be identified and charged
with fraud.
If Alice tries to spend the same coin twice, then there will be two distinct
challenges c 1 and c 2 to which she will respond with (all congruences being
modulo q )

r (1)
c 1

s 1 + s 2 c 1 , (2) t 1 + t 2 c 1 , (3) ≡ ≡ ≡ u 1 + u 2 c 1 ,

c 1 c 1

and

r (1)
c 2

s 1 + s 2 c 2 , (2) t 1 + t 2 c 2 , (3)

≡ ≡ ≡ u 1 + u 2 c 2 ,

c 2 c 2

respectively. Hence,

r (1)
c 1

r (1)
c 2

c 2 ) and r (2) r (2)

c 2

− ≡ s 2 ( c 1 − − ≡ t 2 ( c 1 − c 2 ) ,

c 1

so

c 2 ) − 1 and t 2 ≡ c 2 ) − 1 . ( r (1)

c 1

r (1)
c 2

( r (2)
c 1

r (2)
c 2

s 2 ≡ − )( c 1 − − )( c 1 − (D.8)

D.6 This holds for valid responses from Alice since
g r 1 g r 2 A r 3

g s 1 + s 2 c
1

g t 1 + t 2 c
2

( g e 1 g e 2 ) u 1 + u 2 c ( g s 1 g t 2 A u 1 )( g s 1 g t 2 A u 2 ) c

XY c (mod p ) . ≡ ≡ ≡