Skip to main content
main-content

Über dieses Buch

This book constitutes the post-conference proceedings of the 15th International Conference on Information Security and Cryptology, Inscrypt 2019, held in Nanjing, China, in December 2019.

The 23 full papers presented together with 8 short papers and 2 invited papers were carefully reviewed and selected from 94 submissions. The papers cover topics in the fields of post-quantum cryptology; AI security; systems security; side channel attacks; identity-based cryptography; signatures; cryptanalysis; authentication; and mathematical foundations.

Inhaltsverzeichnis

Frontmatter

Invited Paper

Frontmatter

Revocable and Linkable Ring Signature

In this paper, we construct a revocable and linkable ring signature (RLRS) scheme, which enables a revocation authority to revoke the anonymity of the real signer in linkable ring signature scheme under any circumstances. In other words, the revocability of RLRS is mandatory. The proposed RLRS scheme inherits the desired properties of group signature (anonymity revocation) and linkable ring signature (spontaneous group formation and linkability). In addition, we proved the security of our scheme in the random oracle model. We also provided a revocable ring confidential transaction protocol based on our RLRS scheme, which embedded the revocability in ring confidential transaction protocol.

Xinyu Zhang, Joseph K. Liu, Ron Steinfeld, Veronika Kuchta, Jiangshan Yu

Post-Quantum Cryptography

Frontmatter

Efficient Password-Authenticated Key Exchange from RLWE Based on Asymmetric Key Consensus

A password-authenticated key exchange (PAKE) protocol allows two entities sharing a password to perform mutual authentication and establish a session key. Benefiting from the use of a low-entropy human-memorable password, PAKE avoids the use of PKI in the authentication process, making it more flexible and cheaper. However, with the development of quantum computing, protocols based on classical assumptions will no longer be secure, so designing a PAKE protocol capable of resisting quantum attacks has become an important research direction. In this work, we propose an efficient PAKE protocol using a new error reconciliation mechanism based on the ring learning with errors (RLWE) problem, which is considered to resist quantum attacks. Our protocol is proven security under the Bellare-Pointcheval-Rogaway (BPR) model. The protocol is implemented using the C language, which is highly portable, and is also optimized utilizing the Advanced Vector Extensions 2 (AVX2) instruction set. Compared with the C implementation of Ding’s protocol, our reference C implementation is more than 12x faster, and the efficiency is doubled after AVX2 optimization. Moreover, by choosing the appropriate parameters, the security strength of our scheme is improved and the message size is reduced.

Yingshan Yang, Xiaozhuo Gu, Bin Wang, Taizhong Xu

A Lattice-Based Certificateless Public Key Encryption with Equality Test in Standard Model

Certificateless public key encryption ($$\mathsf {CL}\hbox {-}\mathsf {PKE}$$) solves the problems of establishing public-key infrastructure for traditional public key encryption and resolving key escrow for identity-based encryption. Equality test is an extremely useful property that enables the ability of checking whether two ciphertexts encrypting the same message. Qu et al. (Information Science 2019) introduced the notion of certificateless public key encryption with equality test ($$\mathsf {CL}\hbox {-}\mathsf {PKEET}$$), together with four types of adversaries, that solves certificate manangement and key escrow problems of public key encryption with equality test ($$\mathsf {PKEET}$$) and identity-based encryption with equality test ($$\mathsf {IBEET}$$), and proposed a first $$\mathsf {CL}\hbox {-}\mathsf {PKEET}$$ scheme based on Bilinear Diffie-Hellman assumption in random oracle model. In this paper, we propose the first lattice-based $$\mathsf {CL}\hbox {-}\mathsf {PKEET}$$ in standard model whose security is reduced to the hardness of the learning with errors problem. In particular, we prove that our schemes are secure against two types of selective-identity adversaries introduced by Qu et al.

Dung Hoang Duong, Willy Susilo, Minh Kim Bui, Thanh Xuan Khuc

Attribute-Based Keyword Search from Lattices

Attribute-based keyword search (ABKS) is a special case of public key encryption with keyword search (PEKS) which allows fine-grained control of the search ability and can be further categorized into key-policy ABKS (KP-ABKS) and ciphertext-policy ABKS (CP-ABKS). In a KP-ABKS (resp., CP-ABKS) scheme, a trapdoor that is associated with an access policy f (resp., an attributes string $$\mathbf {x}$$) can only be used to search over ciphertexts that is associated with an attributes string $$\mathbf {x}$$ (resp., an access policy f) if $$f(\mathbf {x})=0$$. As ABKS is very useful in the era of big data, many researchers have been devoted to design ABKS schemes with different features, but almost all the known schemes are based on the traditional number-theoretical assumptions such as Factoring or Discrete Logarithm, and thus are insecure against quantum adversaries.In this paper, we propose a lattice-based KP-ABKS scheme supporting circuit policy of any predetermined polynomial depth. Our scheme is provably secure against chosen keyword attacks and keyword guessing attacks under the DLWE and ISIS assumptions in the random oracle model. By using a universal circuit, our scheme can also be converted into a CP-ABKS scheme.

