Topics in Cryptology — CT-RSA 2003

This paper provides a comprehensive treatment of forwardsecurity in the context of shared-key based cryptographic primitives, as a practical means to mitigate the damage caused by key-exposure. We provide definitions of security, practical proven-secure constructions, and applications for the main primitives in this area. We identify forwardsecure pseudorandom bit generators as the central primitive, providing several constructions and then showing how forward-secure message authentication schemes and symmetric encryption schemes can be built based on standard schemes for these problems coupled with forwardsecure pseudorandom bit generators. We then apply forward-secure message authentication schemes to the problem of maintaining secure access logs in the presence of break-ins.

Exposure of secret keys seems to be inevitable, and may in practice represent the most likely point of failure in a cryptographic system. Recently, the notion of intrusion-resilience [17] (which extends both the notions of forward security [3], [5] and key insulation [11]) was proposed as a means of mitigating the harmful effects that key exposure can have. In this model, time is divided into distinct periods; the public key remains fixed throughout the lifetime of the protocol but the secret key is periodically updated. Secret information is stored by both a user and a base; the user performs all cryptographic operations during a given time period, while the base helps the user periodically update his key. Intrusion-resilient schemes remain secure in the face of multiple compromises of both the user and the base, as long as they are not both compromised simultaneously. Furthermore, in case the user and base are compromised simultaneously, prior time periods remain secure (as in forward-secure schemes). Intrusion-resilient signature schemes have been previously constructed [17], [15]. Here, we give the first construction of an intrusion-resilient publickey encryption scheme, based on the recently-constructed forwardsecure encryption scheme of [8]. We also consider generic transformations for securing intrusion-resilient encryption schemes against chosenciphertext attacks.

In this paper, we propose TMAC. TMAC is a refinement of XCBC such that it requires only two keys while XCBC requires three keys. More precisely, TMAC requires only (k + n)-bit keys while XCBC requires (k + 2n)-bit keys, where k is the key length of the underlying block cipher E and n is its block length. We achieve this by using a universal hash function and the cost is almost negligible. Similar to XCBC, the domain is 0, 1. and it requires no extra invocation of E even if the size of the message is a multiple of n.

Montgomery Prime Hashing (MPH) is a scheme for message authentication based on universal hashing.I n MPH, roughly speaking, the hash value is computed as the Montgomery residue of the message with respect to a secret modulus.T he modulus value is structured in a way that allows fast, compact implementations in both hardware and software.Th e set of allowed modulus values is large, and as a result, MPH achieves good, provable security.

MPH performance is comparable to that of other high-speed schemes such as MMH. An advantage of MPH is that the secret key (i.e., the modulus) is small, typically 128–256 bits, while in MMH the secret key is typically much larger.I n applications where MMH key length is problematic, MPH may be an attractive alternative.

A proxy signature enables the original signer to delegate her signing capability to a proxy entity, who signs a message on behalf of the original signer. In this paper, we discuss the necessity of a secure channel in proxy signatures. Though establishing a secure channel has much influence on the efficiency of the scheme, to the best of our knowledge, this topic has not been discussed before. All known proxy signatures used a secure channel to deliver a signed warrant except one which used a 3-pass weak blind signature. However, the KPW scheme [2] appeared to be secure without the secure channel. We think that our result can contribute to designing more efficient proxy signature scheme.

Traditionally, the strongest notion of security for undeniable and confirmer signatures is invisibility under adaptive attacks. This security property was promoted by Camenisch and Michels and they provided schemes with this property. Gennaro, Krawczyk and Rabin (GKR) developed an RSA-based scheme which is much more efficient than the schemes of Camenisch and Michels, but it does not have invisibility. We give an RSA-based scheme which is as efficient as the GKR scheme, and which has invisibility.

