Proxy re-encryption

A proxy re-encryption (PRE) scheme is a multi-user public-key encryption scheme with re-encryption keys: a proxy holding a re-encryption key from user to user converts a ciphertext under into a ciphertext of the same message under , and learns nothing about the message — BBS98.

Syntax

A PRE scheme is a tuple of efficient algorithms with message space and ciphertext space ; every algorithm after takes as an implicit input:

  • , a randomized algorithm outputting public parameters shared by all users,
  • , a randomized algorithm run by each user,
  • , a (possibly randomized) algorithm run by user , outputting a re-encryption key from to ; in an interactive scheme it also takes ,
  • , a randomized algorithm which takes a public key and a message , outputting ,
  • , a (possibly randomized) algorithm run by the proxy, outputting a ciphertext under or ,
  • , a deterministic algorithm outputting or .

TODO: require here that every scheme on the page be -correct for a negligible function , with a message space containing two distinct messages of equal length, as PKE § Syntax does: as written, a scheme whose ignores its message meets the CPA and CCA games below.

Properties

Correctness

A PRE scheme is -correct if for all and ,

over , independent , (also given in an interactive scheme), and the randomness of and . When , is perfectly correct.

CPA security

The adversary creates users adaptively, each either uncorrupted, in which case it receives the public key, or corrupted, in which case it receives the key pair. It obtains re-encryption keys between any two users except between an uncorrupted and a corrupted one, and must distinguish encryptions of and under an uncorrupted key of its choice. The game adapts the bidirectional PRE-CCA game of CH07 to the syntax above, without its re-encryption and decryption oracles.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{pre\text{-}cpa}}_{\mathsf{PRE},\calA}(\secpar)$}
\begin{algorithmic}
\State $\pp \gets \Setup(1^\secpar)$; $b \getsr \bits$; $n \gets 0$; $\mathit{Hon} \gets \{\}$; $\mathit{Cor} \gets \{\}$
\State $(i^*, m_0, m_1, \stA) \gets \calA^{\calO_{\mathrm{key}}, \calO_{\mathrm{rk}}}(1^\secpar, \pp)$
\Comment{$i^* \in \mathit{Hon}$; $m_0, m_1 \in \calM$ and $|m_0| = |m_1|$}
\State $c^* \gets \Enc(\pk_{i^*}, m_b)$
\State $b' \gets \calA^{\calO_{\mathrm{key}}, \calO_{\mathrm{rk}}}(c^*, \stA)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}
\begin{algorithm}
\algname{Oracle}
\caption{$\calO_{\mathrm{key}}(\beta)$}
\begin{algorithmic}
\State $n \gets n + 1$; $(\sk_n, \pk_n) \gets \KeyGen(\pp)$
\If{$\beta = 1$}
\State $\mathit{Cor} \gets \mathit{Cor} \cup \{n\}$
\Return $(\sk_n, \pk_n)$
\EndIf
\State $\mathit{Hon} \gets \mathit{Hon} \cup \{n\}$
\Return $\pk_n$
\end{algorithmic}
\end{algorithm}
\begin{algorithm}
\algname{Oracle}
\caption{$\calO_{\mathrm{rk}}(i, j)$}
\begin{algorithmic}
\If{$\{i, j\} \not\subseteq \mathit{Hon} \wedge \{i, j\} \not\subseteq \mathit{Cor}$}
\Return $\bot$
\Comment{only keys between two existing users that are both uncorrupted or both corrupted}
\EndIf
\Return $\mathsf{ReKeyGen}(\sk_i, \pk_j)$
\end{algorithmic}
\end{algorithm}

For an interactive scheme also passes . A re-encryption key from an uncorrupted user to a corrupted one would let re-encrypt , directly or along a chain of keys between uncorrupted users, to a key it holds; in a bidirectional scheme a key in the other direction does the same. For a non-interactive scheme, computes keys from a corrupted user itself, so refusing them costs it nothing.

A PRE scheme is CPA-secure if for all admissible efficient ,

is negligible.

Variations

Unidirectional and bidirectional

A scheme is bidirectional if is efficiently computable from , and unidirectional otherwise. The scheme of BBS98 is bidirectional and interactive (DDH ⇒ PRE (Blaze–Bleumer–Strauss scheme)). AFGH05 give unidirectional, non-interactive schemes from bilinear maps.

Single-hop and multi-hop

A scheme is multi-hop if a re-encrypted ciphertext can be re-encrypted again, correctness holding along every chain of re-encryption keys, and single-hop if correctness is required for one re-encryption only. The schemes of AFGH05 are single-hop; those of BBS98 and CH07 are multi-hop.

Chosen-ciphertext security

CH07 define CCA security for bidirectional schemes by adding to the CPA game a re-encryption oracle, which re-encrypts a given ciphertext from one given user to another, and a decryption oracle. After the challenge, the decryption oracle refuses and the ciphertexts CH07 call its derivatives, which include its re-encryptions, and the re-encryption oracle refuses to re-encrypt a derivative from an uncorrupted to a corrupted user — CH07. Without the first restriction would decrypt through the decryption oracle, directly or after re-encrypting it to an uncorrupted user; without the second it would re-encrypt to a corrupted user and decrypt it with that user’s key. CH07 also give simulation-based definitions that guarantee universally composable security — CH07. A CPA adversary is a CCA adversary that queries neither oracle, so every CCA-secure scheme is CPA-secure (CCA-secure PRE ⇒ PRE) — folklore.

Collusion resistance

A proxy colluding with a delegatee holds and . AFGH05 require that such a coalition cannot compute . The scheme of BBS98 does not meet this requirement: there in — AFGH05.

Other results

Participates in

Builds on Proxy re-encryption

Produces Proxy re-encryption