# Struct elastic_elgamal::RingProof

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

## Expand description

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:

- Select random scalar
`x`

and compute`R_G(j) = [x]G`

,`R_K(j) = [x]K`

. - 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. - 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§

source§### impl<G: Group> RingProof<G>

### impl<G: Group> RingProof<G>

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

#### 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.

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

#### 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.