Skip to main content

RSA Blind Signatures

The information below is for an old version of the document.
Document Type
This is an older version of an Internet-Draft that was ultimately published as RFC 9474.
Authors Frank Denis , Frederic Jacobs , Christopher A. Wood
Last updated 2022-08-06
Replaces draft-wood-cfrg-rsa-blind-signatures
RFC stream Internet Research Task Force (IRTF)
IETF conflict review conflict-review-irtf-cfrg-rsa-blind-signatures, conflict-review-irtf-cfrg-rsa-blind-signatures, conflict-review-irtf-cfrg-rsa-blind-signatures, conflict-review-irtf-cfrg-rsa-blind-signatures, conflict-review-irtf-cfrg-rsa-blind-signatures, conflict-review-irtf-cfrg-rsa-blind-signatures
Additional resources Mailing list discussion
Stream IRTF state Active RG Document
Consensus boilerplate Unknown
Document shepherd (None)
IESG IESG state Became RFC 9474 (Informational)
Telechat date (None)
Responsible AD (None)
Send notices to (None)
Network Working Group                                           F. Denis
Internet-Draft                                               Fastly Inc.
Intended status: Informational                                 F. Jacobs
Expires: 6 February 2023                                      Apple Inc.
                                                              C. A. Wood
                                                           5 August 2022

                          RSA Blind Signatures


   This document specifies the RSA-based blind signature protocol with
   appendix (RSA-BSSA).  RSA blind signatures were first introduced by
   Chaum for untraceable payments [Chaum83].  It extends RSA-PSS
   encoding specified in [RFC8017] to enable blind signature support.

Discussion Venues

   This note is to be removed before publishing as an RFC.

   Source for this draft and an issue tracker can be found at

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on 6 February 2023.

Copyright Notice

   Copyright (c) 2022 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

Denis, et al.            Expires 6 February 2023                [Page 1]
Internet-Draft            RSA Blind Signatures               August 2022

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents (
   license-info) in effect on the date of publication of this document.
   Please review these documents carefully, as they describe your rights
   and restrictions with respect to this document.  Code Components
   extracted from this document must include Revised BSD License text as
   described in Section 4.e of the Trust Legal Provisions and are
   provided without warranty as described in the Revised BSD License.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   3
   2.  Requirements Notation . . . . . . . . . . . . . . . . . . . .   3
   3.  Notation  . . . . . . . . . . . . . . . . . . . . . . . . . .   3
   4.  Blind Signature Protocol Overview . . . . . . . . . . . . . .   4
   5.  RSABSSA Signature Instantiation . . . . . . . . . . . . . . .   4
     5.1.  Signature Generation  . . . . . . . . . . . . . . . . . .   5
       5.1.1.  Blind . . . . . . . . . . . . . . . . . . . . . . . .   5
       5.1.2.  BlindSign . . . . . . . . . . . . . . . . . . . . . .   6
       5.1.3.  Finalize  . . . . . . . . . . . . . . . . . . . . . .   7
     5.2.  External Application Interface  . . . . . . . . . . . . .   8
       5.2.1.  Salted Blind  . . . . . . . . . . . . . . . . . . . .   9
       5.2.2.  Salted Finalize . . . . . . . . . . . . . . . . . . .   9
       5.2.3.  Salted Verify . . . . . . . . . . . . . . . . . . . .  10
     5.3.  Encoding Options  . . . . . . . . . . . . . . . . . . . .  11
   6.  Public Key Certification  . . . . . . . . . . . . . . . . . .  12
   7.  Implementation Considerations . . . . . . . . . . . . . . . .  12
     7.1.  Errors  . . . . . . . . . . . . . . . . . . . . . . . . .  12
     7.2.  API Considerations  . . . . . . . . . . . . . . . . . . .  12
   8.  Security Considerations . . . . . . . . . . . . . . . . . . .  12
     8.1.  Timing Side Channels  . . . . . . . . . . . . . . . . . .  13
     8.2.  Message Robustness  . . . . . . . . . . . . . . . . . . .  13
     8.3.  Message Entropy . . . . . . . . . . . . . . . . . . . . .  14
     8.4.  Randomized and Deterministic Signatures . . . . . . . . .  14
     8.5.  Key Substitution Attacks  . . . . . . . . . . . . . . . .  15
     8.6.  Alternative RSA Encoding Functions  . . . . . . . . . . .  15
     8.7.  Alternative Blind Signature Protocols . . . . . . . . . .  15
     8.8.  Post-Quantum Readiness  . . . . . . . . . . . . . . . . .  17
   9.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  17
   10. References  . . . . . . . . . . . . . . . . . . . . . . . . .  17
     10.1.  Normative References . . . . . . . . . . . . . . . . . .  17
     10.2.  Informative References . . . . . . . . . . . . . . . . .  18
   Appendix A.  Test Vectors . . . . . . . . . . . . . . . . . . . .  21
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  25

