Paillier Bridge Key Derivation: A Deterministic Construction for Bridging Elliptic Curve and Homomorphic Encryption Key Spaces

Abstract — This paper presents a novel cryptographic construction for deterministically deriving Paillier homomorphic encryption keys from Elliptic Curve Diffie-Hellman (ECDH) key material. The construction, implemented in the Express Suite cryptographic library, establishes a one-way, deterministic bridge between the secp256k1 elliptic curve domain and the Paillier cryptosystem’s integer factorization domain. The bridge employs a pipeline of established cryptographic primitives — ECDH shared secret computation, HKDF (RFC 5869) key derivation with domain separation, HMAC-DRBG (NIST SP 800-90A) deterministic random bit generation, and Miller-Rabin primality testing with deterministic witnesses — to produce 3072-bit Paillier key pairs suitable for privacy-preserving electronic voting systems. We analyze the security properties of this construction, including its one-wayness, determinism, collision resistance, and domain separation guarantees, while identifying potential pitfalls related to prime generation bias, cross-platform reproducibility, quantum vulnerability, and the inherent tension between deterministic key recovery and forward secrecy. The construction achieves a 128-bit security level consistent with NIST recommendations for the 2030+ timeframe.

Keywords — Paillier cryptosystem, ECDH, key derivation, homomorphic encryption, HKDF, HMAC-DRBG, electronic voting, threshold cryptography, bridge keys

I. Introduction

Modern cryptographic systems frequently require interoperability between fundamentally different algebraic structures. Elliptic curve cryptography (ECC) operates over the group of points on an elliptic curve, providing efficient key agreement and digital signatures, while the Paillier cryptosystem [1] operates over the multiplicative group of integers modulo n², providing additive homomorphic encryption. These two domains serve complementary purposes: ECC excels at authenticated key exchange and identity binding, while Paillier enables computation on encrypted data without decryption.

In privacy-preserving electronic voting systems, both capabilities are essential. Voters must authenticate using identity-bound keys (typically ECC-based), while ballots must be encrypted under a homomorphic scheme that permits tallying without revealing individual votes. The conventional approach requires maintaining two independent key pairs per participant — an ECC key pair for authentication and a Paillier key pair for vote encryption — creating significant key management overhead, backup complexity, and operational risk.

This paper presents a Paillier Bridge Key Derivation construction that deterministically derives Paillier key pairs from existing ECDH key material, eliminating the need for independent key generation and storage while preserving the security properties of both cryptosystems. The construction is implemented in the Express Suite library with both browser (Web Crypto API) and Node.js (crypto module) implementations.

A. Motivation

The key management problem in hybrid cryptographic voting systems is non-trivial. Consider a system where N voters each require:

An ECDSA/ECDH key pair for identity and authentication (secp256k1, ~256-bit private key)
A Paillier key pair for homomorphic vote encryption (3072-bit modulus, ~1536-bit primes)

Without a bridge construction, each voter must independently generate, securely store, and back up both key pairs. The Paillier key pair alone comprises several kilobytes of key material (the modulus n, the private components λ and μ), compared to the compact 32-byte ECC private key. This asymmetry creates practical challenges:

Storage overhead: Paillier keys are ~100× larger than ECC keys
Backup complexity: Two independent secrets must be preserved
Recovery risk: Loss of either key pair compromises different system functions
Provisioning latency: Paillier key generation requires finding large primes, which is computationally expensive (~seconds vs. microseconds for ECC)

The bridge construction addresses all four challenges by making the Paillier key pair a deterministic function of the ECDH key material, reducing the backup requirement to a single ECC private key.

B. Contributions

This paper makes the following contributions:

A formal description of the ECDH-to-Paillier bridge key derivation pipeline
Security analysis of the construction under standard cryptographic assumptions
Analysis of the instance isolation layer that prevents cross-instance ballot tampering
Discussion of the threshold extension enabling k-of-n distributed decryption
Identification of pitfalls and limitations, including quantum vulnerability, prime generation bias, and determinism trade-offs

C. Paper Organization

Section II provides background on the Paillier cryptosystem and ECDH. Section III describes the bridge construction in detail. Section IV presents the instance isolation layer. Section V covers the threshold extension. Section VI provides security analysis. Section VII discusses pitfalls and limitations. Section VIII covers related work. Section IX presents the formal security model. Section X discusses implementation considerations. Section XI concludes.

II. Background

A. The Paillier Cryptosystem

The Paillier cryptosystem [1] is a probabilistic, additively homomorphic public-key encryption scheme. Key generation selects two large primes p and q, computes n = pq, and derives the public key (n, g) where g = n + 1 (the simplified form). The private key consists of λ = lcm(p−1, q−1) and μ = (L(g^λ mod n²))⁻¹ mod n, where L(x) = (x−1)/n.

The homomorphic properties are:

Additive homomorphism: E(m₁) · E(m₂) mod n² = E(m₁ + m₂)
Scalar multiplication: E(m)^k mod n² = E(k · m)

These properties make Paillier ideal for vote tallying: encrypted votes can be aggregated (added) without decryption, and the final tally is obtained by decrypting only the aggregate.

The implementation uses 3072-bit moduli, providing approximately 128 bits of security per NIST SP 800-57 recommendations [2]. This matches the security level of the secp256k1 curve used for ECDH.

B. Elliptic Curve Diffie-Hellman (ECDH)

ECDH on secp256k1 provides a shared secret computation between two parties holding key pairs (d_A, Q_A) and (d_B, Q_B), where Q = d·G for generator point G. The shared secret is S = d_A · Q_B = d_B · Q_A, yielding a 65-byte uncompressed point (with 0x04 prefix).

In the bridge construction, the ECDH shared secret serves as the entropy source for Paillier key derivation. The full 65-byte uncompressed representation (including both X and Y coordinates) is used to maximize entropy input to the key derivation function.

C. HKDF (RFC 5869)

HMAC-based Key Derivation Function (HKDF) [3] is a two-stage extract-then-expand construction:

Extract: PRK = HMAC-Hash(salt, IKM) — concentrates entropy from input keying material
Expand: OKM = HKDF-Expand(PRK, info, L) — produces output keying material of desired length

The info parameter provides domain separation, ensuring that keys derived for different purposes from the same input material are cryptographically independent. The bridge construction uses info = "PaillierPrimeGen" to bind the derivation to its specific purpose.

D. HMAC-DRBG (NIST SP 800-90A)

The HMAC-based Deterministic Random Bit Generator [4] provides a cryptographically secure pseudorandom number generator seeded from the HKDF output. The DRBG maintains internal state (V, K) and produces output through iterated HMAC computations:

K = HMAC(K, V || 0x00 || seed)
V = HMAC(K, V)
K = HMAC(K, V || 0x01 || seed)
V = HMAC(K, V)

This construction ensures that the prime generation process is fully deterministic given the same seed, enabling key recovery from the original ECDH material.

III. Bridge Key Derivation Construction

A. Overview

The bridge construction transforms ECDH key material into a Paillier key pair through a four-stage pipeline:

ECDH(privKey, pubKey) → SharedSecret → HKDF → Seed → DRBG → (p, q) → Paillier(n, g, λ, μ)

Each stage is designed to be one-way: knowledge of the output does not reveal the input, and the composition preserves this property.

B. Stage 1: Shared Secret Computation

The first stage computes an ECDH shared secret from the participant’s key pair:

S = secp256k1.getSharedSecret(d, Q, uncompressed=true)

Where d is the 32-byte private key and Q is the public key (accepted in compressed 33-byte, uncompressed 64-byte, or prefixed 65-byte formats). The implementation normalizes all input formats:

31-byte private keys: Left-padded with a zero byte (occurs ~0.4% of the time when Node.js createECDH strips a leading zero)
33-byte compressed public keys: Accepted directly by @noble/secp256k1
64-byte raw public keys: Prefixed with 0x04 to form uncompressed format
65-byte prefixed public keys: Used as-is

The output is a 65-byte uncompressed point. Using the full point (both X and Y coordinates) rather than just the X coordinate provides maximum entropy (approximately 256 bits of security) for the subsequent derivation.

Security consideration: The shared secret computation is the only stage that requires the ECDH private key. All subsequent stages operate on derived material, ensuring that the private key is not exposed to the prime generation process.

Platform note: The Node.js implementation of deriveVotingKeysFromECDH is synchronous (returns KeyPair directly), while the browser (ecies-lib) implementation is async (returns Promise<KeyPair>) due to the Web Crypto API’s promise-based interface. The VotingService wrapper normalizes both to an async interface.

C. Stage 2: HKDF Key Derivation

The shared secret is processed through HKDF-SHA512 to produce a 64-byte seed:

