Struct elastic_elgamal::RangeProof

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

Zero-knowledge proof that an ElGamal ciphertext encrypts a value into a certain range 0..n.

Construction

To make the proof more compact – O(log n) in terms of size and proving / verification complexity – we use the same trick as for Pedersen commitments (used, e.g., for confidential transaction amounts in Elements):

1. Represent the encrypted value x as x = x_0 + k_0 * x_1 + k_0 * k_1 * x_2 + …, where 0 <= x_i < t_i is the decomposition of x as per the RangeDecomposition, 0..t_0 + k_0 * (0..t_1 + …). As an example, if n is a power of 2, one can choose a decomposition as the base-2 presentation of x, i.e., t_i = k_i = 2 for all i. For brevity, denote a multiplier of x_i in x decomposition as K_i, K_i = k_0 * … * k_{i-1}; K_0 = 1 by extension.
2. Split the ciphertext: E = E_0 + E_1 + …, where E_i encrypts K_i * x_i.
3. Produce a RingProof that for all i the encrypted scalar for E_i is among 0, K_i, …, K_i * (t_i - 1). The range proof consists of all E_i ciphertexts and this RingProof.

As with range proofs for Pedersen commitments, this construction is not optimal in terms of space or proving / verification complexity for large ranges; it is linear w.r.t. the bit length of the range. (Constructions like Bulletproofs are logarithmic w.r.t. the bit length.) Still, it can be useful for small ranges.

Examples

// Generate the ciphertext receiver.
let mut rng = thread_rng();
let receiver = Keypair::<Ristretto>::generate(&mut rng);
// Find the optimal range decomposition for our range
// and specialize it for the Ristretto group.
let range = RangeDecomposition::optimal(100).into();

let (ciphertext, proof) = RangeProof::new(
    receiver.public(),
    &range,
    55,
    &mut Transcript::new(b"test_proof"),
    &mut rng,
);
let ciphertext = Ciphertext::from(ciphertext);

// Check that the ciphertext is valid
let lookup = DiscreteLogTable::new(0..100);
assert_eq!(receiver.secret().decrypt(ciphertext, &lookup), Some(55));
// ...and that the proof verifies.
proof.verify(
    receiver.public(),
    &range,
    ciphertext,
    &mut Transcript::new(b"test_proof"),
)?;

Implementations

impl<G: Group> RangeProof<G>

pub fn new<R: RngCore + CryptoRng>(
    receiver: &PublicKey<G>,
    range: &PreparedRange<G>,
    value: u64,
    transcript: &mut Transcript,
    rng: &mut R
) -> (CiphertextWithValue<G, u64>, Self)

Encrypts value for receiver and creates a zero-knowledge proof that the encrypted value is in range.

This is a lower-level operation; see PublicKey::encrypt_range() for a higher-level alternative.

Panics

Panics if value is outside the range specified by range.

pub fn from_ciphertext<R: RngCore + CryptoRng>(
    receiver: &PublicKey<G>,
    range: &PreparedRange<G>,
    ciphertext: &CiphertextWithValue<G, u64>,
    transcript: &mut Transcript,
    rng: &mut R
) -> Self

Creates a proof that a value in ciphertext is in the range.

The caller is responsible for providing a ciphertext encrypted for the receiver; if the ciphertext is encrypted for another public key, the resulting proof will not verify.

Panics

Panics if value is outside the range specified by range.

pub fn verify(
    &self,
    receiver: &PublicKey<G>,
    range: &PreparedRange<G>,
    ciphertext: Ciphertext<G>,
    transcript: &mut Transcript
) -> Result<(), VerificationError>

Verifies this proof against ciphertext for receiver and the specified range.

This is a lower-level operation; see PublicKey::verify_range() for a higher-level alternative.

For a proof to verify, all parameters must be identical to ones provided when creating the proof. In particular, range must have the same decomposition.

Errors

Returns an error if this proof does not verify.

Trait Implementations

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

fn clone(&self) -> RangeProof<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 RangeProof<G>

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

Formats the value using the given formatter.

impl<'de, G: Group> Deserialize<'de> for RangeProof<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 RangeProof<G>

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

Serialize this value into the given Serde serializer.