Information Security and Privacy

This paper addresses the issue of selective disclosure of verifiable content. It extends previous work relating to Content Extraction Signatures [21] to implement a more complex structure that encodes a richer, more flexible fragment extraction policy, which includes fragment grouping. The new extraction policy enables the signer to specify both optional and mandatory fragment associations (or groupings) for verifying extracted content.

In the paper we shall evaluate various aspects of anonymity properties afforded by practical anonymous communication networks. For that purpose, first we propose two novel anonymity metrics for practical anonymous communication networks. Next we shall discuss whether or not deterministic protocols can provide anonymity efficiently in terms of computational complexity. Unfortunately, we can show that it is diffi- cult to build efficient anonymous networks only by means of deterministic approaches. We also run simulation experiments and discuss the results.

In this paper we present a non-transferable anonymous credential system that is based on the concept of a chameleon certificate. A chameleon certificate is a special certificate that enjoys two interesting properties. Firstly, the owner can choose which attributes of the certificate to disclose. Moreover, a chameleon certificate is multi-show in the sense that several uses of the same chameleon certificate by the same user cannot be linked together.We adopt the framework of Brands [2] and our construction improves the results of Camenisch et al. [5] and Verheul [16] since it allows the owner of a certificate to prove general statements on the attributes encoded in the certificate and our certificates enjoy the multi-show property.

This paper introduces weaknesses of two robust Mix-nets proposed in [10] and [7]. First, we show that [10] can lose anonymity in the presence of a malicious user even though all servers are honest. Second, we show that [7] can lose anonymity through the collaboration of a malicious user and the first server. The user can identify the plaintext sent from the targeted user by invoking two mix sessions at the risk of the colluding server receiving an accusation. We also point out that in a certain case, anonymity is violated solely by the user without colluding to any server. Practical repairs are provided for both schemes. Since such flaws are due to their weak security definitions, we present a stronger security definition by regarding a Mix-net as a batch decryption algorithm of a CCA secure public-key encryption scheme.

Privacy presents many puzzles. In particular, why is it eroding, given the high value people assign to their privacy? This extended abstract argues that there are strong incentives for decreasing privacy, rooted in the economic benefits of price discrimination. As a result, the privacy problem is unsolvable. The conflict between incentives to price discriminate and the public dislike of this practice will influence what security technologies are likely to succeed.

This paper examines the cryptographic security of fixed versus random elliptic curves over the field GF(p). Its basic assumption is that a large precomputation to aid in breaking the elliptic curve discrete logarithm problem (ECDLP) can be made for a fixed curve. We take this into account when examining curve security as well as considering a variation of Pollard’s rho method where computations from solutions of previous ECDLPs can be used to solve subsequent ECDLPs on the same curve. We present a lower bound on the expected time to solve such ECDLPs using this method, as well as an approximation of the expected time remaining to solve an ECDLP when a given size of precomputation is available. We conclude that adding 5 bits to the size of a fixed curve to avoid general software attacks and an extra 6 bits to avoid attacks on special moduli and a parameters provides an equivalent level of security.

In [12], Okeya and Sakurai showed that the simple version randomized addition-subtraction chains countermeasure [14] is vulnerable to SPA attack. But their analysis method is not able to be applicable to the complex version [14]. In this paper, we show that Okeya and Sakurai’s attack algorithm has two latent problems which need to be considered. We further propose new powerful concrete attack algorithms which are different from [12,15]. By using our proposed attack algorithms, we can totally break the full version randomized addition-subtraction chains [14]. From our implementation results for standard 163-bit keys, the success probability for the simple version with 20 AD sequences is about 94% and with 30 AD sequences is about 99%. Also, the success probability for the complex version with 40 AD sequences is about 94% and with 70 AD sequences is about 99%.

This work discusses generic arithmetic for arbitrary binary fields in the context of elliptic curve cryptography (ECC). ECC is an attractive public-key cryptosystem recently endorsed by the US government for mobile/wireless environments which are limited in terms of their CPU, power, and network connectivity. Its efficiency enables constrained, mobile devices to establish secure end-to-end connections. Hence the server side has to be enabled to perform ECC operations for a vast number of mobile devices that use variable parameters in an efficient way to reduce cost. We present algorithms that are especially suited to high-performance devices like large-scaled server computers. We show how to perform an efficient field multiplication for operands of arbitrary size, and how to achieve efficient field reduction for dense polynomials. We also give running times of our implementation for both general elliptic curves and Koblitz curves on various platforms, and analyze the results. Our new algorithms are the fastest algorithms for arbitrary binary fields in literature.

This paper gives an efficient algorithm to compute addition in Jacobian of C₃₄ curves. The paper modifies the addition algorithm of [1], by classifying the forms of Groebner bases of all ideals involved in the addition in Jacobian, and by computing Groebner bases of ideals without using Buchberger algorithm. The algorithm computes the addition in Jacobian of C₃₄ curves in about 3 times amount of computation of the one in elliptic curves, when the sizes of groups are set to be the same.

Recently, many research works have been conducted about how to carry out physical cryptanalysis on cryptographic devices by exploiting any possible leaked information through side channels. Research results were also reported on how to develop countermeasures against existing physical cryptanalysis. However, very little attention has been paid to deal with the possible mutual relationship between different kinds of physical cryptanalysis when designing a specific countermeasure. In this paper, it is pointed out that enhanced implementations of the Rijndael cipher (AES) against timing cryptanalysis and simple power cryptanalysis (SPA) may unfortunately become more vulnerable to the differential power cryptanalysis (DPA). Technically speaking, based on Sommer’s work and experiments presented in CHES 2000, this new DPA on the above mentioned Rijndael implementations enables a much more significant observable peak within the differential power trace. This makes the DPA attack be more easier with fewer required power traces.

This paper describes a DFA attack on the AES key schedule. This fault model assumes that the attacker can induce a single byte fault on the round key. It efficiently finds the key of AES-128 with feasible computation and less than thirty pairs of correct and faulty ciphertexts. Several countermeasures are also proposed. This weakness can be resolved without modifying the structure of the AES algorithm and without decreasing the efficiency.

KASUMI is a block cipher which has been adopted as a standard of 3GPP. In this paper, we study the pseudorandomness of idealized KASUMI type permutations for adaptive adversaries. We show that the four round version is pseudorandom andthe six round version is super-pseudorandom.

In this paper, we give a theoretical analysis of η2 attack proposed by Knudsen and Meier on the RC6 block cipher. To this end, we propose the method of security evaluation against η2 attack precisely including key dependency by introducing a method “Transition Matrix Computing.” Previously, no theoretical security evaluation against η2 attack was known, it has been done by computer experiments. We should note that this is the first results that a theoretical evaluation against η2 attack is shown.

We propose a novel security type system for the π-calculus in which a fine-grained access control mechanism is guaranteed by static type checking and secure information flow can be characterized by a new form of non-interference property based on typed behavioral equivalence. In this paper, we present the syntax, subtyping rules, and typing rules of the type system, and explain how the secure data access can be controlled by typing. And then we elaborate a framework of typed level bisimulation to construct the secure information flow property named as non-interference at level. Moreover, some results are presented to indicate that our theory is an efficient enforceable model to support the specification and analysis of secure mobile systems.

Practical use of the Canetti and Krawczyk approach to development of proven secure key exchange protocols is explored. The suite of protocols that can be developed using existing building blocks is discussed. An additional building block is provided by proving a new protocol secure in the ideal model of the approach. In the application area of wireless protocols it is shown that the best existing protocols can be matched with versions carrying security proofs. We conclude that building a library of building blocks will allow protocols with proven security to become the norm rather than the exception.

The next generation mobile Internet is expected to develop towards “Always Best Connected (ABC)”, or “Any Time, Any Where, Any Service”, and provide completely open environments for interconnection with the external world through the IP-enabled structure. In addition to this, the support for new kinds of management such as service provisioning, customization, and personalization will lead to a more complicated network revolution. In the paper, we propose an authentication framework, which use PKI-based mutual authentication to establish trust relations between the communication entities and to guarantee minimized handover delay by extending the trust relations. The simulation results, in conjunction with the experiment conducted on a WLAN testbed, are presented that illustrate how the framework can best be applied to the next generation mobile environments.

We propose an efficient and robust Pay TV scheme for the case when there are a number of streams, as opposed to just one. In our model, the broadcast is divided into billing periods; during each billing period the entitlement of the users does not change. We achieve full flexibility with only a constant factor data redundancy. Our scheme has very little secure memory requirements and does not require the users’ secure keys to be changed once they have been written into the secure memory. There is also no upper limit on the number of subscribers. We extend this scheme to have the cracker identification property: If a collusion of less than t users crack their set-top terminals and produce a new decryption key, the exact set of crackers can be efficiently identified with high probability. This property is similar to but different from the traitor tracing schemes of Chor et al [5].

In order to protect network from the Denial of Service attacks which sends excessive traffic to a host, it is required for network components to throttle unauthorized traffics. The attacker must be identified through the cooperation of routers and must be isolated by the nearest router. It is the most important to identify and isolate the attacker since the nearest router can make ideal blocking of the DoS attacks. In this research, we will present a protocol which can identify the attacker of DoS by the request of victim in cooperation of routers on the attacking path between a victim and the attacker. The performance of our protocol will be verified by simulations and the experiments show that it takes considerably small time to identify the location of attacker.

We propose a distributed approach to detect distributed denial of service attacks by monitoring the increase of new IP addresses. Unlike previous proposals for bandwidth attack detection schemes which are based on monitoring the traffic volume, our scheme is very effective for highly distributed denial of service attacks. Our scheme exploits an inherent feature of DDoS attacks, which makes it hard for the attacker to counter this detection scheme by changing their attack signature. Our scheme uses a sequential nonparametric change point detection method to improve the detection accuracy without requiring a detailed model of normal and attack traffic. In a multi-agent scenario, we show that by sharing the distributed beliefs, we can improve the detection efficiency.

This paper presents a systematic solution to the problem of using ICMP tunneling for covert channel. ICMP is not multiplexed via port numbers and the data part of the ICMP packet provides considerable bandwidth for malicious covert channels. These factors make it an integral part of many malicious software like remote access and denial of service attack tools. These tools use ICMP to establish covert communication channels. In this paper a stateless model is proposed to prevent ICMP tunneling. A Linux kernel module was implemented to demonstrate the proposed stateless solution. The module enforces a fixed payload policy for ICMP packets and virtually eliminates ICMP tunneling which arises due to the data carrying capability of ICMP. The performance impact on end hosts and routers due to the stateless monitoring model is described.

A fair electronic cash system is a system that allows customers to make payments anonymously. Moreover, under certain circumstances, a trusted authority can revoke the anonymity of suspicious transactions. Various fair e-cash systems using group signature schemes have been proposed [4,15,16,18]. Unfortunately, they do not realize coin tracing [4,15,18] (the possibility to trace the coins withdrawn by a customer). In this paper, we describe several failures in the solution of [16] and we present a secure and efficient fair e-cash system based on a group signature scheme. Our system ensures traceability of double-spenders, supports coin tracing and provides coins that are unforgeable and anonymous under standard assumptions.

At present, network users have to manage one set of authentication credentials (usually a username/password pair) for every service with which they are registered. Single Sign-On (SSO) has been proposed as a solution to the usability, security and management implications of this situation. Under SSO, users authenticate themselves only once and are logged into the services they subsequently use without further manual interaction. Several architectures for SSO have been developed, each with different properties and underlying infrastructures. This paper presents a taxonomy of these approaches and puts some of the SSO schemes, services and products into that context. This enables decisions about the design and selection of future approaches to SSO to be made within a more structured context; it also reveals some important differences in the security properties that can be provided by various approaches.

The RMAC[6] is a variant of CBC-MAC, which resists birthday attacks and gives provably full security. The RMAC uses 2k-bit keys and the size of the RMAC is 2n, where n is the size of underlying block cipher. The TMAC[10] is the improved MAC scheme of XCBC[4] such that it requires (k +n)-bit keys while the XCBC requires (k +2n)-bit keys. In this paper, we introduce trivial key recovery attack on the RMAC with about 2n computations, which is more realistic than the attacks in [9]. Also we give a new attack on the TMAC using about 2n/2+1 texts, which can recover an (k + n)-bit key. However this attack can not be applied to the XCBC. Furthermore we analyzed the IACBC mode[8], which gives confidentiality and message integrity.

NTRU is an efficient public-key cryptosystem proposed by Hoffstein, Pipher, and Silverman. Assuming access to a decryption oracle, we show ways to recover the private key of NTRU systems that do not include a ciphertext validating procedure. The strongest of our methods will employ just a single call to the oracle, and in all cases, the number of calls needed will be small enough to be realistic.

Chinese remainder theorem has been widely employed to speedup the RSA computation. In this paper, one kind of permanent fault attack on RSA with CRT will be pointed out which exploits a permanent fault on the storage of either p or q. This proposed attack is generic and powerful which can be applicable to both the conventional RSA with CRT and Shamir’s fault attack immune design of RSA with CRT. Two popular and one recently proposed CRT recombination algorithms which are necessary for the above two mentioned RSA with CRT will be carefully examined in this paper for their immunity against the proposed parameter permanent fault attack.

There has been much recent research in designing symmetric ciphers with backdoors that have either public designs or black-box designs. Current Digital Rights Management needs have resurrected the use of hidden ciphers (which were traditionally suggested by the government as black-box designs) in the form of obfuscated “white-box” algorithms. A recent backdoor proposal is the Monkey cipher which is intended to have a secret design and that can be implemented using any deterministic trapdoor one-way function. Monkey leaks information about its user’s key to the designer. The primary drawback of Monkey is that it requires the designer (attacker) to obtain a sufficient number of ciphertexts all under the same symmetric key, such that each contains one known plaintext bit. In this paper a new design is proposed that eliminates the need for known plaintext entirely. Also, whereas Monkey reveals one plaintext bit of each ciphertext to the reverse-engineer (i.e., an entity that tries to learn the black-box device), our solution only leaks a bound on the message entropy to the reverse-engineer, while requiring that the designer obtain a sufficient number of ciphertexts that encrypt messages with a requisite level of redundancy. The information leakage method we use employs “data compression” as a basic tool for generating a hidden information channel. This highlights the need to only encrypt compressed strings when a block cipher with a secret design must be used.

Blind signature and proxy signature are very important technologies in secure e-commerce. Identity-based (simply ID-based) public key cryptosystem can be a good alternative for certificate-based public key setting, especially when efficient key management and moderate security are required. In this paper, we propose a new ID-based blind signature scheme and an ID-based partial delegation proxy signature scheme with warrant based on the bilinear pairings. Also we analyze their security and efficiency. We claim that our new blind signature scheme is more efficient than Zhang and Kim’s scheme [27] in Asiacrypt2002.

In some practical circumstances, the ability of a signer should be restricted. In group signature schemes, a group member may be allowed to generate signatures up to a certain number of times according to his/her position in the group. In proxy signature schemes, an original signer may want to allow a proxy signer to generate a certain number of signatures on behalf of the original signer. In the paper, we discuss signature schemes, called c-times signature schemes, that restrict the signing ability of a signer up to c times for pre-defined value c at set-up. We formally define the notion and the security model of c-times signature schemes. In fact, c-times signature schemes can be classified into two types according to restriction features: one with an explicit limitation, called a c-times signature scheme, and the other with an implicit limitation, called an implicit c-times signature scheme. We present two instances of implicit c-times signature schemes and then give proofs of the security. For one instance we suggest cS which is a composition of a signature scheme S based on the discrete logarithm and Feldman’s VSS. For the other we present cDSA based on DSA. Our basic approach can be applied to signature schemes such as HVZK based signature schemes.

Up to present, we have yet seen no multi-signature schemes based on RSA secure against active attacks proposed. We have examined the possibility of simulation of signatures in the MM scheme [7] in order to investigate whether that scheme has the security against active attacks. The MM scheme cannot be shown secure against active attacks. We have constructed the RSA-based multi-signature scheme in order to overcome the problem that the MM scheme has. The proposed scheme provides the security against adaptive chosen message insider attack targeting one signer, and can keep tighter reduction rate.

We propose a public-key cryptosystem which is derived from the Paillier cryptosystem. The scheme inherits the attractive homomorphic properties of Paillier encryption. In addition, we achieve two new properties: First, all users can use the same modulus when generating key pairs, this allows more efficient proofs of relations between different encryptions. Second, we can construct a threshold decryption protocol for our scheme that is length-flexible, i.e., it can handle efficiently messages of arbitrary length, even though the public key and the secret key shares held by decryption servers are of fixed size. We show how to apply this cryptosystem to build a self-tallying election scheme with perfect ballot secrecy, and to build a length-flexible mix-net which is universally verifiable, where the size of keys and ciphertexts do not depend on the number of mix servers, and is robust against a corrupt minority.

Secure distribution of digital goods is now a significantly important issue for protecting publishers’ copyrights. In this paper, we study a useful primitive for constructing a secure and efficient digital rights management system (DRM) where a server which encrypts digital content and one which issues the corresponding decryption key works independently, and existing schemes lack this property. We first argue the desired property necessary of an encryption scheme for constructing an efficient DRM, and formally define an encryption scheme as split encryption scheme containing such property. Also, we show that an efficient split encryption scheme can be constructed from any identity-based scheme. However, since currently there is no identity-based encryption scheme which is based on well-known computational assumption and/or provable security without the random oracle, by reasonably tuning the system parameter, we show another construction of split encryption which is secure against chosen ciphertext attacks in the standard model assuming that the decision Diffie-Hellman problem is hard to solve.

We deal with the revocation scheme such that the revoked receivers should not be able to obtain available information when a center broadcasts data to all receivers. We propose a new revocation scheme with minimal message length for stateless receivers, where the receivers do not update their state from session to session. The proposed scheme requires storage of ₁2 log2n−₁2 log n+2 keys at the receiver and a message length of at most r+1. The main contribution of the proposed scheme is to reduce the message length. Namely, the proposed scheme minimizes the number of subsets which the non-revoked receivers are partitioned.

A parallel authentication and public-key encryption is introduced and exemplified on joint encryption and signing which compares favorably with sequential Encrypt-then-Sign (ɛtS) or Sign-then-Encrypt (Stɛ) schemes as far as both efficiency and security are concerned. A security model for signcryption, and thus joint encryption and signing, has been recently defined which considers possible attacks and security goals. Such a scheme is considered secure if the encryption part guarantees indistinguishability and the signature part prevents existential forgeries, for outsider but also insider adversaries. We propose two schemes of parallel signcryption, which are efficient alternative to Commit-then-Sign-and- Encrypt (Ct&G3&S). They are both provably secure in the random oracle model. The first one, called generic parallel encrypt and sign, is secure if the encryption scheme is semantically secure against chosen-ciphertext attacks and the signature scheme prevents existential forgeries against random-message attacks. The second scheme, called optimal parallel encrypt. and sign, applies random oracles similar to the OAEP technique in order to achieve security using encryption and signature components with very weak security requirements — encryption is expected to be one-way under chosen-plaintext attacks while signature needs to be secure against universal forgeries under random-plaintext attack, that is actually the case for both the plain-RSA encryption and signature under the usual RSA assumption. Both proposals are generic in the sense that any suitable encryption and signature schemes (i.e. which simply achieve required security) can be used. Furthermore they allow both parallel encryption and signing, as well as parallel decryption and verification. Properties of parallel encrypt and sign schemes are considered and a new security standard for parallel signcryption is proposed.

This paper examines the access control requirements of distributed health care information networks. Since the electronic sharing of an individual’s personal health information requires their informed consent, health care information networks need an access control framework that can capture and enforce individual access policies tailored to the specific circumstances of each consumer. Role Based Access Control (RBAC) is examined as a candidate access control framework. While it is well suited to the task in many regards, we identify a number of shortcomings, particularly in the range of access policy expression types that it can support. For efficiency and comprehensibility, access policies that grant access to a broad range of entities whilst explicitly denying it to subgroups of those entities need to be supported in health information networks. We argue that RBAC does not support policies of this type with sufficient flexibility and propose a novel adaptation of RBAC principles to address this shortcoming. We also describe a prototype distributed medical information system that embodies the improved RBAC model.

Cellular automata provide discrete deterministic mathematical models for physical, biological and computational systems. Despite their simple construction, cellular automata are shown to be capable of complicated behaviour, and to generate complex and random patterns. There have been constant efforts to exploit cellular automata for cryptography since the very beginning of the research on cellular automata. Unfortunately, most of the previous cryptosystems based on cellular automata are either insecure or inefficient. [8] is the latest effort in cellular automata cryptosystems (CACs) design, where the affine cellular automata are combined with non-affine transformations. It is claimed that the weakness in some of the previous CACs due to affine property is removed. In this paper we show that the new CAC is still insecure. It can be broken by a chosen-plaintext attack. The attack is very efficient, requiring only hundreds of chosen plaintexts and a small computation amount. We also consider the possibility of modifying the new CAC. Our results show, however, that it is not easy to secure the scheme by minor modifications. The cryptanalysis in this paper enforces the opinion once more that the security must be very carefully analyzed in designing the cryptosystems based on some mathematical systems. We should not blindly trust the pseudo randomness brought by the available mathematical systems. The designing techniques developed by cryptographic community are always optimal.

In 1998, Cramer and Shoup proposed the first practical and provable cryptosystem against adaptive chosen ciphertext attack under the standard assumption in the standard model, that is, decisional Diffie-Hellman assumption. Recently, Lucks extended the Cramer-Shoup cryptosystem to a group of quadratic residues modulo a composite number and showed that the scheme is provably secure in the standard model. In this paper, we extend Lucks’ key encapsulation scheme to a third order linear feedback shift register and is based on a new assunmption which is called shift register based decisional Diffie-Hellman assumptions (SR-DDH). The proposed scheme is provably secure against adaptive chosen ciphertext attack based on the hardness of shift register based decisional Diffie-Hellman assumption in the standard model and not in random oracle model. Furthermore, the size of public key and ciphertext are shorter than Cramer-Shoup cryptosystem and the computational complexity is also more efficient than Cramer-Shoup cryptosystem and Lucks scheme.

A system related to the shrinking generator that is made up of two feedback shift registers in which one (FSR $$ \mathbb{A} $$)) controls the clocking of the other (FSR $$ \mathbb{B} $$) is introduced. It is established that if FSR $$ \mathbb{A} $$) generates an m-sequence of period (2m − 1) and FSR $$ \mathbb{B} $$ generates a de Bruijn sequence of period 2η, then the output sequence of the system has period P = 2m+ν−1, linear complexity L bounded from below by 2m+η−2, good statistical properties, and it is secure against correlation attacks. All these properties make it a suitable crypto-generator for stream cipher applications.

A password-based protocol for authenticated key exchange must provide security against attacks using low entropy of a memorable password. We propose a new password-based protocol for authenticated key exchange, EPA (Efficient Password-based protocol for Authenticated key exchange), which has smaller computational and communicational workloads than previously proposed protocols with the same security requirements. EPA is an asymmetric model in which each client has a password and the server has a password file. While the server’s password file is compromised, the client’s password is not directly exposed. However, if the adversary mounts an additional dictionary attack, he can obtain the client’s password. By using a modified amplified password file, we construct EPA+, which is secure against dictionary attack and server impersonation even if the server’s password file is compromised.

In a dynamic group key distribution scheme, members of a group themselves generate private common keys with the help of a group controller in an initialization phase. The system must enable the revocation and the addition of members to the group in the successive periods of time. If the addition of new members can also be performed by the existing members themselves, then the scheme is said to have decentralized user join.In this work we construct a general family of dynamic group key distribution schemes with decentralized user join by using linear secret sharing schemes as a tool. This allows to obtain new schemes with more flexible characteristics than the previous threshold-based constructions.

This paper presents a robust software token that was developed to protect user’s digital identity by simple software-only techniques. This work is closely related to Hoover and Kausik’s software smart cards, and MacKenzie and Reiter’s networked cryptographic devices, in the fact that user’s private key is protected by postulating a remote server rather than tamper-resistance. The robust software token is aimed to be richer than the related schemes in terms of security, efficiency and flexibility. A two-party RSA scheme was carefully applied for the purpose, in a way of considering practical construction rather than theoretical framework.

In this paper we propose a key-exchange system and a public-key encryption scheme based on the class semigroups of imaginary quadratic non-maximal orders, the former is analogous to the Diffie-Hellman’s key-exchange system and the latter is similar to the ElGamal’s encryption scheme, whose security is based on the difficulty of the discrete logarithm problem of that class semigroup.

We explore three applications of geometric sequences in constructing cryptographic Boolean functions. First, we construct 1-resilient functions of n Boolean variables with nonlinearity 2n−1−2(n−1)/2, n odd. The Hadamard transform of these functions is 3-valued, which limits the efficiency of certain stream cipher attacks. From the case for n odd, we construct highly nonlinear 1-resilient functions which disprove a conjecture of Pasalic and Johansson for n even. Our constructions do not have a potential weakness shared by resilient functions which are formed from concatenation of linear functions. Second, we give a new construction for balanced Boolean functions with high nonlinearity, exceeding 2n−1−2(n−1)/2, which is not based on the direct sum construction. Moreover, these functions have high algebraic degree and large linear span. Third, we construct balanced vectorial Boolean functions with nonlinearity 2n−1−2(n−1)/2 and low maximum correlation. They can be used as nonlinear combiners for stream cipher systems with high throughput.

In this paper, we study variants of the parallel hash function construction of Damgård. We first show an improvement such that the number of processors is almost a half if |M| = (2s + 1)n for some s, where M is the message to be hashed. We next show that there exists a variant of our parallel hash construction such that it is secure even if the underlying compression function is not necessarily collision-free nor one-way. The cost is that some constant times more processors are required.

This paper shows an improvement of square hash function family proposed by Etzel et al. [5]. In the new variants, the size of keys is much shorter while the collision probability is slightly larger. Most of the main techniques used to optimize the original square hash functions work on our variants as well. The proposed algorithms are applicable to fast and secure message authentication.