In this thesis, three main cryptographic schemes are proposed which utilize general broadcast channels. In each of these schemes, broadcast channels will the used to improve communication efficiency, anonymity, and deniability where appropriate. The first scheme focuses on improving the efficiency of mass communication using broadcast encryption over hierarchal service sets. Broadcast encryption involves securely sending an encrypted message over a broadcast channel such that only members of a dynamic user set can decode this message. The second scheme allows an arbitrary set of users to generate a common group key or private key with member remaining anonymous within this user set. The final scheme is a novel general auction scheme that allows the auction results to be deniable by the auctioneer. This ensures that the provability of all notifications send by the auctioneer stay contained within the set of register members.

The first chapter introduces the structure of the thesis, motivations for the proposed research, and outlines the major contributions of the thesis to the audience. The overlying theme of the thesis is that utilizing broadcast channels allows for very efficient one-to-many mass communication and also allows for natural verification since all information transmitted is publicly broadcasted. Using broadcast channels, key management schemes and deniability preserving communication systems can be improved and extended. Figure 1 below shows how each of the three proposed schemes related to thesis.

The second chapter introduces the audience to the main mathematical tools and the cryptographic primitives or tools used in the subsequent chapters. The first half of the chapter focuses mainly on algebraic groups of prime finite size and Fermat's Little Theorem is also derived. The second half of the chapter introduces many of the cryptographic tools - hash functions, public-key encryption, digital signatures, and zero-knowledge proofs - used to build more complicated communication system in later chapters.

The third chapter focuses on broadcast encryption schemes that attempt to efficiently and securely send a single message to a single dynamic group of user (non-revoked user set). Only users in the non-revoked user set have the capability to decrypt the ciphertext sent over a broadcast channel. By modifying the Chick-Tavares Key Management Scheme, the proposed broadcast encryption scheme improves bandwidth and memory efficiency in the general case with multiple messages and multiple non-revoked user sets. This proposed scheme also preserves forward compatibility while simultaneously maintaining forward and backwards security. Lastly, the proposed scheme is general enough to accommodate both stateless and non-stateless receivers.

In chapter 4, a deniable group/private key establishment scheme is proposed. This proposed deniable key establishment scheme allows both the initiator (Alice) and potential multiple recipients (Bob) to generate either a deniable group key or a deniable private key. Alice wishes to remain anonymous throughout the process and similarly Bob would also wish to remain anonymous. However, Alice wants to ensure that the anonymous counterparty is someone within her target group of counterparties.

The scheme proposed in this thesis modifies Naor's ring authentication scheme to include group and private key establishment. Group key establishment generates a common key computable by all members in the user set S. On the other hand, private key establishment generates a private key computable by only two members - Alice and (single) Bob.

In addition, two protocols were proposed with differing levels of anonymity for Alice shown in Fig. 3. The strongly anonymous initiator protocol (SAIP) allows Alice to remain perfectly anonymous since there are no restrictions on her being within or outside user set S. The weakly anonymous initiator protocol (WAIP) forces Alice to choose a target user set S such that Alice is also in that set.

In chapter 5, two main auctioneer-deniable single-item auctions are proposed. This proposed auction scheme satisfies many of the common auction properties such as bidder anonymity, non-repudiation by the bidder, traceability, non-forgeable, bidder fairness, public verifiability, linkable during the auction, and non-linkable over multiple auctions. In addition, the proposed auction scheme will also ensure that the winning bid notification issued by the auctioneer will satisfy two goals. First, all registered members of the auction will be completely verifiable and convinced of any notification from the auctioneer. Second, this provability and verifiability will be limited to only registered members of the auction. This condition prevents any registered member from selling or profiting from the auction results.

The proposed auction schemes are divided into two main groups- open-price auctions and sealed-bid auctions - shown in Fig. 4. For the open-price auction case, a deniable English Auction (Ascending Price Auction) is proposed for each subsequent bid must be higher than the previous highest bid to be accepted by the auctioneer. For the sealed-bid auction case, a deniable first-price sealed-bid auction scheme is also proposed where all bids are privately tallied (one bid per member) and the highest bid is announced.

Finally, each of the research contributions presented in this thesis is summarized and future areas of research are identified. The thesis contributions include improving existing broadcast encryption systems to incorporate general hierarchal service sets. Next, various deniable key establishment protocols were proposed for both the SAIP and WAIP cases. Finally, a novel general auction scheme with auctioneer deniable settlement is proposed.

