Paper 2021/925

Bilinear Map Based One-Time Signature Scheme with Secret Key Exposure

Marten van Dijk, Deniz Gurevin, Chenglu Jin, Omer Khan, and Phuong Ha Nguyen


Dijk et al. 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). Dijk et al. show 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\times$ 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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Remote AttestationOne Time SignaturesSecret Key Exposure
Contact author(s)
deniz gurevin @ uconn edu
2021-07-09: received
Short URL
Creative Commons Attribution


      author = {Marten van Dijk and Deniz Gurevin and Chenglu Jin and Omer Khan and Phuong Ha Nguyen},
      title = {Bilinear Map Based One-Time Signature Scheme with Secret Key Exposure},
      howpublished = {Cryptology ePrint Archive, Paper 2021/925},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.