Francois Grieu

2004-06-09 11:12:07 UTC

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

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