Information Security and Cryptology

Table of Contents

1. Frontmatter

2. Signatures

   1. Frontmatter

   2. Concurrent Signatures from a Variety of Keys

      George Teşeleanu

      Abstract

      Concurrent signatures allow two entities to produce two ambiguous signatures that become binding once an extra piece of information (called the keystone) is released. Such a signature is developed by Chen et al., but it restricts signers to using the same public parameters. We describe and analyse a new concurrent signature that allows users to sign documents even if they use different underlying hard problems when generating their public parameters.

   3. A Generic Construction of Fuzzy Signature

      Jie Song, Yunhua Wen

      Abstract

      Fuzzy signature is a signature scheme in which the signing key is no longer uniformly generated nor precisely reproducible but a fuzzy string with enough entropy such as biometric information. In this paper, we give a variant definition of fuzzy signature and propose a generic construction of fuzzy signature which uses a fuzzy extractor and a signature scheme with simple key generation process as building blocks. Meanwhile, we give two instantiations of our generic construction. The first instantiation results in a fuzzy signature scheme which is secure under the computational Diffie-Hellman (CDH) assumption over bilinear groups in the standard model. The second instantiation results in a fuzzy signature that is secure in the random oracle model under the worst-case hardness of the \(\widetilde{O}(n^{1.5})\)-SIVP problem in general lattices. Moreover, compared with previous work, our fuzzy signatures have weaker requirements for the fuzzy signing key, which makes our fuzzy signatures more practical.

   4. Identity Based Linkable Ring Signature with Logarithmic Size

      Mohamed Nassurdine, Huang Zhang, Fangguo Zhang

      Abstract

      Anonymity is an inevitable and sensitive matter of concern, especially in the age where people are willing to use digital devices and Internet to deal with almost all things in their work and daily life. To support anonymity, modern cryptography is one of the most suitable choices in the algorithm level. Particularly, in the scenarios, such as e-voting, crypto-currency, and smart grid etc., a cryptographic primitive, called linkable ring signature, has shown its ability to handle anonymity problems. However, signature schemes will introduce additional costs to those e-commerce systems, so that they should be as efficient as possible. On the other side, a signature scheme that requires the public key infrastructure (PKI) brings much unnecessary inconvenience to its users, since typically, users of the aforementioned systems are not familiar with cryptographic skills and the system establishers are trusted by them in some sense. As a result, an identity-based (ID-based) signature scheme with small size fulfills the visible requirements of e-commerce systems. In this paper, we proposed an ID-based linkable ring signature scheme with logarithmic size from pairing and elliptic curve discrete logarithm problem (ECDLP), and gave all the security proofs in detail. Besides that, the scheme needs no trusted setup, except that the key generation center knows the secret key of each user and it is a property of ID-based cryptography in nature.

   5. Security Analysis of DGM and GM Group Signature Schemes Instantiated with XMSS-T

      Mahmoud Yehia, Riham AlTawy, T. Aaron Gulliver

      Abstract

      Group Merkle (GM) (PQCrypto 2018) and Dynamic Group Merkle (DGM) (ESORICS 2019) are recent proposals for post-quantum hash-based group signature schemes. They are designed as generic constructions that employ any stateful Merkle hash-based signature scheme. XMSS-T (PKC 2016, RFC8391) is the latest stateful Markle hash-based signature scheme where (almost) optimal parameters are provided. In this paper, we show that the setup phase of both GM and DGM does not enable drop-in instantiation by XMSS-T which limits both designs in employing earlier XMSS versions with sub-optimal parameters which negatively affects the performance of both schemes. Thus, we provide a tweak to the setup phase of GM and DGM to overcome this limitation and enable the adoption of XMSS-T. Moreover, we analyze the bit security of DGM when instantiated with XMSS-T and show that it is susceptible to multi-target attacks because of the parallel Signing Merkle Trees (SMT) approach. More precisely, when DGM is used to sign \(2^{64}\) messages, its bit security is 44 bits less than that of XMSS-T. Finally, we provide a DGM variant that mitigates multi-target attacks and show that it attains the same bit security as XMSS-T.

