P2P Multiple Secret Sharing P2P IP ISP Named Data Networking(NDN) NDN P2P Multiple Secret Sharing i

Size: px

Start display at page:

Download "P2P Multiple Secret Sharing P2P IP ISP Named Data Networking(NDN) NDN P2P Multiple Secret Sharing i"

かずきみつだ
7 years ago
Views:

2 P2P Multiple Secret Sharing P2P IP ISP Named Data Networking(NDN) NDN P2P Multiple Secret Sharing i

3 P2P Digital Right Management(DRM) DRM DRM P2P P2P Distributed Hash Table(DHT) P2P CGM :(k, n) :Multiple Secret Sharing Multiple Secret Sharing ii

................... 8 2.4 P2P CGM................... 8 2.4.1.............................. 8 2.4.2............................. 9 2.5 :(k, n)................. 10 2.5.1.................. 10 2.5.2.............. 11 2.

4 3 NDN Named Data Networking NDN NDN Content Firewall D cmd iii

4.1............................. 36 3.4.2............................. 38 3.5.................. 38 3.5.1 D cmd.................. 38 3.5.2................ 38 3.6..................................... 39 4 40 4.

5 % % % Interest packet Data packet NDN router iv

2 NDN router.............................. 30 3.3............................. 33 3.4................................ 33 3.5................................... 34 3.

6 v

7 1

8 P2P P2P ISP ASP P2P Content Delivery Network(CDN) CDN CDN CDN Google Google Youtube Google ISP ASP 1.2 ASP

9 1 3 P2P P2P IP Multiple Secret Sharing P2P ISP Named Data Networking(NDN) NDN P2P Content Firewall P2P Multiple Secret Sharing P2P 3 NDN 2 Secret Sharing Multiple Secret Sharing 3 NDN NDN Content Firewall P2P P2P Multiple Secret Sharing

10 2 P2P

11 2 P2P %P2P [1] [2] Youtube [3] [4] CGM(Consumer Generated Media) ISP 4 1 [5] CGM iphone 3.9G LTE P2P P2P [6] Sharecast [7] UG Live [8] P2P P2P CGM P2P Contents Delivery Network(CDN) [9] P2P P2P P2P CGM CGM P2P Einy OnDemand Skeedcast Windows Media Digital Rights Management(WMDRM) [10] CGM DRM CGM

12 2 P2P 6 Veoh P2P CGM P2P PPLive DRM [11] [12] P2P DRM CGM [13, 14] P2P CGM Multiple Secret Sharing 2.2 DRM 2.3 P2P 2.4 P2P Digital Right Management(DRM) DRM DRM DRM DRM WMDRM Fairplay DRM DRM

13 2 P2P 7 (3) DTCP DRM DRM DRM CGM DRM DRM CGM 2.3 P2P P2P P2P ( ) Hybrid P2P Super node P2P Pure P2P 3 Hybrid P2P Super node P2P Node Node Super node CGM Super node Pure P2P Pure P2P

14 2 P2P Distributed Hash Table(DHT) Pure P2P Distributed Hash Table(DHT) DHT Pastry [15] Chord [16] Kademlia [17] Pastry 10 P2P 4 DHT DHT ( ) DHT 2.4 P2P CGM P2P CGM 2.3 P2P CGM CGM 1 ID 2 3 ID DHT P2P (ID) ID IP DHT Pure P2P ID P2P ID

15 2 P2P 9 ID ID DHT ID ID (DRM) CGM (CGM ) CGM P2P CGM P2P CGM P2P 3. CGM P2P P2P P2P P2P CGM P2P (PKI)

16 2 P2P 10 CGM 2.5 :(k, n) 2.4 Shamir [18] Blakley [19] (k, n) (Secret Sharing Scheme) [13, 14] (k, n) n k : 1. P2P P2P DHT

17 2 P2P (k, n) n P2P 3. ID P2P ID DHT 5. P2P k P2P P2P k 1 P2P DHT 2.5.2

18 2 P2P : 2.1: % 10% - 60% (10% ) n 100 DHT 60 Pastry() ( 2.1) Overlay Weaver [20] P2P 10% P2P M/M/S(0) [21] PPLive [22] 21 ( 2.2) k 22

19 2 P2P 13 n k P2P n k k n P2P n P2P 2.6 :Multiple Secret Sharing 2.5 P2P n P2P Multiple Secret Sharing 1 P2P DHT ID P2P Multiple Secret Sharing Multiple Secret Sharing Multiple Secret Sharing Multiple Secret Sharing Scheme He Dawson [23] (k, n) Multiple Secret Sharing 1 Multiple Secret Sharing Duo Liu Multiple Secret Sharing [24] (k, n) Duo Liu Multiple Secret Sharing Duo Liu Bilinear self-pairing

