ENCRY 15 авг 2021 в 14:00

Private party protocol: how to distinguish friends and foes using cryptographic tools

12 мин

1.2K

Информационная безопасность*Криптография*Сетевые технологии*

Туториал

ENCRY presents a new interactive identification protocol aimed at controlling the access of selected users to various resources.

Close your eyes and imagine Nice, a luxurious estate whose extravagant owner throws epic parties with jazz and fireworks every weekend.

To attend such a party is a lot of the elite. Invitations are sent out in advance, and guests do not know the names of other invited persons. The owner of the estate, the mysterious Jay Gatsby, an eager luxury-lover, values privacy so much that he is not ready to entrust the list of invitees to anyone, not even his buttress. Moreover, the owner of the estate would like the guests not to reveal their names when entering the property. After all, there may be the mayor of the city, or the chief prosecutor among them, and they would like to keep their visit secret. Unfortunately, the owner of the estate himself is so busy that he cannot independently check each guest at the entrance, especially since there are several access roads to his house. How could he solve this problem?

Fortunately for Gatsby, his friend Albert, a mathematician and cryptographer, advised him a solution. Using a special cryptographic protocol, he found the way to distinguish friends and foes based on the group public key and personal secret keys for each invitee. Gatsby, as an organizer, has the right to change the invite list and the group public key, accordingly. Furthermore, Albert developed a mobile application with customized role-based functionality. Conventionally, such settings can be designated as the “Gatekeeper”, “Guest” and “Organizer” operating modes. For example, the application with the “Gatekeeper” role is passed to the gatekeepers, as well as to everyone else who is responsible for checking guests. This role supposes that one is allowed to distinguish an invitee from an outsider. Accordingly, the “Guest” role allows one to prove that she is invited. The roles of each person are applied by Gatsby himself.

As a big fan of original ideas, Gatsby agreed to try out the new technology at the next party. He switched the mobile application to the “Organizer” mode and entered the list of invitees. As a result, the application automatically generated a group public key, and then, using the secret Telegram chat, it sent a copy of the group public key with the “Guest” setting together with a personal secret key to each of the invitees.

The coveted Friday evening comes. Lines of Lamborghinis, Bentleys and Bugattis are heading to the estate. Approaching the entrance, guests use a mobile application that stores a secret key to prove that they are invited. If the protocol the mobile application is based on allows access, then the gates are opened and the car with the guests enters the estate. This is how Gatsby's guests get to the party without revealing their identity even to gatekeepers.

The 21st century is the era of instant messaging and quick interaction. The vast world shrunk down to the size of a computer or smartphone. We are much faster and easier to contact people living on other continents, we can see them in the same virtual space. But new technologies led to the emergence of various challenges. One of them is the need to find new ways to define friends and foes in an environment where communication is conducted online. This is exactly what problem the mobile app created by the mathematician in our fictional story about Gatsby is designed to solve.

You probably already guessed that we will talk about an identification protocol based on asymmetric cryptography. We will not talk about what secret and public keys are and how they are created. This information can be easily found in any cryptography basics book. And if you are reading this text, then most likely you have basic knowledge in the field of cryptography at least at the level of general concepts. Let's pay attention to the fact that in our identification protocol we are talking about one group public key and a certain number of personal secret keys, and not about pair keys, when each unique secret key has its own public key.

Our development, an interactive identification protocol, is based on a well-known cryptographic primitive that is elliptic curve pairing. It has many applications.

Be careful! Elliptic curves ahead!

Elliptic curve cryptosystems are used in many widespread technologies such as TLS, PGP, and SSH, and in newly emerging decentralized systems such as cryptocurrencies. The Discrete Logarithm Problem DLP, as well as a related intractable problem known as the Elliptic Curve Discrete Logarithm Problem ECDLP are the key points in this context.

To understand what these problems are, you need to be familiar with such concepts as a finite field, multiplicative and additive group, subgroup, and their order. We will not delve into this topic, just recall that the presence of a multiplicative and additive group, as well as the existence of an element that is inverse in multiplication and opposite in addition, provided that the mentioned arithmetic operations are commutative, defines a finite field. The number of elements in a group, or its cardinality, is called the order of the group. Finally, the associative and distributive laws apply to the elements of the group.

