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:

  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§

source§

impl<G: Group> RingProof<G>

source

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>

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

Trait Implementations§

source§

impl<G: Clone + Group> Clone for RingProof<G>where G::Scalar: Clone,

source§

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

Returns a copy of the value. Read more
1.0.0 · source§

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

Performs copy-assignment from source. Read more
source§

impl<G: Debug + Group> Debug for RingProof<G>where G::Scalar: Debug,

source§

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

Formats the value using the given formatter. Read more
source§

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

source§

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer. Read more
source§

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

source§

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

Serialize this value into the given Serde serializer. Read more

Auto Trait Implementations§

§

impl<G> RefUnwindSafe for RingProof<G>where <G as ScalarOps>::Scalar: RefUnwindSafe,

§

impl<G> Send for RingProof<G>where <G as ScalarOps>::Scalar: Send,

§

impl<G> Sync for RingProof<G>where <G as ScalarOps>::Scalar: Sync,

§

impl<G> Unpin for RingProof<G>where <G as ScalarOps>::Scalar: Unpin,

§

impl<G> UnwindSafe for RingProof<G>where <G as ScalarOps>::Scalar: UnwindSafe,

Blanket Implementations§

source§

impl<T> Any for Twhere T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for Twhere T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for Twhere T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for Twhere U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> Same<T> for T

§

type Output = T

Should always be Self
source§

impl<T> ToOwned for Twhere T: Clone,

§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> TryFrom<U> for Twhere U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for Twhere U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
§

impl<V, T> VZip<V> for Twhere V: MultiLane<T>,

§

fn vzip(self) -> V

source§

impl<T> DeserializeOwned for Twhere T: for<'de> Deserialize<'de>,