seed = HKDF(
    IKM  = S,              // 65-byte shared secret
    salt = empty,           // Empty/null salt; per RFC 5869: uses HashLen zeros
    info = "PaillierPrimeGen",  // Domain separation string
    L    = 64              // Output length in bytes
)

The domain separation string "PaillierPrimeGen" is critical: it cryptographically binds this derivation to the specific purpose of Paillier prime generation. Even if the same ECDH shared secret were used for other purposes (e.g., AES key derivation with info = "AESKeyGen"), the outputs would be computationally independent.

The Node.js implementation passes Buffer.alloc(0) (an empty buffer) as the salt, while the browser implementation passes null. The HKDF function in both implementations normalizes empty/null salt to a string of HashLen zero bytes (64 bytes for SHA-512), consistent with RFC 5869 default behavior. This is acceptable because the input keying material (the ECDH shared secret) already has high min-entropy.

Cross-platform note: The browser implementation uses crypto.subtle.deriveBits() with the HKDF algorithm, while the Node.js implementation uses a manual extract-then-expand construction with createHmac(). Both must produce identical output for the same inputs, which is essential for cross-platform key recovery. This is a potential fragility point — see Section VII.B.

D. Stage 3: Deterministic Prime Generation

The 64-byte seed initializes an HMAC-DRBG instance (NIST SP 800-90A), which then generates candidate primes:

drbg = HMAC-DRBG(seed, algorithm="SHA-512")
p = generateDeterministicPrime(drbg, bits=1536, iterations=256)
q = generateDeterministicPrime(drbg, bits=1536, iterations=256)

The prime generation algorithm for each prime follows this procedure:

Candidate generation: Draw ceil(1536/8) = 192 bytes from the DRBG
Bit fixing: Set the top bit (ensures exact bit length) and bottom bit (ensures odd)
Small prime sieve: Test divisibility against the first 54 primes (2 through 251) for quick composite elimination
Miller-Rabin test: Perform 256 rounds of the Miller-Rabin primality test

Implementation detail: The Miller-Rabin test uses a two-phase witness strategy to achieve the full configured round count while maintaining determinism:

Phase 1 (rounds 1–12): Tests against 12 small-prime deterministic witnesses: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}. These provide strong heuristic confidence and, for numbers below ψ₁₂ ≈ 3.19×10²⁴, constitute a deterministic primality proof [12][13].
Phase 2 (rounds 13–k): Generates additional deterministic witnesses derived from the candidate itself. For each round i, the witness is computed as:
```
witness_bytes = HMAC-SHA256(key = UTF-8(hex(n)), data = UTF-8(hex(i)))
witness_int   = big-endian-unsigned(witness_bytes)          // 256-bit integer
witness       = (witness_int mod (n - 3)) + 2              // maps to range [2, n-2]
```
HMAC-SHA256 is a standard PRF (pseudorandom function) under the assumption that SHA-256’s compression function is a PRF [3]. Using a recognized cryptographic primitive rather than an ad-hoc hash eliminates reviewer concerns about witness quality. The cost is negligible: HMAC-SHA256 on a ~400-byte input takes microseconds, while the subsequent modular exponentiation in the witness loop takes milliseconds.

With primeTestIterations = 256, the test performs 12 deterministic small-prime rounds followed by 244 HMAC-SHA256-derived rounds, achieving a false positive probability bounded by 4⁻²⁵⁶ ≈ 2⁻⁵¹².

For each candidate n, the test writes n − 1 = 2^r · d and verifies that for each witness a:

a^d ≡ 1 (mod n), or
a^(2^j · d) ≡ −1 (mod n) for some 0 ≤ j < r

If a candidate fails any witness test, it is rejected and the next candidate is drawn from the DRBG. The maximum attempt count is 10,000 (configurable up to 20,000), which is sufficient given that the density of primes near 2^1536 is approximately 1/ln(2^1536) ≈ 1/1065.

E. Stage 4: Paillier Key Construction

Given primes p and q, the Paillier key pair is constructed after three safety checks:

Distinctness: p ≠ q (probability of collision ≈ 2⁻¹⁵³⁶, but checked as a guard against DRBG failure)
Distance: * p − q > 2^(bits/4)* (resists Fermat factoring; for 1536-bit primes, requires at least 768 bits of difference)
Coprimality: gcd(n, λ) = 1 (a technical requirement of the Paillier cryptosystem)

n = p · q
g = n + 1                          // Simplified Paillier
λ = lcm(p − 1, q − 1)
μ = (L(g^λ mod n²))⁻¹ mod n       // where L(x) = (x − 1) / n

The simplified form g = n + 1 is used because it yields the most efficient encryption and decryption operations while maintaining full security [1].

Validation: After construction, the key pair is validated with a test encryption/decryption cycle:

const testPlaintext = 42n;
const encrypted = publicKey.encrypt(testPlaintext);
const decrypted = privateKey.decrypt(encrypted);
assert(decrypted === testPlaintext);

This guards against implementation errors and ensures the generated primes produce a valid Paillier key pair.

F. Complete Reproducible Algorithm Specification

The following specification is intended to be sufficient for an independent implementation to produce byte-identical output given the same ECDH key pair. All byte orderings are big-endian unless otherwise noted.

F.1. Input Normalization

INPUT:  privKey : byte[31..32]   — ECDH private key (secp256k1 scalar)
        pubKey  : byte[33|64|65] — ECDH public key (compressed, raw, or prefixed)

NORMALIZE privKey:
    if len(privKey) == 31:
        privKey = 0x00 || privKey          // left-pad to 32 bytes
    assert len(privKey) == 32

NORMALIZE pubKey:
    if len(pubKey) == 33:
        pass                                // compressed, @noble/secp256k1 handles natively
    elif len(pubKey) == 65 and pubKey[0] == 0x04:
        pass                                // uncompressed with prefix
    elif len(pubKey) == 64:
        pubKey = 0x04 || pubKey             // add uncompressed prefix

F.2. Shared Secret (Stage 1)

S = secp256k1_ecdh(privKey, pubKey, compress=false)
// S is 65 bytes: 0x04 || X[32] || Y[32]
// Uses @noble/curves/secp256k1 getSharedSecret(privKey, pubKey, false)
assert len(S) == 65

F.3. HKDF-SHA512 (Stage 2)

Per RFC 5869, with the following exact parameters:

hash       = SHA-512
IKM        = S                              // 65 bytes, the full uncompressed shared point
salt       = 0x00 * 64                      // 64 zero bytes (SHA-512 hash length)
info       = UTF-8("PaillierPrimeGen")      // 16 bytes: [0x50,0x61,0x69,0x6C,0x6C,0x69,0x65,
                                            //            0x72,0x50,0x72,0x69,0x6D,0x65,0x47,
                                            //            0x65,0x6E]
L          = 64                             // output length in bytes

// Extract
PRK = HMAC-SHA512(key=salt, data=IKM)       // 64 bytes

// Expand (only 1 iteration needed since L ≤ HashLen)
T(1) = HMAC-SHA512(key=PRK, data=info || 0x01)
seed = T(1)[0..63]                          // first 64 bytes

F.4. HMAC-DRBG Initialization (Stage 3a)

Per NIST SP 800-90A, using SHA-512:

K = 0x00 * 64                               // 64 zero bytes
V = 0x01 * 64                               // 64 0x01 bytes

// Update with seed:
K = HMAC-SHA512(key=K, data=V || 0x00 || seed)
V = HMAC-SHA512(key=K, data=V)
K = HMAC-SHA512(key=K, data=V || 0x01 || seed)
V = HMAC-SHA512(key=K, data=V)

F.5. Prime Generation (Stage 3b)

Repeat for p, then q (sequential, using the same DRBG instance):

function generatePrime(drbg, numBits=1536):
    numBytes = ceil(1536 / 8) = 192
    topBitMask = 1 << ((1536 - 1) % 8) = 0x80   // bit 7 of byte 0

    for attempt in 0..9999:
        // Generate candidate bytes from DRBG
        bytes = drbg.generate(192)

        // DRBG generate: repeatedly compute V = HMAC(K, V), concatenate
        // until 192 bytes produced, then call drbg.update() with no data

        // Fix bits
        bytes[0]   |= 0x80                  // set top bit (ensures 1536-bit length)
        bytes[191] |= 0x01                  // set bottom bit (ensures odd)

        candidate = BigInt("0x" + hex(bytes))  // big-endian interpretation

        // Small prime sieve: primes 2,3,5,7,...,251 (54 primes)
        for each smallPrime in [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,
                                53,59,61,67,71,73,79,83,89,97,101,103,107,
                                109,113,127,131,137,139,149,151,157,163,167,
                                173,179,181,191,193,197,199,211,223,227,229,
                                233,239,241,251]:
            if candidate % smallPrime == 0 and candidate != smallPrime:
                reject candidate, continue to next attempt

        // Miller-Rabin with 256 rounds (two-phase deterministic witnesses)
        // Phase 1: 12 small-prime deterministic witnesses
        witnesses_phase1 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
        // Phase 2: 244 HMAC-SHA256-derived deterministic witnesses from candidate
        // For round i in [12..255]:
        //   witness_bytes = HMAC-SHA256(key=UTF-8(hex(candidate)), data=UTF-8(hex(i)))
        //   witness_int = big_endian_unsigned(witness_bytes)   // 256-bit integer
        //   witness = (witness_int mod (candidate - 3)) + 2
        if millerRabin(candidate, 256):   // all 256 rounds must pass
            return candidate

    error("Failed to find prime in 10000 attempts")

F.6. Paillier Key Construction (Stage 4)

// Safety checks
assert p ≠ q
assert |p - q| > 2^(bits/4)                 // resist Fermat factoring

n = p * q
g = n + 1
λ = lcm(p - 1, q - 1)                      // lcm(a,b) = (a * b) / gcd(a, b)

assert gcd(n, λ) == 1                       // Paillier correctness requirement

n² = n * n
μ = modInverse((modPow(g, λ, n²) - 1) / n, n)

// Validation
testCiphertext = g^42 * r^n mod n²          // r is random in [1, n)
assert privateKey.decrypt(testCiphertext) == 42

return (PublicKey(n, g), PrivateKey(λ, μ))

Note on validation: The test encryption uses paillier-bigint’s encrypt() method, which selects a random r. This means the validation ciphertext differs between runs, but decryption always yields 42. The validation confirms the key pair is mathematically correct but is not itself deterministic.

IV. Instance Isolation Layer

A. Motivation

The bridge construction produces deterministic Paillier keys: the same ECDH input always yields the same Paillier key pair. While this is desirable for key recovery, it creates a risk in multi-session voting scenarios. If the same Paillier public key is used across multiple voting sessions (polls), an adversary who obtains a ciphertext from one session could potentially inject it into another session — a ballot replay attack.

The instance isolation layer addresses this by extending the Paillier public and private keys with per-instance identifiers and HMAC-based ciphertext tagging.

B. IsolatedPublicKey Construction

The IsolatedPublicKey class extends the base Paillier PublicKey with three additional components:

keyId: A deterministic identifier derived from the public key modulus n. The computation converts n to a hex string padded to 768 characters, encodes that string as UTF-8 bytes, and hashes the result with SHA-256:
```
nHex = hex(n).padStart(768, '0')
keyId = SHA-256(UTF-8(nHex))
```
This encoding is consistent across all code paths: votingPublicKeyToBuffer, bufferToVotingPublicKey, IsolatedPublicKey.verifyKeyId(), and all test fixtures. The UTF-8 encoding of the hex string (not raw hex-to-bytes parsing) is the canonical representation.
instanceId: A unique-per-instance identifier derived from the keyId, modulus, and a random 32-byte salt:
```
instanceId = SHA-256(keyId || hex(n) || randomSalt)
```

HMAC tagging: Each ciphertext is tagged with an HMAC computed from the keyId and instanceId:

tag = HMAC-SHA256(keyId || instanceId, hex(ciphertext))
taggedCiphertext = ciphertext || tag

The encryptIsolated method replaces the standard encrypt method, producing tagged ciphertexts that are bound to the specific key instance. The standard encrypt method is overridden to throw an error, enforcing the use of isolated encryption.

C. IsolatedPrivateKey Validation

The IsolatedPrivateKey class extends the base Paillier PrivateKey with instance validation:

Instance ID verification: Before decryption, the current instanceId of the associated public key is compared against the instanceId stored at construction time. If they differ (indicating the public key’s instance was rotated), decryption is refused.
HMAC verification: The HMAC tag is extracted from the tagged ciphertext and verified against the expected value computed from the original keyId and instanceId. If verification fails, decryption is refused.
Decryption: Only after both checks pass is the underlying Paillier decryption performed on the untagged ciphertext.

function decryptIsolated(taggedCiphertext):
    // Verify instance ID hasn't changed
    assert(publicKey.currentInstanceId == originalInstanceId)
    
    // Extract and verify HMAC
    (ciphertext, receivedHmac) = split(taggedCiphertext)
    expectedHmac = HMAC-SHA256(keyId || instanceId, hex(ciphertext))
    assert(receivedHmac == expectedHmac)
    
    // Decrypt
    return paillierDecrypt(ciphertext)

D. Homomorphic Operations Under Isolation

The isolation layer must preserve Paillier’s homomorphic properties. The IsolatedPublicKey provides isolated versions of the homomorphic operations:

additionIsolated(a, b): Strips tags from both ciphertexts, performs homomorphic addition (a · b mod n²), and re-tags the result
multiplyIsolated(ciphertext, constant): Strips the tag, performs scalar multiplication (ciphertext^constant mod n²), and re-tags the result

This ensures that intermediate computations (e.g., vote aggregation) maintain the instance binding throughout the tally process.

E. Instance Rotation

The updateInstanceId() method generates a new random salt and recomputes the instanceId. This invalidates all previously encrypted ciphertexts, providing a mechanism for session separation:

function updateInstanceId():
    newSalt = randomBytes(32)
    instanceId = SHA-256(keyId || hex(n) || newSalt)

After rotation, any attempt to decrypt ciphertexts encrypted under the previous instanceId will fail the instance ID verification check.

V. Threshold Extension

A. Distributed Trust Model

For high-stakes voting scenarios, concentrating the decryption capability in a single private key is unacceptable. The threshold extension distributes the Paillier private key across n guardians using Shamir’s Secret Sharing [5], requiring any k of n guardians to cooperate for decryption.

The ThresholdKeyGenerator implements the following procedure:

Base key generation: Generate a standard Paillier key pair using paillier-bigint.generateRandomKeys(3072)
Shamir splitting: Split the private key component λ using a degree-(k−1) polynomial over Z_{n·λ}:
```
f(x) = λ + a₁x + a₂x² + ... + a_{k-1}x^{k-1}  (mod n·λ)
```
where a₁, …, a_{k-1} are random coefficients. The modulus n·λ is chosen because the order of Z_{n²}** divides n·λ, ensuring that Lagrange reconstruction in the exponent is correct.
Share evaluation: Each guardian i receives share s_i = f(i) for i = 1, 2, …, n
Verification keys: For each share, a verification key v_i = g^{s_i} mod n² is computed, enabling zero-knowledge proof verification without revealing the share
Theta computation: The threshold decryption constant θ = L(g^{4·Δ·λ} mod n²) mod n is computed, where Δ = n! (the factorial of the total number of shares). This constant is used by the combiner to convert combined partial decryptions into plaintext.

C. Partial Decryption

Each guardian computes a partial decryption of the encrypted tally:

partialValue_i = ciphertext^(2·s_i) mod n²

Along with each partial decryption, the guardian produces a zero-knowledge proof demonstrating that the partial decryption is consistent with their verification key, without revealing the share itself. The proof uses a Schnorr-like protocol with a ceremony nonce for freshness.

D. Decryption Combining

The DecryptionCombiner reconstructs the plaintext from k partial decryptions using Lagrange interpolation in the exponent:

combined = Π_i partialValue_i^(2·λ'_i) mod n²

where λ’_i = Δ · Π_{j≠i} j/(j−i) are integer Lagrange coefficients (scaled by Δ to avoid fractions). The plaintext is then recovered:

m = L(combined) · θ⁻¹ mod n

The combiner verifies each guardian’s zero-knowledge proof before including their partial decryption, preventing malicious guardians from corrupting the tally.

E. Integration with Bridge Keys

The threshold extension can be applied to bridge-derived Paillier keys. In this configuration:

A designated key ceremony coordinator derives the base Paillier key pair from ECDH material using the bridge construction
The private key component λ is split into shares using the threshold generator
Shares are distributed to guardians
The original private key is destroyed; only the shares remain

This combines the key management benefits of the bridge (single ECC key backup) with the distributed trust benefits of threshold decryption. However, it introduces a trust assumption: the ceremony coordinator temporarily possesses the complete private key during share generation.

VI. Security Analysis

A. One-Wayness

Claim: Given a Paillier key pair (n, g, λ, μ), it is computationally infeasible to recover the ECDH private key d or shared secret S.

Argument: The derivation pipeline composes four one-way transformations:

S → seed: HKDF is a PRF under the assumption that HMAC-SHA512 is a PRF [3]. Inverting HKDF requires inverting HMAC, which is infeasible under the PRF assumption.
seed → (p, q): The HMAC-DRBG is a PRG under the HMAC-PRF assumption [4]. The prime generation process additionally discards non-prime candidates, creating a many-to-one mapping from DRBG states to primes.
(p, q) → n: Recovering p and q from n requires integer factorization, which is believed to be hard for 3072-bit moduli (equivalent to ~128-bit security).
d → S: Recovering the ECDH private key from the shared secret requires solving the Elliptic Curve Discrete Logarithm Problem (ECDLP) on secp256k1, which is believed to require ~2¹²⁸ operations.

The composition of one-way functions is itself one-way, so the complete pipeline is one-way under the conjunction of these assumptions.

B. Determinism and Key Recovery

Claim: The same ECDH key pair always produces the same Paillier key pair.

Argument: Every stage of the pipeline is deterministic:

ECDH shared secret computation is deterministic (scalar multiplication on a fixed curve)
HKDF with fixed parameters (salt=null, info=”PaillierPrimeGen”, L=64) is deterministic
HMAC-DRBG seeded with the same seed produces the same output sequence
The prime search is deterministic given the same DRBG output sequence
Paillier key construction from fixed (p, q) is deterministic

This property enables key recovery: a user who has backed up only their ECDH private key can regenerate their Paillier key pair by re-executing the bridge derivation with the same public key.

Caveat: Determinism requires that the implementation details (DRBG state management, candidate rejection logic, byte ordering) are identical across platforms. The implementation achieves this through careful cross-platform testing between the browser (Web Crypto API) and Node.js (crypto module) implementations.

C. Collision Resistance

Claim: Different ECDH key pairs produce different Paillier key pairs with overwhelming probability.

Argument: For a collision to occur, two different ECDH shared secrets must produce the same HKDF output (a collision in HKDF-SHA512), or two different seeds must produce the same pair of primes through the DRBG. The birthday bound for HKDF-SHA512 with 512-bit output is ~2²⁵⁶ operations, and the probability of two independent DRBG instances producing the same prime pair is negligible given the density of 1536-bit primes.

The effective collision resistance is ~2¹²⁸ operations, bounded by the security level of the secp256k1 curve.

D. Domain Separation

Claim: Paillier keys derived with the bridge construction are cryptographically independent of keys derived from the same ECDH material for other purposes.

Argument: The HKDF info parameter "PaillierPrimeGen" provides domain separation per RFC 5869 Section 3.2. Keys derived with different info strings are computationally independent under the PRF assumption for HMAC-SHA512. This means that even if the same ECDH shared secret is used for AES key derivation (with a different info string), the resulting keys are independent.

E. Security Level Assessment

The construction achieves a consistent 128-bit security level across all components:

Component	Parameter	Security Level
ECDH	secp256k1 (256-bit)	~128 bits
HKDF	SHA-512	256 bits (preimage)
HMAC-DRBG	SHA-512	256 bits (state recovery)
Miller-Rabin	256 rounds (12 deterministic + 244 HMAC-SHA256-derived)	< 2⁻⁵¹² false positive
Paillier	3072-bit modulus	~128 bits (GNFS)
Instance HMAC	SHA-256	128 bits (forgery)

The weakest link is the 128-bit security provided by secp256k1 and the 3072-bit Paillier modulus, which is consistent with NIST recommendations for protection through 2030 and beyond [2].

VII. Pitfalls and Limitations

A. Prime Generation Bias

The deterministic prime generation process introduces a subtle bias. The DRBG generates candidate integers uniformly over the range [2^1535, 2^1536) (after setting the top bit), but the distribution of primes in this range is not uniform — it follows the Prime Number Theorem with local fluctuations. The candidate rejection process (rejecting composites) produces primes that are biased toward those preceded by shorter gaps in the prime distribution.

Impact: This bias is shared by virtually all practical prime generation algorithms and does not meaningfully reduce security. The density of primes near 2^1536 is approximately 1/1065, and the bias introduced by sequential candidate testing is negligible compared to the entropy of the seed.

Mitigation: The implementation uses a small prime sieve (primes up to 251) before Miller-Rabin testing, which improves efficiency but does not introduce additional bias beyond the inherent sequential search bias.

B. Cross-Platform Reproducibility

The determinism guarantee requires byte-exact agreement between the browser and Node.js implementations. Several sources of divergence must be carefully managed:

HKDF implementation differences: The browser uses crypto.subtle.deriveBits() while Node.js uses a manual HMAC-based construction. Both must produce identical output for the same inputs. The RFC 5869 specification is unambiguous, but implementation bugs (e.g., incorrect handling of null salt) can cause divergence.
BigInt serialization: The conversion between byte arrays and BigInt values must use consistent endianness and padding. The implementation uses big-endian hex encoding throughout.
HMAC-DRBG state management: The async (browser) and sync (Node.js) DRBG implementations must maintain identical internal state sequences. The browser implementation uses crypto.subtle.sign() for HMAC, while Node.js uses createHmac().
Private key normalization: Node.js createECDH occasionally returns 31-byte private keys (when the key has a leading zero). Both implementations must normalize to 32 bytes with identical padding.

Mitigation: The implementation includes cross-platform integration tests that verify byte-exact agreement of derived keys between browser and Node.js environments.

C. Determinism vs. Forward Secrecy

The deterministic nature of the bridge construction creates an inherent tension with forward secrecy. If an adversary compromises the ECDH private key at any point, they can derive all past and future Paillier key pairs generated from that key. This is in contrast to randomly generated Paillier keys, where compromise of one key pair does not affect others.

Impact: In a voting system, compromise of a voter’s ECDH private key would allow the adversary to:

Derive the voter’s Paillier private key
Decrypt all ballots cast by that voter (past and future)
Potentially forge ballots if the instance isolation layer is also compromised

Mitigation:

The instance isolation layer (Section IV) provides session separation, limiting the impact of key compromise to sessions where the adversary possesses both the private key and the correct instanceId
For high-security deployments, the threshold extension (Section V) distributes the decryption capability, so compromise of a single voter’s key does not compromise the election tally
Key rotation (generating new ECDH key pairs) provides a mechanism for limiting the window of vulnerability

D. Quantum Vulnerability

The bridge construction is vulnerable to quantum attacks at multiple levels:

Shor’s algorithm can factor the 3072-bit Paillier modulus in polynomial time on a sufficiently large quantum computer, breaking the Paillier cryptosystem entirely
Shor’s algorithm can also solve the ECDLP on secp256k1, recovering the ECDH private key from the public key
The HKDF and HMAC-DRBG components are resistant to quantum attacks (Grover’s algorithm provides only a quadratic speedup against symmetric primitives)

Impact: A quantum adversary could break both the bridge derivation (by recovering the ECDH private key) and the Paillier encryption (by factoring the modulus) independently. The bridge construction does not introduce additional quantum vulnerability beyond what already exists in the individual components.

Mitigation: Post-quantum migration would require replacing both the ECDH component (with a lattice-based or code-based key exchange) and the Paillier component (with a lattice-based homomorphic encryption scheme such as BGV or CKKS). The bridge construction’s modular design facilitates such migration: the HKDF and DRBG stages can be reused with different input and output key types.

E. Computational Cost of Prime Generation

Generating 1536-bit primes is computationally expensive. The expected number of candidates tested before finding a prime is approximately ln(2^1536) ≈ 1065. Each candidate requires:

54 modular divisions (small prime sieve)
256 modular exponentiations (Miller-Rabin witnesses: 12 deterministic + 244 HMAC-SHA256-derived)

On modern hardware, this translates to several seconds of computation per prime, and two primes are needed per key pair. This latency is acceptable for key provisioning (a one-time operation) but would be prohibitive for real-time key generation.

Mitigation: The deterministic nature of the construction means that key generation can be performed once and the result cached. The key pair can be regenerated from the ECDH material if the cache is lost, at the cost of re-incurring the generation latency.

E.1. Safe Primes: Evaluated and Deferred

A safe prime is a prime p where (p−1)/2 is also prime (a Sophie Germain prime). Safe primes provide additional resistance against Pollard’s p−1 and Williams’ p+1 factoring algorithms, which exploit smooth factors of p−1 or p+1. Some RSA key generation standards recommend safe primes for this reason.

We benchmarked safe prime generation against regular prime generation at 1536 bits with 256 Miller-Rabin rounds on an Apple M4 Max (2024):

Metric	Regular Primes	Safe Primes	Ratio
Average time per prime	~1.3s	~232s	174×
Average time per key pair (2 primes)	~2.7s	~465s	174×
Average candidates tested	~404	~611,000	1,514×

The 174× slowdown is consistent with the theoretical density ratio: safe primes near 2^1536 have density approximately C₂/(ln n)² where C₂ ≈ 1.32 is the twin prime constant, compared to 1/ln(n) for regular primes — a factor of roughly ln(2^1536)/C₂ ≈ 807.

Decision: At this time, we do not use safe primes. The ~8-minute key derivation time on high-end desktop hardware (Apple M4 Max) is unacceptable for a user-facing system where key derivation occurs at account creation. On mid-range hardware or in a browser environment, the time would be substantially worse. The marginal security benefit is minimal: Pollard’s p−1 and Williams’ p+1 are already impractical against 1536-bit primes regardless of smoothness, as the general number field sieve (GNFS) dominates at this scale.

Future reconsideration: As hardware performance improves, safe primes may become practical. The benchmark script is preserved at tests/scripts/safe-prime-benchmark.spec.ts for re-evaluation. If safe prime generation can be brought under ~10 seconds per key pair on mainstream hardware, the tradeoff should be revisited.

F. DRBG State Exhaustion

The HMAC-DRBG has a finite state space determined by the hash function output length (512 bits for SHA-512). While the state space is enormous (2^512 possible states), the NIST SP 800-90A specification recommends reseeding after 2^48 generate calls. The prime generation process typically requires fewer than 10,000 generate calls (each producing 192 bytes), well within this limit.

Impact: State exhaustion is not a practical concern for the bridge construction’s use case.

G. Timing Side Channels

The Miller-Rabin primality test and modular exponentiation operations are not constant-time in the implementation. The number of candidates tested before finding a prime leaks information about the DRBG output sequence, and the modular exponentiation timing depends on the exponent value.

Impact: In a local key derivation scenario (where the adversary does not observe the computation), timing side channels are not relevant. In a remote or shared-hardware scenario, timing information could theoretically leak information about the derived primes.

Mitigation: The implementation notes that timing attack mitigation depends on the underlying crypto library implementation. For high-security deployments, key derivation should be performed in a trusted execution environment (TEE) or hardware security module (HSM).

H. The Ceremony Coordinator Trust Assumption

When the threshold extension is combined with bridge-derived keys, the ceremony coordinator temporarily possesses the complete Paillier private key before splitting it into shares. This creates a single point of trust during the key ceremony.

Impact: A malicious ceremony coordinator could retain a copy of the private key, enabling unilateral decryption of all ballots without guardian cooperation.

Mitigation:

The ceremony coordinator’s actions can be audited through the ThresholdAuditLog
Distributed key generation (DKG) protocols could eliminate the trusted coordinator, but would require a more complex protocol that generates shares directly without ever materializing the complete private key
The ceremony can be performed in a TEE with attestation, providing assurance that the private key was destroyed after share generation

I. Homomorphic Security Classification

Not all voting methods are compatible with Paillier’s additive homomorphism. The implementation classifies voting methods into three security levels:

Security Level	Methods	Properties
Fully Homomorphic	Plurality, Approval, Weighted, Borda, Score, YesNo, YesNoAbstain, Supermajority	Single-round, no intermediate decryption
Multi-Round	RankedChoice, TwoRound, STAR, STV	Requires decryption between rounds
Insecure	Quadratic, Consensus, ConsentBased	Cannot be made secure with Paillier

Fully homomorphic methods can be tallied entirely in the encrypted domain: votes are encrypted, homomorphically aggregated, and only the final tally is decrypted. This provides maximum privacy.

Multi-round methods (e.g., Ranked Choice / Instant Runoff Voting) require intermediate decryption to determine which candidates are eliminated between rounds. This reveals partial tally information and requires re-encryption for subsequent rounds, reducing privacy guarantees.

Insecure methods require operations that Paillier cannot support homomorphically (e.g., square root for Quadratic voting) or inherently reveal individual votes (e.g., Consensus voting requires knowing if 95%+ agreement was reached, which leaks information about individual positions).

J. Key Serialization and Interoperability

The implementation defines a binary serialization format for Paillier keys with SHA-256 integrity checksums:

Public Key: [magic:4][version:1][keyId:32][n_length:4][n:variable][checksum:32] Private Key: [magic:4][version:1][lambda_length:4][lambda:variable][mu_length:4][mu:variable][checksum:32] IsolatedPublicKey: [magic:4][version:1][keyId:32][instanceId:32][n_length:4][n:variable][checksum:32]

The magic bytes "BCVK" (BrightChain Voting Key) and version number (currently 2) provide format identification and forward compatibility. Each serialized key includes a trailing 32-byte SHA-256 checksum computed over the payload (all bytes preceding the checksum). Deserialization verifies this checksum before parsing the key material, ensuring that corrupted or truncated buffers are rejected with a clear error rather than silently producing invalid keys.

The format does not include:

Encryption: Serialized private keys are in plaintext. Applications must encrypt them before storage or transmission.
Algorithm agility: The format assumes Paillier with g = n + 1. Supporting alternative homomorphic schemes would require a new format version.

K. Miller-Rabin Witness Count: Discovery and Resolution

During the preparation of this paper, a discrepancy was discovered between the documented intent and the original implementation of the Miller-Rabin primality test. The configuration specified primeTestIterations = 256, but the original code capped the witness count at the length of a hardcoded 12-element array:

// ORIGINAL (buggy) implementation:
for (let i = 0; i < Math.min(k, witnesses.length); i++) { ... }

This meant the primeTestIterations parameter was effectively ignored beyond 12. The bug was present in both the browser (ecies-lib) and Node.js (node-ecies-lib) packages.

Resolution: The implementation was corrected to use a two-phase witness strategy:

Phase 1 (rounds 1–12): Tests against the original 12 small-prime deterministic witnesses {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}.
Phase 2 (rounds 13–k): Generates additional deterministic witnesses via HMAC-SHA256, a standard pseudorandom function. Each witness is computed as HMAC-SHA256(key=UTF-8(hex(n)), data=UTF-8(hex(roundIndex))), interpreted as a 256-bit big-endian integer, then mapped to the range [2, n−2]. Using a recognized cryptographic PRF rather than an ad-hoc hash ensures that the witness distribution is indistinguishable from uniform under standard assumptions.

This approach preserves full determinism (the same candidate always produces the same witness sequence), honors the configured round count, and achieves the documented 2⁻⁵¹² false positive bound with k = 256. The fix was applied to both packages and verified by the existing test suites.

Lesson: This discrepancy underscores the importance of auditing implementations against their documented security claims. The 12 deterministic witnesses likely provided adequate security in practice (no known pseudoprimes to all 12 bases exist at 1536-bit sizes), but the gap between documented and actual behavior was unacceptable for a system intended for peer verification.

L. Comparison with Alternative Approaches

The bridge construction is not the only way to provide Paillier keys in a voting system. This section compares the chosen approach with alternatives and explains the design rationale.

Alternative 1: Independent Paillier key generation. The simplest approach is to generate Paillier keys independently using a cryptographically secure random number generator, with no relationship to the ECDH keys. This eliminates the bridge entirely.

Advantage: No novel construction to audit; standard Paillier key generation is well-understood.
Disadvantage: Two independent secrets must be backed up and managed. Loss of the Paillier private key is irrecoverable. In a system with N voters, this doubles the key management burden.
Why we chose the bridge: The voting system already requires ECDH keys for identity and authentication. Deriving Paillier keys from ECDH material reduces the backup requirement to a single 32-byte secret, which is a significant operational simplification.

Alternative 2: RSA-KEM or RSA key derivation. Since Paillier keys are structurally similar to RSA keys (both require two large primes), one could use an RSA key derivation scheme to produce the primes.

Advantage: RSA key generation is extensively studied.
Disadvantage: Standard RSA key generation is randomized, not deterministic. Making it deterministic requires the same DRBG-based approach we use, so the complexity is equivalent. There is no standard for “deterministic RSA key generation from a seed.”
Why we chose the bridge: The bridge construction is no more complex than deterministic RSA key generation, and it provides the additional benefit of binding the Paillier keys to the ECDH identity.

Alternative 3: BIP-32-style hierarchical derivation. BIP-32 [6] derives child keys from parent keys using HMAC-SHA512. One could extend this to derive Paillier key material.

Advantage: BIP-32 is a well-known standard in the cryptocurrency ecosystem.
Disadvantage: BIP-32 operates entirely within the elliptic curve domain (secp256k1 → secp256k1). Extending it to produce integer-factorization-based keys requires the same HKDF → DRBG → prime generation pipeline we already use. BIP-32 would only replace the HKDF stage, not simplify the overall construction.
Why we chose HKDF directly: HKDF (RFC 5869) is a more general and widely implemented KDF than BIP-32’s HMAC-SHA512 chain. Using HKDF directly avoids introducing a dependency on BIP-32’s specific derivation path semantics, which are designed for hierarchical key trees rather than cross-domain key bridging.

Alternative 4: Lattice-based homomorphic encryption. Post-quantum schemes like BGV or CKKS provide homomorphic encryption without relying on integer factorization.

Advantage: Quantum-resistant.
Disadvantage: Significantly more complex, less mature implementations, larger ciphertexts, and no established library ecosystem comparable to paillier-bigint. The additive homomorphism of Paillier is a natural fit for vote tallying; lattice-based schemes provide more general (but more expensive) homomorphic capabilities.
Future direction: The bridge construction’s modular design (ECDH → HKDF → DRBG → key generation) can be adapted to lattice-based schemes by replacing the prime generation stage with lattice parameter generation. This is noted as future work in the conclusion (Section XI).

M. Honest Disclosure: Status and Limitations

This section consolidates the limitations of the bridge construction that a prospective user or reviewer should be aware of. We present these not as caveats buried in technical discussion, but as a forthright assessment of what this construction is and is not.

What this construction is:

A deterministic, reproducible bridge between ECDH and Paillier key spaces, built from standard cryptographic primitives (HKDF, HMAC-DRBG, HMAC-SHA256, Miller-Rabin)
Specified to byte-level precision with two independent test vectors (Appendix C)
Implemented in two parallel packages (browser and Node.js) with shared test suites
Self-audited: bugs were found and fixed during the preparation of this paper (Section VII.K)

What this construction is not:

Not independently audited. This construction has not been reviewed by an external cryptographer or security firm. The security arguments in Section VI are proof sketches under standard assumptions, not formal proofs. We encourage and welcome independent review.
Not formally verified. The implementation has not been subjected to formal verification (e.g., using Coq, Lean, or F*). The correctness argument relies on test suites and manual code review.
Not constant-time. The Miller-Rabin test, modular exponentiation, and BigInt operations are not guaranteed to be constant-time. In a local key derivation scenario this is acceptable; in a shared-hardware or remote-computation scenario, timing side channels could leak information about the derived primes (see Section VII.G).
Not quantum-resistant. Both the ECDH and Paillier components are vulnerable to Shor’s algorithm (see Section VII.D).
Not a replacement for established voting standards. This construction addresses key management, not the broader requirements of election security (voter authentication, ballot secrecy, verifiability, coercion resistance). It should be evaluated as one component of a larger system.

Open questions for reviewers:

~~Is the HMAC-SHA256 witness derivation in Phase 2 of Miller-Rabin sufficient, or should a more conservative approach (e.g., HKDF with per-round info strings) be used?~~ Resolved: HMAC-SHA256 is sufficient. HMAC is a standardized PRF (RFC 2104) under the assumption that SHA-256’s compression function is a PRF [3]. The witness derivation HMAC-SHA256(key=hex(n), data=hex(i)) produces outputs computationally indistinguishable from uniform random for distinct inputs, which is exactly the property needed for Miller-Rabin witnesses. A more conservative approach such as HKDF-per-round would add complexity (an additional extract-then-expand step per witness) for no meaningful security gain — HKDF’s expand phase is itself HMAC-based, so the underlying primitive is identical. The current approach is simpler, faster, and equally sound. We leave this as a note for reviewers who may prefer the additional formalism of HKDF, but do not consider it necessary.
~~Should the construction enforce p ≠ q explicitly, or is the probability of collision (≈ 2⁻¹⁵³⁶) sufficient?~~ Resolved: Both implementations now enforce p ≠ q with an explicit check after prime generation. The check is free and guards against DRBG failures or insufficient seed entropy. Additionally, |p − q| > 2^(bits/4) is enforced to resist Fermat factoring, and gcd(n, λ) = 1 is verified as a Paillier correctness requirement.
~~Is the use of the full 65-byte uncompressed ECDH shared point (including the 0x04 prefix) as HKDF input material a concern, given that the prefix byte is constant and contributes no entropy?~~ Resolved: The constant 0x04 prefix byte is harmless. HKDF’s extract phase (HMAC-SHA512(salt, IKM)) processes the entire IKM as an opaque byte string; a fixed prefix byte does not weaken the extraction — it simply means 1 of the 65 input bytes carries zero entropy, leaving 64 bytes (~256 bits) of entropy from the X and Y coordinates. This far exceeds the 128-bit security target. Stripping the prefix would save one byte of input but would introduce a divergence from the standard getSharedSecret() output format, creating a maintenance risk for no cryptographic benefit. The prefix is retained intentionally.
~~Should the test vectors include intermediate DRBG state (K, V after initialization) to enable debugging of cross-platform divergence at a finer granularity?~~ Resolved: Appendix C now includes the full DRBG state (K, V) after initialization for test vector 1, enabling step-by-step debugging of cross-platform divergence.

All four open questions have been resolved during the self-audit process. We continue to invite feedback on the construction as a whole. The goal is to build a system that is honest about its assumptions and limitations, not one that claims more than it can deliver.

A. Key Derivation Across Cryptographic Domains

The concept of deriving keys for one cryptosystem from another is not new. BIP-32 [6] defines hierarchical deterministic key derivation for Bitcoin, producing child keys from parent keys using HMAC-SHA512. However, BIP-32 operates entirely within the elliptic curve domain (secp256k1 → secp256k1), whereas the bridge construction crosses domain boundaries (elliptic curve → integer factorization).

The NIST Key Derivation Functions (SP 800-108) [7] provide general-purpose KDF constructions but do not address the specific challenge of deriving RSA-type keys (which require prime generation) from elliptic curve material.

B. Threshold Paillier

Threshold Paillier decryption was first proposed by Fouque et al. [8] and later refined by Damgård and Jurik [9]. The implementation follows the Fouque et al. approach, using Shamir’s Secret Sharing over Z_{n·λ} with Lagrange interpolation in the exponent. The key innovation in the bridge construction is combining threshold Paillier with deterministic key derivation from ECDH, enabling a unified key management model.

C. Homomorphic Encryption in Voting

Homomorphic encryption for electronic voting was proposed by Benaloh [10] and extensively developed by Cramer et al. [11]. The Paillier cryptosystem has become the preferred choice for additive homomorphic voting due to its efficient homomorphic addition and scalar multiplication operations. The bridge construction contributes to this line of work by simplifying key management in Paillier-based voting systems.

IX. Formal Security Model

A. Definitions

Let B: K_EC → K_P denote the bridge function mapping ECDH key pairs to Paillier key pairs. We define the following security properties formally:

Definition 1 (Bridge One-Wayness): The bridge B is one-way if for all probabilistic polynomial-time (PPT) adversaries A:

Pr[A(B(k)) = k : k ←$ K_EC] ≤ negl(λ)

where λ is the security parameter and negl denotes a negligible function.

Definition 2 (Bridge Determinism): The bridge B is deterministic if for all k ∈ K_EC:

B(k) = B(k)  (with probability 1)

Definition 3 (Bridge Collision Resistance): The bridge B is collision-resistant if for all PPT adversaries A:

Pr[B(k₁) = B(k₂) ∧ k₁ ≠ k₂ : (k₁, k₂) ← A(1^λ)] ≤ negl(λ)

Definition 4 (Domain Separation): For bridge functions B_info₁ and B_info₂ parameterized by different HKDF info strings, the outputs are computationally independent:

{B_info₁(k)} ≈_c {B_info₂(k)}  for all k ∈ K_EC

where ≈_c denotes computational indistinguishability.

B. Security Theorem

Theorem 1: Under the assumptions that (i) HMAC-SHA512 is a PRF, (ii) the ECDLP on secp256k1 is hard, and (iii) factoring 3072-bit integers is hard, the bridge construction B satisfies one-wayness, determinism, collision resistance, and domain separation as defined above.

Proof sketch: One-wayness follows from the composition of one-way functions (ECDH → HKDF → DRBG → factoring). Determinism follows from the deterministic nature of each stage. Collision resistance follows from the collision resistance of HKDF-SHA512 (birthday bound ~2²⁵⁶) composed with the negligible probability of two independent DRBG instances producing the same prime pair. Domain separation follows from the PRF property of HMAC-SHA512 applied to different info strings in the HKDF expand phase. □

X. Implementation Considerations

A. Cross-Platform Architecture

The implementation provides two parallel implementations:

@digitaldefiance/ecies-lib (browser): Uses Web Crypto API (crypto.subtle) for all cryptographic operations. All operations are async due to the Web Crypto API’s promise-based interface.
@digitaldefiance/node-ecies-lib (Node.js): Uses the crypto module for cryptographic operations. Provides both sync and async interfaces, with sync operations using createHmac() and createHash() directly.

Both implementations share the same mathematical logic and produce byte-identical output for the same inputs. The IsolatedPublicKey and IsolatedPrivateKey classes are implemented independently in each package but conform to shared interfaces defined in ecies-lib.

B. Dependency Management

The Paillier implementation depends on the paillier-bigint library, which is loaded dynamically (await import('paillier-bigint') in the browser, require('paillier-bigint') in Node.js). This allows the voting functionality to be an optional feature — applications that don’t use voting don’t need to install the Paillier dependency.

The @noble/curves/secp256k1 library provides the ECDH shared secret computation, chosen for its audited, constant-time implementation and cross-platform compatibility.

C. Singleton Pattern

The VotingService uses a singleton pattern (VotingService.getInstance()) to ensure consistent configuration across an application. This is appropriate because the service is stateless (all state is in the keys themselves) and the configuration parameters (curve name, key size, etc.) should be consistent within a deployment.

D. Error Handling

The implementation defines a comprehensive error taxonomy through the VotingErrorType enumeration, covering:

Key format validation errors (wrong magic bytes, unsupported version, buffer too short)
Key ID mismatches (corrupted or tampered keys)
Instance ID mismatches (cross-instance decryption attempts)
HMAC validation failures (ciphertext tampering)
Prime generation failures (exceeded maximum attempts)

Each error type maps to a specific failure mode, enabling precise diagnostics in production systems.

XI. Conclusion

The Paillier Bridge Key Derivation construction provides a practical solution to the key management challenge in hybrid cryptographic voting systems. By deterministically deriving Paillier homomorphic encryption keys from ECDH key material, the construction reduces the key management burden from two independent key pairs to a single ECC private key, while preserving the security properties of both cryptosystems.

The construction achieves 128-bit security through a carefully composed pipeline of established cryptographic primitives (ECDH, HKDF, HMAC-DRBG, Miller-Rabin), with formal security guarantees under standard assumptions. The instance isolation layer provides session separation to prevent ballot replay attacks, and the threshold extension enables distributed trust through k-of-n decryption.

However, the construction is not without limitations. The deterministic nature creates a tension with forward secrecy, the computational cost of prime generation introduces provisioning latency, and the entire construction is vulnerable to quantum attacks. The ceremony coordinator trust assumption in the threshold extension represents a practical deployment concern that could be addressed through distributed key generation protocols.

Future work should address post-quantum migration paths, investigate distributed key generation protocols that eliminate the trusted coordinator, and explore the application of the bridge construction to other homomorphic encryption schemes (e.g., lattice-based systems) that may provide quantum resistance.

References

[1] P. Paillier, “Public-Key Cryptosystems Based on Composite Degree Residuosity Classes,” in Advances in Cryptology — EUROCRYPT ‘99, Springer, 1999, pp. 223–238.

[2] E. Barker, “Recommendation for Key Management: Part 1 — General,” NIST Special Publication 800-57 Part 1, Revision 5, May 2020.

[3] H. Krawczyk and P. Eronen, “HMAC-based Extract-and-Expand Key Derivation Function (HKDF),” RFC 5869, May 2010.

[4] E. Barker and J. Kelsey, “Recommendation for Random Number Generation Using Deterministic Random Bit Generators,” NIST Special Publication 800-90A, Revision 1, June 2015.

[5] A. Shamir, “How to Share a Secret,” Communications of the ACM, vol. 22, no. 11, pp. 612–613, November 1979.

[6] P. Wuille, “BIP-32: Hierarchical Deterministic Wallets,” Bitcoin Improvement Proposal, February 2012.

[7] L. Chen, “Recommendation for Key Derivation Using Pseudorandom Functions,” NIST Special Publication 800-108, Revision 1, August 2022.

[8] P.-A. Fouque, G. Poupard, and J. Stern, “Sharing the Ability to Open Encrypted Messages,” Journal of Cryptology, vol. 14, no. 4, pp. 259–280, 2001.

[9] I. Damgård and M. Jurik, “A Generalisation, a Simplification and Some Applications of Paillier’s Probabilistic Public-Key System,” in Public Key Cryptography — PKC 2001, Springer, 2001, pp. 119–136.

[10] J. Benaloh, “Verifiable Secret-Ballot Elections,” Ph.D. dissertation, Yale University, 1987.

[11] R. Cramer, R. Gennaro, and B. Schoenmakers, “A Secure and Optimally Efficient Multi-Authority Election Scheme,” in Advances in Cryptology — EUROCRYPT ‘97, Springer, 1997, pp. 103–118.

[12] Y. Jiang and Y. Deng, “Strong Pseudoprimes to the First Eight Prime Bases,” Mathematics of Computation, vol. 83, no. 290, pp. 2915–2924, 2014.

[13] J. Sorenson and J. Webster, “Strong Pseudoprimes to Twelve Prime Bases,” Mathematics of Computation, vol. 86, no. 304, pp. 985–1003, 2017. (Establishes ψ₁₂ ≈ 3.19×10²⁴.)

Appendix A: Configuration Constants

The following constants are defined in the VOTING configuration object and govern the bridge construction’s behavior:

Constant	Value	Purpose
`PRIME_GEN_INFO`	`"PaillierPrimeGen"`	HKDF domain separation string
`PRIME_TEST_ITERATIONS`	`256`	Miller-Rabin rounds: 12 deterministic small-prime witnesses + 244 HMAC-SHA256-derived witnesses
`KEYPAIR_BIT_LENGTH`	`3072`	Paillier modulus bit length
`PUB_KEY_OFFSET`	`768`	Hex padding for key serialization
`HKDF_LENGTH`	`64`	HKDF output bytes
`HMAC_ALGORITHM`	`"sha512"`	HKDF/DRBG hash algorithm
`HASH_ALGORITHM`	`"sha256"`	Key ID / HMAC tag algorithm
`KEY_RADIX`	`16`	Hex serialization radix
`KEY_VERSION`	`2`	Serialization format version
`KEY_MAGIC`	`"BCVK"`	BrightChain Voting Key identifier
`CHECKSUM_LENGTH`	`32`	SHA-256 checksum appended to serialized keys

Appendix B: Voting Method Security Classification

Method	Security Level	Homomorphic Operations Used	Notes
Plurality	Fully Homomorphic	Addition	One-hot encoding, sum per candidate
Approval	Fully Homomorphic	Addition	Binary vector, sum per candidate
Weighted	Fully Homomorphic	Addition	Scalar-weighted one-hot encoding
Borda	Fully Homomorphic	Addition	Point allocation, sum per candidate
Score	Fully Homomorphic	Addition	Score encoding, sum per candidate
YesNo	Fully Homomorphic	Addition	Binary choice, sum
YesNoAbstain	Fully Homomorphic	Addition	Ternary encoding, sum per option
Supermajority	Fully Homomorphic	Addition	Binary choice with threshold check
RankedChoice	Multi-Round	Addition + Decryption	Requires elimination rounds
TwoRound	Multi-Round	Addition + Decryption	Top-2 runoff requires intermediate tally
STAR	Multi-Round	Addition + Decryption	Score phase + runoff phase
STV	Multi-Round	Addition + Decryption	Proportional with elimination
Quadratic	Insecure	Requires sqrt (non-homomorphic)	Credit cost = vote²
Consensus	Insecure	Requires threshold check	95%+ agreement reveals positions
ConsentBased	Insecure	Requires objection detection	Individual objections must be visible

Appendix C: Reproducible Test Vector

The following test vector enables independent implementations to verify byte-exact agreement at each pipeline stage. The ECDH private key is derived deterministically as SHA-256("PaillierBridgeTestVector1"). The full vector (with complete hex values) is available in packages/digitaldefiance-node-ecies-lib/tests/fixtures/bridge-vectors.json.

C.1. Input: ECDH Key Pair

Private key (32 bytes):
  9f57dd33c6480a67dce6058da3ef16d18549b3bbe8851399742c92b5575a1c2d

Public key (65 bytes, uncompressed):
  04ce83152404ea19e8f8674e0303e4857e5073d98c535fc2b9843b47451a1559
  af620cb7ff4fc2c7e412ae361e6d5c846670ed48abba580297cc96aed5efc2baec

C.2. Stage 1: ECDH Shared Secret (65 bytes)

042ba64b426b0dbbd2cef5adfbdc2cb4543c2a2deffb684a476d58fe93965bd5
2a4688289ae409de8927c13348ec138d60878bcd84d17206c1464c94d8acbb4f5a

Computed via secp256k1.getSharedSecret(privKey, pubKey, false) — self-ECDH for this single-party vector.

C.3. Stage 2: HKDF-SHA512 Seed (64 bytes)

Parameters:
  IKM       = shared secret (65 bytes above)
  salt      = 0x00 × 64  (64 zero bytes)
  info      = "PaillierPrimeGen"  (0x5061696c6c6965725072696d6547656e)
  L         = 64
  algorithm = SHA-512

Output seed:
  c3df32be5fa20f722c0c9281fbc98c5aa062708bb00e48364dd811e7d9a2745d
  757bb2865e40e3f421b4eec5e109f6ef5ca4ea1882ebc522029de6499755b297

C.4. Stage 3: HMAC-DRBG Initialization

Algorithm: HMAC-DRBG per NIST SP 800-90A, using SHA-512
Initial K: 0x00 × 64
Initial V: 0x01 × 64
Seed:      (64 bytes from Stage 2)

After update step 1 (K = HMAC(K, V || 0x00 || seed), V = HMAC(K, V)):
  K: f87ee0f04656fa248564c2aefaba35b5d881525cec9cd03ee306d61733ef6006
     aad01aa936e6bd706043812fab51bfba7c0a9e39cb31cad79c1caf3b4d341d32
  V: 2f99a2cae6febad66e90c97e7e72ae2c3e75d361763e75eef6f2c9dac6e157b4
     3a2145e62dcded23d3eb3b2a014ca32333975029b3b17699b641d18685780362

After update step 2 (K = HMAC(K, V || 0x01 || seed), V = HMAC(K, V)):
  K: 98f41217b3991da1fa5826e5abe4c5e7dc9f0a08b2ed6e217d15b15af83e66eb
     6055a4f499654840366bf2e6f8982d056eb744321f092dc680fec279956403a5
  V: aa50c847de670b93b2afbc70b2906ba60c7b08fddcf9bf71e4af95bfc85f3554
     b85ff0abbbc4de79027a5dcb2ced1778f2cbbdb825c41df24224d56e6a21a15a

These intermediate values enable step-by-step debugging of cross-platform DRBG divergence. An independent implementation should match K and V exactly after each update step before proceeding to prime generation.

C.5. Stage 3: Prime Generation

Both primes are 1536 bits. First 64 hex characters shown; full values in the JSON fixture.

p (1536 bits):
  c3ee9e0f1cdef0dc699ab675b515edb8c76c2829566bea6e0847b42f1b3f886a...

q (1536 bits):
  f33d85e365fbd972fa73d4fd48c51e67e093ea4419a9c5f25e6de7aa2b45ab12...

Miller-Rabin: 256 rounds (12 deterministic small-prime witnesses + 244 HMAC-SHA256-derived witnesses). Small prime sieve: first 54 primes (2 through 251).

C.6. Stage 4: Paillier Key Pair

n = p × q (3072 bits):
  ba2a965d04c366e53cb73ebe6586f73b75c793e6bd2b925d3a71448ae158f03f...

g = n + 1

λ = lcm(p−1, q−1):
  5d154b2e8261b3729e5b9f5f32c37b9dbae3c9f35e95c92e9d38a24570ac781f...

μ = (L(g^λ mod n²))⁻¹ mod n:
  3f1cd8a8123351352bb4da5aa551239f0b92ab9e65240cc9ea6a8709534da203...

Validation: encrypt(42) → decrypt → 42 ✓

C.7. Key Identifier

nHex = hex(n).padStart(768, '0')
keyId = SHA-256(UTF-8(nHex))
      = 09f0fd4634ab2e5a14174860a8bd6a9698239929848b8b696d16401b9ce5e88d

C.8. Second Test Vector (Summary)

A second vector demonstrates that the algorithm is specified tightly enough to produce distinct, correct keys from different inputs. Full hex values are in the JSON fixture.

Input:     SHA-256("PaillierBridgeTestVector2")
Private key: 6b17fb1474c776db314962bdbe0f7af9f7d7726a50ade06b406e674efbcbb293
HKDF seed:   9a7306e0a7ff56df33d8eda8d5d6883343bf28a88923131616890e9a69f1c28e...
p (1536 bits): bcd1ea155c0b29b84b8593cd8f3972678de81cf468eadef37d16a57b081ccbcc...
q (1536 bits): 8d3dbc3f6332b1ebcca12f482be5183547f34bc54efe31837f22714cffda1a53...
n (3071 bits): 682d26cb7383f13e55224809c1bf003ac542b4bb8868724e6796dac6c3ec4c9b...
keyId:         b65ad7907d0a4b149aa26a8bf3f1b46d48aef7d9300371f7202261424180af00
Validation:    encrypt(42) → decrypt → 42 ✓

Note: n is 3071 bits rather than 3072 because the product of two 1536-bit primes can occasionally be one bit shorter when the leading bits do not carry. This is expected and does not affect security — the modulus is still within the 3072-bit security class.

C.9. Verification Procedure

An independent implementation should:

Derive the private key: SHA-256("PaillierBridgeTestVector1") → 32 bytes
Compute the secp256k1 public key (uncompressed) and verify against C.1
Compute the ECDH shared secret (self-ECDH) and verify against C.2
Run HKDF-SHA512 with the exact parameters in C.3 and verify the seed
Initialize HMAC-DRBG with the seed and generate primes; verify p and q match C.5
Construct the Paillier key pair and verify n, λ, μ match C.6
Compute the keyId and verify against C.7
Repeat steps 1–7 with SHA-256("PaillierBridgeTestVector2") and verify against C.8
Perform a test encryption of 42 and verify decryption succeeds for both key pairs

Any divergence at any stage indicates an implementation incompatibility that must be resolved before the bridge can be used for cross-platform key recovery.

Paillier Bridge Key Derivation: A Deterministic Construction for Bridging Elliptic Curve and Homomorphic Encryption Key Spaces

I. Introduction

A. Motivation

B. Contributions

C. Paper Organization

II. Background

A. The Paillier Cryptosystem

B. Elliptic Curve Diffie-Hellman (ECDH)

C. HKDF (RFC 5869)

D. HMAC-DRBG (NIST SP 800-90A)

III. Bridge Key Derivation Construction

A. Overview

B. Stage 1: Shared Secret Computation

C. Stage 2: HKDF Key Derivation

D. Stage 3: Deterministic Prime Generation

E. Stage 4: Paillier Key Construction

F. Complete Reproducible Algorithm Specification

F.1. Input Normalization

F.2. Shared Secret (Stage 1)

F.3. HKDF-SHA512 (Stage 2)

F.4. HMAC-DRBG Initialization (Stage 3a)

F.5. Prime Generation (Stage 3b)

F.6. Paillier Key Construction (Stage 4)

IV. Instance Isolation Layer

A. Motivation

B. IsolatedPublicKey Construction

C. IsolatedPrivateKey Validation

D. Homomorphic Operations Under Isolation

E. Instance Rotation

V. Threshold Extension

A. Distributed Trust Model

B. Key Share Generation

C. Partial Decryption

D. Decryption Combining

E. Integration with Bridge Keys

VI. Security Analysis

A. One-Wayness

B. Determinism and Key Recovery

C. Collision Resistance

D. Domain Separation

E. Security Level Assessment

VII. Pitfalls and Limitations

A. Prime Generation Bias

B. Cross-Platform Reproducibility

C. Determinism vs. Forward Secrecy

D. Quantum Vulnerability

E. Computational Cost of Prime Generation

E.1. Safe Primes: Evaluated and Deferred

F. DRBG State Exhaustion

G. Timing Side Channels

H. The Ceremony Coordinator Trust Assumption

I. Homomorphic Security Classification

J. Key Serialization and Interoperability

K. Miller-Rabin Witness Count: Discovery and Resolution

L. Comparison with Alternative Approaches

M. Honest Disclosure: Status and Limitations

VIII. Related Work

A. Key Derivation Across Cryptographic Domains

B. Threshold Paillier

C. Homomorphic Encryption in Voting

IX. Formal Security Model

A. Definitions

B. Security Theorem

X. Implementation Considerations

A. Cross-Platform Architecture

B. Dependency Management

C. Singleton Pattern

D. Error Handling

XI. Conclusion

References

Appendix A: Configuration Constants

Appendix B: Voting Method Security Classification

Appendix C: Reproducible Test Vector

C.1. Input: ECDH Key Pair

C.2. Stage 1: ECDH Shared Secret (65 bytes)

C.3. Stage 2: HKDF-SHA512 Seed (64 bytes)

C.4. Stage 3: HMAC-DRBG Initialization

C.5. Stage 3: Prime Generation

C.6. Stage 4: Paillier Key Pair

C.7. Key Identifier