3. System Security

   1. Frontmatter

   2. UC-Secure Cryptographic Reverse Firewall–Guarding Corrupted Systems with the Minimum Trusted Module

      Geng Li, Jianwei Liu, Zongyang Zhang, Yanting Zhang

      Abstract

      Nowadays, mass-surveillance is becoming an increasingly severe threat to the public’s privacy. The PRISM and a series of other events showed that inner attacks such as subversion attacks may exist in the current network extensively. As an important strategy to defend users’ privacy against these attacks, cryptographic reverse firewall (CRF) is designed to be a middle-box, modifying all the messages coming in and out of a computer. However, the current formal definition of CRFs merely considers a single protocol session. If such a CRF applies to multiple entities, the security of every entity could not be deduced directly, which leads to an application limitation. In this work, we re-define the notion of CRF from a new perspective based on UC-emulation. Our new definition expresses all expected properties of a CRF in a more brief way, under the universal composition environment. We present a composition theorem which enables deploying one CRF for a local area of network rather than a single computer, and this can significantly reduce the number of CRFs used in practical applications.

      As another part of this work, under the new definition, we present the first deterministic CRF construction. Compared with existing CRFs, our construction only requires secure randomness in its initial phase rather than every protocol session, and such randomness can be acquired from a public resource. Noting that the probabilistic algorithms are the main targets of subversion attacks, our work makes it much easier to realize a trusted CRF, and thus, pushes CRFs from a concept to application with one more step.

   3. A Message Franking Channel

      Loïs Huguenin-Dumittan, Iraklis Leontiadis

      Abstract

      We pursue to formalize and instantiate a secure bidirectional channel with message franking properties. Under this model a sender may send an abusive message to the receiver and the latter wish to open it in a verifiable way to a third party. Potential malicious behavior of a sender requires message franking protocols resistant to sending messages that cannot be opened later by the receiver. An adversary impersonated by the receiver may also try to open messages that have not been sent by the sender. Wrapping a message franking protocol in a secure channel requires a more delicate treatment in order to avoid drops or replay of messages and out-of-order delivery. To the best of our knowledge we are the first to model the security of a message franking channel, which apart from integrity, confidentiality, resistance to drops, relays and out-of-order delivery is sender and receiver binding: a sender cannot send a message which cannot be opened in a verifiable way later by the receiver, and the receiver cannot claim a message that had not been truly sent by the receiver. Finally, we instantiate a bidirectional message franking channel from symmetric primitives and analyze its security.

   4. SparrowHawk: Memory Safety Flaw Detection via Data-Driven Source Code Annotation

      Yunlong Lyu, Wang Gao, Siqi Ma, Qibin Sun, Juanru Li

      Abstract

      Detecting code flaws in programs is a vital aspect of software maintenance and security. Classic code flaw detection techniques rely on program analysis to check whether the code logic violates certain pre-define rules. In many cases, however, program analysis falls short of understanding the semantics of a function (e.g., the functionality of an API), and thus is difficult to judge whether the function and its related behaviors would lead to a security bug. In response, we propose an automated data-driven annotation strategy to enhance the understanding of the semantics of functions during flaw detection. Our designed SparrowHawk source code analysis system utilizes a programming language aware text similarity comparison to efficiently annotate the attributes of functions. With the annotation results, SparrowHawk makes use of the Clang static analyzer to guide security analyses.

      To evaluate the performance of SparrowHawk, we tested SparrowHawk for memory corruption detection, which relies on the annotation of customized memory allocation/release functions. The experiment results show that by introducing function annotation to the original source code analysis, SparrowHawk achieves more effective and efficient flaw detection, and successfully discovers 51 new memory corruption vulnerabilities in popular open source projects such as FFmpeg and kernel of OpenHarmony IoT operating system.

4. Symmetric Cryptanalysis

   1. Frontmatter

   2. A New Approach for Finding Low-Weight Polynomial Multiples

      Laila El Aimani

      Abstract

      We consider the problem of finding low-weight multiples of polynomials over binary fields, which arises in stream cipher cryptanalysis or in finite field arithmetic. We first devise memory-efficient algorithms based on the recent advances in techniques for solving the knapsack problem. Then, we tune our algorithms using the celebrated Parallel Collision Search (PCS) method to decrease the time cost at the expense of a slight increase in space. Both our memory-efficient and time-memory trade-off algorithms improve substantially the state-of-the-art. The gain is for instance remarkable for large weights; a situation which occurs when the available keystream is small, e.g. the Bluetooth keystream.

   3. Differential-Linear Cryptanalysis of the Lightweight Crytographic Algorithm KNOT

      Shichang Wang, Shiqi Hou, Meicheng Liu, Dongdai Lin

      Abstract

      KNOT is one of the 32 candidates in the second round of NIST’s lightweight cryptography standardization process. The KNOT family consists of bit-slice lightweight Authenticated Encryption with Associated Data (AEAD) and hashing algorithms. In this paper, we evaluate the security for the initialization phase of two members of the KNOT-AEAD family by differential-linear cryptanalysis.

      More exactly, we analyze KNOT-AEAD(128,256,64) and KNOT-AEAD(128,384,192) which have 128-bit secret keys. As a result, for 15-round KNOT-AEAD(128,256,64), our attack takes \(2^{48.8}\) time complexity and \(2^{47.5}\) blocks to recover the full 128-bit key. To the best of our knowledge, this is the first full key-recovery attack on 15-round KNOT-AEAD(128,256,64), and it achieves three more rounds compared with the existing work. Regarding 17-round KNOT-AEAD(128,384,192), time complexity of \(2^{59.2}\) and data complexity of \(2^{58.2}\) are required to launch a key-recovery attack, which is five rounds better than the known result. We stress here that our attacks do not threaten the security of KNOT-AEAD.

   4. Revisit Two Memoryless State-Recovery Cryptanalysis Methods on A5/1

      Mingxing Wang, Yonglin Hao

      Abstract

      At ASIACRYPT 2019, Zhang proposes a near collision attack on A5/1. He claims that such an attack method can recover the 64-bit A5/1 state with a time complexity around \(2^{32}\) cipher ticks and requires negligible memory complexities. Soon after its proposal, Zhang’s near collision attack is severely challenged by Derbez et al. who claim that Zhang’s attack cannot have a time complexity lower than Golic’s memoryless guess-and-determine attack dating back to EUROCRYPT 1997. In this paper, we study both the guess-and-determine and the near collision attacks for recovering A5/1 states with negligible memory complexities. In order to make a fair comparison, we recover the state \(\boldsymbol{s}^0\) using both methods. We propose a new guessing technique that can construct linear equation filters in a more efficient manner. When evaluating time complexities, we take the filtering strength of the linear equation systems into account making the complexities more convincing. According to our detailed analysis, the new guess-and-determine attack can recover the state \(\boldsymbol{s}^0\) with a time complexity of \(2^{43.91}\) simple operations. The time complexity for the near collision attack is \(2^{50.57}\) simple operations.

   5. More Accurate Division Property Propagations Based on Optimized Implementations of Linear Layers

      Chunlei Hong, Shasha Zhang, Siwei Chen, Da Lin, Zejun Xiang

      Abstract

      As a generalized integral property, the division property can be used to search integral distinguishers of symmetric ciphers by taking the advantage of automatic tools, such as Mixed Integer Linear Programming (MILP) and Boolean Satisfiability Problem (SAT) solvers. In this case, the accuracy of corresponding models will influence the resulting distinguishers. In this paper, we present a new technique to characterize the division property propagation of linear layers. Firstly, we study the impact of a linear layer implementation on its division property propagations. We found that division trails derived from an optimized implementation of a linear layer can be more accurate than the \(\mathcal {S}\) method, and different implementations can eliminate some different invalid division trails. Thus, we can eliminate a large number of invalid division trails by combining different implementations. As an application of our technique, we have searched distinguishers for Midori64, Skinny64 and LED. As a result, we can obtain the same longest distinguishers as the \(\mathcal {ZR}\) method and the \(\mathcal {HW}\) method, which are the exact modeling of linear layers. Moreover, our method can be used with both MILP and SAT, while the \(\mathcal {HW}\) method can only work with SAT. In addition, the number of constraints with the \(\mathcal {HW}\) method increases quadratically, however it increases linearly with our method.

