Return-Path: X-Original-To: cfrg@ietfa.amsl.com Delivered-To: cfrg@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id B12D8C151088 for ; Sat, 19 Oct 2024 04:38:09 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -4.393 X-Spam-Level: X-Spam-Status: No, score=-4.393 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_MED=-2.3, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, RCVD_IN_ZEN_BLOCKED_OPENDNS=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_KAM_HTML_FONT_INVALID=0.01, T_SCC_BODY_TEXT_LINE=-0.01, UNPARSEABLE_RELAY=0.001, URIBL_DBL_BLOCKED_OPENDNS=0.001, URIBL_ZEN_BLOCKED_OPENDNS=0.001] autolearn=ham autolearn_force=no Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=ens.fr Received: from mail.ietf.org ([50.223.129.194]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id K96TGlu__VCd for ; Sat, 19 Oct 2024 04:38:05 -0700 (PDT) Received: from nef.ens.fr (nef2.ens.fr [129.199.96.40]) (using TLSv1.2 with cipher ECDHE-ECDSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id B8291C14F6E4 for ; Sat, 19 Oct 2024 04:38:03 -0700 (PDT) X-ENS-nef-client: 129.199.99.32 ( name = mail.di.ens.fr ) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=ens.fr; s=default; t=1729337881; bh=7ZXc+NkiMPorJl1THBYNRZS2OXSYeXj95oDrk1AyFNw=; h=References:In-Reply-To:From:Date:Subject:To:Cc:From; b=ahoZiUTcAmbDi05AVrRAp1XTieqkPmzNyu5VIT4Yv6xaekj2FhCkaXBb2/FoZAnCL bfJ4cdyn7yAemC4ebyo7kKOOz/OGWGXrfcqSxfObB1gMInJYN7TS7FXCMS27Kr3BGd nYF+MMgretW2QR9VMf0NoDMepTLDt+l1xR16UOfI= Received: from mail.di.ens.fr (mail.di.ens.fr [129.199.99.32]) by nef.ens.fr (8.14.4/1.01.28121999) with ESMTP id 49JBc1ul030209 for ; Sat, 19 Oct 2024 13:38:01 +0200 Received: from mail-qv1-f42.google.com using smtps by mail.di.ens.fr (8.15.2/jb-1.1) id 49JBc0Xo025750 for ; Sat, 19 Oct 2024 13:38:01 +0200 (authenticated user morru) X-Envelope-To: Received: by mail-qv1-f42.google.com with SMTP id 6a1803df08f44-6cbcc2bd800so24600766d6.0 for ; Sat, 19 Oct 2024 04:38:01 -0700 (PDT) X-Gm-Message-State: AOJu0YxtJrteEYuRokXrVX9j/uFzqHsGwsYmoNYbVd0FXWQ+ZZTXA+Yf RW7OtdM/9rWYT5PB8+o8c79e1tPxZLWdgknkQZZjydeqq5uvFF4wpzckcYH2euZAMwGl2ecorwB KpppvXNjX+p8SP/Ev4vIbtodAevtoEzZ95wki+A== X-Google-Smtp-Source: AGHT+IGXcRj2rarGhQCLcMikfLAztdgD2eYozvjngL1tZ2o2urGV3Atgx5Hbyf1e3X2b5FUxlNXzLwVYQ0MYr9l1CpI= X-Received: by 2002:a05:6214:5084:b0:6cc:1d39:377 with SMTP id 6a1803df08f44-6cc3786ef87mr143337286d6.13.1729337875221; Sat, 19 Oct 2024 04:37:55 -0700 (PDT) MIME-Version: 1.0 References: <20240823205242.c6kg3h652mrddoui@napoli> <20241011114221.bahblkvehm62jpet@napoli> In-Reply-To: <20241011114221.bahblkvehm62jpet@napoli> From: =?UTF-8?Q?Michele_Orr=C3=B9?= Date: Sat, 19 Oct 2024 13:37:00 +0200 X-Gmail-Original-Message-ID: Message-ID: To: Jaromil , Watson Ladd Content-Type: multipart/alternative; boundary="000000000000bff2a10624d2d9ee" X-Virus-Scanned: by amavisd-milter (http://amavis.org/) X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.4.3 (nef.ens.fr [129.199.96.32]); Sat, 19 Oct 2024 13:38:01 +0200 (CEST) Message-ID-Hash: CDUFZFMXMQVURGVON2DXHMANVO5OSJTQ X-Message-ID-Hash: CDUFZFMXMQVURGVON2DXHMANVO5OSJTQ X-MailFrom: michele.orru@ens.fr X-Mailman-Rule-Misses: dmarc-mitigation; no-senders; approved; emergency; loop; banned-address; member-moderation; header-match-cfrg.irtf.org-0; nonmember-moderation; administrivia; implicit-dest; max-recipients; max-size; news-moderation; no-subject; digests; suspicious-header CC: cfrg@irtf.org, Vasileios Kalos , Andrew Whitehead X-Mailman-Version: 3.3.9rc6 Precedence: list Subject: =?utf-8?q?=5BCFRG=5D_Re=3A_BBS+_benchmarks_v06?= List-Id: Crypto Forum Research Group Archived-At: List-Archive: List-Help: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: --000000000000bff2a10624d2d9ee Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable 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 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 that I generalised from dalek's . 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 ]= ), 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 , Fig. 2] and I essentially do the same with minor changes in [Orru24 , 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=E2=80=AFPM Jaromil wrote: > Dear colleagues, > > I'm following up on the feedback I got by participants to the last W3C CC= G > in which I've presented my independent analysis on BBS+ v06. The benchmar= ks > 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 > =E2=9C=89 Haparandadam 7-A1, 1013AK Amsterdam, The Netherlands > =F0=9D=84=9E crypto =CE=BA=CF=81=CF=85=CF=80=CF=84=CE=BF =D0=BA=D1=80= =D0=B8=D0=BF=D1=82=D0=BE =E0=A4=95=E0=A5=8D=E0=A4=B0=E0=A4=BF=E0=A4=AA=E0= =A5=8D=E0=A4=9F=E0=A5=8B =E5=8A=A0=E5=AF=86 =D8=A7=D9=84=D8=AA=D8=B4=D9=81= =D9=8A=D8=B1 =D7=94=D7=A6=D7=A4=D7=A0=D7=94 > =E2=9A=B7 6113D89C A825C5CE DD02C872 73B35DA5 4ACB7D10 > > _______________________________________________ > CFRG mailing list -- cfrg@irtf.org > To unsubscribe send an email to cfrg-leave@irtf.org > --000000000000bff2a10624d2d9ee Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable

Hi=C2=A0Jaromil,=C2=A0

=

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

I did not understand if "credentials" means "attrib= ute" (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 po= ly for that matter.=C2=A0

Unless I'm missing somet= hing big, BBS sign and verify are linear in the number of issued credential= s and blind BBS presentation should also be linear when implemented with Sc= hnorr proofs.=C2=A0

Please correct me=C2=A0if I'm wrong here!=C2=A0

Is it correct t= hat blind issuance (so private attributes) has not been implemented?=C2=A0<= /span>


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

- Amortize verification cost (by a constant factor, not asymptotical= ly), using the strategy already described in BIP 0340 without too much burden on the implementor's side.=C2=A0

=

- Use fixed-basis exponentiation instead=C2=A0of standard expone= ntiation for the generators.=C2=A0

- Use Pippenger'= ;s algorithm for multi-scalar-multiplication,=C2=A0which has complexity O(n= /log n) instead of O(n). Here's an example from arkworks that I generalised from dalek's.=C2=A0

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


In addition, for closed systems, where the issuer a= nd redeemer are the same person (this is the case in Signal, in Tor, and of= ten in the Web -- just like in [Privacy Pass]), one does not need a pairing map. They could ch= eck 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, Fig. 2] and I e= ssentially do the same with minor changes in [Orru24, 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 potenti= ally 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.=C2=A0


On Fri, Oct 11, 2024= at 1:46=E2=80=AFPM Jaromil <jaromil@dyne.org> 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 be= nchmarks 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-t= he-bbs-signature-scheme-v06/

The update includes the "Size" section now including the measurem= ent of size growth with the growth of total credentials. As well a "Se= curity Considerations" new section with a caveat for anyone implementi= ng a BBS+ powered application.

Ciao!

--

=C2=A0 Denis "Jaromil" Roio=C2=A0 =C2=A0Dyne.org think &do ta= nk
=C2=A0 Ph.D, CTO & founder=C2=A0 =C2=A0 software to empower communities=
=C2=A0 =E2=9C=89 Haparandadam 7-A1, 1013AK Amsterdam, The Netherlands
=C2=A0 =F0=9D=84=9E crypto =CE=BA=CF=81=CF=85=CF=80=CF=84=CE=BF =D0=BA=D1= =80=D0=B8=D0=BF=D1=82=D0=BE =E0=A4=95=E0=A5=8D=E0=A4=B0=E0=A4=BF=E0=A4=AA= =E0=A5=8D=E0=A4=9F=E0=A5=8B =E5=8A=A0=E5=AF=86 =D8=A7=D9=84=D8=AA=D8=B4=D9= =81=D9=8A=D8=B1 =D7=94=D7=A6=D7=A4=D7=A0=D7=94
=C2=A0 =E2=9A=B7 6113D89C A825C5CE DD02C872 73B35DA5 4ACB7D10

_______________________________________________
CFRG mailing list -- cfr= g@irtf.org
To unsubscribe send an email to cfrg-leave@irtf.org
--000000000000bff2a10624d2d9ee--