We suggest that anonymity is the most relevant security property for undeniable and confirmer signatures. We give a precise definition of anonymity for undeniable and confirmer signatures in the multi-user setting and show that anonymity and invisibility are closely related. Finally, we show that anonymity can be achieved even when the parties use completely different cryptographic primitives.

We present a new class of signature schemes based on properties of certain bilinear algebraic maps. These signatures are secure against existential forgery under a chosen message attack in the standard model (without using the random oracle model). Security is based on the computational Diffie-Hellman problem. The concrete schemes that we get are the most efficient provable discrete-log type signature schemes to date.

We present a mechanism to encrypt to an arbitrary collection of identities using a variant of the Boneh-Franklin identity based encryption scheme. The decryptor is defined by a logical formulae of conjunctions and disjunctions. This enables a simple mechanism to drive access control to broadcast encrypted data using user identities as the public keys.

In this paper we introduce NTRUSign, an ew family of signature schemes based on solving the approximate closest vector problem (appr-CVP) in NTRU-type lattices. We explore the properties of general appr-CVP based signature schemes (e.g. GGH) and show that they are not immune to transcript attacks even in the random oracle model. We then introduce the idea of using carefully chosen perturbations to limit the information that is obtainable from an analysis of a large signature transcript. In the case of NTRUSign this can be achieved while maintaining attractive efficiency properties.

Several public key cryptosystems (HFE, Quartz, Sflash, etc.) are based on the problem MQ of solving a system of multivariate quadratic equations over a finite field. At Asiacrypt 2002, Courtois and Pieprzyk show that the MQ problem is also relevant to the security of AES. At Eurocrypt 2000, Courtois, Klimov, Patarin and Shamir introduced the XL algorithm for solving MQ. They show that if the number of equations m is much larger than the number of variables n, such overdefined MQ systems can be easily solved. From their simplified and heuristic analysis it seemed that even when m = n, a variant of XL could still be subexponential. The exact complexity of the XL algorithm remained an open problem. Moreover, all their simulations has been done over GF(127) and with D < 127, with D being the parameter of the XL algorithm.

At Asiacrypt 2002, an algorithm XSL, derived from XL, is introduced for the cryptanalysis of block ciphers [5]. Very little is known about the behaviour of XSL and we believe that one should study the XL algorithm itself first. In this paper we study the behaviour of XL for systems of quadratic equations over GF(2). We show that the possibility to use the equations of the field GF(2): x ²/ _i = x _i that are also quadratic, makes that the XL algorithm works better. We also introduce two improved versions of XL, called XL’ and XL2, with an improved final step of the algorithm (that also can be used in XSL). We present an explanation for the linear dependencies that appear in the XL algorithm, and derive a formula for the number of linearly independent equations in XL or XL2. Then we run various computer simulations and observe that this formula is always verified. Apparently we are able to predict exactly the behaviour of XL, XL’ and XL2 for random systems of equations. Due to the entanglement of linear dependencies, the analysis of XL becomes increasingly difficult, and XL may be really exponential for m = n.

Recently, there has been a lot of interest on cryptographic applications based on fields GF(p ^m ), for p > 2. This contribution presents GF(p ^m ) multipliers architectures, where p is odd. We present designs which trade area for performance based on the number of coefficients that the multiplier processes at one time. Families of irreducible polynomials are introduced to reduce the complexity of the modulo reduction operation and, thus, improved the efficiency of the multiplier. We, then, specialize to fields GF(3 ^m ) and provide the first cubing architecture presented in the literature. We synthesize our architectures for the special case of GF(3⁹⁷) on the XCV1000-8-FG1156 and XC2VP20-7-FF1156 FPGAs and provide area/performance numbers and comparisons to previous GF(3 ^m ) and GF(2 ^m ) implementations. Finally, we provide tables of irreducible polynomials over GF(3) of degree m with 2 ≤ m ≤ 255.

