Advances in Cryptology — EUROCRYPT ’93

In this paper we show an explicit relation between authentication codes and codes correcting independent errors. This relation gives rise to several upper bounds on A-codes. We also show how to construct A-codes starting from error correcting codes. The latter is used to show that if P_s exceeds P _I by an arbitrarily small positive amount, then the number of source states grows exponentially with the number of keys but if P_s = P_I it will grow only linearly.

In this paper we define an optimal authentication systems as a system whose minimum probability of deception is k/M, k and M being the number of source states and cryptograms respectively, and satisfies information theoretic bounds on the value of impersonation and substitution games. We will characterize order-1 perfect systems and δ-perfect systems and prove their optimality when E, the number of encoding rules, satisfies certain bounds. We will show that both types of systems, in this case, also have best game theoretic performance. This will be used to prove that optimal systems exist only if E ≥ M2/k2 and for less value of E probability of deception is always greater than k/M. We will prove that doubly perfect codes are optimal systems with minimum value of E and perfect systems are not optimal. Characterization of doubly perfect systems follows from characterization theorems mentioned earlier. We give constructions for each class.

We describe our single-instruction multiple data (SIMD) implementation of the multiple polynomial quadratic sieve integer factoring algorithm. On a 16K MasPar massively parallel computer, our implementation can factor 100 digit integers in a few days. Its most notable success was the factorization of the 110-digit RSA-challenge number, which took about a month.

A new public key cryptosystem based on elliptic curves over the ring Z_n is described. The scheme can be used for both digital signature and encryption applications, does not expand the amount of data that needs to be transmitted and appears to be immune from homomorphic attacks. The main advantage of this system over other similar elliptic curve based systems is that there is very little restriction on the types of elliptic curves and types of primes (comprising the arithmetic modulus, n) that can be used. In addition, the system works on fixed elliptic curves. Problems associated with imbedding plaintext onto a curve are avoided by working within a multiple group structure. This enables the encryption and decryption operations to be performed on only the first coordinate of points on the given curve. The security of the system relies on the difficulty of factorising large composite numbers.

Recently, Qu and Vanstone have announced the construction of several new public-key cryptosystems based on group factorization. One of these was described at the last AUSCRYPT meeting [2]. We point out a serious weakness of this last system which makes it insecure. Our method only uses elementary algebra.

This work is motivated by the observation that in DES-like ciphers it is possible to choose the round functions in such a way that every non-trivial one-round characteristic has small probability. This gives rise to the following definition. A mapping is called differentially uniform if for every non-zero input difference and any output difference the number of possible inputs has a uniform upper bound. The examples of differentially uniform mappings provided in this paper have also other desirable cryptographic properties: large distance from affine functions, high nonlinear order and efficient computability.

In this paper basic properties of APN permutations, which can be used in an iterated secret-key block cipher as a round function to protect it from a differential cryptanalysis, are investigated. Several classes of almost perfect nonlinear permutations and other permutations in GF(2)n with good nonlinearity and high nonlinear order are presented. Included here are also three methods for constructing permutations with good nonlinearity.

We introduce a new class of bent functions on (GF(2))n (n even). We prove that this class is not included in one of the known classes of bent functions, and that, when n equals 6, it covers the whole set of bent functions of degree 3. This class is obtained by using a result from J.F. Dillon. We generalize this result and deduce a second new class of bent functions which we checked was not included in one of the preceding ones.

The Strict Avalanche Criterion (SAC) for Boolean functions was introduced by Webster and Tavares in connection with a study of the design of S-boxes. Later Forré extended this notion by defining strict avalanche criteria of order k for Boolean functions of n variables, where 0 ≤ k ≤ n − 2; the case k = 0 is the original SAC Recent work by Lloyd, Preneel and others has been concerned with the problem of counting the functions which satisfy SAC of various orders. If the order is n − 2 or n − 3, this problem has been completely solved; the work in these cases is made easier by the fact that only quadratic Boolean functions occur. In this paper, we give good estimates for the number of Boolean functions which satisfy the SAC of order n − 4. We also give a detailed description of the functions which satisfy SAC of order n − 4, so the actual construction of these functions for cryptographic applications is made easy.

