The Variant of Designated Verifier Signature Scheme with Message Recovery

arXiv:2403.07820 · cs.CR · Submitted 2024-03-12 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: Today's paper: "The Variant of Designated Verifier Signature Scheme with Message Recovery".

Elias: The gist This work introduces a strong Designated Verifier Signature (DVS) scheme enhanced with a message recovery mechanism, inspired by universal designated verifier signature concepts,

Nadia: First, who's behind it and why it matters.

Title and authors: Elias: So, let's talk about the specific components mentioned in "The Variant of Designated Verifier Signature Scheme with Message Recovery." The authors are building on previous work, specifically drawing inspiration from universal designated verifier signature collaboration for message recovery to ensure privacy for both the signer and the designated verifiers.

Nadia: That sounds like they’re trying to separate the roles a bit more, making sure that only designated verifiers can authenticate the true signer. It involves three main algorithms: Setup, PV-Signature-Generation, and PV-Signature-Verification.

Priya: From what I see in their setup process, Alice generates a signature with parameters like t, c, r, and s using two random numbers from Z q. That’s the initial data input for the signature generation step.

Elias: The generation step itself involves choosing two random numbers, say k one and k two from Z q, to create t = g k one mod p, then c = m k two B mod p, and finally a hash value for the randomness, which they call r <ref:2403.07820#pg1>.

Nadia: And then there’s that final calculation for the signature component, where they use the inverse of one of those random numbers to get s, which is (k-one(xAr - k two)) mod q. It seems like a lot of number manipulation just to tie the message into the signature structure.

Priya: That complexity is what they’re aiming to manage so that you can simultaneously recover the message and verify the signature, which they say is possible because the message is embedded within those initial components.

The paper's summary: Nadia: Moving on to what this paper actually says in its summary, it explains that this new scheme extends Lee’s strong designated verifier signature with a message recovery scheme to create a universal designated verifier signature scheme.

Elias: They specifically state that this extension is crafted to safeguard the privacy of both the signer and the designated verifiers, which they see as holding significant promise for applications like certificate management for medical records and electronic voting systems.

Priya: So, in simple terms, what I’m hearing is that this approach moves beyond just having a signature to making sure that only designated verifiers can access the message when they need to do so.

Nadia: Precisely. They are building a way where the message isn't just hidden but is integrated into the signature structure itself, allowing designated verifiers to recover it while also verifying the signature at the same time.

Elias: The summary highlights how this design works by showing how transcript simulation is still possible, meaning Bob can generate a simulated signature that looks exactly like a real one without needing Alice's private key.

Priya: That’s interesting because if transcript simulation holds up, it means the system remains functional for verification even when you’re just trying to prove authenticity without knowing the secret keys.

The paper's improvements: Nadia: Now let's look at the actual improvements they propose over what came before. They draw inspiration from universal designated verifier signature collaboration for message recovery to ensure privacy for both parties involved in the process.

Elias: The authors describe a new structure involving three main algorithms: Setup, PV-Signature-Generation, and then PV-Signature-Verification. The PV signature generation takes the signer's choice of two random integers k one and k two to generate the signature (t, c, r, s) for a message m <ref:2403.07820#pg1>.

Priya: The key improvement seems to be how they extend this into the universal designated multi-verifier signature or UDMS. This involves a sequential process where Alice sends a PV-signature to a designator, who then creates a DV-signature.

Nadia: And finally, that designator delivers the DV-signature back to the designated verifier along with the original message m. This layered approach is what they suggest for achieving better privacy guarantees.

Elias: The verification step for this new structure involves checking if m = c(t s y-r A) xB mod p, and that a specific hash relationship holds, which they state is equivalent to r? = H(m, yr A t - s).

Priya: The analysis shows they establish the scheme as a designated verifier signature scheme because the transcripts simulated by the designated verifier are indistinguishable from those generated by the signer with a probability of one/q(q-one)(q-two) <ref:2403.07820#pg1>.

Conclusion: Nadia: So to wrap up, this paper proposes variants of a strong designated verifier signature scheme with a message recovery mechanism, inspired by UDVS. They’ve successfully separated the roles and enhanced obfuscation to achieve unforgeability and confidentiality.

Elias: The security assumption they rely on is the discrete logarithm problem, which they state is what underpins their security. The paper emphasizes that because it involves the designated verifier’s secret key in both recovery and verification steps, no one can discern the real signer or recover the message except for that designated verifier.

Priya: I think what this means for applications is that by making this scheme work, AI systems handling sensitive data, like medical record certificates or voting systems, can ensure that only authorized verifiers can decrypt and interpret the underlying information.

Nadia: Exactly. And they’ve shown how to make the transcript simulation robust enough to prevent third parties from finding out who the real signer is when using this variant of the strong designated verifier signature scheme with message recovery.

