Advances in Cryptology - ASIACRYPT’99

We propose a mathematical problem, and show how to solve it elegantly. This problem is related with elliptic curve cryptosystems (ECC). The solving methods can be applied to a new paradigm of key generations of the ECC.

Constructing a block cipher requires to define a random permutation, which is usually performed by the Feistel scheme and its variants. In this paper we investigate the Lai-Massey scheme which was used in IDEA. We show that we cannot use it “as is” in order to obtain results like Luby-Rackoff Theorem. This can however be done by introducing a simple function which has an orthomorphism property. We also show that this design offers nice decorrelation properties, and we propose a block cipher family called Walnut.

In this paper, we show the first method to construct vectorial bent functions which satisfy both the largest degree and the largest number of output bits simultaneously. We next apply this method to construct balanced vectorial Boolean functions which have larger nonlinearities than previously known constructions.

This paper presents a weakness in the key schedule of the AES candidate HPC (Hasty Pudding Cipher). It is shown that for the HPC version with a 128-bit key, 1 in 256 keys is weak in the sense that it has 230 equivalent keys. An efficient algorithm is proposed to construct these weak keys and the corresponding equivalent keys. If a weak key is used, it can be recovered by exhaustive search trying only 289 keys on average. This is an improvement by a factor of 238 over a normal exhaustive key search, which requires on average 2127 attempts. The weakness also implies that HPC cannot be used in standard constructions for hash functions based on block ciphers. The analysis is extended to HPC with a 192-bit key and a 256-bit key, with similar results. For some other key lengths, all keys are shown to be weak. An example of this is the HPC variant with a 56-bit user key and block length of 128 bits, which can be broken in 231 attempts on average.

An block cipher CRYPTON based on the structure of SQUARE is a candidate algorithm for the AES. Recently Lim changes the S-box construction and key scheduling, and suggested modified version(version 1.0) in FSE’99. In this paper we present an attack on CRYPTON reduced to 5 rounds. This attack is based on impossible differentials[7]. 4 rounds of CRYPTON has impossible differential, we use this to show that CRYPTON version 1.0 reduced to 5 rounds can be attacked using 283.4 chosen plaintext and ciphertext pairs. This attack can be also applied to CRYPTON version 0.5 using less chosen plaintext and ciphertext pairs.

The paper cryptanalyses two public key cryptosystems based on ${\mbox{SL}_2 (\mathbb{Z})}$ that have been recently proposed by Yamamura.

We first show that a Feistel type block cipher is broken if the round function is approximated by a low degree vectorial Boolean function. The proposed attack is a generalization of the higher order differential attack to a probabilistic one. We next introduce a notion of higher order bent functions in order to prevent our attack. We then show their explicit constructions.

In the underlying finite field arithmetic of an elliptic curve cryptosystem, field multiplication is the next computational costly operation other than field inversion. We present two novel algorithms for efficient implementation of field multiplication and modular reduction used frequently in an elliptic curve cryptosystem defined over GF(2n). We provide a complexity study of the two algorithms and present an implementation performance of the algorithms over GF(2167).

We address the Menezes-Okamoto-Vanstone (MOV) algorithm for attacking elliptic curve cryptosystems which is completed in subexponential time for supersingular elliptic curves. There exist two hurdles to clear, from an algorithmic point of view, in applying the MOV reduction to general elliptic curves: the problem of explicitly determining the minimum extension degree k such that $E[n]\subset E(F_{q^k})$ and that of efficiently finding an n-torsion point needed to evaluate the Weil pairing, where n is the order of a cyclic group of the elliptic curve discrete logarithm problem. We can find an answer to the first problem in a recent paper by Balasubramanian and Koblitz. On the other hand, the second problem is important as well, since the reduction might require exponential time even for small k. In this paper, we actually construct a novel method of efficiently finding an n-torsion point, which leads to a solution of the second problem. In addition, our contribution allows us to draw the conclusion that the MOV reduction is indeed as powerful as the Frey-Rück reduction under $n\not\vert q-1$, not only from the viewpoint of the minimum extension degree but also from that of the effectiveness of algorithms.

