Bilinear map based one-time signature scheme with secret key exposure

Dijk et al. [6] presents Remote Attestation (RA) for secure processor technology which is secure in the presence of an All Digital State Observing (ADSO) adversary. The scheme uses a combination of hardware security primitives and design principles together with a new cryptographic primitive called a Public Key Session based One-Time Signature Scheme with Secret Key Exposure (OTS-SKE). [6] shows a hash based realization of OTS-SKE which is post quantum secure but suffers long 8.704 KB signatures for 128-bit quantum security or 256-bit classical security. From a classical cryptographic perspective we complete the picture by introducing a bilinear map based OTS-SKE with short 0.125 KB signatures, 65 times shorter, and for which the security reduces to the Computational Diffie-Hellman Problem (CDHP) – at the cost of a 9× longer initialization phase in the RA scheme if implemented in software (this can be improved with appropriate elliptic curve hardware acceleration). Signing takes 560 ms at most 60% of the > 936 ms needed for the hash based scheme.