ieee sp 2004

Information about ieee sp 2004

Published on June 18, 2007

Author: Breezy

Source: authorstream.com

Content

On-The-Fly Verification of Rateless Erasure Codes:  On-The-Fly Verification of Rateless Erasure Codes Max Krohn (MIT CSAIL) Michael Freedman and David Mazières (NYU) On-The-Fly Verification of Rateless Erasure Codes:  On-The-Fly Verification of Rateless Erasure Codes Max Krohn (MIT CSAIL) Michael Freedman and David Mazières (NYU) Multicast Authentication: Dead/Exhausted The Setting:  The Setting A large file F Linux ISO (650MB) H(F) is available signed by Publisher (RedHat) A handful of untrusted sources/mirrors S1,…S8 A Handful of Senders:  A Handful of Senders The Setting:  The Setting A large file F Linux ISO (650MB) H(F) is available signed by Publisher (RedHat) A handful of untrusted sources S1,…S8 Their aggregate BW is limited A slew of receivers R1,...,R1,000,000 Version 81.3 just released! Want it Now! Three Desirable Properties:  Three Desirable Properties Sources Can Multicast Clients Get Fast Downloads Clients Can Verify Blocks On-the-Fly Receivers Get Fast, Verifiable Downloads:  Receivers Get Fast, Verifiable Downloads The trusted publisher (RedHat) Splits up F into n blocks Hashes all blocks Signs all hashes (or hash tree) Receivers: Download and verify hashes Download needed file blocks in parallel Everyone for Themselves:  R1 S1 S3 S4 S2 R3 R2 R4 R5 R6 R7 R8 R9 R10 R11 R12 R13 Everyone for Themselves Everyone For Themselves:  Everyone For Themselves Sources Can Multicast Clients Get Fast Downloads Clients Can Verify Blocks On-the-Fly Verifiable Multicast (BitTorrent):  R1 S1 S3 S4 S2 R3 R2 R4 R5 R6 R7 R8 R9 R10 R11 R12 R13 Verifiable Multicast (BitTorrent) Verifiable Multicast (BitTorrent):  Verifiable Multicast (BitTorrent) Sources Can Multicast Clients Get Fast Downloads Clients Can Verify Blocks On-the-Fly Multicast With Erasure Codes:  Multicast With Erasure Codes Sources erasure encode the file F n blocks blocks F Multicast With Erasure Codes:  Multicast With Erasure Codes Sources erasure encode the file F Receivers collect blocks and decode n blocks blocks 1.03n blocks n blocks F F … … … … … Multicast With Erasure Codes:  R1 S1 S3 S4 S2 R3 R2 R4 R5 R6 R7 R8 R9 R10 R11 R12 R13 Multicast With Erasure Codes Multicast With Erasure Codes:  Multicast With Erasure Codes Bullet [SOSP 2003] SplitStream [SOSP 2003] Big Downloads [IPTPS 2003] Informed Content Delivery [SIGCOMM 2002] Receivers Cannot Verify Content:  R1 S1 S3 S4 S2 Receivers Cannot Verify Content ? ? ? ? ? ? ? ? ? ? ? ? ? ? Receivers Cannot Verify Content:  Receivers Cannot Verify Content R1 S1 S3 S4 S2 ? ? ? ? ? ? ? ? ? ? Multicast With Erasure Codes:  Multicast With Erasure Codes Sources Can Multicast Clients Get Fast Downloads Clients Can Verify Blocks On-the-Fly Multicast With Erasure Codes:  Multicast With Erasure Codes Sources Can Multicast Clients Get Fast Downloads Clients Can Verify Blocks On-the-Fly What is the Attack Goal?:  What is the Attack Goal? To corrupt the file. To waste bandwidth. R S1 S3 S2 How To Attack?:  How To Attack? Send correct blocks but with skewed distributions. 'Distribution Attack' Send incorrect blocks 'Pollution Attack' Karlof et al. [NDSS ’04] R S1 S3 S2 Properties of a Solution to Pollution:  Properties of a Solution to Pollution OK: Receivers can tell good from bad. Much better: Receivers can finger bad blocks as they arrive. R S1 S3 S2 CONTRIBUTION Outline:  Outline Introduction Review of LT Codes Strawman #1 Strawman #2 Efficiently Catching Bad Blocks as They Arrive LT-Codes [Luby, FOCS 2002]:  LT-Codes [Luby, FOCS 2002] b1 b2 b3 b4 b5 F= n=5 input blocks LT-Codes – How To Encode:  LT-Codes – How To Encode b1 b2 b3 b4 b5 c1 Pick degree d1 from a pre-specified distribution. (d1=2) Select d1 input blocks uniformly at random. (Pick b1 and b4 ) Compute their sum. Output E(F)= F= LT-Codes – How To Encode (cont’d):  LT-Codes – How To Encode (cont’d) b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= How To Decode:  How To Decode b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= How To Decode:  How To Decode b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= How To Decode:  How To Decode b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= How To Decode:  b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= How To Decode How To Decode:  How To Decode b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= b5 b5 b5 How To Decode:  How To Decode b1 b2 b3 b4 b5 c1 c2 c3 c5 c6 c7 E(F)= F= b5 b5 How To Decode:  How To Decode b1 b2 b3 b4 b5 c1 c2 c3 c5 c6 c7 E(F)= F= b5 b5 How To Decode:  How To Decode b1 b2 b3 b4 b5 c1 c2 c3 c5 c6 c7 E(F)= F= b5 b5 How To Decode:  How To Decode b1 b2 b3 b4 b5 c1 c2 c3 c5 c6 c7 E(F)= F= b5 b5 b2 b2 How To Decode:  How To Decode b1 b2 b3 b4 b5 c1 c2 c3 c5 c6 c7 E(F)= F= b5 b5 b2 b2 Outline:  Outline Introduction Review of LT Codes Strawman #1 Simple Solution To Tell Good Blocks From Bad Strawman #2 Efficiently Catching Bad Blocks as They Arrive “Smart Decoder” for LT-Codes:  'Smart Decoder' for LT-Codes b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= “Smart Decoder” for LT-Codes:  'Smart Decoder' for LT-Codes b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= “Smart Decoder” for LT-Codes:  'Smart Decoder' for LT-Codes b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= “Smart Decoder” for LT-Codes:  'Smart Decoder' for LT-Codes b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= “Smart Decoder” for LT-Codes:  'Smart Decoder' for LT-Codes b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= “Smart Decoder” for LT-Codes:  'Smart Decoder' for LT-Codes b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= b5 b5 b5 “Smart Decoder” for LT-Codes:  'Smart Decoder' for LT-Codes b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= b5 b5 b5 “Smart Decoder” for LT-Codes:  'Smart Decoder' for LT-Codes b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= b5 b5 b5 X “Smart Decoder” for LT-Codes:  'Smart Decoder' for LT-Codes b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= b5 b5 b5 X “Smart Decoder” for LT-Codes:  'Smart Decoder' for LT-Codes b1 b2 b3 b4 b5 c1 c2 c3 c4 c5 c6 c7 E(F)= F= b5 b5 b5 “Smart Decoder:” Problem:  'Smart Decoder:' Problem Data collected from 50 random Online encodings of a 10,000 block file. Outline:  Outline Introduction Review of LT Codes Strawman #1 Strawman #2 Hashing/Signing Encoded Blocks Efficiently Catching the Bad as They Arrive Hashing/Signing Encoded Blocks:  Hashing/Signing Encoded Blocks Trusted Publisher (RedHat) Picks e, computes e·n encoded blocks Hashes all encoded blocks Signs the hashes. n blocks e·n blocks F Hashing/Signing Encoded Blocks:  Hashing/Signing Encoded Blocks Expansion factor e should be big to avoid duplicate blocks. e should be small to make crypto overhead acceptable. Our analysis shows there’s no 'sweet spot'. Hashing/Signing Encoded Blocks:  Hashing/Signing Encoded Blocks Expansion factor e should be big to avoid duplicate blocks. e should be small to make crypto overhead acceptable. Our analysis shows there’s no 'sweet spot'. e.g., best case bandwidth requirements: +5% e.g., generating hashes is very expensive as e gets large. Outline:  Outline Introduction Review of LT Codes Strawman #1 Strawman #2 Efficiently Catching the Bad as They Arrive Best of Both Worlds :  Best of Both Worlds Goal: Crypto overhead of one hash for every block in the input file (Strawman #1) Verify blocks as they arrive (Strawman #2) Idea: Distribute hashes of file blocks, and use them to verify encoded blocks. Need a better hash function. Insight: Homomorphic Hashing:  Insight: Homomorphic Hashing Assume function h exists such that: is homomorphic: is a CRHF: Homomorphic Hashing: Intuition:  Homomorphic Hashing: Intuition R receives the block c b2 b5 c Homomorphic Hashing: Intuition:  Homomorphic Hashing: Intuition c b2 b5 c R receives the block Homomorphic Hashing: Intuition:  Homomorphic Hashing: Intuition c b2 b5 c R receives the block Homomorphic Hashing: Intuition:  Homomorphic Hashing: Intuition R receives the block Homomorphic Hashing: Intuition:  Homomorphic Hashing: Intuition Property 1 R receives the block Homomorphic Hashing: Intuition:  Homomorphic Hashing: Intuition Property 1 Property 2 R receives the block Homomorphic Hashing: Protocol:  Homomorphic Hashing: Protocol R receives the block Compute h(c) If Accept block; mark as valid else Suspect sender of being bad guy, and switch. Homomorphic Hashing: Protocol:  Homomorphic Hashing: Protocol R receives the block Compute h(c) If Accept block; mark as valid else Suspect sender of being bad guy, and switch. Can such an h possibly exist? Homomorphic Hashing: Related Work:  Homomorphic Hashing: Related Work DLog-Based CRHF Pederson Commitment [CRYPTO ’91] Chaum et al. [CRYPTO ’91] One-Way Accumulators Benaloh and de Mare [EUROCRYPT ’93] Barić and Pfitzmann [EUROCRYPT ’93] Incremental Hashing Bellare et al. [CRYPTO ’94] Homomorphic Signatures Micali and Rivest [RSA ’02] Johnson et al. [RSA ’02] Mechanics of Homomorphic Hashing:  Mechanics of Homomorphic Hashing Discrete Log Hash Pick 1024-bit prime p and 256-bit prime q, q divides (p-1) Pick from 512 generators of order q: Write F as elements in F= 256-bit 'fragment' 16K 'block' How to Encode (example):  How to Encode (example) How To DLog Hash:  How To DLog Hash Hashes are elements in (128 bytes big) Hash reduces 16K block by a factor of 128 How To DLog Hash:  How To DLog Hash Hashes are elements in (128 bytes big) Hash reduces 16K block by a factor of 128 +1% overhead DLog-Hash: Key Property:  DLog-Hash: Key Property Note that: DLog-Hash: Key Property:  DLog-Hash: Key Property Note that: Goal achieved! “This Seems Really Expensive”:  'This Seems Really Expensive' Key Optimizations:  Key Optimizations Hash Generation Each publisher picks her own parameters, compute with 1 exponentiation (not 512) Hash Verification Receiver verifies hashes probabilistically and in batches. Bellare et al. [EUROCRYPT ’98] Much Better:  Much Better Homomorphic Hashing: Key Points:  Homomorphic Hashing: Key Points Key Algebraic Feature Homomorphism: Receivers can compose hashes the way encoders sum file blocks. Can check encoded blocks as they arrive. Fast Can be optimized to achieve good generation and verification throughputs Provably Secure As hard as discrete log (SHA1/MD5 not needed) Conclusion:  Conclusion Sources Can Multicast Clients Get Fast Downloads Clients Can Verify Blocks On-the-Fly Thank you.:  Thank you. Now accepting questions.