5. Asymmetric Cryptanalysis

   1. Frontmatter

   2. Security Analysis on an ElGamal-Like Multivariate Encryption Scheme Based on Isomorphism of Polynomials

      Yasuhiko Ikematsu, Shuhei Nakamura, Bagus Santoso, Takanori Yasuda

      Abstract

      Isomorphism of polynomials with two secrets (IP2S) problem was proposed by Patarin et al. at Eurocrypt 1996 and the problem is to find two secret linear maps filling in the gap between two polynomial maps over a finite field. At PQC 2020, Santoso proposed a problem originated from IP2S, which is called block isomorphism of polynomials with circulant matrices (BIPC) problem. The BIPC problem is obtained by linearizing IP2S and restricting secret linear maps to linear maps represented by circulant matrices. Using the commutativity of products of circulant matrices, Santoso also proposed an ElGamal-like encryption scheme based on the BIPC problem. In this paper, we give a new security analysis on the ElGamal-like encryption scheme. In particular, we introduce a new attack (called linear stack attack) which finds an equivalent key of the ElGamal-like encryption scheme by using the linearity of the BIPC problem. We see that the attack is a polynomial-time algorithm and can break some 128-bit proposed parameters of the ElGamal-like encryption scheme within 10 h on a standard PC.

   3. Attacking ECDSA Leaking Discrete Bits with a More Efficient Lattice

      Shuaigang Li, Shuqin Fan, Xianhui Lu

      Abstract

      A lattice attack on the Elliptic Curve Digital Signature Algorithm (ECDSA) implementation constructs a lattice related to the secret key by utilizing the information leaked and then recovers the secret key by finding a certain short lattice vector. When the information leaked is discrete bits, Fan et al. (CCS 2016) constructed an efficient lattice by translating the problem of recovering the secret key to the Extended Hidden Number Problem (EHNP). Following their works, we propose two new techniques to construct a more efficient lattice which has a lower dimension and a shorter target vector. Moreover, we further improve the success probability of the secret key recovery by adjusting the lattice. Therefore, it is much easier to recover the secret key. Specifically, injecting our techniques into the existing lattice attacks, we recover the secret key with fewer signatures or a higher success probability.

6. Cryptographic Protocols

   1. Frontmatter

   2. A Simple Post-Quantum Non-interactive Zero-Knowledge Proof from Garbled Circuits

      Hongrui Cui, Kaiyi Zhang

      Abstract

      We construct a simple public-coin zero-knowledge proof system solely based on symmetric primitives, from which we can apply the Fiat-Shamir heuristic to make it non-interactive. Our construction can be regarded as a simplified cut-and-choose-based malicious secure two-party computation for the zero-knowledge functionality. Our protocol is suitable for pedagogical purpose for its simplicity (code is only 728 lines).

   3. Improved Zero-Knowledge Argument of Encrypted Extended Permutation

      Yi Liu, Qi Wang, Siu-Ming Yiu

      Abstract

      Extended permutation (EP) is a generalized notion of the standard permutation. Unlike the one-to-one correspondence mapping of the standard permutation, EP allows to replicate or omit elements as many times as needed during the mapping. EP is useful in the area of secure multi-party computation (MPC), especially for the problem of private function evaluation (PFE). As a special class of MPC problems, PFE focuses on the scenario where a party holds a private circuit C while all other parties hold their private inputs \(x_1, \ldots , x_n\), respectively. The goal of PFE protocols is to securely compute the evaluation result \(C(x_1, \ldots , x_n)\), while any other information beyond \(C(x_1, \ldots , x_n)\) is hidden. EP here is introduced to describe the topological structure of the circuit C, and it is further used to support the evaluation of C privately.

      For an actively secure PFE protocol, it is crucial to guarantee that the private circuit provider cannot deviate from the protocol to learn more information. Hence, we need to ensure that the private circuit provider correctly performs an EP. This seeks the help of the so-called zero-knowledge argument of encrypted extended permutation protocol. In this paper, we provide an improvement of this protocol. Our new protocol can be instantiated to be non-interactive while the previous protocol should be interactive. Meanwhile, compared with the previous protocol, our protocol is significantly (e.g., more than \(3.4\times \)) faster, and the communication cost is only around \(24\%\) of that of the previous one.