20 2 P2P 14 q GF (q) E : y 2 = x 3 + ax + b ( a, b GF (q), 4a b 2 0 ) [24] P = (x 1, y 1 ) E P = (x 1, y 1 ) E Q = (x 2, y 2 ) E Q P P + Q = (x 3, y 3 ) x 3 = λ 2 x 1 x 2 y 3 = λ(x 1 x 3 ) y 1 (y 2 y 1 ) (x λ = 2 x 1 ), P Q; (3x 2 1 +a) (2y 1 ), P = Q. Bilinear self-pairing Lee Bilinear self-pairing [25] K 0 p E = E(K) K K K P E lp = 0 l E P l- lp = 0 P E(K) E(K)[l] E(K) l- (l 0) E(K)[l] E[l] l K char(k) 0 p (p l ) E[l] E[l] = Z l Z l G H E[l] E[l] G H E[l] P = a 1 G+b 1 H Q = a 2 G+b 2 H a 1, a 2, b 1, b 2 [0, l 1] α, β [0, l 1] E[l] E[l] E[l] L α,β (P, Q) = (a 1 b 2 a 2 b 1 )(αg + βh) α, β = D n {U 1, U 2,..., U n }

Bilinear self-pairing Lee Bilinear self-pairing [25] K 0 p E = E(K) K K K P E lp = 0 l E P l- lp = 0 P E(K) E(K)[l] E(K) l- (l 0) E(K)[l] E[l] l K char(k) 0 p

21 2 P2P : 1. D GF (q) E(GF (q)) q = p r p GF (q) E(GF (q)) 2. D l l t E[l] E(GF (q t )) 3. D {G, H} E[l] L α,β α, β [1, l 1] 4. D {E, q, l, t, αg + βh} P2P 5. D A : k 1 A = k (n 1) (n 1) 2 (n 1) k 1 n k 6. D 2k {ã j, b j } 1 j k ã j, b j [0, l 1] (1 j k)

22 2 P2P D (a 1, a 2,, a n ) T = A (ã 1, ã 2,, ã k ) T (b 1, b 2,, b n ) T = A ( b 1, b 2,, b k ) T 8. D 1 j n U j {a j, b j } : m {M 1, M 2,, M m } {M 1, M 2,, M m } i 1 i m

23 2 P2P D P k = ã k G + b k H 2. D c i, d i [0, l 1] Q i = c i G + d i H 3. D R i = L α,β (Q i, P k )+M i {c i, d i, R i } P2P {U u1, U u2,, U uk } i 1 i m j 1 j k 1. U uj D {a j, b j } 2. U uj D {E, q, l, t, αg + βh} M i {c i, d i, R i } 3. U uj Q i,j = L α,β (Q i, P uj ) P uj Q i P uj = a uj G + b uj H Q i = c i G + d i H 4. U uj Q i,j {M i } 1 i m i 1 i m j 1 i k 1. U uj Q i,j 2. k T i = y j Q i,j j=1 y j = k (u j u J ) J=1,J j 1 3. D {c i, d i, R i } M i = R i T i

24 2 P2P : 1. P2P 2. P2P ( 2.5) 3. k 1 P2P k 1 k 1

25 2 P2P (2.6.2 ) O(1) (2.6.3) 4 1 O(1) 6 1 O(1) 1 k 2 k O(k 2 ) Windows media DRM(WMDRM) ID 2KB [10] P2P 2.5 n P2P n DHT DHT 1 n DHT 1 DHT

26 2 P2P m O(mn) P2P n () P2P 1 DHT 1 m O((n+1)+m) = O(n+m) m CGM m DHT Kademlia Python2.5.2 M/M/S(0) [21] 20% 80% Kademlia key value Kademlia Network 2.2

27 2 P2P : Parameter k-bucket size 20 α 3 republish interval 60 min. expire interval 120 min. Number of nodes 1000 Number of malicious nodes 100 Number of contents 10 Number of shadows per content 100 Average online rate 20% 40% 60% Percentage of heavy users 20% Percentage of popular contents 20% Average online period 60 min. Usage period of each accessed content 10 min. Timeout of relaying delete requests 30 min. Number of contents chached on a node 4

28 2 P2P 22 k-bucket 10 Kademlia Network 2.2 Kademlia Network k-bucket Kademlia Network α Kademlia Petar [17] key-value expire expire ( ) 20% % republish () expire expire

