In a broadcast encryption system, a sender

can encrypt a message so that only a specified set of recipients can decrypt. Such a system is

made up of three efficient algorithms $($G$,$ E$,$ D$)$: algorithm G is invoked as G$($N $)$ and outputs an

encryptor key ek$,$ and N keys k$1,...,$ kN $,$ one key for each recipient; algorithm E is invoked as

c $$ E$($ek$,$ m$,$ S$),$ where m is the message and S $\{1,...,$ N $\}$ is the intended set of recipients;

algorithm D is invoked as m $=$ D$($ki$,$ c$)$ for some $1<=$ i $<=$ N $,$ and correctly decrypts the given c

whenever i is in the set S$.$ More precisely, for all m and all subsets S of $\{1,...,$ N $\},$ we have that

D$($ki$,$ E$($ek$,$ m$,$ S$))=$ m for all i in S$.$

$1.$ A broadcast encryption scheme is secure if a set of colluding recipients B learns nothing about

plaintexts encrypted for subsets of $\{1,...,$ n$\}\backslash$ B$,$ namely plaintexts that are not intended for

the members of B$.$ Formalize a CPA$-$security style definition for broadcast encryption.

$2.$ Design a broadcast encryption scheme where the size of the ciphertext c grows sublinearly

in the size of S$.$ That is$,$ if S has N$/2$ members, then the size of the ciphertext should be

o$($N $).$ More precisely, describe the workings of algorithms G$,$ E$,$ D work and what are ek and

k$1,...,$ kN $.$ And present an informal security proof under the definition from part $(1).$

$2$