Jie Li, Mimi Ma, Jiang Zhang, Shuqin Fan, Shuaigang Li

Group Key Exchange from CSIDH and Its Application to Trusted Setup in Supersingular Isogeny Cryptosystems

In this paper, we propose a multi-party (group) key exchange protocol based on CSIDH (Commutative Supersingular Isogeny Diffie–Hellman), which is a post-quantum Diffie-Hellman type key exchange protocol from a commutative group action. The proposed group key exchange protocol called G-CSIDH uses the same size prime modulus p as that in CSIDH for the same security level, and the security of G-CSIDH is reduced to the security of CSIDH.In addition, we propose the trusted protocol of generating public parameters of supersingular isogeny cryptosystems by using the proposed G-CSIDH. Trust in the setup based on G-CSIDH is reduced to the security of G-CSIDH, and then that of CSIDH. The trusted protocol can be applied to any supersingular isogeny cryptosystem, which uses a supersingular elliptic curve as a public parameter.

Tomoki Moriya, Katsuyuki Takashima, Tsuyoshi Takagi

AI Security

Frontmatter

RoLMA: A Practical Adversarial Attack Against Deep Learning-Based LPR Systems

With the advances of deep learning, license plate recognition (LPR) based on deep learning has been widely used in public transport such as electronic toll collection, car parking management and law enforcement. Deep neural networks are proverbially vulnerable to crafted adversarial examples, which has been proved in many applications like object recognition, malware detection, etc. However, it is more challenging to launch a practical adversarial attack against LPR systems as any covering or scrawling to license plate is prohibited by law. On the other hand, the created perturbations are susceptible to the surrounding environment including illumination conditions, shooting distances and angles of LPR systems. To this end, we propose the first practical adversarial attack, named as RoLMA, against deep learning-based LPR systems. We adopt illumination technologies to create a number of light spots as noises on the license plate, and design targeted and non-targeted strategies to find out the optimal adversarial example against HyperLPR, a state-of-the-art LPR system. We physicalize these perturbations on a real license plate by virtue of generated adversarial examples. Extensive experiments demonstrate that RoLMA can effectively deceive HyperLPR with an 89.15% success rate in targeted attacks and 97.3% in non-targeted attacks. Moreover, our experiments also prove its high practicality with a 91.43% success rate towards physical license plates, and imperceptibility with around 93.56% of investigated participants being able to correctly recognize license plates.

Mingming Zha, Guozhu Meng, Chaoyang Lin, Zhe Zhou, Kai Chen

A SeqGAN-Based Method for Mimicking Attack

Distributed denial of service (DDoS) attacks continue to be an ever-increasing threat in cyberspace. Nowadays, attackers tend to launch advanced DDoS attacks with botnets to bypass the detection system. In this paper, we present a method for launching an advanced application-layer DDoS which masquerades as a flash crowd (FC). The attack strategy falls in two aspects: (1) extracting legitimate users’ behaviors; (2) instructing bots to behave as legitimate users. To achieve this, we propose a multi-step algorithm to extract user browsing behaviors and establish a Sequence Generative Adversarial Nets (SeqGAN) model to generate mimicking behaviors of bots. In addition, we experimentally study the effectiveness of this mimicking attack. The study shows that the mimicking attack can fool a detection system that is based on machine learning algorithms. The experimental results also demonstrate that the mimicking attack is indistinguishable from FC in term of statistics.

Weiqing Huang, Xiao Peng, Zhixin Shi

Suzzer: A Vulnerability-Guided Fuzzer Based on Deep Learning

