Decimal encryption

Hovav Shacham hovav at
Wed Aug 27 22:16:08 EDT 2008

----- "Jonathan Katz" <jkatz at> wrote:

 > But he probably wants an encryption scheme, not a cipher.

Jon, I'm not sure I understand what you mean.

If I am reading his message correctly, the original poster seems
to be asking for a format-preserving encryption over a domain
with 10^40 elements.  Format-preserving, it seems to me, implies
[a family of keyed] functions that are one-to-one and
deterministic.  In other words, the best security we can hope for
is a PRP on that domain, and this is what B-R gives, starting
from a PRP over a "somewhat larger" domain.

In this setting, what is the difference between an encryption
scheme and a cipher?

 > Also, correct me if I am wrong, but Black and Rogaway's
 > approach is not efficient for large domains. But if you use
 > their approach for small domains then you open yourself up to
 > dictionary attacks.

I think the dependency depends on the amount by which the domain
of the constructed PRP is smaller than the domain of the starting
PRP.  A 133-bit B-R would indeed be inefficient to construct from
a 256-bit block cipher like Rijndael, and one would need a
different starting point; but these could be constructed using a
Feistel of appropriate size.

Is the dictionary attack problem any more severe than for any
other PRP over a small domain?  The best one can hope for is a
security guarantee for a number of queries approaching the size
of the domain -- or to ensure that in practical deployment access
to the encryption and decryption functionality is constrained.

Yours --

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at

More information about the cryptography mailing list