Add Lightweight Bulletproof for Linear Relations

[cathieyun]

In a recent paper, Gentry, Halevi, and Lyubashevsky introduced a technique for making a lightweight bulletproof for linear relations, which they call a linear proof. It is a proof of an inner product <a, b> = c where a is secret but b is public. This approach saves a factor of two in the number of exponentiations needed relative to a regular Bulletproofs inner product proof.

GHL21 paper (see section E.3): https://eprint.iacr.org/2021/1397.pdf

I implemented, tested, and benchmarked the code for the protocol, using similar techniques as found in the inner product proof.

Some notes:

• The verification equation in the paper is incorrect: the challenge x_j and inverse challenge x_j^{-1} are reversed. The correct equation is: sum_{j=0}^{l-1} (x_j * L_j + x_j^{-1} * R_j). I will let the authors know.
• The c++ implementation associated with the paper is here: https://github.com/shaih/cpp-lwevss. Benchmarks show that the rust implementation is ~10x faster than the c++ implementation, though I haven't looked into the main causes for that discrepancy.
• Because the linear proof only commits to the vector a and not b, it only needs the G generators. Therefore, we don't need the full BulletproofGens struct. I changed BulletproofGensShare::G() to be pub instead of pub(crate) so that the G generators could be accessed on their own. Let me know if there is a more elegant way to generate/access G without duplicating the generators code.

[cathieyun]

The authors have updated the paper (https://eprint.iacr.org/2021/1397.pdf), so the verification equation typo has been fixed.

PTAL

[oleganza]

@cathieyun sounds great, thank you!