Advances in Cryptology — ASIACRYPT 2000

In 1980 Hellman introduced a general technique for breaking arbitrary block ciphers with N possible keys in time T and memory M related by the tradeoff curve TM2 = N2 for 1 ≤ T ≤ N. Recently, Babbage and Golic pointed out that a different TM = N tradeoff attack for 1 ≤ T ≤ D is applicable to stream ciphers, where D is the amount of output data available to the attacker. In this paper we show that a combination of the two approaches has an improved time/memory/data tradeoff for stream ciphers of the form TM2D2 = N2 for any D2 ≤ T ≤ N. In addition, we show that stream ciphers with low sampling resistance have tradeoff attacks with fewer table lookups and a wider choice of parameters.

At Asiacrypt’ 99, Sun, Yang and Laih proposed three RSA variants with short secret exponent that resisted all known attacks, including the recent Boneh-Durfee attack from Eurocrypt ’99 that improved Wiener’s attack on RSA with short secret exponent. The resistance comes from the use of unbalanced primes p and q. In this paper, we extend the Boneh-Durfee attack to break two out of the three proposed variants. While the Boneh-Durfee attack was based on Coppersmith’s lattice-based technique for finding small roots to bivariate modular polynomial equations, our attack is based on its generalization to trivariate modular polynomial equations. The attack is heuristic but works well in practice, as the Boneh-Durfee attack. In particular, we were able to break in a few minutes the numerical examples proposed by Sun, Yang and Laih. The results illustrate once again the fact that one should be very cautious when using short secret exponent with RSA.

We present an attack on plain ElGamal and plain RSA encryption. The attack shows that without proper preprocessing of the plaintexts, both El Gamal and RSA encryption are fundamentally insecure. Namely, when one uses these systems to encrypt a (short) secret key of a symmetric cipher it is often possible to recover the secret key from the ciphertext. Our results demonstrate that preprocessing messages prior to encryption is an essential part of bothsy stems.

In 1985 Fell and Diffie proposed constructing trapdoor functions with multivariate equations [11]. They used several sequentially solved stages that combine into a triangular system we call T. In the present paper, we study a more general family of TPM (for “Triangle Plus Minus”) schemes: a triangular construction mixed with some u random polynomials and with some r of the beginning equations removed. We go beyond all previous attacks proposed on such cryptosystems using a low degree component of the inverse function. The cryptanalysis of TPM is reduced to a simple linear algebra problem called MinRank(r): Find a linear combination of given matrices that has a small rank r. We introduce a new attack for MinRank called ‘Kernel Attack’ that works for qr small. We explain that TPM schemes can be used in encryption only if qr is small and therefore they are not secure.As an application, we showed that the TTM cryptosystem proposed by T.T. Moh at CrypTec’99 [15],[16] reduces to MinRank(2). Thus, though the cleartext size is 512 bits, we break it in O(252). The particular TTM of [15],[16] can be broken in O(228) due additional weaknesses, and we needed only few minutes to solve the challenge TTM 2.1. from the website of the TTM selling company, US Data Security.We also studied TPM in signature, possible only if qu small. It is equally insecure: the ‘Degeneracy Attack’ we introduce runs in qu· polynomial.

Batch verification can provide large computational savings when several signatures, or other constructs, are verified together. Several batch verification algorithms have been published in recent years, in particular for both DSA-type and RSA signatures. We describe new attacks on several of these published schemes. A general weakness is explained which applies to almost all known batch verifiers for discrete logarithm based signature schemes. It is shown how this weakness can be eliminated given extra properties about the underlying group structure. A new general batch verifier for exponentiation in any cyclic group is also described as well as a batch verifier for modified RSA signatures.

The past twenty years have seen cryptography move from arcane to commonplace, from difficult to easy, from expensive to cheap. Many influences are at work. These include:the professionalization of cryptographers, in which the IACR has played a significant role; the creation of textbooks and of courses; the steady growth of computational power delivered by the operation of Mooreś Law; the algorithmic advances made by cryptographic researchers and engineers; the rise of e-commerce and wireless infrastructures which have a seemingly endless appetite for cryptographic services; the entry of many young people into the field; and the easing of government export controls. We envisage a near future where cryptographic operations will be as pervasive, cheap and unremarkable as IP protocol operations have become today.Some things about this future are already clear. Cryptographic operations will disappear into the infrastructure. The complexities of cryptography and of cryptographic key management will be hidden from users. New sorts of protocols will become practical. New sorts of businesses will be possible. We will describe several such protocols and businesses. Other important aspects of this future are less clear, such as the social, economic, and political implications. We will hazard guesses at these and other impacts of cryptography everywhere.

Assuming a cryptographically strong cyclic group G of prime order q and a random hash function H, we show that ElGamal encryption with an added Schnorr signature is secure against the adaptive chosen ciphertext attack, in which an attacker can freely use a decryption oracle except for the target ciphertext. We also prove security against the novel one-more-decyption attack. Our security proofs are in a new model, corresponding to a combination of two previously introduced models, the Random Oracle model and the Generic model. The security extends to the distributed threshold version of the scheme. Moreover, we propose a very practical scheme for private information retrieval that is based on blind decryption of ElGamal ciphertexts.

A common practice for signing with RSA is to first apply a hash function or a redundancy function to the message, add some padding and exponentiate the resulting padded message using the decryption exponent. This is the basis of several existing standards.In this paper we show how to build a secure padding scheme for signing arbitrarily long messages with a secure padding scheme for fixed-size messages. This focuses more sharply the question of finding a secure encoding for RSA signatures, by showing that the difficulty is not in handling messages of arbitrary length, but rather in finding a secure redundancy function for short messages, which remains an open problem.

We consider a problem which was stated in a request for comments made by NIST in the FIPS97 document. The question is the following: Can we have a digital signature public key infrastructure where the public (signature verification) keys cannot be abused for performing encryption? This may be applicable in the context of, say, exportable/escrow cryptography. The basic dilemma is that on the one hand, (1) to avoid framing by potentially misbehaving authorities we do not want them to ever learn the “signing keys” (e.g., Japan at some point declared a policy where signature keys may be required to be escrowed), and on the other hand (2) if we allow separate inaccessible public signature verification keys, these keys (based on trapdoor functions) can be used as “shadow public-keys,” and hence can be used to encrypt data in an unrecoverable manner. Any solution within the “trapdoor function” paradigm of Diffie and Hellman does not seem to lead to a solution which will simultaneously satisfy (1) and (2).The cryptographic community so far has paid very limited attention to the problem. In this work, we present the basic issues and suggest a possible methodology and the first scheme that may be used to solve much of the problem. Our solution takes the following steps: (1) it develops the notion of a nested trapdoor which our methodology is based on, (2) we implement this notion based on a novel composite “double-decker” exponentiation technique which embeds the RSA problem within it (the technique may be of independent interest), (3) we analyze carefully what can be and what cannot be achieved regarding the open problem by NIST (our analysis is balanced and points out possibilities as well as impossibilities), and (4) we give a secure signature scheme within a public key infrastructure, wherein the published public key can be used for signature verification only (if it is used for encryptions, then the authorities can decrypt the data). The security of our scheme is based on RSA. We then argue how the scheme’s key cannot be abused (statically) based on an additional assumption. We also show that further leakages and subliminal leakages when the scheme is in (dynamic) use are not added substantially beyond what is always possible by a simple adversary; we call this notion competitive leakage. We also demonstrate such simple leaking adversary.We hope that our initial work will stimulate further thoughts on the non-trivial issue of signature-only signatures.

We improve the Bellare-Miner (Crypto’ 99) construction of signature schemes with forward security in the random oracle model. Our scheme has significantly shorter keys and is, therefore, more practical. By using a direct proof technique not used for forward-secure schemes before, we are able to provide better security bounds for the original construction as well as for our scheme.Bellare and Miner also presented a method for constructing such schemes without the use of the random oracle. We conclude by proposing an improvement to their method and an additional, new method for accomplishing this.