It is important to note here that there is the concept of a generator both in the multiplicative and additive group. For example, in a multiplicative group, this is an element that, when successively raised to a power, runs through all the elements of the group. Note that a generator does not exist in every group, but it always exists in the group of points of an elliptic curve, as well as in multiplicative and additive groups over some finite field.

Let's go back to DLP. Let a finite field and some element of this field be given. Furthermore, the generator is known. By construction, z=x^y. In this case, DLP is to find with given and

When we say brute-force attack, we mean calculating z'=x^i for different and comparing the result with Thus, if z=z’, then i=y.

Currently, there are various methods for solving DLP that can provide some gain over a brute-force attack. These advanced DLP solutions have so-called subexponential complexity. It is clear that the higher the order of the group, the higher the complexity of any attack.

Here it is necessary to take a step aside and note that since the order of the group is a composite number, an effective method to solve DLP is a divide-and-conquer algorithm when a problem is broken into two or more sub-problems until it becomes simple enough to be solved. According to group theory, the order of a subgroup is a divisor of the order of the group Lagrange′stheorem. In other words, if the order of the group is a composite number, then there is always a subgroup of prime order.

But when the order of the group is a prime number, then the solution based on the divide-and-conquer algorithm does not work. This means that, in order to preserve the exponential complexity of the DLP solution in the case of a brute-force attack, the order must be a prime number and the group must contain a subgroup of large prime order.

Security claim is the key factor to define how large the order of the subgroup should be. However, as we mentioned above, it is possible to launch an attack of subexponential complexity. Then it is obvious that such an order should neutralize the gain from the use of subexponential methods for solving DLP. Thus, the task is to select a group that contains a large dependingonsecurityclaim prime-order subgroup.

Cryptographic systems based on elliptic curves are considered more resistant because of ECDLP as a computational hardness assumption. The reason is that for ECDLP it is still unknown a solution of subexponential complexity. But it turned out that the ECDLP solution can be reduced to the DLP solution, and this problem is known to be solved with subexponential complexity. In order to reduce the ECDLP solution to DLP we can use bilinear mapping, or pairing.

Let's denote a finite field of characteristic p>3 by $\mathbb{F}_p.$ The equation of an elliptic curve over $\mathbb{F}_p$ is y^2=x^3+ax+b. Here a, b, x and belong to $\mathbb{F}_p.$ Each point of the curve is specified by a pair of coordinates and that satisfy the above equation. The points of the elliptic curve over $\mathbb{F}_p$ form an additive group, which is finitely generated as it is proved by the Mordell-Weil theorem. Choose and to obtain a subgroup of some prime order of the group of points of an elliptic curve. The group operation assumes the presence of a special point, the so-called point at infinity $\infty,$ such that for an arbitrary point $\mathsf{Q}$ it is true that $\mathsf{Q}+\infty=\infty+\mathsf{Q}=\mathsf{Q}.$ There are known efficient methods for adding and doubling points.

Let an elliptic curve be given over $\mathbb{F}_p.$ $\mathbb{G}_1$ is a subgroup of prime order of the group of points of an elliptic curve with generator $\mathsf{G}_1.$ There are finite fields $\mathbb{F}_{p^k},$ where k>1 is a natural number. Let $\mathbb{G}_3$ be a subgroup of prime order of the multiplicative group $\mathbb{F}^*_{p^k}$ with generator for some We call symmetric such a pairing when $e_m:\mathbb{G}_1\times\mathbb{G}_1\mapsto\mathbb{G}_3.$ There is also an asymmetric pairing $\hat{e}_m:\mathbb{G}_1\times\mathbb{G}_2\mapsto\mathbb{G}_3,$ where $\mathbb{G}_1=\langle\mathsf{G}_1\rangle,$ $\mathbb{G}_2=\langle\mathsf{G}_2\rangle$ are different subgroups of prime order

Let's introduce the scalar product for points from $\mathbb{G}_1.$ This is an operation as $\mathsf{Q}=[\ell]\mathsf{G}_1$ such that

