{"id":356291,"date":"2024-05-20T23:26:31","date_gmt":"2024-05-20T23:26:31","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=356291"},"modified":"-0001-11-30T00:00:00","modified_gmt":"2024-05-20T23:26:31","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=356291","title":{"rendered":"Anonymous identification for groups<\/span>"},"content":{"rendered":"
<\/div>\n
\n
\n
\n
\n

The identification protocol based on the pairing function, resistant to impersonation and compatible with the instant digital signature (IDS) mode, was studied in this article<\/u><\/a>. This protocol uses prover’s and verifier’s public keys. As a result, there is no anonymity, since certificates including personal data of their owners are issued for the mentioned keys. This article contains a description and analysis of new anonymous identification protocols for groups.<\/p>\n

This publication consists of sections where we describe anonymous group identification protocols for two different scenarios, analyze the key security and resistance to impersonation, estimate the amount of information transmitted, and evaluate the optimization of computations and memory resources. At the end of this text, summary and conclusion are specified and formulated.<\/p>\n

This publication consists of sections where we describe anonymous group identification protocols for two different scenarios, analyze the key security and resistance to impersonation, estimate the amount of information transmitted, and evaluate the optimization of computations and memory resources. At the end of this text, summary and conclusion are specified and formulated.<\/p>\n

The term ‘vanishingly small probability’ (abbreviated as v.s.p.) and the boolean variable \"\\mathfrak{B},\"as well as public key certificates functions, were all explained in our previous article<\/u><\/a>.<\/p>\n

The following practical problem is studied in the fundamental work [RST’01]. Some party \"\\texttt{A},\" for example, a member of the cabinet of ministers (CM), intends to publish incriminating information about the actions of the prime minister. For this purpose, \"\\texttt{A}\" contacts, for example, \"\\texttt{B},\" a journalist from an independent media. In this case, on the one hand, it is necessary to guarantee the anonymity of the source. On the other hand, it’s essential to ensure the reliability of the information provided. From the point of view of \"\\texttt{B},\" the information provided by a member of the CM is considered reliable.<\/p>\n

Let’s take a look at possible options.<\/p>\n

    \n
  1. \n

    \"\\texttt{A}\" cannot transmit a message signed with through a digital signature (DS) scheme, since the verification will result in de-anonymization, because\u00a0 \"\\texttt{A}\u2019s\" personal data is included in the public key certificate. Although this method will certainly convince \"\\texttt{B}\" that the information comes from a member of the CM.<\/p>\n<\/li>\n

  2. \n

    If \"\\texttt{A}\" uses anonymizing services, then all identifiers of the sender will be removed from the transmitted message. Therefore, \"\\texttt{B}\" will not be able to verify that the information comes from a member of the CM and won’t consider it reliable.<\/p>\n<\/li>\n<\/ol>\n

    In [RST’01] a solution has been proposed. Each member of the CM generates a DS using his personal private key, but this DS can only be verified using the personal public keys of all members of the CM, including the witness himself. As a result, \"\\texttt{B}\" is convinced and can also convince a third party that the information comes from the CM, but at the same time \"\\texttt{A}\" remains unknown.<\/p>\n

    We propose a solution to the problem formulated above through an anonymous identification protocol for groups. The advantage of our solution is that in addition to anonymous identification, \"\\texttt{A}\" can transmit information confidentially using a secure data transfer tunnel. The tunnel (virtual) is accessible by construction, since \"\\texttt{A}\" and \"\\texttt{B}\" are able to independently generate a shared session secret key upon successful identification. Confidentiality is guaranteed by using a symmetric cryptographic scheme.<\/p>\n

    The anonymous group identification protocol also makes it possible to convince a third party that the information received comes from a member of the CM. This follows from the fact that all public keys involved in verifying the evidence belong to members of the CM, which is easily verified using personal data from the certificates of these keys. Anonymity is based on a simple principle, which can be formulated as follows: \u201cit is reliably known that one is from the group, but it is not known who exactly.\u201d<\/p>\n

    The use of an anonymous group identification protocol is logically justified in the context of solving a wide range of practical problems for which compatibility with the IDS mode is essential. Some scenarios are described here<\/u><\/a>.<\/p>\n

    Anonymous identification protocols for groups<\/h3>\n

    The parameters used below, such as \"p\", \"m\", \"\\mathbb{G}_1\", \"\\mathbb{G}_3\", \"\\mathbb{F}_m\", \"e_m(\\cdot, are explained in Appendix A<\/u><\/a>.<\/p>\n

    For the sake of simplicity, we omit details related to the verification of criteria needed for inclusion in the group, as well as the subsequent registration of those participants who meet them. We will proceed from the assumption that such a group has been successfully created.<\/p>\n

    For \"2\\leqslant participants, represented by a set of numerators\u00a0 \"\\mathcal{I}=\\{1,\\ldots,n,n+1,\\ldots,2n\\},\" the trusted party \"T\" generates a set of long-term public keys \"\\mathcal{P},\" a set of personal private keys of participants \"\\mathcal{K},\" as well as a group public key \"\\mathsf{Q}.\"<\/p>\n

    Setup (Input: \"n\". Output: \"\\mathcal{P}\", \"\\mathcal{K}\", \"\\mathsf{Q}\").<\/strong><\/p>\n

      \n
    1. \n

      \"\\widetilde{\\mathcal{I}}=\\mathcal{I}\\setminus \"|\\widetilde{\\mathcal{I}}|=2n-1.\"<\/p>\n<\/li>\n

    2. \n

      \"\\alpha\\in_R\\!(0,m-1].\"<\/p>\n<\/li>\n

    3. \n

      \"\\omega\\in_R\\!(0,m-1],\" if \"\\omega=\\alpha,\" then it chooses another \"\\omega.\"<\/p>\n<\/li>\n

    4. \n

      \"\\mathsf{P}_i=[\\alpha^i\\omega\\pmod \"\\forall if \"\\exists!_{i\\in\\widetilde{\\mathcal{I}}}(\\mathsf{P}_i=\\infty),\" then it goes to 3.<\/p>\n<\/li>\n

    5. \n

      \"\\gamma\\in_R\\!(0,m-1],\" if \"(\\gamma=\\omega)\\lor(\\gamma=\\alpha),\" then it chooses another \"\\gamma.\"<\/p>\n<\/li>\n

    6. \n

      \"\\mathsf{Q}=[\\gamma\\omega\\alpha^{n+1}\\pmod if \"\\mathsf{Q}=\\infty,\" then it goes to 5.<\/p>\n<\/li>\n

    7. \n

      \"s_{i}=\\alpha^i\\gamma\\pmod \"i=\\overline{1,n},\" if \"\\exists!_{i\\in[1,n]}(s_{i}=0),\" then it goes to 5.<\/p>\n<\/li>\n

    8. \n

      \"\\mathcal{P}=\\{\\mathsf{P}_1,\\ldots,\\mathsf{P}_n,\\mathsf{P}_{n+2},\\ldots,\\mathsf{P}_{2n}\\},\" \"|\\mathcal{P}|=2n-1,\" \"\\mathcal{K}=\\{s_1,\\ldots, \"|\\mathcal{K}|=n.\"<\/p>\n<\/li>\n<\/ol>\n

      The private key \"s_i\\in\\mathcal{K}\" is delivered to the \"i\"-th participant in a private way, for example, using Protocol 3<\/em><\/strong> from this article<\/u><\/a>. A separate certificate is issued indicating the owner\u2019s personal data for each public key from \"\\{\\mathsf{P}_1, In addition, a single certificate is issued for \"\\{\\mathsf{P}_{n+2}, which establishes the connection between the components of this set with keys from \"\\{\\mathsf{P}_1,<\/p>\n

      The setup is performed once<\/u> and ends with the removal of \"\\alpha,\" \"\\gamma,\" \"\\omega,\" \"s_i\" from the local long-term secret memory of party \"T.\" In total, \"n+1\" certificates are issued and maintained.<\/p>\n

      Protocol 1<\/h3>\n

      Let’s consider the anonymous identification protocol for the case where \"V\" does not belong to the group of registered participants and \"\\mathsf{P}_V\" differs from the public keys from \"\\mathcal{P}.\" Let’s suppose that \"V\" owns a key pair \"\\{\\mathbf{y},\\mathsf{P}_V=[\\mathbf{y}]\\mathsf{G}_1\\},\" where \"{\\mathbf{y} The certificate \"\\{D_V,\\mathsf{P}_V, is issued for \"\\mathsf{P}_V.\" \"V\" has access to \"\\mathcal{S}\" and knows \"n.\"<\/p>\n

      Let an \"\\ell\"th participant act as \"P,\" \"\\ell\\in\\mathcal{S},\" \"\\mathcal{S}\\subseteq\\{1,\\ldots,n\\}.\"<\/p>\n

      Protocol messages. <\/strong><\/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.<\/strong> <\/p>\n

        \"P\" proves to \"V\" that it knows the private key \"s_\\ell\" such that \"\\ell\\in\\mathcal{S}\" and \"\\mathsf{P}_\\ell\\in\\{\\mathsf During the proof, \"\\ell,\" \"s_\\ell\" and \"\\mathsf{P}_\\ell\" are not revealed. The following steps are performed:<\/p>\n

          \n
        1. \n

          \"P\" reads the current certificate \"\\{D_V,\\mathsf{P}_V, 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 \"{\\upsilon\\in_R\\!(0,m-1]}\" (commitment<\/em>), computes \"\\mathsf{S}\" (witness<\/em>), checks the condition \"{\\mathsf{S}\\stackrel{?}\\neq\\infty}.\" If \"\\mathsf{S}=\\infty,\" then \"P\" selects a new \"\\upsilon\" and re-performs the necessary computations and checks.<\/p>\n<\/li>\n<\/ol>\n

            \n
          1. \n

            \"V\" reads the current certificate \"\\{D_V,\\mathsf{P}_V, and checks the DS of the trusted party \"\\rm{T}.\" If \"\\mathfrak{B}=False\" then the session ends. If \"\\mathfrak{B}=True,\" then \"V\" selects \"{\\phi\\in_R\\!(0, and computes \"\\mathsf{T}\" (challenge<\/em>). If \"\\mathsf{T}=\\infty,\" then \"V\" selects a new \"\\phi\" and re-performs the necessary computations and checks. <\/p>\n<\/li>\n

          2. \n

            \"P\" checks the integrity, authenticity and relevance of public keys \"j\\in\\widetilde{\\mathcal{S}},\" \"\\widetilde{\\mathcal{S}}=\\{\\mathcal{S}\\}\\setminus\\{\\ell\\},\" using the appropriate certificates. If relevance is not confirmed or \"\\mathfrak{B}=False,\" then the current session ends. \"P\" checks the condition \"\\mathsf{T}\\stackrel{?}\\neq\\infty.\" If it’s true, then \"P\" computes response<\/em> for \"\\widetilde{\\mathcal{S}}\" as \"\\{g_a=g_\\ell^{-1}, where <\/p>\n

            \"g_\\ell=e_m([\\upsilon <\/p>\n

            otherwise the session ends.<\/p>\n<\/li>\n

          3. \n

            \"V\" verifies the integrity, authenticity and relevance of public keys \"\\mathsf{P}_{n+1-j},\" \"j\\in\\mathcal{S},\" using the appropriate certificates. If the relevance is not confirmed or \"\\mathfrak{B}=False,\" then the current session ends. \"V\" checks the condition \"(\\mathsf{S}\\neq\\infty)\\land((g_a\\neq If the condition is not met, the session ends. If it’s met, then \"V\" computes:<\/p>\n

            \"g_b=e_m([\\mathbf{y}^\\phi\\pmod <\/p>\n

            \"g_c=g_bg_a=g^{\\upsilon\\mathbf{y}^{\\phi+1}\\gamma\\omega(\\sum_{j\\in\\mathcal{S}}\\alpha^{n+1-j+\\ell}-\\sum_{j\\in\\widetilde{\\mathcal{S}}}\\alpha^{n+1-j+\\ell})\\pmod <\/p>\n<\/li>\n<\/ol>\n

            Then \"V\" checks \"g_c\\stackrel{?}{=}e_m([\\mathbf{y}^\\phi\\pmod If equal, then the proof is accepted, and rejected otherwise.<\/p>\n

            If the identification stage is successfully completed, the parties independently generate a shared session secret key in accordance with the following rules:<\/p>\n

              \n
            1. \n

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

            2. \n

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

              Protocol 2<\/h2>\n

              Let’s now consider a protocol where \"V\" belongs to a group of registered participants. Then \"V\" owns a key pair \"\\{s_c,\\mathsf{P}_c\\},\" where \"c\\in and \"{s_c=\\gamma\\alpha^c\\pmod \"\\mathsf{P}_c=[\\omega\\alpha^c\\pmod The certificate \"\\{D_c,\\mathsf{P}_c, is issued for \"\\mathsf{P}_c.\"<\/p>\n

              Protocol messages.<\/em><\/strong><\/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><\/strong><\/p>\n

                \"P\" proves to \"V\" that it knows the private key \"s_\\ell\" such that \"\\ell\\in\\mathcal{S}\" and \"\\mathsf{P}_\\ell\\in\\{\\mathsf During the proof, \"\\ell,\" \"s_\\ell\" and \"\\mathsf{P}_\\ell\" are not revealed. The following steps are performed:<\/p>\n

                  \n
                1. \n

                  \"P\" reads the current certificate \"\\{D_c,\\mathsf{P}_c, and checks the DS of the trusted party \"\\rm{T}.\" If \"\\mathfrak{B}=False,\" then the session ends. If \"\\mathfrak{B}=True,\" then \"P\" chooses \"{\\upsilon\\in_R\\!(0,m-1]}\" (commitment<\/em>), computes \"\\widehat{\\mathsf{S}}\" (witness<\/em>), checks the condition \"{\\widehat{\\mathsf{S}}\\stackrel{?}\\neq\\infty}.\" If \"\\widehat{\\mathsf{S}}=\\infty,\" then \"P\" choses another \"\\upsilon\" and re-performs the necessary computations and checks.<\/p>\n<\/li>\n<\/ol>\n

                    \n
                  1. \n

                    \"V\" reads the current certificate \"\\{D_c,\\mathsf{P}_c, and checks the DS of the trusted party \"\\rm{T}.\" If \"\\mathfrak{B}=False,\" then the session ends. If \"\\mathfrak{B}=True,\" then \"V\" computes \"{\\widehat{\\mathsf{P}}_c=[s_c^{-1}]\\mathsf{P}_c=[\\gamma^{-1}\\omega\\pmod chooses \"{\\phi\\in_R\\!(0, and then computes \"\\widehat{\\mathsf{T}}\" (challenge<\/em>). If \"\\widehat{\\mathsf{T}}=\\infty,\" then \"V\" chooses another \"\\phi\" and re-performs the necessary computations and checks.<\/p>\n<\/li>\n<\/ol>\n

                      \n
                    1. \n

                      \"P\" checks the integrity, authenticity and relevance of public keys \"\\mathsf{P}_{n+1-j},\" \"j\\in\\widetilde{\\mathcal{S}},\" \"\\widetilde{\\mathcal{S using the appropriate certificates. If relevance is not confirmed or \"\\mathfrak{B}=False,\" then the current session ends. \"P\" checks the condition \"\\widehat{\\mathsf{T}}\\stackrel{?}\\neq\\infty.\" If the condition is met, then \"P\" computes response<\/em> for \"\\widetilde{\\mathcal{S}}\" as \"\\{\\hat{g}_a=\\hat{g}_\\ell^{-1}, where<\/p>\n<\/li>\n<\/ol>\n

                      \"\\hat{g}_\\ell=e_m([\\upsilon<\/p>\n

                      otherwise the session ends.<\/p>\n

                        \n
                      1. \n

                        \"V\" verifies the integrity, authenticity and relevance of public keys \"\\mathsf{P}_{n+1-j},\" \"j\\in\\mathcal{S},\" using the appropriate certificates. If the relevance is not confirmed or \"\\mathfrak{B}=False,\" then the current session ends. \"V\" checks the condition \"(\\widehat{\\mathsf{S}}\\neq\\infty)\\land((\\hat{g}_a\\neq If the condition is not met, the session ends. If it is met, then \"V\" computes<\/p>\n<\/li>\n<\/ol>\n

                        \"\\hat{g}_b=e_m([\\phi\"\\hat{g}_c=\\hat{g}_b\\hat{g}_a=g^{\\phi\\upsilon\\omega^2(\\sum_{j\\in\\mathcal{S}}\\alpha^{n+1-j+\\ell}-\\sum_{j\\in\\widetilde{\\mathcal{S}}}\\alpha^{n+1-j+\\ell})\\pmod<\/p>\n

                        Then \"V\" checks \"\\hat{g}_c\\stackrel{?}{=}e_m([\\phi If equal, then the proof is accepted, and rejected otherwise.<\/p>\n

                        If the identification stage is successfully completed, the parties independently generate a shared session secret key in accordance with the following rules:<\/p>\n

                          \n
                        1. \n

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

                        2. \n

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

                          Key security<\/h2>\n

                          The idea is that the public key \"\\mathsf{P}_i\" is masked using \"\\omega,\" while the private key \"s_i\" is masked using \"\\gamma,\" where \"{\\gamma, and \"\\gamma\\neq\\omega\\neq\\alpha\" by construction. This means that the complexity of revealing all \"s_i\" with a known ECDLP\/DLP solution for the public key from \"\\mathcal{P},\" as well as a known private key from \"\\mathcal{K},\" is not less than the complexity of finding a ECDLP\/DLP solution.<\/p>\n

                          Let’s consider a particular case. Let us assume that \"s_1=\\gamma\\alpha\\pmod and \"\\varphi_1=\\alpha\\omega\\pmod are known, where \"\\varphi_1\" is the ECDLP\/DLP solution subject to \"\\mathsf{P}_1\" or \"e_m(\\mathsf{ Then<\/p>\n

                          \"\\alpha={\\varphi_1\\omega^{-1}\\pmod \"\\omega={\\varphi_1\\alpha^{-1}\\pmod \"\\gamma=s_1\\alpha^{-1}\\pmod and \"\\psi={s_1\\varphi_1^{-1}\\pmod \"\\psi'=s_1^{-1}\\varphi_1\\pmod Consequently, if \"\\varphi_1\" and \"s_1\" are known, then it is enough to find \"\\alpha\\lor\\gamma\\lor\\omega\" to reveal all \"s_i,\" \"2\\leqslant<\/p>\n

                          Note that the adversary has additional capabilities. Let \"s_u\" and \"\\varphi_u\" be known such that \"u=2^{2^w},\" \"u\\in[2,n],\" \"0\\leqslant The adversary’s motivation is that with known \"\\varphi_u\" and 2″ alt=»u>2″ src=»https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c75\/ded\/48f\/c75ded48f90a63f07c613de0bd3bc1e0.svg» width=»46″ height=»16″\/> (the square root is calculated once if \"u=2\"), it is possible to reveal \"\\alpha\" using the iterative method of taking a square root using the Tonelli-Shanks algorithm of asymptotic complexity \"O((\\log_{2}{m})^2)\" [C’06] (section 11.1.5). <\/p>\n

                          For example, with known \"\\omega,\" \"\\alpha=\\sqrt{\\cdots\\sqrt{\\varphi_u\\omega^{-1}\\pmod and \"\\gamma={s_u\\varphi_u^{-1} In general, it is not known how to take the root of an arbitrary degree in \"\\mathbb{F}_m^*.\"<\/p>\n

                          Brute force attacks for some \"\\varphi_u,\" \"s_u\" are listed in Appendix C<\/u><\/a>. Frontal attack (Algorithm 1) is not considered optimal, since on average it will take \"M\/2\" trials, where \"M=m-1.\"<\/p>\n

                          Let’s suppose that there is a number \"\\mathsf{a}\" such that \"\\mathsf{a}\\equiv\\varphi_u\\pmod and a factorization \u00a0 \"\\mathsf{a}=\\prod_{j=1}^t\\mathsf{p}_j^{r_j}\" is known, \"\\mathsf{p}_j\" are different primes, \"{r_j,t\\in\\mathbb{N}}.\" <\/p>\n

                          Such factorization can be obtained by using, for example, the number field sieve<\/em> method<\/em> or another well-known method [I’11]. Let the set \"\\mathcal{D}=\\{\\mathsf{p}_1^{r_1}, be given. If all \"r_j\" are known, then the following representation is true:<\/p>\n

                          \"\\widehat{\\mathcal{D}}=\\{\\underbrace{\\mathsf{p}^{\\mathstrut}_1,\\ldots,\\mathsf{p}^{\\mathstrut}_1}_{r_1}, \"|\\widehat{\\mathcal{D}}|=\\sum_{j=1}^t <\/p>\n

                          Let us enumerate the prime numbers from \"\\widehat{\\mathcal{D}}\" by integers from \"1\" to \"d\" and move to the set \"\\widetilde{\\mathcal{D}}=\\{\\tilde{\\mathsf{p}}<\/p>\n

                          Let’s estimate the complexity of the optimized brute force (Algorithm 2). The attack uses the auxiliary sequence \"\\mathbf{b}=(b_1, \"b_j\\in\\{0,1\\}.\" The Hamming weight \"\\mathbf{b}\" varies in the range from \"1\" to \"\\lceil and the number of trials is limited above by<\/p>\n

                          \"A=\\sum_{j=1}^{\\lceil <\/p>\n

                          On average, it takes\u00a0 \"A\/2\" trials to find \"\\alpha,\" \"\\omega,\" \"\\gamma.\"<\/p>\n

                          Let’s suppose that \"\\alpha=\\tilde{\\mathsf{p}}_{1}^{\\mathsf{x}}\\pmod and \"\\omega=\\tilde{\\mathsf{p}}_{2}^{\\mathsf{y}}\\pmod \"\\mathsf{x}, Let us recall that \"\\alpha\\neq\\omega\" by construction, and the following options are also possible:<\/p>\n

                            \n
                          1. \n

                            \"\\tilde{\\mathsf{p}}_{1}=\\tilde{\\mathsf{p}}_{2}\" \"\\Rightarrow\" \"((\\mathsf{x}\\geqslant<\/p>\n<\/li>\n

                          2. \n

                            \"\\tilde{\\mathsf{p}}_{1}\\neq\\tilde{\\mathsf{p}}_{2}\" \"\\Rightarrow\" \"(\\mathsf{x}\\geqslant<\/p>\n<\/li>\n<\/ol>\n

                            Let’s denote the number of primes in the range \"[1, as \"\\pi(M).\" According to Chebyshev’s estimates \"{0.92\\times\\frac{M}{\\ln Therefore, \"2<d\\leqslant\\pi(M).\" <\/p>\n

                            It is well known that\u00a0 \"\\sum_{j=0}^d but in (1) approximately half of all possible binomial coefficients are summed up and therefore \"A<2^d.\" Thus, \"\\forall_{d\\leqslant\\lceil<\/p>\n

                            The cardinality of the set \"\\widetilde{\\mathcal{D}}\" cannot be controlled if \"\\alpha, As a result, \"d\" may be small and the complexity of a brute force, meaning the number of trials \"A,\" will not provide the required security level.<\/p>\n

                            Let’s act as follows in order to improve the situation. At the setup stage, let the trusted party \"T\" randomly select \"d\\leqslant distinct primes from the range \"[1, and make the set \"\\widetilde{\\mathcal{D}}.\" The primality test is performed using the technique from [AKS’04]. For example, if \"m\\sim then \"1.2\\times10^{46} Then \"T\" generates a random binary sequence \"\\mathbf{b}\" of Hamming weight \"\\lceil where \"b_j\\in_R\\!\\{0, and for a given \"\\widetilde{ computes:<\/p>\n

                            \"\\alpha=\\prod_{j=1}^d\\tilde{\\mathsf{p}}_j^{b_j}\\pmod and \"\\omega=\\prod_{j=1 \"\\forall_{j\\in[1,d]}\\bar{b}_j=b_j\\oplus <\/p>\n

                            Now the complexity of the brute force mentioned above is limited by the guaranteed value \"B=C_d^{\\lceil and A>B\\geqslant\\frac{2^d}{d+1}.» alt=»2^d>A>B\\geqslant\\frac{2^d}{d+1}.» src=»https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/087\/c9f\/60a\/087c9f60a1c7e32fd324737425daa4a4.svg» width=»181″ height=»48″\/> <\/p>\n

                            In general, \"C_d^{[ad]}=\\left(\\frac{1}{a^a(1-a)^{1-a}}+o(1)\\right)^d,\" <\/p>\n

                            where \"a\\in(0,1),\" \"o(1)\" is a certain function whose modulus tends to zero and can take on both negative and positive values. If \"a=1\/2\" then \"B=(2+o(1))^d.\" For example, to ensure a \"80\"-bit security level or higher, it’s necessary to choose \"d\\geqslant84.\"<\/p>\n

                            The complexity of finding \"\\alpha\\lor\\omega\\lor\\gamma\" under the condition \"\\widetilde{\\mathcal{D}}\" is equivalent to the well-known \"NP\"-complete problem Subset Product<\/em> [GJ’79] (SP14, p. 224) or, in another way, Product of Dimensions<\/em> [GJ’82] (MP 14, page 283). \"NP\"-completeness is proven by reducing another \"NP\"-complete problem known as Exact Coverage by 3-Sets<\/em> [GJ’82] (TP-3, page 73) to this problem. It should be noted that MP 14 is a problem with numerical parameters and \"NP\"-completeness does not exclude solving this problem using a pseudopolynomial time complexity algorithm under the condition \"P\\neq [GJ’82] (section 4.2 on page 117, commentary to MP 14 on page 283), which depends on \"d\" and \"\\max(\\tilde{\\mathsf{p}}_1, Obviously, the existence of an algorithm of such complexity provides the adversary with additional opportunities. However, this drawback is eliminated if \"T\" chooses \"d\" primes from the range \"[\\lceil\\sqrt{\\mathstrut{m}}\\rceil, and the value of \"d\" is such that it compensates for the decrease in security level due to the existence of a pseudo-polynomial complexity algorithm. The value of \"d\" is limited below by the security level. Then \"T\" can choose an arbitrarily large \"d,\" subject to a given security level as a necessary condition. The set \"\\widetilde{\\mathcal{D}}\" is created once at the setup and its cardinality, as well as the bitlength of the prime numbers included, does not affect the performance characteristics of the identification protocol. The number of primes in the mentioned range does not differ in order of magnitude from \"\\pi(M).\" With \"80\"-bit security level, the length of prime numbers will vary from \"80\" to \"160\" bits.<\/p>\n

                            Grover’s algorithm [G’96] allows to find \"\\alpha\\lor\\omega\\lor\\gamma\" under the condition \"\\widetilde{\\mathcal{D}}\" in \"O(\\sqrt{B})\" trials on a quantum computer with \"O(d)\" qubits. If a brute force on a quantum computer seems realistic, then it’s necessary to choose such a value of \"d\" that it could compensate for the decrease in security as a result of using Grover’s algorithm. For example, a security level of \"80\" bits inclusive and higher is provided with \"d\\geqslant<\/p>\n

                            In [S’97] it is demonstrated that on a quantum computer the complexity of such intractable problems as factorization, DLP, and also ECDLP due to the existence of a bilinear mapping \"e_m:\\mathbb{G}_1\\times is limited by some polynomial of the input size.<\/p>\n

                            Let’s note that the set \"\\widetilde{\\mathcal{D}}\" is intended solely for obtaining \"\\alpha,\" \"\\omega,\" on the basis of which \"\\mathsf{P}_i,\" \"s_i\" are then computed. Once all necessary computations are complete, \"T\" removes \"\\widetilde{\\mathcal{D}}\" from local long-term memory.<\/p>\n

                            Why does it work<\/h2>\n

                            It’s worth noting that the anonymous group identification protocol is based on the ideas revealed in [BGW’05].<\/p>\n

                            Let’s dive inside it and look at the function \"{\\eta=n+1-j+\\ell},\" which appears in the exponent of \"\\alpha\" when \"g_\\ell\" and \"g_b,\" as well as \"\\hat{g}_ and \"\\hat{g}_b\" being computed.<\/p>\n

                            The function \"\\eta\" is continuous, and, for analysis purposes, it is enough to look at the Table #1 containing values for some enumerators from the integer interval \"[1,<\/p>\n

                            <\/figure>\n

                            Let \"\\mathcal{S}=\\{1,\\ldots,n\\},\" \"\\ell\\in and \"\\widetilde{\\mathcal{S}}=\\{\\mathcal{S} According to the Table 1, \"\\eta=n+1\" is located on the main diagonal and meet the criteria \"j=\\ell,\" \"\\ell\\neq by construction and therefore \"\\eta\\in[2,2n].\" <\/p>\n

                            Since \"\\widetilde{\\mathcal{S}}\" lacks the \"\\ell\"th numerator, but \"\\mathcal{S}\" contains the numerator \"j=\\ell,\" then<\/p>\n

                            \"\\sum_{j\\in<\/p>\n

                            In \"\\mathcal{S},\" the non-decreasing order of the numerators is chosen to simplify explanations. It’s worth noting that the protocol is invariant regarding this order. Moreover, the protocol works correctly with the subset \"\\mathcal{S}_\\wp\\subseteq\\mathcal{S}.\" The asymptotic estimate for the number of such subsets is \"O(2^n).\" These subsets may either intersect or not.<\/p>\n

                            Example<\/h2>\n

                            Let’s suppose that \"\\mathcal{S}=\\{1,2,3,\\ldots,8,9,10\\}\" and \"(n+1)=11.\" There is some subset \"{\\mathcal{S}_\\wp\\subset\\mathcal{S}}\" such that<\/p>\n

                            \"\\mathcal{S}_\\wp=\\{3,7,5,8,4,2\\}.\" Let \"\\ell=7,\" then \"\\widetilde{\\mathcal{S}}_\\wp=\\{3,5,8,4,2\\}.\" Therefore, <\/p>\n

                            \"\\sum_{j\\in\\mathcal{S}_\\wp}\\alpha^{n+1-j+\\ell}-\\sum_{j\\in\\widetilde{\\mathcal{S}_\\wp}}\\alpha^{n+1-j+\\ell}=\"<\/p>\n

                            \"\\alpha^{11-3+7}+\" <\/p>\n

                            \"\\alpha^{11-7+7}+\"<\/p>\n

                            \"\\alpha^{11-5+7}+\" <\/p>\n

                            \"\\alpha^{11-8+7}+\" <\/p>\n

                            \"\\alpha^{11-4+7}+\"<\/p>\n

                            \"\\alpha^{11-2+7}-\" <\/p>\n

                            \"\\alpha^{11-3+7}-\"<\/p>\n

                            \"\\alpha^{11-5+7}-\" <\/p>\n

                            \"\\alpha^{11-8+7}-\"<\/p>\n

                            \"\\alpha^{11-4+7}-\"<\/p>\n

                            \"\\alpha^{11-2+7}=\\alpha^{11}.\"<\/p>\n

                            Preliminary analysis<\/h2>\n

                            Let’s suppose that the adversary knows \"\\ell\" and \"\\varphi_\\ell\" is a ECDLP\/DLP solution subject to \"\\mathsf{P}_\\ell\" or \"e_m(\\mathsf{P}_\\ell, Then in Protocol 1<\/strong> the adversary on behalf of \"P\" computes witness<\/em> as \"\\mathsf{S}'={[\\upsilon Moreover, \"P\" computes response<\/em> as<\/p>\n

                            \"\\{\\acute{g}_a=\\acute{g}_\\ell^{-1},\" \"\\mathsf{R}'=[\\varphi_\\ell^{-1}]\\mathsf{Q}=[\\gamma\\alpha^{n+1-\\ell}\\pmod where<\/p>\n

                            \"\\acute{g}_\\ell=e_m([\\upsilon<\/p>\n

                            In its turn, \"V\" computes<\/p>\n

                            \"\\acute{g}_b=e_m([\\mathbf{y}^\\phi\\pmod\"\\acute{g}_c=\\acute{g}_b\\acute{g}_a=g^{\\upsilon\\mathbf{y}^{\\phi+1}\\omega^2(\\sum_{j\\in<\/p>\n

                            Therefore, \"\\grave{g}=e_m([\\mathbf{y}^\\phi\\pmod and \"\\acute{g}_c=\\grave{g}\" with v.s.p.<\/p>\n

                            In order to deceive the verifier, the adversary needs to reveal \"\\gamma\" and \"\\omega,\" then<\/p>\n

                            \"\\mathsf{R}'={[\\gamma^{-1}\\omega\\varphi_\\ell^{-1}\\pmod and \"\\acute{g}_c=\\grave{g}.\"<\/p>\n

                            In Protocol 2<\/strong> witness<\/em> and response<\/em> are computed as \"\\widehat{\\mathsf{S}}'=[\\upsilon\\varphi_\\ell and \"\\{\\check{g}_a=\\check{g}_\\ell^{-1},\" \"\\mathsf{R}'=[\\varphi_\\ell^{-1}]\\mathsf{Q}=[\\gamma\\alpha^{n+1-\\ell}\\pmod respectively, where<\/p>\n

                            \"\\check{g}_\\ell=e_m([\\upsilon<\/p>\n

                            \"V\" computes<\/p>\n

                            \"\\check{g}_b=e_m([\\phi\"\\check{g}_c=\\check{g}_b\\check{g}_a=g^{\\phi\\upsilon\\gamma^{-1}\\omega^3(\\sum_{j\\in<\/p>\n

                            Therefore, \"\\bar{g}=e_m([\\phi \u0438 \"\\check{g}_c=\\bar{g}\" with v.s.p.<\/p>\n

                            In order to deceive the verifier, the adversary needs to reveal \"\\gamma\" and \"\\omega,\" then<\/p>\n

                            \"\\mathsf{R}'={[\\gamma^{-1}\\omega\\varphi_\\ell^{-1}\\pmod \u0438 \"\\check{g}_c=\\bar{g}.\"<\/p>\n

                            Let’s recall that, in order to reveal \"\\gamma\" and \"\\omega,\" it’s necessary to find a solution to a specific \"NP\"-complete problem given the known \"\\varphi_u\" and \"s_u.\"<\/p>\n

                            Let a malicious verifier \"V'\" owns the key pair \"\\{\\mathbf{\\acute{y}},\\mathsf{P}_{V'}=[\\mathbf{\\acute{y}}]\\mathsf{G} Let’s evaluate potential risks associated with impersonating the verifier, namely replacing \"V\" with \"V'.\"<\/p>\n

                            Protocol 1<\/h2>\n

                            To impersonate the verifier, it is necessary to find a ECDLP\/DLP solution subject to \"\\mathsf{P}_V\" or \"e_m(\\mathsf{P}_V, Then \"\\mathsf{S}'=[\\mathbf{y}^{-1}\\mathbf{\\acute{y}}\\pmod The relationship between ECDLP and DLP is explained in Appendix A<\/u><\/a>.<\/p>\n

                            Let’s assume that the ECDLP\/DLP solution mentioned above is not known. However, the adversary has access to \"\\mathsf{P}_{V'}\" and is able to impose \"\\mathsf{T}'=[\\phi']\\mathsf{P}_{V'}\" instead of \"\\mathsf{T}\" and \"\\mathsf{S}'=[\\upsilon']\\mathsf{P}_{V'}\" \"\\mathsf{S}\" instead of \"\\mathsf{S},\" where \"\\phi'=\\mathbf{y}^\\phi\\pmod and \"\\upsilon'=\\upsilon with v.s.p. Then \"P\" computes response<\/em> as \"\\acute{g}_a=\\acute{g}_\\ell^{-1},\" \"\\mathsf{R},\" where<\/p>\n

                            \"\\acute{g}_\\ell=e_m([\\upsilon<\/p>\n

                            \"V'\" computes<\/p>\n

                            \"\\acute{g}_b=e_m([\\phi'\\pmod<\/p>\n

                            and \"\\acute{g}_c=\\acute{g}_a\\acute{g}_b.\" Obviously, \"\\acute{g}_c=g_c\" and \"\\acute{g}_c=e_m([\\phi'] with v.s.p.<\/p>\n

                            Let’s assume that the adversary imposes \"\\widetilde{\\mathsf{T}} but doesn’t substitute \"\\mathsf{S},\" then<\/p>\n

                            \"\\acute{g}_b=e_m([\\phi'\\pmod\"\\acute{g}_c=\\acute{g}_b\\acute{g}_a=g^{\\phi'\\upsilon\\mathbf{y}\\gamma\\omega(\\sum_{j\\in<\/p>\n

                            If the final check is performed by \"V,\" then \"\\acute{g}_c=e_m([\\mathbf{y}^{\\phi}\\pmod with v.s.p. If such a check is performed by someone who knows \"\\phi',\" for example \"V',\" then \"\\acute{g}_c=e_m([\\phi'] However, despite the fact that the proof is accepted by \"V',\" impersonation does not take place, since \"V\" is not substituted.<\/p>\n

                            Then \"P\" computes \"\\mathsf{A}'=[\\upsilon and \"V\" computes \"\\mathsf{B}=[\\mathbf{y}^{\\phi}\\pmod<\/p>\n

                            Therefore, \"\\mathsf{A}=\\mathsf{B}'\" with v.s.p. \"V'\" will not be able to reveal the session secret key, since this requires knowing \"\\mathbf{y}.\" However, \"V'\" knows \"\\acute{\\mathbf{y}}\" and can compute \"\\mathsf{B}'=[\\acute{\\mathbf{y}}\\phi'\\pmod but since \"\\acute{\\mathbf{y}}=\\mathbf{y}\" with v.s.p., then \"\\mathsf{A}'=\\mathsf{B}'\" with v.s.p.<\/p>\n

                            Protocol 2<\/h2>\n

                            Let’s suppose that \"{\\varphi_c=\\omega\\alpha^c\\pmod is a ECDLP\/DLP solution subject to\u00a0 \"\\mathsf{P}_c\" or \"e_m(\\mathsf{P}_c, Then \"\\widehat{\\mathsf{S}}'=[\\varphi_c^{-1}\\acute{\\mathbf{y}}\\pmod but in order to compute \"\\widehat{\\mathsf{T}}'=[\\phi'\\gamma\\omega^{-1} where \"\\phi'=\\phi\" with v.s.p., it is necessary to know \"\\gamma\" and \"\\omega.\" As demonstrated above, the revelation of them requires to solve a specific \"NP\"-complete problem under the condition that \"\\varphi_u\" and \"s_u\" are known.<\/p>\n

                            In the light of the explanation given above, further considerations regarding impersonation do not make sense.<\/p>\n

                            Amount of information transmitted<\/h2>\n

                            When a compact representation<\/u><\/a> is used, then, in order to deliver \"\\mathsf{S},\" \"\\mathsf{T},\" \"\\mathsf{R},\" \"g_a\" in Protocol 1<\/strong>, as well as \"\\widehat{\\mathsf{S}},\" \"\\widehat{\\mathsf{T}},\" \"\\mathsf{R},\" \"\\hat{g}_a\" in Protocol 2<\/strong>, one will need to transmit \"3(\\lceil\\log_{2}{p}\\rceil+1)+ bits, where \"\\lambda\" is the bitlength of the binary representation of serial numbers of certificates \"\\{D_V,\\mathsf and \"\\{D_c,\\mathsf{P}_c, and \"k\" is the embedding degree (\"g_a,). Explanations regarding the embedding degree are provided in Appendix A<\/u><\/a>.<\/p>\n

                            If some random subset \"\\mathcal{S}_\\wp\\subseteq\\mathcal{S}\" is involved, then it is necessary to notify \"V\" about the enumerators included in this subset. To do this, \"P\" must additionally transmit \"R(n)\"\u00a0 bits of information, where<\/p>\n

                            <\/figure>\n

                            When \"n\" bits are transmitted, the numerators from \"\\mathcal{S}_\\wp\" correspond to the positions where the binary units are located.<\/p>\n

                            On the other hand, it is reasonable to estimate the amount of information required for the transmission of only protocol messages, since this subset is either fixed or changes slowly over time for most practical applications, although \"V\" must know which numerators are included in \"\\mathcal{S}_\\wp\\subseteq\\mathcal{S},\" and therefore somehow obtain the relevant information. Therefore, it is enough to transmit information about numerators once. When estimating, we can neglect the amount of information that needs to be transmitted to modify such a slowly changing subset.<\/p>\n

                            Computational optimization<\/h2>\n

                            \"\\mathcal{S}\" is fixed in a number of practical applications. For example, when some sets of public keys, used for verification, are assigned to individual structural divisions of a corporation or government agency. In this case, there is no need to report the numerators from \"\\mathcal{S}\" each time, since the set of necessary public keys is predefined.<\/p>\n

                            If you commit \"\\mathcal{S},\" then you can proactively confirm the authenticity, integrity and relevance of public keys \"\\mathsf{P}_{n+1-j},\" \"j\\in\\mathcal{S},\" using corresponding certificates. <\/p>\n

                            Then it’s necessary to compute and publish the point \"\\mathsf{M}=\\sum_{j\\in Then the \"\\ell\"-th prover computes the point \"\\mathsf{K}_\\ell=\\sum_{j\\in\\widetilde{ in advance and stores it in local long-term secret memory. Assuming that Protocol 1<\/strong> is initiated, then in the case of the \"\\ell\"-th prover \"P\" computes \"g_\\ell={e_m([\\upsilon and \"V\" computes \"g_b={e_m([\\mathbf{y}^\\phi\\pmod<\/p>\n

                            The optimization is relevant for both Protocol 1<\/strong> and Protocol 2<\/strong>.<\/p>\n

                            If \"V\" always belongs to a group of registered participants and Protocol 2<\/strong> is initiated, then an optimization is possible that relies on the following rationale.<\/p>\n

                            The embedding degree \"k,\" as well as the field characteristic \"p,\" determine the complexity of the DLP in \"\\mathbb{G}_3.\" For a fixed \"p,\" the larger \"k,\" the higher the complexity of individual pairing, as well as various arithmetic operations in \"\\mathbb{G}_3,\" including discrete exponentiation and multiplicative inversion. Since for Protocol 2<\/strong> the subexponential complexity of finding a DLP solution is not critical, it is reasonable to reduce the complexity of arithmetic operations, as well as reduce the memory resource by using small values of \"k.\"<\/p>\n

                            Conclusions<\/h2>\n

                            Regarding the key security, Protocol 1<\/strong> and Protocol 2<\/strong> are presumably consistent with the basic imperative of post-quantum cryptography<\/em>, where the rationale for security is to prove that an attack on a cryptosystem consists of finding a solution to some problem that is hypothetically intractable on a quantum computer. \"NP\"-complete problems under the condition \"P\\neq fully comply with this statement.<\/p>\n

                            Since the ECDLP\/DLP solution for an arbitrary public key from \"\\mathcal{P}\" does not allow revealing the corresponding private key due to special masking techniques, we assumed that in addition to the solution \"\\varphi_u,\" the private key \"s_u\" is also known. It is demonstrated that even with such assumptions, it is necessary to find a solution to a specific \"NP\"-complete problem to reveal all other private keys.<\/p>\n

                            We emphasize that the choice of numbers \"u=2^{2^w},\" \"u\\in[2,n],\" is limited. There are few such numbers, for example, if we put \"n=2^{16},\" then the numbers from the set \"\\{2, are available. Expansion of this set is unlikely, since groups with the number of participants \"n=2^{32}\" and more are rarely encountered in practice.<\/p>\n

                            Consequently, the adversary’s options are also limited.<\/p>\n

                            It should be noted that Protocol 1<\/strong> allows impersonation with the known ECDLP\/DLP solution. This is because the verifier’s private and public keys do not have additional masking, unlike the keys used in Protocol 2.<\/p>\n

                            The anonymous group identification protocol described and analyzed in this article effectively distinguishes itself by the security level from the functionally similar protocol in this article. This distinction arises because the security of the latter is solely determined by the complexity of finding an ECDLP\/DLP solution.<\/p>\n

                            Final findings<\/h2>\n

                            IDS-compatible anonymous identification protocols for groups have been designed and studied. It is demonstrated that the key security is determined by the complexity of finding a solution to a specific \"NP\"-complete problem.<\/p>\n

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

                            References<\/h2>\n

                            [RST’01] Rivest, Ronald L., Shamir, A., Tauman, Y. «How to leak a secret: Theory and applications of ring signatures.» In \"\\textit{Advances LNCS 3895, (2001) 164-186.<\/p>\n

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

                            [AKS’04] Agrawal, M., Kayal, N., Saxena, N. «PRIMES is in P.» \"\\textit{Annals v.160, (2004) 781-793.<\/p>\n

                            [I’11] \u0418\u0448\u043c\u0443\u0445\u0430\u043c\u0435\u0442\u043e\u0432 \u0428. \u0422. \u041c\u0435\u0442\u043e\u0434\u044b \u0444\u0430\u043a\u0442\u043e\u0440\u0438\u0437\u0430\u0446\u0438\u0438 \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b: \u0443\u0447\u0435\u0431\u043d\u043e\u0435 \u043f\u043e\u0441\u043e\u0431\u0438\u0435. \u2014 \u041a\u0430\u0437\u0430\u043d\u044c: \u041a\u0430\u0437\u0430\u043d. \u0443\u043d-\u0442, 2011. 200 \u0441.<\/p>\n

                            [GJ’79] Garey, M. R.\u00a0 and\u00a0 Johnson, D. S. A Guide to the Theory of \"NP\"-Completeness. W. H. Freeman&Co., New York, NY, 1979.<\/p>\n

                            [G’96] Grover, L. «A fast quantum mechanical algorithm for database search.» Proceedings of \"\\textit{28th (1996) 212-219. https:\/\/arxiv.org\/abs\/quant-ph\/9605043<\/u><\/a>.<\/p>\n

                            [S’97] Shor, Peter W. «Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.» \"\\textit{SIAM v.26, 5, (1997) 1484-1509.<\/p>\n

                            [BGW’05] Boneh, D., Gentry, C. and Waters, B.\u00a0 «Collusion Resistant Broadcast Encryption With Short Ciphertexts and Private Keys.» In \"\\textit{Proceedings LNCS 3621, (2005) 258-275.<\/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\/764470\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

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

                            The identification protocol based on the pairing function, resistant to impersonation and compatible with the instant digital signature (IDS) mode, was studied in this article<\/u><\/a>. This protocol uses prover’s and verifier’s public keys. As a result, there is no anonymity, since certificates including personal data of their owners are issued for the mentioned keys. This article contains a description and analysis of new anonymous identification protocols for groups.<\/p>\n

                            This publication consists of sections where we describe anonymous group identification protocols for two different scenarios, analyze the key security and resistance to impersonation, estimate the amount of information transmitted, and evaluate the optimization of computations and memory resources. At the end of this text, summary and conclusion are specified and formulated.<\/p>\n

                            This publication consists of sections where we describe anonymous group identification protocols for two different scenarios, analyze the key security and resistance to impersonation, estimate the amount of information transmitted, and evaluate the optimization of computations and memory resources. At the end of this text, summary and conclusion are specified and formulated.<\/p>\n

                            The term ‘vanishingly small probability’ (abbreviated as v.s.p.) and the boolean variable as well as public key certificates functions, were all explained in our previous article<\/u><\/a>.<\/p>\n

                            The following practical problem is studied in the fundamental work [RST’01]. Some party for example, a member of the cabinet of ministers (CM), intends to publish incriminating information about the actions of the prime minister. For this purpose, contacts, for example, a journalist from an independent media. In this case, on the one hand, it is necessary to guarantee the anonymity of the source. On the other hand, it’s essential to ensure the reliability of the information provided. From the point of view of the information provided by a member of the CM is considered reliable.<\/p>\n

                            Let’s take a look at possible options.<\/p>\n

                              \n
                            1. \n

                              cannot transmit a message signed with through a digital signature (DS) scheme, since the verification will result in de-anonymization, because\u00a0 personal data is included in the public key certificate. Although this method will certainly convince that the information comes from a member of the CM.<\/p>\n<\/li>\n

                            2. \n

                              If uses anonymizing services, then all identifiers of the sender will be removed from the transmitted message. Therefore, will not be able to verify that the information comes from a member of the CM and won’t consider it reliable.<\/p>\n<\/li>\n<\/ol>\n

                              In [RST’01] a solution has been proposed. Each member of the CM generates a DS using his personal private key, but this DS can only be verified using the personal public keys of all members of the CM, including the witness himself. As a result, is convinced and can also convince a third party that the information comes from the CM, but at the same time remains unknown.<\/p>\n

                              We propose a solution to the problem formulated above through an anonymous identification protocol for groups. The advantage of our solution is that in addition to anonymous identification, can transmit information confidentially using a secure data transfer tunnel. The tunnel (virtual) is accessible by construction, since and are able to independently generate a shared session secret key upon successful identification. Confidentiality is guaranteed by using a symmetric cryptographic scheme.<\/p>\n

                              The anonymous group identification protocol also makes it possible to convince a third party that the information received comes from a member of the CM. This follows from the fact that all public keys involved in verifying the evidence belong to members of the CM, which is easily verified using personal data from the certificates of these keys. Anonymity is based on a simple principle, which can be formulated as follows: \u201cit is reliably known that one is from the group, but it is not known who exactly.\u201d<\/p>\n

                              The use of an anonymous group identification protocol is logically justified in the context of solving a wide range of practical problems for which compatibility with the IDS mode is essential. Some scenarios are described here<\/u><\/a>.<\/p>\n

                              Anonymous identification protocols for groups<\/h3>\n

                              The parameters used below, such as , , , , , are explained in Appendix A<\/u><\/a>.<\/p>\n

                              For the sake of simplicity, we omit details related to the verification of criteria needed for inclusion in the group, as well as the subsequent registration of those participants who meet them. We will proceed from the assumption that such a group has been successfully created.<\/p>\n

                              For participants, represented by a set of numerators\u00a0 the trusted party generates a set of long-term public keys a set of personal private keys of participants as well as a group public key <\/p>\n

                              Setup (Input: . Output: , , ).<\/strong><\/p>\n

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

                                if then it chooses another <\/p>\n<\/li>\n

                              4. \n

                                if then it goes to 3.<\/p>\n<\/li>\n

                              5. \n

                                if then it chooses another <\/p>\n<\/li>\n

                              6. \n

                                if then it goes to 5.<\/p>\n<\/li>\n

                              7. \n

                                if then it goes to 5.<\/p>\n<\/li>\n

                              8. \n<\/li>\n<\/ol>\n

                                The private key is delivered to the -th participant in a private way, for example, using Protocol 3<\/em><\/strong> from this article<\/u><\/a>. A separate certificate is issued indicating the owner\u2019s personal data for each public key from In addition, a single certificate is issued for which establishes the connection between the components of this set with keys from <\/p>\n

                                The setup is performed once<\/u> and ends with the removal of from the local long-term secret memory of party In total, certificates are issued and maintained.<\/p>\n

                                Protocol 1<\/h3>\n

                                Let’s consider the anonymous identification protocol for the case where does not belong to the group of registered participants and differs from the public keys from Let’s suppose that owns a key pair where The certificate is issued for has access to and knows <\/p>\n

                                Let an th participant act as <\/p>\n

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

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

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

                                  proves to that it knows the private key such that and During the proof, and are not revealed. The following steps are performed:<\/p>\n

                                    \n
                                  1. \n

                                    reads the current certificate and checks the DS of the trusted party If then the session ends. If then it chooses (commitment<\/em>), computes (witness<\/em>), checks the condition If then selects a new and re-performs the necessary computations and checks.<\/p>\n<\/li>\n<\/ol>\n

                                      \n
                                    1. \n

                                      reads the current certificate and checks the DS of the trusted party If then the session ends. If then selects and computes (challenge<\/em>). If then selects a new and re-performs the necessary computations and checks. <\/p>\n<\/li>\n

                                    2. \n

                                      checks the integrity, authenticity and relevance of public keys using the appropriate certificates. If relevance is not confirmed or then the current session ends. checks the condition If it’s true, then computes response<\/em> for as where <\/p>\n<\/p>\n

                                      otherwise the session ends.<\/p>\n<\/li>\n

                                    3. \n

                                      verifies the integrity, authenticity and relevance of public keys using the appropriate certificates. If the relevance is not confirmed or then the current session ends. checks the condition If the condition is not met, the session ends. If it’s met, then computes:<\/p>\n<\/p>\n<\/li>\n<\/ol>\n

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

                                      If the identification stage is successfully completed, the parties independently generate 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

                                        Protocol 2<\/h2>\n

                                        Let’s now consider a protocol where belongs to a group of registered participants. Then owns a key pair where and The certificate is issued for <\/p>\n

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

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

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

                                          proves to that it knows the private key such that and During the proof, and are not revealed. The following steps are performed:<\/p>\n

                                            \n
                                          1. \n

                                            reads the current certificate and checks the DS of the trusted party If then the session ends. If then chooses (commitment<\/em>), computes (witness<\/em>), checks the condition If then choses another and re-performs the necessary computations and checks.<\/p>\n<\/li>\n<\/ol>\n

                                              \n
                                            1. \n

                                              reads the current certificate and checks the DS of the trusted party If then the session ends. If then computes chooses and then computes (challenge<\/em>). If then chooses another and re-performs the necessary computations and checks.<\/p>\n<\/li>\n<\/ol>\n

                                                \n
                                              1. \n

                                                checks the integrity, authenticity and relevance of public keys using the appropriate certificates. If relevance is not confirmed or then the current session ends. checks the condition If the condition is met, then computes response<\/em> for as where<\/p>\n<\/li>\n<\/ol>\n

                                                otherwise the session ends.<\/p>\n

                                                  \n
                                                1. \n

                                                  verifies the integrity, authenticity and relevance of public keys using the appropriate certificates. If the relevance is not confirmed or then the current session ends. checks the condition If the condition is not met, the session ends. If it is met, then computes<\/p>\n<\/li>\n<\/ol>\n

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

                                                  If the identification stage is successfully completed, the parties independently generate 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

                                                    Key security<\/h2>\n

                                                    The idea is that the public key is masked using while the private key is masked using where and by construction. This means that the complexity of revealing all with a known ECDLP\/DLP solution for the public key from as well as a known private key from is not less than the complexity of finding a ECDLP\/DLP solution.<\/p>\n

                                                    Let’s consider a particular case. Let us assume that and are known, where is the ECDLP\/DLP solution subject to or Then<\/p>\n

                                                    and Consequently, if and are known, then it is enough to find to reveal all <\/p>\n

                                                    Note that the adversary has additional capabilities. Let and be known such that The adversary’s motivation is that with known and 2″ alt=»u>2″ src=»https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c75\/ded\/48f\/c75ded48f90a63f07c613de0bd3bc1e0.svg» width=»46″ height=»16″\/> (the square root is calculated once if ), it is possible to reveal using the iterative method of taking a square root using the Tonelli-Shanks algorithm of asymptotic complexity [C’06] (section 11.1.5). <\/p>\n

                                                    For example, with known and In general, it is not known how to take the root of an arbitrary degree<\/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-356291","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/356291","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=356291"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/356291\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=356291"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=356291"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=356291"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}