Search

The Finite Element Machine is a special purpose multiprocessor architecture designed to facilitate the solution of structural analysis problems by finite element methods. In this paper, interaction of the hardware aspects of the machine with a specific algorithm is examined in order to establish software primitives for the kernel of an operating system. The behavior of the primitives is explored in detail, and the effects of this behavior on the performance of the algorithm is evaluated. [ABSTRACT FROM AUTHOR]

This paper discusses program transformations to allow traditional programming languages to be used on a variety of architectures. A uniform framework is presented in which various array and multiple-scalar machines are all special cases. The methods are implemented in the Parafrase system, which can be used for machine design as well as compiler design studies. [ABSTRACT FROM AUTHOR]

This paper considers the language design approaches which have been used to support programming on parallel processors such as array and vector processors. The two main approaches have been classified as1.detection of parallelism;2.expression of machine parallelism. The advantages and disadvantages of each approach are briefly examined. A third approach is also considered which reflects neither the compiler's detection mechanism nor the underlying hardware but enables the programmer to express the inherent parallelism of a solution to a problem. In this way a joint syntax can be developed for both types of parallel processors. [ABSTRACT FROM AUTHOR]

This paper discusses the problems that arise when programs written in a conventional language are to be compiled into machine code for a data flow machine. It describes the current state of a project aimed at developing a compiler for an existing high level language for string processing. The compiler is intended to accept the full language without changing its semantics in any respect. The implementation of a sizable subset of the language is described and solutions to the remaining problems are suggested. The results indicate that the gap between data flow machines and conventional languages is easier to bridge than previously assumed. [ABSTRACT FROM AUTHOR]

Of the many proposals for parallel computer architectures, dataflow systems offer perhaps the greatest potential parallelism at the hardware level. However, it is unreasonable to expect users to exploit this parallelism at such a low level, and it is necessary to provide high level programming facilities which allow the user the abstract freedom of expression he requires, whilst permitting efficient use of the hardware. It has been noticed that single-assignment languages are particularly well-suited to dataflow machines, yet exhibit most of the familiar, useful features of conventional high level languages. This paper considers some aspects of code generation from the single-assignment language Lapse for the Manchester prototype dataflow computer. The syntax of Lapse, which resembles Pascal, is introduced, and code generation templates are presented. Some possible optimisations of flowgraph code are discussed, particularly in the implementation of arrays. [ABSTRACT FROM AUTHOR]

This paper describes the core of a complex cellular processor research project — construction and verification of cellular algorithms, the basis for cellular programming. Other important components of the project as theoretical /mathematical/ investigations, simulation language design and simulator implementation, cellular microprogramming will nearly be omitted, other components of central importance will only shortly be sketched and referred to the extent of making understandable the conditions e.g. requirements for and possibilities of the cellprogramming. /basic cellular processor architecture, integration of cellprocessors into digital architecture, real application areas/. Attention will be focused on the class of cellular algorithms taylored to the introduced universal microprogrammable cellprocessor. Less discussions can be devoted here to the important methodology and practice of the cellware — cellular specialized hardware — design and implementation. [ABSTRACT FROM AUTHOR]

Binary matrixes (matrixes having only 0 and 1 elements) occur in many theoretical and practical areas (e.g. in the theory of graphs and relations, grammars, coding, etc.) therefore the binary matrix operations have high importance in these topics. It is an obvious idea to use cellular processor consisting of micro-cells for the execution of these operations. The present paper gives a powerful cellular algorithm for the multiplication of two binary matrixes, taking into account the cellprocessor architecture developed by T. Legendi. Moreover, on the basis of this solution cellular algorithms are given for coding and for the computation of the m-th power of a binary matrix. [ABSTRACT FROM AUTHOR]

Well structured programs written in sequential high level languages are considered in this paper. Techniques of graph analysis are used to exhibit and measure the parallelism in these programs. Graph analysis is made on modified data dependency graphs. Several kinds of parallelism are considered, and particularly pipelining. A control scheme for a parallel computer, taking into account all the parallelism exhibited by the graph analysis and even dynamic pipelining, is then proposed. The control scheme is based on single assigment and guarded commands, associated with a data-driven mechanism. [ABSTRACT FROM AUTHOR]

