Struct elastic_elgamal::RangeProof
source · pub struct RangeProof<G: Group> { /* private fields */ }
Expand description
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):
- Represent the encrypted value
x
asx = x_0 + k_0 * x_1 + k_0 * k_1 * x_2 + …
, where0 <= x_i < t_i
is the decomposition ofx
as per theRangeDecomposition
,0..t_0 + k_0 * (0..t_1 + …)
. As an example, ifn
is a power of 2, one can choose a decomposition as the base-2 presentation ofx
, i.e.,t_i = k_i = 2
for alli
. For brevity, denote a multiplier ofx_i
inx
decomposition asK_i
,K_i = k_0 * … * k_{i-1}
;K_0 = 1
by extension. - Split the ciphertext:
E = E_0 + E_1 + …
, whereE_i
encryptsK_i * x_i
. - Produce a
RingProof
that for alli
the encrypted scalar forE_i
is among 0,K_i
, …,K_i * (t_i - 1)
. The range proof consists of allE_i
ciphertexts and thisRingProof
.
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§
source§impl<G: Group> RangeProof<G>
impl<G: Group> RangeProof<G>
sourcepub fn new<R: RngCore + CryptoRng>(
receiver: &PublicKey<G>,
range: &PreparedRange<G>,
value: u64,
transcript: &mut Transcript,
rng: &mut R
) -> (CiphertextWithValue<G, u64>, Self)
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
.
sourcepub fn from_ciphertext<R: RngCore + CryptoRng>(
receiver: &PublicKey<G>,
range: &PreparedRange<G>,
ciphertext: &CiphertextWithValue<G, u64>,
transcript: &mut Transcript,
rng: &mut R
) -> Self
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
.
sourcepub fn verify(
&self,
receiver: &PublicKey<G>,
range: &PreparedRange<G>,
ciphertext: Ciphertext<G>,
transcript: &mut Transcript
) -> Result<(), VerificationError>
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§
source§impl<G: Clone + Group> Clone for RangeProof<G>
impl<G: Clone + Group> Clone for RangeProof<G>
source§fn clone(&self) -> RangeProof<G>
fn clone(&self) -> RangeProof<G>
1.0.0 · source§fn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
source
. Read more