Editing Probabilistic encryption (section)

== Examples ==

Example of probabilistic encryption using any trapdoor permutation:

* ''x'' - ''single bit'' plaintext
* ''f'' - [[trapdoor permutation]] (deterministic encryption algorithm)
* ''b'' - [[hard core predicate]] of ''f''
* ''r'' - random string

<math>
{\rm Enc}(x) = (f(r), x \oplus b(r))
</math>

<math>
{\rm Dec}(y, z) = b(f^{-1}(y)) \oplus z
</math>

This is inefficient because only a single bit is encrypted. In other words, the message expansion factor is equal to the public key size.

Example of probabilistic encryption in the random oracle model:

* ''x'' - plaintext
* ''f'' - [[trapdoor permutation]] (deterministic encryption algorithm)
* ''h'' - [[random oracle]] (typically implemented using a publicly specified [[cryptographic hash function|hash function]])
* ''r'' - random string

<math>
{\rm Enc}(x) = (f(r), x \oplus h(r))
</math>

<math>
{\rm Dec}(y, z) = h(f^{-1}(y)) \oplus z
</math>