In this paper we study the amount of secret information that must be given to participants in any secret sharing scheme that is secure against coalitions of dishonest participants in the model of Tompa and Woll [20]. We show that any (k, n) threshold secret sharing algorithm in which any coalition of less than it participants has probability of successful cheating less than some ε > 0 it must give to each participant shares whose sizes are at least the size of the secret plus log_#x03B5;1.

This paper shows that nonperfect secret sharing schemes (NSS) have matroid structures and presents a direct link between the secret sharing matroids and entropy for both perfect and nonperfect schemes. We define natural classes of NSS and derive a lower bound of |V_i| for those classes. “Ideal” nonperfect schemes are defined baaed on this lower bound. We prove that every such ideal secret sharing scheme has a matroid structure. The rank function of the matroid is given by the entropy divided by some constant. It satisfies a simple equation which represents the access level of each subset of participants.

Norwegian cryptology was first organized, in the 30’s, by then Capt. R. A. Roscher Lund. He set up a “Cryptology club”, recruited partly from amateurs, partly from mathematicians. Many members came from a bridge club with the appropriate name “Forcing”. Around the outbreak of the war a “Defense information office” was established with some (very) few cryptologists.

In the theory of stream ciphers the termwise product of shift-register sequences plays a crucial role. In this paper we improve and generalize earlier results on the linear complexity of a termwise product of two shift-register sequences and we also provide information on the minimal polynomial of such a product.

In some applications for synchronous stream ciphers, the risk of loss of synchronization cannot be eliminated completely. In these cases frequent synchronization or resynchronization upon request may be necessary. In the paper it is shown that this can lead to significant deterioration of the cryptographic security. A powerful general attack on nonlinearly filtered linear (over ℤ₂) systems is presented. This attack is further refined to efficiently cryptanalyze a linear system with a multiplexer as output function.

The problem of recovering the phase on a known binary m-sequence that is corrupted by a binary noise source is considered. This problem arises in the cryptanalysis of stream ciphers formed from a nonlinear combination of m-sequences. A synchronization procedure is developed for even span n. The procedure obtains a reliable estimate of the phase of an m-sequence of span n from unreliable estimates of the phases of a small number of shifts of a fixed m-sequence of span n/2. These latter estimates can be obtained from a variety of methods available in the literature. The procedure results in a reduction of complexity but requires observing on the order of the square root of the m-sequence’s period.

A Boolean function is said to be correlation immune if its output leaks no information about its input values. Such functions have many applications in computer security practices including the construction of key stream generators from a set of shift registers. Finding methods for easy construction of correlation immune functions has been an active research area since the introduction of the notion by Siegenthaler. In this paper we study balanced correlation immune functions using the theory of Hadamard matrices. First we present a simple method for directly constructing balanced correlation immune functions of any order. Then we prove that our method generates exactly the same set of functions as that obtained using a method by Camion, Carlet, Charpin and Sendrier. Advantages of our method over Camion et al’s include (1) it allows us to calculate the nonlinearity, which is a crucial criterion for cryptographically strong functions, of the functions obtained, and (2) it enables us to discuss the propagation characteristics of the functions. Two examples are given to illustrate our construction method. Finally, we investigate methods for obtaining new correlation immune functions from known correlation immune functions. These methods provide us with a new avenue towards understanding correlation immune functions.

We present a protocol that allows a sender to gradually and verifiably release a secret to a receiver. We argue that the protocol can be efficiently applied to exchange secrets in many cases, for example when the secret is a digital signature. This includes Rabin, low-public-exponent RSA, and El Gamal signatures. In these cases, the protocol requires an interactive 3-pass initial phase, after which each bit (or block of bits) of the signature can be released non-interactively (i.e. by sending 1 message). The necessary computations can be done in a few seconds on an up-to-date PC. The protocol is statistical zero-knowledge, and therefore releases a negligible amount of side information in the Shannon sense to the receiver. The sender is unable to cheat, if he cannot factor a large composite number before the protocol is completed.We also point out a simple method by which any type of signatures can be applied to fair contract signing using only one signature.

