Skip to main content
Engineering LibreTexts

15: Public-Key Encryption

  • Page ID
    86471
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    So far, the encryption schemes that we’ve seen are symmetric-key schemes. The same key is used to encrypt and decrypt. In this chapter we introduce public-key (sometimes called asymmetric) encryption schemes, which use different keys for encryption and decryption. The idea is that the encryption key can be made public, so that anyone can send an encryption to the owner of that key, even if the two users have never spoken before and have no shared secrets. The decryption key is private, so that only the designated owner can decrypt.

    We modify the syntax of an encryption scheme in the following way. A public-key encryption scheme consists of the following three algorithms:

    KeyGen: Outputs a pair \((p k, s k)\) where \(p k\) is a public key and \(s k\) is a private/secret key.

    Enc: Takes the public key \(p k\) and a plaintext \(m\) as input, and outputs a ciphertext \(c\).

    Dec: Takes the secret key \(s k\) and a ciphertext \(c\) as input, and outputs a plaintext \(m\).

    We modify the correctness condition similarly. A public-key encryption scheme satisfies correctness if, for all \(m \in \mathcal{M}\) and all \((p k, s k) \leftarrow \operatorname{KeyGen}\), we have \(\operatorname{Dec}(s k, \operatorname{Enc}(p k, m))=m\) (with probability 1 over the randomness of Enc).


    This page titled 15: Public-Key Encryption is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Mike Rosulek (Open Oregon State) .

    • Was this article helpful?