Modified ElGamal

Modified ElGamal [JCJ02] is a public key encryption scheme over a cyclic group of prime order that introduces a two-dimensional secret key and a three-component ciphertext. The change preserves the core guarantees of classical ElGamal (IND-CPA under DDH, rerandomizability, and homomorphism) while making the ciphertext structure more convenient for zero-knowledge proofs, shuffles, and threshold-style workflows.

Mathematical setting

Let $G$ be a cyclic group of prime order $p$ with independent generators $g_{1}, g_{2} \in G$ .

Secret key: $(x_{1}, x_{2}) \in Z_{p}^{2}$ sampled uniformly at random.
Public key: $h = g_{1}^{x_{1}} \cdot g_{2}^{x_{2}} \in G$ .

Encryption of $m \in G$ :

Sample $r \in Z_{p}$ uniformly at random.
Output ciphertext $C = (A, B, C_{3})$ where $A = g_{1}^{r}, B = g_{2}^{r}, C_{3} = h^{r} \cdot m .$

Decryption with secret key $(x_{1}, x_{2})$ : $m = C_{3} \cdot (A^{x_{1}} \cdot B^{x_{2}})^{- 1} .$

Correctness follows since: $A^{x_{1}} \cdot B^{x_{2}} = (g_{1}^{r})^{x_{1}} \cdot (g_{2}^{r})^{x_{2}} = (g_{1}^{x_{1}} \cdot g_{2}^{x_{2}})^{r} = h^{r} .$

Homomorphism

For any two ciphertexts $C (m_{1}; r_{1})$ and $C (m_{2}; r_{2})$ , $C (m_{1}; r_{1}) \cdot C (m_{2}; r_{2}) = C (m_{1} \cdot m_{2}; r_{1} + r_{2}) .$ Thus Modified ElGamal is multiplicatively homomorphic.

When messages are represented in the exponent, i.e., $m = g^{a}$ for a third fixed generator $g$ , then $C (g^{a_{1}}) \cdot C (g^{a_{2}}) = C (g^{a_{1} + a_{2}}),$ which induces additive homomorphism on exponents. Recovering $a$ from $g^{a}$ requires solving a discrete logarithm and is feasible only for small message domains.

Rerandomization

Given $C (m; r) = (A, B, C_{3})$ , any party can produce a distribution-identical ciphertext on the same plaintext by sampling $z$ in $Z_{p}$ and outputting $(A \cdot g_{1}^{z}, B \cdot g_{2}^{z}, C_{3} \cdot h^{z}) = C (m; r + z) .$ Rerandomization preserves correctness and hides $r$ .

Applications

Verifiable shuffles and mix-nets: ciphertexts can be permuted and rerandomized while preserving plaintexts.
Threshold workflows: the split structure of the secret key and the explicit randomness terms simplify share verifications.
Privacy-preserving systems: voting, sealed-bid auctions, credential systems, and any setting that benefits from efficient NIZKs over ElGamal relations.

Example

The crate is generic over a group backend. For documentation builds, select exactly one backend feature for the library (for example, p256 or ristretto). The alias Curve refers to the selected backend in this build.

// In Cargo.toml of this doc build:
// dlog-sigma-primitives = { version = "x.y.z", features = ["p256"] }

use rand_core::OsRng;
use dlog_sigma_primitives::prelude::*;

// The library exposes a concrete backend alias selected by features:
// type Curve = dlog_group::<backend>::Group;
// All APIs remain generic; Curve is provided for convenience.

fn main() {
let mut rng = OsRng;
// (sk, pk) sampled in the selected Curve
let params = ElGamalParams::<Curve>::new(&mut rng);
let (sk, pk) = KeyPair::<Curve>::new_from_params(&params, &mut rng).into_tuple();

// Sample a random message
let m = Curve::generator() * Curve::scalar_random(&mut rng);

// Encrypt and decrypt
let (ct, _r) = pk.encrypt(m, &params, &mut rng).into_tuple();

let m_dec = sk.decrypt(&ct);

assert_eq!(m, m_dec);
}