Animal Survival – A Threat to Biodiversity

Biodiversity faces a critical threat as animal survival is endangered by factors like deforestation, poaching, and climate change. From the declining rainforest area to the endangered status of tigers, great apes, elephants, pandas, and polar bears, various species are at risk of extinction. The alarming rate of species loss emphasizes the urgent need for conservation efforts to protect our planet's rich ecosystem.

• Animal Survival
• Biodiversity
• Endangered Species
• Conservation
• Threat to Wildlife

grantra Follow

Uploaded on Feb 20, 2025 | 0 Views

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.

Presentation Transcript

1. Online Cryptography Course Dan Boneh Sigs. with special properties Fast one-time signatures and applications Dan Boneh

2. One-time signatures: definition Suppose signing key is used to sign a single message Can we give a simple (fast) construction SS=(Gen,S,V) ? pk Chal. Adv. A m1 M 1 S(sk,m1) (pk,sk) Gen (m, ) A wins if V(pk,m, ) = `accept and m m1 Security: for all efficient A, Adv1-SIG[A,SS] = Pr[ A wins] negl Dan Boneh

3. Application: authenticating streams 1. Next segment: secure one-time sigs secure many-time sigs 2. Super fast online signatures (later this module) 3. Authenticating a video stream: pk sk pk Too slow: signing every packet with sk Dan Boneh

4. Signing streams with fast one-time sigs (pk,sk): key-pair for a many-time signature scheme (Gen1T, S1T, V1T): secure one-time signature (fast) packet #1 packet #0 packet #2 sk (data0, pk1, 0) (data1, pk2, 1) (data2, pk3, 2) Packet #0: (pk1,sk1) Gen1T , 0 S (sk, (data0, pk1)) Packet #1: (pk2,sk2) Gen1T , 1 S1T(sk1, (data1, pk2)) Packet #2: (pk3,sk3) Gen1T , 2 S1T(sk2, (data2, pk3)) Dan Boneh

5. Recipient accepts packet #2 = (data2, pk3, 2) once it verifies 2 How does the recipient verify the signature 2 in packet #2? Accept if 0 and 1 were valid and: V1T( pk3, (data2, pk3), 2) = accept V( pk, (data2, pk3), 2) = accept V1T( pk2, (data2, pk3), 2) = accept V( pk2, (data2, pk3), 2) = accept

6. Authenticating streams Practical difficulties: Packet loss, out of order delivery Many solutions: see further reading Authenticating streams with a MAC: Harder, but can be done: TESLA Dan Boneh

7. End of Segment Dan Boneh

8. Online Cryptography Course Dan Boneh Sigs. with special properties Constructing fast one-time signatures Dan Boneh

9. One-time signatures Secure when sk only signs a single message Attacker: gets pk and can ask for sig. on any single m1 of her choice. should be unable to forge signature on m m1 This segment: one-time sigs from fast one-way functions (OWF) f: X Y is a OWF if (1) f(x) is efficiently computable, (2) hard to invert on random f(x) Examples: (1) f(x) = AES(x, 0128) , (2) f(x) = SHA256(x) key Dan Boneh

10. Lamport one-time signatures (simple) f: X Y a one-way function. Msg space: M = {0,1}256 Gen: generate 2 256 random elements in X sk f f f pk f Dan Boneh

11. Lamport one-time signatures (simple) f: X Y a one-way function. Msg space: M = {0,1}256 Gen: generate 2 256 random elements in X sk m = 0 1 1 0 1 S(sk, m): = (pre-images corresponding to bits of m) Dan Boneh

12. Lamport one-time signatures (simple) f: X Y a one-way function. Msg space: M = {0,1}256 Gen: generate 2 256 random elements in X X256(4KB) = m = 0 1 1 0 1 S(sk, m): = (pre-images corresponding to bits of m) Dan Boneh

13. Lamport one-time signatures (simple) f: X Y a one-way function. Msg space: M = {0,1}256 Gen: generate 2 256 random elements in X X256(4KB) = m = 0 1 1 0 1 pk V( pk, m, ): accept if all pre-images in match values in pk Dan Boneh

14. Very fast signature system. Will prove one-time security in a bit. Is it two-time secure? That is, if sk is used to sign two messages, can an attacker do an existential forgery? No, one-time security implies two-time security It depends on the one-way function used The attacker can ask for a signature on 0128 and on 1128. He gets all of sk which he can use to sign new messages.

15. Abstraction: cover free set systems 1 2 3 4 n S1, S2, , S2256 {1, ., n} Sets: Def: S = {S1, S2, , S2256 } is cover-free if Si Sjfor all i j Example: if all sets in S have the same size k then S is cover free Dan Boneh

16. Abstract Lamport signatures f: X Y a one-way function. Msg space: M = {0,1}256 S = {S1, S2, , S2256 } is cover-free over {1,..,n} H: {0,1}256 S a bijection (one-to-one) Gen: generate n random elements in X sk Xn n 1 f f f pk Yn 1 n Dan Boneh

17. Abstract Lamport signatures f: X Y a one-way function. Msg space: M = {0,1}256 S = {S1, S2, , S2256 } is cover-free over {1,..,n} H: {0,1}256 S a bijection (one-to-one) Gen: generate n random elements in X = pk Yn 1 n S(sk, m): = ( pre-images corresponding to elements of H(m) ) Dan Boneh

18. Why cover free? Suppose S were not cover free exists m1, m2 such that H(m1) H(m2) signature on m2 gives signature on m1 m1 = m2 = pk 1 n S(sk, m): = ( pre-images corresponding to elements of H(m) ) Dan Boneh

19. Security statement Thm: if f: X Y is one-way and S is cover-free then Lamport signatures (Lam) are one-time secure. A B: Adv1-SIG[A,Lam] n AdvOWF[B,f] Proving security: adversary (A) us (B) y=f(x) pk m1 Signature Forger 1 (m, ) x Dan Boneh

20. Proving security adversary us (B) y=f(x) pk m1 Signature Forger choose: i {1, ,n} x1, ,xn X 1 (m, ) x pk= f(x1) f(xi-1) y f(xi+1) f(xn) i H(m1) B can answer signature query i H(m) B gets f-1(y) So: B wins if i H(m) but i H(m1) Dan Boneh

21. Proving security adversary us (B) y=f(x) pk m1 Signature Forger choose: i {1, ,n} x1, ,xn X 1 (m, ) x pk= f(x1) f(xi-1) y f(xi+1) f(xn) S is cover-free H(m) not subset of H(m1) i* s.t. i* H(m) and i* H(m1) Then: Pr[i=i*] = 1/n Therefore: Adv[B,f] Pr[i=i*] Adv1-SIG[A,Lam] = (1/n) Adv1-SIG[A,Lam] Dan Boneh

22. Parameters (f: X Y where X = Y) S = {S1, S2, , S2256 } is cover-free over {1,..,n} In particular: S = (all subsets of {1, ,n} of size k ) pk Yn pk size = (n elements of Y) sig. size = (k elements of X) Msg-space = {0,1}256 |S| =(n choose k) 2256 To shrink signature size, choose small k example: k=32 n 3290 (large public-key) For optimal (sig-size + pk-size) choose n = 261, k = 123 (sig-size + pk-size) 1.5 256 elements of X (6KB) Dan Boneh

23. End of Segment Dan Boneh

24. Online Cryptography Course Dan Boneh Sigs. with special properties One-time signatures many-time signatures Dan Boneh

25. Review Recall: one-time signatures need not be 2-time secure example: Lamport signatures Goal: convert any one-time signature into a many-time signature Main tool: collision resistant hash functions Dan Boneh

26. Construction (Gen1T, S1T, V1T): secure one-time signature (fast) Four-time signature: (stateful version) Gen: ( pk0123, sk0123 ) Gen1T (pk01,sk01) (pk23,sk23) (pk2,sk2) (pk0,sk0) (pk1,sk1) (pk3,sk3) Dan Boneh

27. Construction (Gen1T, S1T, V1T): secure one-time signature (fast) Four-time signature: (stateful version) Gen: pk0123, 0123 S1T(sk, (pk01,pk23)) (pk01,sk01) (pk23,sk23) (pk2,sk2) (pk0,sk0) (pk1,sk1) (pk3,sk3) Dan Boneh

28. Construction (Gen1T, S1T, V1T): secure one-time signature (fast) Four-time signature: (stateful version) Gen: pk0123, 0123 (pk01, 01) (pk23, 23) (pk2,sk2) (pk0,sk0) (pk1,sk1) (pk3,sk3) Dan Boneh

29. Construction (Gen1T, S1T, V1T): secure one-time signature (fast) Four-time signature: (stateful version) pk0123, 0123 Sig. on msg m0: ( 0123, 01, 0, pk01, pk23, pk0, pk1 ) (pk01, 01) (pk23, 23) (pk2,sk2) (pk0, 0) (pk1,sk1) (pk3,sk3) m0 Dan Boneh

30. Construction (Gen1T, S1T, V1T): secure one-time signature (fast) Four-time signature: (stateful version) pk0123, 0123 Sig. on msg m1: ( 0123, 01, 1, pk01, pk23, pk0, pk1 ) (pk01, 01) (pk23, 23) (pk2,sk2) (pk0, 0) (pk1, 1) (pk3,sk3) m0 m1 Dan Boneh

31. Construction (Gen1T, S1T, V1T): secure one-time signature (fast) Four-time signature: (stateful version) pk0123, 0123 Sig. on msg m2: ( 0123, 23, 2, pk01, pk23, pk2, pk3 ) (pk01, 01) (pk23, 23) (pk2, 2) (pk0, 0) (pk1, 1) (pk3,sk3) m2 m0 m1 Dan Boneh

32. Construction (Gen1T, S1T, V1T): secure one-time signature (fast) Four-time signature: (stateful version) pk0123, 0123 Sig. on msg m3: ( 0123, 23, 3, pk01, pk23, pk2, pk3 ) (pk01, 01) (pk23, 23) (pk2, 2) (pk0, 0) (pk1, 1) (pk3, 3) Dan Boneh m3 m2 m0 m1

33. More generally: 2d-time signature Tree of depth d: Every signature contains d+1 one-time signatures along with associated pk s pk pk0pk1 Tree is generated on-the fly: Signer stores only d secret keys at a time Stateful signature: Signer maintains a counter indicating which leaf to use for signature Every leaf must only be used once! m2d-1 m0 Dan Boneh

34. Optimized 2d-time signatures Combined with Lamport signatures: collision resistant hash funs many-time signature With further optimizations: For 240signatures: (stateful) signature size is 5KB signing time is about the same as RSA signatures Recall: RSA sig size is 256 bytes (2048 bit RSA modulus) Dan Boneh

35. End of Segment Dan Boneh

36. Online Cryptography Course Dan Boneh Sigs. with special properties Super-fast online signatures Dan Boneh

37. Goals Problem: generating RSA, ECDSA, BLS signatures can be slow On low power devices sk Goal: Do heavy signature computation before message is known Quickly output signature once user supplies message Dan Boneh

38. Method 1: using one-time sigs (Gen, S, V): secure many-time signature (slow) (Gen1T, S1T, V1T): secure one-time signature (fast) slow Gen (pk,sk) PreSign(sk): (pk1T, sk1T) Gen1T , S(sk, pk1T) Sonline( ( , sk1T, pk1T) , m): 1T S1T (sk1T , m) output * Vonline( pk, m, *=(pk1T, , 1T)): accept if V(pk, pk1T, ) = V1T(pk1T, m, 1T) = accept fast (pk1T, , 1T) Dan Boneh

39. Method 1: using one-time sigs One-time sigs. fast-online sigs. Problem: Lamport results in very long signatures A more suitable one-time signature: Hard Dlog in group G secure one-time sigs. with fast signing Signature size: if |G|=p then signature is (r,s) (Zp)2 64 bytes How: see homework problem Dan Boneh

40. Better method: chameleon hash G: finite cyclic group of order p. g, h=g G generators. H(m,r) = gr hm G Define: Properties: H(m,r) can be efficiently evaluated H is collision resistant if Dlog in G is hard (collision = Dlogg(h) ) If is known: given m and tcan find r s.t. H(m,r) = ht r = (t-m) . Indeed: H(m,r) = gr hm= Dan Boneh

41. Fast online signatures (Gen, S, V): secure many-time signature (slow) G: finite cyclic group of order p. g, h=g G rand. generators slow Gen (pk,sk) , sk*= (sk, ) PreSign(sk*): random t Zp , S(sk, ht) Sonline( ( , , t,ht) , m): r ( , ht,r) (t-m) , output * fast Vonline( pk, m, *=( , ht,r)): accept if V(pk, ht) = accept and H(m,r) = ht Dan Boneh

42. Fast online signatures Shorter signatures than one-time sigs. method: Total overhead is only 64 bytes (vs. 128 bytes with 1-time sigs) Online signature time: one multiplication in Zp Security: A forger can be used to either (1) forge signatures for (Gen, S, V), or (2) find collisions on H(m,r) Dan Boneh

43. Fast online signatures have a fast online signing time. If we count the entire signing time (i.e. PreSign + Sign), would the time be better or worse than a standard signature like RSA? Online signatures are always faster than regular signatures The PreSign step uses a regular signatures, so overall they cannot be faster than a regular signature It depends on which online signature is used Note: signature verification time is always worse than regular sigs.

44. End of Segment Dan Boneh

45. Online Cryptography Course Dan Boneh Sigs. with special properties Blind signatures Dan Boneh

46. Problem: digital cash (centralized system) I am Alice: withdraw 1$ skbank Alice coinID {0,1}256 = Bank It s Alice! S(skbank, coinID) Is coinID spent? no (coinID, ) Alice anonymous channel (Tor) = pkbank Who did I talk to? For simplicity, assume only one bank and all coins worth 1$. Dan Boneh

47. Solution: blind signatures Goal: we want Bank to sign coinID , but without knowing coinID m Bank r R, m Blind(m, r) sk client Unblind( , r) Signer SignBlind(sk, m ) Where: (1) is a valid signature on m: V(pk, m, ) = accept (2) m Blind(m)is independent of m That is, m reveals no information about m Dan Boneh

48. Blind signatures: security New definition of existential forgery: adversary asks for q blind signatures, and outputs (q+1) message/signature pairs pk Chal. Adv. A mi i=1, ,q (pk,sk) Gen i SignBlind(sk,mi ) A wins if V(pk,mi, i) = `accept for all i=1, ,q+1 Security: for all efficient A, AdvBlind[A,SS] = Pr[ A wins] negl Dan Boneh

49. Blind signatures: applications Anonymous digital cash Anonymous voting systems Election results are known, but not who voted how Adaptive oblivious transfer (week 4) Dan Boneh

50. Simple Constructions: RSA and BLS BLS review: G finite group of order p with a pairing sk = Zp , pk = (g, g ) , H: M G S(sk, m) = H(m) G Independent of m m r Zp, m H(m) gr Bank sk= client / (g )r Signer (m ) Indeed: = (m ) / (g )r = Same method also works for RSA. Problem: security under strong assumption. Dan Boneh

Load More ...