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?


1 Answer 1


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]$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.