Struct elastic_elgamal::RingProof

pub struct RingProof<G: Group> { /* private fields */ }

Zero-knowledge proof that the one or more encrypted values is each in the a priori known set of admissible values. (Admissible values may differ among encrypted values.)

Construction

In short, a proof is constructed almost identically to Borromean ring signatures by Maxwell and Poelstra, with the only major difference being that we work on ElGamal ciphertexts instead of group elements (= public keys).

A proof consists of one or more rings. Each ring proves than a certain ElGamal ciphertext E = (R, B) for public key K in a group with generator G encrypts one of distinct admissible values x_0, x_1, …, x_n. K and G are shared among rings, admissible values are generally not. Different rings may have different number of admissible values.

Single ring

A ring is a challenge e_0 and a set of responses s_0, s_1, …, s_n, which must satisfy the following verification procedure:

For each j in 0..=n, compute

R_G(j) = [s_j]G - [e_j]R;
R_K(j) = [s_j]K - [e_j](B - [x_j]G);
e_{j+1} = H(j, R_G(j), R_K(j));

Here, H is a cryptographic hash function. The ring is valid if e_0 = e_{n+1}.

This construction is almost identical to Abe–Ohkubo–Suzuki ring signatures, with the only difference that two group elements are hashed on each iteration instead of one. If admissible values consist of a single value, this protocol reduces to LogEqualityProof / Chaum–Pedersen protocol.

As with “ordinary” ring signatures, constructing a ring is only feasible when knowing additional trapdoor information. Namely, the prover must know

r = dlog_G(R) = dlog_K(B - [x_j]G)

for a certain j. (This discrete log r is the random scalar used in ElGamal encryption.) With this info, the prover constructs the ring as follows:

1. Select random scalar x and compute R_G(j) = [x]G, R_K(j) = [x]K.
2. Compute e_{j+1}, … e_n, …, e_j (“wrapping” around e_0 = e_{n+1}) as per verification formulas. s_* scalars are selected uniformly at random.
3. Compute s_j using the trapdoor information: s_j = x + e_j * r.

Multiple rings

Transformation to multiple rings is analogous to one in Borromean ring signatures. Namely, challenge e_0 is shared among all rings and is computed by hashing values of R_G and R_K with the maximum index for each of the rings.

Applications

Voting protocols

EncryptedChoice uses RingProof to prove that all encrypted values are Boolean (0 or 1). Using a common challenge allows to reduce proof size by ~33%.

Range proofs

See RangeProof.

Implementation details

• The proof is serialized as the common challenge e_0 followed by s_i scalars for all the rings.
• Standalone proof generation and verification are not exposed in public crate APIs. Rather, proofs are part of large protocols, such as PublicKey::encrypt_bool() / PublicKey::verify_bool().
• The context of the proof is set using Transcript APIs, which provides hash functions in the protocol described above. Importantly, the proof itself commits to encrypted values and ring indexes, but not to the admissible values across the rings. This must be taken care of in a higher-level protocol, and this is the case for protocols exposed by the crate.

Implementations

impl<G: Group> RingProof<G>

pub fn to_bytes(&self) -> Vec<u8>

Serializes this proof into bytes. As described above, the proof is serialized as the common challenge e_0 followed by response scalars s_* corresponding successively to each admissible value in each ring.

pub fn from_bytes(bytes: &[u8]) -> Option<Self>

Attempts to deserialize a proof from bytes. Returns None if bytes do not represent a well-formed proof.

Trait Implementations

impl<G: Clone + Group> Clone for RingProof<G>

where G::Scalar: Clone,

fn clone(&self) -> RingProof<G>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<G: Debug + Group> Debug for RingProof<G>

where G::Scalar: Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'de, G: Group> Deserialize<'de> for RingProof<G>

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<G: Group> Serialize for RingProof<G>

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.