Batched Signatures
draft-joseph-tls-batch-signatures-00
| Document | Type | Active Internet-Draft (individual) | |
|---|---|---|---|
| Authors | David Joseph , Deirdre Connolly , Carlos Aguilar-Melchor | ||
| Last updated | 2023-11-04 | ||
| RFC stream | (None) | ||
| Intended RFC status | (None) | ||
| Formats | |||
| Stream | Stream state | (No stream defined) | |
| Consensus boilerplate | Unknown | ||
| RFC Editor Note | (None) | ||
| IESG | IESG state | I-D Exists | |
| Telechat date | (None) | ||
| Responsible AD | (None) | ||
| Send notices to | (None) |
draft-joseph-tls-batch-signatures-00
Network Working Group D. Joseph
Internet-Draft D. Connolly
Intended status: Informational C. Aguilar-Melchor
Expires: 8 May 2024 SandboxAQ
5 November 2023
Batched Signatures
draft-joseph-tls-batch-signatures-00
Abstract
This document proposes a construction for batch signatures where a
single, potentially expensive, "base" digital signature authenticates
a Merkle tree constructed from many messages.
Discussion of this work is encouraged to happen on the IETF TLSWG
mailing list tls@ietf.org or on the GitHub repository which contains
the draft: https://github.com/PhDJsandboxaq/draft-joseph-batch-
signatures
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 https://datatracker.ietf.org/drafts/current/.
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 8 May 2024.
Copyright Notice
Copyright (c) 2023 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents (https://trustee.ietf.org/
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
Joseph, et al. Expires 8 May 2024 [Page 1]
Internet-Draft joseph-tls-batch-signatures November 2023
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 . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1. Signatures . . . . . . . . . . . . . . . . . . . . . . . 3
2.2. Hash functions . . . . . . . . . . . . . . . . . . . . . 3
2.2.1. Hash function properties . . . . . . . . . . . . . . 4
2.2.2. Tweakable Hash functions . . . . . . . . . . . . . . 4
2.3. Motivation for batching messages before signing . . . . . 5
2.4. Scope . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3. Batch signature construction . . . . . . . . . . . . . . . . 5
3.1. Batch signature definition . . . . . . . . . . . . . . . 5
3.2. Merkle tree batch signature . . . . . . . . . . . . . . . 6
3.3. Signing . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.3.1. Tree computation . . . . . . . . . . . . . . . . . . 6
3.3.2. Signature construction . . . . . . . . . . . . . . . 7
3.4. Verification . . . . . . . . . . . . . . . . . . . . . . 7
4. Security Considerations . . . . . . . . . . . . . . . . . . . 8
4.1. Correctness . . . . . . . . . . . . . . . . . . . . . . . 8
4.2. Domain separation . . . . . . . . . . . . . . . . . . . . 9
4.3. Target collision resistance vs collision resistance . . . 9
5. Post-quantum and hybrid signatures . . . . . . . . . . . . . 9
5.1. Signature sizes . . . . . . . . . . . . . . . . . . . . . 10
5.2. Hybrid signatures {pqc-hybrid} . . . . . . . . . . . . . 10
5.3. Privacy . . . . . . . . . . . . . . . . . . . . . . . . . 10
6. Relationship to Merkle Tree Certificates . . . . . . . . . . 11
7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 12
8. Informative References . . . . . . . . . . . . . . . . . . . 12
Appendix A. Related work . . . . . . . . . . . . . . . . . . . . 14
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 14
1. Introduction
The computational complexity of unkeyed and symmetric cryptography is
known to be significantly lower than asymmetric cryptography.
Indeed, hash functions, stream or block ciphers typically require
between a few cycles [AES-NI] to a few hundred cycles [GK12], whereas
key establishment and digital signature primitives require between
tens of thousands to hundreds of millions of cycles [SUPERCOP]. In
situations where a substantial volume of signatures must be handled
-- e.g. a Hardware Security Module (HSM) renewing a large set of
short-lived certificates or a load balancer terminating a large
number of TLS connections per second -- this may pose serious
limitations on scaling these and related scenarios.
Joseph, et al. Expires 8 May 2024 [Page 2]
Internet-Draft joseph-tls-batch-signatures November 2023
These challenges are amplified by upcoming public-key cryptography
standards: in July 2022, the US National Institute of Standards and
Technology (NIST) announced four algorithms for post-quantum
cryptography (PQC) standardisation. In particular, three digital
signature algorithms -- Dilithium [CRYSTALS-DILITHIUM], Falcon
[FALCON] and SPHINCS [SPHINCS] -- were selected, and migration from
current standards to these new algorithms is already underway
[NSM10]. One of the key issues when considering migrating to PQC is
that the computational costs of the new digital signature algorithms
are significantly higher than those of ECDSA; the fastest currently-
deployed primitive for signing. This severely impacts the ability of
systems to scale and inhibits their migration to PQC, especially in
higher-throughput settings.
2. Preliminaries
2.1. Signatures
* *DSA* Digital Signature Algorithm, a public key cryptography
primitive consisting of a triple of algorithms _KeyGen_, _Sign_,
_Verify_ whereby:
- _KeyGen(k)_ outputs a keypair _sk, pk_ where _k_ is a security
parameter
- _Sign(sk, msg) = s_
- _Verify(pk, s, msg) = b_. When _b=1_, the result is ACCEPT
which occurs on receipt of message, correctly signed with the
secret key _sk_ corresponding to _pk_. Otherwise the result is
REJECT when _b=0_.
2.2. Hash functions
In this work we consider _tweakable_ hash functions. These are keyed
hash functions that take an additional input which can be thought of
as a domain separator (while the key or public parameter serves as a
separator between users). Tweakable hash functions allow us to
tightly achieve target collision resistance even in multi-target
settings where an adversary wins when they manage to attack one out
of many targets.
* *Keyed Hash function* A keyed hash function is one that outputs a
hash that depends both on a message _msg_ and a key _v_ that is
shared by both the hash generator and the hash validator. It is
easiest to compute via prepending the key to the message before
computing the hash _h <-- H(v | msg)_. Let _Hv_ denote the family
of hash functions keyed with _v_.
Joseph, et al. Expires 8 May 2024 [Page 3]
Internet-Draft joseph-tls-batch-signatures November 2023
2.2.1. Hash function properties
* Collision resistance - no two inputs _x1, x2_ should map to the
same output hash (regardless of choice of key in the case of a
keyed hash).
* Preimage resistance - it should be difficult to guess the input
value _x_ for a hash function given only its output _H(x)_.
* Second preimage resistance - given an input _x1_, it should be
difficult to find another distinct input _x2_ such that
_H(x1)=H(x2)_.
* Target collision resistance - choose input _x1_. Then given a key
_v_, find _x2_ such that _Hv(x1) = Hv(x2)_.
Target collision resistance is a weaker requirement than collision
resistance but is sufficient for signing purposes. Tweakable hash
functions enable us to tightly achieve TCR even in multi-target
settings where an adversary can attack one out of many targets.
Specifically, the property achieved in the following is _single-
function multi-target collision resistance_ (SM-TCR) which is
described more formally in [AABBHHJM23].
2.2.2. Tweakable Hash functions
One form of keyed hash function is a tweakable hash function, which
enables one to obtain SM-TCR:
* *Tweakable Hash functions* A _tweakable hash function_ is a tuple
of algorithms _H=(KeyGen, Eval)_ such that:
- _KeyGen_ takes the security parameter _k_ and outputs a
(possibly empty) public parameter _p_. We write _p <--
KeyGen(k)_.
- _Eval_ is deterministic and takes public parameters _p_, a
tweak _t_, an input _msg_ in _[0,1]^m_ and returns a hash value
_h_. We write _h <-- Eval(p,t,msg)_ or simply _h <--
H(p,t,msg)_.
Joseph, et al. Expires 8 May 2024 [Page 4]
Internet-Draft joseph-tls-batch-signatures November 2023
2.3. Motivation for batching messages before signing
Batch signing enables the scaling of slow algorithms by signing large
batches of messages simultaneously. This comes at a relatively low
latency cost, and significant throughput improvements. These
advantages are particularly pertinent when considering the use of
post-quantum signatures, such as those being standardised by NIST at
the time of writing. In some applications, the amount of data that
needs to be sent can be reduced in addition; namely, if a given
entity (is aware that it) receives multiple signatures from the same
batch. In this case, sending the signed root multiple times is
redundant and we can asymptotically reduce the amount of received
information to a few hashes per message.
2.4. Scope
This document describes a construction for batch signatures based
upon a Merkle tree design. The total signature consists of a
signature of the root of the Merkle tree, as well as the sibling path
of the individual message. We discuss the applicability of such
signatures to various protocols, but only at a high level. The
document describes a scheme which enables smaller signatures than
outlined in [BEN20] by relying not on hash collision resistance, but
instead on target collision resistance, however for the security
proofs the reader should see [AABBHHJM23].
3. Batch signature construction
3.1. Batch signature definition
We define a batch signature as a triple of algorithms - *Batch
signature* a batch signature scheme is comprised of _KeyGen_,
_BSign_, _Verify_ whereby: - _KeyGen(k)_ outputs a keypair _sk, pk_
where _k_ is a security parameter - _BSign(sk, M)_ the batch signing
algorithm takes as input a list of messages _M = {msg-i}_ and outputs
a list of signatures _S={sig-i}_. We write _S <-- BSign(sk,M)_ -
PVerify(pk, sig, msg)_. We call the verification _PVerify_ to
represent Path Verification, because in the construction outlined
below, verification involves an extra step of verifying a sibling
path, which _Verify_ in the ordinary DSA setting does not do.
Joseph, et al. Expires 8 May 2024 [Page 5]
Internet-Draft joseph-tls-batch-signatures November 2023
3.2. Merkle tree batch signature
Our construction relies on a Merkle tree. When addressing nodes in a
Merkle tree of height _h_ with _N_ leaves, we may label nodes and
leaves in the tree by their position: _T[i,k]_ is the _i_-th node at
height _k_, counting from left to right and from bottom upwards (i.e.
leaves are on height _0_ and the root is on height _h_. We illustrate
this in Figure 1.
Let _Sig=(KeyGen, Sign, Verify)_ be a DSA as defined in Section 2.1,
let _thash_ be a tweakable hash function as defined in Section 2.2.2.
We define our batch signature scheme _BSig = (KeyGen, BSign, BVerify_
with _KeyGen := Sig.KeyGen_ and _BSign, Verify_ as in Section 3.1
respectively.
Here we describe the case of binary Merkle trees. In the case where
_N_ is not a power of _2_, one can pad the tree by repeating leaves,
or else continue with an incomplete tree.
3.3. Signing
_BSign(sk, M=[msg-0,...,msg-N-1])_ where _N=2^n_. We first treat the
case that _N_ is a power of _2_, and then consider incomplete trees
using standard methods.
3.3.1. Tree computation
* *Initialize tree* _T[ ]_, which is indexed by the level, and then
the row index, e.g. _T[3,5]_ is the fifth node on level 3 of _T_.
Height _h <-- log2(N)_
* *Tree identifier* Sample a tree identifier _id <--$ {0,1}^k_
* *Generate leaves* For leaf _i in [0,...,N-1]_, sample randomness
_r-i <--$ {0,1}^k_. Then set _T[0,i] = H(id, 0, i, r-i, msg-i)._
* *Populate tree* For levels _l in [1,..., h]_ compute level _l_
from level _l-1_ as follows:
- Initialize level _l_ with half as many elements as level _l-1_.
- For node _j_ on level _l_, set _left=T[l-1, 2j]_ and
_right=T[l-1, 2j+1]_
- _id_ is the public parameter, _(1, l, j)_ is the tweak.
- _T[l, j] <-- H(id, 1, l, j, left, right)_
Joseph, et al. Expires 8 May 2024 [Page 6]
Internet-Draft joseph-tls-batch-signatures November 2023
* *Root* set _root <-- T[h,0]_
3.3.2. Signature construction
* *Sign the root* Use the base DSA to sign the root of the Merkle
tree _rootsig <-- Sign(sk, id, root, N)_
* *Sibling path* For each leaf: The sibling path is an array of _h-
1_ hashes. Compute the sibling path as follows:
- Initialize _path-i <-- []_
- For _l in [0, ..., N-1]_, set _j <--floor(i / 2^l)_. If _j mod
2 = 0_ then _path-i[l]=T[l,j+1]_, else _path-i[l]=T[l,j-1]_
* *Generate batch signatures* _bsig-i <-- (id, N, sig, i, r-i, path-
i)_
* *Return batch of signatures* batch signatures are {bsig-1, ...,
bsig-N}
Figure 1 illustrates the construction of the Merkle tree and the
signature of the root.
lvl3=root (T30)--DSA--> sig
/ \
lvl2 T20---- ----T21
/\ /\
/ \ / \
lvl2 T10 T11 T12 T13
/\ /\ /\ /\
/ \ / \ / \ / \
lvl1 T00 T01 T02 T03 T04 T05 T06 T07
| | | | | | | |
| | |
H(_) ... H(id,0,3,r3,msg3) ...H(_)
Figure 1: Merkle tree batch signature construction
3.4. Verification
Verification proceeds by first reconstructing the root hash via the
leaf information (public parameters, tweak, message) and iteratively
hashing with the nodes provided in the sibling path. Next the base
verification algorithm is called to verify the base DSA signature of
the root.
Joseph, et al. Expires 8 May 2024 [Page 7]
Internet-Draft joseph-tls-batch-signatures November 2023
* *Generate leaf hash* Get hash from public parameter, tweak, and
message _h <-- H(id, 0, i, r, msg)_.
* *Reconstruct root* Set _l=0_. For _l in [ 1, ..., h]_ set _j <--
floor(i/2^l)_.
- If _j mod 2 = 0_: set _h <-- H(id, 1, l, j, h, path[l])_.
- If _j mod 2 = 1_: set _h <-- H(id, 1, l, j, path[l], h)_.
* *Verify root* Return _Verify(pk, sig, h)_.
4. Security Considerations
A reduction in certificate sizes is proposed by a new type of CA
(certificate authority) which would exclusively sign a new type of
batch oriented certificates. Such a CA would only be used together
with a Certificate Transparency log, which changes the usual required
flows for authentication. The benefits obtained in certificate size
and verification/signature costs are significant. It also implies
that the main criterion for being on a same batch are: being signed
by the same CA, and being signed roughly at the same time.
4.1. Correctness
Correctness can be broken down into correctness of the base DSA, and
correctness of the Merkle tree. Correctness is considered a security
property, and is generally proven for each DSA, so we only need to
demonstrate correctness of the Merkle tree root. The Merkle proof
assures that a message is a leaf at a given index or address, in the
tree identified by _id_, and nothing more.
Hash functions are symmetric and therefore deterministic in nature,
therefore, given the correct sibling path as part of the signer's
signature, will generate the Merkle tree root correctly. Given an
accepting (message, signature) pair, so long as one uses a hash
function that provides second preimage resistance (from which the
tweakable hash then provides SM-TCR), this guarantees that - except
with negligible probability - the proof must be valid only for the
message provided.
Joseph, et al. Expires 8 May 2024 [Page 8]
Internet-Draft joseph-tls-batch-signatures November 2023
4.2. Domain separation
Our construction uses tweakable hashfunctions which take as input a
public parameter _id_, a tweak _t_, and a message _msg_. The public
parameter domain separates between Merkle trees used in the same
protocol. In [BEN20] it is suggested that TLS context strings are
used to prevent cross-protocol attacks, however we note here that
_msg_, which is the full protocol transcript up to that point,
includes such protocol context strings. Therefore domain separation
is handled implicitly. However in an idea world all protocols would
agree on a uniform approach to domain separation, and so we invite
comment on how to concretely handle this aspect.
4.3. Target collision resistance vs collision resistance
Instead of collision resistance, relying on the weaker assumption of
TCR, and more specifically SM-TCR, increases the attack complexity of
finding a forgery and breaking the scheme. The result is that
smaller hash outputs are required to achieve an equivalent security
level. This key modification versus [BEN20] thus provides smaller
signatures or higher security for the same sized signatures.
The reduction in signature size is _(h-1) * d_ where _h_ is the tree
height and _d_ is the difference between the hash output length based
on SM-TCR and that based on collision resistance. Usually TCR
implies using, for example, 128b digests to achieve 128b security,
whereas basing on CR would require 256b digests. This change
therefore in essence halves the size of the Merkle tree proofs.
5. Post-quantum and hybrid signatures
*Digital signatures* The transition to post-quantum cryptography
(PQC) coincides with increasing demands on performance and
throughput. Post-quantum signatures suffer worse performance both on
computation and public key/signature sizes versus their quantum-
vulnerable counterparts which are based on elliptic curve
cryptography and RSA. As a result, techniques to boost performance
are especially relevant in this case. In Section 5.1 one can see
that the extra size cost due to the sibling path is roughly
independent of the algorithm used (therefore relatively much smaller
for PQC).
*Hash functions* In contrast to DSAs, Hash functions are purely
symmetric cryptography which is weakened but not broken by quantum
computers. Therefore the Merkle tree construction is not affected in
the post-quantum era, other than a doubling of parameters (in the
worst case) to achieve the same security level.
Joseph, et al. Expires 8 May 2024 [Page 9]
Internet-Draft joseph-tls-batch-signatures November 2023
5.1. Signature sizes
In Figure 2 one can see the size of a batch signature which signs 16
or 32 transcripts, relative to the size of the underlying primitive.
For post-quantum schemes the overhead in size is relatively small due
to the much larger sizes of the base DSAs.
+--------------------+-----+------+-------+----+--------+
| Scheme | k | |vk| | |sig| | N | |bsig| |
+--------------------+-----+------+-------+----+--------+
| ECDSA P256 | 128 | 64 | 64 | 32 | 180 |
| Dilithium2 | 128 | 1312 | 2420 | 32 | 2536 |
| Dilithium5 | 256 | 2592 | 4595 | 32 | 4823 |
| Falcon-512 | 128 | 897 | 666 | 16 | 766 |
| Falcon-1024 | 256 | 1793 | 1280 | 32 | 1508 |
| Falcon-512-fpuemu | 128 | 897 | 666 | 16 | 766 |
| Falcon-1024-fpuemu | 256 | 1793 | 1280 | 16 | 1476 |
| SPHINGS+-128f | 128 | 32 | 17088 | 16 | 17188 |
| SPHINCS-256f | 256 | 64 | 49856 | 32 | 50084 |
+--------------------+-----+------+-------+----+--------+
Figure 2: Batch signature sizes
5.2. Hybrid signatures {pqc-hybrid}
A likely mode of transition to PQC will be via 'hybrid mode', where
data is protected independently via two algorithms, one quantum-
vulnerable (but well studied and understood) and one PQC algorithm.
This is to mitigate the risk of a complete break - classical or
quantum - of a PQC algorithm. Breaking a hybrid scheme should imply
breaking _both_ of the algorithms used.
We do not discuss the details of such hybrid signatures or hybrid
certificates in this document, but simply state that so long as the
hybrid scheme adheres to the API described above, the Batch signature
Merkle tree construction described in this document remains
unaltered. Explicitly, the root is generated via the procedure of
Section 3.3.1. Then the root is signed by the hybrid DSA, whose
functions _KeyGen_, _Sign_, _Verify_ are constructed via some
composition of _KeyGen_, _Sign_, _Verify_ for a PQC algorithm and
_KeyGen_, _Sign_, _Verify_ for some presently-used algorithm.
5.3. Privacy
In [AABBHHJM23] two privacy notions are defined:
* *Batch Privacy* can one cannot deduce whether two messages were
signed in the same batch.
Joseph, et al. Expires 8 May 2024 [Page 10]
Internet-Draft joseph-tls-batch-signatures November 2023
* *weak Batch Privacy* for two messages signed in the same batch, if
one is given the signature for one
* message, it does not leak any information about the other message,
for which no signature is available.
The authors prove in [AABBHHJM23] that this construction achieves the
weaker variant, but not full Batch Privacy.
6. Relationship to Merkle Tree Certificates
A Merkle tree construction for TLS certificates [BEN23] is being
developed at the time of writing, by the same author of the original
Merkle tree signing draft [BEN20]. The construction bears strong
similarities to the current proposal. In ordinary TLS certificates,
a Certificate Authority (CA) signs a certificate which asserts that a
public key belongs to a given subscriber. In the Merkle tree
construction, many certificates are batched together using a similar
Merkle tree construction to the one presented in this document. The
CA then signs only the root of the Merkle tree, and returns (root
signature + sibling path) to the subscriber.
A client verifies a server's identity by:
* Verifying a server's signature: the server signs the TLS
transcript up to that point with their private key and the client
verifies with the server's public key _pk_.
* Verifying that the public key belongs to the server by verifying
the trusted CA's signatures certificate which states that the
server owns _pk_.
- Doing this repeatedly in the case of certificate chains until
reaching a root CA.
The document of [BEN23] relates specifically to signing certificates,
the second bullet above, whereas the constructions of [BEN20] and
this document pertain to a server authenticating itself online,
relating to the first bullet above. The two have slightly different
usecases, which both benefit from Merkle tree constructions under
different scenarios.
Cases where Merkle tree certificates may be appropriate have certain
properties:
* Certificates are short-lived.
Joseph, et al. Expires 8 May 2024 [Page 11]
Internet-Draft joseph-tls-batch-signatures November 2023
* Certificates are issued after a significant delay, e.g. around one
hour.
* Batch sizes can be estimated to be up to 2^24 (based on unexpired
number of certificates in certificate transparency logs)
Cases where TLS batch signing may be appropriate differ slightly, for
example:
* High throughput servers and load balancers - in particular when
rate of incoming signing requests exceeds _(time * threads)_ where
_time_ is the average time for a signing thread to generate a
signature, and _threads_ is the number of available signing
threads.
* In scenarios where the latency is not extremely sensitive: waiting
for signatures to arrive before constructing a Merkle tree incurs
a small extra latency cost which is amortised by the significant
extra throughput achievable.
* Batch sizes are likely to be smaller than the usecase for Merkle
tree certificates. Batch sizes of 16 or 32 can already improve
throughput by an order of magnitude.
7. Acknowledgements
8. Informative References
[AABBHHJM23]
Carlos Aguilar-Melchor, Martin Albrecht, Thomas Bailleux,
Nina Bindel, James Howe, Andreas Huelsing, David Joseph,
and Marc Manzano, "Batch Signatures, Revisited", 2023,
<https://eprint.iacr.org/2023/492>.
[AES-NI] Kahraman Akdemir, Martin Dixon, Wajdi Feghali, Patrick
Fay, Vinodh Gopal, Jim Guilford, Erdincand Ozturk, Gil
Wolrich, and Ronen Zohar, "Breakthrough AES Performance
with Intel AES New Instructions", 2010,
<https://www.intel.cn/content/dam/develop/external/us/en/
documents/10tb24-breakthrough-aes-performance-with-intel-
aes-new-instructions-final-secure-165940.pdf>.
[BEN20] David Benjamin, "Batch Signing for TLS: draft-ietf-tls-
batch-signing-00", 2023,
<https://datatracker.ietf.org/doc/html/draft-ietf-tls-
batch-signing-00#section-2>.
Joseph, et al. Expires 8 May 2024 [Page 12]
Internet-Draft joseph-tls-batch-signatures November 2023
[BEN23] David Benjamin, "Merkle Tree Certificates for TLS", 8
September 2023, <https://datatracker.ietf.org/doc/draft-
davidben-tls-merkle-tree-certs/>.
[CRYSTALS-DILITHIUM]
Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V.,
Schwabe, P., Seiler, G., and D. Stehlé, "CRYSTALS-
Dilithium: A Lattice-Based Digital Signature Scheme",
Universitatsbibliothek der Ruhr-Universitat Bochum, IACR
Transactions on Cryptographic Hardware and Embedded
Systems pp. 238-268, DOI 10.46586/tches.v2018.i1.238-268,
February 2018,
<https://doi.org/10.46586/tches.v2018.i1.238-268>.
[FALCON] Moody, D., "Fast Fourier Sampling over NTRU Lattices
Digital Signature Standard", National Institute of
Standards and Technology, DOI 10.6028/nist.fips.206, 2023,
<https://doi.org/10.6028/nist.fips.206>.
[GK12] Gueron, S. and V. Krasnov, "Parallelizing message
schedules to accelerate the computations of hash
functions", Springer Science and Business Media LLC,
Journal of Cryptographic Engineering vol. 2, no. 4, pp.
241-253, DOI 10.1007/s13389-012-0037-z, September 2012,
<https://doi.org/10.1007/s13389-012-0037-z>.
[NSM10] Shalanda D Young, "National Security Memorandum on
Promoting United States Leadership in Quantum Computing
While Mitigating Risks to Vulnerable Cryptographic
Systems", 4 May 2010, <https://www.whitehouse.gov/
briefing-room/statements-releases/2022/05/04/national-
security-memorandum-on-promoting-united-states-leadership-
in-quantum-computing-while-mitigating-risks-to-vulnerable-
cryptographic-systems/>.
[SPHINCS] Bernstein, D., Hülsing, A., Kölbl, S., Niederhagen, R.,
Rijneveld, J., and P. Schwabe, "The SPHINCS <sup>+</sup>
Signature Framework", ACM, Proceedings of the 2019 ACM
SIGSAC Conference on Computer and Communications Security,
DOI 10.1145/3319535.3363229, November 2019,
<https://doi.org/10.1145/3319535.3363229>.
[SUPERCOP] Daniel J Bernstein and Tanja Lange, "SUPERCOP: System for
unified performance evaluation related to cryptographic
operations and primitives.", 2018,
<https://bench.cr.yp.to/supercop.html>.
Joseph, et al. Expires 8 May 2024 [Page 13]
Internet-Draft joseph-tls-batch-signatures November 2023
Appendix A. Related work
Authors' Addresses
David Joseph
SandboxAQ
Email: dj@sandboxaq.com
Deirdre Connolly
SandboxAQ
Email: deirdre.connolly@sandboxquantum.com
Carlos Aguilar-Melchor
SandboxAQ
Email: carlos.aguilar@sandboxaq.com
Joseph, et al. Expires 8 May 2024 [Page 14]