In I985, Simmons showed how to embed a subliminal channel in digital signatures created using the El Gamal signature scheme. This channel, though, had several shortcomings. In order for the subliminal receiver to be able to recover the subliminal message, it was necessary Tor him to know the transmitter’s secret key. This meant that the subliminal receiver had the capability to utter undetectable forgeries of the transmitter’s signature. Also, only a fraction of the number of messages that the channel could accommodate in principal could actually be communicated subliminally (ϕ(p-1) messages instead of p-1) and some of those that could be transmitted were computationally infeasible for the subliminal receiver to recover.In August 1991, the U.S. National Institute of Standards and Technology proposed as a standard a digital signature algorithm (DSA) derived from the El Gamal scheme. The DSA accommodates a number of subliminal channels that avoid all of the shortcomings encountered in the El Gamal scheme. In fairness, it should be mentioned that not all are avoided at the same time. The channel in the DSA analogous to the one Simmons demonstrated in the El Gamal scheme can use all of the bits contained in the signature that are not used to provide for the security of the signature against forgery, alteration or transplantation, and is hence said to be broadband. All messages can be easily encoded for communication through this channel and are easily decoded by the subliminal receiver. However, this broadband channel still requires that the subliminal receiver know the transmitter’s secret key. There are two narrowband subliminal channels in the DSA, though, that do not give the subliminal receiver any better chance of forging the transmitter’s signature than an outsider has. The price one pays to secure this integrity for the transmitter’s signature is a greatly reduced bandwidth for the subliminal channel and a large, but feasible—dependent on the bandwidth actually used—amount of computation needed to use the channel. In one realization of a narrowband subliminal channel, the computational burden is almost entirely on the transmitter while in the other it is almost entirely on the subliminal receiver.In this paper we discuss only the broadband channel. The narrowband channels have been described by Simmons in a paper presented at the 3rd Symposium on State and Progress of Research in Cryptography, Rome, Italy, February 15–16, 1993. Space does not permit them to be described here. The reader who wishes to see just how easy it is to communicate subliminally using the DSA is referred to that paper as well. The inescapable conclusion, though, is that the DSA provides the most hospitable setting for subliminal communications discovered to date.

This paper describes a family of new Ong-Schnorr-Shamir-Fiat-Shamir-like [1] identification and signature protocols designed to prevent forgers from using the Pollard-Schnorr attack [2].Our first signature scheme (and its associated identification protocol) uses x, which is secret-free, as a commitment on which k will depend later. Therefore, the original quadratic equation is replaced by x2 − -k(x)y2 = m mod n where k(x) is a non-polynomial function of x and since the Poliard-Schnorr algorithm takes as input value k (to output x and y), it becomes impossible to feed à-priori k(x) which is output-dependentThe second signature method takes advantage of the fact that although an attacker can generate validOSS signatures (solutions {x,y} of x2 - k y2 = m mod n), he has no control over the internal structure of x and y and in particular, if we restrict the solution space by adding extra conditions on x and y, it becomes very difficult to produce forged solutions that satisfy the new requirements.

In the past few years a lot of attention has been paid to the use of special logics to analyse cryptographic protocols, foremost among these being the logic of Burrows, Abadi and Needham (the BAN logic). These logics have been successful in finding weaknesses in various examples. In this paper a limitation of the BAN logic is illustrated with two examples. These show that it is easy for the BAN logic to approve protocols that are in practice unsound.

The contribution of this paper are twofold. First, we present an efficient computationally secure anonymous channel which has no problem of ciphertext length expansion. The length is irrelevant to the number of MIXes ( control centers ). It improves the efficiency of Chaum’s election scheme based on the MIX net automatically. Second, we show an election scheme which satisfies fairness. That is, if some vote is disrupted, no one obtains any information about all the other votes. Each voter sends O(nk) bits so that the probability of the fairness is 1 − 2−k, where n is the bit length of the ciphertext.

