[openpgp] Proposal for a separable ring signature scheme compatible with RSA, DSA, and ECDSA keys

Vincent Yu <v@v-yu.com> Thu, 13 March 2014 21:03 UTC

Return-Path: <v@v-yu.com>
X-Original-To: openpgp@ietfa.amsl.com
Delivered-To: openpgp@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com []) by ietfa.amsl.com (Postfix) with ESMTP id 12BE61A075E for <openpgp@ietfa.amsl.com>; Thu, 13 Mar 2014 14:03:27 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.998
X-Spam-Status: No, score=0.998 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, J_CHICKENPOX_42=0.6, MANGLED_TIME=2.3, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=no
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id tYzVvcWm1Cfv for <openpgp@ietfa.amsl.com>; Thu, 13 Mar 2014 14:03:23 -0700 (PDT)
Received: from smtp2.hushmail.com (smtp2.hushmail.com []) by ietfa.amsl.com (Postfix) with ESMTP id 246AD1A09E8 for <openpgp@ietf.org>; Thu, 13 Mar 2014 14:03:22 -0700 (PDT)
Received: from smtp2.hushmail.com (localhost []) by smtp2.hushmail.com (Postfix) with SMTP id 5EC6EA020F for <openpgp@ietf.org>; Thu, 13 Mar 2014 21:03:16 +0000 (UTC)
Received: from smtp.hushmail.com (w5.hushmail.com []) (using TLSv1.2 with cipher DHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp2.hushmail.com (Postfix) with ESMTPS for <openpgp@ietf.org>; Thu, 13 Mar 2014 21:03:16 +0000 (UTC)
Message-ID: <80674820640dbeb5ae81f81c67d87541@smtp.hushmail.com>
Date: Thu, 13 Mar 2014 17:03:13 -0400
From: Vincent Yu <v@v-yu.com>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.3.0
MIME-Version: 1.0
To: openpgp@ietf.org
X-Enigmail-Version: 1.6
OpenPGP: id=d28d7c4078b3742a; url=https://v-yu.com/pubkeys/openpgp.asc
Content-Type: multipart/signed; micalg="pgp-sha512"; protocol="application/pgp-signature"; boundary="WWhgD7eSLjLc8NQ8uhxgD44Du9v1hbCRx"
Archived-At: http://mailarchive.ietf.org/arch/msg/openpgp/PZzHYqcGmYyOl2TDauDJeVEcukM
Subject: [openpgp] Proposal for a separable ring signature scheme compatible with RSA, DSA, and ECDSA keys
X-BeenThere: openpgp@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: "Ongoing discussion of OpenPGP issues." <openpgp.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/openpgp>, <mailto:openpgp-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/openpgp/>
List-Post: <mailto:openpgp@ietf.org>
List-Help: <mailto:openpgp-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/openpgp>, <mailto:openpgp-request@ietf.org?subject=subscribe>
X-List-Received-Date: Thu, 13 Mar 2014 21:03:27 -0000

I propose an extension to RFC 4880 to add support for ring signatures 
based on a separable scheme published by Abe et al. in 2002 [AOS04].

The following additions to RFC 4880 are proposed:

1. A new public-key algorithm, ID 22, for ring signatures.

2. A new signature subpacket, ID 33, which lists the key-specific 
algorithm IDs (see below) and key IDs of the possible signers of a ring 

3. A new registry of ring signature key-specific algorithm IDs with the 
following initial values:

     ID   Algorithm
     --   ---------
     1  - RSA signing
     2  - Schnorr signing
     3  - EC-Schnorr signing

1. Overview

Ring signatures allow a signer to specify a set of possible signers 
without revealing who actually signed the message. The proposed scheme 
is compatible with existing RSA, DSA, and ECDSA keys. Furthermore, it is 
unconditionally signer-ambiguous: even if the private keys of all 
possible signers of a message are revealed, it remains impossible to 
determine which private key was used to sign the message.

The current OpenPGP specification lacks a straightforward way for Alice 
to send Bob an authenticated message that can only be verified by Bob. 
Right now, if such a signature is desired, the best that Alice can do is 
to send Bob a signed-then-encrypted message. Unfortunately, this means 
that Bob can show others the decrypted signature to prove to others that 
Alice signed the message. This ability of Bob to transfer Alice's 
signature to others is often undesirable from Alice's point of view.

Ring signatures provide an easy way for Alice to authenticate a message 
to Bob without concomitantly giving Bob the ability to transfer her 
signature. Alice simply creates a ring signature that specifies Alice 
and Bob as the possible signers of a message. Upon receipt of the 
message and ring signature, Bob is assured that the message is signed by 
Alice, but he cannot prove to others that Alice signed the message 
because Bob could have created the ring signature himself.

The scenario outlined above is typical of two-party email 
communications: when we communicate with someone by email, we often wish 
ensure the authenticity and privacy of our messages. Thus we sign and 
encrypt messages. However, we do not usually intend to grant our 
recipient the ability to authenticate our private messages to others. 
For such communications, I suggest that using ring signatures with 
encryption is an option that better reflects our intentions.

The proposed scheme closely follows Abe et al's scheme [AOS04], with 
small modifications made to better integrate with the current OpenPGP 
specification. Where possible, the notation and variable names in the 
following sections are the same as those in their paper.

Compatibility with DSA and ECDSA keys is achieved by using them as 
Schnorr and EC-Schnorr keys in the ring signature generation algorithm 
in Section 3. For now, I ignore ECDSA keys in following sections because 
I have not yet gone through the process of creating a ring signature 
using an ECDSA key to make sure that I comprehend RFC 6637. However, I 
believe that there are no issues with using ECDSA keys in a way 
analogous to the way that DSA keys are used in the proposed scheme.

2. Ring signature packet format

To create a ring signature, a V4 signature packet MUST be used, and V3 
signature packets MUST NOT be used. The public-key algorithm field MUST 
have the value 22 (0x16), which is a new algorithm type for ring signatures.

A signature subpacket of type 33 (0x21) MUST be present in the hashed 
subpacket data, and it SHOULD be placed ahead of any other hashed 
subpacket. This new subpacket type holds a list of pairs of key-specific 
algorithm ID and key ID of possible signers. The subpacket body is 
formed as the concatenation of the following 9-octet pairs:

     (1 octet algorithm ID, 8 octet key ID)

Each key ID is a possible signer of the ring signature, and the 
prepended algorithm ID specifies how the public key is used in the ring 
signature generation algorithm presented in Section 3. Currently, RSA 
keys MUST have a prepended algorithm ID value of 1 (indicating that they 
are to be used as RSA keys) and DSA keys MUST have a prepended algorithm 
ID value of 2 (indicating that they are to be used as Schnorr keys).

The 9-octet pairs SHOULD be ordered such that their key IDs appear in 
big-endian ascending order.

To illustrate the format of the subpacket body, suppose that we wish to 
create a ring signature with three possible signers, with two DSA key IDs:


And an RSA key ID:


The correct subpacket body here would be (spaces are inserted for 
readability only):

     02 4F0540D577F95F95  01 6B1947C7B5BAA022  02 F2AD85AC1E42B367

Once the hashed subpacket data has been prepared (it would be normal to 
include a signature creation time subpacket), a hash of the message to 
be signed is produced as specified in Section 5.2.4 of RFC 4880.

The algorithm-specific fields of a ring signature packet form a 
concatenated list of MPIs that are generated as prescribed in Section 3.

3. Ring signature generation

The ring signature generation algorithm takes the hashed message and 
prepends a single octet containing the hash algorithm ID (identified in 
Section 9.4 of RFC 4880) of the hash function used (this is done to 
prevent length-extension shenanigans with hash functions based on the 
Merkle–Damgård construction). That is, given the hashed message m, we 

     hm = hash_algorithm_id || m

To generate a ring signature, the actual signer must have available to 
them the public keys of all the possible signers, as well as the private 
key of one of the public keys.

Label the public keys from 1 to n in the same order as in the ring 
signature key-specific IDs and key IDs subpacket. Let k be the label of 
the public key for which the signer has the private key (so k is one of 
the integers from 1 to n).

For each public key, given its label i, use the following variable names 
for the unsigned integers that form the key material (the names are the 
same as those used in Section 5.5.2 of RFC 4880):

     if RSA(i):     (n_i, e_i)
     if Schnorr(i): (p_i, q_i, g_i, y_i)

For the private key (same as Section 5.5.3 of RFC 4880):

     if RSA(k):     (d_k, p_k, q_k, u_k)
     if Schnorr(k): (x_k)

Define the functions Random(n), MPI(n), and Hash() as follows.

Random(n) returns a uniformly random integer from 0 to n-1 inclusive.

MPI(n) returns a string of octets that is the unique MPI representation 
of the unsigned integer n, as defined in Section 3.2 of RFC 4880.

Hash() is the same hash function as that used to hash the message.

Now evaluate the following to generate the ring signature.

Initialize the ring signature:

     if RSA(k):
         r   = Random(n_k)
         a_k = r
     if Schnorr(k):
         r   = Random(q_k)
         a_k = g_k**r mod p_k

     c_(k+1) = Hash(hm || MPI(a_k))

For i = k+1, ..., n, 1, ..., k-1:

     if RSA(i):
         s_i = Random(n_i)
         a_i = (c_i + s_i**e_i) mod n_i
     if Schnorr(i):
         s_i = Random(q_i)
         a_i = (g_i**s_i * y_i**c_i) mod p_i

     c_(i+1) = Hash(hm || MPI(a_i))

Close the ring signature:

     if RSA(k):
         s_k = (r - c_k)**d_k mod n_k
     if Schnorr(k):
         s_k = (r - x_k*c_k) mod q_k

The ring signature output is a concatenated list of n+1 MPIs:

     MPI(c_1) || MPI(s_1) || MPI(s_2) || ... || MPI(s_n)

Note that in the degenerate case where n=1, the middle loop is skipped 
and the resulting signature is simply a randomized RSA signature or a 
standard Schnorr signature.

4. Ring signature verification

Given a message and a ring signature packet, the signature can be 
verified by following the same steps as in the signature generation to 
hash the message, then prepending the hash algorithm ID to get hm, then 
finally evaluating the following loop.

For i = 1, ..., n:

     if RSA(i):
         a_i = (c_i + s_i**e_i) mod n_i
     if Schnorr(i):
         a_i = (g_i**s_i * y_i**c_i) mod p_i

     c_(i+1) = Hash(hm || MPI(a_i))

Accept the signature if and only if the computed c_1 (i.e., c_(n+1)) is 
identical to the input c_1.

5. Notes for implementers

As outlined in the overview in Section 1, an intended use of ring 
signatures is to provide non-transferable authenticity in two-party 
communications. Ring signatures can be used for other purposes (see 
[RST06]). This proposal does not give a strict prescription for the 
usage of ring signatures, and decisions regarding the creation and 
interpretation of ring signatures is left to the implementation.

It is common for an OpenPGP key bundle to contain multiple keys that are 
capable of producing signatures. For instance, this is the case when the 
primary certification key and a subkey both have their signing flags set 
(see Section of RFC 4880). When a user wishes to create a ring 
signature that includes a key ID in a bundle that contains other keys 
capable of signing, it would make sense to include all signing-capable 
keys in the ring signature. This is illustrated in Appendix A.

6. Summary

In this message, I proposed an extension to RFC 4880 that adds support 
for ring signatures and provided specifications for the packet format 
and signature generation algorithm.

I would like to hear your comments on this proposal.


Selected references

For readers unfamiliar with ring signatures, I recommend first reading 
[RST06], then Sections 1–3 of [BSS02], then finally [AOS04].

M. Abe, M. Ohkubo, and K. Suzuki (2004).
1-out-of-n signatures from a variety of keys.
This is a newer version of an earlier conference paper that was 
published at ASIACRYPT 2002.

E. Bresson, J. Stern, and M. Szydlo (2002).
Threshold ring signatures and applications to ad-hoc groups.
This is the full version of an extended abstract that was published at 
CRYPTO 2002.

R. L. Rivest, A. Shamir, and Y. Tauman (2006).
How to leak a secret: Theory and applications of ring signatures.
This is an updated version of an earlier conference paper that was 
published at ASIACRYPT 2001.

Appendix A. Example of a ring signature following the current proposal

Hash: SHA256

This message is used to demonstrate a ring signature.


To demonstrate the proposed specification and to eliminate ambiguity, I 
have prepared the cleartext ring signature above. The signed message 
complies with the cleartext signature framework in Section 7 of RFC 
4880. The base64-encoded data contains a ring signature packet that 
follows the current proposal. Three key IDs are identified as the 
possible signers:

     4F0540D577F95F95 - Werner's DSA signing subkey.
     6B1947C7B5BAA022 - RSA signing key that I created for this occasion.
     F2AD85AC1E42B367 - Werner's DSA primary key.

Werner's public keys are available at:


The private key for 6B1947C7B5BAA022 is provided in Appendix B. This 
private key was used to create the ring signature.

The value of r used in the ring signature generation algorithm can be 
recovered from the signature, but let me provide it here anyway for your 
convenience in case you wish to reproduce an exact copy of the ring 

     r = 0x5202a86b534ac6e7680c3db32f1b409a8529d1e8d51baf648e9f0d

The following is an overview of the signature structure in hex:

C2 C045
New packet format holding a signature packet with data length 261.

04 01 16 08
V4 signature of canonical text document using a ring signature with SHA256.

Length of hashed subpacket data: 35 octets.

1C 21 02 4F0540D577F95F95 01 6B1947C7B5BAA022 02 F2AD85AC1E42B367
28-octet hashed subpacket containing the ring signature key-specific 
algorithm IDs and key IDs.

05 02 52D6DB07
5-octet hashed subpacket containing the signature creation time.

Length of unhashed subpacket data: 0 octets.

2-octet field containing the leftmost 16 bits of the hashed message.

The remaining packet data is a concatenated list of four MPIs that form 
the ring signature, generated as prescribed in Section 3.

Appendix B. Private key for 6B1947C7B5BAA022

The following private key was used in the ring signature generation 
algorithm to create the ring signature displayed in Appendix A.

pub  1024R/6B1947C7B5BAA022  created: 2014-01-15  expires: never usage: SC
      Key fingerprint = 2AA7 1619 35F1 2D1D 2BA6  78B2 6B19 47C7 B5BA A022
uid                          This key is for testing only
Version: GnuPG v2.0.20 (GNU/Linux)