In this paper, we first present a theoretical analysis model on the Proof-of-Work (PoW) for cryptocurrency blockchain. Based on this analysis, we present a new type of PoW, which relies on the hardness of solving a set of random quadratic equations over the finite field GF(2). We will present the advantages of such a PoW, in particular, in terms of its impact on decentralization and the incentives involved, and therefore demonstrate that this is a new good alternative as a new type for PoW in blockchain applications.

In this paper, we introduce a new provably secure ephemeral-only RLWE+Rounding-based key exchange protocol and a proper approach to more accurately estimate the security level of the RLWE problem with only one sample. Since our scheme is an ephemeral-only key exchange, it generates only one RLWE sample from protocol execution. We carefully analyze how to estimate the practical security of the RLWE problem with only one sample, which we call the ONE-sample RLWE problem. Our approach is different from existing approaches that are based on estimation with multiple RLWE samples. Though our analysis is based on some recently developed techniques in Darmstadt, our type of practical security estimate was never done before and it produces security estimates substantial different from the estimates before based on multiple RLWE samples. We show that the new design improves the security and reduce the communication cost of the protocol simultaneously by using one RLWE+Rounding sample technique. We also present two parameter choices ensuring 2^{−60} key exchange failure probability which cover security of AES-128/192/256 with concrete security analysis and implementation. We believe that our construction is secure, simple, efficient and elegant with wide application prospects.

Short integer solution (SIS) and learning with errors (LWE) are two hard lattice problems. These two problems are believed having huge potential in application of cryptography. In 2012, Ding et al. [5] introduced the first provably secure key exchange based on LWE problem. On the other hand, we believe that it is very difficult to do key exchange on SIS problem only. In 2014, Wang et al. [6] did an attempt, but it was not successful. Mao et al. [7] broke the protocol by an attack based on CBi-SIS problem in 2016. However, their attack is not efficient. In this paper, we present a extremely straightforward and simple attack to Wang’s key exchange and then we will construct a key exchange based on SIS and LWE problems.

In CT-RSA 2019, Bauer et al. have analyzed the case when the public key is reused for the NewHope key encapsulation mechanism (KEM), a second-round candidate in the NIST Post-quantum Standard process. They proposed an elegant method to recover coefficients ranging from −6 to 4 in the secret key. We repeat their experiments but there are two fundamental problems. First, even for coefficients in [−6, 4] we cannot recover at least 262 of them in each secret key with 1024 coefficients. Second, for the coefficient outside [−6, 4], they suggested an exhaustive search. But for each secret key on average there are 10 coefficients that need to be exhaustively searched, and each of them has 6 possibilities. This makes Bauer et al.’s method highly inefficient. We propose an improved method, which with 99.22% probability recovers all the coefficients ranging from −6 to 4 in the secret key. Then, inspired by Ding et al.’s key mismatch attack, we propose an efficient strategy which with a probability of 96.88% succeeds in recovering all the coefficients in the secret key. Experiments show that our proposed method is very efficient, which completes the attack in about 137.56 ms using the NewHope parameters.

Oblivious transfer is one of the main pillars of modern cryptography and plays a major role as a building block for other more complex cryptographic primitives. In this work, we present an efficient and versatile framework for oblivious transfer (OT) using one-round key-exchange (ORKE), a special class of key exchange (KE) where only one message is sent from each party to the other. Our contributions can be summarized as follows: - We analyze carefully ORKE schemes and introduce new security definitions. Namely, we introduce a new class of ORKE schemes, called Alice-Bob one-round key-exchange (A-B ORKE), and the definitions of message and key indistinguishability. - We show that OT can be obtained from A-B ORKE schemes fulfilling message and key indistinguishability. We accomplish this by designing a new efficient, versatile and universally composable framework for OT in the Random Oracle Model (ROM). The efficiency of the framework presented depends almost exclusively on the efficiency of the A-B ORKE scheme used since all other operations are linear in the security parameter. Universally composable OT schemes in the ROM based on new hardness assumptions can be obtained from instantiating our framework. Examples are presented using the classical Diffie-Hellman KE, RLWE-based KE and Supersingular Isogeny Diffie-Hellman KE.