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