In this work, we make systematic optimizations of key encapsulation mechanisms based on Module Learning-with-Errors, covering algorithmic design, fundamental operation of the Number Theoretic Transform (NTT), approaches to expanding the encapsulated key size, and AVX2/ARM implementations. We observe that decryption can be simplified, leading to a both faster and less error-prone decryption process. Based on a systematic study of variants of NTT, we present a new variant named hybrid-NTT that combines the advantages of existing NTT methods, and derive its optimality in computational complexity. We analyze and compare the different approaches to expand the size of the key to be encapsulated and conclude with the most economic approach. Each above optimization technique is of independent value, and we apply all of them to KYBER and Aigis, resulting in new scheme variants named OSKR and OKAI, respectively. For all new schemes proposed in this work, we provide optimized AVX2 and ARM Cortex-M4 implementations and present the performance benchmarks. Our AVX2 implementation provides up to 19.7% and 26.4% speedups compared with KYBER and Aigis, respectively. Meanwhile, with our new parameter set and optimization techniques, we show up to a 17% improvement compared with KYBER on the ARM Cortex-M4 platform.

Order-preserving encryption (OPE) and order-revealing encryption (ORE) are among the core ingredients for encrypted databases (EDBs). In this work, we study the leakage of OPE and ORE and their forward security. We propose generic yet powerful file-injection attacks (FIAs) on OPE/ORE, aimed at the situations of possessing order by and range queries. Our FIAs only exploit the ideal leakage of OPE/ORE (in particular, no need of data denseness or frequency). We also improve their efficiency with the frequency statistics using a hierarchical idea such that the high-frequency values will be recovered more quickly. We conduct some experiments on real datasets to test the performance, and the results show that our FIAs can cause an extreme hazard on most of the existing OPEs and OREs with high efficiency and 100% recovery rate. We then formulate forward security of ORE, and propose a practical compilation framework for achieving forward secure ORE to resist the perniciousness of FIA. The compilation framework can transform most of the existing OPEs/OREs into forward secure OREs, with the goal of minimizing the extra burden incurred on computation and storage. We also present its security proof, and execute some experiments to analyze its performance. The proposed compilation is highly efficient and forward secure.

Bitcoin has gained its popularity for almost 10 years as a “secure and anonymous digital currency”. However, according to several recent researches, we know that it can only provide pseudonymity rather than real anonymity, and privacy has been one of the main concerns in the system similar to Bitcoin. Ring signature is a good method for those users who need better anonymity in cryptocurrency. It was first proposed by Rivest et al. based upon the discrete logarithm problem (DLP) assumption in 2006, which allows a user to sign a message anonymously on behalf of a group of users even without their coordination. The size of ring signature is one of the dominating parameters, and constant-size ring signature (where signature size is independent of the ring size) is much desirable. Otherwise, when the ring size is large, the resultant ring signature becomes unbearable for power limited devices or leads to heavy burden over the communication network. Though being extensively studied, currently there are only two approaches for constant-size ring signature. Achieving practical constant-size ring signature is a long-standing open problem since its introduction. In this work, we solve this open question. We present a new constant-size ring signature scheme based on bilinear pairing and accumulator, which is provably secure under the random oracle (RO) model. To the best of our knowledge, it stands for the most practical ring signature up to now.