Related presentations


Other presentations created by Breezy

Plant Anatomy
03. 01. 2008
0 views

Plant Anatomy

Learning Long Division
15. 06. 2007
0 views

Learning Long Division

ADO Net
24. 10. 2007
0 views

ADO Net

Ch 2 Chemistry of Life
05. 01. 2008
0 views

Ch 2 Chemistry of Life

REORGANIZATION
27. 09. 2007
0 views

REORGANIZATION

Enhanced Fujita Scale 6 23 04
05. 10. 2007
0 views

Enhanced Fujita Scale 6 23 04

severe convection punkka
07. 10. 2007
0 views

severe convection punkka

lsad07 psp
09. 10. 2007
0 views

lsad07 psp

idioms1
10. 10. 2007
0 views

idioms1

SabadosCiencia2006
13. 10. 2007
0 views

SabadosCiencia2006

Rousset EID06
19. 10. 2007
0 views

Rousset EID06

TheodoreRoosevelt
22. 10. 2007
0 views

TheodoreRoosevelt

Timss
17. 10. 2007
0 views

Timss

Wynn ASA 2000
04. 10. 2007
0 views

Wynn ASA 2000

aas strom
29. 08. 2007
0 views

aas strom

element connections
29. 08. 2007
0 views

element connections

hwr clustering
29. 08. 2007
0 views

