Skip to main content
Engineering LibreTexts

2.4: How to Prove Security with The Hybrid Technique

  • 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 have seen an example of proving the security of a construction. To show that a construction is insecure, we demonstrate an attack. An attack means a counterexample to the definition of security. Since we define security in terms of two interchangeable libraries, an attack is a distinguisher (calling program) that behaves as differently as possible when linked to the two libraries.

    Below is an example of an insecure construction:

    Construction \(\PageIndex{1}\) :

    Screen Shot 2019-02-16 at 12.28.34 PM.png

    To encrypt a plaintext \(m\), the scheme simply rearranges its bits according to the permutation \(k\).

    Claim \(\PageIndex{1}\) :

    Construction \(\PageIndex{1}\) does not have one-time secrecy.


    Our goal is to construct a program ? so that \(Pr[?\diamondsuit \mathscr{L}^{\Sigma}_{ots-L}\Rightarrow 1]\) and \(Pr[?\diamondsuit \mathscr{L}^{\Sigma}_{ots-R}\Rightarrow 1]\) are different, where \(Sigma\) refers to Construction \(\PageIndex{1}\). There are probably many “reasons” why this construction is insecure, each of which leads to a different distinguisher ?. We need only demonstrate one such ?, and it’s generally a good habit to try to find one that makes the probabilities \(Pr[?\diamondsuit \mathscr{L}^{\Sigma}_{ots-L}\Rightarrow 1]\) and \(Pr[?\diamondsuit \mathscr{L}^{\Sigma}_{ots-R}\Rightarrow 1]\) as different as possible.

    One immediate observation about the construction is that it only rearranges bits of the plaintext, without modifying them. In particular, encryption preserves (leaks) the number of 0s and 1s in the plaintext. By counting the number of 0s and 1s in the ciphertext, we know exactly how many 0s and 1s were in the plaintext. Let’s try to leverage this observation to construct an actual distinguisher.

    Any distinguisher must use the interface of the \(\mathscr{L}_{ots-}^{\ast}\) libraries; in other words, we should expect the distinguisher to call the QUERY subroutine with some choice of \(m_L\) and \(m_R\), and then do something based on the answer that it gets. If we are the ones writing the distinguisher, we must specify how these arguments mL and mR are chosen. Following the observation above, we can choose \(m_L\) and \(m_R\) to have a different number of 0s and 1s. An extreme example (and why not be extreme?) would be to choose \(m_L = 0^{\lambda}\) and \(m_R = 1^{\lambda}\). By looking at the ciphertext, we can determine which of \(m_L\), \(m_R\) was encrypted, and hence which of the two libraries we are currently linked with.

    Putting it all together, we define the following distinguisher:

    \[\mathscr{A}\\c\space\leftarrow\space QUERY(0^{\lambda},1^{\lambda})\\\text{return}\space c\stackrel{?}{=}0^{\lambda}\nonumber\]

    Here is what it looks like when ? is linked to \(\mathscr{L}^{\Sigma}_{ots-L}\) (we have filled in the details of Construction \(\PageIndex{1}\) in \(\mathscr{L}^{\Sigma}_{ots-L}\)):

    Screen Shot 2019-02-16 at 12.39.52 PM.png

    We can see that \(m_L\) takes on the value \(0^{\lambda}\), so each bit of \(m_L\) is 0, and each bit of \(c\) is 0. Hence, the final output of ? is 1 (true). We have:

    \[Pr[? \diamondsuit\mathscr{L}^{\Sigma}_{ots-L} \Rightarrow 1] = 1.\nonumber\]

    Here is what it looks like when ? is linked to \(\mathscr{L}^{\Sigma}_{ots-R}\):

    Screen Shot 2019-02-16 at 12.42.23 PM.png

    We can see that each bit of \(m_R\), and hence each bit of \(c\), is 1. So ? will output 0 (false), giving:

    \[Pr[? \diamondsuit\mathscr{L}^{\Sigma}_{ots-R} \Rightarrow 1] = 0.\nonumber\]

    The two probabilities are different, demonstrating that ? behaves differently (in fact, as differently as possible) when linked to the two libraries. We conclude that Construction \(\PageIndex{1}\) does not satisfy the definition of one-time secrecy.

    This page titled 2.4: How to Prove Security with The Hybrid Technique 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?