Mathematics Problem Archive

Develop methods to factor an integer when the known bits of its factors are nonconsecutive....

Reduce the number of guesses required by lattice attacks for factoring with partially known bits....

Extract useful information from incorrect guesses in factoring attacks based on partially known bits....

Efficiently solve for, or characterize all relevant roots of, $x^2-1$ modulo a composite integer $N$ in the setting of the slides....

Improve the running time of Coppersmith-type methods for finding small modular or integer roots....

Understand and control how the shape of a polynomial affects Coppersmith-type small-root algorithms....

Give conditions or constructions that ensure algebraic independence in multivariate elimination for small-root attacks....

Find an optimal collection of polynomials for multivariate lattice-based small-root attacks....

Determine whether the lattice dimension in the stated small-root constructions can be reduced....

Resolve the zero-constant-term case in the Newton-polytope formulation of multivariate small-root methods....

Construct additional cryptographic primitives whose security follows from the hardness of finding small roots....

Analyze how effective rotation-augmented lattice reduction is on cyclic or NTRU lattices....

Speed up rotation-augmented reduction algorithms for cyclic or NTRU lattices....

For large $N$, efficiently find the required short five-term geometric progressions modulo $N$ that avoid first- and second-order recurrence, thereby ...

Study the distribution of group structures $E(\mathbb{F}_q)$ as elliptic curves $E/\mathbb{F}_q$ vary; in particular, determine the correct nonuniform...

Is the exponent $e_q(E)$ of $E(\mathbb{F}_q)$ typically close to $q$?...

How often is the group of a random elliptic curve over $\mathbb{F}_q$ cyclic?...

Characterize the typical arithmetic structure of $\#E(\mathbb{F}_q)$ for elliptic curves over finite fields....

Prove that there are sufficiently many prime-order elliptic curves over every finite field $\mathbb{F}_q$....

For a fixed $E/\mathbb{F}_q$, prove that $\#E(\mathbb{F}_{q^n})/\#E(\mathbb{F}_q)$ is prime for infinitely many $n$....

For a torsion-free elliptic curve $E/\mathbb{Q}$, prove that $\#E(\mathbb{F}_p)$ is prime for infinitely many primes $p$....

Prove that sufficiently many elliptic curves $E/\mathbb{F}_p$ have smooth group order $\#E(\mathbb{F}_p)$....

Quantify elliptic curves over finite fields whose group order has a large prime divisor....

Prove the conjecture that the EC-LCG, EC-PG, and EC-NRG sequences defined in the slides are very well distributed....

Given integers $n$ and a prime power $q$, construct, when possible, an elliptic curve $E/\mathbb{F}_q$ with $\#E(\mathbb{F}_q)=n$....

Given $n$, efficiently choose a prime power $q$ and construct an elliptic curve $E/\mathbb{F}_q$ with $\#E(\mathbb{F}_q)=n$....

Given the Weil polynomial of an abelian-threefold isogeny class over a finite field, determine whether the class contains a Jacobian....

Decide whether a given principally polarized abelian threefold over a field $k$ is the Jacobian of a curve over $k$....

Give an effective input representation for a principally polarized abelian threefold suitable for deciding whether it is a Jacobian....

Combine the Meagher–Ritzenthaler criteria with Deligne modules to detect Jacobians in an ordinary absolutely simple abelian-threefold isogeny class....

For fixed $q$, is $N_q(g)=\max_C\#C(\mathbb{F}_q)$ increasing as a function of the genus $g$?...

Find a sharp upper bound for the shortest-vector length in an $n$-dimensional positive-definite Hermitian space of determinant $d$ over an imaginary q...

Speed up the computation of cryptographic pairings....

Find more MNT curves, including usable larger embedding degrees, more curve families, and smaller cofactors....

Construct pairing-friendly hyperelliptic curves suitable for cryptography....

Determine the exact computational-speed and security tradeoff for genus-four curves used in pairing cryptography....

Find an attack that breaks the pairing-based cryptographic system discussed in the slides, or establish its resistance to known attacks....

Break, or determine the true hardness of, the weaker security assumptions used in pairing-based cryptography....

Update Joux's 2002 work by developing a systematic taxonomy of pairing-related computational assumptions....

Is the Decision Linear problem strictly harder than the decisional Diffie–Hellman problem in the relevant pairing groups?...

Give the cited pairing-based signature constructions and their security proofs without relying on distortion maps....

Determine the computational hardness of the Pairing Inversion Problem....

Prove that general SVP and SIVP are hard in the worst case to approximate within small polynomial factors....

Prove an analogous small-polynomial-factor worst-case hardness result for SVP and SIVP on ideal lattices....

Is the shortest vector problem on ideal or cyclic lattices NP-hard, either exactly or under approximation?...

Is the minimum-distance problem for cyclic codes NP-hard?...

Reduce computational problems on arbitrary lattices to corresponding problems on cyclic or ideal lattices....

Does SVP reduce to CVP while remaining inside the class of cyclic or ideal lattices?...

Exhibit cyclic or ideal lattices on which LLL achieves its worst-case approximation factor....

Develop an algebraic analogue of the LLL lattice-reduction algorithm that exploits ideal-lattice structure....