We introduce a very high level language for specifying synchronization properties. It is designed using the primitives of temporal logic which facilitates the specification of both invariant and time-dependent properties. The paper begins with a discussion of properties that affect synchronization. The specification language then introduced features constructs to express each of these in a fairly natural and modular fashion. Since the statements in the language have intuitive interpretations, specifications are humanly readable. Also, since they possess appropriate formal semantics, unambiguous specifications result. [ABSTRACT FROM AUTHOR]

This paper describes how a parallel environment has been used to perform the task of compiling. The environment is an International Computers Limited (ICL) Distributed Array Processor (DAP): a machine of SIMD classification. The compiler design is shown to be related to the structure of existing MIMD parallel compilers. Although in this case parallelism is implemented at a data structure rather than a functional level. [ABSTRACT FROM AUTHOR]

This paper is concerned with parallel algorithms for determining the Convex Hull of N points on a plane, for a Shared Memory SIMD Computer. First, simple algorithms with read conflicts are described. It is then shown that the same bounds can be achieved with somewhat more complicated algorithms without read conflicts. The bounds achieved are: 0(N/K log N + log K .log N) for K processors, K ≤ N, which is optimal for the range 1 ≤ K ≤ N/log N, and 0(K log N) for N1+1/K processors, 1 ≤ K ≤ log N. These bounds are the same as those for parallel sorting algorithms, and any further improvement in their efficiency will imply the existence of better sorting algorithms than currently known. [ABSTRACT FROM AUTHOR]

The subject of the paper is discrete systems (DS) represented by a set of elements and a set of operations. In particular these operations are permutations of DS elements. The DS is represented by subsystems with sufficient small number of elements and operations of the same kind. The subsystems are distributed at hierarchical levels. The subsystems of each level can execute their operations in parallel. On the basis of this approach algorithms are constructed for parallel realisation of the permutations in DS using a generating set of permutations. A theoretical group interpretation of the well-known fast Fourier transform is made, which shows that this approach can be applied to a wider class of transformations. [ABSTRACT FROM AUTHOR]

In this paper new parallel algorithms for solving a band system of linear equations with bandwidth 2m+1 and for matrix inversion of such matrix are proposed. The algorithms are based on the simultaneous computation of m band triangular systems differing from each other only at the right-hand side. Thus, a computational complexity of our algorithm for the band system is the same as of a band triangular system solver. A difference is only at the number of processors used. The application of the algorithm for solving the inversion is advantageous if this computation is a part of the solving of system and it is necessary to know only selected rows or columns of the matrix inverse. [ABSTRACT FROM AUTHOR]

This paper examines the use of binary trees in the design of efficient parallel algorithms. Using binary trees, we develop efficient algorithms for several scheduling problems. The shared memory model for parallel computation is used. Our success in using binary trees for parallel computations, indicates that the binary tree is an important and useful design tool for parallel algorithms. [ABSTRACT FROM AUTHOR]

New factorisation methods suitable for the solution of linear equations applicable to parallel computers are proposed in this paper. The methods are based on variations to the Quadrant Interlocking Factorisation (Q.I.F.) methods given earlier in Evans and Hadjidimos [1] and Evans and Hatzopoulos [2]. The new methods can be considered as the Crout and Gauss-Jordan type for general real matrices and Choleski type for matrices which are positive definite. The paper also includes topics such as error analysis and computational cost analysis for the proposed methods. [ABSTRACT FROM AUTHOR]

During the past few years in our laboratory we have had many experiences with various software engineering technologies and sophisticated computer aids for software development. In general, we felt that they usually try to solve too much but do indeed practically very few. In this paper we intentionally avoided proposing too much (e.g. by over-formulating those aspects which could well have been formalized strictly if we had wanted). The way outlined in this paper concentrates on the process of development, emphasises the discipline and not the formalities. [ABSTRACT FROM AUTHOR]

Very few of the existing software analysis and design methodologies provide a facility for developing and specifying system components containing cooperating parallel processes. In this paper we develop a general specification technique which allows to precisely describe processes, process-classes, events and messages. The proposed methodology is based on Petri Nets which have been extended with higher level concepts to allow the straight forward specification of processes and their cooperation and to avoid the principle problem of Petri Nets, i.e. the large complexity of such nets when specifying even simple mechanisms. Care has been taken to provide for the adaption of the many formal analysis principles available for Petri Nets to the proposed technique. The development, design and specification technique is then used to extend four of the most popular design methodologies — Jackson, SADT, HIPO and Nassi Shneiderman — with process and event/message specification facilities. [ABSTRACT FROM AUTHOR]

