new ElGamal(standard, pGroup, random, statDist)
The El Gamal cryptosystem implemented on top of
verificatum.arithm.PGroup. This is a generalized implementation in
several ways and eliminates the complexity that plagues other
implementations by proper abstractions.
The first generalization allows us to use multiple El Gamal public
keys in parallel. The second allows us to define and implement the
Naor-Yung cryptosystem directly from the El Gamal cryptosystem and
a proof equal exponents (see verificatum.crypto.ElGamalZKPoK). The third generalizes the
cryptosystem to any width of plaintexts, i.e., lists of plaintexts
or equivalently elements of product groups.
- The first generalization is captured by letting the underlying
group G be of the form G = H^k, where H is a group of prime
order q and k > 0 is the key width, and the private key is
contained in the ring of exponents R = (Z/qZ)^k of G, where
Z/qZ is the field of prime order q.
- In the standard cryptosystem the private key is an element x
of R, and the public key has the form (g, y), where g is an
element of G and y = g^x. In the second generalization we
instead allow the public key to be an element ((g, h), y) of
(G x G) x G, but still define y = g^x with x in R. Here h can
be defined as h = y^z for a random z in R.
The standard cryptosystem defines encryption of a message m in
G as Enc((g, y), m, r) = (g^r, y^r * m), where r is randomly
chosen in R. We generalize encryption by simply setting
Enc(((g, h), y), m, r) = ((g^r, h^r), y^r * m). Note that the
same exponent r is used for all three exponentiations and that
it resides in R.
The standard cryptosystem defines decryption of a ciphertext
(u, v) by Dec(x, (u, v)) = v / u^x. In the generalized version
a decryption is defined by Dec(x, ((u, a), v)) = v / u^x.
- We generalize the cryptosystem to allow encryption of
plaintexts m of width w contained in G' = G^w, or equivalently
lists of plaintexts in G. A simple way to accomplish this with
a proper implementation of groups (see verificatum.arithm.PGroup) is to simply widen public and
secret keys.
- The original secret key is replaced by x' = (x, x,..., x)
in R' = R^w.
- A public key (g, y) in G x G is replaced by (g', y'),
where y' = (g, g,..., g) and y' = (y, y,..., y) are
elements in G'. Thus, the new public key is contained in
G' x G'.
- A public key ((g, h), y) in (G x G) x G is replaced by a
wider public key ((g', h'), y'), where g', and y' are
defined as above and h' is defined accordingly. Thus, the
new public key is contained in (G' x G') x G'.
Parameters:
Name |
Type |
Description |
standard |
|
Determines if the standard or variant El Gamal
cryptosystem is used. |
pGroup |
|
Group G over which the cryptosystem is defined. |
random |
|
Source of randomness. |
statDist |
|
Statistical distance from the uniform distribution
assuming that the output of the instance of the random source is
perfect. |
- Source:
Methods
(static) benchEncrypt(standard, pGroups, maxWidth, minSamples, randomSource, statDist)
Estimates the running time of encryption in
milliseconds for various groups and widths.
Parameters:
Name |
Type |
Description |
standard |
|
Indicates if the standard or variant scheme is
used. |
pGroups |
|
Groups over which the cryptosystem is defined. |
maxWidth |
|
Maximal width of plaintexts. |
minSamples |
|
Minimum number of executions performed. |
randomSource |
|
Source of randomness. |
statDist |
|
Statistical distance from the uniform distribution
assuming that the output of the instance of the random source is
perfect. |
- Source:
Returns:
Array or arrays of estimated running time of encryption in
milliseconds.
(static) benchEncryptPGroup(standard, pGroup, maxWidth, minSamples, randomSource, statDist)
Estimates the running time of encryption in
milliseconds for various widths.
Parameters:
Name |
Type |
Description |
standard |
|
Indicates if the standard or variant scheme is
used. |
pGroup |
|
Group over which the cryptosystem is defined. |
maxWidth |
|
Maximal width of plaintexts. |
minSamples |
|
Minimum number of executions performed. |
randomSource |
|
Source of randomness. |
statDist |
|
Statistical distance from the uniform distribution
assuming that the output of the instance of the random source is
perfect. |
- Source:
Returns:
Array of estimated running times of encryption in
milliseconds.
(static) benchEncryptPGroupWidth(standard, pGroup, width, minSamples, randomSource, statDist)
Estimates the running time of encryption in
milliseconds.
Parameters:
Name |
Type |
Description |
standard |
|
Indicates if the standard or variant scheme is
used. |
pGroup |
|
Group over which the cryptosystem is defined. |
width |
|
Width of plaintexts. |
minSamples |
|
Minimum number of executions performed. |
randomSource |
|
Source of randomness. |
statDist |
|
Statistical distance from the uniform distribution
assuming that the output of the instance of the random source is
perfect. |
- Source:
Returns:
Estimated running time of encryption in milliseconds.
completeEncrypt(publicKey, ruv, message)
Completes the encryption of a message with the El
Gamal cryptosystem.
Parameters:
Name |
Type |
Description |
publicKey |
|
Public key of the form (g', y'), or ((g', h'), y')
depending on if the standard or variant scheme is used. |
ruv |
|
Triple of the form [r, u, v] or [r, (u, a), v] as output
by verificatum.crypto.ElGamal.precomputeEncrypt, depending on
if the standard or variant scheme is used. |
message |
|
Message in G' to encrypt (must match group used in
pre-computation). |
- Source:
Returns:
Ciphertext of the form (u, v * message) or ((u, a), v *
message), depending on if the standard or variant scheme is used.
decrypt(privateKey, ciphertext)
Decrypts an El Gamal ciphertext.
Parameters:
Name |
Type |
Description |
privateKey |
|
Private key x' contained in R'. |
ciphertext |
|
Ciphertext (u, v) in G' x G', or ((u, a), v) in
(G' x G') x G') to be decrypted, depending on if the standard or
variant scheme is used. |
- Source:
Returns:
Plaintext computed as v / u^(x').
encrypt(publicKey, message, random)
Encrypts a message with the El Gamal cryptosystem.
Parameters:
Name |
Type |
Description |
publicKey |
|
Public key. |
message |
|
Message in G' to encrypt. |
random |
|
Randomness r in R' used for decryption. If this is
empty, then it is generated. |
- Source:
Returns:
Ciphertext of the form output by verificatum.crypto.ElGamal.completeEncrypt.
gen()
Generates a key pair of the El Gamal cryptosystem.
- Source:
Returns:
Pair [pk, sk] such that pk is a public key in G x G or in
(G x G) x G depending on if the standard or variant scheme is used,
and sk is the corresponding private key contained in R.
precomputeEncrypt(publicKey, random)
Pre-computation for encrypting a message using verificatum.crypto.ElGamal.completeEncrypt.
Parameters:
Name |
Type |
Description |
publicKey |
|
Public key of the form (g', y'), or ((g', h'), y')
depending on if the standard or variant scheme is used. |
random |
|
Randomness r in R' used for encryption. If this is
empty, then it is generated. |
- Source:
Returns:
Triple of the form [r, u, v] or [r, (u, a), v], where u =
(g')^r, a = (h')^r, and v = (y')^r, depending on if the standard or
variant scheme is used.
randomnessByteLength()
Computes the number of random bytes needed to encrypt.
- Source:
Returns:
Number of random bytes needed to encrypt.
widePrivateKey(privateKey, width)
Widens a private key such that a ciphertext resulting
from the encryption with the correspondingly widened public key can
be decrypted.
Parameters:
Name |
Type |
Description |
privateKey |
|
Original private key. |
width |
|
Width of wider public key. |
- Source:
Returns:
Public key with the same key width, but with the given
width.
widePublicKey(publicKey, width)
Widens a public key such that an element from a
product group of the underlying group can be encrypted.
Parameters:
Name |
Type |
Description |
publicKey |
|
Original public key. |
width |
|
Width of wider public key. |
- Source:
Returns:
Public key with the same key width, but with the given
width.