[CFRG] Re: BBS+ benchmarks v06

[Michele Orrù <[e-mail]>]

Hi Jaromil,


Good job and it's nice to see you around here. A few notes on the
benchmarks.

I did not understand if "credentials" means "attribute" (an element in the
message array) in your jargon.

If I understand correctly you say a graph is "logarithmic", but it looks
more exponential than logarithmic. Well.. it could even be poly for that
matter.

Unless I'm missing something big, BBS sign and verify are linear in the
number of issued credentials and blind BBS presentation should also be
linear when implemented with Schnorr proofs.

Please correct me if I'm wrong here!

Is it correct that blind issuance (so private attributes) has not been
implemented?


There are a few minor improvements that I think can be made technically,
but that are not yet in the BBS draft (I think?)

- Amortize verification cost (by a constant factor, not asymptotically),
using the strategy already described in BIP 0340
<https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#user-content-Batch_Verification>
without too much burden on the implementor's side.

- Use fixed-basis exponentiation instead of standard exponentiation for the
generators.

- Use Pippenger's algorithm for multi-scalar-multiplication, which has
complexity O(n/log n) instead of O(n). Here's an example from arkworks
<https://github.com/arkworks-rs/algebra/blob/master/ec/src/scalar_mul/variable_base/mod.rs>
that I generalised from dalek's
<https://github.com/dalek-cryptography/curve25519-dalek/blob/main/curve25519-dalek/src/backend/serial/scalar_mul/pippenger.rs>
.

It would perhaps be worth mentioning them in the BBS spec.


In addition, for closed systems, where the issuer and redeemer are the same
person (this is the case in Signal, in Tor, and often in the Web -- just
like in [Privacy Pass <https://datatracker.ietf.org/wg/privacypass/about/>]),
one does not need a pairing map. They could check the signature using x.
The proofs are not made in the target group but instead done in the group.
This was done by Barkit et al. [BBDT16
<https://link.springer.com/chapter/10.1007/978-3-319-69453-5_20>, Fig. 2]
and I essentially do the same with minor changes in [Orru24
<https://eprint.iacr.org/2024/1552.pdf>, Figure 6]. Off the top of my head,
I can say it'd be about 1.5x faster but it'd be exciting (also for the
generic spec) to get input on whether it'd be useful for implementers to
have potentially simpler requirements and codebase.

This last comment is more high-level and I'll follow up with a more
detailed email in a separate thread.

On Fri, Oct 11, 2024 at 1:46 PM Jaromil <[e-mail]> wrote:

> Dear colleagues,
>
> I'm following up on the feedback I got by participants to the last W3C CCG
> in which I've presented my independent analysis on BBS+ v06. The benchmarks
> article is now updated, as well the code used to do the benchmarks, and
> available from the same site:
>
> https://news.dyne.org/benchmark-of-the-bbs-signature-scheme-v06/
>
> The update includes the "Size" section now including the measurement of
> size growth with the growth of total credentials. As well a "Security
> Considerations" new section with a caveat for anyone implementing a BBS+
> powered application.
>
> Ciao!
>
> --
>
>   Denis "Jaromil" Roio   Dyne.org think &do tank
>   Ph.D, CTO & founder    software to empower communities
>   ✉ Haparandadam 7-A1, 1013AK Amsterdam, The Netherlands
>   𝄞 crypto κρυπτο крипто क्रिप्टो 加密 التشفير הצפנה
>   ⚷ 6113D89C A825C5CE DD02C872 73B35DA5 4ACB7D10
>
> _______________________________________________
> CFRG mailing list -- [e-mail]
> To unsubscribe send an email to [e-mail]
>