| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

1. Codes

    1. Problem 1.1.

      [Edoardo Persichetti] Parameters: $n \geq 1$, $r\geq 1$, $\mathbb F_{q^m}$, $t \geq 1$. How quickly can we find $v\in \mathbb F_{q^m}^n$ with $Hv = s$ and $\text{wt}(v) = t$, given $H\in \mathbb F_{q^m}^{r\times n}$ and $s\in \mathbb F_{q^m}^r$?

      Here, $\text{wt}(v)$ is defined to be the rank of the $v$, viewed as a matrix with $n$ columns.
        • Problem 1.2.

          [Tanja Lange] Given a parity-check matrix $H$, find the hidden Goppa code in $H$. How quickly can we decode $H$, assuming Goppa decoder for $H$ exists?
            • Problem 1.3.

              What witnesses are there of Goppa decodability or non-decodability?

                  Cite this as: AimPL: Quantum algorithms for analysis of public-key crypto, available at http://aimpl.org/quantumalg.