29 2 P2P 23 Kademlia Publish lookup k-bucket expire P2P (30 ) republish 60 republish expire republish expire 3 lookup expire expire republish 90 expire expire : 20% 20% 40% 60%P2P

30 2 P2P : 40% 2.8: 60%

31 2 P2P lookup k-bucket %- 20% republish % republish Kademlia republish k % 20% republish k 40 40% republish 9 20% k 65 60% republish

32 2 P2P 26 k k-bucket lookup 2.9 DRM P2P CGM P2P (k, n) P2P (k, n) Multiple Secret Sharing (k, n) 2 P2P

33 3 NDN

34 3 NDN Named Data Networking(NDN) NDN P2P TCP/IP P2P CDN Content Pollution DDoS Location independent NDN Supervisor Application NDN 3.2 Named Data Networking NDN NDN NDN router Interest packet Data packet( 3.1 [26]) Packet NDN router LAN 3G/4G (face) ( 3.2)NDN Jacobson [26,27] NDN NDN router 3.3 User Application Interest packet NDN router Interest packet URL /u-tokyo.ac.jp/videos/hoge.mp4 Data packet VoIP

35 3 NDN : Interest packet Data packet Figure 1: Packets In the NDN Architecture. Interest packet /u-tokyo.ac.jp/voip/alice to bob/ v / s2 URL NDN achieved by conventions agreed between data producers and NDN router Interest packet versioning and segmentation. Name conventions are specific NDN router Interest packet Pending Interest Table(PIT) Forwarding Names do not Information needbase(fib) to be globally unique, 3.2.1althoughretrie uniqueness. /u-tokyo.ac.jp/videos/hoge.mp4 Names intended for Name local /u-tokyo.ac.jp/ communication may b -> faces 1,2 Name FIB face Interest only local routing (or local broadcast) to find corresponding d packet /u-tokyo.ac.jp/video/ -> faces 1 FIB To retrieve NDN router dynamically generated data, consumers must b FIB Interest packet Name for a desired piece of data without having previously seen Data packet algorithm Intrest allows producer packet FIB and consumer IP to arrive at the s and/or (2) consumers can retrieve datainterest based packet on partial nam PIT /parc/videos/widgeta.mpg and get back a data packet n FIB consumer OSPF [28] can BGP then [29] specify later segments and request them IP forwarding table [30] FIB by the first data packet and the naming convention agreed upo The naming system is the most important piece in the NDN particular, how to define and allocate top level names remain need be answered immediately, however; the opaqueness o Fi

36 3 NDN : NDN router NDN router Interest packet Data packet Data packet Data packet Data packet FIB NDN router Data packet NDN router Interest packet Data packet PIT Interest packet Data packet PIT Content Store Data packet Data packet Interest packet Data packet Interest packet Data packet Interest packet Data packet

37 3 NDN Interest packet NDN router Data packet Interest packet FIB Intrest packet (3.2.1 ) Data packet Interest packet NDN NDN 2.1 NDN Data packet NDN router Content Store Data packet Data packet Data packet VoIP IM NDN Data packet PKI [31] PGP Web of Trust [32] SDSI/SPKI [33 35] CRL OCSP [36] NDN Data packet Content Store IP NDN P2P NDN router Content Store NDN Content Firewall NDN router Packet Policy [26]

38 3 NDN 32 NDN NDN Interest Flooding Attacks Content Pollution Attacks Interest Flooding Attacks IP DDoS Interest packet Interest packet Name Name NDN router Name Interest packet Data packet Interest packet NDN router Content Firewall NDN Data packet Interest packet Data Flooding Attacks Content Pollution Attacks Interest packet Data packet Data packet NDN router NDN router FIB FIB Strategy Layer NDN router FIB User Application NDN router Medium Application Supervisor Supervisor Application 3 ( 3.3) NDN router face ( 3.2) Supervisor Application NDN router D per key.sec.super Medium Application User Application D per key.pub.super Alice key.sec.alice key.pub.alice E H key C E key (C) H(C) C name Content Firewall NDN router Content Firewall(3.2.2 )

39 3 NDN : 3.4: C C Alice User Application C D per Alice key.sec.alice E key.sec.alice ((C name ), H(C)) Interest packet D req ( 3.4) D req FIB face C NDN router D req D req Interest Flooding Attacks NDN face D req Supervisor Application Alice D req C Alice key.pub.alice D req C

