Identity Based Encryption

a form of public-key encryption, where sender can use public parameters of an entity to encrypt a message which can be decrypted only by a private key that is generated by a central authority.

then it's not that beneficial, right? you have to trust a central authority which can be adversary itself?

Third party entity called PRG (Private Key Generator) is responsible for creating public and private keys and assigning them to participants. PRG has a master private/public key pair which it uses to create new public/private key pair for any other participant. Any public entity can contact PRG to create a private key pair for itself and public key can be generated by combining master public key and self’s public ID.

so PRG is a single point of failure. PRG can't get compromised. also how does PRG at the time generating the private key authenticates identity of the entity?

It’s mentioned in the wikipedia article that IBE doesn’t concern with the need of security (integrity, authentication, confidentiality)

sequenceDiagram
actor Alice
participant PRG
actor Bob
note over PRG:1. generate a master <br/> private/public key pair
note over Alice:2. generate a private key
Alice->>PRG:3. Obtain master public key
Note over Alice:4. create public key from master public key
Alice->>PRG:5. send request to create a private key
PRG->>Alice:6. send private key for Alice
note over Alice:7. use Bob's ID to generate <br/> Bob's public key and encrypt message
Alice->>Bob:8. send ciphertext
Bob->>PRG:9. obtain master public key
Bob->>PRG:10.send request to create private key
PRG->>Bob:11. send private key for Bob
note over Bob:12. decrypt ciphertext for message m

Formal Protocol:

• $\text{Setup}(1^{\lambda })\to \mathcal{P},K_m$: takes security parameter and outputs public parameters (message space $\mathcal{M}$ and ciphertext space $\mathcal{C}$), and master key $K_m$.
• $\text{Extract}(\mathcal{P},K_m,\mathsf{ID}\in {\left\{0,1\right\}}^{\ast })\to d$: generates user’s private key. takes public parameter, master key, user public ID and outputs user private key $d$.
• $\text{Encrypt}(\mathcal{P},m\in \mathcal{M},\mathsf{ID})\to c\in \mathcal{C}$: encrypts a message $m$ to ciphertext $c$.
• $\text{Decrypt}(\mathcal{P},c\in \mathcal{C},d)\to m\in \mathcal{M}$: decrypts a message encrypted by user’s public key using private key as decryption key.

$$\begin{array}{c}\forall m\in \mathcal{M},\mathsf{ID}\in {\left\{0,1\right\}}^{\ast }:\mathsf{Decrypt}(\mathsf{Extract},\mathcal{P},\mathsf{Encrypt})=m\end{array}$$

Practical Protocols:

Boneh-Franklin scheme

Assume existence of hash function $H$ that can map element to $\mathbb{G}$.

• \textsf{Setup}(1^{\lambda})$$: sample a bilinear group \mathcal{P}:\mathbb{G},p,g,e$,$K_{m}=x$,anelement$s \xleftarrow{$}\mathbb{Z}_{p}$and$pk:(\mathcal{P},h=g^{x})$.
• $\text{Extract}(\mathcal{P},K_m,\text{ID})$: output $sk\text{(ID)}=H(\text{ID}{)}^x$
• $\text{Encrypt}(\mathcal{P},\text{ID},m)$: samples r\xleftarrow{\}\mathbb{Z}_{p}$,computes$u=g^{r}$and$v=m\times e(H(\textsf{ID}),u)$.$c=(u,v)$
• $\text{Decrypt}(\mathcal{P},c,{\text{sk}}_{\text{ID}})$: parse $(u,v)\leftarrow c$, computes $z=e(sk(\text{ID}),u)$, outputs $m=v/z$.

things that I am liking about IBE:

• in a network where key escrows are necessary, it’s perfect use case for setting up PKI.
• doesn’t require bootstrapping of public key infrastructure
• sender can control the properties of ciphertext. For example: can encode expiration in public key identifier like bob@hotmail.com || current-year, which PRG can use to deny private key generation for the receiver.
• PRG can control entities inside the system using expiration of keys. can produce static or ephemeral keys.

A corporation PKI is perfect use case for IBE.

Security

• PKG is a single point of failure, as if it gets compromised, all the keys being used in the system are compromised and adversary can spoof anyone.

Is standard public-key encryption (PKE) semantic security enough?

what’s the meaning of semantic security? if the notion of semantic security is satisfied even when encryption algorithm ignores identities and everyone has same secret key, then what is it use case because obviously, stricter algorithm will satisfy it as well, i.e. everyone having different secret keys?

Security of any public key encryption scheme is based on the notion of semantic security wherein an adversary $\mathcal{A}$ knowing the public key $\mathsf{pk}$ cannot tell the difference between $m_0,m_1$ for message of its own choice.

Security which is considered for IBE, will allow $\mathcal{A}$ to obtain secret keys of $\mathsf{I}{\mathsf{D}}_1,\mathsf{I}{\mathsf{D}}_2,\dots ,\mathsf{I}{\mathsf{D}}_{\mathsf{k}}$ and has to break semantic security for ${\mathsf{ID}}^{\ast }$. Let’s define an attack game between challenger and adversary $\mathcal{A}$:

• $\mathsf{Setup}(1^{\lambda })$: outputs $\mathcal{P}$ and $pk$ is given to $\mathcal{A}$.
• $\mathcal{A}$ samples secret key queries for any identity $i{d}_i$ and get $sk\leftarrow \mathsf{Extract}(\mathcal{P},\mathsf{ID},K_m)$
• $\mathcal{A}$ outputs challenge id $\mathsf{I}{\mathsf{D}}^{\ast }$ and messages $m_0,m_1$ and get $c\leftarrow \mathsf{Encrypt}(\mathcal{P},\mathsf{ID},m_b)$.
• $\mathcal{A}$ can sample additional secret key queries.
• $\mathcal{A}$ has to output $i$ for message $m_i$ that was chosen for encryption.

$\mathcal{A}$ wins if $m_i=m_b$ and $\mathcal{A}$ never queries for secret key of ${\mathsf{ID}}^{\ast }$. An IBE scheme is deemed secure if for any PPT adversary, $\mathsf{P}{\mathsf{r}}_{\mathcal{A}}(m_i=m_b)\ge \frac{1}{2}+\mathsf{negl}(\lambda )$

Let’s define other variations of IBE with varying security guarantees:

• Adaptively secure IBE: adversary can make series of queries to challenger, queries being key queries or encryption query. at the end of game, adversary has to output bit $\hat{b}\in \left\{0,1\right\}$.
• Private IBE (anonymous IBE): stricter assumption, an eavesdropper who has $mpk$ and $c\stackrel{R}{\leftarrow }E(mpk,id,m)$ cannot learn the identity of the target recipient.
  • the attack game is modified where in encryption query, adversary $\mathcal{A}$ sends: tuple: $({\mathsf{ID}}_0,m_0),({\mathsf{ID}}_1,m_1)$.
  • In the end, adversary has to output bit $\hat{b}\in \left\{0,1\right\}$ such that $c\leftarrow E(mpk,\mathsf{I}{\mathsf{D}}_{\mathsf{b}},m_b)$.
• Selectively secure IBE: weaker notion of IBE security where adversary needs to select challenge identity $\mathsf{ID}$ before key queries.
  • to model the security proof, we first select a hash function $H:{\mathsf{ID}}^{\prime }\to \mathsf{ID}$ which will be modelled as a random oracle.
  • choose an adversary $\mathcal{B}$ that will wrap around adversary $\mathcal{A}$ and play the attack game with the challenger.
  • $\mathcal{A}$ can at most make $Q_{RO}$ random oracle queries for $\mathsf{ID}$ and $Q_S$ key queries.
  • $\mathcal{B}$ chooses a \omega \xleftarrow{\}\left{1,\dots,Q_{RO}+1\right}$,andarandom$\mathsf{ID}{ch}\xleftarrow{$}\mathcal{ID}$.sends$\mathsf{ID}{ch}$tochallengeraschallengeidentityandgetsback$mpk$for$\mathcal{E}’_{id}$.
  • Now, $\mathcal{A}$ starts querying random oracle of ${\mathsf{ID}}_j$ and $\mathcal{B}$ maps each query to random identity in $\mathcal{I}\mathcal{D}$ and sends value of $H({\mathsf{ID}}_j^{\prime })$. for query number $\omega$, it maps that to ${\mathsf{ID}}_{ch}$ that it sent to challenger.
  • then, $\mathcal{A}$ starts key queries. for jth query, if $H({\mathsf{ID}}_j)\ne {\mathsf{ID}}_{ch}$ then $\mathcal{B}$ sends the key query to challenger and send response back to $\mathcal{A}$. if it’s equal to ${\mathsf{ID}}_{ch}$, then $\mathcal{B}$ can’t send to challenger and aborts with random bit.
  • $\mathcal{A}$ issues its single encryption query for $({\mathsf{ID}}^{\prime },m_0,m_1)$, $\mathcal{B}$ first checks if $H({\mathsf{ID}}^{\prime })={\mathsf{ID}}_{ch}$, if its not, sends the query to challenger, gets $c$ and send that to $\mathcal{A}$, for which $\mathcal{A}$ outputs the bit $\hat{b}$. if $H({\mathsf{ID}}^{\prime })={\mathsf{ID}}_{ch}$, then $\mathcal{B}$ aborts with random bit.

Some questions regarding the security of this scheme:

• why ${\mathcal{E}}_{id}(S,G,E,D)$ is modified to ${\mathcal{E}}_{id}^{\prime }(S,G^{\prime },E^{\prime },D)$?
• why use a hash function to map $H:\mathcal{I}\mathcal{D}\to \mathcal{I}{\mathcal{D}}^{\prime }$?

Security of Boneh-Franklin scheme

TODO

Resources

• CS355 Lecture 7: IBE
• CS355 Spring’14: IBE
• Boneh-Shoup book Section 15.6