Denis, et al.            Expires 6 February 2023                [Page 2]
Internet-Draft            RSA Blind Signatures               August 2022

1.  Introduction

   Originally introduced in the context of digital cash systems by Chaum
   for untraceable payments [Chaum83], RSA blind signatures turned out
   to have a wide range of applications ranging from electric voting
   schemes to authentication mechanisms.

   Recently, interest in blind signatures has grown to address
   operational shortcomings from VOPRFs such as [I-D.irtf-cfrg-voprf].
   Specifically, VOPRF evaluation requires access to the private key,
   and is therefore required for both issuance and redemption of tokens
   in anonymous authentication protocols such as Privacy Pass
   [I-D.davidson-pp-protocol].  This limitation complicates deployments
   where it is not desirable to distribute secret keys to entities
   performing token verification.  Additionally, if the private key is
   kept in a Hardware Security Module, the number of operations on the
   key is doubled compared to a scheme where the private key is only
   required for issuance of the tokens.

   In contrast, cryptographic signatures provide a primitive that is
   publicly verifiable and does not require access to the private key
   for verification.  Moreover, [JKK14] shows that one can realize a
   VOPRF in the Random Oracle Model by hashing a (deterministic) blind
   signature-message pair.

   This document specifies a protocol for the RSA Blind Signature Scheme
   with Appendix (RSABSSA).  In order to facilitate deployment, we
   define it in such a way that the resulting (unblinded) signature can
   be verified with a standard RSA-PSS library.

2.  Requirements Notation

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "OPTIONAL" in this document are to be interpreted as described in
   BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all
   capitals, as shown here.

3.  Notation

   The following terms are used throughout this document to describe the
   protocol operations in this document:

   *  bytes_to_int and int_to_bytes: Convert a byte string to and from a
      non-negative integer. bytes_to_int and int_to_bytes are
      implemented as OS2IP and I2OSP as described in [RFC8017],
      respectively.  Note that these functions operate on byte strings
      in big-endian byte order.

Denis, et al.            Expires 6 February 2023                [Page 3]
Internet-Draft            RSA Blind Signatures               August 2022

   *  random_integer_uniform(M, N): Generate a random, uniformly
      distributed integer R such that M <= R < N.

   *  inverse_mod(x, n): Compute the multiplicative inverse of x mod n.
      This function fails if x and n are not co-prime.

   *  len(s): The length of a byte string, in octets.

   *  random(n): Generate n random octets using a cryptographically-
      secure pseudorandom number generator.

4.  Blind Signature Protocol Overview

   In this section, we sketch the blind signature protocol wherein a
   client and server interact to compute sig = Sign(skS, msg), where msg
   is the private message to be signed, and skS is the server's private
   key.  In this protocol, the server learns nothing of msg, whereas the
   client learns sig and nothing of skS.

   The core issuance protocol runs as follows:

      Client(pkS, msg)                      Server(skS, pkS)
     blinded_msg, inv = Blind(pkS, msg)


                    blind_sig = BlindSign(skS, blinded_msg)


     sig = Finalize(pkS, msg, blind_sig, inv)

   Upon completion, correctness requires that clients can verify
   signature sig over private input message msg using the server public
   key pkS by invoking the RSASSA-PSS-VERIFY routine defined in
   [RFC3447].  The finalization function performs that check before
   returning the signature.

5.  RSABSSA Signature Instantiation

   Section 8.1 of [RFC8017] defines RSASSA-PSS RSAE, which is a
   signature algorithm using RSASSA-PSS [RFC8017] with mask generation
   function 1.  In this section, we define RSABSSA, a blinded variant of
   this algorithm.

Denis, et al.            Expires 6 February 2023                [Page 4]
Internet-Draft            RSA Blind Signatures               August 2022

5.1.  Signature Generation

   As outlined in Section 4, signature generation involves three
   subroutines: Blind, BlindSign, and Finalize.  The output from
   Finalize is a signature over the input to Blind.  A specification of
   these subroutines is below.

5.1.1.  Blind

   rsabssa_blind encodes an input message and blinds it with the
   server's public key.  It outputs the blinded message to be sent to
   the server and the corresponding inverse, both encoded as octet
   strings.  RSAVP1 and EMSA-PSS-ENCODE are as defined in [RFC3447].

