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-----