A scheme for ensuring access rights untransferability in a client-server scenario with a central authority and where servers hold no access information about clients is presented in this paper; an extension to a multi- authority scenario is conceivable, since servers are also authority independent. Usurping a right with no information at all about other clients is for a client as hard as the discrete logarithm, and rights sharing between clients does not compromise their non-shared rights as long as RSA confidentiality holds. Transferring rights between clients without the authority’s contribution cannot be done unless RSA confidentiality is broken; however, only control on partial rights transfers is addressed in this paper, which does not deal with total identity transfer or alienation.

Often the core difficulty in designing zero-knowledge protocols arises from having to consider every possible cheating verifier trying to extract additional information. We here consider a compiler which transforms protocols proven secure only with respect to the honest verifier into protocols which are secure against any (even cheating) verifier. Such a compiler, which preserves the zero-knowledge property of a statistically or computationally secure protocol was first proposed in [BMO] based on Discrte Logarithm problem. In this paper, we show how such a compiler could be constructed based on any one-way permutation using our recent method of interactive hashing [OVY-90, NOVY]. This applies to both statistically and computationally secure protocols, preserving their respective security. Our result allows us to utilize DES-like permutations for such a compiler.

This paper describes a simple candidate one-way hash function which satisfies a quasi-commutative property that allows it to be used as an accumulator. This property allows protocols to be developed in which the need for a trusted central authority can be eliminated. Space-efficient distributed protocols are given for document time stamping and for membership testing, and many other applications are possible.

The AR hash function has been proposed by Algorithmic Research Ltd and is currently being used in practice in the German banking world. AR hash is based on DES and a variant of the CBC mode. It produces a 128 bit hash value.In this paper, we present two attacks on AR hash. The first one constructs in one DES encryption two messages with the same hash value. The second one finds, given an arbitrary message M, an M′ ≠ M with the same hash value as M. The attack is split into two parts, the first part needs about 233 DES encryptions and succeeds with probability 63%, the second part needs at most about 266 DES encryptions and succeeds with probability about 99% of the possible choices of keys in AR. Moreover, the 233 respectively 266 encryptions are necessary only in a one-time preprocessing phase, i.e. having done one of the attacks once with success, a new message can be attacked at the cost of no encryptions at all. Since the hash value is 128 bits long, the times for the attacks should be compared to 264, resp. 2128 DES encryptions for brute force attacks. For the particular keys chosen in AR hash we implemented the first part of the second attack. In 233 encryptions we found two messages that breaks AR hash.

At Crypto’ 91 Ronald L. Rivest introduced the MD5 Message Digest Algorithm as a strengthened version of MD4, differing from it on six points. Four changes are due to the two existing attacks on the two round versions of MD4. The other two changes should additionally strengthen MD5. However both these changes cannot be described as well-considered. One of them results in an approximate relation between any four consecutive additive constants. The other allows to create collisions for the compression function of MD5. In this paper an algorithm is described that finds such collisions.A C program implementing the algorithm establishes a work load of finding about 216 collisions for the first two rounds of the MD5 compression function to find a collision for the entire four round function. On a 33MHz 80386 based PC the mean run time of this program is about 4 minutes.

Ivan Damgård [4] suggested at Crypto’89 concrete examples of hash functions including, among others, a knapsack scheme. In [3], P. Camion and myself have shown how to break this scheme with a number of computations in the region of 232 and about 128 Gigabytes of memory. More precisely in [3] we showed how to find an x such that h(x) = b, for a fixed and average b. (1).But in order to show that h is not collision free, we have just to find x and y, x ≠ y such that h(x) = h(y). (2). This is a weaker condition than (1).We will see in this paper how to find (2) with a number in the region of 224 computations and about 512 Megabytes of memory. That is to say with about 256 times less computation and memory than [3]. Moreover, ways to extend our algorithm to other knapsacks than that (256, 128) suggested by Damgård are investigated.Then we will see that for solving problems like (1) or (2) for various knapsacks it is also possible to use less memory if we are allowed to use a little more computing time. This is a usefull remark since the memory needed was the main problem of the algorithms of [3].Finally, at the end of this paper, we will briefly study some ideas on how to avoid all these attacks by slightly modifying the knapsack Hash functions. However some different attacks could appear, and it is not so easy to find a colision free Hash function, both very quick and with very simple Mathematic expression.