7. Mathematical Foundations

   1. Frontmatter

   2. Isomorphism and Equivalence of Galois Nonlinear Feedback Shift Registers

      Wenhui Kong, Jianghua Zhong, Dongdai Lin

      Abstract

      Nonlinear feedback shift registers (NFSRs) have been used in many recent stream ciphers. They are generally classified as Fibonacci NFSRs and Galois NFSRs in terms of their implementation configurations. Two NFSRs are said to be isomorphic if their state diagrams are isomorphic, and two NFSRs are equivalent if their sets of output sequences are equal. Equivalent NFSRs must be isomorphic NFSRs, but not the vice versa. Previous work has been done on the isomorphism and equivalence of Fibonacci NFSRs. This paper continues this research for Galois NFSRs. It first gives some characterizations for several kinds of isomorphic Galois NFSRs, which improves and generalizes the previous corresponding results for Fibonacci NFSRs. It then presents some characterizations for two kinds of equivalent Galois NFSRs, helpful to the design of NFSR-based stream ciphers.

   3. Elliptic Curve and Integer Factorization

      Zhizhong Pan, Xiao Li

      Abstract

      Suppose that we want to factor an integer D where \(D=pq\), and p, q are two distinct odd primes. Assuming the parity conjecture and BSD conjecture hold, we reduce the problem of integer factorization to computing the generators of the Mordell-Weil group of \(E_{Dr}:y^{2}=x^{3}-Drx\), where r is a suitable integer with \((r,D)=1\). Then for the sake of deciding whether the point of \(E_{Dr}\) can factor D, it is shown that we need to compute the 2-Selmer group of \(E_{Dr}\). Finally, we give a method to compute the 2-Selmer group of \(E_{Dr}\) and conduct some experiments to illustrate our method.

   4. On the Linear Complexity of Feedforward Clock-Controlled Sequence

      Yangpan Zhang, Maozhi Xu

      Abstract

      As a research field of stream ciphers, the pursuit of a balance of security and practicality is the focus. The conditions for security usually have to satisfy at least high period and high linear complexity. Because the feedforward clock-controlled structure can provide quite a high period and utility, many sequence ciphers are constructed based on this structure. However, the past study of its linear complexity only works when the controlled sequence is an m-sequence. Using the theory of matrix over the ring and block matrix in this paper, we construct a more helpful method. It can estimate the lower bound of the linear complexity of the feedforward clock-controlled sequence. Even the controlled sequence has great linear complexity.