A potentially serious problem with current digital signature schemes is that their underlying hard problems from number theory may be solved by an innovative technique or a new generation of computing devices such as quantum computers. Therefore while these signature schemes represent an efficient solution to the short term integrity (unforgeability and non-repudiation) of digital data, they provide no confidence on the long term (say of 20 years) integrity of data signed by these schemes. In this work, we focus on signature schemes whose security does not rely on any unproven assumption. More specifically, we establish a model for unconditionally secure digital signatures in a group, and demonstrate practical schemes in that model. An added advantage of the schemes is that they allow unlimited transfer of signatures without compromising the security of the schemes. Our scheme represents the first unconditionally secure signature that admits provably secure transfer of signatures.

Since the introduction of secure multi-party computation, all proposed protocols that provide security against cheating players suffer from very high communication complexities. The most efficient unconditionally secure protocols among n players, tolerating cheating by up to t < n/3 of them, require communicating O(n6) field elements for each multiplication of two elements, even if only one player cheats. In this paper, we propose a perfectly secure multi-party protocol which requires communicating O(n3) field elements per multiplication. In this protocol, the number of invocations of the broadcast primitive is independent of the size of the circuit to be computed. The proposed techniques are generic and apply to other protocols for robust distributed computations.Furthermore, we show that a sub-protocol proposed in [GRR98] for improving the efficiency of unconditionally secure multi-party computation is insecure.

We introduce a novel approach to general secure multiparty computation that avoids the intensive use of verifiable secret sharing characterizing nearly all previous protocols in the literature. Instead, our scheme involves manipulation of ciphertexts for which the underlying private key is shared by participants in the computation. The benefits of this protocol include a high degree of conceptual and structural simplicity, low message complexity, and substantial flexibility with respect to input and output value formats. We refer to this new approach as mix and match. While the atomic operations in mix and match are logical operations, rather than full field operations as in previous approaches, the techniques we introduce are nonetheless highly practical for computations involving intensive bitwise manipulation. One application for which mix and match is particularly well suited is that of sealed-bid auctions. Thus, as another contribution in this paper, we present a practical, mix-and-match-based auction protocol that is fully private and non-interactive and may be readily adapted to a wide range of auction strategies.

This paper presents a secure and flexible Mix-net that has the following properties; it efficiently handles long plaintexts that exceed the modulus size of underlying public-key encryption as well as very short ones (length-flexible), input ciphertext length is not impacted by the number of mix-servers (length-invariant), and its security in terms of anonymity is proven in a formal way (provably secure). One can also add robustness i.e. it outputs correct results in the presence of corrupt servers. The security is proved in the random oracle model by showing a reduction from breaking the anonymity of our Mix-net to breaking a sort of indistinguishability of the underlying symmetric encryption scheme or solving the Decision Diffie-Hellman problem.

AMIX net takes a list of ciphertexts (c₁,... , c_N) and outputs a permuted list of the plaintexts (m₁,... ,m_N) without revealing the relationship between (c₁,... , c_N) and (m₁,... ,m_N). This paper shows that the Jakobsson’s flash MIX of PODC’99, which was believed to be the most efficient robust MIX net, is broken. The first MIX server can prevent computing the correct output with probability 1 in our attack. We also present a countermeasure for our attack.

This work describes distributed protocols for oblivious transfer, in which the role of the sender is divided between several servers, and a chooser (receiver) must contact a threshold of these servers in order to run the oblivious transfer protocol. These distributed oblivious transfer protocols provide information theoretic security, and do not require the parties to compute exponentiations or any other kind of public key operations. Consequently, the protocols are very efficient computationally.

This paper describes improved methods for XTR key representation and parameter generation (cf. [4]). If the field characteristic is properly chosen, the size of the XTR public key for signature applications can be reduced by a factor of three at the cost of a small one time computation for the recipient of the key. Furthermore, the parameter set-up for an XTR system can be simplified because the trace of a proper subgroup generator can, with very high probability, be computed directly, thus avoiding the probabilistic approach from [4]. These non-trivial extensions further enhance the practical potential of XTR.

In this work we investigate the dificulty of the discrete logarithm problem in class groups of imaginary quadratic orders.In particular, we discuss several strategies to compute discrete logarithms in those class groups.Based on heuristic reasoning, we give advice for selecting the cryptographic parameter, i.e. the discriminant, such that cryptosystems based on class groups of imaginary quadratic orders would offer a similar security as commonly used cryptosystems.

The paper shows that some of elliptic curves over finite fields of characteristic three of composite degree are attacked by a more effective algorithm than Pollard’s ρ method. For such an elliptic curve E, we construct a C_ab curve D on its Weil restriction in order to reduce the discrete logarithm problem on E to that on D. And we show that the genus of D is small enough so that D is attacked by a modified form of Gaudry’s variant for a suitable E. We also see such a weak elliptic curve is easily constructed.

Construction of secure hyperelliptic curves is of most important yet most dificult problem in design of cryptosystems based on the discrete logarithm problems on hyperelliptic curves. Presently the only accessible approach is to use CM curves. However, to find models of the CM curves is nontrivial. The popular approach uses theta functions to derive a projective embedding of the Jacobian varieties, which needs to calculate the theta functions to very high precision. As we show in this paper, it costs computation time of an exponential function in the discriminant of the CM field. This paper presents new algorithms to find explicit models of hyperelliptic curves with CM. Algorithms for CM test of Jacobian varieties of algebraic curves and to lift from small finite fields both the models and the invariants of CM curves are presented. We also show that the proposed algorithm for invariants lifting has complexity of a polynomial time in the discriminant of the CM field.

In this paper we introduce a structure iterated by the rule A of Skipjack and show that this structure is provably resistant against differential or linear attacks. It is the main result of this paper that the upper bound of r-round (r ≥ 15) differential(or linear hull) probabilities are bounded by p4 if the maximum differential (or linear hull) probability of a round function is p, and an impossible differential of this structure does not exist if r ≥ 16. Application of this structure which can be seen as a generalized Feistel structure in a way to block cipher designs brings out the provable security against differential and linear attacks with some upper bounds of probabilities. We also propose an interesting conjecture.

Block ciphers are usually basedon one top-level scheme into which we plug “roundf unctions”. To analyze security, it is important to study the intrinsic security provided by the top-level scheme from the viewpoint of randomness: given a block cipher in which we replaced the lower-level schemes by idealized oracles, we measure the security (in terms of best advantage for a distinguisher) depending on the number of rounds and the number of chosen plaintexts. We then extrapolate a sufficient number of secure rounds given the regular bounds provided by decorrelation theory.This approach allows the comparison of several generalizations of the Feistel schemes andot hers. In particular, we compare the randomness provided by the schemes used by the AES candidates.In addition we provide a general paradigm for analyzing the security provided by the interaction between the different levels of the block cipher structure.

This paper describes some attacks on word-oriented stream ciphers that use a linear feedback shift register (LFSR) and a non-linear filter. These attacks rely on exploiting linear relationships corresponding to multiples of the connection polynomial that define the LFSR.

We investigate the following approach to symmetric encryption: first encode the message via some keyless transform, and then encipher the encoded message, meaning apply a permutation F_K based on a shared key K. We provide conditions on the encoding functions and the cipher which ensure that the resulting encryption scheme meets strong privacy (eg. semantic security) and/or authenticity goals. The encoding can either be implemented in a simple way (eg. prepend a counter and append a checksum) or viewed as modeling existing redundancy or entropy already present in the messages, whereby encode-then-encipher encryption provides a way to exploit structured message spaces to achieve compact ciphertexts.

We generalize and improve the security and efficiency ofthe verifiable encryption scheme of Asokan et al., such that it can rely on more general assumptions, and can be proven secure without assuming random oracles. We extend our basic protocol to a new primitive called verifiable group encryption. We show how our protocols can be applied to construct group signatures, identity escrow, and signature sharing schemes from a wide range of signature, identification, and encryption schemes already in use. In particular, we achieve perfect separability for all these applications, i.e., all participants can choose their signature and encryption schemes and the keys thereofi ndependent of each other, even without having these applications in mind.

We introduce an efficient method for performing computation on encrypted data, allowing addition of ElGamal encrypted plaintexts. We demonstrate a solution that is robust and leaks no information to a minority of colluding cheaters. Our focus is on a three-player solution, but we also consider generalization to a larger number of players. The amount of work is exponential in the number of players, but reasonable for small sets.

