[Cfrg] A note on PRF

Watson Ladd <watsonbladd@gmail.com> Sun, 12 January 2014 14:49 UTC

Return-Path: <watsonbladd@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com []) by ietfa.amsl.com (Postfix) with ESMTP id 0E67E1ADED7 for <cfrg@ietfa.amsl.com>; Sun, 12 Jan 2014 06:49:28 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id kvyr-1J1Y61v for <cfrg@ietfa.amsl.com>; Sun, 12 Jan 2014 06:49:26 -0800 (PST)
Received: from mail-wg0-x235.google.com (mail-wg0-x235.google.com [IPv6:2a00:1450:400c:c00::235]) by ietfa.amsl.com (Postfix) with ESMTP id 940191AD8E1 for <cfrg@irtf.org>; Sun, 12 Jan 2014 06:49:26 -0800 (PST)
Received: by mail-wg0-f53.google.com with SMTP id k14so5639034wgh.8 for <cfrg@irtf.org>; Sun, 12 Jan 2014 06:49:15 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:subject:from:to:content-type; bh=attkGIgrTyT8n28IujIx4WoIjwlxDr9SYsdKRwfKO5Y=; b=EqAQx0nTikoe7Bsw/kO8LT5NUPv/SScXd7YiGX5Guw2C2zQlHrTJXQCqkzhqCOdHxV 5jKNYxzAxQlESE61aZINI/KOU2u+7ugydt/e9xnKdVupR0KtK1X8iJBWVHQjfztJGT3y w6IdUdjBCgsycBwIID1Ahxl50vesxNfnW6JscLW0tFJSOhWReoP9gs28OY7hCwNnoLTR SEGzMc+OAmLa4Jw/CEsfAGHYbtzd1M4PAlR58SLgslhWSmrkQS8XtIiD2eJOspxCKrK/ pISCrMroqxkOpUK1SU/MFYdjNkN1xs0FJKiz2LM2K8rdoFq0tdkvPbPlSoTA/moun3Y0 tl4Q==
MIME-Version: 1.0
X-Received: by with SMTP id dl2mr11492438wib.17.1389538155489; Sun, 12 Jan 2014 06:49:15 -0800 (PST)
Received: by with HTTP; Sun, 12 Jan 2014 06:49:15 -0800 (PST)
Date: Sun, 12 Jan 2014 06:49:15 -0800
Message-ID: <CACsn0cmnhpFm3izZZ3L4QOD2fwwo8wH1UDc7dF2EQfhTmDvk=A@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: "cfrg@irtf.org" <cfrg@irtf.org>
Content-Type: text/plain; charset="UTF-8"
Subject: [Cfrg] A note on PRF
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Sun, 12 Jan 2014 14:49:28 -0000

Let H(k, m) be a PRF with output length n and input all strings. Then
I claim that
H(H(k, m), "0"), H(H(k,m),"1") is a PRF of output length 2n.

A proof of this, together with evaluating the loss of security
resulting from such composite,
is left as an exercise for the reader.

In other words, don't worry about the length of the hash function we
adopt for our new Schnorr style signature scheme: it can be extended
by classical techniques easily.

Watson Ladd