Search

Abstract Verifiable delay functions (VDFs) and delay encryptions (DEs) are two important primitives in decentralized systems, while existing constructions are mainly based on time-lock puzzles. A disparate framework has been established by applying isogenies and pairings on elliptic curves. Following this line, we first employ Richelot isogenies and non-degenerate pairings from hyperelliptic curves for a new verifiable delay function, such that no auxiliary proof and interaction are needed for the verification. Then, we demonstrate that our scheme satisfies all security requirements, in particular, our VDF can resist several attacks, including the latest attacks for SIDH. Besides, resorting to the same techniques, a secure delay encryption from hyperelliptic curves is constructed by modifying Boneh and Frankiln’s IBE scheme, which shares the identical setup with our VDF scheme. As far as we know, these schemes are the first cryptographic applications from high-genus isogenies apart from basic protocols, i.e., hash functions and key exchange protocols.

Pairing-friendly curves with odd prime embedding degrees at the 128-bit security level, such as BW13-310 and BW19-286, sparked interest in the field of public-key cryptography as small sizes of the prime fields. However, compared to mainstream pairing-friendly curves at the same security level, i.e., BN446 and BLS12-446, the performance of pairing computations on BW13-310 and BW19-286 is usually considered inefficient. In this paper we investigate high performance software implementations of pairing computation on BW13-310 and corresponding building blocks used in pairing-based protocols, including hashing, group exponentiations and membership testings. Firstly, we propose efficient explicit formulas for pairing computation on this curve. Moreover, we also exploit the state-of-art techniques to implement hashing in G1 and G2, group exponentiations and membership testings. In particular, for exponentiations in G2 and GT , we present new optimizations to speed up computational efficiency. Our implementation results on a 64-bit processor show that the gap in the performance of pairing computation between BW13-310 and BN446 (resp. BLS12-446) is only up to 4.9% (resp. 26%). More importantly, compared to BN446 and BLS12-446, BW13-310 is about 109.1% − 227.3%, 100% − 192.6%, 24.5%−108.5% and 68.2%−145.5% faster in terms of hashing to G1, exponentiations in G1 and GT , and membership testing for GT , respectively. These results reveal that BW13-310 would be an interesting candidate in pairing-based cryptographic protocols.

A bilinear map whose domain and target sets are identical is called a self-bilinear map. Original self-bilinear maps are defined over cyclic groups. Since the map itself reveals information about the underlying cyclic group, the Decisional Diffie–Hellman Problem (DDH) and the computational Diffie–Hellman (CDH) problem may be solved easily in some specific groups. This brings a lot of limitations to constructing secure self-bilinear schemes. As a compromise, a self-bilinear map with auxiliary information was proposed in CRYPTO’2014. In this paper, we construct this weak variant of a self-bilinear map from generic sets and indistinguishable obfuscation. These sets should own several properties. A new notion, One Way Encoding System (OWES), is proposed to summarize these properties. The new Encoding Division Problem (EDP) is defined to complete the security proof. The OWES can be built by making use of one level of graded encoding systems (GES). To construct a concrete self-bilinear map scheme, Garg, Gentry, and Halvei(GGH13) GES is adopted in our work. Even though the security of GGH13 was recently broken by Hu et al., their algorithm does not threaten our applications. At the end of this paper, some further considerations for the EDP for concrete construction are given to improve the confidence that EDP is indeed hard.

Since supersingular elliptic curve isogenies are one of the several candidate sources of hardness for building post-quantum cryptographic primitives, the research of efficient signature schemes based on them is still a hot topic. In this paper, we present a many-time signature scheme based on the hash function from supersingular elliptic curve isogenies over the finite field Fp2 where p = 2521 - 1. Our signature scheme achieves smaller signature sizes relative to other post-quantum signature schemes based on supersingular elliptic curve isogenies, such as Galbraith's signature schemes (AsiaCrypt 2017) and Yoo's scheme (FC 2017). The structure of our scheme follows that of the hash-based signature scheme submitted to National Institute of Standards and Technology for post-quantum cryptography in 2018 with some modifications. To complete the construction, we firstly apply the method of Weil restriction to improve the efficiency of hash function from supersingular elliptic curve isogenies by approximately 30%, then propose a new Winternitz one-time signature scheme based on the hash function. Finally, we implement the signature scheme.

Pollard's rho method and its parallelized variant are at present known as the best generic algorithms for computing discrete logarithms. However, when we compute discrete logarithms in cyclic groups of large orders using Pollard's rho method, collision detection is always a high time and space consumer. In this paper, we present a new efficient collision detection algorithm for Pollard's rho method. The new algorithm is more efficient than the previous distinguished point method and can be easily adapted to other applications. However, the new algorithm does not work with the parallelized rho method, but it can be parallelized with Pollard's lambda method. Besides the theoretical analysis, we also compare the performances of the new algorithm with the distinguished point method in experiments with elliptic curve groups. The experiments show that the new algorithm can reduce the expected number of iterations before reaching a match from 1.309G to 1.295G under the same space requirements for the single rho method.