A t out of n threshold scheme is such that shares are distributed to n participants so that any set of t participants can compute the secret, whereas any set of less than t participants gain no information about the secret. In [4], Desmedt and Frankel introduced a threshold scheme that can be used with any finite Abelian group. Hence it can be used to provide threshold RSA. In this scheme, the size of the share is on the order n times the size of the secret. Further, due to a complicated algebraic setting, and the large shares, this schemes requires a “large” amount of computations. Recent work have addressed how to reduce the resource requirements. Within this paper we provide improved methods and demonstrate the computational requirements of the Desmedt- Frankel scheme using our method is, in many cases, better than other existing threshold RSA signature schemes.

In a recent Stanford Law Review article, Ayres and Bulow [1] propose a radical anonymity-based solution to disrupt the “market” for monetary influence in political campaigns. To realize their proposal, we propose new cryptographic protocols for commital deniable proofs and deniable payment schemes.“[T]here is little reason to doubt that sometimes large contributions will work actual corruption of our political system, and no reason to question the existence of a corresponding suspicion among voters.”- U.S. Supreme Court Justice David Souter, Nixon v. Shrink Missouri Government PAC, Jan 24, 2000.“[Spiritually] lower than this is one who gives to the poor in a way that the giver does not know to whom he is giving and the poor person does not know who he took from. Lower than this is where the giver knows who he is giving to and the poor does not know who he is receiving from. Lower than this is where the poor knows who he is receiving from but the giver does not.” - Maimonides, Laws of Gifts to the Poor 10:7–14, 12th Century.

Naor and Pinkas introduced metering schemes at Eurocrypt ’98 in order to decide on advertisement fees for web servers. In the schemes, any server should be able to construct a proof to be sent to an audit agency if and only if it has been visited by at least a certain number, say k, of clients. This paper first shows an attack for their schemes such that only two malicious clients can prevent a server from computing a correct proof. We next present provably secure metering schemes. Finally, an efficient robust secret sharing scheme is derived from our metering scheme.

We will describe the outline of the cryptographic technology evaluation project in Japan and those present conditions. The purpose of this project is that the cyptographic technology which the Japanese Government uses is evaluated and listed. Selected cryptographic technology will be used in the information security system which the Japanese Government will use in the future.

Fingerprinting schemes support copyright protection by enabling the merchant of a data item to identifythe original buyer of a redistributed copy. In asymmetric schemes, the merchant can also convince an arbiter of this fact. Anonymous fingerprinting schemes allow buyers to purchase digital items anonymously; however, identification is possible if theyre distribute the data item.In this paper, we present an equallyefficient anonymous fingerprinting scheme with direct non-repudiation. The main technique we use, delayed verifiable encryption, is related to coin tracing in escrowed cash systems. However, there are technical differences, mainlyt to provide an unforgeable link to license conditions.

Fingerprinting schemes enable a merchant to identify the buyer of an illegally distributed digital good by providing each buyer with a slightly different version. Asymmetric fingerprinting schemes further prevent the merchant from framing a buyer by making the fingerprinted version known to the buyer only. In addition, an anonymous fingerprinting scheme allows the buyer to purchase goods without revealing her identity to the merchant. However, as soon as the merchant finds a sold version that has been (illegally) distributed, he is able to retrieve a buyer’s identity and take her to court. This paper proposes a new and more efficient anonymous fingerprinting scheme that uses group signature schemes as a building block. A byproduct of independent interest is an asymmetric fingerprinting scheme that allows so-called two-party trials, which is unmet so far.

We introduce weaker models for non-interactive zero knowledge, in which the dealer is not restricted to deal a truly random string and may also have access to the input to the protocol (i.e. the statement to prove). We show in these models a non-interactive statistical zero-knowledge proof for every language that has (interactive) statistical zero-knowledge proof, and a computational zero-knowledge proof for every language in NP. We also show how to change the latter proof system to fit the model of non-interactive computational zero-knowledge with preprocessingto improve existing results in term of the number of bit commitments that are required for the protocol to work.

In this paper, we investigate the gap between auxiliary-input zero-knowledge (AIZK) and blackbox-simulation zero-knowledge (BSZK). It is an interestingop en problem whether or not there exists a protocol which achieves AIZK, but not BSZK. We show that the existence of such a protocol is closely related to the existence of secure code obfuscators. A code obfuscator is used to convert a code into an equivalent one that is difficult to reverse-engineer. This paper provides security definitions of code obfuscation. By their definitions, it is easy to see that the existence of the gap implies the existence of a cheating verifier such that it is impossible to obfuscate any code of it. Intuitively, this means that it is possible to reverse-engineer any code of such a cheating verifier. Furthermore, we consider the actual behavior of such a cheating verifier. In order to do so, we focus on two special cases in which the gap exists: (1) there exists a constant round public-coin AIZK interactive argument for a language outside of BPP. (2) there exists a 3-round secret-coinAIZK interactive argument for a language outside of BPP. In the former case, we show that it is impossible to securely obfuscate a code of a cheating verifier behaving as a pseudorandom function. A similar result is shown also in the latter case. Our results imply that any construction of constant round public-coin or 3-round secret-coin AIZK arguments for non-trivial languages essentially requires a computational assumption with a reverse-engineering property.

A discrete-logarithm algorithm is called generic if it does not exploit the specific representation of the cyclic group for which it is supposed to compute discrete logarithms. Such algorithms include the well-known Baby-Step-Giant-Step procedure as well as the PohligHellman algorithm. In particular, these algorithms match a lower bound of Nachaev showing that generic discrete-log algorithms require exponentially many group operations. Building on this lower bound, Shoup and subsequently Schnorr and Jakobsson proved other discrete-log-based protocols to be intractable in the generic model. Here, we discuss pitfalls when applying the generic model to other schemes than the discrete-log problem and when interpreting such lower bounds as security proofs for these schemes.

We establish, for the first time, an explicit and simple lower bound on the nonlinearity N_f of a Boolean function f of n variables satisfying the avalanche criterion of degree p, namely, N_f≥ 2n-1 . 2n-1-1/2p. We also show that the lower bound is tight, and identify all the functions whose nonlinearity attains the lower bound. As a further contribution of this paper, we prove that except for very few cases, the sum of the degree of avalanche and the order of correlation immunity of a Boolean function of n variables is atmost n-2. These new results further highlight the significance of the fact that while avalanche property is in harmony with nonlinearity, it goes against correlation immunity.

This paper analyzes the security of a hash mode recently proposed by Yi and Lam. Given a block cipher with m-bit block size and 2m-bit key, they build a hash function with 2m-bit outputs that can hash messages as fast as the underlying block cipher can encrypt. This construction was conjectured to have ideal security, i.e., to resist all collision attacks faster than brute force. We disprove this conjecture by presenting a collision attack that is substantially faster than brute force and which could even be considered practical for typical security parameters.

Since Power Analysis on smart-cards was introduced by Paul Kocher [KJJ98], the validity of the model used for smart-cards has not been given much attention. In this paper, we first describe and analyze some different possible models. Then we apply these models to real components and clearly define what can be detected by power analysis (simple, differential, code reverse engineering...). We also study, from a statistical point of view, some new ideas to exploit these models to attack the card by power analysis. Finally we apply these ideas to set up real attacks on cryptographic algorithms or enhance existing ones.

We investigate several alternate characterizations of pseudorandom functions (PRFs) and pseudorandom permutations (PRPs) in a concrete security setting. By analyzing the concrete complexity of the reductions between the standard notions and the alternate ones, we show that the latter, while equivalent under polynomial-time reductions, are weaker in the concrete security sense. With these alternate notions, we argue that it is possible to get better concrete security bounds for certain PRF/PRP-based schemes. As an example, we show how using an alternate characterization of a PRF could result in tighter security bounds for some types of message authentication codes. We also use this method to give a simple concrete security analysis of the counter mode of encryption. In addition, our results provide some insight into how injectivity impacts pseudorandomness.

This paper takes a closer look at Rivest’s chaffing-and-winnowing paradigm for data privacy.We begin with a definition which enables one to clearly determine whether a given scheme qualifies as “chaffing-and-winnowing.” We then analyze Rivest’s schemes to see what quality of data privacy they provide. His bit-by-bit scheme is easily proven secure but is inefficient. His more efficient scheme -based on all-or-nothing transforms (AONTs)- can be attacked under Rivest’s definition of security of an AONT, and even under stronger notions does not appear provable. However we show that by using OAEP as the AONT one can prove security, and also present a different scheme, still using AONTs, that is equally efficient and easily proven secure even under a relatively weak notion of security of AONTs.