Elias: They also proved unforgeability by showing that forging a signature requires solving either the discrete logarithm problem for a signer or computing c', which needs that designated verifier’s secret key for a designator forgery.

Priya: It’s important to remember the limitation they state: the scheme relies on the discrete logarithm problem, so if you can solve that, you can break their security assumptions.

Nadia: So they have given us a framework where we get message recovery and strong privacy, even in complex multi-party settings with this universal designated verifier signature scheme with message recovery. That’s what we have here from this paper.

Department of Computer Science and Engineering, National Taiwan Ocean University

cs.CR

Submitted: 2024-03-12

Updated: 2026-10-14

Comments: 11 pages

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 83/100

The gist: The gist This work introduces a strong Designated Verifier Signature (DVS) scheme enhanced with a message recovery mechanism, inspired by universal designated verifier signature concepts, to

Key concepts

Strong Designated Verifier Signature Scheme: This scheme allows a signer to provide non-interactive evidence of a signature to a designated verifier. The verifier uses their private key to produce a 'transcript simulation,' which makes the simulated signature indistinguishable from a genuine one, ensuring strong authentication.
Message Recovery Mechanism: The message is integrated directly into the signature structure. This allows designated verifiers, who possess the necessary secret keys, to simultaneously verify the signature's validity and recover the original message content without compromising privacy.
Universal Designated Verifier Signature (UDVS) Inspiration: The scheme draws inspiration from UDVS collaboration concepts to separate roles into a signer, designator, and designated verifier. This sequential process ensures that only the designated verifier can access the message after validation by intermediate parties.

Terminology

Verifier — 8× in this paper · explained in 2 episodes

Summary

The gist

This work introduces a strong Designated Verifier Signature (DVS) scheme enhanced with a message recovery mechanism, inspired by universal designated verifier signature concepts, to safeguard signature holder privacy and enable message recovery for applications like medical records and voting systems<ref:2403.07820#pg12>.

Strong Designated Verifier Signature Scheme

The initial strong designated verifier signature scheme is introduced by Jakobsson et al. in 1996, which improves upon the undeniable signature by allowing the signer to provide evidence to a designated verifier non-interactively through transcript simulation<ref:2403.07820#pg3>. This capability is achieved because of the designated verifier’s ability to produce a valid DVS using their private key, known as transcript simulation, which makes a simulation signature indistinguishable from a valid signature<ref:2403.07820#pg4>. Saeednia et al. proposed an efficient strong designated verifier signature scheme by incorporating the designated verifier’s private key into the verification step to ensure that any third party lacking the designated verifier’s private key would be unable to verify the signature or access any message contained within it<ref:2403.07820#pg5>.

Strong Designated Verifier Signature Scheme with Message Recovery Mechanism

The scheme with message recovery integrates the message as part of the signature itself, allowing designated verifiers to simultaneously recover the message and verify the signature<ref:2403.07820#pg6>. The setup involves Alice generating a strong designated verifier signature (t, c, r, s) with a message m by choosing two random numbers k1 from Zq and k2 from Zq to generate t = g k1 mod p, c = m k2 B mod p, r = H(m, gk2), and s = (k-1(xAr - k2)) mod q<ref:2403.07820#pg7>. The verification process for Bob involves checking if m = c(t s y-r A) xB mod p r?= H(m, yr At-s)<ref:2403.07820#pg8>. Transcript simulation is possible where Bob selects two random values w1 from Zq and w2 from Zq to compute a simulated signature (t', c', r', s') such that the transcript is indistinguishable from a genuine signature<ref:2403.07820#pg9>.

Proposed Scheme

The proposed scheme extends the strong designated verifier signature scheme by drawing inspiration from universal designated verifier signature collaboration for message recovery, ensuring privacy for both the signer and designated verifiers. The construction involves three main algorithms: Setup, PV-Signature-Generation (PSG), and PV-Signature-Verification (PSV). In PSG, the signer chooses two random integer k1 from Zq and k2 from Zq to generate the signature (t, c, r, s) where t = g k1 mod p, c = mgk2 mod p, r = H(m, gk2), and s = k-1(xAr - k2) mod q. The PSV algorithm allows anyone to verify the PV-signature by checking if m = c(t s y-r A) mod p r?= H(m, t−s y r A).

Extension into UDVS Scheme

The extension into the Universal Designated Verifier Signature (UDVS) scheme involves three involved parties: a signer, a designator, and a designated verifier. The process is sequential: the signer generates a PV-signature and sends it to the designator, who validates it and then creates a DV-signature. Finally, the designator delivers this DV-signature to the designated verifier along with the message. The DV-Signature-Generation (DSG) algorithm takes a PV-signature and generates a DV-signature δ by choosing a random number d ∈ Zq and computing e = g-d mod p w = cydB. The DV-Signature-Verification (DSV) algorithm allows the designated verifier to check the validity of δ by verifying m = w(t s y-r A e xB) mod p r?= H(m, t−s y-r s).

