[messaging] Padding

[David Leon Gil]

Guy: Awesome to hear that!

Michael: Agreed; whether or not a padding scheme is optimal depends on the
prior. Mutual information sounds about right.

(The strongest case seems to be where unpadded message lengths are unique
labels, and the adversary knows the true pdf for unpadded message length.)

But optimization is fairly constrained; the expectation for message size
must (obviously) be finite, and padded messages must be at least as long as
unpadded messages.

(Yo is nearly optimal in the unconstrained case. (Sorry, couldn't resist.)
)

I've doodled a bit at various models to capture what's needed in the
strongest adversarial model; but thus far have only come up with
excessively complex models with no non-trivial analytic solutions.

(There's always the trivial solution for the delta - or, if
indistinguishability from an unpadded distribution isn't required, any
finitely bounded - distribution, which is just a delta function.)

I'm curious, however: What are the properties that people expect a message
padding scheme to achieve?

For padding alone, indistinguishability doesn't seem that useful, because
if the scheme is disclosed, the adversary knows whether padding is being
used. (Indistinguishability does seem to be useful if message delta-ts are
brought in.)

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

On 08/06/14 06:12, David Leon Gil wrote:
> *Min-entropy choice:* Exponential-padding, i.e., padding to the
> next-highest power of some constant, c. This asymptotically leaks
> a bounded amount of information. And it only costs O(n) space. I
> am puzzled why this is not the default for most messaging systems.

It seems to me that the information leak depends on the observer's
prior knowledge about possible message sizes. For example, if the
observer knows that the message is either "Yes" or "No" then padding
to the next power of two does nothing to conceal the message size
(which in turn reveals the content).

So perhaps the asymptotic behaviour isn't the best metric - but I
don't know what is.

> Q2.Are there any good publications on adversarial models for
> message padding?

I'd also be interested to know this.

Cheers,
Michael
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)

iQEcBAEBCAAGBQJTrG0hAAoJEBEET9GfxSfMsz8H/1ePZv+bGiJ0iHaQPkDTRRcv
b+EZu4541u4LITHdbl45q1h4eBXkGmgeH2+k7TqFbEDJaRPYDHqYlqA6CK+1UrU6
z3zq2xYXpxuOiVDb2lXopT9gUfb5SMQjnBBknINTIzcY98/vvQhgwoYt4R1m7Fu+
2E8BSEYjizhylZ1EvuryTWUrinvp0qvyQMPbmQFiz3JnfgVvHPbQiCUzNbs4IGB7
qwFvTDazGgTzQ5PeTMPuZbSexRXRgjhlL/3OIfVcqnvYe1UOkwBYceaZU9243q6r
dXsL5Ho6+pDzYZozisEqxWNTukxCb4g061CEFTa2eFPPi+oNFw2/McL5XQhr6sg=
=Rnp7
-----END PGP SIGNATURE-----
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20140701/3e2bb3a7/attachment.html>