Denis, et al.            Expires 6 February 2023                [Page 5]
Internet-Draft            RSA Blind Signatures               August 2022

   rsabssa_blind(pkS, msg)

   - kLen, the length in octets of the RSA modulus n
   - kBits, the length in bits of the RSA modulus n
   - HF, the hash function used to hash the message
   - MGF, the mask generation function

   - pkS, server public key (n, e)
   - msg, message to be signed, an octet string

   - blinded_msg, an octet string of length kLen
   - inv, an octet string of length kLen

   - "message too long": Raised when the input message is too long.
   - "encoding error": Raised when the input message fails encoding.
   - "invalid blind": Raised when the inverse of r cannot be found.

   1. encoded_msg = EMSA-PSS-ENCODE(msg, kBits - 1)
      with MGF and HF as defined in the parameters
   2. If EMSA-PSS-ENCODE raises an error, raise the error and stop
   3. m = bytes_to_int(encoded_msg)
   4. r = random_integer_uniform(1, n)
   5. r_inv = inverse_mod(r, n)
   6. If inverse_mod fails, raise an "invalid blind" error
      and stop
   7. x = RSAVP1(pkS, r)
   8. z = m * x mod n
   9. blinded_msg = int_to_bytes(z, kLen)
   10. inv = int_to_bytes(r_inv, kLen)
   11. output blinded_msg, inv

   The blinding factor r must be randomly chosen from a uniform
   distribution.  This is typically done via rejection sampling.

5.1.2.  BlindSign

   rsabssa_blind_sign performs the RSA private key operation on the
   client's blinded message input and returns the output encoded as an
   octet string.  RSASP1 is as defined in [RFC3447].

Denis, et al.            Expires 6 February 2023                [Page 6]
Internet-Draft            RSA Blind Signatures               August 2022

   rsabssa_blind_sign(skS, blinded_msg)

   - kLen, the length in octets of the RSA modulus n

   - skS, server private key
   - blinded_msg, encoded and blinded message to be signed, an
     octet string

   - blind_sig, an octet string of length kLen

   - "unexpected input size": Raised when a byte string input doesn't
     have the expected length.
   - "invalid message length": Raised when the message representative
     to sign is not an integer between 0 and n - 1.

   1. If len(blinded_msg) != kLen, raise "unexpected input size"
      and stop
   2. m = bytes_to_int(blinded_msg)
   3. If m >= n, raise "invalid message length" and stop
   4. s = RSASP1(skS, m)
   5. blind_sig = int_to_bytes(s, kLen)
   6. output blind_sig

5.1.3.  Finalize

   rsabssa_finalize validates the server's response, unblinds the
   message to produce a signature, verifies it for correctness, and
   outputs the signature upon success.  Note that this function will
   internally hash the input message as is done in rsabssa_blind.

Denis, et al.            Expires 6 February 2023                [Page 7]
Internet-Draft            RSA Blind Signatures               August 2022

   rsabssa_finalize(pkS, msg, blind_sig, inv)

   - kLen, the length in octets of the RSA modulus n

   - pkS, server public key (n, e)
   - msg, message to be signed, an octet string
   - blind_sig, signed and blinded element, an octet string of
     length kLen
   - inv, inverse of the blind, an octet string of length kLen

   - sig, an octet string of length kLen

   - "invalid signature": Raised when the signature is invalid
   - "unexpected input size": Raised when a byte string input doesn't
     have the expected length.

   1. If len(blind_sig) != kLen, raise "unexpected input size" and stop
   2. If len(inv) != kLen, raise "unexpected input size" and stop
   3. z = bytes_to_int(blind_sig)
   4. r_inv = bytes_to_int(inv)
   5. s = z * r_inv mod n
   6. sig = int_to_bytes(s, kLen)
   7. result = RSASSA-PSS-VERIFY(pkS, msg, sig)
   8. If result = "valid signature", output sig, else
      raise "invalid signature" and stop

5.2.  External Application Interface

   This section presents an application interface for blinding,
   finalizing, and verifying messages that is build on the internal
   functions described in Section 5.1.  This interface injects
   additional entropy into application messages by choosing a random
   salt of length 32 bytes, prepending the salt to the input message,
   and then invoking the internal functions in Section 5.1.  Note that
   this only changes what is passed to rsabssa_blind and
   rsabssa_finalize, as the application message is not provided as input
   to rsabssa_blindsign.

   Applications that provide high-entropy input messages can expose the
   internal rsabssa_blind and rsabssa_finalize directly, as the
   additional message randomization does not offer security advantages.
   See [Lys22], Section 7.2, and Section 8.3 for more information.

Denis, et al.            Expires 6 February 2023                [Page 8]
Internet-Draft            RSA Blind Signatures               August 2022

5.2.1.  Salted Blind

   rsabssa_salted_blind invokes rsabssa_blind with a salted input
   message and outputs the blinded message to be sent to the server and
   the corresponding inverse, both encoded as octet strings, as well as
   the fresh message salt, which is 32 random bytes.

   rsabssa_salted_blind(pkS, msg)

   - kLen, the length in octets of the RSA modulus n
   - kBits, the length in bits of the RSA modulus n
   - HF, the hash function used to hash the message
   - MGF, the mask generation function

   - pkS, server public key (n, e)
   - msg, message to be signed, an octet string

   - blinded_msg, an octet string of length kLen
   - inv, an octet string of length kLen
   - msg_salt, an octet string of length 32 bytes

   - "message too long": Raised when the input message is too long.
   - "encoding error": Raised when the input message fails encoding.
   - "invalid blind": Raised when the inverse of r cannot be found.

   1. msg_salt = random(32)
   2. salted_msg = msg_salt || msg
   3. blinded_msg, inv = blind(pkS, salted_msg)
   4. output msg_salt, blinded_msg, inv

