Discussion:
Signing a message with low size penalty
Francois Grieu
2004-06-09 11:12:07 UTC
Raw Message
We want to digitaly sign a message, in a context such
that it is of no use for an adversary to make a forgery
of an entirely random message. We want the signature
process to incur a minimal message size penalty, such
as 1 bit.

Message could be voice or face picture processed with
a general-purpose sound or picture compression scheme
(mp3, mpeg), and listened or seen by a human after
decompression.

I fail to find a solution that works for arbitrary sized
messages; this is my question.

I formalize the problem as follows:

- There is some pre-existing "Verification" process
for a message m, giving Verif(m) = PASS or FAIL,
such that odds that a random message m gives PASS
is <=2^-w for some security parameter w (e.g w=80).
Note: it might be trivial to find a message m such
that Verif(m) = PASS, if one is allowed to change w
bits out of a random value in order to construct m.

- A public/private key pair pk/sk is setup.

- The signing process (to be determined), using key sk,
takes a message m and transforms it into a signed
message s.

- An opening process (to be determined), using key pk,
takes s and must output Open(s) = m whenever s
was obtained from m by the signing process.

- An adversary can obtain many (m,s) pairs for messages
m she entirely choose, regardless of Verif(m).

- The adversary's objective if to find an s, other than
obtained as above, such that Verif(Open(s)) = PASS.

The closest thing I have is for agreed-in-advance message
size k set to 1 bit less than the modulus size of an
RSA key (n,e,d). In this setup, a scheme expanding the
message by only 1 bit might be:

Signing process
- apply some reversible random-like transform to m,
giving c = T(m) of same size k as the original
message
- output s = (c ^ d) % n

Opening process
- check that 0 <= s < n, else output f for some constant
f such that Verif(f) = FAIL
- set c = (s ^ e) % n
- check that c < 2^k, else output f
- undo the reversible transform T, giving the one m
such that E(m) = c
- output m

A suitable transform T can be obtained from a secure
hash (in the random oracle model), by repeatedly
- splitting m into m' | m", with m' the size of
the hash
- replacing m with m" | (Hash(m") ^ m')
I'm not quite sure how many rounds are necessary to
obtain a provably secure scheme. My guess is that
ceil(k/size-of-hash) is enough.

More efficient transforms T can be built from a hash
and a block cipher (e.g SHA-256 and AES-128 in CTR mode).

Fran<E7>ois Grieu
Andrew Swallow
2004-06-10 10:49:01 UTC
Raw Message
Post by Francois Grieu
We want to digitaly sign a message, in a context such
that it is of no use for an adversary to make a forgery
of an entirely random message. We want the signature
process to incur a minimal message size penalty, such
as 1 bit.
One bit is too short. Your opponent can fake a message
by sending two copies - the first with the bit set to 1 and
the second with the bit set to 0.

Where there are n bits the check can be beaten by
sending 2**n messages. So n has to be big.

In practice if you system is limited by communications
speed then n=64 may work. n=128 is better and
n=160 is a full defence against this attack.

Too many rejected messages should be reported.
You have either got a very poor link or a hacker.

Andrew Swallow
Francois Grieu
2004-06-12 07:19:04 UTC
Raw Message
Post by Andrew Swallow
Post by Francois Grieu
We want to digitaly sign a message, in a context such
that it is of no use for an adversary to make a forgery
of an entirely random message. We want the signature
process to incur a minimal message size penalty, such
as 1 bit.
One bit is too short. Your opponent can fake a message
by sending two copies - the first with the bit set to 1
and the second with the bit set to 0.
Andrew's remark apply in the framework of digital signatures
with appendix, which attach a signature to an unmodified
message. But in the framework [*] that I propose:

- The signing process is allowed to transform the message,
as long as the opening process recovers it unchanged.
This is as in existing "signature with message recovery"
schemes (e.g. ISO 9796-2)

- To suceed, the adversary has to forge a signed message
which, after opening, is not entirely random. This is
what allows zero message expansion.

The interest of such a scheme (if it can be built with
provable security, something in which I'm confident)
comes from that

- its measure of the adversary's sucess is a reasonable
model of reality when e.g. the message is audio or
face image (including compressed, transmitted, and
robustly decompressed).

- it allows to trivialy build a traditional "signature
with message recovery" scheme with minimal size penalty:
simply append w bits of 0 to a message and sign it.
Note that message expansion is more than twice lower
than in established schemes (e.g ISO 9796-2):
for 1024 bit RSA security, message expansion is 8 bytes
for any message of 120 bytes or more.

Francois Grieu

[*] Problem statement, polished:

- We assume some "Verification" process for a message
m, giving Verif(m) = PASS or FAIL, such that odds
that a random message m gives PASS is 2^-w for
some security parameter w (e.g w>=80).

- Some public/private key pair pk/sk is setup.

- A signing process (to be determined), using key sk,
takes a message m and transforms it into a signed
message s.

- An opening process (to be determined), using key pk,
takes s and must output Open(s) = m whenever s
was obtained from m by the signing process.

- An adversary can obtain many (m,s) pairs for messages
m she entirely choose, regardless of Verif(m).

- The adversary's objective if to find an s, other than
obtained as above, such that Verif(Open(s)) = PASS,
in less than 2^w operations of some kind.

- The scheme must work for any verification process
(that is, the adversary should be allowed to
choose the verification process, as long as it
does so independetly from pk)

We could call such a scheme a digital signature scheme
with randomized message recovery.

Objectives are:

- minimizing message expansion in the signing process,
e.g. to 0 or 1 bit at most.

- minimizing the minimum message size.

- allowing flexibility in message size.

The original message describes a scheme that, in
this framework,

- signs a 1023 bit recoverable message into 1024 bits

- seems convincingly (maybe provably) as secure as
the least secure of
- 1024 bits RSA
- some hash
- finding m with Verif(m) = PASS by random queries.

I believe we can get rid of the 1 bit loss in capacity,
and extend to larger messages regardless of the key.
Michael Amling
2004-06-12 08:09:57 UTC
Raw Message
Andrew Swallow wrote:
< "Francois Grieu" <***@francenet.fr> wrote in message
< news:***@uni-berlin.de...
<
<>We want to digitaly sign a message, in a context such
<>that it is of no use for an adversary to make a forgery
<>of an entirely random message. We want the signature
<>process to incur a minimal message size penalty, such
<>as 1 bit.
<
< One bit is too short. Your opponent can fake a message
< by sending two copies - the first with the bit set to 1 and
< the second with the bit set to 0.
<
< Where there are n bits the check can be beaten by
< sending 2**n messages. So n has to be big.

No, in this case the OP's premise was that existential forgeries
are of no value to the attacker.

--Mike Amling
David Wagner
2004-06-12 08:30:52 UTC
Raw Message
Post by Francois Grieu
- There is some pre-existing "Verification" process
for a message m, giving Verif(m) = PASS or FAIL,
such that odds that a random message m gives PASS
is <=2^-w for some security parameter w (e.g w=80).
- The signing process (to be determined), using key sk,
takes a message m and transforms it into a signed
message s.
- An opening process (to be determined), using key pk,
takes s and must output Open(s) = m whenever s
was obtained from m by the signing process.
- An adversary can obtain many (m,s) pairs for messages
m she entirely choose, regardless of Verif(m).
- The adversary's objective if to find an s, other than
obtained as above, such that Verif(Open(s)) = PASS.
A few notes.

1. If you want w-bit security, you probably will need to require
at least 2w bits of redundancy in the messages. In other words,
Pr[Verif(m) = PASS] <= 2^{-2w} for random m. Why? If we look at
short signatures (with appendix), most schemes require at least 2w
bits of expansion (redundancy) for w-bit security. I'm aware of
only one scheme that gets this close to w bits of redundancy, and
that's the Courtois-Finiasz-Sendrier scheme, but its security has
not been well analyzed as far as I know.

2. If messages are compressible, it may be possible to achieve your
goals. Since the distribution on m must be samplable by polynomial
time randomized algorithms, there is some algorithm A so that A(r)
has the same distribution on m when r is a string of random coins.
If A is easily invertible, so that given m we can find a short string
r with A(r) = m, then we can compress and sign by sending r and a
signature on r. This achieves your goals, but then the signature
scheme must be tailored to the specific message distribution and it
must be possible to compress messages. Probably not the conditions

3. If you're content to ignore short messages, the following may work.
Let Pi,Pi^{-1} be a random permutation oracle. It is like a random
oracle, except that it is a length-preserving permutation: on input x,
Pi returns a new string Pi(x) of the same length as x and different from
all other outputs of the same length; on input y, Pi^{-1} returns the
string x such that Pi(x) = y. Let F_pk:{0,1}^k -> {0,1}^k be a trapdoor
one-way permutation, with inverse I_sk. Define the length-preserving
one-way permutation F*_pk, whose domain is the set S of all bit-strings
of length at least k, so that F*_pk(x,y) = (F_pk(x),y) if len(x)=k, and
define I*_sk to be its corresponding inverse. Consider the following
signature scheme on messages of length at least k:
Sign_sk(m) = I*_sk(Pi(m)).
Open_pk(s) = Pi^{-1}(F*_pk(s)).
Conjecture: This provides reasonable security, for appropriate
parameter choices. I haven't tried to prove it, but it may be
possible to adapt the proof of security for Full Domain Hash to this
construction.

For example, given a random oracle (hash function), we can construct
Pi,Pi^{-1} using the four-round Luby-Rackoff construction, and we
might instantiate F_pk,I_sk using RSA or Rabin (squaring mod n).
Of course, this won't help you with very short messages (shorter than
k bits long), but maybe it is enough for some applications. What do
you think?