8. Symmetric Cryptography

   1. Frontmatter

   2. On Characterization of Transparency Order for (n, m)-functions

      Yu Zhou, Yongzhuang Wei, Hailong Zhang, Luyang Li, Enes Pasalic, Wenling Wu

      Abstract

      The transparency order (denoted by \(\mathcal {TO}\)) is a useful measure of the robustness of (n, m)-functions (cryptographic S-boxes as mappings from \(GF(2)^n\) to \(GF(2)^m\)) to multi-bits Differential Power Analysis (DPA). An improved version of transparency order (denoted by \(\mathcal {RTO}\)), based on the use of cross-correlation coefficients, was also introduced recently. For the first time, we resolve this open problem which (n, m)-functions reach the upper bound on \(\mathcal {TO}\) for odd n (m is a power of 2). We also investigate the tightness of upper and lower bounds related to \(\mathcal {RTO}\) and derive its relationship to main cryptographic characterizations of (n, m)-functions (such as nonlinearity, the sum-of-square indicator and algebraic immunity). Finally, concerning S-boxes of size \(4\times 4\), the distributions of \(\mathcal {RTO}\) for all 302 balanced S-boxes (up to affine equivalence) and 16 equivalence classes of optimal S-boxes are given.

   3. Binary Sequences Derived from Monomial Permutation Polynomials over GF(2)

      Qun-Xiong Zheng, Yupeng Jiang, Dongdai Lin, Wen-Feng Qi

      Abstract

      In this paper, we propose a class of binary sequences induced by monomial permutation polynomials over \(\mathrm {GF}(2^{p})\) and study the period property and the shift-equivalence of these binary sequences. In particularly, we give a necessary and sufficient condition for such a sequence to have maximal period. Moreover, we also give a necessary and sufficient condition for two such sequences to be shift equivalent.

   4. On the Provable Security Against Truncated Impossible Differential Cryptanalysis for AES in the Master-Key Setting

      Xueping Yan, Lin Tan, Hong Xu, Wenfeng Qi

      Abstract

      Impossible differential cryptanalysis is a powerful cryptanalysis technique of block ciphers. Length of impossible differentials is important for the security evaluation of a block cipher against impossible differential cryptanalysis. Many previous studies on finding impossible differentials of AES assumed that round keys are independent and uniformly random. There are few results on security evaluation of AES in the master-key setting. In ASIACRYPT 2020, Hu et al. redefined impossible differential with the key schedule considered, and showed that there exists no one-byte active input and one-byte active output impossible differential for 5-round AES-128 even considering the relations of 3-round keys. In this paper, we prove theoretically that even though the relations of all round keys are considered, there do not exist three kinds of truncated impossible differentials for 5-round AES: (1) the input truncated differences are nonzero only in any diagonal and the output truncated differences are nonzero only in any inverse diagonal; (2) the input truncated differences are nonzero only in any two diagonals and the output truncated differences are nonzero only in any inverse diagonal; (3) the input truncated differences are nonzero only in any diagonal and the output truncated differences are nonzero only in any two inverse diagonals. Furthermore, for any given truncated differentials of these three kinds, the lower bounds of the number of master keys such that the truncated differentials are possible for 5-round AES-128 are presented.

   5. Adaptive Side-Channel Analysis Model and Its Applications to White-Box Block Cipher Implementations

      Yufeng Tang, Zheng Gong, Tao Sun, Jinhai Chen, Fan Zhang

      Abstract

      White-box block cipher (WBC) aims at protecting the secret key of a block cipher even if an adversary has full control over the implementations. At CHES 2016, Bos et al. proved that WBC are also threatened by side-channel analysis (SCA), e.g., differential fault analysis (DFA) and differential computation analysis (DCA). Therefore, advanced countermeasures have been proposed by Lee et al. for resisting DFA and DCA, such as table redundancy and improved masking methods, respectively. In this paper, we introduce a new adaptive side-channel analysis model which assumes that an adversary adaptively collects the intermediate values of a specific function and can mount the DFA/DCA attack with chosen inputs. In the adaptive SCA model, both theoretical analysis and experimental results show that Lee et al.’s proposed methods are vulnerable to DFA and DCA attacks. Moreover, a negative proposition is also demonstrated on the corresponding high-order countermeasures under our new model.

