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__. 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.

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.

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.

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__.

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.

Let's take a look at possible options.

cannot transmit a message signed with through a digital signature (DS) scheme, since the verification will result in de-anonymization, because 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.

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.

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.

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.

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: “it is reliably known that one is from the group, but it is not known who exactly.”

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__.

### Anonymous identification protocols for groups

The parameters used below, such as , , , , , are explained in __Appendix A__.

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.

For participants, represented by a set of numerators 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

**Setup (Input: . Output: , , ).**

if then it chooses another

if then it goes to 3.

if then it chooses another

if then it goes to 5.

if then it goes to 5.

The private key is delivered to the -th participant in a private way, for example, using ** Protocol 3** from

__this article__. A separate certificate is issued indicating the owner’s 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

The setup __is performed once__ and ends with the removal of from the local long-term secret memory of party In total, certificates are issued and maintained.

### Protocol 1

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

Let an th participant act as

**Protocol messages. **

**Actions of the parties.**

proves to that it knows the private key such that and During the proof, and are not revealed. The following steps are performed:

reads the current certificate and checks the DS of the trusted party If then the session ends. If then it chooses (

*commitment*), computes (*witness*), checks the condition If then selects a new and re-performs the necessary computations and checks.

reads the current certificate and checks the DS of the trusted party If then the session ends. If then selects and computes (

*challenge*). If then selects a new and re-performs the necessary computations and checks.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*for as whereotherwise the session ends.

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:

Then checks If equal, then the proof is accepted, and rejected otherwise.

If the identification stage is successfully completed, the parties independently generate a shared session secret key in accordance with the following rules:

computes

computes

## Protocol 2

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

*Protocol messages.*

*Actions of the parties.*

proves to that it knows the private key such that and During the proof, and are not revealed. The following steps are performed:

reads the current certificate and checks the DS of the trusted party If then the session ends. If then chooses (

*commitment*), computes (*witness*), checks the condition If then choses another and re-performs the necessary computations and checks.

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*). If then chooses another and re-performs the necessary computations and checks.

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*for as where

otherwise the session ends.

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

Then checks If equal, then the proof is accepted, and rejected otherwise.

If the identification stage is successfully completed, the parties independently generate a shared session secret key in accordance with the following rules:

computes

computes

## Key security

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.

Let's consider a particular case. Let us assume that and are known, where is the ECDLP/DLP solution subject to or Then

and Consequently, if and are known, then it is enough to find to reveal all

Note that the adversary has additional capabilities. Let and be known such that The adversary's motivation is that with known and (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).

For example, with known and In general, it is not known how to take the root of an arbitrary degree in

Brute force attacks for some are listed in __Appendix C__. Frontal attack (Algorithm 1) is not considered optimal, since on average it will take trials, where

Let's suppose that there is a number such that and a factorization is known, are different primes,

Such factorization can be obtained by using, for example, the *number field sieve* *method* or another well-known method [I'11]. Let the set be given. If all are known, then the following representation is true:

Let us enumerate the prime numbers from by integers from to and move to the set

Let's estimate the complexity of the optimized brute force (Algorithm 2). The attack uses the auxiliary sequence The Hamming weight varies in the range from to and the number of trials is limited above by

On average, it takes trials to find

Let's suppose that and Let us recall that by construction, and the following options are also possible:

Let's denote the number of primes in the range as According to Chebyshev's estimates Therefore,

It is well known that but in (1) approximately half of all possible binomial coefficients are summed up and therefore Thus,

The cardinality of the set cannot be controlled if As a result, may be small and the complexity of a brute force, meaning the number of trials will not provide the required security level.

Let's act as follows in order to improve the situation. At the setup stage, let the trusted party randomly select distinct primes from the range and make the set The primality test is performed using the technique from [AKS'04]. For example, if then Then generates a random binary sequence of Hamming weight where and for a given computes:

and

Now the complexity of the brute force mentioned above is limited by the guaranteed value and

In general,

where is a certain function whose modulus tends to zero and can take on both negative and positive values. If then For example, to ensure a -bit security level or higher, it's necessary to choose

The complexity of finding under the condition is equivalent to the well-known -complete problem *Subset Product* [GJ'79] (SP14, p. 224) or, in another way, *Product of Dimensions* [GJ'82] (MP 14, page 283). -completeness is proven by reducing another -complete problem known as *Exact Coverage by 3-Sets* [GJ'82] (TP-3, page 73) to this problem. It should be noted that MP 14 is a problem with numerical parameters and -completeness does not exclude solving this problem using a pseudopolynomial time complexity algorithm under the condition [GJ'82] (section 4.2 on page 117, commentary to MP 14 on page 283), which depends on and Obviously, the existence of an algorithm of such complexity provides the adversary with additional opportunities. However, this drawback is eliminated if chooses primes from the range and the value of is such that it compensates for the decrease in security level due to the existence of a pseudo-polynomial complexity algorithm. The value of is limited below by the security level. Then can choose an arbitrarily large subject to a given security level as a necessary condition. The set 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 With -bit security level, the length of prime numbers will vary from to bits.

Grover's algorithm [G'96] allows to find under the condition in trials on a quantum computer with qubits. If a brute force on a quantum computer seems realistic, then it's necessary to choose such a value of that it could compensate for the decrease in security as a result of using Grover's algorithm. For example, a security level of bits inclusive and higher is provided with

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 is limited by some polynomial of the input size.

Let's note that the set is intended solely for obtaining on the basis of which are then computed. Once all necessary computations are complete, removes from local long-term memory.

## Why does it work

It's worth noting that the anonymous group identification protocol is based on the ideas revealed in [BGW'05].

Let's dive inside it and look at the function which appears in the exponent of when and as well as and being computed.

