Advances in Cryptology — CRYPTO’ 89 Proceedings

The German navy prepared keys for the Enigma cipher machine that was the Wehrmacht’s standard cryptographic system in a manner different from the army and the air force. They permitted the encipherers to select “random” starting positions of the rotors. The navy, on the other hand, prescribed these positions in keys when, in 1926, it adopted the Enigma. The motive for this is not known, but it proved superior to the other method, which was often compro- mised by the encipherers’ using as settings three-letter sequences from the type- writer keyboard (QWE and RFV, for example) or from girlfriends’ names or from obscene words. The consequence was that while Luftwaffe cryptograms in par- ticular were read by the enemy early on, the Kriegsmarine Enigma defended its messages far better. Only when the British captured important keying docu- ments could they begin to crack German naval messages.

[Sim84] introduced the concept of subliminal channel in the context of signature systems. [Des88b] presented a solution against subliminal channels and extended in [Des88a] the solution to abuse-free coin-flipping, abuse-free generation of public keys, and abuse-free zero-knowledge. In this paper we demonstrate that a whole family of systems (generalized Arthur-Merlin games) can be made abuse-free, avoiding the exhaustive approach of [Des88a]. We will hereto formalize the concept of abuse.

It has been proved earlier that the existence of bit commitment schemes (blobs) implies the existence of zero-knowledge proofs of information possession, which are MA-protocols (i.e. the verifier sends only independent random bits) [BrChCr], [GoMiWi].In this paper we prove the converse result in a slightly modified form: We define a concept called weakly zero-knowledge, which is like ordinary zero-knowledge, except that we only require that an honest verifier learns nothing from the protocol. We then show that if, using an MA-protocol, P can prove to V in weakly zero-knowledge that he possesses a solution to some hard problem, then this implies the existence of a bit commitment scheme. If the original protocol is (almost) perfect zero-knowledge, then the resulting commitments are secure against an infinitely powerful receiver.Finally, we also show a similar result for a restricted class of non-MA protocols.

The normal use of cryptography in unclassified computing systems often fails to provide the level of protection that the system designers and users would expect. This is partially caused by confusion of cryptographic keys and user passwords, and by un- derestimations of the power of known plaintext attacks. The situation is worsenned by performance constraints and occasionally by the system builder’s gross misunderstand- ings of the cryptographic algorithm and protocol.

In a workstation environment, the user often has complete control over the worksta- tion. Workstation operating systems therefore cannot be trusted to accurately identify their users. Some other method of authentication is needed, and this motivated the design and implementation of the Kerberos authentication service.Kerberos is based on the Needham and Schroeder trusted third-party authentication model, using private-key encryption. Each user and network server has a key (like a password) known only to it and the Kerberos database. A database server uses this knowledge to authenticate network entities to one another.The encryption used to achieve this authentication, the protocols currently in use and the protocols proposed for future use are described.

Passwords in the UNIX operating system are encrypted with the crypt algorithm and kept in the publicly-readable file /etc/passwd. This paper examines the vulnerability of UNIX to attacks on its password system. Over the past 10 years, improvements in hardware and software have increased the crypts/second/dollar ratio by five orders of magnitude. We reexamine the UNIX password system in light of these advances and point out possible solutions to the problem of easily found passwords. The paper discusses how the authors built some high-speed tools for password cracking and what elements were necessary for their success. These elements are examined to determine if any of them can be removed from the hands of a possible system infiltrator, and thus increase the security of the system. We conclude that the single most important step that can be taken to improve password security is to increase password entropy.

Z is a software system designed to provide media-transparent net- work services on a collection of UNIX® machines. These services are comprised of file transfer and command execution; Z preserves file own- ership on remote transfer, and more significantly, owner and group iden- tity when executing commands remotely. In order to secure known vulner- abilities in the system, enhancements were made. In particular, a cryptographically-derived checksum was added to the messages. After the initial implementation of the checksumming scheme, several iterations of performance improvement occurred. The result was unsatisfactory to the user community, so the checksum was removed. Instead, vulnerabilities were reduced by improved monitoring and maintenance procedures.

It is becoming increasingly common for large, distributed systems to utilise personal computers (PC’s) for the purpose of user access, and hence the security arrangements for such an access point have become a focus of attention in systems security design. Generally speaking the functional requirements of a PC security sub-system are as follows:- (i)Identity verification of the user, for controlling access both to resources within the local PC workstation and to remote teleprocessing services on other machines.(ii)File encryption at the PC for secure storage.(iii)Message encryption and message authentication for secure communications.(iv)Digital signatures for proof of origin of communications and for data and software certification.

Random binaxy sequences are required in many applications of modern communi- cation systems and in designing reliable circuits. However, truly random sequences are often associated with extremely high costs, and are therefore infeasible to use. Deter- ministically generated sequences that pass certain statistical tests suggested by random sequences are often used instead and are referred to as pseudorandom sequences. In applications involving, for instance, secure or spread spectrum communications, it is essential that these pseudorandom sequences be unpredictable. This paper addresses the problem of predicting the terms of a pseudorandom sequence from some initial por- tion of the sequence. A good introduction to the issues involved in this area can be found in [7].

In this paper the problem of finding the absolutely shortest (possibly nonlin- ear) feedback shift register, which can generate a given sequence with characters from some arbitrary finite alphabet, is considered. To this end, a new complex- ity measure is defined, called the maximum order complexity. A new theory of the nonlinear feedback shift register is developed, concerning elementary complexity properties of transposed and reciprocal sequences, and feedback functions of the maximum order feedback shift register equivalent. Moreover, Blumer’s algorithm is identified as a powerful tool for determining the maxi- mum order complexity profile of sequences, as well as their period, in linear time and memory. The typical behaviour of the maximum order complexity profile is shown and the consequences for the analysis of given sequences and the synthesis of feedback shift registers are discussed.

The concept of provable cryptographic security for pseudo-random number generators that was introduced by Schnorr is investigated and extended. The cryptanalyst is assumed to have infinite computational resources and hence the security of the generators does not rely on any unproved hypothesis about the difficulty of solving a certain problem, but rather relies on the assumption that the number of bits of the generated sequence the enemy can access is limited. The concept of perfect local randomness of a sequence generator is introduced and investigated using some results from coding theory. The theoretical and practical cryptographic implications of this concept are discussed. Possible extensions of the concept of local randomness as well as some applications are proposed.

Pseudorandom distributions on n-bit strings are ones which cannot be effi- ciently distinguished from the uniform distribution on strings of the same length. Namely, the expected behavior of any polynomial-time algorithm on a pseudorandom input is (almost) the same as on a random (i.e. uniformly chosen) input. Clearly, the uni- form distribution is a pseudorandom one. But do such trivial cases exhaust the notion of pseudorandomness? Under certain intractability assumptions the existence of pseudoran- dom generators was proven, which in turn implies the existence of non-trivial pseudoran- dom distributions. In this paper we investigate the existence of pseudorandom distribu- tions, using no unproven assumptions.We show that sparse pseudorandom distributions do exist. A probability distribu- tion is called sparse if it is concentrated on a negligible fraction of the set of all strings (of the same length). It is shown that sparse pseudorandom distributions can be gen- erated by probabilistic (non-polynomial time) algorithms, and some of them are not sta- tistically close to any distribution induced by probabilistic polynomial-time algorithms.Finally, we show the existence of probabilistic algorithms which induce pseudoran- dom distributions with polynomial-time evasive support. Any polynomial-time algorithm trying to find a string in their support will succeed with negligible probability. A conse- quence of this result is a proof that the original definition of zero-knowledge is not robust under sequential composition. (This was claimed before, leading to the introduction of more robust formulations of zero-knowledge.)

We show how a pseudo-random generator can provide a bit commitment protocol. We also analyze the number of bits communicated when parties commit to many bits simultaneously, and show that the assumption of the existence of pseudo-random generators suffices to assure amortized O(1) bits of communication per bit commitment.

In this paper we show how to predict a large class of pseudorandom number generators. We consider congruential generators which output a sequence of integers s₀,s₁,... where s_i is computed by the recurrence 1$$ s_i \equiv \sum\limits_{j = 1}^k {\alpha _j \Phi _j (s_0 ,s_1 , \cdots ,s_{i - 1} )(\bmod m)} $$ for integers m and α_j, and integer functions Φ_j, j= 1,...,k. Our predictors are efficient, provided that the functions Φ_j are computable (over the integers) in polynomial time. These predictors have access to the elements of the sequence prior to the element being predicted, but they do not know the modulus m or the coefficients α_j the generator actually works with. This extends previous results about the predictability of such generators. In particular, we prove that multivariate polynomial generators, i.e. generators. where s_i ≡ P(s_i-n,..., s_i-1) (mod m), for a polynomial P of fixed degree in n variables, are efficiently predictable.

A critical analysis of the modified cryptographic checksum algorithm of Cohen and Huang points out some weaknesses in the scheme. We show how to exploit these weaknesses with a chosen text attack to derive the first bits of the key. This information suffices to manipulate blocks with a negligible chance of detection.

In this paper, we give at first a precise estimation for the consistency probability of a system of linear algebraic equations Ax = b with random m × n coefficient matrix A, m > n, and fixed non-zero right side b. A new test in cryptanalysis is then formulated on the basis of the estimation and applied to at- tack the multiplexing generator of Jennings (1980) and the multiple-speed gen- erator of Massey-Rueppel (1984). Some security remarks concerning the perfect linear cipher of the latter authors are also made.

Number theoretic cryptographic algorithms are all based upon modular mul- tiplication modulo some composite or prime. Some security parameter n is set (the length of the composite or prime). Cryptographic functions such as digi- tal signature or key exchange require O(n) or O(√n) modular multiplications ([DH, RSA, R, E, GMR, FS], etc.).This paper proposes a variant of the RSA scheme which requires only polylog(n) (O(log2n)) modular multiplications per RSA operation. Inherent to the scheme is the idea of batching, i.e., performing several encryption or signature operations simultaneously. In practice, the new variant effectively performs several modular exponentiations at the cost of a single modular ex- ponentiation. This leads to a very fast RSA-like scheme whenever RSA is to be performed at some central site or when pure-RSA encryption (vs. hybrid encryption) is to be performed.An important feature of the new scheme is a practical scheme that isolates the private key from the system, irrespective of the size of the system, the number of sites, or the number of private operations that need be performed.

A family of elliptic curves for cryptographic use is proposed for which the determination of the order of the corresponding algebraic group is much easier than in the general case. This makes it easier to meet the cryptographic requirement that this order have a large prime factor. Another advantage of this familiy is that the group operation simplifies slightly. Explicit numerical examples are given that are suitable for practical use.

Using non-interactive zero knowledge proofs we provide a simple new para- digm for diǵital signing and message authentication secure against adaptive chosen message attack.For digital signatures we require that the non-interactive zero knowledge proofs be publicly verifiable: they should be checkable by anyone rather than directed at a particular verifier. We accordingly show how to implement non- interactive zero knowledge proofs in a network which have the property that anyone in the network can individually check correctness while the proof is zero knowledge to any sufficiently small coalition. This enables us to implement signatures which are history independent.

Digital signatures [DH]—unlike handwritten signatures and banknote printing—are easily copied exactly. This property can be advantageous for some uses, such as dissemination of announcements and public keys, where the more copies distributed the better. But it is unsuitable for many other applications. Consider electronic replacements for all the written or oral commitments that are to some extent personally or commercially sensitive. In such cases the proliferation of certified copies could facilitate improper uses like blackmail or industrial espionage. The recipient of such a commitment should of course be able to ensure that the issuer cannot later disavow it—but the recipient should also be unable to show the commitment to anyone else without the issuer’s consent.

A practical digital signature system based on a conventional encryption function which is as secure as the conventional encryption function is described. Since certified conventional systems are available it can be implemented quickly, without the several years delay required for certification of an untested system.

We present an efficient interactive identification scheme and a related signature scheme that are based on discrete logarithms and which are particularly suited for smart cards. Previous cryptoschemes, based on the discrete logarithm, have been proposed by El Gamal (1985), Chaum, Evertse, Graaf (1988), Beth (1988) and Günter (1989). The new scheme comprises the following novel features.

This paper presents a signature scheme for a single user or a group of users. The shared verification of such a signature uses the principle of threshold schemes. The constructions are based on a special class of finite incidence struc- tures, so called generalised quadrangles.

We introduce and exemplify the new concept of ON-LINE/OFF-LINE digital signature schemes. In these schemes the signing of a message is broken into two phases. The first phase is off-line. Though it requires a moderate amount of compu- tation, it presents the advantage that it can be performed leisurely, before the message to be signed is even known. The second phase is on-line. It starts after the message becomes known, it utilizes the precomputation of the first phase and is much faster.A general construction which transforms any (ordinary) digital signature scheme to an on-line/off-line signature scheme is presented, entailing a small overhead. For each message to be signed, the time required for the off-line phase is essentially the same as in the underlying signature scheme; the time required for the on-line phase is essentially negligible. The time required for the verification is essentially the same as in the underlying signature scheme.In a practical implementation of our general construction, we use a variant of Rabin’s signature scheme (based on factoring) and DES. In the on-line phase, all we use is a moderate amount of DES computation. This implementation is ideally suited for electronic wallets or smart cards.On-line/Off-line digital schemes may also become useful in case substantial pro- gress is made on, say, factoring. In this case, the length of the composite numbers used in signature schemes may need to be increased and signing may become imprac- tical even for the legitimate user. In our scheme, all costly computations are per- formed in the off-line stage while the time for the on-line stage remains essentially unchanged.An additional advantage of our method is that in some cases the transformed signature scheme is invulnerable to chosen message attack even if the underlying (ordinary) digital signature scheme is not In particular, it allows us to prove that the existence of signature schemes which are unforgeable by known message attack is a (necessary and) sufficient condition for the existence of signature schemes which are unforgeable by chosen message attack.

In a secret sharing scheme, a dealer has a secret key. There is a finite set P of participants and a set Γ of subsets of P. A secret sharing scheme with Γ as the access structure is a method which the dealer can use to distribute shares to each participant so that a subset of participants can determine the key if and only if that subset is in Γ. The share of a participant is the information sent by the dealer in private to the participant. A secret sharing scheme is ideal if any subset of participants who can use their shares to determine any information about the key can in fact actually determine the key, and if the set of possible shares is the same as the set of possible keys. In this paper, we show a relationship between ideal secret sharing schemes and matroids.

This paper investigates the characterizations of threshold /ramp schemes which give rise to the time-dependent threshold schemes. These schemes are called the “dynamic threshold schemes” as compared to the conventional time-independent threshold scheme. In a (d, m, n, T) dynamic threshold scheme, there are n secret shadows and a public shadow, pj, at time t=t_j, 1≤t_j≤T. After knowing any m shadows, m≤n, and the public shadow, pj, we can easily recover d master keys, k₁j, K₂j, ..., and K_dj. Furthermore, if the d master keys have to be changed to $$ K\begin{array}{*{20}c} {j + 1} \\ 1 \\ \end{array} ,K\begin{array}{*{20}c} {j + 1} \\ 2 \\ \end{array} ,...,and\,K\begin{array}{*{20}c} {j + 1} \\ d \\ \end{array} $$ for some security reasons, only the public shadow, pj, has to be changed to pj+1. All the n secret shadows issued initially remain unchanged. Compared to the conventional threshold/ramp schemes, at least one of the previous issued n shadows need to be changed whenever the master keys need to be updated for security reasons. A (1, m, n, T) dynamic threshold scheme based on the definition of cross-product in an N- dimensional linear space is proposed to illustrate the characterizations of the dynamic threshold schemes.

A (k, n) secret sharing scheme is a probabilistic mapping of a secret to n shares, such that The secret can be reconstructed from any k shares.No subset of k − 1 shares reveals any partial information about the secret.Various secret sharing schemes have been proposed, and applications in diverse con- texts were found. In all these cases, the set of secrets and the set of shares are finite.In this paper we study the possibility of secret sharing schemes over infinite do- mains. The major case of interest is when the secrets and the shares are taken from a countable set, for example all binary strings. We show that no (k, n) secret sharing scheme over any countable domain exists (for any 2 ≤k ≤ n).One consequence of this impossibility result is that no perfect private-key encryp- tion schemes, over the set of all strings, exist. Stated informally, this means that there is no way to perfectly encrypt all strings without revealing information about their length.We contrast these results with the case where both the secrets and the shares are real numbers. Simple secret sharing schemes (and perfect private-key encryption schemes) are presented. Thus, infinity alone does not rule out the possibility of secret sharing.

In a society oriented cryptography it is better to have a public key for the company (organization) than having one for each individual employee [Des88]. Certainly in emergency situations, power is shared in many organizations. Solutions to this problem were presented [Des88], based on [GMW87], but are completely im- practical and interactive. In this paper practical non-interactive public key systems are proposed which allow the reuse of the shared secret key since the key is not revealed either to insiders or to outsiders.

We show how to create a master key scheme for controlling access to a set of services. Each master key is a concise representation for a list of service keys, such that only service keys in this list can be computed easily from the master key. Our scheme is more flexible than others, permitting hierarchical organization and expansion of the set of services.

A key distribution protocol is proposed for digital mobile communi- cation systems. The protocol can be used with a star-type network. User terminals have a constraint of being hardware-limited.Security of the protocol is discussed. A countermeasure is proposed to cope with a possible active attack by a conspiracy of two opponents.

In [3] Diffie and Hellman described a novel scheme by which two individuals could exchange a secret cryptographic key over a public channel. This scheme is based on the arithmetic in the multiplicative group Fx of a finite field F. It is secure because computing discrete logarithms in finite fields is a very hard problem. It has been noted subsequently by several authors (e.g. [1], [5], [6]) that any finite abelian group G may be used to replace Fx in this scheme as long as the discrete logarithm problem in G is difficult.

Zero Knowledge (ZK) theory formed the basis for practical identification and signature cryptosysems (invented by Fiat and Shamir). It also was used to construct a key distribution scheme (invented by Bauspiess and Knobloch); however, it seems that the ZK concept is less appropriate for key distribution systems (KDS), where the main cost is the number of communications. We propose relaxed criteria for the security of KDS, which we assert are sufficient, and present a system which meets most of the criteria. Our system is not ZK (it leaks few bits), but in return it is very simple. It is a Diffie-Hellman variation. Its security is equivalent to RS A, but it runs faster.Our definition for the security of KDS is based on a new definition of security for one-way functions recently proposed by Goldreich and Levin. For a given system and given cracking- algorithm, I, the cracking rate is roughly the average of the inverse of the running-time over all instances (if on some instance it fails, that inverse is zero). If there exists a function s:N→N, s.t. for all I, the cracking-rate for security parameter n is O (1)/s(n), then we say that the system has at least security s. We use this concept to define the security of KDS for malicious adversary (the passive adversary is a special case). Our definition of a malicious adversary is relatively restricted, but we assert it is general enough for KDS. This restriction enables the proof of security results for simple and practical systems. We further modify the definition to allow past keys and their protocol messages in the input data to a cracking algorithm. The resulting security functi on is called the “amortized security” of the system. This is justified by current usage of KDS, where the keys are often used with cryptosystems of moderate strength. We demonstrate the above properties on some Diffie-Hellman KDS variants which also authenticate the parties. In particular, we give evidence that one of the variants has super-polynomial security against any malicious adversary, assuming RSA modulus is hard to factor. We also give evidence that its amortized security is super-polynomial. (The original DH scheme does not authenticate, and the version with public directory has a fixed key, i.e. zero amortized security.)

The Secure Data Network System (SDNS) is intended to provide secure data communications to a variety of DoD and commercial users. SDNS services include key management and system management as well as data encryption, authentication and access control. The program is a U. S. Government/Industry effort, with participation by the National Security Agency, National Institute for Standards and Technology, other government agencies and about a dozen government contractors. During the concept definition and prototyping phases, a joint working group defined the set of security services to be provided and developed protocols for key management and for secure communications [1]. The protocols and architecture are compatible with the International Standards Organization (ISO) Reference Model for Open Systems Interconnection (OSI), and the end-to-end encryption (E3) protocols are being proposed as U.S. and international standards. The E3 protocols are publicly released and appropriate for the OSI environment.

Today, a dozen years after the discovery of the RSA encryption algorithm [12], there are many chips available for performing RSA encryption [1] [3] [4] [5] [8] [9] [13] [15]. The purpose of this paper is to briefly describe some of the different compu- tational algorithms that have been used in the chip designs and to provide a list of all of the currently available chips. In this abstract, we will simply mention some of these computational algorithms and give references. The full paper will contain more details of these algorithms and will appear in a book on survey articles in Cryptology which is being edited by Gus Simmons and will be published by IEEE in 1990.

This paper describes a method for computing a modular exponentiation, useful in performing the RSA Public Key algorithm, suitable for software or hardware implementation. The method uses conventional multiplication, followed by partial modular reduction based on sums of residues. We show that for a simple recursive system where the output of partial modular reduction is the input for the next multiplication, overflow presents few problems.

This paper presents a new fast compact modular-multiplication algorithm, which will multiply modulo N in log(N)/log(r) clock pulses when the algorithm is based on radix r (r ≥ 4).

Much current research focuses on fast evaluation of RSA, which consists of computing powers modulo a large number n. While some try to increase the speed of multiplica- tions, here we consider reducing the number of multiplications. In particular, we present a precomputation method that reduces the number of multiplications for the computation of a given power.

Given a cryptographic algorithm f (depending upon a fixed message m and a key k), a pair of keys with collision k₀ and k₁ (in short, a collision) are keys such that f(m,k₀) = f(m,k₁).The existence of collisions for a cryptographic algorithm means that this algorithm is not faithful in a precise technical sense (see [2]).

We show that if there exists a computationally collision free function f from m bits to t bits where m > t, then there exists a computationally collision free function h mapping messages of arbitrary polynomial lengths to t-bit strings.Let n be the length of the message. h can be constructed either such that it can be evaluated in time linear in n using 1 processor, or such that it takes time O(log(n)) using O(n) processors, counting evaluations of f as one step. Finally, for any constant k and large n, a speedup by a factor of k over the first construction is available using k processors.Apart from suggesting a generally sound design principle for hash functions, our results give a unified view of several apparently unrelated constructions of hash functions proposed earlier. It also suggests changes to other proposed constructions to make a proof of security potentially easier.We give three concrete examples of constructions, based on modular squaring, on Wolfram’s pseudoranddom bit generator [Wo], and on the knapsack problem.

One way hash functions are a major tool in cryptography. DES is the best known and most widely used encryption function in the commercial world today. Generating a one-way hash function which is secure if DES is a “good” block cipher would therefore be useful. We show three such functions which are secure if DES is a good random block cipher.

A cryptographic system, called PGM, was invented in the late 1970’s by S. Magliveras. PGM is based on the prolific existence of certain kinds of fac- torization sets, called logarithmic signatures, for finite permutation groups. Logarithmic signatures were initially motivated by C. Sims’ bases and strong generators. Statistical properties of random number generators based on PGM have been investigated in [7], [8] and show PGM to be statistically robust. In this paper we present recent results on the algebraic properties of PGM. PGM is an endomorphic cryptosystem in which the message space is Z_|G|, for a given finite permutation group G. We show that the set of PGM transformations T_G is not closed under functional composition and hence not a group. This set is 2-transitive on Z_|G| if the underlying group G is not hamiltonian. Moreover, if |G| ≠ 2a, then the set of transformations contains an odd permutation. An important consequence of the above results is that the group generated by the set of transformations is nearly always the full symmetric group.

One of the ultimate goals of cryptography researchers is to construct a (secrete-key) block cipher which has the following ideal properties: (1) The cipher is provably secure, (2) Security of the cipher does not depend on any unproved hypotheses, (3) The cipher can be easily implemented with current technology, and (4) All design criteria for the cipher are made public. It is currently unclear whether or not there really exists such an ideal block cipher. So to meet the requirements of practical applications, the best thing we can do is to construct a block cipher such thai it approximates the ideal one as closely as possible. In this paper, we make a significant step in this direction. In particular, we construct several block ciphers each of which has the above mentioned properties (2), (3) and (4) as well as the following one: (1’) Security of the cipher is supported by convincing evidence. Our construction builds upon profound mathematical bases for information security recently established in a series of excellent papers.

In this paper, we propose a new type of authentication system, disposable zero-knowledge authentication system. Informally speaking, in this authentication system, double usage of the same authentication is prevented. Based on these disposable zero-knowledge authentication systems, we propose a new untraceable electronic cash scheme satisfying both untraceability and unreusablity. This scheme overcomes the problems of the previous scheme proposed by Chaum, Fiat and Naor through its greater efficiency and provable security under reasonable cryptographic assumptions. We also propose a scheme, transferable untraceable electronic cash scheme, satisfying transferability as well as the above two criteria, whose properties have not been previously proposed in any other scheme. Moreover, we also propose a new type of electronic cash, untraceable electronic coupon ticket, in which the value of one piece of the electronic cash can be subdivided into many pieces.

We present two efficient identification schemes based on the difficulty of solving the subset sum problem and the circuit satisfiability problem. Both schemes use the two prover model introduced by [BGKW], where the verifier (e.g the Bank) interacts with two untrusted provers (e.g two bank identification cards) who have jointly agreed on a strategy to convince the verifier of their identity. To believe the validity of their identity proving procedure, the verifier must make sure that the two provers can not communicate with each other dur- ing the course of the proof process. In addition to the simplicity and efficiency of the schemes, the resulting two prover interactive proofs can be shown to be perfect zero knowledge, making no intractability assumptions.

The fact that there axe zero-knowledge proofs for all languages in NP has, potentially, enormous implications to cryptography. For cryptographers, the issue is no longer “which languages in NP have zero-knowledge proofs” but rather “which languages in NP have practical zero-knowledge proofs”. Thus, the concrete complexity of zero-knowledge proofs for different languages must be established.In this paper, we study the concrete complexity of the known general meth- ods for constructing zero-knowledge proofs. We establish that circuit-based methods have the potential of producing proofs which can be used in prac- tice. Then we introduce several techniques which greatly reduce the concrete complexity of circuit-based proofs. In order to show that our protocols yield proofs of knowledge, we show how to extend the Feige-Fiat-Shamir definition for proofs of knowledge to the model of Brassard-Chaum-Crépeau. Finally, we present techniques for improving the efficiency of protocols which involve arith- metic computations, such as modular addition, subtraction, and multiplication, and greatest common divisor.

We construct constant round ZKIPs for any NP language, under the sole assumption that oneway functions exist. Under the stronger Certified Discrete Log assumption, our construction yields perfect zero knowledge protocols. Our protocols rely on two novel ideas: One for constructing commitment schemes, the other for constructing subprotocols which are not known to be zero knowl- edge, yet can be proven not to reveal useful information.

What are the resources of a zero-knowledge Proof? Interaction, communication, and en- velops. That interaction, that is the number of rounds of a protocol, is a resource is clear. Actually, it is not a very available one: having someone on the line to answer your questions all the time is quite a luxury. Thus, minimizing the number of rounds in zero-knowledge proofs will make these proofs much more attractive from a practical standpoint. That communication, that is the number of bits exchanged in a protocol, is a resource is also immediately clear. Perhaps, what is less clear is why envelopes are a resource. Let us explain why this is the case.

We show how to implement oblivious transfer without interaction, through the medium of a public file. As an application we can get non-interactive zero knowledge proofs via the same public file.

We show that a complete broadcast network of n processors can evaluate any function fx₁,...,x_n) at private inputs supplied by each processor, revealing no information other than the result of the function, while tolerating up to t maliciously faulty parties for 2t < n. This improves the previous bound of 3t < n on the tolerable number of faults [BGW88, CCD88]. We demonstrate a resilient method to multiply secretly shared values without using unproven cryptographic assumptions. The crux of our method is a new, non-cryptographic zero-knowledge technique which extends verifiable secret sharing to allow proofs based on secretly shared values. Under this method, a single party can secretly share values v₁,...,v_m along with another secret w = P(v₁,...,v_m), where P is any polynomial size circuit; and she can prove to all other parties that w = P(v₁,...,v_m), without revealing w or any other information. Our protocols allow an exponentially small chance of error, but are provably optimal in their resilience against Byzantine faults. Furthermore, our solutions use operations over exponentially large fields, greatly reducing the amount of interaction necessary for computing natural functions.

We construct a protocol that enables a secret bit to be revealed gradually in a very controlled manner. In particular, if Alice possesses a bit S that was generated ran- domly according to the uniform distribution and 1/2 < p_i < ... < p_m = 1 then, using our protocol with Bob, Alice can achieve the following. The protocol consists of m stages and, after the i-th stage, Bob’s best prediction of 5, based on all his interac- tions with Alice, is correct with probability exactly p_i- (and a reasonable condition is satisfied in the case where S is not initially uniform). Furthermore, under an in- tractability assumption, our protocol can be made “oblivious” to Alice and “secure” against an Alice or Bob that might try to cheat in various ways. Previously proposed gradual disclosure schemes for single bits release information in a less controlled man- ner: the probabilities that represent Bob’s confidence of his knowledge of 5 follow a random walk that eventually drifts towards 1, rather than a predetermined sequence of values.Using controlled gradual disclosure schemes, we show how to construct an im- proved version of the protocol proposed by Luby, Micali and Rackoff for two-party secret bit exchanging (“How to Simultaneously Exchange a Secret Bit by Flipping a Symmetrically-Biased Coin”, Proc. 22nd Ann. IEEE Symp. on Foundations of Computer Science, 1983, pp. 11–21) that is secure against additional kinds of attacks that the previous protocol is not secure against. Also, our protocol is more efficient in the number of rounds that it requires to attain a given level of security, and is proven to be asymptotically optimal in this respect.We also show how to use controlled gradual disclosure schemes to improve existing protocols for other cryptographic problems, such as multi-party function evaluation.