40 3 NDN : 3.6: Alice C D per Data packet ( 3.4) D req D per Content Supervisor Application D per key.sec.super C H(C) D per Data packet Alice User Application D per key.pub.super D per Content C Name D per Content Content Name Interest packet D cmd FIB Medium Application ( 3.5) Medium Application D cmd D cmd D per D per key.pub.super User Application C Content Firewall Policy(3.2.2 ) Content Store C Data packet Medium Application NDN router FIB face Medium Application

41 3 NDN 35 face D cmd face D cmd D cmd ( 3.6) D cmd face Data packet D fin Interest packet D fin D cmd face ( 3.5, 3.6) Content Firewall Policy C Interest packet FIB Interest packet Medium Application face [26] Alice D fin D cmd D cmd Medium Application Content Firewall Policy C NDN routet Content Firewall C Alice Stakeholder Stakeholder Supervisor Supervisor D cmd Supervisor Application D req D cmd 3.4 Supervisor Application Medium Application 3.3 IP NDN NDN router ISP ASP NDN router Medium Application Supervisor Application NDN router IP NDN router Medium Application Medium Application 3.3 D cmd [37] Secret Sharing Alice C Bob C Alice C k n

42 3 NDN NDN Alice n S j (1 j n) 2. Alice S j (1 j n) Alice key.sec.alice NDN NDN (3.2.1 ) Data packet host ( host ) NDN Medium Application 3. Alice C Alice NDN key.sec.alice C key.sec.alice.c E key.sec.alice.c (C) NDN 4. Alice C key.pub.alice.c SP I key.pub.alice.c NDN 5. C Bob NDN E key.sec.alice.c (C) Aliice SP I key.pub.alice.c 6. Bob SP I key.pub.alice.c S j (1 j n) Interest packet I P S.j ( 3.8) 7. S j Medium Application I P S.j key.pub.alice.c S j P S j Data packet D P S.j ( 3.8) 8. Bob k D P S.j Multiple Secret Sharing Alice key.pub.alice.c k P S j key.pub.alice.c E key.sec.alice.c (C) Medium Application ID ISP (ISP name) ID(random ID) Interest packetss req ( 3.7) ID Medium Application ID Interest packet Medium Application Data packetss res Medium Application Interest packetrs req Interest packet Data packetrs res ( 3.7)

43 3 NDN : 3.8: ID N ISP Medium Application l N = l Medium Application N < l Medium Application k N > l Medium Application ID Medium Application Interest packet NDN D cmd 3.5.2

44 3 NDN Alice key.pub.alice.c 2. Alice P S j 3.5 D cmd D cmd Medium Application Content Store P S j Content Firewall Policy P S j Medium Application k 1 Medium Application key.pub.alice.c E key.sec.alice.c (C) C 3. Alice Alice D cmd Interest packet D cmd Flooding NDN Medium Application D cmd C D cmd PIT D cmd face Data packet D fin C key.sec.medium Interest packet Flooding D cmd Name domain D cmd Flooding NDN D cmd Interest Flooding Attacks D cmd D fin Medium Application PIT face D fin D fin D fin Medium Application D cmd Content Store D fin NDN Name Interest packet Interest Flooding Attacks (3.2.2 ) SS req (random ID) SS res Medium Application (random ID) Interest Flooding Attacks (random ID) Content Firewall SS req Name

45 3 NDN 39 /domain/content management/send shadow/ 3.6 NDN NDN router Multiple Secret Sharing

46 4

47 ISP ASP ASP P2P Multiple Secret Sharing P2P P2P ISP ASP ISP Named Data Networking(NDN) NDN Content Firewall Content Firewall P2P Multiple Secret Sharing 4.2 P2P P2P DHT Kademlia P2P

48 4 42 NDN Content Firewall NDN NDN

49 43

50 44 [1] Cisco Systems, Cisco visual networking index: Forecast and methodology, , ns341/ns525/ ns537/ns705/ns827/white_paper_c pdf [2] Cisco Systems, Hyperconnectivity and the approaching zettabyte era, ns705/ns827/vni_hyperconnectivity_wp.pdf [3] Google, Youtube, [4] (9), [5], [6] S. Androutsellis-Theotokis and D. Spinellis, A survey of peer-to-peer content distribution technologies, ACM Computing Surveys, vol.36, no.4, pp , Dec [7] Bitmedia and ANCL, Sharecast, [8] UG Live, [9] C. Labovitz, D. McPherson, and S. Iekel-Johnson, Internet Observatory 2009 Annual Report, The North American Network Operators, pp.1 32, Labovitz_ObserveReport_N47_Mon.pdf [10] Microsoft, [MS-DRM]: Digital Rights Management License Protocol Specification, EF66AF BB0-A41D-A4F81802D92C/[MS-DRM].pdf [11] V. Networks, Veoh video network, [12] PPLive Inc., Pptv,

