CoolTest: Improved Randomness Testing Using Boolean Functions

D 2025

CoolTest: Improved Randomness Testing Using Boolean Functions

GAVENDA, Jiří a Marek SÝS

Základní údaje

Originální název

CoolTest: Improved Randomness Testing Using Boolean Functions

Autoři

GAVENDA, Jiří a Marek SÝS

Vydání

Cham, ICT Systems Security and Privacy Protection. SEC 2025. IFIP Advances in Information and Communication Technology, od s. 3-17, 15 s. 2025

Nakladatel

Springer Nature Switzerland

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Švýcarsko

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Odkazy

URL

Označené pro přenos do RIV

Ano

Organizační jednotka

Fakulta informatiky

ISBN

978-3-031-92886-4

DOI

https://doi.org/10.1007/978-3-031-92886-4_1

Klíčová slova anglicky

Statistical randomness testing; Boolean functions; Random number generators

Štítky

core_B, firank_B

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 6. 6. 2025 09:59, RNDr. Jiří Gavenda

Anotace

V originále

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ávaznosti

MUNI/A/1709/2024, interní kód MU

Název: Aplikovaný výzkum na FI: Důvěra v dynamických softwarových ekosystémech, kryptografické implementace včetně uživatelských aspektů, kyberbezpečnostní cvičení, fúze dat pro fyzikální sensory a algoritmy plánování v logistice

Investor: Masarykova univerzita, Aplikovaný výzkum na FI: Důvěra v dynamických softwarových ekosystémech, kryptografické implementace včetně uživatelských aspektů, kyberbezpečnostní cvičení, fúze dat pro fyzikální sensory a algoritmy plánování v logistice

Citovat

GAVENDA, Jiří a Marek SÝS. CoolTest: Improved Randomness Testing Using Boolean Functions. Online. In Lili Nemec Zlatolas, Kai Rannenberg, Tatjana Welzer, Joaquin Garcia-Alfaro. ICT Systems Security and Privacy Protection. SEC 2025. IFIP Advances in Information and Communication Technology. Cham: Springer Nature Switzerland, 2025, s. 3-17. ISBN 978-3-031-92886-4. Dostupné z: https://doi.org/10.1007/978-3-031-92886-4_1.

@inproceedings{2482401,
   author = {Gavenda, Jiří and Sýs, Marek},
   address = {Cham},
   booktitle = {ICT Systems Security and Privacy Protection. SEC 2025. IFIP Advances in Information and Communication Technology},
   doi = {https://doi.org/10.1007/978-3-031-92886-4_1},
   editor = {Lili Nemec Zlatolas, Kai Rannenberg, Tatjana Welzer, Joaquin Garcia-Alfaro},
   keywords = {Statistical randomness testing; Boolean functions; Random number generators},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Cham},
   isbn = {978-3-031-92886-4},
   pages = {3-17},
   publisher = {Springer Nature Switzerland},
   title = {CoolTest: Improved Randomness Testing Using Boolean Functions},
   url = {https://link.springer.com/chapter/10.1007/978-3-031-92886-4_1},
   year = {2025}
}

TY  - CONF
ID  - 2482401
AU  - Gavenda, Jiří - Sýs, Marek
PY  - 2025
TI  - CoolTest: Improved Randomness Testing Using Boolean Functions
PB  - Springer Nature Switzerland
CY  - Cham
SN  - 9783031928864
KW  - Statistical randomness testing
KW  - Boolean functions
KW  - Random number generators
UR  - https://link.springer.com/chapter/10.1007/978-3-031-92886-4_1
N2  - 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.
ER  -

GAVENDA, Jiří a Marek SÝS. CoolTest: Improved Randomness Testing Using Boolean Functions. Online. In Lili Nemec Zlatolas, Kai Rannenberg, Tatjana Welzer, Joaquin Garcia-Alfaro. \textit{ICT Systems Security and Privacy Protection. SEC 2025. IFIP Advances in Information and Communication Technology}. Cham: Springer Nature Switzerland, 2025, s.~3-17. ISBN~978-3-031-92886-4. Dostupné z: https://doi.org/10.1007/978-3-031-92886-4\_{}1.

Přehled o publikaci