9. Public Key Cryptography

   1. Frontmatter

   2. Fully Secure Lattice-Based ABE from Noisy Linear Functional Encryption

      Geng Wang, Ming Wan, Zhen Liu, Dawu Gu

      Abstract

      Constructing lattice-based fully secure attribute-based encryption (ABE) has always been a challenging task. Although there are many selective secure ABE schemes from the hardness of learning with errors (LWE) problem, it is hard to extend them to fully security, since the dual system technique in pairing-based cryptography cannot be applied to lattice-based constructions.

      In this paper, we take a different approach: constructing fully secure ABE from another primitive called noisy linear functional encryption (NLinFE) which can be constructed from LWE problem. We give a fully secure ciphertext-policy ABE scheme for CNF formulae which security relies on the security of NLinFE and hardness of LWE. Since current constructions for NLinFE only satisfy bounded collusion security, our resulting scheme is also bounded collusion only, but it can be easily extended into unbounded security if unbounded NLinFE can be shown to exist. Also, since existing NLinFE schemes are inefficient, we give a new construction for NLinFE with better efficiency, hence our ABE construction is more efficient than other existing bounded collusion ABE/FE schemes.

   3. Revocable Identity-Based Encryption with Server-Aided Ciphertext Evolution from Lattices

      Yanhua Zhang, Ximeng Liu, Yupu Hu, Huiwen Jia

      Abstract

      Revocable identity-based encryption (RIBE) with server-aided ciphertext evolution (RIBE-CE), recently proposed by Sun et al. at TCS 2020, offers significant advantages over previous identity (or key) revocation mechanisms when considering the scenario of a secure data sharing in the cloud setting. In this new system model, the user (i.e., a recipient) can utilize the current short-term decryption key to decrypt all ciphertexts sent to him, meanwhile, the ciphertexts in the cloud evolve to new ones with the aided of the cloud server and the old ones are completely deleted, and thus, the revoked users cannot access to both the previously and subsequently shared data.

      In this paper, inspired by Sun et al.’s work, we propose the first lattice-based RIBE-CE. Our scheme is more efficient and secure than the existing constructions of lattice-based RIBE. Simultaneously, the private key generator (PKG) maintains a binary tree (BT) to handle key revocation only with a logarithmic complexity workload in time key update, not growing linearly in the numbers of system users N, which serves as one solution to the challenge proposed by Sun et al. and based on the hardness of the learning with errors (LWE) problem, we prove that our first scheme is selectively secure in the standard model. Subsequently, based on the main techniques for lattice basis delegation with hierarchical IBE (HIBE), we construct our second lattice-based RIBE-CE scheme with decryption key exposure resistance (DKER), a default security requirement for RIBE, which has not been considered by Sun et al.

   4. Homomorphic Modular Reduction and Improved Bootstrapping for BGV Scheme

      Ruiqi Li, Chunfu Jia

      Abstract

      Bootstrapping is a crucial subroutine of fully homomorphic encryption (FHE), where a homomorphic encryption scheme evaluates its own decryption circuits. Homomorphic modular reduction is a crucial part of bootstrapping a BGV ciphertext.

      In this paper, we investigate the homomorphic modular reduction technique. We propose a new homomorphic modular reduction algorithm based on the idea of “blind rotation”. This new homomorphic modular reduction procedure requires no basic homomorphic operations, hence it has lower noise accumulation and more suitable for implementing. Furthermore, we also resort to the blind rotation to construct a new bootstrapping procedure for the BGV scheme. We analyze the noise performance and the computational complexity of our scheme. The results illustrate that our new bootstrapping scheme achieves low noise accumulation so that the lattice approximation factor for the underlying worst-case lattice assumption is smaller than that of Chen and Zhang’s work. Meanwhile, the complexity of our bootstrapping scheme is comparable with their scheme.