LDM (Logic based Development Method) is a method, a language, and a support system for designing software objects on different levels of abstraction. It is based on the ideas of logic programming (PROLOG) and the Vienna Development Method (VDM). The paper gives an overview of the method, the language, the first experimental support system, and the experiences from its usage. It gives an example of the development process in LDM, and further plans are summarised. [ABSTRACT FROM AUTHOR]

This paper outlines ESPRESO, a specification system for process control software, which was developed at Nuclear Research Center, Karlsruhe, Federal Republic of Germany. ESPRESO is based on some new ideas, which are combined with elements taken from other systems. ESPRESO consists of a set of concepts, a specification language, a tool for the management, evaluation and validation of specifications, and the method how to use the system. Language, tool, and method are carefully adapted to the concepts. The aim was to demonstrate some ideas not found in the specification systems currently available, rather than to provide another product for the software market. The concepts of ESPRESO where abstracted from the most common tasks in real time programming, focusing on process communication. All operations are precisely defined. The concept of modules allows for the definition of static units which hide their internal structure from the outside. An attribute grammar was used, which describes not only the context sensitive syntax of the language, but also the effect of operations on the stored specification. The tool-component was partially coded in PASCAL, and installated on IBM-OS and VAX-VMS. While ESPRESSO is already being used for the specification of a nuclear reactor safety system, more components are being implemented in order to provide means for validation and documentation. [ABSTRACT FROM AUTHOR]

There is an increasing wealth of experience with abstract data types. This experience encompasses informal discussion of abstract data types, their formal specification, programming language constructs to facilitate their implementation, and the formal verification of implementations. This paper shows how abstract data types may be used as the basis of a top-down method of program design which leads to programs with a high degree of information hinding. [ABSTRACT FROM AUTHOR]

This paper presents two examples of implementing shared abstract data types in EDISON and Ada®. The solutions are based on Laventhal's algorythm for implementing synchronization specification. The presented two examples illustrate how shared abstract data types can be implemented using different language constructs. [ABSTRACT FROM AUTHOR]

In the paper, application of idempotent elements to construction of cryptographic systems has been presented. The public key cryptosystem bead on idempotent elements and the cryptographic transformation that preserves elementary arithmetic operatione have been described. [ABSTRACT FROM AUTHOR]

In the papers [1][2] Kjeldsen derived very interesting properties of cascade couple sequence generators. For applications in ciphering we are interested to know the linear complexity of such sequences. In the following we first consider the examples 1 and 2. [ABSTRACT FROM AUTHOR]

The Matsumoto-Imai public key scheme was developed to provide very fast signatures. It is based on substitution polynomials over GF(2m). This paper shows in two ways that the Matsumoto-Imai public key scheme is very easy to break. In the faster of the two attacks the time to cryptanalyze the scheme is about proportional to the binary length of the public key. This shows that Matsumoto and Imai greatly overestimated the security of their scheme. [ABSTRACT FROM AUTHOR]

This paper presents a new trapdoor-knapsack public-key-cryptosystem. The encryption equation is based on the general modular knapsack equation, but unlike the Merkle-Hellman scheme the knapsack components do not have to have a superincreasing structure. The trapdoor is based on transformations between the modular and radix form of the knapsack components, via the Chinese Remainder Theorem. The resulting cryptosystem has high density and has a typical message block size of 2000 bits and a public key of 14K bits. The security is based on factoring a number composed of 256 bit prime factors. The major advantage of the scheme when compared with the RSA scheme is one of speed. Typically, knapsack schemes such as the one proposed here are capable of throughput speeds which are orders of magnitude faster than the RSA scheme. [ABSTRACT FROM AUTHOR]

