A Non-interactive Public-Key Distribution System

An identity-based non-interactive public key distribution system is presented that is based on a novel trapdoor one-way function allowing a trusted authority to compute the discrete logarithms modulo a publicly known composite number m while this is infeasible for an adversary not knowing the factorization of m. Without interaction with a key distribution center or with the recipient of a given message, a user can generate a mutual secure cipher key based solely on the recipient's identity and his own secret key, and subsequently send the message, encrypted with the generated cipher used in a conventional cipher, over an insecure channel to the recipient. In contrast to previously proposed identity-based systems, no public keys, certificates for public keys or other information need to be exchanged and thus the system is suitable for certain applications that do not allow for interaction. The paper solves an open problem proposed by Shamir in 1984.     

Cryptography with chaos at the physical level

In this work, we devise a chaos-based secret key cryptography scheme for digital communication where the encryption is realized at the physical level, that is, the encrypting transformations are applied to the wave signal instead to the symbolic sequence. The encryption process consists of transformations applied to a two-dimensional signal composed of the message carrying signal and an encrypting signal that has to be a chaotic one. The secret key, in this case, is related to the number of times the transformations are applied. Furthermore, we show that due to its chaotic nature, the encrypting signal is able to hide the statistics of the original signal.     

Revocable hierarchical identity-based encryption with shorter private keys and update keys

Revocable hierarchical identity-based encryption (RHIBE) is an extension of HIBE that supports the revocation of user’s private keys to manage the dynamic credentials of users in a system. Many different RHIBE schemes were proposed previously, but they are not efficient in terms of the private key size and the update key size since the depth of a hierarchical identity is included as a multiplicative factor. In this paper, we propose efficient RHIBE schemes with shorter private keys and update keys and small public parameters by removing this multiplicative factor. To achieve our goals, we first present a new HIBE scheme with the different generation of private keys such that a private key can be simply derived from a short intermediate private key. Next, we show that two efficient RHIBE schemes can be built by combining our HIBE scheme, an IBE scheme, and a tree based broadcast encryption scheme in a modular way.     

Certificateless signature: a new security model and an improved generic construction

Certificateless cryptography involves a Key Generation Center (KGC) which issues a partial key to a user and the user also independently generates an additional public/secret key pair in such a way that the KGC who knows only the partial key but not the additional secret key is not able to do any cryptographic operation on behalf of the user; and a third party who replaces the public/secret key pair but does not know the partial key cannot do any cryptographic operation as the user either. We call this attack launched by the third party as the key replacement attack. In ACISP 2004, Yum and Lee proposed a generic construction of digital signature schemes under the framework of certificateless cryptography. In this paper, we show that their generic construction is insecure against key replacement attack. In particular, we give some concrete examples to show that the security requirements of some building blocks they specified are insufficient to support some of their security claims. We then propose a modification of their scheme and show its security in a new and simplified security model. We show that our simplified definition and adversarial model not only capture all the distinct features of certificateless signature but are also more versatile when compared with all the comparable ones. We believe that the model itself is of independent interest.A conventional certificateless signature scheme only achieves Girault’s Level 2 security. For achieving Level 3 security, that a conventional signature scheme in Public Key Infrastructure does, we propose an extension to our definition of certificateless signature scheme and introduce an additional security model for this extension. We show that our generic construction satisfies Level 3 security after some appropriate and simple modification. A preliminary version of the extended abstract of partial results appeared in ACISP 2006 [9].     

Design of Self-Healing Key Distribution Schemes

A self-healing key distribution scheme enables dynamic groups of users of an unreliable network to establish group keys for secure communication. In such a scheme, a group manager, at the beginning of each session, in order to provide a key to each member of the group, sends packets over a broadcast channel. Every user, belonging to the group, computes the group key by using the packets and some private information. The group manager can start multiple sessions during a certain time-interval, by adding/removing users to/from the initial group. The main property of the scheme is that, if during a certain session some broadcasted packet gets lost, then users are still capable of recovering the group key for that session simply by using the packets they have received during a previous session and the packets they will receive at the beginning of a subsequent one, without requesting additional transmission from the group manager. Indeed, the only requirement that must be satisfied, in order for the user to recover the lost keys, is membership in the group both before and after the sessions in which the broadcast messages containing the keys are sent. This novel and appealing approach to key distribution is quite suitable in certain military applications and in several Internet-related settings, where high security requirements need to be satisfied. In this paper we continue the study of self-healing key distribution schemes, introduced by Staddon et al. [37]. We analyze some existing constructions: we show an attack that can be applied to one of these constructions, in order to recover session keys, and two problems in another construction. Then, we present a new mechanism for implementing the self-healing approach, and we present an efficient construction which is optimal in terms of user memory storage. Finally, we extend the self-healing approach to key distribution, and we present a scheme which enables a user to recover from a single broadcast message all keys associated with sessions in which he is member of the communication group.     

A more secure parallel keyed hash function based on chaotic neural network

Although various hash functions based on chaos or chaotic neural network were proposed, most of them can not work efficiently in parallel computing environment. Recently, an algorithm for parallel keyed hash function construction based on chaotic neural network was proposed [13]. However, there is a strict limitation in this scheme that its secret keys must be nonce numbers. In other words, if the keys are used more than once in this scheme, there will be some potential security flaw. In this paper, we analyze the cause of vulnerability of the original one in detail, and then propose the corresponding enhancement measures, which can remove the limitation on the secret keys. Theoretical analysis and computer simulation indicate that the modified hash function is more secure and practical than the original one. At the same time, it can keep the parallel merit and satisfy the other performance requirements of hash function, such as good statistical properties, high message and key sensitivity, and strong collision resistance, etc.     

Error Correcting Codes, Block Designs, Perfect Secrecy and Finite Fields

The ancient difficulty for establishing a common cryptographic secret key between two communicating parties Alice and Bob is nicely summarized by the Catch-22 dictum of S.J. Lomonaco [1999], to wit: “in order to communicate in secret one must first communicate in secret”. In other words, to communicate in secret, Alice and Bob must already have a shared secret key. In this paper we analyse an algorithm for establishing such a common secret key by public discussion, under the modest and practical requirement that Alice and Bob are initially in possession of keys and , respectively, of a common length which are not necessarily equal but are such that the mutual information is non-zero. This assumption is tantamount to assuming only that the corresponding statistical variables are correlated. The common secret key distilled by the algorithm will enjoy perfect secrecy in the sense of Shannon. The method thus provides a profound generalization of traditional symmetric key cryptography and applies also to quantum cryptography. Here, by purely elementary methods, we give a rigorous proof that the method proposed by Bennett, Bessette, Brassard, Salvail, and Smolin will in general converge to a non-empty common key under moderate assumptions on the choice of block lengths provided the initial bit strings are sufficiently long. Full details on the length requirements are presented. Furthermore, we consider the question of which block lengths should be chosen for optimal performance with respect to the length of the resulting common key. A new and fundamental aspect of this paper is the explicit utilization of finite fields and error-correcting codes both for checking equality of the generated keys and, later, for the construction of various hash functions. Traditionally this check has been done by performing a few times a comparison of the parity of a random subset of the bits. Here we give a much more efficient procedure by using the powerful methods of error-correcting codes. More general situations are treated in Section 8.The research of the first and second authors is supported by grants from NSERC.     

A new substitution–diffusion based image cipher using chaotic standard and logistic maps

In this paper, we propose a new loss-less symmetric image cipher based on the widely used substitution–diffusion architecture which utilizes chaotic standard and logistic maps. It is specifically designed for the coloured images, which are 3D arrays of data streams. The initial condition, system parameter of the chaotic standard map and number of iterations together constitute the secret key of the algorithm. The first round of substitution/confusion is achieved with the help of intermediate XORing keys calculated from the secret key. Then two rounds of diffusion namely the horizontal and vertical diffusions are completed by mixing the properties of horizontally and vertically adjacent pixels, respectively. In the fourth round, a robust substitution/confusion is accomplished by generating an intermediate chaotic key stream (CKS) image in a novel manner with the help of chaotic standard and logistic maps. The security and performance of the proposed image encryption technique has been analyzed thoroughly using various statistical analysis, key sensitivity analysis, differential analysis, key space analysis, speed analysis, etc. Results of the various types of analysis are encouraging and suggest that the proposed image encryption technique is able to manage the trade offs between the security and speed and hence suitable for the real-time secure image and video communication applications.     

On non-negligible bias of the first output byte of RC4 towards the first three bytes of the secret key

In this paper, we show that the first byte of the keystream output of RC4 has non-negligible bias towards the sum of the first three bytes of the secret key. This result is based on our observation that the index, where the first byte of the keystream output is chosen from, is approximately twice more likely to be 2 than any other value. Our technique is further used to theoretically prove Roos’s experimental observation (A class of weak keys in the RC4 stream cipher, 1995) related to weak keys.     

A fast image encryption and authentication scheme based on chaotic maps

In recent years, a variety of chaos-based image cryptosystems have been proposed. The key used for encryption/decryption is usually independent of the plain-image. To achieve a satisfactory level of security, at least two overall rounds of the substitution-diffusion process are required so that a change in any pixels of the plain-image spreads over the whole cipher-image. Moreover, the receiver is not able to determine whether the decrypted image is exactly the one sent. In this paper, a fast image encryption and authentication scheme is proposed. In particular, a keyed hash function is introduced to generate a 128-bit hash value from both the plain-image and the secret hash keys. The hash value plays the role of the key for encryption and decryption while the secret hash keys are used to authenticate the decrypted image. Simulation results show that satisfactory security performance is achieved in only one overall round. The speed efficiency is thus improved.     

A key-lock-pair oriented access control scheme for the growth of users and files

A new access control scheme for the growth of users and files in file protection systems is proposed. Our scheme associates each user with a user key and each file with a file key. For each key, there are some corresponding locks, that can be extracted from a nonsingular matrix. Through simple operations on keys and locks, privacy decisions of the protection system can easily be revealed. Furthermore, by employing our method, whenever a new user or file is joined, the corresponding key values and lock values will be determined immediately without changing any previously defined keys and locks.     

Cryptosystem using chaotic keys

According to Kerchoff's principle, the secrecy of a cryptosystem must reside entirely on the secret keys. In this paper, a new cryptosystem is presented and one of its secret keys is generated by a chaotic map, we call it chaotic key. Some experimental results are given and the security of our cryptosystem is discussed.     

Efficient identity-based encryption with Hierarchical key-insulation from HIBE

Hierarchical key-insulated identity-based encryption (HKIBE) is identity-based encryption (IBE) that allows users to update their secret keys to achieve (hierarchical) key-exposure resilience, which is an important notion in practice. However, existing HKIBE constructions have limitations in efficiency: sizes of ciphertexts and secret keys depend on the hierarchical depth. In this paper, we first triumph over the barrier by proposing simple but effective design methodologies to construct efficient HKIBE schemes. First, we show a generic construction from any hierarchical IBE (HIBE) scheme that satisfies a special requirement, called MSK evaluatability introduced by Emura et al. (Des. Codes Cryptography 89(7):1535–1574, 2021). It provides several new and efficient instantiations since most pairing-based HIBE schemes satisfy the requirement. It is worth noting that it preserves all parameters’ sizes of the underlying HIBE scheme, and hence we obtain several efficient HKIBE schemes under the k-linear assumption in the standard model. Since MSK evaluatability is dedicated to pairing-based HIBE schemes, the first construction restricts pairing-based instantiations. To realize efficient instantiation from various assumptions, we next propose a generic construction of an HKIBE scheme from any plain HIBE scheme. It is based on Hanaoka et al.’s HKIBE scheme (Asiacrypt 2005), and does not need any special properties. Therefore, we obtain new efficient instantiations from various assumptions other than pairing-oriented ones. Though the sizes of secret keys and ciphertexts are larger than those of the first construction, it is more efficient than Hanaoka et al.’s scheme in the sense of the sizes of master public/secret keys.

     

Generic cryptographic weakness of k-normal Boolean functions in certain stream ciphers and cryptanalysis of grain-128

This paper considers security implications of k-normal Boolean functions when they are employed in certain stream ciphers. A generic algorithm is proposed for cryptanalysis of the considered class of stream ciphers based on a security weakness of k-normal Boolean functions. The proposed algorithm yields a framework for mounting cryptanalysis against particular stream ciphers within the considered class. Also, the proposed algorithm for cryptanalysis implies certain design guidelines for avoiding certain weak stream cipher constructions. A particular objective of this paper is security evaluation of stream cipher Grain-128 employing the developed generic algorithm. Contrary to the best known attacks against Grain-128 which provide complexity of a secret key recovery lower than exhaustive search only over a subset of secret keys which is just a fraction (up to 5%) of all possible secret keys, the cryptanalysis proposed in this paper provides significantly lower complexity than exhaustive search for any secret key. The proposed approach for cryptanalysis primarily depends on the order of normality of the employed Boolean function in Grain-128. Accordingly, in addition to the security evaluation insights of Grain-128, the results of this paper are also an evidence of the cryptographic significance of the normality criteria of Boolean functions.     

A Weak Key Test for Braid Based Cryptography

This work emphasizes an important problem of braid based cryptography: the random generation of good keys. We present a deterministic, polynomial algorithm that reduces the conjugacy search problem in braid group. The algorithm is based on the decomposition of braids into products of canonical factors and gives a partial factorization of the secret: a divisor and a multiple. The tests we performed on different keys of existing protocols showed that many protocols in their current form are broken and that the efficiency of our attack depends on the random generator used to create the key. Therefore, this method gives new critera for testing weak keys. We also propose a new random generator of key which is secure against our attack and the one of Hofheinz and Steinwandt.     

Geometrical contributions to secret sharing theory

Finite geometry has found applications in many different fields and practical environments. We consider one such application, to the theory of secret sharing, where finite projective geometry has proved to be very useful, both as a modelling tool and as a means to establish interesting results. A secret sharing scheme is a means by which some secret data can be shared among a group of entities in such a way that only certain subsets of the entities can jointly compute the secret. Secret sharing schemes are useful for information security protocols, where they can be used to jointly protect cryptographic keys or provide a means of access control. We review the contribution of finite projective geometry to secret sharing theory, highlighting results and techniques where its use has been of particular significance.     

Cryptanalysis of Two McEliece Cryptosystems Based on Quasi-Cyclic Codes

We cryptanalyse here two variants of the McEliece cryptosystem based on quasi-cyclic codes. Both aim at reducing the key size by restricting the public and secret generator matrices to be in quasi-cyclic form. The first variant considers subcodes of a primitive BCH code. The aforementioned constraint on the public and secret keys implies to choose very structured permutations. We prove that this variant is not secure by producing many linear equations that the entries of the secret permutation matrix have to satisfy by using the fact that the secret code is a subcode of a known BCH code. This attack has been implemented and in all experiments we have performed the solution space of the linear system was of dimension one and revealed the permutation matrix. The other variant uses quasi-cyclic low density parity-check (LDPC) codes. This scheme was devised to be immune against general attacks working for McEliece type cryptosystems based on LDPC codes by choosing in the McEliece scheme more general one-to-one mappings than permutation matrices. We suggest here a structural attack exploiting the quasi-cyclic structure of the code and a certain weakness in the choice of the linear transformations that hide the generator matrix of the code. This cryptanalysis adopts a polynomial-oriented approach and basically consists in searching for two polynomials of low weight such that their product is a public polynomial. Our analysis shows that with high probability a parity-check matrix of a punctured version of the secret code can be recovered with time complexity O(n ³) where n is the length of the considered code. The complete reconstruction of the secret parity-check matrix of the quasi-cyclic LDPC codes requires the search of codewords of low weight which can be done with about 2³⁷ operations for the specific parameters proposed.     

On the Security of the Digital Signature Algorithm

We present a key-recovery attack against the Digital Signature Algorithm (DSA). Our method is based on the work of Coppersmith [7], and is similar in nature to the attacks of Boneh et al. [5,9] which use lattice reduction techniques to determine upper bounds on the size of an RSA decryption exponent under which it will be revealed by the attack. This work similarly determines provable upper bounds on the sizes of the two key parameters in the DSA for which the system can be broken. Specifically if about half of the total number of bits in the secret and ephemeral keys, assuming contiguous unknown bits in each key, are known, the system can be shown to be insecure. The same technique shows that if about half of the total number of bits in two ephemeral keys are known, again assumed contiguous unknown bits in each key, but with no knowledge of the secret key, the system can be shown to be insecure.     

Critique of the related-key attack concept

In a related-key attack, an attacker seeks to discover the secret key by requesting encryptions under keys related to the secret key in a manner chosen by the attacker. We describe a new related-key attack against generic ciphers, requiring just O(1) work to distinguish a cipher from random, and O(key length) to completely recover the secret key. This attack applies within a model which was not previously known to be vulnerable, undermining the theoretical foundation of the related-key attack concept. We propose a new definition of related-key security, which prevents all known generic attacks including this new attack. We discuss the theoretical consequences of this new definition.     

Key distribution patterns using Minkowski planes

A key distribution pattern is a combinatorial structure which provides a secure method of distributing secret keys among a number of participants in a cryptographic scheme. Inversive and Laguerre planes have been used to construct key distribution patterns with storage requirements lower than the trivial distribution system. In this note we construct key distribution patterns from Minkowski planes, the third of the so-calledcircle geometries.The author acknowledges the support of the Australian Research Council