We present a new construction for off-line electronic coins that is both far more efficient and much simpler than previous systems. Instead of using many terms, each for a single bit of the challenge, our system uses a single term for a large number of possible challenges. The withdrawal protocol does not use a cut-and-choose methodology as with earlier systems, but uses a direct construction.

Wallets with observers were suggested by David Chaum and have previously been described in [Ch92] and [CP92]. These papers argue that a particular combination of a tamper-resistant-unit and a small computer controlled by the user is very suitable as a personal device in consumer transaction systems. Using such devices, protocols are constructed that, simultaneously, achieve high levels of security for organizations and anonymity for individual users. The protocols from [CP92] offer anonymity to users, under the assumption that the information stored by observers is never revealed to the outside world.This paper extends [CP92] by defining additional requirements for the protocols which make it impossible to trace the behaviour of individuals in the system if one is also allowed to analyse a posteriori the information observers can collect. We propose two protocols satisfying our requirements, thus achieving a higher degree of privacy for individuals. This extra level of privacy is obtained at essentially no cost as the new protocols have the same complexity as those previously proposed.

It is often the case in applications of cryptographic protocols that one party would like to determine a practical upper-bound on the physical distance to the other party. For instance, when a person conducts a cryptographic identification protocol at an entrance to a building, the access control computer in the building would like to be ensured that the person giving the responses is no more than a few meters away.The “distance bounding” technique we introduce solves this problem by timing the delay between sending out a challenge bit and receiving back the corresponding response bit. It can be integrated into common identification protocols. The technique can also be applied in the three-party setting of “wallets with observers” in such a way that the intermediary party can prevent the other two from exchanging information, or even developing common coinflips.

Differential cryptanalysis is a method of attacking iterated mappings which has been applied with varying success to a number of product ciphers and hash functions [1, 3]. The attack is based on predicting a series of differences ΔY₁, ΔY₂,..., ΔY, known as a characteristic Ω. Partial information about the key can be derived when the differences are correctly predicted. The probability of a given characteristic Ω correctly predicting differences is derived from the XOR tables associated with the iterated mapping.Even though differential cryptanalysis has been applied successfully to a number of specific iterated mappings such as DES, FEAL and LOKI, the effectiveness of the attack against an arbitrary iterated mapping has not been considered. In this paper we derive the exact distribution of characteristics in XOR tables, and determine an upper bound on the probability of the most likely characteristic Ω in a product cipher constructed from randomly selected S-boxes that are bijective mappings. From this upper bound we are then able to construct product ciphers for which all characteristics Ω occur with low probability.

IDEA is an iterated block cipher proposed by Lai and Massey and is based on the design concept of “mixing operations from different algebraic groups”. New arithmetic properties of the basic operations used in the round function are found and investigated with respect to the security of this block cipher. Evidence is given that these properties can be exploited in the cryptanalysis of the first 2 rounds of IDEA but that they are of no assistance in the cryptanalysis of the full IDEA block cipher containing 8 rounds.

We introduce a new method for cryptanalysis of DES cipher, which is essentially a known-plaintext attack. As a result, it is possible to break 8-round DES cipher with 221 known-plaintexts and 16-round DES cipher with 247 known-plaintexts, respectively. Moreover, this method is applicable to an only-ciphertext attack in certain situations. For example, if plaintexts consist of natural English sentences represented by ASCII codes, 8-round DES cipher is breakable with 229 ciphertexts only.