We show how to speed up the discrete log computations on curves having automorphisms of large order, thus generalizing the attacks on anomalous binary elliptic curves. This includes the first known attack on most of the hyperelliptic curves described in the literature.

A prohibitive barrier faced by elliptic curve users is the difficulty of computing the curves’ cardinalities. Despite recent theoretical breakthroughs, point counting still remains very cumbersome and intensively time consuming.In this paper we show that point counting can be avoided at the cost of a protocol slow-down. This slow-down factor is quite important (typically ≅) 500) but proves that the existence of secure elliptic-curve signatures is not necessarily conditioned by point counting.

We describe a new method for conducting scalar multiplication on a non-supersingular elliptic curve in characteristic two. The idea is to replace all point doublings in the double-and-add algorithm with a faster operation called point halving.

At Eurocrypt’99, Boneh and Durfee presented a new short secret exponent attack which improves Wiener’s bound (d < N0.25) up to d < N0.292. In this paper we show that it is possible to use a short secret exponent which is below these bounds while not compromising with the security of RSA provided that p and q are differing in size and are large enough to combat factoring algorithms. As an example, the RSA system with d of 192 bits, p of 256 bits, and q of 768 bits is secure against all the existing short secret exponent attacks. Besides, in order to balance and minimize the overall computations between encryption and decryption, we propose a variant of RSA such that both e and d are of the same size, e.g., log₂e ≈ log₂d ≈ 568 for a 1024-bit RSA modulus. Moreover, a generalization of this variant is presented to design the RSA system with log₂e + log₂d ≈ log₂N + l _k where l _k is a predetermined constant, e.g., 112. As an example, we can construct a secure RSA system with p of 256 bits, q of 768 bits, d of 256 bits, and e of 880 bits.

This paper proposes two new public-key cryptosystems semantically secure against adaptive chosen-ciphertext attacks. Inspired from a recently discovered trapdoor technique based on composite-degree residues, our converted encryption schemes are proven, in the random oracle model, secure against active adversaries (NM-CCA2) under the assumptions that the Decision Composite Residuosity and Decision Partial Discrete Logarithms problems are intractable. We make use of specific techniques that differ from Bellare-Rogaway or Fujisaki-Okamoto conversion methods. Our second scheme is specifically designed to be efficient for decryption and could provide an elegant alternative to OAEP.

When attacking a distributed protocol, an adaptive adversary may determine its actions (e.g., which parties to corrupt), at any time, based on its entire view of the protocol including the entire communication history. In this paper we are concerned with proactive RSA protocols, i.e., robust distributed RSA protocols that rerandomize key shares at certain intervals to reduce the threat of long-term attacks. Here we design the first proactive RSA system that is secure against an adaptive adversaries. The system achieves “optimal-resilience” and “secure space scalability” (namely O(1) keys per user).

On February 2, 1999, we completed the factorization of the 140-digit number RSA-140 with the help of the Number Field Sieve factoring method (NFS). This is a new general factoring record. The previous record was established on April 10, 1996 by the factorization of the 130-digit number RSA-130, also with the help of NFS. The amount of computing time spent on RSA-140 was roughly twice that needed for RSA-130, about half of what could be expected from a straightforward extrapolation of the computing time spent on factoring RSA-130. The speed-up can be attributed to a new polynomial selection method for NFS which will be sketched in this paper.The implications of the new polynomial selection method for factoring a 512-bit RSA modulus are discussed and it is concluded that 512-bit (= 155-digit) RSA moduli are easily and realistically within reach of factoring efforts similar to the one presented here.

The problem of proving a number is of a given arithmetic format with some prime elements, is raised in RSA undeniable signature, group signature and many other cryptographic protocols. So far, there have been several studies in literature on this topic. However, except the scheme of Camenisch and Michels, other works are only limited to some special forms of arithmetic format with prime elements. In Camenisch and Michels’s scheme, the main building block is a protocol to prove a committed number to be prime based on algebraic primality testing algorithms. In this paper, we propose a new protocol to prove a committed number to be prime. Our protocol is O(t) times more efficient than Camenisch and Michels’s protocol, where t is the security parameter. This results in O(t) time improvement for the overall scheme.