hwr clustering

Pov map 20060717 1
29. 11. 2007
0 views

Pov map 20060717 1

CONSTRUCTING BUD VASES ADN BOWS
11. 12. 2007
0 views

CONSTRUCTING BUD VASES ADN BOWS

nobel talk
15. 10. 2007
0 views

nobel talk

18 FOSIS
24. 10. 2007
0 views

18 FOSIS

Lec 08 FO1 06 Urbanisation
01. 11. 2007
0 views

Lec 08 FO1 06 Urbanisation

America vs The World
22. 10. 2007
0 views

America vs The World

Vasco Da Gama Slide Show
07. 11. 2007
0 views

Vasco Da Gama Slide Show

Fliess
15. 11. 2007
0 views

Fliess

01 threat
19. 11. 2007
0 views

01 threat

Konsolen
21. 11. 2007
0 views

Konsolen

the dancers
23. 11. 2007
0 views

the dancers

Probil
26. 11. 2007
0 views

Probil

UNE Benz
27. 11. 2007
0 views

UNE Benz

Galaxies
29. 08. 2007
0 views

Galaxies

DB2 XML DatabaseFINAL
23. 10. 2007
0 views

DB2 XML DatabaseFINAL

akzonobel
15. 10. 2007
0 views

akzonobel

ilana
29. 08. 2007
0 views

