All papers (Page 193 of 21762 results)

Last updated:  2008-01-22
HB#: Increasing the Security and Efficiency of HB+
Henri Gilbert, Matthew J. B. Robshaw, Yannick Seurin
The innovative HB+ protocol of Juels and Weis [10] extends device authentication to low-cost RFID tags. However, despite the very simple on-tag computation there remain some practical problems with HB+ and despite an elegant proof of security against some limited active attacks, there is a simple man-in-the-middle attack due to Gilbert et al. [8]. In this paper we consider improvements to HB+ in terms of both security and practicality. We introduce a new protocol that we denote random-HB#. This proposal avoids many practical drawbacks of HB+, remains provably resistant to attacks in the model of Juels and Weis, and at the same time is provably resistant to a broader class of active attacks that includes the attack of [8]. We then describe an enhanced variant called HB# which offers practical advantages over HB+.
Last updated:  2008-01-22
Blind Signature Scheme over Braid Groups
Girraj Kumar Verma
A blind signature scheme is a cryptographic protocol for obtaining a signature from a signer such that the signer's view of the protocol cannot be linked to the resulting message signature pair. In this paper we have proposed two blind signature schemes using Braid groups. The security of given schemes depends upon conjugacy search problem in Braid groups.
Last updated:  2008-06-02
Pairing-friendly Hyperelliptic Curves with Ordinary Jacobians of Type $y^2=x^5+ax$
Mitsuru Kawazoe, Tetsuya Takahashi
An explicit construction of pairing-friendly hyperelliptic curves with ordinary Jacobians was firstly given by D.~Freeman. In this paper, we give other explicit constructions of pairing-friendly hyperelliptic curves with ordinary Jacobians based on the closed formulae for the order of the Jacobian of a hyperelliptic curve of type $y^2=x^5+ax$. We present two methods in this paper. One is an analogue of the Cocks-Pinch method and the other is a cyclotomic method. By using these methods, we construct a pairing-friendly hyperelliptic curve $y^2=x^5+ax$ over a finite prime field ${¥mathbb F}_p$ whose Jacobian is ordinary and simple over ${¥mathbb F}_p$ with a prescribed embedding degree. Moreover, the analogue of the Cocks-Pinch produces curves with $¥rho¥approx 4$ and the cyclotomic method produces curves with $3¥le ¥rho¥le 4$.
Last updated:  2008-01-22
Non-Cyclic Subgroups of Jacobians of Genus Two Curves with Complex Multiplication
Uncategorized
Christian Robenhagen Ravnshoj
Show abstract
Uncategorized
Let E be an elliptic curve defined over a finite field. Balasubramanian and Koblitz have proved that if the l-th roots of unity m_l is not contained in the ground field, then a field extension of the ground field contains m_l if and only if the l-torsion points of E are rational over the same field extension. We generalize this result to Jacobians of genus two curves with complex multiplication. In particular, we show that the Weil- and the Tate-pairing on such a Jacobian are non-degenerate over the same field extension of the ground field.
Last updated:  2008-01-22
Identity Based Strong Bi-Designated Verifier Proxy Signature Schemes
Sunder Lal, Vandani Verma
Proxy signature schemes allow delegation of signing rights. The paper proposes the notion of Identity Based Strong Bi-Designated Verifier Proxy Signature (ID-SBDVPS) schemes. In such schemes, only the two designated verifiers can verify that the proxy signer on behalf of the original signer signed the message but none of them is able to convince anyone else of this fact. The paper proposes nine such schemes and analyses the computational efficiency of each.
Last updated:  2008-06-23
General Certificateless Encryption and Timed-Release Encryption
Sherman S. M. Chow, Volker Roth, Eleanor G. Rieffel
While recent timed-release encryption (TRE) schemes are implicitly supported by a certificateless encryption (CLE) mechanism, the security models of CLE and TRE differ and there is no generic transformation from a CLE to a TRE. This paper gives a generalized model for CLE that fulfills the requirements of TRE. This model is secure against adversaries with adaptive trapdoor extraction capabilities, decryption capabilities for arbitrary public keys, and partial decryption capabilities. It also supports hierarchical identifiers. We propose a concrete scheme under our generalized model and prove it secure without random oracles, yielding the first strongly-secure security-mediated CLE and the first TRE in the standard model. In addition, our technique of partial decryption is different from the previous approach.
Last updated:  2008-01-22
Computing Almost Exact Probabilities of Differential Hash Collision Paths by Applying Appropriate Stochastic Methods
Uncategorized
M. Gebhardt, G. Illies, W. Schindler
Show abstract
Uncategorized
Generally speaking, the probability of a differential path determines an upper bound for the expected workload and thus for the true risk potential of a differential attack. In particular, if the expected workload seems to be in a borderline region between practical feasibility and non-feasibility it is desirable to know the path probability as exact as possible. We present a generally applicable approach to determine at least almost exact probabilities of differential paths where we focus on (near-)collision paths for Merkle-Damgard-type hash functions. Our results show both that the number of bit conditions provides only a rough estimate for the true path probability and that the IV may have significant impact on the path probability. For MD5 we verified the effectivity of our approach experimentally. An abbreviated version [GIS4], which in particular omits proofs, technical details and several examples, will appear in the proceedings of the security conference 'Sicherheit 2008'.
Last updated:  2008-02-15
Block Ciphers Implementations Provably Secure Against Second Order Side Channel Analysis
Matthieu Rivain, Emmanuelle Dottax, Emmanuel Prouff
In the recent years, side channel analysis has received a lot of attention, and attack techniques have been improved. Side channel analysis of second order is now successful in breaking implementations of block ciphers supposed to be effectively protected. This progress shows not only the practicability of second order attacks, but also the need for provably secure countermeasures. Surprisingly, while many studies have been dedicated to the attacks, only a few papers have been published about the dedicated countermeasures. In fact, only the method proposed by Schramm and Paar at CT-RSA 2006 enables to thwart second order side channel analysis. In this paper, we introduce two new methods which constitute a worthwhile alternative to Schramm and Paar's proposition. We prove their security in a strong security model and we exhibit a way to signifficantly improve their efficiency by using the particularities of the targeted architectures. Finally, we argue that the introduced methods allow to efficiently protect a wide variety of block ciphers, including AES.
Last updated:  2008-06-23
CCA2 Secure IBE: Standard Model Efficiency through Authenticated Symmetric Encryption
Eike Kiltz, Yevgeniy Vahlis
We propose two constructions of chosen-ciphertext secure identity-based encryption (IBE) schemes. Our schemes have a security proof in the standard model, yet they offer performance competitive with all known random-oracle based schemes. The efficiency improvement is obtained by combining modifications of the IBE schemes by Waters and Gentry with authenticated symmetric encryption.
Last updated:  2008-01-22
Computing Pairings Using x-Coordinates Only
Uncategorized
Steven D. Galbraith, Xibin Lin
Show abstract
Uncategorized
To reduce bandwidth in elliptic curve cryptography one can transmit only $x$-coordinates of points (or $x$-coordinates together with an extra bit). For further computation using the points one can either recover the $y$-coordinates by taking square roots or one can use point multiplication formulae which use $x$-coordinates only. We consider how to efficiently use point compression in pairing-based cryptography. We give a method to compute compressed Weil pairings using $x$-coordinates only. We also show how to compute the compressed Tate and ate pairings using only one $y$-coordinate. Our methods are more efficient than taking square roots when the embedding degree is small. We implemented the algorithms in the case of embedding degree 2 curves over $\F_p$ where $p \equiv 3 \pmod{4}$ and found that our methods are $10-15\%$ faster than the analogous methods using square roots.
Last updated:  2008-01-14
Disjunctive Multi-Level Secret Sharing
Mira Belenkiy
A disjunctive multi-level secret sharing scheme divides users into different levels. Each level L is associated with a threshold t_L, and a group of users can only recover the secret if, for some L, there are at least t_L users at levels 0....L in the group. We present a simple ideal disjunctive multi-level secret sharing scheme -- in fact, the simplest and most direct scheme to date. It is the first polynomial-time solution that allows the dealer to add new users dynamically. Our solution is by far the most efficient; the dealer must perform O(t) field operations per user, where t is the highest threshold in the system. We demonstrate the simplicity of our scheme by extending our construction into a distributed commitment scheme using standard techniques.
Last updated:  2008-02-20
New State Recovery Attack on RC4
Uncategorized
Alexander Maximov, Dmitry Khovratovich
Show abstract
Uncategorized
The stream cipher RC4 was designed by R.~Rivest in 1987, and it has a very simple and elegant structure. It is probably the most deployed cipher on the Earth. ~~~~In this paper we analyse the class RC4-$N$ of RC4-like stream ciphers, where $N$ is the modulus of operations, as well as the length of internal arrays. Our new attack is a state recovery attack which accepts the keystream of a certain length, and recovers the internal state. For the original RC4-256, our attack has total complexity of around $2^{241}$ operations, whereas the best previous attack needs $2^{779}$ of time. Moreover, we show that if the secret key is of length $N$ bits or longer, the new attack works faster than an exhaustive search. The algorithm of the attack was implemented and verified on small cases.
Last updated:  2011-10-08
ECM using Edwards curves
Uncategorized
Daniel J. Bernstein, Peter Birkner, Tanja Lange, Christiane Peters
Show abstract
Uncategorized
This paper introduces EECM-MPFQ, a fast implementation of the elliptic-curve method of factoring integers. EECM-MPFQ uses fewer modular multiplications than the well-known GMP-ECM software, takes less time than GMP-ECM, and finds more primes than GMP-ECM. The main improvements above the modular-arithmetic level are as follows: (1) use Edwards curves instead of Montgomery curves; (2) use extended Edwards coordinates; (3) use signed-sliding-window addition-subtraction chains; (4) batch primes to increase the window size; (5) choose curves with small parameters and base points; (6) choose curves with large torsion.
Last updated:  2009-01-21
Practical Short Signature Batch Verification
Anna Lisa Ferrara, Matthew Green, Susan Hohenberger, Michael Østergaard Pedersen
In many applications, it is desirable to work with signatures that are both short, and yet where many messages from different signers be verified very quickly. RSA signatures satisfy the latter condition, but are generally thousands of bits in length. Recent developments in pairing-based cryptography produced a number of short signatures which provide equivalent security in a fraction of the space. Unfortunately, verifying these signatures is computationally intensive due to the expensive pairing operation. In an attempt to simultaneously achieve "short and fast" signatures, Camenisch, Hohenberger and Pedersen (Eurocrypt 2007) showed how to batch verify two pairing-based schemes so that the total number of pairings was independent of the number of signatures to verify. In this work, we present both theoretical and practical contributions. On the theoretical side, we introduce new batch verifiers for a wide variety of regular, identity-based, group, ring and aggregate signature schemes. These are the first constructions for batching group signatures, which answers an open problem of Camenisch et al. On the practical side, we implement each of these algorithms and compare each batching algorithm to doing individual verifications. Our goal is to test whether batching is practical; that is, whether the benefits of removing pairings significantly outweigh the cost of the additional operations required for batching, such as group membership testing, randomness generation, and additional modular exponentiations and multiplications. We experimentally verify that the theoretical results of Camenisch et al. and this work, indeed, provide an efficient, effective approach to verifying multiple signatures from (possibly) different signers.
Last updated:  2008-01-14
Simulatable Adaptive Oblivious Transfer
Jan Camenisch, Gregory Neven, abhi shelat
We study an adaptive variant of oblivious transfer in which a sender has N messages, of which a receiver can adaptively choose to receive k one-after-the-other, in such a way that (a) the sender learns nothing about the receiver’s selections, and (b) the receiver only learns about the k requested messages. We propose two practical protocols for this primitive that achieve a stronger security notion than previous schemes with comparable efficiency. In particular, by requiring full simulatability for both sender and receiver security, our notion prohibits a subtle selective-failure attack not addressed by the security notions achieved by previous practical schemes. Our first protocol is a very efficient generic construction from unique blind signatures in the random oracle model. The second construction does not assume random oracles, but achieves remarkable efficiency with only a constant number of group elements sent during each transfer. This second construction uses novel techniques for building efficient simulatable protocols.
Last updated:  2008-03-13
Twisted Edwards Curves
Uncategorized
Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange, Christiane Peters
Show abstract
Uncategorized
This paper introduces ``twisted Edwards curves,'' a generalization of the recently introduced Edwards curves; shows that twisted Edwards curves include more curves over finite fields, and in particular every elliptic curve in Montgomery form; shows how to cover even more curves via isogenies; presents fast explicit formulas for twisted Edwards curves in projective and inverted coordinates; and shows that twisted Edwards curves save time for many curves that were already expressible as Edwards curves.
Last updated:  2008-04-29
The Encrypted Elliptic Curve Hash
Daniel R. L. Brown
Bellare and Micciancio's MuHASH applies a pre-existing hash function to map indexed message blocks into a secure group. The resulting hash is the product. Bellare and Micciancio proved, in the random oracle model, that MuHASH is collision-resistant if the group's discrete logarithm problem is infeasible. MuHASH, however, relies on a pre-existing hash being collision resistant. In this paper, we remove such a reliance by replacing the pre-existing hash with a block cipher under a fixed key. We adapt Bellare and Micciancio's collision-resistance proof to the ideal cipher model. Preimage resistance requires us to add a further modification.
Last updated:  2008-01-08
A simple generalization of the {E}l{G}amal cryptosystem to non-abelian groups II
Ayan Mahalanobis
In this paper I study the MOR cryptosystem using the special linear group over finite fields. At our current state of knowledge, I show that the MOR cryptosystem is more secure than the ElGamal cryptosystem over finite fields.
Last updated:  2016-02-22
A Proof of Security in $O(2^n)$ for the Xor of Two Random Permutations\\ -- Proof with the ``$H_{\sigma}$ technique''--
Uncategorized
Jacques Patarin
Show abstract
Uncategorized
Xoring two permutations is a very simple way to construct pseudorandom functions from pseudorandom permutations. The aim of this paper is to get precise security results for this construction. Since such construction has many applications in cryptography (see \cite{BI,BKrR,HWKS,SL} for example), this problem is interesting both from a theoretical and from a practical point of view. In \cite{SL}, it was proved that Xoring two random permutations gives a secure pseudorandom function if $m \ll 2^{\frac {2n}{3}}$. By ``secure'' we mean here that the scheme will resist all adaptive chosen plaintext attacks limited to $m$ queries (even with unlimited computing power). More generally in \cite{SL} it is also proved that with $k$ Xor, instead of 2, we have security when $m \ll 2^{\frac {kn}{k+1}}$. In this paper we will prove that for $k=2$, we have in fact already security when $m \ll O(2^n)$. Therefore we will obtain a proof of a similar result claimed in \cite{BI} (security when $m\ll O(2^n /n^{2/3})$). Moreover our proof is very different from the proof strategy suggested in \cite{BI} (we do not use Azuma inequality and Chernoff bounds for example, but we will use the ``$H_{\sigma}$ technique'' as we will explain), and we will get precise and explicit $O$ functions. Another interesting point of our proof is that we will show that this (cryptographic) problem of security is directly related to a very simple to describe and purely combinatorial problem.
Last updated:  2013-04-14
Generic Attacks for the Xor of k random permutations
Jacques Patarin
\begin{abstract} Xoring the output of $k$ permutations, $k\geq 2$ is a very simple way to construct pseudo-random functions (PRF) from pseudo-random permutations (PRP). Moreover such construction has many applications in cryptography (see \cite{BI,BKrR,HWKS,SL} for example). Therefore it is interesting both from a theoretical and from a practical point of view, to get precise security results for this construction. In this paper, we will describe the best attacks that we have found on the Xor of $k$ random $n$-bit to $n$-bit permutations. When $k=2$, we will get an attack of computational complexity $O(2^n)$. This result was already stated in \cite{BI}. On the contrary, for $k \geq 3$, our analysis is new. We will see that the best known attacks require much more than $2^n$ computations when not all of the $2^n$ outputs are given, or when the function is changed on a few points. We obtain like this a new and very simple design that can be very usefull when a security larger than $2^n$ is wanted, for example when $n$ is very small. \end{abstract}
Last updated:  2008-05-13
Factoring Polynomials for Constructing Pairing-friendly Elliptic Curves
Zhitu su, Hui Li, Jianfeng Ma
In this paper we present a new method to construct a polynomial $u(x) \in \mathbb{Z}[x]$ which will make $\mathrm{\Phi}_{k}(u(x))$ reducible. We construct a finite separable extension of $\mathbb{Q}(\zeta_{k})$, denoted as $\mathbb{E}$. By primitive element theorem, there exists a primitive element $\theta \in \mathbb{E}$ such that $\mathbb{E}=\mathbb{Q}(\theta)$. We represent the primitive $k$-th root of unity $\zeta_{k}$ by $\theta$ and get a polynomial $u(x) \in \mathbb{Q}[x]$ from the representation. The resulting $u(x)$ will make $\mathrm{\Phi}_{k}(u(x))$ factorable.
Last updated:  2008-05-07
Efficient One-round Key Exchange in the Standard Model
Colin Boyd, Yvonne Cliff, Juan M. Gonzalez Nieto, Kenneth G. Paterson
We consider one-round identity-based key exchange protocols secure in the standard model. The security analysis uses the powerful security model of Canetti and Krawczyk and a natural extension of it to the ID-based setting. It is shown how KEMs can be used in a generic way to obtain two different protocol designs with progressively stronger security guarantees. A detailed analysis of the performance of the protocols is included; surprisingly, when instantiated with specific KEM constructions, the resulting protocols are competitive with the best previous schemes that have proofs only in the random oracle model.
Last updated:  2013-08-30
Joint State Theorems for Public-Key Encryption and Digital Signature Functionalities with Local Computation
Ralf Kuesters, Max Tuengerthal
In frameworks for universal composability, complex protocols can be built from sub-protocols in a modular way using composition theorems. However, as first pointed out and studied by Canetti and Rabin, this modular approach often leads to impractical implementations. For example, when using a functionality for digital signatures within a more complex protocol, parties have to generate new verification and signing keys for every session of the protocol. This motivates to generalize composition theorems to so-called joint state (composition) theorems, where different copies of a functionality may share some state, e.g., the same verification and signing keys. In this paper, we present a joint state theorem which is more general than the original theorem of Canetti and Rabin, for which several problems and limitations are pointed out. We apply our theorem to obtain joint state realizations for three functionalities: public-key encryption, replayable public-key encryption, and digital signatures. Unlike most other formulations, our functionalities model that ciphertexts and signatures are computed locally, rather than being provided by the adversary. To obtain the joint state realizations, the functionalities have to be designed carefully. Other formulations proposed in the literature are shown to be unsuitable. Our work is based on the IITM model. Our definitions and results demonstrate the expressivity and simplicity of this model. For example, unlike Canetti's UC model, in the IITM model no explicit joint state operator needs to be defined and the joint state theorem follows immediately from the composition theorem in the IITM model.
Last updated:  2008-02-08
Information Theoretic Evaluation of Side-Channel Resistant Logic Styles
Francois Mace, Francois-Xavier Standaert, Jean-Jacques Quisquater
We propose to apply an information theoretic metric to the evaluation of side-channel resistant logic styles. Due to the long design and development time required for the physical evaluation of such hardware countermeasures, our analysis is based on simulations. Although they do not aim to replace the need of actual measurements, we show that simulations can be used as a meaningful first step in the validation chain of a cryptographic product. For illustration purposes, we apply our methodology to gate-level simulations of different logic styles and stress that it allows a significant improvement of the previously considered evaluation methods. In particular, our results allow putting forward the respective strengths and weaknesses of actual countermeasures and determining to which extent they can practically lead to secure implementations (with respect to a noise parameter), if adversaries were provided with simulation-based side-channel traces. Most importantly, the proposed methodology can be straightforwardly adapted to adversaries provided with any other kind of leakage traces (including physical ones).
Last updated:  2008-07-08
Efficient Tweakable Enciphering Schemes from (Block-Wise) Universal Hash Functions
Palash Sarkar
This paper describes several constructions of tweakable strong pseudorandom permutations (SPRPs) built from different modes of operations of a block cipher and suitable universal hash functions. For the electronic codebook (ECB) based construction, an invertible blockwise universal hash function is required. We simplify an earlier construction of such a function described by Naor and Reingold. The other modes of operations considered are the counter mode and the output feedback (OFB) mode. All the constructions make the same number of block cipher calls and the same number of multiplications. Combined with a class of polynomials defined by Bernstein, the new constructions provide the currently best known algorithms for the important practical problem of disk encryption.
Last updated:  2008-01-03
On Collisions of Hash Functions Turbo SHA-2
Vlastimil Klima
In this paper we don't examine security of Turbo SHA-2 completely; we only show new collision attacks on it, with smaller complexity than it was considered by Turbo SHA-2 authors. In [1] they consider Turbo SHA-224/256-r and Turbo SHA-384/512-r with variable number of rounds r from 1 to 8. The authors of [1] show collision attack on Turbo SHA-256-1 with one round which has the complexity of 2^64. For other r from 2 to 8 they don't find better attack than with the complexity of 2^128. Similarly, for Turbo SHA-512 they find only collision attack on Turbo SHA-512-1 with one round which has the complexity of 2^128. For r from 2 to 8 they don't find better attack than with the complexity of 2^256. In this paper we show collision attack on SHA-256-r for r = 1, 2,..., 8 with the complexity of 2^{16*r}. We also show collision attack on Turbo SHA-512-r for r = 1, 2,..., 8 with the complexity of 2^{32*r}. It follows that the only one remaining candidate from the hash family Turbo SHA is Turbo SHA-256 (and Turbo SHA-512) with 8 rounds. The original security reserve of 6 round has been lost.
Last updated:  2008-01-03
Fuzzy Identity Based Signature
Piyi Yang, Zhenfu Cao, Xiaolei Dong
We introduce a new cryptographic primitive which is the signature analogue of fuzzy identity based encryption(IBE). We call it fuzzy identity based signature(IBS). It possesses similar error-tolerance property as fuzzy IBE that allows a user with the private key for identity $\omega$ to decrypt a ciphertext encrypted for identity $\omega'$ if and only if $\omega$ and $\omega'$ are within a certain distance judged by some metric. A fuzzy IBS is useful whenever we need to allow the user to issue signature on behalf of the group that has certain attributes. Fuzzy IBS can also be applied to biometric identity based signature. To our best knowledge, this primitive was never considered in the identity based signature before. We give the definition and security model of the new primitive and present the first practical implementation based on Sahai-Waters construction\cite{6} and the two level hierarchical signature of Boyen and Waters\cite{9}. We prove that our scheme is existentially unforgeable against adaptively chosen message attack without random oracles.
Last updated:  2008-01-03
Security Proof for the Improved Ryu-Yoon-Yoo Identity-Based Key Agreement Protocol
Shengbao Wang, Zhenfu Cao, Kim-Kwang Raymond Choo, Lihua Wang
Key agreement protocols are essential for secure communications in open and distributed environments. The protocol design is, however, extremely error-prone as evidenced by the iterative process of fixing discovered attacks on published protocols. We revisit an efficient identity-based (ID-based) key agreement protocol due to Ryu, Yoon and Yoo. The protocol is highly efficient and suitable for real-world applications despite offering no resilience against key-compromise impersonation (K-CI). We then show that the protocol is, in fact, insecure against reflection attacks. A slight modification to the protocol is proposed, which results in significant benefits for the security of the protocol without compromising on its efficiency. Finally, we prove the improved protocol secure in a widely accepted model.
Last updated:  2008-01-07
TinyPBC: Pairings for Authenticated Identity-Based Non-Interactive Key Distribution in Sensor Networks
Uncategorized
Leonardo B. Oliveira, Michael Scott, Julio López, Ricardo Dahab
Show abstract
Uncategorized
Key distribution in Wireless Sensor Networks (WSNs) is challenging. Symmetric cryptosystems can perform it efficiently, but they often do not provide a perfect trade-off between resilience and storage. Further, even though conventional public key and elliptic curve cryptosystem are computationally feasible on sensor nodes, protocols based on them are not. They require exchange and storage of large keys and certificates, which is expensive. Using Pairing-based Cryptography (PBC) protocols, conversely, parties can agree on keys without any interaction. In this work, we (i) show how security in WSNs can be bootstrapped using an authenticated identity-based non-interactive protocol and (ii) present TinyPBC, to our knowledge, the most efficient implementation of PBC primitives for an 8-bit processor. TinyPBC is an open source code able to compute pairings as well as binary multiplication in about 5.5s and 4019.46$\mu$s, respectively, on the ATmega128L 7.3828-MHz/4KB SRAM/128KB ROM processor -- the MICA2 and MICAZ node processor.
Last updated:  2008-05-06
MAC-free variant of KD04
Uncategorized
Xianhui Lu, Xuejia Lai, Dake He
Uncategorized
Kurosawa and Desmedt proposed an efficient hybrid encryption scheme(KD04) which is secure against adaptive chosen ciphertext attacks(IND-CCA) although the underlying KEM(key encapsulation mechanism) is not IND-CCA secure\cite{Kurosawa2004}. We show a variant of KD04 which is IND-CCA secure when the the underlying DEM part is IND-CCA secure. We need a DEM built from one-time symmetric encryption scheme and a MAC in the security reduction to check if the KEM part of a ciphertext is valid. However in the real situation we can check if the KEM part of the ciphertext is valid without the help of the MAC. So the hybrid encryption scheme can also use redundancy-free IND-CCA secure DEMs that avoid the overhead due to the MAC. When using redundancy-free(MAC-free) IND-CCA secure DEMs, the new scheme will be more efficient than KD04 in bandwidth.
Last updated:  2007-12-28
Differential Fault Analysis on the AES Key Schedule
Junko Takahashi, Toshinori Fukunaga
This letter proposes a differential fault analysis on the AES key schedule and shows how an entire 128-bit AES key can be retrieved. In the workshop at FDTC 2007, we presented the DFA mechanism on the AES key schedule and proposed general attack rules. Using our proposed rules, we showed an efficient attack that can retrieve 80 bits of the 128-bit key. Recently, we have found a new attack that can obtain an additional 8 bits compared with our previous attack. As a result, we present most efficient attack for retrieving 88 bits of the 128-bit key using approximately two pairs of correct and faulty ciphertexts.
Last updated:  2008-05-15
An Efficient Identification Protocol and the Knowledge-of-Exponent Assumption
J. Wu, D. R. Stinson
In this paper, we propose an extremely simple identification protocol and prove its security using the Knowledge-of-Exponent Assumption (KEA). We discuss the applicability of KEA in various protocol settings as well. Recently, doubts have been raised about applying KEA in some protocols where an adversary has auxiliary inputs. However, we suggest that KEA is applicable in these cases. We present two variants of KEA, Generalized KEA (GKEA) and Auxiliary-Input KEA (AI-KEA), to clarify the proper use of KEA.
Last updated:  2010-06-06
Impossibility Results for Universal Composability in Public-Key Models and with Fixed Inputs
Dafna Kidron, Yehuda Lindell
Universal composability and concurrent general composition consider a setting where secure protocols are run concurrently with each other and with arbitrary other possibly insecure protocols. Protocols that meet the definition of universal composability are guaranteed to remain secure even when run in this strongly adversarial setting. In the case of an honest majority, or where there is a trusted setup phase of some kind (like a common reference string or the key-registration public-key infrastructure of Barak et al.~in FOCS 2004), it has been shown that any functionality can be securely computed in a universally composable way. On the negative side, it has also been shown that in the {\em plain model}\/ where there is no trusted setup at all, there are large classes of functionalities which cannot be securely computed in a universally composable way without an honest majority. In this paper we extend these impossibility results for universal composability. We study a number of public-key models and show for which models the impossibility results of universal composability hold and for which they do not. We also consider a setting where the inputs to the protocols running in the network are fixed before any execution begins. The majority of our results are negative and we show that the known impossibility results for universal composability in the case of no honest majority extend to many other settings.
Last updated:  2007-12-28
Algebraic Side-Channel Collision Attacks on AES
Andrey Bogdanov, Andrey Pyshkin
This paper presents a new powerful side-channel cryptanalytic method - algebraic collision attacks - representing an efficient class of power analysis being based on both the power consumption information leakage and specific structure of the attacked cryptographic algorithm. This can result in an extremely low measurement count needed for a key recovery. The algebraic collision attacks are well applicable to AES, if one-byte collisions are detectable. For the recovery of the complete AES key, one needs 3 measurements with a probability of 0.42 and 4.24 PC hours post-processing, 4 measurements with a probability of 0.82 and several seconds of offline computations or 5 measurements with success probability close to 1 and several seconds of post-processing.
Last updated:  2008-11-20
Dynamic SHA
Uncategorized
Xu Zijie
Show abstract
Uncategorized
In this paper I describe the construction of Dynamic SHA family of cryptographic hash functions. They are built with design components from the SHA-2 family, but there is function R in the new hash functionh. It enabled us to achieve a novel design principle: When message is changed, different rotate right operation maybe done. It make the system can resistant against all extant attacks.
Last updated:  2007-12-19
Obtaining Universally Composable Security: Towards the Bare Bones of Trust
Ran Canetti
A desirable goal for cryptographic protocols is to guarantee security when the protocol is composed with other protocol instances. Universally Composable (UC) security provides this guarantee in a strong sense: A UC-secure protocol maintains its security properties even when composed concurrently with an unbounded number of instances of arbitrary protocols. However, many interesting cryptographic tasks are provably impossible to realize with UC security in the standard, ``plain'' model of computation. Impossibility holds even if ideally authenticated communication channels are provided. In contrast, it has been demonstrated that general secure computation can be obtained in a number of idealized models. Each one of these models represents a form of trust that is put in some of the system's components. This survey examines and compares some of these trust models, both from the point of view of their sufficiency for building UC secure protocols, and from the point of view of their practical realizability. We start with the common reference string (CRS) model, and then describe several relaxations and alternatives including the Defective CRS model, the key registration models, the hardware token model, the global and augmented CRS models, and a timing assumption. Finally, we briefly touch upon trust models for obtaining authenticated communication.
Last updated:  2008-08-25
Notes on the Wang et al. $2^{63}$ SHA-1 Differential Path
Martin Cochran
Although advances in SHA-1 cryptanalysis have been made since the 2005 announcement of a $2^{63}$ attack by Wang et al., the details of the attack have not yet been vetted; this note does just that. Working from Adi Shamir's 2005 CRYPTO rump session presentation of Wang et al.'s work, this note corroborates and presents the differential path and associated conditions for the two-block attack. Although the error analysis for the advanced condition correction technique is not verified, a method is given which yields a two-block collision attack on SHA-1 requiring an estimated $2^{62}$ SHA-1 computations if the original error analysis by Wang et al. is correct.
Last updated:  2007-12-26
Authenticated Key Exchange and Key Encapsulation Without Random Oracles
Tatsuaki Okamoto
This paper presents a new paradigm to realize cryptographic primitives such as authenticated key exchange and key encapsulation without random oracles under three assumptions: the decisional Diffie-Hellman (DDH) assumption, target collision resistant (TCR) hash functions and a class of pseudo-random functions (PRFs), $\pi$PRFs, PRFs with pairwise-independent random sources. We propose a (PKI-based) two-pass authenticated key exchange (AKE) protocol that is comparably as efficient as the existing most efficient protocols like MQV and that is secure without random oracles (under these assumptions). Our protocol is shown to be secure in the (currently) strongest security definition, the extended Canetti-Krawczyk (eCK) security definition introduced by LaMacchia, Lauter and Mityagin. We also show that a variant of the Kurosawa-Desmedt key encapsulation mechanism (KEM) using a $\pi$PRF is CCA-secure under the three assumptions. This scheme is secure in a stronger security notion, the chosen public-key and ciphertext attack (CPCA) security, with using a generalized TCR (GTCR) hash function in place of a TCR hash function. The proposed schemes in this paper are validity-check-free and the implication is that combining them with validity-check-free symmetric encryption (DEM) will yield validity-check-free (e.g., MAC-free) CCA-secure hybrid encryption.
Last updated:  2008-03-14
New Features of Latin Dances: Analysis of Salsa, ChaCha, and Rumba
Uncategorized
Jean-Philippe Aumasson, Simon Fischer, Shahram Khazaei, Willi Meier, Christian Rechberger
Show abstract
Uncategorized
The stream cipher Salsa20 was introduced by Bernstein in 2005 as a candidate in the eSTREAM project, accompanied by the reduced versions Salsa20/8 and Salsa20/12. ChaCha is a variant of Salsa20 aiming at bringing better diffusion for similar performance. Variants of Salsa20 with up to 7 rounds (instead of 20) have been broken by differential cryptanalysis, while ChaCha has not been analyzed yet. We introduce a novel method for differential cryptanalysis of Salsa20 and ChaCha, inspired by correlation attacks and related to the notion of neutral bits. This is the first application of neutral bits in stream cipher cryptanalysis. It allows us to break the 256-bit version of Salsa20/8, to bring faster attacks on the 7-round variant, and to break 6- and 7-round ChaCha. In a second part, we analyze the compression function Rumba, built as the XOR of four Salsa20 instances and returning a 512-bit output. We find collision and preimage attacks for two simplified variants, then we discuss differential attacks on the original version, and exploit a high-probability differential to reduce complexity of collision search from 2^256 to 2^79 for 3-round Rumba. To prove the correctness of our approach we provide examples of collisions and near-collisions on simplified versions.
Last updated:  2007-12-19
Attacks on the WEP protocol
Erik Tews
WEP is a protocol for securing wireless networks. In the past years, many attacks on WEP have been published, totally breaking WEP’s security. This thesis summarizes all major attacks on WEP. Additionally a new attack, the PTW attack, is introduced, which was partially developed by the author of this document. Some advanced versions of the PTW attack which are more suiteable in certain environments are described as well. Currently, the PTW attack is fastest publicly known key recovery attack against WEP protected networks.
Last updated:  2007-12-19
Faster Multi-Exponentiation through Caching: Accelerating (EC)DSA Signature Verification
Bodo Möller, Andy Rupp
We consider the task of computing power products $\prod_{1 \leq i \leq k} g_i^{e_i}$ ("multi-exponentiation") where base elements $g_2, ..., g_k$ are fixed while $g_1$ is variable between multi-exponentiations but may repeat, and where the exponents are bounded (e.g., in a finite group). We present a new technique that entails two different ways of computing such a result. The first way applies to the first occurrence of any $g_1$ where, besides obtaining the actual result, we create a cache entry based on $g_1$, investing very little memory or time overhead. The second way applies to any multi-exponentiation once such a cache entry exists for the $g_1$ in question: the cache entry provides for a significant speed-up. Our technique is useful for ECDSA or DSA signature verification with common domain parameters and recurring signers.
Last updated:  2008-12-04
ID-Based Group Password-Authenticated Key Exchange
Uncategorized
Xun Yi, Raylin Tso, Eiji Okamoto
Show abstract
Uncategorized
Password-authenticated key exchange (PAKE) protocols are designed to be secure even when the secret key used for authentication is a human-memorable password. In this paper, we consider PAKE protocols in the group scenario, in which a group of clients, each of them shares a password with an ``honest but curious'' server, intend to establish a common secret key (i.e., a group key) with the help of the server. In this setting, the key established is known to the clients only and no one else, including the server. Each client needs to remember passwords only while the server keeps passwords in addition to private keys related to his identity. Towards our goal, we present a compiler that transforms any group key exchange (KE) protocol secure against a passive eavesdropping to a group PAKE which is secure against an active adversary who controls all communication in the network. This compiler is built on any group KE protocol (e.g., the Burmester-Desmedt protocol), any identity-based encryption (IBE) scheme (e.g., Gentry's scheme), and any identity-based signature (IBS) scheme (e.g., Paterson-Schuldt scheme). It adds only two rounds and $O(1)$ communication (per client) to the original group KE protocol. As long as the underlying group KE protocol, IBE scheme and an IBS scheme have provably security without random oracles, a group PAKE constructed by our compiler can be proven to be secure without random oracles.
Last updated:  2009-10-24
On the hash function of ODH assumption
Uncategorized
Xianhui Lu, Xuejia Lai, Dake He, Guomin Li
Uncategorized
M. Abdalla, M. Bellare and P. Rogaway proposed a variation of Diffie-Hellman assumption named as oracle Diffie-Hellman(ODH) assumption. They recommend to use a one-way cryptographic hash function for the ODH assumption. We notice that if the hash function is just one-way then there will be an attack. We show that if the the hash function is non-malleable then the computational version of ODH assumption can be reduced to the computational Diffie-Hellman(CDH) assumption. But we can not reduce the ODH assumption to the decisional Diffie-Hellman(DDH) even if the hash function is non-malleable. It seems that we need a random oracle hash function to reduce the ODH assumption to the DDH assumption.
Last updated:  2007-12-19
Interactive and Noninteractive Zero Knowledge are Equivalent in the Help Model
Uncategorized
André Chailloux, Dragos Florin Ciocan, Iordanis Kerenidis, Salil Vadhan
Show abstract
Uncategorized
We show that interactive and noninteractive zero-knowledge are equivalent in the `help model' of Ben-Or and Gutfreund ({\em J. Cryptology}, 2003). In this model, the shared reference string is generated by a probabilistic polynomial-time dealer who is given access to the statement to be proven. Our results do not rely on any unproven complexity assumptions and hold for statistical zero knowledge, for computational zero knowledge restricted to AM, and for quantum zero knowledge when the help is a pure quantum state.
Last updated:  2008-03-06
Improved Impossible Differential Cryptanalysis of CLEFIA
Wei Wang, Xiaoyun Wang
This paper presents an improved impossible differential attack on the new block cipher CLEFIA which is proposed by Sony Corporation at FSE 2007. Combining some observations with new tricks, we can filter out the wrong keys more efficiently, and improve the impossible differential attack on 11-round CLEFIA-192/256, which also firstly works for CLEFIA-128. The complexity is about $2^{103.1}$ encryptions and $2^{103.1}$ chosen plaintexts. By putting more constraint conditions on plaintext pairs, we give the first attack on 12-round CLEFIA for all three key lengths with $2^{119.1}$ encryptions and $2^{119.1}$ chosen plaintexts. For CLEFIA-192/256, our attack is applicable to 13-round variant, of which the time complexity is about $2^{181}$, and the data complexity is $2^{120}$. We also extend our attack to 14-round CLEFIA-256, with about $2^{245.4}$ encryptions and $2^{120.4}$ chosen plaintexts. Moreover, a birthday sieve method is introduced to decrease the complexity of the core precomputation.
Last updated:  2009-08-12
A Synthetic Indifferentiability Analysis of Some Block-Cipher-Based Hash Functions
Uncategorized
Zheng Gong, Xuejia Lai, Kefei Chen
Show abstract
Uncategorized
At ASIACRYPT 2006, Chang et al. analyzed the indifferentiability of some popular hash functions based on block ciphers, namely, the twenty collision resistant PGV, the MDC2 and the PBGV hash functions, etc. In particular, two indifferentiable attacks were presented on the four of the twenty collision resistant PGV and the PBGV hash functions with the prefix-free padding. In this article, a synthetic indifferentiability analysis of some block-cipher-based hash functions is considered. First, a more precise definition is proposed on the indifferentiability adversary in block-cipher-based hash functions. Next, the advantage of indifferentiability is separately analyzed by considering whether the hash function is keyed or not. Finally, a limitation is observed in Chang et al.'s indifferentiable attacks on the four PGV and the PBGV hash functions. The formal proofs show the fact that those hash functions are indifferentiable from a random oracle in the ideal cipher model with the prefix-free padding, the NMAC/HMAC and the chop construction.
Last updated:  2010-08-20
Secure Computation Without Authentication
Boaz Barak, Ran Canetti, Yehuda Lindell, Rafael Pass, Tal Rabin
Research on secure multiparty computation has mainly concentrated on the case where the parties can authenticate each other and the communication between them. This work addresses the question of what security can be guaranteed when authentication is not available. We consider a completely unauthenticated setting, where {\em all} messages sent by the parties may be tampered with and modified by the adversary without the uncorrupted parties being able to detect this fact. In this model, it is not possible to achieve the same level of security as in the authenticated-channel setting. Nevertheless, we show that meaningful security guarantees {\em can} be provided: Essentially, all the adversary can do is to partition the network into disjoint sets, where in each set the computation is secure in of itself, and also {\em independent} of the computation in the other sets. In this setting we provide, for the first time, non-trivial security guarantees in a model with {\em no setup assumptions whatsoever.} We also obtain similar results while guaranteeing universal composability, in some variants of the common reference string model. Finally, our protocols can be used to provide conceptually simple and unified solutions to a number of problems that were studied separately in the past, including password-based authenticated key exchange and non-malleable commitments. As an application of our results, we study the question of constructing secure protocols in partially-authenticated networks, where some of the links are authenticated and some are not (as is the case in most networks today).
Last updated:  2008-02-07
Efficient GF(3m) Multiplication Algorithm for eta T Pairing
Gen Takahashi, Fumitaka Hoshino, Tetsutaro Kobayashi
The computation speed of pairing based cryptosystems is slow compared with the other public key cryptosystems even though several efficient computation algorithms have been proposed. Thus more efficient computation of the Tate pairing is an important research goal. GF(3m) multiplication in GF(36m) in the pairing algorithm is the greatest consumer of time. Past research concentrated on reducing the number of GF(3m) multiplications, for instance the Karatsuba method. In this article, we propose a new method to reduce the number of online precomputations( precomputations) in GF(3m) multiplications for the eta T pairing. The proposed algorithm reduces 18 online precomputations in GF(36m) in the eta T pairing to 4 online precomputations by reusing the intermediate products obtained in precomputation.We implement the proposed algorithm and compare the time taken by the proposed algorithm with that of the previous work. Our algorithm offers a 40% performance increase for GF(3m) multiplications in GF(36m) on an AMD 64-bit processor. Additionally, a completely new finding is obtained. The results show that the reducing the number of the multiplications in GF(36m) does not necessarily lead to a speed-up of the eta T pairing calculation.
Last updated:  2008-05-06
Construction of Universal Designated-Verifier Signatures and Identity-Based Signatures from Standard Signatures
Siamak F Shahandashti, Reihaneh Safavi-Naini
We give a generic construction for universal designated-verifier signature schemes from a large class, C, of signature schemes. The resulting schemes are efficient and have two important properties. Firstly, they are provably DV-unforgeable, non-transferable and also non-delegatable. Secondly, the signer and the designated verifier can independently choose their cryptographic settings. We also propose a generic construction for identity-based signature schemes from any signature scheme in C and prove that the construction is secure against adaptive chosen message and identity attacks. We discuss possible extensions of our constructions to hierarchical identity-based signatures, identity-based universal designated verifier signatures, and identity-based ring signatures from any signature in C.
Last updated:  2008-07-11
Verifiable Attribute-based Encryption
Qiang Tang, Dongyao Ji
In this paper,we construct two veriable attribute-based encryption(VABE)schemes.One is with a single authority,and the other is with multi authorities.Not only our schemes are proved secure as the previous ABE schemes,they also provide a verication property.Adding the verication property has a few advantages:first,it allows the user to immediately check the correctness of the keys,if not,he only needs the authority to resend the corresponding shares,especially,in multi-authoritycase,if the key does not pass the check,the user only needs to ask the particular authority to resend its own part,without need to go to all the authorities,this saves a lot of time when error appears;second,if the keys pass the verication but the user still does not rightly decrypt out the message,something might be wrong with the attributes or ciphertexts,then,the user has to contact with the encryptor.We formalize the notion of VABE and prove our schemes in our model.
Last updated:  2007-12-11
Guarantees for Customers of Incentive Anonymizing Networks
Timothy Atkinson, Marius Silaghi
We raise and propose solutions to the problem of guaranteeing that a user of incentive remailing services for anonymization cannot lose money if he does not get full service, i.e., if his message does not reach its destination. Applications such as voting over the Internet or reviewing of articles require anonymous delivery of messages. An anonymizing technique was proposed several decades ago by Chaum and is based on a group of volunteer agents called {\em mixnet}. However, mixnets are not yet widely known and used today, and one often mentioned reason is the lack of incentives for volunteers. A recently proposed solution is based on adding digital coins to messages, such that each volunteer can extract only the digital coin designated as a payment for her. However, registered volunteers can sabotage the system by extracting and using their coins without performing their task --- which consists of forwarding anonymized messages. The main improvement we propose is to guarantee that no money is lost by the user without getting his message at the destination. This is an essential property for a viable service. Solutions described are based on handshaking mechanisms where each volunteer gets her payment (or key to decrypt the payment) from the agent to which she is expected to forward the message, or from the destination using a public board or a reply message. This ensures that a volunteer gets her financial support only if she fulfills her task. We discuss how techniques for non-repudiation of receipt of a message, together with reputation systems, can address the remaining problems.
Last updated:  2007-12-10
Practical Anonymous Divisible E-Cash From Bounded Accumulators
Man Ho Au, Willy Susilo, Yi Mu
We present an efficient off-line divisible e-cash scheme which is \emph{truly anonymous} without a trusted third party. This is the second scheme in the literature which achieves full unlinkability and anonymity, after the seminal work proposed by Canard and Gouget. The main trick of our scheme is the use of a bounded accumulator in combination with the classical binary tree approach. The aims of this paper are twofold. Firstly, we analyze Canard and Gouget's seminal work on the efficient off-line divisible e-cash. We point out some subtleties on the parameters generation of their scheme. Moreover, spending a coin of small value requires computation of several hundreds of multi-based exponentiations, which is very costly. In short, although this seminal work provides a new approach of achieving a truly anonymous divisible e-cash, unfortunately it is rather impractical. Secondly, we present our scheme that uses a novel approach of incorporating a bounded accumulator. In terms of time and space complexities, our scheme is $50$ to $100$ times more efficient than Canard and Gouget's work in the spend protocol at the cost of an $10$ to $500$ (the large range is due to whether pre-processing is taken into account and the probabilistic nature of our withdrawal protocol) times less efficient withdrawal protocol. We believe this trade-off between the withdrawal protocol and the spend protocol is reasonable as the former protocol is to be executed much less frequent than the latter. Nonetheless, while their scheme provides an affirmative answer to whether divisible e-cash can be \emph{truly anonymous}, our result puts it a step further and we show that truly anonymous divisible e-cash can be \emph{practical}.
Last updated:  2007-12-10
Saving Private Randomness in One-Way Functions and Pseudorandom Generators
Nenad Dedic, Danny Harnik, Leonid Reyzin
Can a one-way function f on n input bits be used with fewer than $n$ bits while retaining comparable hardness of inversion? We show that the answer to this fundamental question is negative, if one is limited black-box reductions. Instead, we ask whether one can save on secret random bits at the expense of more public random bits. Using a shorter secret input is highly desirable, not only because it saves resources, but also because it can yield tighter reductions from higher-level primitives to one-way functions. Our first main result shows that if the number of output elements of f is at most $2^k$, then a simple construction using pairwise-independent hash functions results in a new one-way function that uses only k secret bits. We also demonstrate that it is not the knowledge of security of f, but rather of its structure, that enables the savings: a black-box reduction cannot, for a general f, reduce the secret-input length, even given the knowledge that security of f is only $2^{-k}$; nor can a black-box reduction use fewer than k secret input bits when f has $2^k$ distinct outputs. Our second main result is an application of the public-randomness approach: we show a construction of a pseudorandom generator based on any regular one-way function with output range of known size $2^k$. The construction requires a seed of only 2n+O(k\log k) bits (as opposed to O(n \log n) in previous constructions); the savings come from the reusability of public randomness. The secret part of the seed is of length only k (as opposed to n in previous constructions), less than the length of the one-way function input.
Last updated:  2007-12-10
Comparing Implementation Efficiency of Ordinary and Squared Pairings
Christine Abegail Antonio, Tanaka Satoru, Ken Nakamula
In this paper, we will implement a standard probabilistic method of computing bilinear pairings. We will compare its performance to a deterministic algorithm introduced in [5] to compute the squared Tate/Weil pairings which are claimed to be 20 percent faster than the standard method. All pairings will be evaluated over pairing-friendly ordinary elliptic curves of embedding degrees 8 and 10 and a supersingular curve of embedding degree 6. For these curves, we can make the algorithm to compute both the ordinary Weil and Tate pairings deterministic and optimizations to improve the algorithms are applied. We will show that the evaluation of squared Weil pairing is, indeed, faster than the ordinary Weil pairing even with optimizations. However, evaluation of the squared Tate pairing is not faster than the ordinary Tate pairing over the curves that we used when optimizations are applied.
Last updated:  2008-03-16
Precise Zero-Knowledge in Concurrent Setting
Ning Ding, Dawu Gu
We present a stronger notion of zero-knowledge: precise concurrent zero-knowledge. Our notion captures the idea that the view of any verifier in concurrent interaction can be reconstructed in the almost same time (within a constant/polynomial factor). Precise zero-knowledge in stand-alone setting was introduced by Micali and Pass in STOC'06 (The original work used the term "local zero-knowledge".). Their notion shows that the view of any verifier can be reconstructed in the almost same time in stand-alone setting. Hence our notion is the generalization of their notion in concurrent setting. Furthermore, we propose a $\omega (\log ^2 n)$-round concurrent zero-knowledge argument for ${\rm{NP}}$ with linear precision, which shows that the view of any verifier in concurrent interaction can be reconstructed by the simulator with linear-time overhead. Our argument is Feige-Lapidot-Shamir type which consists of a proof-preamble and a proof-body for a modified NP statement. Our result assumes the restriction of adversarial scheduling the communication that the concurrent interaction of preambles of all sessions will be scheduled before any proof-body by the adversarial verifier.
Last updated:  2007-12-07
Analysis and optimization of elliptic-curve single-scalar multiplication
Daniel J. Bernstein, Tanja Lange
Let $P$ be a point on an elliptic curve over a finite field of large characteristic. Exactly how many points $2P,3P,5P,7P,9P,\ldots,mP$ should be precomputed in a sliding-window computation of $nP$? Should some or all of the points be converted to affine form, and at which moments during the precomputation should these conversions take place? Exactly how many field multiplications are required for the resulting computation of $nP$? The answers depend on the size of $n$, the $\inversions/\mults$ ratio, the choice of curve shape, the choice of coordinate system, and the choice of addition formulas. This paper presents answers that, compared to previous analyses, are more carefully optimized and cover a much wider range of situations.
Last updated:  2007-12-07
Efficient Certificateless Signatures Suitable for Aggregation
Rafael Castro, Ricardo Dahab
This technical report describes a novel certificateless signature scheme suitable for aggregation that requires no pairing computations for signing and only 3 pairing computations for signature verification. We provide proofs for the security of single and aggregate signatures.
Last updated:  2009-10-12
On the Relations Between Non-Interactive Key Distribution, Identity-Based Encryption and Trapdoor Discrete Log Groups
Kenneth G. Paterson, Sriramkrishnan Srinivasan
We investigate the relationships between identity-based non-interactive key distribution and identity-based encryption. We provide constructions for these schemes that make use of general trapdoor discrete log groups. We then investigate the schemes that result in two concrete settings, obtaining new, provably secure, near-practical identity-based encryption schemes.
Last updated:  2007-12-14
Constructing Brezing-Weng pairing friendly elliptic curves using elements in the cyclotomic field
Ezekiel J. Kachisa, Edward F. Schaefer, Michael Scott
We describe a new method for constructing Brezing-Weng-like pairing-friendly elliptic curves. The new construction uses the minimal polynomials of elements in a cyclotomic field. Using this new construction we present new ``record breaking'' families of pairing-friendly curves with embedding degrees of $k \in \{16,18,36,40\}$, and some interesting new constructions for the cases $k \in \{8,32\}$
Last updated:  2008-02-01
Precise Concurrent Zero Knowledge
Omkant Pandey, Rafael Pass, Amit Sahai, Wei-Lung Dustin Tseng, Muthuramakrishnan Venkitasubramaniam
\emph{Precise zero knowledge} introduced by Micali and Pass (STOC'06) guarantees that the view of any verifier $V$ can be simulated in time closely related to the \emph{actual} (as opposed to worst-case) time spent by $V$ in the generated view. We provide the first constructions of precise concurrent zero-knowledge protocols. Our constructions have essentially optimal precision; consequently this improves also upon the previously tightest non-precise concurrent zero-knowledge protocols by Kilian and Petrank (STOC'01) and Prabhakaran, Rosen and Sahai (FOCS'02) whose simulators have a quadratic worst-case overhead. Additionally, we achieve a statistically-precise concurrent zero-knowledge property---which requires simulation of unbounded verifiers participating in an unbounded number of concurrent executions; as such we obtain the first (even non-precise) concurrent zero-knowledge protocols which handle verifiers participating in a super-polynomial number of concurrent executions.
Last updated:  2007-12-06
Short Group Signature without Random Oracles
Uncategorized
Xiaohui Liang, Zhenfu Cao, Jun Shao, Huang Lin
Show abstract
Uncategorized
We construct a short group signature which is proven secure without random oracles. By making certain reasonable assumptions and applying the technique of non-interactive proof system, we prove that our scheme is full anonymity and full traceability. Compared with other related works, such as BW06, BW07, ours is more practical due to the short size of both public key and group signature.
Last updated:  2009-04-05
Generic Attacks on Unbalanced Feistel Schemes with Expanding Functions
Uncategorized
Jacques Patarin, Valérie Nachef, Côme Berbain
Show abstract
Uncategorized
\begin{abstract} Unbalanced Feistel schemes with expanding functions are used to construct pseudo-random permutations from $kn$ bits to $kn$ bits by using random functions from $n$ bits to $(k-1)n$ bits. At each round, all the bits except $n$ bits are changed by using a function that depends only on these $n$ bits. C.S.Jutla \cite{Jut} investigated such schemes, which he denotes by $F^d_k$, where $d$ is the number of rounds. In this paper, we describe novel Known Plaintext Attacks (KPA) and Non Adaptive Chosen Plaintext Attacks (CPA-1) against these schemes. With these attacks we will often be able to improve the result of C.S.Jutla. We also give precise formulas for the complexity of our attacks in $d$, $k$ and $n$. \end{abstract}
Last updated:  2007-12-05
Generalized Correlation and Higher Order Nonlinearity for Probabilistic Algebraic Attacks Description
Sergiy Pometun
Abstract. Algebraic attacks are relatively new and interesting subject in cryptanalysis. The algebraic attacks where introduced in [1], where several possible attack's scenarios where given. The big attention was paid to deterministic scenarios of those. In this paper, probabilistic scenarios are studied. Conception of conditional correlation and partial higher order nonlinearity of Boolean function where introduced (briefly definition of conditional correlation: $C(g,f|f = a): = \Pr (g = f|f = a) - \Pr (g \ne f|f = a)$ ) . It was shown, that the both types of scenarios can be seen as a one unified attack - higher order correlation attack, which uses conditional correlation. The clear criteria of vulnerability of Boolean function to both types of scenarios was given. Accordingly, the notion of the algebraic immunity was extended. There are very vulnerable functions to probabilistic scenario. Calculations show that if a function with a very low partial higher order nonlinearity was used in the cipher like SFINKS [8], the simple attack would require only about $ 2^{42}$ operations and $32Kb$ of keystream. The question about relation between partial higher order nonlinearity and algebraic immunity remains open yet.
Last updated:  2007-12-13
Weak adaptive chosen ciphertext secure hybrid encryption scheme
Uncategorized
Xianhui Lu, Xuejia Lai, Dake He, Guomin Li
Show abstract
Uncategorized
We propose a security notion named as weak adaptive chosen ciphertext security(IND-WCCA) for hybrid encryption schemes. Although it is weaker than adaptive chosen ciphertext security(IND-CCA), a IND-WCCA secure hybrid encryption scheme can be used in any situations that a IND-CCA secure hybrid encryption scheme used in. We show that IND-WCCA secure hybrid encryption scheme can be constructed from IND-CCA secure KEM and IND-PA secure DEM. Since IND-PA is the basic requirement of symmetric key encryption schemes, IND-WCCA hybrid encryption scheme is very flexible and can use most of the stream ciphers and block ciphers as the DEM part of the scheme. Use the new secure notion we can refine current IND-CCA secure hybrid encryption schemes and get more efficient IND-WCCA secure hybrid encryption schemes.
Last updated:  2008-02-24
A Lattice-Based Computationally-Efficient Private Information Retrieval Protocol
Carlos AGUILAR MELCHOR, Philippe GABORIT
A PIR scheme is a scheme that allows an user to get an element of a database without giving any information about what part of the database he is interested in. In this paper we present a lattice-based PIR scheme, using an NTRU-like approach, in which the computational cost is a few thousand bit-operations per bit in the database. This improves the protocol computational performance by two orders of magnitude when compared to existing approaches. Our scheme has worse communication performance than other existing protocols, but we show that practical usability of PIR schemes is not as dependent on communication performance as the literature suggests, and that a trade-off between communication and computation leads to much more versatile schemes.
Last updated:  2007-12-05
Proposal of a new efficient public key system for encryption and digital signatures
Gerold Grünauer
In this paper a new efficient public key cryptosystem usable for both encryption and digital signatures is presented. Due to its simple structure this public key cipher can be implemented easily in every software or hardware device, making the cryptosystem available for circumstances where the implementation of an alternative like RSA, El Gamal / Diffie - Hellmann, etc. is too complicated. Furthermore the construction on the closest and shortest vector problem using a new homomorph "almost" linear one-way function gives not only strong evidence of the ciphers security, but may be also the base for a new class of "errorprone" cryptographic primitives based on lattice problems. Therefore this cipher and its construction is a good alternative to cryptosystems based on the integer factoriziation problem or the discrete logarithm and might be a base for secure "errorprone" application like biometrics or image watermarking.
Last updated:  2007-12-15
Tight bounds between algebraic immunity and nonlinearities of high orders
Uncategorized
Lobanov Mikhail
Show abstract
Uncategorized
Among cryptographically significant characteristics of Boolean functions used in symmetric ciphers the algebraic immunity and the nonlinearities of high orders play the important role. Some bounds on the nonlinearities of high orders of Boolean functions via its algebraic immunity were obtained in recent papers. In this paper we improve these results and obtain new tight bounds. We prove new universal tight lower bound that reduces the problem of an estimation of high order nonlinearities to the problem of the finding of dimensions of some linear spaces of Boolean functions. As simple consequences we obtain all previously known bounds in this field. For polynomials with disjoint terms we reduce the finding of dimensions of linear spaces of Boolean functions mentioned above to a simple combinatorial analysis. Finally, we prove the tight lower bound on the nonlinearity of the second order via its algebraic immunity.
Last updated:  2007-12-06
Template Attacks with a Power Model
Moulay Abdelaziz EL AABID, Sylvain GUILLEY, Philippe HOOGVORST
This article analyses some properties of the \emph{template attack}. Examples come from attacks against an unprotected ASIC implementation of DES. The principal components analysis (PCA) is used to represent the templates in two dimensions. We give a physical interpretation of the templates PCA eigenvalues and eigenvectors. We show that the S-boxes are \emph{not} the target of template attacks. We point out that the efficiency of template attacks on unprotected implementations can be unleashed by using a power model. The most suitable power-model happens to be linked to the key schedule. This casts a new light on key schedule requirements for SCA resistance against a ``template'' attacker. The results are tailored for DES, because this symmetric block cipher is emblematic and is still promised a long life. Its key schedule is also remarkably simple, with cryptanalytic weaknesses,that paradoxically turn out to be a strength against SCA.
Last updated:  2011-08-15
Another Look at Non-Standard Discrete Log and Diffie-Hellman Problems
Neal Koblitz, Alfred Menezes
We examine several versions of the one-more-discrete-log and one-more-Diffie-Hellman problems. In attempting to evaluate their intractability, we find conflicting evidence of the relative hardness of the different problems. Much of this evidence comes from natural families of groups associated with curves of genus 2, 3, 4, 5, and 6. This leads to questions about how to interpret reductionist security arguments that rely on these non-standard problems.
Last updated:  2009-03-11
Faster Group Operations on Elliptic Curves
Uncategorized
Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, Ed Dawson
Show abstract
Uncategorized
This paper improves implementation techniques of Elliptic Curve Cryptography. We introduce new formulae and algorithms for the group law on Jacobi quartic, Jacobi intersection, Edwards, and Hessian curves. The proposed formulae and algorithms can save time in suitable point representations. To support our claims, a cost comparison is made with classic scalar multiplication algorithms using previous and current operation counts. Most notably, the best speedup is obtained in the case of Jacobi quartic curves which also lead to one of the most efficient scalar multiplications benefiting from the proposed 2M + 5S + 1D (i.e. 2 multiplications, 5 squarings, and 1 multiplication by a curve constant) point doubling and 7M + 3S + 1D point addition algorithms. Furthermore, the new addition algorithm provides an efficient way to protect against side channel attacks which are based on simple power analysis (SPA).
Last updated:  2007-12-05
An Improved Remote User Authentication Scheme using Bilinear Pairings
Sunder Lal, K. K. Goyal
In 2005 Das et al. [5] proposed a remote user authentication scheme using bilinear pairings. Fang and Huang [7] analyzed the scheme and pointed out some weaknesses. They also proposed an improvement. Recently, Giri and Srivastava [9] observed that the improved scheme is still insecure to off-line attack and an improvement. However, the improved scheme is still insecure. In this paper, we show some weaknesses in the existing scheme and propose an improvement. The proposed scheme also enables users to choose and change the password without the help of the remote server.
Last updated:  2007-12-18
Multiparty Key Agreement Using Bilinear Map
Uncategorized
Nam-Su Jho, Myung-Hwan Kim, Do Won Hong, Byung-Gil Lee
Show abstract
Uncategorized
A key agreement protocol is a cryptographical primitive which allows participants to share a common secret key via insecure channel. In particular, a multiparty key agreement protocol is a key agreement protocol that can manage arbitrary number of participants at once. In the security point of view, authentication and forward secrecy are the most important requirements in such protocols. One interesting problem in key agreement protocols is to construct a multiparty key agreement protocol satisfying the above security requirements with minimal number of communication rounds (i.e. one-round). In literature, there has been no one-round multiparty key agreement protocol that satisfies both of authentication and forward secrecy. In this paper, we present a new multiparty key agreement protocol using bilinear map and adopting the key generation center. The protocol demands only one round for arbitrary number of participants to share a group key and satisfies both authentication and (partial) forward secrecy.
Last updated:  2010-02-21
Ordered Multisignatures and Identity-Based Sequential Aggregate Signatures, with Applications to Secure Routing
Uncategorized
Alexandra Boldyreva, Craig Gentry, Adam O'Neill, Dae Hyun Yum
Show abstract
Uncategorized
We construct two new multiparty digital signature schemes that allow multiple signers to sequentially produce a compact, fixed-length signature. First, we introduce a new primitive that we call \emph{ordered multisignatures} (OMS), which allows signers to attest to a common message as well as the order in which they signed. Our OMS construction substantially improves computational efficiency and scalability over any existing scheme with suitable functionality. Second, we design a new identity-based sequential aggregate signature scheme, where signers can attest to different messages and signature verification does not require knowledge of traditional public keys. The latter property permits savings on bandwidth and storage as compared to public-key solutions. In contrast to the only prior scheme to provide this functionality, ours offers improved security that does not rely on synchronized clocks or a trusted first signer. We provide formal security definitions and support the proposed schemes with security proofs under appropriate computational assumptions. We focus on potential applications of our schemes to secure network routing, but we believe they will find many other applications as well.
Last updated:  2007-11-24
Reconfigurable Hardware Implementations of Tweakable Enciphering Schemes
Cuauhtemoc Mancillas-Lopez, Debrup Chakraborty, Francisco Rodriguez-Henriquez
Tweakable enciphering schemes are length preserving block cipher modes of operation that provide a strong pseudo-random permutation. It has been suggested that these schemes can be used as the main building blocks for achieving in-place disk encryption. In the past few years there has been an intense research activity towards constructing secure and efficient tweakable enciphering schemes. But, actual experimental performance data of these newly proposed schemes are yet to be reported. Accordingly, in this paper we present optimized FPGA implementations of five tweakable enciphering schemes, namely, HCH, HCTR, XCB, EME and TET, using a 128-bit AES core as the underlying block cipher. We report performance timings of these modes when using both, pipelined and sequential AES structures. The universal polynomial hash function included in the specification of HCH, HCHfp (a variant of HCH), HCTR, XCB and TET, was implemented using a Karatsuba-Ofman multiplier as the main building block. We provide detailed analyses of each of the schemes and their experimental performances achieved in various scenarios. Our experiments show that a sequential AES core is not an attractive option for the design of these modes as it leads to rather poor throughputs. In contrast, by using an encryption/decryption pipelined AES core we get a throughput of 3.67 Gbps for HCTR and by using a encryption only pipeline AES core we get a throughput of 5.71 Gbps for EME. The performance results reported in this paper provide experimental evidence that hardware implementations of tweakable enciphering schemes can actually match and even outperform the data rates achieved by state-of-the-technology disk controllers, thus showing that they might be used for achieving provably secure in-place hard disk encryption.
Last updated:  2008-11-29
New Attacks on the Stream Cipher TPy6 and Design of New Ciphers the TPy6-A and the TPy6-B
Gautham Sekar, Souradyuti Paul, Bart Preneel
The stream ciphers Py, Pypy and Py6 were designed by Biham and Seberry for the ECRYPT-eSTREAM project in 2005. The ciphers were promoted to the `Focus' ciphers of the Phase II of the eSTREAM project. However, due to some cryptanalytic results on the ciphers, strengthened versions of the ciphers, namely TPy, TPypy and TPy6 were built. So far there exists no attacks on TPy6. In this paper, we find hitherto unknown weaknesses in the keystream generation algorithms of the Py6 and of its stronger variant TPy6. Exploiting these weaknesses, a large number of distinguishing attacks are mounted on the ciphers, the best of which works with $2^{224.6}$ data and comparable time. In the second part, we present two new ciphers derived from the TPy6, namely TPy6-A and TPy6-B, whose performances are 2.65 cycles/byte and 4.4 cycles/byte on Pentium III. As a result, to the best of our knowledge, on Pentium platforms TPy6-A becomes the fastest stream cipher in the literature. Based on our security analysis, we conjecture that no attacks better than brute force are possible on the ciphers TPy6-A and TPy6-B.
Last updated:  2010-06-09
Irreducibility to the One-More Evaluation Problems: More May Be Less
Daniel R. L. Brown
For a random-self-reducible function, the evaluation problem is irreducible to the one-more evaluation problem, in the following sense. An irreduction algorithm exists that, given a reduction algorithm from the evaluation to the one-more evaluation problem, solves a separator problem: the evaluation problem itself. Another irreduction shows that if the computational Diffie-Hellman problem is reduced to the gap Diffie-Hellman problem, then the decision Diffie-Hellman problem is easy. Irreductions are primarily of theoretical interest, because they do not actually prove inequivalence between problems. What these irreductions suggest, though, is that one-more variants of the RSA and discrete logarithm problems may be easier than the standard variants, and that the gap Diffie-Hellman problem may be easier than the standard Diffie-Hellman problem.
Last updated:  2007-11-24
Computing the Ate Pairing on Elliptic Curves with Embedding Degree $k=9$
Uncategorized
Xibin Lin, Chang-An Zhao, Fangguo Zhang, Yanming Wang
Show abstract
Uncategorized
For AES 128 security level there are several natural choices for pairing-friendly elliptic curves. In particular, as we will explain, one might choose curves with $k=9$ or curves with $k=12$. The case $k=9$ has not been studied in the literature, and so it is not clear how efficiently pairings can be computed in that case. In this paper, we present efficient methods for the $k=9$ case, including generation of elliptic curves with the shorter Miller loop, the denominator elimination and speed up of the final exponentiation. Then we compare the performance of these choices. From the analysis, we conclude that for pairing-based cryptography at the AES 128 security level, the Barreto-Naehrig curves are the most efficient choice, and the performance of the case $k=9$ is comparable to the Barreto-Naehrig curves.
Last updated:  2008-06-22
An (Almost) Constant-Effort Solution-Verification Proof-of-Work Protocol based on Merkle Trees
Fabien Coelho
Proof-of-work schemes are economic measures to deter denial-of-service attacks: service requesters compute moderately hard functions that are easy to check by the provider. We present such a new scheme for solution-verification protocols. Although most schemes to date are probabilistic unbounded iterative processes with high variance of the requester effort, our Merkle tree scheme is deterministic, with an almost constant effort and null variance, and is computation-optimal.
Last updated:  2010-06-17
Trapdoors for Hard Lattices and New Cryptographic Constructions
Craig Gentry, Chris Peikert, Vinod Vaikuntanathan
We show how to construct a variety of ``trapdoor'' cryptographic tools assuming the worst-case hardness of standard lattice problems (such as approximating the length of the shortest nonzero vector to within certain polynomial factors). Our contributions include a new notion of \emph{preimage sampleable} functions, simple and efficient ``hash-and-sign'' digital signature schemes, and identity-based encryption. A core technical component of our constructions is an efficient algorithm that, given a basis of an arbitrary lattice, samples lattice points from a \emph{discrete Gaussian} probability distribution whose standard deviation is essentially the length of the longest Gram-Schmidt vector of the basis. A crucial security property is that the output distribution of the algorithm is oblivious to the particular geometry of the given basis.
Last updated:  2007-11-24
Notions of Efficiency in Simulation Paradigm
Tzer-jen Wei
Abstract. There are some well-known conceptional and technical issues related to a common setting of simulation paradigm, i.e., EPT (expected polynomial time) simulator versus SPT (strict polynomial time) adversary. In fact, it has been shown that this setting is essential for achieving constant-round black-box zero-knowledge protocols. Many suggestions and results have been proposed to deal with these issues. In this paper, we propose an alternative solution. We study a new class of machines, MPT (Markov polynomial time), which is a cryptographic adaption of Levin's average polynomial-time. Since MPT has good compatibility to SPT and intuitive composition properties, we can use it as a drop-in replacement of SPT. Moreover, it is easy to construct simulators in MPT.
Last updated:  2007-11-24
Cryptanalysis of LASH
Scott Contini, Krystian Matusiewicz, Josef Pieprzyk, Ron Steinfeld, Jian Guo, San Ling, Huaxiong Wang
We show that the LASH-$x$ hash function is vulnerable to attacks that trade time for memory, including collision attacks as fast as $2^{\frac{4}{11}x}$ and preimage attacks as fast as $2^{\frac47x}$. Moreover, we describe heuristic lattice based collision attacks that use small memory but require very long messages. Based upon experiments, the lattice attacks are expected to find collisions much faster than $2^{x/2}$. All of these attacks exploit the designers' choice of an all zero IV. We then consider whether LASH can be patched simply by changing the IV. In this case, we show that LASH is vulnerable to a $2^{\frac78x}$ preimage attack. We also show that LASH is trivially not a PRF when any subset of input bytes is used as a secret key. None of our attacks depend upon the particular contents of the LASH matrix -- we only assume that the distribution of elements is more or less uniform. Additionally, we show a generalized birthday attack on the final compression of LASH which requires $O\left(x2^{\frac{x}{2(1+\frac{107}{105})}}\right) \approx O(x2^{x/4})$ time and memory. Our method extends the Wagner algorithm to truncated sums, as is done in the final transform in LASH.
Last updated:  2008-03-14
On compressible pairings and their computation
Michael Naehrig, Paulo S. L. M. Barreto, Peter Schwabe
In this paper we provide explicit formul\ae\ to compute bilinear pairings in compressed form. We indicate families of curves where the proposed compressed computation method can be applied and where particularly generalized versions of the Eta and Ate pairings due to Zhao \emph{et al.} are especially efficient. Our approach introduces more flexibility when trading off computation speed and memory requirement. Furthermore, compressed computation of reduced pairings can be done without any finite field inversions. We also give a performance evaluation and compare the new method with conventional pairing algorithms.
Last updated:  2007-11-18
Isogenies and the Discrete Logarithm Problem on Jacobians of Genus 3 Hyperelliptic Curves
Benjamin Smith
We describe the use of explicit isogenies to reduce Discrete Logarithm Problems (DLPs) on Jacobians of hyperelliptic genus~$3$ curves to Jacobians of non-hyperelliptic genus~$3$ curves, which are vulnerable to faster index calculus attacks. We provide algorithms which compute an isogeny with kernel isomorphic to $(\mathbb{Z}/2\mathbb{Z})^3$ for any hyperelliptic genus~$3$ curve. These algorithms provide a rational isogeny for a positive fraction of all hyperelliptic genus~$3$ curves defined over a finite field of characteristic $p > 3$. Subject to reasonable assumptions, our algorithms provide an explicit and efficient reduction from hyperelliptic DLPs to non-hyperelliptic DLPs for around $18.57\%$ of all hyperelliptic genus~$3$ curves over a given finite field.
Last updated:  2007-12-11
Idempotents in the Neighbourhood of Patterson-Wiedemann Functions having Walsh Spectra Zeros
Sumanta Sarkar, Subhamoy Maitra
In this paper we study the neighbourhood of $15$-variable Patterson-Wiedemann (PW) functions, i.e., the functions that differ by a small Hamming distance from the PW functions in terms of truth table representation. We exploit the idempotent structure of the PW functions and interpret them as Rotation Symmetric Boolean Functions (RSBFs). We present techniques to modify these RSBFs to introduce zeros in the Walsh spectra of the modified functions with minimum reduction in nonlinearity. Our technique demonstrates 15-variable balanced and $1$-resilient functions with currently best known nonlinearities 16272 and 16264 respectively. In the process, we find functions for which the autocorrelation spectra and algebraic immunity parameters are best known till date.
Last updated:  2007-11-18
Implementing Cryptographic Pairings over Curves of Embedding Degrees 8 and 10
Christine Abegail Antonio, Satoru Tanaka, Ken Nakamula
In this paper, we will describe efficient implementations of the Tate and Ate pairings over ordinary elliptic curves of embedding degrees 8 and 10. We will discuss the possible curve-dependent optimizations that can be applied to evaluate the pairings. We pay particular attention to the use of elliptic curve twists and the denominator elimination method to make computations more efficient. Our main goal is to draw together the best possible optimizations that can be used to efficiently evaluate the Tate and the Ate pairings in both curves and to give timings and appropriate interpretation on the rate of change on the running time of our programs for both curves. To come up with an adequate conclusion, we will compare the performance of the curves we chose to an already experimented curve of embedding degree 12.
Last updated:  2007-11-18
On prime-order elliptic curves with embedding degrees k=3,4 and 6
Koray Karabina, Edlyn Teske
We further analyze the solutions to the Diophantine equations from which prime-order elliptic curves of embedding degrees $k=3,4$ or $6$ (MNT curves) may be obtained. We give an explicit algorithm to generate such curves. We derive a heuristic lower bound for the number $E(z)$ of MNT curves with $k=6$ and discriminant $D\le z$, and compare this lower bound with experimental data.
Last updated:  2007-11-18
When e-th Roots Become Easier Than Factoring
Antoine Joux, David Naccache, Emmanuel Thomé
We show that computing $e$-th roots modulo $n$ is easier than factoring $n$ with currently known methods, given subexponential access to an oracle outputting the roots of numbers of the form $x_i + c$. Here $c$ is fixed and $x_i$ denotes small integers of the attacker's choosing. Several variants of the attack are presented, with varying assumptions on the oracle, and goals ranging from selective to universal forgeries. The computational complexity of the attack is $L_n(\frac{1}{3}, \sqrt[3]{\frac{32}{9}})$ in most significant situations, which matches the {\sl special} number field sieve's ({\sc snfs}) complexity. This sheds additional light on {\sc rsa}'s malleability in general and on {\sc rsa}'s resistance to affine forgeries in particular -- a problem known to be polynomial for $x_i > \sqrt[3]{n}$, but for which no algorithm faster than factoring was known before this work.
Last updated:  2009-08-17
Finding Low Weight Polynomial Multiples Using Lattices
Uncategorized
Laila El Aimani, Joachim von zur Gathen
Show abstract
Uncategorized
The low weight polynomial multiple problem arises in the context of stream ciphers cryptanalysis and of efficient finite field arithmetic, and is believed to be difficult. It can be formulated as follows: given a polynomial $f \in \F_2[X]$ of degree $d$, and a bound $n$, the task is to find a low weight multiple of $f$ of degree at most $n$. The best algorithm known so far to solve this problem is based on a time memory trade-off and runs in time ${\cal O}(n^{ \lceil {(w - 1)}/{2} \rceil})$ using ${\cal O}(n^{ \lceil {(w - 1)}/{4} \rceil})$ of memory, where $w$ is the estimated minimal weight. In this paper, we propose a new technique to find low weight multiples using lattice basis reduction. Our algorithm runs in time ${\cal O}(n^6)$ and uses ${\cal O}(nd)$ of memory. This improves the space needed and gives a better theoretical time estimate when $w \geq 12$ . Such a situation is plausible when the bound $n$, which represents the available keystream, is small. We run our experiments using the NTL library on some known polynomials in cryptanalysis and we confirm our analysis.
Last updated:  2007-11-18
Structural Identity-Based Encryption
Man Ho Au, Siu-Ming Yiu
In this paper, we introduce the concept of structural identity-based encryption (SIBE). Similar to hierarchical identity-based encryption (HIBE), entities in the system are organized into hierarchy. An entity in SIBE can decrypt ciphertext for all its ancestors. It can be seen as an opposite of HIBE, where an entity can decrypt the ciphertext for all its descendants. We formalize the notion and security requirements, propose an efficient construction and show that our construction is secure under appropriate assumptions in the random oracle model.
Last updated:  2007-11-18
The role of help in Classical and Quantum Zero-Knowledge
André Chailloux, Iordanis Kerenidis
We study the role of help in Non-Interactive Zero-Knowledge protocols and its relation to the standard interactive model. In the classical case, we show that help and interaction are equivalent, answering an open question of Ben-Or and Gutfreund (\cite{BG03}). This implies a new complete problem for the class SZK, the Image Intersection Density. For this problem, we also prove a polarization lemma which is stronger than the previously known one. In the quantum setting, we define the notion of quantum help and show in a more direct way that help and interaction are again equivalent. Moreover, we define quantum Non-Interactive Zero-Knowledge with classical help and prove that it is equal to the class of languages that have classical honest-Verifier Zero Knowledge protocols secure against quantum Verifiers (\cite{Wat06, HKSZ07}). Last, we provide new complete problems for all these quantum classes. Similar results were independently discovered by Dragos Florin Ciocan and Salil Vadhan.
Last updated:  2007-11-06
A Critical Analysis and Improvement of AACS Drive-Host Authentication
Jiayuan Sui, Douglas R. Stinson
This paper presents a critical analysis of the AACS drive-host authentication scheme. A few weaknesses are identified which could lead to various attacks on the scheme. In particular, we observe that the scheme is susceptible to unknown key-share and man-in-the-middle attacks. Modifications of the scheme are suggested in order to provide better security. A proof of security of the modified scheme is also presented. The modified scheme achieves better efficiency than the original scheme.
Last updated:  2007-11-06
Cryptanalysis of the Random Number Generator of the Windows Operating System
Leo Dorrendorf, Zvi Gutterman, Benny Pinkas
The pseudo-random number generator (PRNG) used by the Windows operating system is the most commonly used PRNG. The pseudo-randomness of the output of this generator is crucial for the security of almost any application running in Windows. Nevertheless, its exact algorithm was never published. We examined the binary code of a distribution of Windows 2000, which is still the second most popular operating system after Windows XP. (This investigation was done without any help from Microsoft.) We reconstructed, for the first time, the algorithm used by the pseudo-random number generator (namely, the function CryptGenRandom). We analyzed the security of the algorithm and found a non-trivial attack: given the internal state of the generator, the previous state can be computed in $O(2^{23})$ work (this is an attack on the forward-security of the generator, an $O(1)$ attack on backward security is trivial). The attack on forward-security demonstrates that the design of the generator is flawed, since it is well known how to prevent such attacks. We also analyzed the way in which the generator is run by the operating system, and found that it amplifies the effect of the attacks: The generator is run in user mode rather than in kernel mode, and therefore it is easy to access its state even without administrator privileges. The initial values of part of the state of the generator are not set explicitly, but rather are defined by whatever values are present on the stack when the generator is called.Furthermore, each process runs a different copy of the generator, and the state of the generator is refreshed with system generated entropy only after generating 128 KBytes of output for the process running it. The result of combining this observation with our attack is that learning a single state may reveal 128 Kbytes of the past and future output of the generator. The implication of these findings is that a buffer overflow attack or a similar attack can be used to learn a single state of the generator, which can then be used to predict all random values, such as SSL keys, used by a process in all its past and future operation. This attack is more severe and more efficient than known attacks, in which an attacker can only learn SSL keys if it is controlling the attacked machine at the time the keys are used.
Last updated:  2007-11-07
An Improved Remote User Authentication Scheme with Smart Cards using Bilinear Pairings
Amit K Awasthi
Recently Manik et al. [3] proposed a novel remote user authentication scheme using bilinear pairings. Various attacks were discussed on this scheme. Recently, Fang et al [15] re-analyzed these schemes and pointed out that these further proposed schemes are not secure. They proposed an improvement to previous schemes. Recently, Giri and Srivastava [16] observed that the improved scheme is still insecure to off-line attack and they suggested an improvement on Feng et al's scheme. However, the improved scheme is still insecure. In this paper, we discuss these attacks and propose an improvement of their scheme that provides the better security compared to the schemes previously published
Last updated:  2008-09-10
Algorithms and Arithmetic Operators for Computing the $\eta_T$ Pairing in Characteristic Three
Jean-Luc Beuchat, Nicolas Brisebarre, Jérémie Detrey, Eiji Okamoto, Masaaki Shirase, Tsuyoshi Takagi
Since their introduction in constructive cryptographic applications, pairings over (hyper)elliptic curves are at the heart of an ever increasing number of protocols. Software implementations being rather slow, the study of hardware architectures became an active research area. In this paper, we discuss several algorithms to compute the $\eta_T$ pairing in characteristic three and suggest further improvements. These algorithms involve addition, multiplication, cubing, inversion, and sometimes cube root extraction over $\mathbb{F}_{3^m}$. We propose a hardware accelerator based on a unified arithmetic operator able to perform the operations required by a given algorithm. We describe the implementation of a compact coprocessor for the field $\mathbb{F}_{3^{97}}$ given by $\mathbb{F}_3[x]/(x^{97}+x^{12}+2)$, which compares favorably with other solutions described in the open literature.
Last updated:  2008-06-18
Compression Function Design Principles Supporting Variable Output Lengths from a Single Small Function
Uncategorized
Donghoon Chang, Mridul Nandi, Jesang Lee, Jaechul Sung, Seokhie Hong
Show abstract
Uncategorized
In this paper, we introduce new compression function design principles supporting variable output lengths (multiples of size $n$). They are based on a function or block cipher with an $n$-bit output size. In the case of the compression function with a $(t+1)n$-bit output size, in the random oracle and ideal cipher models, their maximum advantages from the perspective of collision resistance are $O(\frac{t^2q}{2^{tn}}+\frac{q^2}{2^{(t+1)n}})$. In the case of $t=1$, the advantage is near-optimal. In the case of $t>1$, the advantage is optimal.
Last updated:  2007-11-06
Cryptanalytic Flaws in Oh et al.'s ID-Based Authenticated Key Agreement Protocol
Meng-Hui Lim, Sanggon Lee, Hoonjae Lee
A key agreement protocol is designed for two or more entities to agree upon a shared secret key, which is used to preserve confidentiality and data integrity over an open network. In 2007, Oh et al. proposed an efficient ID-based authenticated key agreement protocol on elliptic curve pairings, which is believed to be able to generate two session keys securely after a protocol execution. However, we discover that their protocol is in fact susceptible to the basic impersonation attack as well as the key compromise impersonation attack. In this paper, we present the imperfections of Oh et al.'s scheme and subsequently we suggest a slight modification to the scheme which would resolve the problems.
Last updated:  2007-11-06
Optimizing double-base elliptic-curve single-scalar multiplication
Daniel J. Bernstein, Peter Birkner, Tanja Lange, Christiane Peters
This paper analyzes the best speeds that can be obtained for single-scalar multiplication with variable base point by combining a huge range of options: – many choices of coordinate systems and formulas for individual group operations, including new formulas for tripling on Edwards curves; – double-base chains with many different doubling/tripling ratios, including standard base-2 chains as an extreme case; – many precomputation strategies, going beyond Dimitrov, Imbert, Mishra (Asiacrypt 2005) and Doche and Imbert (Indocrypt 2006). The analysis takes account of speedups such as S-M tradeoffs and includes recent advances such as inverted Edwards coordinates. The main conclusions are as follows. Optimized precomputations and triplings save time for single-scalar multiplication in Jacobian coordinates, Hessian curves, and tripling-oriented Doche/Icart/Kohel curves. However, even faster single-scalar multiplication is possible in Jacobi intersections, Edwards curves, extended Jacobi-quartic coordinates, and inverted Edwards coordinates, thanks to extremely fast doublings and additions; there is no evidence that double-base chains are worthwhile for the fastest curves. Inverted Edwards coordinates are the speed leader.
Last updated:  2007-11-06
Breaking ONE.FIVIUM by AIDA an Algebraic IV Differential Attack
Uncategorized
Michael Vielhaber
Show abstract
Uncategorized
We show, how to break TRIVIUM with a setup of 576 (instead of 1152) clock cycles, with an effort of 2^6 chosen IV resynchronisations up to cycle 625 for each of the 47 recovered key bits.
Last updated:  2007-11-08
Proposing a Master One-Way Function
Uncategorized
Gideon Samid
Show abstract
Uncategorized
Making an arbitrary binary string fit as a fixed size cipher key (via hashing) one could use an arbitrary string x as both plaintext and key to generate a ciphertext, y defined as "the crypto square of x", while x is the crypto square root of y. Extended to higher powers, this formalism allows for polynomial morphology that combines all one-way functions candidates into a single master function which is at least as intractable as its best ingredient one-way function. The master list has some interesting and useful attributes: at will size for both input and output, controlled forward computational burden, milestone computing, and of course the best practical chance for being one-way.
Last updated:  2007-12-11
Cryptanalysis on Improved One-round Lin-Li's Tripartite Key Agreement Protocol
Uncategorized
Meng-Hui Lim, Sanggon Lee, Hoonjae Lee
Show abstract
Uncategorized
A tripartite authenticated key agreement protocol is designed for three entities to communicate securely over an open network particularly with a shared key. Recently, we have improved a one-round tripartite authenticated key agreement protocol proposed by Lin-Li due to its vulnerability to the forging attack in our previous report. However, we have later discovered that both the original Lin-Li's scheme and our previous enhanced protocol are vulnerable to the insider replay attack. Moreover, we have also realized that both protocols have falsely claimed the forward secrecy attribute. In this paper, we will revise our improvements and again secure this protocol against these cryptanalytic attacks while recovering the precious perfect forward secrecy property.
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.