Cryptography Reference
In-Depth Information
Exercise 8.45
Show that the Paillier encryption scheme is not CCA secure by using
the homomorphic property to exhibit a CCA attack against the voting system just
mentioned that allows the adversary to recover a vote (given the encrypted vote and
the public key) with just one query to the decryption oracle.
8.8.3 The Paillier Encryption Scheme in Maple
Here we give a Maple implementation of the Paillier encryption scheme and an
example of its use for counting votes. For simplicity, our implementation will work
with plaintexts in
Z
n
(given, like the keys, in decimal format)
and we will leave as an exercise for the reader to obtain an implementation able to
deal with messages of arbitrary length given as (ASCII or hex) strings or files. We
start with the key generating function, which just calls the one used for (plain) RSA.
The inputs are just those corresponding to the positional parameters in
RSAKeyGen
(and, also in this case, the seeds may be omitted), except for the fact that now all of
them must be in decimal form and the output is a Paillier public key/private key pair,
given as a Maple list:
> PaillierKeyGen := proc(k::posint, seed1::posint, seed2::posint)
local key;
key := RSAKeyGen(k, _params['seed1'], _params['seed2'], 'format' = 'decimal');
[key[1][1], [key[1][1], (key[2][3]-1)*(key[2][4]-1)]]
end proc:
The Paillier encryption function requires, in addition to the public key and the
plaintext, a decimal random seed (which, for convenience, will be automatically
generated if not provided). As already mentioned, the plaintexts will be the elements
of
Z
n
and ciphertexts in
Z
n
, where
n
is the Paillier public key.
> PaillierEnc := proc(publickey::posint, m::nonnegint, seed::posint)
uses RandomTools;
local n, l, s, B, found, r;
n := publickey;
l := ilog2(n)+1;
if _params['seed'] = NULL then
MersenneTwister:-SetState();
s := MersenneTwister:-GenerateInteger(':-range' = 2ˆ127 .. 2ˆ256)
else
s := seed
end if;
B := BlumBlumShub:-NewBitGenerator(s, primes=1024, numbits=l, output=integer);
found := false;
while not found do
r := B();
found := evalb(r < n and igcd(r, n) = 1)
end do;
(Power(1+n, m)*Power(r, n)) mod nˆ2
end proc:
