Re: [Privacy-pass] External verifiability: a concrete proposal

Michele Orrù <lists@tumbolandia.net> Thu, 16 July 2020 15:13 UTC

Return-Path: <michele@tumbolandia.net>
X-Original-To: privacy-pass@ietfa.amsl.com
Delivered-To: privacy-pass@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 94DA43A0AB8 for <privacy-pass@ietfa.amsl.com>; Thu, 16 Jul 2020 08:13:38 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.086
X-Spam-Level:
X-Spam-Status: No, score=-2.086 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, SPF_HELO_NONE=0.001, SPF_NONE=0.001, T_KAM_HTML_FONT_INVALID=0.01, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=tumbolandia.net
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id lJ1gM-0IojyS for <privacy-pass@ietfa.amsl.com>; Thu, 16 Jul 2020 08:13:36 -0700 (PDT)
Received: from mail-ot1-x335.google.com (mail-ot1-x335.google.com [IPv6:2607:f8b0:4864:20::335]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 9E8F23A0AB5 for <privacy-pass@ietf.org>; Thu, 16 Jul 2020 08:13:36 -0700 (PDT)
Received: by mail-ot1-x335.google.com with SMTP id h13so4481320otr.0 for <privacy-pass@ietf.org>; Thu, 16 Jul 2020 08:13:36 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=tumbolandia.net; s=google; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=rUtAblog6/xrUzg8hMutPERXH6vPIGDTC3vVzuEcQkU=; b=hyDw+i3rdL5MTAJwCkp4y1tMlEUpXR+iCBrswwMsXzrsX7OdS0SrSZpfEHekBxi+xX ALwwxhG+FBpjabonbNpZZw3u/R80za9W3uZcrfWRok9wDoSJH1czdc50OBnQ55XRbjcx UwHWQ4fzNEL8wfpLZ1TiV92Dn2Rfj5cCa3H4NEJwCeiNYcb70s9wy8WFx4+8Rxq4MyQq sIKxTPox9uLq8Jv9BrfLGVkSWzGNzkgOReTIBMTm6jrYFkNIye2fthGCxajkEy0d9o// Pz4D85Ul8nzbCtpZcwk3dTUT/F+W0IldwdOalUJ3Ixjeg1CjfF22FnIjEMZOL5NXia9Y OMag==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=rUtAblog6/xrUzg8hMutPERXH6vPIGDTC3vVzuEcQkU=; b=rkPXPzm26xGLq2HF8SEbONPLOA0LFdk4Q59FckGeaWQl42wA+pOGMhFpC2pWl0ZQW0 ymdajuFdgfP0WC7deOLDB7Dxzt58kRyH87E3XBseDm5tz8/85Ssn/FN/hh+9tIqtXS7p HbnI80A1ei2CVHcYCwMznCBEKCvInGuFpZROC2cGay4k47ICZe9ArwA9NfV6emk+B7AN cq9KuVb5ktXA6vd0hKak0vbEGyxXiY8rmWJ0PWq7jNj/gt+WnT0o1Net00Klpc4Vzyc7 PS9nilKPW1id3JCHbciS3VqNAkB1OmjUyiLRo8nokJNZcY5RyDslgEg7SogjJ9kB6tZr rGIA==
X-Gm-Message-State: AOAM533drpJcl5tko3cUXp7BoqSbJ4nEf9D0hrzamBScwn5pI5RzqCfC pSVPPCwoAVCvhC8rQqjFRwC/OEc/Pf//x/EYCFCfAQ==
X-Google-Smtp-Source: ABdhPJyFGvdHNCTMurV1vK2qB4hvatgs94AcMWIi+OI23Idu5ZC/W8xR17rCt/m/FUNX+KvpQA/ZuTBrlAMUvt+GgGg=
X-Received: by 2002:a9d:3e82:: with SMTP id b2mr4865976otc.320.1594912410436; Thu, 16 Jul 2020 08:13:30 -0700 (PDT)
MIME-Version: 1.0
References: <CACsn0c=KCcq27wEiVnkRritmuxYyR_mewwe48FBx1YnxZTu_aA@mail.gmail.com> <CAHbrMsB_5Y58St3dKu2SeAuxPYEV6=VuDxC+DbpTzhwi8iJHKw@mail.gmail.com> <CACsn0c=u9ETDw-tvC26Yz8odPT4bO7CFFrnC8+AvEwgZ5Y8s8A@mail.gmail.com> <AE699CA2-3B60-44B2-823E-1AC620BBB2EC@cloudflare.com> <20200710134907.GW4003@yoink.cs.uwaterloo.ca> <CAOyO2_Jb8iEg=qY-mPCfyQ5Tyf2H-Qm46Avd=8t7ngi-1NcEzg@mail.gmail.com> <6476CDA9-688F-4970-9287-C35893CBFA90@cloudflare.com>
In-Reply-To: <6476CDA9-688F-4970-9287-C35893CBFA90@cloudflare.com>
From: Michele Orrù <lists@tumbolandia.net>
Date: Thu, 16 Jul 2020 17:13:14 +0200
Message-ID: <CAOyO2_KEX4oo3jcRJUYTsCC2TSogV946V8aEDZT42sC9_3C0-w@mail.gmail.com>
To: Alex Davidson <adavidson@cloudflare.com>
Cc: privacy-pass@ietf.org
Content-Type: multipart/alternative; boundary="000000000000ac221d05aa907b2b"
Archived-At: <https://mailarchive.ietf.org/arch/msg/privacy-pass/yjNASkKGm8bkwqtQ4mwGRZrwcoU>
Subject: Re: [Privacy-pass] External verifiability: a concrete proposal
X-BeenThere: privacy-pass@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: <privacy-pass.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/privacy-pass>, <mailto:privacy-pass-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/privacy-pass/>
List-Post: <mailto:privacy-pass@ietf.org>
List-Help: <mailto:privacy-pass-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/privacy-pass>, <mailto:privacy-pass-request@ietf.org?subject=subscribe>
X-List-Received-Date: Thu, 16 Jul 2020 15:13:39 -0000

Hi Alex,

right, thanks for bringing this up! I had measured *verification for a
single token* (in all schemes).
Batched verification in blind BLS could be done at the amortized cost of
one scalar multiplication for each element, using the same trick for
batched tokens in privacy pass [2008/015
<https://eprint.iacr.org/2008/015.pdf>, Fig. 6].

You can find a link for clause blind Schnorr here: [2019/877
<https://eprint.iacr.org/2019/877.pdf>, section 5]; Antoine also made a
nice presentation <https://www.youtube.com/watch?v=W-uwVdGeUUs> to explain
it.
I'm not sure we should consider their adoption yet; perhaps the protocol
and the assumption are just too new?

On Tue, Jul 14, 2020 at 5:15 PM Alex Davidson <adavidson@cloudflare.com>
wrote:

> Hi Michele,
>
> Thanks, this is really informative. Is the verification time for the blind
> BLS construction for only a single token? Or is it batched for multiple
> tokens?
> Do you have a link for the Clause Blind Schnorr signature scheme? Is there
> a reason why we would not consider this scheme instead, if it is more
> efficient?
>
> Best,
> Alex
>
> On 11 Jul 2020, at 20:32, Michele Orrù <lists@tumbolandia.net> wrote:
>
> Hi,
>
> To my understanding, Watson is proposing to use blind BLS signatures
> (BBLS) as an option for public verifiability.
> In section 5.1 of [Boldyreva
> <https://www.cc.gatech.edu/~aboldyre/papers/bold.pdf>] they are described
> with additive blinding; If you apply it multiplicatively you have Privacy
> Pass (PP) with a DH oracle.
>
> I think that's a great idea to add this as a possible publicly-verifiable
> mechanism. The assumptions are more or less the same: PP is exposing a DH
> oracle with the NIZK, BBLS will do so with the pairing; PP uses
> chosen-target Diffie-Hellman and so will BBLS [JKK
> <https://eprint.iacr.org/2014/650.pdf>]. However, I don't particularly
> see the advantages w.r.t e.g. blind RSA signatures.
>
> Ben: the double-spending protection can follow the same logic of privacy
> pass.
> As Ian says, the ZK proof can go away in BBLS, but the performances will
> still be worse than vanilla PP.
> I had run some numbers on my laptop a while back (please take them with a
> pinch of salt):
>
> blind RSA:
> - signing server: 2.27ms
> - signing client: <0.1ms
> - verification: <1e-5 ms
> This was done with RSA-2048 (sha256) and C's relic
> <https://github.com/relic-toolkit/relic>.
>
> blind BLS:
> - signing server: 0.8ms
> - signing client: 6ms
> - verification: ~4.5 ms
> This was done with BLS12-381 (sha256) and Rust's pairing.
> <https://github.com/zkcrypto/bls12_381>
>
> Clause Blind Schnorr signatures would be faster than BBLS just as well,
> for instance. Just for comparison, on my implementation of PP I have:
>
> PP:
> - signing server: ~4ms
> - signing client: 3ms
> - verification: ~1 ms
> This was done with curve25519 (sha512) and curve25519-dalek.
>
>
> Hope this helps better framing the problem,
> --
> Michele.
>
> --
> Privacy-pass mailing list
> Privacy-pass@ietf.org
> https://www.ietf.org/mailman/listinfo/privacy-pass
>
>
>