We address the problem of performing a multiparty computation when more than half of the processors are cooperating Byzantine faults. We show how to compute any boolean function of n inputs distributively, preserving the privacy of inputs held by nonfaulty processors, and ensuring that faulty processors obtain the function value “if and only if” the nonfaulty processors do. If the nonfaulty processors do not obtain the correct function value, they detect cheating with high probability. Our solution is based on a new type of verifiable secret sharing in which the secret is revealed not all at once but in small increments. This slow-revealing process ensures that all processors discover the secret at roughly the same time. Our solution assumes the existence of an oblivious transfer protocol and uses broadcast channels. We do not require that the processors have equal computing power.

A multiparty-computation protocol allows each of a set of participants to provide secret input to a mutually agreed computation. Such protocols enforce two security properties: (1) secrecy of the inputs, apart from what is revealed by the output; and (2) correctness of the output, as defined by the agreed computation. All solutions, including those presented here, are based on two kinds of assumptions: (a) public-key cryptography; and (b) limited collusion in a setting where pairs of participants can exchange messages with secret and authenticated content. Some of the previous solutions relied totally on assumption (a), the others totally on (b).

Modern cryptography is fundamentally concerned with the problem of secure private communication. Suppose two parties, Alice and Bob, wish to communicate privately over a public channel (for instance, a telephone line with an eavesdropper). If Alice and Bob are able to meet, privately, beforehand, and agree on some common secret key, then it becomes easy for them to achieve such private communication. But Alice and Bob might not be able to first meet in private and agree on a key. In this case, we ask under what assumptions they can still agree on a common secret key, where their conversation is conducted entirely in public.

In 1985 Goldwasser Micali and Rackoff proposed a new type of in- teractive proof system which reveals no knowledge whatsoever about the assertion except its validity. The practical significance of these proofs was demonstrated in 1986 by Fiat and Shamir, who showed how to use efficient zero knowledge proofs of quadratic residuosity to establish user identities and to digitally sign messages. In this paper we propose a new zero knowledge identification scheme, which is even faster than the Fiat-Shamir scheme, using a small number of communicated bits, simple 8-bit arithmetic operations, and compact public and private keys. The security of the new scheme depends on an NP-complete algebraic problem rather than on factoring, and thus it widens the basis of public key cryptography, which has become dangerously dependent on the difficulty of a single problem.

In 1979 Pippenger and Fischer [PF] showed how a two-tape Turing Machine whose head positions (as a function of time) are independent of the input, can simulate, on-line, a one-tape Turing Machine with a logarithmic slowdown in the running time. We show a similar result for random-access machine (RAM) model of computation. In particular, we show how to do an on-line simulation of arbitrary RAM program by probabilistic RAM whose memory access pattern is independent of the program which is being executed with a poly-logarithmic slowdown in the running time.

We describe an efficient design methodology for the s-boxes of DES-like cryptosystems. Our design guarantees that the resulting s-boxes will be bijective and nonlinear and will exhibit the strict avalanche criterion and the output bit independence criterion.

Computer viruses can be used by their authors to harness the resources of in- fected machines for the author’s computation. By doing so without the permission or knowledge of the machine owners, viruses can be used to perform covert distributed proc- essing. We outline the class of problems for which covert distributed processing can be used. A bruteforce attack on cryptosystems is one such problem, and we give estimates of the time required to complete such an attack covertly.

This short paper is intended to provide a statement of current activities in the prepa- ration of data security standards and is directed at the community active in research and development in cryptology, some of whom may not be aware of this aspect of the application of their work; it concentrates on the period since August 1987 when a previous statement was made on this subject in the same context.

With the aim of providing a highly programming efficient cipher system, NTT has developed the open cipher algorithm, FEAL-8 (Fast Data Encipherment Algorithm) [1][2][3], which is a type of secret key cryptosystem.

Know, oh my children, that very long ago, in the Eastern city of Baghdad, there lived an old man named Ali Baba. Every day Ali Baba would go to the bazaar to buy or sell things. This is a story which is partly about Ali Baba, and partly also about a cave, a strange cave whose secret and wonder exist to this day. But I get ahead of myself ...