ilana

lauter
07. 11. 2007
0 views

lauter

GradSch GPOs
04. 10. 2007
0 views

GradSch GPOs

PHYS402 01
16. 10. 2007
0 views

PHYS402 01

cry beloved
02. 08. 2007
0 views

cry beloved

curtis
02. 08. 2007
0 views

curtis

Chaplet of Divine Mercy
02. 08. 2007
0 views

Chaplet of Divine Mercy

CS583 opinion mining
02. 08. 2007
0 views

CS583 opinion mining

A TIME FOR ANDREW Pres 2
02. 08. 2007
0 views

A TIME FOR ANDREW Pres 2

arthur powerpoint 11 20 03
02. 08. 2007
0 views

arthur powerpoint 11 20 03

cheryl toner ific
02. 08. 2007
0 views

cheryl toner ific

bats
02. 08. 2007
0 views

bats

23 stavros thurs
02. 08. 2007
0 views

23 stavros thurs

aas04 jeff
29. 08. 2007
0 views

aas04 jeff

moustakis
29. 08. 2007
0 views

moustakis

irsurveys07
29. 08. 2007
0 views

irsurveys07

venice oct03
29. 08. 2007
0 views

venice oct03

Office of Homeleand Security
29. 10. 2007
0 views

Office of Homeleand Security