In this paper we study the influence of key scheduling algorithms on the strength of blockciphers. We show that the key scheduling algorithms of many blockciphers inherit obvious relationships between keys, and use these key relations to attack the blockciphers. Two new types of attacks are described: New chosen plaintext reductions of the complexity of exhaustive search attacks (and the faster variants based on complementation properties), and new low-complexity chosen key attacks. These attacks are independent of the number of rounds of the cryptosystems and of the details of the F-function and may have very small complexities. These attacks show that the key scheduling algorithm should be carefully designed and that its structure should not be too simple. These attacks are applicable to both variants of LOKI and to Lucifer. DES is not vulnerable to the related keys attacks since the shift pattern in the key scheduling algorithm is not the same in all the rounds.

Assuming that Alice and Bob use a secret noisy channel (modelled by a binary symmetric channel) to send a key, reconciliation is the process of correcting errors between Alice’s and Bob’s version of the key. This is done by public discussion, which leaks some information about the secret key to an eavesdropper. We show how to construct protocols that leak a minimum amount of information. However this construction cannot be implemented efficiently. If Alice and Bob are willing to reveal an arbitrarily small amount of additional information (beyond the minimum) then they can implement polynomial-time protocols. We also present a more efficient protocol, which leaks an amount of information acceptably close to the minimum possible for sufficiently reliable secret channels (those with probability of any symbol being transmitted incorrectly as large as 15%). This work improves on earlier reconciliation approaches [R, BBR, BBBSS].

We investigate the problem of generating a global, unpredictable coin in a distributed system. A fast, efficient solution is of fundamental importance to distributed protocols, especially those that rely on broadcast channels. We present two unpredictable bit generators, based on the Blum-Blum-Shub generator, that can be evaluated non-interactively; that is, each bit (or group of bits) requires each processor merely to send one message to the other processors, without requiring a broadcast or Byzantine Agreement.The unpredictability of our generators (and the security of our protocols) are based provably on the QRA or the intractability of factoring. Remarkably, their structure seems to violate an impossibility result of [8], but our generators escape that lower bound because they achieve a slightly weaker goal: producing unpredictable bits directly, rather than producing “shares” of random bits. In doing so, they avoid the extra machinery (eg., “sharing shares”) of similar results discovered independently in [8].

Schnorr’s preprocessing algorithms [6, 7] are designed to speed up the ‘random’ exponentiation often performed by the prover/signer in identification and signature schemes.In this paper, an attack on these preprocessing algorithms is presented. For the proposed parameters, the attack requires about 231 steps, and 700 identifications or signatures to retrieve the secret key. Here the underlying scheme may be Schnorr, Brickell-McCurley, ElGamal or DSS.

Chang-Wu-Chen presented at Auscrypt 92 a conference key distribution system based on public keys. We show that this scheme is insecure and discuss ways to fix it.

Boyd and Mao (“On a Limitation of BAN Logic”, in these proceedings) suggest that it is easy to use the authentication logic of Burrows, Abadi and Needham to approve protocols that are in practice unsound, and present two examples. We illustrate that the problem in the first example can be traced to a violation of pre-conditions in the BAN analysis (involving ill-founded trust in a trusted server), while in the second the idealization is simply incorrect. For the latter, a general guideline is proposed to avoid similar problems in the future.

By accepting a shared secret or shared control scheme specified by an access structure Γ, an issuing authority also implicitly accepts all of the access structures that can be realized as a result of trust relations that may exist among some of the participants in Γ. An algorithm is presented here that makes it possible to fully analyze the consequences of trust to such schemes.

This paper includes some relations between differential cryptanalysis and group theory. The main result is the following: If the one-round functions of an r-round iterated cipher generate the alternating or the symmetric group, then for all corresponding Markov ciphers the chains of differences are irreducible and aperiodic.As an application it will be shown that if the hypothesis of stochastic equivalence holds for any of these corresponding Markov ciphers, then the DES and the IDEA(32) are secure against a differential cryptanalysis attack after sufficiently many rounds for these Markov ciphers.The section about IDEA(32) includes the result that the one-round functions of this algorithm generate the alternating group.

Mobile communication networks need public key cryptosystems that offer both low computation cost and user authentication. Tatebayashi et al. showed such a key distribution protocol for such networks at CRYPTO’89 based on low exponent RSA. This paper shows that their protocol is not secure. We also present a new secure and efficient key distribution protocol.