Re: [Cfrg] new draft specifying VRFs (verifiable random functions)

Sharon Goldberg <goldbe@cs.bu.edu> Tue, 14 March 2017 22:29 UTC

Return-Path: <sharon.goldbe@gmail.com>
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 523561315D7 for <cfrg@ietfa.amsl.com>; Tue, 14 Mar 2017 15:29:33 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.501
X-Spam-Level:
X-Spam-Status: No, score=-0.501 tagged_above=-999 required=5 tests=[DKIM_SIGNED=0.1, DKIM_VALID=-0.1, FREEMAIL_FORGED_FROMDOMAIN=0.197, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
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 xSkhGJ5qcmFC for <cfrg@ietfa.amsl.com>; Tue, 14 Mar 2017 15:29:32 -0700 (PDT)
Received: from mail-it0-x234.google.com (mail-it0-x234.google.com [IPv6:2607:f8b0:4001:c0b::234]) (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 061241315CE for <cfrg@irtf.org>; Tue, 14 Mar 2017 15:29:28 -0700 (PDT)
Received: by mail-it0-x234.google.com with SMTP id g138so9032528itb.0 for <cfrg@irtf.org>; Tue, 14 Mar 2017 15:29:27 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to:cc; bh=njLC18ORAt0dM7Km0YPiiGdOizkvf6XO5VkgiGLa7+c=; b=SbkRkqSM7LshV0BZjsvgk4DtJcrwZJoYyQ1jgPxsZo47Fg8ZJcmeVA8MO9P+jKj4yt ApmdTt5EIquA4VtFjMyjwbwQqYvi5q17JtNVA4BTU+iheMNiHltIxrmqNUJlgAra7tBT Ln3/G/EGUEzYdMGn4NWqBhgUdB7yK+rqRvIFy8Zi5xYz41zepPf5HwtnlROCH6WaXIMP FQb3E7hooEey5VRo8c9j13papPO9oAf31/ihEEgOiqYqxTRzr56ro4rYap2J10S5hsxB sKmnP9m9OMyhxLlaee5xrP+i8YwdgKXB3cGNpj9SbQBu75c0oTPBmqE7dLDZI1YTNaUM i6HQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:sender:in-reply-to:references:from :date:message-id:subject:to:cc; bh=njLC18ORAt0dM7Km0YPiiGdOizkvf6XO5VkgiGLa7+c=; b=iC2ZsTs1EFXUhTWBJ2c839SlXOJ9fNIG1vj96MM+BVZQ9oXvTZbCGdi+ZgYu9nSoS2 qp/AA86TZ9qoowe+9F0rJ5BaXsqTj8M+RELRkF624aRs9outmrSbgmSAN4XjKabSWJGg yM+HZaEkbgdIYt+FL3nQTa6BbfCsIu67OgCs3q810oLph0wtLAw64QmgNyzFqWrZD9e5 fTP44DN41MvPkfuCxtVhDFpTP1YJwwIXIXsfQxH1BtROVHRflj+uyWTbAHh9FZZRTMFA cWkhMqXHIyHIkyf8s/D9LyzwXw6JEkkqIIMu+0CEnqzvPUZQnpZLPvbFEPXbtrUDVzfb PVaw==
X-Gm-Message-State: AFeK/H21FJMCTJJp9zocsDpCUIeBxSXBXjaM+eCi0FiCMk3cIg9E3bT2U7l00xN6+AGGja9HvjBwz9557gMpkg==
X-Received: by 10.36.84.211 with SMTP id t202mr2301609ita.96.1489530567403; Tue, 14 Mar 2017 15:29:27 -0700 (PDT)
MIME-Version: 1.0
Sender: sharon.goldbe@gmail.com
Received: by 10.107.141.197 with HTTP; Tue, 14 Mar 2017 15:29:26 -0700 (PDT)
In-Reply-To: <CAHOTMVKy3pmZqwoXZ524njsFwXP-y=FLVd+xTCugrbCNy8M8Qw@mail.gmail.com>
References: <CAJHGrrRqchHCvTOBmqgshQ5sxZQ-Moy7ai-Vnoe-R6prJkSRAA@mail.gmail.com> <CAL02cgR1eL=hQu-vQdAbS=-tyGXxatSZD6zJpPpk+w9UoRJS-w@mail.gmail.com> <CAHOTMVKy3pmZqwoXZ524njsFwXP-y=FLVd+xTCugrbCNy8M8Qw@mail.gmail.com>
From: Sharon Goldberg <goldbe@cs.bu.edu>
Date: Tue, 14 Mar 2017 18:29:26 -0400
X-Google-Sender-Auth: C6t6Rrjk7lXJC6pMX0HfXgHCAiQ
Message-ID: <CAJHGrrRs1t7VQyUz2AbWp1_tXb7M=rsBceYaWx_rrjoix0-b4w@mail.gmail.com>
To: Tony Arcieri <bascule@gmail.com>
Cc: Richard Barnes <rlb@ipv.sx>, "cfrg@irtf.org" <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary=001a1139ad8e5a33b0054ab85c6f
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/GL4spJNQ1fpXGmovvK7bGpIzk-o>
Subject: Re: [Cfrg] new draft specifying VRFs (verifiable random functions)
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 14 Mar 2017 22:29:33 -0000

Yes that's true. See the "uniqueness"security property defined in the
draft.

It's also very important that VRF hash outputs look pseudorandom even given
knowledge of the public key. (But not given knowledge of the corresponding
proof or secret key.) That's why the RSA-FDH-VRF hash output is the Hash of
a deterministic RSA signature, not the signature itself. See the security
considerations section of the draft for more details.

Sharon

On Tuesday, March 14, 2017, Tony Arcieri <bascule@gmail.com> wrote:

> On Tue, Mar 14, 2017 at 2:11 PM, Richard Barnes <rlb@ipv.sx
> <javascript:_e(%7B%7D,'cvml','rlb@ipv.sx');>> wrote:
>
>> Thanks for writing this up.  One quick, probably trivial question: How do
>> these VRFs differ from signature schemes?  From the API point of view, they
>> seem very similar, if you view the proof as the signature value.
>>
>
> They are similar, however VRFs are not malleable in the same way as
> signatures (VRFs guarantee a unique mapping of input to random output), and
> specifically designed so the proof can be delivered separately from the
> output (so the output can e.g. be recorded in a Merkle tree for
> timestamping/transparency purposes). The latter prevents low-entropy inputs
> from being preimaged, even if the public key and output are known to the
> attacker (but not the proof).
>
> --
> Tony Arcieri
>


-- 
Sharon Goldberg
Computer Science, Boston University
http://www.cs.bu.edu/~goldbe