We discuss the discrete logarithm problem over the class group Cl(Δ) of an imaginary quadratic order ${\cal O}_\Delta$, which was proposed as a public-key cryptosystem by Buchmann and Williams [8]. While in the meantime there has been found a subexponential algorithm for the computation of discrete logarithms in Cl(Δ) [16], this algorithm only has running time $L_{\Delta}[\frac{1}{2},c]$ and is far less efficient than the number field sieve with $L_p[\frac{1}{3},c]$ to compute logarithms in $\mathbb{F}_p^*$. Thus one can choose smaller parameters to obtain the same level of security. It is an open question whether there is an $L_{\Delta}[\frac{1}{3},c]$ algorithm to compute discrete logarithms in arbitrary Cl(Δ).In this work we focus on the special case of totally non-maximal imaginary quadratic orders ${\cal O}_{\Delta_p}$ such that Δ _p = Δ₁p2 and the class number of the maximal order h(Δ₁)=1, and we will show that there is an $L_{\Delta_p}[\frac{1}{3},c]$ algorithm to compute discrete logarithms over the class group Cl(Δ _p ). The logarithm problem in Cl(Δ _p ) can be reduced in (expected) O(log3p) bit operations to the logarithm problem in $\mathbb{F}_p^*$ (if $(\frac{\Delta_1}{p})=1$) or $\mathbb{F}_{p^2}^*$ (if $(\frac{\Delta_1}{p})=-1$) respectively. This result implies that the recently proposed efficient DSA-analogue in totally non-maximal imaginary quadratic order ${\cal O}_{\Delta_p}$ [21] are only as secure as the original DSA scheme based on finite fields and hence loose much of its attractiveness.

We consider a generalized adversary model for unconditionally secure multi-party computation. The adversary can actively corrupt (i.e. take full control over) a subset D ⊆ P of the players, and, additionally, can passively corrupt (i.e. read the entire information of) another subset E ⊆ P of the players. The adversary is characterized by a generalized adversary structure, i.e. a set of pairs (D,E), where he may select one arbitrary pair from the structure and corrupt the players accordingly. This generalizes the classical threshold results of Ben-Or, Goldwasser and Wigderson, Chaum, Crépeau, and Damgård, and Rabin and Ben-Or, and the non-threshold results of Hirt and Maurer.The generalizations and improvements on the results of Hirt and Maurer are three-fold: First, we generalize their model by considering mixed (active and passive) non-threshold adversaries and characterize completely the adversary structures for which unconditionally secure multi-party computation is possible, for four different models: Perfect security with and without broadcast, and unconditional security (with negligible error probability) with and without broadcast. All bounds are tight. Second, some of their protocols have complexity super-polynomial in the size of the adversary structure; we reduce the complexity to polynomial. Third, we prove the existence of adversary structures for which no polynomial (in the number of players) protocols exist.The following two implications illustrate the usefulness of these results: The most powerful adversary that is unconditionally tolerated by previous protocols among three players is the one that passively corrupts one arbitrary player; using our protocols one can unconditionally tolerate an adversary that either passively corrupts the first player, or actively corrupts the second or the third player.Moreover, in a setting with arbitrarily many cheating players who want to compute an agreed function with the help of a trusted party, we can relax the trust requirement into this helping party: Without support from the cheating players the helping party obtains no information about the honest players’ inputs and outputs.