5.2.2.  Salted Finalize

   rsabssa_salted_finalize invokes rsabssa_finalize directly with the
   salted message and outputs the result.

Denis, et al.            Expires 6 February 2023                [Page 9]
Internet-Draft            RSA Blind Signatures               August 2022

   rsabssa_salted_finalize(pkS, msg, blind_sig, inv)

   - kLen, the length in octets of the RSA modulus n

   - pkS, server public key (n, e)
   - msg, message to be signed, an octet string
   - msg_salt, the 32 octets random salt used to salt the message
   - blind_sig, signed and blinded element, an octet string of
     length kLen
   - inv, inverse of the blind, an octet string of length kLen

   - sig, an octet string of length kLen

   - "invalid signature": Raised when the signature is invalid
   - "unexpected input size": Raised when a byte string input doesn't
     have the expected length.

   1. salted_msg = msg_salt || msg
   2. output rsabssa_finalize(pkS, salted_msg, blind_sig, inv)

5.2.3.  Salted Verify

   rsabssa_salted_verify validates the resulting unblinded signature
   computed over a salted message.  It invokes RSASSA-PSS-VERIFY
   directly by augmenting the input message with the message salt.

Denis, et al.            Expires 6 February 2023               [Page 10]
Internet-Draft            RSA Blind Signatures               August 2022

   rsabssa_salted_verify(pkS, msg, msg_salt, sig)

   - kLen, the length in octets of the RSA modulus n

   - pkS, server public key (n, e)
   - msg, message to be signed, an octet string
   - msg_salt, the 32 octets random salt used to salt the message
   - sig, signature of the salted_msg

   - "valid signature" if the signature is valid

   - "invalid signature": Raised when the signature is invalid

   1. salted_msg = msg_salt || msg
   2. result = RSASSA-PSS-VERIFY(pkS, salted_msg, sig)
   3. If result = "valid signature", output "valid signature", else
     raise "invalid signature" and stop

5.3.  Encoding Options

   The RSASSA-PSS parameters, defined as in [RFC8017], Section 9.1.1,
   are as follows:

   *  Hash: hash function

   *  MGF: mask generation function

   *  sLen: intended length in octets of the salt

   Implementations that expose the interface in Section 5.2 are
   RECOMMENDED to support SHA-384 as Hash and MGF functions and sLen =
   48, as described in [RFC8230], Section 2.

   Implementations that expose the internal interface in Section 5.1 are
   also RECOMMENDED to support SHA-384 as Hash and MGF functions and
   sLen = 0.  Note that setting sLen = 0 has the result of making the
   signature deterministic.

   The blinded functions in Section 5.1 are orthogonal to the choice of
   these encoding options.

Denis, et al.            Expires 6 February 2023               [Page 11]
Internet-Draft            RSA Blind Signatures               August 2022

6.  Public Key Certification

   If the server public key is carried in an X.509 certificate, it MUST
   use the RSASSA-PSS OID [RFC5756].  It MUST NOT use the rsaEncryption
   OID [RFC5280].

7.  Implementation Considerations

   This section documents considerations for interfaces to
   implementations of the protocol in this document.  This includes
   error handling and API considerations.

7.1.  Errors

   The high-level functions specified in Section 5.1 are all fallible.
   The explicit errors generated throughout this specification, along
   with the conditions that lead to each error, are listed in the
   definitions for rsabssa_blind, rsabssa_blind_sign, and
   rsabssa_finalize.  These errors are meant as a guide for
   implementors.  They are not an exhaustive list of all the errors an
   implementation might emit.  For example, implementations might run
   out of memory.

7.2.  API Considerations

   It is NOT RECOMMENDED that APIs allow clients to specify RSA-PSS
   parameters directly, e.g., to set the PSS salt value or its length.
   Instead, it is RECOMMENDED that implementations generate the PSS salt
   using the same source of randomness used to produce the blinding

   If implementations need support for randommized and deterministic
   signatures, they should offer separate abstractions for each.
   Allowing callers to control the PSS salt value or length may have
   security consequences.  See Section 8.4 for more information about

8.  Security Considerations

   Bellare et al.  [BNPS03] proved the following properties of Chaum's
   original blind signature protocol based on RSA-FDH:

   *  One-more-forgery polynomial security.  This means the adversary,
      interacting with the server (signer) as a client, cannot output
      n+1 valid message and signature tuples after only interacting with
      the server n times, for some n which is polynomial in the
      protocol's security parameter.

