Re: [Cfrg] Multi-recipient public key authenticated encryption

Neil Madden <> Mon, 18 May 2020 10:57 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id C6F9B3A0AC5 for <>; Mon, 18 May 2020 03:57:20 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -0.197
X-Spam-Status: No, score=-0.197 tagged_above=-999 required=5 tests=[DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id nPn6RDxJp3mu for <>; Mon, 18 May 2020 03:57:18 -0700 (PDT)
Received: from ( [IPv6:2a00:1450:4864:20::42e]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 92F0E3A0AC4 for <>; Mon, 18 May 2020 03:57:18 -0700 (PDT)
Received: by with SMTP id k13so9204849wrx.3 for <>; Mon, 18 May 2020 03:57:18 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=from:message-id:mime-version:subject:date:in-reply-to:cc:to :references; bh=uJwq6e5XTHuNeIiZw65UEZf9t7I1hDr+5MTx/K0wW7I=; b=NA++YcCqsgnEuloX3mLJAro8kA6JUqu6vp5KUrOWnAm1ptDBMf9o9Kqq8tZ8z8pRoW VViceb0ekqYiz83rgyOCKGO+dh2Np4qxkCZQSYMPVIn7XsFnHn5Q8Gi1JnKul/xl5fJX WXTuoqrSBDR6kJz+XBEo5KGHLrsqB0eHmCkhyDu2nbEqWEDdFdmX6goHyoB0542u5+pV DHLFIodZKlDdi+wmPgUchkXWlTWpG/YGFkMUqwbtyE9ebKx5LQWmRRTYNBQtg59mbLaV lmidV3rTuMRetaLYF96Jlhy6s3W5LFq19ryngSJDY5NJZfqE7ZUr99HTAU0byRlvIdTp dPJA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:from:message-id:mime-version:subject:date :in-reply-to:cc:to:references; bh=uJwq6e5XTHuNeIiZw65UEZf9t7I1hDr+5MTx/K0wW7I=; b=fcuhWXN3clXONq8xc9RjJ7rgFfMkcOJT3nBc+NIfdEKs4d/2iOiPVnrm0K1cS/WP9n rkfxY2FvKMuQjDlY6huosN5u4FpU8XkqqA+rDaX1M7K8jaLLqfaxtVCB9iss5y7FpV0D QqYjI9vaINCEZ5BQFoc6pyFe7LGVorhCTkXdfRUBnwWp9nFKhtyIC0NGnSWDIwESKgFj xroleGWYaQCpqPV9D3FxauvENGGcKsAoX60nadMq9rrARPYaS/9F0HMqMya5W8Wn9kV0 33APHQ6pWm5NNCQXFqXnoDrO4SxLlwJ9i7G7TszpjpFYusAL6GUIhRsanhBU3hII+UpC AFIw==
X-Gm-Message-State: AOAM5338NF+ovZH7jQFLm3kH9UiHRkiVZWQi2QUGlNEJ2yUpQnrBbRTw jV6lIcYPzuEhbr/+rc5WcW2AYVg1
X-Google-Smtp-Source: ABdhPJyodLOIn9bhSt/0DS8BZ6RwuPHy5+/cRQ1C87uw2aC+9t3fTteujpwmj7a8wxQQircP2WIEQw==
X-Received: by 2002:a5d:4ccd:: with SMTP id c13mr19642704wrt.415.1589799437070; Mon, 18 May 2020 03:57:17 -0700 (PDT)
Received: from [] ( []) by with ESMTPSA id h74sm16911945wrh.76.2020. (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Mon, 18 May 2020 03:57:16 -0700 (PDT)
From: Neil Madden <>
Message-Id: <>
Content-Type: multipart/alternative; boundary="Apple-Mail=_648588B1-6E01-4269-BE7E-BAE44A06B442"
Mime-Version: 1.0 (Mac OS X Mail 13.4 \(3608.\))
Date: Mon, 18 May 2020 11:57:14 +0100
In-Reply-To: <>
Cc: Mihir Bellare <>, CFRG <>
To: Phillip Hallam-Baker <>
References: <> <> <>
X-Mailer: Apple Mail (2.3608.
Archived-At: <>
Subject: Re: [Cfrg] Multi-recipient public key authenticated encryption
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Mon, 18 May 2020 10:57:21 -0000

Thanks for the reply, some comments below:

> On 12 May 2020, at 19:06, Phillip Hallam-Baker <> wrote:
> It is an interesting question. One approach is to look at it from a systems angle.
> Alice is going to send a message to Bob, Carol and herself. She wants each to be able to authenticate the message but without being able to prove Alice sent it (so can't just sign).
> Let us begin by assuming we are using ECDH. This means that we are going to need a keywrap for each recipient under the agreed key. We can generate a unique input to a MAC at the same time.
> So to put the pieces together:
> Alice generates an ephemeral key {g^e, e} and an encryption session key k.
> She encrypts and authenticates the message resulting in a ciphertext we can ignore at this point and an authentication tag t.
> For each recipient, Alice calculates 
> IKM_p = (P)^e where P is the recipient public key.
> kw_p = WRAP (k, HKDF (IKM, "keywrap"))
> Auth_p = HMAC(t, HKDF (IKM, "tagmac"))
> So each recipient has an independent verification tag that is derived from the same key exchange used to encrypt the data for their use.

In my case WRAP is AES-KW of RFC 3394, which is already an authenticated encryption scheme [*] so I can just wrap (k, t) together for each recipient. I did consider this kind of approach, but if you have many recipients then this adds quite a lot of overhead. E.g., assuming HMAC-SHA256 with a 32-byte Auth_p tag then if you have a thousand recipients then there is an overhead of 32kB. By contrast, feeding the message MAC tag (or a hash of the message) into the KDF adds no additional per-recipient overhead.

This makes me realise that there is yet another approach that could be used: swap AES-KW for SIV-AES and then feed the message MAC tag as additional authenticated data. (Again, assuming the MAC is compactly committing/collision-resistant).

[*] Albeit with a ciphertext expansion of just 64 bits.

> I am sure this can't be a novel construction simply because it is so heavily constrained. If we are going to use a MAC to authenticate data, we must encrypt to data that is only shared bilaterally. Which means we have to look at the output of the El-Gamal key agreement. Since we have a KDF in there already, the approach falls out naturally.

I believe this is basically what Saltpack does ( <>).

— Neil