search

dalek-cryptography / bulletproofs

A pure-Rust implementation of Bulletproofs using Ristretto.
MIT License
1.02k stars 218 forks source link

Not using constant time scalar multiplication while creating Inner Product argument #274

Closed lovesh closed 5 years ago

lovesh commented 5 years ago

Is there a reason why constant time scalar multiplication is not used while computing L and R in create of InnerProductProof? eg. this computation for L, similarly further computations of L and R.

oleganza commented 5 years ago

Inner-product protocol is not zero-knowledge: all its inputs have been already blinded (with const-time operations) and not secret anymore. IPP is therefore simply a compression mechanism, so we can use faster non-const-time arithmetic in its implementation.

lovesh commented 5 years ago

By blinding, are you referring to this in test_helper_create. If yes, then only b is blinded.

oleganza commented 5 years ago

No, a,b in this test are already considered blinded. Multiplication by powers y^i is adjustment by a public challenge value.

Blinding the inputs is the job of the higher-level protocol, on top of IPP. E.g. in rangeproof protocol, blinding happens here, where l,r polynomials are computed:

https://github.com/dalek-cryptography/bulletproofs/blob/main/src/range_proof/party.rs#L179-L182

the inputs to IPP are computed as evaluation of these polynomials here:

https://github.com/dalek-cryptography/bulletproofs/blob/main/src/range_proof/party.rs#L274-L275

When polynomials are evaluated at some challenge value x, that's when the vectors a,b (aka l,r) become vectors of blinded scalars. At this point you can skip IPP and instead send those vectors directly to the user, and they could check if <a,b>==t(x). This would be perfectly secure and correct, except that it'll take O(n) bandwidth, instead of O(log(n)).

lovesh commented 5 years ago

Your comment about the blinding happening at higher level answers my question. Thanks :+1: