Advances in Cryptology — ASIACRYPT '91

The peak of mechanical cryptography was reached in World War II, then electronics rapidly replaced these machines. A very remarkable technology then ended. Some of the best examples that I have found will be illustrated. The paper continues with some memories of building the first computer at NPL during 1947 to 1950.

In [BrPiSe90] Brown, Pieprzyk and Seberry proposed a new encryption primitive, which encrypts and decrypts a 64-bit block of data using a 64-bit key. Furthermore they propose a way to build private versions of LOKI.In this paper we show first that the keyspace of any LOKI-version is only 260, not 264 as claimed. Therefore there are 15 equivalent keys for every key, that encrypts/decrypts texts the same way. An immediate consequence is, that the proposed Single Block Hash Mode is no good. It is very easy to find collisions.Secondly we do differential cryptanalysis on LOKI and show that n-round LOKI, n≤14 is vulnerable to this kind of attack, at least in principle. We show that we cannot find a characteristic with a probability high enough to break LOKI with 16 rounds. However one might find a private LOKI-version, that is vulnerable to a differential attack for n=16.

Differential Cryptanalysis is currently the most powerful tool available for analysing block ciphers, and new block ciphers need to be designed to resist it. It has been suggested that the use of S-boxes based on bent functions, with a flat XOR profile, would be immune. However our studies of differential cryptanalysis, particularly applied to the LOKI cipher, have shown that this is not the case. In fact, this results in a relatively easily broken scheme. We show that an XOR profile with carefully placed zeroes is required. We also show that in order to avoid some variant forms of differential cryptanalysis, permutation P needs to be chosen to prevent easy propagation of a constant XOR value back into the same S-box. We redesign the LOKI cipher to form LOKI91, to illustrate these results, as well as to correct the key schedule to remove the formation of equivalent keys. We conclude with an overview of the security of the new cipher.

Differential cryptanalysis introduced by Biham and Shamir in 1990 is one of the most powerful attacks to DES-like cryptosystems. This attack presumes on some tendency of the target cryptosystem. So the efficiency of the attack depends upon the conspicuousness of this tendency. S/N ratio introduced in the paper is to evaluate this conspicuousness. In other words, the S/N ratio is a measure of the efficiency of the attack. Nevertheless, S/N ratio does NOT suggest how many pairs of ciphertexts are needed.In this paper, we show how to estimate the number of necessary pairs of ciphertexts for the differential cryptanalysis. We also show that our estimation is adequate using the 8-round-DES as an example. Biham and Shamir also showed a counting scheme to save memories at the cost of efficiency. We show an algorithm to find the secret key saving memories at the less cost of efficiency.

In this paper, we present how to construct DES-like S-boxes based on Boolean functions satisfying the Strict Avalanche Criterion and compare their cryptographic properties with those of DES S-boxes in various points of view. We found that our designed DES-like S-boxes exhibit better cryptographical properties than those of DES S-boxes.

The so called selected permutations, which can be used to compose S-boxes in the DES-like ciphers, are classified under the action of a transformation group G*. A method for building up a data base of the selected permutations is given. In fact, we have built up a data base which consists of one representative from each of the G*-equivaIent classes, it turns out that the data base is of size 17433 and can be easily memorized by the help of a small magnetic disc. The constructed data base together with the applications of the group G* will produce totally 17433×3×29 selected permutations, which can be used to provide ready raw material for composing S-boxes.

At Crypto '89 Ivan Damgård [1] presented a method that allows one to construct a computationally collision free hash function that has provably the same level of security as the computationally collision free function with input of constant length that it is based upon. He also gave three examples of collision free functions to use in this construction. For two of these examples collisions have been found[2]

Much effort has been spent to identify the hard bits of one way functions, such as RSA and Rabin encryption functions. These efforts have been restricted to O(log n) hard bits. In this paper, we propose practical solutions for constructing a family of strong one way permutations such that when a member is chosen uniformly at random, with a high probability we get a one way permutation m, with t<n −O(log n), the maximum number of simultaneous hard bits. We propose two schemes. In the first scheme m is constructed with O(log n) fold iteration of f o g, where f is any one way permutation, g ∈ _r G and G is a strongly universal₂ family of polynomials in Galois field. In the second scheme m = f o g o h, where h is a hiding permutation. We suggest a practical solution based on this scheme. The strong one way permutations can be applied as an efficient tool to build pseudorandom bit generators and universal one way hash functions.

In this paper, first, we have defined the weak claw free family and strong claw free family. Next we have given sufficient conditions for the existence of weak and strong claw free families.

This paper presents a new concept in cryptography called the sibling intractable function family (SIFF) which has the property that given a set of initial strings colliding with one another, it is computationally infeasible to find another string that would collide with the initial strings. The various concepts behind SIFF are presented together with a construction of SIFF from any one-way function. Applications of SIFF to many practical problems are also discussed. These include the hierarchical access control problem which is a long-standing open problem induced by a paper of Akl and Taylor about ten years ago, the shared mail box problem, access control in distributed systems and the multiple message authentication problem.

We show the sequential multisignature scheme based on the Fiat-Shamir scheme which is a slight variant of simultaneous multisignature scheme, and discuss the security of a digital multisignature scheme. The following properties are proven;(1)The difficulty of deriving secret information from public information in a multisignature scheme with already used signatures is equivalent to that of deriving it in a single signature scheme; and(2)The difficulty of forging a partial multisignature so that the total multisignature is valid is equivalent to that of deriving a single signature in the Fiat-Shamir scheme.

A new secret sharing scheme is presented in this paper to realize the generalized secret sharing policy. Different from most of previous works, it is computationally secure and each participant holds only one single shadow. Any honest participant in this scheme can detect and identify who is cheating even when all of the other participants corrupt together. An extended algorithm is also proposed to protect the secret form dishonest participant without the assumption of simultaneous release of the shadows. With (x,x)-homomorphism property, it can also be used to protect individual secrets while revealing the product of these secrets.

In a threshold cryptosystem, one can send an encrypted message to a group without knowing the internal secret sharing policy of the group. The encrypted ciphertext can only be deciphered by some users of the group according to the secret sharing policy. In this paper, we propose solutions to handle the generalized secret sharing policy. In addition, we investigate two different models for the group: one with a mutually trusted party in the group and the other one without.

In this paper we generalise Luby-Rackoff construction of pseudorandom permutation generators to generalised invertible function generators and prove that if there exits a generalised pseudorandom function generator then there exist a generalised pseudorandom invertible generator. This construction is then used for a pseudorandom authentication code which offers provable security against T-fold chosen plaintext/ciphertext attack and provable perfect protection against strong spoofing of order T. The performance of the code is compared with that of a code obtained from a Feistel type permutation generator. The code, called Feistel type A-code, provides a new approach to the design of practically good A-codes and hence is of high practical significance.

In this paper, we introduce the recent development of cryptologic research in Korea since 1989. Two workshops on information security and cryptology and a symposium on data security have been held. The Korea Institute of Information Security and Cryptology (KIISC) was organized in December 1990. The KIISC is playing a leading role for promoting research activities on cryptology in Korea. Since Japan is very active in the area of cryptologic research and development since 1984, it is worth to include Japanese research activities in this paper. Also, the recent cryptologic research activities in the Republic of China (Taiwan) are introduced.With regard to the research activities from other nations in Asia, it is unfortunate not to compile their activities in this issue due to the lack of information available at the present time.

In this paper, we present the necessary and sufficient conditions for super pseudorandomness of DES-like permutations. We show that four rounds of such permutations with a single random function is not super psuedorandom and we present a distinguishing circuit for ψ(f2, f, f, f) and another circuit for ψ(fl, fk, fj, fi). Then, we investigate the necessary and sufficient conditions for super pseudorandomness of type-1 Feistel type transformations, and we show that k2 rounds of this transformation is super pseudorandom.

Shannon defined a random cipher as a collection of randomly chosen permutations, one for each value of the key.We suggest a scheme for a block cipher which uses only one randomly chosen permutation, F. The key, consisting of two blocks, K₁ and K₂ is used in the following way: The message block is XORed with K₁ before applying F, and the outcome is XORed with K₂, to produce the cryptogram block. This removes the need to store, or generate a multitude of permutations.Although the resulting cipher is not random, we claim that it is secure. First, it is shown that if F is chosen randomly then, with high probability the scheme is secure against any polynomial-time algorithmic attack. Next, it is shown that if F is chosen pseudorandomly, the system remains secure against oracle-type attacks.The scheme may lead to a system more efficient than systems such as the DES and its siblings, since the designer has to worry about one thing only: How to implement one pseudorandomly chosen permutation. This may be easier than getting one for each key.

The work examines a class of randomizers built using concatenation of several layers of Luby-Rackoff elementary randomizers. First we examine some properties of Luby and Rackoff randomizers. Next we discuss the quality of randomizers with the concatenation of several Luby-Rackoff randomizers. Finally, the main result of the work is presented which proves that the concatenation of two layers of modified L-R randomizers is a perfect randomizer.

The security of DES-style block ciphers rests largely upon their non-linear S-boxes. If different pairs of input data and key can produce identical inputs to all of a cipher's S-boxes, then for those pairs the system is weakened. A technique is described here which enables a cryptanalyst to find how many of these pairs, if any, exist for a given cryptosystem, and how to exploit those pairs under a chosen plaintext attack.

The closure tests, CCT and MCT, were introduced to analyze the algebraic properties of cryptosystems by Kaliski et al. [KaRiSh]. If a cryptosystem is closed, the tests give the same results “Fail” and the cryptosystem might be breakable. Though CCT requires much less memory and time than MCT, we cannot apply CCT to check cryptosystems having the same data and key block lengths such as FEAL with non-parity mode. Because CCT utilizes the differences in data and key block lengths.Though CCT experiments performed by Kaliski et al. detected that DES is not closed, how should FEAL be checked? Does FEAL pass in MCT? Since MCT needs a lot of memory and time, to check FEAL, we developed a switching closure test SCT [MoOhMi], which is practical version of MCT. In this paper, by using SCT, it is confirmed that FEAL is not closed with high probability.

At the Eurocrypt'88 meeting, Koyama and Ohta proposed a conference key distribution scheme, which was an improved protocol of their earlier version. The authors show that their schemes, constructed for star and complete graph networks, are not secure. Another key distribution scheme, which can be used for conference key distribution, proposed at the Globecom'90 meeting by Chikazawa and Inoue, is not secure either.

In this paper, a private-key cryptosystem equivalent to the private-key cryptosystem proposed by Rao and Nam is analyzed. The main result is that the private-key cryptosystem is vulnerable to a so-called extended majority vote attack. This attack can be averted if one selects the predefined set of error vectors at random. As a consequence, the error vector generating process will become much easier.

A secure technique for analog speech encryption is described which uses the Discrete Cosine Transform (DCT). The paper shows how the proposed technique overcomes weaknesses identified in other analog scramblers by using transform domain permutation and the insertion of dummy transform components. It is shown that the DCT scrambler with dummy spectrum insertion offers a similar level of security to a digital scrambler on a bandlimited channel while providing better quality of recovered speech.

The oblivious transfer protocol is a powerful tool in the design of cryptographic applications, such as coin flipping by the telephone, exchanging secrets and sending certified mail. In this paper, for our purpose of extending the oblivious transfer to the exchange of secrets, we redefine a verifiable oblivious transfer protocol which has the three properties of fairness, verifiability and security. The structure of the protocols is similar to the original protocols proposed by Rabin and Blum. The major difference is that our protocols are based on the difficulty of the discrete logarithm.

This paper presents a 4-move perfect ZKIP of knowledge with no cryptographic assumption for the random self reducible problems [TW87] whose domain is NP∩BPP. The certified discrete log problem is such an example. (Finding a witness is more difficult than the language membership problem.) A largely simplified 4-move ZKIP for the Hamilton Circuit problem is also shown. In our ZKIP, a trapdoor coin flipping protocol is introduced to generate a challenge bit. P and V cooperatively generate a random bit in a coin flipping protocol. In a trapdoor coin flipping protocol, V who knows the trapdoor can create the view which he can later reveal in two possible ways: both as head and as tail.

