🛁 🧕 👩🏿‍💼 Private Party Protocol: How to Distinguish Yours and Foes with Cryptographic Tools 🏪 🔽 🚘

ENCRY talks about a new interactive authentication protocol that allows you to control the access of selected users to various resources.

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

To get to such a party is the lot of the elite. Invitations are sent out in advance, and guests do not know who was invited except them. The owner of the estate, the mysterious Jay Gatsby, a lover of luxury, values privacy so much that he is not ready to entrust the list of invitees to anyone, not even the buttress. Moreover, the owner of the estate would like the guests not to divulge their name when entering the property. Really, after all, among them may be the mayor of the city, and the chief prosecutor, 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 to be?

Luckily for Gatsby, his friend Albert, a mathematician by training and a cryptographer by vocation, suggested a clever way for him. He figured out how, using a special protocol, to make a decision on the principle of "friend / foe" 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, accordingly, the group public key. In addition, Albert has developed a mobile application with customization of role-based functionality. Conventionally, such settings can be designated as the "Gatekeeper", "Guest" and "Organizer" operating modes. For example, an application with the "Gatekeeper" setting is passed to the gatekeepers, as well as to everyone else who is responsible for checking guests. It is clear that this setting allows you to distinguish the invitee from the outsider.Accordingly, the "Guest" setting allows you to prove that you are invited. The decision about this or that personal setting is made by Gatsby himself.

As a fan of original ideas, Gatsby agreed to try the new technology at a nearby 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 chat of the Telegram messenger, addressed a copy with the “Guest” setting along with a personal secret key to each of the invitees.

The coveted Friday evening has come. Lines of Lamborghini, Bentley and Bugatti were drawn to the estate. Approaching the gate that opens the entrance to the estate, guests use a mobile application that stores a secret key to prove that they are invited. If the protocol on the basis of which the mobile application works 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 the gatekeepers.

The 21st century is the era of instant messaging and quick interaction. The vast world has 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 technology challenges have also emerged. One of them is the need to find new ways to define “ours” or “foes” in an environment where communication is conducted online. This is exactly the problem that a mobile app created by a mathematician friend in our fictional story about Gatsby solved.

You probably already guessed - we will talk about an identification protocol based on asymmetric cryptography methods. 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 textbook. 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. You can check your knowledge using our test on Telegram ( @QuizBot quiz: VBwaO0d9). 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 secret keys, and not about pair keys, when each unique secret key has its own public key. If you need to remember the methods of asymmetric cryptography, then we advise you to read the previous text on our blog.

We will talk about our development - an interactive identification protocol . The protocol is based on a well-known cryptographic primitive - pairing points of an elliptic curve. It is used in many applications for encryption and electronic digital signatures.

Caution elliptic curves!

, TLS, PGP SSH, , . (Discrete Logarithm Problem, DLP), , (Elliptic Curve Discrete Logarithm Problem, ECDLP).

, , , , , , . , , , . , , . .

, , , . , , . , , , .

DLP.

$z$ .

$x$ .

$z=x^y$ . DLP

$y$

$z$

$x$ .

« »,

$z’=x^i$

$i$

$z$ . ,

$z=z’$ ,

$i=y$ .

DLP, . DLP . , , .

, — , DLP « ». — , . , . , , . — , . , DLP . — . , , . , DLP. , , ( ) .

? , , ECDLP. , ECDLP . , ECDLP DLP, , , . ECDLP DLP , .

$p>3$

$\mathbb{F}_p$ .

$\mathbb{F}_p$

$y^2=x^3+ax+b$ .

$a, b, x$

$y$

$\mathbb{F}_p$ .

$x$

$y$ , .

$\mathbb{F}_p$ , -.

$a$

$b$ , . ,

$\infty$ , ,

$\mathsf{Q}$

$\mathsf{Q}+\infty=\infty+\mathsf{Q}=\mathsf{Q}$ . .

$\mathbb{F}_p$ .

$\mathbb{G}_1$

$m$

$\mathsf{G}_1$ .

$\mathbb{F}_{p^k}$ ,

$k>1$ — .

$\mathbb{G}_3$ —

$m$

$\mathbb{F}^*_{p^k}$

$g$

$k$ .

$e_m:\mathbb{G}_1\times\mathbb{G}_1\mapsto \mathbb{G}_3$ .

$\hat{e}_m:\mathbb{G}_1\times \mathbb{G}_2\mapsto \mathbb{G}_3$ ,

$\mathbb{G}_1=\langle\mathsf{G}_1\rangle$ ,

$\mathbb{G}_2=\langle\mathsf{G}_2\rangle$ —

$m$ .

$\mathbb{G}_1$ .

$\mathsf{Q}=[\ell]\mathsf{G}_1$ , ,

$\mathsf{Q}=\underbrace{\mathsf{G}_1+\mathsf{G}_1+\ldots+\mathsf{G}_1}_{\ell}$

$[-\ell]\mathsf{G}_1=[\ell](-\mathsf{G}_1), [0]\mathsf{G}_1=\infty$ ,

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

$\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$ .

.

$\ell=151_{10}=10010111_2$ .

$\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$ .

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

$\mathsf{S}$

$\mathsf{Q}$

$e_m(\mathsf{S},\mathsf{Q})=g^{cd \pmod m}$ ,

$\mathsf{S}=[c \pmod m]\mathsf{G}_1$

$\mathsf{Q}=[d \pmod m]\mathsf{G}_1$

$g^{cd \pmod m}$ —

$\mathbb{G}_3$ .

$\mathsf{G}_1$

$g$ —

$\mathbb{G}_1$

$\mathbb{G}_3$ ,

$c$

$d$

$\mathbb{F}^*_m$ .

$e_m:\mathbb{G}_1\times \mathbb{G}_2\mapsto \mathbb{G}_3$ ,

$\mathbb{G}_2$ —

$m$ ,

$\mathbb{G}_1$ .

, , , -. . :

• .

• .

• .

: , ECDLP DLP? , , , . , . , , DLP . . , .

$e_m(\cdot,\cdot)$ , , : , ,

$\mathbb{G}_1$

$\mathbb{G}_3$ , .

, , , , DLP ECDLP .

By analogy with the Gatsby party, we call the gatekeeper the checker (actor

$\texttt{V}$ ), and the guest - the prover (actor

$\texttt{P}$ ).

$\texttt{P}$ trying to convince

$\texttt{V}$ who is the invited guest. To this end, it provides

$\texttt{V}$ some proof. Knowing the secret means belonging to the local community of registered members.

$\texttt{V}$ uses the group public key to validate the evidence, then either accepts or rejects the provided evidence. Returning to our Gatsby party example, the gatekeeper (

$\texttt{V}$ ) either sees on the smartphone screen the inscription "skip" if the proof is accepted, or "refuse" - in the opposite case.

If a

$\texttt{P}$ really has a secret that was taken into account when calculating the group key, i.e. he is included in the list of invitees, then with a predominant probability he will be able to convince

$\texttt{V}$ that he is invited and he will open the gates. If a

$\texttt{P}$ does not have a secret key or has, but was excluded from the list of invitees, then

$\texttt{V}$ with a predominant probability, the gate will not open (it will open with a 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. Rounds are messaging sessions in which each party transmits exactly one message. It is like exchanging punches in boxing.

❶

$\texttt{P} \longrightarrow \texttt{V} : (witness)$

❷

$\texttt{P} \longleftarrow \texttt{V} : (challenge)$

❸

$\texttt{P} \longrightarrow \texttt{V} : (response)$

During the one-step implementation of our protocol (session)

$\texttt{P}$ transmits two messages, and

$\texttt{V}$ - only one. Each individual session consists of three cycles of activity

$\texttt{P}\stackrel{1}{\rightarrow}\texttt{V}\stackrel{2}{\rightarrow}\texttt{P}\stackrel{3}{\rightarrow}\texttt{V}$ ...

Let be

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

$\Omega$ (many letters). Set

$\hslash^i(x)=\overbrace{\hslash(\hslash( \ldots \hslash(\hslash(x)) \ldots )}^{i\hbox{ }})$ and

$\hslash^i(x)=\hslash(\hslash^{i-1}(x))$ ,

$i\geqslant 1$ ,

$\hslash^0(x)=x$ ,

where

$\hslash(\cdot)$ - standard cryptographic hash function from FIPS PUB 180-4, and secret

$\beta\in_R\!(0,m-1]$ ... There is

$1\leqslant n < m$ participants. Each participant has a unique identifier

$\mathbf{a}_i\in\Omega^*$ ... We represent 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 formation

$\mathbf{X}$ ensures that everything

$\mathbf{x}_i$ different and even if

$\mathbf{a}_i=\mathbf{a}_j$ then

$\mathbf{x}_i\neq\mathbf{x}_j$ at

$i\neq j, 1 \leqslant i,j \leqslant n$ ...

We will proceed from the assumption that there is a trusted party

$T$ (in our fictional story about the party, this is the owner of the estate, Gatsby himself), which is responsible for parameter selection, pre-calculations and data distribution.

Set

$\beta, n, p, m, \mathbb{G}_1, \mathbb{G}_3, e_m(\cdot, \cdot)$ ... Then at the preparatory stage

$T$ performs the following actions:

Based $\mathbf{a}_i, \beta$ and with the help $h^{i}(\cdot)$ forms many $\mathbf{X}=\{\mathbf{x}_1,\ldots, \mathbf{x}_n\}, i=\overline{1,n}$ ...
Calculates $\Gamma=\prod_{i=1}^n\mathbf{x}_i\pmod m$ ...
Secretly transmits $i$ to the 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}$ ...
$\tilde{g}=e_m([\beta\Gamma\pmod m]\mathsf{G}_1, \mathsf{G}_1)=g^{\beta\Gamma\pmod m}$ . , $\tilde{g}$ . ${\rm{Sign}}(\cdot,\cdot)$ ${\rm{Verify}}(\cdot,\cdot,\cdot)$ — , $\{D_T,\tilde{g}, \Im_{\tilde{g}}\}$ , $\Im_{\tilde{g}}\Leftarrow{\rm{Sign}}(\mathscr{H}(\tilde{g}\|D_T), S)$ , $\mathscr{H}(\cdot)$ — -, $S$ — $T, D_T$ — $T$ . $\tilde{g}$ $\Im_{\tilde{g}}$ $\mathfrak{B}\Leftarrow{\rm{Verify}}(\mathscr{H}(\tilde{g}\|D_T),\Im_{\tilde{g}},P)$ , $P$ — $T$ . $\mathfrak{B}$ takes on the meaning $True$ , if a $\Im_{\tilde{g}}$ valid, and $False$ - otherwise. If a $T$ is not a certification authority within the existing public key infrastructure, then for $P$ a corresponding certificate is issued.
Keeps it secret $\beta$ ...

Messages. Confirmation / refutation of the fact of ownership (knowledge)

$\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 of the parties. The prover tries to convince the verifier that he owns (knows)

$\mathbf{x}_i\in\mathbf{X}$ ... For this

Prover chooses ${\upsilon\in_R\!(0,m-1]}$ (commitment) ${([\upsilon]\mathsf{P}_i\neq\infty)\land([\upsilon+\mathbf{x}_i\pmod m]\mathsf{P}\neq\infty)}$ . , $\mathsf{P}_w$ (witness), $\upsilon$ .
$\phi\in_R\!(0, m-1]$ $\mathsf{P}_c$ (challenge).
, $\mathsf{P}_c\neq\infty$ $g_1$ (response).
$\{D_T, \tilde{g}, \Im_{\tilde{g}}\}$ $\Im_{\tilde{g}}$ $\mathfrak{B}\Leftarrow{\rm{Verify}}(\mathscr{H}(\tilde{g}\|D_T),\Im_{\tilde{g}},P)$ , $P$ — $T$ ... If a $(\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 ownership (knowledge) $\mathbf{x}_i\in\mathbf{X}$ otherwise the proof is rejected.

From the point of view of its intended use, the developed protocol is similar to the Zero-knowledge Proof (ZKP) authentication protocols. They are also designed to solve a similar problem: with the help of interactive interaction

$\texttt{P}$ trying to convince

$\texttt{V}$ that he 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 this is also a disadvantage from a practical point of view: multiple repetition of sessions leads to computational costs, memory consumption and loading of communication channels.

One of the most well-known ZKP protocols is the Feig-Fiat-Shamir protocol. Designed in 1986 by Uriel Feig, Amos Fiat and Adi Shamir. During the protocol

$\texttt{P}$ proves

$\texttt{V}$ that possesses classified information without disclosing this information. Based on the difficulty of extracting the square root modulo a composite modulus of at least two large prime factors, provided that the decomposition is unknown. The Gillou-Kiskatra protocol is another ZKP protocol. It is a variation of the earlier Fiat-Shamir protocol. Designed in 1988 by Louis Guilloux and Jean-Jacques Quiscatre. Like the Fiat-Shamir protocol, it is based on the difficulty of extracting the square root modulo a composite number. The main differences:

• no repetition of the session is required;

• small amount of memory for storing user secrets.

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

Why create another protocol if the problem is solved by existing identification protocols? The thing is that our protocol solves a problem that is different from the one that is solved by known identification protocols, namely, it allows making decisions on the principle of "friend / foe" for the local community of registered participants with a guarantee of their anonymity. In addition, it has a relatively low computational complexity. Correct comparison with L. Nguyen's protocol (Nguyen, L. “Accumulators from Bilinear Pairings and Applications.” In Topics in Cryptology - CT-RSA'05,LNCS 3376, (2005) 275-292.), Since this protocol uses a similar mathematical apparatus. If we compare in terms of the number of pairing and dot product operations involved, then the computational complexity of our protocol is an order of magnitude lower than in L. Nguyen's protocol.

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 he knows all these secrets. If each secret has its own set of evidences, then the WI-property guarantees the statistical / polynomial indistinguishability of these sets. In this context, polynomial indistinguishabilitymeans 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 identified using the superpolynomial laboriousness algorithm!" To this we answer: of course, only the attacker does not have the resources necessary to perform such time-consuming computational work.

• Witness Hiding (WH). An attacker cannot independently compute new evidence that is relevant in the context of the protocol being executed. The probability with which an attacker can obtain such evidence is no higher than the probability of guessing the secret. The attacker is forced either to guess the evidence or to perform some computational work, 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 same ZKP protocol, which were carried out at the same time, then he 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 cannot later impersonate the prover (in our example, the invited guest).

In total, an interactive pairing and dot product identification protocol with proven WI and WH properties is a new solution that reduces computational complexity and storage space for keys (recall that participants do not need public key certificates). Our protocol, unlike ZKP, does not require multiple repetitions of sessions to minimize the likelihood of fraud. 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 publicly available group 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 have developed can be used even on smartphones, and this paves the way for the creation of new mobile applications with an adequate level of cryptographic strength.

Subscribe to our Hubrablog, we plan to continue to actively cover our research and development, and follow twitter if you do not want to miss other news about ENCRY projects.

Private Party Protocol: How to Distinguish Yours and Foes with Cryptographic Tools

More articles: