Universal composability (UC) is a primary security flavor for designing oblivious transfer (OT) due to its advantage of arbitrary composition. However, the study of UC‐secure OT over lattices is still far behind compared with constructions over prequantum assumptions. Relying on the learning with errors (LWE) assumption, Quach proposes a dual‐mode encryption scheme (SCN’20) for deriving a two‐round OT whose security is provably UC‐secure in the common reference string (CRS) model. Due to its use of a randomized rounding function proposed by Benhamouda et al. (PKC’18), this OT can only be limited to transmitting single‐bit messages. Therefore, conducting trivial repetitions of Quach’s OT when transmitting multibit strings would be very costly. In this work, we put forward a modified dual‐mode encryption cryptosystem under the decisional LWE assumption, from which we can derive a UC‐secure string OT with both full‐fledged dual‐mode security and better efficiency on transmitting strings. The key technique we adopt is a key reconciliation scheme proposed by Jiang et al. (PKC’20), which is utilized to extend the single‐bit symmetric encryption key (produced by the aforementioned rounding function) to a multibit case. Through a comprehensive performance analysis, we demonstrate that our proposal can indeed strike a balance between security and efficiency.

Abstract Fully homomorphic encryption (FHE) allows direct computations over the encrypted data without access to the decryption. Hence multi-key FHE is well suitable for secure multiparty computation. Recently, Brakerski et al. (TCC 2019 and EUROCRYPT 2020) utilized additively homomorphic encryption to construct FHE schemes with different properties. Motivated by their work, we are attempting to construct multi-key FHE schemes via additively homomorphic encryption. In this paper, we propose a general framework of constructing multi-key FHE, combining the additively homomorphic encryption with specific multiparty computation protocols constructed from encryption switching protocol. Concretely, every involved party encrypts his plaintexts with an additively homomorphic encryption under his own public key. Then the ciphertexts are evaluated by suitable multiparty computation protocols performed by two cooperative servers without collusion. Furthermore, an instantiation with an ElGamal variant scheme is presented. Performance comparisons show that our multi-key FHE from additively homomorphic encryption is more efficient and practical.

Abstract As an access control technology of digital material, digital rights management systems have a profound effect on the copyright protection of digital content. To address the threat of key exposure, applying white‐box ciphers is effective to provide a security guarantee for digital rights management systems. SPNbox, proposed at Asiacrypt’16 is such a white‐box cipher that fulfils comprehensive resistance against key exposure for digital rights management systems, including black‐box security on the server‐side and white‐box security on the client‐side. So far, the previous integral cryptanalysis of SPNbox employs a general 2‐round distinguisher without considering the details of SPNbox. The properties of SPNbox are carefully explored and a novel 2‐round integral distinguisher is introduced. On this basis, we propose new competitive 3‐round key recovery attacks with lower complexities. Particularly, the improved attack on 3‐round SPNbox‐32 only requires 2 32 chosen plaintexts, whereas the current best attack necessitates 2 62 chosen plaintexts. In addition, integral attacks on 4‐ and 5‐round SPNbox‐8 are presented for the first time. Thus, the security margin of SPNbox‐8 is narrowed by two rounds. These results indicate that the capability of SPNbox resisting integral cryptanalysis is inferior to the designers' claim.

Abstract For the purpose of improving the efficiency of the cryptosystems built upon lattice trapdoors, Chen, Genise and Mukherjee at ASIACRYPT 2019 modified the gadget trapdoor (G‐trapdoor) to an approximate trapdoor, which enables one to sample short preimages approximately from a discrete Gaussian distribution. The implementation shows that the sizes of the hash‐and‐sign signature scheme can be reduced to 3.67 kB for an estimation of 81.67‐bit security, and 9.97 kB for an estimation of 168.81‐bit security. In this study, the spherical sampling method is adapted to the non‐spherical setting, without leaking any information about the trapdoor. Due to the fact that the signature size and the concrete security are closely related to the Gaussian parameter of the sampling algorithm, this technique provides a tradeoff between them. Specifically, two modes of parameters were set up for different goals. (a) Mode 1 admits to achieve the ‘win–win’ scenario, that is, gain concrete security and simultaneously reduce the signature size. Our proof‐of‐concept implementation shows that for an estimation of 94.5‐ and 185.88‐bit security, the signature sizes can be reduced to 3.3 and 6.98 kB. (b) Mode 2 aims mainly to further reduce the signature sizes, without a decrease in the security level. The implementation shows that the signature size can be reduced to 2.35 kB for an estimation of 81.67‐bit security, and 5.75 kB for an estimation of 168.82‐bit security.