Problems of secure communication and computation have been studied extensively in network models. Goldreich, Goldwasser, and Linial, Franklin and Yung, and Franklin and Wright have initiated the study of secure communication and secure computation in multi-recipient (broadcast) models. A “broadcast channel” (such as Ethernet) enables one processor to send the same message–simultaneously and privately–to a fixed subset of processors. Franklin and Wright, and Wang and Desmedt have shown that if there are at most k malicious (Byzantine style) processors, then there is an efficient protocol for achieving probabilisticly reliable and perfectly private communication in a strongly n-connected network where n≥ k+1. While these results are unconditional, we will consider these problems in the scenario of conditional reliability, and then improve the bounds. In this paper, using the results for hardness of approximation and optimization problems, we will design communication protocols (with broadcast channels) which could defeat more faults than possible with the state of the art. Specifically, assuming certain approximation hardness result, we will construct strongly n-connected graphs which could defeat a k-active adversary (whose computation power is polynomially bounded) for k=cn, where c>1 is any given constant. This result improves a great deal on the results of Franklin and Wright, and Wang and Desmedt.

Two universally verifiable mix-net schemes that eliminate the cumbersome Cut-and-Choose method are presented. The construction is based on a permutation network composed of a network of ‘switches’ that transposes two inputs. For N inputs and t tolerable corrupt mix-servers, the schemes achieve ${\cal O}(t N \log N)$ efficiency in computation and communication while previous schemes require ${\cal O}(\kappa m N)$ for error probability 2 − κ and m mix-servers. The schemes suit small to middle-scale secret-ballot electronic elections. Moreover, one of the schemes enjoys less round complexity so that servers do not need to talk to other servers except their neighbors unless disruption occurs.

We consider the problem of secure communication in a network with malicious (Byzantine) faults for which the trust graph, with vertices the processors and edges corresponding to certified public keys, is not known except possibly to the adversary. This scenario occurs in several models, as for example in survivability models in which the certifying authorities may be corrupted, or in networks which are being constructed in a decentralized way. We present a protocol that allows secure communication in this case, provided the trust graph is sufficiently connected.

Beth and Dai studied in their Eurocrypt paper [1] the relationship between linear complexity (that is, the length of the shortest Linear Feedback Shift Register that generates the given strings) of strings and the Kolmogorov complexity of strings. Though their results are correct, some of their proofs are incorrect. In this note, we demonstrate with a counterexample the reason why their proofs are incorrect and we prove a stronger result. We conclude our note with some comments on the use of the LIL test (the law of the iterated logarithm) for pseudorandom bits generated by pseudorandom generators.

In [7], perfect multi-sequences are introduced and a construction based on function fields over finite fields is given. In this paper, we explore the construction in [7] by considering rational function fields. Consequently a class of perfect multi-sequences are obtained.

This paper proposes an approach for the cryptanalysis of stream ciphers where the encryption is performed by multiple linear feedback shift registers (LFSR) combined by a nonlinear function. The attack assumes no knowledge of either the LFSR initial conditions or the combining function. Thus, the actual architecture of the encryption system can be arbitrary. The attack is also generalized for the situation when the combining function is correlation immune of any particular order. This is in direct contrast with the existing methods which depend heavily not only on the correlation between the output of a particular LFSR and the ciphertext but also on the actual configuration of the encryption system used. Thus, the proposed method is the first ciphertext only attack in the true sense of the phrase. The paper also gives theoretical estimates of the cipherlengths involved in the determination of the initial conditions as well as estimation of the combining function.

We present a variant of the Diffie-Hellman scheme in which the number of bits exchanged is one third of what is used in the classical Diffie-Hellman scheme, while the offered security against attacks known today is the same. We also give applications for this variant and conjecture a extension of this variant further reducing the size of sent information.

This paper proposes a group key distribution scheme with an “entity revocation”, which renews a group key of all the entities except one (or more) specific entity (ies). In broadcast systems such as Pay-TV, Internet multicast and mobile telecommunication for a group, a manager should revoke a dishonest entity or an unauthorized terminal as soon as possible to protect the secrecy of the group communication. However, it takes a long time for the “entity revocation” on a large group, if the manager distributes a group key to each entity except the revoked one. A recently published paper proposed a group key distribution scheme in which the amount of transmission and the delay do not rely on the number of entities of the group, using a type of secret sharing technique. This paper devises a novel key distribution scheme with “entity revocation” that makes frequent key distribution a practical reality. This scheme uses a technique similar to “threshold cryptosystems” and the one-pass Diffie-Hellman key exchange scheme.

