The selection of parameters that offer best possible performance while simultaneously guaranteeing a well-defined level of security is one of the most challenging tasks in cryptographic system design. In order to ensure that the chosen parameters offer a certain level of security an estimation of the computational complexity of the underlying hard problem is required. To date, those estimations are often performed in an ad-hoc manner. This led to a scattered landscape of available estimation scripts, with multiple scripts for the same problem with varying outputs.

Due to its amazing speed and multiplicative properties the Legendre PRF recently finds widespread applications e.g. in Ethereum 2.0, multiparty computation and in the quantum-secure signature proposal LegRoast. However, its security is not yet extensively studied. The Legendre PRF computes for a key$k$on input$x$the Legendre symbol$L_{k}(x)=(\frac{x+k}{p})$in some finite field$\mathbb{F}_{p}$. As standard notion, PRF security is analysed by giving an attacker oracle access to$L_{k}(\cdot)$. Khovratovich's collision-based algorithm recovers$k$using$L_{k}(\cdot)$in time$\sqrt{p}$with constant memory. It is a major open problem whether this birthday-bound complexity can be beaten. We show a somewhat surprising wide-ranging analogy between the discrete logarithm problem and Legendre symbol computations. This analogy allows us to adapt various algorithmic ideas from the discrete logarithm setting. More precisely, we present a small memory multiple-key attack on$m$Legendre keys$k_{1}, \ldots, k_{m}$in time$\sqrt{mp}$, i.e. with amortized cost$\sqrt{p/m}$per key. This multiple-key attack might be of interest in the Ethereum context, since recovering many keys simultaneously maximizes an attacker's profit. Moreover, we show that the Legendre PRF admits precomputation attacks, where the precomputation depends on the public$p$only - and not on a key$k$. Namely, an attacker may compute e.g. in precomputation time$p^{\frac{2}{3}}$a hint of size$p^{\frac{1}{3}}$. On receiving access to$L_{k}(\cdot)$in an online phase, the attacker then uses the hint to recover the desired key$k$in time only$p^{\frac{1}{3}}$. Thus, the attacker's online complexity again beats the birthday-bound. In addition, our precomputation attack can also be combined with our multiple-key attack. We explicitly give various tradeoffs between precomputation and online phase. E.g. for attacking$m$keys one may spend time$mp^{\frac{2}{3}}$in the precomputation phase for constructing a hint of size$m^{2}p^{\frac{1}{3}}$. In an online phase, one then finds all$m$keys in total time only$p^{\frac{1}{3}}$. Precomputation attacks might again be interesting in the Ethereum 2.0 context, where keys are frequently changed such that a heavy key-independent precomputation pays off.

We study the Closest Pair Problem in Hamming metric, which asks to find the pair with the smallest Hamming distance in a collection of binary vectors. We give a new randomized algorithm for the problem on uniformly random input outperforming previous approaches whenever the dimension of input points is small compared to the dataset size. For moderate to large dimensions, our algorithm matches the time complexity of the previously best-known locality sensitive hashing based algorithms. Technically our algorithm follows similar design principles as Dubiner (IEEE Trans. Inf. Theory 2010) and May-Ozerov (Eurocrypt 2015). Besides improving the time complexity in the aforementioned areas, we significantly simplify the analysis of these previous works. We give a modular analysis, which allows us to investigate the performance of the algorithm also on non-uniform input distributions. Furthermore, we give a proof of concept implementation of our algorithm which performs well in comparison to a quadratic search baseline. This is the first step towards answering an open question raised by May and Ozerov regarding the practicability of algorithms following these design principles.