In this paper, we present a general framework for evaluating the performance characteristics of block cipher structures composed of S-boxes and Maximum Distance Separable (MDS) mappings. In particular, we examine nested Substitution-Permutation Networks (SPNs) and Feistel networks with round functions composed of S-boxes and MDS mappings. Within each cipher structure, many cases are considered based on two types of S-boxes (i.e., 4X4 and 8X8) and parameterized MDS mappings. In our study of each case, the hardware complexity and performance are analyzed. Cipher security, in the form of resistance to differential, linear, and Square attacks, is used to determine the minimum number of rounds required for a particular parameterized structure. Because the discussed structures are similar to many existing ciphers (e.g., Rijndael, Camellia, Hierocrypt, and Anubis), the analysis provides a meaningful mechanism for seeking efficient ciphers through a wide comparison of performance, complexity, and security.

Identity-based public key encryption facilitates easy introduction of public key cryptography by allowing an entity’s public key to be derived from an arbitrary identification value, such as name or email address.Th e main practical benefit of identity-based cryptography is in greatly reducing the need for, and reliance on, public key certificates. Although some interesting identity-based techniques have been developed in the past, none are compatible with popular public key encryption algorithms (such as El Gamal and RSA).Th is limits the utility of identity-based cryptography as a transitional step to full-blown public key cryptography. Furthermore, it is fundamentally difficult to reconcile fine-grained revocation with identity-based cryptography.

Mediated RSA (mRSA) [9] is a simple and practical method of splitting a RSA private key between the user and a Security Mediator (SEM). Neither the user nor the SEM can cheat one another since each cryptographic operation (signature or decryption) involves both parties. mRSA allows fast and fine-grained control of users’ security privileges.H owever, mRSA still relies on conventional public key certificates to store and communicate public keys.In this paper, we present IB-mRSA, a simple variant of mRSA that combines identity-based and mediated cryptography. Unde r the random oracle model, IB-mRSA with OAEP [7] is shown as secure (against adaptive chosen ciphertext attack) as standard RSA with OAEP. Furthermore, IB-mRSA is simple, practical, and compatible with current public key infrastructures.

Signcryption is a public key primitive proposed by Zheng [14] to achieve the combined functionality of digital signature and encryption in an efficient manner. We present a signcryption scheme based on RSA and provide proofs of security in the random oracle model [6] for its privacy and unforgeability. Both proofs are under the assumption that inverting the RSA function is hard.

Our scheme has two appealing aspects to it. First of all it produces compact ciphertexts. Secondly it offers non-repudiation in a very straightforward manner.

The hype is over. Cryptographers can fire their PR agents, tear up their stock options, and get back to work. But what to work on? Cryptography cuts across many spheres ofh uman activity. Important challenges remain open at levels of difficulty to suit every taste. We suggest scientific, engineering, social and political agendas in the hope that we will encourage cryptographers to do great things.

Kerckhoffs’ assumption states that an attacker must be assumed to have full knowledge of all the details of a cryptosystem except information about encryption/decryption keys upon which security of the cryptosystem rests entirely. In this paper we generalize the assumption to allow an attacker to have access to intermediate results during the computational process of cryptographic operations. We show that the generalized assumption models quite well such real world attacks as the “memory reconstruction attack” and the “memory core-dump attack” which may be mounted by computer forensic software or computer viruses. We further analyze a number of public key encryption schemes under the generalized Kerckhoffs’ assumption, and demonstrate that some of the schemes, although provably secure under some computational assumptions, may be broken if an attacker has access to intermediate results during a decryption operation.

Mix chains as proposed by Chaum allow sendingun traceable electronic e-mail without requiring trust in a single authority: messages are recursively public-key encrypted to multiple intermediates (mixes), each of which forwards the message after removing one layer of encryption. To conceal as much information as possible when using variable (source routed) chains, all messages passed to mixes should be of the same length; thus, message length should not decrease when a mix transforms an input message into the corresponding output message directed at the next mix in the chain. Chaum described an implementation for such length-preserving mixes, but it is not secure against active attacks. We show how to build practical cryptographically secure length-preserving mixes. The conventional definition of security against chosen ciphertext attacks is not applicable to length-preserving mixes; we give an appropriate definition and show that our construction achieves provable security.

A broadcast encryption scheme enables a server to broadcast information in a secure way over an insecure channel to an arbitrary subset of priviliged recipients. In a set-up phase, the server gives pre-defined keys to every user of the system, using secure point-to-point channels. Later on, it broadcasts an encrypted message along a broadcast channel, in such a way that only users in a priviliged subset can decrypt it, by using the pre-defined keys received in set-up phase. Usually, the broadcast message contains a fresh session key, which can subsequently be used for secure broadcast transmission to the priviliged set of recipients. In this paper we deal with two aspects of secure broadcast transmission: reliability and trust in the broadcaster. The first is a well-studied issue in communication over unreliable channels: packets can get lost and some redundancy is required to provide reliable communication. The second aspect concerns with the assumption that the broadcaster, who receives information for broadcasting from several entities, must be trusted. This issue has not previously been addressed in the broadcast transmission setting. We provide a motivating scenario in which the assumption does not hold and, for both problems, we review and extend some existing broadcast encryption schemes, in order to gain fault tolerance and to remove the need for trust in the broadcaster.

In Crypto’95, Micali and Sidney proposed a method for shared generation of a pseudo-random function f(·) among n players in such a way that for all the inputs x, any u players can compute f(x) while t or fewer players fail to do so, where 0 ≤ t < u ≤ n. The idea behind the Micali-Sidney scheme is to generate and distribute secret seeds S = s1, . . . , sd of a poly-random collection of functions, among the n players, each player gets a subset of S, in such a way that any u players together hold all the secret seeds in S while any t or fewer players will lack at least one element from S. The pseudo-random function is then computed as where f _{s i} (·)’s are poly-random functions. One question raised by Micali and Sidney is how to distribute the secret seeds satisfying the above condition such that the number of seeds, d, is as small as possible. In this paper, we continue the work of Micali and Sidney. We first provide a general framework for shared generation of pseudo-random function using cumulative maps. We demonstrate that the Micali-Sidney scheme is a special case of this general construction.We then derive an upper and a lower bound for d. Finally we give a simple, yet efficient, approximation greedy algorithm for generating the secret seeds S in which d is close to the optimum by a factor of at most u ln 2.

Authenticated data structures provide cryptographic proofs that their answers are as accurate as the author intended, even if the data structure is maintained by a remote host. We present techniques for authenticating data structures that represent graphs and collections of geometric objects. In our model, a data structure maintained by a trusted source is mirrored at distributed directories that answer queries and provide proof of correctness. Our work has applications to the authentication of network management systems and geographic information systems.

We introduce a technique for traversal of Merkle trees, and propose an efficient algorithm that generates a sequence of leaves along with their associated authentication paths. For one choice of parameters, and a total of N leaves, our technique requires a worst-case computational effort of 2 logN/loglog N hash function evaluations per output, and a total storage capacity of less than 1.5 log2 N/loglogN hash values. This is a simultaneous improvement both in space and time complexity over any previously published algorithm.

In this talk I’ll survey a variety of unpublished enhancements, optimizations, implementation ideas and new variants of the RSA scheme which I have found over the years.

