International Association
for Cryptologic Research

The arithmetic of computing multiple scalar multiplications in an elliptic curve group then adding them together is called multi-scalar multiplication (MSM). MSM over fixed points dominates the time consumption in the pairing-based trusted setup zero-knowledge succinct non-interactive argument of knowledge (zkSNARK), thus for practical applications we would appreciate fast algorithms to compute it. This paper proposes a bucket set construction that can be utilized in the context of Pippenger’s bucket method to speed up MSM over fixed points with the help of precomputation. If instantiating the proposed construction over BLS12-381 curve, when computing n-scalar multiplications for n = 2e (10 ≤ e ≤ 21), theoretical analysis ndicates that the proposed construction saves more than 21% computational cost compared to Pippenger’s bucket method, and that it saves 2.6% to 9.6% computational cost compared to the most popular variant of Pippenger’s bucket method. Finally, our experimental result demonstrates the feasibility of accelerating the computation of MSM over fixed points using large precomputation tables as well as the effectiveness of our new construction.

Many block ciphers use permutations defined over the finite field F22k with low differential uniformity, high nonlinearity, and high algebraic degree to provide confusion. Due to the lack of knowledge about the existence of almost perfect nonlinear (APN) permutations over F22k, which have lowest possible differential uniformity, when k > 3, constructions of differentially 4-uniform permutations are usually considered. However, it is also very difficult to construct such permutations together with high nonlinearity; there are very few known families of such functions, which can have the best known nonlinearity and a high algebraic degree. At Crypto’16, Perrin et al. introduced a structure named butterfly, which leads to permutations over F22k with differential uniformity at most 4 and very high algebraic degree when k is odd. It is posed as an open problem in Perrin et al.’s paper and solved by Canteaut et al. that the nonlinearity is equal to 22k−1−2k. In this paper, we extend Perrin et al.’s work and study the functions constructed from butterflies with exponent e = 2i + 1. It turns out that these functions over F22k with odd k have differential uniformity at most 4 and algebraic degree k +1. Moreover, we prove that for any integer i and odd k such that gcd(i, k) = 1, the nonlinearity equality holds, which also gives another solution to the open problem proposed by Perrin et al. This greatly expands the list of differentially 4-uniform permutations with good nonlinearity and hence provides more candidates for the design of block ciphers.