Paper 2022/091

The multiplicative complexity of interval checking

Thomas Häner and Mathias Soeken

Abstract

We determine the exact AND-gate cost of checking if $a\leq x < b$, where $a$ and $b$ are constant integers. Perhaps surprisingly, we find that the cost of interval checking never exceeds that of a single comparison and, in some cases, it is even lower.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
multiplicative complexityBoolean functionsinterval checking
Contact author(s)
mathias soeken @ outlook com
History
2022-01-31: received
Short URL
https://ia.cr/2022/091
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/091,
      author = {Thomas Häner and Mathias Soeken},
      title = {The multiplicative complexity of interval checking},
      howpublished = {Cryptology ePrint Archive, Paper 2022/091},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/091}},
      url = {https://eprint.iacr.org/2022/091}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.