The function is continuous, and, for analysis purposes, it is enough to look at the Table #1 containing values for some enumerators from the integer interval

Let and According to the Table 1, is located on the main diagonal and meet the criteria by construction and therefore

Since lacks the th numerator, but contains the numerator then

In 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 The asymptotic estimate for the number of such subsets is These subsets may either intersect or not.

## Example

Let's suppose that and There is some subset such that

Let then Therefore,

## Preliminary analysis

Let's suppose that the adversary knows and is a ECDLP/DLP solution subject to or Then in **Protocol 1** the adversary on behalf of computes *witness* as Moreover, computes *response* as

where

In its turn, computes

Therefore, and with v.s.p.

In order to deceive the verifier, the adversary needs to reveal and then

and

In **Protocol 2** *witness* and *response* are computed as and respectively, where

computes

Therefore, и with v.s.p.

In order to deceive the verifier, the adversary needs to reveal and then

и

Let's recall that, in order to reveal and it's necessary to find a solution to a specific -complete problem given the known and

Let a malicious verifier owns the key pair Let's evaluate potential risks associated with impersonating the verifier, namely replacing with

## Protocol 1

To impersonate the verifier, it is necessary to find a ECDLP/DLP solution subject to or Then The relationship between ECDLP and DLP is explained in __Appendix A__.

Let's assume that the ECDLP/DLP solution mentioned above is not known. However, the adversary has access to and is able to impose instead of and instead of where and with v.s.p. Then computes *response* as where

computes

and Obviously, and with v.s.p.

Let's assume that the adversary imposes but doesn't substitute then

If the final check is performed by then with v.s.p. If such a check is performed by someone who knows for example then However, despite the fact that the proof is accepted by impersonation does not take place, since is not substituted.

Then computes and computes

Therefore, with v.s.p. will not be able to reveal the session secret key, since this requires knowing However, knows and can compute but since with v.s.p., then with v.s.p.

## Protocol 2

Let's suppose that is a ECDLP/DLP solution subject to or Then but in order to compute where with v.s.p., it is necessary to know and As demonstrated above, the revelation of them requires to solve a specific -complete problem under the condition that and are known.

In the light of the explanation given above, further considerations regarding impersonation do not make sense.

## Amount of information transmitted

When a __compact representation__ is used, then, in order to deliver in **Protocol 1**, as well as in **Protocol 2**, one will need to transmit bits, where is the bitlength of the binary representation of serial numbers of certificates and and is the embedding degree (). Explanations regarding the embedding degree are provided in __Appendix A__.

If some random subset is involved, then it is necessary to notify about the enumerators included in this subset. To do this, must additionally transmit bits of information, where

When bits are transmitted, the numerators from correspond to the positions where the binary units are located.

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 must know which numerators are included in 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.

## Computational optimization

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 each time, since the set of necessary public keys is predefined.

If you commit then you can proactively confirm the authenticity, integrity and relevance of public keys using corresponding certificates.

Then it's necessary to compute and publish the point Then the -th prover computes the point in advance and stores it in local long-term secret memory. Assuming that **Protocol 1** is initiated, then in the case of the -th prover computes and computes

The optimization is relevant for both **Protocol 1** and **Protocol 2**.

If always belongs to a group of registered participants and **Protocol 2** is initiated, then an optimization is possible that relies on the following rationale.

The embedding degree as well as the field characteristic determine the complexity of the DLP in For a fixed the larger the higher the complexity of individual pairing, as well as various arithmetic operations in including discrete exponentiation and multiplicative inversion. Since for **Protocol 2** 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

## Conclusions

Regarding the key security, **Protocol 1** and **Protocol 2** are presumably consistent with the basic imperative of *post-quantum cryptography*, 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. -complete problems under the condition fully comply with this statement.

Since the ECDLP/DLP solution for an arbitrary public key from does not allow revealing the corresponding private key due to special masking techniques, we assumed that in addition to the solution the private key is also known. It is demonstrated that even with such assumptions, it is necessary to find a solution to a specific -complete problem to reveal all other private keys.

We emphasize that the choice of numbers is limited. There are few such numbers, for example, if we put then the numbers from the set are available. Expansion of this set is unlikely, since groups with the number of participants and more are rarely encountered in practice.

Consequently, the adversary's options are also limited.

It should be noted that **Protocol 1** 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.

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.

## Final findings

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 -complete problem.

The text of the article in pdf format can be downloaded here.

## References

[RST'01] Rivest, Ronald L., Shamir, A., Tauman, Y. "How to leak a secret: Theory and applications of ring signatures." In LNCS 3895, (2001) 164-186.

[C'06] Cohen, H., Frey, G., Avanzi, R., Doche, C., Lange, T., Nguyen, K., Vercauteren, F. Chapman and Hall/CRC, 2006.

[AKS'04] Agrawal, M., Kayal, N., Saxena, N. "PRIMES is in P." v.160, (2004) 781-793.

[I'11] Ишмухаметов Ш. Т. Методы факторизации натуральных чисел: учебное пособие. — Казань: Казан. ун-т, 2011. 200 с.

[GJ'79] Garey, M. R. and Johnson, D. S. A Guide to the Theory of -Completeness. W. H. Freeman&Co., New York, NY, 1979.

[G'96] Grover, L. "A fast quantum mechanical algorithm for database search." Proceedings of (1996) 212-219. __https://arxiv.org/abs/quant-ph/9605043__.

[S'97] Shor, Peter W. "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer." v.26, 5, (1997) 1484-1509.

[BGW'05] Boneh, D., Gentry, C. and Waters, B. "Collusion Resistant Broadcast Encryption With Short Ciphertexts and Private Keys." In LNCS 3621, (2005) 258-275.