\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{setspace}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in} \setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in} \setlength{\textheight}{8.5in}
\setstretch{1.3}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{fact}[theorem]{Fact}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{assumption}[theorem]{Assumption}

\newcommand{\qed}{\hfill \ensuremath{\Box}}

\newenvironment{proof}{
\vspace*{-\parskip}\noindent\textit{Proof.}}{$\qed$

\medskip
}

\newcommand{\handout}[5]{
   \renewcommand{\thepage}{#1-\arabic{page}}
   \noindent
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 5.78in { {\bf CS395T Advanced Cryptography} \hfill #2 }
       \vspace{4mm}
       \hbox to 5.78in { {\Large \hfill #5  \hfill} }
       \vspace{2mm}
       \hbox to 5.78in { {\it #3 \hfill #4} }
      }
   }
   \end{center}
   \vspace*{4mm}
}

\newcommand{\ho}[5]{\handout{#1}{#2}{Instructor:
#3}{Scribe: #4}{Lecture #1: #5}}
\newcommand{\al}{\alpha}
\newcommand{\Zp}{\mathbb{Z}_p}
\newcommand{\G}{\mathbb G}
\newcommand{\GT}{\mathbb{G}_T}
\newcommand{\A}{\mathcal A}
\newcommand{\B}{\mathcal B}
\newcommand{\C}{\mathcal C}

\begin{document}
\ho{13}{26 March, 2009}{Brent Waters} {Abhik K. Das} {Broadcast
Encryption (Contd.) and Traitor Tracing}

\section{Security of BGW ('05) Broadcast Encryption Scheme}
The security of BGW scheme with $n$ subscribers depends on the
hardness of the $n$-BDHE assumption which was described in the
previous scribe-note. We now give a proof of its security in form
of the theorem mentioned below.
\begin{theorem}
Let $\G$ be a bilinear group of prime order $p$. Then the BGW
scheme with $n$ subscribers is secure in `static' sense against
CPA if the $n$-BDHE assumption holds in $\G$.
\end{theorem}
\begin{proof}
We prove the contrapositive statement i.e. if the exists an attack
of non-negligible advantage, say $\epsilon$, on the BGW scheme
with $n$ subscribers, then it can be used to construct an attack
of non-negligible advantage on the $n$-BDHE assumption in $\G$.
Let $\A$ denote the $n$-BDHE assumption challenger, $\B$ denote
the the $n$-BDHE assumption attacker or BGW scheme challenger and
$\C$ denote the BGW scheme attacker. The following game is played
among $\A$, $\B$ and $\C$:
\begin{itemize}
\item $\A$ chooses a random $t\in\{0,1\}$ and passes
$g,h,g^a,\ldots,g^{a^n},g^{a^{n+2}},\ldots,g^{a^{2n}},T,\G,\GT$ to
$\B$, where $T=e(g,h)^{a^{n+1}}$ if $t=0$ and $T=$ some random
element in $\GT$ if $t=1$. $\B$ declares the set of subscribers
$S^*\subseteq\{1,2,\ldots,n\}$, it wishes to attack, to $\C$.

\item $\B$ uses group $\G$ and generator $g$ for constructing the
BGW scheme. $\alpha$ is set to $a^{n+1}$ indirectly by setting
$e(g,g)^{\alpha}=e(g^a,g^{a^n})$. $y_1,y_2,\ldots,y_n \in \Zp$ are
chosen randomly and $u_i$'s are set as $u_i=g^{y_i}$ if $i\in S^*$
and $u_i=g^{a^i}g^{y_i}$ if $i\notin S^*$.
$PP=(e(g^a,g^{a^n}),u_1,u_2,\ldots,u_n)$ is given to $\C$.

\item $\C$ queries about the secret keys of the subscribers not in
$S^*$ during the query phases. Then the secret key of
subscriber $i$ ($i\notin S^*$) is generated as follows:\\
$r_i$ is set to $-a^{n+1-i}$ indirectly by setting
$K_{i,2}=(g^{a^{n+1-i}})^{-1}$. This gives
$K_{i,1}=g^{a^{n+1}}u_i^{r_i}=[(g^{a^{n+1-i}})^{-1}]^{y_i}$ and
$u_j^{r_i}=(g^{a^{n+1-i+j}})^{-1}[(g^{a^{n+1-i}})^{-1}]^{y_i}$.
Since $j\neq i$, no information about $g^{a^{n+1}}$ is divulged
due to $u_j^{r_i}$'s. The query is answered by $\B$ returning
$K_i=(K_{i,1},K_{i,2},\{u_j^{r_i}\}_{j\neq i})$ to $\C$.

\item $\C$ selects a pair of distinct messages $(M_0,M_1)$ and
sends it to $\B$. $\B$ chooses a random $b\in\{0,1\}$ and encrypts
$M_b$ by setting $g^s=h$. The cipher-text
$C^*=(C_1^*,C_2^*,C_3^*)$, where
$C_1^*=M_bT,C_2^*=h,C_3^*=F(S^*)^s=\prod_{i\in S^*}h^{y_i}$, is
sent back to $\C$.

\item $\C$ guesses $b'\in\{0,1\}$ for $b$ using its attack
algorithm and sends it to $\B$. If $b=b'$, $\B$ sets $t'=0$ and
sends it to $\A$, else $t'=1$ is sent. The attack succeeds if
$t=t'$.
\end{itemize}
The probability of a successful attack is given by:
\begin{eqnarray*}
Pr(t=t')&=&Pr(t'=0|t=0)Pr(t=0)+Pr(t'=1|t=1)Pr(t=1)\\
&=&Pr(b=b')Pr(t=0)+\frac{1}{2}Pr(t=1)\\
&=&\frac{1}{2}\left(\frac{1}{2}+\epsilon\right)+\frac{1}{2}\cdot
\frac{1}{2}\\
&=&\frac{1}{2}+\frac{\epsilon}{2}
\end{eqnarray*}
We have an attack with non-negligible advantage $\epsilon/2$ on
the $n$-BDHE assumption in $\G$, which was to be shown. This
completes our proof.
\end{proof}

\section{Traitor Tracing}
In broadcast encryption, it is quite possible that a group of
subscribers is acts as a pirate and is involved in data piracy.
The pirate uses the secret keys, available to it, to build a
pirate decoder which extracts data from the broadcast signal and
distributes its copies illegally. In such a scenario, it becomes
necessary to have an algorithm capable of interacting with the
pirate decoder and getting back the identities of the subscribers
whose secret keys are being used in the pirate decoder. The guilty
subscribers can then be penalized. This is referred to as
\emph{traitor tracing}.

Traitor tracing is a hard problem in general, as the tracing
algorithm must do its job by treating the pirate decoder as a
black-box. The pirate is free to build the decoder the way it
wants -- the pirate could obfuscate the code, use tamper resistant
hardware, and try to randomize the secret keys. Hence, it is
safest to treat the pirate decoder as a black box and the tracing
algorithm cannot look into the inner-workings of the decoder. The
only thing the tracer knows is that the decoder can correctly
decrypt the messages from the broadcast signal with high
probability.

\subsection{Algorithms for Traitor Tracing}
A traitor tracing system consists of the following algorithms:
\begin{itemize}
\item \emph{Setup}($\lambda,n$): Takes as input the number of
subscribers $n$ and security parameter $\lambda$ to output the
broadcast key $PK$, tracing key $TK$, and secret keys
$K_1,K_2,\ldots,K_n$. \item \emph{Encrypt}($M,PK$): Takes as input
the message $M$ and $PK$ to output cipher-text $C$. \item
\emph{Decrypt}($i,K_i,C,PK$): Takes as input $K_i$ and $PK$ to
retrieve message $M$ from $C$. \item \emph{Trace}($TK,D$): Takes
as input $TK$ and interacts with a pirate decoder $D$ to output
the index $i\in\{1,2,\ldots,n\}$ of a key $K_i$ that was used to
create $D$.
\end{itemize}

\subsection{Security for Traitor Tracing}
The security and traceability of a traitor tracing system can be
defined by the following game between a challenger $\A$ and
attacker $\B$:
\begin{itemize}
\item $\B$ gives $\A$ a set $S\subseteq \{1,2,\ldots,n\}$ of
subscribers whose secret keys it needs to construct a pirate
decoder. $\A$ runs \emph{Setup}($\lambda,n$) returns back the
secret keys $\{K_i|i\in S\}$ along with the broadcast key $PK$ and
tracing key $TK$ to $\B$. \item $\B$ constructs the pirate decoder
$D$ using the secret keys $\{K_i|i\in S\}$ and gives $D$ to $\A$.
Then $\A$ runs the \emph{Trace}($TK,D$) and obtains the indices of
subscribers who are supposed to be pirates.
\end{itemize}
Attacker $\B$ is said to be successful if $Pr(D(C)=M)\approx 1$
($M$ is a message and $C$ is its encryption) and the indices
returned by \emph{Trace} do not belong to $S$.

\subsection{A Simple Traitor Tracing Scheme}
A simple and brute force traitor tracing scheme can be described
as follows:
\begin{itemize}
\item \emph{Setup}($\lambda,n$): $n$ public key-secret key pairs
$\{(PK_i,K_i)\}_{i=1}^{n}$ are generated. $K_1,K_2,\ldots,K_n$ are
made the secret keys of the subscribers,
$PK=(PK_1,PK_2,\ldots,PK_n)$ is made the broadcast key as well as
the tracing key. \item \emph{Encrypt}($M,PK$): The cipher-text $C$
is obtained by concatenating the cipher-texts obtained using the
different public keys i.e.
$C=(E_{PK_1}(M),E_{PK_2}(M),\ldots,E_{PK_n}(M))$. \item
\emph{Trace}($PK,D$): For $i=1,2,\ldots,n+1$, a cipher-text is
constructed from a message $M$ as
$C_i=(E_{PK_1}(\perp),\ldots,E_{PK_{i-1}}(\perp),E_{PK_i}(M),\ldots,E_{PK_n}(M))$,
where $\perp$ is any random sample from the message space. A
polynomial number of such $C_i$'s are generated for each $i$ and
they are given as input to the pirate decoder $D$. The decryptions
given by $D$ are then used to estimate $p_i=Pr[D(C_i)=M]$ for
$i=1,2,\ldots,n+1$. We have $p_1\approx 1$ and $p_{n+1}\approx 0$
since $D$ decodes correctly with high probability and all messages
are random in $C_{n+1}$. This gives
$$
1\approx
|p_{n+1}-p_1|=\left|\sum_{i=1}^{n}(p_{i+1}-p_i)\right|\leq
\sum_{i=1}^{n}|p_{i+1}-p_i|
$$
$|p_{i+1}-p_i|\approx 0$ if $K_i$ is not used by $D$ else it is
non-negligible if $K_i$ is used by $D$. In the worst-case
scenario, $D$ uses all the keys $K_1,K_2,\ldots,K_n$ and then each
$|p_{i+1}-p_i|$ is of the order of $\frac{1}{n}$. Hence, to
identify the pirates we observe the successive differences between
the $p_i$'s i.e. $|p_{i+1}-p_i|\,\,\forall i$. $K_i$ is one of the
pirates only if $|p_{i+1}-p_i|=O(\frac{1}{n})$.
\end{itemize}
The problem with this brute-force scheme is that the size of the
cipher-texts is large which consumes a lot of bandwidth for the
broadcast signal. A fully collusion resistant traitor tracing
system has been proposed in \cite{BSW06} with the advantage of
shorter cipher-text size and constant size secret keys.

\begin{thebibliography}{99}
\bibitem[BSW06]{BSW06}
D. Boneh, A. Sahai and B. Waters. Fully Collusion Resistant
Traitor Tracing With Short Ciphertexts and Private Keys.
\emph{EUROCRYPT '06}.
\end{thebibliography}

\end{document}