51 4 45 [13] P2P,. IN, vol.108 no.458 pp [14] Y. Kawahara, L. Wang, and T. Asami, Resilient Suppressor Mechanism against Illegal Content Redistribution on Peer-to-Peer Video Sharing Networks, Communications (ICC), 2010 IEEE International Conference onieee, pp [15] A. Rowstron and P. Druschel, Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems, Middleware 2001Springer, pp [16] I. Stoica, R. Morris, D. Karger, M.F. Kaashoek, and H. Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communicationsacm, pp [17] P. Maymounkov and D. Mazieres, Kademlia: A peer-to-peer information system based on the xor metric, Peer-to-Peer Systems, pp.53 65, [18] A. Shamir, How to share a secret, Communications of the ACM, vol.22, no.11, pp , [19] G. BLAKLEY, Safeguarding cryptographic keys, National Computer ConferenceAFIPS Press., p [20] Overlay Weaver, : vol.47 no.12 pp [21] 1990 [22] Y. Huang, T.Z. Fu, D.-M. Chiu, J.C. Lui, and C. Huang, Challenges, design and analysis of a large-scale p2p-vod system, SIGCOMM Comput. Commun. Rev., vol.38, pp , Aug [23] J. He and E. Dawson, Multistage secret sharing based on one-way function, Electronics Letters, vol.30, no.19, pp , [24] D. Liu, D. Huang, P. Luo, and Y. Dai, New schemes for sharing points on an elliptic curve, Computers & Mathematics with Applications, vol.56, no.6, pp , 2008.

52 4 46 [25] H.S. Lee, A self-pairing map and its applications to cryptography* 1, Applied Mathematics and Computation, vol.151, no.3, pp , [26] V. Jacobson, D.K. Smetters, J.D. Thornton, M.F. Plass, N.H. Briggs, and R.L. Braynard, Networking named content, Proceedings of the 5th international conference on Emerging networking experiments and technologies - CoNEXT 09, p.1, ACM Press, New York, New York, USA, [27] L. Zhang, D. Estrin, J. Burke, and V. Jacobson, Named data networking (ndn) project, [28] J. Moy, OSPF Version 2, Technical report, RFC2328, April [29] Y. Rekhter, T. Li, and S. Hares, A Border Gateway Protocol 4(BGP-4), Technical report, RFC4271, Jan [30] Xin Zhao and Yaoqing Liu and Lan Wang and Beichuan Zhang, On the Aggregatability of Router Forwarding Tables, Proc. of the 29th conference on INFO- COM, pp.1 9, INFOCOM 10, March [31] D. Cooper, S. Santesson, S. Farrell, S. Boeyen, R. Housley, and W. Polk, Internet X. 509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile, Technical report, RFC5280, May [32] P.R. Zimmermann, The Official PGP User s Guide, MIT Press, [33] M. Abadi, On SDSI s Linked Local Name Spaces, Journal of Computer Security, vol.6(1-2), pp.3 21, [34] R. Rivest, B. Lampson, C.M. Ellison, B. Frantz, and S. Bell, SPKI Certificate Theory, Technical report, RFC2693, Sept [35] R.L. Rivest and B. Lampson, Sdsi-a simple distributed security infrastructure, Technical report, MIT Technical Report, [36] M. Myers, R. Ankney, A. Malpani, S. Galperin, and C. Adams, X.509 Internet Public Key Infrastructure Online Certificate Status Protocol-OCSP, Technical report, RFC2560, June [37] P2P Multiple Secret Sharing,. B, vol.94 no.10 pp

53 47 [P1], P2P Multiple Secret Sharing, B Vol.J94-B,No.10, pp , Oct [P2],,,, P2P Multiple Secret Sharing, Vol.110, No.128, MoMuC , pp.57-62, July 2010 [P3] Vol.110, No.449, IN , pp.85-90, March [P4] Vol.111, No.409, IN , pp.17-22, Jan [P5] P2P Multiple Secret Sharing B-7-30, Sept [P6], T. T. Quang,,, B-7-39, Sept [P7] B-7-13, March 2011.

スライド 1

スライド 1 WWW Request Client Data Server Request Data Client WWW Request Data Client Server Request Data Client WWW CPU Request Data Client Server Request Data Client Request Client Data Server Request Data Client