$\mathsf{Q}=\underbrace{\mathsf{G}_1+\mathsf{G}_1+\ldots+\mathsf{G}_1}_{\ell}$ and $[-\ell]\mathsf{G}_1=[\ell](-\mathsf{G}_1), [0]\mathsf{G}_1=\infty,$

where $0\leqslant|\ell|\leqslant m-1.$

Let $\ell=a+b.$ $\mathsf{Q}=[a]\mathsf{G}_1+[b]\mathsf{G}_1=[\ell]\mathsf{G}_1.$ $[c]\mathsf{Q}=[c\ell]\mathsf{G}_1=[ca+cb]\mathsf{G}_1.$

Example. Let's say $\ell=151_{10}=10010111_2.$ Then $\mathsf{Q}=[151]\mathsf{G}_1=[2^7]\mathsf{G}_1+[2^4]\mathsf{G}_1+[2^2]\mathsf{G}_1+[2^1]\mathsf{G}_1+[2^0]\mathsf{G}_1.$

Let's take the point $\mathsf{G}_1$ $(1001011{\color{red}{1}}_2).$
Duplicate $\mathsf{G}_1$ and get $[2]\mathsf{G}_1$ $(100101{\color{red}{1}}1_2),$ $\Sigma_1=[2]\mathsf{G}_1+\mathsf{G}_1.$
Duplicate $[2]\mathsf{G}_1$ and get $[2^2]\mathsf{G}_1$ $(10010{\color{red}{1}}11_2),$ $\Sigma_2=[2^2]\mathsf{G}_1+\Sigma_1.$
Duplicate $[2^2]\mathsf{G}_1$ and get $[2^3]\mathsf{G}_1$ $(1001{\color{red}{0}}111_2).$
Duplicate $[2^3]\mathsf{G}_1$ and get $[2^4]\mathsf{G}_1$ $(100{\color{red}{1}}0111_2),$ $\Sigma_3=[2^4]\mathsf{G}_1+\Sigma_2.$
Duplicate $[2^4]\mathsf{G}_1$ and get $[2^5]\mathsf{G}_1$ $(10{\color{red}{0}}10111_2).$
Duplicate $[2^5]\mathsf{G}_1$ and get $[2^6]\mathsf{G}_1$ $(1{\color{red}{0}}010111_2).$
Duplicate $[2^6]\mathsf{G}_1$ and get $[2^7]\mathsf{G}_1$ $({\color{red}{1}}0010111_2),$ $\Sigma_4=[2^7]\mathsf{G}_1+\Sigma_3.$

The pairing of points $\mathsf{S}$ and $\mathsf{Q}$ can be represented as $e_m(\mathsf{S}, \mathsf{Q})=g^{cd\pmod m},$ where $\mathsf{S}=[c\pmod m]\mathsf{G}_1$ and $\mathsf{Q}=[d\pmod m]\mathsf{G}_1$ and $g^{cd\pmod m}$ are some elements of $\mathbb{G}_3.$ Here $\mathsf{G}_1$ and are generators in $\mathbb{G}_1$ and $\mathbb{G}_3,$ respectively, with and belonging to $\mathbb{F}^*_m.$

There are several known types of pairings, for example, Weil pairing and Tate-Lichtenbaum pairing. The second one is more often used in practical applications. Symmetrical pairing has the following properties:

Bilinearity.
Non-degeneracy.
Computability.

This raises the question. Why should one use cryptosystems on elliptic curves, if ECDLP can be reduced to a DLP? After all, this path can be chosen not for constructive purposes, but, for example, to carry out an attack. Over time, it became clear that such a reduction is not true for all curves. For example, supersingular curves and curves with a single trace are characterized by low security level, since the convergence method allows solving DLP in subexponential or even linear time. Therefore, these curves were rejected as the basis for cryptosystems design. There are known elliptic curves with special properties, using which does not lead to a decrease in security level due to the existence of a bilinear mapping.

Structurally, the function $e_m(\cdot, \cdot),$ in the form of which pairing can be represented, works as a one-way function. The function is easy to calculate, but if it concerns inversion, namely, restoring the original pair of points from $\mathbb{G}_1$ by an existing element from $\mathbb{G}_3,$ one needs to solve a problem with exponential complexity.

Our private party protocol, surpassing in a number of indicators the well-known protocols developed using similar mathematical tools, is designed on the assumption of such a choice of parameters that DLP and ECDLP have comparable computational complexity.

