654 lines
78 KiB
TeX
654 lines
78 KiB
TeX
\documentclass{article}
|
|
\usepackage{amsthm}
|
|
\usepackage{bm}
|
|
\usepackage{amsmath}
|
|
\usepackage{graphicx}
|
|
\usepackage{amsfonts}
|
|
\usepackage{newpxtext,newpxmath}
|
|
\usepackage{scrextend}
|
|
\usepackage{seqsplit}
|
|
\usepackage[autostyle]{csquotes}
|
|
\usepackage{xspace}
|
|
\usepackage[margin=1.25in]{geometry}
|
|
\usepackage{wasysym}
|
|
\usepackage{pdfpages}
|
|
\usepackage[toc,page]{appendix}
|
|
\usepackage{relsize}
|
|
|
|
% Indent all description environments slightly
|
|
\usepackage{enumitem}
|
|
\setlist[description]{leftmargin=\parindent,labelindent=\parindent}
|
|
|
|
\newtheorem{definition}{Definition}
|
|
\newtheorem{theorem}{Theorem}
|
|
|
|
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}} % Create horizontal rule command with 1 argument of height
|
|
\newcommand{\ID}{\texttt{ID}\xspace}
|
|
\newcommand{\vsp}[1]{\vspace{#1} \\}
|
|
\newcommand{\hsp}[1]{\-\hspace{#1}}
|
|
\newcommand{\adv}[1]{$\mathcal{#1}$\xspace}
|
|
\newcommand{\G}{$\mathbb{G}$\xspace}
|
|
\newcommand{\Gp}[1]{$\mathbb{G}#1$\xspace}
|
|
\newcommand{\Z}{\mathbb{Z}}
|
|
\newcommand{\Gm}{\mathbb{G}}
|
|
\newcommand{\Gmp}[1]{\mathbb{G}#1}
|
|
\newcommand{\la}{\leftarrow}
|
|
\newcommand{\ra}{\rightarrow}
|
|
\newcommand{\U}{\mathcal{U}}
|
|
\newcommand{\CH}{$\mathcal{C}\mathcal{H}$\xspace}
|
|
\newcommand{\hdr}{\normalfont\text{Hdr}\xspace}
|
|
\newcommand{\set}[1]{\{#1\}}
|
|
\newcommand{\AHBE}{\texttt{AHBE}\xspace}
|
|
\newcommand{\overbar}[1]{\mkern 1.5mu\overline{\mkern-1.5mu#1\mkern-1.5mu}\mkern 1.5mu}
|
|
\newcommand{\KHBE}{\texttt{KHBE}\xspace}
|
|
\newcommand{\mlarge}[1]{\mathlarger{\mathlarger{#1}}}
|
|
|
|
% Use dash instead of bullets for itemize
|
|
\renewcommand\labelitemi{--}
|
|
|
|
\author{\large{Alexander Munch-Hansen} \\ 201505956 \\[1cm]{\small Supervised by:} \\Claudio Orlandi \\ Sophia Yakoubov}
|
|
|
|
\title{
|
|
\normalfont \normalsize
|
|
\textsc{Aarhus University} \\ [20pt]
|
|
\horrule{0.5pt} \\[0.4cm] % Thin top horizontal rule
|
|
\huge Beyond Public Key Cryptography \\ % The assignment main title
|
|
\large A Study of Various Extensions of Public Key Cryptography, With Focus on Broadcast Encryption Schemes \\ % The assignment sub title
|
|
\horrule{2pt} \\[0.5cm] % Thick bottom horizontal rule
|
|
}
|
|
|
|
|
|
\date{\today}
|
|
\begin{document}
|
|
\maketitle
|
|
\newpage
|
|
\tableofcontents
|
|
\newpage
|
|
\section{Introduction}
|
|
By definition, \emph{Encryption} is the process of converting information into a \emph{ciphertext} with the purpose of preventing unauthorised access \cite{oxford}. Traditionally, the way this was accomplished was via some a priori established secret key $k$, which could then be used both for \emph{encryption} to turn some \emph{plaintext} into the ciphertext, but also for \emph{decryption}, to turn the ciphertext back into the plaintext. This concept was however eventually challenged by the new idea of \emph{Public Key Encryption}, \texttt{PKE}, which allows two parties to communicate with each other in a secure and private fashion, without having already shared the aforementioned secret key. This allowed each party to have a \emph{Public Key} and a \emph{Secret Key}, which could then be used to encrypt and decrypt, respectively. This works well and is used in many applications, such as \emph{SSH} and \emph{SSL}. It does however have one caveat. \emph{Public Key Encryption} is notoriusly slow, compared to the \emph{Symmetric}-scheme with only a single key. Thus, we introduce the concept of \emph{Key Encapsulation Mechanisms}, or \texttt{KEM}, in which a decryption key is now what is sent, rather than a message, as opposed to \emph{Data Encapsulation Mechnanisms}, \texttt{DEM}. This naturally solves one of the underlying issues of \texttt{PKE}, as we can now encrypt a symmetric key via a \texttt{KEM} and then change our way of communication after the first message to that of \texttt{DEM}.
|
|
|
|
Now, imagine a scenario where a user has an entire network of people in which he only wishes to send to a subset of these at a time. In the world of \texttt{PKE}, this user will have to fetch each users public key and encrypt the same symmetric key for each user, resulting in a ciphertext for the same key for each user. This is highly inefficient, and becomes even worse if the \emph{authorised set} of receivers change, at which point a new symmetric key must be created and sent to each user. To this end, \emph{Broadcast Encryption}, \texttt{BE}, can be adopted as a solution. In such a scheme, a user will pick his set of recievers $S$, fetch their public keys, but only encrypt the key once and broadcast this. Thus, the resulting ciphertext of the key does not depend in any way on the number of users, and there is only a single message which can easily be broadcasted to all users of the system, but only those users within the set $S$ can decrypt it.
|
|
|
|
In this paper we first cover the concept of \emph{Identity Based Encryption}, \texttt{IBE}, as an introduction to some of the mathmatical concepts used within the paper, such as that of \emph{bilinear maps} and the mathmatical assumption that is the \emph{Bilinear Diffie Hellman}-problem. These two concepts can be extended and applied to many branches of encryption, such as \texttt{BE} or \emph{Dynamic Threshold Public Key Encryption}, \texttt{DTPKE}, both of which will also be introduced in this paper. Thus, we wish to introduce three different types of encryption schemes, \texttt{IBE, BE} and \texttt{DTPKE}, give a notion of what security is defined to be for these as well as an actual construction and extension of these.
|
|
|
|
|
|
\section{Syntax and Preliminaries}
|
|
|
|
\subsection{Bilinear Maps}
|
|
Let $p$ be a large prime number. Let $\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T$ be three groups of order $p$. Let $g_1$ be a generator of $\mathbb{G}_1$ and let $g_2$ be a generator of $\mathbb{G}_2$. $e : \mathbb{G}_1 \times \mathbb{G}_2 \ra \mathbb{G}_T$ is then a bilinear map satisfying the following properties \cite{BMDef}:
|
|
\begin{itemize}
|
|
\item \emph{Bilinearity}: For all $u \in \mathbb{G}_1$, $v \in \mathbb{G}_2$ and $a,b \in \mathbb{Z}$; $e(u^a, v^b) = e(u,v)^{ab}$
|
|
\item \emph{Non-Degeneracy}: $e(g_1,g_2) \neq $ The identity of $\mathbb{G}_T$
|
|
\item \emph{Computability}: For all $u \in \mathbb{G}_1$, $v \in \mathbb{G}_2$, $e(u,v)$ should be efficiently computable.
|
|
\end{itemize}
|
|
A bilinear map satisfying all the above three properties is said to be \emph{admissible}.
|
|
|
|
Intuitively, a bilinear map is simply a linear map, or function, taking two arguments, such that if either is lifted to an exponent within the transformation, the transformation can be applied first and the result lifted to the same exponent instead.
|
|
|
|
\subsection{Mathmatical Assumptions}
|
|
All of the following mathmatical assumptions are derived from the \emph{Diffie-Hellman} assumption. The reader is assumed to be familiar with this. We note that the \emph{Decisional Diffie-Hellman} problem is easy within the setting of bilinear maps, as, given some generator $g$ and $g^a$, $g^b$ and $g^c$ where the question is if $c = ab$, it is straightforward to check if $e(g,g^c) = e(g^a,g^b)$, which holds for the case where $c = ab$, as $e(g^a,g^b) = e(g,g)^{ab} = e(g,g)^c$, if and only if $c = ab$. As such, new assumptions which are difficult within this setting, are required.
|
|
|
|
\subsubsection{The BDH Problem}
|
|
\label{sec:BDHProb}
|
|
Let $\Gm$ and $\Gm_T$ be two groups of prime order $p$. Let $e : \Gm \times \Gm \ra \Gm_T$ be an admissible bilinear map and let $g$ be a generator of $\Gm$. The BDH problem is then in $(\Gm, \Gm_T, e)$ as follows: Given $(g, g^a, g^b, g^c)$ for some $a,b,c \in \mathbb{Z}^*_p$ compute $Z = e(g,g)^{abc}$.
|
|
|
|
\subsubsection{The BDHE Problem}
|
|
\label{sec:BDHE}
|
|
This is defined for a specific $m$ which could for instance be taken as a parameter. Let \G and \Gp{_T} be groups of order $p$ with a bilinear map $e: \Gm \times \Gm \rightarrow \Gmp{_T}$ and let $g \in G$ be a generator. Set $a,s \in_R \Z^*_p$ and $b \in_R \{0,1\}$. If $b=0$, then set $Z = e(g,g)^{a^{m+1} \cdot s}$; $Z \in_R \Gm_T$ otherwise. The problem is then, given $g^s, Z, \{g^{a^i}: i \in [0,m] \cup [m+2, 2m]\}$, what is the value of $b$?
|
|
|
|
\subsubsection{The DBDH Problem}
|
|
\label{sec:DBDH}
|
|
Note that this is simply the decisional version of \ref{sec:BDHProb}, but we will write it out for clarity.
|
|
|
|
Let $\Gm$ and $\Gm_T$ be two groups of prime order $p$. Let $e : \Gm \times \Gm \ra \Gm_T$ be an admissible bilinear map and let $g$ be a generator of $\Gm$. The BDH problem is then in $(\Gm, \Gm_T, e)$ as follows: Given $(g, g^a, g^b, g^c)$ for some $a,b,c \in \mathbb{Z}^*_p$, let $Z = e(g,g)^{d}$. If $b=1$ then $d = abc$, otherwise $d \in_R \mathbb{Z}^*_p$. The problem is then to decide the bit $b$ when you are given $(g,g^a,g^b,g^c, Z)$.
|
|
|
|
\subsubsection{THE MSE-DDH Problem}
|
|
\label{sec:MSE-DDH}
|
|
As defined in \cite{DTPKE}, whose scheme relies on the intractability of the $(\ell,m,t)$-\texttt{MSE-DDH} decisional problem.
|
|
|
|
Let $(\Gm_1, \Gm_2, \Gm_T, e)$ define three groups $\Gm_1,\Gm_2,\Gm_T$ all of order some prime $p$ and a bilinear map $e : \Gm_1 \times \Gm_2 \ra \Gm_T$. Let $\ell, m$ and $t$ be three integers. Let $g$ be a generator of $\Gm_1$ and let $h$ be a generator of $\Gm_2$. Then, given two random coprime polynomials, note that two polynomials are coprime if and only if they share no roots, of respective orders $\ell$ and $m$, with pairwise distinct roots $x_1, \dots x_\ell$ and $y_1, \dots, y_m$ respectively, as well as multiple sequences of exponentiations:
|
|
\begin{align*}
|
|
& x_1, \dots, x_\ell, \qquad \qquad \qquad y_1, \dots, y_m \\
|
|
& g, g^{\gamma}, \dots, g^{\gamma^{\ell + t - 2}}, \qquad \quad g^{k\cdot \gamma \cdot f(\gamma)} \\
|
|
& g^{\alpha}, g^{\alpha \cdot \gamma}, \dots, g^{\alpha \cdot \gamma^{\ell + t}}, \\
|
|
& h, h^{\gamma}, \dots, h^{\gamma^{m-2}}, \\
|
|
& h^{\alpha}, h^{\alpha \cdot \gamma}, \dots, h^{\alpha \cdot \gamma^{2m - 1}}, \qquad h^{k \cdot g(\gamma)},
|
|
\end{align*}
|
|
and finally a $Z \in \Gm_T$. The deciding part is then to decide whether $Z$ is equal to $e(g,h)^{k \cdot f(\gamma)}$ or merely some random element of $\Gm_T$.
|
|
|
|
We want to note that the paper does not define either $\alpha$ or $\gamma$, which essentially means this problem is not well defined. We assume however, that both $\alpha$ and $\gamma$ have to come from $\mathbb{Z}^*_p$, whenever this problem is referenced.
|
|
|
|
\subsubsection{Notation}
|
|
We would like to note that whenever something is prefixed with a capital B, it is in the context of \emph{Broadcast Encryption}. Furthermore we would like to note that for all setup algorithms mentioned, the security parameter will be implicit, but naturally all schemes relies on one in some shape or form, to either denote a bit length, graph size or whatever makes sense within the context.
|
|
|
|
|
|
|
|
\section{Identity Based Encryption}
|
|
We will cover an identity based encryption scheme which illustrates a basic usage of bilinear maps as well as one way to extend the \emph{Diffie-Hellman Assumption} known from Public Key Encryption. This scheme is not secure against an adaptive chosen ciphertext attack (\texttt{IND-ID-CCA}). The scheme can however be extended to cover this, but this is out of the scope of this paper. We note that although this scheme is not awfully relevant for the rest of the paper, it still is something we covered throughout the semester and it offers a delicate and simple introduction to some of the mathematical concepts and encryption schemes which will be used throughout this paper, specifically that of bilinear maps and public key cryptography.
|
|
|
|
|
|
\subsection{Modelling Identity Based Encryption}
|
|
\label{sec:IBEStruct}
|
|
\textbf{Identity-Based Encryption.} \quad An Identity-Based encryption scheme is specified by four different algorithms, all containing some sort of randomness: \texttt{Setup, Extract, Encrypt, Decrypt}:
|
|
\begin{description}
|
|
\item[Setup$()$] Uses some security parameter $k$ and returns the system parameters, \textbf{params}, and a master-key, $MK$. These system parameters include a description of some finite message space $\mathcal{M}$ as well as a description of some finite ciphertext space $\mathcal{C}$. These parameters are known publicly, where as the master-key is known only to the trusted authority, the so called Private Key Generator (\texttt{PKG}).
|
|
\item[Extract$(\text{params}, MK, \mathtt{ID})$] Takes the system parameters, the master-key and an arbitrary \texttt{ID} $\in \{0,1\}^*$ and returns a private key $d$. \texttt{ID} is essentially any arbitrary string which will be used a public key and $d$ is the corresponding decryption key, which can be used by the owner of the \texttt{ID}. Thus, the \textbf{extract} algorithm extracts a private key from the given public key.
|
|
\item[Encrypt$(\text{params}, \mathtt{ID}, M)$] Takes the system parameters, some \texttt{ID}, and an $M \in \mathcal{M}$. Returns some ciphertext $C \in \mathcal{C}$.
|
|
\item[Decrypt$(\text{params}, C, d)$] Takes the system parameters, some private key $d$ and $C \in \mathcal{C}$. Returns the corresponding plaintext $M \in \mathcal{M}$.
|
|
\item[Correctness] Naturally, these algorithms must satisfy that:
|
|
$$ \forall M \in M\ :\ \text{Decrypt}(\mathbf{params}, C, d) = M\quad \text{where}\quad C = \text{Encrypt}(\mathbf{params}, ID, M)$$ I.e. for all messages $M \in \mathcal{M}$, if this is encrypted for some id \ID, then it decrypts to the same message $M$, if the correct decryption key $d$ for the \ID is used.
|
|
\end{description}
|
|
|
|
|
|
\subsection{Security Definition}
|
|
\textbf{Chosen Ciphertext Security.} \quad We have chosen to focus on Chosen Ciphertext Security (\texttt{IND-CPA}), as this is the standard acceptable notion of security for a public key encryption scheme \cite{security_notion}. The standard definition however, is not strong enough for \texttt{IBE}-schemes, as we must also require that the adversary might already know of several \texttt{ID}s and decryption keys, given by the \texttt{PKG} and these should not aid the adversary in breaking the security. We define an \emph{extraction query} to be a query which yields the decryption key for a given \ID. Furthermore, the adversary is given the choice of which \ID to be challenged on, rather than it being a random public key. \cite{WeilIBE}
|
|
An Identity-Based Encryption scheme is semantically secure against an adaptive chosen ciphertext attack (\texttt{IND-ID-CPA}) if no polynomially bounded adversary $\mathcal{A}$ has non-negligible advantage against the Challenger in the following game \adv{E}:
|
|
\begin{description}
|
|
\item[Setup] The challenger is given a security parameter $k$ and he runs the \emph{Setup} algorithm explained above. This returns the public parameters \textbf{params} and the master-key $MK$ to the Challenger, who then forwards the \textbf{params} to the adversary.
|
|
\item[Phase 1] The adversary is allowed to issue queries $q_1, \dots, q_l$ where query $q_i$ is one of two queries;
|
|
\begin{itemize}
|
|
\item An extraction query run on $\ID_i$. The challenger responds by running the \emph{Extract} algorithm on the given $\ID_i$, returning the decryption key $d_i$ corresponding to the \ID. $d_i$ is sent to the adversary.
|
|
\item A decryption query run on $\ID_i$ and some ciphertext $C_i$. First the challenger runs the \emph{Extract} algorithm to get the decryption key $d_i$ corresponding to the given $\ID_i$. The Challenger then runs the \emph{Decrypt} algorithm on $d_i$ and $C_i$, resulting in a plaintext. This plaintext is returned to the adversary.
|
|
\end{itemize}
|
|
\hsp{6mm} These queries may be run \emph{adaptively}, hence the name of the security definition, thus, each query $q_i$ may depend on the previous queries $q_1,\dots,q_{i-1}$, if the adversary so desires.
|
|
\item[Challenge] Once the adversary deems that Phase 1 is over, he outputs two plaintexts of equal length; $M_0, M_1 \in \mathcal{M}$, as well as an \ID on which he desires to be challenged. The single constraint, is that the adversary is not allowed to have queried this \ID before in Phase 1. The Challenger then picks a bit $b \in_R \{0,1\}$ and sets $C = Encrypt(\mathbf{params}, \ID, M_b)$. $C$ is then send to the adversary.
|
|
\item[Phase 2] The adversary is allowed to issue additional $n-l$ queries; $q_{l+1},\dots,q_n$, where query $q_i$ is either of:
|
|
\begin{itemize}
|
|
\item An extraction query run on $\ID_i$. The same query, except $\ID_i \neq \ID$, where \ID is the \ID of the challenge.
|
|
\item A decryption query run on $\ID_i$ and some ciphertext $C_i$. The same query, except $\ID_i \neq \ID$ and $C_i \neq C$, where $C$ is the ciphertext of the challenge.
|
|
\end{itemize}
|
|
These queries may be run adaptively, as in Phase 1.
|
|
\item[Guess] The adversary outputs a guess bit $b' \in \{0,1\}$ and he will win the game if $b' = b$.
|
|
|
|
An adversary \adv{A} as defined above, is refered to as an \texttt{IND-ID-CPA} adversary. The advantage of \adv{A} in defeating the Challenger in the scheme \adv{E}, is defined as a function of the security parameter $k$, $Adv_{\mathcal{E}, \mathcal{A}} = |Pr(b=b') - \frac{1}{2}|$.
|
|
\end{description}
|
|
|
|
This definition closely resembles the standard definition of \texttt{IND-CPA} but extended with the addition of extraction queries and that the challenger is now challenged on an \ID picked by the adversary. The addition of the extraction queries is supported by \cite{ExtractionDef}, when the scheme is to support multiple users, which is likely the case for any IBE scheme. Furthermore, the weaker notion of security known as \emph{Semantic Security} (\texttt{IND-ID-CPA}) can be defined based on \texttt{IND-ID-CCA}, except now the adversary is not allowed to issue any decryption queries, i.e. he is only allowed extraction queries.
|
|
|
|
\subsection{An Instantiation of \texttt{IBE}}
|
|
\label{sec:IBEConst}
|
|
The scheme we will focus on is that of Boneh and Franklin as described in \cite{WeilIBE}. The structure will be as defined in Section \ref{sec:IBEStruct}. We let $\lambda$ be the given security parameter given implicitly to the setup algorithm. We let $\mathcal{G}$ be a BDH parameter generator.
|
|
\begin{description}
|
|
\item[Setup$()$] Given $\lambda$;
|
|
\begin{enumerate}
|
|
\item Run $\mathcal{G}$ on the security parameter $\lambda$ in order to generate a prime $p$ which defines the order of two groups $\Gm$ and $\Gm_T$ as well as an \emph{admissible} bilinear map $e : \Gm \times \Gm \ra \Gm_T$. Pick a random generator $g \in_R \Gm$.
|
|
\item Pick a random $s \in_R \mathbb{Z}^*_p$ and set the public key PK as such, $PK = g^s$.
|
|
\item Choose two hash functions: $H_1 : \{0,1\}^* \ra G^*$ and $H_2 : G_T \ra \{0,1\}^n$ for some $n$. Note that in the security analysis of this scheme, $H_1$ and $H_2$ will be viewed as random oracles. \\
|
|
The message space will be $\mathcal{M} = \{0,1\}^n$ and the ciphertext space is $\mathcal{C} = \Gm^{*} \times \{0,1\}^n$. Finally, the system parameters \textbf{params} are $(p, \Gm, \Gm_T, e, n, g, PK, H_1, H_2)$. The \emph{master key} (Or the systems private key), is then $s$. % TODO: Is this not the same s from the generation of the pk?
|
|
\end{enumerate}
|
|
\item[Extract$(\mathtt{ID}, \mathbf{params}, s)$] For a given string \ID $\in \{0,1\}^*$ the algorithm does two things; Compute $Q_{\mathtt{ID}} = H_1(ID) \in \Gm^*$ and it sets the private key $d_{\mathtt{ID}}$ to be $d_{\mathtt{ID}} = Q_{\mathtt{ID}}^s$, for the master key $s$.
|
|
\item[Encrypt$(\mathtt{ID}, \mathbf{params}, m)$] To encrypt some $m \in \mathcal{M}$ under the public key \ID, the user does the following: Compute $Q_{\mathtt{ID}} = H_1(ID) \in \Gm^*$, choose a random $r \in_R \mathbb{Z}^*_p$ and set the final ciphertext to be:
|
|
$$C = (g^r, m \oplus H_2(g_{\mathtt{ID}}^r)\quad \text{ where }\quad g_{\mathtt{ID}} = e(Q_{\mathtt{ID}}, PK) \in \Gm^*_T$$
|
|
\item[Decrypt$(\mathtt{ID}, \mathbf{params}, C, d_{\mathtt{ID}})$] Parse $C = (u,v)$ as a ciphertext decrypted under the public key \texttt{ID}. Then, to decrypt $C$ using the private key $d_{\mathtt{ID}} \in \Gm^*$, compute:
|
|
$$v \oplus H_2(e(d_{\mathtt{ID}}, u)) = m$$
|
|
|
|
Correctness of the above scheme is obvious from two facts;
|
|
\begin{enumerate}
|
|
\item During encryption $m$ is bitwise XORed with the hash of: $g^r_{\mathtt{ID}}$
|
|
\item During decryption $v$ is bitwise XORed with the hash of: $e(d_{\mathtt{ID}}, u)$
|
|
\end{enumerate}
|
|
Where these masks which are used during encryption and decryption are the same as;
|
|
$$e(d_{\mathtt{ID}}, u) = e(Q_{\mathtt{ID}}^s, g^r) = e(Q_{\mathtt{ID}}, g)^{sr} = e(Q_{\mathtt{ID}}, PK)^r = g^r_{\mathtt{ID}}$$
|
|
|
|
\end{description}
|
|
|
|
|
|
\subsection{Security of the Instantiation}
|
|
The scheme can be shown to be semantically secure (\texttt{IND-ID-CPA}), assuming that the BDH problem is hard in the groups generated by $\mathcal{G}$. It is proven by reducing an adversary who can break the \texttt{IBE} construction from Section \ref{sec:IBEConst}, to breaking an instantiation of the mathmatical problem defined in Section \ref{sec:BDHProb}. The actual proof is quite long and is left within the Appendix \ref{app:IBE-Sec} in its entirety.
|
|
|
|
\section{Broadcast Encryption}
|
|
\label{sec:BE}
|
|
Broadcast Encryption systems \cite{BEDef} in a nutshell, allows one sender to send something to a subset $S \subseteq [1,n]$ of users with a single message. Traditionally, the user would have to encrypt this message once per user in a horribly inefficient manner using regular \texttt{PKE}. This is fixed, by defining the encryption key in such a way to allow for any user within the receiver set $S$ to decrypt the message, while not allowing anyone outside of $S$ to do so. It is preferable for this kind of scheme to be \emph{public key based}, rather than symmetric, as this allows any user to encrypt. It should allow \emph{stateless receivers} such that users will not need to keep any state such as updating a private key, and the system should be \emph{fully collusion resistant}, i.e. not allow decryption even if everybody outside of the set $S$ cooperated.
|
|
|
|
|
|
\subsection{Modelling Broadcast Encryption}
|
|
Broadcast Encryption systems can be defined as a \emph{Key Encapsulation Mechanism}, \texttt{KEM}, where what is actually encrypted is a symmetric key, which can then be used for encryption and decryption at a later stage.
|
|
|
|
% TODO: BSetup takes n and ell, where ell defines the maximum size of the set. Ergo is the security parameter lambda implicit. Change this at later stages!
|
|
\begin{description}
|
|
\item[BSetup$(n, \ell)$] Here, $n$ defines the number of receivers and $\ell$ is the maximum size of the receiver set, $n \leq \ell$. Outputs a public/secret key pair, $(PK, SK)$ of the \texttt{BE} scheme.
|
|
\item[BKeyGen$(i, SK)$] $i$ defines a specific index for a user, $i \in [1,n]$, as well as the secret key $SK$. Outputs a decryption key $d_i$ specific for this user.
|
|
\item[BEnc$(S, PK)$] Takes as input some subset $S \subseteq [1,n]$ where $S$ will henceforth be known as the receiver or authorised set, as well as the public key of the BE scheme. Given that $|S| \leq \ell$, outputs a pair $(\hdr, K)$, where \hdr is called the \emph{header} and $K \in \mathcal{K}$ is the message encryption key. \hdr can be seen as the ciphertext for the key $K$, which in this case is a symmetrical key which can be used after having been extracted from the \hdr.
|
|
\item[BDec$(S, i, d_i, \hdr, PK)$] Takes the receiver set $S$, an index $i \in [1,n]$, a corresponding decryption key, a \hdr and the public key PK. Given $|S| \leq \ell$ and $i \in S$, this extracts the key $K \in \mathcal{K}$ from \hdr.
|
|
\item[Correctness] For all $S \subseteq [1,n]$ and all $i \in S$, if $(PK, SK) \xleftarrow{R} \mathbf{BSetup}(n, \ell)$, $d_i \xleftarrow{R} \mathbf{BKeyGen}(i, SK)$ and $(\hdr, K) \xleftarrow{R} \mathbf{BEnc}(S, PK)$, then $\mathbf{BDec}(S, i, d_i, \hdr, PK) = K$, i.e. if a key $K \in \mathcal{K}$ is encrypted for a receiver set, then a user from within this receiver set can also extract the same $K$ from the \hdr.
|
|
|
|
Ordinary \texttt{BE}-schemes require a trusted authority, like the \texttt{PKG} defined for \texttt{IBE}-schemes. This trusted authority will run the \textbf{BSetup} to get the $PK$ and $SK$ of the system and will then be used to generate the decryption keys for the users afterwards via the \textbf{BKeyGen} algorithm, when a user requests so.
|
|
\end{description}
|
|
|
|
\subsection{Security Defintions}
|
|
\label{sec:BESec}
|
|
We define three levels of security, \emph{Static, Semi-Static} and \emph{Adaptive}. For the sake of simplicity, we will explain Semi-Static and then emphasise the differences. Note that Semi-Static security is stronger than Static security, but weaker than Adaptive. The definition of Semi-Static is due to Gentry and Waters \cite{BESecDef, GentryWaters}.
|
|
|
|
\begin{description}
|
|
\item[Initialisation] The adversary \adv{A} first commits to a \emph{potential} set of receivers which he wishes to attack, $\tilde{S}$, and outputs this.
|
|
\item[Setup] The challenger \CH runs the $\mathbf{BSetup}(n, \ell)$ algorithm of the BE scheme, obtaining a public key PK. \CH gives this PK to \adv{A}.
|
|
\item[Key Extraction Phase] The adversary \adv{A} is allowed to issue private key queries for indices $i \in [1,n] \setminus \tilde{S}$, i.e. he is allowed to ask for the private keys of any user not in the set of potential receivers.
|
|
\item[Challenge] Once the adversary \adv{A} has extracted all desired keys, he specifies an attack set $S^* \subseteq \tilde{S}$, on which he wants to be challenged. The challenger \CH then sets $(\hdr^*, k_0) \leftarrow BEnc(S^*, PK)$ and $k_1 \in_R \mathcal{K}$. Then $b \in_R \{0,1\}$ and \CH sends $(\hdr^*, k_b)$ to \adv{A}.
|
|
\item[Guess] Adversary \adv{A} outputs a guess $b' \in \{0,1\}$ and he wins if $b' = b$.
|
|
|
|
The advantage of \adv{A} is then defined as: $$Adv_{SS,BE,n,\ell}(\lambda) = |Pr(b'=b) - \frac{1}{2}|$$
|
|
Static security is the least strongest type and it requires the adversary to commit to the set of receivers of which he wants to be challenged on, in the initialisation phase, rather than the potential set the Semi-Static adversary has to commit to. Adaptive security is arguably the most desired and correct type, as it enforces nothing in regards to the attack set $S^*$. The adversary is allowed to see the public key PK and ask for several private keys, before choosing which set he wishes to be challenged on. We note here, that due to Gentry and Waters \cite{GentryWaters}, we can transform a Semi-Statically secure BE scheme to an Adaptively secure BE scheme via a general transformation.
|
|
\end{description}
|
|
|
|
|
|
|
|
\subsection{Their construction}
|
|
\label{sec:GentryWatersConst}
|
|
Let $GroupGen(\lambda,n)$ be an algorithm which generates a group \G and \Gp{_T} of prime order $p = \text{poly}(\lambda, n) > n$ with a bilinear map $e : \mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}_T$, based on a security parameter $\lambda$.
|
|
|
|
\begin{description}
|
|
\item[BSetup$(n, \ell)$] Run $(\mathbb{G}, \mathbb{G}_T, e) \xleftarrow{R} GroupGen(\lambda, n)$. Set $\alpha \in_R \Z_p$ and $g,h_1,\dots,h_n \in_R \mathbb{G}^{n+1}$. Finally, set $PK = ((\mathbb{G}, \mathbb{G}_T, e), g, e(g,g)^\alpha, h_1, \dots, h_n)$. The secret key is $SK = g^\alpha$. The result is the pair $(PK, SK)$.
|
|
\item[BKeyGen$(i, SK)$] Set $r_i \in_R \Z_p$ and output; $$d_i \leftarrow (d_{i,0},\dots,d_{i,n}) \quad \text{ where } \quad d_{i,0} = g^{-r_i}, \quad d_{i,i} = g^\alpha h^{r_i}_i, \quad d_{i,j \text{ for } i\neq j} h^{r_i}_j$$
|
|
\item[BEncrypt$(S, PK)$] Set $t \in_R \Z_p$ and $$Hdr = (C_1,C_2), \quad \text{ where }\quad C_1 = g^t, \quad C_2 = (\prod_{i \in S}h_i)^t $$ Finally, set $K = e(g,g)^{t\cdot \alpha}$. Output $(\hdr, K)$.
|
|
\item[BDecrypt$(S,i,d_i,\hdr, PK)$] Check if $i \in S$, if so; let $d_i = (d_{i,0},\dots,d_{i,n})$, Hdr$=(C_1,C_2)$, output $$K =e(d_{i,i} \cdot \prod_{j \in S \setminus \{i\}} d_{i,j}, C_1) \cdot e(d_{i,0}, C_2)$$
|
|
\item[Correctness] Correctness is given by;
|
|
\begin{align*}
|
|
K &= e(d_{i,i} \cdot \prod_{j \in S \setminus \{i\}} d_{i,j}, C_1) \cdot e(d_{i,0}, C_2) \\
|
|
&= e(g^{\alpha}h^{r_i}_i \cdot (\prod_{j \in S \setminus \{i\}} h_j)^{r_i}, g^t) \cdot e(g^{-r_i}, (\prod_{j \in S}h_j)^t) \\
|
|
&= e(g^{\alpha} \cdot (\prod_{j \in S} h_j)^{r_i}, g^t) \cdot e(g^{-r_i}, (\prod_{j \in S}h_j)^t) \\
|
|
&= e(g,g)^{t \cdot \alpha}
|
|
\end{align*}
|
|
\end{description}
|
|
|
|
|
|
\subsection{Proof of Security}
|
|
The proof is a reduction from their construction to the \emph{BDHE}-problem of Section \ref{sec:BDHE}. The scheme is proven secure in the Semi-Static model. We note that the proof in the original paper does not hold, likely due to a typo, but we'll emphasise the fix.
|
|
|
|
We wish to build an algorithm \adv{B}, which will use an adversary \adv{A} who we assume to have a non-negligible advantage in breaking the construction described in \ref{sec:GentryWatersConst}, to break the \emph{BDHE} problem. By breaking the construction in Section \ref{sec:GentryWatersConst}, we mean that \adv{A} will be able to somehow distinguish what is encrypted within an header \hdr. \\ \\
|
|
\adv{B} receives a problem instance which contains $g^s, Z, \{g^{a^i}: i \in [0,m] \cup [m+2, 2m]\}$, where $Z$ is either $e(g,g)^{a^{n+1}\cdot s}$ or random in $\Gm_T$.
|
|
\begin{description}
|
|
\item[Init] \adv{A} commits to a set $\tilde{S} \subseteq [1,n]$.
|
|
\item[Setup] \adv{B} generates $y_0,\dots,y_n \in_R \Z_p$. \adv{B} sets:
|
|
$$
|
|
h_i =
|
|
\begin{cases}
|
|
g^{y_i} & \text{ for } i \in \tilde{S} \\
|
|
g^{y_i + a^{i}} & \text{ for } i \in [1,n] \setminus \tilde{S}
|
|
\end{cases}
|
|
$$
|
|
\adv{B} then sets $\alpha = y_0 \cdot a^{n+1}$. $PK$ is then defined as the scheme dictates where the only oddity is $e(g,g)^\alpha$, which can be computed as $e(g^a,g^{a^{n}})^{y_0}$ due to the definition of $\alpha$. $PK$ is sent to \adv{A}.
|
|
|
|
\item[Key Extraction Phase] \adv{A} is allowed to query private keys for indices $i \in [1,n] \setminus \tilde{S}$. Intuitively, you should not be allowed to query the indices of which you wish to be challenged. To answer a query, \adv{B} will generate a $z_i \in_R \Z_p$ and set $r_i = z_i - y_0 \cdot a^{n+1-i}$. \adv{B} then outputs
|
|
$$ d_i = (d_{i,0},\dots,d_{i,n})\quad \text{ where } \quad d_{i,0} = g^{-r_i},\quad d_{i,i} = g^\alpha h^{r_i}_i, \quad d_{i,j \text{ where } i\neq j}h^{r_i}_j $$
|
|
\item[Challenge] \adv{A} will then choose a subset $S^* \subseteq \tilde{S}$ to which \adv{B} sets:
|
|
$$\hdr = (C_1, C_2) \quad \text{ where } C_1 = g^s, \quad C_2 = (\prod_{j \in S^*}h_j)^s$$
|
|
Note that $g^s$ comes from the original challenge and due to the construction of the $h_j$ values, $C_2$ is computable, as \adv{B} knows the discrete log of each of them, specifically $h_j = g^{y_j}$, as long as $j \in \tilde{S}$.
|
|
\adv{B} sets $K = Z^{y_0}$ (The original; $K = Z$) and sends $(\hdr,K)$ to \adv{A}.
|
|
\item[Guess] \adv{A} will output a guess $b'$. \adv{B} forwards this bit to the Challenger.
|
|
\item[Correctness] This simulation intuitively works, as if \adv{A} returns $b' = 0$ then the pair $(\hdr, K)$ is generated according to the same distribution as in the real world, according to \adv{A}. This is also true for \adv{B}'s simulation, as for $b=0$, $K = e(g,g)^{\alpha \cdot s} = e(g,g)^{(a^{n+1} \cdot s) \cdot y_0} = Z^{y_0}$, so it's a valid ciphertext under randomness $s$. When $b=1$, the $K$ is however picked randomly from $\mathcal{K}$, resulting in a correctly produced header Hdr with randomness $s$, but the accompanying key $K$ is random, making the pair $(\hdr, K)$ where $\hdr$ does not correspond to $K$.
|
|
\end{description}
|
|
This construction will be the foundation of the \emph{Ad-Hoc Broadcast Encryption} which we will explore in Section \ref{sec:AHBE} and likewise will this proof be brought up when exploring possible proofs of security of said \emph{Ad-Hoc Broadcast Encryption} scheme.
|
|
|
|
\section{Dynamic Threshold Public-Key Encryption}
|
|
In a Threshold Public-Key Encryption (\texttt{TPKE}) scheme, the decryption key corresponding to a public key is shared among a set of $n$ users \cite{TPKE}. Specific for \texttt{TPKE} is that for any ciphertext to be correctly decrypted, $t$ receivers has to participate and cooperate. Thus, if any number of users less than $t$ try to decrypt, they will gain nothing, hence the threshold part of \texttt{TPKE}. A limitation of existing \texttt{TPKE} schemes however, is that the threshold value of $t$ is tightly connected to the public key of the system, as such, one has to fix the threshold for good, when setting up the system. Furthermore, existing schemes also has the limitation of being set up for a specific receiver set of $n$ users. As such, if the receiver set changes, a new scheme will have to be created, which naturally brings an overhead whenever any receiver exits or joins the system. Many applications would benefit from a flexibility to choose $t$ whenever broadcasting. As such \emph{Dynamic Threshold Public-Key Encryption} (\texttt{DTPKE}) is proposed \cite{DTPKE}.
|
|
|
|
In a sense, Broadcast Encryption Systems can be related to notion of \emph{Threshold Public Key Encryption Systems} (\texttt{TPKE}) if we define the authorized set of the \texttt{TPKE} system to be equal to $S$ and the threshold parameter $t$ is set to be $1$. This is only true however, for the specific value of $t=1$, thus, specialized systems can be designed for the purpose of being broadcast encryption systems and \texttt{TPKE} can almost be seen as a general case of \texttt{BE}. However, as \texttt{BE} schemes also bring the flexibility of choosing the recipient set $S$, we need something stronger than \texttt{TPKE}, to define \texttt{BE} as a special case. To this end we introduce \texttt{DTPKE}.
|
|
|
|
% TODO: Consistency with encryption key or Encryption Key. Likely the former.
|
|
|
|
\subsection{Modelling Dynamic Threshold Public-Key Encryption}
|
|
A \texttt{DTPKE}-scheme consist of $7$ algorithms: \texttt{DTPKE} $= ($\texttt{Setup}, \texttt{Join}, \texttt{Encrypt}, \texttt{ValidateCT}, \texttt{ShareDecrypt}, \texttt{ShareVerify}, \texttt{Combine}$)$.
|
|
|
|
\begin{description}
|
|
\item[Setup$()$] Uses security parameter $\lambda$. Outputs a set of system parameters: $$\mathtt{params} = (MK,EK,DK,VK,CK).$$ $MK$ is a Master Secret Key, $EK$ is the Encryption Key, $DK$ is the Decryption Key, $VK$ is the Validation Key and $CK$ is the Combination Key. $MK$ is kept secret by the issuer, but the other four are public parameters.
|
|
\item[Join$(MK, \mathtt{ID})$] Takes the $MK$ and an identity \ID of a user. Outputs the user's keys $(usk, upk, uvk)$, where $usk$ is the secret key used for decryption, $upk$ is the public key used for encrypting and $uvk$ is the verification key. $upk, uvk$ are both public, whereas $usk$ is given privately to the user.
|
|
\item[Encrypt$(EK, S, t, M)$] Takes the encryption key, the public keys of the users within the receiver set $S$, a threshold $t$ and a message to be encrypted, $M$. Outputs a ciphertext.
|
|
\item[ValidateCT$(EK, S, t, C)$] Takes the encryption key, the public keys of the receiver set, a threshold and a ciphertext. Checks whether $C$ is a valid ciphertext with respect to $EK, S$ and $t$.
|
|
\item[ShareDecrypt$(DK, \mathtt{ID}, usk, C)$] Takes the decryption key, a user id \ID and his private key $usk$, as well as a ciphertext $C$. Outputs a decryption share $\sigma$ or $\perp$.
|
|
\item[ShareVerify$(VK, \mathtt{ID}, uvk, C, \sigma)$] Takes the verification key $VK$, a user id \ID and his verification key $uvk$ plus a ciphertext $C$ and decryption share $\sigma$. Checks whether $\sigma$ is a valid decryption share with respect to $uvk$.
|
|
\item[Combine$(CK, S, t, C, T, \Sigma)$] Takes the combination key $CK$, a ciphertext $C$, some subset $T \subseteq S$ of $t$ authorised users and $\Sigma = (\sigma_1, \dots, \sigma_t)$ which is a list of $t$ decryption shares. Outputs the plaintext $M$ or $\perp$.
|
|
\end{description}
|
|
|
|
|
|
\subsection{Security Model}
|
|
|
|
\begin{description}
|
|
\item[Setup] The challenger runs Setup$()$ of the \texttt{DTPKE} scheme using security parameter $\lambda$ implicitly, obtaining the $$\mathtt{params} = (MK,EK,DK,VK,CK).$$ All the public parameters (all except for $MK$) are given to the adversary \adv{A}.
|
|
\item[Phase 1] The adversary is allowed to adaptively issue queries where query $q_i$ is one of three queries;
|
|
\begin{itemize}
|
|
\item A \texttt{Join} query on an id \texttt{ID}; The challenger runs the \texttt{Join} algorithm on input $(MK,\mathtt{ID})$, to create a new user in the system. Note that the challenger has $MK$ from the setup step.
|
|
\item A \texttt{Corrupt} query on an id \texttt{ID}: The challenger forwards the corresponding private key to the adversary.
|
|
\item A \texttt{ShareDecrypt} query on an id \texttt{ID} and a header \texttt{Hdr}: The challenger runs the \texttt{ShareDecrypt} algorithm of the \texttt{DTPKE} scheme on \texttt{Hdr}, using the corresponding private key, and forwards the partial decryption to the adversary.
|
|
\end{itemize}
|
|
\item[Challenge] The adversary \adv{A} outputs a target set of users $S^*$ as well as a threshold $t^*$, with the constraint that $|S^*| \leq t^*$. The challenger selects $b \in_R \set{0, 1}$ and then runs \texttt{Encrypt} to obtain $\mathtt{Hdr}^*, k_0) \la \mathtt{Encrypt}(EK, S^*, t^*)$. Furthermore, he picks another key $k_1 \in_R \mathcal{K}$. The challenger outsputs $(\mathtt{Hdr}^*, k_b)$ to \adv{A}.
|
|
\item[Phase 2] The adversary \adv{A} is allowed to continue adaptively issuing \texttt{Join, Corrupt} and \\ \texttt{ShareDecrypt} queries, with the only constraint that he asks queries for less than or equal to $t^*-1$ $\mathtt{IDs} \in S^*$.
|
|
\item[Guess] The adversary outputs a guess bit $b' \in \{0,1\}$ and he will win the game if $b' = b$.
|
|
|
|
From this basic description, we can define three sub definitions:
|
|
\begin{itemize}
|
|
\item \emph{Non-Adaptive Adversary} (\texttt{NAA}): We restrict the adversary to decide upon the challenge set $S^*$ as well as the threshold $t^*$ before the \texttt{Setup} step is run.
|
|
\item \emph{Non-Adaptive Corruption} (\texttt{NAC}): We restrict the adversary to decide before the \textbf{Setup} is run, which identities will be corrupted.
|
|
\item \emph{Chosen-Plaintext Adversary} (\texttt{CPA}): We restrict the adversary from issuing \texttt{ShareDecryption} queries.
|
|
\end{itemize}
|
|
|
|
\end{description}
|
|
|
|
|
|
|
|
% TODO: Consider moving this to the appendix and perhaps just note in the body of the report an informal description of the errors you found?
|
|
|
|
\subsection{A Construction and the Security Thereof}
|
|
It should be noted that this scheme is very long and as such will be left out of the report, but it will be included in the appendix, completely as the original authors wrote it. We will instead list their security proof, which contains an error worth of noting. Their proof is a reduction to the \texttt{MSE-DDH} problem, as defined in Section \ref{sec:MSE-DDH}. Regardless, their security proof states that the \texttt{DTPKE} scheme has \texttt{IND-NAA-NAC-CPA} security (Non-Adaptive-Adversary, Non-Adaptive-Corruption, Chosen-Plaintext-Attack).
|
|
|
|
\begin{theorem}
|
|
For any $l,m,t,$ $\mathbf{Adv}^{ind}_{\mathtt{DTPKE}}(l,m,t) \leq 2 \cdot \mathbf{Adv}^{\text{MSE-DDH}}(l,m,t)$. Where $l$ denotes the total number of \textbf{Join} queries that can be issued by the adversary, $m$ is the maximal size the authorised set of receivers is allowed to be, $t$ is the threshold.
|
|
\end{theorem}
|
|
\begin{proof}
|
|
Let \texttt{DTPKE} denote the construction as described in Appendix \ref{app:DTPKE-Scheme}. Now, to establish the semantic security, the \texttt{IND-NAA-NAC-CPA} security, for static adversaries of the \texttt{DTPKE} scheme, we describe a reduction to the \texttt{MSE-DDH} problem. To this end, we assume an adversary \adv{A} who can break the scheme under an $(l,m,t)$-collusion. This adversary \adv{A} will be used to build an algorithm \adv{B} who can then distinguish the two distributions of the $(l,m,t)$-\texttt{MSE-DDH} problem.
|
|
|
|
The algorithm \adv{B} is given as input some group system $\mathtt{Pub} = (p, \Gm_1, \Gm_2, \Gm_T, e)$ as well as an $(l,m,t)$-\texttt{MSE-DDH} instance in \texttt{Pub} as described in Section \ref{sec:MSE-DDH}. The \texttt{MSE-DDH} instances gives us, \adv{B}, two coprime polynomials $f_{poly}$ and $g_{poly}$ of orders $l$ and $m$ with pairwise distinct roots $(x_1, \dots, x_l)$ and $(x_{l+t}, \dots, x_{l+t+m-1})$ respectively. Finally, \adv{B} has all the exponents;
|
|
\begin{align*}
|
|
& x_1, \dots, x_\ell, \qquad \qquad \qquad y_1, \dots, y_m \\
|
|
& g, g^{\gamma}, \dots, g^{\gamma^{\ell + t - 2}}, \qquad \quad g^{k\cdot \gamma \cdot f(\gamma)} \\
|
|
& g^{\alpha}, g^{\alpha \cdot \gamma}, \dots, g^{\alpha \cdot \gamma^{\ell + t}}, \\
|
|
& h, h^{\gamma}, \dots, h^{\gamma^{m-2}}, \\
|
|
& h^{\alpha}, h^{\alpha \cdot \gamma}, \dots, h^{\alpha \cdot \gamma^{2m - 1}}, \qquad h^{k \cdot g(\gamma)},
|
|
\end{align*}
|
|
as well as the $Z \in \Gm_T$ which can either be $e(g,h)^{k \cdot f(\gamma)}$ or some random element within $\Gm_T$. We will henceforth be using $g_{\mathtt{MSE-DDH}}$ and $h_{\mathtt{MSE-DDH}}$ as the two generators $g$ and $h$ for notational purposes. We define the following polynomials:
|
|
$$f(X) = \prod_{i=1}^\ell (X+x_i), \quad q(X) = \prod_{i=1}^{\ell +t - 1} (X+x_i), \quad g(X) = \prod_{i=1}^{\ell +t+m - 1} (X+x_i)$$
|
|
|
|
Do note here, that the proof does not argue in any way for the sudden appearence of the $x_i$ for $i = \ell+1, \dots, \ell + t - 1$. We have not looked further into a fix for this, however we note that they are used for the set of $t-1$ users of the \emph{target set} who can be corrupted and as such \adv{B} must be prepared to be able to both give a secret key for the specific user, while this key must also be used in the challenge to \adv{A}, as such, the key is not without relevance.
|
|
|
|
As mentioned, $q(X)$ corresponds to the $t-1$ users within the receiver set who may be corrupted. As we are in a static environment, both the receiver set and the corruption set has to be given in the initialisation phase, so we know these ahead of time. $f(X)$ corresponds to the set of $\ell$ users not in the target set, who can be corrupted and $g(X)$ defines the $m$ users of the target set that cannot be corrupted. These polynomials thus allow us to be able to simulate the $\ell +t - 1$ corruptions where $t-1$ are in the target set.
|
|
|
|
For $i \in [1, \ell + 1 - 1]$ we thus set $$f_i(x) = \frac{f(x) \cdot q(\gamma)}{x+x_i}, $$ which is a polynomial of degree $\ell + t - 2$
|
|
\begin{description}
|
|
\item[Init] The adversary \adv{A} outputs his target set $S^* = \set{\mathtt{ID}^*_1, \dots, \mathtt{ID}^*_s}$ as well as a set $\overbar{C} = \set{\overbar{\mathtt{ID}}_1, \dots, \overbar{\mathtt{ID}}_c}$ of identities that \adv{A} intends on corrupting, such that $c \leq \ell$ and $|S^* \cap \overbar{C}| \leq t-1$.
|
|
\item[Setup] To generate the system parameters of the \texttt{DTPKE} scheme, \adv{B} sets $g = g_{\mathtt{MSE-DDH}}^{f(\gamma) \cdot q(\gamma)}$ where $g_{\mathtt{MSE-DDH}}$ come from the \texttt{MSE-DDH} problem as one of the two generators. Note that this is merely set for the sake of replicating what the original scheme does. $g$ is never published and is thus never required to be directly computed, which is not possible in this case either. \adv{B} then set:
|
|
$$h = h_{\mathtt{MSE-DDH}}, \qquad u = g_{\mathtt{MSE-DDH}}^{\alpha \cdot \gamma \cdot f(\gamma) \cdot q(\gamma)} = g^{\alpha \cdot \gamma}$$
|
|
$$v = e(g_{\mathtt{MSE-DDH}}, h_{\mathtt{MSE-DDH}})^{\alpha \cdot f(\gamma) \cdot q(\gamma)} = e(g,h)^\alpha$$
|
|
Where $u$ and $v$ can be computed from the \texttt{MSE-DDH} instance input, since $f \cdot q$ is a $\ell + t - 1$ degree polynomial.
|
|
|
|
\adv{B} then creates a set $\mathcal{D} = \set{d_i}_{i=1}^{m-1}$ which is a set of dummy users such that:
|
|
\begin{itemize}
|
|
\item $\mathcal{D}_{m+t-s^*-1} = \set{d_i}_{i=1}^{m+t-s^*-1}$ is a subset of $\set{x_j}_{j=\ell+t}^{\ell+t+m-1}$, which corresponds to the dummy users included to complete the target set in the challenge.
|
|
\item The rest of the dummy users: $\set{d_i}_{m+t-s^*}^{m-1}$ are random elements in $\mathbb{Z}_p$.
|
|
\end{itemize}
|
|
\adv{B} then defines the encryption key $EK = (m,u,v,h^\alpha, \set{h^{\alpha \cdot \gamma^i}}_{i=1}^{2m-1}, \mathcal{D})$ and the combination key $CK = (h, \set{h^{\gamma^i}}_{i=1}^{m-2}, \mathcal{D})$.
|
|
\item[Generation of Users' Keys] \hspace{1cm} % Hack to force the itemize to the line below ..
|
|
|
|
\begin{itemize}
|
|
\item For each $\overbar{\mathtt{ID}} \in \overbar{C}$, i.e. each \ID which is to be corrupted, \adv{B} computes and sends $(\overbar{\text{usk}}, \overbar{\text{upk}})$ to \adv{A} where:
|
|
\begin{align*}
|
|
&\overbar{\text{upk}} = x_i,\\
|
|
&\overbar{\text{usk}} = g_{\mathtt{MSE-DDH}}^{f_i(\gamma)} = g^{\frac{1}{\gamma + x_i}}
|
|
\end{align*}
|
|
with the constraint that if $\mathtt{ID} \in S^*$ then $x_i$ must be taken from the subset $\set{x_j}_{j=\ell+1}^{\ell+t-1}$ i.e. the ones used in polynomial $q(X)$ (the ones we do not know where originate from) and otherwise $x_i$ must be taken from $\set{x_j}_{j=1}^{\ell}$, i.e. polynomial $f(X)$ or the roots of $f_{poly}$.
|
|
\item For each $\mathtt{ID} \in S^* - (S^* \cap \overbar{C}$, so each \ID which is in the target set \emph{but not} in the corruption target set, \adv{B} sends $upk = x_i$ to \adv{A} where $x_i$ must come from $\set{x_j}_{j=\ell+t}^{\ell+t+m-1} - \mathcal{D}_{m+t-s^*-1}$, i.e. the users from $g(X)$, but without the dummy users included to complete the target set in the challenge.
|
|
\item For each $\mathtt{ID} \not\in S^* \cup \overbar{C}$, each users who is not in the receiver set and may not be corrupted, \adv{B} sends $upk = x$ to \adv{A} where $x \not\in \set{x_j}_{j=1}^{\ell + t + m -1}$
|
|
\end{itemize}
|
|
\adv{B} gives the group information $Pub$ as well as $(EK, CK)$ to \adv{A}.
|
|
\item[Challenge] \adv{B} computes \textbf{Encrypt} in order to obtain the challenge information:
|
|
$$(\hdr^*, S^*, t, K) = \mathbf{Encrypt}(EK, S^*, t), \text{ where}$$
|
|
$$C_1 = g_{\mathtt{MSE-DDH}}^{-k \cdot \gamma \cdot f(\gamma)}, \qquad C_2 = h_{\mathtt{MSE-DDH}}^{k \cdot g(\gamma)}, \qquad K = Z,$$
|
|
$$|S| = s^*, \qquad S^* \subseteq \set{x_j}_{j=\ell+1}^{\ell+t+m-1} - \mathcal{D}_{m+t-s^*-1}$$
|
|
\adv{B} selects $b \in_R \set{0,1}$, sets $K_b = K$ and $K_{1-b} \in_R \mathcal{K}$. Then returns $(\hdr^*,K_0, K_1)$ to \adv{A}.
|
|
\item[Guess] \adv{A} outputs a guess $b' \in \set{0,1}$ and wins if $b' = b$.
|
|
\end{description}
|
|
Without proof we state that
|
|
|
|
\begin{align*}
|
|
\mathbf{Adv}^{\mathtt{MSE-DDH}} &= \\
|
|
&\quad \frac{1}{2} \times (Pr(b'=1 | b=1 \wedge \text{real}) + Pr(b'=1 | b=0 \wedge \text{real}) \\
|
|
&- \frac{1}{2} \times (Pr(b'=1 | b=1 \wedge \text{random}) + Pr(b'=1 | b=0 \wedge \text{random}).
|
|
\end{align*}
|
|
|
|
Now, as the distribution of $b$ is independent from the adversarys view; $$Pr(b'=1 | b=1 \wedge \text{random}) = Pr(b'=1 | b=0 \wedge \text{random})$$ Thus, the left side cancels out. In the real case however, the distribution of all variables which are defined by \adv{B} comply with the definition of the semantic security game, as all simulations are perfect. Thus, to conclude:
|
|
$$\mathbf{Adv}_{\mathtt{DTPKE}}^{\text{ind}}(\mathcal{A}) = Pr(b'=1 | b=1 \wedge \text{real}) - Pr(b'=1 | b=0 \wedge \text{real})$$
|
|
Is exactly equal to $$2 \cdot (\frac{1}{2} \times (Pr(b'=1 | b=1 \wedge \text{real}) + Pr(b'=1 | b=0 \wedge \text{real})).$$
|
|
\end{proof}
|
|
|
|
|
|
\section{Ad-Hoc Broadcast Encryption}
|
|
\label{sec:AHBE}
|
|
The scheme presented in \ref{sec:BE} requires a \emph{trusted dealer} to perform its \textbf{BSetup} and \textbf{BKeyGen}. It goes for all of \emph{Broadcast Encryption} systems, that they require a trusted entity to generate and distribute secret keys to all users. This tends to make the system very rigid and not applicable to ad hoc networks or peer-to-peer networks. A \emph{potential} solution to this is presented by \cite{AHBE}. They present a solution to the fully dynamic case of broadcast encryption. This has significant ties to the \emph{Dynamic Threshold Encryption} scheme in which users could freely join and leave, however they did not quite get rid of the trusted dealer. This is accomplished here however.
|
|
|
|
In an Ad-Hoc Broadcast Encryption (\texttt{AHBE}) scheme all users possess their own public key, which is independently generated by themselves with no need for a trusted authority or setup. Then, by only seeing the public keys of users, a sender can securely broadcast to \emph{any} subset of the users. Only users within the picked subset can decrypt the message. To accomplish this, the authors create a generic transformation from any \emph{key homomorphic} BE (\texttt{KHBE}) scheme to an \texttt{AHBE} scheme. It turns out that the scheme of Gentry and Waters presented in Section \ref{sec:BE} is just this and the transformation will be performed on this.
|
|
|
|
\subsection{Modelling Ad-Hoc Broadcast Encryption}
|
|
As an \texttt{AHBE} system eliminate the trusted dealer, the \textbf{BSetup} and \textbf{BKeyGen} step morph together, as there is no global \textbf{BSetup} step required, but merely something each user should locally run. As all other schemes defined in this paper, this too is defined to be a \emph{Key Encapsulation Method} (\texttt{KEM}).
|
|
|
|
\begin{description}
|
|
\item[KeyGen$(i,n,N)$] Let $N$ be defined as the number of potential receivers of the scheme and let $n \leq N$ be defined as the maximum number of receivers of an ad-hoc broadcast recipient group. The \textbf{KeyGen} (this) algorithm is run by each user $i \in [1,N]$ to create her own public/secret key pair. A user takes $n, N$ as well as her own index $i \in [1,N]$. It's not mentioned how the user receives this index in practice, without simply having a central authority giving them this, but one could imagine the users being aware of how many recipients there are in total and simply increment this to get their own index, if one disregards the issues of people joining the peer-to-peer network at the same time. The \textbf{KeyGen} algorithm outputs the users public/secret key pair $(PK_i,SK_i)$. We define a shorthand for several users key pairs; $\{(PK_i, SK_i)\ |\ i \in S \subseteq [1,N] $ as $(PK_i,SK_i)_{S}$ and likewise only for the public keys; $(PK_i)_{S}$. All of this depends on a security parameter $\lambda$, which is implicitly given to the algorithm.
|
|
\item[AHBEnc$(S, (PK_i)_{S})$] This is run by any sender who may or may not be in $[1,N]$, as long as the sender knows the public keys of the receivers. It takes the recipient set $S \subseteq [1,N]$ and the public keys for $i \in S$; $(PK_i)_{S}$. Given that $|S| \leq n$, the algorithm returns a pair $(\hdr, K)$ where Hdr is the header, the encapsulated key, and $K$ is the message encryption key.
|
|
\item[AHBDec$(S, j, sk_j, \hdr, (PK_i)_{S})$] This allows each recipient $i \in S$ to decrypt the message encryption key which is hidden in the header. If $|S| \leq n, j \in S$, then the algorithm returns the message encryption key $k$.
|
|
|
|
An \emph{Ad-Hoc Broadcast Encryption} system is defined to be \textbf{correct} if any user within the receiver set $S$ can decrypt a valid header.
|
|
\end{description}
|
|
|
|
|
|
\subsection{Definition of Adaptive Security in \AHBE}
|
|
In an adaptively secure ad-hoc broadcast encryption system, the adversary is allowed access to all the public keys of the receivers and to ask for several secret keys before choosing the set of indices that the adversary wishes to attack.
|
|
|
|
% Both the Challenger and an adversary \adv{A} are given the security parameter $\lambda$. \\
|
|
\begin{description}
|
|
\item[Setup] The Challenger runs $\mathbf{KeyGen}(i, n, N)$ to obtain the users' public key. These public keys and the public parameters are given to the adversary \adv{A}.
|
|
\item[Key Extraction Phase] The Challenger runs $\mathbf{KeyGen}(i, n, N)$ to obtain the users' public key. These public keys and the public parameters are given to the adversary \adv{A}.
|
|
\item[Challenge] \adv{A} specifies some challenge set $S^* \subseteq [1,N]$ s.t. \adv{A} has corrupted none of the users $i$ within $S^*$. The challenger sets $(\hdr^*, k_0) \leftarrow \mathbf{AHBEnc}(S^*, (PK_i)_{S^*})$ and $k_1 \in_R \mathbb{K}$. The challenger sets $b \in_R \{0,1\}$. It gives $(\hdr^*, k_b)$ to the adversary \adv{A}.
|
|
\item[Guess] The adversary \adv{A} will output a bit $b' \in \{0,1\}$ as an attempt to guess the bit $b$. \adv{A} wins if $b' = b$.
|
|
|
|
The advantage of \adv{A} is as expected; $Adv^{\texttt{AHBE}}_{\mathcal{A},n,N}(1^\lambda) = |Pr(b = b') - \frac{1}{2}|$ and the scheme is deemed adaptively secure if this advantage is negligible in the security parameter $\lambda$.
|
|
\end{description}
|
|
|
|
|
|
|
|
\subsection{Key Homomorphism}
|
|
As mentioned, the authors present a transformation for any key homomorphic BE scheme. As such, we'll quickly define this.
|
|
|
|
% Reference the AHBE article
|
|
\begin{definition}[Key Homomorphism]
|
|
\normalfont Let $\mlarge{\oplus} : \Gamma \times \Gamma \rightarrow \Gamma$, $\mlarge{\odot} : \Omega \times \Omega \rightarrow \Omega$ and $\mlarge{\ocircle} : \mathbb{K} \times \mathbb{K} \rightarrow \mathbb{K}$ be efficient operations in the public key space $\Gamma$, the decryption key space $\Omega$ and the message encryption key space $\mathbb{K}$, respectively. A BE scheme is then said to be homomorpic if the following conditions hold for all $S \subseteq [1,N]$ for $|S| \leq n$ and all $i \in S$:
|
|
\begin{enumerate}
|
|
\item If $(PK_1, SK_1) \leftarrow $\textbf{BSetup}$(n,N)$, where \textbf{BSetup} is the setup algorithm for the BE scheme, $n$ is the size of the receiver set and it is allowed to be of size $N$, \vsp{2mm}
|
|
$(PK_2, SK_2) \leftarrow $\textbf{BSetup}$(n,N)$, \vsp{2mm}
|
|
$(d_1(i) \la $ \textbf{BKeyGen}$(i, SK_1)$, \vsp{2mm}
|
|
$(d_2(i) \la $ \textbf{BKeyGen}$(i, SK_2)$, \vsp{2mm}
|
|
$(\hdr, k) \la $\textbf{BEnc}$(S, PK_1 \mlarge{\oplus} PK_2)$, \vsp{2mm}
|
|
then \textbf{BDec}$(S, i, d_1(i) \mlarge{\odot} d_2(i), \hdr, PK_1 \mlarge{\oplus} PK_2) = k$.
|
|
\item If \hdr is a header of $k_1$ under $(S, PK_1)$ and also a header of some $k_2$ under $(S, PK_2)$, then it also a header of $k_1 \mlarge{\ocircle} k_2$ under $(S, PK_1 \mlarge{\oplus} PK_2)$.
|
|
\end{enumerate}
|
|
\end{definition}
|
|
|
|
\subsection{Transforming \KHBE to \AHBE}
|
|
The main idea behind their proposed transformation is to use the homomorphic property of the keys of the underlying \KHBE scheme, as illustrated in Figure \ref{fig:KHBEMatrix}, where a question mark (?) indicates that, that specific key is not published, i.e. $d_i(i)$ for $i = 1,\dots,n$, thus, every other key is published as a part of the different public keys.
|
|
|
|
\begin{figure}
|
|
|
|
\[
|
|
\begin{pmatrix}
|
|
\U_1 & \U_2 & \U_3 & \dots & \U_n & \texttt{sender} \vsp{3mm}
|
|
? & d_1(2) & d_1(3) & \dots & d_1(n) & PK_1 \vsp{2mm}
|
|
d_2(1) & ? & d_2(3) & \dots & d_2(n) & PK_2 \vsp{2mm}
|
|
d_3(1) & d_3(2) & ? & \dots & d_3(n) & PK_3 \vsp{2mm}
|
|
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \vsp{2mm}
|
|
d_n(1) & d_n(2) & d_n(3) & \dots & ? & PK_n
|
|
\end{pmatrix}
|
|
\]
|
|
\caption{Matrix explaining the connection between the different keys of the different users}
|
|
\label{fig:KHBEMatrix}
|
|
\end{figure}
|
|
|
|
Within Figure \ref{fig:KHBEMatrix}, the $PK_i$ is the public key of the BE instance specifically generated by user $i$. A decryption key $d_i(j)$ is generated by user $i$ for user $j$, in the underlying scheme. Each row is then published ($PK_i$) by the corresponding member of the group of broadcast receivers, $\U_i$, but their own specific decryption key , $d_i(i)$ is not published. The key homomorphism then allow for an arbitrary receiver set $S$, as all of the public keys for $i \in S$ can be easily aggregated; $\mlarge{\oplus}_{i \in S} PK_i = PK_{\mathtt{AHBE}}$ into a new public key of a new instance of the underlying BE scheme, such that the $j$'th column $\{d_i(j)\}^n_{i=1}$ can be aggregated into a decryption key for this instance; $d(j) = \mlarge{\odot}_{i \in S}d_i(j)$, i.e. a decryption key for the public key $PK_{\mathtt{AHBE}}$. Since the diagonal of the matrix is not published, only user $\U_i$ knows $d_i(i)$ and is thus the only one who can compute $d(i)$. This results in a system where a sender can choose any receiver set $S \subseteq[1,N]$ and broadcast to this set under the key $PK_{\mathtt{AHBE}} = \mlarge{\oplus}_{i \in S} PK_i$ and only users $\U_i$ for $i \in S$ can decrypt using their decryption key $d(i)$. As $PK_{\mathtt{AHBE}}$ functions like a public key for a regular BE scheme where all users have decryption keys, if $j \not\in S$, user $\U_j$ won't be able use her decryption key $d(j) = \mlarge{\odot}_{i \in S}d_i(j)$, as only users in the intended recipient set can decrypt in the new scheme. Note that it is a requirement of the scheme, that all $PK_i$ should be computationally independent and \emph{different}. Intuitively, if they are not different such that $d_1(1) = d_2(1)$, it's trivial to compute the decryption key of user $\U_1$, by simply looking at the data published by $\U_2$.
|
|
|
|
% TODO: Be very consistent in what you call the public keys of the AHBE scheme!
|
|
|
|
\subsubsection{Formal Conversion from \KHBE to \AHBE}
|
|
As discussed, an \AHBE scheme consist of three algorithms; \textbf{KeyGen, AHBEnc, AHBDec}.
|
|
|
|
\begin{description}
|
|
\item[KeyGen] Let the potential receivers be a set $\{1,\dots,N\}$. Let $n \leq N$ be the maximum number of recipients within a single broadcast. For simplicity, we assume that $n = N$. Generate an instance $\pi$ of a \KHBE scheme and let this be a system parameter. The KeyGen algorithm then does the following:
|
|
\begin{itemize}
|
|
\item For receiver $i \in [1,n]$, invoke the setup algorithm of the BE Scheme used by the underlying \KHBE scheme; \textbf{BSetup}, to generate a public/private key pair $(PK_i, SK_i)$ for the \KHBE scheme.
|
|
\item Receiver $i$ runs \textbf{BKeyGen} and obtains $d_i(j) \leftarrow \mathbf{BKeyGen}(j,SK_i)$ for $j = 1,\dots,n$. The public key of the specific receiver $i$ in the \AHBE scheme is then:
|
|
$$PK_{\mathtt{AHBE}} = \{d_i(j) | 1 \leq i \neq j \leq n\} \cup \{PK_i\}$$ Where $PK_i$ came from the \textbf{BSetup} call.
|
|
\item The private key of receiver $i$ is then set to be the \emph{unpublished} $d_i(i)$.
|
|
\end{itemize}
|
|
\item[AHBEnc] Computes the header and key for a receiver set $S$ in the following way:
|
|
\begin{itemize}
|
|
\item Pick receiver set $S \subseteq [1,n]$
|
|
\item Compute the public key of the broadcast:
|
|
$$PK_{\mathtt{AHBE}} = \mlarge{\oplus}_{i \in S} PK_i$$
|
|
\item Invoke the underlying \KHBE encryption algorithm \textbf{BEnc}$(\cdot)$ in order to compute the header of the key:
|
|
$$(Hdr, k) \la \mathbf{BEnc}(S, PK_{\mathtt{AHBE}})$$
|
|
and send $(S, Hdr)$ to the receiver set.
|
|
\end{itemize}
|
|
\item[AHBDec] Due to the underlying \KHBE scheme, the receiver $i \in S$ can compute a decryption key for the \texttt{AHBE} public key $PK_{AHBE}$ by computing:
|
|
$$d(i) = d_i(i) \mlarge{\odot}\{\mlarge{\odot}_{j \in S}^{j \neq i} d_j(i)\} = \mlarge{\odot}_{j \in S} d_j(i)$$
|
|
As only user $\U_i$ knows $d_i(i)$ only she can compute $d(i)$. Due to the homomorphism of the \KHBE scheme, $d(i)$ is a valid decryption key for the public key $PK_{AHBE}$, as long as $i \in S$. To perform this decryption, each user $\U_i$ for $i \in S$, invokes the \KHBE decryption algorithm \textbf{BDec}$(\cdot)$;
|
|
$$k = \mathbf{BDec}(S, i, d(i), Hdr, K) $$
|
|
\end{description}
|
|
|
|
|
|
% TODO: Make big operators for the key homomorphism things
|
|
|
|
\subsection{Proof of Security}
|
|
The security of the \AHBE scheme is proven by a reduction to the underlying \KHBE scheme. As such, if the underlying \KHBE scheme is presumed to be secure, so should the \AHBE scheme. Furthermore, the \AHBE scheme has semi-static security, if the \KHBE scheme has adaptive security.
|
|
|
|
\begin{theorem}
|
|
The generic \AHBE scheme has Semi-Static security if the underlying \KHBE scheme has Adaptive security.
|
|
\end{theorem}
|
|
|
|
\begin{proof}
|
|
We note that something is wrong within this proof, which we will point out in Section \ref{sec:ProofIssues}.
|
|
We wish to construct an adversary \adv{B} who can break the security of the underlying \KHBE scheme, by utilising the adversary \adv{A} who is assumed to be able to break the security of the \AHBE scheme. In the initialisation phase, \adv{A} will commit to a set $\tilde{S} \subseteq [1,n]$. Keep in mind that \adv{A} is a semi-static adversary, so he has to commit to a set of which he wishes to attack a subset of.
|
|
|
|
In the setup phase, \adv{B} picks a user at randomly from within $\tilde{S}$; $i^* \in_R \tilde{S}$. \adv{B} then sets up the \emph{adaptive} game with the \KHBE challenger \CH. \CH returns the system parameters and the \KHBE public key, denoted by $PK_{i^*}$. \adv{B} then queries for the secret key $d_{i^*}(j)$ for each index $j \not\in \tilde{S}$.
|
|
|
|
For $i \in [1,n] \setminus \{i^*\}$, \adv{B} can generate the \KHBE public/private key pair $(PK_i, SK_i)$, as it's not the target of \adv{B}, as it is \emph{adaptive}. This allows \adv{B} to generate the corresponding decryption keys $d_i(j)$ for each index $j \in \{1,n\} \setminus \{i\}$. Then, for $i = 1,\dots,n$, \adv{B} generate $K_i = \{d_i(j) | 1 \leq i \neq j \leq n\} \cup \{PK_i\}$, such that all users' public keys can be provided to the adversary \adv{A}, as a part of the setup phase for the \AHBE scheme.
|
|
|
|
In the corruption phase, \adv{A} may corrupt any user $i \in \{1,\dots,n\} \setminus \tilde{S}$. These users are all however fabricated by the algorithm \adv{B}, so \adv{B} has the public/private key pairs for any user outside of $\tilde{S}$, thus it is no issue to yield the decryption key $d_i(i)$ and answer the query correctly.
|
|
|
|
In the challenge phase, the adversary \adv{A} decides upon an attack set $S^* \subseteq \tilde{S}$. This is given to \adv{B} who then has two options. Either $i^* \not\in S^*$ and \adv{B} reports failure, as the answer from the \AHBE adversary \adv{A} will not be of any help to \adv{B} in breaking the underlying \KHBE scheme. On the other hand, if $i^* \in S^*$, \adv{B} simply forwards the set $S^*$ to the challenger \CH and requests for a \KHBE header and key from \CH. \adv{B} receives a pair $(\hdr^*, k_b)$ under $(S^*, PK_{i^*})$. \adv{B} then has to convert this into a wellformed challenge header for $(S^*, \mlarge{\oplus}_{j \in S^*} PK_j)$ meant for the adversary \adv{A}. Thus, as we know all of the public/private key pairs, we can compute $\mathbf{BDec}(S^*, i^*, d_i(i^*), \hdr^*, PK_i) = k_{b,i}$ for $i \in S^* \setminus \{i^*\}$, noting that, due to the second property of the key homomorphism, we have for all $j \in S^*$; $\mathbf{BDec}(S^*, j, d_i(j), \hdr^*, PK_i) = k_{b,i}$. \adv{B} then sets $k^*_b = k_b \mlarge{\ocircle} \{\mlarge{\ocircle}_{i \in S^* \setminus \{i^*\}} k_{b,i}\}$ and then send $(\hdr^*, k^*_b)$ as a challenge to \adv{A}. Due to the homomorphic properties, if $\hdr^*$ hides the key $k_b$ under $(S^*, PK_{i^*})$, then it also hides the key $k^*_b$ under $(S^*, \mlarge{\oplus}_{i \in S^*} PK_i)$, else the key $k_b$ is picked uniformly from the keyspace, so the aggregation of keys $k_b \mlarge{\ocircle}\{ \mlarge{\ocircle}_{i \in S^* \setminus \{i^*\}} k_{b,i}\}$ still makes sense and will have the correct distribution, it will just be independent on $\hdr^*$.
|
|
|
|
Finally, when \adv{A} guesses bit $b'$, this is forwarded by \adv{B} to the \KHBE challenger \CH. Intuitively, \adv{B} will guess correct, if adversary \adv{A} guesses correct. Thus, if we assume adversary \adv{A} has advantage $\epsilon$, then the advantage of \adv{B} is $\frac{1}{n} \epsilon$, due to \adv{B} aborting in the case of $i^* \not\in S^*$, thus incurring a factor $\frac{1}{n}$.
|
|
\end{proof}
|
|
|
|
% TODO: Fix (?) proof
|
|
|
|
\subsection{Issues with the Proof}
|
|
\label{sec:ProofIssues}
|
|
The primary issue of this proof arises when the following question is raised: "How can the algorithm \adv{B} get the keys $d_{i^*}(j)$ for $j \in \tilde{S}$". These decryption keys will have to be a part of the public keys that \adv{B} has to present to \adv{A} in the beginning of the setup of the \AHBE scheme? The only key which is supposed to be private in the \AHBE scheme is $d_{i^*}(i^*)$, which is an issue, as \adv{B} eventually wants to attack the set $S^*$, which contains several of the users of which he will have to corrupt to get the missing keys. Specifically:
|
|
\begin{figure}
|
|
|
|
\[
|
|
\begin{pmatrix}
|
|
\U_1 & \U_2 & \U_3 & \dots & \U_n & \texttt{sender} \vsp{3mm}
|
|
? & \underline{d_1(2)} & \underline{d_1(3)} & \underline{\dots} & \underline{d_1(n)} & PK_1 \vsp{2mm}
|
|
d_2(1) & ? & d_2(3) & \dots & d_2(n) & PK_2 \vsp{2mm}
|
|
d_3(1) & d_3(2) & ? & \dots & d_3(n) & PK_3 \vsp{2mm}
|
|
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \vsp{2mm}
|
|
d_n(1) & d_n(2) & d_n(3) & \dots & ? & PK_n
|
|
\end{pmatrix}
|
|
\]
|
|
\caption{The missing keys are underlined}
|
|
\label{fig:UnderlinedKHBEMatrix}
|
|
\end{figure}
|
|
If we consider the user $i^*$ to be $\U_1$ and $\tilde{S}$ to simply be all $n$ recipients, then the algorithm \adv{B} is missing all the underlined keys, in the proof, as he is not allowed to query these keys, since he at some point want to attack the set $S^* \subseteq \tilde{S}$, which is against the rules of the adaptive game for the \texttt{(KH)BE} scheme, as defined in Section \ref{sec:BESec}.
|
|
|
|
To remedy this, we considered primarily one thing; Adding another homomorphic property such that we can safely use \emph{only} $\{i^*\}$ as the recipient set we sent to \CH.
|
|
|
|
\begin{definition}
|
|
If $\hdr^*$ is a header for $k_{i^*}$ under $(i^*, PK_{i^*})$, then it can be transformed into a header under $(S^*, PK)$ such that the aggregated public keys for the users within $S^*$ equals $PK$ and $i^* \in S^*$, where the underlying key is allowed to change.
|
|
\end{definition}
|
|
The property stated in \textbf{Definition 2} would allow \adv{B} to challenge for a header for a receiver set only containing $i^*$, which means he does not have to worry about querying for the decryption keys of the other receivers within $S^*$. When \adv{B} receives the challenge header from the challenger, this can be transformed into a proper header for the adversary \adv{A}.
|
|
This transformation would have to be both randomised and one-way, as otherwise the following attacks could take place;
|
|
|
|
\begin{description}
|
|
\item The adversary is a part of the set $[1,n]$, but not a part of the set $S^*$. If then a message containing some header $\hdr$ is sent out to the set $S^*$, the adversary should not be allowed to decrypt the header $\hdr$ and recover the underlying key $k$ intended for the receiver set $S^*$. Now, if the transformation is not \emph{one-way} and the transformation \emph{did not} change the value of the underlying key, it would be simple for the adversary to \emph{artifically add} himself to the set $S^*$, by simply performing the homomorphic operation on the header \hdr achieving some header $\hdr^*$ and then decrypt it, achieving the underlying key $k$. Thus, the transformation necessarily must change the underlying value of the key. Thus, if the transformation is not \emph{one-way}, but does in fact alter the underlying key, a similiar attack can be staged, with a little more effort from the adversary. Say the adversary is in the total set of receivers, but not in the set $S^*$. When he then receives the broadcasted message containing \hdr, he can perform the homomorphic operation as before to the header \hdr and achieve a new header $\hdr^*$ for an altered key $k^*$. However, as the transformation is \emph{not} one-way, the adversary can then perform the inverse homomorphic operation of \textbf{Definition 2} on the key $k^*$ and get back the original key, $k$. This is naturally not desirable either. We note that this inverse operation might not be easy to find, however it must exist per definition on the transformation not being \emph{one-way}.
|
|
\end{description}
|
|
|
|
As such, we conclude that this homomorphic operation must be randomised, one-way and it must alter the value of the underlying key. However, on the other hand, if the operation changes the underlying key, then we run into another issue. If the key changes, this homomorphic transformation can instead be used as a distinguisher.
|
|
|
|
We will describe a game where this homomorphic operation operation breaks the security of the underlying \texttt{BE}-scheme.
|
|
|
|
\begin{description}
|
|
\item An adversary \adv{A} will try to break the semantic security of a \texttt{BE}-scheme which posses the homomorphic properties with the addition of the one described above, by being able to recognise if a key is random or constructed for a specific receiver set. The adversary \adv{A} will receive a \hdr for some set $S$ which hides some key $k_b$, as well as a key $k$, which is either $k_b$ or $k_{1-b}$, from the challenger \CH. This \hdr is then transformed by \adv{A}, who will perform the homomorphic operations on the header \hdr and the key $k$, gaining a new pair $(\hdr^*, k^*)$. He can now decrypt the header $\hdr^*$ and check if the resulting key is $k^*$, if so, he knows the original \hdr and key $k$ must be corresponding, and otherwise they are not.
|
|
\end{description}
|
|
|
|
\subsection{An \AHBE Implementation}
|
|
\label{sec:AHBEImpl}
|
|
To achieve a Semi-Static secure \AHBE scheme, we first need to produce an Adaptively secure \texttt{BE} scheme which is key homomorphic. To this end, we use the scheme defined in Section \ref{sec:BE} coupled with the generic transformation from Semi-Static to Adaptive by Gentry and Waters \cite{GentryWaters}. Note that $g, h_{i,s} \text{ for } i \in [1,n]$ and $ s \in \{0,1\}$ are independent generators of a group $\mathbb{G}$ of prime order $p$, with a bilinear map $e : \Gm \times \Gm \ra \Gm_{T}$.
|
|
|
|
We define all algoritms prefixed by \texttt{AB} to be an \emph{adaptively secure} \texttt{BE} algorithm.
|
|
\begin{description}
|
|
\item[ABSetup$(n, \ell)$] Let $\alpha \in_R \mathbb{Z}_p$ and compute $g^\alpha, e(g,g)^\alpha$. The \texttt{BE} public key $PK$ is then; $PK = e(g,g)^\alpha$ and the private key is $SK = g^\alpha$.
|
|
\item[ABKeyGen$(i, SK)$] Set $r_i \in_R \mathbb{Z}_p$, $s_i \in_R \{0,1\}$. Output decryption key for user $i$; $d_i = (d_{i,0},\dots,d_{i,n})$:
|
|
$$d_i \leftarrow (d_{i,0},\dots,d_{i,n}) \quad \text{ where } \quad d_{i,0} = g^{-r_i}, \quad d_{i,i} = g^\alpha h^{r_i}_{i,s_i}, \quad d_{i,j \text{ for } i\neq j} h^{r_i}_{j,s_i}$$
|
|
\item[ABEnc$(S, PK)$] Set $t \in_R \Z_p$ and $$Hdr = (C_1,C_2, C_3), \quad \text{ where }\quad C_1 = g^t, \quad C_2 = (\prod_{i \in S}h_{i,0})^t,\quad C_3 = (\prod_{i \in S}h_{i,1})^t $$ Finally, set $K = e(g,g)^{t\cdot \alpha}$. Output $(\hdr, K)$. Send $(S, \hdr)$ to the receivers.
|
|
\item[ABDec$(S,i,d_i,\hdr, PK)$] Check if $i \in S$, if so; let $d_i = (d_{i,0},\dots,d_{i,n})$, Hdr$=(C_1,C_2,C_3)$, output $$k =e(d_{i,i} \cdot \prod_{j \in S \setminus \{i\}} d_{i,j}, C_1) \cdot e(d_{i,0}, C_2)$$
|
|
|
|
The correctness is the exact same as defined in Section \ref{sec:GentryWatersConst}.
|
|
\end{description}
|
|
|
|
As we desire a key homomorphic scheme, we define the aggregations like so; $PK_1 \mlarge{\oplus} PK_2 = PK_1PK_2$, $d_{1_i} \mlarge{\odot} d_{2_i} = (d_{1_{i,0}}, d_{2_{i,0}}, \dots, d_{1_{i,n}}, d_{2_{i,n}})$ and $k_1 \mlarge{\ocircle} k_2 = k_1k_2$. Finally we instantiate the \AHBE scheme:
|
|
% TODO: Fix it so that we are consistent with key of AHBE and user and BE
|
|
\begin{description}
|
|
\item[KeyGen$(i, n, N )$] Let the potential receivers be a set $\{1,\dots,N\}$. Let $n \leq N$ be the maximum number of recipients within a single broadcast. For simplicity, we assume that $n = N$. Generate an instance $\pi$ of a \KHBE scheme and let this be a system parameter. The KeyGen algorithm then does the following:
|
|
\begin{itemize}
|
|
\item For receiver $i \in [1,n]$, invoke the \textbf{ABSetup}, to generate a public/private key pair $(PK_i, SK_i) = e(g,g)^{\alpha_i}, g^{\alpha_i}$ for the \KHBE scheme..
|
|
\item Receiver $i$ runs \textbf{ABKeyGen} and obtains $d_i(j) \leftarrow \mathbf{ABKeyGen}(j,SK_i)$ for $i,l,j = 1,\dots,n$ where $d_i(j) = (d_{i,0,j}, \dots, d_{i,n,j})$ such that: \\
|
|
$$d_{i,0,j} = g^{-r_{i,j}},\quad d_{i,j,j} = g^{\alpha_i}h^{r_{i,j}}_{j,s_i}, \quad d_{i,l,j} = h^{r_{i,j}}_{l,s_i},$$ \\
|
|
For $r_{i,j} \in_R \mathbb{Z}_p$, $s_i \in_R \{0,1\}$. Receiver $i$'s private key is then $d_i(i)$. \\
|
|
\item The public key of the specific receiver $i$ in the \AHBE scheme is then: \\
|
|
$$PK_{\mathtt{AHBE}_i} = \{d_i(j) | 1 \leq i \neq j \leq n\} \cup \{PK_i\}$$ Where $PK_i$ came from the BSetup call.
|
|
\end{itemize}
|
|
\item[AHBEnc$(S, (PK_i)_S)$] Computes the header and key for a receiver set $S$ in the following way:
|
|
\begin{itemize}
|
|
\item Pick receiver set $S \subseteq [1,n]$
|
|
\item Compute the public key of the broadcast:
|
|
$$PK_{\mathtt{AHBE}} = \mlarge{\oplus}_{i \in S} PK_i = \prod_{i \in S} PK_i = e(g,g)^{\sum_{i \in S} \alpha_i}$$
|
|
Note that the $PK_i$'s used here are in fact the ones from the original \textbf{ABSetup} call, so it is contained within $PK_{\mathtt{AHBE}_i}$.
|
|
\item Invoke the underlying \KHBE encryption algorithm \textbf{BEnc}$(\cdot)$ in order to compute the header of the key $\hdr = \mathbf{ABEnc}(S, PK_{\mathtt{AHBE}}) = (C_1,C_2,C_3)$ for:
|
|
$$C_1 = g^t, \quad C_2 = (\prod_{i \in S}h_{i,0})^t,\quad C_3 = (\prod_{i \in S}h_{i,1})^t$$
|
|
and for the secret key:
|
|
$$k = PK_{\mathtt{AHBE}}^t = e(g,g)^{t \cdot \sum_{i \in S} \alpha_i}$$
|
|
for $t \in_R \mathbb{Z}_p$
|
|
and send $(S, \hdr)$ to the receiver set.
|
|
\end{itemize}
|
|
\item[AHBDec$(S, j, sk_j, \hdr, (PK_i)_S)$] Due to the underlying \KHBE scheme, the receiver $i \in S$ can compute a decryption key for the \AHBE public key $PK_{\mathtt{AHBE}}$ by computing:
|
|
\begin{align*}
|
|
d(i) &= d_i(i) \mlarge{\odot}\{\mlarge{\odot}_{j \in S}^{j \neq i} d_j(i)\} = \mlarge{\odot}_{j \in S} d_j(i) \\
|
|
&= (\prod_{j \in S} d_{j,0,i}, \dots, \prod_{j \in S} d_{j,n,i})
|
|
\end{align*}
|
|
As only user $\U_i$ knows $d_i(i)$ only she can compute $d(i)$. Due to the homomorphism of the \KHBE scheme, $d(i)$ is a valid decryption key for the public key $PK_{\mathtt{AHBE}}$, as long as $i \in S$. To perform this decryption, each user $\U_i$ for $i \in S$, invokes the \KHBE decryption algorithm \textbf{ABDec}$(\cdot)$;
|
|
$$k = \mathbf{ABDec}(S, i, d(i), \hdr, PK_{\mathtt{AHBE}}) $$
|
|
\end{description}
|
|
|
|
|
|
\subsection{Attempt at Reducing the \AHBE Instantion to BDHE-Problem}
|
|
Seeing that the reduction had some non-salvageable issues regarding the decryption keys of the target set $S^*$, we attempted to reduce their instantiation from Section \ref{sec:AHBEImpl} directly to the BDHE problem from Section \ref{sec:BDHE}, which the original scheme due to Gentry and Waters from Section \ref{sec:GentryWatersConst} was originally reduced to, to prove the Semi-Static security of it. We recall why the original reduction worked: The values $h_1, \dots, h_n$ are picked completely at random from the target group of the bilinear map, $\Gm_T$, which allowed the original reduction to sample $y_1, \dots, y_n$ and lift the generator of the group $\Gm$, $g$, to specific values of $y_i$, whenever we needed to know the discrete log of $h_i$, specifically when $i \in \tilde{S}$, i.e. the set of potential receivers, $h_i = g^{y_i}$. Particularly, we need to know the discrete log, as we will need to be able to create an ``encryption'' of the $Z$ given from the BDHE instantiation, such that the \hdr will correctly hide the $Z$, if this $Z$ is produced in a proper way and is not in fact random in $\Gm_T$.
|
|
Furthermore, for the rest of the users, $i \not\in \tilde{S}$, they generated the values of $h_i = g^{y_i + a^i}$ meaning that the adversary \adv{B} could in fact not compute the discrete log and would thus not have a chance of computing the header information, if the adversary \adv{A} decided to have this user $i$ within the challenge receiver set. Due to the Semi-Static security however, this is not something they have to worry of, as \adv{A} has already commited to $\tilde{S}$. The definition of the $h_i$ for $i \not\in \tilde{S}$, means that \adv{B} can properly answer the extraction queries for these users, as \adv{B} defines the values $r_i$ in such a way, that the exponents cancels out in $d_{i,i} = g^{\alpha}h^{r_i}_i$ and we do not have to bother trying to compute the discrete log of $g^\alpha$, specically the $a^{n+1}$ part of $\alpha = y_0 \cdot a^{n+1}$. The issues then arise, as all the $h_i$ values are required for the \AHBE scheme, essentially meaning we can not fake some and define some in a very specific way, as they are \emph{all} used for the different keys, regardless of the user $i$ being in the attack set $i \in \tilde{S}$, as all the users are using the same underlying \KHBE scheme. This results in the algorthim \adv{B} not being capable of answering extraction queries for any user i outside of the attack set, $i \not\in \tilde{S}$, as \adv{B} also has to generate all the $h$ values in such a way that he can compute the discrete log, which he can not accomplish, if \adv{B} also wants to be able to answer any extraction queries, as he then will neen something which cancels out the value $\alpha$, which has to be defined in a certain way, constrained by the value of $Z$.
|
|
|
|
We note, that it is not obvious if the value of all the different $\alpha$'s can be changed. For the \AHBE scheme, every single user $i$ has their own value of $\alpha_i$ and one might be able to hide something within these values, but it is doubtful, as they have to be generated from the exponentiations of $g$ which we are given through the BDHE problem, $\{g^{a^i} : i \in [0,n] \cup [n+2,2n]\}$ for the values to properly match the decision problem, whether $Z = e(g,g)^{a^{n+1} \cdot s}$. However, if this was successful, one could hide either an easily computable discrete log here or something which could cancel out with $r_i$, which would make it much easier to answer the extraction queries.
|
|
|
|
|
|
As such, we conclude that, if there is a reduction to be found from the \AHBE instantiation directly to the BDHE problem, then we were not to find this.
|
|
|
|
\section{Conclusion}
|
|
We have argued for the necessity of extensions to Public Key Cryptography, specifically those of Identity Based Encryption, Broadcast Encryption, Threshold Public Key Encryption and Ad-Hoc Broadcast Encryption. For each of these extensions, we have presented the model of the schemes, what is used to define the security of the schemes as well as an actual construction. By reading papers in which these schemes were originally presented, we have encountered multiple typos and errors which in the best case can be easily fixed thus making the proofs legitimate, but in the worst case can not be salvaged. One of these cases, which is the one we have primarily focused on, is that of Ad-Hoc Broadcast Encryption. In the main paper regarding this scheme, their reduction proving the security of their model does not hold, as they do not account for some missing decryption keys. We have attempted to fix this, by extending their definition of a Key Homomorphic Broadcast Encryption scheme, but by adding a property which would make the the original reduction work, we cause another security flaw, which is naturally not desirable. Furthermore, we attempt to prove their instantiation of an \AHBE scheme secure by imagining an adversary of their instantiation and then attempting to solve the BDHE-problem. This was however not succesful either and we conclude that this scheme and their transformation likely will not be salvageable.
|
|
|
|
|
|
\newpage\bibliographystyle{plain}
|
|
\nocite{*}
|
|
\bibliography{refs}
|
|
|
|
\newpage
|
|
% https://tex.stackexchange.com/questions/49643/making-appendix-for-thesis
|
|
|
|
\begin{appendices}
|
|
|
|
|
|
|
|
|
|
\includepdf[pages=1,pagecommand={\section{\texttt{IBE} Security Proof} \label{app:IBE-Sec} },width=\textwidth]{papers/IBESecProof.pdf}
|
|
|
|
\includepdf[pages=2-,pagecommand={},width=\textwidth]{papers/IBESecProof.pdf}
|
|
|
|
|
|
\includepdf[pages=1,pagecommand={\section{\texttt{DTPKE} Scheme} \label{app:DTPKE-Scheme}},width=\textwidth]{papers/DTPKE-Const.pdf}
|
|
|
|
\includepdf[pages=2-,pagecommand={},width=\textwidth]{papers/DTPKE-Const.pdf}
|
|
|
|
\end{appendices}
|
|
|
|
\end{document} |