Cryptography Reference
In-Depth Information
However, the advantage can be eliminated bymerelyinsisting in step 1 that
onlynumbers
c
j
with Jacobi symbol 1 be chosen.
We conclude this section with another commitment scheme based upon the
DLP, which will allow us to set up a notion required for Section 5.6.
Commitment Scheme Based on the DLP
This scheme allows Alice to commit to a message
m
∈
Z
/q
Z
where
q
is
prime.
1. Bob randomlyselects primes
p
and
q
as in step 1 of the setup stage of the
DSA described on page 183. Then he randomlyselects distinct generators
α, β
of
Z
/q
Z
, as in steps 2 and 3 of the DSA setup. He sends (
p, q, α, β
)
to Alice.
2. Alice randomlyselects
r
∈
Z
/q
Z
and computes
α
r
β
m
(mod
p
)
,
c
≡
her commitment, which she sends to Bob.
3. When it is time to reveal her commitment, she sends
r
and
m
to Bob, who
verifies that
c
α
r
β
m
(mod
p
).
≡
Analysis
: Since the selection of
p, q, α, β
is as in the DSA, the above
scheme is based upon the DLP. To see why, let us suppose that Alice tries to
cheat byselecting
m
α
r
β
m
(mod
p
),
=
m
as her commitment. Then
α
r
β
m
≡
so
m
)
−
1
(mod
q
)
,
which she must compute. Yet for randomlychosen
α, β
r
)(
m
−
≡
−
log
α
(
β
)
(
r
, this is deemed
to be computationallyinfeasible. Thus, byselecting
α, β
randomlyin step 1,
α
r
β
m
is a means of blinding
m
, which depends upon the DLP.
The above scheme opens the door to a notion for commitments that we will
need later.
∈
Z
/q
Z
Homomorphic Property
If
E
(
x
) and
E
(
y
) are ciphertext in a given scheme and
E
(
x
)
E
(
y
)=
E
(
x
∗
y
)
,
(5.1)
where
is the operation used on plaintext, the scheme is said to have the
homomorphic property
.
For instance if we set
E
(
r, m
)=
α
r
β
m
in the above DLP scheme, then for
r, r
,m,m
∗
E
(
r
+
r
,m
+
m
)(mod
p
), which
satisfies (5.1), so it is an example of a
homomorphic commitment scheme
.
E
(
r
,m
)
∈
Z
/q
Z
,
E
(
r, m
)
·
≡
Analysis
: Homomorphic commitment schemes allow sums of integers to
be calculated without revealing either of the summands. We will see a real-world
application of this when we discuss electronic voting.
Search WWH ::
Custom Search