The quadratic sieve algorithm is currently the method of choice to factor very large composite numbers with no small factors. In the hands of the Sandia National Laboratories team of James Davis and Diane Holdridge, it has held the record for the largest hard number factore since mid-1983. As of this writing, the largest number it has crackd is the 71 digit number (1071−1)/9, taking 9.5 hours on the Cray XMP computer at Los Alamos, New Mexico. In this paper I shall give some of the history of the algorithm and also describe some of the improvements that habe been suggested for it [ABSTRACT FROM AUTHOR]

Given a primitive element g of a finite field GF(q), the discrete logarithm of a nonzero element u ∈ GF(q) is that integer k, 1 ≤ k ≤ q−1, for which u = gk. The well-known problem of computing discrete logarithms in finite fields has acquired additional importance in recent years due to its applicability in cryptography. Several cryptographic systems would become insecure if an efficient discrete logarithm algorithm were discovered. This paper surveys and analyzes known algorithms in this area, with special attention devoted to algorithms for the fields GF(2n). It appears that in order to be safe from attacks using these algorithms, the value of n for which GF(2n) is used in a cryptosystem has to be very large and carefully chosen. Due in large part to recent discoveries, discrete logarithms in fields GF(2n) are much easier to compute than in fields GF(p) with p prime. Hence the fields GF(2n) ought to be avoided in all cryptographic applications. On the other hand, the fields GF(p) with p prime appear to offer relatively high levels of security. [ABSTRACT FROM AUTHOR]

It is generally accepted that data encipherment is needed for secure distributed data processing systems. It is accepted, moreover, that the enciphering algorithms are either published or must be assumed to be known to those who wish to break the security. Security then lies in the safe keeping of the encipherment keys, which must be generated and stored securely and distributed securely to the intending users. At an intermediate level of detail of a system it may be useful to have functions which manipulate keys explicitly but which hide some of the details of key generation and distribution, both for convenience of use and so that new underlying techniques can be developed. This paper offers a contribution to the discussion. It proposes key manipulation functions which are simple from the user's point of view. It seeks to justify them in terms of the final secure applications and discusses how they may be implemented by lower level techniques described elsewhere. The relationship of the functions to telecommunication standards is discussed and a standard form is proposed for encipherment key information. [ABSTRACT FROM AUTHOR]

It is sometimes required that user pairs in a network share secret information to be used for mutual identification or as a key in a cipher system. If the network is large it becomes impractical or even impossible to store all keys securely at the users. A natural solution then is to supply each user with a relatively small amount of secret data from which he can derive all his keys. A scheme for this purpose will be presented and we call such a scheme a symmetric key generation system (SKGS). However, as all keys will be generated from a small amount of data, dependencies between keys will exist. Therefore by cooperation, users in the system might be able to decrease their uncertainty about keys they should not have access to. The objective of this paper is to present a class of SKGS for which the amount of secret information needed by each user to generate his keys is the least possible while at the same time a certain minimum number of users have to cooperate to resolve the uncertainty of unknown keys. [ABSTRACT FROM AUTHOR]

A novel cryptosystem is presented in which the protection of the messages is based on the special properties of the binary multiplying channel. In the system the receiver is mainly responsible for the protection of the messages and not the transmitter. In the paper a small area network realization with a binary multiplying channel is discussed. [ABSTRACT FROM AUTHOR]

In recent years, much effort has gone into the development of high bandwidth communication networks for use over relatively short (local) distances, e.g. an office, an industrial complex, a research laboratory, etc.. The high bandwidth of these networks allows many of the services now requiring separate networks such as facsimile, digitized voice, file transfer and interactive terminal data, to be integrated into a common transmission facility. Manufacturers are currently developing products which conform to the recently established IEEE 802 standard for Local Area Networks (LANs). This standard is based on the concept of a layered, "peer entity" communication protocol put forth in the International Standards Organization's (ISO) seven layer model for Open Systems Interconnection (OSI). In this paper we define the notions of secrecy and privacy as they relate to a LAN environment and the various services a network is required to provide such as data integrity, authentication and digital signature services. We also describe the cost-benefit tradeoff involved in attaining various levels of privacy and secrecy. [ABSTRACT FROM AUTHOR]

