Lattice-based direct anonymous attestation.
Creators: name: El Kassem, Nada
Publisher: name: University of Surrey
Year: 2020

description: A Trusted Platform Module (TPM), is a tamper-resistant hardware device that serves as a trust anchor for the host platform that it is embedded in. To do this, the TPM chip creates attestations about the state of the host system. These attestations convince a remote verifier that the platform it is communicating with is running on trusted hardware and using the correct software. Direct Anonymous Attestation (DAA) is an anonymous digital signature scheme that allows the TPM attestation service to hold the privacy-preserving property. That is, the verifier can check that those attestations originate from a certified TPM, but it does not learn the identity of the particular TPM. Another important feature of DAA is that it supports user-controlled linkability which is obtained by using a basename (bsn). If a platform uses a fresh or empty basename, the resulting attestations cannot be linked whereas using the same basename makes the corresponding transactions linkable. Currently standardised Direct Anonymous Attestation (DAA) schemes have their security based on the factoring and the discrete logarithm problems and are therefore insecure against quantum attackers as a result of Shor’s quantum algorithm. Thus, it is important to find alternatives for the currently used DAA signature schemes. Lattice-based cryptography is considered as a powerful candidate receiving lots of attention not only due to its conjectured quantum-attack resistance but also due to its security guarantee to provide worst-case hardness of average-case instances. This thesis contributes to a smooth transition of the current Direct Anonymous Attestation (DAA) and Enhanced Privacy ID (EPID) schemes, which can be seen as DAA with different linkability requirements, into the world of lattice-based cryptographic schemes. We also provide a novel solution for an outstanding authentication problem in the DAA join protocol. Our contributions are classified into three main parts. The first contribution of this work is constructing two quantum-safe lattice-based Direct Anonymous Attestation protocols from lattice assumptions. Compared to the only other lattice-based DAA scheme with conjectured post-quantum security available in the related art, the first proposed lattice-based DAA (LDAA) the protocol ensures that the storage requirements of the Trusted Platform Module (TPM) are reduced twofold and the signature sizes five times. Moreover, experimental results show that the signing and verification operations are accelerated 1.1 and 2.0 times, respectively. To achieve more efficiency, we constructed a compact quantum-safe lattice-based Direct Anonymous Attestation protocol whose signature size is around 2MB, which is (at least) two orders of magnitude smaller compared to existing post-quantum DAA schemes. The security of both proposed lattice-based DAA schemes is proved in the Universal Composability (UC) model under the assumed hardness of the Ring-Short Integer Solution (Ring-SIS) and the Ring-Learning With Errors (Ring-LWE) problems. This work is a contribution to the European H2020 FutureTPM project and the final result of this work may lead to a post-quantum DAA scheme that is suitable for inclusion in a future quantum-resistant TPM. The second contribution of this work is a new Lattice-based EPID (LEPID) protocol. Inspired by our work on lattice-based DAA schemes, we present the first Enhanced Privacy ID (EPID) scheme, supported on lattice primitives, that may benefit from future research developments in post-quantum cryptography. We also give a new security model for the EPID in the Universal Composability (UC) framework. The proposed LEPID scheme is proved secure under the new model. The third contribution deals with the DAA join protocol when the TPM uses two different keys for the purpose of user privacy. An Endorsement Key (EK) which is used to identify the TPM and an Attestation Key (AK) used for TPM attestation services. Using two different keys result with a problem of how to bind these two keys together. This is a crucial property in scenarios in which an issuer needs reliable information about AK-EK pairs before certifying the AK in the join interface of a DAA protocol. Thus we introduced a new security property of “key binding” in the process of issuing TPM Attestation Key (AK) certificates. Our analysis also showed that the DAA schemes that are supported by the TPM chips (either the TPM 1.2 version or TPM 2.0 version) can suffer from man-in-the-middle attacks from a malicious TPM and/or a malicious host, or cannot be implemented by following the TPM specifications. Finally, we present a novel solution for such an authentication problem with a rigorous security proof and implement this solution by using the existing TPM 2.0 commands with a real TPM 2.0 chip.