CoolTest: Improved Randomness Testing Using Boolean Functions

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F25%3A00140774" target="_blank" >RIV/00216224:14330/25:00140774 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-031-92886-4_1" target="_blank" >http://dx.doi.org/10.1007/978-3-031-92886-4_1</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-031-92886-4_1" target="_blank" >10.1007/978-3-031-92886-4_1</a>

Jazyk výsledku

angličtina

Název v původním jazyce

CoolTest: Improved Randomness Testing Using Boolean Functions

Popis výsledku v původním jazyce

In this work, we present a new randomness test, CoolTest. CoolTest finds the optimal Boolean function from functions over $k$ variables for distinguishing tested data from random. CoolTest generalizes and improves BoolTest (ICETE'17) as it can find an arbitrary correlation among $k$ variables with comparable complexity, while BoolTest searches only for functions of a predefined form. CoolTest uses the innovative idea of Chatterjee et al. (INDOCRYPT'22), allowing to test $2^{2^k}$ Boolean functions while evaluating only $2^k$ of them. The test of Chatterjee et al. works only for rare cases when the correlated bits are close in the data. CoolTest makes the idea practically usable by selecting only a subset of bits on which it looks for a distinguisher. We evaluated CoolTest on outputs of 14 reduced-round cryptographic functions (e.g., AES, Twofish, Keccak, MD5). The results show that CoolTest significantly improves compared to BoolTest in almost all cases. On 100 MB of data, CoolTest provides better results for SHA-2, SHA-1, MD6, and SHACAL-2 than statistical test suites NIST STS, Dieharder, and TestU01, which consist of many different tests. We provide an estimate of the amount of data necessary to find a distinguisher based on the type and relative frequency of a non-random pattern.

Název v anglickém jazyce

CoolTest: Improved Randomness Testing Using Boolean Functions

Popis výsledku anglicky

In this work, we present a new randomness test, CoolTest. CoolTest finds the optimal Boolean function from functions over $k$ variables for distinguishing tested data from random. CoolTest generalizes and improves BoolTest (ICETE'17) as it can find an arbitrary correlation among $k$ variables with comparable complexity, while BoolTest searches only for functions of a predefined form. CoolTest uses the innovative idea of Chatterjee et al. (INDOCRYPT'22), allowing to test $2^{2^k}$ Boolean functions while evaluating only $2^k$ of them. The test of Chatterjee et al. works only for rare cases when the correlated bits are close in the data. CoolTest makes the idea practically usable by selecting only a subset of bits on which it looks for a distinguisher. We evaluated CoolTest on outputs of 14 reduced-round cryptographic functions (e.g., AES, Twofish, Keccak, MD5). The results show that CoolTest significantly improves compared to BoolTest in almost all cases. On 100 MB of data, CoolTest provides better results for SHA-2, SHA-1, MD6, and SHACAL-2 than statistical test suites NIST STS, Dieharder, and TestU01, which consist of many different tests. We provide an estimate of the amount of data necessary to find a distinguisher based on the type and relative frequency of a non-random pattern.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2025

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

ICT Systems Security and Privacy Protection. SEC 2025. IFIP Advances in Information and Communication Technology

ISBN

9783031928857

ISSN

1868-4238

e-ISSN

—

Počet stran výsledku

15

Strana od-do

3-17

Název nakladatele

Springer Nature Switzerland

Místo vydání

Cham

Místo konání akce

Maribor, Slovenia

Datum konání akce

21. 5. 2025

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

001544590800001