随机算法 — Lalande.

Randomized Algorithm.

A randomized algorithm uses a source of (pseudo) randomness as part of its logic.

Randomized algorithm, as opposed to deterministic algorithm, mapping the same input to several random outputs. The randomness is guaranteed by some random tapes implemented by TRNGs, PRGs, PRFs or PRPs.

Randomized algorithms are essential to build secure cryptographic primitives: in particular, Any CPA-secure encryption scheme must be randomized.

Chosen-plaintext attack (CPA): Adversary holds the encryption oracle $Enc_k(\cdot)$ , which means he is able to obtain any ciphertext $c$ for a desired message $m$ without knowing secret key $k$ .

For a deterministic encryption scheme, there is a trivial CPA adversary $\mathscr{A}$ : $\mathscr{A}$ ask $Enc_k(\cdot)$ to encrypt $m_0,m_1$ first and obtain $c_0=Enc_k(m_0), c_1=Enc_k(m_1)$ . Then when it gets challenge ciphertext $c$ , $\mathscr{A}$ simply compares $c$ to $c_0,c_1$ . If $c=c_0$ , output $0$ , and if $c=c_1$ , output $1$ .

Also we could see that, for public encryption scheme, EAV-security is equivalent to CPA-security since adversary knows public key $pk$ . (equivalent to hold the encryption oracle $Enc_{pk}(\cdot)$ )