Winternitz One-Time Signature Scheme (WOTS) Explained

Hash-Based Signatures Johannes Buchmann, Andreas H lsung Supported by DFG and DAAD Part V: Winternitz One-Time Signature Scheme (WOTS)

Winternitz OTS (WOTS) First idea: Full scheme: Security Proofs: Winternitz (Mer89) Even et al. (EGM96) Hevia & Micciancio (HM02) Dods et al. (DSS05) Requires collision-resistant undetectable one-way function family. WOTS$: Requires pseudorandom function family. Buchmann et al. (BDEH+11) WOTS+: Requires second preimage resistant undetectable one-way function family. H lsing (H l13)

Recap LD-OTS [Lam79] Message M = b1, ,bm, OWF H = n bit * SK sk1,0 sk1,1 skm,0 skm,1 H H H H H H PK pk1,0 pk1,1 pkm,0 pkm,1 b1 b2 bn Sig Mux Mux Mux sk1,b1 skm,bm

Trivial Optimization Message M = b1, ,bm, OWF H = n bit * SK sk1,0 sk1,1 skm,0 skm,1 H H H H H H PK pk1,0 pk1,1 pkm,0 pkm,1 Sig bm b1 bm b1 Mux Mux Mux Mux sigm,0 sig1,0 sigm,1 sig1,1

Non-trivial Optimization Message M = b1, ,bm, OWF H SK: sk1, ,skm,skm+1, ,sk2m PK: H(sk1), ,H(skm),H(skm+1), ,H(sk2m) Encode M: M =b1, ,bm, b1, , bm Sig: sigi= ski , if bi= 1 H(ski) , otherwise Checksum with bad performance!

Non-trivial Optimization, contd Message M = b1, ,bm, OWF H SK: sk1, ,skm,skm+1, ,skm+log m PK: H(sk1), ,H(skm),H(skm+1), ,H(skm+log m) Encode M: M =b1, ,bm, 1 ??? Sig: sigi= ski , if bi= 1 H(ski) , otherwise IF one bi is flipped from 1 to 0, another bj will flip from 0 to 1

WOTS Function Chain = ' n n n Function family: { } 1 , 0 { : } 1 , 0 { | } 1 , 0 { } F K F F n K = = 1 ' i i n ( ) ( ( )) ( , ) x } 1 , 0 { c x F c x F F F K Formerly: K K K K i times WOTS+ For w 2 select R R = (r1, , rw-1) K 1 ' n w n } 1 , 0 { , } 1 , 0 { ri ci(x) ci-1(x) = 1 i i ( ) ( ( ) ) c x F c x r F K K i c0(x) = x cw-1(x) c1(x) = ( ) FK x 1r

WOTS Function Chains = n } 1 , 0 { ( ) x c x x For define and WOTS: ) ( F x c i = ) ( x c i = 0 ( ( r )) c 1x ( ) K i ) F WOTS$: ( c x i 1 = ( ) ( ( ) ) c x F c x r WOTS+: 1 i K i i

WOTS+ Winternitz parameter w, security parameter n, message length m, function family } 1 , 0 { : { K n F = F F ' n n n } 1 , 0 { | } 1 , 0 { } K Key Generation: Compute l l , sample K, sample R R pk1= cw-1(sk1) c0(sk1) = sk1 c1(sk1) c1(skll) pkll= cw-1(skll) c0(skll) = skll

WOTS+ Signature generation M bll b1 b2 b3 b4 bm bm +1 bm +2 pk1= cw-1(sk1) c0(sk1) = sk1 C 1=cb1(sk1) Signature: = ( 1, , ll) pkll= cw-1(skll) c0(skll) = skll ll=cbll (skll)

WOTS+ Signature Verification Verifier knows: M, n, w, c bll b1 b2 b3 b4 bm bll 1+2 bm +1 c1( 1) pk1 c3( 1) =? 1 c2( 1) cw-1-b1( 1) Signature: = ( 1, , ll) pkll =? cw-1-bl l ( l l ) ll

WOTS Security Theorem (informally): W-OTS is strongly unforgeable under chosen message attacks if F F is a collision resistant, undetectable one-way function family. W-OTS$is existentially unforgeable under chosen message attacks if F F is a pseudorandom function family. W-OTS+is strongly unforgeable under chosen message attacks if F F is a 2nd-preimage resistant, undetectable one-way function family.

WOTS Sizes and Runtimes Lamport -Diffie WOTS WOTS$ WOTS+ Public Key Size l l 2b l l b (+b) ~ bm/log w l l b ~ bm/log w l l b ~ bm/log w l l b ( +(w-1)b ) ~ bm/log w l l b ~ bm/log w l l b ~ bm/log w 2bm ~ 2bm/log w l l 2b ~ 2bm/log w l l 2b ~ 2bm/log w Secret Key Size 2bm Signature Size bm Key Generation Time ll w ll w ll w ~ 2m ~ wm/log w ~wm/log w ~ wm/log w Security level b, Winternitz parameter w, Message Length m, l l = l l (w,m) ~ m / log w