International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Papers from EPRINT 2004

Year
Venue
Title
2004
EPRINT
A comb method to render ECC resistant against Side Channel Attacks
Side Channel Attacks may exploit leakage information to break cryptosystems on smard card devices. In this paper we present a new SCA-resistant elliptic curve scalar multiplication algorithm, based on the Lim and Lee technique. The proposed algorithm builds a sequence of bit-strings representing the scalar $k$, characterized by the fact that all bit-strings are different from zero; this property will ensure a uniform computation behaviour for the algorithm, and thus will make it secure against SPA (Simple Power Analysis) attacks. The use of a recently introduced randomization technique achieves the security of the proposed scheme against other SCA attacks. Furthermore, the proposed countermeasures do not penalize the computation time
2004
EPRINT
A New Remote User Authentication Scheme Using Smart Cards with Forward Secrecy
Hwang and Li proposed the first remote user authentication scheme using smart cards to solve the problems of Lamport scheme. Unfortunately, Hwang and Li?s scheme has some security weaknesses. First, Chan- Chang, Shen- Lin- Hwang and then Chang-Hwang pointed out some attacks on Hwang ? Li?s scheme. This paper presents a new remote user authentication scheme with forward secrecy, which provides forward secrecy to the long term secret key of the authentication server. This scheme is also secure against Chan ? Cheng and all the extended attacks.
2004
EPRINT
A Bilinear Spontaneous Anonymous Threshold Signature for Ad Hoc Groups
We present an adaptive chosen-plaintext cryptanalysis of Boneh, et al.'s bilinear spontaneous anonymous ad hoc group signature. Then we present a patch, and an extension to a threshold version complete with a security proof in the random oracle model (ROM).
2004
EPRINT
A Biometric Identity Based Signature Scheme
We describe an identity based signature scheme that uses biometric information to construct the public key. Such a scheme would be beneficial in a legal dispute over whether a contract had been signed or not by a user. A biometric reading provided by the alleged signer would be enough to verify the signature. We make use of Fuzzy extractors to generate a key string from a biometric measurement. We use this biometric based key string and an elliptic curve point embedding technique to create the public key and corresponding private key. We then make use of a pairing based signature scheme to perform signing and verification with these keys. We describe a possible attack on this system and suggest ways to combat it. Finally we describe how such a biometric signature scheme can be developed by reusing existing components in our Java Identity Based Encryption implementation. The design allows traditional as well as biometric identity based signatures.
2004
EPRINT
A Characterization of Authenticated-Encryption as a Form of Chosen-Ciphertext Security
In this note we introduce a variation of the standard definition of chosen-ciphertext security, which we call IND-CCA3, and prove that IND-CCA3 is equivalent to authenticated-encryption.
2004
EPRINT
A comparison of MNT curves and supersingular curves
We compare both the security and performance issues related to the choice of MNT curves against supersingular curves in characteristic three, for pairing based systems. We pay particular attention to equating the relevant security levels and comparing not only computational performance and bandwidth performance. The paper focuses on the BLS signature scheme and the Boneh--Franklin encryption scheme, but a similar analysis can be applied to many other pairing based schemes.
2004
EPRINT
A Comparison of Point Counting methods for Hyperelliptic Curves over Prime Fields and Fields of Characteristic 2
Computing the order of the Jacobian of a hyperelliptic curve remains a hard problem. It is usually essential to calculate the order of the Jacobian to prevent certain sub-exponential attacks on the cryptosystem. This paper reports on the viability of implementations of various point-counting techniques. We also report on the scalability of the algorithms as the fields grow larger.
2004
EPRINT
A Complete Divisor Class Halving Algorithm for Hyperelliptic Curve Cryptosystems of Genus Two
We deal with a divisor class halving algorithm on hyperelliptic curve cryptosystems (HECC), which can be used for scalar multiplication, instead of a doubling algorithm. It is not obvious how to construct a halving algorithm, due to the complicated addition formula of hyperelliptic curves. In this paper, we propose the first halving algorithm used for HECC of genus 2, which is as efficient as the previously known doubling algorithm. From the explicit formula of the doubling algorithm, we can generate some equations whose common solutions contain the halved value. From these equations we derive four specific equations and show an algorithm that selects the proper halved value using two trace computations in the worst case. If a base point is fixed, we can reduce these extra field operations by using a pre-computed table which shows the correct halving divisor class ?the improvement over the previously known fastest doubling algorithm is up to about 10%. This halving algorithm is applicable to DSA and DH scheme based on HECC. Finally, we present the divisor class halving algorithms for not only the most frequent case but also other exceptional cases.
2004
EPRINT
A double large prime variation for small genus hyperelliptic index calculus
In this article, we examine how the index calculus approach for computing discrete logarithms in small genus hyperelliptic curves can be improved by introducing a double large prime variation. Two algorithms are presented. The first algorithm is a rather natural adaptation of the double large prime variation to the intended context. On heuristic and experimental grounds, it seems to perform quite well but lacks a complete and precise analysis. Our second algorithm is a considerably simplified variant, which can be analyzed easily. The resulting complexity improves on the fastest known algorithms. Computer experiments show that for hyperelliptic curves of genus three, our first algorithm surpasses Pollard's Rho method even for rather small field sizes.
2004
EPRINT
A DPA Attack on the Improved Ha-Moon Algorithm
The algorithm proposed by Ha and Moon [HM02] is a countermeasure against power analysis. The Ha-Moon algorithm has two drawbacks in that it requires an inversion and has a right-to-left approach. Recently, Yen, Chen, Moon and Ha improved the algorithm by removing these drawbacks [YCMH04]. Their new algorithm is inversion-free, has a left-to-right approach and employs a window method. They insisted that their algorithm leads to a more secure countermeasure in computing modular exponentiation against side-channel attacks. This algorithm, however, still has a similar weakness observed in [FMPV04,SPL04]. This paper shows that the improved Ha-Moon algorithm is vulnerable to differential power analysis even if we employ their method in selecting $s_i$.
2004
EPRINT
A Dynamic and Differential CMOS Logic Style to Resist Power and Timing Attacks on Security IC?s
We present a dynamic and differential CMOS logic style, which has a signal independent switching behavior. It is shown that during each clock cycle, power consumption and all circuit characteristics, such as leakage current, instantaneous current and input-output delay are identical and independent of the logic value and the sequence of the input data. Implementing the encryption module in this logic will protect it against any Side Channel Attack that takes advantage of power, timing and leakage information. We have built a set of logic gates and a flip-flop needed for cryptographic functions and implemented a larger module, for which area, total power consumption and variation on the power consumption have been compared with implementations in Static Complementary CMOS logic, genuine Dynamic and Differential Logic and Current Mode Logic.
2004
EPRINT
A General Cryptanalysis of Permutation-Only Multimedia Encryption Algorithms
In recent years secret permutations have been widely used for protecting different types of multimedia data, including speech files, digital images and videos. Based on a normalized encryption/decryption model, this paper performs a quantitative cryptanalysis on the security of permutation-only image ciphers working in the spatial domain, taking a recently-proposed permutation-only image cipher called HCIE (hierarchical chaotic image encryption) as a typical example. When the plain-image is of size $M\times N$ and with $L$ different levels of pixel values, the following quantitative cryptanalytic findings have been concluded: 1) all permutation-only image ciphers are insecure against known/chosen-plaintext attacks in the sense that only $O\left(\log_L(MN)\right)$ known/chosen plain-images are enough to break the secret permutation mapping; 2) the computational complexity of the known/chosen-plaintext attack is only $O(n\cdot(MN)^2)$, where $n$ is the number of known/chosen plain-images involved. Based on these results, it is found that hierarchical permutation-only image ciphers such as HCIE are less secure than normal (i.e., non-hierarchical) permutation-only image ciphers. Experiments are shown to verify the feasibility of the known/chosen-plaintext attacks. The cryptanalysis result is then generalized to permutation-only image ciphers working in the frequency domain, as well as video ciphers and speech ciphers. Finally, it is suggested that secret permutations have to be combined with other encryption techniques to design highly secure multimedia encryption systems. To the best of our knowledge, for the first time this paper provides a quantitative analysis of such a security principle on the design of multimedia encryption algorithms, from both theoretical and experimental points of view.
2004
EPRINT
A Generalization of PGV-Hash Functions and Security Analysis in Black-Box Model
In~\cite{B02} it was proved that 20 out of 64 PGV-hash functions~\cite{P94} based on block cipher are collision resistant and one-way-secure in black-box model of the underlying block cipher. Here, we generalize the definition of PGV-hash function into a hash family and we will prove that besides the previous 20 hash functions we have 22 more collision resistant and one-way secure hash families. As all these 42 families are keyed hash family, these become target collision resistant also. All these 42 hash families have tight upper and lower bounds on (target) collision resistant and one-way-ness.
2004
EPRINT
A New Designated Confirmer Signature Variant with Intended Recipient
Previous designated confirmer signature schemes were less efficient because complex zero-knowledge proof employed in confirmation and disavowal protocol. In this paper, we propose a new efficient signature scheme which is recipient-specific and confirmer-specific. The new scheme is transformed from ID-based chameleon signature and inherits its advantage in simplicity and efficiency. The scheme's security relies on the underlying secure chameleon signature and public key encryption scheme. We also considers the case of confirmer as an adversary in security proof.
2004
EPRINT
A New Forward Secure Signature Scheme
In this paper, we present two forward secure signature schemes based on gap Diffie-Hellman groups and prove these schemes to be secure in the sense of slightly stronger security notion than that by Bellare and Miner in the random oracle model. Both schemes use the same key update strategy as the encryption scheme presented by Canetti, Halevi and Katz. Hence, our schemes outperform the previous tree-based forward secure signature scheme by Bellare and Miner in the key generation and key update time, which are only constant in the number of time periods. Specifically, we describe a straightforward scheme following from the encryption scheme, and then improve its efficiency for signature verification algorithm which needs only 3 pairing computations independent of the total time periods.
2004
EPRINT
A New ID-based Signature with Batch Verification
An identity (ID)-based signature scheme allows any pair of users to communicate securely and to verify each other's signatures without exchanging public key certificates. We have several ID-based signatures based on the discrete logarithm problem. While they have an advantage that the system secret can be shared by several parties through threshold schemes, they have a critical disadvantage in efficiency. To enhance the efficiency of verification, we propose a new ID-based signature scheme that allows batch verification of multiple signatures. The verification cost of the proposed signature scheme for $k$ signatures is almost constant with minimal security loss and when a new signature by a different signer is added to the batch verification, the additional cost is almost a half of that of a single signature. We prove that the proposed signature scheme is secure against existential forgery under adaptively chosen message and ID attack in the random oracle model and show why other ID-based signature schemes are hard to achieve these properties.
2004
EPRINT
A New Minimal Average Weight Representation for Left-to-Right Point Multiplication Methods
This paper introduces a new radix-2 representation with the same average weight as the width-$w$ nonadjacent form ($w$-NAF). In both $w$-NAF and the proposed representations, each nonzero digit is an odd integer with absolute value less than $M$. However, for $w$-NAF, $M$ is of the form $2^{w-1}$, while for the proposed representation it can be any positive integer. Therefore, using the proposed integer representation we can use the available memory efficiently, which is attractive for devices with limited memory. Another advantage of the proposed representation over $w$-NAF is that it can be obtained by scanning the bits from left-to-right. This property is also useful for memory-constrained devices because it can reduce both time and space complexityof fast point multiplication techniques.
2004
EPRINT
A new security proof for Damg?rd's ElGamal
We provide a new security proof for a variant of ElGamal proposed by Damg{\aa}rd, showing that it is secure against non-adaptive chosen ciphertext. Unlike previous security proofs for this cryptosystem, which rely on somewhat problematic assumptions, our computational problem is similar to accepted problems such the Gap and Decision Diffie-Hellman problems.
2004
EPRINT
A New Stream Cipher HC-256
HC-256 is a software-efficient stream cipher. It generates keystream from a 256-bit secret key and a 256-bit initialization vector. The encryption speed of the C implementation of HC-256 is about 1.9 bits per clock cycle (4.2 cycle/byte) on the Intel Pentium 4 processor. A variant of HC-256 is also introduced in this paper.
2004
EPRINT
A New Two-Party Identity-Based Authenticated Key Agreement
We present a new two-party identity-based key agreement that is more efficient than previously proposed schemes. It is inspired on a new identity-based key pair derivation algorithm first proposed by Sakai and Kasahara. We show how this key agreement can be used in either escrowed or escrowless mode. We also describe conditions under which users of different Key Generation Centres can agree on a shared secret key. We give an overview of existing two-party key agreement protocols, and compare our new scheme with existing ones in terms of computational cost and storage requirements.
2004
EPRINT
A Note on An Encryption Scheme of Kurosawa and Desmedt
Recently Kurosawa and Desmedt presented a new hybrid encryption scheme which is secure against adaptive chosen-ciphertext attack. Their scheme is a modification of the Cramer-Shoup encryption scheme. Its major advantage with respect to Cramer-Shoup is that it saves the computation of one exponentiation and produces shorter ciphertexts. However, the proof presented by Kurosawa and Desmedt relies on the use of information-theoretic key derivation and message authentication functions. In this note we present a different proof of security which shows that the Kurosawa-Desmedt scheme can be instantiated with any computationally secure key derivation and message authentication functions, thus extending the applicability of their paradigm, and improving its efficiency.
2004
EPRINT
A note on efficient computation of cube roots in characteristic 3
The cost of the folklore algorithm for computing cube roots in $\F_{3^m}$ in standard polynomial basis is less that one multiplication, but still $O(m^2)$. Here we show that, if $\F_{3^m}$ is represented in trinomial basis as $\F_3[x]/(x^m + ax^k + b)$ with $a, b = \pm 1$, the actual cost of computing cube roots in $\F_{3^m}$ is only $O(m)$.
2004
EPRINT
A note on L\'opez-Dahab coordinates
L\'opez-Dahab coordinates are usually the system of choice for implementations of elliptic curves over binary fields. We give new formulas for doubling which need one squaring less and one more addition. This leads to a speed-up for binary fields in polynomial basis representation.
2004
EPRINT
A NOVEL ALGORITHM ENUMERATING BENT FUNCTIONS
By the relationship between the Walsh spectra at partial points and the Walsh spectra of its sub-functions, by the action of general linear group on the set of Boolean functions, and by the Reed-Muller transform, a novel method is developed, which can theoretically construct all bent functions. With this method, we enumerate all bent functions in 6 variables; in 8-variable case, our method is more efficient than the method presented by Clark though we still can not enumerate all bent functions; enumeration of all homogeneous bent functions of degree 3 in eight variables can be done in one minute by a P4 1.7G HZ computer; construction of homogenous bent function of degree 3 in 10 variables is efficient too; the nonexistence of homogeneous bent functions in 10 variables of degree 4 is proved
2004
EPRINT
A Proof of Yao's Protocol for Secure Two-Party Computation
In the mid 1980's, Yao presented a constant-round protocol for securely computing any two-party functionality in the presence of semi-honest adversaries (FOCS 1986). In this paper, we provide a complete description of Yao's protocol, along with a rigorous proof of security. Despite the importance of Yao's protocol to the field of secure computation, to the best of our knowledge, this is the first time that a proof of security has been published.
2004
EPRINT
A Provable Secure Scheme for Partially Blind Signatures
This paper proposes a new scheme for partially blind signature based on the difficulty in solving the discrete logarithm problem. Under the assumption of the generic model, random oracle model, and intractable ROS-problem, this paper formally proves that the proposed scheme is secure against one-more signature forgery under the adaptively parallel attack. Previous schemes using two signing equations for plain information and commitment. The proposed scheme uses two secret keys to combine these two signing equations, thus it is more efficient than previous schemes in both communicational and computational cost.
2004
EPRINT
A Provably Secure Nyberg-Rueppel Signature Variant with Applications
This paper analyzes the modified Nyberg-Rueppel signature scheme (mNR), proving it secure in the Generic Group Model (GM). We also show that the security of the mNR signature is equivalent (in the standard model) to that of a twin signature, while achieving computational and bandwidth improvements. As a provably secure signature scheme, mNR is very efficient. We demonstrate its practical relevance by providing an application to the construction of a provably secure, self-certified, identity-based scheme (SCID). SCID schemes combine some of the best features of both PKI-based schemes (functionally trusted authorities, public keys revocable without the need to change identifier strings) and ID-based ones (lower bandwidth requirements). The new SCID scheme matches the performance achieved by the most efficient ones based on the discrete logarithm, while requiring only standard security assumptions in the Generic Group Model.
2004
EPRINT
A Provably Secure Scheme for Restrictive Partially Blind Signatures
A secure scheme of restrictive partially blind signature was presented. The proposed scheme has several advantages over the previous scheme: 1. The scheme is provable secure against the one-more signature forgery under the adaptively parallel attack. 2. The issued signatures can be of polynomial number whereas the previous work allows only logarithmic number. 3. The scheme is more efficient than previous scheme in both communicational and computational complexities.
2004
EPRINT
A Secure and Efficient Key Exchange Protocol for Mobile Communications
This paper proposes a key exchange protocol with mutual authentication, which requires only 0.1 modular multiplications for online computations. This online computation is ten times faster than that of conventional protocols. The message size of the proposed protocol is about half (50%~66%) that of the previous protocols. In addition to its efficiency in online computation and bandwidth, the paper provides a formal proof to guarantee the security of the proposed protocol. Possessing of both secure and efficient properties makes the proposed protocol suitable for the low power mobile communications.
2004
EPRINT
A Small-Scale Voting Protocol Hiding Vote-Counts of All Candidates
In this paper, we focus on the design of the winner-determination procedure of an electronic voting protocol used at critical elections, e.g. at the meeting of the board of a company for critical business decisions or a parliamentary committee for legislation. The number of participating voters is limited to several hundreds but the voting should satisfy a new privacy requirement that the accumulated vote-counts of all candidates should be kept as secret as possible. This additional requirement is significant only for small/medium-scale elections. Traditional electronic voting frameworks simply take the announcement of vote-counts for granted and hope that each individual??s actual vote is hidden in the accumulated vote-counts. Therefore, it is not easy to modify an existing scheme to approach this new goal. In the proposed protocol, the homomorphic ElGamal cryptosystem is used. An electronic bulletin board holds public announced values. A ballot consists of separate encrypted ??yes??/??no?? vote for each candidate such that the accumulated vote-counts can be calculated from the ciphertexts without any decryption. The correctness of each ballot is guaranteed through ZKPs. The accumulated vote-count ciphertexts are then converted to encrypted unary representation through a mix-and-match sub-protocol such that the vote-counts can be concealed in the winner-determination stage. This protocol is suited for both equal-voting and weighted-voting schemes. Also, the type of voter??s selection can be single choice, multiple choices, ranking choice, or the allocative choice.
2004
EPRINT
A Synchronous Model for Multi-Party Computation and the Incompleteness of Oblivious Transfer
This work develops a composable notion of security in a synchronous communication network to analyze cryptographic primitives and protocols in a reliable network with guaranteed delivery. In such a synchronous model the abort of protocols must be handled explicitly. It is shown that a version of *global bit commitment* which allows to identify parties that did not give proper input cannot be securely realized with the primitives *oblivious transfer* and *broadcast*. This proves that the primitives oblivious transfer and broadcast are not complete in our synchronous model of security. In the synchronous model presented ideal functionalities as well as parties can be equipped with a ``shell'' which can delay communication until the adversary allows delivery or the number of rounds since the shell received the message exceeds a specified threshold. This additionally allows asynchronous specification of ideal functionalities and allows to model a network where messages are not necessarily delivered in the right order. If these latency times are chosen to be infinite the network is no more reliable and becomes completely asynchronous. It is shown that secure protocols in the setting of [Canetti01] or [CLOS02] can be transformed to secure realizations in the new model if latency times are chosen to be infinite.
2004
EPRINT
A Technical Comparison of IPSec and SSL
IPSec (IP Security) and SSL (Secure Socket Layer) have been the most robust and most potential tools available for securing communications over the Internet. Both IPSec and SSL have advantages and shortcomings. Yet no paper has been found comparing the two protocols in terms of characteristic and functionality. Our objective is to present an analysis of security and performance properties for IPSec and SSL.
2004
EPRINT
A Verifiable Random Function With Short Proofs and Keys
We give a simple and efficient construction of a verifiable random function (VRF) on bilinear groups. Our construction is direct. In contrast to prior VRF constructions [MRV99, Lys02], it avoids using an inefficient Goldreich-Levin transformation, thereby saving several factors in security. Our proofs of security are based on a decisional bilinear Diffie-Hellman inversion assumption, which seems reasonable given current state of knowledge. For small message spaces, our VRF's proofs and keys have constant size. By utilizing a collision-resistant hash function, our VRF can also be used with arbitrary message spaces. We show that our scheme can be instantiated with an elliptic group of very reasonable size. Furthermore, it can be made distributed and proactive.
2004
EPRINT
A Weakness in Jung-Paeng-Kim's ID-based Conference Key Distribution Scheme
Very recently, Jung, Paeng and Kim [IEEE Communications Letters, Vol 8, No 7, pp 446--448, July 2004] have demonstrated the insecurity of Xu and Tilborg's ID-based conference key distribution scheme, and in addition, have revised the scheme to fix the security flaws discovered by them. However, in this paper, we show that Jung-Paeng-Kim's revised scheme is still insecure since it is vulnerable to an active attack of colluding adversaries. We also show that our attack can be easily thwarted by a simple patch.
2004
EPRINT
A weakness in Sun-Chen-Hwang's three-party key agreement protocols using passwords
Recently, Sun, Chen and Hwang [J. Syst. Software, 75 (2005), 63-68] have proposed two new three-party protocols, one for password-based authenticated key agreement and one for verifier-based authenticated key agreement. In this paper, we show that both of Sun-Chen-Hwang's protocols are insecure against an active adversary who can intercept messages, start multiple sessions of a protocol, or otherwise control the communication in the network. Also, we present a simple solution to the security problem with the protocols.
2004
EPRINT
A Weil Descent Attack against Elliptic Curve Cryptosystems over Quartic Extension Fields
This paper shows that many of elliptic curve cryptosystems over quartic extension fields of odd characteristics are reduced to genus two hyperelliptic curve cryptosystems over quadratic extension fields. Moreover, it shows that almost all of the genus two hyperelliptic curve cryptosystems over quadratic extension fields of odd characteristics come under Weil descent attack. This means that many of elliptic curve cryptosystems over quartic extension fields of odd characteristics can be attacked by Weil descent uniformly.
2004
EPRINT
Adaptively Secure Feldman VSS and Applications to Universally-Composable Threshold Cryptography
We propose the first distributed discrete-log key generation (DLKG) protocol from scratch which is adaptively-secure in the non-erasure model, and at the same time completely avoids the use of interactive zero-knowledge proofs. As a consequence, the protocol can be proven secure in a universally-composable (UC) like framework which prohibits rewinding. We prove the security in what we call the single-inconsistent-player (SIP) UC model, which guarantees arbitrary composition as long as all protocols are executed by the same players. As applications, we propose a fully UC threshold Schnorr signature scheme, a fully UC threshold DSS signature scheme, and a SIP UC threshold Cramer-Shoup cryptosystem. Our results are based on a new adaptively-secure Feldman VSS scheme. Although adaptive security was already addressed by Feldman in the original paper, the scheme requires secure communication, secure erasure, and either a linear number of rounds or digital signatures to resolve disputes. Our scheme overcomes all of these shortcomings, but on the other hand requires some restriction on the corruption behavior of the adversary, which however disappears in some applications including our new DLKG protocol. We also propose several new adaptively-secure protocols, which may find other applications, like a distributed trapdoor-key generation protocol for Pedersen's commitment scheme, an adaptively-secure Pedersen VSS scheme (as a {\em committed} VSS), or distributed-verifier proofs for proving relations among commitments or even any NP relations in general.
2004
EPRINT
Adaptively-Secure, Non-Interactive Public-Key Encryption
Adaptively-secure encryption schemes ensure secrecy even in the presence of an adversary who can corrupt parties in an adaptive manner based on public keys, ciphertexts, and secret data of already-corrupted parties. Ideally, an adaptively-secure encryption scheme should, like standard public-key encryption, allow arbitrarily-many parties to use a single encryption key to securely encrypt arbitrarily-many messages to a given receiver who maintains only a single short decryption key. However, it is known that these requirements are impossible to achieve: no non-interactive encryption scheme that supports encryption of an unbounded number of messages and uses a single, unchanging decryption key can be adaptively secure. Impossibility holds even if secure data erasure is possible. We show that this limitation can be overcome by updating the decryption key over time and making some mild assumptions about the frequency of communication between parties. Using this approach, we construct adaptively-secure, completely non-interactive encryption schemes supporting secure encryption of arbitrarily-many messages from arbitrarily-many senders. Our schemes additionally provide forward security and security against chosen-ciphertext attacks.
2004
EPRINT
Addendum to ``On the Generalized Linear Equivalence of Functions over Finite Fields''
In this paper we discuss the example of APN permutation introduced in the paper ``On the Generalized Linear Equivalence of Functions over Finite Fields'', presented at Asiacrypt 2004. We show that the permutation given there is indeed classically linearly equivalent to a power monomial. More in general, we show that no new class of APN functions can be discovered starting from permutation polynomials of the type used in the paper, and applied on the APN monomial $x^3$.
2004
EPRINT
Almost Ideal Contrast Visual Cryptography with Reversing
A drawback of visual cryptography schemes (VCS) is much loss of contrast in the reconstructed image. This paper shows a new paradigm of VCS in which the original image is almost perfectly reconstructed. A very simple non-cryptographic operation is assumed, reversing black and white, which many copy machines have these days. We first show a $(k,n)$-VCS with {\it reversing} such that white pixels are almost perfectly reconstructed in addition to the perfect reconstruction of black pixels. The proposed scheme is fully compatible with traditional VCS in the following sense: Even if we do not have a copy machine as described above, we can reconstruct the secret image $I$ exactly in the same way as in the underlying VCS. In other words, we use a copy machine as a hedge to obtain better contrast. We next show how to convert a perfect {\it black} $(k,n)$-VCS (with reversing) into a perfect {\it white} $(k,n)$-VCS with reversing. Thirdly, we show a perfect black VCS for any monotone access structure. Finally, we show applications of our idea to colored VCS and grey level VCS, respectively.
2004
EPRINT
An Access Control Scheme for Partially Ordered Set Hierarchy with Provable Security
In a hierarchical structure, an entity has access to another if and only if the former is a superior of the later. The access control scheme for a hierarchy represented by a partially ordered set (poset) has been researched intensively in the past years. In this paper, we propose a new scheme that achieves the best performance of previous schemes and is provably secure under a comprehensive security model.
2004
EPRINT
An AGM-type elliptic curve point counting algorithm in characteristic three
Given an ordinary elliptic curve on Hesse form over a finite field of characteristic three, we give a sequence of elliptic curves which leads to an effective construction of the canonical lift, and obtain an algorithm for computing the number of points. Our methods are based on the study of an explicitly and naturally given $3$-isogeny between elliptic curves on Hesse form.
2004
EPRINT
An Authenticated Certificateless Public Key Encryption Scheme
In 2003, Al-Riyami and Paterson \cite{AP} proposed the certificateless public key cryptography(CL-PKC) which is intermediate between traditional certificated PKC and identity-based PKC. In this paper, we propose an authenticated certificateless public key encryption scheme. Our result improves their public key encryption scheme in efficiency and security. The security of the protocol is based on the hardness of two problems; the computational Diffie-Hellman problem(CDHP) and the bilinear Diffie-Hellman problem(BDHP). We also give a formal security model for both confidentiality and unforgeability, and then show that our scheme is provably secure in the random oracle model.
2004
EPRINT
An e-Voting Scheme with Improved Resistance to Bribe and Coercion
Bribe and coercion are common in conventional voting systems and usually will lead to a biased result that imparts the desired democracy. However, these problems become more difficult to solve when using e-voting schemes. Up to now, many e-voting schemes have been proposed to provide receipt-freeness and uncoercibility to solve these problems. Unfortunately, none is both secure and practical enough. In this paper, we describe an e-voting scheme that can solve or at least lessen the problems of bribe and coercion, and can be realized with current techniques. By using smart cards to randomize part content of the ballot, the voter can not construct a receipt. By using physical voting booths, bribers and coercers can not monitor the voter while he votes. Unlike conventional voting systems, the voter of the proposed scheme can choose any voting booth that is convenient and safe to him. Furthermore, the performance of the proposed schemes is optimal in that time and communication complexity for the voter is independent of the number of voting authorities.
2004
EPRINT
An Enhanced and Secure Protocol for Authenticated Key Exchange
An enhanced authentication key exchange protocol was proposed to exchange multiple session keys between two participants at a time. This paper shows that this enhanced protocol is insecure under the known session key attack, known long-term private key attack, signature forgery attack, and replay attack. This paper also proposes an enhanced and secure key agreement protocol for exchanging multiple session keys in one run of the protocol. The protocol is secure against the attacks mentioned above. Besides, a formal proof is given to guarantee the security of the proposed protocol under other potential attacks.
2004
EPRINT
An Hybrid Mode of Operation
In this paper I propose a tweakable block cipher construction with a mode of operation that combines counter and chaining methods. Using a single key, the direct application of this mode produces unrepeatable message authentication tags.
2004
EPRINT
An IBE Scheme to Exchange Authenticated Secret Keys
We present a variant of the Boneh \& Franklin Identiy-based Encryption {\sc ibe} scheme to derive an authenticated symmetric key-exchange protocol, when combined with a signature scheme. Our protocol uses {\sc ibe} as a secure channel to establish a symmetric key between two users and, after that, further communication can be done by symmetric cryptography, much faster than pairing-based cryptography.
2004
EPRINT
An Oblivious Transfer Protocol with Log-Squared Communication
We propose a one-round $1$-out-of-$n$ computationally-private information retrieval protocol for $\ell$-bit strings with low-degree polylogarithmic receiver-computation, linear sender-computation and communication $\Theta(k\cdot\log^2{n}+\ell\cdot\log{n})$, where $k$ is a possibly non-constant security parameter. The new protocol is receiver-private if the underlying length-flexible additively homomorphic public-key cryptosystem is IND-CPA secure. It can be transformed to a one-round computationally receiver-private and information-theoretically sender-private $1$-out-of-$n$ oblivious-transfer protocol for $\ell$-bit strings, that has the same asymptotic communication and is private in the standard complexity-theoretic model.
2004
EPRINT
Analysis of the WinZip encryption method
WinZip is a popular compression utility for Microsoft Windows computers, the latest version of which is advertised as having "easy-to-use AES encryption to protect your sensitive data." We exhibit several attacks against WinZip's new encryption method, dubbed "AE-2" or "Advanced Encryption, version two." We then discuss secure alternatives. Since at a high level the underlying WinZip encryption method appears secure (the core is exactly Encrypt-then-Authenticate using AES-CTR and HMAC-SHA1), and since one of our attacks was made possible because of the way that WinZip Computing, Inc.~decided to fix a different security problem with its previous encryption method AE-1, our attacks further underscore the subtlety of designing cryptographically secure software.
2004
EPRINT
Another Look at ``Provable Security''
We give an informal analysis and critique of several typical ``provable security'' results. In some cases there are intuitive but convincing arguments for rejecting the conclusions suggested by the formal terminology and ``proofs,'' whereas in other cases the formalism seems to be consistent with common sense. We discuss the reasons why the search for mathematically convincing theoretical evidence to support the security of public-key systems has been an important theme of researchers. But we argue that the theorem-proof paradigm of theoretical mathematics is of limited relevance here and often leads to papers that are confusing and misleading. Because our paper is aimed at the general mathematical public, it is self-contained and as jargon-free as possible.
2004
EPRINT
Architectures and Hardware Implementations of the 64-bit MISTY1 Block Cipher
Two alternative architectures and VLSI implementations of the 64-bit NESSIE proposal, MISTY1 block cipher, are presented in this paper. For these implementations, FPGA devices were used. The first architecture is suitable for applications with high throughput requirements. A throughput of up to 7.2 Gbps can be achieved at a clock frequency of 96 MHz. The main characteristic of this implementation is that uses RAM blocks that are embedded in the FPGA device in order to implement the necessary by the algorithm S-boxes. The second architecture can be used in applications with constrained hardware resources. It uses feedback logic and inner pipeline with negative edge-triggered register. So, it causes the critical path to be shorter, without increasing the latency of the cipher execution. Compared with an implementation without inner pipeline, performance improvement of 97% is achieved. The measured throughput of the second architecture implementation is 561 Mbps at 79 MHz.
2004
EPRINT
Asynchronous Proactive RSA
Nowadays, to model practical systems better, such as the Internet network and ad hoc networks, researchers usually regard these systems as asynchronous networks. Meanwhile, proactive secret sharing schemes are often employed to tolerate a mobile adversary. Considering both aspects, an asynchronous proactive threshold signature scheme is needed to keep computer systems secure. So far, two asynchronous proactive secret sharing schemes have been proposed. One is proposed by Zhou in 2001, which is for RSA schemes. The other scheme is proposed by Cachin in 2002, which is a proactive secret sharing scheme for discrete-log schemes. There exist several drawbacks in both schemes. In Zhou??s scheme, the formal security proof of this scheme is missing. Furthermore, Zhou??s scheme needs to resort to the system administrator as the trusted third party for further run when some Byzantine errors occur. In Cachin??s scheme, the building block is based on the threshold RSA scheme proposed by Shoup. However, how to proactivize Shoup??s scheme is omitted in Cachin??s scheme, so this scheme is incomplete. In this paper, we present a complete provably secure asynchronous proactive RSA scheme (APRS). Our paper has four contributions. Firstly, we present a provably secure asynchronous verifiable secret sharing for RSA schemes (asynchronous verifiable additive secret sharing, AVASS), which is based on a verifiable additive secret sharing over integers. Secondly, we propose an asynchronous threshold RSA signature scheme that is based on the AVASS scheme and the random oracle model, and is capable of being proactivized. Thirdly, we present a provably secure threshold coin-tossing scheme on the basis of the above threshold RSA scheme. Fourthly, we propose an asynchronous proactive secret sharing based on the threshold RSA scheme and the coin-tossing scheme. Finally, combining the proactive secret sharing scheme and the threshold RSA scheme, we achieve a complete provably secure asynchronous proactive RSA scheme.
2004
EPRINT
Attacking a Public Key Cryptosystem Based on Tree Replacement
We point out several security flaws in the cryptosystem based on tree replacement systems proposed by Samuel, Thomas, Abisha and Subramanian at INDOCRYPT 2002. Due to the success of (among others) very simple ciphertext-only attacks, we evidence that this system does not, in its present form, offer acceptable security guarantees for cryptographic applications.
2004
EPRINT
Attacks On An ISO/IEC 11770-2 Key Establishment Protocol
Two possible types of attack (a replay attack and a type attack) on a key establishment protocol (mechanism 12) standardised in ISO/IEC 11770-2 are described and two solutions are proposed.
2004
EPRINT
Attacks on Bresson-Chevassut-Essiari-Pointcheval's Group Key Agreement Scheme for Low-Power Mobile Devices
In this paper, we show that Bresson-Chevassut-Essiari-Pointcheval's group key agreement scheme does not meet the main security properties: implicit key authentication, forward secrecy, and known key security. Also, we propose an improved version which fixes the security flaws found in the scheme.
2004
EPRINT
Authenticated tree parity machine key exchange
The synchronisation of Tree Parity Machines (TPMs), has proven to provide a valuable alternative concept for secure symmetric key exchange. Yet, from a cryptographer's point of view, authentication is at least as important as a secure exchange of keys. Adding an authentication via hashing e.g. is straightforward but with no relation to Neural Cryptography. We consequently formulate an authenticated key exchange within this concept. Another alternative, integrating a Zero-Knowledge protocol into the synchronisation, is also presented. A Man-In-The-Middle attack and even all currently known attacks, that are based on using identically structured TPMs and synchronisation as well, can so be averted. This in turn has practical consequences on using the trajectory in weight space. Both suggestions have the advantage of not affecting the previously observed physics of this interacting system at all.
2004
EPRINT
Badger - A Fast and Provably Secure MAC
We present Badger, a new fast and provably secure MAC based on universal hashing. In the construction, a modified tree hash that is more efficient than standard tree hash is used and its security is being proven. Furthermore, in order to derive the core hash function of the tree, we use a novel technique for reducing $\Delta$-universal function families to universal families. The resulting MAC is very efficient on standard platforms both for short and long messages. As an example, for a $64$-bit tag, it achieves performances up to 2.2 and 1.2 clock cycles per byte on a Pentium III and Pentium 4 processor, respectively. The forgery probability is at most $2^{-52.2}$.
2004
EPRINT
Block Ciphers and Stream Ciphers: The State of the Art
In these lecture notes we survey the state of the art in symmetric key encryption, in particular in the block ciphers and stream ciphers area. The area of symmetric key encryption has been very active in the last five years due to growing interest from academic and industry research, standardization efforts like AES, NESSIE and CRYPTREC, as well as due to ease of government control over export of cryptography.
2004
EPRINT
Building Instances of TTM Immune to the Goubin-Courtois Attack and the Ding-Schmidt Attack
We think that there are two main attacks on TTM cryptosystem; the Goubin-Courtois attack ([6]) and the Ding-Schmidt attack ([5]). The paper of Goubin-Courtois is not clearly written. Their arguments (with many gaps) depend on an parameter $r$ which is never defined. It is nature to take their parameter $r$ to be the index $s$ used in our "lock polynomials" (see section 1). Later on Courtois implies otherwise in his website. In their paper ([6]) or in his website, Courtois simply declares that TTM is of rank 2 (i.e., $r=2$) without any justification. In this paper, we will illustrate another example (cf Example below) satisfies both requirements, i.e., the index $s$ used in our "lock polynomials" (see section 1) is 7, and the number of variables in all quartic forms is 4 which shows that Goubin-Courtois' unsubstantial claim: "TTM is rank 2" invalid. Thus we settle this question of Goubin-Courtois attack once for all. To guard against "high rank attack", in this Example every variable appears 9 times in 9 different polynomials. On the other hand J.~Ding and D.~Schmidt show ([5]) how to construct an interesting attack on some implementations of TTM ([10,11]) based on Patarin's idea ([14]) of bilinear relations created by the structure in the kernel equations in an implementation of TTM. The success of this attack is accidental. In our Example, the attack fails. we will describe a {\it mixed implementation} which will make any attack, which is sensitive to the size of the ground field, ineffective. In this paper, the Example is strong (i.e., $\geq 2^{148})$ against both Goubin-Courtois attack and Ding-Schmidt attack as well as other previously proposed incomplete attacks like XL($>2^{97}$), FXL($>2^{112}$).
2004
EPRINT
Capacity and Examples of Template Protecting Biometric Authentication Systems
In this paper, we formulate precisely the requirements for privacy protecting biometric authentication systems. The secrecy capacity $\Cs$ is investigated for the discrete and the continuous case. We present, furthermore, a general algorithm that meets the requirements and achieves $\Cs$ as well as $\Cid$ (the identification capacity). Finally, we present some practical constructions of the general algorithm and analyze their properties.
2004
EPRINT
Chameleon Hashing without Key Exposure
Chameleon signatures are based on well established hash-and-sign paradigm, where a \emph{chameleon hash function} is used to compute the cryptographic message digest. Chameleon signatures simultaneously provide the properties of non-repudiation and non-transferability for the signed message, $i.e.,$ the designated recipient is capable of verifying the validity of the signature, but cannot disclose the contents of the signed information to convince any third party without the signer's consent. One disadvantage of the initial chameleon signature scheme is that signature forgery results in the signer recovering the recipient's trapdoor information, $i.e.,$ private key. Therefore, the signer can use this information to deny \emph{other} signatures given to the recipient. This creates a strong disincentive for the recipient to forge signatures, partially undermining the concept of non-transferability. In this paper, we firstly propose a chameleon hashing scheme in the gap Diffie-Hellman group to solve the problem of key exposure. We can prove that the recipient's trapdoor information will never be compromised under the assumption of Computation Diffie-Hellman Problem (CDHP) is intractable. Moreover, we use the proposed chameleon hashing scheme to design a chameleon signature scheme.
2004
EPRINT
Charge Recycling Sense Amplifier Based Logic: Securing Low Power Security IC?s against Differential Power Analysis
Charge Recycling Sense Amplifier Based Logic is presented. This logic is derived from Sense Amplifier Based Logic, which is a logic style with signal independent power consumption that is capable to protect security devices such as Smart Cards against power attacks. Experimental results show that utilization of advanced circuit techniques save 20% in power consumption and 63% in peak supply current and that the logic style preserves the energy masking behavior.
2004
EPRINT
Clarifying Obfuscation: Improving the Security of White-Box Encoding
To ensure the security of software executing on malicious hosts, as in digital rights management (DRM) applications, it is desirable to encrypt or decrypt content using white-box encoded cryptographic algorithms in the manner of Chow et al. Such encoded algorithms must run on an adversary?s machine without revealing the private key information used, despite the adversary?s ability to observe and manipulate the running algorithm. We have implemented obfuscated (white-box) DES and 3DES algorithms along the lines of Chow et al., with alterations that improve the security of the key, eliminating attacks that extract the key from Chow et al.?s obfuscated DES. Our system is secure against two previously published attacks on Chow et al.?s system, as well as a new adaptation of a statistical bucketing attack on their system. During implementation of white-box DES we found that a number of optimizations were needed for practical generation and execution. On a typical laptop we can generate obfuscated DES functions in a Lisp environment in under a minute allocating 11 MB, including the space required for the resulting function. The resulting function occupies 4.5 MB and encrypts or decrypts each block in approximately 30 ms on an 800 MHz G4 processor; slight run-time performance of the obfuscated DES could be traded to further reduce our algorithm?s representation to 2.3 MB. Although it is over an order of magnitude slower than typical DES systems, we believe it is fast enough for application to some DRM problems.
2004
EPRINT
Classes of Plateaued Rotation Symmetric Boolean Functions under Transformation of Walsh Spectra
Construction methods of Boolean functions with cryptographically significant properties is an important and difficult problem. In this work we investigate the class of rotation symmetric Boolean functions (RSBFs). These functions are invariant under circular translation of indices and were mainly introduced for efficient implementation purposes. First, we derive general results on these functions. Afterwards, we concentrate on plateaued RSBFs on odd number of variables, which have three valued Walsh Spectra ($0, \pm \lambda$), and can have maximum nonlinearity. We consider both cases when the number of variables $n$ is composite and prime. % When $n$ is odd and prime, we derive the constructive relation between {\it balanced/unbalanced} plateaued RSBFs and show how from one given such function the complete sub class can be generated. As long as search for one plateaued RSBF is of high complexity, our proposed manipulation technique with Walsh spectra imediately give us the way to construct many such functions without time consuming. Since the most important properties of a function are determined via the values of Walsh spectra, then such transformation technique is important to create new function with, possible, better properties. The application of our transformation technique construct a class of $\left((2^{\frac{n-1}{2}}+1)/n\right)!\cdot \left(2^{\frac{n-1}{2}}-1\right)$ balanced/unbalanced plateaued RSBFs. % In our practical implementation of this technique, given one balanced PRSBF on $n=11$ variables we could construct 185 new such functions. To find the first function took us several days, whereas to construct new 185 functions took us just a second. However, this technique can be applied only when the Legendre symbol $(2/n)$ is $-1$, and the first such $n$'s are $3, 5, 7, 11, 13, 19, 29, 37, 43, \ldots$.
2004
EPRINT
Classification of Boolean Functions of 6 Variables or Less with Respect to Cryptographic Properties
This paper presents an efficient approach for classification of the affine equivalence classes of cosets of the first order Reed-Muller code with respect to cryptographic properties such as correlation-immunity, resiliency and propagation characteristics. First, we apply the method to completely classify all the $48$ classes into which the general affine group $AGL(2,5)$ partitions the cosets of $RM(1,5)$. Second, we describe how to find the affine equivalence classes together with their sizes of Boolean functions in 6 variables. We perform the same classification for these classes. Moreover, we also determine the classification of $RM(3,7)/RM(1,7)$. We also study the algebraic immunity of the corresponding affine equivalence classes. Moreover, several relations are derived between the algebraic immunity and other cryptographic properties. Finally, we introduce two new indicators which can be used to distinguish affine inequivalent Boolean functions when the known criteria are not sufficient. From these indicators a method can be derived for finding the affine relation between two functions (if such exists). The efficiency of the method depends on the structure of the Walsh or autocorrelation spectrum.
2004
EPRINT
Classification of genus 2 curves over $\mathbb{F}_{2^n}$ and optimization of their arithmetic
To obtain efficient cryptosystems based on hyperelliptic curves, we studied genus 2 isomorphism classes of hyperelliptic curves in characteristic 2. We found general and optimal form for these curves, just as the short Weierstrass form for elliptic curves. We studied the security and the arithmetic on their jacobian. We also rewrote and optimized the formulas of Lange in characteristic 2, and we introduced a new system of coordinate. Therefore, we deduced the best form of hyperelliptic curves of genus 2 in characteristic 2 to use in cryptography.
2004
EPRINT
Classification of Highly Nonlinear Boolean Power Functions with a Randomised Algorithm for Checking Normality
A Boolean function is called normal if it is constant on flats of certain dimensions. This property is relevant for the construction and analysis of cryptosystems. This paper presents an asymmetric Monte Carlo algorithm to determine whether a given Boolean function is normal. Our algorithm is far faster than the best known (deterministic) algorithm of Daum et al. In a first phase, it checks for flats of low dimension whether the given Boolean function is constant on them and combines such flats to flats of higher dimension in a second phase. This way, the algorithm is much faster than exhaustive search. Moreover, the algorithm benefits from randomising the first phase. In addition, by evaluating several flats implicitly in parallel, the time-complexity of the algorithm decreases further. As an application, we determine the level of normality for several, highly nonlinear Boolean power functions.
2004
EPRINT
Code-Based Game-Playing Proofs and the Security of Triple Encryption
The game-playing technique is a powerful tool for analyzing cryptographic constructions. We illustrate this by using games as the central tool for proving security of three-key triple-encryption, a long-standing open problem. Our result, which is in the ideal-cipher model, demonstrates that for DES parameters (56-bit keys and 64-bit plaintexts) an adversary's maximal advantage is small until it asks about $2^{78}$ queries. Beyond this application, we develop the foundations for game playing, formalizing a general framework for game-playing proofs and discussing techniques used within such proofs. To further exercise the game-playing framework we show how to use games to get simple proofs for the PRP/PRF Switching Lemma, the security of the basic CBC MAC, and the chosen-plaintext-attack security of OAEP.
2004
EPRINT
2004
EPRINT
Combinatorial group theory and public key cryptography
After some excitement generated by recently suggested public key exchange protocols due to Anshel-Anshel-Goldfeld and Ko-Lee et al., it is a prevalent opinion now that the conjugacy search problem is unlikely to provide sufficient level of security if a braid group is used as the platform. In this paper we address the following questions: (1) whether choosing a different group, or a class of groups, can remedy the situation; (2) whether some other ``hard" problem from combinatorial group theory can be used, instead of the conjugacy search problem, in a public key exchange protocol. Another question that we address here, although somewhat vague, is likely to become a focus of the future research in public key cryptography based on symbolic computation: (3) whether one can efficiently disguise an element of a given group (or a semigroup) by using defining relations.
2004
EPRINT
CompChall: Addressing Password Guessing Attacks
Even though passwords are the most convenient means of authentication, they bring along themselves the threat of dictionary attacks. Dictionary attacks may be of two kinds: online and offline. While offline dictionary attacks are possible only if the adversary is able to collect data for a successful protocol execution by eavesdropping on the communication channel and can be successfully countered using public key cryptography, online dictionary attacks can be performed by anyone and there is no satisfactory solution to counter them. This paper presents a new authentication protocol which is called CompChall (computational challenge). The proposed protocol uses only one way hash functions as the building blocks and attempts to eliminate online dictionary attacks by implementing a challenge-response system. This challenge-response system is designed in a fashion that it does not pose any difficulty to a genuine user but is time consuming and computationally intensive for an adversary trying to launch a large number of login requests per unit time as in the case of an online dictionary attack. The protocol is stateless and thus less vulnerable to DoS (Denial of Service) attacks.
2004
EPRINT
Completion of Computation of Improved Upper Bound on the Maximum Average Linear Hull Probabilty for Rijndael
This report presents the results from the completed computation of an algorithm introduced by the authors in [11] for evaluating the provable security of the AES (Rijndael) against linear cryptanalysis. This algorithm, later named KMT2, can in fact be applied to any SPN [8]. Preliminary results in [11] were based on 43\% of total computation, estimated at 200,000 hours on our benchmark machine at the time, a Sun Ultra 5. After some delay, we obtained access to the necessary computational resources, and were able to run the algorithm to completion. In addition to the above, this report presents the results from the dual version of our algorithm (KMT2-DC) as applied to the AES.
2004
EPRINT
Complexity of the Collision and Near-Collision Attack on SHA-0 with Different Message Schedules
SHA-0 employs a primitive polynomnial of degree 16 over GF(2) in its message schedule. There are 2048 primitive polynomials of degree 16 over GF(2). For each primitive polynomial, a SHA-0 variant can be constructed. In this paper, the security of 2048 variants is analyzed against the Chabaud-Joux attack proposed in CRYPTO'98. The analysis shows that all the variants could be collision-attacked by using near-collisions as a tool and thus the replacement of the primitive polynomial is not a proper way to make SHA-0 secure. However, it is shown that the selection of the variants highly affects the complexity of the attack. Furthermore, a collision in the most vulnerable variant is presented. It is obtained by the original Chabaud-Joux attack without any improvements.
2004
EPRINT
Compressed Pairings
Pairing-based cryptosystems rely on bilinear non-degenerate maps called pairings, such as the Tate and Weil pairings defined over certain elliptic curve groups. In this paper we show how to compress pairing values, how to couple this technique with that of point compression, and how to benefit from the compressed representation to speed up exponentiations involving pairing values, as required in many pairing based protocols.
2004
EPRINT
Computing Modular Polynomials
We present a new probabilistic algorithm to compute modular polynomials modulo a prime. Modular polynomials parameterize pairs of isogenous elliptic curves and are useful in many aspects of computational number theory and cryptography. Our algorithm has the distinguishing feature that it does not involve the computation of Fourier coefficients of modular forms. We avoid computing the exponentially large integral coefficients by working directly modulo a prime and computing isogenies between elliptic curves via Velu's formulas.
2004
EPRINT
Concealing Complex Policies with Hidden Credentials
Hidden credentials are useful in protecting sensitive resource requests, resources, policies and credentials. We propose a significant improvement in decryption performance when implementing hidden credentials using the Franklin/Boneh IBE. We also propose a substantially improved secret splitting scheme for enforcing complex policies, and show how it improves concealment of policies from nonsatisfying recipients.
2004
EPRINT
Construction and Traversal of Hash Chain with Public Links
Current hash chain traversal techniques require that the intermediate links of the hash chain be stored secretly on a trusted storage. This requirement is undesirable in several applications. We propose a new construction of hash chains based on inserting a ?breakpoint? after fixed number of links in the chain. We also propose a method with which the current hash chain traversal techniques can be applied to our construction without any significant changes in the storage and computation requirements and with the added advantage that the intermediate links may be stored on a public and non-trusted storage. We are also able to prove the security of our construction by replacing the hash function with a MAC function.
2004
EPRINT
Controlling Spam by Secure Internet Content Selection
Unsolicited and undesirable e-mail (spam) is a growing problem for Internet users and service providers. We present the Secure Internet Content Selection (SICS) protocol, an efficient cryptographic mechanism for spam-control, based on allocation of responsibility (liability). With SICS, e-mail is sent with a content label, and a cryptographic protocol ensures labels are authentic and penalizes falsely labeled e-mail (spam). The protocol supports trusted senders (penalized by loss of trust) and unknown senders (penalized financially). The recipient can determine the compensation amount for falsely labeled e-mail (spam)). SICS is practical, with negligible overhead, gradual adoption path, and use of existing relationships; it is also flexible and appropriate for most scenarios, including deployment by end users and/or ISPs and support for privacy and legitimate, properly labeled commercial e-mail. SICS improves on other crypto-based proposals for spam controls, and complements non-cryptographic spam controls
2004
EPRINT
Corrections of the NIST Statistical Test Suite for Randomness
It is well known that the NIST statistical test suite was used for the evaluation of AES candidate algorithms. We have found that the test setting of Discrete Fourier Transform test and Lempel-Ziv test of this test suite are wrong. We give four corrections of mistakes in the test settings. This suggests that re-evaluation of the test results should be needed.
2004
EPRINT
Covering Radius of the $(n-3)$-rd Order Reed-Muller Code in the Set of Resilient Functions
In this paper, we continue the study of the covering radius in the set of resilient functions, which has been defined by Kurosawa. This new concept is meaningful to cryptography especially in the context of the new class of algebraic attacks on stream ciphers proposed by Courtois and Meier at Eurocrypt 2003 and Courtois at Crypto 2003. In order to resist such attacks the combining Boolean function should be at high distance from lower degree functions. Using a result from coding theory on the covering radius of $(n-3)$-rd Reed-Muller codes, we establish exact values of the the covering radius of $RM(n-3,n)$ in the set of $1$-resilient Boolean functions of $n$ variables, when $\lfloor n/2 \rfloor = 1 \mod\;2$. We also improve the lower bounds for covering radius of the Reed-Muller codes $RM(r,n)$ in the set of $t$-resilient functions, where $\lceil r/2 \rceil = 0 \mod\;2$, $t \leq n-r-2$ and $n\geq r+3$.
2004
EPRINT
Crosscorrelation Spectra of Dillon and Patterson-Wiedemann type Boolean Functions
In this paper we study the additive crosscorrelation spectra between two Boolean functions whose supports are union of certain cosets. These functions on even number of input variables have been introduced by Dillon and we refer to them as Dillon type functions. Our general result shows that the crosscorrelation spectra between any two Dillon type functions are at most $5$-valued. As a consequence we find that the crosscorrelation spectra between two Dillon type bent functions on $n$-variables are at most $3$-valued with maximum possible absolute value at the nonzero points being $\leq 2^{\frac{n}{2}+1}$. Moreover, in the same line, the autocorrelation spectra of Dillon type bent functions at different decimations is studied. Further we demonstrate that these results can be used to show the existence of a class of polynomials for which the absolute value of the Weil sum has a sharper upper bound than the Weil bound. Patterson and Wiedemann extended the idea of Dillon for functions on odd number of variables. We study the crosscorrelation spectra between two such functions and then use the results for the calculating the autocorrelation spectra too.
2004
EPRINT
Cryptanalysis of a Provably Secure Cryptographic Hash Function
We present a cryptanalysis of a provably secure cryptographic hash function proposed by Augot, Finiasz and Sendrier on eprint. Our attack is a variant of Wagner's generalized birthday attack. It is significantly faster than the attack considered by the authors, and it is practical for two of the three proposed parameters.
2004
EPRINT
Cryptanalysis of a threshold proxy signature with known signers
A scheme of threshold proxy signature with known signers was proposed by Hwang et al. In their scheme, the receiver can identify the proxy signers that actually generated a proxy signature. Tzeng et al. demonstrated that this signature scheme is insecure and proposed an improvement to mend the information leakage. This paper shows that the improved scheme is still insecure under the original signer??s forgery attack.
2004
EPRINT
Cryptanalysis of a timestamp-based password authentication scheme
Recently, J.-J. Shen, C.-W. Lin and M.-S. Hwang (Computers & Security, Vol 22, No 7, pp 591-595, 2003) proposed a modified Yang-Shieh scheme to enhance security. They claimed that their modified scheme can withstand the forged login attack and also provide a mutual authentication method to prevent the forged server attack. In this paper, we show that the Shen-Lin-Hwang scheme cannot resist the forged login attack either. The intruder is able to forge a valid forge request of a legitimate user Ui and then successfully impersonate him by intercepting a login request sent by Ui and registering a smart card.
2004
EPRINT
Cryptanalysis of an ID-based Password Authentication Scheme using Smart Cards and Fingerprints
In a paper recently published in the ACM Operating Systems Review, Kim, Lee and Yoo \cite{kim-lee-yoo} describe two ID-based password authentication schemes for logging onto a remote network server using smart cards, passwords and fingerprints. Various claims are made regarding the security of the schemes, but no proof is offered. Here we show how a passive eavesdropper, without access to any smart card, password or fingerprint, and after passively eavesdropping only one legitimate log-on, can subsequently log-on to the server claiming any identity.
2004
EPRINT
Cryptanalysis of Chang et al.'s Signature Scheme with Message Recovery
Recently, Chang \textit{et al}. \cite{Chang} proposed a new digital signature scheme with message recovery and claimed that neither one-way hash functions nor message redundancy schemes were employed in their scheme. However, in this letter, two forgery attacks are proposed to show that Chang \textit{et al.}'s signature scheme is not secure. To resist these attacks, the message redundancy schemes may be still used.
2004
EPRINT
Cryptanalysis of Noel McCullagh and Paulo S. L. M. Barreto??s two-party identity-based key agreement
Noel McCullagh and Paulo S. L. M. Barreto[1] proposed a two-party identity-based key agreement protocol in 2004,which can be used in either escrowed or escrowless mode. They also described conditions under which users of different Key Generation Centres can agree on a shared secret key. In this paper, we show that these two protocols are insecure against the key compromis impersonate attack,and the fix protocol has not the property of Perfect-Forword-Secrecy.We modify these protocols in three ways,which are secure against all attack and satisfy the property of Known-Key Security, Perfect-Forward-Secrecy, Key-Compromise Impersonation, Unknown Key-Share,and Key control and so on.
2004
EPRINT
Cryptanalysis of Park-Lee Nominative Proxy Signature Scheme
Park and Lee have proposed a digital nominative proxy signature scheme for mobile communication in [1]. They claimed that neither Origin signer nor Proxy agent can generate a valid signature solely. In this paper we show that Origin signer can generate a valid signature without the cooperation of the agent. In fact, the flaw comes from that Verifier dose not use the public key of Proxy agent in verifying phase. It's a serious designing error.
2004
EPRINT
Cryptanalysis of Qiu-Gu-Chen Variant Group Signature Scheme
Qiu et al. proposed a variant group signature scheme in [1]. We find that the group manager can successfully forge signature because he has absolute predominance in Join Phase.
2004
EPRINT
Cryptanalysis of RCES/RSES Image Encryption Scheme
Recently, a chaos-based image encryption scheme called RCES (also called RSES) was proposed. This paper analyzes the security of RCES, and points out that it is insecure against the known/chosen-plaintext attacks: the number of required known/chosen plain-images is only one or two. In addition, the security of RCES against the brute-force attack was overestimated. Both theoretical and experimental analyses are given to show the performance of the suggested known/chosen-plaintext attacks. The insecurity of RCES is due to its special design, which makes it a typical example of insecure image encryption schemes. Some lessons are drawn from RCES to show some common principles for ensuring the high level of security of an image encryption scheme.
2004
EPRINT
Cryptanalysis of SFlash v3
Sflash is a fast multivariate signature scheme. Though the first version Sflash-v1 was flawed, a second version, Sflash-v2 was selected by the Nessie Consortium and was recommended for implementation of low-end smart cards. Very recently, due to the security concern, the designer of Sflash recommended that Sflash-v2 should not be used, instead a new version Sflash-v3 is proposed, which essentially only increases the length of the signature. The Sflash family of signature schemes is a variant of the Matsumoto and Imai public key cryptosystem. The modification is through the Minus method, namely given a set of polynomial equations, one takes out a few of them to make them much more difficult to solve. In this paper, we attack the Sflash-v3 scheme by combining an idea from the relinearization method by Kipnis and Shamir, which was used to attack the Hidden Field Equation schemes, and the linearization method by Patarin. We show that the attack complexity is less than 2^80, the security standard required by the Nessie Consortium.
2004
EPRINT
Cryptanalysis of Threshold-Multisignature Schemes
In [1], Li et al. proposed a new type of signature scheme, called the $(t,n)$ threshold-mutisignature scheme. The first one needs a mutually trusted share distribution center (SDC) while the second one does not. In this paper, we present a security analysis on their second schemes. We point out that their second threshold-multisignature scheme is vulnerable to universal forgery by an insider attacker under reasonable assumptions. In our attack, $(n-t+1)$ colluding members can control the group secret key. Therefore, they can generate valid threshold-multisignautre for any message without the help of other members. Furthermore, honest members cannot detect this security flaw in the system, since any $t$ members can generate threshold-multisignatures according to the prescribed protocols.
2004
EPRINT
Cryptanalyzing Bresson, et al.'s Spontaneous Anonymous Threshold Signature for Ad Hoc Groups and Patching via Updating Cramer, et al.'s Threshold Proof-of-Knowledge
We present an algebraic cryptanalysis of Bresson, et al.'s spontaneous anonymous threshold signature for ad hoc groups. The technique is to reduce a degenerate condition in Lagrange interpolation to an algebraically solvable high-density knapsack problem over $GF(2^\ell)$. We repair their protocol by revisiting and updating Cramer, et al.'s result on spontaneous anonymous threshold proof-of-knowledge (partial proof-of-knowledge). We generalize their proof by removing two assumptions, and reduce its security to a new candidate hard problem, PoK-Collision, in the random oracle model. To add to the urgency of our update, we present major versions of major PoK schemes that do not satisfy their special soundness assumption.
2004
EPRINT
Cryptanalyzing the Polynomial-Reconstruction based Public-Key System Under Optimal Parameter Choice
Recently, Augot and Finiasz presented a coding theoretic public key cryptosystem that suggests a new approach for designing such systems based on the Polynomial Reconstruction Problem. Their cryptosystem is an instantiation of this approach under a specific choice of parameters which, given the state of the art of coding theory, we show in this work to be sub-optimal. Coron showed how to attack the Augot and Finiasz cryptosystem. A question left open is whether the general approach suggested by the cryptosystem works or not. In this work, we show that the general approach (rather than only the instantiation) is broken as well. Our attack employs the recent powerful list-decoding mechanisms.
2004
EPRINT
Cryptographic Asynchronous Multi-Party Computation with Optimal Resilience
We consider secure multi-party computation in the asynchronous model and present an efficient protocol with optimal resilience. For $n$ parties, up to $t<n/3$ of them being corrupted, and security parameter $\kappa$, a circuit with $c$ gates can be securely computed with communication complexity $O(c n^3 \kappa)$ bits. In contrast to all previous asynchronous protocols with optimal resilience, our protocol requires access to an expensive broadcast primitive only $O(n)$ times --- independently of the size $c$ of the circuit. This results in a practical protocol with a very low communication overhead. One major drawback of a purely asynchronous network is that the inputs of up to $t$ honest parties cannot be considered for the evaluation of the circuit. Waiting for all inputs could take infinitely long when the missing inputs belong to corrupted parties. Our protocol can easily be extended to a hybrid model, in which we have one round of synchronicity at the end of the input stage, but are fully asynchronous afterwards. In this model, our protocol allows to evaluate the circuit on the inputs of every honest party.
2004
EPRINT
Cryptographic Hash-Function Basics: Definitions, Implications and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance
We consider basic notions of security for cryptographic hash functions: collision resistance, preimage resistance, and second-preimage resistance. We give seven different definitions that correspond to these three underlying ideas, and then we work out all of the implications and separations among these seven definitions within the concrete-security, provable-security framework. Because our results are concrete, we can show two types of implications, "conventional" and "provisional", where the strength of the latter depends on the amount of compression achieved by the hash function. We also distinguish two types of separations, "conditional" and "unconditional". When constructing counterexamples for our separations, we are careful to preserve specified hash-function domains and ranges; this rules out some pathological counterexamples and makes the separations more meaningful in practice. Four of our definitions are standard while three appear to be new; some of our relations and separations have appeared, others have not. Here we give a modern treatment that acts to catalog, in one place and with carefully-considered nomenclature, the most basic security notions for cryptographic hash functions.
2004
EPRINT
Cryptographic Implications of Hess' Generalized GHS Attack
A finite field K is said to be weak for elliptic curve cryptography if all instances of the discrete logarithm problem for all elliptic curves over K can be solved in significantly less time than it takes Pollard's rho method to solve the hardest instances. By considering the GHS Weil descent attack, it was previously shown that characteristic two finite fields GF(q^5) are weak. In this paper, we examine characteristic two finite fields GF(q^n) for weakness under Hess' generalization of the GHS attack. We show that the fields GF(q^7) are potentially partially weak in the sense that any instance of the discrete logarithm problem for half of all elliptic curves over GF(q^7), namely those curves E for which #E is divisible by 4, can likely be solved in significantly less time than it takes Pollard's rho method to solve the hardest instances. We also show that the fields GF(q^3) are partially weak, that the fields GF(q^6) are potentially weak, and that the fields GF(q^8) are potentially partially weak. Finally, we argue that the other fields GF(2^N) where N is not divisible by 3, 5, 6, 7 or 8, are not weak under Hess' generalized GHS attack.
2004
EPRINT
Custodian-Hiding Verifiable Encryption
In a verifiable encryption, an asymmetrically encrypted ciphertext can be publicly verified to be decipherable by a designated receiver while maintaining the semantic security of the message \cite{AsokanShWa98,CamenischDa00,CamenischSh03}. In this paper, we introduce {\em Custodian-Hiding Verifiable Encryption}, where it can be publicly verified that there exists at least one custodian (user), out of a designated group of $n$ custodians (users), who can decrypt the message, while the semantic security of the message and the anonymity of the actual decryptor are maintained. Our scheme is proven secure in the random oracle model. We also introduce two extensions to decryption by a subset of more than one user.
2004
EPRINT
DDH-based Group Key Agreement in a Mobile Environment
A group key agreement protocol is designed to efficiently implement secure multicast channels for a group of parties communicating over an untrusted, open network by allowing them to agree on a common secret key. In the past decade many problems related to group key agreement have been tackled and solved (diminished if not solved), and recently some constant-round protocols have been proven secure in concrete, realistic setting. However, all forward-secure protocols so far are still too expensive for small mobile devices. In this paper we propose a new constant-round protocol well suited for a mobile environment and prove its security under the Decisional Diffie-Hellman assumption. The protocol meets simplicity, efficiency, and all the desired security properties.
2004
EPRINT
Delegateable Signature Using Witness Indistinguishable and Witness Hiding Proofs
A delegateable signature scheme is a signature scheme where the owner of the signing key(Alice) can securely delegate to another party(Bob) the ability to sign on Alice's behalf on a restricted subset $S$ of the message space. Barak first defined and constructed this signature scheme using non-interactive zero-knowledge proof of knowledge(NIZKPK)\cite{Barak}. In his delegateable signature scheme, the function of NIZKPK is to prevent the signing verifier from tell which witness(i.e. restricted subset) is being used. Witness indistinguishable(WI) and witness hiding(WH) proof systems are weaker proof model than zero-knowledge proof and were proposed by Feige and Shamir in \cite{FS}, however, the verifier cannot also distinguish the witness which is being used in these two protocols. In this paper, we construct delegateable signature scheme using WI and WH proof protocols.
2004
EPRINT
Design Principles for Iterated Hash Functions
This paper deals with the security of iterated hash functions against generic attacks, such as, e.g., Joux' multicollision attacks from Crypto 04. The core idea is to increase the size of the internal state of an n-bit hash function to w > n bit. Variations of this core idea allow the use of a compression function with n output bits, even if the compression function itself is based on a block cipher. In a formal model, it is shown that these modifications quantifiably improve the security of iterated hash functions against generic attacks.
2004
EPRINT
Designing Against the `Overdefined System of Equations' Attack
Recently, Courtois and Pieprzyk proposed an attack on symmetric ciphers that takes advantage of a previously-unexploited property of substitution boxes, or s-boxes, in the round function. This paper gives a brief overview of this ``overdefined system of equations'' attack and shows how the attack may be avoided through the use of round functions that contain a variety of protection mechanisms, including combinations of operators from different algebraic groups, a circular rotation step, and substitution boxes (s-boxes) of large dimension.
2004
EPRINT
Designs of Efficient Secure Large Hash Values
A double length hash function is a 2n-bit hash function based on an n-bit compression function. To increase the security level, designs of good double length hash functions are important. In this paper we construct a class of maximally secure double length hash functions in random oracle model based on some good permutations. This class contains recently proposed double length hash functions. We also propose an efficient double length hash function and study its security level in the random oracle model. We prove that any attack algorithm in the random oracle model needs \Omega(2^n/(s^2n^s)) time complexity, where $s$ is some parameter related to the rate of the hash function. Thus there is a trade-off between the efficiency and security. We use the notion of computable message to make the security analysis of proposed hash functions. We also see that the security analysis of hash functions based on random permutations and hash functions based on random functions are very much related.
2004
EPRINT
Deterministic Polynomial Time Equivalence of Computing the RSA Secret Key and Factoring
We address one of the most fundamental problems concerning the RSA cryptosystem: does the knowledge of the RSA public and secret key-pair (e,d) yield the factorization of N=pq in polynomial time? It is well-known that there is a probabilistic polynomial time algorithm that on input (N,e,d) outputs the factors p and q. We present the first deterministic polynomial time algorithm that factors N provided that e,d<N. Our approach is an application of Coppersmith's technique for finding small roots of univariate modular polynomials.
2004
EPRINT
Direct Anonymous Attestation
This paper describes the direct anonymous attestation scheme (DAA). This scheme was adopted by the Trusted Computing Group as the method for remote authentication of a hardware module, called trusted platform module (TPM), while preserving the privacy of the user of the platform that contains the module. Direct anonymous attestation can be seen as a group signature without the feature that a signature can be opened, i.e., the anonymity is not revocable. Moreover, DAA allows for pseudonyms, i.e., for each signature a user (in agreement with the recipient of the signature) can decide whether or not the signature should be linkable to another signature. DAA furthermore allows for detection of ``known'' keys: if the DAA secret keys are extracted from a TPM and published, a verifier can detect that a signature was produced using these secret keys. The scheme is provably secure in the random oracle model under the strong RSA and the decisional Diffie-Hellman assumption.
2004
EPRINT
Direct Division in Factor Rings
Conventional techniques for division in the polynomial factor ring $\Ftm$ or the integer ring $\Zzs$ use a combination of inversion and multiplication. We present a new algorithm that computes the division directly and therefore eliminates the multiplication step. The algorithm requires $2\,{\rm degree\/}{(m)}$ (resp. $2 \log_2 n$) steps, each of which uses only shift and multiply-subtract operations.
2004
EPRINT
Distributed Ring Signatures for Identity-Based Scenarios
In a ring signature scheme, a signer in a subset (or {\it ring}) of potential signers produces a signature of a message in such a way that the receiver can verify that the signature comes from a member of the ring, but cannot know which member has actually signed. In this work, we extend this concept to that of distributed ring signatures, where a subset of users cooperate to compute a distributed anonymous signature on a message, on behalf of a family of subsets. We propose two schemes, one for general families of subsets, and a more efficient one for threshold families of subsets. The security of both proposals is formally proved, assuming the hardness of the Computational Diffie-Hellman problem. Our two schemes run in an identity-based scenario, where public keys of the users can be derived from their identities. This fact avoids the necessity of digital certificates, and therefore allows more efficient implementations of such systems.
2004
EPRINT
DISTRIBUTION OF R-PATTERNS IN THE KERDOCK-CODE BINARY SEQUENCES AND THE HIGHEST LEVEL SEQUENCES OF PRIMITIVE SEQUENCES OVER $Z_{2^l}$
The distribution of r-patterns is an important aspect of pseudorandomness for periodic sequences over finite field.The aim of this work is to study the distribution of r-patterns in the Kerdock-code binary sequences and the highest level sequences of primitive sequences over $Z_{2^l}$.By combining the local Weil bound with spectral analysis,we derive the upper bound of the deviation to uniform distribution.As a consequence,the recent result on the quantity is improved.
2004
EPRINT
Divisors in Residue Classes, Constructively
Let $r,s,n$ be integers satisfying $0 \leq r < s < n$, $s \geq n^{\alpha}$, $\alpha > 1/4$, and $\gcd(r,s)=1$. Lenstra showed that the number of integer divisors of $n$ equivalent to $r \pmod s$ is upper bounded by $O((\alpha-1/4)^{-2})$. We re-examine this problem; showing how to explicitly construct all such divisors and incidentally improve this bound to $O((\alpha-1/4)^{-3/2})$.
2004
EPRINT
Easy decision-Diffie-Hellman groups
It is already known that the Weil and Tate pairings can be used to solve many decision-Diffie-Hellman (DDH) problems on elliptic curves. A natural question is whether all DDH problems are easy on supersingular curves. To answer this question it is necessary to have suitable distortion maps. Verheul states that such maps exist, and this paper gives methods to construct them. The paper therefore shows that all DDH problems on supersingular elliptic curves are easy. We also discuss the issue of which DDH problems on ordinary curves are easy. A related contribution is a discussion of distortion maps which are not isomorphisms. We give explicit distortion maps for elliptic curves with complex multiplication of discriminants $D=-7$ and $D=-8$.
2004
EPRINT
Efficient and Forward-Secure Identity-Based Signcryption
Several signcryption schemes proposed in the literature are known to lack semantic security, and semantically secure signcryption schemes tend to be more computationally expensive. In fact, devising an efficient signcryption scheme providing both public verifiability and forward security was until now an open problem. In this paper, we show how a particular kind of signcryption scheme may become completely insecure when implemented with certain efficient instantiations of the Tate or Weil pairing. We also address the drawbacks of the secure schemes by proposing efficient, semantically and forward-secure signcryption schemes, in both transferable and non-transferable form, that can be realised on top of any pairing instantiation. As a bonus, we also derive from them a new, efficient identity-based signature scheme.
2004
EPRINT
Efficient and Optimistic Fair Exchanges Based on Standard RSA with Provable Security
In this paper, we introduce a new and natural paradigm for fair exchange protocols, called verifiable probabilistic signature scheme. A security model with precise and formal definitions is presented, and an RSA-based efficient and provably secure verifiable probabilistic signature scheme is proposed. Our scheme works well with standard RSA signature schemes, and the proposed optimistic fair exchange protocol is much concise and efficient, and suitable for practical applications.
2004
EPRINT
Efficient and Provably Secure Trapdoor-free Group Signature Schemes from Bilinear Pairings
Group signature schemes are cryptographic systems that provide revocable anonymity for signers. We propose a group signature scheme with constant-size public key and signature length that does not require trapdoor. So system parameters can be shared by multiple groups belonging to different organizations. The scheme is provably secure in the formal model recently proposed by Bellare, Shi and Zhang (BSZ04), using random oracle model, Decisional Bilinear Diffie-Hellman and Strong Diffie-Hellman assumptions. We give a more efficient variant scheme and prove its security in a formal model which is a modification of BSZ04 model and has a weaker anonymity requirement. Both schemes are very efficient and the sizes of signatures are approximately one half and one third, respectively, of the sizes of the well-known ACJT00 scheme. We will show that the schemes can be used to construct a traceable signature scheme and identity escrow schemes. They can also be extended to provide membership revocation.
2004
EPRINT
Efficient and Secure Multi-Party Computation with Faulty Majority and Complete Fairness
We study the problem of constructing secure multi-party computation (MPC) protocols that are {\em completely fair} --- meaning that either all the parties learn the output of the function, or nobody does --- even when a majority of the parties are corrupted. We first propose a framework for fair multi-party computation, within which we formulate a definition of secure and fair protocols. The definition follows the standard simulation paradigm, but is modified to allow the protocol to depend on the runing time of the adversary. In this way, we avoid a well-known impossibility result for fair MPC with corrupted majority; in particular, our definition admits constructions that tolerate up to $(n-1)$ corruptions, where $n$ is the total number of parties. Next, we define a ``commit-prove-fair-open'' functionality and construct an efficient protocol that realizes it, using a new variant of a cryptographic primitive known as ``time-lines.'' With this functionality, we show that some of the existing secure MPC protocols can be easily transformed into fair protocols while preserving their security. Putting these results together, we construct efficient, secure MPC protocols that are completely fair even in the presence of corrupted majorities. Furthermore, these protocols remain secure when arbitrarily composed with any protocols, which means, in particular, that they are concurrently-composable and non-malleable. Finally, as an example of our results, we show a very efficient protocol that fairly and securely solves the socialist millionaires' problem.
2004
EPRINT
Efficient and Universally Composable Committed Oblivious Transfer and Applications
Committed Oblivious Transfer (COT) is a useful cryptographic primitive that combines the functionalities of bit commitment and oblivious transfer. In this paper, we introduce an extended version of COT (ECOT) which additionally allows proofs of relations among committed bits, and we construct an efficient protocol that securely realizes an ECOT functionality in the universal-composability (UC) framework in the common reference string (CRS) model. Our construction is more efficient than previous (non-UC) constructions of COT, involving only a constant number of exponentiations and communication rounds. Using the ECOT functionality as a building block, we construct efficient UC protocols for general two-party and multi-party functionalities (in the CRS model), each gate requiring a constant number of ECOT's.
2004
EPRINT
Efficient Batch Verification of Signature Schemes based on Bilinear Maps
In this paper we present batch signature verification schemes for identity and non-identity signatures schemes based on bilinear maps. We examine some signature schemes and exploit their properties so that we can batch process the verification of these signatures in an efficient manner. Batch verification of message signatures is useful in real world applications. Most email clients are predominantly offline and so do not download emails one at a time. Instead the mails arrive at an online mail server individually, where they are collected together and stored. It is only after some period of time that any mails on the server are downloaded in bulk. It is not unreasonable to have 5 - 10 emails download into your inbox in any one transaction with the mail server. Say these mails were all signed, then this would be an ideal time to do batch signature verification. We show that we can make substantial savings over the na?ve approach of verifying one message signature at a time.
2004
EPRINT
Efficient Consistency Proofs for Generalized Queries on a Committed Database
A *consistent query protocol* (CQP) allows a database owner to publish a very short string $c$ which *commits* her and everybody else to a particular database $D$, so that any copy of the database can later be used to answer queries and give short proofs that the answers are consistent with the commitment $c$. Here *commits* means that there is at most one database $D$ that anybody can find (in polynomial time) which is consistent with $c$. (Unlike in some previous work, this strong guarantee holds even for owners who try to cheat while creating $c$.) Efficient CQPs for membership and one-dimensional range queries are known \cite{BRW02,K98,MR}: given a query pair $a,b\in \mathbb{R}$, the server answers with all the keys in the database which lie in the interval $[a,b]$ and a proof that the answer is correct. This paper explores CQPs for more general types of databases. We put forward a general technique for constructing CQPs for any type of query, assuming the existence of a data structure/algorithm with certain inherent robustness properties that we define (called a *data robust algorithm*). We illustrate our technique by constructing an efficient protocol for *orthogonal range queries*, where the database keys are points in $\mathbb{R}^d$ and a query asks for all keys in a rectangle $[a_1,b_1]\times\ldots \times [a_d,b_d]$. Our data-robust algorithm is within a $O(\log N)$ factor of the best known standard data structure (a range tree, due to Bentley (1980)). We modify our protocol so that it is also private, that is, the proofs leak no information about the database beyond the query answers. We show a generic modification to ensure privacy based on zero-knowledge proofs, and also give a new, more efficient protocol tailored to hash trees.
2004
EPRINT
Efficient Identity-Based Encryption Without Random Oracles
We present the first efficient Identity-Based Encryption (IBE) scheme that is fully secure without random oracles. We first present our IBE construction and reduce the security of our scheme to the decisional Bilinear Diffie-Hellman (BDH) problem. Additionally, we show that our techniques can be used to build a new signature scheme that is secure under the computational Diffie-Hellman assumption without random oracles.
2004
EPRINT
Efficient k-out-of-n Oblivious Transfer Schemes with Adaptive and Non-Adaptive Queries
In this paper we propose a very efficient two-round k-out-of-n oblivious transfer scheme, in which R sends O(k) messages to S, and S sends O(n) messages back to R. The computation cost of R and S is reasonable as R needs O(k) operations and S needs O(n)operations. The choices of R are unconditionally secure and the secrecy of unchosen messages is guaranteed as well if the decisional bilinear Diffie-Hellman problem is hard. When k=1, our scheme is as efficient as the most efficient 1-out-of-n oblivious transfer scheme up to now. Our scheme has the nice property of universal parameters. That is, each pair of R and S need neither hold any secret key nor perform any prior setup. The system parameters can be used by all senders and receivers without any trapdoor specification. Our k-out-of-n oblivious transfer scheme is the most efficient one in terms of the communication cost, in both rounds and the number of messages. Moreover, our scheme can be extended in a straightforward way to an adaptive k-out-of-n oblivious transfer scheme, which allows the receiver R to choose the secrets one by one adaptively. In our scheme, S sends O(n) messages to R in one round in the commitment phase. For each query of R, only O(1) messages are exchanged and O(1) operations (in elliptic curves) are performed. In fact, the number k of queries need not be pre-fixed or known beforehand. This makes our scheme highly flexible.
2004
EPRINT
Efficient Pairing Computation on Supersingular Abelian Varieties
We present a general technique for the efficient computation of pairings on supersingular Abelian varieties. This formulation, which we call the eta pairing, generalises results of Duursma and Lee for computing the Tate pairing on supersingular elliptic curves in characteristic three. We then show how our general technique leads to a new algorithm which is about twice as fast as the Duursma-Lee method. These ideas are then used for elliptic and hyperelliptic curves in characteristic 2 with very efficient results. In particular, the hyperelliptic case is faster than all previously known pairing algorithms.
2004
EPRINT
Efficient Selective-ID Secure Identity Based Encryption Without Random Oracles
We construct two efficient Identity Based Encryption (IBE) systems that are selective identity secure {\em without the random oracle model} in groups equipped with a bilinear map. Selective identity secure IBE is a slightly weaker security model than the standard security model for IBE. In this model the adversary must commit ahead of time to the identity that it intends to attack, whereas in the standard model the adversary is allowed to choose this identity adaptively. The first system is based on the decisional bilinear Diffie-Hellman assumption, and extends to give a selective identity Hierarchical IBE secure without random oracles. The second system is based on a related assumption called the bilinear Diffie-Hellman inversion assumption. Applications of either system include an efficient CCA2 public key cryptosystem that supports non-interactive threshold decryption in the standard model, and a simple and practical IBE system that remains secure against full adaptive-ID attacks, under some security penalty, without random oracles.
2004
EPRINT
Efficient Tate Pairing Computation for Supersingular Elliptic Curves over Binary Fields
We present a closed formula for the Tate pairing computation for supersingular elliptic curves defined over the binary field F_{2^m} of odd dimension. There are exactly three isomorphism classes of supersingular elliptic curves over F_{2^m} for odd m and our result is applicable to all these curves. Moreover we show that our algorithm and also the Duursma-Lee algorithm can be modified to another algorithm which does not need any inverse Frobenius operation (square root or cube root extractions) without sacrificing any of the computational merits of the original algorithm. Since the computation of the inverse Frobenius map is not at all trivial in a polynomial basis and since a polynomial basis is still a preferred choice for the Tate pairing computation in many situations, this new algorithm avoiding the inverse Frobenius operation has some advantage over the existing algorithms.
2004
EPRINT
Efficient Universal Padding Schemes for Multiplicative Trapdoor One-way Permutation
Coron et al. proposed the ES-based scheme PSS-ES which realizes an encryption scheme and a signature scheme with a unique padding scheme and key pair. The security of PSS-ES as an encryption scheme is based on the \textit{partial-domain one-wayness} of the encryption permutation. In this paper, we propose new ES schemes OAEP-ES, OAEP++-ES, and REACT-ES, and prove their security under the assumption of \textit{only} the \textit{one-wayness} of encryption permutation. OAEP-ES, OAEP++-ES, and REACT-ES suit practical implementation because they use the same padding technique for encryption and for signature, and their security proof guarantees that we can prepare one key pair to realize encryption and signature in the same way as PSS-ES. Since \textit{one-wayness} is a weaker assumption than \textit{partial-domain one-wayness}, the proposed schemes offer tighter security than PSS-ES. Hence, we conclude that OAEP-ES, OAEP++-ES, and REACT-ES are more effective than PSS-ES. OAEP++-ES is the most practical approach in terms of the tightness of security and communication efficiency.
2004
EPRINT
Efficient Verifiably Encrypted Signature and Partially Blind Signature from Bilinear Pairings
Verifiably encrypted signatures are used when Alice wants to sign a message for Bob but does not want Bob to possess her signature on the message until a later date. Such signatures are used in optimistic contact signing to provide fair exchange. Partially blind signature schemes are an extension of blind signature schemes that allows a signer to sign a partially blinded message that include pre-agreed information such as expiry date or collateral conditions in unblinded form. These signatures are used in applications such as electronic cash (e-cash) where the signer requires part of the message to be of certain form. In this paper, we propose a new verifiably encrypted signature scheme and a partially blind signature scheme, both based on bilinear pairings. We analyze the security and efficiency of these schemes and show that they are more efficient than the previous schemes of their kinds.
2004
EPRINT
Elastic AES
Recently an algorithmic schema was proposed for converting any existing block cipher into one which excepts variable length inputs with the computational workload increasing in proportion to the block size. The resulting cipher is referred to as an elastic block cipher. The initial work presented immunity to certain key recovery attacks, and left open further analysis of the method and its possible instantiations. In order to provide a concrete example of an elastic block cipher, we design and implement an elastic version of the Advanced Encryption Standard (AES) cipher which accepts all block sizes in the range 128 to 255 bits. To validate the design we perform differential cryptanalysis on elastic AES which confirms that the cipher does not introduce potential differential attacks as a result of a subset of bits being omitted from each round (which is at the heart of the elastic design). We also compare the performance of software implementations of elastic AES and regular AES on variable size inputs, as a step in determining the practicality of the elastic version.
2004
EPRINT
Elastic Block Ciphers
We introduce the new concept of elastic block ciphers, symmetric-key encryption algorithms that (1) for a variable-size input do not expand the plaintext (i.e., do not require plaintext padding) and (2) adjust their computational load proportionally to the size increase. Contrary to stream ciphers, elastic block ciphers maintain the diffusion property and non-synchronicity of traditional block ciphers. Elastic block ciphers are ideal (when combined with encryption modes) for applications where length-preserving encryption is most beneficial, such as protecting variable-length database fields or network packets. We present a general algorithm for converting a traditional block cipher, such as AES, to its elastic version, and analyze the security of the resulting cipher against key recovery attacks. Our approach allows us to ``stretch'' the supported block size of a block cipher up to twice the original length, while increasing the computational load proportionally to the expanded block size. Our approach does not allow us to use the original cipher as a ``black box'' (i.e., as an ideal cipher or a pseudorandom permutation as is used in constructing modes of encryption). Nevertheless, under some reasonable conditions on the cipher's structure and its key schedule, we reduce certain key recovery attacks of the elastic version to such attacks on the fixed-size block cipher. This schema and the security reduction enable us to capitalize on secure ciphers and their already established security properties in developing elastic designs. We note that we are not aware of previous ``reduction type'' proofs of security in the area of concrete (i.e., non ``black-box'') block cipher design. Our work puts forth the notion of elasticity in block cipher design.
2004
EPRINT
Electromagnetic Side Channels of an FPGA Implementation of AES
We show how to attack an FPGA implementation of AES where all bytes are processed in parallel using differential electromagnetic analysis. We first focus on exploiting local side channels to isolate the behaviour of our targeted byte. Then, generalizing the Square attack, we describe a new way of retrieving information, mixing algebraic properties and physical observations.
2004
EPRINT
Elliptic Curve based Signcryption and its Multi-party Schemes
Signcryption is a novel public key primitive to achieve the combined functionality of authentication and confidentiality in an efficient manner. A new Elliptic Curve Cryptosystems based Signcryption which combines ECDSA and PSCE-1 is presented in the paper. The signcryption scheme is a publicly verifiable scheme which can be verified by the third party after the specific recipient removes his key information. Analysis shows that the proposed scheme is secure against the adaptive chosen ciphertext attack. The signcryption saves the communication cost at least 1.25 times and enhances computation cost 1.19 times over ECDSA-then-PSCE-1. Compared with other signcryption schemes, such as Y.Zheng??s ECSCS, the new signcryption uses a uniform elliptic curve cryptosystem platform instead of four kinds of cryptosystem components: hash function, keyed hash function, symmetric cipher and elliptic curve. While keeping high security and efficiency, the scheme can be implemented in software and hardware at low price because of above advantages. Base on the signcryption, a broadcast scheme for multiple recipients and a threshold scheme with key distributed generation for multiple senders are also proposed.
2004
EPRINT
EME*: extending EME to handle arbitrary-length messages with associated data
This work describes a mode of operation, EME*, that turns a regular block cipher into a length-preserving enciphering scheme for messages of (almost) arbitrary length. Specifically, the resulting scheme can handle any bit-length, not shorter than the block size of the underlying cipher, and it also handles associated data of arbitrary bit-length. Such a scheme can either be used directly in applications that need encryption but cannot afford length expansion, or serve as a convenient building block for higher-level modes. The mode EME* is a refinement of the EME mode of Halevi and Rogaway, and it inherits the efficiency and parallelism from the original EME.
2004
EPRINT
Entropic Security and the Encryption of High Entropy Messages
Russell and Wang (Eurocrypt 2002) recently introduced an elegant, information-theoretic notion called entropic security of encryption: they required that the cipher text leak no predicate of the plaintext (similar to semantic security (Goldwasser and Micali, JCSS 1984)) but only as long as the distribution on messages has high entropy from the adversary's point of view. They show that this notion of security can be achieved with very short keys for entropically rich message spaces. Canetti, Miccianci and Reingold (STOC, 1998) had previously constructed hash functions which satisfy a similar entropic security condition. The output of such hash function leaks no partial information about the input, provided the input has sufficiently high entropy. This paper studies entropic security in general, and its application to the encryption of high-entropy messages. (1) We elucidate the notion of entropic security. Our results apply to all entropically-secure primitives, including both encryption and hash functions. We strengthen the formulation of Canetti and Russell and Wang: we require that an entropically-secure primitive leak no function whasoever of its input, while the previous works focus only on predicates. This stronger formulation is much closer to the original notion of semantic security. We also show that entropic security is equivalent to indistinguishability on pairs of input distributions of sufficiently high entropy. This equivalence generalizes the conventional equivalence between indistinguishability and semantic security. Indistinguishability, in turn, is related to randomness extraction from non-uniform distributions. The proof of the equivalence of hiding predicates to hiding all functions is quite involved, and requires very different techniques from those of Goldwasser and Micali. (2) We use the equivalence above, and the connection to randomness extraction, to prove several new results on entropically-secure encryption. We obtain: (a) Two general frameworks for constructing entropically secure encryption schemes, one based on expander graphs and the other on XOR-universal hash functions. These schemes generalize the schemes of Russell and Wang, yielding simpler constructions and proofs as well as improved parameters. The best scheme uses a key of length k=n-t+2log(1/eps)+O(1), where eps is a measure of leakage and t is the initial min-entropy of the message. (b) Lower bounds on the key length k for entropic security and indistinguishability. In particular, we show near tightness of Russell-Wang constructions: k > n-t. (In fact, for a large class of schemes k >= n-t + log(1/eps).)
2004
EPRINT
Equivalent Keys in HFE, C$^*$, and variations
In this article, we investigate the question of equivalent keys for two $\mathcal{M}$ultivariate $\mathcal{Q}$uadratic public key schemes HFE and C$^{*--}$ and improve over a previously known result, to appear at PKC 2005. Moreover, we show a new non-trivial extension of these results to the classes HFE-, HFEv, HFEv-, and C$^{*--}$, which are cryptographically stronger variants of the original HFE and C$^*$ schemes. In particular, we are able to reduce the size of the private --- and hence the public --- key space by at least one order of magnitude. While the results are of independent interest themselves, we also see applications both in cryptanalysis and in memory efficient implementations.
2004
EPRINT
Escrow-Free Encryption Supporting Cryptographic Workflow
Since Boneh and Franklin published their seminal paper on identity based encryption (IBE) using the Weil pairing , there has been a great deal of interest in cryptographic primitives based on elliptic-curve pairings. One particularly interesting application has been to control access to data, via possibly complex policies. In this paper we continue the research in this vein. We present an encryption scheme such that the receiver of an encrypted message can only decrypt if it satisfies a particular policy chosen by the sender at the time of encryption. Unlike standard IBE, our encryption scheme is escrow free in that no key-issuing authority (or colluding set of key-issuing authorities) is able to decrypt ciphertexts itself. In addition we describe a security model for the scenario in question and provide proofs of security for our scheme (in the random oracle model).
2004
EPRINT
Evaluating elliptic curve based KEMs in the light of pairings
Several efforts have been made recently to put forward a set of cryptographic primitives for public key encryption, suitable to be standardized. In two of them (in the first place the NESSIE european evaluation project, already finished, and in the second place the standardisation bodies ISO/IEC), the methodology by Victor Shoup for hybrid encryption, known as {\em Key Encapsulation Method-Data Encapsulation Mechanism} (KEM-DEM), has been accepted. In this work we re-evaluate the elliptic curve based KEMs studied to become standards, which are called ACE-KEM, ECIES-KEM and PSEC-KEM. Their security is based on different assumptions related to the elliptic curve discrete logarithm (ECDL) problem on a random elliptic curve. First of all, we fix some inexact results claimed in the previous literature. As a consequence, the performance features of PSEC-KEM are dramatically affected. In second place, we analyse both their security properties and performance when elliptic curves with computable bilinear maps ({\em pairing curves} for short) are used. It turns out that these KEMs present a very tight security reduction to the same problem, namely the ECDH problem on such curves; moreover, one can even relate their security to the ECDL problem in certain curves with a small security loss. It is also argued that ECIES-KEM arises as the best option among these KEMs when pairing curves are used. This is remarkable, since NESSIE did not include ECIES-KEM over a random curve in its portfolio of recommended cryptographic primitives. It is concluded that for medium security level applications, which is likely the case for many embedded systems (e.g. smart cards), implementing these KEMs over pairing curves should be considered a very reasonable option.
2004
EPRINT
Experimenting with Faults, Lattices and the DSA
We present an attack on DSA smart-cards which combines physical fault injection and lattice reduction techniques. This seems to be the first (publicly reported) physical experiment allowing to concretely pull-out DSA keys out of smart-cards. We employ a particular type of fault attack known as a glitch attack, which will be used to actively modify the DSA nonce k used for generating the signature: k will be tampered with so that a number of its least significant bytes will flip to zero. Then we apply well-known lattice attacks on El Gamal-type signatures which can recover the private key, given sufficiently many signatures such that a few bits of each corresponding k are known. In practice, when one byte of each k is zeroed, 27 signatures are sufficient to disclose the private key. The more bytes of k we can reset, the fewer signatures will be required. This paper presents the theory, methodology and results of the attack as well as possible countermeasures.
2004
EPRINT
Exponential S-boxes
Exponentiation in finite fields of characteristic 2 is proposed to construct large bijective S-boxes of block ciphers. We obtain some properties of the exponential S-boxes that are related to differential, higher order differential, and linear cryptanalysis methods.
2004
EPRINT
Extending the Resynchronization Attack
Synchronous stream ciphers need perfect synchronization between sender and receiver. In practical applications, this is ensured by a resync mechanism. Daemen et al first described attacks on ciphers using such a resync mechanism. In this paper, we extend their attacks in several ways by combining the standard attack with several cryptanalytic techniques such as algebraic attacks and linear cryptanalysis. Our results show that using linear resync mechanisms should be avoided, and give lower bounds for the nonlinearity required from a secure resync mechanism.
2004
EPRINT
Externalized Fingerprint Matching
The 9/11 tragedy triggered an increased interest in biometric passports. According to several sources \cite{sp2}, the electronic ID market is expected to increase by more than 50\% {\sl per annum} over the three coming years, excluding China. \smallskip To cost-effectively address this foreseen explosion, a very inexpensive memory card (phonecard-like card) capable of performing fingerprint matching is paramount.\smallskip This paper presents such a solution. The proposed protocol is based on the following idea: the card stores the user's fingerprint information to which random minutiae were added at enrolment time (we denote this scrambled template by $t$). The card also stores a binary string $w$ encoding which of the minutiae in $t$ actually belong to the holder. When an identification session starts, the terminal reads $t$ from the card and, based upon the incoming scanner data, determines which of the minutiae in $t$ are genuine. The terminal forms a candidate $w'$ and sends it to the card. All the card needs to do is test that the Hamming weight of $w \oplus w'$ is smaller than a security threshold $d$. \smallskip It follows that the card only needs to embark passive data storage capabilities, one exclusive-or gate, a shift register, a counter and a comparator (less than 40 logical gates).
2004
EPRINT
Fast addition on non-hyperelliptic genus $3$ curves
We present a fast addition algorithm in the Jacobian of a genus $3$ non-hyperelliptic curve over a field of any characteristic. When the curve has a rational flex and $\textrm{char}(k) > 5$, the computational cost for addition is $148M+15SQ+2I$ and $165M+20SQ+2I$ for doubling. An appendix focuses on the computation of flexes in all characteristics. For large odd $q$, we also show that the set of rational points of a non-hyperelliptic curve of genus $3$ can not be an arc.
2004
EPRINT
Fast and Proven Secure Blind Identity-Based Signcryption from Pairings
We present the first blind identity-based signcryption (BIBSC). We formulate its security model and define the security notions of blindness and parallel one-more unforgeability (p1m-uf). We present an efficient construction from pairings, then prove a security theorem that reduces its p1m-uf to Schnorr??s ROS Problem in the random oracle model plus the generic group and pairing model. The latter model is an extension of the generic group model to add support for pairings, which we introduce in this paper. In the process, we also introduce a new security model for (non-blind) identity-based signcryption (IBSC) which is a strengthening of Boyen??s. We construct the first IBSC scheme proven secure in the strenghened model which is also the fastest (resp. shortest) IBSC in this model or Boyen??s model. The shortcomings of several existing IBSC schemes in the strenghened model are shown.
2004
EPRINT
Fast Pseudo-Hadamard Transforms
We prove that the fast pseudo-Hadamard transform (FPHT) over a finite field has a bounded branch number. We shall demonstrate that the transform has an efficient implementation for various platforms compared to an equal dimension MDS code. We prove that when using a CS-Cipher\cite{CSC} like construction the weight of any $2R$ trail is bounded for the case of an $8 \times 8$ transform. We show that the FPHT can also be combined with MDS codes to produce efficient transforms with half of the branch of a comparable sized MDS code. We present the FPHT-HASH one-way hash function which is constructed using a $32 \times 32$ FPHT which produces a $256$-bit digest and processes the input at 24 cycles per byte with ISO C source code on an AMD Athlon XP processor.
2004
EPRINT
Fault and Side-Channel Attacks on Pairing Based Cryptography
Current side-channel analytic attacks against public key cryptography focus on traditional schemes such as RSA and ECC, and to a lesser extent primitives such as XTR. However, bilinear maps, or pairings, have presented theorists with a new and increasingly popular way of constructing cryptographic protocols. Most notably, this has resulted in efficient methods for Identity Based Encryption (IBE). Since identity based cryptography seems an ideal partner for identity aware devices such as smart-cards, in this paper we examine the security of concrete pairing instantiations in terms of side-channel analysis.
2004
EPRINT
Fault attack on the DVB Common Scrambling Algorithm
The Common Scrambling Algorithm (CSA) is used to encrypt streams of video data in the Digital Video Broadcasting (DVB) system. The algorithm uses a combination of a stream and a block cipher, apparently for a larger security margin. However these two algorithms share a common key. In this paper we present a fault attack on the block cipher which can be launched without regarding the stream cipher part. This attack allows us to reconstruct the common key and thus breaks the complete Algorithm.
2004
EPRINT
Finding good differential patterns for attacks on SHA-1
In this paper we describe a method of finding differential patterns that may be used to attack reduced versions of SHA-1. We show that the problem of finding optimal differential patterns for SHA-1 is equivalent to the problem of finding minimal weight codeword in a linear code. Finally, we present a number of patterns of different lengths suitable for finding collisions and near-collisions and discuss some bounds on minimal weights of them.
2004
EPRINT
Finding Optimum Parallel Coprocessor Design for Genus 2 Hyperelliptic Curve Cryptosystems
Hardware accelerators are often used in cryptographic applications for speeding up the highly arithmetic-intensive public-key primitives, e.g. in high-end smart cards. One of these emerging and very promising public-key scheme is based on HyperElliptic Curve Cryptosystems (HECC). In the open literature only a few considerations deal with hardware implementation issues of HECC. Our contribution appears to be the first one to propose architectures for the latest findings in efficient group arithmetic on HEC. The group operation of HECC allows parallelization at different levels: bit-level parallelization (via different digit-sizes in multipliers) and arithmetic operation-level parallelization (via replicated multipliers). We investigate the trade-offs between both parallelization options and identify speed and time-area optimized configurations. We found that a coprocessor using a single multiplier (D = 8) instead of two or more is best suited. This coprocessor is able to compute group addition and doubling in 479 and 334 clock cycles, respectively. Providing more resources it is possible to achieve 288 and 248 clock cycles, respectively.
2004
EPRINT
Forgery Attacks on Chang et al.'s signature scheme with message recovery
It is found that Chang et al.'s signature scheme with message recovery is not as secure as they claimed, in fact. In this letter, two forgery attacks is proposed to show that the signature can be forged on any uncontrolled messages. To overcome these attacks, the one-way hash functions and the message redundancy schemes may be still used.
2004
EPRINT
Foundations of Group Signatures: The Case of Dynamic Groups
A first step toward establishing foundations for group signatures was taken by Bellare, Micciancio and Warinschi (Eurocrypt 2003) with a treatment of the case where the group is static. However the bulk of existing practical schemes and applications are for dynamic groups, and these involve important new elements and security issues. This paper treats this case, providing foundations for dynamic group signatures, in the form of a model, strong formal definitions of security, and a construction proven secure under general assumptions. We believe this is an important and useful step because it helps bridge the gap between Bellare Micciancio and Warinschi and the previous practical work, and delivers a basis on which existing practical schemes may in future be evaluated or proven secure.
2004
EPRINT
FRMAC, a Fast Randomized Message Authentication Code
We revisit the randomized approach followed in the design of the RMAC message authentication code in order to construct a MAC with similar properties, but based on Wegman-Carter's $\varepsilon$-universal hash families instead of a classical CBC chain. This yields a new message authentication code called FRMAC whose security bounds are, as in RMAC, beyond the birthday paradox limit. With efficient hash functions in software, the performance of FRMAC for large messages is similar to those of the fastest previously known schemes. FRMAC can also be more efficient for small messages. Furthermore, due to relaxed requirements about the nonces in the security proof, the implementation of FRMAC in real applications tends to be easier.
2004
EPRINT
Fuzzy Identity Based Encryption
We introduce a new type of Identity-Based Encryption (IBE) scheme that we call Fuzzy Identity-Based Encryption. In Fuzzy IBE we view an identity as set of descriptive attributes. A Fuzzy IBE scheme allows for a private key for an identity, $\omega$, to decrypt a ciphertext encrypted with an identity, $\omega'$, if and only if the identities $\omega$ and $\omega'$ are close to each other as measured by the ``set overlap'' distance metric. A Fuzzy IBE scheme can be applied to enable encryption using biometric inputs as identities; the error-tolerance property of a Fuzzy IBE scheme is precisely what allows for the use of biometric identities, which inherently will have some noise each time they are sampled. Additionally, we show that Fuzzy-IBE can be used for a type of application that we term ``attribute-based encryption''. In this paper we present two constructions of Fuzzy IBE schemes. Our constructions can be viewed as an Identity-Based Encryption of a message under several attributes that compose a (fuzzy) identity. Our IBE schemes are both error-tolerant and secure against collusion attacks. Additionally, our basic construction does not use random oracles. We prove the security of our schemes under the Selective-ID security model.
2004
EPRINT
Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions
We investigate the average case complexity of a generalization of the compact knapsack problem to arbitrary rings: given $m$ (random) ring elements a_1,...,a_m in R and a (random) target value b in R, find coefficients x_1,...,x_m in S (where S is an appropriately chosen subset of R) such that a_1*x_1 + ... + a_m*x_m = b. We consider compact versions of the generalized knapsack where the set S is large and the number of weights m is small. Most variants of this problem considered in the past (e.g., when R = Z is the ring of the integers) can be easily solved in polynomial time even in the worst case. We propose a new choice of the ring R and subset S that yields generalized compact knapsacks that are seemingly very hard to solve on the average, even for very small values of m. Namely, we prove that for any unbounded function m = omega(1) with arbitrarily slow growth rate, solving our generalized compact knapsack problems on the average is at least as hard as the worst-case instance of various approximation problems over cyclic lattices. Specific worst-case lattice problems considered in this paper are the shortest independent vector problem SIVP and the guaranteed distance decoding problem GDD (a variant of the closest vector problem, CVP) for approximation factors n^{1+epsilon} almost linear in the dimension of the lattice. Our results yield very efficient and provably secure one-way functions (based on worst-case complexity assumptions) with key size and time complexity almost linear in the security parameter n. Previous constructions with similar security guarantees required quadratic key size and computation time. Our results can also be formulated as a connection between the worst-case and average-case complexity of various lattice problems over cyclic and quasi-cyclic lattices.
2004
EPRINT
Generalizing Kedlaya's order counting based on Miura Theory
K. Kedlaya proposed an method to count the number of ${\mathbb F}_q$-rational points in a hyper-elliptic curve, using the Leschetz fixed points formula in Monsky-Washinitzer Cohomology. The method has been extended to super-elliptic curves (Gaudry and G\"{u}rel) immediately, to characteristic two hyper-elliptic curves, and to $C_{ab}$ curves (J. Denef, F. Vercauteren). Based on Miura theory, which is associated with how a curve is expressed as an affine variety, this paper applies Kedlaya's method to so-called strongly telescopic curves which are no longer plane curves and contain super-elliptic curves as special cases.
2004
EPRINT
Generating more MNT elliptic curves
In their seminal paper, Miyaji, Nakabayashi and Takano~\cite{miyaji-nakabayashi-takano} describe a simple method for the creation of elliptic curves of prime order with embedding degree 3, 4, or 6. Such curves are important for the realisation of pairing-based cryptosystems on ordinary (non-supersingular) elliptic curves. We provide an alternative derivation of their results, and extend them to allow for the generation of many more suitable curves.
2004
EPRINT
Generation of random Picard curves for cryptography
Based on ideas in an earlier paper by Mark Bauer, Edlyn Teske and myself and ideas of Pierrick Gaudry and Eric Schost, we present an algorithm for counting the number of elements in the Jacobian of a random Picard curve over a finite prime field of cryptosize. We give two examples of curves with a Jacobian of prime group order.
2004
EPRINT
Geometric Key Establishment
We propose a new class of key establishment schemes which are based on geometric generalizations of the classical Diffie-Hellman. The simplest of our schemes ? based on the geometry of the unit circle ? uses only multiplication of rational numbers by integers and addition of rational numbers in its key creation. Its first computer implementation works significantly faster than all known implementations of Diffie-Hellman. Preliminary estimations show that our schemes are resistant to attacks. This resistance follows the pattern of the discrete logarithm problem and hardness of multidimensional lattice problems
2004
EPRINT
GNFS Factoring Statistics of RSA-100, 110, ..., 150
GNFS (general number field sieve) algorithm is currently the fastest known algorithm for factoring large integers. Up to the present, several running time estimates for GNFS are announced. These estimates are usually based on the previous factoring results. However, since the previous factoring results were done by various programs and/or computers, it is difficult to compare those running time. We implemented GNFS and factored 100- to 150-digits number on the same environment. This manuscript describes the statistics of these factorings.
2004
EPRINT
Grey Box Implementation of Block Ciphers Preserving the Confidentiality of their Design
In 1997,Patarin and Goubin introduce new asymmetric cryptosystems based on the difficulty of recovering two systems of multivariate polynomials from their composition. We make a different use of this difficult algorithmic problem to obtain a way of representing block ciphers concealing their design but still leaving them executable. We show how to implement our solution with Field Programmable Gate Array. Finally, we give a compact representation of our solution using Binary Decision Diagrams.
2004
EPRINT
Group Signatures: Provable Security, Efficient Constructions and Anonymity from Trapdoor-Holders
To date, a group signature construction which is efficient, scalable, allows dynamic adversarial joins, and proven secure in a formal model has not been suggested. In this work we give the first such construction in the random oracle model. The demonstration of an efficient construction proven secure in a formal model that captures all intuitive security properties of a certain primitive is a basic goal in cryptographic design. To this end we adapt a formal model for group signatures capturing all the basic requirements that have been identified as desirable in the area and we construct an efficient scheme and prove its security. Our construction is based on the Strong-RSA assumption (as in the work of Ateniese et al.). In our system, due to the requirements of provable security in a formal model, we give novel constructions as well as innovative extensions of the underlying mathematical requirements and properties. Our task, in fact, requires the investigation of some basic number-theoretic techniques for arguing security over the group of quadratic residues modulo a composite when its factorization is known. Along the way we discover that in the basic construction, anonymity does not depend on factoring-based assumptions, which, in turn, allows the natural separation of user join management and anonymity revocation authorities. Anonymity can, in turn, be shown even against an adversary controlling the join manager.
2004
EPRINT
Hardness amplification of weakly verifiable puzzles
Is it harder to solve many puzzles than it is to solve just one? This question has different answers, depending on how you define puzzles. For the case of inverting one-way functions it was shown by Yao that solving many independent instances simultaneously is indeed harder than solving a single instance (cf. the transformation from weak to strong one-way functions). The known proofs of that result, however, use in an essential way the fact that for one-way functions, verifying candidate solutions to a given puzzle is easy. We extend this result to the case where solutions are efficiently verifiable only by the party that generated the puzzle. We call such puzzles weakly verifiable. That is, for weakly verifiable puzzles we show that if no efficient algorithm can solve a single puzzle with probability more than $\eps$, then no efficient algorithm can solve $n$ independent puzzles simultaneously with probability more than $\eps^n$. We also demonstrate that when the puzzles are not even weakly verifiable, solving many puzzles may be no harder than solving a single one. Hardness amplification of weakly verifiable puzzles turns out to be closely related to the reduction of soundness error under parallel repetition in computationally sound arguments. Indeed, the proof of Bellare, Impagliazzo and Naor that parallel repetition reduces soundness error in three-round argument systems implies a result similar to our first result, albeit with considerably worse parameters. Also, our second result is an adaptation of their proof that parallel repetition of four-round systems may not reduce the soundness error.
2004
EPRINT
Hardware and Software Normal Basis Arithmetic for Pairing Based Cryptography in Characteristic Three
Although identity based cryptography offers a number of functional advantages over conventional public key methods, the computational costs are significantly greater. The dominant part of this cost is the Tate pairing which, in characteristic three, is best computed using the algorithm of Duursma and Lee. However, in hardware and constrained environments this algorithm is unattractive since it requires online computation of cube roots or enough storage space to pre-compute required results. We examine the use of normal basis arithmetic in characteristic three in an attempt to get the best of both worlds: an efficient method for computing the Tate pairing that requires no pre-computation and that may also be implemented in hardware to accelerate devices such as smart-cards. Since normal basis arithmetic in characteristic three has not received much attention before, we also discuss the construction of suitable bases and associated curve parameterisations.
2004
EPRINT
HENKOS Stream Cipher
The purpose of this paper is to revise the HENKOS Stream Cipher paper present in the archive at 2004/080 and to provide a clear description of the proposed HENKOS cryptographic algorithm.
2004
EPRINT
Hierarchical Group Signatures
We introduce the notion of \emph{hierarchical group signatures}. This is a proper generalization of group signatures, which allows multiple group managers organized in a tree with the signers as leaves. For a signer that is a leaf of the subtree of a group manager, the group manager learns which of its children that (perhaps indirectly) manages the signer. We provide definitions for the new notion and construct a scheme that is provably secure given the existence of a family of trapdoor permutations. We also present a construction which is relatively practical, and prove its security in the random oracle model under the strong RSA assumption and the DDH assumption.
2004
EPRINT
How to Cheat at Chess: A Security Analysis of the Internet Chess Club
The Internet Chess Club (ICC) is a popular online chess server with more than 30,000 members worldwide including various celebrities and the best chess players in the world. Although the ICC website assures its users that the security protocol used between client and server provides sufficient security for sensitive information to be transmitted (such as credit card numbers), we show this is not true. In particular we show how a passive adversary can easily read all communications with a trivial amount of computation, and how an active adversary can gain virtually unlimited powers over an ICC user. We also show simple methods for defeating the timestamping mechanism used by ICC. For each problem we uncover, we suggest repairs. Most of these are practical and inexpensive.
2004
EPRINT
How to Disembed a Program?
This paper presents the theoretical blueprint of a new secure token called the Externalized Microprocessor (XmP). Unlike a smart-card, the XmP contains no ROM at all. While exporting all the device's executable code to potentially untrustworthy terminals poses formidable security problems, the advantages of ROM-less secure tokens are numerous: chip masking time disappears, bug patching becomes a mere terminal update and hence does not imply any roll-out of cards in the field. Most importantly, code size ceases to be a limiting factor. This is particularly significant given the steady increase in on-board software complexity. After describing the machine's instruction-set we will introduce two XmP variants. The first design is a public-key oriented architecture which relies on a new RSA screening scheme and features a relatively low communication overhead at the cost of computational complexity, whereas the second variant is secret-key oriented and relies on simple MACs and hash functions but requires more communication. For each of these two designs, we propose two protocols that execute and dynamically authenticate arbitrary programs. We also provide a strong security model for these protocols and prove their security under appropriate complexity assumptions.
2004
EPRINT
How To Re-initialize a Hash Chain
Hash Chains are used extensively in various cryptographic systems such as one-time passwords, server supported signatures, secure address resolution, certificate revocation, micropayments etc. However, currently they suffer from the limitation that they have a finite number of links which when exhausted requires the system to be re-initialized. In this paper, we present a new kind of hash chain which we call a Re-initializable Hash Chain (RHC). A RHC has the property that if its links are exhausted, it can be securely re-initialized in a non-repudiable manner to result in another RHC. This process can be continued indefinitely to give rise to an infinite length hash chain, or more precisely, an infinite number of finite length hash chains tied together. Finally we illustrate how a conventional hash chain (CHC) may be profitable replaced with a RHC in cryptographic systems.
2004
EPRINT
Hybrid Cryptography
This paper examines the methods in which the ideas behind a KEM--DEM hybrid encryption scheme can be extended to other types of asymmetric primitives, particularly to signcryption schemes. The central principle is a keyed symmetric algorithm can be used to provide a security service for in an asymmetric algorithm provided that that symmetric primitive is under the control of the asymmetric part of the cipher (say, if asymmetric techniques are used to generate the key that the symmetric primitive uses). This theory is applied to signcryption schemes with outsider security and an efficient, provably secure scheme, termed ECISS-KEM, is proposed. The theory is also applied to signature schemes, where it is shown that efficient hybrid signature schemes can never exist, and to signcryption schemes with insider security, where it is shown that several existing schemes can be considered hybrid signcryption schemes.
2004
EPRINT
ID-based Cryptography from Composite Degree Residuosity
We present identity-based identification (resp. encryption, signature, blind signature,ring signature) from composite degree residuosity (CDR). Constructions of identifications and signatures motivated by several existing CDR-based bandwidth-efficient encryption schemes are presented. Their securities are proven equivalent to famous hard problems, in the random oracle model. Motivated by Cocks,we construct an identity-based encryption from CDR. Its security is proven equivalent to a new problem, the JSR (Jacobi Symbol of Roots of two quadratic polynomials) Problem. We prove JSR is at least as hard as QRP (Quadratic Residuosity Problem). Furthermore, we present the first two-way equivalence reduction of the security of Cocks' IBE, to the JSR Problem.
2004
EPRINT
ID-Based Encryption for Complex Hierarchies with Applications to Forward Security and Broadcast Encryption
A forward-secure encryption scheme protects secret keys from exposure by evolving the keys with time. Forward security has several unique requirements in Hierarchical Identity-Based Encryption (HIBE) scheme: (1) users join dynamically; (2) encryption is joining-time-oblivious; (3) users evolve secret keys autonomously. We present a scalable forward-secure HIBE scheme satisfying the above properties. Note that a naive combination of Gentry-Silverberg HIBE scheme with the forward-secure Public-Key Encryption scheme by Canetti, Halevi and Katz would not meet the requirements. We also show how our fs-HIBE scheme can be used to construct a forward-secure public-key Broadcast Encryption scheme, which protects the secrecy of prior transmissions in the Broadcast Encryption setting. We further generalize fs-HIBE into a collusion-resistant Multiple Hierarchical ID-Based Encryption scheme, which can be used for secure communications with entities having multiple roles in Role-Based Access Control. The security of our schemes is based on the Bilinear Diffie-Hellman assumption in the random oracle model.
2004
EPRINT
ID-Based Proxy Signature Using Bilinear Pairings
Identity-based (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. A proxy signature scheme permits an entity to delegate its signing rights to another entity. But to date, no ID-based proxy signature schemes with provable security have been proposed. In this paper, we formalize a notion of security for ID-based proxy signature schemes and propose a scheme based on the bilinear pairings. We show that the security of our scheme is tightly related to the computational Diffie-Hellman assumption in the random oracle model.
2004
EPRINT
ID-based Ring Signature and Proxy Ring Signature Schemes from Bilinear Pairings
n 2001, Rivest et al. firstly introduced the concept of ring signatures. A ring signature is a simplified group signature without any manager. It protects the anonymity of a signer. The first scheme proposed by Rivest et al. was based on RSA cryptosystem and certificate based public key setting. The first ring signature scheme based on DLP was proposed by Abe, Ohkubo, and Suzuki. Their scheme is also based on the general certificate-based public key setting too. In 2002, Zhang and Kim proposed a new ID-based ring signature scheme using pairings. Later Lin and Wu proposed a more efficient ID-based ring signature scheme. Both these schemes have some inconsistency in computational aspect. In this paper we propose a new ID-based ring signature scheme and a proxy ring signature scheme. Both the schemes are more efficient than existing one. These schemes also take care of the inconsistencies in above two schemes.
2004
EPRINT
Identity Based Threshold Proxy Signature
Identity-based (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 a $(t,n)$ threshold proxy signature scheme, the original signer delegates the power of signing messages to a designated proxy group of $n$ members. Any $t$ or more proxy signers of the group can cooperatively issue a proxy signature on behalf of the original signer, but $t-1$ or less proxy signers cannot. In this paper, we present an ID-based threshold proxy signature scheme using bilinear pairings. We show the scheme satisfies all security requirements in the random oracle model. To the best of authors' knowledge, our scheme is the first ID-based threshold proxy signature scheme.
2004
EPRINT
Identity Based Threshold Ring Signature
In threshold ring signature schemes, any group of $t$ entities spontaneously conscripting arbitrarily $n-t$ entities to generate a publicly verifiable $t$-out-of-$n$ signature on behalf of the whole group, yet the actual signers remain anonymous. The spontaneity of these schemes is desirable for ad-hoc groups such as mobile ad-hoc networks. In this paper, we present an identity based (ID-based) threshold ring signature scheme. The scheme is provably secure in the random oracle model and provides trusted authority compatibility. To the best of authors' knowledge, our scheme is the first ID-based threshold ring signature scheme which is also the most efficient (in terms of number of pairing operations required) ID-based ring signature scheme (when $t = 1$) and threshold ring signature scheme from pairings.
2004
EPRINT
Identity-Based Hierarchical Strongly Key-Insulated Encryption and Its Application
In this paper, we discuss non-interactive updating of decryption keys in identity-based encryption (IBE). IBE is a public key cryptosystem where a public key is an arbitrary string. In practice, key revocation is a necessary and inevitable process and IBE is no exception when it comes to having to manage revocation of decryption keys without losing its merits in efficiency. Our main contribution of this paper is to propose novel constructions of IBE where the decryption key can be renewed without having to make changes to its public key, i.e. user's identity. We achieve this by tactfully extending the hierarchical IBE (HIBE). Regarding security, we address semantic security against adaptive chosen cipher-text attack for a very strong attack environment that models all possible types of key exposures in the random oracle model. Straightforward extension of the HIBE, however, does not achieve our goal and such scheme is completely insecure under our attack model. In addition to this, we show method of constructing (partially collusion resistant) HIBE from arbitrary IBE in the random oracle model. By combining these results, we can construct an IBE with non-interactive key update from only an arbitrary IBE.
2004
EPRINT
Improved Efficiency for CCA-Secure Cryptosystems Built Using Identity-Based Encryption
Recently, Canetti, Halevi, and Katz showed a general method for constructing CCA-secure encryption schemes from identity-based encryption schemes in the standard model. We improve the efficiency of their construction, and show two specific instantiations of our resulting scheme which offer the most efficient encryption (and, in one case, key generation) of any CCA-secure encryption scheme to date.
2004
EPRINT
Improved Identity-Based Signcryption
We present an identity-based signcryption scheme that we believe is the most efficient proposed to date. We provide random oracle model~\cite{ROP} proofs of security under the definitions proposed in~\cite{MIBS}
2004
EPRINT
Improvement of Th?Leriault Algorithm of Index Calculus for Jacobian of Hyperelliptic Curves of Small Genus
Gaudry present a variation of index calculus attack for solving the DLP in the Jacobian of hyperelliptic curves. Harley and Th?Lerialut improve these kind of algorithm. Here, we will present a variation of these kind of algorithm, which is faster than previous ones. Its complexity is $O(2-\frac{2}{g}+\epsilon)$. Recently, P. Gaudry and E. Thom'e http://eprint.iacr.org/2004/153/ present the algorithm, whose complexity is same as our results. So I submit my manuscript to this eprint archive.
2004
EPRINT
Improving the algebraic immunity of resilient and nonlinear functions and constructing bent functions
The currently known constructions of Boolean functions with high nonlinearities, high algebraic degrees and high resiliency orders do not seem to permit achieving sufficiently high algebraic immunities. We introduce a construction of Boolean functions, which builds a new function from three known ones. Assuming that the three functions have some resiliency order, nonlinearity and algebraic degree, as well as their sum modulo 2, the constructed function has the same resiliency order and can have the same nonlinearity, but has potentially better algebraic degree and algebraic immunity. The set of classical constructions together with this new one (and with a simpler derived one, having the same advantages) permit now to obtain functions achieving all necessary criteria for being used in the pseudo-random generators in stream ciphers.\\ We also apply this construction to obtain bent functions from known ones.
2004
EPRINT
Index calculus for abelian varieties and the elliptic curve discrete logarithm problem
We propose an index calculus algorithm for the discrete logarithm problem on general abelian varieties. The main difference with the previous approaches is that we do not make use of any embedding into the Jacobian of a well-suited curve. We apply this algorithm to the Weil restriction of elliptic curves and hyperelliptic curves over small degree extension fields. In particular, our attack can solve all elliptic curve discrete logarithm problems defined over $GF(q^3)$ in time $O(q^{10/7})$, with a reasonably small constant; and an elliptic problem over $GF(q^4)$ or a genus 2 problem over $GF(p^2)$ in time $O(q^{14/9})$ with a larger constant.
2004
EPRINT
Inversion-Free Arithmetic on Genus 3 Hyperelliptic Curves
Hyperelliptic curve cryptosystem (HECC) is becoming more and more promising for network security applications because of the common effort of several academic and industrial organizations. With short operand size compared to other public key cryptosystems, HECC has showed excellent performance in embedded processors. Recently years, many effort has been made to investigate all kinds of explicit formulae for speeding up group operation of HECC. In this paper, explicit formulae without using inversion for genus 3 HECC are given. We introduce a further coordinate to collect the common denominator of the usual 6 coordinates. The proposed formulae can be used in smart card where inversion is much more expensive than multiplication.
2004
EPRINT
Key Recovery Method for CRT Implementation of RSA
This paper analyzes a key recovery method for RSA signature generation or decryption implementations using the Chinese Remainder Theorem (CRT) speed up. The CRT-based RSA implementation is common in both low computing power devices and high speed cryptographic acceleration cards. This recovery method is designed to work in conjunction with a side-channel attack where the CRT exponents are discovered from a message decryption or signature generation operation, the public exponent is assumed small and the public modulus is unknown. Since many RSA implementations use the small, low hamming weight public exponent 65537 this turns out to be a realistic method. An algorithm for recovering the private key, modulus and prime factorization candidates is presented with a proof of correctness. Runtime estimates and sample source code is given.
2004
EPRINT
Known-Plaintext Attack Against a Permutation Based Video
One of the approaches to deliver real-time video encryption is to apply permutations to the bytes within a frame of a fully encoded MPEG stream as presented in [2]. We demonstrate that this particular algorithm is vulnerable to a known-plaintext attack, and hence its use should be carefully considered. We also discuss modifications that can make the algorithm resistant to our attack.
2004
EPRINT
Linkable Spontaneous Anonymous Group Signature for Ad Hoc Groups
We present a linkable spontaneously anonymous group (LSAG) signature scheme (alternatively known as linkable ring signature scheme) satisfying the following three properties. (1) Anonymity, or signer indistinguishability. (2) Linkability: That two signatures by the same signer can be linked. (3) Spontaneity: No group secret, therefore no group manager or group secret sharing setup. We reduce the security of our scheme to well-known problems under the random oracle model. Using the scheme, we construct a new efficient one-round e-voting system which does not have a registration phase. We also present a new efficient reduction of famous rewind simulation lemma which only relies on elementary probability theory. Threshold extensions of our scheme are also presented.
2004
EPRINT
Long Modular Multiplication for Cryptographic Applications
A digit-serial, multiplier-accumulator based cryptographic co-processor architecture is proposed, similar to fix-point DSP's with enhancements, supporting long modular arithmetic and general computations. Several new ?column-sum? variants of popular quadratic time modular multiplication algorithms are presented (Montgomery and interleaved division-reduction with or without Quisquater scaling), which are faster than the traditional implemen-tations, need no or very little memory beyond the operand storage and perform squaring about twice faster than general multiplications or modular reductions. They provide similar advantages in software for general purpose CPU's.
2004
EPRINT
Lower Bounds and Impossibility Results for Concurrent Self Composition
In the setting of concurrent self composition, a single protocol is executed many times concurrently by a single set of parties. In this paper, we prove lower bounds and impossibility results for secure protocols in this setting. First and foremost, we prove that there exist large classes of functionalities that {\em cannot} be securely computed under concurrent self composition, by any protocol. We also prove a {\em communication complexity} lower bound on protocols that securely compute a large class of functionalities in this setting. Specifically, we show that any protocol that computes a functionality from this class and remains secure for $m$ concurrent executions, must have bandwidth of at least $m$ bits. The above results are unconditional and hold for any type of simulation (i.e., even for non-black-box simulation). In addition, we prove a severe lower bound on protocols that are proven secure using black-box simulation. Specifically, we show that any protocol that computes the blind signature or oblivious transfer functionalities and remains secure for $m$ concurrent executions, where security is proven via {\em black-box simulation}, must have at least $m$ rounds of communication. Our results hold for the plain model, where no trusted setup phase is assumed. While proving our impossibility results, we also show that for many functionalities, security under concurrent {\em self} composition (where a single secure protocol is run many times) is actually equivalent to the seemingly more stringent requirement of security under concurrent {\em general} composition (where a secure protocol is run concurrently with other arbitrary protocols). This observation has significance beyond the impossibility results that are derived by it for concurrent self composition.
2004
EPRINT
Lower Bounds for Non-Black-Box Zero Knowledge
We show new lower bounds and impossibility results for general (possibly *non-black-box*) zero-knowledge proofs and arguments. Our main results are that, under reasonable complexity assumptions: 1. There does not exist a two-round zero-knowledge *proof* system with perfect completeness for an NP-complete language. The previous impossibility result for two-round zero knowledge, by Goldreich and Oren (J. Cryptology, 1994) was only for the case of *auxiliary-input* zero-knowledge proofs and arguments. 2. There does not exist a constant-round zero-knowledge *strong* proof or argument of knowledge (as defined by Goldreich (2001)) for a nontrivial language. 3. There does not exist a constant-round public-coin *proof* system for a nontrivial language that is *resettable zero knowledge*. This result also extends to "bounded-resettable" zero knowledge, in which the number of resets is a priori bounded by a polynomial in the input length and prover-to-verifier communication. In contrast, we show that under reasonable assumptions, there does exist such a (computationally sound) *argument* system that is bounded-resettable zero knowledge. The complexity assumptions we use are not commonly used in cryptography. However, in all cases, we show that assumptions similar to ours are necessary for the above results. Most previously known lower bounds, such as those of Goldreich and Krawczyk (SIAM J. Computing, 1996), were only for *black-box* zero knowledge. However, a result of Barak (FOCS 2001) shows that many (or even most) of these black-box lower bounds do *not* extend to the case of general zero knowledge.
2004
EPRINT
MD5 To Be Considered Harmful Someday
Joux and Wang's multicollision attack has yielded collisions for several one-way hash algorithms. Of these, MD5 is the most problematic due to its heavy deployment, but there exists a perception that the flaws identified have no applied implications. We show that the appendability of Merkle-Damgard allows us to add any payload to the proof-of-concept hashes released by Wang et al. We then demonstrate a tool, Stripwire, that uses this capability to create two files -- one which executes an arbitrary sequence of commands, the other which hides those commands with the strength of AES -- both with the same MD5 hash. We show how this affects file-oriented system auditors such as Tripwire, but point out that the failure is nowhere near as catastrophic as it appears at first glance. We examine how this failure affects HMAC and Digital Signatures within Digital Rights Management (DRM) systems, and how the full attack expands into an unusual pseudo-steganographic strikeback methodology against peer to peer networks.
2004
EPRINT
Mobile Terminal Security
The miniaturization of electronics and recent developments in biometric and screen technologies will permit a pervasive presence of embedded systems. This - and the inclusion of networking capabilities and IP addresses in many handheld devices - will foster the widespread deployment of personal mobile equipment.\smallskip This work attempts to overview these diverse aspects of mobile device security. We will describe mobile networks' security (WLAN and WPAN security, GSM and 3GPP security) and address platform security issues such as bytecode verification for mobile equipment and protection against viruses and Trojan horses in mobile environment - with a concrete J2ME implementation example. Finally we will turn to hardware attacks and briefly survey the physical weaknesses that can be exploited to compromise mobile equipment.\smallskip
2004
EPRINT
Modified Parameter Attacks: Practical Attacks against CCA2 Secure Cryptosystems and Countermeasures
We introduce the concept of Modified Parameter Attacks, a natural extension of the idea of Adapative Chosen Ciphertext Attacks (CCA2) under which some CCA2 secure systems can be shown to be insecure. These insecurities can be addressed at the application level, but can also be addressed when cryptographic schemes are being designed. We survey some existing CCA2 secure systems which are vulnerable to this attack and suggest practical countermeasures.
2004
EPRINT
More Efficient Server Assisted One Time Signatures
Server assisted one time signature scheme was recently presented as a non-repudiation service for mobile and constrained devices. However, the scheme suffered with high storage requirements for the virtual server and high memory requirements for the mobile client. We improve the scheme by significantly reducing virtual server storage requirements as well as mobile client memory requirements. More precisely, the virtual server storage requirements in our scheme are reduced by a factor of more than 80 compared to the original scheme. Further, memory requirements for the mobile client are reduced by a factor of more than 130. This is done by generating various quantities pseudorandomly and storing just their cryptographic hash (instead of storing them fully) wherever possible, while still being able to perform dispute resolution.
2004
EPRINT
Multi-sequences with d-perfect property
Sequences with almost perfect linear complexity profile are defined by H.~Niederreiter[4]. C.P. Xing and K.Y. Lam[5, 6] extended this concept from the case of single sequences to the case of multi-sequences and furthermore proposed the concept of d-perfect. In this paper, based on the technique of m-continued fractions due to Dai et al, we investigate the property of d-perfect multi-sequences and obtain the sufficient and necessary condition on d-perfect property. We show that multi-sequences with d-perfect property are not always strongly d-perfect. In particular, we give one example to disprove the conjecture on d-perfect property of multi-sequences proposed by C.P. Xing in [6].
2004
EPRINT
Multicollision Attacks on Generalized Hash Functions
In a recent paper in crypto-04, A. Joux showed a multicollision attacks on the classical iterated hash function. He also showed how the multicollision attack can be used to get a collision attack on the concatenated hash function. In this paper we have shown that the multicollision attacks exist in a general class of sequential or tree based hash functions even if message blocks are used twice unlike the classical hash function.
2004
EPRINT
Multivariable public--key cryptosystems
Recently Landau and Diffie gave in a series of articles in the Notices of the American Mathematical Society and in the American Mathematical Monthly excellent expositions on how the theory of multivariable polynomials are used in cryptography. However they covered only half of the story. They covered only the theory of polynomials in symmetric or secret cryptography. There is another half of the story, namely the story about the theory of multivariable polynomials in asymmetric or public key cryptosystems. We give an overview of the families of public key cryptosystems, which have been developed in the last ten years.
2004
EPRINT
Musings on the Wang et al. MD5 Collision
Wang et al. caused great excitement at CRYPTO2004 when they announced a collision for MD5~\cite{R92_MD5}. This paper is examines the internal differences and conditions required for the attack to be successful. There are a large number of conditions that must be satisfied, thus indicating Wang at al. have found a clever way to generate message pairs for which the conditions are satisfied. The large number of conditions suggests that an attacker cannot use these differentials to cause second pre-image attacks with complexity less than generic attacks. Initial examination also suggests that an attacker cannot cause such collisions for HMAC-MD5 with complexity less than generic attacks.
2004
EPRINT
Near-Collisions of SHA-0
In this paper we find two near-collisions of the full compression function of SHA-0, in which up to 142 of the 160 bits of the output are equal. We also find many full collisions of 65-round reduced SHA-0, which is a large improvement to the best previous result of 35 rounds. We use the very surprising fact that the messages have many neutral bits, some of which do not affect the differences for about 15--20 rounds. We also show that 82-round SHA-0 is much weaker than the (80-round) SHA-0, although it has more rounds. This fact demonstrates that the strength of SHA-0 is not monotonous in the number of rounds.
2004
EPRINT
New Approaches to Password Authenticated Key Exchange based on RSA
We investigate efficient protocols for password-authenticated key exchange based on the RSA public-key cryptosystem. To date, most of the published protocols for password-authenticated key exchange were based on Diffie-Hellman key exchange. It appears inappropriate to design password-authenticated key exchange protocols using RSA and other public-key cryptographic techniques. In fact, many of the proposed protocols for password-authenticated key exchange based on RSA have been shown to be insecure; the only one that remains secure is the SNAPI protocol. Unfortunately, the SNAPI protocol has to use a prime public exponent $e$ larger than the RSA modulus $n$. In this paper, we present a new password-authenticated key exchange protocol, called {\em PEKEP}, which allows using both large and small prime numbers as RSA public exponents. Based on number-theoretic techniques, we show that the new protocol is secure against the $e$-{\em residue attack}, a special type of off-line dictionary attack against RSA-based password-authenticated key exchange protocols. We also provide a formal security analysis of PEKEP under the RSA assumption and the random oracle model. On the basis of PEKEP, we present a computationally-efficient key exchange protocol to mitigate the burden on communication entities.
2004
EPRINT
New Distributed Ring Signatures for General Families of Signing Subsets
In a distributed ring signature scheme, a subset of users cooperate to compute a distributed anonymous signature on a message, on behalf of a family of possible signing subsets. The receiver can verify that the signature comes from a subset of the ring, but he cannot know which subset has actually signed. In this work we use the concept of dual access structures to construct a distributed ring signature scheme which works with general families of possible signing subsets. The length of each signature is linear on the number of involved users, which is desirable for some families with many possible signing subsets. The scheme achieves the desired properties of correctness, anonymity and unforgeability. The reduction in the proof of unforgeability is tighter than the reduction in the previous proposals which work with general families. We analyze the case in which our scheme runs in an identity-based scenario, where public keys of the users can be derived from their identities. This fact avoids the necessity of digital certificates, and therefore allows more efficient implementations of such systems. But our scheme can be extended to work in more general scenarios, where users can have different types of keys.
2004
EPRINT
New GF(2n) Parallel Multiplier Using Redundant Representation
A new GF(2n) redundant representation is presented. Squaring in the representation is almost cost-free. Based on the representation, two multipliers are proposed. The XOR gate complexity of the first multiplier is lower than a recently proposed normal basis multiplier when CN (the complexity of the basis) is larger than 3n-1.
2004
EPRINT
New Monotone Span Programs from Old
In this paper we provide several known and one new constructions of new linear secret sharing schemes (LSSS) from existing ones. This constructions are well-suited for didactic purposes, which is a main goal of this paper. It is well known that LSSS are in one-to-one correspondence with monotone span programs (MSPs). MSPs introduced by Karchmer and Wigderson, can be viewed as a linear algebra model for computing a monotone function (access structure). Thus the focus is in obtaining a MSP computing the new access structure starting from the MSPs that compute the existing ones, in the way that the size of the MSP after the transformation is well defined. Next we define certain new operations on access structures and prove certain related properties.
2004
EPRINT
New Notions of Security: Achieving Universal Composability without Trusted Setup
We propose a modification to the framework of Universally Composable (UC) security [Canetti'01]. Our new notion, involves comparing the protocol executions with an ideal execution involving ideal functionalities (just as in UC-security), but allowing the environment and adversary access to some super-polynomial computational power. We argue the meaningfulness of the new notion, which in particular subsumes many of the traditional notions of security. We generalize the Universal Composition theorem of [Canetti'01] to the new setting. Then under new computational assumptions, we realize secure multi-party computation (for static adversaries) without a common reference string or any other set-up assumptions, in the new framework. This is known to be impossible under the UC framework.
2004
EPRINT
New paradigms for digital generation and post-processing of random data
A new method for digital true random number generation based on asynchronous logic circuits with feedback is introduced. In particular, a concrete technique using the so-called Fibonacci and Galois ring oscillators is developed and experimentally tested in FPGA technology. The generated random binary sequences inherently have a high speed and a very high and robust entropy rate in comparison with previous proposals for digital random number generators. A new method for digital post-processing of random data based on non-autonomous synchronous logic circuits with feedback is also introduced and a concrete technique using a self-clock-controlled linear feedback shift register is proposed. The post-processing can provide both randomness extraction and computationally secure speed increase of input random data.
2004
EPRINT
New Security Proofs for the 3GPP Confidentiality and Integrity Algorithms
This paper analyses the 3GPP confidentiality and integrity schemes adopted by Universal Mobile Telecommunication System, an emerging standard for third generation wireless communications. The schemes, known as $f8$ and $f9$, are based on the block cipher KASUMI. Although previous works claim security proofs for $f8$ and $f9'$, where $f9'$ is a generalized versions of $f9$, it was recently shown that these proofs are incorrect. Moreover, Iwata and Kurosawa (2003) showed that it is \emph{impossible} to prove $f8$ and $f9'$ secure under the standard PRP assumption on the underlying block cipher. We address this issue here, showing that it is possible to prove $f8'$ and $f9'$ secure if we make the assumption that the underlying block cipher is a secure PRP-RKA against a certain class of related-key attacks; here $f8'$ is a generalized version of $f8$. Our results clarify the assumptions necessary in order for $f8$ and $f9$ to be secure and, since no related-key attacks are known against the full eight rounds of KASUMI, lead us to believe that the confidentiality and integrity mechanisms used in real 3GPP applications are secure.
2004
EPRINT
Nominative Proxy Signature Schemes
In a nominative proxy signature scheme, an original singer delegates his signing power to a proxy, who generates a nominative signature on behalf of the original signer. In a nominative proxy signature scheme, only the nominee can verify the signature and if necessary, only the nominee can prove its validity to the third party. In this paper, we first classify the nominative proxy signature into two types, original-nominative proxy signature and proxy-nominative proxy signature. Then we analyze the nominative proxy scheme proposed by Park and Lee. We show that the scheme suffers from universal verification. We also point out that the scheme presented by S.-H. Seo and S.-H. Lee is insecure and the scheme cannot provide non-repudiation. Finally we present our nominative proxy signature schemes which overcome the weakness mentioned above. Compared with the scheme recently proposed by G.-L. Wang, our scheme is more efficient.
2004
EPRINT
Non-Interactive and Information-Theoretic Secure Publicly Verifiable Secret Sharing
A publicly verifiable secret sharing scheme is more applicable than a verifiable secret sharing because of the property that the validity of the shares distributed by the dealer can be verified by any party. In this paper, we construct a non-interactive and information-theoretic publicly verifiable secret sharing by a computationally binding and unconditionally hiding commitment scheme and zero-knowledge proof of knowledge.
2004
EPRINT
Oblivious Transfer Is Symmetric
We show that oblivious transfer of bits from $A$ to $B$ can be obtained from a single instance of the same primitive from $B$ to $A$. Our reduction is perfect and shows that oblivious transfer is in fact a symmetric functionality. This solves an open problem posed by Cr\'epeau and S\'antha in 1991.
2004
EPRINT
On a Probabilistic Approach to the Security Analysis of Cryptographic Hash Functions
In this paper we focus on the three basic security requirements for a cryptographic hash function, commonly referred as preimage, second preimage and collision resistance. We examine these security requirements in the case of attacks which do not take advantage on how the hash function is computed, expressing them as success probabilities of suitable randomized algorithms. We give exact mathematical expressions for such resistance indices, and obtain their functional behaviour in relation to the amount of uniformity in the hash function outcomes. Our work provides a mathematical framework for the study of cryptographic hash functions, which enable us to give proofs for some prevailing beliefs.
2004
EPRINT
On a Threshold Group Signature Scheme and a Fair Blind Signature Scheme
In the paper, we analyze two signature schemes. The first is a $(t_j, t, n) $ threshold group signature scheme proposed by Shi and Feng in [1]. The second is a fair blind signature scheme proposed by Feng in [2]. Our results show that both schemes are forgeable. Besides, we introduce a concept, i.e., suspended factor, to describe the common error in designing signature scheme, which means that some signature data lie at neither base position nor exponent position in verifying equation, instead lie at factor position solely .
2004
EPRINT
On a zero-knowledge property of arguments of knowledge based on secure public key encryption schemes
This paper considers a weak variant on the notion of zero-knowledge. The weak notion is compatible with the chosen ciphertext security. In fact, arguments of knowledge based on IND-CCA encryption schemes are shown to be statistical zero-knowledge in that sense.
2004
EPRINT
On Boolean Functions with Generalized Cryptographic Properties
By considering a new metric, we generalize cryptographic properties of Boolean functions such as resiliency and propagation characteristics. These new definitions result in a better understanding of the properties of Boolean functions and provide a better insight in the space defined by this metric. This approach leads to the construction of ``hand-made'' Boolean functions, i.e., functions for which the security with respect to some specific monotone sets of inputs is considered, instead of the security with respect to all possible monotone sets with the same cardinality, as in the usual definitions. This approach has the advantage that some trade-offs between important properties of Boolean functions can be relaxed.
2004
EPRINT
On Cheating Immune Secret Sharing
This work addresses the problem of cheating prevention in secret sharing. The scheme is said to be $k$-cheating immune if any group of $k$ cheaters has no advantage over honest participants. In this paper we study the constraints of cheating immune secret sharing schemes. We give a necessary and sufficient condition for SSSs to be cheating immune. Then, we improve the upper bound of D'Arco {\textit et.~al} on the number of cheaters tolerated in such scheme. Our proof is much simpler than the proof of D'Arco {\textit et.~al} and relies on certain properties of cryptographic Boolean functions. As a result of independent interest we provide a condition given function to be $t$-resilient and to satisfy the propagation criterion of degree $\ell$ over any finite field.
2004
EPRINT
On codes, matroids and secure multi-party computation from linear secret sharing schemes
Error correcting codes and matroids have been widely used in the study of ordinary secret sharing schemes. In this paper, we study the connections between codes, matroids, and a special class of secret sharing schemes: multiplicative linear secret sharing schemes. Such schemes are known to enable multi-party computation protocols secure against general (non-threshold) adversaries. Two open problems related to the complexity of multiplicative LSSSs are considered in this paper. The first one deals with strongly multiplicative LSSSs. As opposed to the case of multiplicative LSSSs, it is not known whether there is an efficient method to transform an LSSS into a strongly multiplicative LSSS for the same access structure with a polynomial increase of the complexity. We prove a property of strongly multiplicative LSSSs that could be useful in solving this problem. Namely, using a suitable generalization of the well-known Berlekamp-Welch decoder, we show that all strongly multiplicative LSSSs enable efficient reconstruction of a shared secret in the presence of malicious faults. The second one is to characterize the access structures of ideal multiplicative LSSSs. Specifically, we wonder whether all self-dual vector space access structures are in this situation. By the aforementioned connection, this in fact constitutes an open problem about matroid theory, since it can be re-stated in terms of representability of identically self-dual matroids by self-dual codes. We introduce a new concept, the flat-partition, that provides a useful classification of identically self-dual matroids. Uniform identically self-dual matroids, which are known to be representable by self-dual codes, form one of the classes. We prove that this property also holds for the family of matroids that, in a natural way, is the next class in the above classification: the identically self-dual bipartite matroids.
2004
EPRINT
On Corrective Patterns for the SHA-2 Family
The Secure Hash Standard (SHS) [3] includes hashing algorithms denoted SHA-n, (n in {224, 256, 384, 512}) for producing message digests of length n. These algorithms are based on a common design, sometimes known as SHA-2, that consists of a message schedule and a register. The most successful attacks on the SHA algorithms are Chabaud-Joux differential collisions [1, 2, 4, 5, 7], which are based on finding a corrective pattern for the register. Previous analysis of the SHA-2 algoritms [4] indicated that, for all SHA-2 algorithms, the best corrective pattern has probability 2^-66. We find that the complexity of obtaining a collision is 2^39 when the register state is unknown. Of this complexity, a factor of 2^9 corresponds to conditions on the internal state that must be satisfied, and a factor of 2^30 corresponds to 30 bits of internal state that must be guessed correctly in order to generate a collision. When the register state is known (as is the case when generating a hash) then the guessed bits are known and the complexity is reduced to 2^9. The simple analysis of the message schedule in [4] determines limits on the probability of collision for SHA-2, and was sufficient at that time to conclude that the algorithms resist the attacks. In [4] the claimed complexity is compared against the birthday attack bound of 2^n/2. However, the corrective pattern can be converted into a second pre-image attack for which the complexity should be greater than 2^n. When accounting for the complexity of 2^9 per corrective pattern, the previous analysis of the message schedule yields lower bounds on the complexities 2^27 for SHA-224/256 and 2^45 for SHA-224/256. These complexities are significantly less than the 2^n bound. It is no longer certain that SHA-2 resists this attack. More detailed analysis of the message schedule is required.
2004
EPRINT
On Multiple Linear Approximations
In this paper we study the long standing problem of information extraction from multiple linear approximations. We develop a formal statistical framework for block cipher attacks based on this technique and derive explicit and compact gain formulas for generalized versions of Matsui's Algorithm 1 and Algorithm 2. The theoretical framework allows both approaches to be treated in a unified way, and predicts significantly improved attack complexities compared to current linear attacks using a single approximation. In order to substantiate the theoretical claims, we benchmarked the attacks against reduced-round versions of DES and observed a clear reduction of the data and time complexities, in almost perfect correspondence with the predictions. The complexities are reduced by several orders of magnitude for Algorithm 1, and the significant improvement in the case of Algorithm 2 suggests that this approach may outperform the currently best attacks on the full DES algorithm.
2004
EPRINT
On Oleshchuk's Public Key Cryptosystem
This paper revisits a public key cryptosystem which is based on finite Church-Rosser string-rewriting systems. We consider some ideas for cryptanalysis and discuss issues concerning practical usage. It turns out that without changing crucial details of key generation this cryptosystem does not offer acceptable cryptographic security. We also provide the source code of our rudimentary implementation, if someone would like to use it for further cryptanalysis.
2004
EPRINT
On security of XTR public key cryptosystems against Side Channel Attacks
The XTR public key system was introduced at Crypto 2000. Application of XTR in cryptographic protocols leads to substantial savings both in communication and computational overhead without compromising security. It is regarded that XTR is suitable for a variety of environments, including low-end smart cards, and XTR is the excellent alternative to either RSA or ECC. In \cite{LV00a,SL01}, authors remarked that XTR single exponentiation (XTR-SE) is less susceptible than usual exponentiation routines to environmental attacks such as timing attacks and Differential Power Analysis (DPA). In this paper, however, we investigate the security of side channel attack (SCA) on XTR. This paper shows that XTR-SE is immune against simple power analysis (SPA) under assumption that the order of the computation of XTR-SE is carefully considered. However we show that XTR-SE is vulnerable to Data-bit DPA (DDPA)\cite{Cor99}, Address-bit DPA (ADPA)\cite{IIT02}, and doubling attack \cite{FV03}. Moreover, we propose two countermeasures that prevent from DDPA and a countermeasure against ADPA. One of the countermeasures using randomization of the base element proposed to defeat DDPA, i.e., randomization of the base element using field isomorphism, could be used to break doubling attack. Thus if we only deal with SPA, DDPA, ADPA, and doubling attack as the attack algorithm for XTR-SE, XTR-SE should be added following countermeasures: randomization of the base element using field isomorphism (DDPA and doubling attack) + randomized addressing (ADPA). But the proposed countermeasure against doubling attack is very inefficient. So to maintain the advantage of efficiency of XTR a good countermeasure against doubling attack is actually necessary.
2004
EPRINT
On Small Characteristic Algebraic Tori in Pairing-Based Cryptography
The output of the Tate pairing on an elliptic curve over a finite field may be viewed as an element of an algebraic torus. Using this simple observation, we transfer techniques recently developed for torus-based cryptography to pairing-based cryptography, resulting in more efficient computations, and lower bandwidth requirements. To illustrate the efficacy of this approach, we apply the method to pairings on supersingular elliptic curves in characteristic three.
2004
EPRINT
On the Affine Transformations of HFE-Cryptosystems and Systems with Branches
We show how to recover the affine parts of the secret key for a certain class of HFE-Cryptosystems. Further we will show that any system build on branches can be decomposed in its single branches in polynomial time on average. The first part generalizes the result from \cite{geisel} to a bigger class of systems and is achieved by a different approach. Dispite the fact that systems with branches are not used anymore (see \cite{patarin1, goubin}), our second result is a still of interest as it applies to a very general class of HFE-cryptosystems and thus is a contribution to the list of algebraic properties, which cannot be hidden by composition with the secret affine transformations. We derived both algorithms by considering the cryptosystem as objects from the theory of nonassociative algebras and applying classical techniques from this theory. This general framework might be useful for future investigations of HFE-Cryptosysstems or to generalize other attacks known so far.
2004
EPRINT
On the Ambiguity of Concurrent Signatures
We point out that the notion of {\em ambiguity} introduced in the concurrent signatures proposed by Chen, Kudla, and Paterson in Eurocrypt 2004 is incorrect. Any third party who observed two signatures can differentiate who has/have produced the signatures by performing the verification algorithm. We note that the model proposed in the paper is sound, but the concrete scheme does not really provide what is required in the model.
2004
EPRINT
On the Composition of Authenticated Byzantine Agreement
A fundamental problem of distributed computing is that of simulating a secure broadcast channel, within the setting of a point-to-point network. This problem is known as Byzantine Agreement (or Generals) and has been the focus of much research. Lamport et al. showed that in order to achieve Byzantine Agreement in the standard model, more than 2/3 of the participating parties must be honest. They further showed that by augmenting the network with a public-key infrastructure for digital signatures, it is possible to obtain protocols that are secure for any number of corrupted parties. The problem in this augmented model is called "authenticated Byzantine Agreement". In this paper we consider the question of concurrent, parallel and sequential composition of authenticated Byzantine Agreement protocols. We present surprising impossibility results showing that: * If an authenticated Byzantine Agreement protocol remains secure under parallel or concurrent composition (even for just two executions), then more than 2/3 of the participating parties must be honest. * Deterministic authenticated Byzantine Agreement protocols that run for $r$ rounds and tolerate 1/3 or more corrupted parties, can remain secure for at most $2r-1$ sequential executions. In contrast, we present randomized protocols for authenticated Byzantine Agreement that remain secure under sequential composition, for {\em any}\/ polynomial number of executions. We exhibit two such protocols. In the first protocol, the number of corrupted parties may be any number less than 1/2 (i.e., an honest majority is required). In the second protocol, any number of parties may be corrupted; however, the overall number of parties must be limited to $O(\log k/\log\log k)$, where $k$ is the security parameter (and so all parties run in time that is polynomial in $k$). Finally, we show that when the model is further augmented so that unique and common session identifiers are assigned to each concurrent session, then any polynomial number of authenticated Byzantine agreement protocols can be concurrently executed, while tolerating any number of corrupted parties.
2004
EPRINT
ON THE DEGREE OF HOMOGENEOUS BENT FUNCTIONS
It is well known that the degree of a $2m$-variable bent function is at most $m.$ However, the case in homogeneous bent functions is not clear. In this paper, it is proved that there is no homogeneous bent functions of degree $m$ in $2m$ variables when $m>3;$ there is no homogenous bent function of degree $m-1$ in 2m variables when $m>4;$ Generally, for any nonnegative integer $k$, there exists a positive integer $N$ such that when $m>N$, there is no homogeneous bent functions of degree $m-k$ in $2m$ variables. In other words, we get a tighter upper bound on the degree of homogeneous bent functions. A conjecture is proposed that for any positive integer $k>1$, there exists a positive integer $N$ such that when $m>N$, there exists homogeneous bent function of degree $k$ in $2m$ variables.
2004
EPRINT
On the Existence of low-degree Equations for Algebraic Attacks
Algebraic attacks on block ciphers and stream ciphers have gained more and more attention in cryptography. The idea is to express a cipher by a system of equations whose solution reveals the secret key. The complexity of an algebraic attack is closely related to the degree of the equations. Hence, low-degree equations are crucial for algebraic attacks. So far, the existence of low-degree equations for simple combiners, combiners with memory and S-boxes was treated independently. In this paper, we unify these approaches by reducing them to the same problem: finding low-degree annihilators. This enables a systematic treatment and implies a general criterion for the existence of low-degree equations. The unification allows to extend former results to all three cases. Therefore, we repeat an algorithm for finding a generating set of all low-degree equations. Additionally, we introduce a new improved version, adapted to specific keystream generators (e.g., for the Bluetooth keystream generator). Finally, we describe for certain cases an upper and a lower bound for the lowest possible degree. To the best of our knowledge, the upper bound has only been presented in the context of keystream generators before and the lower bound was not published previously.
2004
EPRINT
On the Impossibility of Highly-Efficient Blockcipher-Based Hash Functions
Fix a small, non-empty set of blockcipher keys K. We say a blockcipher-based hash function is "highly-efficient" if it makes exactly one blockcipher call for each message block hashed, and all blockcipher calls use a key from K. Although a few highly-efficient constructions have been proposed, no one has been able to prove their security. In this paper we prove, in the ideal-cipher model, that it is impossible to construct a highly-efficient iterated blockcipher-based hash function that is provably secure. Our result implies, in particular, that the Tweakable Chain Hash (TCH) construction suggested by Liskov, Rivest, and Wagner is not correct under an instantiation suggested for this construction, nor can TCH be correctly instantiated by any other efficient means.
2004
EPRINT
On the Key Exposure Problem in Chameleon Hashes
Chameleon signatures were introduced by Krawczyk and Rabin, being non-interactive signature schemes that provide non-transferability. However, that first construction employs a chameleon hash that suffers from a key exposure problem: The non-transferability property requires willingness of the recipient in consequentially exposing a secret key, and therefore invalidating all signatures issued to the same recipient's public key. To address this key-revocation issue, and its attending problems of key redistribution, storage of state information, and greater need for interaction, an identity-based scheme was proposed in [1], while a fully key-exposure free construction, based on the elliptic curves with pairings, appeared later in [7]. Herein we provide several constructions of exposure-free chameleon hash functions based on different cryptographic assumptions, such as the RSA and the discrete logarithm assumptions. One of the schemes is a novel construction that relies on a single trapdoor and therefore may potentially be realized over a large set of cryptographic groups (where the discrete logarithm is hard).
2004
EPRINT
On the Key-Uncertainty of Quantum Ciphers and the Computational Security of One-way Quantum Transmission
We consider the scenario where Alice wants to send a secret(classical) $n$-bit message to Bob using a classical key, and where only one-way transmission from Alice to Bob is possible. In this case, quantum communication cannot help to obtain perfect secrecy with key length smaller then $n$. We study the question of whether there might still be fundamental differences between the case where quantum as opposed to classical communication is used. In this direction, we show that there exist ciphers with perfect security producing quantum ciphertext where, even if an adversary knows the plaintext and applies an optimal measurement on the ciphertext, his Shannon uncertainty about the key used is almost maximal. This is in contrast to the classical case where the adversary always learns $n$ bits of information on the key in a known plaintext attack. We also show that there is a limit to how different the classical and quantum cases can be: the most probable key, given matching plain- and ciphertexts, has the same probability in both the quantum and the classical cases. We suggest an application of our results in the case where only a short secret key is available and the message is much longer.
2004
EPRINT
On the Limitations of Universally Composable Two-Party Computation Without Set-up Assumptions
The recently proposed {\em universally composable {\em (UC)} security} framework for analyzing security of cryptographic protocols provides very strong security guarantees. In particular, a protocol proven secure in this framework is guaranteed to maintain its security even when run concurrently with arbitrary other protocols. It has been shown that if a majority of the parties are honest, then universally composable protocols exist for essentially any cryptographic task in the {\em plain model} (i.e., with no setup assumptions beyond that of authenticated communication). When honest majority is not guaranteed, general feasibility results are known only given trusted set-up, such as in the common reference string model. Only little was known regarding the existence of universally composable protocols in the plain model without honest majority, and in particular regarding the important special case of two-party protocols. We study the feasibility of universally composable two-party {\em function evaluation} in the plain model. Our results show that in this setting, very few functions can be securely computed in the framework of universal composability. We demonstrate this by providing broad impossibility results that apply to large classes of deterministic and probabilistic functions. For some of these classes, we also present full characterizations of what can and cannot be securely realized in the framework of universal composability. Specifically, our characterizations are for the classes of deterministic functions in which (a) both parties receive the same output, (b) only one party receives output, and (c) only one party has input.
2004
EPRINT
On the Role of the Inner State Size in Stream Ciphers
Many modern stream ciphers consist of a keystream generator and a key schedule algorithm. In fielded systems, security of the keystream generator is often based on a large inner state rather than an inherently secure design. Note, however, that little theory on the initialisation of large inner states exists, and many practical designs are based on an ad-hoc approach. As a consequence, an increasing number of attacks on stream ciphers exploit the (re-)initialisation of large inner states by a weak key schedule algorithm. In this paper, we propose a strict separation of keystream generator and key schedule algorithm in stream cipher design. A formal definition of inner state size is given, and lower bounds on the necessary inner state size are proposed. After giving a construction for a secure stream cipher from an insecure keystream generator, the limitations of such an approach are discussed. We introduce the notion of inner state size efficiency and compare it for a number of fielded stream ciphers, indicating that a secure cipher can be based on reasonable inner state sizes. Concluding, we ask a number of open questions that may give rise to a new field of research that is concerned with the security of key schedule algorithms.
2004
EPRINT
On the Security and Composability of the One Time Pad
Recent experimental results in quantum cryptography have renewed the interest in information-theoretically secure ciphers. In April 2004, in Vienna a bank transfer was secured by means of a one time pad encryption, with the key material being derived from a quantum key exchange. However, in this experiment the integrity of the transmitted message remained unprotected. This can have severe consequences, if the bank transfer form itself contains no authentication mechanism and there is a known position where the amount of money or the recipient is specified. Through flipping bits at the corresponding positions in the ciphertext, the amount of transfered money or the recipient of the money can be changed. This concrete example illustrates the necessity for a thorough theoretical analysis of information-theoretically secure cryptographic techniques that are to be deployed in practice. In this work we show how to implement a statistically secure and composable system for message passing, that is, a channel with negligible failure rate secure against unbounded adversaries, using a one time pad based cryptosystem. We prove the security of our system in an asynchronous adversarially-controlled network using the framework put forward by Backes, Pfitzmann, and Waidner. The composition theorem offered by this framework enables the use of our scheme as a building block of more complex protocols as needed in practical applications.
2004
EPRINT
On the security of some nonrepudiable threshold proxy signature schemes with known signers
A (t,n) threshold proxy signature scheme enables an original signer to delegate the signature authority to a proxy group of n member such that t or more than t proxy signers can cooperatively sign messages on behalf of the original signer. In the paper, we review the security of some nonrepudiable threshold proxy signature schemes with known signers. We show that Sun's threshold proxy scheme, Yang et al.'s threshold proxy signature scheme and Tzeng et al.'s threshold proxy signature scheme are insecure against an original signer's forgery. We also show that Hsu et al.'s threshold proxy signature scheme suffers from the conspiracy of the original signer and the secret share dealer SA, and that Hwang et al.'s threshold proxy signature scheme is universally forgeable. In a word, none of the above-mentioned threshold proxy signature schemes can provide non-repudiation.
2004
EPRINT
On The Security of Two Key-Updating Signature Schemes
In ICICS 2004, Gonzalez-Deleito, Markowitch and Dall'Olio proposed an efficient strong key-insulated signature scheme. They claimed that it is (N-1,N)-key-insulated, i.e., the compromise of the secret keys for arbitrarily many time periods does not expose the secret keys for any of the remaining time periods. But in this paper, we demonstrate an attack and show that an adversary armed with the signing keys for any two time periods can compute the signing keys for the remaining time periods except for some very special cases. In a second attack, the adversary can forge signatures for many remaining time periods without computing the corresponding signing keys. Therefore it is only equivalent to a (1,N)-key-insulated signature scheme. A variant forward-secure signature scheme was also presented in ICICS 2004 and claimed more robust than traditional forward-secure signature schemes. But we find that the scheme has two similar weaknesses. We try to repair the two schemes in this paper.
2004
EPRINT
On the supports of the Walsh transforms of Boolean functions
In this paper, we study, in relationship with covering sequences, the structure of those subsets of $\V {n}$ which can be the Walsh supports of Boolean functions.
2004
EPRINT
On the Weaknesses and Improvements of an Efficient Password Based Remote User Authentication Scheme Using Smart Cards
In 2002, Chien et al. proposed an efficient remote user authentication scheme using smart cards. Later, in 2004, W. C. Ku and S. M. Chen pointed out some attacks on Chien et al.?s scheme. W. C. Ku and S. M. Chen also proposed a modified scheme to prevent the attacks on Chien et al.?s scheme. This paper discusses the security of the W. C. Ku and S. M. Chen?s scheme. This paper aims to show that the modified scheme is still vulnerable to the password guessing attack and the insider attack.
2004
EPRINT
Optimal Signcryption from Any Trapdoor Permutation
We build several highly-practical and optimized signcryption constructions directly from trapdoor permutations, in the random oracle model. All our constructions share features such as simplicity, efficiency, generality, near-optimal exact security, flexible and ad-hoc key management, key reuse for sending/receiving data, optimally-low message expansion, "backward" use for plain signature/encryption, long message and associated data support, the strongest-known qualitative security (so-called IND-CCA and sUF-CMA) and, finally, complete compatibility with the PKCS#1 infrastructure. While some of these features are present in previous works to various extents, we believe that our schemes improve on earlier proposals in at least several dimensions, making the overall difference quite noticeable in practice. Concretely, we present three methods generally based on what we call Parallel, Sequential, and eXtended sequential Padding schemes (P-Pad, S-Pad, X-Pad). P-Pad offers parallel "signing" and "encrypting", optimal exact security, and minimum ciphertext length twice as long as the length of a TDP , while still maintaining optimal bandwidth. S-Pad loses parallelism and some exact security, but has minimal ciphertext length equal to that of a TDP. Any S-Pad can also be used as a "universal padding" scheme. X-Pad is similar to S-Pad, but regains optimal exact security at the expense of a marginally-longer minimum ciphertext length. Moreover, to unify various padding options, we construct a single versatile padding scheme PSEP (Probabilistic Signature-Encryption Padding) which, by simply adjusting the lengths of the parameters, can work optimally as either a P-Pad, S-Pad or X-Pad.
2004
EPRINT
Optimal Updating of Ideal Threshold Schemes
We consider the problem of changing the parameters of an established ideal $(k,n)$-threshold scheme without the use of secure channels. We identify the parameters $(k',n')$ to which such a scheme can be updated by means of a broadcast message and then prove a lower bound on the size of the relevant broadcast. The tightness of this bound is demonstrated by describing an optimal procedure for updating the parameters of an ideal scheme.
2004
EPRINT
Ordinary abelian varieties having small embedding degree
Miyaji, Nakabayashi and Takano (MNT) gave families of group orders of ordinary elliptic curves with embedding degree suitable for pairing applications. In this paper we generalise their results by giving families corresponding to non-prime group orders. We also consider the case of ordinary abelian varieties of dimension 2. We give families of group orders with embedding degrees 5, 10 and 12.
2004
EPRINT
Pairing-Based Cryptographic Protocols : A Survey
The bilinear pairing such as Weil pairing or Tate pairing on elliptic and hyperelliptic curves have recently been found applications in design of cryptographic protocols. In this survey, we have tried to cover different cryptographic protocols based on bilinear pairings which possess, to the best of our knowledge, proper security proofs in the existing security models.
2004
EPRINT
Pairing-Based One-Round Tripartite Key Agreement Protocols
Since Joux published the first pairing-based one-round tripartite key agreement protocol [13], many authenticated protocols have been proposed. However most of them were soon broken or demonstrated not to achieve some desirable security attributes. In this paper we present a protocol variant based on Shim's work [20]. As the formalized model of this type of AK protocols is not mature, the security properties of the protocol are heuristically investigated by attempting a list of attacks. The attack list presented in the paper has both the importance in theory and the meaning in practice and can be used to evaluate other tripartite and group key agreement protocols.
2004
EPRINT
Parallel FPGA Implementation of RSA with Residue Number Systems - Can side-channel threats be avoided? - Extended version
In this paper, we present a new parallel architecture to avoid side-channel analyses such as: timing attack, simple/differential power analysis, fault induction attack and simple/differential electromagnetic analysis. We use a Montgomery Multiplication based on Residue Number Systems. Thanks to RNS, we develop a design able to perform an RSA signature in parallel on a set of identical and independent coprocessors. Of independent interest, we propose a new DPA countermeasure in the framework of RNS. It is only (slightly) memory consuming (1.5 KBytes). Finally, we synthesized our new architecture on FPGA and it presents promising performance results. Even if our aim is to sketch a secure architecture, the RSA signature is performed in less than 160 ms, with competitive hardware resources. To our knowledge, this is the first proposal of an architecture counteracting electromagnetic analysis apart from hardware countermeasures reducing electromagnetic radiations.
2004
EPRINT
Parallel Montgomery Multiplication in $GF(2^k)$ using Trinomial Residue Arithmetic
We propose the first general multiplication algorithm in $\mathrm{GF}(2^k)$ with a subquadratic area complexity of $\mathcal{O}(k^{8/5}) = \mathcal{O}(k^{1.6})$. Using the Chinese Remainder Theorem, we represent the elements of $\mathrm{GF}(2^k)$; i.e. the polynomials in $\mathrm{GF}(2)[X]$ of degree at most $k-1$, by their remainder modulo a set of $n$ pairwise prime trinomials, $T_1,\dots,T_{n}$, of degree $d$ and such that $nd \geq k$. Our algorithm is based on Montgomery's multiplication applied to the ring formed by the direct product of the trinomials.
2004
EPRINT
Password Based Key Exchange with Mutual Authentication
A reasonably efficient password based key exchange (KE) protocol with provable security without random oracle was recently proposed by Katz, {\em et al.} \cite{KOY01} and later by Gennaro and Lindell \cite{GL03}. However, these protocols do not support mutual authentication (MA). The authors explained that this could be achieved by adding an additional flow. But then this protocol turns out to be 4-round. As it is known that a high entropy secret based key exchange protocol with MA\footnote{we do not consider a protocol with a time stamp or a stateful protocol (e.g., a counter based protocol). In other words, we only consider protocols in which a session execution within an entity is independent of its history, and in which the network is asynchronous.} is optimally 3-round (otherwise, at least one entity is not authenticated since a replay attack is applicable), it is quite interesting to ask whether such a protocol in the password setting (without random oracle) is achievable or not. In this paper, we provide an affirmative answer with an efficient construction in the common reference string (CRS) model. Our protocol is even simpler than that of Katz, {\em et al.} Furthermore, we show that our protocol is secure under the DDH assumption ({\em without} random oracle).
2004
EPRINT
Password-Based Authenticated Key Exchange in the Three-Party Setting
Password-based authenticated key exchange are protocols which are designed to be secure even when the secret key or password shared between two users is drawn from a small set of values. Due to the low entropy of passwords, such protocols are always subject to on-line guessing attacks. In these attacks, the adversary may succeed with non-negligible probability by guessing the password shared between two users during its on-line attempt to impersonate one of these users. The main goal of password-based authenticated key exchange protocols is to restrict the adversary to this case only. In this paper, we consider password-based authenticated key exchange in the three-party scenario, in which the users trying to establish a secret do not share a password between themselves but only with a trusted server. Towards our goal, we recall some of the existing security notions for password-based authenticated key exchange protocols and introduce new ones that are more suitable to the case of generic constructions. We then present a natural generic construction of a three-party protocol, based on any two-party authenticated key exchange protocol, and prove its security without making use of the Random Oracle model. To the best of our knowledge, the new protocol is the first provably-secure password-based protocol in the three-party setting.
2004
EPRINT
Piece In Hand Concept for Enhancing the Security of Multivariate Type Public Key Cryptosystems: Public Key Without Containing All the Information of Secret Key
We propose a new concept, named piece in hand, which can be applicable to a wide class of multivariate type public key cryptosystems to enhance their security. The piece in hand provides such cryptosystems with a new type of trapdoor which is compatible with the trapdoor originally equipped in them. The piece in hand concept is based on a new paradigm for public key cryptosystem in general. On the one hand, in most traditional public key cryptosystems such as the RSA and ElGamal schemes, the public key contains all the information of the secret key. On the other hand, in our scheme, the piece in hand, which is a part of the secret key, is not contained in the public key but is taken from outside of the public key to plug in during the decryption. In this paper, we illustrate how to apply the piece in hand concept to enhance the security of multivariate type public key cryptosystems, by presenting the general theory for the use of the concept.
2004
EPRINT
Pitfalls in public key cryptosystems based on free partially commutative monoids and groups
At INDOCRYPT 2003 Abisha, Thomas, and Subramanian proposed two public key schemes based on word problems in free partially commutative monoids and groups. We show that both proposals are vulnerable to chosen ciphertext attacks, and thus in the present form must be considered as insecure.
2004
EPRINT
Plaintext-Simulatability
We propose a new security class, called plaintext-simulatability, defined over the public-key encryption schemes. The notion of plaintext simulatability (denoted PS) is similar to the notion of plaintext awareness (denoted PA), but it is, ``properly'', a weaker security class for public-key encryption. In most cases, PA is ``unnecessarily'' strong, --- only used to prove that a public-key encryption scheme is CCA2-secure, because it looks much easier than to prove ``directly'' that the scheme meets IND-CCA2. We show that PS also implies IND-CCA2, while preserving a good view of the security proofs as well as PA. PS looks ``properly'' stronger than IND-CCA2. So far, however, it is not sure how to prove this, which remains open.
2004
EPRINT
Plateaued Rotation Symmetric Boolean Functions on Odd Number of Variables
The class of Rotation Symmetric Boolean Functions (RSBFs) has received serious attention recently in searching functions of cryptographic significance. These functions are invariant under circular translation of indices. In this paper we study such functions on odd number of variables and interesting combinatorial properties related to Walsh spectra of such functions are revealed. In particular we concentrate on plateaued functions (functions with three valued Walsh spectra) in this class and derive necessary conditions for existence of balanced rotation symmetric plateaued functions. As application of our result we show the non existence of 9-variable, 3-resilient RSBF with nonlinearity 240 that has been posed as an open question in FSE 2004. Further we show how one can make efficient search in the space of RSBFs based on our theoretical results and as example we complete the search for unbalanced 9-variable, 3rd order correlation immune plateaued RSBFs with nonlinearity 240.
2004
EPRINT
Point Compression on Jacobians of Hyperelliptic Curves over $\F_q$
Hyperelliptic curve cryptography recently received a lot of attention, especially for constrained environments. Since there space is critical, compression techniques are interesting. In this note we propose a new method which avoids factoring the first representing polynomial. In the case of genus two the cost for decompression is, essentially, computing two square roots in $\F_q$, the cost for compression is much less.
2004
EPRINT
Positive Results and Techniques for Obfuscation
Informally, an obfuscator $\Obf$ is an efficient, probabilistic ``compiler'' that transforms a program $P$ into a new program $\Obf(P)$ with the same functionality as $P$, but such that $\Obf(P)$ protects any secrets that may be built into and used by $P$. Program obfuscation, if possible, would have numerous important cryptographic applications, including: (1) ``Intellectual property'' protection of secret algorithms and keys in software, (2) Solving the long-standing open problem of homomorphic public-key encryption, (3) Controlled delegation of authority and access, (4) Transforming Private-Key Encryption into Public-Key Encryption, and (5) Access Control Systems. Unfortunately however, program obfuscators that work on arbitrary programs cannot exist [Barak et al]. No positive results for program obfuscation were known prior to this work. In this paper, we provide the first positive results in program obfuscation. We focus on the goal of access control, and give several provable obfuscations for complex access control functionalities, in the random oracle model. Our results are obtained through non-trivial compositions of obfuscations; we note that general composition of obfuscations is impossible, and so developing techniques for composing obfuscations is an important goal. Our work can also be seen as making initial progress toward the goal of obfuscating finite automata or regular expressions, an important general class of machines which are not ruled out by the impossibility results of Barak et al. We also note that our work provides the first formal proof techniques for obfuscation, which we expect to be useful in future work in this area.
2004
EPRINT
Post-Quantum Signatures
Digital signatures have become a key technology for making the Internet and other IT infrastructures secure. But in 1994 Peter Shor showed that quantum computers can break all digital signature schemes that are used today and in 2001 Chuang and his coworkers implemented Shor s algorithm for the first time on a 7-qubit NMR quantum computer. This paper studies the question: What kind of digital signature algorithms are still secure in the age of quantum computers?
2004
EPRINT
Practical Attacks on Digital Signatures Using MD5 Message Digest
We use the knowledge of the single MD5 collision published by Wang et al. [1] to show an example of a pair of binary self-extract packages with equal MD5 checksums, whereas resulting extracted contracts have fundamentally different meaning. Secondly, we demonstrate how an attacker could create custom pair of such packages containing files arbitrarily chosen by the attacker with equal MD5 sums where each of the package extracts different file. Once the algorithm for finding MD5 collisions is published, attack could be made even more effective as we explain further. Authors of [1] claim to know such algorithm for any MD5 initialization vector. A real-world scenario of such attack is outlined. Finally, we point out the consequences resulting from such attack for signature schemes based on MD5 message digest on an example using GPG. [1] X. Wang, D. Feng, X. Lai, H. Yu, "Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD", rump session, CRYPTO 2004, Cryptology ePrint Archive, Report 2004/199, http://eprint.iacr.org/2004/199
2004
EPRINT
Practical Cryptography in High Dimensional Tori
At Crypto 2004, van Dijk and Woodruff introduced a new way of using the algebraic tori T_n in cryptography, and obtained an asymptotically optimal n/phi(n) savings in bandwidth and storage for a number of cryptographic applications. However, the computational requirements of compression and decompression in their scheme were impractical, and it was left open to reduce them to a practical level. We give a new method that compresses orders of magnitude faster than the original, while also speeding up the decompression and improving on the compression factor (by a constant term). Further, we give the first efficient implementation that uses T_30, compare its performance to XTR, CEILIDH, and ECC, and present new applications. Our methods achieve better compression than XTR and CEILIDH for the compression of as few as two group elements. This allows us to apply our results to ElGamal encryption with a small message domain to obtain ciphertexts that are 10% smaller than in previous schemes.
2004
EPRINT
Privacy Preserving Keyword Searches on Remote Encrypted Data
We consider the following problem: a user \U\ wants to store his files in an encrypted form on a remote file server \FS. Later the user \U\ wants to efficiently retrieve some of the encrypted files containing (or indexed by) specific keywords, keeping the keywords themselves secret and not jeopardizing the security of the remotely stored files. For example, a user may want to store old e-mail messages encrypted on a server managed by Yahoo or another large vendor, and later retrieve certain messages while traveling with a mobile device. In this paper, we offer solutions for this problem under well-defined security requirements. Our schemes are efficient in the sense that no public-key cryptosystem is involved. Indeed, our approach is independent of the encryption method chosen for the remote files. They are also incremental, in that \U\ can submit new files which are totally secure against previous queries but still searchable against future queries.
2004
EPRINT
Privacy-Enhanced Searches Using Encrypted Bloom Filters
It is often necessary for two or more or more parties that do not fully trust each other to selectively share data. We propose a search scheme based on Bloom filters and Pohlig-Hellman encryption. A semi-trusted third party can transform one party's search queries to a form suitable for querying the other party's database, in such a way that neither the third party nor the database owner can see the original query. Furthermore, the encryption keys used to construct the Bloom filters are not shared with this third party. Provision can be made for third-party ``warrant servers'', as well as ``censorship sets'' that limit the data to be shared.
2004
EPRINT
Private Inference Control
Access control can be used to ensure that database queries pertaining to sensitive information are not answered. This is not enough to prevent users from learning sensitive information though, because users can combine non-sensitive information to discover something sensitive. Inference control prevents users from obtaining sensitive information via such ``inference channels'', however, existing inference control techniques are not private - that is, they require the server to learn what queries the user is making in order to deny inference-enabling queries. We propose a new primitive - private inference control (PIC) - which is a means for the server to provide inference control without learning what information is being retrieved. PIC is a generalization of private information retrieval (PIR) and symmetrically-private information retrieval (SPIR). While it is straightforward to implement access control using PIR (simply omit sensitive information from the database), it is nontrivial to implement inference control efficiently. We measure the efficiency of a PIC protocol in terms of its communication complexity, its round complexity, and the work the server performs per query. Under existing cryptographic assumptions, we give a PIC scheme which is simultaneously optimal, up to logarithmic factors, in the work the server performs per query, the total communication complexity, and the number of rounds of interaction. We also present a scheme requiring more communication but sufficient storage of state by the server to facilitate private user revocation. Finally, we present a generic reduction which shows that one can focus on designing PIC schemes for which the inference channels take a particularly simple threshold form.
2004
EPRINT
Protocol Initialization for the Framework of Universal Composability
Universally composable protocols (Canetti, FOCS 2000) are cryptographic protocols that remain secure even when run concurrently with arbitrary other protocols. Thus, universally composable protocols can be run in modern networks, like the Internet, and their security is guaranteed. However, the definition of universal composition actually assumes that each execution of the protocol is assigned a unique session identifier, and furthermore, that this identifier is known to all the participating parties. In addition, all universally composable protocols assume that the set of participating parties and the specification of the protocol to be run are a-priori agreed upon and known to all parties. In a decentralized network like the Internet, this setup information must be securely generated by the parties themselves. In this note we formalize the setup problem and show how to securely realize it with a simple and highly efficient protocol.
2004
EPRINT
Provably Secure Authenticated Tree Based Group Key Agreement Protocol
We present a provably secure authenticated tree based key agreement protocol. The protocol is obtained by combining Boldyreva's multi-signature with an unauthenticated ternary tree based multi-party extension of Joux's key agreement protocol. The securiry is in the standard model as formalized by Bresson et al. The proof is based on the techniques used by Katz and Yung in proving the security of their key agreement protocol.
2004
EPRINT
Provably Secure Authentication of Digital Media Through Invertible Watermarks
The recent advances in multimedia technology have made the manipulation of digital images, videos or audio files easy. On the one hand the broad availability of these new capabilities enabled numerous new applications. On the other hand, for the same reasons, digital media can easily be forged by almost anyone. To counteract this risk, fragile watermarks were proposed to protect the integrity and authenticity of digital multimedia objects. Traditional watermarking schemes employ non-cryptographic and signal processing oriented techniques, which fail to provide any provable security guarantee against malicious modification attempts. In this paper, we give for the first time a provably secure authentication mechanism for digital multimedia files that is based on both cryptographic signatures and invertible watermarks. While traditional watermarking schemes introduce some small irreversible distortion in the digital content, invertible watermarks can be completely removed from a watermarked work.
2004
EPRINT
Provably Secure Delegation-by-Certification Proxy Signature Schemes
In this paper, we first show that previous proxy signature schemes by delegation with certificate are not provably secure under adaptive-chosen message attacks and adaptive-chosen warrant attacks. The schemes do not provide the strong undeniability. Then we construct a proxy signature scheme by delegation with certificate based on Co-GDH group from bilinear map. Our proxy signature scheme is existentially unforgeable against adaptive-chosen message attacks and adaptive-chosen warrant attacks in random oracle model. We adopt a straight method of security reduction in which our scheme's security is reduced to hardness of the computational co-Diffie-Hellem problem. The proposed signature scheme is the first secure delegation-by-certificate proxy signature based on co-GDH groups from bilinear maps under the formal security model in random oracle model.
2004
EPRINT
Provably Secure Masking of AES
A general method to secure cryptographic algorithm implementations against side-channel attacks is the use of randomization techniques and, in particular, masking. Roughly speaking, using random values unknown to an adversary one masks the input to a cryptographic algorithm. As a result, the intermediate results in the algorithm computation are uncorrelated to the input and the adversary cannot obtain any useful information from the side-channel. Unfortunately, previous AES randomization techniques have based their security on heuristics and experiments. Thus, flaws have been found which make AES randomized implementations still vulnerable to side-channel cryptanalysis. In this paper, we provide a formal notion of security for randomized maskings of arbitrary cryptographic algorithms. Furthermore, we present an AES randomization technique that is provably secure against side-channel attacks if the adversary is able to access a single intermediate result. Our randomized masking technique is quite general and it can be applied to arbitrary algorithms using only arithmetic operations over some even characteristic finite field. We notice that to our knowledge this is the first time that a randomization technique for the AES has been proven secure in a formal model.
2004
EPRINT
Provably Secure On-demand Source Routing in Mobile Ad Hoc Networks
Routing is one of the most basic networking functions in mobile ad hoc networks. Hence, an adversary can easily paralyze the operation of the network by attacking the routing protocol. This has been realized by many researchers, and several ``secure'' routing protocols have been proposed for ad hoc networks. However, the security of those protocols have mainly been analyzed by informal means only. In this paper, we argue that flaws in ad hoc routing protocols can be very subtle, and we advocate a more systematic way of analysis. We propose a mathematical framework in which security can be precisely defined, and routing protocols for mobile ad hoc networks can be analyzed rigorously. Our framework is tailored for on-demand source routing protocols, but the general principles are applicable to other types of protocols too. Our approach is based on the simulation paradigm, which has already been used extensively for the analysis of key establishment protocols, but to the best of our knowledge, it has not been applied in the context of ad hoc routing so far. We also propose a new on-demand source routing protocol, called endairA, and we demonstrate the usage of our framework by proving that it is secure in our model.
2004
EPRINT
Provably-Secure and Communication-Efficient Scheme for Dynamic Group Key Exchange
Group key agreement protocols are designed to solve the fundamental problem of securely establishing a session key among a group of parties communicating over a public channel. Although a number of protocols have been proposed to solve this problem over the years, they are not well suited for a high-delay wide area network; their communication overhead is significant in terms of the number of communication rounds or the number of exchanged messages, both of which are recognized as the dominant factors that slow down group key agreement over a networking environment with high communication latency. In this paper we present a communication-efficient group key agreement protocol and prove its security in the random oracle model under the factoring assumption. The proposed protocol provides perfect forward secrecy and requires only a constant number of communication rounds for any of group rekeying operations, while achieving optimal message complexity.
2004
EPRINT
Ramanujan Graphs and the Random Reducibility of Discrete Log on Isogenous Elliptic Curves
Cryptographic applications using an elliptic curve over a finite field filter curves for suitability using their order as the primary criterion: e.g. checking that their order has a large prime divisor before accepting it. It is therefore natural to ask whether the discrete log problem (DLOG) has the same difficulty for all curves with the same order; if so it would justify the above practice. We prove that this is essentially true by showing random reducibility of dlog among such curves, assuming the Generalized Riemann Hypothesis (GRH). Our reduction proof works for curves with (nearly) the same endomorphism rings, but it is unclear if such a reduction exists in general. This suggests that in addition to the order, the conductor of its endomorphism ring may play a role. The random self-reducibility for dlog over finite fields is well known; the non-trivial part here is that one must relate non-isomorphic algebraic groups of two isogenous curves. We construct certain expander graphs with elliptic curves as nodes and low degree isogenies as edges, and utilize the rapid mixing of random walks on this graph. We also briefly look at some recommended curves, compare ?random? type NIST FIPS 186-2 curves to other special curves from this standpoint, and suggest a parameter to measure how generic a given curve is.
2004
EPRINT
Random Switching Logic: A Countermeasure against DPA based on Transition Probability
In this paper, we propose a new model for directly evaluating DPA leakage from logic information in CMOS circuits.This model is based on the transition probability for each gate, and is naturally applicable to various actual devices for simulating power analysis. We also report on our study of the effects of the previously known countermeasures on both our model and FPGA, and show the possibility of leaking information, which is caused by strict precondition for implementing a secure circuit. Furthermore, we present an efficient countermeasure, \textit{Random Switching Logic}(RSL), for relaxing the precondition, and show that RSL makes a cryptographic circuit secure through evaluation on both our model and FPGA.
2004
EPRINT
RDS: Remote Distributed Scheme for Protecting Mobile Agents
As of today no solely software-based solution that a priori protects the computation of any mobile code and/or mobile agent was presented. Furthermore, Algesheimer et al. [1], argue that minimal trust in a third party is essential for the protection of mobile entities. This paper shows that under very mild assumptions, there exists a software-only based solution that can protect any computation of mobile entities in polynomial time bound systems, and without relaying on the minimal trust requirement. A novel Remote Distributed Scheme, called RDS, is described. RDS is based on fault-tolerant and modest cryptographic techniques and supports an a priori protection of any mobile computation that is carried in an honest-but-curious environment (?trusted entities?). We next show, by using on probabilistic techniques, that RDS provides an a priori protection for any mobile computation, in any environment, and for any required level of secrecy. We also prove that RDS equivalents, and by thus, provides the same level of protection that is supports by the traditional client/server scheme.
2004
EPRINT
Receipt-Free Homomorphic Elections and Write-in Ballots
We present a voting protocol that protects voters' privacy and achieves universal verifiability, receipt-freeness, and uncoercibility without ad hoc physical assumptions or procedural constraints (such as untappable channels, voting booths, smart cards, third-party randomizers, and so on). We discuss under which conditions the scheme allows voters to cast write-in ballots, and we show how it can be practically implemented through voter-verified (paper) ballots. The scheme allows voters to combine voting credentials with their chosen votes applying the homomorphic properties of certain probabilistic cryptosystems.
2004
EPRINT
Reducing Complexity Assumptions for Statistically-Hiding Commitment
Determining the minimal assumptions needed to construct various cryptographic building blocks has been a focal point of research in theoretical cryptography. For most --- but not all! --- cryptographic primitives, complexity assumptions both necessary and sufficient for their existence are known. Here, we revisit the following, decade-old question: what are the minimal assumptions needed to construct a statistically-hiding bit commitment scheme? Previously, it was known how to construct such schemes based on any one-way permutation. In this work, we show that regular one-way functions suffice. We show two constructions of statistically-hiding commitment schemes from regular one-way functions. Our first construction is more direct, and serves as a ``stepping-stone'' for our second construction which has improved round complexity. Of independent interest, as part of our work we show a compiler transforming any commitment scheme which is statistically-hiding against an honest-but-curious receiver to one which is statistically-hiding against a malicious receiver. This demonstrates the equivalence of these two formulations of the problem. Our results also improve the complexity assumptions needed for statistical zero-knowledge arguments.
2004
EPRINT
Redundant Trinomials for Finite Fields of Characteristic $2$
In this paper we introduce a new way to represent elements of a finite field of characteristic $2$. We describe a new type of polynomial basis, called {\it redundant trinomial basis} and discuss how to implement it efficiently. Redundant trinomial bases are well suited to build $\mathbb{F}_{2^n}$ when no irreducible trinomial of degree $n$ exists. Tests with {\tt NTL} show that improvements for squaring and exponentiation are respectively up to $45$\% and $25$\%. More attention is given to relevant extension degrees for doing elliptic and hyperelliptic curve cryptography. For this range, a scalar multiplication can be speeded up by a factor up to $15$\%.
2004
EPRINT
Refinements of Miller's Algorithm for Computing Weil/Tate Pairing
In this paper we propose three refinements to Miller's algorithm for computing Weil/Tate Pairing.The first one is an overall improvement and achieves its optimal behavior if the binary expansion of the involved integer has more zeros. If more ones are presented in the binary expansion, second improvement is suggested. The third one is especially efficient in the case base three. We also have some performance analysis.
2004
EPRINT
Regional Blackouts: Protection of Broadcast Content on 3G Networks
One of the driving forces behind the development of 3G systems is the potential to deliver complex content to consumers. This is evident from the growing collaboration between broadcast and mobile network operators, and the expectation that future broadcast receivers will be able to forward content to mobile devices. One challenge in providing such a service is the requirement for content protection. An aspect of this that is particularly relevant to mobile systems is the ability to control where content is viewed. Although 3G networks can provide location of a user?s receiver, this device may be in a different location from the device that renders the content. Thus the provider cannot be certain where the content will be viewed. This paper proposes two protocols that will provide the location of the end device in a secure manner that can be trusted by the content provider.
2004
EPRINT
Relating Symbolic and Cryptographic Secrecy
We investigate the relation between symbolic and cryptographic secrecy properties for cryptographic protocols. Symbolic secrecy of payload messages or exchanged keys is arguably the most important notion of secrecy shown with automated proof tools. It means that an adversary restricted to symbolic operations on terms can never get the entire considered object into its knowledge set. Cryptographic secrecy essentially means computational indistinguishability between the real object and a random one, given the view of a much more general adversary. In spite of recent advances in linking symbolic and computational models of cryptography, no relation for secrecy under active attacks is known yet. For exchanged keys, we show that a certain strict symbolic secrecy definition over a specific Dolev-Yao-style cryptographic library implies cryptographic key secrecy for a real implementation of this cryptographic library. For payload messages, we present the first general cryptographic secrecy definition for a reactive scenario. The main challenge is to separate secrecy violations by the protocol under consideration from secrecy violations by the protocol users in a general way. For this definition we show a general secrecy preservation theorem under reactive simulatability, the cryptographic notion of secure implementation. This theorem is of independent cryptographic interest. We then show that symbolic secrecy implies cryptographic payload secrecy for the same cryptographic library as used in key secrecy. Our results thus enable existing formal proof techniques to establish cryptographically sound proofs of secrecy for payload messages and exchanged keys.
2004
EPRINT
Relation between XL algorithm and Groebner Bases Algorithms
We clarify a relation between the XL algorithm and Groebner bases algorithms. The XL algorithm was proposed to be a more efficient algorithm to solve a system of equations with a special assumption without trying to calculate a whole Groebner basis. But in our result, it is shown that the XL algorithm is also a Groebner bases algorithm which can be represented as a redundant version of a Groebner bases algorithm F4 under the assumption in XL.
2004
EPRINT
Request for Review of Key Wrap Algorithms
A key wrap algorithm is a secret key algorithm for the authenticated encryption of specialized data such as cryptographic keys. Four key wrap algorithms have been proposed for the draft ASC X9 standard, ANS X9.102. NIST is serving as the editor of ANS X9.102, and, on behalf of the X9F1 working group, NIST requests a cryptographic review of the four algorithms. This document specifies the algorithms and suggests security models for their analysis. Comments will be accepted until May 21, 2005.
2004
EPRINT
Rethinking the security of some authenticated group key agreement schemes
In this paper we analyse three improved authenticated group key agreement schemes, all of which are based on the conference key distribution systems proposed by Burmester and Desmedt. We show that all the schemes suffer from a type of impersonation attack, although these schemes are claimed to be secure.
2004
EPRINT
Reusable Cryptographic Fuzzy Extractors
We show that a number of recent definitions and constructions of fuzzy extractors are not adequate for multiple uses of the same fuzzy secret---a major shortcoming in the case of biometric applications. We propose two particularly stringent security models that specifically address the case of fuzzy secret reuse, respectively from an outsider and an insider perspective, in what we call a chosen perturbation attack. We characterize the conditions that fuzzy extractors need to satisfy to be secure, and present generic constructions from ordinary building blocks. As an illustration, we demonstrate how to use a biometric secret in a remote error tolerant authentication protocol that does not require any storage on the client's side.
2004
EPRINT
Revision of Tractable Rational Map Cryptosystem
We introduce a new public-key cryptosystem with tractable rational maps. As an application of abstract algebra and algebraic geometry to cryptography, TRMC (Tractable Rational Map Cryptosystem) has many superior properties including high complexity, easy implementation and very fast execution. We describe the principles and implementation of TRMC and analyze its properties. Also, we give a brief account of security analysis.
2004
EPRINT
Revisit Of McCullagh--Barreto Two-Party ID-Based Authenticated Key Agreement Protocols
The recently proposed two-party ID-based authenticated key agreement protocols (with and without escrow) and its variant resistant to key-compromise impersonation by McCullagh & Barreto are revisited. The protocol carries a proof of security in the Bellare & Rogaway (1993) model. In this paper, it is demonstrated that the protocols and its variant are not secure if the adversary is allowed to send a Reveal query to reveal non-partner players who had accepted the same session key.
2004
EPRINT
Rewriting Variables: the Complexity of Fast Algebraic Attacks on Stream Ciphers
Recently proposed algebraic attacks [AK03,CM03] and fast algebraic attacks [A04,C03] have provided the best analyses against some deployed LFSR-based ciphers. The process complexity is exponential in the degree of the equations. Fast algebraic attacks were introduced [C03] as a way of reducing run-time complexity by reducing the degree of the system of equations. Previous reports on fast algebraic attacks [A04,C03] have underestimated the complexity of substituting the keystream into the system of equations, which in some cases dominates the attack. We also show how the Fast Fourier Transform (FFT) [CT65] can be applied to decrease the complexity of the substitution step, although in one case this step still dominates the attack complexity. Finally, we show that all functions of degree d satisfy a common, function-independent linear combination that may be used in the pre-computation step of the fast algebraic attack and provide an explicit factorization of the corresponding characteristic polynomial. This yields the fastest known method for performing the pre-computation step.
2004
EPRINT
s(n) An Arithmetic Function of Some Interest, and Related Arithmetic
Every integer n > 0 ? N defines an increasing monotonic series of integers: n1, n2, ...nk, such that nk = nk +k(k-1)/2. We define as s(m) the number of such series that an integer m belongs to. We prove that there are infinite number of integers with s=1, all of the form 2^t (they belong only to the series that they generate, not to any series generated by a smaller integer). We designate them as s-prime integers. All integers with a factor other than 2 are not s-prime (s>1), but are s-composite. However, the arithmetic s function shows great variability, lack of apparent pattern, and it is conjectured that s(n) is unbound. Two integers, n and m, are defined as s-congruent if they have a common s-series. Every arithmetic equation can be seen as an expression without explicit unknowns -- provided every integer variable can be replaced by any s-congruent number. To validate the equation one must find a proper match of such members. This defines a special arithmetic, which appears well disposed towards certain cryptographic applications.
2004
EPRINT
Scalable Public-Key Tracing and Revoking
Traitor Tracing Schemes constitute a very useful tool against piracy in the context of digital content broadcast. In such multi-recipient encryption schemes, each decryption key is fingerprinted and when a pirate decoder is discovered, the authorities can trace the identities of the users that contributed in its construction (called traitors). Public-key traitor tracing schemes allow for a multitude of non-trusted content providers using the same set of keys, which makes the scheme ``server-side scalable.'' To make such schemes also ``client-side scalable,'' i.e. long lived and usable for a large population of subscribers that changes dynamically over time, it is crucial to implement efficient Add-user and Remove-user operations. Previous work on public-key traitor tracing did not address this dynamic scenario thoroughly, and there is no efficient scalable public key traitor tracing scheme that allows an increasing number of Add-user and Remove-user operations. To address these issues, we introduce the model of Scalable Public-Key Traitor Tracing, and present the first construction of such a scheme. Our model mandates for deterministic traitor tracing and an unlimited number of efficient Add-user operations and Remove-user operations. A scalable system achieves an unlimited number of revocations while retaining high level of efficiency by dividing the run-time of the system into periods. Each period has a saturation level for the number of revocations. When a period becomes saturated, an _efficient_ New-period operation is issued by the system server that resets the saturation level. We present a formal adversarial model for our system taking into account its periodic structure, and we prove our construction secure, both against adversaries that attempt to cheat the revocation mechanism as well as against adversaries that attempt to cheat the traitor tracing mechanism.
2004
EPRINT
Scalable, Server-Passive, User-Anonymous Timed Release Public Key Encryption from Bilinear Pairing
We consider the problem of sending messages into the future, commonly known as timed release cryptography. Existing schemes for this task either solve the relative time problem with uncontrollable, coarse-grained release time (time-lock puzzle approach) or do not provide anonymity to sender and/or receiver and are not scalable (server-based approach). Using a bilinear paring on any Gap Diffie-Hellman group, we solve this problem by giving a scalable, server-passive and user-anonymous timed release public-key encryption scheme which allows precise absolute release time specifications. Unlike the existing server-based schemes, the trusted time server in our scheme is completely passive --- no interaction between it and the sender or receiver is needed; it is even not aware of the existence of a user, thus assuring the anonymity of both the sender and receiver of a message and the privacy of the message. Besides, our scheme also has a number of desirable properties including self-authenticated time-bound key updates, a single form of update for all receivers, simple public-key renewal and key insulation, making it a scalable and appealing solution.
2004
EPRINT
Scalar Multiplication in Elliptic Curve Cryptosystems: Pipelining with Pre-computations
The pipelining scheme proposed in~\cite{PKM04} is an efficient and secure scheme for computing scalar multiplication in Elliptic Curve Cryptosystems (ECC). The scheme proposed in~\cite{PKM04} does not assume any pre-computation. In this work we extend the scheme to the situation where the system allows some pre-computation and is capable of storing some precomputed values. Like the scheme proposed in~\cite{PKM04} our scheme uses an extra multiplier. On the performance front, it outperforms the best known sequential and parallel schemes. On the security front, our algorithm uses two countermeasures against SPA and hence are doubly secured against SPA. Also, it is secure against DPA using the Joye-Tymen's curve randomization countermeasure.
2004
EPRINT
Scan Based Side Channel Attack on Data Encryption Standard
Scan based test is a double edged sword. On one hand, it is a powerful test technique. On the other hand, it is an equally powerful attack tool. In this paper we show that scan chains can be used as a side channel to recover secret keys from a hardware implementation of the Data Encryption Standard (DES). By loading pairs of known plaintexts with one-bit difference in the normal mode and then scanning out the internal state in the test mode, we first determine the position of all scan elements in the scan chain. Then, based on a systematic analysis of the structure of the non-linear substitution boxes, and using three additional plaintexts we discover the DES secret key. Finally, some assumptions in the attack are discussed.
2004
EPRINT
Second Preimages on n-bit Hash Functions for Much Less than 2^n Work
We provide a second preimage attack on all $n$-bit iterated hash functions with Damgard-Merkle strengthening and $n$-bit itermediate states, allowing a second preimage to be found for a $2^k$-message-block message with about $k \times 2^{n/2+1}+2^{n-k+1}$ work. Using SHA1 as an example, our attack can find a second preimage for a $2^{60}$ byte message in $2^{106}$ work, rather than the previously expected $2^{160}$ work. We also provide slightly cheaper ways to find multicollisions than the method of Joux. Both of these results are based on expandable messages--patterns for producing messages of varying length, which all collide on the intermediate hash result immediately after processing the message. We also provide algorithms for finding expandable messages for a hash function, using only a small multiple of the work done to find a single collision in the hash function.
2004
EPRINT
Secret Handshakes from CA-Oblivious Encryption
Secret handshake protocols were recently introduced by Balfanz et al. [IEEE, Oakland 2003] to allow members of the same group to authenticate each other *secretly*, in the sense that someone who is not a group member cannot tell, by engaging some party in the handshake protocol, whether that party is a member of the group. On the other hand, any two parties who are members of the same group will recognize each other as members. Thus, secret handshakes can be used in any scenario where group members need to identify each other without revealing their group affiliations to outsiders. The secret handshake protocol of Balfanz et al. relies on a Bilinear Diffie-Hellman assumption (in ROM) on certain elliptic curves. We show how to build secret handshake protocols secure under more standard cryptographic assumption of Computational Diffie Hellman(CDH), using a novel tool of CA-oblivious public key encryption, which is an encryption scheme s.t. neither the public key nor the ciphertext reveal any information about the Certification Authority (CA) which certified the public key. We construct such CA-oblivious encryption, and hence a handshake scheme, based on CDH (in ROM). The new scheme takes 3 communication rounds like the scheme of Balfanz et al., but it is about twice cheaper computationally, and it relies on a weaker computational assumption.
2004
EPRINT
Secure and Efficient AES Software Implementation for Smart Caards
In implementing cryptographic algorithms on limited devices such as smart cards, speed and memory requirements had always presented a challenge. With the advent of side channel attacks, this task became even more difficult because a programmer must take into account countermeasures against such attacks, which often increases computational time, or memory requirements, or both. In this paper we describe a new method for secure implementation of the Advanced Encryption Standard algorithm. The method is based on a data masking technique, which is the most widely used countermeasure against power analysis and timing attacks at a software level. The change of element representation allows us to replace all multiplications in the field with table lookups using masked log/alog tables, and achieve an efficient solution that combines low memory requirements with high speed and resistance to attacks.
2004
EPRINT
Secure and Efficient Masking of AES - A Mission Impossible?
This document discusses masking approaches with a special focus on the AES S-box. Firstly, we discuss previously presented masking schemes with respect to their security and implementation. We conclude that algorithmic countermeasures to secure the AES algorithm against side-channel attacks have not been resistant against all first-order side-channel attacks. Secondly, we introduce a new masking countermeasure which is not only secure against first-order side-channel attacks, but which also leads to relatively small implementations compared to other masking schemes when implemented in dedicated hardware.
2004
EPRINT
Secure Computation of the Mean and Related Statistics
In recent years there has been massive progress in the development of technologies for storing and processing of data. If statistical analysis could be applied to such data when it is distributed between several organisations, there could be huge benefits. Unfortunately, in many cases, for legal or commercial reasons, this is not possible. The idea of using the theory of multi-party computation to analyse efficient algorithms for privacy preserving data-mining was proposed by Pinkas and Lindell. The point is that algorithms developed in this way can be used to overcome the apparent impasse described above: the owners of data can, in effect, pool their data while ensuring that privacy is maintained. Motivated by this, we describe how to securely compute the mean of an attribute value in a database that is shared between two parties. We also demonstrate that existing solutions in the literature that could be used to do this leak information, therefore underlining the importance of applying rigorous theoretical analysis rather than settling for ad hoc techniques.
2004
EPRINT
Secure Direct Communication Using Quantum Calderbank-Shor-Steane Codes
The notion of quantum secure direct communication (QSDC) has been introduced recently in quantum cryptography as a replacement for quantum key distribution, in which two communication entities exchange secure classical messages without establishing any shared keys previously. In this paper, a quantum secure direct communication scheme using quantum Calderbank-Shor-Steane (CCS) error correction codes is proposed. In the scheme, a secure message is first transformed into a binary error vector and then encrypted(decrypted) via quantum coding(decoding) procedures. An adversary Eve, who has controlled the communication channel, can't recover the secrete messages because she doesn't know the deciphering keys. Security of this scheme is based on the assumption that decoding general linear codes is intractable even on quantum computers.
2004
EPRINT
Secure Group Communications over Combined Wired/Wireless Networks
This paper considers the fundamental problem of key agreement among a group of parties communicating over an insecure public network. Over the years, a number of solutions to this problem have been proposed with varying degrees of complexity. However, there seems to have been no previous systematic look at the growing problem of key agreement over combined wired/wireless networks, consisting of both high-performance computing machines and low-power mobile devices. In this paper we present an efficient group key agreement scheme well suited for this networking environment. Our construction is intuitively simple, and yet offers a scalable solution to the problem.
2004
EPRINT
Secure Hashed Diffie-Hellman over Non-DDH Groups
We show that in applications that use the Diffie-Hellman (DH) transform but take care of hashing the DH output (as required, for example, for secure DH-based encryption and key exchange) the usual requirement to work over a DDH group (i.e., a group in which the Decisional Diffie-Hellman assumption holds) can be relaxed to only requiring that the DH group contains a large enough DDH subgroup. In particular, this implies the security of (hashed) Diffie-Hellman over non-prime order groups such as $Z_p^*$. Moreover, our results show that one can work directly over $Z_p^*$ without requiring any knowledge of the prime factorization of $p-1$ and without even having to find a generator of $Z_p^*$. These results are obtained via a general characterization of DDH groups in terms of their DDH subgroups, and a relaxation (called $t$-DDH) of the DDH assumption via computational entropy. We also show that, under the short-exponent discrete-log assumption, the security of the hashed Diffie-Hellman transform is preserved when replacing full exponents with short exponents.
2004
EPRINT
Secure Identity Based Encryption Without Random Oracles
We present a fully secure identity based encryption scheme whose proof of security does not rely on the random oracle heuristic. Security is based on the decisional bilinear Diffie-Hellman assumption. Previous constructions of this type incurred a large penalty factor in the security reduction from the underlying complexity assumption. The security reduction of the present system is polynomial in all the parameters.
2004
EPRINT
Secure Multi-party Computation for selecting a solution according to a uniform distribution over all solutions of a general combinatorial problem
Secure simulations of arithmetic circuit and boolean circuit evaluations are known to save privacy while providing solutions to any probabilistic function over a field. The problem we want to solve is to select a random solution of a general combinatorial problem. Here we discuss how to specify the need of selecting a random solution of a general combinatorial problem, as a probabilistic function. Arithmetic circuits for finding the set of all solutions are simple to design. We know no arithmetic circuit proposed in the past, selecting a single solution according to a uniform distribution over all solutions of a general constraint satisfaction problem. The only one (we) are able to design has a factorial complexity in the size of the search space (O(d^m!d^m) multiplications of secrets), where m is the number of variables and d the maximal size of a variable's domain. Nevertheless, we were able to develop a methodology combining secure arithmetic circuit evaluation and mix-nets, able to compile the problem of selecting a random solution of a CSP to a n/2-private multi-party computation assuming passive attackers. The complexity of this solution is more acceptable, O(d^m) multiplications, being therefore applicable for some reasonable problems, like meeting scheduling. Constraint satisfaction is a framework extensively used in some areas of artificial intelligence to model problems like meeting scheduling, timetabling, the stable marriages problem, and some negotiation problems. It is based on abstracting a problem as a set of variables, and a set of constraints that specify unacceptable combination of values for sets of distinct variables.
2004
EPRINT
Security of Wang-Li Threshold Signature Scheme
In 2003, Wang et al.[1] proposed a $(t, n)$ threshold signature scheme without a trusted party based on the discrete logarithm problem. In this paper, according to [5]'s attacking method, we show that there are still some security leaks in that scheme, and give some methods of forgery attack. Moreover, we point out this scheme is vulnerable to universal forgery by an insider attacker under reasonable assumptions.
2004
EPRINT
Security Analysis of a 2/3-rate Double Length Compression Function in Black-Box Model
In this paper, we propose a $2/3$-rate double length compression function and study its security in black-box model. We prove that to get a collision attack for the compression function requires $\Omega(2^{2n/3})$ queries, where $n$ is the single length output size. Thus, it has better security than a most secure single length compression function. This construction is more efficient than the construction given in~\cite{Hirose04}. Also the three computations of underlying compression functions can be done in parallel. The proof idea uses a concept of computable message which can be helpful to study security of other constructions like ~\cite{Hirose04},~\cite{Lucks04},~\cite{Nandi04} etc.
2004
EPRINT
Security Analysis of A Dynamic ID-based Remote User Authentication Scheme
Since 1981, when Lamport introduced the remote user authentication scheme using table, a plenty of schemes had been proposed with table and without table using. Recently Das, Saxena and Gulati have proposed A dynamic ID-based remote user authentication scheme. They claimed that their scheme is secure against ID-theft, and can resist the reply attacks, forgery attacks, and insider attacks and so on. In this paper we show that Das et al.?s scheme is completely insecure and using of this scheme is equivalent to an open server access without any password.
2004
EPRINT
Security and Identification Indicators for Browsers against Spoofing and Phishing Attacks
In spite of the use of standard web security measures (SSL/TLS), users enter sensitive information such as passwords into scam web sites. Such scam sites cause substantial damages to individuals and corporations. In this work, we analyze these attacks, and find they often exploit usability failures of browsers. We developed and describe TrustBar, a browser extension for improved secure identification indicators. Users can assign a name/logo to a secure site, presented by TrustBar when the browser presents that secure site; otherwise, TrustBar presents the certified site's owner name, and the name/logo of the Certificate Authority (CA) who identified the owner. Some of these ideas are already adopted by browsers, following our work. We describe usability experiments, which measure, and prove the effectiveness, of TrustBar's improved security and identification indicators. We derive general secure-usability principles from our experiments and experience with TrustBar
2004
EPRINT
Security Arguments for Partial Delegation with Warrant Proxy Signature Schemes
Proxy signature is an important cryptographic primitive and has been suggested in numerous applications. In this paper, we present an attack on the aggregate-signature-based proxy signature schemes, then point out there are two flaws in BPW notion of security for proxy signature. Furthermore, we give arguments for partial delegation with warrant proxy signature schemes. We construct a new proxy signature scheme and prove that it is secure against existentially forgery on adaptively chosen-message attacks and adaptively chosen-warrant attacks under the random oracle model.
2004
EPRINT
Security Flaws in a Pairing-based Group Signature Scheme
Deng and Zhao recently proposed a group signature scheme. We find that the scheme cannot satisfy all of the requirements of a secure group signature.
2004
EPRINT
Security of Random Key Pre-distribution Schemes With Limited Tamper Resistance
Key pre-distribution (KPD) schemes, are inherently trade-offs between security and complexity, and are perhaps well suited for securing large-scale deployments of resource constrained nodes without persistent access to a trusted authority (TA). However, the need to offset their inherent security limitations, calls for some degree of tamper - resistance of nodes. Obviously, if absolute tamper-resistance is guaranteed, KPD schemes are rendered secure. In practice, however, tamper-resistance will have some limitations which will be exploited by attackers. In this paper, we analyze the security of deployments of random key pre-distribution schemes based on some assumptions on the "extent of tamper-resistance." We argue that a "limited extent of tamper resistance" when used in conjunction with a mechanism for "periodic key updates," drastically improves the security of (especially random) KPD schemes.
2004
EPRINT
Security of Symmetric Encryption Schemes with One-Way IND-CNA Key Setup
We analyse the consequences of specific properties of the key-setup phase in symmetric encryption schemes for their security. We find that key-setup routines satisfying IND-CNA and one-wayness allow to construct schemes which are provably secure against key-recovery attacks. We propose a specific cryptosystem based on a stream cipher with a one-way IND-CNA key-setup, for which we present a proof, based on a set of scheme-specific assumptions, that it remains secure even if a successful key-recovery attack against the underlying cipher is found.
2004
EPRINT
Security on Generalized Feistel Scheme with SP Round Function
This paper studies the security against differential/linear cryptanalysis and the pseudorandomness for a class of generalized Feistel scheme with SP round function called $GFSP$. We consider the minimum number of active s-boxes in some consecutive rounds of $GFSP$,i.e., in four, eight and sixteen consecutive rounds, which provide the upper bound of the maximum differential/linear probabilities of 16-round $GFSP$ scheme, in order to evaluate the strength against differential/linear cryptanalysis. Furthermore, We investigate the pseudorandomness of $GFSP$, point out 7-round $GFSP$ is not pseudorandom for non-adaptive adversary, by using some distinguishers, and prove that 8-round $GFSP$ is pseudorandom for any adversaries.
2004
EPRINT
Security Pitfalls of an efficient remote user authentication scheme using smart cards
In 2004, W. C. Ku and S. M. Chen proposed an efficient remote user authentication scheme using smart cards to solve the security problems of Chien et al.?s scheme. Recently, Hsu and Yoon et al. pointed out the security weakness of the Ku and Chen?s scheme Furthermore, Yoon et al.?s scheme also proposed a new efficient remote user authentication scheme using smart cards. This paper analyzes the security pitfalls of Yoon et al?s scheme and aims to show that the Yoon et al.?s scheme is still vulnerable to the password guessing attack and the insider attack.
2004
EPRINT
Separable Linkable Threshold Ring Signatures
A ring signature scheme is a group signature scheme with no group manager to setup a group or revoke a signer. A linkable ring signature, introduced by Liu, et al. \cite{LWW04}, additionally allows anyone to determine if two ring signatures are signed by the same group member (a.k.a. they are \emph{linked}). In this paper, we present the first separable linkable ring signature scheme, which also supports an efficient thresholding option. We also present the security model and reduce the security of our scheme to well-known hardness assumptions. In particular, we introduce the security notions of {\em accusatory linkability} and {\em non-slanderability} to linkable ring signatures. Our scheme supports ``event-oriented'' linking. Applications to such linking criterion is discussed.
2004
EPRINT
Sequences of games: a tool for taming complexity in security proofs
This paper is a brief tutorial on a technique for structuring security proofs as sequences of games.
2004
EPRINT
Short Group Signatures
We construct a short group signature scheme. Signatures in our scheme are approximately the size of a standard RSA signature with the same security. Security of our group signature is based on the Strong Diffie-Hellman assumption and a new assumption in bilinear groups called the Decision Linear assumption. We prove security of our system, in the random oracle model, using a variant of the security definition for group signatures recently given by Bellare, Micciancio, and Warinschi.
2004
EPRINT
Short Linkable Ring Signatures for E-Voting, E-Cash and Attestation
A ring signature scheme can be viewed as a group signature scheme with no anonymity revocation and with simple group setup. A \emph{linkable} ring signature (LRS) scheme additionally allows anyone to determine if two ring signatures have been signed by the same group member. Recently, Dodis et al. \cite{DKNS04} gave a short (constant-sized) ring signature scheme. We extend it to the first short LRS scheme, and reduce its security to a new hardness assumption, the Link Decisional RSA (LD-RSA) Assumption. We also extend \cite{DKNS04}'s other schemes to a generic LRS scheme and a generic linkable group signature scheme. We discuss three applications of our schemes. Kiayias and Yung \cite{KY04} constructed the first e-voting scheme which simultaneously achieves efficient tallying, public verifiability, and write-in capability for a typical voter distribution under which only a small portion writes in. We construct an e-voting scheme based on our short LRS scheme which achieves the same even for all worst-case voter distribution. Direct Anonymous Attestation (DAA) \cite{BCC04} is essentially a ring signature scheme with certain linking properties that can be naturally implemented using LRS schemes. The construction of an offline anonymous e-cash scheme using LRS schemes is also discussed.
2004
EPRINT
Short Signatures Without Random Oracles
We describe a short signature scheme which is existentially unforgeable under a chosen message attack without using random oracles. The security of our scheme depends on a new complexity assumption we call the {\em Strong Diffie-Hellman} assumption. This assumption has similar properties to the Strong RSA assumption, hence the name. Strong RSA was previously used to construct signature schemes without random oracles. However, signatures generated by our scheme are much shorter and simpler than signatures from schemes based on Strong RSA. Furthermore, our scheme provides a limited form of message recovery.
2004
EPRINT
Short Signatures, Provable Security, Generic Attacks and Computational Security of Multivariate Polynomial Schemes such as HFE, Quartz and Sflash
This paper should be considered as a draft. Part of it is an extended version of the paper Generic Attacks and the Security of Quartz presented at PKC 2003 and at the second Nessie workshop. It also contains a lot of new material that is not published elsewhere: -(yet another) discussion about what is and what isn't a secure signature scheme -up-to-date security results fo Sflash and Quartz -new results on computational security of Sflash w.r.t algebraic relation attacks in the light of Faug?re-Joux Crypto 2003 paper. -and more... Comments are welcome !
2004
EPRINT
Side Channel Analysis for Reverse Engineering (SCARE) - An Improved Attack Against a Secret A3/A8 GSM Algorithm
Side-channel analysis has been recognized for several years as a practical and powerful means to reveal secret keys of [publicly known] cryptographic algorithms. Only very recently this kind of cryptanalysis has been applied to reverse engineer a non-trivial part of the specification of a proprietary (i.e., secret) algorithm. The target here is no longer the value of secret key but the secret specifications of the cryptographic algorithm itself. In a recent paper, Roman Novak (2003) describes how to recover the value of one (out of two) substitution table of a secret instance of the A3/A8 algorithm, the GSM authentication and session-key generation algorithm. His attack presents however two drawbacks from a practical viewpoint. First, in order to retrieve one substitution table ($T_2$), the attacker must know the value of the other substitution table ($T_1$). Second, the attacker must also know the value of secret key $K$. In this paper, we improve Novak's attack and show how to retrieve \emph{both} substitution tables ($T_1$ and $T_2$) \emph{without any prior knowledge about the secret key}. Furthermore, as a side-effect, we also recover the value of the secret key. With this contribution, we intend to present a practical SCARE (Side Channel Analysis for Reverse Engineering) attack, anticipate a growing interest for this new area of side-channel signal exploitation, and remind, if needed, that security cannot be achieved through obscurity alone.
2004
EPRINT
Sign Change Fault Attacks On Elliptic Curve Cryptosystems
We present a new type of fault attacks on elliptic curve scalar multiplications: Sign Change Attacks. These attacks exploit different number representations as they are often employed in modern cryptographic applications. Previously, fault attacks on elliptic curves aimed to force a device to output points which are on a cryptographically weak curve. Such attacks can easily be defended against. Our attack produces points which do not leave the curve and are not easily detected. The paper also presents a revised scalar multiplication algorithm that provably protects against Sign Change Attacks.
2004
EPRINT
Signature Bouquets: Immutability for Aggregated/Condensed Signatures
Database outsourcing is a popular industry trend which involves organizations delegating their data management needs to an external service provider. In this model, a service provider hosts its clients? databases and offers mechanisms for clients to create, store, update and access (query) their databases. Since a service provider is almost never fully trusted, security and privacy of outsourced data are important concerns. This paper focuses on integrity and authenticity issues in outsourced databases. Whenever someone queries a hosted database, the returned results must be demonstrably authentic: the querier needs to establish ? in an efficient manner ? that both integrity and authenticity (with respect to the actual data owner) are assured. To this end, some recent work examined two relevant signature schemes: one based on a condensed variant of batch RSA and the other ? on aggregated signature scheme by Boneh, et al. In this paper, we introduce the notion of immutability for aggregated signature schemes. Immutability refers to the difficulty of computing new valid aggregated signatures from a set of other aggregated signatures. This is an important feature, particularly for outsourced databases, as lack thereof would enable a frequent querier to eventually amass enough aggregated signatures to answer other (un-posed) queries, thus becoming a de facto service provider. Since the schemes considered in [19] do not offer immutability, we propose several practical methods to achieve it.
2004
EPRINT
Signcryption in Hierarchical Identity Based Cryptosystem
In many situations we want to enjoy confidentiality, authenticity and non-repudiation of message simultaneously. One approach to achieve this objective is to "sign-then-encrypt" the message, or we can employ special cryptographic scheme like signcryption. Two open problems about identity-based (ID-based) signcryption were proposed in \cite{CryptoePrint:2003:023}. The first one is to devise an efficient forward-secure signcryption scheme with public verifiability and public ciphertext authenticity, which is promptly closed by \cite{LNCS2971:ICISC2003:CYHC}. Another one which still remains open is to devise a hierarchical ID-based signcryption scheme that allows the user to receive signcrypted messages from sender who is under another sub-tree of the hierarchy. This paper aims at solving this problem by proposing two concrete constructions of hierarchical ID-based signcryption.
2004
EPRINT
Signed Binary Representations Revisited
The most common method for computing exponentiation of random elements in Abelian groups are sliding window schemes, which enhance the efficiency of the binary method at the expense of some precomputation. In groups where inversion is easy (e.g. elliptic curves), signed representations of the exponent are meaningful because they decrease the amount of required precomputation. The asymptotic best signed method is wNAF, because it minimizes the precomputation effort whilst the non-zero density is nearly optimal. Unfortunately, wNAF can be computed only from the least significant bit, i.e. right-to-left. However, in connection with memory constraint devices left-to-right recoding schemes are by far more valuable. In this paper we define the MOF (Mutual Opposite Form), a new canonical representation of signed binary strings, which can be computed in any order. Therefore we obtain the first left-to-right signed exponent-recoding scheme for general width w by applying the width w sliding window conversion on MOF left-to-right. Moreover, the analogue right-to-left conversion on MOF yields wNAF, which indicates that the new class is the natural left-to-right analogue to the useful wNAF. Indeed, the new class inherits the outstanding properties of wNAF, namely the required precomputation and the achieved non-zero density are exactly the same.
2004
EPRINT
Simpler Session-Key Generation from Short Random Passwords
Goldreich and Lindell (CRYPTO `01) recently presented the first protocol for password-authenticated key exchange in the standard model (with no common reference string or set-up assumptions other than the shared password). However, their protocol uses several heavy tools and has a complicated analysis. We present a simplification of the Goldreich--Lindell (GL) protocol and analysis for the special case when the dictionary is of the form $D=\{0,1\}^d$, i.e. the password is a short random string (like an ATM PIN number). Our protocol can be converted into one for arbitrary dictionaries using a common reference string of logarithmic length. The security bound achieved by our protocol is somewhat worse than the GL protocol. Roughly speaking, our protocol guarantees that the adversary can ``break'' the scheme with probability at most $O(\mathrm{poly}(n)/|D|)^{\Omega(1)}$, whereas the GL protocol guarantees a bound of $O(1/|D|)$. We also present an alternative, more natural definition of security than the ``augmented definition'' of Goldreich and Lindell, and prove that the two definitions are equivalent.
2004
EPRINT
Single Database Private Information Retrieval with Logarithmic Communication
In this paper, we study the problem of single database private information retrieval, and present schemes with only logarithmic server-side communication complexity. Previously the best result could only achieve polylogarithmic communication, and was based on certain less well-studied assumptions in number theory \cite{CMS99}. On the contrary, our construction is based on Paillier's cryptosystem \cite{P99}, which along with its variants have drawn extensive studies in recent cryptographic researches \cite{PP99,G00,CGGN01,DJ01,CGG02,CNS02,ST02,GMMV03,KT03}, and have many important applications (e.g., the Cramer-Shoup CCA2 encryption scheme in the standard model \cite{CS02}). Actually, our schemes can be directly used to implement $1$-out-of-$N$ {\em $\ell$-bit string} oblivious transfer with $O(\ell)$ sender-side communication complexity (against semi-honest receivers and malicious senders). Note the sender-side communication complexity is independent of $N$, the constant hidden in the big-$O$ notation is in fact small, and $\ell$ is unrestricted. Moreover, We also show a way to do communication balancing between the sender-side and the receiver-side. In addition, we show how to handle malicious receivers with small communication overheads, which itself is a non-trivial result.
2004
EPRINT
Solving Systems of Differential Equations of Addition
Mixing addition modulo $2^n$ ($+$) and exclusive-or ($\oplus$) have a host of applications in symmetric cryptography as the operations are fast and nonlinear over GF(2). We deal with a frequently encountered equation $(x+y)\oplus((x\oplus\x)+(y\oplus\y))=\z$. The difficulty of solving an arbitrary system of such equations -- named \emph{differential equations of addition} (DEA) -- is an important consideration in the evaluation of the security of many ciphers against \emph{differential attacks}. This paper shows that the satisfiability of an arbitrary set of DEA -- which has so far been assumed \emph{hard} for large $n$ -- is in the complexity class P. We also design an efficient algorithm to obtain all solutions to an arbitrary system of DEA with running time linear in the number of solutions.\\ Our second contribution is solving DEA in an \emph{adaptive query model} where an equation is formed by a query $(\x,\y)$ and oracle output $\z$. The challenge is to optimize the number of queries to solve $(x+y)\oplus((x\oplus\x)+(y\oplus\y))=\z$. Our algorithm solves this equation with only 3 queries in the worst case. Another algorithm solves the equation $(x+y)\oplus(x+(y\oplus\y))=\z$ with $(n-t-1)$ queries in the worst case ($t$ is the position of the least significant `1' of $x$), and thus, outperforms the previous best known algorithm by Muller -- presented at FSE~'04 -- which required $3(n-1)$ queries. Most importantly, we show that the upper bounds, for our algorithms, on the number of queries match worst case lower bounds. This, essentially, closes further research in this direction as our lower bounds are \emph{optimal}. Finally we describe applications of our results in \emph{differential cryptanalysis.
2004
EPRINT
SPA-based attack against the modular reduction within a partially secured RSA-CRT implementation
This note describes an SPA-based side channel attack against a CRT implementation of an RSA function. In contrast with Novak?s attack [8], it concentrates on the initial modular reduction. With the help of lattice reduction it applies even to implementations which use a common randomising technique to ensure resistance against certain side channel attacks.
2004
EPRINT
sSCADA: Securing SCADA Infrastructure Communications
Distributed control systems (DCS) and supervisory control and data acquisition (SCADA) systems were developed to reduce labor costs, and to allow system-wide monitoring and remote control from a central location. Control systems are widely used in critical infrastructures such as electric grid, natural gas, water, and wastewater industries. While control systems can be vulnerable to a variety of types of cyber attacks that could have devastating consequences, little research has been done to secure the control systems. This paper presents a suite of security protocols optimized for SCADA/DCS systems which include: point-to-point secure channels, authenticated broadcast channels, authenticated emergency channels, and revised authenticated emergency channels. These protocols are designed to address the specific challenges that SCADA systems have.
2004
EPRINT
Statistical Zero-Knowledge Arguments for NP Using Approximable-Preimage-Size One-Way Functions
A statistical zero knowledge argument for NP is a cryptographic primitive that allows a polynomial-time prover to convince another polynomial-time verifier of the validity of an NP statement. It is guaranteed that even an infinitely powerful verifier does not learn any additional information but the validity of the claim. Naor et al., Journal of Cryptology 1998, showed how to implement such a protocol using any one-way permutation. We achieve such a protocol using any approximable-preimage-size one-way function. These are one-way functions with the additional feature that there is a feasible way to approximate the number of preimages of a given output. A special case is regular one-way functions where each output has the same number of preimages. Our result is achieved by showing that a variant of the computationally-binding bit-commitment protocol of Naor et al. can be implemented using a any one-way functions with ``sufficiently dense'' output distribution. We construct such functions from approximable-preimage-size one-way functions using ``hashing techniques'' inspired by Hastad et al., SIAM Journal on Computing 1998.
2004
EPRINT
Suitable Curves for Genus-4 HCC over Prime Fields: Point Counting Formulae for Hyperelliptic Curves of type $y^2=x^{2k+1}+ax$
Computing the order of the Jacobian group of a hyperelliptic curve over a finite field is very important to construct a hyperelliptic curve cryptosystem (HCC), because to construct secure HCC, we need Jacobian groups of order in the form $l(J\(Bcdot c$ where $l$ is a prime greater than about $2^{160}$ and $c$ is a very small integer. But even in the case of genus two, known algorithms to compute the order of a Jacobian group for a general curve need a very long running time over a large prime field. In the case of genus three, only a few examples of suitable curves for HCC are known. In the case of genus four, no example has been known over a large prime field. In this article, we give explicit formulae of the order of Jacobian groups for hyperelliptic curves over a finite prime field of type $y^2=x^{2k+1}+a x$, which allows us to search suitable curves for HCC. By using these formulae, we can find many suitable curves for genus-4 HCC and show some examples.
2004
EPRINT
Summation polynomials and the discrete logarithm problem on elliptic curves
The aim of the paper is the construction of the index calculus algorithm for the discrete logarithm problem on elliptic curves. The construction presented here is based on the problem of finding bounded solutions to some explicit modular multivariate polynomial equations. These equations arise from the elliptic curve summation polynomials introduced here and may be computed easily. Roughly speaking, we show that given the algorithm for solving such equations, which works in polynomial or low exponential time in the size of the input, one finds discrete logarithms faster than by means of Pollard's methods.
2004
EPRINT
Superfluous Keys in Multivariate Quadratic Asymmetric Systems
In this article, we show that public key schemes based on multivariate quadratic equations allow many equivalent, and hence superfluous private keys. We achieve this result by investigating several transformations to identify these keys and show their application to Hidden Field Equations (HFE), C$^*$, and Unbalanced Oil and Vinegar schemes (UOV). In all cases, we are able to reduce the size of the private --- and hence the public --- key space by at least one order of magnitude. We see applications of our technique both in cryptanalysis of these schemes and in memory efficient implementations.
2004
EPRINT
Symmetric Encryption in a Simulatable Dolev-Yao Style Cryptographic Library
Recently we solved the long-standing open problem of justifying a Dolev-Yao type model of cryptography as used in virtually all automated protocol provers under active attacks. The justification was done by defining an ideal system handling Dolev-Yao-style terms and a cryptographic realization with the same user interface, and by showing that the realization is as secure as the ideal system in the sense of reactive simulatability. This definition encompasses arbitrary active attacks and enjoys general composition and property-preservation properties. Security holds in the standard model of cryptography and under standard assumptions of adaptively secure primitives. A major primitive missing in that library so far is symmetric encryption. We show why symmetric encryption is harder to idealize in a way that allows general composition than existing primitives in this library. We discuss several approaches to overcome these problems. For our favorite approach we provide a detailed provably secure idealization of symmetric encryption within the given framework for constructing nested terms.
2004
EPRINT
Synthesis of Secure FPGA Implementations
This paper describes the synthesis of Dynamic Differential Logic to increase the resistance of FPGA implementations against Differential Power Analysis. The synthesis procedure is developed and a detailed description is given of how EDA tools should be used appropriately to implement a secure digital design flow. Compared with an existing technique to implement Dynamic Differential Logic on FPGA, the technique saves a factor 2 in slice utilization. Experimental results also indicate that a secure version of the AES encryption algorithm can now be implemented with a mere 50% increase in time delay and 90% increase in slice utilization when compared with a normal non-secure single ended implementation.
2004
EPRINT
Tail-MAC: A Message Authentication Scheme for Stream Ciphers
Tail-MAC, A predecessor to the VMPC-MAC, algorithm for computing Message Authentication Codes for stream ciphers is described along with the analysis of its security. The proposed algorithm was designed to employ some of the data already computed by the underlying stream cipher in the purpose of minimizing the computational cost of the operations required by the MAC algorithm. The performed analyses indicate several problems with the security of the scheme and lead to a new design which described in a paper "VMPC-MAC: A Stream Cipher Based Authenticated Encryption Scheme". The new scheme solves all the problems found at a cost of some compromise in the performance.
2004
EPRINT
The conjugacy search problem in public key cryptography: unnecessary and insufficient
The conjugacy search problem in a group $G$ is the problem of recovering an $x \in G$ from given $g \in G$ and $h=x^{-1}gx$. This problem is in the core of several recently suggested public key exchange protocols, most notably the one due to Anshel, Anshel, and Goldfeld, and the one due to Ko, Lee at al. In this note, we make two observations that seem to have eluded most people's attention. The first observation is that solving the conjugacy search problem is not necessary for an adversary to get the common secret key in the Ko-Lee protocol. It is sufficient to solve an apparently easier problem of finding $x, y \in G$ such that $h=ygx$ for given $g, h \in G$. Another observation is that solving the conjugacy search problem is not sufficient for an adversary to get the common secret key in the Anshel-Anshel-Goldfeld protocol.
2004
EPRINT
The CS2 Block Cipher
In this paper we describe our new CS$^2$ block cipher which is an extension of the original CS-Cipher. Our new design inherits the efficiency of the original design while being upgraded to support a larger block size as well as use a slightly improved substitution box. We prove that our design is immune to differential and linear cryptanalysis as well as argue it resists several other known attacks.
2004
EPRINT
The CSQUARE Transform
In this paper we show how to combine the design concepts of the SQUARE and CS block ciphers to produce a pseudo-random permutation CSQUARE suitable for use in block cipher and hash design with a very high multi-round trail weight. The new design inherits the hardware efficiency of the SQUARE linear transform pattern as well as the efficiency of the fast pseudo-Hadamard transform over a finite field. We demonstrate the DMWT hash function which makes use of our new results.
2004
EPRINT
The Exact Security of an Identity Based Signature and its Applications
This paper first positively answers the previously open question of whether it was possible to obtain an optimal security reduction for an identity based signature (IBS) under a reasonable computational assumption. We revisit the Sakai-Ogishi-Kasahara IBS that was recently proven secure by Bellare, Namprempre and Neven through a general framework applying to a large family of schemes. We show that their modified SOK-IBS scheme can be viewed as a one-level instantiation of Gentry and Silverberg's alternative hierarchical IBS the exact security of which was never considered before. We also show that this signature is as secure as the one-more Diffie-Hellman problem. As an application, we propose a modification of Boyen's "Swiss Army Knife" identity based signature encryption (IBSE) that presents better security reductions and satisfies the same strong security requirements with a similar efficiency.
2004
EPRINT
The Extended Codebook (XCB) Mode of Operation
We describe a block cipher mode of operation that implements a `tweakable' (super) pseudorandom permutation with an arbitrary block length. This mode can be used to provide the best possible security in systems that cannot allow data expansion, such as disk-block encryption and some network protocols. The mode accepts an additional input, which can be used to protect against attacks that manipulate the ciphertext by rearranging the ciphertext blocks. Our mode is similar to a five-round Luby-Rackoff cipher in which the first and last rounds do not use the conventional Feistel structure, but instead use a single block cipher invocation. The third round is a Feistel structure using counter mode as a PRF. The second and fourth rounds are Feistel structures using a universal hash function; we re-use the polynomial hash over a binary field defined in the Galois/Counter Mode (GCM) of operation for block ciphers. This choice provides efficiency in both hardware and software and allows for re-use of implementation effort. XCB also has several useful properties: it accepts arbitrarily-sized plaintexts and associated data, including any plaintexts with lengths that are no smaller than the width of the block cipher. This document is a pre-publication draft manuscript.
2004
EPRINT
The Hierarchy of Key Evolving Signatures and a Characterization of Proxy Signatures
For the last two decades the notion and implementations of proxy signatures have been used to allow transfer of digital signing power within some context (in order to enable flexibility of signers within organizations and among entities). On the other hand, various notions of the key-evolving signature paradigms (forward-secure, key-insulated, and intrusion-resilient signatures) have been suggested in the last few years for protecting the security of signature schemes, localizing the damage of secret key exposure. In this work we relate the various notions via direct and concrete security reductions that are tight. We start by developing the first formal model for fully hierarchical proxy signatures, which, as we point out, also addresses vulnerabilities of previous schemes when self-delegation is used. Next, we prove that proxy signatures are, in fact, equivalent to key-insulated signatures. We then use this fact and other results to establish a tight hierarchy among the key-evolving notions, showing that intrusion-resilient signatures and key-insulated signatures are equivalent, and imply forward-secure signatures. We also introduce other relations among extended notions. Besides the importance of understanding the relationships among the various notions that were originally designed with different goals or with different system configuration in mind, our findings imply new designs of schemes. For example, many proxy signatures have been presented without formal model and proofs, whereas using our results we can employ the work on key-insulated schemes to suggest new provably secure designs of proxy signatures schemes.
2004
EPRINT
The Knowledge-of-Exponent Assumptions and 3-Round Zero-Knowledge Protocols
Hada and Tanaka showed the existence of 3-round, negligible-error zero-knowledge arguments for NP based on a pair of non-standard assumptions, here called KEA1 and KEA2. In this paper we show that KEA2 is false. This renders vacuous the results of Hada and Tanaka. We recover these results, however, under a suitably modified new assumption called KEA3. What we believe is most interesting is that we show that it is possible to ``falsify'' assumptions like KEA2 that, due to their nature and quantifier-structure, do not lend themselves easily to ``efficient falsification'' (Naor).
2004
EPRINT
The Mundja Streaming MAC
Mundja is a MAC generation algorithm that has been designed for use together with a stream cipher. Mundja accumulates the message onto two independent registers: the first is a Cyclic Redundancy Checksum (CRC) that uses linear feedback; the second is a strengthened version of the SHA-256 register that uses nonlinear feedback. Mundja is fast (asymptotically about 4 times the speed of HMAC-SHA-256), and can generate MACs of any desired length. Mundja is designed to be secure at the equivalent level of 128-bit keys. When used in cooperation with a correspondingly secure stream cipher, it is hoped to remain secure even at the equivalent level of 256-bit keys. Appendices give details of the use of Mundja with the SOBER-128, Turing and RC4 stream ciphers.
2004
EPRINT
The Polynomial Composition Problem in $(\mathbb{Z}/n\mathbb{Z})[X]$
Let $n$ be an RSA modulus and let $P,Q \in (\mathbb{Z}/n\mathbb{Z})[X]$. This paper explores the following problem: Given $Q$ and $Q(P)$, find~$P$. We shed light on the connections between the above problem to the RSA problem and derive from it new zero-knowledge protocols.
2004
EPRINT
The Power of Verification Queries in Message Authentication and Authenticated Encryption
This paper points out that, contrary to popular belief, allowing a message authentication adversary multiple verification attempts towards forgery is NOT equivalent to allowing it a single one, so that the notion of security that most message authentication schemes are proven to meet does not guarantee their security in practice. We then show, however, that the equivalence does hold for STRONG unforgeability. Based on this we recover security of popular classes of message authentication schemes such as MACs (including HMAC and PRF-based MACs) and CW-schemes. Furthermore, in many cases we do so with a TIGHT security reduction, so that in the end the news we bring is surprisingly positive given the initial negative result. Finally, we show analogous results for authenticated encryption.
2004
EPRINT
The Rabbit Stream Cipher - Design and Security Analysis
The stream cipher Rabbit was rst presented at FSE 2003 [6]. In the paper at hand, a full security analysis of Rabbit is given, focusing on algebraic attacks, approximations and di erential analysis. We determine the algebraic normal form of the main nonlinear parts of the cipher as part of a comprehensive algebraic analysis. In addition, both linear and nonlinear approximations of the next-state function are presented, as well as a differential analysis of the IV-setup function. None of the investigations have revealed any exploitable weaknesses. Rabbit is characterized by high performance in software with a measured encryption/decryption speed of 3.7 clock cycles per byte on a Pentium III processor.
2004
EPRINT
The Reactive Simulatability (RSIM) Framework for Asynchronous Systems
We define \emph{reactive simulatability} for general asynchronous systems. Roughly, simulatability means that a real system implements an ideal system (specification) in a way that preserves security in a general cryptographic sense. Reactive means that the system can interact with its users multiple times, e.g., in many concurrent protocol runs or a multi-round game. In terms of distributed systems, reactive simulatability is a type of refinement that preserves particularly strong properties, in particular confidentiality. A core feature of reactive simulatability is \emph{composability}, i.e., the real system can be plugged in instead of the ideal system within arbitrary larger systems; this is shown in follow-up papers, and so is the preservation of many classes of individual security properties from the ideal to the real systems. A large part of this paper defines a suitable system model. It is based on probabilistic IO automata (PIOA) with two main new features: One is \emph{generic distributed scheduling}. Important special cases are realistic adversarial scheduling, procedure-call-type scheduling among colocated system parts, and special schedulers such as for fairness, also in combinations. The other is the definition of the \emph{reactive runtime} via a realization by Turing machines such that notions like polynomial-time are composable. The simple complexity of the transition functions of the automata is not composable. As specializations of this model we define security-specific concepts, in particular a separation beween honest users and adversaries and several trust models. The benefit of IO automata as the main model, instead of only interactive Turing machines as usual in cryptographic multi-party computation, is that many cryptographic systems can be specified with an ideal system consisting of only one simple, deterministic IO automaton without any cryptographic objects, as many follow-up papers show. This enables the use of classic formal methods and automatic proof tools for proving larger distributed protocols and systems that use these cryptographic systems.
2004
EPRINT
The Security and Efficiency of Micciancio's Cryptosystem
We report experiments on the security of the GGH-like cryptosystem proposed by Micciancio. Based on these experiments, we conclude that the system can be securely used only in lattice dimensions > 781. Further experiments on the efficiency of the system show that it requires key sizes of 1 MByte and more and that the key generation as well as the decryption take inacceptibly long. Therefore, Micciancio's cryptosystem seems currently far from being practical.
2004
EPRINT
The Security and Performance of the Galois/Counter Mode of Operation (Full Version)
The recently introduced Galois/Counter Mode (GCM) of operation for block ciphers provides both encryption and message authentication, using universal hashing based on multiplication in a binary finite field. We analyze its security and performance, and show that it is the most efficient mode of operation for high speed packet networks, by using a realistic model of a network crypto module and empirical data from studies of Internet traffic in conjunction with software experiments and hardware designs. GCM has several useful features: it can accept IVs of arbitrary length, can act as a stand-alone message authentication code (MAC), and can be used as an incremental MAC. We show that GCM is secure in the standard model of concrete security, even when these features are used. We also consider several of its important system-security aspects.
2004
EPRINT
The Security of the FDH Variant of Chaum's Undeniable Signature Scheme
In this paper, we first introduce a new kind of adversarial goal called {\em forge-and-impersonate} in undeniable signature schemes. Note that forgeability does not necessarily imply impersonation ability. We then classify the security of the FDH variant of Chaum's undeniable signature scheme according to three dimensions, the goal of adversaries, the attacks and the ZK level of confirmation and disavowal protocols. We finally relate each security to some well-known computational problem. In particular, we prove that the security of the FDH variant of Chaum's scheme with NIZK confirmation and disavowal protocols is equivalent to the CDH problem, as opposed to the GDH problem as claimed by Okamoto and Pointcheval.
2004
EPRINT
The Sorcerer?s Apprentice Guide to Fault Attacks
The effect of faults on electronic systems has been studied since the 1970s when it was noticed that radioactive particles caused errors in chips. This led to further research on the effect of charged particles on silicon, motivated by the aerospace industry who was becoming concerned about the effect of faults in airborn electronic systems. Since then various mechanisms for fault creation and propagation have been discovered and researched. This paper covers the various methods that can be used to induce faults in semiconductors and exploit such errors maliciously. Several examples of attacks stemming from the exploiting of faults are explained. Finally a series of countermeasures to thwart these attacks are described.
2004
EPRINT
The Static Diffie-Hellman Problem
The static Diffie-Hellman problem (SDHP) is the special case of the classic Diffie-Hellman problem where one of the public keys is fixed. We establish that the SDHP is almost as hard as the associated discrete logarithm problem. We do this by giving a reduction that shows that if the SDHP can be solved then the associated private key can be found. The reduction also establishes that certain systems have less security than anticipated. The systems affected are based on static Diffie-Hellman key agreement and do not use a key derivation function. This includes some cryptographic protocols: basic ElGamal encryption; Chaum and van Antwerpen's undeniable signature scheme; and Ford and Kaliski's key retrieval scheme, which is currently being standardized in IEEE P1363.2.
2004
EPRINT
The Vulnerability of SSL to Chosen Plaintext Attack
The Secure Sockets Layer (SSL) protocol is widely used for securing communication over the Internet. When utilizing block ciphers for encryption, the SSL standard mandates the use of the cipher block chaining (CBC) mode of encryption which requires an initialization vector (IV) in order to encrypt. Although the initial IV used by SSL is a (pseudo)random string which is generated and shared during the initial handshake phase, subsequent IVs used by SSL are chosen in a deterministic, predictable pattern; in particular, the IV of a message is taken to be the final ciphertext block of the immediately-preceding message. We show that this introduces a vulnerability in SSL which (potentially) enables easy recovery of low-entropy strings such as passwords or PINs that have been encrypted. Moreover, we argue that the open nature of web browsers provides a feasible ``point of entry'' for this attack via a corrupted plug-in; thus, implementing the attack is likely to be much easier than, say, installing a Trojan Horse for ``keyboard sniffing''. Finally, we suggest a number of modifications to the SSL standard which will prevent this attack.
2004
EPRINT
Timed-Release and Key-Insulated Public Key Encryption
In this paper we consider two security notions related to Identity Based Encryption: Key-insulated public key encryption, introduced by Dodis, Katz, Xu and Yung; and Timed-Release Public Key cryptography, introduced independently by May and Rivest, Shamir and Wagner. We first formalize the notion of secure timed-release public key encryption, and show that, despite several differences in its formulation, it is equivalent to strongly key-insulated public key encryption (with optimal threshold and random access key updates). Next, we introduce the concept of an authenticated timed-release cryptosystem, briefly consider generic constructions, and then give a construction based on a single primitive which is efficient and provably secure.
2004
EPRINT
Towards Plaintext-Aware Public-Key Encryption without Random Oracles
We consider the problem of defining and achieving plaintext-aware encryption without random oracles in the classical public-key model. We provide definitions for a hierarchy of notions of increasing strength: PA0, PA1 and PA2, chosen so that PA1+IND-CPA => IND-CCA1 and PA2+IND-CPA => IND-CCA2. Towards achieving the new notions of plaintext awareness, we show that a scheme due to Damgard, denoted DEG, and the ``lite'' version of the Cramer-Shoup scheme, denoted CSL, are both PA0 under the KEA0 assumption of Damgard, and PA1 under an extension of this assumption called KEA1. As a result, DEG is the most efficient proven IND-CCA1 scheme known.
2004
EPRINT
Traceable Signatures
We present, implement and apply a new privacy primitive that we call ``Traceable Signatures.'' To this end we develop the underlying mathematical and protocol tools, present the concepts and the underlying security model, and then realize the scheme and its security proof. Traceable signatures support an extended set of fairness mechanisms (mechanisms for anonymity management and revocation) when compared with the traditional group signature mechanism. We demonstrate that this extended function is needed for proper operation and adequate level of privacy in various settings and applications. For example, the new notion allows (distributed) tracing of all signatures by a single (misbehaving) party without opening signatures and revealing identities of any other user in the system. In contrast, if such tracing is implemented by a state of the art group signature system, such wide opening of all signatures of a single user is a (centralized) operation that requires the opening of {\em all} anonymous signatures and revealing the users associated with them, an act that violates the privacy of all users. Our work includes a novel modeling of security in privacy systems that leads to simulation-based proofs. Security notions in privacy systems are typically more complex than the traditional security of cryptographic systems, thus our modeling methodology may find future applications in other settings. To allow efficient implementation of our scheme we develop a number of basic tools, zero-knowledge proofs, protocols, and primitives that we use extensively throughout. These novel mechanisms work directly over a group of unknown order, contributing to the efficiency and modularity of our design, and may be of independent interest. The interactive version of our signature scheme yields the notion of ``traceable (anonymous) identification.''
2004
EPRINT
Tracing-by-Linking Group Signautres
In a group signature \cite{CvH91}, any group member can sign on behalf of the group while remaining anonymous, but its identity can be traced in an future dispute investigation. Essentially all state-of-the-art group signatures implement the tracing mechnism by requiring the signer to escrow its identity to an Open Authority (OA) \cite{ACJT00,CL02scn,BMW03,KiayiasYu04,BSZ05,BBS04,KiayiasTsYu04}. We call them {\em Tracing-by-Escrowing (TbE)} group signatures. One drawback is that the OA also has the unnecessary power to trace without proper cause. In this paper we introduce {\em Tracing-by-Linking (TbL)} group signatures. The signer's anonymity is irrevocable by any authority if the group member signs only once (per event). But if a member signs twice, its identity can be traced by a public algorithm without needing any trapdoor. We initiate the formal study of TbL group signatures by introducing its security model, constructing the first examples, and give several applications. Our core construction technique is the successful transplant of the TbL technique from single-term offline e-cash from the blind signature framework \cite{Brands93,Ferguson93,Ferguson93c} to the group signature framework. Our signatures have size $O(1)$.
2004
EPRINT
Transitive Signatures Based on Non-adaptive Standard Signatures
Transitive signature, motivated by signing vertices and edges of a dynamically growing, transitively closed graph, was first proposed by Micali and Rivest. The general designing paradigm proposed there involved a underlying standard signature scheme, which is required to be existentially unforgeable against adaptive chosen message attacks. We show that the requirement for the underlying signature is not necessarily so strong, instead non-adaptive security is enough to guarantee the transitive signature scheme secure in the strongest sense, i.e, transitively unforgeable under adaptive chosen message attack (defined by Bellare and Neven). We give a general proof of such transitive signature schemes, and also propose a specific transitive signature scheme based on factoring and strong-RSA. Hence the choice of standard signatures that can be employed by transitive signature schemes is enlarged. The efficiency of transitive signature schemes may be improved since efficiency and security are trade-off parameters for standard signature schemes.
2004
EPRINT
Tree Parity Machine Rekeying Architectures
The necessity to secure the communication between hardware components in embedded systems becomes increasingly important with regard to the secrecy of data and particularly its commercial use. We suggest a low-cost (i.e. small logic-area) solution for flexible security levels and short key lifetimes. The basis is an approach for symmetric key exchange using the synchronisation of Tree Parity Machines. Fast successive key generation enables a key exchange within a few milliseconds, given realistic communication channels with a limited bandwidth. For demonstration we evaluate characteristics of a standard-cell ASIC design realisation as IP-core in 0.18 micrometer-technology.
2004
EPRINT
TTS: Rank Attacks in Tame-Like Multivariate PKCs
We herein discuss two modes of attack on multivariate public-key cryptosystems. A 2000 Goubin-Courtois article applied these techniques against a special class of multivariate PKC's called ``Triangular-Plus-Minus'' (TPM), and may explain in part the present dearth of research on ``true'' multivariates -- multivariate PKC's in which the middle map is not really taken in a much larger field. These attacks operate by finding linear combinations of matrices with a given rank. Indeed, we can describe the two attacks very aptly as ``high-rank'' and ``low-rank''. However, TPM was not general enough to cover all pertinent true multivariate PKC's. \emph{Tame-like} PKC's, multivariates with relatively few terms per equation in the central map and an easy inverse, is a superset of TPM that can enjoy both fast private maps and short set-up times. However, inattention can still let rank attacks succeed in tame-like PKCs. The TTS (Tame Transformation Signatures) family of digital signature schemes lies at this cusp of contention. Previous TTS instances (proposed at ICISC '03) claim good resistance to other known attacks. But we show how careless construction in current TTS instances (TTS/4 and TTS/$2'$) exacerbates the security concern of rank, and show two different cryptanalysis in under $2^{57}$ AES units. TTS is not the only tame-like PKC with these liabilities -- they are shared by a few other misconstructed schemes. A suitable equilibrium between speed and security must be struck. We suggest a generic way to craft tame-like PKC's more resistant to rank attacks. A demonstrative TTS variant with similar dimensions is built for which rank attack takes $>2^{80}$ AES units, while remaining very fast and as resistant to other attacks. The proposed TTS variants can scale up. In short: We show that rank attacks apply to the wider class of tame-like PKC's, sometimes even better than previously described. However, this is relativized by the realization that we can build adequately resistant tame-like multivariate PKC's, so the general theme still seem viable compared to more traditional or large-field multivariate alternatives.
2004
EPRINT
Two Software Normal Basis Multiplication Algorithms for GF(2n)
In this paper, two different normal basis multiplication algorithms for software implementation are proposed over GF(2n). The first algorithm is suitable for high complexity normal bases and the second algorithm is fast for type-I optimal normal bases and low complexity normal bases. The ANSI C source program is also included in this paper.
2004
EPRINT
Universal Forgeability of a Forward-Secure Blind Signature Scheme Proposed by Duc et al
Duc et al. proposed a forward-secure blind signature scheme in [1]. They claimed that the scheme is constructed from the provably secure Okamoto-Guilou-Quisquater blind signature scheme. But we recently found that their scheme is insecure. In the paper, we show the scheme is universally forgeable by a simple and direct attack.
2004
EPRINT
Universal Forgeability of Wang-Wu-Wang Key-Insulated Signature Scheme
Wang et al. recently proposed a new perfect and strong key-insulated signature scheme in [1]. We find that the scheme is universally forgeable. In the paper we present a simple and direct attack on it.
2004
EPRINT
Universal Undeniable Signatures
In this paper, we provide a new approach to study undeniable signatures by translating secure digital signatures to secure undeniable signatures so that the existing algorithms can be used. Our mechanism is that any verifier without trapdoor information cannot distinguish whether a message is encoded from Diffie-Hellamn resource $D$ or random resource $R$ while a signer with trapdoor information can distinguish efficiently a codeword which is computed from $D$ or $R$. We show how our mechanism can be efficiently achieved and provide proofs of security for our schemes in the standard complexity model. We also provide evidences to show that our approach can be applied to construct designated confirmer signatures, designated verifier signatures as well.
2004
EPRINT
Universally Composable DKG with Linear Number of Exponentiations
Many problems have been solved by protocols using discrete-logarithm based threshold cryptosystems. Such protocols require a random joint public key for which the secret key is shared among the parties. A multiparty protocol that generates such a key is called a DKG protocol. Until now no DKG protocol is known to be universally composable. We extend Feldman's original verifiable secret sharing scheme to construct a DKG protocol, and prove that it is universally composable. Our result holds in a common random string model under the Decision Diffie-Hellman assumption. We stress that we do not need any trapdoor for the common random string. Our protocol is optimistic. If all parties behave honestly, each party computes only $O(3k)$ exponentiations, where $k$ is the number of parties. In the worst case each party computes $O(k^2)$ exponentiations. This should be contrasted with previous constructions in which each party computes $\Omega(k^2)$ exponentiations regardless of if they behave honestly or not. In the optimistic case the number of bits sent in our protocol is essentially equal to the number of bits sent in $k$ independent copies of Feldman's original protocol.
2004
EPRINT
Universally Composable Symbolic Analysis of Cryptographic Protocols (The case of encryption-based mutual authentication and key exchange)
Symbolic analysis of cryptographic protocols is dramatically simpler than full-fledged cryptographic analysis. In particular, it is readily amenable to automation. However, symbolic analysis does not a priori carry any cryptographic soundness guarantees. Following recent work on cryptographically sound symbolic analysis, we demonstrate how Dolev-Yao style symbolic analysis can be used to assert the security of cryptographic protocols within the universally composable (UC) security framework. Consequently, our methods enable security analysis that is completely symbolic, and at the same time cryptographically sound with strong composability properties. More specifically, we define a mapping from a class of cryptographic protocols to Dolev-Yao style symbolic protocols. For this mapping, we show that the symbolic protocol satisfies a certain symbolic criterion if and only if the corresponding cryptographic protocol is UC-secure. We concentrate on mutual authentication and key-exchange protocols that use public-key encryption as their only cryptographic primitive. For mutual authentication, our symbolic criterion is similar to the traditional Dolev-Yao criterion. For key exchange, we demonstrate that the traditional Dolev-Yao style symbolic criterion is insufficient, and formulate an adequate symbolic criterion. Finally, to demonstrate the viability of the treatment, we use an existing automated verification tool to assert UC security of some prominent key exchange protocols.
2004
EPRINT
Untraceability of Wang-Fu Group Signature Scheme
Wang et al. recently proposed an improved edition based on Tseng-Jan group signature scheme${}^{[1]}$. In the paper, we show that the scheme is untraceable by a simple attack.
2004
EPRINT
Updating the Parameters of a Threshold Scheme by Minimal Broadcast
Threshold schemes allow secret data to be protected amongst a set of participants in such a way that only a pre-specified threshold of participants can reconstruct the secret from private information (shares) distributed to them on system setup using secure channels. We consider the general problem of designing unconditionally secure threshold schemes whose defining parameters (the threshold and the number of participants) can later be changed by using only public channel broadcast messages. In this paper we are interested in the efficiency of such threshold schemes, and seek to minimise storage costs (size of shares) as well as optimise performance in low bandwidth environments by minimising the size of necessary broadcast messages. We prove a number of lower bounds on the smallest size of broadcast message necessary to make general changes to the parameters of a threshold scheme in which each participant already holds shares of minimal size. We establish the tightness of these bounds by demonstrating optimal schemes.
2004
EPRINT
Upper and Lower Bounds on Black-Box Steganography
We study the limitations of steganography when the sender is not using any properties of the underlying channel beyond its entropy and the ability to sample from it. On the negative side, we show that the number of samples the sender must obtain from the channel is exponential in the rate of the stegosystem. On the positive side, we present the first secret-key stegosystem that essentially matches this lower bound regardless of the entropy of the underlying channel. Furthermore, for high-entropy channels, we present the first secret-key stegosystem that matches this lower bound statelessly (i.e., without requiring synchronized state between sender and receiver).
2004
EPRINT
Upper Bounds for the Selection of the Cryptographic Key Lifetimes: Bounding the Risk of Key Exposure in the Presence of Faults
With physical attacks threatening the security of current cryptographic schemes, no security policy can be developed without taking into account the physical nature of computation. In this article we first introduce the notion of \emph{Cryptographic Key Failure Tolerance}, then we offer a framework for the determination of upper bounds to the key lifetimes for any cryptographic scheme used in the presence of faults, given a desired (negligible) error-bound to the risk of key exposure. Finally we emphasize the importance of choosing keys and designing schemes with good values of failure tolerance, and recommend minimal values for this metric. In fact, in \emph{standard environmental conditions}, cryptographic keys that are especially susceptible to erroneous computations (e.g., RSA keys used with CRT-based implementations) are exposed with a probability greater than a standard error-bound (e.g., ${2^{-40}}$) after operational times shorter than one year, if the failure-rate of the cryptographic infrastructure is greater than ${1.04\times10^{-16}}$ {\it failures/hours}.
2004
EPRINT
Upper Bounds on the Communication Complexity of Optimally Resilient Cryptographic Multiparty Computation
We give improved upper bounds on the communication complexity of optimally-resilient secure multiparty computation in the cryptographic model. We consider evaluating an $n$-party randomized function and show that if $f$ can be computed by a circuit of size $c$, then $\O(c n^2 \kappa)$ is an upper bound for active security with optimal resilience $t < n/2$ and security parameter $\kappa$. This improves on the communication complexity of previous protocols by a factor of at least $n$. This improvement comes from the fact that in the new protocol, only $\O(n)$ messages (of size $\O(\kappa)$ each) are broadcast during the \emph{whole} protocol execution, in contrast to previous protocols which require at least $\O(n)$ broadcasts \emph{per gate}. Furthermore, we improve the upper bound on the communication complexity of passive secure multiparty computation with resilience $t<n$ from $\O(c n^2 \kappa)$ to $\O(c n \kappa)$. This improvement is mainly due to a simple observation.
2004
EPRINT
Using primitive subgroups to do more with fewer bits
This paper gives a survey of some ways to improve the efficiency of discrete log-based cryptography by using the restriction of scalars and the geometry and arithmetic of algebraic tori and abelian varieties.
2004
EPRINT
Vectorial Boolean functions and induced algebraic equations
A general mathematical framework behind algebraic cryptanalytic attacks is developed. The framework relates to finding algebraic equations induced by vectorial Boolean functions and, in particular, equations of low algebraic degree. The equations may involve only a subset of input variables and may or may not be conditioned on the values of output variables. In addition, the equations may have a special form interesting for the so-called fast algebraic attacks. A possible divide-and-conquer effect is pointed out and the notion of algebraic immunity order, naturally extending the notion of correlation immunity order, is introduced. An application of general results to stream ciphers known as combiners with or without memory, with possibly multiple outputs, is studied in particular detail. Special properties of combiners with finite input memory, such as nonlinear filter generators, are established. Finally, finding induced algebraic equations for divide-and-conquer algebraic attacks on combiners with or without memory is also considered.
2004
EPRINT
Vectorial fast correlation attacks
A new, vectorial approach to fast correlation attacks on binary memoryless combiners is proposed. Instead of individual input sequences or their linear combinations, the new attack is targeting subsets of input sequences as a whole, thus exploiting the full correlation between the chosen subset and the output sequence. In particular, all the input sequences can be targeted simultaneously. The attack is based on a novel iterative probabilistic algorithm which is also applicable to general memoryless combiners over finite fields or finite rings. Experimental results obtained for randomly chosen binary combiners with balanced combining functions show that the vectorial approach yields a considerable improvement in comparison with the classical, scalar approach.
2004
EPRINT
VMPC-MAC: A Stream Cipher Based Authenticated Encryption Scheme
A stream cipher based algorithm for computing Message Authentication Codes is described. The algorithm employs the internal state of the underlying cipher to minimize the required additional-to-encryption computational effort and maintain general simplicity of the design. The scheme appears to provide proper statistical properties, a comfortable level of resistance against forgery attacks in a chosen ciphertext attack model and high efficiency in software implementations.
2004
EPRINT
Why Quantum Cryptography?
Quantum Key Exchange (QKE, also known as Quantum Key Distribution or QKD) allows communicating parties to securely establish cryptographic keys. It is a well-established fact that all QKE protocols require that the parties have access to an authentic channel. Without this authenticated link, QKE is vulnerable to man-in-the-middle attacks. Unfortunately this fact is frequently overlooked, resulting in exaggerated claims and/or false expectations about the potential impact of QKE. In this paper we present a systematic comparison of QKE with traditional key exchange protocols in realistic secure communication systems.
2004
EPRINT
Yet another attack on a password authentication scheme based on quadratic residues with parameters unknown 1
In 1988, Harn, Laih and Huang proposed a password authentication scheme based on quadratic residues. However, in 1995, Chang, Wu and Laih pointed out that if the parameters d b a , , and l are known by the intruder, this scheme can be broken. In this paper, we presented another attack on the Harn-Laih-Huang scheme. In our attack, it doesn’t need to know the parameters and it is more efficient than the Chang-Wu-Laih attack.