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.