agn presentation 102106
29. 08. 2007
0 views

agn presentation 102106

ReginaSchulteLadbeck 042104
29. 08. 2007
0 views

ReginaSchulteLadbeck 042104

Weingarten
03. 01. 2008
0 views

Weingarten

Presentation NASDAQ
24. 02. 2008
0 views

Presentation NASDAQ

nov retail ebony
24. 02. 2008
0 views

nov retail ebony

APAsymp04AIDMAN
02. 08. 2007
0 views

APAsymp04AIDMAN

Ray Flores Roadmap
04. 03. 2008
0 views

Ray Flores Roadmap

Beloved
02. 08. 2007
0 views

Beloved

2004 4050S1 11 Levin
02. 08. 2007
0 views

2004 4050S1 11 Levin

Konstantinidis
29. 09. 2007
0 views

Konstantinidis

Qin and Han Dynasties
25. 03. 2008
0 views

Qin and Han Dynasties

andy powell presentation
02. 08. 2007
0 views

andy powell presentation

arena rome minier
13. 11. 2007
0 views

arena rome minier

Presentation010605
10. 04. 2008
0 views

Presentation010605

03edclark lecture
13. 04. 2008
0 views

03edclark lecture

richard mushotzky
29. 08. 2007
0 views

richard mushotzky

Lawrence D Boston 2006
14. 04. 2008
0 views

Lawrence D Boston 2006

DMCH13
16. 04. 2008
0 views

DMCH13

ERates
17. 04. 2008
0 views

ERates

JHAN 14
18. 04. 2008
0 views

JHAN 14

4884061 firstfileFILE
22. 04. 2008
0 views

4884061 firstfileFILE

ppt26
23. 12. 2007
0 views

ppt26

Operations
28. 04. 2008
0 views

Operations

CH10 Outline
07. 04. 2008
0 views

CH10 Outline

CIM research
30. 04. 2008
0 views

CIM research

komossa
29. 08. 2007
0 views

komossa

icws 2006 3
18. 06. 2007
0 views

icws 2006 3

ICTP intro
18. 06. 2007
0 views

ICTP intro

human mating beh 2005
18. 06. 2007
0 views

human mating beh 2005

IMDS CIESP
14. 11. 2007
0 views

IMDS CIESP

welch adv camp july05
02. 10. 2007
0 views

welch adv camp july05

Glycosylation
15. 06. 2007
0 views

Glycosylation

Making a Story Board
15. 06. 2007
0 views

Making a Story Board

Story Literary Elements
15. 06. 2007
0 views

Story Literary Elements

Life Cycle of Plants and Animals
15. 06. 2007
0 views

Life Cycle of Plants and Animals

Session1Alila
02. 11. 2007
0 views

Session1Alila

beetleborers
02. 01. 2008
0 views

beetleborers

2006 IADB
10. 10. 2007
0 views

2006 IADB

robo wk1
03. 01. 2008
0 views

robo wk1

Rosemary Panama
22. 10. 2007
0 views

Rosemary Panama

ec06nicapan
25. 10. 2007
0 views

ec06nicapan

Allies Pre Training Module
02. 08. 2007
0 views

Allies Pre Training Module

Carmona
30. 12. 2007
0 views

Carmona

TheSuccessofSingapor e2006
27. 03. 2008
0 views

TheSuccessofSingapor e2006

Advisory Board Presentation
02. 08. 2007
0 views

Advisory Board Presentation

Cameron SAS44 A Century of OA
27. 02. 2008
0 views

Cameron SAS44 A Century of OA

dubrovnik
16. 10. 2007
0 views

dubrovnik

sprfett
07. 01. 2008
0 views

sprfett

mccune albright syndrome
15. 10. 2007
0 views

mccune albright syndrome

michael soendermann 2007
18. 10. 2007
0 views

michael soendermann 2007

astro12Summer12
29. 08. 2007
0 views

astro12Summer12

familyweek1
19. 02. 2008
0 views

familyweek1