Denis, et al.            Expires 6 February 2023               [Page 12]
Internet-Draft            RSA Blind Signatures               August 2022

   *  Concurrent polynomial security.  This means that servers can
      engage in polynomially many invocations of the protocol without
      compromising security.

   Both results rely upon the RSA Known Target Inversion Problem being

   The design in this document differs from the analysis in [BNPS03]
   only in message encoding, i.e., using PSS instead of FDH.  Note,
   importantly, that an empty salt effectively reduces PSS to FDH, so
   the same results apply.

8.1.  Timing Side Channels

   rsabssa_blind_sign is functionally a remote procedure call for
   applying the RSA private key operation.  As such, side channel
   resistance is paramount to protect the private key from exposure
   [RemoteTimingAttacks].  Implementations MUST implement RSA blinding
   as a side channel attack mitigation.  One mechanism is described in
   Section 10 of [TimingAttacks].  Failure to do so may lead to side
   channel attacks that leak the private signing key.

8.2.  Message Robustness

   An essential property of blind signature protocols is that the signer
   learns nothing of the message being signed.  In some circumstances,
   this may raise concerns of arbitrary signing oracles.  Applications
   using blind signature protocols should take precautions to ensure
   that such oracles do not cause cross-protocol attacks.  This can be
   done, for example, by keeping blind signature keys distinct from
   signature keys used for other protocols, such as TLS.

   An alternative solution to this problem of message blindness is to
   give signers proof that the message being signed is well-structured.
   Depending on the application, zero knowledge proofs could be useful
   for this purpose.  Defining such a proof is out of scope for this

   Verifiers should check that, in addition to signature validity, the
   unblinded message is well-structured for the relevant application.
   For example, if an application of this protocol requires messages to
   be structures of a particular form, then verifiers should check that
   unblinded messages adhere to this form.

Denis, et al.            Expires 6 February 2023               [Page 13]
Internet-Draft            RSA Blind Signatures               August 2022

8.3.  Message Entropy

   As discussed in [Lys22], the choice of blinding mechanism has
   security implications on the blindness properties of the blind RSA
   protocol.  In particular, a malicious signer can construct an invalid
   public and use it to learn information about low-entropy with input
   messages.  Note that some invalid public keys may not yield valid
   signatures when run with the protocol, e.g., because the signature
   fails to verify.  However, if an attacker can coerce the client to
   use these invalid public keys with low-entropy inputs, they can learn
   information about the client inputs before the protocol completes.

   Based on this fact, using the internal functions in Section 5.1 is
   possibly unsafe, unless one of the following conditions are met:

   1.  The client has proof that the signer's public key is honestly
       generated.  [GRSB19] presents some (non-interactive) honest-
       verifier zero-knoweldge proofs of various statements about the
       public key.

   2.  The client input message has high entropy.

   The interface in Section 5.2 is designed to explicitly inject fresh
   entropy alongside each message to satisfy condition (2).  As such,
   this interface is safe for all application use cases.

   Note that this interface effectively means that the resulting
   signature is always randomized.  As such, this interface is not
   suitable for applications that require deterministic signatures.  See
   Section 8.4 for more details.

8.4.  Randomized and Deterministic Signatures

   When sLen > 0, the PSS salt is a randomly generated string chosen
   when a message is encoded.  This means the resulting signature is
   non-deterministic.  As a result, two signatures over the same message
   will be different.  If the salt is not generated randomly, or is
   otherwise constructed maliciously, it might be possible for the salt
   to encode information that is not present in the signed message.  For
   example, the salt might be maliciously constructed to encode the
   local IP address of the client.  As a result, APIs SHOULD NOT allow
   clients to provide the salt directly; see Section 7.2 for API

   When sLen = 0, the PSS salt is empty and the resulting signature is
   deterministic.  Such signatures may be useful for applications
   wherein the only desired source of entropy is the input message.

Denis, et al.            Expires 6 February 2023               [Page 14]
Internet-Draft            RSA Blind Signatures               August 2022

   Applications that use deterministic signatures SHOULD carefully
   analyze the security implications.  When the required signature
   protocol is not clear, applications SHOULD default to randomized
   signatures, and the salted interface described in Section 5.2 SHOULD
   be used.

8.5.  Key Substitution Attacks

   RSA is well known to permit key substitution attacks, wherein an
   attacker generates a key pair (skA, pkA) that verify some known
   (message, signature) pair produced under a different (skS, pkS) key
   pair [WM99].  This means it may be possible for an attacker to use a
   (message, signature) pair from one context in another.  Entities that
   verify signatures must take care to ensure a (message, signature)
   pair verifies with a valid public key from the expected issuer.

