Overview of Hash-Based Signatures and XMSS Secret Key Generation
This content delves into the concepts of hash-based signatures, particularly focusing on the XMSS secret key generation parameters, secret key size, forward-secure variants of XMSS, and the importance of forward security in signature schemes. The discussions cover key generation processes, security goals, and mechanisms such as PRG and FSPRG in the context of XMSS forward secure signatures.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Hash-Based Signatures Lamport-Diffie-Merkle-Winternitz Draft-McGrew (Leighton-Micali) Draft-Huelsing (XMSS) SPHINCS
Basic One-Time-Signature Signing a bit Public key: H(s0)||H(s1) Secret key: s0, s1 Signature for 0: s0 Signature for 1: s1 To sign a message digest, simply concatenate 256 one-bit public keys/ secret keys / signatures One for each bit of the digest: Public key: H(s0,0)||H(s0,1) || H(s1,0)||H(s1,1) || || H(s255,0)||H(s255,1) Note that with a signature on as few as two digests (e.g. 111 1, 000 0) the adversary can forge any signature. (Hence, One-Time Signature.)
Improvements (Winternitz) Save space with a checksum E.g. Only release a secret for bits of the digest that are ones. Now an adversary can change ones to zeros, but not vice versa. To fix this problem, append to the digest a binary representation of the number of zeroes in the digest. Now the public key size goes from 2n hashes to n + log n Use a hash chain to go from binary representation of the digest to base w. Public key for each digit is a secret hashed w times. To sign a digit, d, release the secret hashed w d times. Now the checksum is n w/log(w) <Sum of the Digits>. The Winternitz parameter w presents a time-space tradeoff.
Many Time Signatures (Merkle) PK = H(H0|| H1) H0 = H1 = H(H00|| H01) H(H10|| H11) H10 = H(PK2) H11 = H(PK3) H00 = H(PK0) H01 = H(PK1)
Many Time Signatures (Merkle) PK = H(H0|| H1) H0 = H1 = H(H00|| H01) H(H10|| H11) H10 = H(PK2) H11 = H(PK3) H00 = H(PK0) H01 = H(PK1) Signature: OTSsk1(m) || PK1 || H00|| H1
Key Generation Times and Certificate Chains With standard Merkle signature, you have to precompute the whole tree before you can sign anything! Allowing more signatures under one key has: Log overhead in signature length/signing time Linear overhead in key generation time. Solution, use the Merkle tree to sign the root of another Merkle tree. Taken to the extreme, this can enable stateless signatures. (More later)
XMSS and McGrews draft Both are IRTF drafts XMSS is a work item and McGrew s draft is a personal draft (I think.) XMSS has a standard model proof (second-preimage resistance.) McGrew s draft (Leighton-Micali signatures) has a random oracle proof. Leighton-Micali is old enough that it can t still be in patent, although I think XMSS is not patented. Importantly, both drafts are stateful. This might be ok for things like code signing, where strong version control is assumed, but will make trouble for Software processes where memory failure due to unexpected reboot is a real possibility. Online signing services that are duplicated on several systems. Etc.
SPHINCS (stateless hash-based signatures) Signature is structured like a cert-chain with many layers (12) of small Merkle Trees (32 nodes) Sample tree index randomly Use Few-Time Signature (HORST) rather than One-Time Signature to sign messages. (OTS is fine for signing Merkle Tree roots.) Signature size: 328,000 bits This compares to a typical size of 15,000 bits per layer for stateful schemes.
