Copyright protection plays an important role in content distribution such as pay-TV, DVD-ROM distribution, etc. Both a content supplier and users can get the benefit of appropriate copyright protection in the sense that the content supplier can offer the digital contents to users without concern about the piracy and the users can enjoy up-to-date contents with higher quality.

We consider the following content distribution system in which the contents should be available only to authorized users. The content supplier broadcasts an encrypted version of the digital contents （e.g., a movie） to subscribers （users）, and only users can decrypt them with their decryption devices （decoders） in which their decryption keys are embedded. In this system, there are two kinds of piracy malicious users （traitors） might commit in order to allow the non-users to have illegal access to the contents. One is the redistribution of the decryption key, e.g., the traitors construct a pirated version of a decoder （pirate decoder） using their decryption keys and sell it at the black market. The other is the redistribution of the contents themselves. In this thesis, we focus on a countermeasure against the former piracy since, from the traitors' view, the risk of being detected in the former piracy is lower than in the latter one. In the former piracy, the leaked decryption keys can also be used to illicitly obtain any contents distributed in the system once the traitors redistribute their decryption keys, while the traitors have to redistribute each of the entire contents in the latter one, although it is also a serious problem.

As a deterrent to the piracy, traitor tracing has been studied extensively. Since a traitor tracing scheme can identify at least one of the traitors from the pirate decoder, it can discourage them from committing the piracy. There are two desirable properties to be supported in a traitor tracing scheme. One is black-box tracing and the other is public-key setting. In black-box tracing, a tracer, who performs tracing, can identify the traitor（s） without breaking open the pirate decoder, i.e., in a black-box manner. Since it is assured that the traitor（s） can be identified no matter how the pirate decoder is implemented, it is desirable to support black-box tracing. In the public-key setting, there are one or more public keys corresponding to the decryption keys of the users. Since no secret information is needed to encrypt the contents and to execute the tracing algorithm, anyone can work as a content supplier and/or a tracer. This property is desirable as well because of the following two reasons: （i） it enhances the sender-scalability in the sense that plural content suppliers can use the same system and （ii） it provides public availability of the tracing algorithm, which can be a stronger deterrent to the piracy. We propose public-key black-box tracing schemes. All of the proposed schemes are proved to be secure under the decision Diffie-Hellman assumption, which is one of the standard intractability assumptions. Each scheme is also analyzed in terms of efficiency.

First, we propose a new type of revocation scheme for efficient public-key black-box traitor tracing. Our revocation scheme is flexible and efficient in the sense that （i） any number of subscribers can be revoked in each distribution under an assumption that the number of revoked subscribers who collude in one coalition is limited to a threshold and （ii） all of the required storage at each user, the transmission overhead, and the public-key size are independent of n, while （i） the maximum number of revoked ones cannot be changed or （ii） at least one of the three depends on n in previous schemes, where n is the total number of users. The flexibility in revocation is significant since flexible revocation can be integrated with efficient black-box tracing and this integration can be achieved without a substantial increase in the transmission overhead over the previous schemes. In this chapter, we show a concrete construction of an efficient public-key black-box traceable and revocable scheme by combining flexible revocation with a known black-box tracing algorithm which works under the same attack model as assumed in the previous schemes. Our scheme achieves that （i） the required storage at each user is constant, （ii） the transmission overhead remains efficient, especially linear only in k in case of bulk revocation and （iii） the public-key size is linear only in k, while the previous ones cannot satisfy all of these properties, where k is the maximum number of traitors in a coalition.

Secondly, we suppose stronger pirates against which the first proposed scheme cannot work. Here, we propose a public-key traitor tracing scheme in which （i） the size of a ciphertext is sublinear in n, actually of the order of the square root of n and （ii） black-box tracing is efficiently achieved against the stronger pirates. When assuming that a pirate decoder can take some self-defensive reaction （e.g., erasing all of the internal keys and shutting down） to escape from tracing if it detects tracing, it has been an open question to construct a sublinear black-box tracing scheme that can detect efficiently at least one traitor with overwhelming probability, although a tracing algorithm that works successfully against self-defensive pirate decoders itself is known. In this chapter, we answer affirmatively this question by presenting a concrete construction of a public-key black-box tracing scheme in which the known tracing algorithm can be used while keeping the size of a ciphertext sublinear.

