Cryptography Reference
In-Depth Information
(2)
The bank stores (
A,I
A
,N
A
) in its database where
I
A
is a digital data
string uniquely identifying Alice and
N
A
is her account number.
Identification Protocol:
D.1
When Alice wishes to withdraw coins from
her account, she must first identify herself to the bank's satisfaction.
g
f
1
g
f
2
∈
Z
Z
)
∗
, at random, computes
f
≡
(1) Alice generates
f
1
,f
2
(
/q
(mod
p
),
2
and sends
f
to the bank.
)
∗
(2)
The bank generates a random
k
∈
(
Z
/q
Z
(the challenge), and sends it
to Alice.
(3)
Alice computes
1
≡
f
1
+
ke
1
(mod
q
) and
2
≡
f
2
+
ke
2
(mod
q
) (the
responses) and sends (
1
,
2
) to the bank.
g
1
g
2
(mod
p
).
D.2
(5) If the bank accepts her response in step (4), it sends her an identification
number
y
1
=
A
x
.
(
By completing step
(5)
, Alice proves that she owns
A
. She does this by a
proof of knowledge of
(
e
1
,e
2
)
.
)
(4) The bank accepts her response if and only if
fA
k
≡
Coin Withdrawal Protocol:
For simplicity, we assume that Alice wants
to withdraw only one coin, a six-tuple of integers (
X,Y,Y
1
,Y
2
,Y
3
,Z
), which we
will now see how to construct.
)
∗
, computes
y
2
≡
α
w
(mod
p
),
(1) The bank chooses a random
w
∈
(
Z
/q
Z
A
w
(mod
p
), and sends (
y
2
,y
3
) to Alice.
y
3
≡
∈
Z
Z
)
∗
∈
Z
Z
(2) Alice selects three random integers
z
1
(
/q
and
z
2
,z
3
,
/q
. She
computes the following where all congruences are modulo
p
:
y
1
≡
A
z
1
,
1
≡
y
z
1
,
2
≡
y
z
2
α
z
3
y
z
1
z
2
3
A
z
1
z
3
.
and
Y
3
≡
)
∗
such that
Now she computes
s
1
,s
2
,t
1
,t
2
,u
1
,u
2
∈
(
Z
/q
Z
e
1
z
1
≡
s
1
+
s
2
(mod
q
)
,e
2
z
1
≡
t
1
+
t
2
(mod
q
)
,z
1
≡
u
1
+
u
2
(mod
q
)
.
D.1
In the Brands scheme this step is often called the
representation problem step
. It turns
out that the Brands scheme is built on the Schnorr signature scheme and the representation
problem which is given as follows. In a group of prime order
G
with generators (
g
1
,g
2
,...,g
s
)
for
s
G
, find a representation such that
h
=
j
=1
g
b
j
j
for
b
j
≥
0.
The reader will note that this is related to a discrete log problem and so is di cult without
knowledge of the
b
j
.
D.2
To see that step (4) identifies Alice uniquely, note that since
A
is unique to Alice and
≥
2,
g
j
∈
G
, and a given
h
∈
≡ g
f
1
g
f
2
(
g
e
1
g
e
2
)
k
≡ g
f
1
+
ke
1
1
g
f
2
+
ke
2
2
≡ g
1
g
2
(mod
p
)
,
fA
k
then Alice's identity is indeed verified.
Search WWH ::
Custom Search