Convolutional neural networks (CNNs) have excellent and extensive applications in image recognition. With the continuous exploitation of data value and the proliferation of machine learning-as-a-service, convolutional neural network prediction schemes on privacy preservation have been introduced one after another, which makes much more attention focused on the privacy leakage and services offered to be efficient and light. Therefore, how to improve the convolutional neural prediction scheme on the premise of privacy preservation turns out to be an imperative research issue. In this paper, we propose a privacy-preserving convolutional neural network prediction scheme (PCP-LL) that supports low latency and lightweight users. The scheme starts from the perspective of lossless accuracy from underlying networks. First, we construct a secure activation function computing protocol (SActF) utilizing a commodity-based secure comparison protocol, which reduces the complexity and latency during the activation function computing under ciphertexts compared with common schemes. Second, to further support lightweight users, we introduce a secure output layer protocol (SOut) that enables users to obtain the prediction results without extra decryption after simple operations. Then, the scheme adopts the distributed two trapdoors public-key cryptosystem (DT-PKC) to achieve both data and model security, which well avoids security issues especially such as wiretapping by semi-honest participants commonly in secret sharing schemes. Finally, through relevant evaluations, the scheme not only achieves privacy preservation and low latency, but also supports lightweight users.

For group signature (GS) supporting membership revocation, verifier-local revocation (VLR) mechanism seems to be a more flexible choice, because it requires only that verifiers download up-to-date revocation information for signature verification, and the signers are not involved. As a post-quantum secure cryptographic counterpart of classical number-theoretic cryptographic constructions, the first lattice-based VLR group signature (VLR-GS) was introduced by Langlois et al. (2014). However, none of the contemporary lattice-based VLR-GS schemes provide backward unlinkability (BU), which is an important property to ensure that previously issued signatures remain anonymous and unlinkable even after the corresponding signer (i.e., member) is revoked. In this study, we introduce the first lattice-based VLR-GS scheme with BU security (VLR-GS-BU), and thus resolve a prominent open problem posed by previous works. Our new scheme enjoys an $${\cal O}\left( {\log \,N} \right)$$ factor saving for bit-sizes of the group public-key (GPK) and the member’s signing secret-key, and it is free of any public-key encryption. In the random oracle model, our scheme is proven secure under two well-known hardness assumptions of the short integer solution (SIS) problem and learning with errors (LWE) problem.

Lattice-based key exchange protocols have attracted tremendous attention for its post-quantum security. In this work, we construct a Module-LWE-based key exchange protocol using Peikert’s error reconciliation mechanism. Compared with Kyber.KE, our key exchange protocol reduces the total communication cost by 96-byte, i.e., 3.2% ∼ 6.1%, under the different parameter sets, and without reducing the post-quantum security levels. Moreover, our key exchange protocol slightly reduces the probability of session key agreement failure and the time consumed by modular multiplication of numbers and ring elements by approximately 30%. Thus, the key exchange protocol in this paper is more suitable for the lightweight communication systems.

Abstract Attribute‐based encryption (ABE) is a promising management method that enables fine‐grained access control in large‐scale systems. Revocable ABE (RABE) can support a key revocation mechanism in an ABE system. With the advent of the Internet of Things, users may need to delegate their decryption capacity to other devices, which requires that RABE meet a necessary feature called decryption key exposure resistance (DKER). Although many constructions about RABE from bilinear maps have been proposed, the situation of lattice‐based constructions with DKER is less satisfactory. In order to narrow this gap, this paper propose the first lattice‐based RABE with DKER. First, a formal description of RABE with DKER and the corresponding security models is proposed. Subsequently, a lattice‐based RABE scheme without DKER is constructed and it is proved to be selective indistinguishability under chosen‐plaintext attack (IND‐CPA) security based on Learning with Errors (LWE). To achieve DKER, this paper construct a RABE scheme by using the RABE scheme without DKER and a key extension mechanism as its building blocks. Finally, this paper show that this scheme is selective IND‐CPA security, with the DKER based on LWE.