8.6.  Alternative RSA Encoding Functions

   This document document uses PSS encoding as specified in [RFC3447]
   for a number of reasons.  First, it is recommended in recent
   standards, including TLS 1.3 [RFC8446], X.509v3 [RFC4055], and even
   PKCS#1 itself.  According to [RFC3447], "Although no attacks are
   known against RSASSA-PKCS#1 v1.5, in the interest of increased
   robustness, RSA-PSS is recommended for eventual adoption in new
   applications."  While RSA-PSS is more complex than RSASSA-PKCS#1 v1.5
   encoding, ubiquity of RSA-PSS support influenced the design decision
   in this draft, despite PKCS#1 v1.5 having equivalent security
   properties for digital signatures [JKM18]

   Full Domain Hash (FDH) [RSA-FDH] encoding is also possible, and this
   variant has equivalent security to PSS [KK18].  However, FDH is less
   standard and not used widely in related technologies.  Moreover, FDH
   is deterministic, whereas PSS supports deterministic and
   probabilistic encodings.

8.7.  Alternative Blind Signature Protocols

   RSA has some advantages as a signature protocol, particularly around
   verification efficiency.  However, the protocol in this document is
   not without shortcomings, including:

   *  RSA key and signature sizes are larger than those of alternative
      blind signature protocols;

   *  No evaluation batching support, which means that the cost of the
      protocol scales linearly with the number of invocations; and

Denis, et al.            Expires 6 February 2023               [Page 15]
Internet-Draft            RSA Blind Signatures               August 2022

   *  Extensions for features such as threshold signing are more complex
      to instantiate compared to other protocols based on, for example,
      Schnorr signatures.

   There are a number of blind signature protocols beyond blind RSA.
   This section summarizes these at a high level, and discusses why an
   RSA-based variant was chosen for the basis of this specification,
   despite the shortcomings above.

   *  Blind Schnorr [Sch01]: This is a three-message protocol based on
      the classical Schnorr signature protocol over elliptic curve
      groups.  Although simple, the hardness problem upon which this is
      based -- Random inhomogeneities in a Overdetermined Solvable
      system of linear equations, or ROS -- can be broken in polynomial
      time when a small number of concurrent signing sessions are
      invoked [PolytimeROS], leading to signature forgeries.  Even with
      small concurrency limits, Wagner's generalized attack [Wagner02]
      leads to subexponential forgery speedup.  For example, a limit of
      15 parallel sessions yields an attack runtime of approximately
      2^55, which is substantially lower than acceptable security
      levels.  In contrast, the variant in this specification has no
      such concurrency limit.

   *  Clause Blind Schnorr [FPS20]: This is a three-message protocol
      based on a variant of the blind Schnorr signature protocol.  This
      variant of the protocol is not known to be vulnerable to the
      attack in [PolytimeROS], though the protocol is still new and
      under consideration.  In the future, this may be a candidate for
      future blind signatures based on blind signatures.  However, the
      three-message flow necessarily requires two round trips between
      the client and server, which may be prohibitive for large-scale
      signature generation.  Further analysis and experimentation with
      this protocol is needed.

   *  BSA [Abe01]: This is a three-message protocol based on elliptic
      curve groups similar to blind Schnorr.  It is also not known to be
      vulnerable to the ROS attack in [PolytimeROS].  Kastner et al.
      [KLRX20] proved concurrent security with a polynomial number of
      sessions.  For similar reasons to the clause blind Schnorr
      protocol above, the additional number of round trips requires
      further analysis and experimentation.

Denis, et al.            Expires 6 February 2023               [Page 16]
Internet-Draft            RSA Blind Signatures               August 2022

   *  Blind BLS [BLS-Proposal]: The Boneh-Lynn-Shacham
      [I-D.irtf-cfrg-bls-signature] protocol can incorporate message
      blinding when properly instantiated with Type III pairing group.
      This is a two-message protocol similar to the RSA variant, though
      it requires pairing support, which is not common in widely
      deployed cryptographic libraries backing protocols such as TLS.
      In contrast, the specification in this document relies upon widely
      deployed cryptographic primitives.

   Beyond blind signature protocols, anonymous credential schemes with
   public verifiability such as U-Prove [UProve] may be used instead of
   blind signature protocols.  Anonymous credentials may even be
   constructed with blind signature protocols.  However, anonymous
   credentials are higher-level constructions that present a richer
   feature set.

8.8.  Post-Quantum Readiness

   The blind signature protocol specified in this document is not post-
   quantum ready since it is based on RSA.  (Shor's polynomial-time
   factorization algorithm readily applies.)

9.  IANA Considerations

   This document makes no IANA requests.

10.  References

10.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997,

   [RFC3447]  Jonsson, J. and B. Kaliski, "Public-Key Cryptography
              Standards (PKCS) #1: RSA Cryptography Specifications
              Version 2.1", RFC 3447, DOI 10.17487/RFC3447, February
              2003, <>.

   [RFC5756]  Turner, S., Brown, D., Yiu, K., Housley, R., and T. Polk,
              "Updates for RSAES-OAEP and RSASSA-PSS Algorithm
              Parameters", RFC 5756, DOI 10.17487/RFC5756, January 2010,