Analysis

The scheme is established as a designated verifier signature scheme because the transcripts simulated by the designated verifier are indistinguishable from those generated by the signer, with a probability of 1/q(q−1)(q−2). The scheme satisfies the strongness property because it involves the designated verifier’s secret key in both recovery and verification steps, meaning no one can discern the real signer or recover the message except the designated verifier. Unforgeability is maintained because forging a signature requires solving either the discrete logarithm problem (for signer forgery) or computing c' which necessitates the designated verifier’s secret key (for designator forgery). Confidentiality is satisfied because only the designated verifier’s secret key is required to recover the message.

Conclusion

In conclusion, this work proposes variants of a strong designated verifier signature scheme with a message recovery mechanism, inspired by UDVS, which separates roles and enhances obfuscation to achieve unforgeability and confidentiality. The security assumption relies on the discrete logarithm problem.

References

I. Ray, N. Narasimhamurthi, An anonymous electronic voting protocol for voting over the Internet, In: Proceedings of the 3rd International Workshop on Advanced Issues of E-Commerce and Web-Based Information Systems (WECWIS’01), California, 2001, pp. 188-190.
B. Schoenmakers, A simple publicly verifiable secret sharing scheme and its application to electronic voting, Advances in Cryptology-CRYPTO’99, Springer-Verlag, 1999, 148-164.
Yao, A.C., Protocols for secure computations, 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), 160-164.
Jakobsson, M., Sako, K., Impagliazzo, R., Designated Verifier Proofs and Their Applications, In: Maurer, U. (eds) Advances in Cryptology - EUROCRYPT ’96. EUROCRYPT 1996. Lecture Notes in Computer Science, vol 1070. Springer, Berlin, Heidelberg.
Chaum, David; van Antwerpen, Hans, Undeniable Signatures, Advances in Cryptology - CRYPTO’ 89 Proceedings. Lecture Notes in Computer Science. Vol. 435. pp. 212–216.
S Saeednia, S Kremer, O Markowitch, An efficient strong designated verifier signature scheme, In: Proceedings of the 6th International Conference on Information Security and Cryptology (ICISC 2003), Seoul, Korea, 2003, pp. 40-54.
K Nyberg, R A Rueppel, A new signature scheme based on the DSA givingmessagerecovery, Proc of the First ACM Conference on Computer and Communication Security, vol. 1. pp. 58-61, 1993.
K Nyberg, R A Rueppel, Message recover for signature schemes based on the discrete logarithm problem, Advances in Cryptology - EUROCRYPT’94, LNCS 950, pp. 182-193, 1994.
J-S Lee and J H Chang, Strong Designated Verifier Signature Scheme with Message Recovery, The 9th International Conference on Advanced Communication Technology, Gangwon, Korea (South), 2007, pp. 801-803.

Improvements for AI systems

No third party can discern the real signer nor access any message because the designated verifier’s secret key is required to recover the message. This allows AI systems handling sensitive data, such as medical record certificates or voting systems, to ensure that only authorized verifiers can decrypt and interpret the underlying information.
AI systems can be engineered to generate strong designated verifier signature (DVS) scheme transcripts that are indistinguishable from those generated by the signer, which prevents third parties from ascertaining the true signer. This enhances the privacy of data origin in applications like electronic voting where initiator identity must be safeguarded.
The proposed scheme allows for message recovery and verification, enabling Bob to simultaneously recover the message and verify it, as shown by the correctness proof: m = c(t s y − r A) xB mod p = c(g xBsk1−xAr) mod p = c(g−k2) mod p = mgk2 mod p = cy-k2 B mod p. This capability is crucial for AI systems that process encrypted messages, allowing the designated verifier to immediately validate and extract the original content.
The extension into a universal designated multi-verifier signature (UDMVS) scheme allows for a structure where the signer will generate a PV-signature and send it along with the message to the designator, followed by the designator further creates a designated verifier signature (DV-signature) and deliveries it together with the message to the designated verifier. This multi-step verification process can be used in complex AI workflows requiring layered authentication, such as secure certificate management.

Abstract

In this work, we introduce a strong Designated Verifier Signature (DVS) scheme that incorporates a message recovery mechanism inspired by the concept of the Universal Designated Verifier Signature (UDVS) scheme. It is worth noting that Saeednia's strong designated verifier signature scheme fails to guarantee the privacy of the signature, making it unsuitable for certain applications such as medical record certificates or voting systems. To overcome this limitation, we extend Lee's strong designated verifier signature with a message recovery scheme to develop a universal designated verifier signature scheme. This universal designated verifier scheme is crafted to safeguard the privacy of signature holders, ensuring that only designated verifiers can authenticate the true signer and recover the messages.