In our example with the Gatsby party, the gatekeeper is the verifier (actor $\texttt{V}$ ) and the guest is the prover (actor $\texttt{P}$ ). $\texttt{P}$ tries to convince $\texttt{V}$ that she is the invited guest. To this end, she provides $\texttt{V}$ with some proof. Knowing the secret means belonging to the local community of registered members. $\texttt{V}$ uses the group public key to validate the proof, then either accepts or rejects the submitted proof. Returning to our example of the Gatsby party, the gatekeeper ( $\texttt{V}$ ) either sees “accept” on the smartphone screen if the proof is true, or “deny” otherwise.

If $\texttt{P}$ truly has a secret that was taken into account when calculating the group public key, i.e. she is included in the invite list, then with the overwhelming probability she will be able to convince $\texttt{V}$ that she is invited and that the gatekeeper will open the gate. If $\texttt{P}$ does not have the personal secret key or does, but was excluded from the invite list, then $\texttt{V}$ will open the gate with negligible probability.

Important: during the proof no information about the invitee and his secret is disclosed.

Let's take a look inside the protocol and see how it works. The identification protocol consists of one and a half rounds. Round is a message exchange in which each party transmits one message. This is similar to the exchange of punches in boxing.

❶ $\texttt{P} \longrightarrow \texttt{V} : witness$

❷ $\texttt{P} \longleftarrow \texttt{V} : challenge$

❸ $\texttt{P} \longrightarrow \texttt{V} : response$

During the one-time implementation of our protocol session, $\texttt{P}$ transmits two messages, and $\texttt{V}$ transmits only one message. Each individual session consists of three activity cycles $\texttt{P}\stackrel{1}{\rightarrow}\texttt{V}\stackrel{2}{\rightarrow}\texttt{P}\stackrel{3}{\rightarrow}\texttt{V}.$

Let $\Omega^*$ be the set of all sequences of letters of arbitrary length in a finite alphabet $\Omega$ set of letters.

Set $\hslash^i(x)=\overbrace{\hslash(\hslash(\ldots\hslash(\hslash(x))\ldots)}^{i~\hbox{times}})$ and $\hslash^i(x)=\hslash(\hslash^{i-1}(x)),$ $i\geqslant1, \hslash^0(x)=x,$

where $\hslash(\cdot)$ is a standard cryptographic hash function from FIPS PUB 180-4, and secret $\beta\in_R\!(0, m-1].$ There are $1\leqslant n<m$ members. Each participant has a unique identifier $\mathbf{a}_i\in\Omega^*.$ Let's represent the identifiers as a set $\mathbf{X}=\{\mathbf{x}_1, \ldots, \mathbf{x}_n\}$ such that $\mathbf{x}_i=\hslash(\mathbf{a}_i\|\hslash^i(\beta)),$ where $\mathbf{a}_i\in\Omega^*, \mathbf{x}_i\in\{0,1\}^{\lceil\lg{m}\rceil}, i=\overline{1, n}.$ The described method of forming $\mathbf{X}$ guarantees that all $\mathbf{x}_i$ are different and even if $\mathbf{a}_i=\mathbf{a}_j,$ then $x_i\neq x_j$ for $i\neq j, 1\leqslant i, j\leqslant n.$

We will proceed from the assumption that there is a trusted party in our fictional story with the party, this is Gatsby, the owner of the estate, which is responsible for the selection of parameters, pre-calculations and data distribution.

$\beta, n, p, m, \mathbb{G}_1, \mathbb{G}_3, e_m(\cdot, \cdot)$ are given. Then, at the setup, performs the following actions:

Based on $\mathbf{a}_i, \beta$ and using $h^{i}(\cdot),$ forms the set $\mathbf{X}=\{\mathbf{x}_1, \ldots, \mathbf{x}_n \}, i=\overline{1, n}.$
Computes $\Gamma={\prod_{i=1}^n}\mathbf{x}_i\pmod m.$
Secretly transfers to -th participant $\{\mathbf{x}_i, \mathsf{P}_i=[\beta\widehat\Gamma_i\pmod m]\mathsf{G}_1\},$ where $\widehat\Gamma_i=\mathbf{x}_i^{-1}\Gamma\pmod m,$ $i=\overline{1, n}.$
Secretly computes and then publishes the group public key $\tilde{g}=e_m([\beta\Gamma\pmod m]\mathsf{G}_1, \mathsf{G}_1)=g^{\beta\Gamma\pmod m}.$ It is assumed that the authenticity and integrity of $\tilde{g}$ is guaranteed by a digital signature. If ${\rm{Sign}}(\cdot,\cdot)$ and ${\rm{Verify}}(\cdot,\cdot,\cdot)$ are functions for generating and verifying digital signatures, then a certificate $\{D_T,\tilde{g},\Im_{\tilde{g}}\}$ is issued, where $\Im_{\tilde{g}}\Leftarrow{\rm{Sign}}(\mathscr{H}(\tilde{g}\|D_T),S),$ $\mathscr{H}(\cdot)$ is a cryptographic hash function, is a secret key of the trusted party , and is information about Before using $\tilde{g}$ , one needs to check the validity of $\Im_{\tilde{g}}$ using $\mathfrak{B}\Leftarrow{\rm {Verify}}(\mathscr{H}(\tilde{g}\|D_T), \Im_{\tilde{g}}, P),$ where is the paired public key of the trusted party The variable $\mathfrak{B}$ is if $\Im_{\tilde{g}}$ is valid, or otherwise. If is not a certification authority under the current public key infrastructure, then an appropriate certificate is issued for
Keeps $\beta$ secret.

Messages. Confirmation/rejection of the fact of possession knowledge of $\mathbf{x}_i{\in}\mathbf{X}.$

❶ $\texttt{P} \longrightarrow \texttt{V} : \mathsf{P}_w=[\upsilon]\mathsf{P}_i=[\upsilon\beta\widehat{\Gamma}_i\pmod m]\mathsf{G}_1$

❷ $\texttt{P} \longleftarrow \texttt{V} : \mathsf{P}_c=[\phi]\mathsf{G}_1$

❸ $\texttt{P} \longrightarrow \texttt{V} : g_1=e_m([\upsilon+\mathbf{x}_i\pmod m]\mathsf{P}_i,\mathsf{P}_c)=g^{\phi\beta(\upsilon\widehat{\Gamma}_i+\Gamma)\pmod m}$

Actions. $\texttt{P}$ is trying to convince $\texttt{V}$ that she owns knows $\mathbf{x}_i\in\mathbf{X}.$ To achieve this goal,

$\texttt{P}$ selects ${\upsilon\in_R\!(0, m-1]}$ (commitment) and checks the condition ${([\upsilon]\mathsf{P}_i\neq\infty)\land([\upsilon+\mathbf{x}_i\pmod m]\mathsf{P}\neq\infty)}.$ If the condition is met, then it evaluates the point $\mathsf{P}_w$ (witness), otherwise selects a new $\upsilon.$
$\texttt{V}$ selects $\phi\in_R\!(0, m-1]$ and evaluates point $\mathsf{P}_c$ (challenge).
$\texttt{P}$ checks that $\mathsf{P}_c\neq\infty$ and then evaluates (response).
$\texttt{V}$ reads a valid certificate $\{D_T,\tilde{g},\Im_{\tilde{g}}\}$ from memory and verifies the signature $\Im_{\tilde{g}}$ using $\mathfrak{B}\Leftarrow{\rm{Verify}}(\mathscr{H}(\tilde{g}\|D_T),\Im_{\tilde{g}},P),$ where is the public key If $(\mathfrak{B}=True)\land(\mathsf{P}_w\neq\infty),$ then checks $\tilde{g}^\phi g_2\stackrel{?}{=}G_1,$ where $g_2=e_m(\mathsf{P}_w,\mathsf{P}_c).$ Equality confirms the fact of possession (knowledge) of $\mathbf{x}_i\in\mathbf{X},$ otherwise the proof is rejected.

From the field of application point of view, the developed protocol is similar to the Zero-knowledge Proof ZKP protocols. They are also designed to solve a similar problem: using interaction, $\texttt{P}$ tries to convince $\texttt{V}$ that she knows some secret that is not revealed during the protocol. Like all other identification protocols, ZKP protocols consist of one and a half rounds one and a half rounds = session. In the case of ZKP protocols, a single session is repeated many times. The more repetitions, the less chance of cheating. But from a practical point of view this is a disadvantage. Multiple repetition of sessions leads to computational costs, memory consumption and loading of communication channels.

One of the most famous ZKP protocols is the Feige-Fiat-Shamir protocol developed in 1986 by Uriel Feige, Amos Fiat, and Adi Shamir. During this protocol, $\texttt{P}$ proves to $\texttt{V}$ that she possesses secret information without revealing this information. Based on the difficulty in determining a square root with composite modulus including two large prime factors, when the modulus' factorization is unknown. The Guillou-Quisquater protocol is another ZKP protocol. It is a variation of the earlier Fiat-Shamir protocol designed in 1988 by Louis Guillou and Jean-Jacques Quisquater. Like the Fiat-Shamir protocol, it is based on the difficulty in computing square root modulo a large composite number. The main differences are:

no repetition of the session is required;
a small amount of memory is needed for storing user secrets.

Known identification protocols are also the Schnorr authentication protocol, the Brickell-McCurley and Okamoto protocols.

So, why should we create another identification protocol if the problem is solved by already existing identification protocols? The key idea is that our protocol solves a problem that is different from the one that is solved by known identification protocols. Namely, it allows making a decision on the principle of “friend or foe” for the local community of registered participants with a guarantee of their anonymity. Furthermore, it has a relatively low computational complexity. It is more correct to compare our protocol with Nguyen's protocol Nguyen, L. “Accumulators from Bilinear Pairings and Applications.” In Topics in Cryptology –CT-RSA'05, LNCS 3376, (2005 275-292), since that protocol uses a similar math. If we compare these two protocols in terms of the number of pairings and scalar products involved, then the computational complexity of our protocol is an order of magnitude lower than Nguyen's one.

Proven properties of our protocol:

Witness Indistinguishable (WI). The WI property means that an attacker cannot determine which secret the current witness corresponds to, even if she knows all these secrets. If each secret has its own set of witnesses, then the WI-property guarantees the statistical/polynomial indistinguishability of these sets. In this context, polynomial indistinguishability means that, despite the discrepancy in statistical characteristics, these differences cannot be detected using the polynomial complexity algorithm. An attentive reader here will probably exclaim: “Differences can be detected using the algorithm of superpolynomial complexity!” To this we answer: sure, but the attacker does not have the resources necessary to perform such time- and space-consuming computation.
Witness Hiding (WH). An attacker cannot independently compute a new witness that is relevant in the context of the protocol being executed. The probability that an attacker can obtain such a witness is no higher than the probability of guessing the secret. The attacker is forced either to guess the witness or to perform some computational efforts, the complexity of which is not less than the complexity of the disclosure of the secret.

In basic research Feige, U. and Shamir, A. “Witness Indistinguishable and Witness Hiding Protocols.” In Proceedings of 22nd STOC, ACM Press, (1990 416–426) the WH property is considered as an alternative to the ZKP property. If an attacker gains access to transcriptions of various sessions of the ZKP protocol, which were carried out at the same time, then she gets the opportunity to interfere and influence the course of their execution. The WH-property, in contrast to ZKP, guarantees that the attacker does not extract any meaningful information from the transcriptions of the protocol sessions and therefore will not be able to impersonate the prover in our example, the invited guest.

Altogether, an interactive identification protocol with pairings and scalar products with proven WI and WH properties is a new solution that reduces computational complexity and memory to storage keys (recall that participants do not need private public key certificates). Our protocol, unlike ZKP, does not require multiple sessions to minimize the probability of cheating. This was achieved thanks to the proven properties of WI and WH. The advantage of the new protocol is that the amount of memory for storing the group public key, as well as the number of messages and the amount of information transmitted, do not depend on the capacity of the local community.

The protocol we developed can be used even on smartphones, and this paves the way for the development of new mobile applications with an adequate security level.

Теги:

Хабы:

Private party protocol: how to distinguish friends and foes using cryptographic tools

Be careful! Elliptic curves ahead!

Публикации

Истории

Работа

Ближайшие события