Denis, et al.            Expires 6 February 2023               [Page 17]
Internet-Draft            RSA Blind Signatures               August 2022

   [RFC8017]  Moriarty, K., Ed., Kaliski, B., Jonsson, J., and A. Rusch,
              "PKCS #1: RSA Cryptography Specifications Version 2.2",
              RFC 8017, DOI 10.17487/RFC8017, November 2016,

   [RFC8174]  Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
              2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
              May 2017, <>.

   [RFC8230]  Jones, M., "Using RSA Algorithms with CBOR Object Signing
              and Encryption (COSE) Messages", RFC 8230,
              DOI 10.17487/RFC8230, September 2017,

10.2.  Informative References

   [Abe01]    Abe, M., "A Secure Three-Move Blind Signature Scheme for
              Polynomially Many Signatures", Lecture Notes in Computer
              Science pp. 136-151, DOI 10.1007/3-540-44987-6_9, 2001,

              "[Privacy-pass] External verifiability: a concrete
              proposal", July 2020,

   [BNPS03]   Bellare, Namprempre, Pointcheval, and Semanko, "The One-
              More-RSA-Inversion Problems and the Security of Chaum's
              Blind Signature Scheme", Journal of Cryptology vol. 16,
              no. 3, pp. 185-215, DOI 10.1007/s00145-002-0120-1, June
              2003, <>.

   [Chaum83]  "Blind Signatures for Untraceable Payments", 1983,

   [FPS20]    Fuchsbauer, G., Plouviez, A., and Y. Seurin, "Blind
              Schnorr Signatures and Signed ElGamal Encryption in the
              Algebraic Group Model", Advances in Cryptology - EUROCRYPT
              2020 pp. 63-95, DOI 10.1007/978-3-030-45724-2_3, 2020,

   [GRSB19]   "Efficient Noninteractive Certification of RSA Moduli and
              Beyond", October 2019,

Denis, et al.            Expires 6 February 2023               [Page 18]
Internet-Draft            RSA Blind Signatures               August 2022

              Davidson, A., "Privacy Pass: The Protocol", Work in
              Progress, Internet-Draft, draft-davidson-pp-protocol-01,
              13 July 2020, <

              Boneh, D., Gorbunov, S., Wahby, R. S., Wee, H., Wood, C.
              A., and Z. Zhang, "BLS Signatures", Work in Progress,
              Internet-Draft, draft-irtf-cfrg-bls-signature-05, 16 June
              2022, <

              Davidson, A., Faz-Hernandez, A., Sullivan, N., and C. A.
              Wood, "Oblivious Pseudorandom Functions (OPRFs) using
              Prime-Order Groups", Work in Progress, Internet-Draft,
              draft-irtf-cfrg-voprf-12, 1 August 2022,

   [JKK14]    "Round-Optimal Password-Protected Secret Sharing and
              T-PAKE in the Password-Only model", August 2014,

   [JKM18]    Jager, T., Kakvi, S., and A. May, "On the Security of the
              PKCS#1 v1.5 Signature Scheme", Proceedings of the 2018 ACM
              SIGSAC Conference on Computer and Communications Security,
              DOI 10.1145/3243734.3243798, January 2018,

   [KK18]     Kakvi, S. and E. Kiltz, "Optimal Security Proofs for Full
              Domain Hash, Revisited", Journal of Cryptology vol. 31,
              no. 1, pp. 276-306, DOI 10.1007/s00145-017-9257-9, April
              2017, <>.

   [KLRX20]   "On Pairing-Free Blind Signature Schemes in the Algebraic
              Group Model", September 2020,

   [Lys22]    "Security Analysis of RSA-BSSA", n.d.,

              "On the (in)security of ROS", July 2020,

Denis, et al.            Expires 6 February 2023               [Page 19]
Internet-Draft            RSA Blind Signatures               August 2022

              "Remote Timing Attacks are Practical", May 2003,

   [RFC4055]  Schaad, J., Kaliski, B., and R. Housley, "Additional
              Algorithms and Identifiers for RSA Cryptography for use in
              the Internet X.509 Public Key Infrastructure Certificate
              and Certificate Revocation List (CRL) Profile", RFC 4055,
              DOI 10.17487/RFC4055, June 2005,

   [RFC5280]  Cooper, D., Santesson, S., Farrell, S., Boeyen, S.,
              Housley, R., and W. Polk, "Internet X.509 Public Key
              Infrastructure Certificate and Certificate Revocation List
              (CRL) Profile", RFC 5280, DOI 10.17487/RFC5280, May 2008,

   [RFC8446]  Rescorla, E., "The Transport Layer Security (TLS) Protocol
              Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018,

   [RSA-FDH]  "Random Oracles are Practical: A Paradigm for Designing
              Efficient Protocols", October 1995,

   [Sch01]    Schnorr, C., "Security of Blind Discrete Log Signatures
              against Interactive Attacks", Information and
              Communications Security pp. 1-12,
              DOI 10.1007/3-540-45600-7_1, 2001,

              Kocher, P., "Timing Attacks on Implementations of Diffie-
              Hellman, RSA, DSS, and Other Systems", Advances in
              Cryptology - CRYPTO '96 pp. 104-113,
              DOI 10.1007/3-540-68697-5_9, 1996,

   [UProve]   "U-Prove", February 2012, <

   [Wagner02] Wagner, D., "A Generalized Birthday Problem", Advances in
              Cryptology - CRYPTO 2002 pp. 288-304,
              DOI 10.1007/3-540-45708-9_19, 2002,

   [WM99]     "Unknown key-share attacks on the station-to-station (STS)
              protocol", October 1999.

