We adhere to established tradition and continue to present the latest findings. In this note, we discuss the Instant Digital Signature (IDS) mode, which was __announced earlier__. While the main content of the IDS mode was already disclosed in a __previous publication__, we believe that additional specifications will improve understanding.

It should be emphasized that the IDS is not a distinct type of signature, but rather a special mode in which any known digital signature (DS) scheme can be used. In other words, we do not take responsibility for developing a new scheme, but rather propose a practical way to apply existing schemes.

As the name suggests, the IDS mode operates in real-time, specifically, at the moment of signature generation. This means that the mode is used to certify data that is directly associated with an identifying entity, as confirmed in a previously presented proof. Such proof can be obtained through executing an interactive identification protocol, which is necessary for justifying the IDS mode. When discussing this combination, we assume that certain unique variables from the current identification session are used in generating the signature. It is important to understand that these variables are ephemeral by design and only have an effect within the current session.

It should be noted that in this __publication__, we use personal data assurance as an example, which is perhaps the most natural application for the IDS mode.

We demonstrate that the IDS mode is compatible with any known DS scheme. However, it is an open question whether this mode can be used with arbitrary identification protocols. On the other hand, the IDS mode is easily combined with an interactive identification protocol that enables the generation of a shared secret session key, which was created in the development of the protocol presented __in this note__.

We do not provide formal proofs in this text, but rather present examples to convey the essence of our findings. Unfortunately, we could not avoid using formal notation, but we hope that it will not pose any difficulties, as all necessary notation was introduced in __our earlier publication__. Additionally, we use standard mathematical notation adopted in specialized literature, such as [Cohen_etc._2006].

**Interactive Identification Protocol**

First of all, let us recall what an interactive identification protocol is. In fact, this is a game of __two participants__, each of which is endowed with its own role. To avoid unnecessary complications, we will deliberately limit the number of subjects of interaction.

There are two distinct roles: (Prover) and (Verifier). provides proof of knowledge, such as a secret, which then verifies using a decision rule. The verdict can be positive (evidence accepted), negative (evidence rejected), or indeterminate. Typically, upon acceptance or rejection of the evidence, a specific action is initiated. For example, a common scenario is when requests access to a resource, which is granted if accepts the proof. There are other applications for this protocol as well.

Identification protocols belong to a more general class of , which were first introduced in [Cramer_1996]. and are modeled using a probabilistic interactive Turing machine, and the itself is an interactive proof scheme based on Arthur-Merlin game style [Babai_Moran_1988], in which always chooses some variable with a random distribution.

Let's focus on identification protocols that rely on asymmetric cryptography.

The interactive identification protocol can be represented by the following diagram:

It is clear that three messages are transmitted during the protocol: *witness, challenge, *and *response*. In this case, transmits two messages (*witness* and *response*), and transmits only one message (*challenge*). The purpose of each message is clear from its name.

Let's call the independent variables with a random distribution that change from one protocol session to another as the *ephemeris*. In cryptographic terms, ephemeris is equivalent to secret keys. To reveal an unknown ephemeris, it is necessary to find a solution to some computational complexity problem or to undertake a brute force attack.

It is assumed that each participant has a pair of unique keys: a secret key and a public key. Additionally, proper certificates have been issued for the public keys.

The parties do the following:

generates a

*witness*based on the public key and at least one ephemeris known only to .creates a

*challenge*using at least one ephemeris known only to .generates a

*response*based on their own private and public keys and the*challenge*.renders a verdict based on the

*witness*, the*response*, the ephemeris involved in the*challenge*, and the public key .

All identification protocols include three messages, which, thanks to ephemeris, are randomly distributed. It is proven that there cannot be fewer messages (there can be more). All of the above messages carry the same semantic load in different identification protocols, but the methods of their computation can vary significantly and depend on the main provisions of the computational complexity problem, as well as the chosen mathematical apparatus.

After some deliberation, we decided to keep the designations used in the interactive identification protocol we developed with the possibility of generating a shared secret session key, which has not yet been made public. Therefore, is passed as a *response*, where is some cryptographic hash function known to both parties. To check the proof, computes . This uses a simple decision rule like . Here . Note that the way and are computed is irrelevant in this context.

Since most of the texts we publish are interconnected, we hope that this approach will further simplify the “bridge” between our various posts.

**Compatibility with any DS scheme**

Let there be a pair of keys and a certificate . Let's show how it works taking the well-known Schnorr's DS scheme [Schnorr_1990] as an example.

acts as the signer. Given message , secret key , and , the signer performs the following computations:

, where ;

;

;

.

Let there be a signature and a message such that . Let's assume that the authenticity and integrity of the key is confirmed by checking the valid certificate . performs the following computations:

;

.

If , then , where . Suppose . Therefore, if . For with overwhelming probability and negligible . However, if , then it is with overwhelming probability and with negligible probability.

DS verification and verification of personal data are interconnected. Let be some personal data and . , and a valid certificate are presented for verification. If the DS is valid, in other words , then . If valid, is verified. The authenticity of personal data arises from .

The IDS mode can be implemented using an arbitrary conventional scheme based on the elliptic curve points arithmetic. This approach is inherent in the vast majority of modern DS schemes [Schnorr_1990, Paterson_2002, Hess_2003, Boneh_Shacham_Lynn_2004, Zhang_Safavi-Naini_Susilo_2004, Boneh_Boyen_2004]. However, this condition is not necessary. For example, without losing the generality, one can replace a subgroup of the group of elliptic curve points with a subgroup of prime order of the group . Note that the mode is also compatible with DS schemes, which are developed consistent with the provisions of post-quantum cryptography.

This compatibility has a simple explanation. Since in an arbitrary conventional DS scheme the computation of is normative in nature, that means that it is always present in any DS scheme, then replacing with does not lead to negative consequences for the cryptographic strength of this scheme, since in the general case the dependence of the collision probability on the argument of the cryptographic hash function is unknown. Here, by collision we mean for and .

For example, if the DS scheme [Zhang Safavi-Naini_Susilo_2004] is used for this purpose, then for the given message and secret key the signer first computes , and then generates the signature .

Let there be a signature and a message such that . first evaluates and then . Checks and if .

Note that at the identification stage, is transmitted over an insecure communication channel, and to reveal with an unknown secret message, you must either compute , or find solution of some computational complexity problem.

Let's summarize.

is unable to forge/falsify the DS given is known, because it does not know . He can use the key pair , where , and certificate has been issued for , but subsequent verification will show that .

(signer) can generate only if he knows the secret .

DS verification is possible only if there is a positive decision regarding the

*response*.

Let's list the distinctive features of the IDS mode.

The mode is active within the current session and is relevant only for .

cannot convince a third party of the authenticity and integrity of the data received during a particular session.

The IDS can be formed by someone who knows the secret key and is able to compute

Anyone who knows and can check the IDS.

The correctness of the IDS is guaranteed if the proof is accepted.

The IDS mode is ideologically close to the work of [Dwork_Naor_Sahai_1998], in which the problem of *deniable authentication* was first formulated and the authors proposed a specific solution.

Let's assume that verified the authenticity of the signer's personal data using the IDS mode with subsequent verification. Now the signer can use the secret key to generate a signature using an arbitrary conventional DS scheme based on the elliptic curve points arithmetic (or any other). Note that this scheme may differ from the one used to verify personal data. It makes sense to keep such the DS in long-term memory, and you need a valid certificate to verify it. This means that after authentication in the IDS mode, undeniable authentication is guaranteed for all other data, the certification of which is made within the framework of the conventional DS scheme. And it does not need auxiliary computation and additional organizational costs.

In general, an attacker does not have access to personal data, since it is transmitted and stored in encrypted form, but can determine the serial numbers of certificates of public keys of signers by tracking requests from verifiers, for example, according to the rules of the OCSP (Online Certificate Status Protocol). Such monitoring should be regarded as a threat, because certificates contain information that allows to deanonymize a participant. Potential risks are offset by the transfer of certificates through a secure tunnel. Furthermore, certificates can be read using the Private Information Retrieval (PIR) method [Chor_Goldreich_Kushilevitz_Sudan_1995, Kushilevitz_Ostrovsky_1997].

**Incompatibility with arbitrary protocol **

As it was shown, in the IDS mode, any known DS scheme based on the elliptic curve points arithmetic (or any other) can be applied.

All identification protocols consist of one and a half rounds and provide for the transmission of *witness*, *challenge* and *response* messages. There is the following fundamental question to be answered: is the IDS mode possible only for a specific identification protocol or is it compatible with an arbitrary protocol?

Let's consider a specific example. To do this, when describing the Schnorr's identification protocol [Schnorr_1990], we pass from a subgroup of prime order of the group to a subgroup of order of the elliptic curve points group.

first selects and generates a pair of keys . Then contacts trusted authority to issue a certificate , where and are personal data of .

For simplicity, we omit information about the location of the certificate, as well as its updating by checking with the list of revoked certificates.

__Schnorr's Identification Protocol__

*Protocol messages.*

*Actions of the parties. *

proves to that he owns (knows) . To do this, the following steps are performed:

selects (

*commitment*), computes (*witness*), checks the condition . If , then choose a new and re-do the necessary computations and checks.reads the valid certificate and checks the DS . If then chooses (

*challenge*), otherwise the session ends.checks the condition . If it is true, evaluates (

*response*), otherwise the session ends.computes . Then checks . If equal, then the proof is accepted, or it is rejected otherwise.

In the general case, the pair of keys , with wich is signed/verified, differs from . For , trusted authority also issues a certificate . For simplicity, we set .

Let's assume that sends some data certified by DS. Moreover, the DS is generated using the secret key , and it is necessary to use the public key from the certificate for verification. At the same time, there is no guarantee that it was who certified the data, and not an attacker who fraudulently forced to generate the DS for this data or obtained it from open sources. However, also does not mean that the data was certified by the one who provided the proof at the current time. Thus, for example, an attacker can impose data certified by the DS, but at the same time no longer relevant. We have shown above that the IDS mode also can be used to solve this problem. Therefore, it is necessary to demonstrate the operability of the IDS mode in the Schnorr's identification protocol.

Note that the DS in this protocol, as well as any other action, is “torn off” from the identification results. Indeed, if accepted the proof from , and then certified some data with the DS and sent them to then it is impossible to guarantee that the identity of did not undergo fundamental changes as a result of *significant events *in the time interval between the acceptance of the proof and the moment the DS was created. Such events include, for example, revocation of certificate due to secret key being compromised, its expiration, and others. As a result, will not be able to provide proof, while the proof provided earlier loses legitimacy. The time interval with a significant event can be arbitrarily small, but it is nonzero, and therefore the problem is classified as fundamental.

Thus, when discussing the IDS mode in the Schnorr's identification protocol, it is necessary to follow the unreasonable assumption of a negligible probability of a significant event.

It should be noted that significant events are also possible in the identification protocol developed by us, however, a secure data transmission tunnel due to encryption, which is established only upon the fact of proof, provides additional guarantees. In other words, identification is legitimate within a single session, which ends as a result of the session key deactivation after a predetermined time interval, which in turn is set up by the provisions of the current security policy.

The** necessary condition** is that the *response* cannot be transmitted over an unsecured communication channel without first being converted by a one-way function. Let's explain why.

If is sent as a *response* instead of , then not only , but anyone who has gained access to will be able to generate the DS. Obviously, the use of a one-way pseudo-random function, assuming a random oracle model, such as , violates the algebraic structure of the response in the form of .

The latter means that the verification of the proof must be based on a method different from the algebraic one. This is how our protocol checks . Only can compute because it knows the secret, and is the only one able to compute because he knows the *challenge*. An attacker observes , and in order to reveal , he needs to solve a computational complexity problem or compute .

In the Schnorr's identification protocol, the *response* is given as , and to check, you must first compute the point and then check . It is clear that if you pass instead of and compute , then with overwhelming probability .

Therefore, checking is possible for , but not for . This means that in this protocol, the *response* can only be transmitted in cleartext, but then the IDS mode does not meet the necessary condition.

There are two directions for future research under consideration:

Search/development of identification protocols for which the necessary condition is met.

A formal proof of the fact that a necessary condition is not met for any identification protocol using an algebraic way of checking the proof.

We also do not rule out that the proof of the properties such as *witness indistinguishable* and *witness hiding* [Feige_Shamir_1990] may be questioned. However, only the expert community is able to confirm/refute this proof after the publication of the identification protocol developed by us in a peer-reviewed periodical.

**Conclusion**

Compared to the conventional scheme, the IDS mode has some limitations. However, as follows from the explanations, the conventional DS schemes themselves are useless from the point of view of solving the __task__, since they do not guarantee that the signature was created by the one who provided the certified data at the current time.

Presumably, the IDS mode works only in our protocol, since the algebraic equation is used to verify the proof in all known identification protocols [Fiat_Shamir_1987, Feige_Fiat_Shamir_1988, Guillou_Quisquater_1988, Schnorr_1990, Brickell_Mccurley_1992, Okamoto_1993, Nguyen_2005]. For all these protocols, the necessary condition is not met.

This post omits the proof of cryptographic strength of the IDS mode. This is a conscious step, as we wanted to cut and simplify the text. Additionally, for such reasoning, it is necessary to have a detailed description of the identification protocol. We reserve the right to return to this topic after the corresponding publication.

The pdf version of this article is available here.

## The Bibliography

[Cohen_etc._2006] Cohen, H., Frey, G., Roberto Avanzi, R., Doche C., Lange, T., Nguyen, K. and Vercauteren, F. Handbook of Elliptic and Hyperelliptic Curve Cryptography, Chapman and Hall/CRC, 2006.

[Cramer_1996] Cramer, R. “Modular Design of Secure, yet Practical Cryptographic Protocols.” PhD Thesis, University of Amsterdam, 1996.

[Babai_Moran_1988] Babai, L. and Moran, S. “Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes.” Journal of Computer and System Sciences, Volume 36, Issue 2, April (1988) 254–276.

[Schnorr_1990] Schnorr, C. P. “Efficient identification and signatures for smart cards.” Advances in Cryptology — CRYPTO’89 LNCS 435, (1990) 239–252.

[Paterson_2002] Paterson, K. G. “ID-based signatures from pairings on elliptic curves.” IEEE Electronic Letters, 38(18), (2002) 1025–1026.

[Hess_2003] Hess, F. “Efficient Identity Based Signature Schemes Based on Pairings.” Revised Papers from the 9th Annual International Workshop on Selected Areas in Cryptography — SAC’02, (2003) 310–324.

[Boneh_Shacham_Lynn_2004] Boneh, D., Shacham, H. and Lynn B. “Short Signatures from the Weil Pairing.” J. Cryptol., Vol. 17, No. 4, (2004) 297–319.

[Zhang_Safavi-Naini_Susilo_2004] Zhang, F., Safavi-Naini, R. and Susilo, W. “An efficient signature scheme from bilinear pairing and its applications.” Public Key Cryptography, LNCS 2947, (2004) 277–290.

[Boneh_Boyen_2004] Boneh, D. and Boyen, X. “Short Signatures Without Random Oracles.” EUROCRYPT 2004, LNCS 3027, (2004) 56–73.

[Chor_Goldreich_Kushilevitz_Sudan_1995] Chor, B., Goldreich, O., Kushilevitz, E. and Sudan M. “Private information retrieval.” In Proc. of the 36th IEEE Symp. on Foundations of Computer Science, (1995) 41–51.

[Kushilevitz_Ostrovsky_1997] Kushilevitz, E. and Ostrovsky, R. “Replication is not needed: Single database, computationally-private information retrieval.” In Proc. of the 38th IEEE Symp. on Foundations of Computer Science, (1997) 36–373.

[Fiat_Shamir_1987] Fiat, A. and Shamir, A. “How to prove yourself: Practical solutions to identification and signature problems.” Advances in Cryptology[ — CRYPTO’86 LNCS 263, (1987) 186–194.

[Feige_Fiat_Shamir_1988] Feige, U., Fiat, A. and Shamir, A. “Zero-knowledge Proofs of Identity.” Journal of Cryptology, 1 (1988) 77–94.

[Guillou_Quisquater_1988] Guillou, L. C. and Quisquater, J. -J. “A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory.” Advances in Cryptology — EUROCRYPT’88 LNCS 330, (1988) 123–128.

[Brickell_Mccurley_1992] Brickell, E. F. and Mccurley, K. S. “An interactive identification scheme based on discrete logarithms and factoring.” Journal of Cryptology, 5 (1992) 29–39.

[Okamoto_1993] Okamoto, T. “Provably secure and practical identification schemes and corresponding signature schemes.” Advances in Cryptology — CRYPTO’92 LNCS 740, (1993) 31–53.

[Nguyen_2005] Nguyen, L. “Accumulators from Bilinear Pairings and Applications.” In Topics in Cryptology — CT-RSA’05, LNCS 3376, (2005) 275–292.

[Dwork_Naor_Sahai_1998] Dwork, C., Naor, M. and Sahai, A. “Concurrent Zero-Knowledge.” Proc. 30th ACM Symposium on the Theory of Computing, (1998), 409–418.

[Feige_Shamir_1990] Feige, U. and Shamir, A. “Witness Indistinguishable and Witness Hiding Protocols.” In Proceedings of 22nd STOC, ACM Press, (1990) 416–426.