An attestation protocol between a prover device (P), a verifier device (V), and a trusted third-party device (TTP). P and TTP have a first trust relationship represented by a first cryptographic representation based on a one-or-few-times, hash-based, signature key. V sends an attestation request to P, with the attestation request including a second cryptographic representation of a second trust relationship between V and TTP. In response to the attestation request, P sends a validation request to TTP, with the validation request being based on a cryptographic association of the first trust relationship and the second trust relationship. TTP provides a validation response including a cryptographic representation of verification of validity of the first trust relationship and the second trust relationship. P sends an attestation response to V based on the validation response.