All papers (Page 189 of 21762 results)

Last updated:  2009-09-17
Delegatable Anonymous Credentials
Mira Belenkiy, Jan Camenisch, Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya, Hovav Shacham
We construct an efficient delegatable anonymous credential system. Users can anonymously and unlinkably obtain credentials from any authority, delegate their credentials to other users, and prove possession of a credential $L$ levels away from the given authority. The size of the proof (and time to compute it) is $O(Lk)$, where $k$ is the security parameter. The only other construction of delegatable anonymous credentials (Chase and Lysyanskaya, Crypto 2006) relies on general non-interactive proofs for NP-complete languages of size $k \Omega(2^{L})$. We revise the entire approach to constructing anonymous credentials and identify \emph{randomizable} zero-knowledge proof of knowledge systems as the key building block. We formally define the notion of randomizable non-interactive zero-knowledge proofs, and give the first construction by showing how to appropriately rerandomize Groth and Sahai (Eurocrypt 2008) proofs. We show that such proof systems, in combination with an appropriate authentication scheme and a few other protocols, allow us to construct delegatable anonymous credentials. Finally, we instantiate these building blocks under appropriate assumptions about groups with bilinear maps.
Last updated:  2011-04-04
LEGO for Two Party Secure Computation
Jesper Buus Nielsen, Claudio Orlandi
The first and still most popular solution for secure two-party computation relies on Yao's garbled circuits. Unfortunately, Yao's construction provide security only against passive adversaries. Several constructions (zero-knowledge compiler, cut-and-choose) are known in order to provide security against active adversaries, but most of them are not efficient enough to be considered practical. In this paper we propose a new approach called LEGO (Large Efficient Garbled-circuit Optimization) for two-party computation, which allows to construct more efficient protocols secure against active adversaries. The basic idea is the following: Alice constructs and provides Bob a set of garbled NAND gates. A fraction of them is checked by Alice giving Bob the randomness used to construct them. When the check goes through, with overwhelming probability there are very few bad gates among the non-checked gates. These gates Bob permutes and connects to a Yao circuit, according to a fault-tolerant circuit design which computes the desired function even in the presence of a few random faulty gates. Finally he evaluates this Yao circuit in the usual way. For large circuits, our protocol offers better performance than any other existing protocol. The protocol is universally composable (UC) in the OT-hybrid model.
Last updated:  2008-10-08
On Kasami Bent Functions
Uncategorized
Deepmala Sharma, Sugata Gangopadhyay
Show abstract
Uncategorized
It is proved that no non-quadratic Kasami bent is affine equivalent to Maiorana-MacFarland type bent functions.
Last updated:  2010-12-24
Efficient Asynchronous Multiparty Computation with Optimal Resilience
Arpita Patra, Ashish Choudhury, C. Pandu Rangan
Verifiable Secret Sharing (VSS) is a fundamental primitive used as a building block in many distributed cryptographic tasks, such as Secure Multiparty Computation (MPC) and Byzantine Agreement (BA). An important variant of VSS is Asynchronous VSS (AVSS) which is designed to work over asynchronous networks. AVSS is a two phase (Sharing, Reconstruction) protocol carried out among $n$ parties in the presence of a computationally unbounded active adversary, who can corrupt up to $t$ parties. We assume that every two parties in the network are directly connected by a pairwise secure channel. In this paper, we present a new statistical AVSS protocol with optimal resilience; i.e. with $n = 3t+1$. Our protocol privately communicates O((\ell n^3 + n^4 \log{\frac{1}{\epsilon}}) \log{\frac{1}{\epsilon}}) bits and A-cast O(n^3 \log(n)) bits to simultaneously share \ell \geq 1 elements from a finite field F, where \epsilon is the error parameter of our protocol. There are only two known statistical AVSS protocols with $n = 3t+1$ reported in [CR93] and [PCR08]. The AVSS protocol of [CR93] requires a private communication of O(n^9 (\log{\frac{1}{\epsilon}})^4) bits and A-cast of O(n^9 (\log{\frac{1}{\epsilon}})^2 \log(n)) bits to share a single element from F. Thus our AVSS protocol shows a significant improvement in communication complexity over the AVSS of [CR93]. The AVSS protocol of [PCR08] requires a private communication and A-cast of O((\ell n^3 + n^4) \log{\frac{1}{\epsilon}}) bits to share \ell \geq 1 elements. However, the shared element(s) may be NULL \not \in F. Thus our AVSS is better than the AVSS of [PCR08] due to the following reasons: 1. The A-cast communication of our AVSS is independent of the number of secrets i.e. \ell; 2. Our AVSS makes sure that the shared value(s) always belong to F. Using our AVSS, we design a new primitive called Asynchronous Complete Secret Sharing (ACSS) which acts as an important building block of asynchronous multiparty computation (AMPC). Using our ACSS scheme, we design a statistical AMPC protocol with optimal resilience; i.e., with $n = 3t+1$, that privately communicates O(n^5 \log{\frac{1}{\epsilon}}) bits per multiplication gate. This significantly improves the communication complexity of only known optimally resilient [BKR93] that privately communicates \Omega(n^{11} (\log{\frac{1}{\epsilon}})^4) bits and A-cast \Omega(n^{11} (\log{\frac{1}{\epsilon}})^2 \log(n)) bits per multiplication gate. Both our ACSS and AVSS employ several new techniques, which are of independent interest.
Last updated:  2013-10-11
Asynchronous Byzantine Agreement with Optimal Resilience
Uncategorized
Arpita Patra, Ashish Choudhury, C. Pandu Rangan
Show abstract
Uncategorized
We present an efficient, optimally-resilient Asynchronous Byzantine Agreement (ABA) protocol involving n = 3t+1 parties over a completely asynchronous network, tolerating a computationally unbounded Byzantine adversary, capable of corrupting at most t out of the n parties. In comparison with the best known optimally-resilient ABA protocols of Canetti and Rabin (STOC 1993) and Abraham, Dolev and Halpern (PODC 2008), our protocol is significantly more efficient in terms of the communication complexity. Our ABA protocol is built on a new statistical asynchronous verifiable secret sharing (AVSS) protocol with optimal resilience. Our AVSS protocol significantly improves the communication complexity of the only known statistical and optimally-resilient AVSS protocol of Canetti et al. Our AVSS protocol is further built on an asynchronous primitive called asynchronous weak commitment (AWC), while the AVSS of Canetti et al. is built on the primitive called asynchronous weak secret sharing (AWSS). We observe that AWC has weaker requirements than AWSS and hence it can be designed more efficiently than AWSS. The common coin primitive is one of the most important building blocks for the construction of an ABA protocol. In this paper, we extend the existing common coin protocol to make it compatible with our new AVSS protocol that shares multiple secrets simultaneously. As a byproduct, our new common coin protocol is more communication efficient than all the existing common coin protocols.
Last updated:  2008-10-23
Searchable encryption with decryption in the standard model
Dennis Hofheinz, Enav Weinreb
A *searchable public key encryption (PEKS) scheme* allows to generate, for any given message $W$, a trapdoor $T_W$, such that $T_W$ allows to check whether a given ciphertext is an encryption of $W$ or not. Of course, $T_W$ should not reveal any additional information about the plaintext. PEKS schemes have interesting applications: for instance, consider an email gateway that wants to prioritize or filter encrypted emails based on keywords contained in the message text. The email recipient can then enable the gateway to do so by releasing the trapdoors for the corresponding keywords. This way, the gateway can check emails for these keywords, but it learns nothing more about the email contents. PEKS schemes have first been formalized and constructed by Boneh et al.. But with one exception, no known construction of a PEKS scheme supports the decryption of ciphertexts. That is, known constructions allow to *test* for a certain message, but they do not allow to *retrieve* the message, even when having the full secret key. Besides being somewhat unnatural for an encryption scheme, this ``no-decryption''-property also limits the applicability of a PEKS scheme. The one exception, a PEKS scheme with decryption due to Fuhr and Paillier, is formulated in the random oracle model, and inherently relies on the statistical properties of the random oracle. In fact, Fuhr and Paillier leave it as an open problem to construct a PEKS scheme with decryption in the standard model. In this paper, we construct the first PEKS scheme with decryption (PEKSD scheme) in the standard model. Our sole assumption is an anonymous IBE scheme. We explain the technical difficulties that arise with previous attempts to build a PEKS scheme with decryption and how we overcome these difficulties. Technically, we isolate a vital additional property of IBE schemes (a property we call *well-addressedness* and which states that a ciphertext is tied to an identity and will be rejected when trying to decrypt with respect to any other identity) and show how to generically achieve it. Our construction of a PEKSD scheme from an anonymous IBE scheme provides a natural example of a *non-shielding* construction (in which the decryption algorithm queries the encryption algorithm). Gertner et al. have shown that an IND-CCA secure public key encryption scheme cannot be constructed and proven from an IND-CPA secure scheme in a black-box and *shielding* way. However, our results give evidence that encryption queries in the decryption algorithm may well prove useful in a security reduction.
Last updated:  2008-10-02
A New Approach for Algebraically Homomorphic Encryption
Frederik Armknecht, Ahmad-Reza Sadeghi
The existence of an efficient and provably secure algebraically homomorphic scheme (AHS), i.e., one that supports both addition and multiplication operations, is a long stated open problem. All proposals so far are either insecure or not provable secure, inefficient, or allow only for one multiplication (and arbitrary additions). As only very limited progress has been made on the existing approaches in the recent years, the question arises whether new methods can lead to more satisfactory solutions. In this paper we show how to construct a provably secure AHS based on a coding theory problem. It allows for arbitrary many additions and for a fixed, but arbitrary number of multiplications and works over arbitrary finite fields. Besides, it possesses some useful properties: i) the plaintext space can be extended adaptively without the need for re-encryption, ii) it operates over arbitrary infinite fields as well, e.g., rational numbers, but the hardness of the underlying decoding problem in such cases is less studied, and iii) depending on the parameter choice, the scheme has inherent error-correcting up to a certain number of transmission errors in the ciphertext. However, since our scheme is symmetric and its ciphertext size grows exponentially with the expected total number of encryptions, its deployment is limited to specific client-server-applications with few number of multiplications. Nevertheless, we believe room for improvement due to the huge number of alternative coding schemes that can serve as the underlying hardness problem. For these reasons and because of the interesting properties of our scheme, we believe that using coding theory to design AHS is a promising approach and hope to encourage further investigations.
Last updated:  2008-12-05
Truly Efficient 2-Round Perfectly Secure Message Transmission Scheme
Uncategorized
Kaoru Kurosawa, Kazuhiro Suzuki
Show abstract
Uncategorized
In the model of perfectly secure message transmission schemes (PSMTs), there are $n$ channels between a sender and a receiver. An infinitely powerful adversary $\A$ may corrupt (observe and forge)the messages sent through $t$ out of $n$ channels. The sender wishes to send a secret $s$ to the receiver perfectly privately and perfectly reliably without sharing any key with the receiver. In this paper, we show the first $2$-round PSMT for $n=2t+1$ such that not only the transmission rate is $O(n)$ but also the computational costs of the sender and the receiver are both polynomial in $n$. This means that we solve the open problem raised by Agarwal, Cramer and de Haan at CRYPTO 2006.
Last updated:  2009-04-09
Oblivious Transfer from Weak Noisy Channels
Uncategorized
Jürg Wullschleger
Show abstract
Uncategorized
Various results show that oblivious transfer can be implemented using the assumption of noisy channels. Unfortunately, this assumption is not as weak as one might think, because in a cryptographic setting, these noisy channels must satisfy very strong security requirements. Unfair noisy channels, introduced by Damgard, Kilian and Salvail [Eurocrypt '99], reduce these limitations: They give the adversary an unfair advantage over the honest player, and therefore weaken the security requirements on the noisy channel. However, this model still has many shortcomings: For example, the adversary's advantage is only allowed to have a very special form, and no error is allowed in the implementation. In this paper we generalize the idea of unfair noisy channels. We introduce two new models of cryptographic noisy channels that we call the weak erasure channel and the weak binary symmetric channel, and show how they can be used to implement oblivious transfer. Our models are more general and use much weaker assumptions than unfair noisy channels, which makes implementation a more realistic prospect. For example, these are the first models that allows the parameters to come from experimental evidence.
Last updated:  2008-10-02
Parsing ambiguities in authentication and key establishment protocols
Liqun Chen, Chris J. Mitchell
A new class of attacks against authentication and authenticated key establishment protocols is described, which we call parsing ambiguity attacks. If appropriate precautions are not deployed, these attacks apply to a very wide range of such protocols, including those specified in a number of international standards. Three example attacks are described in detail, and possible generalisations are also outlined. Finally, possible countermeasures are given, as are recommendations for modifications to the relevant standards.
Last updated:  2008-10-02
Privacy-Enhancing First-Price Auctions Using Rational Cryptography
Peter Bro Miltersen, Jesper Buus Nielsen, Nikos Triandopoulos
We consider enhancing a sealed-bid single-item auction with \emph{privacy} concerns, our assumption being that bidders primarily care about monetary payoff and secondarily worry about exposing information about their type to other players and learning information about other players' types. To treat privacy explicitly within the game theoretic context, we put forward a novel \emph{hybrid utility} model that considers both fiscal and privacy components in the players' payoffs. We show how to use rational cryptography to approximately implement a given \emph{ex interim} individually strictly rational equilibrium of such an auction (or any game with a winner) without a trusted mediator through a cryptographic protocol that uses only point-to-point authenticated channels between the players. By ``ex interim individually strictly rational'' we mean that, given its type and before making its move, each player has a strictly positive expected utility, i.e., it becomes the winner of the auction with positive probability. By ``approximately implement'' we mean that, under cryptographic assumptions, running the protocol is a computational Nash equilibrium with a payoff profile negligibly close to the original equilibrium. In addition the protocol has the stronger property that no collusion, of any size, can obtain more by deviating in the implementation than by deviating in the ideal mediated setting which the mechanism was designed in. Also, despite the non-symmetric payoffs profile, the protocol always correctly terminates.
Last updated:  2009-03-10
On the security of pairing-friendly abelian varieties over non-prime fields
Uncategorized
Naomi Benger, Manuel Charlemagne, David Freeman
Show abstract
Uncategorized
Let $A$ be an abelian variety defined over a non-prime finite field $\F_{q}$ that has embedding degree $k$ with respect to a subgroup of prime order $r$. In this paper we give explicit conditions on $q$, $k$, and $r$ that imply that the minimal embedding field of $A$ with respect to $r$ is $\F_{q^k}$. When these conditions hold, the embedding degree $k$ is a good measure of the security level of a pairing-based cryptosystem that uses $A$. We apply our theorem to supersingular elliptic curves and to supersingular genus 2 curves, in each case computing a maximum $\rho$-value for which the minimal embedding field must be $\F_{q^k}$. Our results are in most cases stronger (i.e., give larger allowable $\rho$-values) than previously known results for supersingular varieties, and our theorem holds for general abelian varieties, not only supersingular ones.
Last updated:  2008-10-03
Almost-Asynchronous MPC with Faulty Minority
Zuzana Beerliova-Trubiniova, Martin Hirt, Jesper Buus Nielsen
Secure multiparty computation (MPC) allows a set of parties to securely evaluate any agreed function of their inputs, even when up to $t$ of the $n$ parties are faulty. Protocols for synchronous networks (where every sent message is assumed to arrive within a constant time) tolerate up to $t<n/2$ faulty parties, whereas in the more realistic asynchronous setting (with no \emph{a priory} information on maximal message delay) only security against $t<n/3$ is possible. We present the first protocol that achieves security against $t<n/2$ without assuming a fully synchronous network. Actually our protocol guarantees security against any faulty minority in an \emph{almost asynchronous} network, i.e. in a network with one single round of synchronous broadcast (followed by a fully asynchronous communication). Furthermore our protocol takes inputs of all parties (in a fully asynchronous network only inputs of $n-t$ parties can be guaranteed), and so achieves everything that is possible in synchronous networks (but impossible in fully asynchronous networks) at the price of just one synchronous broadcast round. As tools for our protocol we introduce the notions of \emph{almost non-interactive verifiable secret-sharing} and \emph{almost non-interactive zero-knowledge proof of knowledge}, which are of independent interest as they can serve as efficient replacements for fully non-interactive verifiable secret-sharing and fully non-interactive zero-knowledge proof of knowledge.
Last updated:  2008-10-27
Asynchronous Multiparty Computation: Theory and Implementation
Ivan Damgård, Martin Geisler, Mikkel Krøigaard, Jesper Buus Nielsen
We propose an asynchronous protocol for general multiparty computation with perfect security and communication complexity O(n^2 |C| k) where n is the number of parties, |C| is the size of the arithmetic circuit being computed, and k is the size of elements in the underlying field. The protocol guarantees termination if the adversary allows a preprocessing phase to terminate, in which no information is released. The communication complexity of this protocol is the same as that of a passively secure solution up to a constant factor. It is secure against an adaptive and active adversary corrupting less than n/3 players. We also present a software framework for implementation of asynchronous protocols called VIFF (Virtual Ideal Functionality Framework), which allows automatic parallelization of primitive operations such as secure multiplications, without having to resort to complicated multithreading. Benchmarking of a VIFF implementation of our protocol confirms that it is applicable to practical non-trivial secure computations. VIFF can be downloaded from http://viff.dk/.
Last updated:  2008-10-02
On the Number of Synchronous Rounds Required for Byzantine Agreement
Matthias Fitzi, Jesper Buus Nielsen
Byzantine agreement is typically considered with respect to either a fully synchronous network or a fully asynchronous one. In the synchronous case, either $t+1$ deterministic rounds are necessary in order to achieve Byzantine agreement or at least some expected large constant number of rounds. In this paper we examine the question of how many initial synchronous rounds are required for Byzantine agreement if we allow to switch to asynchronous operation afterwards. Let $n=h+t$ be the number of parties where $h$ are honest and $t$ are corrupted. As the main result we show that, in the model with a public-key infrastructure and signatures, $d+O(1)$ deterministic synchronous rounds are sufficient where $d$ is the minimal integer such that $n-d>3(t-d)$. This improves over the $t+1$ necessary deterministic rounds for almost all cases, and over the exact expected number of rounds in the non-deterministic case for many cases.
Last updated:  2008-10-08
Password Mistyping in Two-Factor-Authenticated Key Exchange
Vladimir Kolesnikov, Charles Rackoff
Abstract: We study the problem of Key Exchange (KE), where authentication is two-factor and based on both electronically stored long keys and human-supplied credentials (passwords or biometrics). The latter credential has low entropy and may be adversarily mistyped. Our main contribution is the first formal treatment of mistyping in this setting. Ensuring security in presence of mistyping is subtle. We show mistyping-related limitations of previous KE definitions and constructions. We concentrate on the practical two-factor authenticated KE setting where servers exchange keys with clients, who use short passwords (memorized) and long cryptographic keys (stored on a card). Our work is thus a natural generalization of Halevi-Krawczyk and Kolesnikov-Rackoff. We discuss the challenges that arise due to mistyping. We propose the first KE definitions in this setting, and formally discuss their guarantees. We present efficient KE protocols and prove their security.
Last updated:  2008-10-02
Key Predistribution for Homogeneous Wireless Sensor Networks with Group Deployment of Nodes
Uncategorized
Keith M. Martin, Maura B. Paterson, Douglas R. Stinson
Show abstract
Uncategorized
Recent literature contains proposals for key predistribution schemes for sensor networks in which nodes are deployed in separate groups. In this paper we consider the implications of group deployment for the connectivity and resilience of a key predistribution scheme. After showing that there is a lack of flexibility in the parameters of a scheme due to Liu, Ning and Du, limiting its applicability in networks with small numbers of groups, we propose a more general scheme, based on the structure of a resolvable transversal design. We demonstrate that this scheme permits effective trade-offs between resilience, connectivity and storage requirements within a group-deployed environment as compared with other schemes in the literature, and show that group deployment can be used to increase network connectivity, without increasing storage requirements or sacrificing resilience.
Last updated:  2008-10-02
Cryptanalysis of LU Decomposition-based Key Pre-distribution Scheme for Wireless Sensor Networks
Bo Zhu, Yanfei Zheng, Yaowei Zhou, Kefei Chen
S. J. Choi and H. Y. Youn proposed a key pre-distribution scheme for Wireless Sensor Networks based on LU decomposition of symmetric matrix, and later many researchers did works based on this scheme. Nevertheless, we find a mathematical relationship of L and U matrixes decomposed from symmetric matrix, by using which we can calculate one matrix from another regardless of their product -- the key matrix K. This relationship would profoundly harm the secure implementation of this decomposition scheme in the real world. In this paper, we first present and prove the mathematical theorem. Next we give samples to illustrate how to break the networks by using this theorem. Finally, we state the conclusion and some directions for improving the security of the key pre-distribution scheme.
Last updated:  2009-04-26
On the Role of PKG for Proxy Re-encryption in Identity Based Setting
Uncategorized
Xu an Wang, Xiaoyuan Yang, Fagen Li
Show abstract
Uncategorized
In 1998, Blaze, Bleumer, and Strauss proposed a kind of cryptographic primitive called proxy re-encryption. In proxy re-encryption, a proxy can transform a ciphertext computed under Alice's public key into one that can be opened under Bob's decryption key. In 2007, Matsuo proposed the concept of four types of proxy re-encryption schemes: CBE(Certificate Based Public Key Encryption) to IBE(Identity Based Encryption)(type 1), IBE to IBE(type 2), IBE to CBE (type 3), CBE to CBE (type 4). Now CBE to IBE and IBE to IBE proxy re-encryption schemes are being standardized by IEEEP1363.3 working group. In this paper, based on we pay attention to the role of PKG for proxy re-encryption in identity based setting. We find that if we allow the PKG to use its master-key in the process of generating re-encryption key for proxy re-encryption in identity based setting, many open problems can be solved. Our main results are as following: We construct the first proxy re-encryption scheme from CBE to IBE which can resist malicious PKG attack, the first proxy re-encryption scheme from IBE to CBE, the second proxy re-encryption scheme based on a variant of BB_1 IBE, the first proxy re-encryption scheme based on BB_2 IBE, the first proxy re-encryption scheme based on SK IBE, we also prove their security in their corresponding security models.
Last updated:  2008-10-02
A New $(k,n)$-Threshold Secret Sharing Scheme and Its Extension
Jun Kurihara, Shinsaku Kiyomoto, Kazuhide Fukushima, Toshiaki Tanaka
In Shamir's $(k,n)$-threshold secret sharing scheme (threshold scheme), a heavy computational cost is required to make $n$ shares and recover the secret. As a solution to this problem, several fast threshold schemes have been proposed. This paper proposes a new (k,n)$-threshold scheme. For the purpose to realize high performance, the proposed scheme uses just EXCLUSIVE-OR(XOR) operations to make shares and recover the secret. We prove that the proposed scheme is a {\it perfect} secret sharing scheme, every combination of $k$ or more participants can recover the secret, but every group of less than $k$ participants cannot obtain any information about the secret. Moreover, we show that the proposed scheme is an {\it ideal} secret sharing scheme similar to Shamir's scheme, which is a {\it perfect} scheme such that every bit-size of shares equals that of the secret. We also evaluate the efficiency of the scheme, and show that our scheme realizes operations that are much faster than Shamir's. Furthermore, from the aspect of both computational cost and storage usage, we also introduce how to extend the proposed scheme to a new $(k,L,n)$-threshold {\it ramp} scheme similar to the existing {\it ramp} scheme based on Shamir's scheme.
Last updated:  2008-10-02
The Enigmatique Toolkit
Christopher Billings
Abstract: This paper describes a new method of creating systems of poly-alphabetic, symmetric ciphers with a large set of algorithms. The method uses two translation tables containing the code-text character set, one for encryption and the other for decryption. After each character is encrypted or decrypted, these tables are permuted through a series of pseudo random, pairwise swaps. The implementation of alternative swap formulas leads to systems with large sets of encryption/decryption algorithms. Systems that contain more than a googol (1E100) algorithms have been easily implemented. An algorithm set can be easily sub-setted, producing hierarchical systems where a program may contain a single algorithm or a portion of the full set. The strength of these systems has not been determined. However strength can be inferred through the use of a substantial number of numeric keys , pseudo random number generators, algorithm switching, and other features.
Last updated:  2008-12-12
Indifferentiable Security Analysis of choppfMD, chopMD, a chopMDP, chopWPH, chopNI, chopEMD, chopCS, and chopESh Hash Domain Extensions
Uncategorized
Donghoon Chang, Jaechul Sung, Seokhie Hong, Sangjin Lee
Show abstract
Uncategorized
We provide simple and unified indifferentiable security analyses of choppfMD, chopMD, a chopMDP (where the permutation $P$ is to be xored with any non-zero constant.), chopWPH (the chopped version of Wide-Pipe Hash proposed in \cite{Lucks05}), chopEMD, chopNI, chopCS, chopESh hash domain extensions. Even though there are security analysis of them in the case of no-bit chopping (i.e., $s=0$), there is no unified way to give security proofs. All our proofs in this paper follow the technique introduced in \cite{BeDaPeAs08}. These proofs are simple and easy to follow.
Last updated:  2008-09-24
An asymptotically optimal RFID protocol against relay attacks
Gildas Avoine, Aslan Tchamkerten
Relay attacks are a major concern for RFID systems: during an authentication process an adversary transparently relays messages between a verifier and a remote legitimate prover. We present an authentication protocol suited for RFID systems. Our solution is the first that prevents relay attacks without degrading the authentication security level: it minimizes the probability that the verifier accepts a fake proof of identity, whether or not a relay attack occurs.
Last updated:  2008-09-24
Slid Pairs in Salsa20 and Trivium
Deike Priemuth-Schmid, Alex Biryukov
The stream ciphers Salsa20 and Trivium are two of the finalists of the eSTREAM project which are in the final portfolio of new promising stream ciphers. In this paper we show that initialization and key-stream generation of these ciphers is {\em slidable}, i.e. one can find distinct (Key, IV) pairs that produce identical (or closely related) key-streams. There are $2^{256}$ and more then $2^{39}$ such pairs in Salsa20 and Trivium respectively. We write out and solve the non-linear equations which describe such related (Key, IV) pairs. This allows us to sample the space of such related pairs efficiently as well as detect such pairs in large portions of key-stream very efficiently. We show that Salsa20 does not have 256-bit security if one considers general birthday and related key distinguishing and key-recovery attacks.
Last updated:  2008-09-24
Pairing with Supersingular Trace Zero Varieties Revisited
Emanuele Cesena
A Trace Zero Variety is a specific subgroup of the group of the divisor classes on a hyperelliptic curve $C/\F_q$, which are rational over a small degree extension $\F_{q^r}$ of the definition field. Trace Zero Varieties (\tzv) are interesting for cryptographic applications since they enjoy properties that can be exploited to achieve fast arithmetic and group construction. Furthermore, supersingular \tzv allows to achieve higher MOV security per bit than supersingular elliptic curves, thus making them interesting for applications in pairing-based cryptography. In this paper we survey algorithms in literature for computing bilinear pairings and we present a new algorithm for the Tate pairing over supersingular \tzv, which exploits the action of the $q$-Frobenius. We give explicit examples and provide experimental results for supersingular \tzv defined over fields of characteristic 2. Moreover, in the same settings, we propose a more efficient variant of the Silverberg's point compression algorithm.
Last updated:  2008-09-24
SPICE Simulation of a "Provably Secure" True Random Number Generator
Markus Dichtl, Bernd Meyer, Hermann Seuschek
In their paper "A Provably Secure True Random Number Generator with Built-in Tolerance to Active Attacks", B. Sunar, W. Martin, and D. Stinson propose a design for a true random number generator. Using SPICE simulation we study the behaviour of their random number generator and show that practical implementations result in a too high frequency signal to be processed with current CMOS technology.
Last updated:  2008-09-24
Algebraic Cryptanalysis of Curry and Flurry using Correlated Messages
Jean-Charles Faugère, Ludovic Perret
In \cite{BPW}, Buchmann, Pyshkin and Weinmann have described two families of Feistel and SPN block ciphers called Flurry and Curry respectively. These two families of ciphers are fully parametrizable and have a sound design strategy against basic statistical attacks; i.e. linear and differential attacks. The encryption process can be easily described by a set of algebraic equations. These ciphers are then targets of choices for algebraic attacks. In particular, the key recovery problem has been reduced to changing the order of a Groebner basis \cite{BPW,BPWext}. This attack - although being more efficient than linear and differential attacks - remains quite limited. The purpose of this paper is to overcome this limitation by using a small number of suitably chosen pairs of message/ciphertext for improving algebraic attacks. It turns out that this approach permits to go one step further in the (algebraic) cryptanalysis of Flurry and \textbf{Curry}. To explain the behavior of our attack, we have established an interesting connection between algebraic attacks and high order differential cryptanalysis \cite{Lai}. From extensive experiments, we estimate that our approach, that we can call an ``algebraic-high order differential" cryptanalysis, is polynomial when the Sbox is a power function. As a proof of concept, we have been able to break Flurry -- up to $8$ rounds -- in few hours.
Last updated:  2008-09-24
Two New Efficient CCA-Secure Online Ciphers: MHCBC and MCBC
Mridul Nandi
Online ciphers are those ciphers whose ciphertexts can be computed in real time by using a length-preserving encryption algorithm. HCBC1 and HCBC2 are two known examples of Hash Cipher Block Chaining online ciphers. The first construction is secure against chosen plaintext adversary (or called CPA-secure) whereas the latter is secure against chosen ciphertext adversary (or called CCA-secure). In this paper, we have provided simple security analysis of these online ciphers. We have also proposed two new more efficient chosen ciphertext secure online ciphers modified-HCBC (MHCBC) and modified-CBC (MCBC). If one uses a finite field multiplication based universal hash function, the former needs one less key and one less field multiplication compared to HCBC2. The MCBC does not need any universal hash function and it needs only one blockcipher key unlike the other three online ciphers where two independent keys (hash function and blockcipher) are required.
Last updated:  2008-09-24
Comments on two password based protocols
Yalin Chen, Hung-Min Sun, Chun-Hui Huang, Jue-Sam Chou
Recently, M. Hölbl et al. and I. E. Liao et al. each proposed an user authentication protocol. Both claimed that their schemes can withstand password guessing attack. However, T. Xiang et al. pointed out I. E. Liao et al.'s protocol suffers three kinds of attacks, including password guessing attacks. We present an improvement protocol to get rid of password guessing attacks. In this paper, we first point out the security loopholes of M. Hölbl et al.'s protocol and review T. Xiang et al.'s cryptanalysis on I. E. Liao et al.'s protocol. Then, we present the improvements on M. Hölbl et al.'s protocol and I. E. Liao et al.'s protocol, respectively.
Last updated:  2008-09-24
Round Efficient Unconditionally Secure Multiparty Computation Protocol
Arpita Patra, Ashish Choudhary, C. Pandu Rangan
In this paper, we propose a round efficient {\it unconditionally secure multiparty computation} (UMPC) protocol in {\it information theoretic} model with $n > 2t$ players, in the absence of any physical broadcast channel, which communicates ${\cal O}(n^4)$ field elements per multiplication and requires ${\cal O}(n \log(n) + {\cal D})$ rounds, even if up to $t$ players are under the control of an active adversary having {\it unbounded computing power}. In the absence of a physical broadcast channel and with $n > 2t$ players, the best known UMPC protocol with minimum number of rounds, requires ${\cal O}(n^2{\cal D})$ rounds and communicates ${\cal O}(n^6)$ field elements per multiplication, where ${\cal D}$ denotes the multiplicative depth of the circuit representing the function to be computed securely. On the other hand, the best known UMPC protocol with minimum communication complexity requires communication overhead of ${\cal O}(n^2)$ field elements per multiplication, but has a round complexity of ${\cal O}(n^3 +{\cal D})$ rounds. Hence our UMPC protocol is the most round efficient protocol so far and ranks second according to communication complexity. To design our protocol, we use certain new techniques which are of independent interest.
Last updated:  2008-10-31
Generating genus two hyperelliptic curves over large characteristic finite fields
Takakazu Satoh
In hyperelliptic curve cryptography, finding a suitable hyperelliptic curve is an important fundamental problem. One of necessary conditions is that the order of its Jacobian is a product of a large prime number and a small number. In the paper, we give a probabilistic polynomial time algorithm to test whether the Jacobian of the given hyperelliptic curve of the form $Y sup 2 = X sup 5 + u X sup 3 + v X$ satisfies the condition and, if so, gives the largest prime factor. Our algorithm enables us to generate random curves of the form until the order of its Jacobian is almost prime in the above sense. A key idea is to obtain candidates of its zeta function over the base field from its zeta function over the extension field where the Jacobian splits.
Last updated:  2008-11-27
A Framework for the Development Playfair Cipher Considering Probability of Occurrence of Characters in English Literature
Uttam Kr. Mondal, Satyendra Nath Mandal, J. PalChoudhury
The Playfair cipher was the first practical digraph substitution cipher. The scheme was invented in 1854 by Charless Wheatstone, but was the named after Lord Playfair who promoted the use of the cipher. In this paper, two algorithms have been proposed to written the Playfair cipher. The first effort is being made to write the playfair cipher in a new way by considering the probability of the occurrence of english character in context to english literature. In the proposed algorithm at each and every time, the algorithm will check whether, the plain text contains odd number of words or not. If the plain text is of odd number of characters, the algorithm will concatenate a dummy character at the end with lowest probability to form even length word in the cipher text and then search is being made in the dictionary to find out whether the word with dummy character is present in the dictionary or not. If that word is present in the dictionary, delete that dummy character of that word and the same effort is being made with another dummy character with next lowest probability occurrence. The second method add another new approach, it replace all blanks between two consecutive word by some character which has least probability to appear at that position in the sentence and search the dictionary to check whether this new word has different meaning . If new word if present, replace blank with next higher probability character for this blank. Finally, time comparison has made of encryption and decryption of some sentences using original with two algorithms and it has been found that the decryption time are much better than original play fair algorithm and that will produce the original message from encrypted message directly.
Last updated:  2011-11-03
Analysis of RC4 and Proposal of Additional Layers for Better Security Margin
Subhamoy Maitra, Goutam Paul
In this paper, the RC4 Key Scheduling Algorithm (KSA) is theoretically studied to reveal non-uniformity in the expected number of times each value of the permutation is touched by the indices $i, j$. Based on our analysis and the results available in literature regarding the existing weaknesses of RC4, few additional layers over the RC4 KSA and RC4 Pseudo-Random Generation Algorithm (PRGA) are proposed. Analysis of the modified cipher (we call it RC4$^+$) shows that this new strategy avoids existing weaknesses of RC4.
Last updated:  2008-09-22
New Applications of Differential Bounds of the SDS Structure
Jiali Choy, Khoongming Khoo
In this paper, we present some new applications of the bounds for the differential probability of a SDS (Substitution-Diffusion-Substitution) structure by Park et al. at FSE 2003. Park et al. have applied their result on the AES cipher which uses the SDS structure based on MDS matrices. We shall apply their result to practical ciphers that use SDS structures based on {0,1}-matrices of size n times n. These structures are useful because they can be efficiently implemented in hardware. We prove a bound on {0,1}-matrices to show that they cannot be MDS and are almost-MDS only when n=2,3 or 4. Thus we have to apply Park's result whenever {0,1}-matrices where $n \geq 5$ are used because previous results only hold for MDS and almost-MDS diffusion matrices. Based on our bound, we also show that the {0,1}-matrix used in E2 is almost-optimal among {0,1}-matrices. Using Park's result, we prove differential bounds for E2 and an MCrypton-like cipher, from which we can deduce their security against boomerang attack and some of its variants. At ICCSA 2006, Khoo and Heng constructed block cipher-based universal hash functions, from which they derived Message Authentication Codes (MACs) which are faster than CBC-MAC. Park's result provides us with the means to obtain a more accurate bound for their universal hash function. With this bound, we can restrict the number of MAC's performed before a change of MAC key is needed.
Last updated:  2008-09-16
Attribute-Based Ring Signatures
Jin Li, Kwangjo Kim
Ring signature was proposed to keep signer's anonymity when it signs messages on behalf of a ``ring" of possible signers. In this paper, we propose a novel notion of ring signature which is called attribute-based ring signature. In this kind of signature, it allows the signer to sign message with its attributes from attribute center. All users that possess of these attributes form a ring. The identity of signer is kept anonymous in this ring. Furthermore, anyone out of this ring could not forge the signature on behalf of the ring. Two constructions of attribute-based ring signature are also presented in this paper. The first scheme is proved to be secure in the random oracle model, with large universal attributes. We also present another scheme in order to avoid the random oracle model. It does not rely on non-standard hardness assumption or random oracle model. Both schemes in this paper are based on standard computational Diffie-Hellman assumption.
Last updated:  2009-11-30
How Far Must You See To Hear Reliably
Uncategorized
Pranav K Vasishta, Anuj Gupta, Prasant Gopal, Piyush Bansal, Rishabh Mukherjee, Poornima M, Kannan Srinathan, Kishore Kothapalli
Show abstract
Uncategorized
We consider the problem of probabilistic reliable communication (PRC) over synchronous networks modeled as directed graphs in the presence of a Byzantine adversary when players' knowledge of the network topology is not complete. We show that possibility of PRC is extremely sensitive to the changes in players' knowledge of the topology. This is in complete contrast with earlier known results on the possibility of perfectly reliable communication over undirected graphs where the case of each player knowing only its neighbours gives the same result as the case where players have complete knowledge of the network. Specifically, in either case, $(2t+1)$-vertex connectivity is necessary and sufficient, where $t$ is the number of nodes that can be corrupted by the adversary \cite{DDWY93:PSMT,SKR05}. We introduce a novel model for quantifying players' knowledge of network topology, denoted by {$\mathcal TK$}. Given a directed graph $G$, influenced by a Byzantine adversary that can corrupt up to any $t$ players, we give a necessary and sufficient condition for possibility of PRC over $G$ for any arbitrary topology knowledge {$\mathcal TK$}. It follows from our main characterization theorem that knowledge of up to $d = \lfloor \frac{n - 2t}{3} \rfloor + 1$ levels is sufficient for the solvability of honest player to honest player communication over any network over which PRC is possible when each player has complete knowledge of the topology. We also show the existence of networks where PRC is possible when players have complete topology knowledge but it is not possible when the players do not have knowledge of up to $d = \lfloor \frac{n - 2t}{3} \rfloor + 1$ levels.
Last updated:  2009-02-04
GUC-Secure Set-Intersection Computation
Uncategorized
TIAN Yuan, WANG Ying
Show abstract
Uncategorized
Secure set-intersection computation is one of important problems in the field of secure multiparty computation with valuable applications. We propose a very gerneral construction for 2-party set-intersection computation based-on anonymous IBE scheme and its user private-keys blind generation techniques. Compared with recently-proposed protocols, e.g., those of Freedman-Nissim-Pinkas, Kissner-Song and Hazay-Lindell, this construction is provabley GUC-secure in standard model with acceptable efficiency. For this goal a new notion of non-malleable zero-knowledge proofs of knowledge and its efficient general construction is presented. In addition, we present an efficient instantiation of this general construction via anonymous Boyen-Waters IBE scheme.
Last updated:  2008-11-25
Could The 1-MSB Input Difference Be The Fastest Collision Attack For MD5 ?
Tao Xie, FanBao Liu, DengGuo Feng
So far, two different 2-block collision differentials, both with 3-bit input differences for MD5, have been found by Wang etc in 2005 and Xie etc in 2008 respectively, and those differentials have been improved later on to generate a collision respectively within around one minute and half an hour on a desktop PC. Are there more collision differentials for MD5? Can a more efficient algorithm be developed to find MD5 collisions? In this paper, we list the whole set of 1-bit to 3-bit input difference patterns that are possibly qualified to construct a feasible collision differential, and from which a new collision differential with only 1-MSB input difference is then analyzed in detail, finally the performances are compared with the prior two 3-bit collision attacks according to seven criteria proposed in this paper. In our approach, a two-block message is still needed to produce a collision, the first block being only one MSB different while the second block remains the same. Although the differential path appears to be computationally infeasible, most of the conditions that a collision differential path must satisfy can be fulfilled by multi-step modifications, and the collision searching efficiency can be much improved further by a specific divide-and-conquer technique, which transforms a multiplicative accumulation of the computational complexities into an addition by properly grouping of the conditional bits. In particular, a tunneling-like technique is applied to enhance the attack algorithm by introducing some additional conditions. As a result, the fastest attack algorithm is obtained with an averaged computational complexity of 2^20.96 MD5 compressions, which implies that it is able to search a collision within a second on a common PC for arbitrary random initial values. With a reasonable probability a collision can be found within milliseconds, allowing for instancing an attack during the execution of a practical protocol. The collision searching algorithm, however, is very complex, but the algorithm has been implemented which is available from the website http://www.is.iscas.ac.cn/gnomon, and we suggest you download the implementation program from the website for a personal experience if you are interested in it.
Last updated:  2011-08-15
Elliptic Curve Cryptography: The Serpentine Course of a Paradigm Shift
Ann Hibner Koblitz, Neal Koblitz, Alfred Menezes
Over a period of sixteen years elliptic curve cryptography went from being an approach that many people mistrusted or misunderstood to being a public key technology that enjoys almost unquestioned acceptance. We describe the sometimes surprising twists and turns in this paradigm shift, and compare this story with the commonly accepted Ideal Model of how research and development function in cryptography. We also discuss to what extent the ideas in the literature on "social construction of technology" can contribute to a better understanding of this history.
Last updated:  2008-09-15
Optimal Subset-Difference Broadcast Encryption with Free Riders
Murat Ak, Kamer Kaya, Ali Aydin Selcuk
Broadcast encryption (BE) deals with secure transmission of a message to a group of receivers such that only an authorized subset of receivers can decrypt the message. The transmission cost of a BE system can be reduced considerably if a limited number of free riders can be tolerated in the system. In this paper, we study the problem of how to optimally place a given number of free riders in a subset difference (SD) based BE system, which is currently the most efficient BE scheme in use and has also been incorporated in standards, and we propose a polynomial-time optimal placement algorithm and three more efficient heuristics for this problem. Simulation experiments show that SD-based BE schemes can benefit significantly from the proposed algorithms.
Last updated:  2010-04-27
Double-Base Number System for Multi-Scalar Multiplications
Christophe Doche, David R. Kohel, Francesco Sica
The Joint Sparse Form is currently the standard representation system to perform multi-scalar multiplications of the form $[n]P+m[Q]$. We introduce the concept of Joint Double-Base Chain, a generalization of the Double-Base Number System to represent simultaneously $n$ and $m$. This concept is relevant because of the high redundancy of Double-Base systems, which ensures that we can find a chain of reasonable length that uses exactly the same terms to compute both $n$ and $m$. Furthermore, we discuss an algorithm to produce such a Joint Double-Base Chain. Because of its simplicity, this algorithm is straightforward to implement, efficient, and also quite easy to analyze. Namely, in our main result we show that the average number of terms in the expansion is less than $0.3945\log_2 n$. With respect to the Joint Sparse Form, this induces a reduction by more than $20\%$ of the number of additions. As a consequence, the total number of multiplications required for a scalar multiplications is minimal for our method, across all the methods using two precomputations, $P+Q$ and $P-Q$. This is the case even with coordinate systems offering very cheap doublings, in contrast with recent results on scalar multiplications. Several variants are discussed, including methods using more precomputed points and a generalization relevant for Koblitz curves. Our second contribution is a new way to evaluate $\overline\phi$, the dual endomorphism of the Frobenius. Namely, we propose formulae to compute $\pm\overline\phi(P)$ with at most 2 multiplications and 2 squarings in $\F_{2^d}$. This represents a speed-up of about $50\%$ with respect to the fastest techniques known. This has very concrete consequences on scalar and multi-scalar multiplications on Koblitz curves.
Last updated:  2009-02-13
--Withdrawn--
Uncategorized
--withdrawn--
Uncategorized
None
Last updated:  2008-09-15
Shared Key Encryption by the State Machine with Two-Dimensional Random Look-up Table
Michael Lifliand
This paper describes a new approach to creation of fast encryption methods with symmetric (shared) key. The result solution is intermediate one between block and stream ciphers. The main advantages of both types of ciphers are realized, while most of disadvantages are eliminated. The new approach combines encryption with built-in calculation of the hash for the data integrity, pseudo-random generator, and option for dual shared keys. These properties are pivotal for secure applications. These new methods may be designed for different size of shared secret key. Both software and hardware implementations of the new methods are fast and simple and may be used in various security applications. Presented cryptanalysis proves basic features and gives an option to design actual provable security methods.
Last updated:  2009-01-26
Cube Attacks on Tweakable Black Box Polynomials
Uncategorized
Itai Dinur, Adi Shamir
Show abstract
Uncategorized
Almost any cryptographic scheme can be described by \emph{tweakable polynomials} over $GF(2)$, which contain both secret variables (e.g., key bits) and public variables (e.g., plaintext bits or IV bits). The cryptanalyst is allowed to tweak the polynomials by choosing arbitrary values for the public variables, and his goal is to solve the resultant system of polynomial equations in terms of their common secret variables. In this paper we develop a new technique (called a \emph{cube attack}) for solving such tweakable polynomials, which is a major improvement over several previously published attacks of the same type. For example, on the stream cipher Trivium with a reduced number of initialization rounds, the best previous attack (due to Fischer, Khazaei, and Meier) requires a barely practical complexity of $2^{55}$ to attack $672$ initialization rounds, whereas a cube attack can find the complete key of the same variant in $2^{19}$ bit operations (which take less than a second on a single PC). Trivium with $735$ initialization rounds (which could not be attacked by any previous technique) can now be broken with $2^{30}$ bit operations. Trivium with $767$ initialization rounds can now be broken with $2^{45}$ bit operations, and the complexity of the attack can almost certainly be further reduced to about $2^{36}$ bit operations. Whereas previous attacks were heuristic, had to be adapted to each cryptosystem, had no general complexity bounds, and were not expected to succeed on random looking polynomials, cube attacks are provably successful when applied to random polynomials of degree $d$ over $n$ secret variables whenever the number $m$ of public variables exceeds $d+log_dn$. Their complexity is $2^{d-1}n+n^2$ bit operations, which is polynomial in $n$ and amazingly low when $d$ is small. Cube attacks can be applied to any block cipher, stream cipher, or MAC which is provided as a black box (even when nothing is known about its internal structure) as long as at least one output bit can be represented by (an unknown) polynomial of relatively low degree in the secret and public variables.
Last updated:  2008-09-14
Improving the Boneh-Franklin Traitor Tracing Scheme
Pascal Junod, Alexandre Karlov, Arjen K. Lenstra
Traitor tracing schemes are cryptographically secure broadcast methods that allow identification of conspirators: if a pirate key is generated by $k$ traitors out of a static set of $\ell$ legitimate users, then all traitors can be identified given the pirate key. In this paper we address three practicality and security issues of the Boneh-Franklin traitor-tracing scheme. In the first place, without changing the original scheme, we modify its tracing procedure in the non-black-box model such that it allows identification of $k$ traitors in time $\tilde{O}(k^2)$, as opposed to the original tracing complexity $\tilde{O}(\ell)$. This new tracing procedure works independently of the nature of the Reed-Solomon code used to watermark private keys. As a consequence, in applications with billions of users it takes just a few minutes on a common desktop computer to identify large collusions. Secondly, we exhibit the lack of practical value of list-decoding algorithms to identify more than $k$ traitors. Finally, we show that $2k$ traitors can derive the keys of all legitimate users and we propose a fix to this security issue.
Last updated:  2008-09-14
Hierarchical Identity Based Encryption with Polynomially Many Levels
Craig Gentry, Shai Halevi
We present the first hierarchical identity based encryption (HIBE) system that has full security for more than a constant number of levels. In all prior HIBE systems in the literature, the security reductions suffered from exponential degradation in the depth of the hierarchy, so these systems were only proven fully secure for identity hierarchies of constant depth. (For deep hierarchies, previous work could only prove the weaker notion of selective-ID security.) In contrast, we offer a tight proof of security, regardless of the number of levels; hence our system is secure for polynomially many levels. Our result can very roughly be viewed as an application of Boyen's framework for constructing HIBE systems from exponent-inversion IBE systems to a (dramatically souped-up) version of Gentry's IBE system, which has a tight reduction. In more detail, we first describe a generic transformation from ``identity based broadcast encryption with key randomization" (KR-IBBE) to a HIBE, and then construct KR-IBBE by modifying a recent construction of IBBE of Gentry and Waters, which is itself an extension of Gentry's IBE system. Our hardness assumption is similar to that underlying Gentry's IBE system.
Last updated:  2008-12-16
Authenticated Wireless Roaming via Tunnels: Making Mobile Guests Feel at Home
Uncategorized
Mark Manulis, Damien Leroy, Francois Koeune, Olivier Bonaventure, Jean-Jacques Quisquater
Show abstract
Uncategorized
In wireless roaming a mobile device obtains a service from some foreign network while being registered for the similar service at its own home network. However, recent proposals try to keep the service provider role behind the home network and let the foreign network create a tunnel connection through which all service requests of the mobile device are sent to and answered directly by the home network. Such Wireless Roaming via Tunnels (WRT) offers several (security) benefits but states also new security challenges on authentication and key establishment, as the goal is not only to protect the end-to-end communication between the tunnel peers but also the tunnel itself. In this paper we formally specify mutual authentication and key establishment goals for WRT and propose an efficient and provably secure protocol that can be used to secure such roaming session. Additionally, we describe some modular protocol extensions to address resistance against DoS attacks, anonymity of the mobile device and unlinkability of its roaming sessions, as well as the accounting claims of the foreign network in commercial scenarios.
Last updated:  2008-09-25
New AES software speed records
Daniel J. Bernstein, Peter Schwabe
This paper presents new speed records for AES software,taking advantage of (1) architecture-dependent reduction of instructions used to compute AES and (2) microarchitecture-dependent reduction of cycles used for those instructions. A wide variety of common CPU architectures---amd64, ppc32, sparcv9, and x86---are discussed in detail, along with several specific microarchitectures.
Last updated:  2008-09-07
Dynamic Threshold Cryptosystem without Group Manager
Andreas Noack, Stefan Spitz
In dynamic networks with flexible memberships, group signatures and distributed signatures are an important problem. Dynamic threshold cryptosystems are best suited to realize distributed signatures in dynamic (e.g. meshed) networks. Without a group manager or a trusted third party even more flexible scenarios can be realized. Gennaro et al. showed, it is possible to dynamically increase the size of the signer group, without altering the public key. We extend this idea by removing members from the group, also without changing the public key. This is an important feature for dynamic groups, since it is very common, e.g. in meshed networks that members leave a group. Gennaro et al. used RSA and bi-variate polynomials for their scheme. In contrast, we developed a DL-based scheme that uses ideas from the field of proactive secret sharing (PSS). One advantage of our scheme is the possibility to use elliptic curve cryptography and thereby decrease the communication and computation complexity through a smaller security parameter. Our proposal is an efficient threshold cryptosystem that is able to adapt the group size in both directions. Since it is not possible to realize a non-interactive scheme with the ability to remove members (while the public key stays unchanged), we realized an interactive scheme whose communication efficency is highly optimized to compete with non-interactive schemes. Our contribution also includes a security proof for our threshold scheme.
Last updated:  2011-06-01
A Characterization of Chameleon Hash Functions and New, Efficient Designs
Uncategorized
Mihir Bellare, Todor Ristov
Show abstract
Uncategorized
This paper shows that chameleon hash functions and Sigma protocols are equivalent. We provide a transform of any suitable Sigma protocol to a chameleon hash function, and also show that any chameleon hash function is the result of applying our transform to some suitable Sigma protocol. This enables us to unify previous designs of chameleon hash functions, seeing them all as emanating from a common paradigm, and also obtain new designs that are more efficient than previous ones. In particular, via a modified version of the Fiat-Shamir protocol, we obtain the fastest known chameleon hash function with a proof of security based on the STANDARD factoring assumption. The increasing number of applications of chameleon hash functions, including on-line/off-line signing, chameleon signatures, designated-verifier signatures and conversion from weakly-secure to fully-secure signatures, make our work of contemporary interest.
Last updated:  2010-08-15
Additively Homomorphic Encryption with d-Operand Multiplications
Uncategorized
Carlos Aguilar Melchor, Philippe Gaborit, Javier Herranz
Show abstract
Uncategorized
The search for encryption schemes that allow to evaluate functions (or circuits) over encrypted data has attracted a lot of attention since the seminal work on this subject by Rivest, Adleman and Dertouzos in 1978. In this work we define a theoretical object, chained encryption schemes, which allow an efficient evaluation of polynomials of degree d over encrypted data. Chained encryption schemes are generically constructed by concatenating cryptosystems with the appropriate homomorphic properties; such schemes are common in lattice-based cryptography. As a particular instantiation we propose a chained encryption scheme whose IND-CPA security is based on a worst-case/average-case reduction from uSVP.
Last updated:  2008-09-06
TRIVIUM's output partially autocancels
Michael Vielhaber
The eStream cipher proposal TRIVIUM outputs an XOR sum of six internal state bits. These in turn are obtained from 18 bits linearly, plus six ANDings of two bits each. We show that 4 of the 18 linear terms cancel between themselves.
Last updated:  2009-06-09
Session-state Reveal is stronger than Ephemeral Key Reveal: Attacking the NAXOS Authenticated Key Exchange protocol
Cas J. F. Cremers
In the papers Stronger Security of Authenticated Key Exchange [LLM07, LLM06], a new security model for key exchange protocols is proposed. The new model is suggested to be at least as strong as previous models for key exchange protocols. In particular, the model includes a new notion of an Ephemeral Key Reveal adversary query, which is claimed in [LLM06, Oka07, Ust08] to be at least as strong as existing definitions of the Session-state Reveal query. We show that for some protocols, Session-state Reveal is strictly stronger than Ephemeral Key Reveal. In particular, we show that the NAXOS protocol from [LLM07, LLM06] does not meet its security requirements if the Session-state Reveal query is allowed in the security model.
Last updated:  2009-01-16
A public key encryption scheme secure against key dependent chosen plaintext and adaptive chosen ciphertext attacks
Uncategorized
Jan Camenisch, Nishanth Chandran, Victor Shoup
Show abstract
Uncategorized
Recently, at Crypto 2008, Boneh, Halevi, Hamburg, and Ostrovsky (BHHO) solved the long-standing open problem of ``circular encryption,'' by presenting a public key encryption scheme and proving that it is semantically secure against key dependent chosen plaintext attack (KDM-CPA security) under standard assumptions (and without resorting to random oracles). However, they left as an open problem that of designing an encryption scheme that \emph{simultaneously} provides security against both key dependent chosen plaintext \emph{and} adaptive chosen ciphertext attack (KDM-CCA2 security). In this paper, we solve this problem. First, we show that by applying the Naor-Yung ``double encryption'' paradigm, one can combine any KDM-CPA secure scheme with any (ordinary) CCA2 secure scheme, along with an appropriate non-interactive zero-knowledge proof, to obtain a KDM-CCA2 secure scheme. Second, we give a concrete instantiation that makes use the above KDM-CPA secure scheme of BHHO, along with a generalization of the Cramer-Shoup CCA2 secure encryption scheme, and recently developed pairing-based NIZK proof systems. This instantiation increases the complexity of the BHHO scheme by just a small constant factor.
Last updated:  2008-09-05
Chosen Ciphertext Security with Optimal Ciphertext Overhead
Masayuki Abe, Eike Kiltz, Tatsuaki Okamoto
Every public-key encryption scheme has to incorporate a certain amount of randomness into its ciphertexts to provide semantic security against chosen ciphertext attacks (IND-CCA). The difference between the length of a ciphertext and the embedded message is called the ciphertext overhead. While a generic brute-force adversary running in $2^t$ steps gives a theoretical lower bound of $t$ bits on the ciphertext overhead for IND-CPA security, the best known IND-CCA secure schemes demand roughly $2 t$ bits even in the random oracle model. Is the $t$-bit gap essential for achieving IND-CCA security? We close the gap by proposing an IND-CCA secure scheme whose ciphertext overhead matches the generic lower bound up to a small constant. Our scheme uses a variation of a four-round Feistel network in the random oracle model and hence belongs to the family of OAEP-based schemes. Maybe of independent interest is a new efficient method to encrypt long messages exceeding the length of the permutation while retaining the minimal overhead.
Last updated:  2009-04-08
Analysis and Improvement of Authenticatable Ring Signcryption Scheme
Fagen Li, Masaaki Shirase, Tsuyoshi Takagi
Ring signcryption is an anonymous signcryption which allows a user to anonymously signcrypt a message on behalf of a set of users including himself. In an ordinary ring signcryption scheme, even if a user of the ring generates a signcryption, he also cannot prove that the signcryption was produced by himself. In 2008, Zhang, Yang, Zhu, and Zhang solve the problem by introducing an identity-based authenticatable ring signcryption scheme (denoted as the ZYZZ scheme). In the ZYZZ scheme, the actual signcrypter can prove that the ciphertext is generated by himself, and the others cannot authenticate it. However, in this paper, we show that the ZYZZ scheme is not secure against chosen plaintext attacks. Furthermore, we propose an improved scheme that remedies the weakness of the ZYZZ scheme. The improved scheme has shorter ciphertext size than the ZYZZ scheme. We then prove that the improved scheme satisfies confidentiality, unforgeability, anonymity and authenticatability.
Last updated:  2008-09-01
Enumeration of Balanced Symmetric Functions over GF(p)
Shaojing Fu, Chao Li, Longjiang Qu, Ping Li
It is proved that the construction and enumeration of the number of balanced symmetric functions over GF(p) are equivalent to solving an equation system and enumerating the solutions. Furthermore, we give an lower bound on number of balanced symmetric functions over GF(p), and the lower bound provides best known results.
Last updated:  2008-09-02
Unconditionally Reliable Message Transmission in Directed Hypergraphs
Kannan Srinathan, Arpita Patra, Ashish Choudhary, C. Pandu Rangan
We study the problem of unconditionally reliable message transmission (URMT), where two non-faulty players, the sender S and the receiver R are part of a synchronous network modeled as a directed hypergraph, a part of which may be under the influence of an adversary having unbounded computing power. S intends to transmit a message $m$ to R, such that R should correctly obtain S's message with probability at least $(1-\delta)$ for arbitrarily small $\delta > 0$. However, unlike most of the literature on this problem, we assume the adversary modeling the faults is threshold mixed, and can corrupt different set of nodes in Byzantine, passive and fail-stop fashion simultaneously. The main contribution of this work is the complete characterization of URMT in directed hypergraph tolerating such an adversary. Working out a direct characterization of URMT over directed hypergraphs tolerating threshold mixed adversary is highly un-intuitive. So we first propose a novel technique, which takes as input a directed hypergraph and a threshold mixed adversary on that hypergraph and outputs a corresponding digraph, along with a non-threshold mixed adversary, such that URMT over the hypergraph tolerating the threshold mixed adversary is possible iff a special type of URMT is possible over the obtained digraph, tolerating the corresponding non-threshold mixed adversary}. Thus characterization of URMT over directed hypergraph tolerating threshold mixed adversary reduces to characterizing special type of a URMT over arbitrary digraph tolerating non-threshold mixed adversary. We then characterize URMT in arbitrary digraphs tolerating non-threshold mixed adversary and modify it to obtain the characterization for special type of URMT over digraphs tolerating non-threshold mixed adversary. This completes the characterization of URMT over the original hypergraph. Surprisingly, our results indicate that even passive corruption, in collusion with active faults, substantially affects the reliability of URMT protocols! This is interesting because it is a general belief that passive corruption (eavesdropping) does not affect reliable communication.
Last updated:  2008-08-27
Compartmented Threshold RSA Based on the Chinese Remainder Theorem
Uncategorized
Sorin Iftene, Stefan Ciobaca, Manuela Grindei
Show abstract
Uncategorized
In this paper we combine the compartmented secret sharing schemes based on the Chinese remainder theorem with the RSA scheme in order to obtain, as a novelty, a dedicated solution for compartmented threshold decryption or compartmented threshold digital signature generation. AMS Subject Classification: 94A60, 94A62, 11A07 Keywords and phrases: threshold cryptography, secret sharing, Chinese remainder theorem
Last updated:  2008-10-04
New Directions in Cryptanalysis of Self-Synchronizing Stream Ciphers
Shahram Khazaei, Willi Meier
In cryptology we commonly face the problem of finding an unknown key K from the output of an easily computable keyed function F(C,K) where the attacker has the power to choose the public variable C. In this work we focus on self-synchronizing stream ciphers. First we show how to model these primitives in the above-mentioned general problem by relating appropriate functions F to the underlying ciphers. Then we apply the recently proposed framework presented at AfricaCrypt’08 by Fischer et. al. for dealing with this kind of problems to the proposed T-function based self-synchronizing stream cipher by Klimov and Shamir at FSE’05 and show how to deduce some non-trivial information about the key. We also open a new window for answering a crucial question raised by Fischer et. al. regarding the problem of finding weak IV bits which is essential for their attack.
Last updated:  2008-08-27
Side Channel Attack Resistant Implementation of Multi-Power RSA using Hensel Lifting
Varad Kirtane, C. Pandu Rangan
Multi-Power RSA [1] is a fast variant of RSA [2] with a small decryption time, making it attractive for implementation on lightweight cryptographic devices such as smart cards. Hensel Lifting is a key component in the implementation of fast Multi-Power RSA Decryption. However, it is found that a naive implementation of this algorithm is vulnerable to a host of side channel attacks, some of them powerful enough to entirely break the cryptosystem by providing a factorisation of the public modulus $N$. We propose here a secure (under reasonable assumptions) implementation of the Hensel Lifting algorithm. We then use this algorithm to obtain a secure implementation of Multi-Power RSA Decryption.
Last updated:  2008-08-27
Threshold Homomorphic Encryption in the Universally Composable Cryptographic Library
Uncategorized
Peeter Laud, Long Ngo
Show abstract
Uncategorized
Protocol security analysis has become an active research topic in recent years. Researchers have been trying to build sufficient theories for building automated tools, which give security proofs for cryptographic protocols. There are two approaches for analysing protocols: formal and computational. The former, often called Dolev-Yao style, uses abstract terms to model cryptographic messages with an assumption about perfect security of the cryptographic primitives. The latter mathematically uses indistinguishability to prove that adversaries with computational resources bounds cannot gain anything significantly. The first method is easy to be automated while the second one can give sound proofs of security. Therefore there is a demand to bridge the gap between two methods in order to have better security-proof tools. One idea is to prove that some Dolev-Yao style cryptographic primitives used in formal tools are computationally sound for arbitrary active attacks in arbitrary reactive environments, i.e universally composable. As a consequence, protocols that use such primitives can also be proved secure by formal tools. In this paper, we prove that a homomorphic encryption used together with a non-interactive zero-knowledge proof in Dolev-Yao style are sound abstractions for the real implementation under certain conditions. It helps to automatically design and analyze a class of protocols that use homomorphic encryptions together with non-interactive zero-knowledge proofs, such as e-voting.
Last updated:  2008-09-28
Unique Shortest Vector Problem for max norm is NP-hard
Uncategorized
Than Quang Khoat, Nguyen Hong Tan
Show abstract
Uncategorized
The unique Shortest vector problem (uSVP) in lattice theory plays a crucial role in many public-key cryptosystems. The security of those cryptosystems bases on the hardness of uSVP. However, so far there is no proof for the proper hardness of uSVP even in its exact version. In this paper, we show that the exact version of uSVP for $\ell_\infty$ norm is NP-hard. Furthermore, many other lattice problems including unique Subspace avoiding problem, unique Closest vector problem and unique Generalized closest vector problem, for any $\ell_p$ norm, are also shown to be NP-hard.
Last updated:  2008-10-21
Entropy Bounds for Traffic Confirmation
Luke O'Connor
Consider an open MIX-based anonymity system with $N$ participants and a batch size of $b$. Assume a global passive adversary who targets a given participant Alice with a set ${\cal R}_A$ of $m$ communicating partners. Let $H( {\cal R}_A \mid {\cal B}_t)$ denote the entropy of ${\cal R}_A$ as calculated by the adversary given $t$ message sets (MIX batches) where Alice is a sender in each message set. Our main result is to express the rate at which the anonymity of Alice (as measured by ${\cal R}_A$) degrades over time as a function of the main parameters $N$, $b$ and $m$.
Last updated:  2008-08-27
Zcipher Algorithm Specification
Ilya O Levin
This paper describes the Zcipher - a symmetric encryption/decryption cryptographic algorithm, designed to be secure and high-performance with small memory footprint and simple structure.
Last updated:  2008-08-27
An argument for Hamiltonicity
Vadym Fedyukovych
A constant-round interactive argument is introduced to show existence of a Hamiltonian cycle in a directed graph. Graph is represented with a characteristic polynomial, top coefficient of a verification polynomial is tested to fit the cycle, soundness follows from Schwartz-Zippel lemma.
Last updated:  2009-02-25
The Cost of False Alarms in Hellman and Rainbow Tradeoffs
Jin Hong
Cryptanalytic time memory tradeoff algorithms are generic one-way function inversion techniques that utilize pre-computation. Even though the online time complexity is known up to a small multiplicative factor for any tradeoff algorithm, false alarms pose a major obstacle in its accurate assessment. In this work, we study the expected pre-image size for an iteration of functions and use the result to analyze the cost incurred by false alarms. We are able to present the expected online time complexities for the Hellman tradeoff and the rainbow table method in a manner that takes false alarms into account. We also analyze the effects of the checkpoint method in reducing false alarm costs. The ability to accurately compute the online time complexities will allow one to choose their tradeoff parameters more optimally, before starting the expensive pre-computation process.
Last updated:  2010-12-20
IEEE P1363.1 Draft 10: Draft Standard for Public Key Cryptographic Techniques Based on Hard Problems over Lattices.
William Whyte, Nick Howgrave-Graham, Jeff Hoffstein, Jill Pipher, Joseph H. Silverman, Phil Hirschhorn
Engineering specifications and security considerations for NTRUEncrypt, secure against the lattice attacks presented at Crypto 2007
Last updated:  2008-08-18
An Approach to ensure Information Security through 252-Bit Integrated Encryption System (IES)
Saurabh Dutta, Jyotsna Kumar mandal
In this paper, a block-cipher, Integrated Encryption System (IES), to be implemented in bit-level is presented that requires a 252-bit secret key. In IES, there exist at most sixteen rounds to be implemented in cascaded manner. RPSP, TE, RPPO, RPMS, RSBM, RSBP are the six independent block-ciphering protocols, that are integrated to formulate IES. A round is constituted by implementing one of the protocols on the output produced in the preceding round. The process of encryption is an interactive activity, in which the encryption authority is given enough scope of flexibility regarding choice of protocols in any round. However no protocol can be used in more than three rounds. Formation of key is a run-time activity, which gets built with the interactive encryption process proceeds. Results of implementation of all six protocols in cascaded manner have been observed and analyzed. On achieving a satisfactory level of performance in this cascaded implementation, IES and its schematic and operational characteristics have been proposed.
Last updated:  2008-08-18
Argument of knowledge of a bounded error
Vadym Fedyukovych
A protocol is introduced to show knowledge of a codeword of Goppa code and Goppa polynomial. Protocol does not disclosure any useful information about the codeword and polynomial coefficients. A related protocol is introduced to show Hamming weight of an error is below a threshold. Protocol does not disclosure codeword and weight of the error. Verifier only uses commitments to codeword components and coefficients while testing validity of statements. Both protocols are honest verifier zero knowledge.
Last updated:  2008-08-18
History-Independent Cuckoo Hashing
Moni Naor, Gil Segev, Udi Wieder
Cuckoo hashing is an efficient and practical dynamic dictionary. It provides expected amortized constant update time, worst case constant lookup time, and good memory utilization. Various experiments demonstrated that cuckoo hashing is highly suitable for modern computer architectures and distributed settings, and offers significant improvements compared to other schemes. In this work we construct a practical {\em history-independent} dynamic dictionary based on cuckoo hashing. In a history-independent data structure, the memory representation at any point in time yields no information on the specific sequence of insertions and deletions that led to its current content, other than the content itself. Such a property is significant when preventing unintended leakage of information, and was also found useful in several algorithmic settings. Our construction enjoys most of the attractive properties of cuckoo hashing. In particular, no dynamic memory allocation is required, updates are performed in expected amortized constant time, and membership queries are performed in worst case constant time. Moreover, with high probability, the lookup procedure queries only two memory entries which are independent and can be queried in parallel. The approach underlying our construction is to enforce a canonical memory representation on cuckoo hashing. That is, up to the initial randomness, each set of elements has a unique memory representation.
Last updated:  2008-08-18
A protocol for K-multiple substring matching
Vadym Fedyukovych, Vitaliy Sharapov
A protocol is introduced to show $K$ copies of a pattern string are embedded is a host string. Commitments to both strings, and to offsets of copies of the pattern in the host is input of Verifier. Protocol does not leak useful information about strings, and is zero knowledge.
Last updated:  2008-08-18
Using Commutative Encryption to Share a Secret
Saied Hosseini Khayat
It is shown how to use commutative encryption to share a secret. Suppose Alice wants to share a secret with Bob such that Bob cannot decrypt the secret unless a group of trustees agree. It is assumed that Alice, Bob and the trustees communicate over insecure channels. This paper presents a scheme that uses modular exponentiation and does not require key exchange. The security of the scheme rest of the difficulty of the discrete logarithm problem.
Last updated:  2008-08-18
An argument for rank metric
Vadym Fedyukovych
A protocol is introduced to show an upper bound for rank of a square matrix
Last updated:  2008-08-31
On DDos Attack against Proxy in Re-encryption and Re-signature
Uncategorized
Xu an Wang
Uncategorized
In 1998, Blaze, Bleumer, and Strauss proposed new kind of cryptographic primitives called proxy re-encryption and proxy re-signature[BBS98]. In proxy re-encryption, a proxy can transform a ciphertext computated under Alice's public key into one that can be opened under Bob's decryption key. In proxy re-signature, a proxy can transform a signature computated under Alice's secret key into one that can be verified by Bob's public key. In 2005, Ateniese et al proposed a few new re-encryption schemes and discussed its several potential applications especially in the secure distributed storage[AFGH05]. In 2006, they proposed another few re-signature schemes and also discussed its several potential applications[AH06]. They predicated that re-encryption and re-signature will play an important role in our life. Since then, researchers are sparked to give new lights to this area. Many excellent schemes have been proposed. In this paper, we introduce a new attack- DDos attack against proxy in the proxy re-cryptography. Although this attack can also be implemented against other cryptographic primitives, the danger caused by it in proxy re-cryptography seems more serious. We revisit the current literature, paying attention on their resisting DDos attack ability. We suggest a solution to decline the impact of DDos attacking. Also we give a new efficient re-encryption scheme which can achieve CCA2 secure based on Cramer-Shoup encryption scheme and prove its security. We point out this is the most efficient proxy re-encryption schemes for the proxy which can achieve CCA2 secure in the literature. At last we give our conclusions with hoping researchers give more attention on this attack.
Last updated:  2008-08-13
Weaknesses in HENKOS Stream Cipher
Prasanth Kumar Thandra, S. A. V. Satya Murty, R Balasubramanian
HENKOS is a synchronous stream cipher posted by Marius Oliver Gheorghita to eprint. In this paper we are going to present some weaknesses in the cipher. We first present a chosen IV attack which is very straight forward attack on the cipher. Second we present a group of weak keys.
Last updated:  2009-07-29
On Notions of Security for Deterministic Encryption, and Efficient Constructions without Random Oracles
Alexandra Boldyreva, Serge Fehr, Adam O'Neill
The study of deterministic public-key encryption was initiated by Bellare et al. (CRYPTO~'07), who provided the ``strongest possible" notion of security for this primitive (called PRIV) and constructions in the random oracle (RO) model. We focus on constructing efficient deterministic encryption schemes \emph{without} random oracles. To do so, we propose a slightly weaker notion of security, saying that no partial information about encrypted messages should be leaked as long as each message is a-priori hard-to-guess \emph{given the others} (while PRIV did not have the latter restriction). Nevertheless, we argue that this version seems adequate for certain practical applications. We show equivalence of this definition to single-message and indistinguishability-based ones, which are easier to work with. Then we give general constructions of both chosen-plaintext (CPA) and chosen-ciphertext-attack (CCA) secure deterministic encryption schemes, as well as efficient instantiations of them under standard number-theoretic assumptions. Our constructions build on the recently-introduced framework of Peikert and Waters (STOC '08) for constructing CCA-secure \emph{probabilistic} encryption schemes, extending it to the deterministic-encryption setting and yielding some improvements to their original results as well.
Last updated:  2009-03-27
Flaws in Some Self-Healing Key Distribution Schemes with Revocation
Vanesa Daza, Javier Herranz, German Saez
Dutta and Mukhopadhyay have recently proposed some very efficient self-healing key distribution schemes with revocation. The parameters of these schemes contradict some results (lower bounds) presented by Blundo et al. In this paper different attacks against the schemes of Dutta and Mukhopadhyay are explained: one of them can be easily avoided with a slight modification in the schemes, but the other one is really serious.
Last updated:  2009-06-05
Higher Order Differential Cryptanalysis of Multivariate Hash Functions
Uncategorized
Yiyuan Luo, Xuejia Lai
Show abstract
Uncategorized
In this paper, we analyze the security of multivariate hash functions and conclude that low degree multivariate functions such as MQ-HASH are neither pseudo-random nor unpredictable. And they are also not computation-resistance, which makes MAC forgery easily.
Last updated:  2008-08-11
Time-Area Optimized Public-Key Engines: MQ-Cryptosystems as Replacement for Elliptic Curves?
Andrey Bogdanov, Thomas Eisenbarth, Andy Rupp, Christopher Wolf
In this paper ways to efficiently implement public-key schemes based onMultivariate Quadratic polynomials (MQ-schemes for short) are investigated. In particular, they are claimed to resist quantum computer attacks. It is shown that such schemes can have a much better time-area product than elliptic curve cryptosystems. For instance, an optimised FPGA implementation of amended TTS is estimated to be over 50 times more efficient with respect to this parameter. Moreover, a general framework for implementing small-field MQ-schemes in hardware is proposed which includes a systolic architecture performing Gaussian elimination over composite binary fields.
Last updated:  2008-08-11
Iterative Probabilistic Reconstruction of RC4 Internal States
Jovan Golic, Guglielmo Morgari
It is shown that an improved version of a previously proposed iterative probabilistic algorithm, based on forward and backward probability recursions along a short keystream segment, is capable of reconstructing the RC4 internal states from a relatively small number of known initial permutation entries. Given a modulus $N$, it is argued that about $N/3$ and $N/10$ known entries are sufficient for success, for consecutive and specially generated entries, respectively. The complexities of the corresponding guess-and-determine attacks are analyzed and, e.g., for $N=256$, the data and time complexities are (conservatively) estimated to be around $D \approx 2^{41}$, $C \approx 2^{689}$ and $D \approx 2^{211}$, $C \approx 2^{262}$, for the two types of guessed entries considered, respectively.
Last updated:  2008-08-11
Information Leakage in Optimal Anonymized and Diversified Data
Uncategorized
Chengfang Fang, Ee-Chien Chang
Show abstract
Uncategorized
To reconcile the demand of information dissemination and preservation of privacy, a popular approach generalizes the attribute values in the dataset, for example by dropping the last digit of the postal code, so that the published dataset meets certain privacy requirements, like the notions of k-anonymity and l-diversity. On the other hand, the published dataset should remain useful and not over generalized. Hence it is desire to disseminate a database with high "usefulness", measured by a utility function. This leads to a generic framework whereby the optimal dataset (w.r.t. the utility function) among all the generalized datasets that meet certain privacy requirements, is chosen to be disseminated. In this paper, we observe that, the fact that a generalized dataset is optimal may leak information about the original. Thus, an adversary who is aware of how the dataset is generalized may able to derive more information than what the privacy requirements constrained. This observation challenges the widely adopted approach that treats the generalization process as an optimization problem. We illustrate the observation by giving counter-examples in the context of k-anonymity and l-diversity.
Last updated:  2008-11-03
Remote Integrity Check with Dishonest Storage Server
Ee-Chien Chang, Jia Xu
We are interested in this problem: a verifier, with a small and reliable storage, wants to periodically check whether a remote server is keeping a large file $\mathbf{x}$. A dishonest server, by adapting the challenges and responses, tries to discard partial information of $\mathbf{x}$ and yet evades detection. Besides the security requirements, there are considerations on communication, storage size and computation time. Juels et al. \cite{Pors} gave a security model for {\em Proof of Retrievability} ({\POR}) system. The model imposes a requirement that the original ${\bf x}$ can be recovered from multiple challenges-responses. Such requirement is not necessary in our problem. Hence, we propose an alternative security model for {\em Remote Integrity Check} ({\RIC}). We study a few schemes and analyze their efficiency and security. In particular, we prove the security of a proposed scheme {\simplePIR}. This scheme can be deployed as a {\POR} system and it also serves as an example of an effective {\POR} system whose ``extraction'' is not verifiable. We also propose a combination of the RSA-based scheme by Filho et al. \cite{DDPs} and the ECC-based authenticator by Naor et al. \cite{complex_memcheck}, which achieves good asymptotic performance. This scheme is not a {\POR} system and seems to be a secure {\RIC}. In-so-far, all schemes that have been proven secure can also be adopted as {\POR} systems. This brings out the question of whether there are fundamental differences between the two models. To highlight the differences, we introduce a notion, {\em trap-door compression}, that captures a property on compressibility.
Last updated:  2008-08-11
An Efficient Authenticated Key Exchange Protocol with a Tight Security Reduction
Jooyoung Lee, Choon Sik Park
In this paper, we present a new authenticated key exchange(AKE) protocol, called NETS, and prove its security in the extended Canetti-Krawczyk model under the random oracle assumption and the gap Diffie-Hellman(GDH) assumption. Our protocol enjoys a simple and tight security reduction compared to those of HMQV and CMQV without using the Forking Lemma. Each session of the NETS protocol requires only three exponentiations per party, which is comparable to the efficiency of MQV, HMQV and CMQV.
Last updated:  2008-08-11
Authenticated Key Exchange Secure under the Computational Diffie-Hellman Assumption
Jooyoung Lee, Je Hong Park
In this paper, we present a new authenticated key exchange(AKE) protocol and prove its security under the random oracle assumption and the computational Diffie-Hellman(CDH) assumption. In the extended Canetti-Krawczyk model, there has been no known AKE protocol based on the CDH assumption. Our protocol, called NAXOS+, is obtained by slightly modifying the NAXOS protocol proposed by LaMacchia, Lauter and Mityagin. We establish a formal security proof of NAXOS+ in the extended Canetti-Krawczyk model using as a main tool the trapdoor test presented by Cash, Kiltz and Shoup.
Last updated:  2008-12-05
Efficient RFID authentication protocols based on pseudorandom sequence generators
Uncategorized
Jooyoung Lee, Yongjin Yeom
Show abstract
Uncategorized
In this paper, we introduce a new class of PRSGs, called partitioned pseudorandom sequence generators(PPRSGs), and propose an RFID authentication protocol using a PPRSG, called S-protocol. Since most existing stream ciphers can be regarded as secure PPRSGs, and stream ciphers outperform other types of symmetric key primitives such as block ciphers and hash functions in terms of power, performance and gate size, S-protocol is expected to be suitable for use in highly constrained environments such as RFID systems. We present a formal proof that guarantees resistance of S-protocol to desynchronization and tag-impersonation attacks. Speci¯cally, we reduce the availability of S-protocol to pseudorandomness of the underlying PPRSG, and the security of the protocol to the availability. Finally, we give a modi¯cation of S-protocol, called S¤-protocol, that provides mutual authentication of tag and reader.
Last updated:  2008-08-11
Cryptanalysis of Li et al.'s Identity-Based Threshold Signcryption Scheme
S. Sharmila Deva Selvi, S. Sree Vivek, Neha Jain, Pandu Rangan Chandrasekaran
Signcryption is a cryptographic primitive that aims at providing confidentiality and authentication simultaneously. Recently in May 2008, a scheme for identity based threshold signcryption was proposed by Fagen Li and Yong Yu. They have proved the confidentiality of their scheme and have also claimed the unforgeability without providing satisfactory proof. In this paper, we show that in their signcryption scheme the secret key of the sender is exposed(total break) to the clerk during sincryption and hence insecure in the presence of malicious clerks. Further, we propose a corrected version of the scheme and formally prove its security under the existing security model for signcryption.
Last updated:  2009-04-16
An Efficient Identity-Based Signcryption Scheme for Multiple Receivers
S. Sharmila Deva Selvi, S. Sree Vivek, Rahul Srinivasan, Pandu Rangan Chandrasekaran
This paper puts forward a new efficient construction for Multi-Receiver Signcryption in the Identity-based setting. We consider a scenario where a user wants to securely send a message to a dynamically changing subset of the receivers in such a way that non-members of the of this subset cannot learn the message. The obvious solution is to transmit an individually signcrypted message to every member of the subset. This requires a very long transmission (the number of receivers times the length of the message) and high computation cost. Another simple solution is to provide every possible subset of receivers with a key. This requires every user to store a huge number of keys. In this case, the storage efficiency is compromised. The goal of this paper is to provide solutions which are efficient in all three measures i.e. transmission length, storage of keys and computation at both ends. We propose a new scheme that achieve both confidentiality and authenticity simultaneously in this setting and is the most efficient scheme to date, in the parameters described above. It breaks the barrier of ciphertext length of linear order in the number of receivers, and achieves constant sized ciphertext, independent of the size of the receiver set. This is the first Multi-receiver Signcryption scheme to do so. We support the scheme with security proofs under a precisely defined formal security model
Last updated:  2011-12-05
On construction of signature schemes based on birational permutations over noncommutative rings
Yasufumi Hashimoto, Kouichi Sakurai
In the present paper, we give a noncommutative version of Shamir's birational permutation signature scheme proposed in Crypto'93 in terms of square matrices. The original idea to construct the multivariate quadratic signature is to hide a quadratic triangular system using two secret linear transformations. However, the weakness of the triangular system remains even after taking two transformations, and actually Coppersmith et al. broke it linear algebraically. In the non-commutative case, such linear algebraic weakness does not appear. We also give several examples of noncommutative rings to use in our scheme, the ring consisting of all square matrices, the quaternion ring and a subring of three-by-three matrix ring generated by the symmetric group of degree three. Note that the advantage of Shamir's original scheme is its efficiency. In our scheme, the efficiency is preserved enough.
Last updated:  2008-08-11
High Performance Implementation of a Public Key Block Cipher - MQQ, for FPGA Platforms
Mohamed El-Hadedy, Danilo Gligoroski, Svein J. Knapskog
We have implemented in FPGA recently published class of public key algorithms -- MQQ, that are based on quasigroup string transformations. Our implementation achieves decryption throughput of 399 Mbps on an Xilinx Virtex-5 FPGA that is running on 249.4 MHz. The encryption throughput of our implementation achieves 44.27 Gbps on four Xilinx Virtex-5 chips that are running on 276.7 MHz. Compared to RSA implementation on the same FPGA platform this implementation of MQQ is 10,000 times faster in decryption, and is more than 17,000 times faster in encryption.
Last updated:  2009-05-16
An improvement of discrete Tardos fingerprinting codes
Uncategorized
Koji Nuida, Satoshi Fujitsu, Manabu Hagiwara, Takashi Kitagawa, Hajime Watanabe, Kazuto Ogawa, Hideki Imai
Show abstract
Uncategorized
It has been known that the code lengths of Tardos's collusion-secure fingerprinting codes are of theoretically minimal order with respect to the number of adversarial users (pirates). However, the code lengths can be further reduced, as some preceding studies on Tardos's codes already revealed. In this article we improve a recent discrete variant of Tardos's codes, and give a security proof of our codes under an assumption weaker than the original assumption (Marking Assumption). Our analysis shows that our codes have significantly shorter lengths than Tardos's codes. For example, in a practical setting, the code lengths of our codes are about 3.01%, 4.28%, and 4.81% of Tardos's codes if the numbers of pirates are 2, 4, and 6, respectively.
Last updated:  2008-08-11
Modified Huang-Wang's Convertible Nominative Signature Scheme
Wei Zhao, Dingfeng Ye
At ACISP 2004, Huang and Wang first introduced the concept of convertible nominative signatures and also proposed a concrete scheme. However, it was pointed out by many works that Huang-Wang's scheme is in fact not a nominative signature. In this paper, we first present a security model for convertible nominative signatures. The properties of Unforgeability, Invisibility, Non-impersonation and Non-repudiation in the setting of convertible nominative signatures are defined formally. Then we modify Huang-Wang's scheme into a secure one. Formal proofs are provided to show that the modified Huang-Wang's scheme satisfies all the security properties under some conventional assumptions in the random oracle model.
Last updated:  2008-08-03
New attacks on ISO key establishment protocols
Anish Mathuria, G. Sriram
Cheng and Comley demonstrated type flaw attacks against the key establishment mechanism 12 standardized in ISO/IEC 11770-2:1996. They also proposed enhancements to fix the security flaws in the mechanism. We show that the enhanced version proposed by Cheng and Comley is still vulnerable to type flaw attacks. As well we show that the key establishment mechanism 13 in the above standard is vulnerable to a type flaw attack.
Last updated:  2008-08-03
Public Key Cryptography from Different Assumptions
Boaz Barak, Avi Wigderson
We construct a new public key encryption based on two assumptions: 1) One can obtain a pseudorandom generator with small locality by connecting the outputs to the inputs using any sufficiently good unbalanced expander. 2) It is hard to distinguish between a random graph that is such an expander and a random graph where a (planted) random logarithmic-sized subset S of the outputs is connected to fewer than |S| inputs. The validity and strength of the assumptions raise interesting new algorithmic and pseudorandomness questions, and we explore their relation to the current state-of-art.
Last updated:  2008-10-07
Analyzing the Galbraith-Lin-Scott Point Multiplication Method for Elliptic Curves over Binary Fields
Darrel Hankerson, Koray Karabina, Alfred Menezes
Galbraith, Lin and Scott recently constructed efficiently-computable endomorphisms for a large family of elliptic curves defined over F_{q^2} and showed, in the case where q is prime, that the Gallant-Lambert-Vanstone point multiplication method for these curves is significantly faster than point multiplication for general elliptic curves over prime fields. In this paper, we investigate the potential benefits of using Galbraith-Lin-Scott elliptic curves in the case where q is a power of 2. The analysis differs from the q prime case because of several factors, including the availability of the point halving strategy for elliptic curves over binary fields. Our analysis and implementations show that Galbraith-Lin-Scott offers significant acceleration for curves over binary fields, in both doubling- and halving-based approaches. Experimentally, the acceleration surpasses that reported for prime fields (for the platform in common), a somewhat counterintuitive result given the relative costs of point addition and doubling in each case.
Last updated:  2008-12-01
Explicit hard instances of the shortest vector problem
Johannes Buchmann, Richard Lindner, Markus Rückert, Michael Schneider
Building upon a famous result due to Ajtai, we propose a sequence of lattice bases with growing dimension, which can be expected to be hard instances of the shortest vector problem (SVP) and which can therefore be used to benchmark lattice reduction algorithms. The SVP is the basis of security for potentially post-quantum cryptosystems. We use our sequence of lattice bases to create a challenge, which may be helpful in determining appropriate parameters for these schemes.
Last updated:  2008-08-03
Efficient Key Distribution Schemes for Large Scale Mobile Computing Applications
Mahalingam Ramkumar
In emerging networks consisting of large-scale deployments of mobile devices, efficient security mechanisms are required to facilitate cryptographic authentication. While computation and bandwidth overheads are expensive for mobile devices, the cost of storage resources continue to fall at a rapid rate. We propose a simple novel key predistribution scheme, \textit{key subset and symmetric certificates} (KSSC) which can take good advantage of inexpensive storage resources, and has many compelling advantages over other approaches for facilitating ad hoc establishment of pairwise secrets in mobile computing environments. We argue that a combination of KSSC with a variant of an elegant KDS proposed by Leighton and Micali is an appealing choice for securing large scale deployments of mobile devices.
Last updated:  2008-08-03
A Secure Remote User Authentication Scheme with Smart Cards
Manoj Kumar
Remote user authentication scheme is one of the simplest and the most convenient authentication mechanisms to deal with secret data over insecure networks. These types of schemes are applicable to the areas such as computer networks, wireless networks, remote login systems, operation systems and database management systems.The goal of a remote user authentication scheme is to identify a valid card holder as having the rights and privileges indicated by the issuer of the card. In recent years, so many remote user authentication schemes have been proposed to authenticate a legitimate user, but none of them can solve all possible problems and withstand all possible attacks. This paper presents a secure remote user authentication scheme with smart cards. The proposed scheme provides the essential security requirements and achieves particular attributes.
Last updated:  2009-10-23
Chosen ciphertext secure public key encryption under DDH assumption with short ciphertext
Uncategorized
Xianhui Lu, Xuejia Lai, Dake He
Uncategorized
An efficient variant of the ElGamal public key encryption scheme is proposed which is provably secure against adaptive chosen ciphertext attacks(IND-CCA2) under the decisional Diffie-Hellman(DDH) assumption. Compared to the previously most efficient scheme under DDH assumption by Kurosawa and Desmedt [Crypto 2004] it has one group element shorter ciphertexts, 50\% shorter secret keys, 25\% shorter public keys and it is 28.6\% more efficient in terms of encryption speed, 33.3\% more efficient in terms of decryption speed. A new security proof logic is used, which shows directly that the decryption oracle will not help the adversary in the IND-CCA2 game. Compared to the previous security proof, the decryption simulation is not needed in the new logic. This makes the security proof simple and easy to understand.
Last updated:  2008-08-03
SMS4 Encryption Algorithm for Wireless Networks
Whitfield Diffie, George Ledin (translators)
SMS4 is a Chinese block cipher standard, mandated for use in protecting wireless net- works, and issued in January 2006. The input, output, and key of SMS4 are each 128 bits. The algorithm has 32 rounds, each of which modifies one of the four 32-bit words that make up the block by xoring it with a keyed function of the other three words. Encryption and decryption have the same structure except that the round key schedule for decryption is the reverse of the round key schedule for encryption.
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.