Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR24-018 | 12th September 2024 17:18

The more the merrier! On total coding and lattice problems and the complexity of finding multicollisions

RSS-Feed




Revision #2
Authors: Huck Bennett, Surendra Ghentiyala, Noah Stephens-Davidowitz
Accepted on: 12th September 2024 17:18
Downloads: 20
Keywords: 


Abstract:

We study the problem of finding multicollisions, that is, the total search problem in which the input is a function $\mathcal{C} : [A] \to [B]$ (represented as a circuit) and the goal is to find $L \leq \lceil A/B \rceil$ distinct elements $x_1,\ldots, x_L \in A$ such that $\mathcal{C}(x_1) = \cdots = \mathcal{C}(x_L)$. The associated complexity classes Polynomial Multi-Pigeonhole Principle ($(A,B)$-$PMPP^L$) consist of all problems that reduce to this problem.

We show close connections between $(A,B)$-$PMPP^L$ and many celebrated upper bounds on the minimum distance of a code or lattice (and on the list-decoding radius). In particular, we show that the associated computational problems (i.e., the problem of finding distinct codewords or lattice points that lie in a certain small ball) are in $(A,B)$-$PMPP^L$, with a more-or-less smooth tradeoff between the distance and the parameters $A$, $B$, and $L$. These connections are particularly rich in the case of codes, in which case we show that multiple incomparable bounds on the minimum distance lie in seemingly incomparable complexity classes. Surprisingly, we also show that some bounds on the minimum distance are actually complete for these classes (for codes represented by arbitrary circuits).

We go on to study $(A,B)$-$PMPP^L$ as an interesting family of complexity classes in their own right, and we uncover a rich structure. We first show that techniques that were recently developed in the cryptographic literature on multicollision-resistant hash functions can be applied in our setting. Specifically, we show inclusions of the form $(A,B)$-$PMPP^L \subseteq (A',B')$-$PMPP^{L'}$ for certain non-trivial parameters, black-box separations between such classes in different parameter regimes, and a non-black-box proof that $(A,B)$-$PMPP^{L} \in FP$ if $(A',B')$-$PMPP^{L'} \in FP$ for yet another parameter regime. We also show that $(A,B)$-$PMPP^L$ lies in the recently introduced complexity class Polynomial Long Choice for some parameters.


Revision #1 to TR24-018 | 11th September 2024 06:01

The more the merrier! On the complexity of finding multicollisions, with connections to codes and lattices





Revision #1
Authors: Huck Bennett, Surendra Ghentiyala, Noah Stephens-Davidowitz
Accepted on: 11th September 2024 06:01
Downloads: 14
Keywords: 


Abstract:

We show a number of connections between two types of search problems: (1) the problem of finding an $L$-wise multicollision in the output of a function; and (2) the problem of finding two codewords in a code (or two vectors in a lattice) that are within distance $d$ of each other. Specifically, we study these problems in the total regime, in which $L$ and $d$ are chosen so that such a solution is guaranteed to exist, though it might be hard to find.

In more detail, we study the total search problem in which the input is a function $\mathcal{C} : [A] \to [B]$ (represented as a circuit) and the goal is to find $L \leq \lceil{A/B}\rceil$ distinct elements $x_1,\ldots, x_L \in A$ such that $\mathcal{C}(x_1) = \cdots = \mathcal{C}(x_L)$. The associated complexity classes Polynomial Multi-Pigeonhole Principle ($(A,B)$-$\mathsf{PMPP}^L$) consist of all problems that reduce to this problem.

We show close connections between $(A,B)$-$\mathsf{PMPP}^L$ and many celebrated upper bounds on the minimum distance of a code or lattice (and on the list-decoding radius). In particular, we show that the associated computational problems (i.e., the problem of finding two distinct codewords or lattice points that are close to each other) are in $(A,B)$-$\mathsf{PMPP}^L$, with a more-or-less smooth tradeoff between the distance $d$ and the parameters $A$, $B$, and $L$. These connections are particularly rich in the case of codes, in which case we show that multiple incomparable bounds on the minimum distance lie in seemingly incomparable complexity classes.

Surprisingly, we also show that the computational problems associated with some bounds on the minimum distance of codes are actually hard for these classes (for codes represented by arbitrary circuits). In fact, we show that finding two vectors within a certain distance $d$ is actually hard for the important (and well-studied) class $\mathsf{PWPP} = (B^2,B)\text{-}\mathsf{PMPP}^2$ in essentially all parameter regimes for which an efficient algorithm is not known, so that our hardness results are essentially tight. In fact, for some $d$ (depending on the block length, message length, and alphabet size), we obtain both hardness and containment. We therefore completely settle the complexity of this problem for such parameters and add coding problems to the short list of problems known to be complete for $\mathsf{PWPP}$.

We also study $(A,B)$-$\mathsf{PMPP}^L$ as an interesting family of complexity classes in its own right, and we uncover a rich structure. Specifically, we use recent techniques from the cryptographic literature on multicollision-resistant hash functions to (1) show inclusions of the form $(A,B)\text{-}\mathsf{PMPP}^L \subseteq (A',B')\text{-}\mathsf{PMPP}^{L'}$ for certain non-trivial parameters; (2) black-box separations between such classes in different parameter regimes; and (3) a non-black-box proof that $(A,B)\text{-}\mathsf{PMPP}^{L} \in \mathsf{FP}$ if $(A',B')\text{-}\mathsf{PMPP}^{L'} \in \mathsf{FP}$ for yet another parameter regime. We also show that $(A,B)$-$\mathsf{PMPP}^L$ lies in the recently introduced complexity class Polynomial Long Choice for some parameters.


Paper:

TR24-018 | 28th January 2024 01:09

The more the merrier! On the complexity of finding multicollisions, with connections to codes and lattices





TR24-018
Authors: Huck Bennett, Surendra Ghentiyala, Noah Stephens-Davidowitz
Publication: 28th January 2024 15:14
Downloads: 406
Keywords: 


Abstract:

We study the problem of finding multicollisions, that is, the total search problem in which the input is a function $\mathcal{C} : [A] \to [B]$ (represented as a circuit) and the goal is to find $L \leq \lceil A/B \rceil$ distinct elements $x_1,\ldots, x_L \in A$ such that $\mathcal{C}(x_1) = \cdots = \mathcal{C}(x_L)$. The associated complexity classes Polynomial Multi-Pigeonhole Principle ($(A,B)$-$\rm{PMPP}^L$) consist of all problems that reduce to this problem.

We show close connections between $(A,B)$-$\rm{PMPP}^L$ and many celebrated upper bounds on the minimum distance of a code or lattice (and on the list-decoding radius). In particular, we show that the associated computational problems (i.e., the problem of finding distinct codewords or lattice points that lie in a certain small ball) are in $(A,B)$-$\rm{PMPP}^L$, with a more-or-less smooth tradeoff between the distance and the parameters $A$, $B$, and $L$. These connections are particularly rich in the case of codes, in which case we show that multiple incomparable bounds on the minimum distance lie in seemingly incomparable complexity classes. Surprisingly, we also show that some bounds on the minimum distance are actually complete for these classes (for codes represented by arbitrary circuits).

We go on to study $(A,B)$-$\rm{PMPP}^L$ as an interesting family of complexity classes in their own right, and we uncover a rich structure. We first show that techniques that were recently developed in the cryptographic literature on multicollision-resistant hash functions can be applied in our setting. Specifically, we show inclusions of the form $(A,B)\text{-}\rm{PMPP}^L \subseteq (A',B')\text{-}\rm{PMPP}^{L'}$ for certain non-trivial parameters, black-box separations between such classes in different parameter regimes, and a non-black-box proof that $(A,B)\text{-}\rm{PMPP}^{L} \in \rm{FP}$ if $(A',B')\text{-}\rm{PMPP}^{L'} \in \rm{FP}$ for yet another parameter regime. We also show that $(A,B)$-$\rm{PMPP}^L$ lies in the recently introduced complexity class Polynomial Long Choice for some parameters.



ISSN 1433-8092 | Imprint