[Cryptography] Formal definition of lightweight crypto

[Jerry Leichter]

> ...This is the idea of lightweight crypto. It is doing something useful — an authenticity seal that might otherwise be done by a plastic hologram seal or whatever — but it's not something that will keep a government out. It's just more expensive to make a counterfeit seal than the product is worth.
> 
> That's kinda the idea. Weak, and yet still useful. And more importantly it can be run on very cheap hardware as well.
That's an odd definition.  After all, in some sense you can apply it to any security system:  There's no such thing as absolute security, but if the cost of breaking the security exceeds the value of what's being protected (suitably computed - all secondary effects included) then any additional expenditure on security is wasted.

It's also highly technology-dependent.  Even the weakest reasonable processor available today is pretty strong compared to the strongest processor available 30 years ago.  In the example you gave that I elided, you talked about "50-60 bits of security" - i.e., about as strong as DES, which for quite some time after it was introduced was at the limits of practical implementability with hardware of reasonable cost.

"Lightweight" implies a binary criterion.  What it doesn't *necessarily* imply, to me, is anything about strength.

Personally, I'd focus just on the hardware requirements:  Lightweight cryptography allows for some kind of useful cryptographic operation using very cheap, widely available hardware.  The definition is inherently technology-based and will shift over time, though more slowly than you might expect because the primary use case is in various kinds of embedded systems, which themselves change relatively slowly.

To achieve the goal of light weight, various tradeoffs might need to be made.  Strength may well be one.  But you could imagine, for example, a system which had a very cheap encryption operation but a much more expensive decryption operation - suitable for remote systems that have to "report home" securely but never, or almost never, need to receive secure commands.  (I don't know of any such systems; the closest idea is using small exponents to make RSA signature *generation* cheap at the expense of making signature *checking* more expensive.  The mechanisms we currently use for constructing symmetric cryptosystems do pretty much if not exactly the same operations in both directions, so none will have this property; but that doesn't mean there aren't ways to construct such primitives.  We've just never had reason to look for them.  Note that if you can make either direction cheap while the other direction is expensive, you can do two-way communication between a cheap remote and a strong center.  And, yes, you could make both directions cheap by using counter mode based on the "cheap" side - but perhaps a tradeoff in the system is that isn't very secure against encrypting large numbers of blocks with small Hamming distance between them.)

                                                        -- Jerry