Abstract Aigis‐Enc is an encryption algorithm based on asymmetrical learning with errors (LWE). A thorough comparison between Aigis‐Enc (with the recommended parameters) and a symmetrical LWE encryption scheme on the same scale (the sampling parameters are { η 1 , η 2 } = {2, 2} instead of {1, 4}) on Chosen‐plaintext attack (CPA) security, computation complexity and decryption failure probability is made. In particular, the authors ascertain that the CPA security of Aigis‐Enc is 160.895, and that of the symmetrical LWE encryption scheme on the same scale is 161.834. The ratio of computation complexity on the sampling amount of the former and the latter is 5:4 in the key generation phase and 19:14 in the encryption phase. The decryption failure probability of the former is 2 −128.699 and that of the latter is 2 −67.0582 , then the authors show how to reduce the decryption failure probability of the latter significantly by increasing some traffic. Furthermore, those attacks presented by designers of Aigis‐Enc, including primal attacks and dual attacks are generalised. Our attacks are more extensive, simpler, and clearer. With them, the optimal attacks and the ‘optimal‐optimal attacks’ on Aigis‐Enc and the symmetrical LWE scheme on the same scale are obtained.

With the rapid development of electronic information technology, digital signature has become an indispensable part of our lives. Traditional public key certificate cryptosystems cannot overcome the limitations of certificate management. Identity-based cryptosystems can avoid the certificate management issues. The development of quantum computers has brought serious challenges to traditional cryptography. Post-quantum cryptography research is imperative. At present, almost all post-quantum identity-based signature (IBS) schemes are constructed using Gaussian sampling or trapdoor technologies. However, these two technologies have a great impact on computational efficiency. To overcome this problem, we construct an IBS scheme on lattices by employing Lyubashevsky’s signature scheme. Based on the shortest vector problem on lattices, our scheme does not use Gaussian sampling or trapdoor technologies. In the random oracle model, it is proved that our scheme is strongly unforgeable against adaptive chosen messages and identity attacks. The security level of our scheme is strongly unforgeable, which is a higher level than the existential unforgeability of other schemes. Compared with other efficient schemes, our scheme has advantages in computation complexity and security.

Private information retrieval (PIR) protocol is a powerful cryptographic tool and has received considerable attention in recent years as it can not only help users to retrieve the needed data from database servers but also protect them from being known by the servers. Although many PIR protocols have been proposed, it remains an open problem to design an efficient PIR protocol whose communication overhead is irrelevant to the database size N . In this paper, to answer this open problem, we present a new communication-efficient PIR protocol based on our proposed single-ciphertext fully homomorphic encryption (FHE) scheme, which supports unlimited computations with single variable over a single ciphertext even without access to the secret key. Specifically, our proposed PIR protocol is characterized by combining our single-ciphertext FHE with Lagrange interpolating polynomial technique to achieve better communication efficiency. Security analyses show that the proposed PIR protocol can efficiently protect the privacy of the user and the data in the database. In addition, both theoretical analyses and experimental evaluations are conducted, and the results indicate that our proposed PIR protocol is also more efficient and practical than previously reported ones. To the best of our knowledge, our proposed protocol is the first PIR protocol achieving O1 communication efficiency on the user side, irrelevant to the database size N .

Abstract Identity-based revocation system (IBRS) generates the ciphertext with a revoked identity list such that only the non-revoked identities can use their private keys to decrypt this ciphertext. IBRS can be efficiently applied in some practical applications, such as the pay-TV systems when the number of revoked identities are much less than the non-revoked ones. However, since IBRS is based on identity-based cryptography, it also suffers from the inherent key escrow problem where the private key generator (PKG) has full control of each user’s private key. As a consequence, it is hard to judge whether a pirated private key is generated by the PKG or the suspected user. There is no study on IBRS fulfilling accountability in literature to date. In this paper, we introduce the notion of accountable authority IBRS (A-IBRS), which provides accountability in IBRS schemes. In an A-IBRS, the aforementioned problem can be alleviated and resolved. Furthermore, a full black-box A-IBRS can distinguish the creator of a black box between the PKG and the associated user and the dishonest PKG is allowed to access the decryption results of the user private key. We formalize the definition and security models of the full black-box A-IBRS schemes. Then, we present a concrete full black-box A-IBRS scheme with constant-size master public key and private key. Finally, we prove the security of our scheme under the defined security models without random oracle.

Attribute‐based encryption (ABE) supports fine‐grained sharing of encrypted data so that it can be used in a plenty of application scenarios, and many constructions of ABE scheme have been presented. The first arithmetic circuit ABE system was proposed by Boneh, Gentry, Gorbunov et al . (BGG + 14) in Eurocrypt 2014. It is one of the major candidates for ABE, whose security is based on the learning with errors assumption. In this work, the authorsanalyse three different versions of BGG + 14 ABE with weak attributes, weak variants, and weak modulus. First, they discuss weak attributes of BGG + 14 ABE. A weak attribute is generated with corresponding decryption key, such that whenever a ciphertext is labelled with this weak attribute, 1 bit of the plaintext can be revealed. Second, they discuss the security of three variants of BGG + 14 ABE with simplified pre‐sampled matrices, and show that all of them are not secure under collusion attack. Third, they consider the composite modulus rather than prime modulus in BGG + 14 ABE scheme. They show that, if a small factor of the modulus is known, the set of users able to decrypt is clearly expanded. These analyses give different perspectives on the security of BGG + 14 ABE under different conditions.

For the decryption of the fully homomorphic encryption (FHE) over the integers with the message space ZQ , Nuida and Kurosawa proposed a Q4λ -multiplicative-degree circuit to compute it at Eurocrypt 2015, where λ is the security parameter and the message size Q is a constant. Since the degree of the decryption circuit is polynomial in Q , the range of the message size Q is limited. In this work, we solve this open problem as long as Q is large enough (larger than λ ). We represent the decryption circuit as a arithmetic polynomial of multiplicative degree 108·λ log3λ , which is independent of the message size Q except a constraint Q>λ . Moreover, the bootstrapping process requires only O(λ·log⁡λ) number of multiplications to implement the decryption circuit, which is significantly lower than O(λ4) of Nuida and Kurosawa’s work. We also show the efficiency of the FHE scheme with message space ZQ compared to the FHE scheme with binary message space. As a result, we have that the former is preferable.

The minimum degree (resp. algebraic degree ) of a Boolean permutation is the minimum (resp. maximum) algebraic degree of all the non‐zero linear combinations of its coordinate functions. In this study, the authors concentrate on the design of Boolean permutations with optimal minimum degree . First, they present a novel method for optimising the minimum degrees of known Boolean permutations. Second, they show that the Boolean permutations, which are obtained by optimising Boolean permutations without optimal algebraic degree , have optimal minimum degree. At last, it is shown that their method generates an infinite class of involutions with optimal minimum degree.

Because of the concise functionality of oblivious transfer (OT) protocols, they have been widely used as building blocks in secure multiparty computation and high-level protocols. The security of OT protocols built upon classical number theoretic problems, such as the discrete logarithm and factoring, however, is threatened as a result of the huge progress in quantum computing. Therefore, post-quantum cryptography is needed for protocols based on classical problems, and several proposals for post-quantum OT protocols exist. However, most post-quantum cryptosystems present their security proof only in the context of classical adversaries, not in the quantum setting. In this paper, we close this gap and prove the security of the lattice-based OT protocol proposed by Peikert et al. (CRYPTO, 2008), which is universally composably secure under the assumption of learning with errors hardness, in the quantum setting. We apply three general quantum security analysis frameworks. First, we apply the quantum lifting theorem proposed by Unruh (EUROCRYPT, 2010) to prove that the security of the lattice-based OT protocol can be lifted into the quantum world. Then, we apply two more security analysis frameworks specified for post-quantum cryptographic primitives, i.e., simple hybrid arguments (CRYPTO, 2011) and game-preserving reduction (PQCrypto, 2014).

Identity-based signature has become an important technique for lightweight authentication as soon as it was proposed in 1984. Thereafter, identity-based signature schemes based on the integer factorization problem and discrete logarithm problem were proposed one after another. Nevertheless, the rapid development of quantum computers makes them insecure. Recently, many efforts have been made to construct identity-based signatures over lattice assumptions against attacks in the quantum era. However, their efficiency is not very satisfactory. In this study, an efficient identity-based signature scheme is presented over the number theory research unit (NTRU) lattice assumption. The new scheme is more efficient than other lattice- and identity-based signature schemes. The new scheme proves to be unforgeable against the adaptively chosen message attack in the random oracle model under the hardness of the γ-shortest vector problem on the NTRU lattice.

Abstract Revocation functionality is crucial for the practicality of the public key cryptosystems, especially for that of identity‐based cryptosystems. When some users lose their private keys, the cryptosystems must support an efficient revocation method to revoke such users. On the other hand, strong unforgeability provides stronger security than existential unforgeability and ensures the adversary cannot even produce a new signature for a previously signed message. However, existing revocable identity‐based signature schemes can support neither efficient key revocation nor strong unforgeability. In this paper, we propose a strongly unforgeable identity‐based signature scheme with efficient revocation. In the proposed scheme, the master key is randomly divided into two parts: one is used to construct the initial secret key, the other is used to generate the key update. Furthermore, they are used to periodically and re‐randomly produce signing keys for non‐revoked users. Thus, the proposed scheme can efficiently revoke users and resist key exposure attacks. In the standard model, our scheme is proven to be strongly unforgeable under the CDH hardness assumption. Copyright © 2016 John Wiley & Sons, Ltd.

Abstract The first multi‐use unidirectional proxy re‐signature scheme was proposed by Benoît and Damien in 2008, which allowed translating in one direction and can be re‐translated several times. However, constructing multi‐use unidirectional proxy re‐signature scheme where the size of signature and the verification cost did not increase linearly with the number of translations was left as the open problem. This paper presents an efficient multi‐use unidirectional proxy re‐signature scheme and a multi‐use identity‐based unidirectional proxy re‐signature. They are proven secure in the standard model under the small integer solution assumption. And they solve the open problem left in 2008. Moreover, as proxy re‐signature scheme based on the number theory assumptions is no longer secure in quantum era, they are still secure. Copyright © 2017 John Wiley & Sons, Ltd.

Abstract Two ring signature schemes over number theory research unit (NTRU) lattices are presented. The first scheme constructed in the random oracle model is an extension of Ducas, Lyubashevsky, and Prest's identity‐based encryption scheme over NTRU lattices (in Asiacrypt 2014). Moreover, motivated by Boyen's lattice mixing and vanishing trapdoors (in PKC 2010), the second scheme in the standard model is achieved. Under the chosen‐message attack, our new constructions are proved strongly existentially unforgeable, and the security can be reduced to the hardness of NTRU lattices. Compared with the existing lattice‐based ring signatures, our schemes are more efficient and with shorter signature length. Copyright © 2016 John Wiley & Sons, Ltd.

Abstract Proxy re‐encryption (PRE) is a cryptographic primitive that allows a proxy to turn an Alice's ciphertext into a Bob's ciphertext on the same plaintext. At present, there are many different PRE schemes that have been proposed with different properties. However, all of them are based on the logarithm assumption and the large integer factorization assumption except for a bidirectional PRE scheme over lattices. In this paper, we construct the first multi‐use unidirectional PRE scheme based on lattices. In addition, the generation of the PRE key does not interact with two users, and the scheme can resist collusion attacks. Moreover, it is proved chosen plaintext attack secure in the standard model based on the Learning With Errors assumption. Finally, an identity‐based PRE is obtained from the basic construction. Copyright © 2015 John Wiley & Sons, Ltd.

Key-dependent message KDM security should be considered in the design of security protocols, especially for complicated ones, where the messages related to the secret key might be encrypted. In this paper, we present a new method of constructing a KDM secure asymmetric encryption scheme with the notation of hybrid encryption in the standard model; although the notation of hybrid encryption was thought as no help to get rid of dependencies between messages and the secret key. Our result can also be seen as a partial instantiation for a previously well-known KDM secure asymmetric encryption scheme based on random oracle. As we know, this has never been carried out before. And our result indicates a new cryptographic application for the primitive of lossy trapdoor function. Throughout the paper, our main idea is to archive KDM security by making use of both leakage-resilience and auxiliary-input security properties. Copyright © 2014 John Wiley & Sons, Ltd.

ABSTRACT Public key cryptography is an important technique to resolve the security issues in computer communication networks. In some scenarios, a public key cryptosystem with double trapdoor decryption mechanism is desired. Previous known public key cryptosystems with double trapdoor decryption mechanism achieve no standard semantic security goals against adaptive chosen ciphertext attacks and were shown vulnerable to some attacks. In this paper, two new problems, the generalized RSA problem and the computational generalized RSA problem, are introduced, and the equivalence of the standard RSA problem and the computational generalized RSA problem is proven. Accordingly, on the basis of the computational generalized RSA problem, a public key cryptosystem with double trapdoor decryption mechanism, called GenRSA, is presented. We prove the GenRSA's indistinguishability security against adaptive chosen ciphertext attack under the computational generalized RSA intractability assumption and in the random oracle model. Copyright © 2013 John Wiley & Sons, Ltd.

The F5 algorithm [8] is generally believed as one of the fastest algorithms for computing Gröbner bases. However, its termination problem is still unclear. The crux lies in the non-determinacy of the F5 in selecting which from the critical pairs of the same degree. In this paper, we construct a generalized algorithm F5GEN which contain the F5 as its concrete implementation. Then we prove the correct termination of the F5GEN algorithm. That is to say, for any finite set of homogeneous polynomials, the F5 terminates correctly.

ABSTRACT An identity‐based signature scheme from lattices is constructed. The scheme is obtained from a modification of Agrawal, Boneh, and Boyen's lattice identity‐based encryption scheme. In this construction, we use two distinct trapdoors for finding short bases. One trapdoor enables the real implementation to generate short bases for all lattices. The other trapdoor enables the simulator to generate short bases for all lattices. Furthermore, the generating short bases are used to sample short vectors as signatures. Our scheme is computationally efficient. The scheme's strong unforgeability is proven in the standard model and rests on the hardness of the small integer solution problem. Finally, we extend the basic construction to obtain a hierarchical identity‐based signature scheme. Copyright © 2012 John Wiley & Sons, Ltd.

ABSTRACT Symmetric polynomial‐based key distribution scheme has been widely adopted in various communication applications. This type of key distribution consists of a server and a set of users, where the server is responsible to distribute shares for each user via a symmetric polynomial. Based on the property of symmetry of this polynomial, each pair of users can compute a common secret key using their shares for establishing a secure communication channel. However, some users may receive faulty shares from the server because of some uncertain factors in the communication environment, such as software failures and transmission errors. As a result, the users who receive faulty shares cannot share common secret keys with other users. To solve this problem, in this paper, we propose two individual verifiable key distribution schemes on the basis of a symmetric polynomial based key distribution. In both our proposed schemes, the server adopts the same approach to distribute shares for users; the users are able to verify the validity of their shares without revealing them before establishing communication channels. If all shares are verified valid, users can ensure that each pair of them possesses a common secret key, they can establish secure communication channels when needed; otherwise, all users can collaborate to identify those users who possess faulty shares and require the server to distribute a set of valid shares for those users. Furthermore, both our proposed schemes are efficient, because the procedures of verification and identification do not involve any complicated cryptographic operation. Copyright © 2012 John Wiley & Sons, Ltd.

ABSTRACT Internet Key Exchange (IKE) protocol is widely applied on the Internet to protect confidentiality of the Internet communication. However, there are many high‐risk security vulnerabilities in various IKE implementations. Traditional fuzzing approaches with the aim of discovering vulnerabilities have some blind spots, such as time‐consuming, low efficiency, and low degree of automation. This paper introduces a new vulnerability discovering approach based on fuzzing and applies the approach to the IKE protocol. Through summarizing the most comprehensive vulnerable points of IKE protocol and proposing a two‐stage test cases library, an IKE protocol vulnerability discovering tool called IKEProFuzzer is designed and implemented. It is a network protocol fuzzing framework with extensibility and automated Monitor/Debugger designed by ourselves. In the experiments, IKEProFuzzer has discovered 14 vulnerabilities, including nine released vulnerabilities and five unreleased ones, which affect many kinds of routers and applications. The evaluation results prove the feasibility, efficiency, and extensibility of the approach compared with the existing approaches. Copyright © 2012 John Wiley & Sons, Ltd.

ABSTRACT Correlation power analysis (CPA) has been a powerful and thoroughly studied threat for implementations of block ciphers and public key algorithms but not yet for stream ciphers. This paper proposes a novel CPA attack on the hardware‐oriented stream cipher Trivium, one of the finally chosen ciphers by the eSTREAM project. Based on the Hamming distance model, the proposed attack exploits the resynchronization phase of Trivium. By choosing proper initial value vectors, the algorithmic noise of the device is completely eliminated. Furthermore, a novel concept of modified correlation coefficients is introduced, which can be used to describe the relation between the hypothetical power consumption values and the measured power consumption values. Through the calculation of modified correlation coefficients, the effect of the electronic noise is significantly decreased and values of the hypotheses can be discriminated uniquely by the highest modified correlation coefficient. According to the recovered hypotheses, many equations on the secret key bits can be obtained, which will be sequentially solved to extract the secret key of Trivium. Compared with Fischer's differential power analysis attack on Trivium, the proposed algorithm is more efficient and robust. Finally, a simulation attack is mounted to confirm the efficiency of the algorithm. Copyright © 2011 John Wiley & Sons, Ltd.

ABSTRACT In this paper, we concentrate on the design of 1‐resilient Boolean functions with desirable cryptographic properties. Firstly, we put forward a novel secondary construction to obtain 1‐resilient functions. Next, we present the relationships between the properties of these constructed 1‐resilient functions and that of the initial functions. Based on the construction and a class of bent functions on n variables, we can obtain a class of ( n + 3)‐variable 1‐resilient non‐separable cryptographic functions with a high algebraic immunity, whose nonlinearity is equal to the bent concatenation bound 2 n + 2 − 2 ( n + 2)/2 . Furthermore, we propose a set of 1‐resilient non‐separable functions on odd number of variables with an optimal algebraic degree, a high algebraic immunity, and a high nonlinearity. Copyright © 2011 John Wiley & Sons, Ltd.

Although there are many different approaches used in cryptanalysis of nonlinear filter generators, the selection of tap positions has not received enough attention yet. In this paper we examine the security of nonlinear filter generators that output several bits at the time against a variant of a guess and determine attack that takes into account the tap positions of the generator. In difference to the filter state guessing attack (FSGA) introduced by Pasalic (2009), our approach further reduces the input preimage space by using a given placement of the tap positions. The new attack, though a simple generalization of the FSGA, in many cases outperforms both classical algebraic attacks and the FSGA. In particular, the new attack is much more efficiently applied against filter generators that use a vectorial Maiorana-McFarland than classical algebraic attacks or the FSGA. As a proof of the concept we apply our attack to the stream cipher SOBER-t32 without stuttering and show that our attack performs slightly better than a guess and determine attack proposed by Babbage et al.

We propose a new biometric identity based encryption scheme (Bio-IBE), in which user biometric information is used to generate the public key with a fuzzy extractor. This is the first Bio-IBE scheme that achieves constant size ciphertext. This is also a scheme that is secure against the adaptive chosen ciphertext attack (CCA2). Details are presented along with a discussion of Shamir’s threshold secret sharing and fuzzy extraction of biometrics, which is based on error correction codes. We also define a security model and prove that the security of the proposed scheme is reduced to the decisional bilinear Diffie-Hellman (DBDH) assumption. The comparison shows that the proposed scheme has better efficiency and stronger security compared with the available Bio-IBE schemes.

In this paper, the correlation properties of a nonlinear combining function over its support or zero set are investigated. Based on this characterization, a new attack on nonlinear combining generators is proposed. Our attack does not utilize traditional (non)linear statistics between the input and the output over the entire variable space, as the distinguishing process is rather applied to the restricted input space. The attack appears to be very efficient against nonlinear combining generators whose combining LFSRs are of relatively small input size. In many cases, our attack is a more favorable alternative than the known correlation attacks (but also than algebraic attacks in certain cases). To study the maximum correlation of a nonlinear combining function over its support or zero set, the notion of maximum distinguishable correlation is introduced. The relationship between the maximum distinguishable correlation and the nonlinearity of a combining function is then derived by using the normalized Walsh transform. Finally, we extend the usual notion of resiliency and discuss its implications towards the resistance against our attack.

For stream ciphers which use binary linear feedback shift registers as stream generators, fast correlation attack is one of the most important attacks. Aiming at the shortcomings of serial algorithm, the proposed technique is based on parallel computing. This kind of attack divides the initial state into several parts, uses multiprocessor to recover all parts of the initial state synchronously. Comparing with previous results, this kind of attack shows low complexity and high attack efficiency.

Murakami and Nasako proposed a knapsack public key cryptosystem in 2008. They claimed that their proposal is secure against some known attacks. In this paper, we propose a cryptanalytic attack on the cryptosystem. We use a heuristic method to show that the secret key can be recovered with lattice reduction algorithms. Hence, their construction is insecure.

A new knapsack type public key cryptosystem is proposed by constructing an easy knapsack problem. The cryptosystem is shown to be secure against Shamir's key recovery attack in that it does not use a super-increasing knapsack sequence in the construction process. The cryptosystem is also invulnerable to low density attack in that it obtains a relatively high density. It is shown that the cryptosystem resists some brute force attacks and the simultaneous Diophantine approximation attack. It only performs n addition operations for the cryptosystem to encrypt a plaintext, and the decryption algorithm only carries out n modular 2 divisions. Therefore, the cryptosystem is efficient with respect to the encryption and the decryption. Furthermore, the cryptosystem is suited for software and hardware implementations.

In this paper, a new construction of hierarchical ID-Based signature (HIBS) scheme is proposed. The new scheme has some advantages over the available schemes: the private keys size shrinks as the identity depth increases and the signature size is a constant as it consists of three group elements. Furthermore, under the h-CDH assumption, our scheme is provably secure in the standard model. This assumption is more natural than many of the hardness assumptions recently introduced to HIBS in the standard model.

Several public key cryptosystems and authentication schemes based on the conjugator search and root extraction problems over braid groups have been proposed. However, security analysis showed that it is not necessary to solve the underlying conjugator search problem or the root extraction problem in order to break these public key cryptographic algorithms. Hence, these cryptographic primitives suffer from some security drawbacks. A digital signature scheme based on the root extraction problem over braid groups is proposed. It is proven that the only way for the attacker to forge a signature is to extract the eth root for a given braid in the braid group. It is also shown that given sufficiently many message-signature pairs, the attacker needs to solve an intractable problem, the group factorisation problem, in order to forge a signature. Furthermore, it is pointed out that the attacker cannot learn much useful information by reconstructing braid equations with respect to the public and secret keys. Performance analysis shows that the proposed signature scheme is efficient and practical, and the key sizes are acceptable. The computational overheads to sign a message and to verify a signature are only equivalent to several 1024-RSA modular multiplications.

NTRUSign, a digital signature scheme, is suffering an effective attack. In this correspondence, we insert a new perturbation into NTRUSign primitive. With the new perturbation, each signature value is a linear combination of the private keys, and the combination coefficients have a hidden distribution. By a large number of signatures, the attacker obtains the value of some complicated function of the private keys. It appears as hard problem computing the private keys from this value. Our scheme is smaller in size, presents a higher efficiency, and provides a clearer security proof than NTRUSign with the old perturbation.

This paper investigates two new design rules of nonlinear combining functions in stream ciphers. It is shown that a combining function with high nonlinearity and high order correlation immunity is still not enough to prevent the divide and conquer attack and the BAA attack (or the best affine approximation attack) since the autocorrelation function of the combining function may also be leaked much more information about the input of the combining function. To measure the strength of nonlinear combining functions, the notion of maximum autocorrelation is introduced, which is based on the correlation between linear functions of input and the autocorrelation function of a combining function. The relationship between the maximum autocorrelation coefficient and the mutual information of the autocorrelation function of the combining function is discussed. Moreover, the upper bound of maximum autocorrelation coefficient is presented by using Walsh transform.

In this paper, we provide a new generalized construction method for (n, m, t) resilient functions with satisfying synthetical cryptographic criteria. These synthetical cryptographic criteria include high nonlinearity, good resiliency, high algebraic degree, and nonexistence of nonzero linear structure and so on. The construction is based on the use of linear error-correcting code. Given a linear [u, m, t + 1] code and its dual code [u, u - m, t/sup */ + 1], we show that it is possible to construct (n, m, d) resilient functions with satisfying synthetical cryptographic criteria, where d = min(t, t/sup */) and n > u > 2m. The method provides a new idea in designing cryptographic functions.

In this correspondence, we present a simple bit-stream generator. It is a specialization of shrinking generator and a generalization of self-shrinking generator. We call it "generalized self-shrinking generator." The family of such generated sequences has a group structure. The correlation between the sequences is quite good and the sequences themselves are balanced. For each k, 0<k<n, no more than 1/2/sup n-k/ of the sequences have least periods less than 2/sup k/. No more than 1/4 of the sequences have least periods less than 2/sup n-1/. There are two sequences with least periods of 2. There is no sequence with a least period p such that 2<p

Resilient functions play an important role in the art of information security. In this correspondence, we discuss the existence, construction, and enumeration of resilient functions over finite fields. We show that, for each finite field GF(q) with q > 3, we can easily construct a large number of (q, n, 1, n - 1) resilient functions, most of which include mixing terms. We give a general structure for (q, m + 1, m, 1) resilient functions, and present an example which is not of this general structure. We prove that (q, m + 2, m, 2) resilient functions exist for any m such that 12. We prove that (q, m + t, m, t) resilient functions exist for any (m, t) such that 13. By making some simple generalizations of former results, we also provide some new methods for constructing resilient functions.