We consider two possible notions of authenticity for symmetric encryption schemes, namely integrity of plaintexts and integrity of ciphertexts, and relate them to the standard notions of privacy for symmetric encryption schemes by presenting implications and separations between all notions considered. We then analyze the security of authenticated encryption schemes designed by “generic composition,” meaning making black-box use of a given symmetric encryption scheme and a given MAC. Three composition methods are considered, namely Encrypt-and-MAC plaintext, MAC-then-encrypt, and Encrypt-then- MAC. For each of these, and for each notion of security, we indicate whether or not the resulting scheme meets the notion in question assuming the given symmetric encryption scheme is secure against chosen-plaintext attack and the given MAC is unforgeable under chosen-message attack. We provide proofs for the cases where the answer is “yes” and counter-examples for the cases where the answer is “no.”

Rather than use a shared key directly to cryptographically process (e.g. encrypt or authenticate) data one can use it as a master key to derive subkeys, and use the subkeys for the actual cryptographic processing. This popular paradigm is called re-keying, and the expectation is that it is good for security. In this paper we provide concrete security analyses of various re-keying mechanisms and their usage. We show that re-keying does indeed “increase” security, effectively extending the lifetime of the master key and bringing significant, provable security gains in practical situations. We quantify the security provided by different rekeying processes as a function of the security of the primitives they use, thereby enabling a user to choose between different re-keying processes given the constraints of some application.

We give the first proof of security for the full Unix password hashing algorithm (rather than of a simplified variant). Our results show that it is very good at extracting almost all of the available strength from the underlying cryptographic primitive and provide good reason for confidence in the Unix construction.

This paper introduces three new probabilistic encryption schemes using elliptic curves over rings. The cryptosystems are based on three specific trapdoor mechanisms allowing the recipient to recover discrete logarithms on different types of curves. The first scheme is an embodiment of Naccache and Stern’s cryptosystem and realizes a discrete log encryption as originally wanted in [23] by Vanstone and Zuccherato. Our second scheme provides an elliptic curve version of Okamoto and Uchiyama’s probabilistic encryption, thus answering a question left open in [10] by the same authors. Finally, we introduce a Paillier-like encryption scheme based on the use of twists of anomalous curves. Our contributions provide probabilistic, homomorphic and semantically secure cryptosystems that concretize all previous research works on discrete log encryption in the elliptic curve setting.

McEliece cryptosystem is a public-key cryptosystem based on error-correcting codes. It constitutes one of the few alternatives to cryptosystems relying on number theory. We present a modification of the McEliece cryptosystem which strengthens its security without increasing the size of the public key. We show that it is possible to use some properties of the automorphism groups of the codes to build decodable patterns of large weight errors. This greatly strengthens the system against the decoding attacks.

There have been many proposals in recent years for password-authenticated key exchange protocols.Man y of these have been shown to be insecure, and the only ones that seemed likely to be proven secure (against active adversaries who may attempt to perform off-line dictionary attacks against the password) were based on the Diffie-Hellman problem. In fact, some protocols based on Diffie-Hellman have been recently proven secure in the random-oracle model. We examine how to design a provably-secure password-authenticated key exchange protocol based on RSA.We first look at the OKE and protected-OKE protocols (both RSA-based) and show that they are insecure.Then we show how to modify the OKE protocol to obtain a password-authenticated key exchange protocol that can be proven secure (in the random oracle model). The resulting protocol is very practical; in fact the basic protocol requires about the same amount of computation as the Diffie-Hellman-based protocols or the well-known ssh protocol.

A conference key protocol allows a group of participants to establish a secret communication (conference) key so that all their communications thereafter are protected by the key. In this paper we consider the distributed conference key (conference key agreement) protocol. We present two round-efficient conference key agreement protocols, which achieve the optimum in terms of the number of rounds. Our protocols are secure against both passive and active adversaries under the random oracle model. They release no useful information to passive adversaries and achieve fault tolerance against any coalition of malicious participants. We achieve the optimal round by transferring an interactive proof system to a non-interactive version, while preserving its security capability.