Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / multiplicative complexity, Boolean functions, interval checking

Date: received 25 Jan 2022

Contact author: mathias soeken at outlook com

Available format(s): PDF | BibTeX Citation

Version: 20220131:074145 (All versions of this report)

Short URL: ia.cr/2022/091


[ Cryptology ePrint archive ]