Skip to main content
Engineering LibreTexts

5.3: Taking the Contrapositive Point-of-View

  • Page ID
  • \( \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}}\)

    We just proved the statement “if \(G\) is a secure PRG, then pOTP[\(G\)] has one-time secrecy,” but let’s also think about the contrapositive of that statement:

    If the pOTP[G] scheme is not one-time secret, then G is not a secure PRG.

    If the pOTP scheme is not secure, then there is some distinguisher ? that can distinguish the two \(\mathscr{L}_{\text{ots-}^{\ast}}\) libraries with better than negligible advantage. Knowing that such an \(?\) exists, can we indeed break the security of \(G\)?

    Imagine going through the sequence of hybrid libraries with this hypothetical ? as the calling program. We know that one of the steps of the proof must break down since ? successfully distinguishes between the endpoints of the hybrid sequence. Some of the steps of the proof were unconditional; for example, factoring out and inlining subroutines never has an effect on the calling program. These steps of the proof always hold; they are the steps where we write \(\mathscr{L}_\text{hyb-i} \equiv \mathscr{L}_{\text{hyb-(i + 1)}}\).

    The steps where we write \(\mathscr{L}_{\text{hyb-i}} ≋ \mathscr{L}_{\text{hyb-(i + 1)}}\) are conditional. In our proof, the steps \(\mathscr{L}_{\text{hyb-1}} ≋ \mathscr{L}_{\text{hyb-2}}\) and \(\mathscr{L}^{\text{OTP}}_{\text{ots-R}} ≋ \mathscr{L}_{\text{hyb-4}}\) relied on \(G\) being a secure PRG. So if a hypothetical ? was able to break the security of pOTP, then that same ? must also successfully distinguish between \(\mathscr{L}_{\text{hyb-1}}\) and \(\mathscr{L}_{\text{hyb-2}}\), or between \(\mathscr{L}_{\text{hyb-5}}\) and \(\mathscr{L}_{\text{hyb-6}}\) — the only conditional steps of the proof.

    Let’s examine the two cases:

    • Suppose the hypothetical ? successfully distinguishes between \(\mathscr{L}_{\text{hyb-1}}\) and \(\mathscr{L}_{\text{hyb-2}}\). Let’s recall what these libraries actually look like:Screen Shot 2019-03-02 at 5.22.04 PM.png
      Interestingly, these two libraries share a common component that is linked to either \(\mathscr{L}_{\text{prg-rea}}\) or \(\mathscr{L}_{\text{prg-rand}}\). (This is no coincidence!) Let’s call that common library \(\mathscr{L}^{\ast}\) and write
      Since ? successfully distinguishes between \(\mathscr{L}_{\text{hyb-1}}\) and \(\mathscr{L}_{\text{hyb-2}}\), the following advantage is non-negligible:

    \[\mid Pr[\mathscr{A}\diamondsuit\mathscr{L}^{\ast}\diamondsuit\mathscr{L}^G_{\text{prg-real}}\Rightarrow\space 1]\space\space\space\space Pr[\mathscr{A}\diamondsuit\mathscr{L}^{\ast}\diamondsuit\mathscr{L}^G_{\text{prg-rand}}\Rightarrow\space 1]\mid\nonumber\]

    But with a change of perspective, this means that \(? \diamondsuit \mathscr{L}^{\ast}\) is a calling program that successfully distinguishes \(\mathscr{L}^G_{\text{prg-rea}}\) from \(\mathscr{L}^G_{\text{prg-rand}}\). In other words, \(? \diamondsuit \mathscr{L}^{\ast}\) breaks the PRG security of G!

    • Suppose the hypothetical \(?\) only distinguishes \(\mathscr{L}_{\text{hyb-5}}\) from \(\mathscr{L}_{\text{hyb-6}}\). Going through the reasoning above, we will reach a similar conclusion but with a different \(\mathscr{L}^{\ast}\) than before (in fact, it will be mostly the same library but with \(m_L\) replaced with \(m_R\)).

    So you can think of our security proof as a very roundabout way of saying the following:

    If you give me an adversary/distinguisher ? that breaks the one-time secrecy of pOTP[G], then I can use it to build an adversary that breaks the PRG security of G. More specifically, G is guaranteed to be broken by (at least) one of the two distinguishers:\(^{1}\)

    Screen Shot 2019-03-02 at 5.37.26 PM.png

    In fact, this would be the “traditional” method for proving security that you might see in many other cryptography texts. You would suppose you are given an adversary ? breaking pOTP, then you would demonstrate why at least one of the adversaries given above breaks the PRG. Unfortunately, it is quite difficult to explain to students how one is supposed to come up with these PRG-adversaries in terms of the one-time-secrecy adversaries. For that reason, we will reason about proofs in the “if this is secure then that is secure” realm, rather than the contrapositive “if that is insecure then this is insecure.”

    2The statement is somewhat non-constructive, since we don’t know for sure which of the two distinguishers will be the one that actually works. But a way around this is to consider a single distinguisher that flips a coin and acts like the first one with probability 1/2 and acts like the second one with probability 1/2.

    5.3: Taking the Contrapositive Point-of-View is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Mike Rosulek.