Denis, et al.            Expires 6 February 2023               [Page 20]
Internet-Draft            RSA Blind Signatures               August 2022

Appendix A.  Test Vectors

   This section includes test vectors for the blind signature protocol
   defined in Section 5.  It does not include test vectors based on the
   external interface in Section 5.2.  The following parameters are
   specified for each test vector:

   *  p, q, n, e, d: RSA private and public key parameters, each encoded
      as a hexadecimal string.

   *  msg: Messsage being signed, encoded as a hexadecimal string.  The
      hash is computed using SHA-384.

   *  salt: Randomly-generated salt used when computing the signature.
      The length (sLen) is either 48 or 0 bytes.

   *  inv: The message blinding inverse, encoded as a hexadecimal

   *  encoded_msg: EMSA-PSS encoded message.  The mask generation
      function is MGF1 with SHA-384.

   *  blinded_msg, blind_sig: The protocol values exchanged during the
      computation, encoded as hexadecimal strings.

   *  sig: The output message signature.

   Test vector for probabilistic signatures (sLen=48):

   p = e1f4d7a34802e27c7392a3cea32a262a34dc3691bd87f3f310dc756734889305
   q = c601a9caea66dc3835827b539db9df6f6f5ae77244692780cd334a006ab353c8
   n = aec4d69addc70b990ea66a5e70603b6fee27aafebd08f2d94cbe1250c556e047

Denis, et al.            Expires 6 February 2023               [Page 21]
Internet-Draft            RSA Blind Signatures               August 2022

   e = 010001
   d = 0d43242aefe1fb2c13fbc66e20b678c4336d20b1808c558b6e62ad16a2870771
   msg = 8f3dc6fb8c4a02f4d6352edf0907822c1210a9b32f9bdda4c45a698c80023a
   salt = 051722b35f458781397c3a671a7d3bd3096503940e4c4f1aaa269d60300ce
   inv = 80682c48982407b489d53d1261b19ec8627d02b8cda5336750b8cee332ae26

Denis, et al.            Expires 6 February 2023               [Page 22]
Internet-Draft            RSA Blind Signatures               August 2022

   encoded_msg = 6e0c464d9c2f9fbc147b43570fc4f238e0d0b38870b3addcf7
   blinded_msg = 10c166c6a711e81c46f45b18e5873cc4f494f003180dd7f115
   blind_sig = 364f6a40dbfbc3bbb257943337eeff791a0f290898a67912

Denis, et al.            Expires 6 February 2023               [Page 23]
Internet-Draft            RSA Blind Signatures               August 2022

   sig = 6fef8bf9bc182cd8cf7ce45c7dcf0e6f3e518ae48f06f3c670c649ac737a8b

   Test vector for deterministic signatures (sLen=0):

   p = ca9d82e9059fa3b145da850e0c451ff31093d819644ba29a3409393de2adfa1b
   q = c075694f69db6a07456e19eeace01b430f2d6cc6cd5495d569e242b6f5e8ded7
   n = 98530f850dcc894d84ecfce9dec3a475bf30ec3ce4606f677ac4a6ef63f763ff
   e = 010001
   d = 6b15d18e4f8220709fe75f7226ca517ef9b7320d28dc66d54fa89a5727670f24
   msg = 5465737420766563746f7220776974682064657465726d696e697374696320

Denis, et al.            Expires 6 February 2023               [Page 24]
Internet-Draft            RSA Blind Signatures               August 2022

   encoded_msg = 4021ac68705782fb7587bf24ac0528853025aa4a998db7b1a503af
   inv = 6e69972553327ee6240ce0de7146aea2243927cf9f7f52c0103367df79e3ba
   blinded_msg = 5a631b41e7759a634cef04359436e358143ee2892fbebd072d1e5c
   blind_sig = 817596a0b568088b60c29482c0178d34e0d54dc34a9375152701e4e6
   sig = 848fc8a032ea073280a7d9146ae55bb0199cd1941c10a03cce1dc38579c4e7

Authors' Addresses

   Frank Denis
   Fastly Inc.

Denis, et al.            Expires 6 February 2023               [Page 25]
Internet-Draft            RSA Blind Signatures               August 2022

   Frederic Jacobs
   Apple Inc.

   Christopher A. Wood

Denis, et al.            Expires 6 February 2023               [Page 26]