{"id":352195,"date":"2024-05-20T22:03:56","date_gmt":"2024-05-20T22:03:56","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=352195"},"modified":"-0001-11-30T00:00:00","modified_gmt":"2024-05-20T22:03:56","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=352195","title":{"rendered":"Pairing-based identification protocols compatible with instant digital signature mode<\/span>"},"content":{"rendered":"
<\/div>\n
\n
\n
\n
\n

In our previous post<\/u><\/a>, we presented a modified Schnorr protocol compatible with the Instant Digital Signature (IDS) mode and also announced the design of other protocols with this feature. In this post we describe such protocols based on the pairing function.<\/p>\n

Introduction<\/strong><\/p>\n

The following text is dedicated to the description of two digital signature (DS) schemes based on the pairing function (Appendix A<\/u><\/a>). These schemes are then transformed into IDS-compatible identification protocols. We specified and investigated the problem of impersonation, that is, the substitution of one party involved in protocol, with another one. The achieved result consists in the design and analysis of a new IDS-compatible identification protocol, with impersonation presumably impossible for it.<\/p>\n

We will use the abbreviation v.s.p. to denote a vanishingly small probability. This means that for some \"\\alpha\\in\\mathbb{F}_m\" and \"\\beta\" distributed uniformly and independently on the interval \"(0,m-1],\" otherwise \"{\\beta\\in_R\\! \"{\\Pr[\\alpha=\\beta]=m^{-1}}\" and for large \"m\" this probability is vanishingly small. For example, \"\\Pr[\\alpha=\\beta]\\sim for \"m\\sim A similar argument applies to \"\\Pr[g^{\\alpha}=g^{\\beta}],\" where \"g\" is a generator of \"\\mathbb{G}_3\" (Appendix A<\/u><\/a>).<\/p>\n

When describing DS schemes and identification protocols, we will proceed from the assumption that there is a pair of linked keys \"\\{\\mathbf{x},\\mathsf{P}=[\\mathbf{x}]\\mathsf{G}_1\\},\" where \"\\mathbf{x}\" is a secret key, \"{\\mathbf{x}\\in_R\\!(0,m-1]},\" and \"\\mathsf{P}\" is a public one for which a certificate \"\\{D,\\mathsf{P}, is issued. In this certificate, \"D\" is the personal data of the owner of \"\\mathsf{P},\" \"\\Im_{\\rm{T}}\" is the DS of the trusted party \"\\rm{T}\" (the certification authority responsible for issuing and maintaining certificates).<\/p>\n

Let’s call the functions of signing and verifying the digital signature as \"{\\rm{Sign}}(\\cdot,\\cdot)\" and \"{\\rm{Verify}}(\\cdot,\\cdot,\\cdot),\" respectively. Let’s denote the cryptographic hash function by \"\\hslash(\\cdot)\" (Appendix B<\/u><\/a>). Then \"\\Im_{\\rm{T}}\\Leftarrow{\\rm{Sign}}(\\hslash(\\mathsf{P}||D), where \"\\rm{S}_{\\rm{T}}\" is the secret key of the trusted party \"\\rm{T},\" consigned for signing.<\/p>\n

Before use, \"\\mathsf{P}\" is checked for authenticity, integrity, and relevance. The latter task is done by checking a list of revoked certificates. \"\\mathfrak{B}\\Leftarrow{\\rm{Verify}}(\\hslash(\\mathsf{P}||D), is computed, where \"\\rm{P}_{\\rm{T}}\" is the public key of trusted party \"\\rm{T}.\" If \"\\Im_{\\rm{T}}\" is valid, then the boolean variable \"\\mathfrak{B}=True\" and this means integrity, authenticity of \"\\mathsf{P}\" and \"D,\" otherwise \"\\mathfrak{B}=False.\" The trusted party \"T\" can use any DS scheme, for example, one of those described below.\u00a0<\/p>\n

For the sake of simplicity, let’s assume that different DS schemes and identification protocols use the same public key \"\\mathsf{P}.\"<\/p>\n

It should be noted that most of the known DS schemes use simple equations. This is important, because this simplifies their understanding and analysis. We will be guided by the same \"\\textit{modus when design identification protocols.<\/p>\n

DS schemes based on pairing<\/strong><\/p>\n

Hereinafter let’s call the one who sign the message \"{M\\in\\{0,1\\}^*}\" as the \"\\textit{witness}.\" Below there are descriptions of two DS schemes based on pairing (Appendix A<\/u><\/a>).<\/p>\n

In the DS scheme [Zhang_Safavi-Naini_Susilo_2004] for a given message \"M,\" the witness performs the following actions:<\/p>\n

    \n
  1. \n

    Computes \"\\phi=\\hslash(M).\"<\/p>\n<\/li>\n

  2. \n

    Generates the signature \"\\mathsf{S}=[\\frac{1}{\\phi+\\mathbf{x}\\pmod<\/p>\n<\/li>\n<\/ol>\n

    Let there be some signature \"\\mathsf{S}'=[\\psi']\\mathsf{G}_1\" and a message \"M\u2032.\" The verifier performs the following actions:<\/p>\n

      \n
    1. \n

      Computes \"\\phi'=\\hslash(M').\"<\/p>\n<\/li>\n

    2. \n

      Checks the authenticity, integrity and relevance of \"\\mathsf{P},\" if the relevance is not confirmed or \"\\mathfrak{B}=False,\" then it completes the verification of the DS.<\/p>\n<\/li>\n

    3. \n

      Computes \"g'=e_m([\\phi']\\mathsf{G}_1+<\/p>\n<\/li>\n

    4. \n

      Checks \"g'\\stackrel{?}{=}e_m(\\mathsf{G}_1,<\/p>\n<\/li>\n<\/ol>\n

      Then \"g'=g\" if \"(\\psi'=\\psi)\\land(\\phi'=\\phi)\\Rightarrow If \"(\\psi'\\neq\\psi)\\lor(\\phi'\\neq\\phi)\" then \"g'=g\" with v.s.p.<\/p>\n

      It is clear that \"g=e_m(\\mathsf{G}_1, is computed only once and stored in the local long-term memory. Authenticity and integrity of \"g\" needs to be guaranteed. For example, it can be stored in secure memory along with the secret key \"\\mathbf{x}.\"<\/p>\n

      Let’s look at another DS scheme from [Boneh_Shacham_Lynn_2004]. There is a given hash function \"H:\\{0,1\\}^*\\mapsto\\mathbb{G}_1\"\u00a0 (Appendix B<\/u><\/a>). The witness performs the following steps:<\/p>\n

        \n
      1. \n

        Computes \"\\mathsf{Q}=H(M)=[\\upsilon]\\mathsf{G}_1.\"<\/p>\n<\/li>\n

      2. \n

        Generates the signature \"\\mathsf{S}=[\\mathbf{x}]\\mathsf{Q}=[\\mathbf{x}\\upsilon\\pmod<\/p>\n<\/li>\n<\/ol>\n

        There is a message \"M\u2032\" and signature \"\\mathsf{S}'.\" The verifier does the following steps:<\/p>\n

          \n
        1. \n

          Computes \"\\mathsf{Q}'=H(M').\"<\/p>\n<\/li>\n

        2. \n

          Checks the authenticity, integrity and relevance of \"\\mathsf{P},\" if the relevance is not confirmed or \"\\mathfrak{B}=False,\" then it completes the verification of the DS.<\/p>\n<\/li>\n

        3. \n

          Checks \"e_m(\\mathsf{P},\\mathsf{Q}')\\stackrel{?}{=}e_m(\\mathsf{G}_1,\\mathsf{S}').\"<\/p>\n<\/li>\n<\/ol>\n

          If \"\\mathsf{Q}'=\\mathsf{Q}=[\\upsilon]\\mathsf{G}_1\" and \"\\mathsf{S}'=\\mathsf{S}=[\\mathbf{x}\\upsilon\\pmod then, due to the bilinearity, \"e_m(\\mathsf{P},\\mathsf{Q}')=e_m([\\mathbf{x}]\\mathsf{G}_1, If \"\\mathsf{Q}'\\neq\\mathsf{Q}\" and\/or \"\\mathsf{S}'\\neq\\mathsf{S},\" then \"e_m(\\mathsf{P},\\mathsf{Q}')= with v.s.p.<\/p>\n

          Both above-mentioned DS schemes use the \"e_m(\\cdot, pairing function, but differ in computational complexity of check. In the [Zhang_Safavi-Naini_Susilo_2004] scheme, when checking the DS, only one pairing is computed, while in [Boneh_Shacham_Lynn_2004] it is necessary to compute two pairings.<\/p>\n

          IDS-compatible identification protocols based on pairing<\/strong><\/p>\n

          According to the Fiat-Shamir heuristic [Fiat_Shamir_1987], each DS scheme has its own identification protocol. However, we will be interested in IDS-compatible versions of such protocols.<\/p>\n

          Below there is a description of the IDS-compatible identification protocol for the DS scheme from [Zhang_Safavi-Naini_Susilo_2004].<\/p>\n

          Protocol 1<\/strong><\/p>\n

          Protocol messages.<\/em><\/p>\n

            \n
          1. \n

            \"P<\/p>\n<\/li>\n

          2. \n

            \"P<\/p>\n<\/li>\n

          3. \n

            \"P<\/p>\n<\/li>\n<\/ol>\n

            Actions of the parties.<\/em><\/p>\n

            \"P\" proves to \"V\" that it owns (knows) \"\\mathbf{x}.\" To do this, the following steps are performed:<\/p>\n

              \n
            1. \n

              \"P\" selects \"{\\upsilon\\in_R\\!(0,m-1]}\" \"(\\textit{commitment}),\" computes \"\\mathsf{S}=[\\upsilon]\\mathsf{G}_1\" \"(\\textit{witness}),\" checks \"\\mathsf{S}\\stackrel{?}\\neq\\infty.\" If \"\\mathsf{S}=\\infty\" then selects a new \"\\upsilon,\" re-executes the necessary computations and checks.<\/p>\n<\/li>\n

            2. \n

              \"V\" reads the current certificate \"\\{D,\\mathsf{P}, and checks the DS of the trusted party \"\\rm{T}.\" If \"\\mathfrak{B}=False\" then the session ends. If \"\\mathfrak{B}=True\" then it chooses \"{\\phi\\in_R\\!(0, and computes \"\\mathsf{T}=[\\phi]\\mathsf{G}_1\" \"(\\textit{challenge}).\" If \"\\mathsf{T}=\\infty,\" then it chooses a new \"\\phi\" and re-executes the necessary computations and checks.<\/p>\n<\/li>\n

            3. \n

              \"P\" checks \"\\mathsf{T}\\stackrel{?}\\neq\\infty,\" if it is true, it computes \"\\mathsf{N}=[(\\upsilon+\\mathbf{x}\\pmod \"(\\textit{response})\" otherwise the session ends.<\/p>\n<\/li>\n

            4. \n

              \"V\" computes \"g_2=e_m([\\phi^{-1}]\\mathsf{S}+[\\phi^{-1}]\\mathsf{P}, Then it checks \"g_2\\stackrel{?}{=}g.\" If equal, then the proof is accepted, and rejected otherwise.<\/p>\n<\/li>\n<\/ol>\n

              Now let’s see what IDS-compatible protocol can be proposed for the DS scheme from [Boneh_Shacham_Lynn_2004].<\/p>\n

              Protocol 2<\/strong><\/p>\n

              Protocol messages.<\/em><\/p>\n

                \n
              1. \n

                \"P<\/p>\n<\/li>\n

              2. \n

                \"P<\/p>\n<\/li>\n

              3. \n

                \"P<\/p>\n<\/li>\n<\/ol>\n

                Actions of the parties.<\/em><\/p>\n

                \"P\" proves to \"V\" that it owns (knows) \"\\mathbf{x}.\" To do this, the following steps are performed:<\/p>\n

                  \n
                1. \n

                  As in Protocol 1<\/strong>.<\/p>\n<\/li>\n

                2. \n

                  As in Protocol 1<\/strong>.<\/p>\n<\/li>\n

                3. \n

                  \"P\" checks \"{\\mathsf{T}\\stackrel{?}\\neq\\infty},\" if it is true, it computes \"{\\mathsf{N}=[\\upsilon\\mathbf{x}\\pmod \"(\\textit{response}),\" otherwise the session ends.<\/p>\n<\/li>\n

                4. \n

                  \"V\" computes \"g_2=e_m([\\phi]\\mathsf{S}, Then it checks \"g_2\\stackrel{?}{=}e_m(\\mathsf{N}, If equal, then the proof is accepted, and rejected otherwise.<\/p>\n<\/li>\n<\/ol>\n

                  For Protocols 1<\/strong> and 2<\/strong>, in case of successful completion of the identification stage, the parties independently compute a shared session secret key in accordance with the following rules:<\/p>\n

                    \n
                  1. \n

                    \"P\" computes \"\\mathsf{A}=[\\upsilon]\\mathsf{T}=[\\upsilon\\phi\\pmod<\/p>\n<\/li>\n

                  2. \n

                    \"V\" computes \"\\mathsf{B}=[\\phi]\\mathsf{S}=[\\phi\\upsilon\\pmod<\/p>\n<\/li>\n<\/ol>\n

                    Obviously, \"\\mathsf{A}=\\mathsf{B}\" due to commutativity.<\/p>\n

                    Impersonation of the verifier<\/strong><\/p>\n

                    An active attack includes a set of measures taken to replace the information that the parties exchange with each other during the identification protocol. Protocol 1<\/strong> and Protocol<\/strong> 2<\/strong> are reliable provided that the probability of an active attack is negligible. For example, when data exchange between \"P\" and \"V\" is carried out using NFC (Near-Field Communication) technology or similar.<\/p>\n

                    If the parties interact through other insecure communication channels, including the Internet, then an active attack aimed at impersonating the verifier is possible. Let’s call the bogus verifier as \"V'.\" The attacker tries to replace \"V\" with \"V'.\"<\/p>\n

                    Let’s choose Protocol 2<\/strong> as the object of attack. Using the interception and blocking technique, the attacker is able to impose \"\\mathsf{T}'=[\\phi']\\mathsf{G}_1\" instead of \"\\mathsf{T},\" such that \"\\phi'=\\phi\" with v.s.p. The \"P\" computes \"\\textit{response}\" as \"\\mathsf{N}'=[\\upsilon\\mathbf{x}\\pmod<\/p>\n

                    \"V'\" computes \"\\hat{g}_2=e_m([\\phi']\\mathsf{S}, and checks \"\\hat{g}_2\\stackrel{?}{=}e_m(\\mathsf{N}', \"P\" computes \"{\\mathsf{A}'=[\\upsilon]\\mathsf{T}'=[\\upsilon\\phi'\\pmod and \"V'\" computes \"\\mathsf{B}'=[\\phi']\\mathsf{S}=[\\phi'\\upsilon\\pmod It is obvious that \"\\mathsf{A}'=\\mathsf{B}'.\"<\/p>\n

                    The above mentioned reasoning is equally valid for Protocol 1<\/strong>. In addition, the attack is also applicable to modified Schnorr protocol<\/u><\/a>.<\/p>\n

                    In the next section, we will demonstrate a protocol where impersonation is not presumably possible.<\/p>\n

                    Protocol resistant to impersonation<\/strong><\/p>\n

                    Let’s assume that, for \"{\\mathbf{x}, \"P\" and \"V\" own key pairs \"\\{\\mathbf{x}, and \"\\{\\mathbf{y},\\mathsf{P}_V=[\\mathbf{y}]\\mathsf{ respectively. There are certificates \"\\{D_P,\\mathsf{P}_P, and \"\\{D_V,\\mathsf{P}_V, issued for \"\\mathsf{P}_P\" and \"\\mathsf{P}_V.\"<\/p>\n

                    Let us consider an IDS-compatible and at the same time impersonation-resistant protocol.<\/p>\n

                    Protocol 3<\/strong><\/p>\n

                    Protocol messages<\/em>.<\/p>\n

                      \n
                    1. \n

                      \"P<\/p>\n<\/li>\n

                    2. \n

                      \"P<\/p>\n<\/li>\n

                    3. \n

                      \"P<\/p>\n<\/li>\n<\/ol>\n

                      Actions of the parties<\/em>.<\/p>\n

                      \"P\" proves to \"V\" that it owns (knows) \"\\mathbf{x}.\" To do this, the following steps are performed:<\/p>\n

                        \n
                      1. \n

                        \"P\" reads the current certificate \"\\{D_V,\\mathsf{P}_V, and verifies the DS of the trusted party \"\\rm{T}.\" If \"\\mathfrak{B}=False\" then the session ends. If \"\\mathfrak{B}=True\" then it selects \"{\\upsilon\\in_R\\!(0,m-1]}\" \"(\\textit{commitment}),\" computes \"\\mathsf{S}=[\\upsilon] \"(\\textit{witness}),\" checks \"{\\mathsf{S}\\stackrel{?}\\neq If \"\\mathsf{S}=\\infty,\" then it chooses a new \"\\upsilon\" and re-executes the necessary computations and checks.<\/p>\n<\/li>\n

                      2. \n

                        \"V\" reads the current certificate \"\\{D_P,\\mathsf{P}_P, and verifies the DS of the trusted party \"\\rm{T}.\" If \"\\mathfrak{B}=False\" then the session ends. If \"\\mathfrak{B}=True\" then it chooses \"{\\phi\\in_R\\!(0, and computes \"\\mathsf{T}=[\\phi]\\mathsf{P}_P= \"(\\textit{challenge}).\" If \"\\mathsf{T}=\\infty,\" then it chooses a new \"\\phi\" and re-executes the necessary computations and checks.<\/p>\n<\/li>\n

                      3. \n

                        \"P\" checks \"\\mathsf{T}\\stackrel{?}\\neq\\infty.\" if it is true, it computes \"\\mathsf{N}=[\\upsilon^{-1}\\mathbf{x}^ \"(\\textit{response}),\" otherwise the session ends.<\/p>\n<\/li>\n

                      4. \n

                        \"V\" computes \"g_2=e_m(\\mathsf{S}, Then it checks \"g_2\\stackrel{?}{=}e_m([\\phi]\\mathsf{P}_V, If equal, then the proof is accepted, and rejected otherwise.<\/p>\n<\/li>\n<\/ol>\n

                        If \"V\" accepted the proof provided by \"P,\" then the parties independently compute a shared session secret:<\/p>\n

                          \n
                        1. \n

                          \"P\" computes \"\\mathsf{A}=[\\upsilon\\mathbf{x}^{-1}\\pmod<\/p>\n<\/li>\n

                        2. \n

                          \"V\" computes\u00a0 \"\\mathsf{B}=[\\phi\\mathbf{y}^{-1}\\pmod<\/p>\n<\/li>\n<\/ol>\n

                          It is clear that \"\\mathsf{A}=\\mathsf{B}\" due to commutativity.<\/p>\n

                          Preliminary analysis<\/strong><\/p>\n

                          Let bogus verifier \"V'\" owns the key pair \"\\{\\mathbf{\\acute{y}},\\mathsf{P}_{V'}=[\\mathbf{\\acute{y}}]\\mathsf{G} \"\\mathbf{\\acute{y}}=\\mathbf{y}\" with v.s.p.<\/p>\n

                          We restrict ourselves to the analysis of Protocol 3<\/strong>, in which it is necessary to impose \"\\mathsf{S}'=[\\upsilon]\\mathsf{P}_{V'}\" instead of \"\\mathsf{S}\" in order to impersonate the verifier (replace \"V\" with \"V'\"). However, the attacker does not know the \"\\upsilon\" ephemeris. To reveal \"\\upsilon,\" one need to solve an ECDLP\/DLP given\u00a0 \"\\mathsf{S}\" or \"e_m(\\mathsf{S}, <\/p>\n

                          Another strategy is to solve ECDLP\/DLP given \"\\mathsf{P}_V\" or \"e_m(\\mathsf{P}_V, Then \"{\\mathsf{S}'=[\\mathbf{y}^{-1} The relationship between ECDLP and DLP is explained in Appendix A<\/u><\/a>.<\/p>\n

                          The attacker has access to \"\\mathsf{P}_P\" and is able to impose \"\\mathsf{T}'=[\\phi']\\mathsf{P}_P\" instead of \"\\mathsf{T}\" and \"\\mathsf{S}'=[\\upsilon']\\mathsf{P}_{V'}\" instead of \"\\mathsf while \"\\phi'=\\phi\" and \"\\upsilon'=\\upsilon\" being with v.s.p. \"P\" computes \"\\textit{response}\" as \"\\mathsf{N}'=[\\upsilon^{-1}\\mathbf{x}^{-1}\\pmod<\/p>\n

                          \"V'\" computes \"\\hat{g}_2=e_m(\\mathsf{S}', Obviously, \"\\hat{g}_2=e_m([\\phi']\\mathsf{P}_{V'}, with v.s.p. In addition, the attacker can choose arbitrary \"\\upsilon'\" and \"\\phi'.\" Let \"\\upsilon'=\\phi'=1\" but \"g^{\\mathbf{\\acute{y}}\\upsilon^{-1}\\pmod with v.s.p.<\/p>\n

                          It is easy to show that replacement of \"\\mathsf{T}\" does not lead to the desired result. To do this, when computing \"\\hat{g}_2,\" we set \"\\mathsf{N}'=\\mathsf{N}.\" However, \"g^{\\upsilon'\\mathbf{\\acute{y}}\\phi\\upsilon^{-1}\\pmod with v.s.p.<\/p>\n

                          If we assume that the attacker imposes \"\\mathsf{T}'\" instead of \"\\mathsf{T},\" but there is no replacement of \"\\mathsf{S},\" then the impersonation of \"V\" is also impossible, since \"g^{\\upsilon'\\mathbf{\\acute{y}}\\phi\\upsilon^{-1}\\pmod with v.s.p.<\/p>\n

                          Note that \"\\mathsf{A}'=[\\upsilon\\mathbf{x}^{-1}\\pmod \"\\mathsf{B}'=[\\phi'\\mathbf{\\acute{y}}^{-1}\\pmod or \"\\mathsf{B}'=[\\phi'\\mathbf{\\acute{y}}^{- Therefore, \"\\mathsf{A}'=\\mathsf{B}'\" with v.s.p.<\/p>\n

                          When computing \"\\mathsf{T}',\" replacing \"\\mathsf{P}_P\" with some \"\\mathsf{P}_{P'}\" seems to be counterproductive. If such a replacement is allowed, then \"\\mathsf{P}_{P'}=[\\mathbf{\\acute{x}}]\\mathsf{G}_1,\" \"\\mathbf{\\acute{x}}=\\mathbf{x}\" with v.s.p., there will be a discrepancy in \"\\mathbf{x}.\" Let \"\\mathsf{S},\" \"\\mathsf{N}'=[\\upsilon^{-1}\\mathbf{x}^{-1}\\phi'\\mathbf{\\acute{x}}\\pmod Then \"g^{\\mathbf{y}\\mathbf{x}^{-1}\\phi'\\mathbf{\\acute{x}}\\pmod with v.s.p.<\/p>\n

                          The amount of information transmitted<\/strong><\/p>\n

                          If compact representation<\/u><\/a> is used, then one needs to transfer \"3(\\lceil\\log_{2}{p}\\rceil+1)\" bits in Protocol<\/strong> 1<\/strong> and Protocol 2<\/strong> in order to deliver \"\\mathsf{S},\" \"\\mathsf{T},\" and \"\\mathsf{N}\" in total.<\/p>\n

                          In Protocol<\/strong> 3<\/strong>, \"P\" must inform \"V\" of the serial number of \"\\{D_P,\\mathsf{P}_P, Let’s suppose that \"\\ell\" bits need to be allocated to store this number in long-term memory. Then one needs to send \"3(\\lceil\\log_{2}{p}\\rceil+1)+\\ell\" bits in order to deliver \"\\mathsf{S},\" \"\\mathsf{T},\" and \"\\mathsf{N}\" in total.<\/p>\n

                          Other overheads are allowed. The amount of information transmitted satisfies the asymptotic estimate \"O(\\log_{2}{p}).\"<\/p>\n

                          Computational complexity<\/strong><\/p>\n

                          In addition to the scalar multiplication, whose computation features are described here<\/u><\/a>, in the Protocol 3<\/strong> parties \"P\" and \"V\" compute \"\\{\\upsilon^{-1},\" \"\\mathbf{x}^{-1}\\}\" and \"\\mathbf{y}^{-1},\" respectively.<\/p>\n

                          In this case, \"\\mathbf{x}^{-1}\" and \"\\mathbf{y}^{-1}\" are computed only once. \"P\" and \"V\" store the computed values in secured long-term memory. As a result, \"P\" and \"V\" store \"\\{\\mathbf{x}, and \"\\{\\mathbf{y}, respectively. <\/p>\n

                          \"P\" computes \"\\upsilon^{-1}\" in every single session. If on the \"P\" side the performance of the platform exceeds the bandwidth of the communication channel between \"P\" and \"V,\" then with \"\\upsilon\" known, it is appropriate to initiate the computation of \"\\upsilon^{-1}\" ahead of time, until \"\\mathsf{ This method minimizes the computational delay, since it is plausible to assume that \"\\upsilon^{-1}\" will be known by the time \"\\mathsf{N}\" is needed to be computed.<\/p>\n

                          Since \"e_m([\\phi]\\mathsf{P}_V, due to the bilinearity, then optimization is possible when computing \"[\\phi]\\mathsf{G}_1\" (Table 1<\/u><\/a>).<\/p>\n

                          Let the affine points \"\\mathsf{S},\" \"\\mathsf{T}\" and \"\\mathsf{N}\" represented compactly<\/u><\/a>, then it will be necessary to restore the coordinates of \"y_{\\mathsf{S}},\" \"y_{\\mathsf{T}}\" and \"y_{\\mathsf{N}}\" with using the Tonelli-Shanks algorithm of asymptotic complexity \"O(\\log_{2}^2{p})\" [Cohen_etc._2006] (section 11.1.5) for subsequent computations. However, this is not necessary if point arithmetic is based on the Montgomery elliptic curve [Montgomery_1987]. It is possible to use birational equivalents, for example, twisted Edwards curves [Bernstein_2008].<\/p>\n

                          Methods for multiplicative inversion in \"\\mathbb{F}_m^*\" are described in [Cohen_etc._2006] (section 11.1).<\/p>\n

                          For the software implementation of the considered protocols, it is advisable to use the primitives of the PBC<\/u><\/a> library.<\/p>\n

                          The problem of hardware implementation of pairings is comprehensively considered in a number of publications [Rodriguez-Henriquez_etc._2006, Beuchat_etc._Nov_2008, Beuchat_etc._2008, Kammler_etc._2009, Ghosh_etc._2010, Estibals_2010, Ghosh_etc._2011, Beuchat_etc._2011, Cheung_etc._2011, Adikari_etc._2012].<\/p>\n

                          Summary<\/strong><\/p>\n

                          Protocol 1<\/strong> and Protocol 2<\/strong>, as well as modified Schnorr protocol<\/u><\/a>, have a limited scope due to the risk of impersonation.<\/p>\n

                          Preliminary analysis shows that impersonation is presumably impossible in Protocol 3<\/strong>. Everyone can use the keys \"\\mathsf{P}_P\" and \"\\mathsf{P}_V,\" but only \"P\" can provide conclusive evidence because it owns the long-term secret key \"\\mathbf{x}\" and knows the ephemeris \"\\upsilon.\" Only \"V\" can verify the proof because it knows the ephemeris \"\\phi.\"<\/p>\n

                          In addition, only \"P\" and \"V\" can independently compute \"\\mathsf{A}\" and \"\\mathsf{B}\" such that \"\\mathsf{A}=\\mathsf{B},\" since they own the secret keys \"\\mathbf{x}\" and \"\\mathbf{y}.\"<\/p>\n

                          Conclusion<\/strong><\/p>\n

                          IDS-compatible identification protocols based on the pairing function have been presented and studied. The problem of impersonification is formulated. A new impersonation-resistant IDS-compatible identification protocol has been designed.<\/p>\n

                          The text of the article in pdf format can be downloaded here<\/a>.<\/p>\n

                          Bibliography<\/strong><\/p>\n

                          [Boneh_Shacham_Lynn_2004] Boneh, D., Shacham, H. and Lynn B. «Short Signatures from the Weil Pairing.» \"\\textit{J. Vol. 17, No. 4, (2004) 297\u2013319.<\/p>\n

                          [Zhang_Safavi-Naini_Susilo_2004] Zhang, F., Safavi-Naini, R. and Susilo, W. «An efficient signature scheme from bilinear pairing and its applications.\u201d \"\\textit{Public LNCS 2947, (2004) 277\u2013290.<\/p>\n

                          [Fiat_Shamir_1987] Fiat, A. and Shamir, «How to prove yourself: Practical solutions to identification and signature problems.\u201d \"\\textit{Advances LNCS 263, (1987) 186\u2013194.<\/p>\n

                          [Cohen_etc._2006] Cohen, H., Frey, G., Roberto Avanzi, R., Doche C., Lange, T., Nguyen, K. and Vercauteren, F. \"\\textit{Handbook Chapman and Hall\/CRC, 2006.<\/p>\n

                          [Montgomery_1987] Montgomery, Peter L. «Speeding the Pollard and Elliptic Curve Methods of Factorization.\u201d \"\\textit{Mathematics (1987) 48 (177): 243\u2013264.<\/p>\n

                          [Bernstein_2008] Bernstein, Daniel J., Birkner, Peter, Joye, Marc, Lange, Tanja, Peters, Christiane. In Vaudenay, Serge (ed.). «Twisted Edwards Curves.\u201d \"\\textit{Progress LNCS 5023, (2008) 389\u2013405.\u00a0<\/p>\n

                          [Rodriguez-Henriquez_etc._2006] Rodr\u00edguez-Henr\u00edquez, F., D\u00edaz-P\u00e9rez, A., Saqib, N. A. and Ko\u010d, \u010c. K. \"\\textit{Cryptographic Signals and Communication Technology. Boston, MA: Springer US, 2006.<\/p>\n

                          [Beuchat_etc._Nov_2008] Beuchat, J.-L., Brisebarre, N., Detrey, J., Okamoto, E., Shirase, M. and Takagi,\u00a0 T. «Algorithms and Arithmetic Operators for Computing the \"\\eta Pairing in Characteristic Three.\u201d \"\\textit{IEEE vol. 57, no. 11, (Nov. 2008) 1454\u20131468.<\/p>\n

                          [Beuchat_etc._2008] Beuchat, J.-L., Brisebarre, N., Detrey, J., Okamoto,\u00a0 E. and\u00a0 Rodriguez-Henriquez, F. «A Comparison Between Hardware Accelerators for the Modified Tate Pairing over \"F_{2^m}\" and \"F_{3^m}.\"\u201d \"\\textit{Pairing-Based (2008) 297\u2013315.<\/p>\n

                          [Kammler_etc._2009] Kammler, D.,\u00a0 Zhang, D., Schwabe, P., Scharwaechter, H., Langenberg, M.,\u00a0 Auras, D., Ascheid, G. and\u00a0 Mathar, R. «Designing an ASIP for Cryptographic Pairings over Barreto-Naehrig Curves.\u201d \"\\textit{Cryptographic Springer Berlin\/Heidelberg, (2009) 254\u2013271.<\/p>\n

                          [Ghosh_etc._2010]\u00a0 Ghosh, S., Mukhopadhyay, D. and Roychowdhury, D. «High Speed Flexible Pairing Cryptoprocessor on FPGA Platform.\u201d \"\\textit{Pairing-Based vol. 6487, (2010) 450\u2013466.<\/p>\n

                          [Estibals_2010] Estibals, N. «Compact Hardware for Computing the Tate Pairing over 128-Bit Security Supersingular Curves.\u201d \"\\textit{Pairing-Based vol. 6487, (2010) 397\u2013416.<\/p>\n

                          [Ghosh_etc._2011] Ghosh, S., Roychowdhury, D. and Das, A. «High Speed Cryptoprocessor for \"\\eta Pairing on 128-bit Secure Supersingular Elliptic Curves over Characteristic Two Fields.\u201d \"\\textit{Cryptographic (2011) 442\u2013458.<\/p>\n

                          [Beuchat_etc._2011] Beuchat, J.-L.,\u00a0 Detrey, J., Estibals, N.,\u00a0 Okamoto, E. and\u00a0 Rodriguez-Henriquez, F. «Fast Architectures for the \"\\eta Pairing over Small-Characteristic Supersingular Elliptic Curves.\u201d \"\\textit{IEEE vol. 60, no. 2,\u00a0 (Feb. 2011) 266\u2013281.<\/p>\n

                          [Cheung_etc._2011]\u00a0 Cheung, R. C. C.,\u00a0 Duquesne, S., Fan, J.,\u00a0 Guillermin, N., Verbauwhede, I. and Yao, G. X. «FPGA Implementation of Pairings Using Residue Number System and Lazy Reduction.\u201d \"\\textit{Cryptographic no. 07, (2011) 421\u2013441.<\/p>\n

                          [Adikari_etc._2012] Adikari, J., Hasan, M. A. and Negre, C. «Towards Faster and Greener Cryptoprocessor for Eta Pairing on Supersingular Elliptic Curve over \"F_{2^{1223}}.\"\u201d \"19^{\\mbox{th}}\" \"\\textit{International (2012) 166\u2013183.<\/p>\n<\/p>\n<\/div>\n<\/div>\n<\/div>\n

                          <\/div>\n


                          \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438                           https:\/\/habr.com\/ru\/articles\/754688\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

                          <\/div>\n
                          \n
                          \n
                          \n
                          \n

                          In our previous post<\/u><\/a>, we presented a modified Schnorr protocol compatible with the Instant Digital Signature (IDS) mode and also announced the design of other protocols with this feature. In this post we describe such protocols based on the pairing function.<\/p>\n

                          Introduction<\/strong><\/p>\n

                          The following text is dedicated to the description of two digital signature (DS) schemes based on the pairing function (Appendix A<\/u><\/a>). These schemes are then transformed into IDS-compatible identification protocols. We specified and investigated the problem of impersonation, that is, the substitution of one party involved in protocol, with another one. The achieved result consists in the design and analysis of a new IDS-compatible identification protocol, with impersonation presumably impossible for it.<\/p>\n

                          We will use the abbreviation v.s.p. to denote a vanishingly small probability. This means that for some and distributed uniformly and independently on the interval otherwise and for large this probability is vanishingly small. For example, for A similar argument applies to where is a generator of (Appendix A<\/u><\/a>).<\/p>\n

                          When describing DS schemes and identification protocols, we will proceed from the assumption that there is a pair of linked keys where is a secret key, and is a public one for which a certificate is issued. In this certificate, is the personal data of the owner of is the DS of the trusted party (the certification authority responsible for issuing and maintaining certificates).<\/p>\n

                          Let’s call the functions of signing and verifying the digital signature as and respectively. Let’s denote the cryptographic hash function by (Appendix B<\/u><\/a>). Then where is the secret key of the trusted party consigned for signing.<\/p>\n

                          Before use, is checked for authenticity, integrity, and relevance. The latter task is done by checking a list of revoked certificates. is computed, where is the public key of trusted party If is valid, then the boolean variable and this means integrity, authenticity of and otherwise The trusted party can use any DS scheme, for example, one of those described below.\u00a0<\/p>\n

                          For the sake of simplicity, let’s assume that different DS schemes and identification protocols use the same public key <\/p>\n

                          It should be noted that most of the known DS schemes use simple equations. This is important, because this simplifies their understanding and analysis. We will be guided by the same when design identification protocols.<\/p>\n

                          DS schemes based on pairing<\/strong><\/p>\n

                          Hereinafter let’s call the one who sign the message as the Below there are descriptions of two DS schemes based on pairing (Appendix A<\/u><\/a>).<\/p>\n

                          In the DS scheme [Zhang_Safavi-Naini_Susilo_2004] for a given message the witness performs the following actions:<\/p>\n

                            \n
                          1. \n

                            Computes <\/p>\n<\/li>\n

                          2. \n

                            Generates the signature <\/p>\n<\/li>\n<\/ol>\n

                            Let there be some signature and a message The verifier performs the following actions:<\/p>\n

                              \n
                            1. \n

                              Computes <\/p>\n<\/li>\n

                            2. \n

                              Checks the authenticity, integrity and relevance of if the relevance is not confirmed or then it completes the verification of the DS.<\/p>\n<\/li>\n

                            3. \n

                              Computes <\/p>\n<\/li>\n

                            4. \n

                              Checks <\/p>\n<\/li>\n<\/ol>\n

                              Then if If then with v.s.p.<\/p>\n

                              It is clear that is computed only once and stored in the local long-term memory. Authenticity and integrity of needs to be guaranteed. For example, it can be stored in secure memory along with the secret key <\/p>\n

                              Let’s look at another DS scheme from [Boneh_Shacham_Lynn_2004]. There is a given hash function \u00a0 (Appendix B<\/u><\/a>). The witness performs the following steps:<\/p>\n

                                \n
                              1. \n

                                Computes <\/p>\n<\/li>\n

                              2. \n

                                Generates the signature <\/p>\n<\/li>\n<\/ol>\n

                                There is a message and signature The verifier does the following steps:<\/p>\n

                                  \n
                                1. \n

                                  Computes <\/p>\n<\/li>\n

                                2. \n

                                  Checks the authenticity, integrity and relevance of if the relevance is not confirmed or then it completes the verification of the DS.<\/p>\n<\/li>\n

                                3. \n

                                  Checks <\/p>\n<\/li>\n<\/ol>\n

                                  If and then, due to the bilinearity, If and\/or then with v.s.p.<\/p>\n

                                  Both above-mentioned DS schemes use the pairing function, but differ in computational complexity of check. In the [Zhang_Safavi-Naini_Susilo_2004] scheme, when checking the DS, only one pairing is computed, while in [Boneh_Shacham_Lynn_2004] it is necessary to compute two pairings.<\/p>\n

                                  IDS-compatible identification protocols based on pairing<\/strong><\/p>\n

                                  According to the Fiat-Shamir heuristic [Fiat_Shamir_1987], each DS scheme has its own identification protocol. However, we will be interested in IDS-compatible versions of such protocols.<\/p>\n

                                  Below there is a description of the IDS-compatible identification protocol for the DS scheme from [Zhang_Safavi-Naini_Susilo_2004].<\/p>\n

                                  Protocol 1<\/strong><\/p>\n

                                  Protocol messages.<\/em><\/p>\n

                                    \n
                                  1. \n<\/li>\n
                                  2. \n<\/li>\n
                                  3. \n<\/li>\n<\/ol>\n

                                    Actions of the parties.<\/em><\/p>\n

                                    proves to that it owns (knows) To do this, the following steps are performed:<\/p>\n

                                      \n
                                    1. \n

                                      selects computes checks If then selects a new re-executes the necessary computations and checks.<\/p>\n<\/li>\n

                                    2. \n

                                      reads the current certificate and checks the DS of the trusted party If then the session ends. If then it chooses and computes If then it chooses a new and re-executes the necessary computations and checks.<\/p>\n<\/li>\n

                                    3. \n

                                      checks if it is true, it computes otherwise the session ends.<\/p>\n<\/li>\n

                                    4. \n

                                      computes Then it checks If equal, then the proof is accepted, and rejected otherwise.<\/p>\n<\/li>\n<\/ol>\n

                                      Now let’s see what IDS-compatible protocol can be proposed for the DS scheme from [Boneh_Shacham_Lynn_2004].<\/p>\n

                                      Protocol 2<\/strong><\/p>\n

                                      Protocol messages.<\/em><\/p>\n

                                        \n
                                      1. \n<\/li>\n
                                      2. \n<\/li>\n
                                      3. \n<\/li>\n<\/ol>\n

                                        Actions of the parties.<\/em><\/p>\n

                                        proves to that it owns (knows) To do this, the following steps are performed:<\/p>\n

                                          \n
                                        1. \n

                                          As in Protocol 1<\/strong>.<\/p>\n<\/li>\n

                                        2. \n

                                          As in Protocol 1<\/strong>.<\/p>\n<\/li>\n

                                        3. \n

                                          checks if it is true, it computes otherwise the session ends.<\/p>\n<\/li>\n

                                        4. \n

                                          computes Then it checks If equal, then the proof is accepted, and rejected otherwise.<\/p>\n<\/li>\n<\/ol>\n

                                          For Protocols 1<\/strong> and 2<\/strong>, in case of successful completion of the identification stage, the parties independently compute a shared session secret key in accordance with the following rules:<\/p>\n

                                            \n
                                          1. \n

                                            computes <\/p>\n<\/li>\n

                                          2. \n

                                            computes <\/p>\n<\/li>\n<\/ol>\n

                                            Obviously, due to commutativity.<\/p>\n

                                            Impersonation of the verifier<\/strong><\/p>\n

                                            An active attack includes a set of measures taken to replace the information that the parties exchange with each other during the identification protocol. Protocol 1<\/strong> and Protocol<\/strong> 2<\/strong> are reliable provided that the probability of an active attack is negligible. For example, when data exchange between and is carried out using NFC (Near-Field Communication) technology or similar.<\/p>\n

                                            If the parties interact through other insecure communication channels, including the Internet, then an active attack aimed at impersonating the verifier is possible. Let’s call the bogus verifier as The attacker tries to replace with <\/p>\n

                                            Let’s choose Protocol 2<\/strong> as the object of attack. Using the interception and blocking technique, the attacker is able to impose instead of such that with v.s.p. The computes as <\/p>\n

                                            computes and checks computes and computes It is obvious that <\/p>\n

                                            The above mentioned reasoning is equally valid for Protocol 1<\/strong>. In addition, the attack is also applicable to modified Schnorr protocol<\/u><\/a>.<\/p>\n

                                            In the next section, we will demonstrate a protocol where impersonation is not presumably possible.<\/p>\n

                                            Protocol resistant to impersonation<\/strong><\/p>\n

                                            Let’s assume that, for and own key pairs and respectively. There are certificates and issued for and <\/p>\n

                                            Let us consider an IDS-compatible and at the same time impersonation-resistant protocol.<\/p>\n

                                            Protocol 3<\/strong><\/p>\n

                                            Protocol messages<\/em>.<\/p>\n

                                              \n
                                            1. \n<\/li>\n
                                            2. \n<\/li>\n
                                            3. \n<\/li>\n<\/ol>\n

                                              Actions of the parties<\/em>.<\/p>\n

                                              proves to that it owns (knows) To do this, the following steps are performed:<\/p>\n

                                                \n
                                              1. \n

                                                reads the current certificate and verifies the DS of the trusted party If then the session ends. If then it selects computes checks If then it chooses a new and re-executes the necessary computations and checks.<\/p>\n<\/li>\n

                                              2. \n

                                                reads the current certificate and verifies the DS of the trusted party If then the session ends. If then it chooses and computes If then it chooses a new and re-executes the necessary computations and checks.<\/p>\n<\/li>\n

                                              3. \n

                                                checks if it is true, it computes otherwise the session ends.<\/p>\n<\/li>\n

                                              4. \n

                                                computes Then it checks If equal, then the proof is accepted, and rejected otherwise.<\/p>\n<\/li>\n<\/ol>\n

                                                If accepted the proof provided by then the parties independently compute a shared session secret:<\/p>\n

                                                  \n
                                                1. \n

                                                  computes <\/p>\n<\/li>\n

                                                2. \n

                                                  computes\u00a0 <\/p>\n<\/li>\n<\/ol>\n

                                                  It is clear that due to commutativity.<\/p>\n

                                                  Preliminary analysis<\/strong><\/p>\n

                                                  Let bogus verifier owns the key pair with v.s.p.<\/p>\n

                                                  We restrict ourselves to the analysis of Protocol 3<\/strong>, in which it is necessary to impose instead of in order to impersonate the verifier (replace with ). However, the attacker does not know the ephemeris. To reveal one need to solve an ECDLP\/DLP given\u00a0 or <\/p>\n

                                                  Another strategy is to solve ECDLP\/DLP given or Then The relationship between ECDLP and DLP is explained in Appendix A<\/u><\/a>.<\/p>\n

                                                  The attacker has access to and is able to impose instead of and instead of while and being with v.s.p. computes as <\/p>\n

                                                  computes Obviously, with v.s.p. In addition, the attacker can choose arbitrary and Let but with v.s.p.<\/p>\n

                                                  It is easy to show that replacement of does not lead to the desired result. To do this, when computing we set However, with v.s.p.<\/p>\n

                                                  If we assume that the attacker imposes instead of but there is no replacement of then the impersonation of is also impossible, since with v.s.p.<\/p>\n

                                                  Note that or Therefore, with v.s.p.<\/p>\n

                                                  When computing replacing with some seems to be counterproductive. If such a replacement is allowed, then with v.s.p., there will be a discrepancy in Let Then with v.s.p.<\/p>\n

                                                  The amount of information transmitted<\/strong><\/p>\n

                                                  If compact representation<\/u><\/a> is used, then one needs to transfer bits in Protocol<\/strong> 1<\/strong> and Protocol 2<\/strong> in order to deliver and in total.<\/p>\n

                                                  In Protocol<\/strong> 3<\/strong>, must inform of the serial number of Let’s suppose that bits need to be allocated to store this number in long-term memory. Then one needs to send bits in order to deliver and in total.<\/p>\n

                                                  Other overheads are allowed. The amount of information transmitted satisfies the asymptotic estimate <\/p>\n

                                                  Computational complexity<\/strong><\/p>\n

                                                  In addition to the scalar multiplication, whose computation features are described here<\/u><\/a>, in the Protocol 3<\/strong> parties and compute and respectively.<\/p>\n

                                                  In this case, and are computed only once. and store the computed values in secured long-term memory. As a result, and store and respectively. <\/p>\n

                                                  computes in every single session. If on the side the performance of the platform exceeds the<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-352195","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/352195","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=352195"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/352195\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=352195"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=352195"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=352195"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}