> For the complete documentation index, see [llms.txt](https://valargroup.gitbook.io/shielded-vote-docs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://valargroup.gitbook.io/shielded-vote-docs/circuit-components/el-gamal-encryption-integrity.md). # El Gamal Encryption Integrity **Used in:** ZKP #2 (condition 11) ## What it does Proves that each encrypted share is a valid El Gamal ciphertext of the corresponding plaintext share under the election authority's public key. ## Inputs | Name | Type | Role | Range | Description | | ---------- | --------------------- | ---------------------------------------- | ----------- | ----------------------------------------------------------------------------------------------------------------------- | | `ea_pk` | Pallas point `(x, y)` | **public input** **and private witness** | on-curve | Election authority public key. Same for all proofs in a voting round. | | `G` | Pallas point | **constant** | generator | Generator of the Pallas prime-order subgroup. Hardcoded at circuit compile time. We use SpendAuthG point as this value. | | `shares_i` | Pallas scalar | **private witness** | `[0, 2^30)` | Plaintext share value. Range enforced by condition 9 (Shares Range Check, 3 × 10-bit lookup words). | | `r_i` | Pallas scalar | **private witness** | `[0, q)` | El Gamal randomness. `q` is the Pallas scalar field order. | | `C1_i` | Pallas point `(x, y)` | **private witness** | on-curve | First ciphertext component. Flows into shares hash (condition 10). | | `C2_i` | Pallas point `(x, y)` | **private witness** | on-curve | Second ciphertext component. Flows into shares hash (condition 10). | Note: `C1_i, C2_i` are private witnesses in ZKP #2 — their x-coordinates are committed inside per-share blinded commitments which are then hashed into `shares_hash`. They become public later when revealed in ZKP #3, but observers cannot link them back to a specific `shares_hash` without the blind factors. Note on `ea_pk` being both a public input and a private witness: In halo2, all computation happens in advice (witness) cells — you cannot do arithmetic directly on instance column values. So ea\_pk must be witnessed into advice cells to compute \[r\_i] \* ea\_pk. But a witness alone is private: the verifier can't see what value the prover used. The constrain\_instance calls add equality constraints that bind those advice cells to the public instance column, giving the verifier a guarantee that the prover used the specific EA key declared publicly. Witness = makes computation possible. Instance constraint = makes the verifier trust which key was used. In theory, it is possible to use `assign_advice_from_instance` but `halo2_gadgets` API limitation prevents it. By making ea\_pk\_x and ea\_pk\_y public inputs and binding the advice cells to them via constrain\_instance, the verifier's check of the proof implicitly asserts: "the ciphertext is a valid ElGamal encryption under exactly the ea\_pk coordinate pair listed in the public instance." The prover cannot substitute a different key without the proof failing. Note on why SpendAuthG: El Gamal requires a prime-order generator with an unknown discrete log. SpendAuthG is derived via `GroupPHash("z.cash:Orchard", "G")` — a nothing-up-my-sleeve point. Using it for El Gamal (Condition 11) avoids introducing a second generator point. Two variants of SpendAuthG are used: * `[r_i] * G` uses `OrchardBaseFieldBases::SpendAuthGBase` — 85-window tables shared with the full-scalar SpendAuthG entry, via `FixedPointBaseField`. * `[v_i] * G` uses `OrchardShortScalarBases::SpendAuthGShort` — a separate 22-window table set over the same generator, via `FixedPointShort`. This is possible because `shares_i` is bounded to 30 bits by condition 9. Note on why we only constrain x coordinates of the ciphertext, not y: We constrain C1.x = x(\[r]\*G) and C2.x = x(\[v]\*G + \[r]\*ea\_pk). A malicious prover cannot find a different y because both points are bound by the same r. The two x-constraints together pin r to a single value. Once r is fixed, the y-coordinates of both C1 and C2 are fully determined. The prover has no freedom left to choose them. So constraining x only is sufficient because x already implies y indirectly, through the shared r binding both equations. ## Circuit For each share `i` (i = 1..16), constrain: ``` C1_i = [r_i] * G C2_i = [shares_i] * G + [r_i] * ea_pk ``` This requires three scalar multiplications per share: | Operation | Base point | Scalar | Scalar width | Method | | ---------------- | ---------------------- | ---------- | ---------------------------------------------------------------------------------------------------- | ------------------------------------------- | | `[r_i] * G` | `G` (constant) | `r_i` | 255 bits | **Fixed-base** window method | | `[shares_i] * G` | `G` (constant) | `shares_i` | 64-bit signed (`ScalarFixedShort`, 22-window; range `[0, 2^30)` from condition 9, sign pinned to +1) | **Fixed-base** window method (short scalar) | | `[r_i] * ea_pk` | `ea_pk` (public input) | `r_i` | 255 bits | **Variable-base** double-and-add | Plus one point addition for `C2_i`. ## Scalar multiplication methods ### Fixed-base (for `[r_i] * G` and `[shares_i] * G`) When the base point is known at circuit compile time, we precompute tables of multiples. This is the same pattern Sinsemilla uses — decompose input into small windows, look up precomputed values, accumulate via point addition: ``` // Decompose scalar into w-bit windows (e.g. w = 3) windows = decompose(scalar, w) // each window in [0, 2^w) // For each window position j, a table of [k * 2^(wj) * G] for k in [0, 2^w) // is precomputed at circuit compilation time result = identity for j in 0..num_windows: // Lookup: select precomputed point for window value windows[j] // This is a constrained table lookup, not a branch table_point = TABLE[j][windows[j]] result = result + table_point ``` The window decomposition implicitly range-checks the scalar to `num_windows * w` bits — each window is constrained to `[0, 2^w)`, and the recomposition is verified. For `[shares_i] * G` the scalar is bounded to `[0, 2^30)` by condition 9, so we use `FixedPointShort::mul` with `ScalarFixedShort` — a 22-window signed short scalar (64-bit magnitude + sign). `ScalarFixedShort::new` wraps the caller-supplied `share_cells[i]` directly as the magnitude cell with no new allocation, so the same cell that conditions 8 and 9 operate on is used verbatim here. The sign cell is pinned to `+1` via `assign_advice_from_constant`, preventing negation attacks. This saves 63 windows per share (×16 = 1008 rows) compared to the full 85-window `FixedPointBaseField` path used for `[r_i] * G`. ### Variable-base (for `[r_i] * ea_pk`) When the base point is not known at compile time, we fall back to bit-by-bit double-and-add: ``` // Decompose r_i into individual bits bits = decompose(r_i, 1) // 255 bits accumulator = identity for j in 254 downto 0: accumulator = 2 * accumulator // point doubling // Conditional addition: add ea_pk if bit is 1, add identity if 0 // Implemented as: select(bits[j], ea_pk, identity) then add accumulator = accumulator + select(bits[j], ea_pk, identity) ``` Each step is \~1 doubling + 1 conditional addition. This is significantly more expensive than fixed-base — roughly 255 doublings and 255 conditional additions. ## Range constraints | Value | Required range | How enforced | | ------------ | --------------------------------------- | ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | `shares_i` | `[0, 2^30)` | Condition 9 (Shares Range Check) decomposes into 30 bits (3 × 10-bit lookup words). Cell sharing IS achieved: `ScalarFixedShort::new` wraps `share_cells[i]` directly as the magnitude cell, so the encryption scalar is provably identical to the range-checked share value. The sign cell is pinned to `+1` via a constant column, preventing negation attacks. | | `r_i` | `[0, q)` where `q = scalar field order` | The 255-bit window decomposition in the fixed-base mul constrains `r_i < 2^255`. Since `q < 2^255`, an additional overflow check is needed: verify the top window doesn't cause the total to exceed `q`. Alternatively, accept the negligible bias (`2^255 / q ≈ 1 + 2^{-127}`) since `r_i` is prover-chosen randomness. | | `ea_pk` | On the Pallas curve | Verified on-curve at assignment. As a public input, the verifier can also check this out-of-circuit. | | `C1_i, C2_i` | On the Pallas curve | Derived in-circuit from the scalar muls, so on-curve by construction. | ## Cost summary (per share) | Operation | Dominant cost | | ------------------------- | ----------------------------------------------------------------------------------------------------------------------- | | `[r_i] * G` | \~85 window lookups + point additions (fixed-base, 255-bit scalar, w=3) | | `[shares_i] * G` | \~22 window lookups + point additions (fixed-base short scalar, 22-window via `FixedPointShort`/`SpendAuthGShort`, w=3) | | `[r_i] * ea_pk` | \~255 doublings + 255 conditional additions (variable-base) | | Point addition for `C2_i` | 1 incomplete addition | The variable-base `[r_i] * ea_pk` dominates. This is repeated 16 times (once per share), making it the most expensive part of ZKP #2. ## Why this is needed Without this check, a malicious prover could commit to arbitrary ciphertext values that don't correspond to valid encryptions of the shares. The homomorphic tally would then produce a meaningless result. ## See also * [El Gamal on Pallas](/shielded-vote-docs/appendices/el-gamal.md) for the full encryption scheme * [Shares Range Check](https://github.com/z-cale/shielded-vote-book/blob/main/circuits/shielded_vote_book/circuits/shares-range-check.md) for the 30-bit constraint on `shares_i` * [Shares Hash Integrity](https://github.com/z-cale/shielded-vote-book/blob/main/circuits/shielded_vote_book/circuits/shares-hash-integrity.md) for how the ciphertexts are committed