[go: up one dir, main page]

KR100562982B1 - 브로드캐스트 암호화 시스템에서 트레이터 수신기들을추적하기 위한 방법 - Google Patents

브로드캐스트 암호화 시스템에서 트레이터 수신기들을추적하기 위한 방법 Download PDF

Info

Publication number
KR100562982B1
KR100562982B1 KR1020037009629A KR20037009629A KR100562982B1 KR 100562982 B1 KR100562982 B1 KR 100562982B1 KR 1020037009629 A KR1020037009629 A KR 1020037009629A KR 20037009629 A KR20037009629 A KR 20037009629A KR 100562982 B1 KR100562982 B1 KR 100562982B1
Authority
KR
South Korea
Prior art keywords
subset
trader
receiver
key
receivers
Prior art date
Application number
KR1020037009629A
Other languages
English (en)
Other versions
KR20030085126A (ko
Inventor
제프리 부르스 로츠스피치
달리트 나오르
시몬 나오르
Original Assignee
인터내셔널 비지네스 머신즈 코포레이션
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 인터내셔널 비지네스 머신즈 코포레이션 filed Critical 인터내셔널 비지네스 머신즈 코포레이션
Publication of KR20030085126A publication Critical patent/KR20030085126A/ko
Application granted granted Critical
Publication of KR100562982B1 publication Critical patent/KR100562982B1/ko

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
    • G—PHYSICS
    • G11—INFORMATION STORAGE
    • G11B—INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER
    • G11B20/00—Signal processing not specific to the method of recording or reproducing; Circuits therefor
    • G11B20/00086—Circuits for prevention of unauthorised reproduction or copying, e.g. piracy
    • G—PHYSICS
    • G11—INFORMATION STORAGE
    • G11B—INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER
    • G11B20/00—Signal processing not specific to the method of recording or reproducing; Circuits therefor
    • G11B20/00086—Circuits for prevention of unauthorised reproduction or copying, e.g. piracy
    • G11B20/0021—Circuits for prevention of unauthorised reproduction or copying, e.g. piracy involving encryption or decryption of contents recorded on or reproduced from a record carrier
    • G—PHYSICS
    • G11—INFORMATION STORAGE
    • G11B—INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER
    • G11B20/00—Signal processing not specific to the method of recording or reproducing; Circuits therefor
    • G11B20/00086—Circuits for prevention of unauthorised reproduction or copying, e.g. piracy
    • G11B20/0021—Circuits for prevention of unauthorised reproduction or copying, e.g. piracy involving encryption or decryption of contents recorded on or reproduced from a record carrier
    • G11B20/00217—Circuits for prevention of unauthorised reproduction or copying, e.g. piracy involving encryption or decryption of contents recorded on or reproduced from a record carrier the cryptographic key used for encryption and/or decryption of contents recorded on or reproduced from the record carrier being read from a specific source
    • G11B20/00224—Circuits for prevention of unauthorised reproduction or copying, e.g. piracy involving encryption or decryption of contents recorded on or reproduced from a record carrier the cryptographic key used for encryption and/or decryption of contents recorded on or reproduced from the record carrier being read from a specific source wherein the key is obtained from a remote server
    • G—PHYSICS
    • G11—INFORMATION STORAGE
    • G11B—INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER
    • G11B20/00—Signal processing not specific to the method of recording or reproducing; Circuits therefor
    • G11B20/00086—Circuits for prevention of unauthorised reproduction or copying, e.g. piracy
    • G11B20/0021—Circuits for prevention of unauthorised reproduction or copying, e.g. piracy involving encryption or decryption of contents recorded on or reproduced from a record carrier
    • G11B20/00217—Circuits for prevention of unauthorised reproduction or copying, e.g. piracy involving encryption or decryption of contents recorded on or reproduced from a record carrier the cryptographic key used for encryption and/or decryption of contents recorded on or reproduced from the record carrier being read from a specific source
    • G11B20/00246—Circuits for prevention of unauthorised reproduction or copying, e.g. piracy involving encryption or decryption of contents recorded on or reproduced from a record carrier the cryptographic key used for encryption and/or decryption of contents recorded on or reproduced from the record carrier being read from a specific source wherein the key is obtained from a local device, e.g. device key initially stored by the player or by the recorder
    • G—PHYSICS
    • G11—INFORMATION STORAGE
    • G11B—INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER
    • G11B20/00—Signal processing not specific to the method of recording or reproducing; Circuits therefor
    • G11B20/00086—Circuits for prevention of unauthorised reproduction or copying, e.g. piracy
    • G11B20/0021—Circuits for prevention of unauthorised reproduction or copying, e.g. piracy involving encryption or decryption of contents recorded on or reproduced from a record carrier
    • G11B20/00217—Circuits for prevention of unauthorised reproduction or copying, e.g. piracy involving encryption or decryption of contents recorded on or reproduced from a record carrier the cryptographic key used for encryption and/or decryption of contents recorded on or reproduced from the record carrier being read from a specific source
    • G11B20/00253—Circuits for prevention of unauthorised reproduction or copying, e.g. piracy involving encryption or decryption of contents recorded on or reproduced from a record carrier the cryptographic key used for encryption and/or decryption of contents recorded on or reproduced from the record carrier being read from a specific source wherein the key is stored on the record carrier
    • G—PHYSICS
    • G11—INFORMATION STORAGE
    • G11B—INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER
    • G11B20/00—Signal processing not specific to the method of recording or reproducing; Circuits therefor
    • G11B20/00086—Circuits for prevention of unauthorised reproduction or copying, e.g. piracy
    • G11B20/0021—Circuits for prevention of unauthorised reproduction or copying, e.g. piracy involving encryption or decryption of contents recorded on or reproduced from a record carrier
    • G11B20/00485—Circuits for prevention of unauthorised reproduction or copying, e.g. piracy involving encryption or decryption of contents recorded on or reproduced from a record carrier characterised by a specific kind of data which is encrypted and recorded on and/or reproduced from the record carrier
    • G11B20/00492—Circuits for prevention of unauthorised reproduction or copying, e.g. piracy involving encryption or decryption of contents recorded on or reproduced from a record carrier characterised by a specific kind of data which is encrypted and recorded on and/or reproduced from the record carrier wherein content or user data is encrypted
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
    • H04L9/0816—Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for subsequent use
    • H04L9/0819—Key transport or distribution, i.e. key establishment techniques where one party creates or otherwise obtains a secret value, and securely transfers it to the other(s)
    • H04L9/083—Key transport or distribution, i.e. key establishment techniques where one party creates or otherwise obtains a secret value, and securely transfers it to the other(s) involving central third party, e.g. key distribution center [KDC] or trusted third party [TTP]
    • H04L9/0833—Key transport or distribution, i.e. key establishment techniques where one party creates or otherwise obtains a secret value, and securely transfers it to the other(s) involving central third party, e.g. key distribution center [KDC] or trusted third party [TTP] involving conference or group key
    • H04L9/0836—Key transport or distribution, i.e. key establishment techniques where one party creates or otherwise obtains a secret value, and securely transfers it to the other(s) involving central third party, e.g. key distribution center [KDC] or trusted third party [TTP] involving conference or group key using tree structure or hierarchical structure
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
    • H04L9/0891—Revocation or update of secret information, e.g. encryption key update or rekeying
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N21/00—Selective content distribution, e.g. interactive television or video on demand [VOD]
    • H04N21/20—Servers specifically adapted for the distribution of content, e.g. VOD servers; Operations thereof
    • H04N21/25—Management operations performed by the server for facilitating the content distribution or administrating data related to end-users or client devices, e.g. end-user or client device authentication, learning user preferences for recommending movies
    • H04N21/266—Channel or content management, e.g. generation and management of keys and entitlement messages in a conditional access system, merging a VOD unicast channel into a multicast channel
    • H04N21/26606—Channel or content management, e.g. generation and management of keys and entitlement messages in a conditional access system, merging a VOD unicast channel into a multicast channel for generating or managing entitlement messages, e.g. Entitlement Control Message [ECM] or Entitlement Management Message [EMM]
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N21/00—Selective content distribution, e.g. interactive television or video on demand [VOD]
    • H04N21/40—Client devices specifically adapted for the reception of or interaction with content, e.g. set-top-box [STB]; Operations thereof
    • H04N21/41—Structure of client; Structure of client peripherals
    • H04N21/418—External card to be used in combination with the client device, e.g. for conditional access
    • H04N21/4181—External card to be used in combination with the client device, e.g. for conditional access for conditional access
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N21/00—Selective content distribution, e.g. interactive television or video on demand [VOD]
    • H04N21/40—Client devices specifically adapted for the reception of or interaction with content, e.g. set-top-box [STB]; Operations thereof
    • H04N21/43—Processing of content or additional data, e.g. demultiplexing additional data from a digital video stream; Elementary client operations, e.g. monitoring of home network or synchronising decoder's clock; Client middleware
    • H04N21/433—Content storage operation, e.g. storage operation in response to a pause request, caching operations
    • H04N21/4331—Caching operations, e.g. of an advertisement for later insertion during playback
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N21/00—Selective content distribution, e.g. interactive television or video on demand [VOD]
    • H04N21/40—Client devices specifically adapted for the reception of or interaction with content, e.g. set-top-box [STB]; Operations thereof
    • H04N21/45—Management operations performed by the client for facilitating the reception of or the interaction with the content or administrating data related to the end-user or to the client device itself, e.g. learning user preferences for recommending movies, resolving scheduling conflicts
    • H04N21/462—Content or additional data management, e.g. creating a master electronic program guide from data received from the Internet and a Head-end, controlling the complexity of a video stream by scaling the resolution or bit-rate based on the client capabilities
    • H04N21/4623—Processing of entitlement messages, e.g. ECM [Entitlement Control Message] or EMM [Entitlement Management Message]
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N7/00—Television systems
    • H04N7/16—Analogue secrecy systems; Analogue subscription systems
    • H04N7/167—Systems rendering the television signal unintelligible and subsequently intelligible
    • H04N7/1675—Providing digital key or authorisation information for generation or regeneration of the scrambling sequence
    • G—PHYSICS
    • G11—INFORMATION STORAGE
    • G11B—INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER
    • G11B2220/00—Record carriers by type
    • G11B2220/20—Disc-shaped record carriers
    • G11B2220/25—Disc-shaped record carriers characterised in that the disc is based on a specific recording technology
    • G11B2220/2537—Optical discs
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
    • H04L2209/60—Digital content management, e.g. content distribution
    • H04L2209/601—Broadcast encryption
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
    • H04L2209/60—Digital content management, e.g. content distribution
    • H04L2209/606—Traitor tracing

Landscapes

  • Engineering & Computer Science (AREA)
  • Signal Processing (AREA)
  • Computer Security & Cryptography (AREA)
  • Multimedia (AREA)
  • Databases & Information Systems (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Two-Way Televisions, Distribution Of Moving Picture Or The Like (AREA)
  • Storage Device Security (AREA)
  • Electrochromic Elements, Electrophoresis, Or Variable Reflection Or Absorption Elements (AREA)

Abstract

브로드캐스트 암호 시스템에서 트레이터 수신기들을 추적하는 방법이 개시된다. 상기 방법은 시스템내에서 수신기들을 나타내는 다수의 부집합들을 거짓키를 이용하여 인코드하는 단계를 포함한다. 부집합들은 부집합-커버 시스템을 이용하여 트리로부터 도출되고, 트레이터 수신기는 잠재적으로 클로닝되는 해적 수신기들에 의해 획득된 하나 이상의 손상키와 연관되어 있다. 해적 수신기의 클론을 이용하여, 트레이터 수신기의 식별자가 판단되거나, 올바른 일단의 부집합들을 생성함으로써 해적 수신기 클론들이 손상키를 이용하여 데이터 해독하는 것이 쓸모없게 된다.
트레이터(traitor) 수신기, 부집합-커버(subset-cover) 시스템

Description

브로드캐스트 암호화 시스템에서 트레이터 수신기들을 추적하기 위한 방법{Method for tracing traitor receivers in a broadcast encryption system}
본원 발명은 일반적으로 암호화키를 이용하는 데이터 암호를 브로드캐스트하는 것에 관련된 것이다.
CD 및 DVD와 같은 기록매체를 이용하여, 또는 위성 브로드캐스트와 같은 무선 브로드캐스트 방법들을 통하여 잠재적으로 수백만의 수신기들에 브로드캐스트되는 콘텐트를 암호화하기 위한 다양한 브로드캐스트 암호화 시스템에 제안되어 왔다. 이들 시스템은 권한있는 수신기들(또는 "사용자 " 및 "플레이어-레코더"로도 지칭됨)만이 콘텐트를 해독하고 상영할 수 있도록 하고, 권한있는 장치,"트레이터(traitor)"로부터 유효한 해독키를 입수하고자 하는 소프트웨어 또는 하드웨어로 구현된 해적 장치들(본 명세서에서는 "클론(clones)" 및 나쁜 장치"라고도 지칭됨)이 콘텐트를 해독하고 상영할 수 없도록, 콘텐트를 암호화하고자 하는 것들이다.
이러한 시스템의 한가지 예가, 본 명세서의 일부로서 참조되는, 본발명과 동일한 양수인의 미국특허 제6,118,873호에 개시되어 있다. 상기 특허에 개시된 바에 의하면, 권한있는 플레이어-레코더만이 콘텐트를 상영 및/또는 복사할 수 있으 며, 이는 콘텐트 제조업자에 의해 확립된 규칙에 따라서만 이루어진다. 이러한 방식에 의하면, 현재 콘텐트 제공자들에게 매년 수억달러의 손해를 입히고 있는 콘텐트의 해적 복사가 방지될 수 있다.
브로드캐스트 암호화 시스템의 또다른 예는 본 출원과 동일 양수인의 계류중인 미국출원(문서번호:ARC9200100_US)에 개시되어 있는 "부집합 커버(subset cover)"시스템이며, 이는 본 명세서의 일부로서 참조된다. 후자 시스템은, 이에 대한 상세한 설명은 이하에서 이루어지겠으나, "상태 비-유지(stateless)"수신기들, 즉, 해적 장치에 대하여 대응수단을 수락하기 위해 브로드캐스트간에 그들의 암호화 상태를 필수적으로 갱신하고 있지는 않은 수신기들에 대한 어려운 시나리오에 관한 것이다. 예를 들어, 유료 채널에 가입한 텔레비전은 갱신된 암호화 데이터가 시스템을 통해 브로드캐스트되는 기간동안에 비-에너지화(deenergized)되는 셋탑 박스를 구비할 수 있다. 이러한 디바이스는 다시 가동된 후에(reenergized) 스스로를 갱신할 수 없는 일이 발생하는 경우에 "상태 비-유지"로 될 것이며, 이후의 콘텐트 해독을 위해 필요한 갱신을 수신하지 못할 것이다. 상태 비유지 수신기의 또다른 예로서 일반적으로 다른 시스템 컴포넌트들과 상호작용하지 않는 CD 및 DVD의 플레이어-레코더가 될 수 있으며, 어떠한 플레이어도 판매된 모든 디스크를 수신하는 것은 아니기 때문에, 모든 가능한 암호화 데이터 갱신 정보를 수신하지는 않을 것이다.
본 기술분야의 당업자들에게 이해되는 바와 같이, 브로드캐스트 암호화 시스템에서 해독키가 손상되어, 권한없는 해적 장치가 콘텐트를 해독할 수 있도록 할 수 있다. 이러한 해독 장치들은 하드웨어 또는 소프트웨어로 구현될 수 있으며, 후자의 경우에는 값을 지불하지 않고서도 유료의 콘텐트를 획득하고자 하는 누구나 무료로 다운로드할 수 있도록 인터넷상에 게시될 수 있다. 어떠한 경우이든, 본 발명은 해적 장치에 의해 그의 키가 습득되는 시스템 수신기들("트레이터"들)의 식별자를 찾아냄으로써 해적 클론들이 확대되는 것을 막아내거나 클론들에 의해서는 해독될 수 없고 권한있는 사용자들에 의해서만 해독될 수 있는 암호를 찾아냄으로써 해적 클론들을 쓸모없게 만드는 것에 관한 것이다.
본 발명은 부집합-커버 시스템내의 트레이터를 추적하는 문제에 특히 중점을 두고 있다 (이에 한정되는 것은 아니다). 전술한 '873 미국특허와는 달리, 부집합-커버 시스템에서는 디바이스들간에 어떠한 키 중복도 존재하지 않는다. 873 미국특허에서 키 중복에 따르면, 임의의 디바이스키들은 올바르게 콘텐트를 해독하고 다른 몇몇은 그렇지 않은 동작에서는 완벽히 정상이어서, 클론이 자신에게 전송된 메시지가 모든 키들로써 해독될 수 없는지를 단순 관찰함으로써 자신이 테스트되고 있는지의 여부를 확인할 수 없다. 부집합-커버 시스템에서는 모든 디바이스가 적어도 하나의 유일한 키를 가지고 있기 때문에 이러한 것이 해당되지 않는다. 따라서, 클론이 다수의 트레이터로부터 키를 획득한 경우에, 그리고 하나의 트레이터로부터얻은 하나의 키가 적절하게 콘텐트를 해독할 수 있는 반면에 또다른 트레이로부터 얻은 또다른 키는 그렇지 않은 경우에, 클론은 그가 테스트중임을 추론해낼 수 있다.
일단 클론이 자신이 테스트중임을 추론해내면, 그것은, 가령, 트레이터간에 식별자를 바꾸든지, 또는 심지어 자체-파괴(self-destructing)와 같은 임의의 대항수단중 하나를 수행할 수 있다. 물론, 자체-파괴되는 경우에, 라이센싱 에이전시는 이후의 (변경된) 테스팅을 위해 또다른 클론을 간단히 얻을 수 있지만, 이는 시간이 걸린다. 이러한 중요한 문제점들을 고려하여, 본 발명의 바람직한 실시예는 하나 이상의 문제점들에 대한 이하의 해결책을 제공한다.
따라서, 제1 측면에 따른 본 발명은, 브로드캐스트 암호 시스템에서 적어도 하나의 연관된 유일한, 손상된 해독키를 갖는 적어도 하나의 트레이터 수신기를 식별 또는 디스에이블링하는 방법을 제공하는데, 상기 방법은 리프들(leaves)을 정의하는 트리로부터 파생된 부집합 세트(a set of subsets)를 수신하는 단계 -상기 트리내의 각각의 리프(leaf)는 각각의 수신기를 나타냄- 와, 후보(candidate) 트레이터 수신기를 나타내는 적어도 하나의 리프를 포함하는 적어도 하나의 트레이터 부집합을 상기 부집합 세트로부터 식별하는 단계와, 상기 트레이터 부집합을 이용하여, 상기 트레이터 수신기를 식별하거나 또는 디스에이블링하는 단계를 포함한다.
바람직하게, 상기 제1 측면에 따른 방법은 상기 트레이터 부집합이 적어도 하나의 후보 트레이터 수신기를 나타내는지를 판단하는 단계와, 상기 트레이터 부집합이 적어도 하나의 후보 트레이터 수신기를 나타낸다면 상기 트레이터 부집합을 2개의 자식 집합들로 나누는 단계를 더 포함한다.
바람직하게, 상기 제1 측면에 따른 방법은 상기 트레이터 부집합이 프론티어(frontier) 집합의 구성원인지를 판단하는 단계와, 상기 트레이터 부집합 이 프론티어 집합의 구성원이라면 상기 프론티어 집합으로부터 상보(complementary) 부집합을 제거하는 단계를 더 포함한다.
바람직하게, 상기 제1 측면에 따른 방법은 확률을 이용하여 상기 일단의 부집합들에 대하여 이진 서치(binary search)를 실행하는 단계를 더 포함한다.
삭제
바람직하게, 상기 이진 서치는 j개의 부집합들이 거짓키를 포함할 때 메시지를 해독할 확률 pj와 j-1개의 부집합들이 거짓키를 포함할 때 메시지를 해독할 확률 pj-1간의 차이가 선정된 확률과 적어도 동일한지를 판단함으로써 종료한다.
바람직하게, 상기 트레이터 부집합은
Figure 112005076027911-pct00017
일 때 식별되며, 여기서 m은 상기 부집합 세트내의 부집합 개수이다.
바람직하게, 상기 부집합 세트는, 일군의 수신기들의 각각의 수신기에 각각의 개인 정보 Iu를 할당하는 단계와, 적어도 하나의 세션 암호키 K를 선택하는 단계와, 철회 집합 R에 속하지 않는 수신기들을 연관 부집합 키 Li1 ...Lim을 갖는 디스조인트 부집합 Si1 ...Sim으로 분할하는 단계와, 상기 세션키 K와 상기 거짓키를 부집합 키Li1 ...Lim로 암호화하는 단계를 수행함으로써 생성된다.
바람직하게, 상기 트리는 루트와 다수의 노드들을 포함하고, 각각의 노드는 연관키를 가지며, 각각의 수신기에 상기 수신기를 나타내는 리프와 루트간의 직접 경로내의 모든 노드 키들이 할당된다.
바람직하게, 상기 트리는 루트와 다수의 노드들을 포함하고, 각각의 노드는 일단의 라벨들과 연관되어 있으며, 각각의 수신기에 상기 수신기와 루트간의 직접 경로내의 노드들이 아닌 상기 경로로부터 벗어나 있는 모든 노드의 라벨들이 할당된다.
바람직하게, 상기 철회집합 R은 스패닝 트리를 정의하고, 상기 방법은, 상기 스패닝 트리로서 커버 트리 T를 초기화시키는 단계와, 상기 커버 트리 T가 최대(at most) 하나의 노드를 가질 때까지 상기 커버 트리 T로부터 노드들을 제거하고 상기 커버 트리 T에 노드들을 추가하는 동작을 반복하는 단계를 포함한다.
바람직하게, 상기 제1 측면에 따른 방법은 클론으로 구현된 다수의 트레이터 수신기들을 식별 또는 디스에이블링하는 단계를 더 포함한다.
바람직하게, 본 발명은 컴퓨터에 의해 이용될 수 있는 프로그램 명령어들을 포함하는 컴퓨터 프로그램 저장 장치를 포함하는 컴퓨터 프로그램 장치를 제공하는데, 상기 프로그램 명령어는 손상키에 의해 특정되는 적어도 하나의 트레이터 디바이스를 나타내는 리프를 포함하는 트리를 액세스하여 일단의 부집합들을 생성하기 위한 로직 수단과, 거짓키를 j번 암호화하고 세션키를 m-j번(m은 상기 일단의 부집합들의 부집합 개수) 암호화하기 위한 로직 수단과, 상기 암호화 수단에 응답하여 트레이터 부집합을 식별하기 위한 로직 수단과, 상기 트레이터 부집합을 이용하여 트레이터 디바이스를 식별 또는 디스에이블링하기 위한 로직 수단을 포함한다.
상기 컴퓨터 프로그램 장치의 더욱 바람직한 특징은 컴퓨터 시스템으로 하여금 상기 제1 측면의 바람직한 특징에 따르는 상기 방법 단계들을 수행하도록 만드는 로직 수단을 포함한다.
제2 측면에 따른 본 발명은, 컴퓨터 시스템에 로딩되어 실행될때, 컴퓨터로 하여금 상기 제1 측면에 따른 방법 단계들을 수행하는 컴퓨터 프로그램 코드를 포함하는 컴퓨터 프로그램을 제공한다.
제2 측면에 따른 바람직한 특징들은 상기 컴퓨터 시스템으로 하여금 상기 제1 측면의 바람직한 특징들에 따른 방법의 단계들을 수행하도록 만드는 컴퓨터 프로그램 코드를 포함한다.
바람직하게, 본 발명은 컴퓨터로 하여금 이하의 단계들을 포함하는 방법을 실행토록 만드는 명령어들로 프로그래밍된 컴퓨터를 제공하는데, 상기 단계들에는, 거짓키를 이용하여 상태 비유지 수신기들 - 상기 수신기들중 적어도 하나의 트레이터 수신기는 적어도 하나의 해적 수신기에 의해 획득된 적어도 하나의 손상키와 연관되어 있음 -을 나타내는 다수의 부집합들을 인코드하는 단계와, 상기 해적 수신기 또는 이의 클론을 이용하여 상기 트레이터 수신기의 식별자를 판단하거나 상기 해적 수신기 또는 이의 클론이 상기 손상키를 이용하여 데이터를 해독할 수 없도록 만드는 단계가 포함된다.
바람직하게, 상기 부집합들은 부집합 세트를 정의하고, 상기 컴퓨터에 의해 수행되는 방법은 각각의 리프가 각각의 수신기를 나타내는 리프들을 정의하는 트리로부터 도출된 부집합 세트를 수신하는 단계와, 트레이터 수신기를 나타내는 적어도 하나의 리프를 포함하는 적어도 하나의 트레이터 부집합을 상기 부집합 세트로부터 식별해내는 단계와, 상기 트레이터 부집합을 이용하여 상기 트레이터 수신기를 식별하는 단계를 포함한다.
바람직하게, 상기 컴퓨터에 의해 수행되는 방법은 상기 트레이터 부집합이 적어도 하나의 트레이터 수신기를 나타내는지를 판단하는 단계와, 상기 트레이터 부집합이 적어도 하나의 트레이터 수신기를 나타낸다면 상기 트레이터 부집합을 2개의 자식 집합들로 나누는 단계를 더 포함한다.
바람직하게, 상기 컴퓨터에 의해 수행되는 방법은 상기 트레이터 부집합이 프론티어 집합의 구성원인지를 판단하는 단계와, 상기 트레이터 부집합이 프론티어 집합의 구성원이라면 상기 프론티어 집합으로부터 상보 부집합을 제거하는 단계를 더 포함한다.
바람직하게, 상기 컴퓨터에 의해 수행되는 방법은 상기 식별 단계가 거짓키를 이용하여 상기 부집합 세트의 다수의 부집합들을 인코딩하는 단계를 포함한다.
바람직하게, 상기 컴퓨터에 의해 수행되는 방법은 확률을 이용하여 상기 일단의 부집합들에 대하여 이진 서치를 실행하는 단계를 더 포함한다.
바람직하게, 상기 이진 서치는 j개의 부집합들이 거짓키를 포함할 때 메시지를 해독할 확률 pj와 j-1개의 부집합들이 거짓키를 포함할 때 메시지를 해독할 확률 pj-1간의 차이가 선정된 확률과 적어도선정된 확률과 적어도 동일한지를 판단함으로써 종료한다.
바람직하게, 상기 트레이터 부집합은
Figure 112005076027911-pct00018
일 때 식별되며, 여기서 m은 상기 부집합 세트내의 부집합 개수이다.
바람직하게, 상기 부집합 세트는, 일군의 수신기들의 각각의 수신기에 각각의 개인 정보 Iu를 할당하는 단계와, 적어도 하나의 세션 암호키 K를 선택하는 단계와, 철회 집합 R에 속하지 않는 수신기들을 연관 부집합 키 Li1 ...Lim을 갖는 디스조인트 부집합 Si1 ...Sim으로 분할하는 단계와, 상기 세션키 K와 상기 거짓키를 부집합 키Li1 ...Lim로 암호화하는 단계를 수행함으로써 생성되고, 상기 트리는 루트와 다수의 노드들을 포함하고, 각각의 노드는 일단의 라벨들과 연관되어 있으며, 각각의 수신기에 상기 수신기와 루트간의 직접 경로내의 노드들이 아닌 상기 경로로부터 벗어나 있는 모든 노드의 라벨들이 할당된다.
바람직하게, 본 발명은 이하의 로직 집합을 수행하기 위한 컴퓨터 시스템을 포함한다. 또한, 본 발명은 상기 로직을 저장하고 상기 로직을 실행시키기 위해 프로세서가 액세스할 수 있는 컴퓨터 프로그램 제품으로 구현될 수 있다. 또한, 본 발명의 이하에 설명될 로직을 따르는 컴퓨터-구현 방법이다.
바람직하게, 컴퓨터는 거짓키를 이용하여 상태 비유지 수신기들을 나타내는 복수의 부집합들을 인코드하도록 프로그래밍된다. 시스템 내의 적어도 하나의 트 레이터 수신기는 클론화된 해적 수신기에 의해 획득된 손상키와 연관되어 있다. 상기 해적 수신기의 클론을 이용하여, 상기 컴퓨터는 트레이터 수신기의 식별자를 판단하거나, 올바른 암호화 전략을 생성함으로써 상기 해적 수신기 클론들이 상기 손상키를 이용하여 데이터를 해독할 수 없도록 만든다.
또다른 측면에서, 브로드캐스트 암호 시스템에서 적어도 하나의 연관된 유일한, 손상된 해독키를 갖는 적어도 하나의 트레이터 수신기를 식별하는 바람직한 방법이 개시된다. 상기 방법은 각각의 리프가 각각의 수신기를 나타내는 리프들을 정의하는 트리로부터 도출된 부집합 세트를 수신하는 단계를 포함한다. 또한, 상기 방법은 적어도 하나의 트레이터 수신기를 나타내는 트레이터 부집합을 상기 부집합 세트로부터 식별해내는 단계와, 상기 트레이터 부집합을 이용하여 상기 트레이터 수신기를 식별하는 단계를 포함한다.
바람직한 실시예에서, 상기 방법은 상기 트레이터 부집합이 2개 이상의 트레이터 수신기를 나타내는지를 판단하는 단계와, 상기 트레이터 부집합이 2개 이상의 트레이터 수신기를 나타낸다면 상기 트레이터 부집합을 2개의 자식 집합들로 나누는 단계와, 상기 2개의 자식 집합을 이용하여 새로운 트레이터 부집합을 식별하는 단계를 포함한다. 또한, 상기 방법은 상기 트레이터 부집합이 프론티어 집합의 구성원인지를 판단하는 단계와, 상기 트레이터 부집합이 프론티어 집합의 구성원이라면 상기 프론티어 집합으로부터 상보 부집합을 제거하는 단계를 포함한다.
상기 트레이터 부집합을 식별하는 바람직한 방법은 거짓키를 이용하여 상기 부집합 세트중 j개의 부집합들을 인코딩한 후에 확률을 이용하여 상기 일단의 부집합들에 대하여 이진 서치를 실행하는 단계를 포함한다. 상기 이진 서치는 j개의 부집합들이 거짓키를 포함할 때 메시지를 해독할 확률 pj와 j-1개의 부집합들이 거짓키를 포함할 때 메시지를 해독할 확률 pj-1간의 차이가 선정된 확률과 적어도 동일한지를 판단함으로써 종료된다. 구체적으로, 상기 트레이터 부집합은
Figure 112005076027911-pct00019
일 때 식별되며, 여기서 m은 상기 부집합 세트내의 부집합 개수이다. 상기 부집합 세트는 두가래로 갈릴 수 있는 부집합들을 생성하는 속성을 갖는 부집합-커버 계획(subset-cover scheme)에 의해 생성된다.
또다른 측면에서, 컴퓨터 프로그램 장치는 손상키에 의해 특정되는 적어도 하나의 트레이터 디바이스를 나타내는 리프를 포함하는 트리를 액세스하여 상기 트리에 대한 부집합 세트를 생성하기 위한 로직 수단을 포함한다. 거짓키를 j번 암호화하고 세션키를 m-j번(m은 상기 부집합 세트의 부집합 개수) 암호화하기 위한 로직 수단이 제공된다. 또한, 상기 암호화 수단에 응답하여 트레이터 부집합을 식별하기 위한 로직 수단이 제공된다. 그런 후에, 로직 수단은 상기 트레이터 부집합을 이용하여 트레이터 디바이스를 식별한다.
본원 발명의 바람직한 실시예가 이하에 첨부된 도면들을 참조하여 예시적으로 설명될 것이다.
도 1은 본 발명에 따른 시스템의 블록도이다.
도 2는 개괄적인 암호화 로직의 흐름도이다.
도 3은 개괄적인 해독 로직의 흐름도이다.
도 4는 완전 부트리 방법의 키 할당 부분에 대한 흐름도이다.
도 5는 완전 부트리 방법의 암호 부분에 대한 흐름도이다.
도 6은 완전 부트리 방법의 해독 부분에 대한 흐름도이다.
도 7은 완전 부트리의 부집합 개념도이다.
도 8은 부집합 차이 방법에서의 부집합 개념도이다.
도 9는 부집합 차이 방법에서의 부집합의 또다른 형태의 개념도이다. 도 10은 부집합 차이 방법에서 커버(cover)를 정의하기 위한 로직의 흐름도이다.
도 11은 키 할당을 설명하는 부집합 차이 방법에서의 트리 부집합 개념도이다.
도 12는 부집합 차이 방법의 암호해독 부분에 대한 흐름도이다.
도 13은 부집합 차이 방법에서 키를 할당하기 위한 로직의 흐름도이다.
도 14는 부집합 차이 방법에서의 트리 부집합 개념도이다.
도 15는 본 발명에 따른 추적 로직을 도시한 흐름도이다.
도 16은 추적 로직의 부집합 추적 모듈을 도시한 흐름도이다.
본 발명의 바람직한 실시예는 다수의 브로드캐스트 암호화 방법중 어느 것과도 이용될 수 있다. 비제한적인 예시로서, 하나의 시스템 - 부집합 커버 시스템(subset-cover system)을 먼저 설명하고, 이러한 부집합-커버 시스템 측면에서, 본 발명에 따른 추적 알고리즘을 설명하겠다.
우선, 도 1을 참조하면, 브로드캐스트 콘텐트 가드(guard) 시스템에서 키 집합을 생성하기 위한 시스템(10)이 도시되어 있으나, 이러한 시스템이 전술한 특허에 개시된 시스템으로 한정되는 것은 아니다. "브로드캐스트(broadcast)"란 의미는 콘텐트 제공자로부터 동시에 다수의 수신기에게, (위성 소스로부터) 케이블을 통해, 또는 유선, 또는 (위성 소스로부터의) 라디오주파수를 통해, 또는 광범위하게 판매된 콘텐트 디스크로부터 프로그램의 광범위하게 유포되는 것을 의미한다.
도시된 바와 같이, 시스템(10)은 이하에서 설명되는 것에 따라 기능하는 키집합 정의 모듈(14)을 액세스하는 키집합 정의 컴퓨터(12)를 포함한다. 컴퓨터(12)에 의해 정의되는 키집합은 잠재적으로 상태 비-유지의 플레이어-레코더 장치(160)(본명세서에서, "수신기" 또는 "사용자"로 언급되기도 함)에 의해 사용되며, 이들 장치(160)는 콘텐트 해독을 위해 그들 내부에 프로세서를 구비한다. 이하에서 설명될 임의의 키들과 함께 콘텐트가 각각의 장치들에, 예를 들어, 장치 제조업자(16)들을 통해 미디어(17) 상에 제공된다. 플레이어-레코더 장치는 미디어상의 콘텐트를 해독하거나 무선 통신을 통해 그것을 브로드캐스트하기 위해 그의 키 집합을 액세스할 수 있다. 본 명세서에서 언급되는 "미디어"는 DVD, CD, 하드디스크 및 플래시 메모리 디바이스를 포함할 수 있으며, 이에 한정되는 것은 아니다. 대안적인 실시예에서, 각각의 수신기(16)는 철회 수신기 집합들이 주어지고 이하에 설명될 로직을 수행함으로써 이하에 개시될 "커버(cover)"를 계산하는 단계를 수행하는 모듈(14)를 실행시킨다.
모듈(14)과 연관된 프로세서는 모듈을 액세스하여 도시된 로직을 수행하도록 하며, 로직은 프로세서에 의해 일련의 컴퓨터 실행가능 명령들로서 실행됨은 이해할 것이다. 본 명세서에서는 시스템(10)이 손상되지 않은 임의의 수신기(16)가 브로드캐스트 콘텐트를 해독하는 능력은 철회하지 않고 손상된 수신기(16)의 브로드캐스트 콘텐트 해독 능력만을 선택적으로 철회할 수 있는 두가지 방법, 완전 부트리(complete subtree) 방법과 부집합 차이 방법을 개시한다.
명령들은, 컴퓨터 기록 코드 요소가 저장된 컴퓨터 사용가능 매체를 구비한 컴퓨터 디스켓과 같이, 컴퓨터 기록매체를 구비한 데이터 저장 장치상에 저장될 수 있다. 혹은, 명령어는 DASD 어레이, 자기 테이프, 종래 하드디스크 드라이브, 전자적 판독전용 메모리, 광학 저장 장치, 또는 기타 적절한 데이터 저장장치상에 저장될 수 있다. 본 발명의 예시적인 구현에서, 컴퓨터-실행가능 명령어들은 C++ 호환 코드 라인으로 이루어질 수 있다.
본명세서에 개시된 흐름도들은 컴퓨터 프로그램 소프트웨어로 구현될 수 있는 본 발명의 바람직한 실시예 로직 구조를 도시한다. 본 기술분야의 당업자들은 흐름도들이 본 발명에 따라 기능하는 집적 회로상의 논리회로를 포함하는 컴퓨터 프로그램 코드 요소들의 구조를 설명하고 있음을 이해할 것이다. 자명하게, 본 발명은 디지털 프로세싱 장치(즉, 컴퓨터)로 하여금 도시된 절차에 대응하는 일련의 기능 동작들을 수행하도록 명령하는 형태로 프로그램 코드 요소들을 만드는 머신 컴포넌트에 의한 기본 구현으로 실시된다.
부트리 차이 방법 및 완전 부트리 방법에 의해 구현된 본 발명의 바람직한 실시예에 따른 전체 논리는 도 2를 참조하여 알 수 있다. 본 발명의 설명을 위해, 시스템(10)내에 N개의 수신기들이 존재하며, 철회 수신기 부집합 R의 r개의 철회 수신기들이 (암호화 정보를 공유함으로써) 연합하여 작동하더라도 이들 수신기들의 암호 해독 능력을 철회하고 임의의 수신기들은 계속해서 암호해독할 수 있도록 하는 것이 바람직하다고 가정한다. 블록(19)에서, 시스템은, 수신기들이 이하의 설명에 따라 그룹화되는 부집합 S1, ... Sw 들의 해당 부집합들에 장기-수명(long-lived) 부집합 키들L1, ... Lw을 할당함으로써 초기화되며, 따라서, 각각의 부집합 Sj는 그에 연관된 장기-수명 부집합 키 Lj를 갖게 된다. 첫 번째 ("완전 부트리(complete subtree))" 방법에서, 철회집합에 속하지 않는 수신기들을 커버하는 부집합들은 이하의 설명에 따라 생성되는 부트리들이다. 두 번째("부집합 차이(subset difference))" 방법에서, 철회집합에 없는 수신기들을 커버하는 부집합들은 이하에서 설명되는 바와 같이 제1 부집합과 제1 부집합내에 완전히 포함되는 작은 부트리간의 차이에 의해 정의된다.
블록(20)에서, 시스템은 각각의 수신기 u에게 내용을 해독하는데 유용한 개인 정보 Iu를 공급함으로써 또한 개시된다. 개인정보 Iu에 대한 상세한 설명은 이하에 설명될 것이다. Iu가 수신기 u에 제공되는 비밀 정보라면, Sj의 각각의 수신기 u는 그의 Iu로부터 Lj를 추론해낼 수 있다. 이하에서 좀더 상세히 설명되는 바와 같이, 소정의 철회집합 R에 대해, 비-철회 수신기들은 m개의 디스조인트 부집합 Si1,...Sim로 나뉘고 단기-수명 세션 키 K가 각각의 부집합 Si1,...Sim 와 연관된 장기-수명 부집합 Li1,...Lim로써 m번 암호화된다. 부집합 키들은 완전 부집합 방법에서는 명시된(explicit) 부집합 키들이며, 부집합 차이 방법에서는 부집합 라벨에 의해 유도된다.
구체적으로, 블록(22)에서, 적어도 하나의 세션키 K가, 무선 또는 유선통신경로를 통해, 또는 CD 및 DVD와 같은 저장매체를 통해, 메시지 M에 브로드캐스트되는 내용을 암호화하기 위해 선택된다. 세션키 K는 각각의 메시지에 대하여 새롭게 선택되는 랜덤 비트 스트링이다. 바람직하게는, 메시지 M의 각각이 부분들을 암호화하기 위해 다수의 세션키들이 이용될 수 있다.
이하에서 설명되는 양 방법에서, 비-철회 수신기들은 트리를 이용하여 블록(24)에서 디스조인트 부집합 Si1,...Sim으로 나뉜다. 부집합들은 본명세서에서 "부트리"로 지칭되기도 하며, 첫 번째 방법에서는 부트리를 명백하게 고려하고 있으며 두 번째 방법에서는 부트리를 "제1 부트리에서 상기 제1 부트리에 완전히 포함된 제2 부트리를 제외한" 형태로서 간주한다. 각각의 부집합 Si1,...Sim은 각각의 부집합 키 Li1,...Lim와 연관되어 있다. 임의의 데이터 트리-유사 구조가 본명세서에서 고려되겠지만, 설명을 위해 트리는 완전이진트리(full binary tree)로서 가정된다.
블록(26)으로 진행하여, 일반적으로 세션키 K가 각각의 부집합 키Li1,...Lim로 각각 한번씩, m번 암호화된다. 최종적으로 브로드캐스트되는 암호문은 이하처럼 표현될 수 있는데, 메시지 M의 헤더를 나타내는 중괄호([])사이의 부분과 디스조인트 부집합 인덱스를 나타내는 i1,i2 ...im를 포함한다.
<[i1,i2 ...im, ELi1(K),...,ELim(K)], FK (M)>
일실시예에서, 암호 원시함수 FK는 메시지 M과 세션키 K에 의해 생성된 스트림 암호를 XOR함으로써 구현된다. 암호 원시함수 EL는 장기-수명 부집합 키들을 이용하여 수신기들(16)에 세션키 K를 전달하기 위한 방법이다. FK 및 EL를 위한 모든 암호화 알고리즘은 본 발명의 바람직한 실시예의 범위내에 있음을 이해하여야 한다. EL의 한가지 바람직한 실시예는 블록 암호의 프리픽스-절단(Prefix-Truncation) 사양이 될 수 있다. l이 EL의 블록 길이와 동일한 길이를 갖는 랜덤 스트링을 나타내고, K는 길이가, 예를 들어, 56 비트인 암호 FK의 단축키로 가정한다. [프리픽스-K-EL(l)/K]는 강한 암호를 제공한다. 따라서, 프리픽스-절단형 헤더는 다음과 같다.
<[ii,i2,,..,im,U, [Prefix-K-ELi1(U)]/K,...,Prefix -K-ELim(U)/K],FK(M)>.
이는 헤더길이를 약 m-L-대신에 m-K-비트로 줄여주는 장점을 갖는다. EL의 키 길이가 최소인 경우에, 주먹구구식 공격에서 대항자가 갖는 인자 m개의 장점을 제거하기 위해 다음 식이 이용될 수 있으며, 이는 동일한 스트링 l을 서로 다른 m 개의 키들로 암호화함으로 인한 것이다. 스트링 l/ij가 암호화된다. 즉,
<[ii,i2,,..,im,U, [Prefix-L-ELi1(U/i1 )]/K,...,Prefix-L-ELim(U/im)/K],FK(M)>.
암호 원시함수 E와 F를 구현하는 여러 가지 바람직한 방법들이 설명되었다. 이제, 수신기(16)에 의해 수행되는 암호해독 로직이 도시된 도 3을 참조한다. 블록(28)에서 시작하여, 각각의 비철회 수신기 u는 암호문에서 부집합 식별자 ij를 찾는데, 수신기는 부집합 Sij에 속하게 된다. 이하에서 설명되는 바와 같이, 수신기가 철회집합 R내에 속하는 경우에, 블록(28)의 결과는 널(null)이 될 것이다. 다음에, 블록(30)에서, 수신기가 그의 개인 정보 Iu를 이용하여 부집합 Sij에 대응하는 부집합키 Lij를 추출한다. 부집합키를 이용하여, 블록(32)에서 세션키 K가 결정된 후에, 블록(34)에서 세션키 K를 이용하여 메시지가 해독된다.
전술한 전체 로직을 수행하기 위한 두가지 방법이 이하에서 설명된다. 각각의 방법에서, 부집합들이 지정되고, 부집합들에 키들이 할당되고, 부집합들이 지정되고, 전체로부터 디스조인트 부집합을 이용하여 비-철회 수신기들을 커버하는 방법이 이용된다. 각각에서, 시스템내의 수신기 집합은 이진완전트리(이에 한정되는 것은 아님)와 같은 트리의 리프를 형성한다.
설명될 첫 번째 방법은 도 4-7에 도시된 완전 부트리 방법이다. 도 4의 블록(36)에서 시작하여, 독립적이고 랜덤한 부집합 키 Li이 트리내의 각각의 노드 vi에 할당된다. 이러한 부집합키 Li은 노드 vi를 루트로 하는 모든 리프들을 포함하 는 부집합에 대응한다. 그러면, 블록(38)에서, 각각의 수신기 u에 수신기로부터 루트까지의 직접 경로에 있는 모든 부집합 키들이 제공된다. 도 7을 참조하여 간단히 설명되는 바와 같이, 부집합 Si의 수신기 u에 노드 vi와 연관된 부집합키 Li뿐만 아니라, Si에 포함되는 수신기들과 트리의 루트사이에 존재하는 노드 P에 연관된 키들도 제공된다.
메시지를 전송하고 몇몇 수신기들의 메시지 해독 능력을 철회하고하고자 할 때, 비-철회 수신기들을 디스조인트 부집합들로 분할하기 위해 도 5의 로직이 호출된다. 블록(40)에서 개시되어, 철회 수신기 집합 R의 리프들에 의해 정의되는 스패닝 트리가 발견된다. 스패닝 트리는 "철회" 리프들을 연결시키는 완전이진트리의 최소 부트리이고, 이는 스테이너(Steiner) 트리일 수 있다. 블록(42)으로 진행하여, 트리에서 1차 노드(즉, 최소 트리에 직접 인접한 노드들)들에 인접한 루트를 갖는 부트리들이 식별된다. 이들 부트리들은 "커버(cover)"를 정의하고 부집합 Si1,...Sim 을 형성한다. 커버는 모든 비-철회 수신기들을 포함한다. 따라서, 블록(44)에서, 커버에 의해 정의된 부집합 키들을 이용하여 세션키 K가 암호화된다.
메시지를 해독하기 위해, 각각의 수신기는 도 6의 로직을 호출한다. 블록(46)에서 개시되어, 수신기의 임의의 조상 노드가 메시지 헤더내의 집합 i1,i2 ...im중에 있는지 판단함으로써 수신기의 조상 노드가 커버의 부집합 키와 연관되어 있는지의 여부가 판단된다. 이를 판단하기 위해, 완전 부트리 방법에서는 트리 내 자신의 위치와 조상 노드에 연관된 부집합 키로 구성되는 수신기의 개인정보 Iu가 이용된다. 조상 노드가 (수신기가 비-철회 수신기임을 나타내는) 메시지 헤더에서 발견되면, 세션키 K는 부집합 키를 이용하여 블록(48)에서 해독되며, 그 후에 블록(50)에서 메시지가 세션키 K를 이용하여 해독된다.
완전 부트리 방법에서, 헤더는 최대 r*log(N/r) 부집합 키들과 암호들을 포함한다. 이는 또한 키 및 암호들의 평균 개수이다. 더욱이, 각각의 수신기는 log N개의 키들을 저장하여야 하며, 각각의 수신기는 최대 log log N 연산 및 하나의 해독 연산을 이용하여 메시지를 처리한다.
이제 도 8 내지 13을 참조하면, 수신기들을 철회하기 위한 부집합 차이 방법이 도시된다. 부집합 차이 방법에서, 각각의 수신기는 완전 부트리 방법보다 상대적으로 많은 개수의 키들( .5log2N + .5logN +1개의 키)을 저장하여야 한다. 그러나, 메시지 헤더는 최대 2r-1개의 부집합 키들과 암호(평균 1.25r)를 포함할 뿐이며, 이는 완전 부트리 방법보다 실질적으로 짧다. 또한, 부집합 차이 방법에서, 메시지는 최대 log N번의 슈도랜덤 숫자 생성기 적용 및 하나의 해독 연산을 이용하여 처리된다.
도 8 및 9를 참조하면, 부집합 차이 방법은 부집합들을 큰 부집합 A와 A에 완전히 포함되는 작은 부집합 B간의 차이로서 간주한다. 따라서, 도시된 바와 같이, 큰 부트리는 노드 vi를 루트로 하며, 작은 부트리는 vi의 후손인 vj를 루트로 한다. 최종 부집합 Si,j는 "아니오"라고 라벨링된 (그리고, "예"라고 라벨링된 리프들 보다 좁더 어두운 색깔로 칠해진) 리프들을 제외하고 vi아래의 모든 "예"리프들로 구성된다. 도 9는 이를 설명하며, 부집합 Si,j는 좀더 작은 삼각형 외부의 좀더 큰 삼각형 내부의 영역들에 의해 표현된다.
부집합 차이 방법에 따라 메시지를 전송하고 몇몇 수신기들의 메시지 해독 능력을 철회하고자 할때, 도 10에 도시된 바와 같은 전술한 구조가 이용된다. 블록(52)에서 시작하여, 철회 수신기 집합 R의 리프들에 의해 정의되는 스패닝 트리가 발견된다. 스패닝 트리는 "철회" 리프들을 연결시키는 완전이진트리의 최소 부집합이며, 이는 스테이너 트리가 될 수 있다. 블록(54)로 진행하여, 커버 트리 T가 스패닝 트리로서 초기화된다. 그 다음에, 커버 트리 T가 최대 1개의 노드를 가질 때까지 커버 트리로부터 노드들이 제거되고 커버에 부트리들이 추가되는 반복적인 루프가 시작된다. 그 결과 비-철회 수신기들에 대한 커버가 정의된다.
좀더 구체적으로, 블록(54)에서 블록(56)으로 이동하여, 그들의 최소공통조상 v가 T 내의 어떠한 다른 리프들도 포함하지 않도록 하는 리프 vi 및 vj가 커버 트리 T에서 발견된다. 결정블록(57)에서, 단지 하나의 리프만이 커버 트리 T에 존재하는지 여부가 판단된다. 하나 이상의 리프가 존재하는 경우에, 로직은 블록(58)으로 이동하여 vi가 vl의 자손이고 vj가 vk의 자손이고 vl,vk가 v의 자식인 (즉, v와 vl,vk간에 중간 노드들 없이 v의 직접 자손이 되는) 노드들 vl, vk을 찾는다. 대조적으로, T에 하나의 리프만이 존재할 때, 로직은 결정블록(57)에서 블록(60)으로 이동하여, vi = vj = 단독 존재 리프(sole remaining leaf)로 설정하고, T의 루트에 v를 배치하고, vl = vk = 루트로 설정한다.
블록(58) 또는 블록(60)으로부터 로직은 결정블록(62)으로 이동한다. 선택블럭(62)에서, vl가 vi와 동일한지가 판단된다. 마찬가지로, vk가 vj 와 동일한지가 판단된다. vl가 vi와 동일하지 않다면, 로직은 블록(64)으로 이동하여 T에 부집합 Sl,i를 추가시키고, T로부터 v의 모든 자손들을 제거하여 v를 리프로 만든다. 마찬가지로, vk가 vj와 동일하지 않다면, 로직은 블록(64)으로 이동하여 T에 부집합 Sk,j를 추가시키고, T로부터 v의 모든 자손들을 제거하여 v를 리프로 만든다. 블록(64) 또는 결정블록(62)로부터 어떠한 도일성도 판단되지 않는다면, 로직은 블록(56)으로 되돌아간다.
부집합 차이 키 할당방법에 대한 전술한 개요를 기반으로 하여, 특정의 바람직한 실시예가 이제 설명된다. 수신기가 속한 부집합의 전체 개수가 N인 경우에, 이러한 부집합들은 (또다른 부집합이 감해지는) 제1 부집합 i에 의해 정의되는 logN 클러스터들로 그룹핑될 수 있다. 전체 트리의 내부 노드들에 대응하는 각각의 l<i<N에 대하여, 독립적이고 랜덤한 라벨 LABELi이 선택되는데, 이는 형태 Si,j 의 모든 적법한 부집합들에 대한 라벨을 유도한다. 라벨들로부터, 부집합 키들이 도출된다. 도 11은 이하에서 설명될 바람직한 라벨링 방법을 설명한다. Li로 라벨링 된 노드는 부집합 Ti의 루트이고, 그의 자손들은 본 발명의 원칙에 따라 라벨링된다.
G가 입력 길이를 세배로 늘리는 암호화 슈도랜덤 시퀀스 생성자라면, G_L(S)는 시드 S에 대한 G 출력의 세 번째 왼쪽을 나타내는 것이고, G_R(S)는 오른쪽 세 번째를 나타내는 것이며, G_M(S)는 중간 세 번째를 나타낸다. 라벨 LABELi를 갖는 노드 vi를 루트로 하는 커버 트리 T의 부트리 Ti를 고려해본다. 이 노드가 S로 라벨링되는 경우에, 이의 두 자식은 각각 G_L(S) 및 G_R(S)로 각각 라벨링된다. 집합 Si,j에 할당되는 부집합키 Li,j는 부집합 Ti로부터 유도되는 노드 v j의 LABELi,j 라벨의 G_M이다. 각각의 라벨 S는 세 개의 부분, 즉, 왼쪽 및 오른쪽 자식, 그리고 노드의 키에 대한 라벨들을 유도한다. 따라서, 노드의 라벨이 주어지면, 그의 모든 자손들에 대한 라벨 및 키들을 계산하는 것이 가능하다. 바람직한 실시예에서, 함수 G는 Secure Hashing Algorithm-1와 같은 암호 해쉬이며, 그밖에 다른 함수들도 이용될 수 있다.
도 12는 부집합 차이 방법에 따라 수신기들이 어떻게 메시지를 해독하는지를 도시한다. 블록(66)에서 시작하여, 수신기는 연관된 라벨(수신기가 LABELi,j 및 부집합키 Li,j를 유도할 수 있도록 해주는 수신기의 개인정보의 부분)과 함께 그가 속한 부집합 Si,j을 찾는다. 라벨을 이용하여, 수신기는 블록(68)에서 최대 N번 함수 G값을 구함으로써 부집합키 Li,j를 계산한다. 그런 후에, 수신기는 후속되는 메시지 해독을 위해 블록(70)에서 부집합키를 이용하여 세션키 K를 해독한다.
도 13은 부집합 차이 방법에서 수신기들에 라벨 및 이에 따른 부집합 키들이 어떻게 할당되는지를 도시한다. 본명세서에 도시된 라벨링 방법은 각각의 수신기가 저장하여야 하는 키의 개수를 최소화시키는데 이용된다.
블록(72)에서 시작하여, 각각의 수신기에 수신기 및 루트간의 직접경로에 있지 않고 직접경로로부터 매달려 있으면서, u의 조상인 임의의 노드 vi에 의해 유도되는 노드들의 라벨들이 제공된다. 이러한 라벨들은 블록(74)에서 수신기의 개인정보(Iu)를 형성하며, 후속하는 메시지 세션 키들은 블록(76)에서 라벨들로부터 유도된 부집합 키들로 암호화된다.
도 14를 간단히 참조하면, 전술한 원칙이 설명된다. 수신기 u의 라벨 S를 갖는 모든 vi 조상에 대해, 수신기 u는 노드 vi 로부터 수신기 u에 이르는 직접 경로로부터 벗어나있는 모든 노드들(71)의 라벨들을 수신한다. 이하에서 좀더 자세히 설명되겠지만, 이들 라벨들은 바람직하게는 S로부터 모두 유도된다. 완전부트리 방법에 대한 표시 대비에 있어서, 도 8-14에 설명된 부집합 차이 방법에서, 수신기 u는 수신기 u와 노드 vi 사이에 있는 직접 경로내의 노드(73)로부터는 라벨을 수신하지 않는다. 라벨들을 이용하여, 수신기 u는 전술한 함수 G값을 구함으로써 노드 vi를 루트로 하는 (직접경로 집합을 제외한) 모든 집합들의 부집합 키들을 계산할 수 있지만, 기타 다른 부집합 키들은 계산할 수 없다.
종래의 다중캐스트 시스템은 역방향 비밀성(secrecy)이 결여되어, 즉, 철회되었음에도 불구하고 계속적으로 청취중인 수신기는 모든 암호화 콘텐트를 기록할 수 있으며, (예를 들어, 재등록에 의해) 이후에 종종 유효한 새로운 키를 얻어 과거 콘텐트를 해독할 수 있다. 본 발명의 바람직한 실시예는, 철회 수신기 집합에, 아직 할당되지 않은 수신기 식별자 모두를 포함시킴으로써, 이러한 시나리오에서 역방향 비밀성의 결여를 치유하기 위해 이용될 수 있다. 이는 모든 수신기들이 순차대로 리프들에 할당되는 경우에 행해질 수 있다. 이러한 경우에, 모든 비할당된 식별자의 철회는 메시지 헤더 크기에 약간의 증가를 가져오지만, 이러한 식별자의 개수에 비례하여 늘어나는 것은 아니다.
본 발명의 바람직한 실시예는 또한 메시지 헤더에서 부집합 ij의 정확한 인코딩을 구비하고 수신기가 부집합 ij에 속하는지를 판단할 수 있는 신속한 방법을 제공하는 것이 바람직함을 인식한다. 노드가 루트로의 경로에 의해 표시되고, 0은 왼쪽 브랜치를 표시하며 1은 오른쪽 브랜치를 표시한다고 가정한다. 경로의 끝부분은 1 다음에 1개 이상의 0비트들이 이어지는 것으로서 표시된다. 따라서, 루트는 1000...000b이고, 루트의 가장 오른쪽 자식은 0100...000b이고, 가장 왼쪽 자식은 11000...000b이고, 리프는 xxxx...xxxx1b이다.
여기서 인식되는 바와 같이, 좀더 큰 부집합 루트의 경로는 좀더 작은 부집합 루트의 경로의 부집합이므로, 부집합 차이는 좀더 작은 부트리의 루트에 큰 부트리 루트까지의 경로 길이를 더한 것에 의하여 표시된다. 이를 이용하여, 수신기 는 이하의 Intel Pentium 프로세서 루프를 실행시킴으로써 자신이 소정의 부집합 내에 있는지를 신속하게 판단할 수 있다.
루프를 벗어나면, 다음의 레지스터들이 셋업된다: ECX는 수신기의 리프 노드를 포함하고, ESI는 메시지 버퍼를 가리키고(첫번째 바이트는 큰 부트리 루트에 대한 경로 길이이고, 다음 4개의바이트는 작은 트리의 루트임), 정적 테이블은 경로 길이에 의해 인덱스될 때 32개 비트들을 출력하는데, 첫 번째 비트는 1이고 나머지 비트들은 0이다.
loop:MOV BYTE EBX, [ESI++]
MOV DWORD EAX, [ESI++]
XOR EAX, ECX
AND EAX, TABLE[EBX]
JNZ loop
수신기가 루프밖으로 나오면, 이는 그가 특정 부집합에 반드시 속하는 것은 아님을 의미한다. 이는 작은 제외된 부트리(smaller executed subtree)내에 있을 수 있으며, 그렇다면 루프로 리턴하여야 한다. 그러나, 대부분의 경우에 수신기들은 더 큰 부트리내도 없기 때문에, 루프에서 처리시간을 거의 보내지 않는다.
더 최적화된 부집합 차이 방법에서, 시스템 서버는 수백만개에 달할 수도 있는 각각의 모든 라벨을 기억할 필요가 없다. 대신에, i번째 노드의 라벨은 노드의 비밀 함수일 수 있다. 비밀 함수는 숫자 i에 적용된다면 I번째 노드의 라벨을 만 들기 위해 비밀 키를 이용하는 3배 DES 암호가 될 수 있다.
이제까지 본 발명의 바람직한 실시예가 이용될 수 있는 부집합-커버 시스템에 관하여 설명하였으므로, 이제는 도 15 및 도 16을 참조한다. 블록(100)에서 시작하여, 부집합 Si1,...Sim 중 파티션(partition) S가 권한있는 추적 에이전시에 의해 획득된 의심대상 해적 클론 디바이스에 입력된다. 초기 파티션은 현재의 철회장치 집합들에 의해 유도되며, 또는, 어떠한 디바이스도 철회되지 않은 경우에, 초기 파티션 S는 모든 사용자들의 집합이다. 결정블록(102)으로 진행하여, 클론이 전술한 부집합-커버 시스템의 원리에 따라 (바람직하게는 부집합-차이 방법의 원리에 따라), 파티션 S를 이용하여 콘텐트를 해독하였는지 여부를 판단한다. 클론이 선정된 확률(예, p>.5)를 갖고 메시지를 해독할 수 있다면 그것은 암호를 해독한 것으로 간주된다. 대부분의 실제 클론들의 경우에, p=1이다. 클론이 해독할 수 없다면, 클론을 무력하게 만든 암호화가 발견된 것이며, 이에 따라 프로세스는 상태(104)에서 종료한다.
그러나, 클론이 성공적으로 콘텐트를 해독한 경우에, 프로세스는 블록(124)로 진행한다. 블록(124)에서, 이하에서 설명될 도 16의 부집합 추적 로직이 파티션 S에 대해 실행되어 부집합 Si,j를 산출하고, 프로세스는 블록(106)으로 진행하여 부집합 Si,j를 수신한다. 부집합 Si,j가 단지 1개의 트레이너 후보자를 갖고 있는지, 즉, 부집합 Si,j가 단지 1개의 리프만을 갖고 있는지가 판단된다. 그렇다면, 트레이터가 발견되고, 프로세스는 단계(110)에서 j번째 디바이스를 "트레이터"로 나타내 고 그것을 비철회 수신기 집합으로부터 제거하는 대신에 철회 수신기들의 집합 R에 둠으로써 철회한다. 이에 의해, 새로운 커버 집합 S가 블록(111)에서 정의되고, 프로세스는 이하에서 더욱 상세히 설명되는 블록(124)으로 진행한다.
부집합 Si,j가 2개 이상의 트레이터 후보자를 갖고 있을때, 로직은 결정 블록(108)에서 블록(112)로 흐르는데, 여기서 집합 Si,j는 2개의 자식 집합 S1 ij 및 S2 ij로 나뉜다. 부집합-커버 시스템의 두갈래(bifurcation) 특성 때문에 가능하며, 부트리들이 대략적으로(꼭 정확하는 것은 아니지만) 2개로 분할될 수 있다.
t개의 트레이터를 추적하기 위해 필요한 메시지들의 길이를 줄임으로써 효율성을 실현시키기 위해, 하나의 바람직한 실시예는 블록(112)로부터 블록(114-122)에 도시된 서브루틴들로 이동할 수 있다. 이들 서브루틴의 기능은 트레이터를 아직 포함하지 않을 부집합들을 하나의 효율적으로 처리되는 그룹으로 병합하는 것이다. 이러한 감소가 바람직하지 않다면, S1 ij 및 S2 ij가 커버에 추가되고 블록(114-122)은 생략된다.
블록(114)에서, 자식 집합 S1 ij 및 S2 ij은 프론티어(frontier) 집합 F에 추가되고 서로 "버디 집합(buddy set)"으로서 연관된다. 다음에, 결정 블록(116)에서, 집합 Sij이 이전의 프론티어 집합 F(즉, 자식 집합 S1 ij 및 S2 ij이 그것에 추가되기 이전에 존재하였던 집합 F)에 있었는지를 판단한다. 그렇다면, 이는 집합 Sij이 프론티어 집합 F내에 또한 존재하였든 상보, 소위, "버디" 집합을 갖고 있었음을 의미하고, (하나 이상의 수신기를 나타내는) "버디"집합은 블록(118)에서 프론티어 집합 F로부터 제거된다. 이러한 방법으로, 아직까지 트레이터 후보를 포함하지 않는 것으로 파악된 집합들은 프론티어 집합 F와 별도로 그룹화된다.
블록(118) 또는 결정블록(116)으로부터 테스트 결과가 부정적이었다면, 로직은 블록(120)으로 진행하는데, 여기서 전술한 부집합-커버 원리에 따라 프론티어 집합 F 내의 집합들로 표시되지 않은 모든 수신기 u에 대한 커버 C가 계산된다. 구체적으로, 프론티어 집합 F 내의 집합들에 의해 표시되지 않은 수신기들은 일시적으로 철회집합 R로 분류되고나서, 전술한 원칙에 따라 커버가 결정된다. 블록(122)에서, 커버 C와 프론티어 집합 F의 부집합들과 합쳐진 것으로 새로운 파티션 S가 정의된다. 그런후에, 도 16의 부집합 추적 로직이 블록(124)에서 새로운 S에 대해 실행되어 또다른 Sij를 산출하고, 로직은 다시 블록(106)으로 돌아간다.
따라서, 이제 도 16의 부집합 추적 로직을 고려하면, 블록(126)에서 파티션 S가 수신된다. 로직은 단계들의 순서를 지배하는데, 전형적인 단계들이 j개의 부집합들이 세션키 K와 동일한 길이를 갖는 거짓키 RK로 인코딩되는 암호화를 수행한다. 즉, 클론이 파티션 S로써 올바르게 해독하는 확률이 p일 때, 메시지는다음과 같은 형태로 산출된다.
<ELi1 (RK),ELi2 (RK), ...,ELij (RK), ELi(j+1) (K),...,ELim (K),FK(M)>.
pj는 j개의 부집합들이 거짓키를 포함할 때 해독 확률이다.
Figure 112005076027911-pct00020
이면, 본 발명의 바람직한 실시예에 따라, Sij는 트레이터를 나타내는 리프를 포함한다. 확률 pj을 구하기 위해, 전체 실험(experiments)의 시퀀스중에서 몇 번이나 클론이 실제의 메시지 M을 출력해 내는지를 판단하기 위해 m2log(l/e)번의 실험이 수행된다. 구체적으로, 클론이 (실제 세션키 K를 암호화하는) 최근 m-j개의 부집합들로부터 어떠한 키도 갖지 않는다면, 그것은 절대로 (우연을 제외하고는) M을 결정할 수 없을 것이다.
이에 따라, 트레이터를 포함하는 Sij를 효율적으로 찾기 위해 이진 서치가 실행되는데, 전체 간격[0,m]에서 시작하여 (130)에서 [0,m]으로 초기화된)상한 및 하한[a,b]을 이용하여 간격을 계속적으로 이분한다. p0 = p이고, pm= 0이다. 대부분의 실제 경우에서, p=1, 즉, 클론은 정상동작중에는 항상 해독한다는 의미이다.
이진 서치는 결정 블록(132)에서 시작하는데, 여기서 상한 및 하한값이 하나 차이인지를(서치의 종료를 나타냄) 판단한다. 그렇다면, 블록(134)에서, 로직은 j번째 트레이터의 인덱스를 상한값 b로서 리턴한다. 그렇지 않다면, 로직은 블록(136)으로 진행하여, 간격[a,b]의 중간지점 c의 확률, 즉, 제1의 c 부집합이 거짓키를 포함하고 나머지들은 참(true) 키를 포함할 때 해독할 수 있는 확률을 구한다.
본 발명의 바람직한 실시예에 따르면, j개의 부집합들이 거짓키를 포함할 때 메시지가 성공적으로 해독되는 확률 pj는 메시지 M과 함께 키 K를 선택하고, Fk(M)으로서 M을 암호화하고, 거짓키를 이용하여 j개의 부집합들을 인코딩하고 참 키 K를 이용하여 m-j개의 부집합들을 인코딩하고, 클론이 M을 성공적으로 해독하는지를 관찰하는 동작을 반복적으로 수행함으로써 계산된다.
결정 블록(138)에서, 중간지점 확률과 하한선의 확률간의 차이의 절대치가 하한선 및 상한선 확률간의 차이의 1/2의 절대치와 적어도 동일한지를, 즉,
Figure 112005076027911-pct00021
를 판단한다. 그렇다면, 블록(140)에서, 상한값 b를 현재 중간값 c로 만들고 상한에서의 확률 pb를 중간지점의 확률 pc로 만듬으로써, 간격은 [a,c]로 하향하여 이분된다. 반면에, 결정 블록(138)에서 부정적인 결과가 나온 경우에는, 로직은 블록(142)으로 진행한다. 블록(142)에서, 하한값 a를 현재 중간값 c로 만들고 하한에서의 확률 pa를 중간지점의 확률 pc로 만듬으로써, 간격은 [c, b]로 상향하여 이분된다. 로직은 다시 결정 블록(132)으로 돌아간다.
블럭(136)에서, 중간값에서의 확률 pc는 바람직하게는 1/m의 정확도로 계산된다. pc가 1-e의 확률로 정확하게 추정되는 것을 보장하기 위해서는 클론에 대한 m2log(1/e) 번 질의를 관찰하는 것이 필요하다.
따라서, 도 16의 로직은 바람직하게 클론에 대해 m2log(m) log(l/e) 번 질의 를 이용한다. 바람직하게는, 각각의 단계에서, 올바른 결정이 얻어질 확률이 1-Q(Q는 1/2에 가까운값, 예, Q=1/3)라고 가정하는 노이지(noisy) 이진 서치가 수행될 수 있다. 각각의 답이 올바를 확률이 히스토리와 무관하게 일정하게 고정되는(예, 2/3보다 큰 값) 모델에서, 중간지점의 확률은 확률 Q의 잘못된 값을 산출할 수 있음을 가정할 수 있다. 이는 확률 1-Q를 갖고 pc를 정확하게 계산하기 위해서는 각 단계에서 m2개의 질의가 필요하기 때문에 전체 프로시져에 걸친 질의 개수는 m2 (logm + log 1/Q)로 줄어들 수 있음을 의미한다.
트레이터들은 동일한 입력을 갖고 클론들에 대하여 추적 알고리즘을 병렬로 실행시킴으로써 하나 이상의 클론으로부터 추적될 수 있다. 초기 입력은 모든 사용자 집합으로부터 발생한 파티션 S0인데, 아무도 철회 집합 R에 포함되어 있지 않다. 프로세스가 진행함에 따라, 제1의 클론이 그의 집합중 하나에서 트레이터를 "감지하면", (트레이터를 철회집합 R로 이동시킴으로써) 재분할한다(re-partition). 새로운 파티션은 동시에 모든 클론들에게 입력된다. 동시 방법의 출력은 모든 철회수신기들과 클론들을 무효로 만드는 파티션 (또는 "철회 전략")이다.
본 발명의 바람직한 실시예는 상대적으로 작은 메시지를 이용하여 상대적으로 많은 수의 트레이터들을 추적할 수 있는 능력을 제공한다. 전술한 부집합-커버 시스템으로 경계없이 통합될 수 있다. 또한, 추적될 트레이터 개수에 대한 사전 제한치를 필요로 하지 않는다. 본 발명의 바람직한 실시예는 트레이터를 추적하거나 또는 클론이 추적에 맞서서 어떠한 작업을 하든지에 상관없이 해적 클론들을 쓸모없게 만듬으로써 기능한다
본 명세서에서 도시되고 상세히 설명된 특정의 "브로드캐스트 암호 시스템에서 트레이터 수신기들을 추적하는 방법"은 본 발명의 전술한 목적들을 완전히 달성하였으나, 이는 현재 본 발명의 바람직한 실시예에 불과하며 본 발명의 바람직한 실시예에 의해 넓게 고려된 발명을 대표한 것임, 본 발명의 범위는 본 기술분야의 당업자들에게 명백한 다른 실시예들도 모두 포함하는 것이며, 따라서, 본 발명의 범위는 첨부된 클레임들 이외에는 그 어떠한 것에 의해서 제한되지 않는다. 청구항에서 단수로 지칭된 요소는, 청구항에 다르게 기재되어 있지 않은 한, "단지 하나"가 아니라 "적어도하나"를 의미하는 것이다. 본 기술분야의 당업자들에게 공지되거나 이후에 공지될 전술한 바람직한 실시예들의 요소들에 대한 구조적 및 기능적 균등물들은 명백히 본 명세서의 일부로 참조되며 청구항에 의해 포함되는 것이다. 더욱이, 본 발명의 바람직한 실시예에 의해 해결하고하 하는 모든 각각의 문제를 처리하는 것이 반드시 장치이거나 방법이 아니더라도 청구범위에 의해 포함된다. 본 명세서에에 개시된 어떠한 요소, 컴포넌트 또는 방법 단계도, 그것들이 청구항에 명백하게 개시된것인지에 상관없이, 공중에게 기증되려는 것은 아니다. 청구항의 요소가 "수단"이라는 용어를 이용하여, 또는 방법 청구항의 경우에는 "동작(act)" 대신에 "단계"로서 명백하게 기재되지 않은 한, 청구항의 어떠한 요소도 미국특허법 제112조 제6항의 규정에 따라 해석되어서는 아니될 것이다.

Claims (13)

  1. 브로드캐스트 암호 시스템에서 적어도 하나의 손상된(compromised) 해독키를 갖는 적어도 하나의 트레이터(traitor) 수신기를 식별 또는 디스에이블링하는 방법에 있어서,
    리프들(leaves)을 정의하는 트리로부터 파생된 부집합 세트(a set of subsets)를 수신하는 단계 -상기 트리내의 각각의 리프(leaf)는 각각의 수신기를 나타냄- 와,
    후보(candidate) 트레이터 수신기를 나타내는 적어도 하나의 리프를 포함하는 적어도 하나의 트레이터 부집합을 상기 부집합 세트로부터 식별하는 단계와,
    상기 트레이터 부집합을 이용하여, 상기 트레이터 수신기를 식별하거나 또는 디스에이블링하는 단계중 적어도 하나를 시작하는 단계와,
    상기 트레이터 부집합이 적어도 두개의 후보 트레이터 수신기를 나타내는지 여부를 판단하는 단계와, 그러한 경우에는 상기 트레이터 부집합을 2개의 자식집합(child set)으로 나누는 단계 -상기 식별 또는 디스에이블링 단계는 상기 부집합 세트내의 다수의 부집합들을 거짓키(false key)로 인코딩하는 단계를 포함함-
    를 포함하는 방법.
  2. 삭제
  3. 제1항에 있어서, 상기 트레이터 부집합이 프론티어(frontier) 집합의 구성원인지를 판단하는 단계와, 상기 트레이터 부집합이 프론티어 집합의 구성원이라면 상기 프론티어 집합으로부터 상보(complementary) 부집합을 제거하는 단계를 더 포함하는 방법.
  4. 삭제
  5. 제1항에 있어서, 확률을 이용하여 상기 부집합 세트에 대하여 이진 서치(binary search)를 실행하는 단계를 더 포함하는 방법.
  6. 제5항에 있어서, 상기 이진 서치는 j개의 부집합들이 거짓키를 포함할 때 메시지를 해독할 확률 pj와 j-1개의 부집합들이 거짓키를 포함할 때 메시지를 해독할 확률 pj-1간의 차이가 선정된 확률과 적어도 동일한지를 판단함으로써 종료하는 방법.
  7. 제6항에 있어서, 상기 트레이터 부집합은
    Figure 112005076027911-pct00022
    일 때 식별되며, 여기서 m은 상기 부집합 세트내의 부집합 개수인 방법.
  8. 삭제
  9. 삭제
  10. 삭제
  11. 삭제
  12. 컴퓨터로 판독가능한 매체를 포함하는 디바이스에 있어서,
    상기 컴퓨터로 판독가능한 매체는
    트리의 부집합 세트를 생성하기 위하여 상기 트리에 엑세스하기 위한 로직 수단 -상기 트리는 손상된 키에 의해 특정되는 적어도 하나의 트레이터 디바이스를 나타내는 리프들을 포함함- 과,
    거짓키를 j번 암호화하고 세션키를 m-j번 암호화하기 위한 로직 수단 -상기 m은 상기 부집합 세트내의 부집합 개수임- 과,
    상기 암호화하기 위한 로직 수단에 반응하여 트레이터 부집합을 식별하기 위한 로직 수단과,
    상기 트레이터 부집합을 이용하여 상기 트레이터 디바이스를 식별 또는 디스에이블링하기 위한 로직 수단
    을 포함하는 디바이스.
  13. 상태 비유지 수신기들을 나타내는 다수의 부집합들을 인코딩하는데 거짓키를 이용하는 단계 -상기 수신기들중 적어도 하나의 트레이터 수신기는 적어도 하나의 해적 수신기에 의해 얻어진 적어도 하나의 손상된 키와 연관됨- 와,
    상기 해적 수신기 또는 그것의 클론을 이용하여 상기 트레이터 수신기의 식별자를 판단하거나 또는 상기 해적 수신기 또는 그것의 클론이 상기 손상된 키를 이용하여 데이터를 해독할 수 없도록 만드는 단계를 포함하는 방법을 컴퓨터가 실행하도록하는 명령(instruction)으로 프로그램된 컴퓨터.
KR1020037009629A 2001-01-26 2002-01-23 브로드캐스트 암호화 시스템에서 트레이터 수신기들을추적하기 위한 방법 KR100562982B1 (ko)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
US09/771,239 US7010125B2 (en) 2001-01-26 2001-01-26 Method for tracing traitor receivers in a broadcast encryption system
US09/771,239 2001-01-26
PCT/GB2002/000312 WO2002060118A2 (en) 2001-01-26 2002-01-23 Method for tracing traitor receivers in a broadcast encryption system

Publications (2)

Publication Number Publication Date
KR20030085126A KR20030085126A (ko) 2003-11-03
KR100562982B1 true KR100562982B1 (ko) 2006-03-23

Family

ID=25091165

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020037009629A KR100562982B1 (ko) 2001-01-26 2002-01-23 브로드캐스트 암호화 시스템에서 트레이터 수신기들을추적하기 위한 방법

Country Status (10)

Country Link
US (1) US7010125B2 (ko)
EP (1) EP1354444B1 (ko)
JP (1) JP2004527937A (ko)
KR (1) KR100562982B1 (ko)
CN (1) CN1310463C (ko)
AT (1) ATE411665T1 (ko)
DE (1) DE60229354D1 (ko)
HK (1) HK1068513A1 (ko)
TW (1) TWI222302B (ko)
WO (1) WO2002060118A2 (ko)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8229121B2 (en) 2008-06-09 2012-07-24 Samsung Electronics Co., Ltd. Method of tracing device keys for broadcast encryption

Families Citing this family (62)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP1111923A1 (en) * 1999-12-22 2001-06-27 Irdeto Access B.V. Method for operating a conditional access system for broadcast applications
CN100401667C (zh) * 2000-06-21 2008-07-09 索尼公司 信息记录/再生装置及方法
US9520993B2 (en) 2001-01-26 2016-12-13 International Business Machines Corporation Renewable traitor tracing
JP2002319932A (ja) * 2001-04-19 2002-10-31 Sony Corp 情報記録装置、情報再生装置、および情報記録方法、情報再生方法、並びにプログラム
JP3917507B2 (ja) * 2002-01-28 2007-05-23 株式会社東芝 コンテンツ提供側システム、ユーザ側システム、追跡システム、コンテンツ提供方法、暗号化コンテンツ復号方法、不正ユーザ特定方法、暗号化装置、復号装置及びプログラム
US7450722B2 (en) * 2002-12-13 2008-11-11 General Instrument Corporation Subset difference method for multi-cast rekeying
US20040128259A1 (en) * 2002-12-31 2004-07-01 Blakeley Douglas Burnette Method for ensuring privacy in electronic transactions with session key blocks
BRPI0406777B1 (pt) * 2003-01-15 2017-12-26 Matsushita Electric Ind Co Ltd sistema de proteção de conteúdo, aparelho de geração de dados de chave e aparelho terminal
FR2850826B1 (fr) * 2003-02-04 2005-04-01 Medialive Procede et dispositif de protection pour la diffusion securisee d'oeuvres audiovisuelles
JP4625011B2 (ja) * 2003-05-21 2011-02-02 株式会社エヌ・ティ・ティ・ドコモ Ｒｓａを用いるブロードキャスト暗号
FR2856539A1 (fr) * 2003-06-17 2004-12-24 France Telecom Procede et systeme tracables de chiffrement et/ou de dechiffrement d'informations, et supports d'enregistrement pour la mise en oeuvre du procede
CN1833400B (zh) * 2003-08-05 2011-12-28 松下电器产业株式会社 著作权保护系统
JP4161859B2 (ja) 2003-09-11 2008-10-08 ソニー株式会社 情報処理装置、情報記録媒体、および情報処理方法、並びにコンピュータ・プログラム
US8180059B2 (en) * 2003-11-28 2012-05-15 Panasonic Corporation Management apparatus, terminal apparatus, and copyright protection system
KR100579515B1 (ko) * 2004-10-08 2006-05-15 삼성전자주식회사 브로드캐스트 암호화를 위한 키 생성 장치 및 방법
US7454021B2 (en) * 2004-10-29 2008-11-18 Hewlett-Packard Development Company, L.P. Off-loading data re-encryption in encrypted data management systems
KR101092543B1 (ko) * 2004-11-12 2011-12-14 삼성전자주식회사 브로드캐스트 암호화를 위한 사용자 키 관리 방법
US8090105B2 (en) * 2004-11-24 2012-01-03 International Business Machines Corporation Broadcast encryption with dual tree sizes
JP4599194B2 (ja) * 2005-03-08 2010-12-15 株式会社東芝 復号装置、復号方法、及びプログラム
KR100717005B1 (ko) * 2005-04-06 2007-05-10 삼성전자주식회사 폐기 키를 결정하는 방법 및 장치와 이것을 이용하여복호화하는 방법 및 장치
WO2006112635A1 (en) * 2005-04-19 2006-10-26 Samsung Electronics Co., Ltd Tag generation method in broadcast encryption system
KR100970391B1 (ko) 2005-04-19 2010-07-15 삼성전자주식회사 브로드 캐스트 암호화 시스템에서의 태그 형성방법
US8161296B2 (en) * 2005-04-25 2012-04-17 Samsung Electronics Co., Ltd. Method and apparatus for managing digital content
US7711114B2 (en) * 2005-09-19 2010-05-04 International Business Machines Corporation System and method for assigning sequence keys to a media player to enable flexible traitor tracing
US7630497B2 (en) * 2005-09-19 2009-12-08 International Business Machines Corporation System and method for assigning sequence keys to a media player to enable hybrid traitor tracing
KR100803596B1 (ko) * 2005-11-25 2008-02-19 삼성전자주식회사 폐기 메커니즘 상에서 외부 디바이스 또는 서비스를이용하는 복호화 방법 및 장치, 이를 위한 복호화 지원방법 및 장치
US8176568B2 (en) * 2005-12-30 2012-05-08 International Business Machines Corporation Tracing traitor coalitions and preventing piracy of digital content in a broadcast encryption system
US7756035B2 (en) * 2006-01-31 2010-07-13 Nortel Networks Limited Planning routes and allocating identifiers to routes in a managed frame-forwarding network
FR2899748B1 (fr) * 2006-04-07 2008-11-28 Thales Sa Schema de diffusion hybride efficace, adapte a une faible bande passante
US8121289B2 (en) * 2006-05-31 2012-02-21 France Telecom Cryptographic method with integrated encryption and revocation, system, device and programs for implementing this method
EP1890493A1 (fr) * 2006-08-17 2008-02-20 Nagracard S.A. Méthode de révocation de modules de sécurité utilisés pour sécuriser des messages diffusés
JP4984827B2 (ja) * 2006-10-30 2012-07-25 ソニー株式会社 鍵生成装置、暗号化装置、受信装置、鍵生成方法、暗号化方法、鍵処理方法、およびプログラム
US7986787B2 (en) * 2006-12-08 2011-07-26 International Business Machines Corporation System, method, and service for tracing traitors from content protection circumvention devices
CN101578813A (zh) * 2007-01-11 2009-11-11 皇家飞利浦电子股份有限公司 跟踪实现的拷贝
US8290157B2 (en) * 2007-02-20 2012-10-16 Sony Corporation Identification of a compromised content player
US7876895B2 (en) * 2007-05-09 2011-01-25 International Business Machines Corporation System, method, and service for performing unified broadcast encryption and traitor tracing for digital content
US7975313B2 (en) 2007-08-14 2011-07-05 International Business Machines Corporation System and method for tracing Tardos fingerprint codes
US8824685B2 (en) * 2007-10-15 2014-09-02 Sony Corporation Method for detection of a hacked decoder
EP2068490A1 (en) 2007-12-05 2009-06-10 Nagravision S.A. Method to generate a private key in a Boneh-Franklin scheme
EP2073431A1 (en) 2007-12-21 2009-06-24 Nagravision S.A. Method to trace traceable parts of original private keys in a public-key cryptosystem
US7936882B2 (en) * 2008-01-17 2011-05-03 Nagravision S.A. Method to trace traceable parts of original private keys in a public-key cryptosystem
US8306220B2 (en) * 2008-01-17 2012-11-06 Nagravision S.A. Method to generate a private key in a boneh-franklin scheme
US8499149B2 (en) * 2008-02-20 2013-07-30 Hewlett-Packard Development Company, L.P. Revocation for direct anonymous attestation
US9729316B2 (en) * 2008-02-27 2017-08-08 International Business Machines Corporation Unified broadcast encryption system
CN101534428B (zh) * 2008-03-12 2011-01-19 北京视博数字电视科技有限公司 一种动态叛逆者追踪方法及系统
CN101534429B (zh) * 2008-03-12 2011-02-09 北京视博数字电视科技有限公司 盗版者追踪方法和系统
US8122501B2 (en) * 2008-06-20 2012-02-21 International Business Machines Corporation Traitor detection for multilevel assignment
US8108928B2 (en) * 2008-06-20 2012-01-31 International Business Machines Corporation Adaptive traitor tracing
EP2151763A1 (en) * 2008-07-28 2010-02-10 Nagravision S.A. Method and apparatus for obfuscating virtual to physical memory mapping
US8422684B2 (en) * 2008-08-15 2013-04-16 International Business Machines Corporation Security classes in a media key block
US8897448B2 (en) * 2008-10-31 2014-11-25 Ciena Corporation Controlling session keys through in-band signaling
US8189789B2 (en) * 2008-11-03 2012-05-29 Telcordia Technologies, Inc. Intrusion-tolerant group management for mobile ad-hoc networks
US8571209B2 (en) 2009-01-19 2013-10-29 International Business Machines Recording keys in a broadcast-encryption-based system
US9455992B2 (en) * 2009-06-12 2016-09-27 Microsoft Technology Licensing, Llc Trusted hardware component for distributed systems
US8934626B2 (en) * 2010-03-03 2015-01-13 Nagravision S.A. Method to manage revocations in a group of terminals
EP2393292A1 (en) 2010-06-01 2011-12-07 Nagravision S.A. A method and apparatus for decrypting encrypted content
US8396896B2 (en) * 2010-11-10 2013-03-12 International Business Machines Corporation Assigning resources to a binary tree structure
US9071421B2 (en) 2010-12-15 2015-06-30 Microsoft Technology Licensing, Llc Encrypted content streaming
MX2013011549A (es) 2011-04-15 2013-11-01 Nagravision Sa Metodo para identificar el origen de un modulo de seguridad en un sistema decodificador de television de paga.
US10467384B2 (en) * 2016-05-18 2019-11-05 International Business Machines Corporation Subset-difference broadcast encryption with blacklisting
EP3280146A1 (en) * 2016-08-04 2018-02-07 Nagravision SA Traitor tracing
US10104088B2 (en) 2016-09-28 2018-10-16 International Business Machines Corporation Traitor tracing for obfuscated credentials

Family Cites Families (20)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4417338A (en) * 1981-04-13 1983-11-22 Wisconsin Alumni Research Foundation Cryptographic key sharing circuit and method using code correction
JPH03272293A (ja) * 1990-03-22 1991-12-03 Pioneer Electron Corp テレビジョン信号のスクランブル方法および装置
US5124984A (en) * 1990-08-07 1992-06-23 Concord Communications, Inc. Access controller for local area network
US5241597A (en) 1991-02-01 1993-08-31 Motorola, Inc. Method for recovering from encryption key variable loss
US5675649A (en) 1995-11-30 1997-10-07 Electronic Data Systems Corporation Process for cryptographic key generation and safekeeping
US5812670A (en) 1995-12-28 1998-09-22 Micali; Silvio Traceable anonymous transactions
US5748736A (en) 1996-06-14 1998-05-05 Mittra; Suvo System and method for secure group communications via multicast or broadcast
US5974151A (en) * 1996-11-01 1999-10-26 Slavin; Keith R. Public key cryptographic system having differential security levels
DE19649292A1 (de) * 1996-11-28 1998-06-04 Deutsche Telekom Ag Verfahren zum Sichern eines durch eine Schlüsselhierarchie geschützten Systems
US6285991B1 (en) 1996-12-13 2001-09-04 Visa International Service Association Secure interactive electronic account statement delivery system
US5920861A (en) 1997-02-25 1999-07-06 Intertrust Technologies Corp. Techniques for defining using and manipulating rights management data structures
JP4062367B2 (ja) * 1997-03-21 2008-03-19 カナル プラス ソシエテ アノニム Ｍｐｅｇ受信機／デコーダ及びデータをｍｐｅｇ受信機／デコーダにダウンロードする方法
US6397329B1 (en) 1997-11-21 2002-05-28 Telcordia Technologies, Inc. Method for efficiently revoking digital identities
US6098056A (en) 1997-11-24 2000-08-01 International Business Machines Corporation System and method for controlling access rights to and security of digital content in a distributed information system, e.g., Internet
US6247127B1 (en) 1997-12-19 2001-06-12 Entrust Technologies Ltd. Method and apparatus for providing off-line secure communications
US6118873A (en) * 1998-04-24 2000-09-12 International Business Machines Corporation System for encrypting broadcast programs in the presence of compromised receiver devices
IL126472A0 (en) 1998-10-07 1999-08-17 Nds Ltd Secure communications system
TW460846B (en) * 1998-12-10 2001-10-21 Toshiba Corp Data recording media having certification information
US6684331B1 (en) 1999-12-22 2004-01-27 Cisco Technology, Inc. Method and apparatus for distributing and updating group controllers over a wide area network using a tree structure
WO2002052778A2 (en) 2000-12-22 2002-07-04 Koninklijke Philips Electronics N.V. Conditional access system

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8229121B2 (en) 2008-06-09 2012-07-24 Samsung Electronics Co., Ltd. Method of tracing device keys for broadcast encryption

Also Published As

Publication number Publication date
WO2002060118A2 (en) 2002-08-01
US7010125B2 (en) 2006-03-07
TWI222302B (en) 2004-10-11
CN1310463C (zh) 2007-04-11
ATE411665T1 (de) 2008-10-15
KR20030085126A (ko) 2003-11-03
HK1068513A1 (en) 2005-04-22
WO2002060118A3 (en) 2002-09-19
EP1354444A2 (en) 2003-10-22
CN1554163A (zh) 2004-12-08
US20020133701A1 (en) 2002-09-19
DE60229354D1 (de) 2008-11-27
JP2004527937A (ja) 2004-09-09
EP1354444B1 (en) 2008-10-15

Similar Documents

Publication Publication Date Title
KR100562982B1 (ko) 브로드캐스트 암호화 시스템에서 트레이터 수신기들을추적하기 위한 방법
KR100543630B1 (ko) 브로드캐스트 암호화 및 상태 비유지 수신기들의 키 철회방법
US7613302B2 (en) Systems and methods for compression of key sets having multiple keys
US8023655B2 (en) System, method, and service for tracing traitors from content protection circumvention devices
WO2001013571A1 (en) Systems and methods for compression of key sets having multiple keys
JP2000031922A (ja) 放送番組を暗号化するためのシステムおよび方法
KR20100020481A (ko) 암호 키 데이터 갱신
JP2009509371A (ja) 更新可能なトレイタ追跡
KR20080031751A (ko) 키 블록 기반의 인증 시스템 및 방법
KR20090127716A (ko) 브로드캐스트 암호화에서 디바이스 키를 추적하는 방법
EP2286610B1 (en) Techniques for peforming symmetric cryptography
US20050125356A1 (en) Method and apparatus for decrypting encrypted data by suing copy control information and computer readable recording medium for storing program for implementing the apparatus and method
JP2008092514A (ja) 情報処理装置、および情報処理方法、並びにコンピュータ・プログラム
JP2004229128A (ja) 暗号データ配信システム、および情報処理装置、情報処理方法、並びにコンピュータ・プログラム
Broadnax et al. Towards Efficient Software Protection Obeying Kerckhoffs's Principle using Tamper-proof Hardware.
JP2004320183A (ja) 情報処理装置、および情報処理方法、並びにコンピュータ・プログラム

Legal Events

Date Code Title Description
PA0105 International application

Patent event date: 20030721

Patent event code: PA01051R01D

Comment text: International Patent Application

A201 Request for examination
PA0201 Request for examination

Patent event code: PA02012R01D

Patent event date: 20030822

Comment text: Request for Examination of Application

PG1501 Laying open of application
E902 Notification of reason for refusal
PE0902 Notice of grounds for rejection

Comment text: Notification of reason for refusal

Patent event date: 20051028

Patent event code: PE09021S01D

E701 Decision to grant or registration of patent right
PE0701 Decision of registration

Patent event code: PE07011S01D

Comment text: Decision to Grant Registration

Patent event date: 20060306

GRNT Written decision to grant
PR0701 Registration of establishment

Comment text: Registration of Establishment

Patent event date: 20060314

Patent event code: PR07011E01D

PR1002 Payment of registration fee

Payment date: 20060313

End annual number: 3

Start annual number: 1

PG1601 Publication of registration
PR1001 Payment of annual fee

Payment date: 20090226

Start annual number: 4

End annual number: 4

PR1001 Payment of annual fee

Payment date: 20091231

Start annual number: 5

End annual number: 5

PR1001 Payment of annual fee

Payment date: 20110201

Start annual number: 6

End annual number: 6

PR1001 Payment of annual fee

Payment date: 20120229

Start annual number: 7

End annual number: 7

FPAY Annual fee payment

Payment date: 20130304

Year of fee payment: 8

PR1001 Payment of annual fee

Payment date: 20130304

Start annual number: 8

End annual number: 8

FPAY Annual fee payment

Payment date: 20140217

Year of fee payment: 9

PR1001 Payment of annual fee

Payment date: 20140217

Start annual number: 9

End annual number: 9

FPAY Annual fee payment

Payment date: 20150227

Year of fee payment: 10

PR1001 Payment of annual fee

Payment date: 20150227

Start annual number: 10

End annual number: 10

FPAY Annual fee payment

Payment date: 20160229

Year of fee payment: 11

PR1001 Payment of annual fee

Payment date: 20160229

Start annual number: 11

End annual number: 11

FPAY Annual fee payment

Payment date: 20170227

Year of fee payment: 12

PR1001 Payment of annual fee

Payment date: 20170227

Start annual number: 12

End annual number: 12

FPAY Annual fee payment

Payment date: 20180227

Year of fee payment: 13

PR1001 Payment of annual fee

Payment date: 20180227

Start annual number: 13

End annual number: 13

FPAY Annual fee payment

Payment date: 20190227

Year of fee payment: 14

PR1001 Payment of annual fee

Payment date: 20190227

Start annual number: 14

End annual number: 14

FPAY Annual fee payment

Payment date: 20200227

Year of fee payment: 15

PR1001 Payment of annual fee

Payment date: 20200227

Start annual number: 15

End annual number: 15

PC1801 Expiration of term

Termination date: 20220723

Termination category: Expiration of duration