Using only a logarithmic number of blinding scalars

[bbuenz]

In a recent paper (https://eprint.iacr.org/2019/944) Hoffmann, Kloß and Rupp show how to reduce the required blinding scalars to only a logarithmic number. This could be a nice prover speedup.
The main idea is that for each value send in the inner product argument only a single blinding scalar is needed. The blinding vector s therefore only needs 2 log(n) random entries at specific positions. It's explained in section 3.4.3 of the paper.

They also have an implementation here: https://github.com/emsec/QESA_ZK

CC: @devhoffmann

[hdevalence]

Cool! Thanks for pointing this out. We should check

1. whether this optimization can be done transparently by the prover;
2. an estimate on how much time it actually saves – I think the dominant part of the prover's work is the group operations in the inner product argument, so if it only saves a few scalar operations it may not be worthwhile.

[bbuenz]

I think the main advantage is that it reduces the number of prover operations that need to be done with constant time exponentiations. It would cheapen the computation of S. But obviously if it's only a minor save then it's not worthwhile.

[kenshamir]

For anyone looking to verify the prover performance, you can use the code at https://github.com/crate-crypto/qesa/blob/master/src/ipa/no_zk.rs

It was specifically made to mimic the Dalek bulletproof IPA API to test performance. However naively, only verifier performance was tested.

As stated on Pg39 "Optimised verification performance of Bulletproofs and our proof systems is almost identical" in the multiexponetiation setting.

Evidence: https://github.com/kenshamir/qesa/blob/nozk-verifier/src/ipa/no_zk.rs