Join Log in
Score:3
avatar Crypto

What is the modern terminology for a digital signature scheme with a shadow?

in flag
Ethan Heilman

In Guillou and Quisquater's 1988 paper "A 'Paradoxical' Indentity-Based Signature Scheme Resulting from Zero-Knowledge", they say that an RSA identity has a shadow and go on to state that this property is being standardized:

Let us mention that ISO is standardizing a “digital signature scheme with shadow (see ISO-DP 9796) in the Working Group JTC1/SC20/WG2 (public-key techniques).

The Guillou-Quisquater (GQ) signature scheme introduced in this paper is still an active area of research, but searching digital signature shadow and related queries on google only brings up this paper. ISO-DP 9796 doesn't seem to be avaliable online and AFAICT doesn't mention shadows. I assume "shadow" is term of art that did not catch on with the wider cryptography community. Is there modern terminology for this?

81
1 + 2
poncho avatar
my flag
poncho
Just a guess: might the modern terminology be "digital signature with message recovery", that is, the ability to recover the message (or at least part of it) from just the signature (and the public key)?
3
Reply
in flag
Ethan Heilman
Perhaps message recovery implies a shadow or not, I'm not sure. They don't exactly use it for message recovery but they do use if for identity verification based on a message which is almost the same thing.
0
Reply
Score:3
fgrieu avatar Crypto
ng flag
fgrieu

In modern terminology, a digital signature scheme with a shadow is a (digital) signature scheme giving (total) message recovery. The shadow is the message representative.

The paper linked in the question refers to it's reference [12] for the definition of shadow. That's Louis C. Guillou, Marc Davio & Jean-Jacques Quisquater's Public-Key Techniques: Randomness and Redundancy, in Cryptologia Volume 13, 1989 - Issue 2, p.167-189.

Reading this, the term shadow is used for a message representative in an e.g. RSA-based signature scheme. That shadows embeds a relatively small message with added redundancy, and is passed to e.g. the textbook RSA private key function to obtain a signature giving total message recovery, in the modern terminology of ISO/IEC 9796-2:2010.

An example of that is ISO/IEC 9796:1991, which signature embeds a message up to about half of the signature size. That message is returned as a byproduct of signature verification. The scheme is withdrawn because it's EUF-CMA security is broken with 1 or 3 chosen-message queries, due to the rather ad-hoc way the message representative (shadow) is built. An equivalent INCITS standard still seems purchasable.

A free online source explaining ISO/IEC 9796:1991 is section 11.3.5 in the HAC. The shadow would be $\mathsf{MR}$ there.

A modern equivalent with a security reduction would be ISO/IEC 9796-2:2010 scheme 3, which signs with a lower size overhead of $2b+16$ bits for $b$-bit security, or Louis Granboulan's OPSSR which further lowers overhead / increases the amount of message embedded in the signature.

Note: EMV 4.4 Book 2 describes ISO/IEC 9796-2:1997, simplified by a restriction to byte-aligned messages and keys. This scheme remains in the 2010 edition (with some tweaks), although it's EUF-CMA security is broken with some thousands chosen-message queries. This and ISO/IEC 9796:1991 are still in use, and that does not lead to fraud, because existential forgery under chosen message attack is only an issue in some applications.

+ 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.