In this paper, we show that if a relation R has a three move blackbox simulation zero-knowledge interactive proof system of possession of knowledge, then there exists a probabilistic polynomial time algorithm that on input x ∈ {0,1}*, outputs y such that (x, y) ∈ R with overwhelming probability if x ∈ dom R, and outputs “⊥” with probability 1 if x ∉ dom R. In the present paper, we also show that without any unproven assumption, there exists a four move blackbox simulation perfect zero-knowledge interactive proof system of possession of the prime factorization, which is optimal in the light of the round complexity.

We show that any language that has a two-locally-random reduction in which the target functions are boolean is in NP/poly∩co-NP/poly. This extends and simplifies a result by Yao.

In this note we study two cryptographic notions introduced in recent years: zero-knowledge proof systems [GMR] and instance-hiding schemes [AFK]. Addressing an open problem of [BFS] and extending the work in [AFK], we show that, if one-way permutations exist, the following two statements are equivalent for any function f:(i)f has a one-prover, instance-hiding, zero-knowledge proof system.(ii)f is computable in polynomial space and has an instance-hiding scheme that leaks at most the length of the input.

We present an interactive zero-knowledge proof for the discrete logarithm problem which is based on smooth numbers. The main feature of our proof is its communication complexity (number of messages exchanged, number of bits communicated) which is less than that of competing schemes.

This paper presents an extension (or relaxation) of zero-knowledge proofs, called oracle-simulation zero-knowledge proofs. It is based on a new simulation technique, called no-knowledge-release-oracle simulation, in which, roughly speaking, the view of the history of an interactive proof is simulated by the poly-time machine (simulator) with the help of an oracle which does not release any knowledge to the simulator. We show that, assuming the existence of a secure bit-commitment, any NP language has a three round oracle-simulation zero-knowledge proof, which is obtained by combining a public-coin-type zero-knowledge proof and a coin-flip protocol. This result is very exciting given the previously known negative result on the conventional zero-knowledge proofs, such that only BPP languages can have three round black-box-simulation zero-knowledge proofs. We also show some applications of this notion to identification systems based on digital signature schemes.

A notion of “divertible” zero-knowledge interactive proof systems was introduced by Okamoto and Ohta, and they showed that for any commutative random self-reducible relation, there exists a divertible (perfect) zero-knowledge interactive proof system of possession of information. In addition, Burmester and Desmedt proved that for any language L ∈ $$\mathcal{N}\mathcal{P}$$ , there exists a divertible zero-knowledge interactive proof system for the language L under the assumption that probabilistic encryption homomorphisms exist. In this paper, we classify the notion of divertible into three types, i.e., perfectly divertible, almost perfectly divertible, and computationally divertible, and investigate which complexity class of languages has a perfectly (almost perfectly) (computationally) divertible zero-knowledge interactive proof system. The main results in this paper are: (1) there exists a perfectly divertible perfect zero-knowledge interactive proof system for graph non-isomorphism (GNI) without any unproven assumption; and (2) for any language L having an interactive proof system, there exists a computationally divertible computational zero-knowledge interactive proof system for the language L under the assumption that probabilistic encryption homomorphisms exist.

In this paper, we propose a multi-purpose proof system which allows a user to perform various proof protocols needing to remember only one piece of secret data. These proofs include identity proof, membership proof without revealing one's identity, and combined identity and membership proof. When a user participates in a group, he will obtain a secret witness corresponding to the group's name from some administrator of the group. Using the secret witness, the user can prove his membership in this group. Many secret witnesses can be combined into one piece of secret data. From the secret data, the user can obtain the secret witness of the group he participates in. If the user participates in a new group afterward, he can also easily update his secret data. But the size of the secret data is independent of the number of the groups in which the user participates. Our system satisfies other desirable properties which were not attained by the previously proposed systems.

We introduce an original method to verify probabilistic properties in cryptographic protocols. This method uses the representation of participants' knowledge that we presented at CRYPTO'91. The modelization is based on the assumption that the underlying cryptographic system is perfect and is an extension of the “Hidden Automorphism Model” introduced by Merritt.

This paper gives a survey of the relationship between the fields of cryptography and machine learning, with an emphasis on how each field has contributed ideas and techniques to the other. Some suggested directions for future cross-fertilization are also proposed.