In a paper entitled "The Prisoners' Problem and the Subliminal Channel" [1], the present author showed that a message authentication without secrecy channel providing m bits of overt communication and r bits of message authentication could be perverted to allow an l < r bit covert channel between the transmitter and a designated receiver at the expense of reducing the message authentication capability to r-l bits, without affecting the overt channel. It was also shown that under quite reasonable conditions the detection of even the existence of this covert channel could be made as difficult as the underlying cryptoalgorithm was difficult to "break." In view of this open -- but indetectable -- existence, the covert channel was called the "subliminal" channel. The examples constructed in [1], although adequate to prove the existence of such channels, did not appear to be feasible to extend to interesting communications systems. Fortunately, two digital signature schemes have been proposed since Crypto 83 -- one by Ong-Schnorr-Shamir [2] based on the difficulty of factoring sufficiently large composite numbers and one by Gamal [3] based on the difficulty of taking discrete logarithms with respect to a primitive element in a finite field -- that provide ideal bases for implementing practical subliminal channels. This paper reviews briefly the essential features of the subliminal channel and then discusses implementations in both the Ong-Schnorr-Shamir and Gamal digital signature channels. [ABSTRACT FROM AUTHOR]

To perform message authentication in a telesurveillance system, the paper proposes a non linear time varying encryption algorithm, based on key layering in three levels (system key, intermediate key, running key) and on encryption organization into two or more sets of three operations (running key rotation, message digit substitution and transposition). The algorithm was designed to be implemented on an 8-bit microprocessor. [ABSTRACT FROM AUTHOR]

The paper presents a software protection system that prevents "software piracy" reliably while allowing to produce an unlimited number of program copies. Based on a combination of smart card technology and cryptographic techniques the system provides not only a high level of security, but also enhanced ease-of-use for the software manufacturer as well as for the user. [ABSTRACT FROM AUTHOR]

Recently Ong, Schnorr, and Shamir [OSS1, OSS2] have presented new public key signature schemes based on quadratic equations. We will refer to these as the OSS schemes. The security of the schemes rest in part on the difficulty of finding solutions to (1)$$ X^2 - KY^2 \equiv M(mod{\mathbf{ }}n), $$ where n is the product of two large rational primes. In the original OSS scheme [OSS1], K, M, X, and Y were to be rational integers. However, when this version succumbed to an attack by Pollard [PS,S1], a new version was introduced [OSS2], where M, X, and Y were to be quadratic integers, i. e. elements of the ring $$ Z[\sqrt d ] $$. In this paper we will show that the OSS system in $$ Z[\sqrt d ] $$ is also breakable The method by which we do this is to reduce the problem of solving the congruence over the ring $$ Z[\sqrt d ] $$ to the problem of solving the congruence over the integers, for which we can use Pollard's algorithm. [ABSTRACT FROM AUTHOR]

At Crypto'83, the present author showed that a transmitter and chosen receiver(s) -- by secretly exchanging some side information -- could pervert an authentication without secrecy channel to allow them to convert a portion of the authentication information to a hidden (covert) communications channel [1]. It was also shown that under quite reasonable conditions even the detecticn of the existence of this Covert channel could be made as difficult as the underlying authentication algorithm was "cryptosecure". In view of this open -- but indetectable -- existence, such a covert channel was called a "sublininal" channel. The examples constructed in [1] were more in the nature of existence proofs than of practical subliminal communications channels. At Eurocrypt'84 [2], however, it was shown how to use digital signature schemes as a way of realizing practical subliminal channels and, in particular, subliminal channels were devised using Ong and Schnorr's quadratic approximation scheme [3], Ong, Schnorr and Shamir's quadratic representation schemes [4] and Ong. Schnorr and Shamir's cubic signature scheme [5] as Well as Carnal's discrete logarithm-based digital signature scheme [6]. Unfortunately, from the standpoint of providing a secure (and feasible) subliminal channel, all Of these digital signature schemes were cryptanalyzed [7],[8] shortly after being proposed. At Crypto'84, a fourth variant to the earlier digital signature schemes of Ong, Schnorr and Shamir was presented by Schnorr [9] which was also quickly cryptanalyzed [10]. At the 1985 IEEE Symposium on Security and Privacy, Okamoto and Shiraishi proposed yet another digital signature scheme based on quadratic inequalities [11] which had been designed to avoid the cryptanalytic weaknesses that hed flawed the schemes of Schnorr, et al. The cryptanalysis of this scheme by Erickell and DeLaurentis is reported elsewhere in these Proceedings [12]. In view of the short-lived nature Of all of these schemes, it has become a high risk venture to propose subliminal channels based on digital signatures. The motivation for going so is that digital Signatures can be much easier to calculate and verify tnan full-fledged two-key ciphers. As a result, the benefits (of a successful implementation) far outweigh the risks of perhaps having an insecure digital sianature (or subliminal) channel slip by undetected. Based on the cumulative experience gained in cryptanalyzing the six digital signature schemes mentioned above, Brickell and DeLaurentis propose a new scheme in their paper that appears to avoid the weaknesses exploited in the earlier cryptanalyses. [ABSTRACT FROM AUTHOR]