Finally, we improve our second scheme from the viewpoint of the ciphertext size. We propose a hierarchical key-assignment method which can be used to construct a public-key black-box tracing scheme in which （i） the size of a ciphertext can be reduced to O（k+log（n/k）） without a substantial increase in the size of a secret key and （ii） black-box tracing can be performed against self-defensive pirate decoders. In this chapter, we show a concrete construction of a public-key black-box tracing scheme by using our hierarchical key assignment method. Additionally, we point out that our black-box tracing scheme can also be used as an anonymous revocation scheme in which the identity of a revoked receiver cannot be revealed to the other receivers. Moreover, we present a combined scheme in which the mechanism of flexible revocation in the first proposal is integrated into our black-box tracing scheme.

本論文は「Black-Box Traitor Tracing Schemes for Copyright Protection（著作権保護のためのブラックボックス不正者追跡方式に関する研究）」と題し，コンテンツ配信システムなど多数の受信者が存在する暗号通信において，不正な受信者が復号鍵を第三者へ漏洩させた場合，この不正な漏洩者を特定可能な暗号方式（不正者追跡方式）を提案し，その安全性及び効率性について厳密な評価を行ったものである．本論文では，不正者追跡において望ましい性質であるブラックボックス追跡可能性（復号器の入出力を観測するのみで不正者の特定を行うことができること）と公開鍵方式に基づいていること（暗号化を公開情報である公開鍵のみで行うことができること）に焦点を当て，これらの性質を満たす実用的な不正者追跡方式を提案している．従来の不正者追跡方式では，不正者の追跡に要する処理量が過大で実際上追跡不可能であるという問題や，より強力な不正者に対しては追跡が失敗するという問題があり，これらの問題が実用化へ向けた大きな課題となっている．本論文は，これらの問題に対し，有効な解決策を示したものであり，論文の構成は「Overview of This Thesis」を含め5章からなる．

第1章は「Overview of This Thesis（論文の概要）」で，本研究の背景を明らかにした上で，研究の動機と目的について言及し，研究の位置付けについて整理している．

第2章は「Flexible Revocation for Efficient Public-Key Black-Box Tracing（効率的な公開鍵方式に基づいたブラックボックス追跡のための柔軟な復号鍵無効化）」と題し，一度に無効化できる復号鍵（すなわちユーザ）数に制限がないという意味で柔軟な復号鍵無効化方法を提案し，その復号鍵無効化方法はブラックボックス追跡に応用可能であることを示している．また，従来の不正者追跡方式においては不正者の追跡に要する処理量が過大で実際上追跡不可能であるという問題があったが，提案方式では，この問題が解決されることも示している．提案方式の安全性は，計算量的な仮定（Diffie-Hellman仮定）に基づいて数学的に証明されている．また，効率性について，復号鍵サイズや暗号文サイズなどの観点から評価が行われている．本章以降についても，全ての提案方式は，計算量的な仮定（Diffie-Hellman仮定）に基づいて安全であることが数学的に証明されており，また，復号鍵サイズや暗号文サイズなどの観点から効率性評価が行われている．

第3章は「Public-Key Black-Box Tracing with Sublinear Ciphertext Size against Self-Defensive Pirates（暗号文サイズが全ユーザ数に比例せずより強力な不正者に対しても追跡可能な公開鍵方式に基づいたブラックボックス追跡）」と題し，追跡を察知した場合，追跡を回避するような機構を備えているという意味でより強力な不正者を想定した場合でも，ブラックボックス追跡可能な方式を提案し，より強力な不正者に対して追跡が失敗するという問題が解決されることを示している．提案方式は，このような仮定の下で，暗号文サイズが全ユーザ数に比例しない（sublinearである）初めての方式である．

第4章は「Hierarchical Key Assignment for Efficient Public-Key Black-Box Tracing against Self-Defensive Pirates（効率的でより強力な不正者に対しても追跡可能な公開鍵方式に基づいたブラックボックス追跡のための階層的な復号鍵割り当て）」と題し，第3章で提案した方式に対して，復号鍵サイズを僅かに増加させることにより暗号文サイズを大幅に削減できる階層的な復号鍵割り当て方法を提案している．また，ブラックボックス追跡と匿名性を有する復号鍵無効化との関係について指摘し，さらに，特定された不正者の排除を目的として，第2章で提案した復号鍵無効化方法と本章の提案方式を統合した方式も提案している．

最後に第5章は「Conclusion（結論）」で，本研究の総括を行い，併せて将来展望について述べている．

以上これを要するに，本論文は，不正に対する抑止力となるブラックボックス不正者追跡の基礎検討を行うとともに，従来方式における問題点を解決する具体的方法を明示したものであり，電子情報学，特に情報セキュリティ工学において貢献するところが少なくない．

よって本論文は博士（情報理工学）の学位請求論文として合格と認められる．