We present various ways of speeding up the standard methods for generating provable, resp. probable primes. For probable primes, the effect of using test division and 2 as a fixed base for the Rabin test is analysed, showing that a speedup of almost 50% can be achieved with the same confidence level, compared to the standard method. For Maurer's algorithm generating provable primes p, we show that a small extension of the algorithm will mean that only one prime factor of p−1 has to be generated, implying a gain in efficiency. Further savings can be obtained by combining with the Rabin test. Finally, we show how to combine the algorithms of Maurer and Gordon to make ”strong provable primes” that satisfy additional security constraints.

A server-aided secret computation protocol (SASC) is a method that allows a client (e.g. smart card) to compute a function efficiently with the aid of a powerful server (e.g. computer) without revealing the client's secrets to the server. Matsumoto et al. proposed a solution to the problem which is suitable for the RSA cryptosystem. Kawamura et al. have shown that a client, with a 105 times more powerful server's aid, can compute an RSA signature 50 times faster than the case without a server if the communication cost can be ignored. In this paper, we propose two SASC protocols based on the addition sequence to improve the efficiency. In the first protocol, since the addition sequence is determined by the server, it can improve the computational efficiency of the server only and it is suitable for the low speed communication link (e.g. 9.6 Kbps). It is expected that a client, with an 8982 times more powerful server's aid, can compute an RSA signature 50 times faster than the case without a server. In the second protocol, since the addition sequence is determined by the client, it can improve the computational efficiency of the client and server simultaneously but takes more communication time and it is suitable for the high speed communication link (e.g. above 10 Mbps). It is expected that a client, with a 3760 times more powerful server's aid, can compute an RSA signature 200 times faster than the case without a server.

Recently, a method, reducing the elliptic curve discrete logarithm problem(EDLP) to the discrete logarithm problem(DLP) in a finite field, was proposed. But this reducing is valid only when Weil pairing can be defined over the m-torsion group which includes the base point of EDLP. If an elliptic curve is ordinary, there exists EDLP to which we cannot apply the reducing. In this paper, we investigate the condition for which this reducing is invalid. We show the next two main results.(1) For any elliptic curve E defined over F₂r, we can reduce EDLP on E, in an expected polynomial time, to EDLP that we can apply the MOV reduction to and whose size is same as or less than the original EDLP. (2) For an ordinary elliptic curve E defined over F _p (p is a large prime), EDLP on E cannot be reduced to DLP in any extension field of F _p by any embedding. We also show an algorithm that constructs such ordinary elliptic curves E defined over F _p that makes reducing EDLP on E to DLP by embedding impossible.

At the last Eurocrypt meeting, a cryptosystem based on modular knapsacks was proposed (see [11]). We show that this system is not secure, and we describe two different ways of breaking it using the LLL algorithm. This is one more example of a cryptosystem that can be broken using this powerful algorithm (see [1, 13, 14]). For more details, the reader should refer to [4].

A method is described to generate collisions for the hash function FFT-Hash that was presented by Claus Schnorr at Crypto '91. A set of colliding messages is given that was obtained by this method.

The proposal by NIST/NSA of a digital signature standard has some positive aspects, but is marred by serious flaws. Most notably, it is not sufficiently secure for a standard and seems vulnerable to “trapdoors.”

I present a new attack of FEAL-4 blockcipher. The attack requires only 24 blocks of 8-byte randomly given known-plaintext. Using these blocks, we can break FEAL-4 with the probability of greater than 90%, in 14 seconds on a personal computer (cpu 80386 16MHz). It is based on the system of linear equations on the differences.

One aspect of differential cryptanalysis that appears to have been largely overlooked is the use of several differences to attack a cipher simultaneously. While the use of quartets and octets have been briefly described by Biham and Shamir [1], this was not carried to its logical conclusion — namely, how many different attacks can you use and still get an improvement. The issues involved are briefly covered here.

In [1] a construction of a block cipher from a single pseudorandom permutation is proposed. In a complexity theoretical setting they prove that this scheme is secure against a polynomially bounded adversary. In this paper it is shown that this construction suffers from severe limitations that are immediately apparent if differential cryptanalysis [3] is performed. The fact that these limitations do not contradict the theoretical results obtained in [1] leads the authors to question the relevance of computational complexity theory in practical conventional cryptography.