A New Hash-Based Enhanced Privacy ID Signature Scheme

The elliptic curve-based Enhanced Privacy ID (EPID) signature scheme is broadly used for hardware enclave attestation by many platforms that implement Intel Software Guard Extensions (SGX) and other devices. This scheme has also been included in the Trusted Platform Module (TPM) specifications and ISO/IEC standards. However, it is insecure against quantum attackers. While research into quantum-resistant EPID has resulted in several lattice-based schemes, Boneh et al. have initiated the study of EPID signature schemes built only from symmetric primitives. We observe that for this line of research, there is still room for improvement. In this paper, we propose a new hash-based EPID scheme, which includes a novel and efficient signature revocation scheme. In addition, our scheme can handle a large group size (up to \(2^{60}\) group members), which meets the requirements of rapidly developing hardware enclave attestation applications. The security of our scheme is proved under the Universal Composability (UC) model. Finally, we have implemented our EPID scheme, which, to our best knowledge, is the first implementation of EPID from symmetric primitives.

1. 1.

   The revocation code is available at: https://github.com/UoS-SCCS/HB_EPID_Revocation.

We thank the European Union’s Horizon research and innovation program for support under grant agreement numbers: 779391 (FutureTPM), 952697 (ASSURED), 101019645 (SECANT), 101069688 (CONNECT), 101070627 (REWIRE) and 101095634 (ENTRUST). These projects are funded by the UK government’s Horizon Europe guarantee and administered by UKRI. We also thank the National Natural Science Foundation of China for support under grant agreement numbers: 62072132 and 62261160651. Finally, we appreciate the valuable comments from the anonymous reviewers; particularly, the suggestion that removing \(B_j\) values from a signature would improve the performance of our scheme.

Authors and Affiliations

1. University of Surrey, Guildford, UK

   Liqun Chen, Nada El Kassem, Christopher J. P. Newton & Yalan Wang

2. Guangzhou University, Guangzhou, China

   Changyu Dong

Corresponding author

Correspondence to Liqun Chen .

Editors and Affiliations

1. Tampere University, Tampere, Finland

   Markku-Juhani Saarinen

2. University of Louisville, Gaithersburg, MD, USA

   Daniel Smith-Tone

Appendix

A Security Analysis: F-SPHINCS+

The standard security definition for digital signature schemes is existential unforgeability under adaptive chosen-message attacks (EU-CMA). It can be extended to a few-time signature by limiting the adversary’s call to the sign oracle to q times where q is the maximum number of signatures that the few-time signature scheme is allowed to generate for each signing key. Let \(SIG=(kg,sign,vf)\) be a q-time signature scheme, Fig. 4 shows the q-EU-CMA game.

q-EU-CMA game.

Full size image

Definition 1

(q-EU-CMA). Let SIG be a digital signature scheme. It is said to be q-EU-CMA secure, if for any adversary A, the following holds:

Theorem 1

For suitable parameters, n, d, k, h, q, the F-SPHINCS+ signature is \(q^h\)-EU-CMA secure if:

• \(H_1\) is SM-TCR and SM-DSPR secure;

• \(H_2\) is TSR secure with at most q queries;

• \(H_3\) is ITSR secure with at most \(q^h\) queries;

• \(\textsf {prf}\) is a secure pseudorandom function.

Proof

To successfully forge a group issuer’s signature on a message M chosen by the adversary, there are the following mutually exclusive cases:

1. 1

   Let \(MD||idx=H_3(M||gr)\) for some gr. In the forged signature, All secret strings corresponding to \(MD=p_0||\cdots ||p_{k-1}\), i.e. \(\{{\textbf {x}}^{(i)}_{p_i}\}_{i=0}^{k-1}\), are the same as generated from \(\texttt {leaf}_{idx}\)’s secret key. This case consists of the following sub-cases:

   1. 1.1

      The adversary learns all secret strings from signatures obtained in the query phase.

   2. 1.2

      Some secret strings are not leaked from previous signatures, and for each of them, the adversary either:

      1. 1.2.1

         learns it by breaking the pseudorandom function that is used to expand the secret key into x\(_i\);

      2. 1.2.2

         or learns it by looking at their \(H_1\) hash values and find the pre-images.

2. 2

   Let \(MD||idx=H_3(M||gr)\) for some gr. In the forged signature, some secret strings corresponding to \(MD=p_0||\cdots ||p_{k-1}\), i.e. \(\{{\textbf {x}}^{(i)}_{p_i}\}_{i=0}^{k-1}\), are NOT the same as generated from \(\texttt {leaf}_{idx}\)’s secret key. Then let S be the list of \(h+1\) M-FORS signatures in the forged signature, we can find i such that when verifying the i-th signature \((0\le i\le h)\), we obtain the same public key as would be generated by the signer, but for all \(0\le j<i\), we obtain a different public key as would be generated by the signer. This means:

   1. 2.1

      The adversary has found at least one second-preimages of \(H_1\) so that some Merkle trees in the ith signature are computed with the second-preimages. They end up having the same roots as the trees computed by the group issuer.

   2. 2.2

      The adversary knows all secret strings corresponding to the public key produced from verifying the \((i-1)\)th signature. This public key is different from the public key at the same location generated by the group issuer. This can be done by either:

      1. 2.2.1

         learning all from previous signature queries;

      2. 2.2.2

         or breaking the pseudorandom function;

      3. 2.2.3

         or finding some pre-images of \(H_1\).