Fuzzing is a simple and effective way to find software bugs. Most state-of-the-art fuzzers focus on improving code coverage to enhance the possibility of causing crashes. However, a software program oftentimes has only a fairly small portion that contains vulnerabilities, leading coverage-based fuzzers to work poorly most of the time. To address this challenge, we propose Suzzer, a vulnerability-guided fuzzer, to concentrate on testing code blocks that are more likely to contain bugs. Suzzer has a light-weight static analyzer to extract ACFG vector from target programs. In order to determine which code blocks are more vulnerable, Suzzer is equipped with prediction models which get the prior probability of each ACFG vector. The prediction models will guide Suzzer to generate test inputs with higher vulnerability scores, thus improving the efficiency of finding bugs. We evaluate Suzzer using two different datasets: artificial LAVA-M dataset and a set of real-world programs. The results demonstrate that in the best case of short-term fuzzing, Suzzer saved 64.5% of the time consumed to discover vulnerabilities compared to VUzzer.

Yuyue Zhao, Yangyang Li, Tengfei Yang, Haiyong Xie

Systems Security

Frontmatter

Symmetric Frame Cracking: A Powerful Dynamic Textual CAPTCHAs Cracking Policy

In this work, we analyze the vulnerability of the dynamic textual CAPTCHA ( http://fexteam.gz01.bdysite.com/blog/2014/07/captcha-gif/ .) and propose a new method to automatically identify the CAPTCHA, which is based on Basic Vector Space Search Engine (BVSSE) and Convolutional Neural Network (CNN). Specifically, by exploiting the specific “Symmetric Frame Vulnerability”, we can remove most of the noise, therefore greatly reducing the difficulty of cracking. In the process of cracking, we first use the BVSSE to identify the CAPTCHA . The method is simple and fast, but there are problems such as a low recognition rate. Then we choose the CNN to identify the CAPTCHA, and finally get a recognition rate of 99.98% with the average speed of 0.092 s/gif. To have a deeper understanding of the internal recognition process, we visualize the intermediate output of the CNN model. In general, by comparing the two identification methods and visualizing the model, the entire recognition process becomes easier to understand. Based on the above experimental results and analyses, we finally summarize a new and general CAPTCHA attack method and discuss the security of the dynamic textual CAPTCHA .

Yueyao Chen, Qianjun Liu, Tianyu Du, Yuan Chen, Shouling Ji

Invisible Poisoning: Highly Stealthy Targeted Poisoning Attack

Deep learning is widely applied to various areas for its great performance. However, it is vulnerable to adversarial attacks and poisoning attacks, which arouses a lot of concerns. A number of attack methods and defense strategies have been proposed, most of which focus on adversarial attacks that happen in the testing process. Poisoning attacks, using poisoned-training data to attack deep learning models, are more difficult to defend since the models heavily depend on the training data and strategies to guarantee their performances. Generally, poisoning attacks are conducted by leveraging benign examples with poisoned labels or poison-training examples with benign labels. Both cases are easy to detect. In this paper, we propose a novel poisoning attack named Invisible Poisoning Attack (IPA). In IPA, we use highly stealthy poison-training examples with benign labels, perceptually similar to their benign counterparts, to train the deep learning model. During the testing process, the poisoned model will handle the benign examples correctly, while output erroneous results when fed by the target benign examples (poisoning-trigger examples). We adopt the Non-dominated Sorting Genetic Algorithm (NSGA-II) as the optimizer for evolving the highly stealthy poison-training examples. The generated approximate optimal examples are promised to be both invisible and effective in attacking the target model. We verify the effectiveness of IPA against face recognition systems on different face datasets, including attack ability, stealthiness, and transferability performance.

Jinyin Chen, Haibin Zheng, Mengmeng Su, Tianyu Du, Changting Lin, Shouling Ji

Privacy-Preserving and yet Robust Collaborative Filtering Recommender as a Service

In this paper, we provide a general system structure for latent factor based collaborative filtering recommenders by formulating them into model training and prediction computing stages. Aiming at pragmatic solutions, we first show how to construct privacy-preserving and yet robust model training stage based on existing solutions. Then, we propose two cryptographic protocols to realize a privacy-preserving prediction computing stage, depending on whether or not an extra proxy is involved.

Qiang Tang

CAVAEva: An Engineering Platform for Evaluating Commercial Anti-malware Applications on Smartphones

The pervasiveness of mobile devices, such as Android and iOS smartphones, and the type of data available and stored on these devices make them an attractive target for cyber-attackers. For example, mobile malware authors seek to compromise devices to collect sensitive information and data from the smartphones. To mitigate such a threat, a number of online scanning platforms exist to evaluate existing anti-malware applications. However, existing platforms have a number of limitations, such as configuration inflexibility. Also, in practice, the code protection and different structures complicate efforts to effectively evaluate different commercial anti-malware software in a configurable and unified platform. Hence in this work, we design CAVAEva, an engineering platform for commercial anti-malware application evaluation, in which users/researchers have the capability to configure the platform based on their needs and requirements. In particular, we show how to design such a platform and introduce its performance. Specifically, we present a comparative summary of seven commercial anti-malware software, and collect the feedback from a user study. Experimental results demonstrate the potential utility of our platform in evaluating commercial anti-malware software in a real-world smartphone deployment.

Hao Jiang, Weizhi Meng, Chunhua Su, Kim-Kwang Raymond Choo

SymSem: Symbolic Execution with Time Stamps for Deobfuscation

Code virtualization technique obfuscates programs by transforming original code to self-defined bytecode in a different instruction architecture. It is widely used in obfuscating malware for its ability to render normal analysis ineffective. Using symbolic execution to assist in deobfuscating such programs turned to be a trend in recent research. However, we found many challenges that may lead to semantic confusion in previous symbolic execution technique, and proposed a novel symbolic execution technique enhanced by time stamps to tackle these issues. For evaluation, we implemented it as a prototype of SymSem and deobfuscated programs protected by popular virtual machines. The results indicate that our method is able to accurately recover the semantics of obfuscated function trace.

Huayi Li, Yuanyuan Zhan, Wang Jianqiang, Dawu Gu

Elaphurus: Ensemble Defense Against Fraudulent Certificates in TLS

Recent security incidents indicate that certificate authorities (CAs) might be compromised to sign certificates with fraudulent information. The fraudulent certificates are exploited to launch successful TLS man-in-the-middle (MitM) attacks, even when TLS clients strictly verify the server certificates. Various security-enhanced certificate verification schemes have been proposed to defend against fraudulent certificates, such as Pinning, CAge, CT, DANE, and DoubleCheck. However, none of the above schemes perfectly solves the problem, which hinders them from being widely deployed. This paper analyzes these schemes in terms of security, usability and performance. Based on the analysis, we propose Elaphurus, an integrated security-enhanced certificate verification scheme on the TLS client side. Elaphurus is designed on top of Pinning, while integrating other schemes to eliminate their disadvantages and improving the overall security and usability. We implement the prototype system with OpenSSL. Experimental results show that it introduces a reasonable overhead, while effectively enhancing the security of certificate verification.

Bingyu Li, Wei Wang, Lingjia Meng, Jingqiang Lin, Xuezhong Liu, Congli Wang

Improving Division Property Based Cube Attacks by Removing Invalid Monomials

Division property based cube attack was proposed by Todo et al. at CRYPTO 2017, which can exploit larger cube indices than traditional cube attacks. At CRYPTO 2018, Wang et al. introduced degree evaluation and flag technique to reduce the complexity of recovering the superpoly. Although division property based cube attacks that introducing these methods are powerful to analyze many stream ciphers, how to further reduce the complexity of determining possible monomials of the superpoly is still a problem. In this paper, we introduce some techniques to speedup the recovery of the superpoly. 1. When evaluating all possible monomials, we provide the filter technique to reduce the complexity of evaluating monomials by division trails. Non-cube public variables involved in superpoly also can be obtained by the filter technique. While evaluating monomials, the effect of non-cube public variables on all monomials can be considered directly. 2. In order to remove most invalid monomials, we modify the parameters of flag technique in the initialization phase. Most invalid division trails can be identified and fewer remaining monomials need to be determined by constructing a linear system. To verify our scheme, we apply the method to the initialization of the Grain128a. In the recovery of the superpoly of 106-round Grain128a, the number of possible monomials needs to be determined is reduced to $$5.56\%$$ of Wang et al.’s superpoly evaluations. The complexity of analysing 184-round Grain128a is smaller than $$57\%$$ of the current best complexity. In the recovery attack of 185 or higher rounds Grain128a, cube indices set that includes all non-constant public variables can be achieved according to the results of the filter technique.

Senshan Pan, Zhuhua Li, Liangmin Wang

PPIDS: A Pyramid-Like Printer Intrusion Detection System Based on ATT&CK Framework

Nowadays, network printers have become one of the essential devices for daily work, and are getting more and more attention from attackers. Traditional intrusion detection system may not apply quite well to network printers since it can’t detect growing multi-step complex attacks for network printers. To detect and prevent such attacks, we design a network printer attackers’ behavioral model and knowledge base named TTPE based on ATT&CK framework. Then we propose an attack detection system named PPIDS which is based on TTPE to detect and analyze network attacks against network printers. For experiments, we capture 38 network traffic packets from 4 typical scenarios. In our experiments, PPIDS achieves false-positive rate of 0%, false-negative rate of 14.29%. Experiment result shows that our method performs superior to traditional intrusion detection systems on identifying complex network attacks against network printers.

Houhua He, Lei Yu, Weixia Cai, Xiaoyu Wang, Xiaorui Gong, Haoyu Wang, Chen Liu

A Privacy Enhancing Scheme for Mobile Devices Based Secure Multi-party Computation System

Mobile devices, such as smart phones, have recently become the typical computing platforms for many users. Consequently, in practice more and more multi-party computation systems are deployed on users’ mobile devices, resulting in various applications such as mobile outsourcing computing and mobile cooperative computing. However, as the mobile platforms may have inherent flaws, the connection of mobile devices and multi-party computation systems usually arouse new security risks. We point out that an application in one party’s mobile device can be a powerful privileged attacker to the multi-party computation system. Previous studies have mainly focused on avoiding the privacy leaks of one or several malicious parties or eavesdroppers on the Internet. This paper presents a privacy enhancing scheme for a kind of secure multi-party computation systems. The scheme can resist the privileged attackers from the party’s mobile device. Our scheme transforms the original computation process and puts the critical calculation process into trusted execution environment. We provide three components to build a privacy-enhanced multi-party computation system with our scheme. Our scheme is implemented to an actual secure multi-party computation system to demonstrate its validity and acceptable performance overhead.

Xueyi Yang, Na Lv, Tianyu Chen, Cunqing Ma, Limin Liu

Consolidating Hash Power in Blockchain Shards with a Forest

Sharding has been a highly expected solution for the blockchain scalability problem. But with computation power of honest miners (or stakes in PoS based systems) distributed in shards, it becomes easier for attackers to attack a single shard. In this research, we propose a new consensus algorithm, Greedy Observed Largest Forest (GOLF), aiming to consolidate distributed hash power in all shards to make attacking a single shard as hard as attacking the entire system.

Jun Zhao, Jiangshan Yu, Joseph K. Liu

Side Channel Attacks

Frontmatter

Evaluating the Cache Side Channel Attacks Against ECDSA

Various attacks are proposed against different ECDSA implementations: the key-related data are acquired through cache side channels, and then processed to recover the private key. For each cache side channel attack, the requirements of the data qualified for sequent processing vary greatly, and the success probability of private key recovery relies on both the acquired data and the parameters of data processing. So it is difficult to tell, for a certain ECDSA implementation, (a) how many signatures does a cache side channel attack need to recover the private key? or which attack performs the best? and (b) what kind of threat level exists due to potential side channel attacks, if the ECDSA implementation runs for a number of signatures on an unprotected system with cache side channels? Currently, there is no quantitative metric to fairly answer the questions. Such a metric to evaluate cache side channel attacks, will provide a reference for the adversaries to choose the suitable attack, and also for the defenders to set up protections for the certain ECDSA implementation (e.g., updating the private key after it has been used for a certain number of signatures). In this paper, we design an evaluation approach to quantitatively compare the cache side channel attacks against ECDSA. The expected minimum number of signatures needed for at least one successful private key recovery, is proposed as the metric, and this metric considers both the data requirements and the success probability. We apply the approach to evaluate various cache side channel attacks against ECDSA. By calculating the metric, we obtain (a) for each attack, the optimal parameters with the minimum number of signatures needed, and (b) for each ECDSA implementation, the minimum number of signatures that will be enough for at least one successful private key recovery of some cache side channel attacks.

Ziqiang Ma, Quanwei Cai, Jingqiang Lin, Jiwu Jing, Dingfeng Ye, Lingjia Meng

Side-Channel Leakage of Alarm Signal for a Bulk-Current-Based Laser Sensor

Laser-based fault injections (LFI) attack is a serious threat against cryptographic implementations. One of the effective countermeasures against LFI attacks is to detect the laser shot and delete the sensitive information before any leakage occurs. This paper focuses on an ASIC AES implementation protected by a laser sensor that can detect the irregular current caused by the laser shot and send the alarm signal. We experimentally show that the single-bit alarm signal generated by the laser sensor is a source of side-channel leakage that leaks the sensitive information of the AES calculation. Specifically, by adjusting the strength of the laser shot to achieve an unstable alarm signal, we demonstrate the most effective successful key recovery in our setup. Our results imply that the sensitivity of the on-chip sensor could leak the sensitive information of cryptographic calculation; thus they should be implemented with careful side-channel countermeasures.

Yang Li, Ryota Hatano, Sho Tada, Kohei Matsuda, Noriyuki Miura, Takeshi Sugawara, Kazuo Sakiyama

Identity-Based Cryptography

Frontmatter

Efficient Identity-Based Outsider Anonymous Public-Key Trace and Revoke with Constant Ciphertext-Size and Fast Decryption

In this paper, we present the first identity-based outsider anonymous public-key trace and revoke (OAnoPKTR) scheme achieving constant-size communication bandwidth and computation cost. Our construction is obtained by twitching Tardos fingerprinting code (TFC) over Waters identity-based encryption (IBE) framework (EUROCRYPT 2005) endowed with the most efficient asymmetric Type-3 variant of the bilinear maps. We efficiently couple two mutually orthogonal functionalities, namely receivers anonymity and public traceability, which is difficult to accomplish without losing cost-efficiency. Our scheme provably achieves indistinguishable chosen-plaintext attack (IND-CPA) security against adaptive adversary beneath the standard decisional bilinear Diffie-Hellman exponent (DBDHE) assumption. The security analysis is in the standard security model without applying random oracles.

Mriganka Mandal, Ratna Dutta

Generic Constructions of Revocable Identity-Based Encryption

Revocable identity-based encryption (RIBE) is an extension of IBE which can support a key revocation mechanism, and it is important when deploying an IBE system in practice. Boneh and Franklin (Crypto’01) presented the first generic construction of RIBE, however, their scheme is not scalable where the size of key updates is linear in the number of users in the system. Then, Boldyreva, Goyal and Kumar (CCS’08) presented the first scalable RIBE which significantly reduces the size of key update to logarithmic in the number of users.In this paper, we first present a generic construction of scalable RIBE from any IBE in a black-box way which solves the open problem presented by Seo and Emura (PKC’13). Our construction has some merits both in theory and practice. In theory, we can obtain the first RIBE scheme from quadratic residues modulo composite and the first adaptive-ID secure RIBE scheme from lattices if we instantiate the underlying IBE with IBE schemes from quadratic residues modulo composite and adaptive-ID secure IBE schemes from lattices, respectively. In practice, public parameters size and secret keys size of our construction can be same as those of the underlying (H)IBE scheme. Our construction is naturally server-aided where the overheads of decryption computation for receivers is the same as that of underlying IBE schemes. Inspired by recent work of Katsumata et al. (PKC’19), we present a generic construction of RIBE with decryption key exposure resistance by using hierarchical IBE (HIBE) and IBE schemes. Finally, we reduce the ciphertext size to constant by using two HIBE schemes.

Xuecheng Ma, Dongdai Lin

Certificateless Identity-Concealed Authenticated Encryption Under Multi-KGC

In the certificateless cryptography, users generate their partial private key and the Key Generation Centre (KGC) generates the other partial private key of users. In some certificateless application scenarios, a sender might want to send messages to a receiver which registers with another KGC. Unfortunately, no certificateless authenticated encryption scheme under multi-KGC has been put forward so far. In this work, we propose the first certificateless identity-concealed authenticated encryption scheme under multi-KGC. Our proposed scheme hides the public identity information of both sender and receiver from any third party. We build a security model for certificateless identity-concealed authenticated encryption scheme under multi-KGC. We prove that our proposed scheme is secure under the random oracle model. We also present a variant of our proposed scheme which supports bilateral identity-concealed authentication key exchange.

Chuang Li, Chunxiang Xu, Yunlei Zhao, Kefei Chen, Xiaojun Zhang

Signatures

Frontmatter

A Pairing-Less Identity-Based Blind Signature with Message Recovery Scheme for Cloud-Assisted Services

The rapid growing big data enforces many organizations to shift their data and services like digital right management, e-payment, and e-voting systems to the cloud. In such cloud-assisted services, the blind signature scheme could be one of the cryptographic tools, which provides the integrity of data and user anonymity. It allows the user to ask the signer for signing on message without disclosing any information about the content to the signer. Since several blind signature schemes have been proposed, but due to the expensive computation and bandwidth cost, they are impractical for the cloud-assisted as well as Internet-based environment. In this paper, we propose a new provable secure identity-based blind signature scheme with message recovery (IDBS-MR) using the elliptic curve cryptography. The proposed IDBS-MR scheme does not transmit the message with the signature while the message is recovered during verification round; hence it has the least message-signature length. The security analysis shows that the proposed IDBS-MR scheme is secured against existential forgery attack under the adaptive chosen message and ID attacks (EF-ID-CMA) under the assumption of solving the ECDL problem, and random oracle model (ROM) and achieves blindness property. The performance analysis shows that our scheme is efficient as compared to related existing schemes.

Mahender Kumar, Satish Chand

Group Signatures with Decentralized Tracing

Group signature is a useful cryptographic primitive that allows a message to be signed by a user on behalf of a group which is managed by some trusted authority, namely the group manager. However, group signature schemes typically place a disturbingly high level of trust on the group manager, which has become a major deployment issue in cyber applications where there is no centralized trust management. In this paper, we investigate mechanisms that aim to achieve a balance between anonymity and accountability in group signatures by decentralizing the operation of tracing the signer. We propose a practical group signature scheme with decentralized tracing. When comparing with a similar result by Benjumea et al. (FC 2008), our proposal has the advantage of a shorter signature size.

Tingting Lu, Jiangtao Li, Lei Zhang, Kwok-Yan Lam

MQ Aggregate Signature Schemes with Exact Security Based on UOV Signature

Multivariate public key cryptography which relies on multivariate quadratic (MQ) problem is one of the main approaches to guarantee the security of communication in the post-quantum world. In this paper, we focus mainly on the yet unbroken (under proper parameter choice) Unbalanced Oil and Vinegar (UOV) scheme, and discuss the exact security of it. Then we propose a combined signature scheme which that (1) not only can reduce the public key size of the UOV signature scheme, and (2) but also can provide tighter security against chosen-message attack in the random oracle. On the other hand, we propose a novel aggregate signature scheme based on UOV signature scheme. Additionally, we give security proof for our aggregate signature scheme under the security of our proposed signature scheme.

Jiahui Chen, Jie Ling, Jianting Ning, Zhiniang Peng, Yang Tan

Untraceability of Partial Blind and Blind Signature Schemes

Blind Signature is employed in privacy related protocols, where signer signs on a blinded message. It provides anonymity in various cryptographic applications such as electronic voting, digital cash system etc. Concerning the need for quantum resistant scheme, Ruckert and Tian et al. proposed the lattice based blind signature and partial blind signature schemes respectively. But, both the schemes left out one of the security requirement of a blind i.e. Untraceability, where the signer can’t link the blinded signature with a valid message-signature pair even when it is revealed in public. In this article, we propose an attack on the untracebility property of both the schemes. The proposed attack opens the door for researchers to work on quantum resistant untraceable blind signature.

Swati Rawal, Sahadeo Padhye

Cryptanalysis

Frontmatter

Improved Integral Attack on Generalized Feistel Cipher

Division property is a generalized integral property proposed by Todo in Eurocrypt 2015. Utilizing automated tools such as SAT and MILP, the complexity to search for integral distinguisher by division property was greatly reduced. Based on division property and automated tools, Derbez et al. obtained a 10-round integral distinguisher of RECTANGLE by considering the linear transformation of the input and output state bits of the cipher, which is one round longer than known integral distinguishers. In this paper, we further consider improved integral attack on block ciphers with Generalized Feistel Structure (GFS cipher) by considering the linear transformation of the S-boxes. Taking the 16-branch GFS cipher with 4-bit S-boxes as an example, using this improved method, we can increase the round of integral distinguishers by one round for many S-boxes. The result implies that ability to resist this improved integral attack should also be considered when designing corresponding GFS ciphers.

Zhichao Xu, Hong Xu, Xuejia Lai

Enhanced Differential Cache Attacks on SM4 with Algebraic Analysis and Error-Tolerance

Block ciphers with Feistel structures are vulnerable to a specific type of cache attacks named differential cache attacks. The attacks leverage side-channel leakages from cache and differential property of cipher component to reveal the master key of cipher. In this paper, we combine the algebraic analysis to enhance the attacks, and propose a novel method named Algebraic Differential Cache Attack (ADCA). By converting both cipher and cache leakages to algebraic equations, ADCA can reveal the cipher key automatically with the help of the SAT solver, which allows the analysis on much deeper rounds and makes a considerable reduction in attack complexity. When it is applied to the block cipher SM4, 10 plaintexts are enough to reveal the master key in 8-rounds analysis, while the traditional differential cache attack needs 20 ones. Finally, to eliminate the impact from noise, an error-tolerant method is proposed to deduce cache events from the leakage traces. It vastly enhances the robustness of attack, and makes the attack more practical. The experimental results show that the error-tolerant ADCA can correctly reveal the master key even when the uncertainty rate of cache events reaches to 60%.

Xiaoxuan Lou, Fan Zhang, Guorui Xu, Ziyuan Liang, Xinjie Zhao, Shize Guo, Kui Ren

Authentication

Frontmatter

Round-Efficient Anonymous Password-Authenticated Key Exchange Protocol in the Standard Model

Anonymous password-authenticated key exchange (APAKE) protocols allow for authenticating legitimate users via low-entropy passwords while keeping their actual identities private. They are important cryptographic primitives for privacy protection, which have attracted much attention recently and have been standardized in the international standard ISO/IEC 20009-4. However, most of the existing APAKE schemes (especially including all the APAKE schemes in the storage-extra setting) are developed in the random oracle model. In this paper, we present the first storage-extra APAKE protocol in the standard model by combing the technique of algebraic MAC with oblivious designated-verifier non-interactive zero-knowledge (DVNIZK) proof. Toward our aim, we first give out a new construction of the oblivious DVNIZK proof system, which is compatible with a new class of algebraic MAC schemes. As a consequence, our APAKE protocol needs only 2 flows of messages in the authentication phase, which is very efficient in terms of rounds. Moreover, we show that this protocol enjoys stronger security guarantees while achieves considerably computational performance.

Qihui Zhang, Wenfen Liu, Kang Yang, Xuexian Hu, Ying Mei

Strong Authenticity with Leakage Under Weak and Falsifiable Physical Assumptions

Authenticity can be compromised by information leaked via side-channels (e.g., power consumption). Examples of attacks include direct key recoveries and attacks against the tag verification which may lead to forgeries. At FSE 2018, Berti et al. described two authenticated encryption schemes which provide authenticity assuming a leak-free implementation of a Tweakable Block Cipher ($$\mathsf {TBC} $$). Precisely, security is guaranteed even if all the intermediate computations of the target implementation are leaked in full but the $$\mathsf {TBC} $$ long-term key. Yet, while a leak-free implementation reasonably models strongly protected implementations of a $$\mathsf {TBC} $$, it remains an idealized physical assumption that may be too demanding in many cases, in particular if hardware engineers mitigate the leakage to a good extent but (due to performance constraints) do not reach leak-freeness. In this paper, we get rid of this important limitation by introducing the notion of Strong Unpredictability with Leakage for $$\mathsf {BC} $$’s and $$\mathsf {TBC} $$’s. It captures the hardness for an adversary to provide a fresh and valid input/output pair for a $$(\mathsf {T})\mathsf {BC} $$, even having oracle access to the $$(\mathsf {T})\mathsf {BC} $$, its inverse and their leakages. This definition is game-based and may be verified/falsified by laboratories. Based on it, we then provide two Message Authentication Codes ($$\mathsf {MAC} $$) which are secure if the $$(\mathsf {T})\mathsf {BC} $$ on which they rely are implemented in a way that maintains a sufficient unpredictability. Thus, we improve the theoretical foundations of leakage-resilient $$\mathsf {MAC} $$ and extend them towards engineering constraints that are easier to achieve in practice. (The full version of this paper is available on ePrint [8].)

Francesco Berti, Chun Guo, Olivier Pereira, Thomas Peters, François-Xavier Standaert

Mathematical Foundations

Frontmatter

Improving ECDLP Computation in Characteristic 2

Pollard rho and its parallelized variants are at present known as the best generic algorithms for computing discrete logarithms in groups of elliptic curves over finite fields. The $$r+h$$-mixed walk, one of the variant parallelized rho method in characteristic 2, is expected to have r times point addition operations and h times point halving operations. We observe that by reducing the randomness but increasing the ratio of h/r, the overall efficiency for parallelized rho method can be improved. Hence, we try to find the best ratio to get the best overall efficiency for parallelized rho method. And then, we provide an optimal configuration with the best overall efficiency for the parallelized rho method. Our experiments show that the optimal configuration can improve the overall efficiency of ECC2-79 by about $$36\%$$. Further, we give algorithms to improve the efficiency of basic operations in $$\mathbb {F}_{2^{131}}$$ and estimate that the optimal configuration can improve the overall efficiency of ECC2-131 by about $$39\%$$.

Fangguo Zhang, Zhijie Liu, Ping Wang, Haibo Tian

Linear Complexity of New q-ary Generalized Cyclotomic Sequences of Period

In this paper, we construct new q-ary generalized cyclotomic sequences of length $$2p^n$$. We study the linear complexity of these sequences over the finite field of order q and show that they have high linear complexity when $$n\ge 2$$. These sequences are constructed by new generalized cyclotomic classes presented by Zeng et al.

Vladimir Edemskiy, Nikita Sokolovskii

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise