36 problems

For every pair of positive integers $n,k$ with $\gcd(k,n)=1$, let $F:\mathbb{F}_{2^n}\to\mathbb{F}_{2^n}$ be defined by $F(x)=x^{4^k-2^k+1}$, and let…

…

Given a modular polynomial equation $f(x_1,\ldots,x_n)\equiv 0\pmod N$ and the associated lattice-based Coppersmith method, determine the optimal asymptotic region of exponents…

For an $n$-party monotone access structure $\Gamma\subseteq 2^{[n]}$, let $\ell_{\Gamma}$ be the minimum, over all linear secret-sharing schemes for one-bit secrets realizing…

Determine the supremum of the exponents $\alpha$ for which the following holds: for every fixed $\varepsilon>0$, there is a deterministic polynomial-time algorithm that, given a ba…

For $N=2^n$, let $s\in\mathbb{Z}_N$ be hidden. Given polynomially many independent copies of the mixed coset state…

Budaghyan–Carlet–Helleseth conjecture. No APN function $F \colon \mathbb{F}_2^n \to \mathbb{F}_2^n$ has algebraic degree $n$ for all $n \geq 3$.

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…

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 and let $f_{\text{inv}}:\mathbb F_{2^n}\to\mathbb F_{2^n}$ be defined by … A function is $k$th order sum-free if the sum of its values is nonzero on e…

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$,…

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

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…

Let $X,Y,Z$ have the distribution specified in the source, with $Z$ determined by $X$ and $Y$ according to the displayed table. For $N\geq1$, let $\overline{Y^N}$ be any binary out…

Let $X,Y,Z$ be jointly distributed, and let $\overline{X}$ and $\overline{Y}$ be binary outputs of arbitrary binary output channels applied to $X$ and $Y$. For $N\geq 1$, let…

Let $X,Y,Z$ be jointly distributed random variables, and let $S(X:Y||Z)$ denote the secret-key rate and $I(X:Y \downarrow Z)$ the intrinsic information. The bound-secrecy conjectur…

Let $P_{XYZ}$ be a probability distribution. The Renner–Wolf conjecture. … The reduced intrinsic information is a known upper bound on the secret-key rate and can be strictly small…

New toy conjecture. The distributions $(S_1,\ldots,S_m)$ and $(T_1,\ldots,T_m)$ are computationally indistinguishable.

Toy conjecture. The distributions $(S_1,\ldots,S_m)$ and $(T_1,\ldots,T_m)$ are computationally indistinguishable.

Let $G_p$ be the graph of Markoff triples modulo a prime $p$, and let a triple in $G_p$ be lifted to a triple in the Markoff tree over $\mathbb Z$. The lifting-length conjecture st…

PcN power-exponent conjecture. For all $0\leq j\leq 6$, the only possible values of $d$ are the elements of

Let $q=2^n$ with $n$ odd and $\gcd(i,n)=1$. For … set … Let $\Gamma$ be the parameter set defined in equation. Butterfly permutation parameter conjecture. If $V_i$ is a permutation…

Let $T$ be the total time considered above, with expectation and variance denoted by $\mathbb E[T]$ and $\operatorname{Var}(T)$, and let $N$ and $M$ be the parameters satisfying…