Journal of Applied Mathematics and Computing Прикладная математика

Design of two cryptographic functions from bose-type Sidon sets with differential 2-uniformity and near-optimal linearity

Julian Osorio, Carlos Trujillo, Diego Ruiz
Springer Nature · 2026-06-01 · DOI 10.1007/s12190-026-02828-6

Аннотация

Abstract Sidon sets, defined by the property that every sum of any two elements is distinct, play a significant role in areas such as coding theory and cryptography. In this paper, we study two cryptographic functions, $$\boldsymbol{f_q}$$ and $$\boldsymbol{g_q}$$ , constructed from Bose-type Sidon sets. These functions exhibit three key cryptographic properties: low differential uniformity, uniform output distribution, and low linearity. The first ensures consistent sensitivity to input changes, offering resistance against differential cryptanalysis, as both functions achieve differential $$\boldsymbol{2}$$ -uniformity, the lowest non-trivial value possible, thus guaranteeing maximum theoretical resistance. The second maximizes entropy by ensuring a uniform output distribution, thereby avoiding statistical biases that attackers could exploit. The third property exhibits different behavior between the two functions: while $$\boldsymbol{f_p}$$ demonstrates linear growth $$\boldsymbol{\mathcal{L}(f_p) \approx 0.637p}$$ , the function $$\boldsymbol{g_p}$$ achieves remarkably low linearity, empirically characterized by $$\boldsymbol{\mathcal{L}(g_p) \approx 1.89\sqrt{p}}$$ , which is close to the optimal bound $$\sqrt {\boldsymbol{p}} $$ , providing superior resistance to linear cryptanalysis. This linearity result is supported by extensive computational evidence and is presented as a well-founded conjecture, whose analytical proof remains an open problem. We provide theoretical characterizations of these properties and validate them through comprehensive statistical testing, including lattice tests, Q-Q plots and chi-square tests, demonstrating their suitability for symmetric-key cryptography applications.

Читать у издателя →