10. Real World Cryptography

    1. Frontmatter

    2. Privacy Preserving OpenPGP Public Key Distribution with Spamming Resistance

       Wenyuan Li, Wei Wang, Jingqiang Lin, Qiongxiao Wang, Wenjie Wang

       Abstract

       OpenPGP public key distribution via Synchronizing KeyServers (SKS) is facing the challenges of user privacy leakage caused by keyword search behaviors and service unavailability of OpenPGP software caused by OpenPGP certificate spamming attack (CVE-2019-13050). Most existing solutions to the problem dispense with the necessary features and functions of SKS or Web of Trust (WoT) for attack mitigation. In this paper, we put forward a solution which is privacy-preserving and spamming-resistant, while maintaining the functionalities of SKS and WoT. Considering the characteristics of our scenario, we protect user privacy by introducing a third-party server, and propose a specific third party-based private set intersection protocol to improve usability of OpenPGP software. Our protocol helps users filter out the required key data by intersection computation between unbalanced sets of keywords. We also propose an enhanced scheme for multi-key query and further privacy protection. We evaluate the usability and privacy of our schemes. Experimental results show that our scheme can largely reduce unnecessary data download with appropriate filter parameters. The proposed solution relies on the security of Elliptic Curve Diffie–Hellman, HMAC-based Key Derivation Function, Bloom filter and symmetric cryptographic encryption to defend against semi-honest adversaries.

    3. Collaborative Verifiable Delay Functions

       Liam Medley, Elizabeth A. Quaglia

       Abstract

       We propose and define a new primitive, collaborative verifiable delay functions (coVDFs), an extension to VDFs allowing multiple parties to jointly compute a publicly verifiable delay, whilst encapsulating a personal input from each party. These personal inputs can contain information such as a hash of a bid in an auction, or some public identifier of the solving party. We highlight the differences between the single-party and the multi-party settings, and discuss some applications facilitated by the additional properties offered by coVDFs.

       We formalise this new primitive, as well as the relevant security properties, and we introduce the notions of robustness and traceability, which mitigate adversarial behaviour arising from the introduction of multiple parties. We propose two candidate constructions: the first is an extension of Wesolowski’s VDF construction from EUROCRYPT 2019, relying on repeated squaring in a finite abelian group. We prove that this extension satisfies the traceability property, however it is not robust. Our second construction is based on the hashgraph protocol proposed by Baird in 2016, and involves each of the n parties repeatedly implementing a gossip protocol to one another and computing a hash each time they do. The construction results in every party producing a copy of the same graph, and is robust, meaning it runs correctly, in the presence of up to n/3 malicious parties.

    4. SMCOS: Fast and Parallel Modular Multiplication on ARM NEON Architecture for ECC

       Wenjie Wang, Wei Wang, Jingqiang Lin, Yu Fu, Lingjia Meng, Qiongxiao Wang

       Abstract

       Elliptic Curve Cryptography (ECC) is considered a more effective public-key cryptographic algorithm in some scenarios, because it uses shorter key sizes while providing a considerable level of security. Modular multiplication constitutes the “arithmetic foundation” of modern public-key cryptography such as ECC. In this paper, we propose the Cascade Operand Scanning for Specific Modulus (SMCOS) vectorization method to speed up the prime field multiplication of ECC on Single Instruction Multiple Data (SIMD) architecture. Two key features of our design sharply reduce the number of instructions. 1) SMCOS uses operands based on non-redundant representation to perform a “trimmed” Cascade Operand Scanning (COS) multiplication, which minimizes the cost of multiplication and other instructions. 2) One round of fast vector reduction is designed to replace the conventional Montgomery reduction, which consumes less instructions for reducing intermediate results of multiplication. Further more, we offer a general method for pipelining vector instructions on ARM NEON platforms. By this means, the prime field multiplication of ECC using the SMCOS method reaches an ever-fastest execution speed on 32-bit ARM NEON platforms. Detailed benchmark results show that the proposed SMCOS method performs modular multiplication of NIST P192, Secp256k1, and Numsp256d1 within only 205, 310 and 306 clock cycles respectively, which are roughly 32% faster than the Multiplicand Reduction method, and about 47% faster than the Coarsely Integrated Cascade Operand Scanning method.

11. Correction to: Differential-Linear Cryptanalysis of the Lightweight Cryptographic Algorithm KNOT

    Shichang Wang, Shiqi Hou, Meicheng Liu, Dongdai Lin

12. Backmatter