Figure 1:Thesis Overview

Figure 2:Master Key and Service Key Relationship

Figure 3:SAIP and WAIP

Figure 4:Algorithm Flow of Open-Price and Sealed-Bid Auctions

本論文は「The Design and Analysis of Secure Communication Systems Distributed Over Broadcast Channels(放送型通信を利用した安全な通信システムの設計と解析)」と題し、6章から構成されている。放送やネットワークを通して、情報サービスの配信やネットオークションが既に実用化されているが、今後ますますきめ細かいサービスや安全性が必要となる。本論文では、放送型通信を用いて、効率よくかつ安全に暗号化鍵を配信あるいは共有するためのプロトコルや、安全でかつ落札価格を部外者に信頼できる形で伝えることができないネットオークションを実現するプロトコルを提案し、その安全性を理論的に解析している。

第1章「Introduction」では,本論文で取り扱う放送型通信を用いた情報セキュリティシステムに対する研究の背景と目的を述べると共に、本論文の構成を示している。

第2章「Mathematical Foundations and Cryptographic Tools」では,暗号理論で用いられる代数の基本定理、本論文で仮定する計算困難問題(因数分解問題や離散対数問題)を示すと共に、本論文で必要となるハッシュ関数,公開鍵暗号,署名方式,ゼロ知識証明などを紹介している。

第3章「Broadcast Encryption」では、放送型通信を通して、ユーザで異なる多種類の情報を多くのユーザに配信するためのセッション暗号鍵配布方式を取り扱っている。 情報配信サービスは、多くの場合階層構造になっている。その階層構造を利用して、上位サービスのマスター鍵を配送すれば全ての下位サービスのセッション鍵を安全に作成・更新ができる暗号方式を本章で提案している。マスター鍵を一定期間ごとにリセットするが,途中でのユーザの加入や脱退を許さない方式に加えて、任意の時刻に脱退のみ,加入のみ,および加入と脱退を許す方式の構成法を与えている。安全性は離散対数問題の困難さに根拠を置いており、提案したシステムの安全性を理論的に解析している。

第4章「Deniable Key Establishment」では,匿名性を保持した鍵共有方式を提案している。ネットワークを通して、アンケート調査や公開討論を行なうときに、匿名性を保持しつつ、回答する人があるグループに属していることを確証したい場合がある。本章では、そのような要求を満たすことができる暗号鍵の共有手法を提案している。グループの選定者が任意の人でよい場合と、選定者がそのグループに含まれていなければならない場合を取り扱っている。安全性は公開鍵暗号の安全性に根拠を置いているが、一部でハッシュ関数や離散対数を利用することにより、計算量を減らした方式も提案している。また、提案したシステムの安全性を理論的に解析している。

第5章「General Auction Schemes with Deniable Settlement」では,放送型通信を用いたネットオークション方式を取り扱っている。公平で信頼性のおけるオークションを実現するためには、オークションの落札価格を、全参加者に信頼できる形で伝える必要がある。しかし、参加者が落札価格を部外者に信頼できる形で伝えることができると、オークションの手数料の支払いを逃れるために、その落札価格を参考にしたオークション外取引が増えてしまう問題がある。本章では、この問題を解決するために、オークションの正規の参加者には、各時刻の最大入札価格や落札価格を信頼できる形で伝えるが、オークション外の人にはそれらの情報が全く漏洩しないようにし、さらに、オークションの正規の参加者が入札価格や落札価格を部外者に伝えても、信頼できない情報になるというオークションシステムを実現している。なお、オークションへのユーザの登録時には、部分的に信頼できる登録マネージャーを仮定しているが、登録マネージャー以外には信頼できる第3者を必要としない特徴がある。また、通常のオークションで必要とされる「入札者の匿名性」「登録マネージャーと競売者の協力の下での、不正者の追跡可能性」「入札の公平性」などの安全性も満たされていることを理論的に解析している。さらに、上記のような公開入札(open-price auction)の代わりに、封印入札(sealed-bid auction)に提案方式を用いる場合のプロトコルも示されている。

第6章「Conclusions」では、本論文の成果をまとめると共に、今後の研究課題を示している。

なお,本論文の成果は、山本博資との共同研究であるが、論文提出者が主体となって新しい情報セキュリティシステムの提案および解析を行なったものであり、論文提出者の寄与が十分であると判断する。

したがって、博士(科学)の学位を授与できると認める。