88 problems

Let $G$ be a finite simple group, and let a logarithmic signature of $G$ mean a factorized description of the elements of $G$ whose length is measured by the number of factors in t…

Let $k$ be a positive integer and let $t\in\{1,\ldots,2^k-2\}$. Write $s(n)$ for the number of $1$s in the base-$2$ expansion of $n$. Consider pairs $(a,b)$ in…

Zhang–Zheng's conjecture. The absolute indicator of $f$ is at least

Let $p$ and $q$ be prime, and let $G$ be a subgroup of order $q$ of ${\mathbb Z_p^*}$, with $g$ a divisor of $p-1$. The DDH assumption is the claim that no efficient distinguisher…

Let $m$ be a positive integer and let $\mathbb{F}_{2^m}$ be the finite field with $2^m$ elements. A function $F:\mathbb{F}_{2^m}\to\mathbb{F}_{2^m}$ is almost perfect nonlinear (AP…

Constructive membership testing difficulty conjecture. CMT is difficult whenever the group $G$ either involves a large abelian group as a quotient of a normal subgroup or has nonab…

Let $\mathcal{F}'$ be the modified oracle using the truncated CCL process with $l=\log N$, an oracle $\mathsf{RND}_3$ making $k$ calls to a permutation oracle, and parameters as de…

Let $S_N$ be the symmetric group on $N$ elements. A random cyclus is a uniformly random permutation in $S_N$ with a prescribed cycle structure, as obtained by conjugating a fixed f…

Let $C\subseteq\mathbb{F}_q^n$ be a random linear code of dimension $k$, and let its cube code be $C^{(3)}=C\ast C\ast C$, where $\ast$ denotes the Schur product of linear codes. C…

Let $E_{f,g,h}$ denote the sequence produced by the construction from three polynomials $f$, $g$, and $h$, whose pseudorandom properties are measured by the associated quantities s…

Topological exactness conjecture. If $T$ is topologically exact and the system admits a hard telic problem, then there exists an almost-everywhere $\delta$ hard-on-average telic pr…

An APN function on $\mathbf{GF}(2^n)$ is a function for which, for every nonzero $a\in\mathbf{GF}(2^n)$ and every $b\in\mathbf{GF}(2^n)$, the equation $f(x+a)+f(x)=b$ has at most t…

Let $f$ be a function, let … and let $h(L_f)$ denote the homological complexity of the inversion problem associated with $f$. Homological characterization of one-way functions. The…

Let $n$ be a positive integer, let $\mathbb{F}_2$ be the field with two elements, and let $\chi_n$ denote the mapping obtained from the coordinate rule $y_i=x_i+(x_{i+1}+1)x_{i+2}$…

Let $f\colon \mathbb F_{2^n}\to\mathbb F_{2^n}$ be a crooked function. Quadraticity conjecture. The function $f$ must be quadratic. This is motivated by the fact that all currently…

Zero-correctness conjecture.

Sum-freeness conjecture. For odd $n\ge 7$,

Sum-freedom conjecture for the multiplicative inverse function. For even $n$, $F_{\operatorname{inv}}$ is not $k$th order sum-free for $2\le k\le n-2$. For odd $n$,…

Boomerang-uniformity conjecture. Then

Let $V=V_1\oplus\cdots\oplus V_m$, with $V_i\simeq (\mathbb{F}_2)^n$ for $i=1,\ldots,m$, and let $\circ=(\circ_1,\ldots,\circ_m)$ be a parallel alternative operation as in Section…

Tokareva–Shapovalov conjecture. The function $f$ is a derivative of a bent function.

Let an RSA-type semiprime be a product of two suitably large primes, and let Shor's algorithm denote the quantum algorithm for integer factorisation. Quantum factorisation conjectu…

Let $XYZ$ be the candidate distribution described immediately before the claim, and let $P_{\overline{X}|X}$ and $P_{\overline{Y}|Y}$ range over binarization channels. The Z-shaped…

Let $XYZ$ be the distribution displayed in the source, depending on a parameter $a$. The candidate-distribution binarization conjecture. There exists a value $a$ such that, for eve…

Let $a_{ij}:=P_{\overline{Y^2}|Y^2}(0,rs)$ for $r,s\in\{1,2,3\}$, and define $\tau_2$ on the indicated set by … where $j=\left\lceil i/2\right\rceil$ for $1\leq i\leq6$, and … The…