Efficient ID-based key sharing schemes are desired world-widely for secure communications on Internet and other networks. The Key Predistiribution Systems (KPS) are a large class of such key sharing schemes. The remarkable property of KPS is that in order to share the key, a participant should only input its partner’s identifier to its secret KPS-algorithm. Although it has a lot of advantages in terms of efficiency, on the other hand it is vulnerable by certain collusion attacks. While conventional KPS establishes communication links between any pair of entities in a communication system, in many practical communication systems such as broadcasting, not all links are required. In this article, we propose a new version of KPS which is called Hierarchical KPS. In Hierarchical KPS, simply by removing unnecessary communication links, we can significantly increase the collusion threshold. As an example, for a typical security parameter setting the collusion threshold of the Hierarchical KPS i s 16 times higher than that of the conventional KPS while using the same amount of memory at the KPS center. The memory required by the user is even reduced for a factor 1/16 in comparison with the conventional linear scheme. Hence, Hierarchical KPS provides a more efficient method for secure communication.

A periodical multi-secret threshold cryptosystem enables a sender to encrypt a message by using a cyclical sequence of keys which are shared by n parties and periodically updated. The same keys appear in the same order in each cycle, and thus any subset of t+1 parties can decrypt the message only in the periodical time-frames, while no subset of t corrupted parties can control the system (in particular, none can learn the decryption key). This scheme can be applied to a timed-release cryptosystem whose release time is determined when the number of share update phases equals the period of the sequence. The system is implemented by sharing a pseudo-random sequence generator function. It realizes n≥3t+1 robustness, and is therefore secure against an adversary who can corrupt at most one third of the parties.

This paper, for the first time, presents a provably secure signature scheme with message recovery based on the (elliptic-curve) discrete logarithm. The proposed scheme can be proven to be secure in the strongest sense (i.e., existentially unforgeable against adaptively chosen message attacks) in the random oracle model under the (elliptic-curve) discrete logarithm assumption. We give the concrete analysis of the security reduction. When practical hash functions are used in place of truly random functions, the proposed scheme is almost as efficient as the (elliptic-curve) Schnorr signature scheme and the existing schemes with message recovery such as (elliptic-curve) Nyberg-Rueppel and Miyaji schemes.

An A3-code is an extension of A-code in which none of the three participants, transmitter, receiver and arbiter, is assumed trusted. In this paper we extend the previous model of A3-codes by allowing transmitter and receiver not only to individually attack the system but also collude with the arbiter against the other. We derive information-theoretic lower bounds on success probability of various attacks, and combinatorial lower bounds on the size of key spaces. We also study combinatorial structure of optimal A3-code against collusion attacks and give a construction of an optimal code.

Traditional point-to-point message authentication systems have been extensively studied in the literature. In this paper we consider authentication for group communication. The basic primitive is a multireceiver authentication system with dynamic sender (DMRA-code). In a DMRA-code any member of a group can broadcast an authenticated message such that all other group members can individually verify its authenticity. In this paper first we give a new and flexible ‘synthesis’ construction for DMRA-codes by combining an authentication code (A-code) and a key distribution pattern. Next we extend DMRA-codes to tDMRA-codes in which t senders are allowed. We give two constructions for tDMRA-codes, one algebraic and one by ‘synthesis’ of an A-code and a perfect hash family. To demonstrate the usefulness of DMRA systems, we modify a secure dynamic conference key distribution system to construct a key-efficient secure dynamic conference system that provides secrecy and authenticity for communication among conferencees. The system is key-efficient because the key requirement is essentially the same as the original conference key distribution system and so authentication is effectively obtained without any extra cost. We show universality of ‘synthesis’ constructions for unconditional and computational security model that suggests direct application of our results to real-life multi-casting scenarios in computer networks. We discuss possible extensions to this work.