The Vernam scheme protects the privacy unconditionally, but is completely insecure to protect the authenticity of a message. Schemes will be discussed in this paper that protect the authenticity unconditionally. The definition of unconditional security is defined. Stream cipher authentication schemes are proposed. The consequences on information protection using RSA and DES are discussed. [ABSTRACT FROM AUTHOR]

Staggering amounts of commercial software are marketed to fulfill needs from the PC explosion. Unfortunately, such software is trivial to duplicate! From the vendors' viewpoint a way to protect profit is needed. Typically, they have resorted to various schemes that attempt to inhibit the duplication process. Although protection of future profit is important, so is protection against current loss. Commercial and business related software must be adequately protected lest data be stolen or manipulated. However, more important than any of these classes is protection of government computer resources, especially classified and operational software and data. Loss of control in this realm could be detrimental to national security. This paper addresses current technologies employed in protection schemes: signatures (magnetic and physical) on floppy disks, Software Analysis Denial (SAD), Hardware Security Devices (HSD), and Technology Denial Concepts (TDC) are presented, with an emphasis on SAD. Advantages and disadvantages of these schemes will be clarified. [ABSTRACT FROM AUTHOR]

In his 1983 paper, Neal Wagner1 defines a perfect fingerprint to be an identifying fingerprint added to an object in such a way that any alteration to it that makes the fingerprint unrecognizable will also make the object unusable. A perfect fingerprinting scheme for binary data would seem difficult to devise, since it would be possible to discover the fingerprints by comparing different fingerprinted copies of the same piece of data. In this paper we discuss a fingerprinting scheme which, although it does not surmount this problem entirely, at least specifies the number of copies an opponent must obtain in order to erase the fingerprints. [ABSTRACT FROM AUTHOR]

During summer 1985, we performed eight cycling experiments on the Data Encryption Standard (DES) to see if DES has certain algebraic weaknesses. Using special-purpose hardware, we applied the cycling closure test described in our Eurocrypt 85 paper to determine whether DES is a pure cipher. We also carried out a stronger version of this test. (A cipher is pure if, for any keys i, j, k, there exists some key l such that TiTj−1Tk = Tl, where Tw denotes encryption under key w.) In addition, we followed the orbit of a randomly chosen DES transformation for 236 steps, as well as the orbit of the composition of two of the "weak key" transformations. Except for the weak key experiment, our results are consistent with the hypothesis that DES acts like a set of randomly chosen permutations. In particular, our results show with overwhelming confidence that DES is not pure. The weak key experiment produced a short cycle of about 233 steps, the consequence of hitting a fixed point for each weak key. [ABSTRACT FROM AUTHOR]

This paper presents a layered approach to the design of private key cryptographic algorithms based on a few strategically chosen layers. Each layer is a conceptually simple invertible transformation that may be weak in isolation, but makes a necessary contribution to the security of the algorithm. This is in contrast to algorithms such as DES which utilize many layers and depend on S-boxes that have no simple mathematical interpretation. A property called transparency is introduced to deal with the interaction of layers and how they must be selected to eliminate system weaknesses. Utilizing this layered approach, a private key cryptographic algorithm consisting of three layers is constructed to demonstrate the design criteria. The algorithm has an adequate key space and valid keys can be easily generated. The design is based on a symmetrical layered configuration, which allows encryption and decryption to be performed using the same algorithm. The algorithm is suitable for VLSI implementation. Some statistical tests are applied to the algorithm in order that its cryptographic performance can be evaluated. The test results and attempts at cryptanalysis suggest that the three-layered algorithm is secure. [ABSTRACT FROM AUTHOR]