In the paper "Efficient Encryption from Random Quasi-Cyclic Codes" of Gaborit et al. p.14, I read "Encrypt$(pk=(G,Q,s),\mu,\theta)$: uses randomness $\theta$ to generate $\epsilon \xleftarrow{\\\$}V,r=(r_1,r_2) \xleftarrow{\\\$}V^2$...". Does it mean exactly "uses randomness $\theta$"? Where Can I find a descryption of a PKE in this terms?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
For an encryption scheme to satisfy the standard notion of security (IND-CPA), its encryption algorithm must be randomised. Therefore $\textsf{Encrypt}$ has access to random coins, denoted here by $\theta$. It is usually implicit in the syntax of $\textsf{Encrypt}$ $$c\leftarrow\textsf{Encrypt}(pk,m),$$ but it can be made explicit as $$c=\textsf{Encrypt}(pk,m;\theta).$$
For example, the encryption algorithm in El Gamal (which is IND-CPA secure under the DDH assumption) with public key $pk=(G,g,h,q)$ and message $m\in G$ can be described as $$(c_1=g^r,c_2=h^r\cdot m)=\mathsf{Encrypt}(pk,m;\theta),$$ where the random coin $\theta$ (interpreted as a string) is used to sample $r\in[1,q-1]$.