The side channel attack (SCA) is a serious attack on wearable devices that have scarce computational resources. Cryptographic algorithms on them should be efficient using small memory — we have to make efforts to optimize the trade-off between efficiency and memory. In this paper we present efficient SCA-resistant scalar multiplications based on window method. Möller proposed an SPA-resistant window method based on 2 ^w -ary window method, which replaces w-consecutive zeros to 1 plus w-consecutive 1 and it requires 2 ^w points of table (or 2^w-1 +1 points if the signed 2 ^w -ary is used). The most efficient window method with small memory is the width-w NAF, which requires 2^w-2 points of table. In this paper we convert the width-w NAF to an SPA-resistant addition chain. Indeed we generate a scalar sequence with the fixed pattern, e.g. 0..0x0..0x...0..0x, where x is positive odd points < 2w. Thus the size of the table is 2^w-1, which is optimal in the construction of the SPA-resistant chain based on width-w NAF. The table sizes of the proposed scheme are 6% to 50% smaller than those of Möller’s scheme for w = 2, 3, 4, 5, which are relevant choices in the sense of efficiency for 160-bit ECC.

We present an algorithm which speeds scalar multiplication on a general elliptic curve by an estimated 3.8% to 8.5% over the best known general methods when using affine coordinates. This is achieved by eliminating a field multiplication when we compute 2P +Q from given points P, Q on the curve. We give applications to simultaneous multiple scalar multiplication and to the Elliptic Curve Method of factorization. We show how this improvement together with another idea can speed the computation of the Weil and Tate pairings by up to 7.8%.

Secrecy of private signing keys is one of the most important issues in secure electronic commerce. A promising solution to this problem is to distribute the signing function among multiple parties. However, a threshold signature scheme typically assumes that the shared signing function can only be activated by a quorum number of parties, which is inappropriate in settings where a user employs some public servers for a threshold protection of her private signing function (therefore the name “server-assisted threshold signatures”).

In this paper we present two efficient and provably secure schemes for server-assisted threshold signatures, where the signing function is activated by a user (but in certain enhanced way). The first one (we call TPAKE-HTSig) is tailored for the setting where a user has a networked device that is powerful enough to efficiently compute modular exponentiations. The second one (we call LW-TSig) is tailored for the setting where a user has a smart card without a cryptographic co-processor. Modular construction of the schemes ensures that any module can be substituted without weakening security of the resultant scheme, as long as the substitutive one satisfies certain security requirement. In addition to the two schemes, we also present a taxonomy of systems protecting private signing functions.

A Distributed Key Generation (DKG)p rotocol is an essential component of any threshold cryptosystem. It is used to initialize the cryptosystem and generate its private and public keys, and it is used as a subprotocol, for example to generate a one-time key pair which is a part of any threshold El-Gamal-like signature scheme. Gennaro et al. showed [GJKR99] that a widely-known non-interactive DKG protocol suggested by Pedersen does not guarantee a uniformly random distribution of generated secret keys even in the static adversary model. Furthermore, Gennaro et al. proposed to replace this protocol with one that guarantees a uniform distribution of the generated key but requires an extra round of reliable broadcast communication.

We investigate the question whether some discrete-log based threshold cryptosystems remain secure when implemented using the more efficient DKG protocol of Pedersen, in spite of the fact that the adversary can skew the distribution of the secret key generated by this protocol. We answer this question in the positive. We show that threshold versions of some schemes whose security reduces to the hardness of the discrete logarithm problem, remain secure when implemented with Pedersen DKG. We exemplify this claim with a threshold Schnorr signature scheme.

However, the resulting scheme has less efficient security reduction (in the random oracle model)from the hardness of the discrete logarithm problem than the same scheme implemented with the computationally more expensive DKG protocol of Gennaro et al. Thus our results imply a trade-o. in the design of threshold versions of certain discrete-log based schemes between the round complexity of a protocol and the size of the modulus.

We present extremely simple ways of embedding a backdoor in the key generation scheme of RSA. Three of our schemes generate two genuinely random primes p and q of a given size, to obtain their public product n = pq. However they generate private/public exponents pairs (d, e) in such a way that appears very random while allowing the author of the scheme to easily factor n given only the public information (n, e). Our last scheme, similar to the PAP method of Young and Yung, but more secure, works for any public exponent e such as 3, 17, 65537 by revealing the factorization of n in its own representation. This suggests that nobody should rely on RSA key generation schemes provided by a third party.