2004-06-09 11:12:07 UTC
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
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
- 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:
- apply some reversible random-like transform to m,
giving c = T(m) of same size k as the original
- output s = (c ^ d) % n
- 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
- 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).