Given the above, we analyze the F-SPHINCS+ signature scheme through a series of games:

Game 0: The original EU-CMA game in which the adversary needs to forge a valid group issuer’s signature after \(q_s\) queries.

Game 1: Exactly as Game 0 except all output of prf are replaced by truly random n-bit strings. We eliminate from the above list Case 1.2.1 and 2.2.2 by this modification. Since each call to prf uses a secret key and a distinct value as input, assuming prf is a pseudorandom function, we have:

Game 2: Game 2 differs from Game 1 in that we consider the adversary lost if the adversary outputs a forgery by breaking the ITSR security of \(H_3\). This modification eliminates from the above list Case 1.1. The winning condition in Fig. 4 is changed to:

• Return 1 iff \(ITSR(H_3,M^*)=0\wedge vf(pk,M^*,\sigma ^*)=1 \wedge M^*\not \in \{M_i\}_{i=1}^{q^h}\).

The predicate ITSR is defined as the following:

• Let \(M^*\) be the message that the adversary chooses to generate the forgery on, and \(gr^*\) the random string used by the adversary to compute \(MD^*||idx^*=H_3(M^*||gr^*)\).

• Parse \(MD^*=p_0^*||\cdots ||p_{k-1}^*\) where each \(p_j^*\in [0,2^d-1]\). From the above we obtain a set \(C^*=((idx^*,0,p_0^*),\cdots ,(idx^*,k-1,p_{k-1}^*))\).

• For each message queried in the query phase \(M_i\) (\(1\le i\le q^h\)), and \(gr_i\) the random string, compute \(MD_i||idx_i=H_3(M_i||gr_i)\) and obtain \(C_i=((idx_i,0,p_{i,0}),\cdots ,(idx_i,k-1,p_{i,k-1}))\).

• Return 1 iff \(C^*\subseteq \bigcup _{i=1}^{q^h}C_i\).

We can see that \(ITSR(H_3,M^*)=0\) iff the adversary can break the ITSR security of \(H_3\). Hence, we have:

Game 3: Game 3 differs from Game 2 in that we consider the adversary lost if the forgery contains a second preimage for an input to \(H_1\) that was part of a signature returned as a signing-query response. Here the second preimage can be included explicitly in the signature, or implicitly observed when verifying the signature. This eliminates from the above list Case 2.1. Then we have:

Game 4: Game 4 differs from Game 3 in that we consider the adversary lost if the adversary outputs a forgery by breaking the TSR security of \(H_2\), which allows the adversary to forge an intermediate signature in \({\textbf {S}}\), and then any signature earlier in the chain. This eliminates from the above list Case 2.2.1. The winning condition in Fig. 4 is changed to:

• Return 1 iff \(TSR(H_2,M^*)=0\wedge ITSR(H_3,M^*)=0\wedge vf(pk,M^*,\sigma ^*)=1 \wedge M^*\not \in \{M_i\}_{i=1}^{q^h}\).

The predicate TSR is defined as the following:

• The adversary chooses an intermediate node in the hyper-tree at address (a, b), and two n-bit string \(L^*,R^*\).

• For each signature obtained in the query phase, if \({\textbf {S}}_i\) includes a signature generated using the secret key in node (a, b) over the public key in one of its child node, parse this public key into k blocks, each of d-bit \(pk_i=p_{i,0}||\cdots ||p_{i,k-1}\), and generate a set \(C_i=\{( j,p_{i,j})\}_{j=0}^{k-1}\).

• Compute \(pk^*=H_2(\texttt {aux}||k||0||0||L^*||R^*)\), parse \(pk^*\) into \(p_{0}^*||\cdots ||p_{k-1}^*\), and generate a set \(C^*=\{( j,p_{j}^*)\}_{j=0}^{k-1}\).

• Return 1 iff \(C^*\subseteq \bigcup _{i=1}^{q}C_i\).

Note that each M-FORS public key is the root of a Merkle tree generated from pseudorandom strings. Also for each intermediate node in a hyper-tree, it has at most q children, hence no more than q signatures signed by the secret key in this intermediate node can be obtained by the adversary. So \(TSR(H_2,M^*)=0\) iff the adversary can break the TSR security of \(H_2\). Hence, we have:

Now the cases in which the adversary can forge a signature are all eliminated except Case 1.2.2 and 2.2.3, which requires the adversary to find a pre-image of at least one hash values produced by \(H_1\). The success probability of finding a pre-image is as analyzed in [4]:

So overall, the advantage of the adversary is negligible.    \(\square \)

TSR security of \(\boldsymbol{H_2}\). In any case, q signatures can be generated under the secret key of a non-leaf node in the hyper-tree. Assuming the adversary knows all of them, then for each block of the chosen \(pk^*\), the probability of the secret string has been leaked is \(1-(1-\frac{1}{2^d})^q\), so all secret string have been leaked is \((1-(1-\frac{1}{2^d})^q)^k\). For \(d={16},q=1024,k=68\), this probability is \(2^{-468.87}\), if \(k=35\), this probability is \(2^{-210.39}\).

ITSR security of \(\boldsymbol{H_3}\). For a leaf node of the hyper-tree, it may have been used to sign \(\gamma \) signatures out of the total \(q_s\) signature queries. So the probability that all secret string of a chosen message M being leaked through query is:

For \(d={16},q=1024,k=68, h=6, q_s=2^{60}\), this probability is \(2^{-407.32}\), if \(k=35\), this probability is \(2^{-208.95}\).

Reprints and permissions

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

Policies and ethics