2
$\begingroup$

I would like to understand the typical size of a lookup table for software implementations of a cryptographic scheme.

  1. What size is considered reasonable?
  2. What make them (in)efficient?
  3. Are there heuristics to determine (without implementing anything) if a table will become interesting?
Improve this question
$\endgroup$
1
  • $\begingroup$ What is a cryptographic lookup table? $\endgroup$
    – Paul Uszak
    Sep 11, 2017 at 21:21

1 Answer 1

Reset to default
3
$\begingroup$

This is a very / too generic question:

Q1: What size is considered reasonable?

Any size that fits easily in the CPU cache(s) of the target platform. Otherwise it depends on the memory requirements for the algorithm in general.

Q2: What make them (in)efficient?

If the CPU data cache needs to be refreshed continuously then they may slow down the algorithm and, if you're unlucky, leak side channel information as well.

Q3: Are there heuristics to determine (without implementing anything) if a table will become interesting?

Probably not as it depends a lot on specifics of the underlying platform.

In general lookup tables are used to speedup calculations, so as long as the resulting implementation is faster, you're in business.

But note that there may be security implications when using them, all depending on what is being implemented.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your answer. As regards question 3, for instance, I was wondering if a table that can fit only in L3 cache but not in L2, nor L1, could produce a significant performance gain? $\endgroup$
    – Dingo13
    Sep 11, 2017 at 13:22
  • $\begingroup$ There is one way to find out: try. Because it certainly depends on what it is that it is replacing. If that (partial) algorithm is fast then probably not; if it is slow then it may be worth the cost. All caches are not created equal either. $\endgroup$
    – Maarten Bodewes ♦
    Sep 11, 2017 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.