%& latex
\documentstyle{article}
\voffset = -1cm \hoffset = -2cm  \vsize = 22cm \textwidth 160mm \textheight 220mm
\font\BBb=msbm10

%
% generate the index, comment out if not required
%
\makeindex

%
% Mathematical functions and symbols
%
\def\deg{\mathop{\rm deg}\nolimits}
\def\min{\mathop{\rm min}\nolimits}
\def\max{\mathop{\rm max}\nolimits}
\def\mod{\mathop{\rm mod}\nolimits}
\def\Z{\mbox{\BBb Z}}   \def\N{\mbox{\BBb N}}   \def\R{\mbox{\BBb R}}
\def\F{\mbox{\BBb F}}   \def\st{:}              \def\BB{\mbox{$\bullet$}}
\def\notdiv{\!\not\vert\thinspace}

%
% Abstracting abbreviations
%
\def\T#1{{\par\subsection*{#1}}}
\def\A#1{{{\em #1\index{#1}.\ }}}
\def\E#1{{{\em #1\index{#1} (ed.).\ }}}
\def\J#1{{\par\vspace {0.2cm}\noindent{#1}}}
\def\D#1{({#1})}
\def\X#1{{\par\vspace {0.2cm}\noindent #1}}
\def\Q#1{}

\title{Abstracts in Cryptology: 1990--1994\\ Volume~X, Release 1}
\author{Sean A. Irvine\\ Electronic mail: {\tt sirvine@waikato.ac.nz}}
\date{\today}

\begin{document}
\small
\maketitle

\begin{abstract}
This volume of {\sl Abstracts in Cryptology\/} contains references and abstracts for the cryptologic literature for the years 1990 through 1994. Other volumes cover different decades. The purpose of the document is aid the location of relevant cryptologic literature.
\end{abstract}

\subsection*{Preface}

This is Volume~X, Release 1, of the {\sl Abstracts in Cryptology.} This release contains approximately one thousand abstracts and references to books, papers, articles, technical reports, letters, and other literature pertaining to cryptology. The core references deal with secrecy, authentication, cryptanalysis, protocol, and so on. Other subjects having some coverage include random number generation, number theory (factoring and primality testing), zero-knowledge proofs, data compression, and complexity theory. I believe that all works referenced are publicly available.

Other volumes covering different decades are also available, but are not as complete as the current volume. Volume~I covers literature prior to 1900, Volume~II covers 1900--1919, Volume~III cover 1920--1929, Volume~IV covers 1930--1939, Volume~V covers 1940--1949, Volume~VI covers 1950--1959, Volume~VII covers 1960--1969, Volume~VIII covers 1970--1979, Volume~IX covers 1980--1989, Volume~X covers 1990--1994, and Volume~XI covers 1995--1999.

I regret that I am unable to supply copies of works referenced, nor can I specify where individual works may be obtained. Most of the books referenced should be available from a university or large public library. Most of the journal articles can be obtained by the interloan services of a library. The technical reports can usually obtained by directly contacting the author or institution concerned. Many of the technical reports from 1985 onwards are available on-line using the World-Wide-Web, gopher, and ftp systems.

Some journals are not covered very well in this release: notable omissions are {\em Cryptologia\/} and the {\em Journal of Cryptology.} If somebody with access to these journals can send me abstracts for the papers in them I will include them in the document for the next release.

If you know of any relevant document not listed here please send me the title, author, and journal or publisher, and if possible send an abstract. I am also happy to receive complete papers.

This document is designed to be printed using the \LaTeX\ typesetting system.

\vspace{1cm}

\noindent Sean Irvine.

\vspace{1cm}

{\obeylines Department of Mathematicss and Statistics
University of Waikato
Private Bag 3105
Hamilton
New Zealand.}

\T {Achieving Electronic Privacy}
\A {David Chaum}
\J {Scientific American {\bf 267,} 2}
\D {1992}
\X {All of your electronic transactions, from credit card purchases to bank
withdrawals, are creating a digital dossier of your life. The author proposes
an encryption system that would allow individuals and institutions to take
advantage of the benefits of computer communications while protecting privacy.}

\T {Administrator's Guide to the Digital Signature Facility ``Rover''}
\A {Matt Bishop}
\J {Dartmouth College Computer Science Technical Report PCS-TR90-153}
\D {1990}
\X {This document describes the installation and maintenance of the rover utility, which provides a digital signature capability for internet messages.}

\T {Algebraic Methods for Interactive Proof Systems}
\A {Carsten Lund}
\A {Lance Fortnow}
\A {Howard Karloff}
\A {Noam Nisan}
\J {J ACM {\bf 39,} 4, pp. 859--868}
\D {1992}
\X {A new algebraic technique for the construction of interactive proof systems
is presented. Our technique is used to prove that every language in the
polynomial-time hierarchy has an interactive proof system. This technique
played a pivotal role in the recent proofs that IP = PSPACE and that MIP =
NEXP.}

\T {Algorithm Engineering for Public Key Algorithms}
\A {T. Beth}
\J {IEEE Selected Areas of Communication {\bf 1,} 4, pp. 458--466}
\D {1990}

\T {An Algorithmic Solution to Sequential Homophonic Ciphers}
\A {King}
\A {Bahler}
\J {Cryptologia {\bf 17,} 2}
\D {1993}

\T {Algorithms in Number Theory}
\A {A. K. Lenstra}
\A {H. W. Lenstra Jr.}
\J {Handbook of Theoretical Computer Science, J. van Leeuwen (ed.) {\bf A} MIT Press/Elsevier}
\D {1990}

\T {Algorithms in Number Theory}
\A {Jonathan Paul Sorenson}
\J {Computer Science Technical Report TR 1027, University of Wisconsin}
\D {1991}
\X {This thesis discusses four sets of results on number theoretic algorithms. A positive integer $n$ is a perfect power if there exist integers $a,b>1$ such that $n = a^b$.0 We give a new sieve algorithm to recognize perfect powers.This algorithm has a linear median running time, and it has a subquadratic average running time assuming the extended Riemann hypothesis. Previous algorithms to recognize perfect powers require at least cubic average time. We also show unconditionally that the set of perfect powers is in the parallel complexity class $NC^2$. This is joint work with Eric Bach. We give the first randomized parallel algorithms that run in polylog time using a subexponential number of processors for factoring integers and computing discrete logarithms over finite fields of prime order. This solves a problem posed by Adleman and Kompella in 1988. We present the new $k$-ary greatest commmon divisor (GCD) algorithm, a generalization of the binary algorithm of Stein. In a sequential implementation, this algorithm outperformed many previous algorithms, including the binary algorithm and the Euclidean algorithm. In addition, the complexity of a parallel version of the $k$-ary GCD algorithm matches that of the best previous parallel GCD algorithms. And finally, we analyze the number of integers factorable in random polynomial time using Pollard's $p-1$ factoring algorithm. We show that, in random polynomial time, the $p-1$ method can factor more integers than trial division but fewer than Lenstra's elliptic curve method. This is joint work with Carl Pomerance.}

\T {All Languages in {\bf NP} Have Divertible Zero-Knowledge Proofs and Arguments Under Cryptographic Assumptions}
\A {Mike V. D. Burmester}
\A {Yvo Desmedt}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {We present a diveritble zero-knowledge proof (argument) for SAT under the assumption that probabilitistic encryption homomorphisms exists. Our protocol uses a simple `swapping' technique which can be applied to many zero knowledge proofs (arguments). In particular we obtain a divetible zero-knowledge proof for graph isomorphism. The consequences for abuse-free zero-knowledge proofs are also considered.}

\T {An Almost-Constant Round Interactive Zero-Knowledge Proof}
\A {M. Burmester}
\J {Info. Proc. Letters {\bf 42,} 2}
\D {1992}

\T {An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem}
\A {Zvi Galil}
\A {Oded Margalit}
\J {SIAM J. Computing, {\bf 20,} 6, pp.~1157--1189}
\D {1991}
\X {This paper describes a new approach for solving the subset-sum problem. It is useful for solving other NP-hard problems. The limits and potential of this approach are discussed. The apprach yields an algorithm for solving the dense version of the subset-sum problem. It runs in time $O(\ell\log\ell),$ where $\ell$ is the bound on the size of the elements. But for dense enough inputs an target numbers near the middle sum, it runs in time $O(m),$ where $m$ is the number of elements. Consequently, it improves the previously best algorithms by at least one order of magnitude and sometimes by two. The algorithm yields a characterization of the set of subset sums as a collection of arithmetic progressions with the same difference. This characterization is derived by elementary number-theoretic and algorithmic techniques. Such a characterization was first obtained by using analytic number theory and yielded inferior algorithms.}

\T {Amending Leighton and Micali's Key Distribution Protocol}
\A {Yuliang Zheng}
\J {Technical report: tr-93-17, Centre for Computer Security Research, University of Woolongong, NSW, Australia}
\D {1993}
\X {A key distribution protocol is a set of rules by which two users can establish a shared common keybetween them andthen use the key in future secure communications.We analyze a key distribution protocolpresented by Leighton and Micali at the CRYPTO'93 conference,which is based on tamper-proof hardware,and show that the protocol fails in thata common key shared between two userscan always be obtained by a number of otherlegitimate users in a systemwhere the proposed protocol is employed.An interesting point is thatthe legitimate users can derive the keywithout opening a single tamper-proof chip.We also propose a very simple identity basedconference key distribution protocol that frees of the flaw possessed by Leighton and Micali's protocol.Furthermore, we employ ideas behind our protocolto successfully repair Leighton and Micali's failed protocol.}

\T {American National Standard for Financial Institution Sign-On Authentication for Wholesale Financial Transaction}
\A {American Bankers Association}
\J {ANSI X9.26 (Revised)}
\D {1990}

\T {Analysis of Cellular Automata Used as Pseudorandom Pattern Generators}
\A {P. H. Bardell}
\J {Proc. of 1990 Int. Test Conference, pp. 762--768}
\D {1990}

\T {Analysis of Two Prime Number Sieves, an}
\A {Jonathan Sorenson}
\J {Computer Science Technical Report TR 1028, University of Wisconsin}
\D {1991}
\X {A prime number sieve is an algorithm that finds all prime numbers up to a bound $n$. In this paper, we calculate the number of arithmetic operations used by two prime number sieves: the sieve of Eratosthenes and an efficient linear sieve due to Pritchard. Although Pritchard's sieve is asymptotically faster than the sieve of Eratosthenes by a factor of $\Theta (\log\log n )$, we show that the sieve of Eratosthenes uses fewer arithmetic operations than Pritchard's sieve for most feasible inputs. In addition, we analyze and compare versions of both algorithms that use wheels, and we give implementation timing results.}

\T {Anonymous One-Time Signatures and Flexible Untraceable Electronic Cash}
\A {Barry Hayes}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}

\T {Applying the Take-Grant Protection Model}
\A {Matt Bishop}
\J {Darmouth College Computer Science Technical Report PCS-TR90-151}
\D {1990}
\X {The Take-Grant Protection Model has in the past been used to model multilevel security hierarchies and simple protection systems. The models are extended to include theft of rights and sharing of information, and additional security policies are examined. The analysis suggests that in some cases the basic rules of the Take-Grant Protection Model should be augmented to represent the policy properly; when appropriate, such modifications are made and their effects with respect to the policy and its Take-Grant representations are discussed.}

\T {Are Computer Hacker Break-ins Ethical?}
\A {E. H. Spafford}
\J {Technical Report 994, Purdue University}
\D {1990}

\T {AS 2805.6.5.3: Electronic Funds Transfer---Key Management}
\A {Standards Australia}
\D {1990}

\T {Asynchronous Secure Computation}
\A {Michael Ben-Or}
\A {Ran Canetti}
\A {Oded Goldreich}
\J {25th ACM STOC}
\D {1993}
\X {We initiate a study of security in {\em asynchronous\/} networks. We consider a completely asynchronous network where every two parties are connected via a private channel, and some of the parties may be faulty. We start by defining secure computation in this mpdel. Our definition adapts the underlying principles of defining security (i.e., comparing the computation to a computation in the presence of a trusted party) to the asynchronous model. In particular, our definition takes into account the fact that the computation must be completed even if we never hear from the faulty parties. Next, we show that whatever can be securely computed in an asynchronous network in the presence of a trusted party, can be securely computed in a network in which no such trusted party exists. We distinguish two types of faults. In case of Fail-Stop faults, our construction is valid as long as the faulty parties constitute less than a {\em third\/} of the parties in the network. In case of general (i.e., Byzantine) faults, our construction requires that the faulty parties are less than a {\em fourth\/} fraction. In both cases, the resilience of our construction is optimal. Our construction generalizes known synchronous constructions by Ben-Or, Goldwasser and Wigderson. In addition, we introduce and implement several new asynchronous primitives. Among these, we note an {\em errorless\/} asynchronous verifiable secret sharing scheme, an asynchronous agreement on a large set that is contained in the dynamically growing inputs of all non-faulty parties, and an {\em on-line\/} error-correcting procedure.}

\T {Attacks on Okamoto and Tanaka's One-way ID-based Key Distribution System}
\A {T. Hwang}
\J {Info. Proc. Letters {\bf 43,} 2}
\D {1992}
\X {Okamoto and Tanak's one-way ID-based key distribution system is shown to be
insecure in providing private communications. A modified scheme is proposed
under the same assumptions, however, achieving even better performance.}

\T {Authentication and Delegation with Smart-cards}
\A {M. Abadi}
\A {M. Burrows}
\A {C. Kaufman}
\A {B. Lampson}
\J {DEC Systems Research Centre}
\D {1990}
\X {The authentication of users in distributed systems poses special problems because users lack the ability to encrypt and decrypt. The same problems arise when users wish to delegate some of their authority to nodes, after mutual authentication. In most systems today, the user is forced to trust the node he wants to use. In a more satisfactory design, the user carries a smart-card with sufficient computing power to assist him; the card provides encryption and decryption capabilities for authentication and delegation. authentication is relatively straightforward with a sufficiently powerful smart-card. However, for practical reasons, protocols that place few demands on smart-cards should be considered. These protocols are subtle, as they rely on fairly complex trust relations between the principals in the system (users, hosts, services). In this paper, we discuss a range of public-key smart-card protocols, and analyze their assumptions and the guarantees they offer.}

\T {Authentication in Distributed Systems: Theory and Practice}
\A {Butler Lampson}
\A {Martin Abadi}
\A {Michael Burrows}
\A {Edward Wobber}
\J {DEC Systems Research Centre}
\D {1992}
\X {We describe a theory of authentication and a system that implements it. Our theory is based on the notion of principal and a ``speaks for'' relation between principals. A simple principal either has a name or is a communication channel; a compound principal can express an adopted role or delegation of authority. The theory shows how to reason about a principal's authority be deducing the other principals that it can speak for; authenticating a channel is one important application. We use the theory to explain many existing and proposed mechanisms for security. In particular, we describe the system we have built. It passes princpals efficiently as arguments or results of remote procedure calls, and it handles public and shared key encryption, name lookup in a large name space, groups of principals, loading programs, delegation, access control, and revocation.}

\T {Average Case Intractability of Matrix and Diophantine Problems}
\A {Ramarathnam Venkatesan}
\A {Sivaramakrishnan Rajagopalan}
\J {Proc. of the 24th ACM Symp. on the Theory of Computing}
\D {1992}

\T {AXYTRANS: Physical Funds Transport and DES}
\A {Marc Geoffrey}
\A {Ronny Bjones}
\A {Hedwig Cnudde}
\J {Computer Security and Industrial Cryptography, Lecture Notes in Computer Science(741), Springer-Verlag}
\D {1993}
\X {Currently, the transport of valuables and their storage is based upon physical determent. Very often, this leads to the escalation of violence. Therefore, AXYTRANS developed a whole new way of thinking with regard to the transport of valuables (i.c. paper money, bank cards, $\ldots$): AXYTRANS. This system aims to degrade the valuables in the case of an agression: the value of the original bank note or bank card is reduced to that of a piece of paper or plastic. The practical implementation of the system required the practical knowledge of a variety of different disciplines: basic electronics, physical and mechanical security, cryptography, computer security, $\ldots$ In this project, CRYPTECH took care of all the logical security aspects and of the implementation of the {\em centre serveur.} The system is current being tested by the PTT in France and in Belgium.}

\T {Beating the Code Breakers}
\A {Artur Ekert}
\J {Nature {\bf 358,} pp. 14--15}
\D {2 July 1992}

\T {Better Login Protocols for Computer Networks}
\A {Dominique {de Waleffe}}
\A {Jean-Jacques Quisquater}
\J {Computer Security and Industrial Cryptography, Lecture Notes in Computer Science(741), Springer-Verlag}
\D {1993}
\X {Authenticating computer users is a fairly old problem. Password based solutions were acceptable until the growth of computer networks based on insecure communication. Today many systems still use fixed passwords as a means of authentication. We show in this paper how an old scheme by Lamport can be used to provide more security. Relying on that scheme and zero-knowledge techniques, we show extensions proving much more general access control mechanisms. Those extensions can be exploited in several ways: to authenticate users in computer networks, to provide users with access tickets or provide servers with proofs of usage. We also show how, in a single transaction, a user can prove this authenticity as well as prove his possession of a ticket. Finally, we explain how smart cards make those protocols very practical.}

\T {The Biased Coin Problem}
\A {Ravi B. Boppana}
\A {Babu O. Narayanan}
\J {25th ACM STOC}
\D {1993}
\X {A slightly-random source (with {\em bias\/} $\epsilon$) is a sequences $x=(x_1,x_2,\ldots,x_n)$ of random bits such that the conditional probability that $X_i=1,$ given the outcomes of the first $i-1$ bits, is always between ${1\over2}-\epsilon$ and ${1\over2}+\epsilon.$ Given a subset $S$ of $\{0,1\}^n,$ define its $\epsilon$-{\em biased probability\/} to be the minimum of $Pr[x\in S]$ over all slightly-random sources $x$ with bias $\epsilon.$ We show that, for every fixed $\epsilon<{1\over2}$ and almost every subset $S$ of $\{0,1\}^n,$ the $\epsilon$-biased probability of $S$ is bounded away from 0. We also show that there exists a perfect-information, collective coin-flipping (and leader-election) protocol for $n$ players that tolerates $\epsilon n$ cheaters, for every $\epsilon<(2\sqrt{10}-5)/3\approx.44.$}

\T {A Binary Sequence Generator Based on Ziv-Lempel Source Coding}
\A {Cees J. A. Jansen}
\A {Dick E. Boekee}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {A new binary sequence generator is proposed, which is based on Ziv-Lempel source coding. In particular the Ziv-Lempel decoding algorithm is applied to codewords generated by linear feedback shift registers. It is shown that the sequences generated in this way have a high linear complexity and good statistical properties. This sequence generator can also be viewd at as an LFSR which is `filtered' by a nonlinear feedforward function containing memory. In the simplest case the sequence generator reduces to an LFSR filtered by a memoryless nonlinear feedforward function, thereby demonstrating that our construction can be seen to produce very efficient feedforward functions from a circuit complexity point of view.}

\T {Carmichael Functions}
\A {Eric Bach}
\J {Computer Science Technical Report TR 939, University of Wisconsin}
\D {1990}
\X {A Carmichael number is a composite number $n$ such that for every $a$ relatively prime to $n$, $a^{n-1}\equiv1$ modulo $n$. It is unknown whether infinitely many Carmichael numbers exist. The analogous question for polynomials over a finite field with $q$ elements asks if there are infinitely many reducible polynomials $f$ such that if $a$ and $f$ are coprime, then $a^{q^{{\rm deg}\ f}}\equiv1$ modulo $f$. We show this is true, and that such polynomials are rare compared to irreducibles.}

\T {Certainty from Uncertainty}
\A {Charles H. Bennet}
\J {Nature {\bf 362,} pp. 694--695}
\D {22 April 1993}

\T {Characterizing the Structures of Highly Nonlinear Cryptographic Functions}
\A {J. Seberry}
\A {X. M. Zhang}
\A {Y. Zheng}
\J {Technical Report: 94--15, Dept. of Comp. Sc., University of Wollongong, NSW, Aust.}
\D {1994}
\X {This paper studies the properties and constructions of nonlinear
functions, which are a core component of cryptographic primitives
including data encryption algorithms and one-way hash functions.
A main contribution of this paper is to reveal the relationship
between nonlinearity and propagation characteristic, two
critical indicators of the cryptographic strength of a Boolean
function.  In particular, we prove that
\begin{enumerate}
\item[(i)] if $f$, a Boolean function on $V_{n}$,
        satisfies the propagation criterion with respect to
        all but a subset $\Re$ of vectors in $V_{n}$,
        then the nonlinearity of $f$ satisfies
        $N_{f}\geq 2^{n-1}-2^{\frac{1}{2}(n+t)-1}$,
        where $t$ is the rank of $\Re$, and
\item[(ii)] When $|\Re| > 2$, the nonzero vectors in $\Re$
        are linearly dependent.
\end{enumerate}
Furthermore we show that
\begin{enumerate}
\item[(iii)] if $|\Re| = 2$ then $n$ must be odd,
        the nonlinearity of $f$ satisfies
        $N_{f}=2^{n-1}-2^{\frac{1}{2}(n-1)}$,
        and the nonzero vector in $\Re$
        must be a linear structure of $f$.
\item[(iv)] there exists no function on $V_n$
         such that $|\Re| = 3$.
\item[(v)] if $|\Re| = 4$ then $n$ must be even,
        the nonlinearity of $f$ satisfies
        $N_{f}=2^{n-1}-2^{\frac{1}{2}n}$,
        and the nonzero vectors in $\Re$
        must be linear structures of $f$.
\item[(vi)] if $|\Re| = 5$ then $n$ must be odd,
        the nonlinearity of $f$ is
        $N_{f} = 2^{n-1}-2^{\frac{1}{2}(n-1)}$,
        the four nonzero vectors in $\Re$,
        denoted by
        $\beta_{1}$, $\beta_{2}$, $\beta_{3}$ and $\beta_{4}$, 
        are related by the equation 
        $\beta_{1}\oplus \beta_{2}\oplus \beta_{3}\oplus \beta_{4}=0$,
        and {\em none\/} of the four vectors is
        a linear structure of $f$. 
\item[(vii)] there exists no function on $V_n$
         such that $|\Re| = 6$.
\end{enumerate}
We also discuss the structures of functions with $|\Re| = 2,4,5$.
In particular we show that these functions have close
relationships with bent functions, and can be easily
constructed from the latter.}

\T {Comments on `Cryptanalysis of Knapsack Ciphers Using Genetic Algorithms'}
\A {Rubin}
\J {Cryptologia, {\bf XVIII,} 2}
\D {1994}

\T {Common Authentication Technology Overview}
\A {J. Linn}
\J {RFC 1511}
\D {1993}

\T {Communication Complexity of Secure Computation}
\A {Matthew Franklin}
\A {Moti Yung}
\J {Proc. of the 24th ACM Symp. on the Theory of Computing}
\D {1992}
\X {A secret-ballot vote for a single proposition is an example of a secure distributed computation. The goal is for $n$ participants to jointly compute the output of some $n$-ary function (in this case, the sum of the votes), while protecting their individual inputs against some form of misbehavior. In this paper, we initiate the investigation of the communication complexity of unconditionally secure multi-party computation, and its relation with various fault-tolerant models. We present upper and lower bounds on communication, as well as tradeoffs among resources. First, we consider tge ``direct sum problem'' for communication complexity of perfectly secure protocols: Can the communication complexity of securely computing a single function $f:F^n\rightarrow F$ at $k$ sets of inputs be smaller if all are computed simultanesouly than if each is computed individually? We show that the answer depends on the failure model. A factor of $O({n\over\log n})$ can be gained in the privacy model (where processors are curious but correct); specifically, when $f$ is $n$-ary addition (mod 2), we show a lower bounds of $\Omega(n^2)$ bits for computing $f$ once and an upper bound of $O(n^2\log n)$ for computing $f$ $O(n)$ times simultaneously. No gain is possible in a slightly stronger fault model (fail-stop mode); specifically, when $f$ is $n$-ary addition over $GF(q),$ we show an exact bound of $\Theta(kn^2\log q)$ for computing $f$ at $k$ sets of inputs simultaneously (for any $k\ge 1).$ However, if one is willing to pay an additive cost in fault tolerance (from $t$ to $t-k+1$), then a variety of known non-cryptographic protocols (including ``provably unparallelizable'' protocols from above!) can be systematically compiled to compute one function at $k$ sets of inputs {\sl with no increase in communication complexity.} Our compilation technique is based on a new compression idea of polynomial-based multi-secret sharing. Lastly, we show how to compile private protocols into error-detecting protocols at a big savings of a factor of $O(n^3)$ (up to a log factor) over the best known error-correcting protocols. This is a new notion of fault-tolerant protocols, and is especially useful when malicious behavior is infrequent, sice error-detection implies error-correction in this case.}

\T {Comparison of Block Ciphers}
\A {Helen Gustafson}
\A {Ed Dawson}
\A {Bill Caelli}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {Several DES replacement block ciphers had been published. In this paper a report will be given on the development of a package for analysis and comparison of block ciphers. Experimental results are presented on applying this package to DES, FEAL-N, and Madryga ciphers.}

\T {Complexity of the Max Word Problem (and the Power of One-way Interactive Proof Systems), the}
\A {Anne Condon}
\J {Computer Science Technical Report TR 952, University of Wisconsin}
\D {1990}
\X {We study the complexity of the max word problem for matrices, a variation of the well-known word problem for matrices. We show that the problem is NP-complete, and cannot be approximated within any constant factor, unless P = NP. We describe applications of this result to probabilistic finite state automata, rational series and k-regular sequences. Our proof is novel in that it employs the theory of interactive proof systems, rather than a standard reduction argument. As another consequence of our results, we characterize NP exactly in terms of one-way interactive proof systems.}

\T {The Composibility of Behaviorally Secure Systems}
\A {Ping Lin}
\J {Ph.D. Thesis (CSRI--250), University of Toronto}
\D {1991}

\T {Computation of Discrete Logarithms in Prime Fields}
\A {Brian A. LaMacchia}
\A {Andrew M. Odlyzko}
\J {Designs, Codes, and Cryptography, {\bf 1,} pp. 46--62}
\D {1991}

\T {Computers at Risk: Safe Computing In the Information Age}
\A {{National Research Council}}
\J {National Academy Press}
\D {1991}
\X {Overview and recommendations, the growing potential for system abuse,
concepts of information security, security policies, technology to achieve
secure computer systems, models, programming methodology, criteria to evaluate
computer and network security, why the security market has not worked well, the
need to establish an information security foundation.}

\T {Computer Security and Industrial Cryptography: State of the Art and Evolution}
\A {Bart Preneel}
\A {Ren\'e Govaerts}
\A {Joos Vanderwalle}
\J {Lecture Notes in Computer Science(741), Springer-Verlag}
\D {1993}
\X {Individual papers listed elsewhere in this document.}

\T {Computer Security Basics}
\A {Deborah Russel}
\A {G. T. Gangemi Sr.}
\J {O'Reilly and Associates, Sebastopol, CA}
\D {1991}

\T {Computer Viruses---A Form of Artificial Life?}
\A {E. H. Spafford}
\J {Technical Report 985, Purdue University}
\D {1990}

\T {Confirmation that Some Hash Functions Are Not Collision Free}
\A {Shoji Miyaguchi}
\A {Kazuo Ohta}
\A {Masahiko Iwata}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {Hash functions are used to compress messages into digital signatures. A hash function has to be collision free; i.e., it must be computationally infeasible to construct different messages which output the same hash-value. This paper shows that fiver hash functions are not collision free, including the assumptions that an attacker can modify an initial value of the hash function. These hash functions are analyzed from the standpoints of their structure, the complementation property and the weak keys of the block ciphers used in them. As a result, it is clear that many pairs of messages can be created to generate the same hash-values. Therefore, users desiring to use these hash functions should be notified of their weakness.}

\T {Constructions of Bent Functions and Difference Sets}
\A {Kaisa Nyberg}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}

\T {Contemporary Cryptology: the Science of Information Integrity}
\E {G. Simmons}
\J {IEEE Press}
\D {1991}

\T {Content-MD5 Header Field, the}
\A {M. Rose}
\J {RFC 1544}
\D {1993}
\X {This memo specifies an optional header field, Content-MD5, for use with MIME-conformant messages.}

\T {Continued Fractions and the Berlekamp-Massey Algorithm}
\A {Zongduo Dai}
\A {Kencheng Zeng}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}

\T {The COPS Security Checker System}
\A {D. Farmer}
\A {E. H. Spafford}
\J {Technical Report 993, Purdue University}
\D {1990}

\T {Correlation Functions of Geometric Sequences}
\A {Agnes Hui Chan}
\A {Mark Goresky}
\A {Andrew Klapper}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {This paper consider the cross-correlation function values of a family of binary sequences obtained from finite geometries. These values are shown to depend on the intersection of hyperplanes in a projective space and the cross-correlation function values of the nonlinear feedforward functions used in the construction of the goemetric sequences.}

\T {Correlation Properties of Combiners with Memory in Stream Ciphers}
\A {Willi Meier}
\A {Othmar Staffelbach}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {In stream cipher design pseudo random generators have been proposed which combine the output of one or several LFSRs in order to produce the key stream. For memoryless combiners it is known that the product sequence has correlation to sums of certain LFSR-sequences whose correlation coefficients $c_i$ satisfy the equation $\sum_i c_i^2=1.$ It is proved that a corresponding result also hold for combiners with memory. If correlation probabilities are conditioned on side information, e.g. on known output digits, it is shown that new or stronger correlations may occur. This is exempified for the summation cipher with two LFSRs where such correlations can be exploited in a known plaintext attack. A cryptanalytic algorithm is given which is shown to be successful for LFSRs of considerable elngth and with arbitrary feedback connection.}

\T {Could a Machine Think?}
\A {Paul M. Churchland}
\A {Patricia Smith Churchland}
\J {Scientific American {\bf 262,} 1}
\D {1990}
\X {Machines that manipulate symbols according to rules may well never achieve
intelligence, but, the authors argue, the proposition does not have absolute
force. New kinds of systems (such as artificial neural networks) whose physical
organization mimics that of the brain might well succeed.}

\T {Cryptanalysis and Protocol Failures}
\A {Gustavus J. Simmons}
\J {CACM {\bf 37,} 11, pp.~56--65}
\D {1994}

\T {Cryptanalysis of a Public-Key Cryptosystem Based on Approximations by Rational Numbers}
\A {Jacques Stern}
\A {Philippe Toffin}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {At the Eurocrypt meeting, a public-key cryptosystem based on rational numbers has been proposed. We show that this system is not secure. Our attack uses the LLL algorithm. Numerical computations confirm that it is successful.}

\T {Cryptanalysis of Knapsack Ciphers Using Genetic Algorithms}
\A {Spillman}
\J {Cryptologia, {\bf XVII,} 4}
\D {1993}

\T {Cryptanalysis of Short RSA Secret Exponents}
\A {M. J. Wiener}
\J {IEEE Trans. Information Theory {\bf 36,} 3, pp. 553--558}
\D {1990}
\X {A cryptanalytic attack on the use of short RSA secret exponents is described. The attack makes use of an algorithm based on continued fractions that finds the numerator and denominator of a fraction in polynomial time when a close enough estimate of the fraction is given. The public exponent $e$ and the modulus $pq$ can be used to give an estimate of a fraction that involves the secret exponent $d.$ The algorithm based on continued fractions uses this estimate to disciver relatively short secret exponents. For a typical case where $e<pq,$ $(p-1)(q-1)$ is small, and $p$ and $q$ have approximately the same number of bits, this attack will discover secret exponents with up yo approximately one-quarter as many bits as the modulus. Ways to com? this attack, ways to improve ir, and two open problems are described. This attack poses no threat to the normal case of RSA where the secret exponent is approximately the same size as the modulus. This is ? this attack uses information provided by the public exponent ? normal case, the public exponent can be chosen almost ? of the modulus.}

\T {Cryptanalysis of the Chaotic-Map Cryptosystem Suggested at EUROCRYPT'91}
\A {E. Biham}
\J {Advances in Cryptology---EUROCRYPT'91, Lecture Notes in Computer Science, pp.~532--534}
\D {1991}

\T {Cryptographic Defense Against Traffic Analysis}
\A {Charles Rackoff}
\A {Daniel R. Simon}
\J {25th ACM STOC}
\D {1993}
\X {We present a model which allows us formally to define ``untraceability'' of messages in a network of synchronously communicating processors. We consider several different definitions, based on different assumptions about the strength of the ``adversary'' attempting to identify the senders and receivers of messages; for example, the adversary may be able to control some of the processors to obtain information, or even disrupt the traffic in the network. We present efficient protocols which are provably secure against each such adversary, using such cryptographic techniques as secure multiparty computation and non-interactive zero-knowledge proof. One proof of security also relies on an interesting general lemma about the ``mixing'' achieved by certain kinds of random processes, or ``shuffles'', performed on a set of items.}

\T {Cryptographic Hardness of Distribution-specific Learning}
\A {Michael Kharitonov}
\J {25th ACM STOC}
\D {1993}
\X {We investigate cryptographic lower bounds on the learnability of Boolean formulas and constant depth circuits on the uniform distribution and other specific distributions. We first show that weakly learning Boolena formulas and constant depth threshold circuits with membership queries on the uniform distribution in polynomial time is as hard as factoring Blum integers (or inverting RSA, or deciding quadratic residuosity). We formalize the notion of a trvially learnable distribution and extend these hardness results to all non-trivial distributions. Moreover, we show that under appropriate assumptions on the hardness of factoring, the learnability of Boolean formulas and constant depth threshold circuits on any distribution is characterized by the distribution's Renyi entropy. Furthermore, we show that a sub-exponential lower bound for factoring implies a $\Omega(2^{\log^{\beta\cdot d}n})$ lower bound (for some constant $\beta$) for learning Boolean circuits of depth $d$ on the uniform distribution (with membership queries), which matches the upper bound of Linial, Mansour, and Nisan. From this we conclude that, assuming such a lower bound for factoring, there is no $O(n^{poly \log n})$ algorithm to learn all of $AC^0$ on the iniform distribution. We observe that, under cryptographic assumptions, all our bounds can be used to establish tradeoffs between the running time and the number of samples necessary to learn.}

\T {A Cryptographic Library for the Motorola DSP56000}
\A {Stephen R. {Duss\'e}}
\A {Burton S. {Kaliski Jr.}}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {We describe a cryptographic library for the Motorola DSP56000 that provides hardware speed yet software flexibility. The library includes modular arithmetic, DES, message digest and other methods. Of particular interest is an algorithm for modular multiplication that interleaves multiplication with Montgomery modular reduction to give a very fast implementation of RSA.}

\T {Cryptographic Protocol for Secure Communications}
\A {S. M. Bellovin}
\A {M. Merritt}
\J {US Patent \#5241599}
\D {1993}

\T {Cryptography Policy}
\A {lance J. Hoffman}
\A {Faraz A. Ali}
\A {Steven L. Heckler}
\A {Ann Huybrechts}
\J {C ACM {\bf 37,} 9}
\D {1994}

\T {Cryptography Within Phase I of the EEC-RACE Programme}
\A {Antoon Bosselaers}
\A {Ren\'e Govaerts}
\A {Joos Vandewalle}
\J {Computer Security and Industrial Cryptography, Lecture Notes in Computer Science(741), Springer-Verlag}
\D {1993}
\X {In order to pave the way towards commercial use of Integrated Broadband Communications (IBC) in Europe, the Commission of the European Communities has launched the RACE programme. Under this RACe programme pre-competitive and per-normative work is going on. Most advanced applications in IBC and many services rely on the cost efffective provision of integrity mechanisms. Within the first phase of the RACE programme (RACE I) three projects were preoccupied with the provision of these mechanisms in a universal and unified manner to all users of IBC. While project R1025 looked at the overall IBC needs by providing the functional specifications for the global provision of security, projects R1040 and R1047 were providing the necessary technology base. The goal of the R1040-RIPE consortium was to put forward an ensemble of techniques to meet the anticipated requriements of the future IBC Network in the European Community. A description of the achievements of the RIPE project is given.}

\T {Crypto Policy Perspectives}
\A {Susan Landau}
\A {Stephen Kent}
\A {Clint Brooks}
\A {Scott Charney}
\A {Dorothy Denning}
\A {Whitfield Diffie}
\A {Anthony Lauck}
\A {Douglas Miller}
\A {Peter Neumann}
\A {David Sobel}
\J {C ACM {\bf 38,} 8, pp.~115--120}
\D {1994}

\T {Cryptosystem for Group Orientated Cryptography}
\A {Tzonelih Hwang}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {A practical non-interactive scheme is proposed to simultaneously solve several open problems in group oriented cryptography. The sender of the information is allowed to determine the encryption/decryption keys as well as the information destination without any coordination with the receving group. The encrypted message is broadcasted to the receving group and the receivers may authenticate themselves for legitimacy of the information directly from the ciphertext. The security of the scheme can be shown to be equivalent to the difficulty of solving the discrete logarithm problem.}

\T {DASS---Distributed Authentication Security Service}
\A {C. Kaufman}
\J {RFC 1507}
\D {1993}

\T {Decoding a VCR Controller Code}
\A {K. Shirriff}
\A {C. Welsh}
\A {A. Kinsman}
\J {Cryptologia {\bf 16,} 3, pp. 227--234}
\D {1992}

\T {Decrypting the Puzzle Palace}
\A {J. P. Barlow}
\J {C ACM {\bf 35,} 7, pp. 25--31}
\D {1992}

\T {Definitions of Managed Objects for the Security Protocols of the Point-to-Point Protocol, the}
\A {F. Kastenholz}
\J {RFC 1472}
\D {1993}
\X {This memo defines a portion of the Management Information Base (MIB) for use with network management protocols in TCP/IP-based internets. In particular, it describes managed objects used for managing the Security Protocols on subnetwork interfaces using the family of Point-to-Point Protocols.}

\T {Demonstrating Possession without Revealing Factors and its Application}
\A {Hiroki Shizuya}
\A {Kenji Koyama}
\A {Toshiya Itoh}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {This paper presents a zero-knowledge interactive protocol that demonstates that {\sl two\/} factors, $a$ and $b$, of a composite number $n$ ($=ab$) are actually known by the prover, without revelation of the factors themselves and where $a$ and $b$ are not necessarily primes. The security of this protocol is based on the difficulty of computing a discrete logarithm modulo a large prime. As an extension of this, a protocol that can demonstrate that {\sl two\/} or {\sl more\/} factors are known by the prover is shown and applied to a weighted membership protocol with hierarchical classes within a group.}

\T {Denial of Service: An Example}
\A {Roger M. Needham}
\J {CACM {\bf 37,} 11, pp.~42--46}
\D {1994}

\T {DES Watch: An Examination of the Sufficiency of the Data Encryption Standard for Financial Institutions in the 1990's}
\A {G. Garon}
\A {R. Outerbridge}
\J {Cryptologia {\bf XV,} 3, pp. 177--193}
\D {1991}

\T {Design and Analysis of Efficient Lossless Data Compression Systems, the}
\A {Paul Glor Howard}
\J {Doctoral Thesis, Dept. of Computer Science, Brown University, Providence, R. I. 02912--1910}
\Q {001}
\D {1993}
\X {Our thesis is that high compression efficiency for text and images can be obtained by using sophisticated statistical compression techniques, and that greatly increased speed can be achieved at only a small cost in compression efficiency. Our emphasis is on elegant design and mathematical as well as empirical analysis. We analyze arithmetic coding as it is commonly implemented and show rigorously that almost no compression is lost in the implementation. We show that high-efficiency lossless compression of both text and grayscale images can be obtained by using appropriate models in conjunction with arithmetic coding. We introduce a four-component paradigm for lossless image compression and present two methods that give state of the art compression efficiency. In the text compression area, we give a small improvement on the preferred method in the literature. We show that we can often obtain significantly improved throughput at the cost of slightly reduced compression. The extra speed comes from simplified coding and modeling. Coding is simplified by using prefix codes when arithmetic coding is not necessary, and by using a new practical version of arithmetic coding, called {\em quasi-arithmetic coding,} when the precision of arithmetic coding is needed. We simplify image modeling by using small prediction contexts and making plausible assumptions about the distributions of pixel intensity values. For text modeling we use self-organizing-list heuristics and low-precision statistics.}

\T {Designing Stronger Algorithms}
\A {Ross J. Anderson}
\J {Proc Infosec 90 pp. 59--70}
\D {1990}
\X {Cryptographic algorithm design is often described in the literature as an
analytic process, yet provable security remains elusive and the majority of
strong algorithms are actually the outcome of a Darwinian process. An algorithm
is strong if it survives attack by a lot of bright people, and when algorithms
are broken we can often `mutate' them slightly so that they retain their
desirable properties, but not the newly discovered weakness. To illustrate the
point, an equivalent machine attack is shown on a new cipher feedback system
which has some mathematical justification but no evolutionary history.}

\T {Differential Cryptanalysis Mod $2^{32}$ with Applications to MD5}
\A {T. Berson}
\J {Advances in Cryptology---EUROCRYPT'92, Lecture Notes in Computer Science, pp.~71--80}
\D {1992}

\T {Differential Cryptanalysis of DES-like Cryptosystems}
\A {E. Biham}
\A {A. Shamir}
\J {J of Cryptology {\bf 4,} 1, pp. 3--72}
\D {1991}
\J {Advances in Cryptology---CRYPTO'90, Lecture Notes in Computer Science, pp.~2--21}
\D {1991}

\T {Differential Cryptanalysis of Feal and N-Hash}
\A {E. Biham}
\A {A. Shamir}
\J {Advances in Cryptology---EUROCRYPT'91, Lecture Notes in Computer Science, pp.~1--16}
\D {1991}

\T {Differential Cryptanalysis of Snefru, Khafre, REDOC-II, LOKI and LUCIFER}
\A {E. Biham}
\A {A. Shamir}
\J {Advances in Cryptology---CRYPTO'91, pp. 156--171}
\D {1992}

\T {Differential Cryptanalysis of the Data Encryption Standard}
\A {Eli Biham}
\A {Adi Shamir}
\J {Springer-Verlag}
\D {1993}
\X {In this book, we develop a new type of cryptanalytic attack which can be successfully applied to many iterated cryptosystems and hash functions. It is primarily a chosen plaintext attack but under certain circumstances, it can also be applied as a known plaintext attack. We call it ``differential cryptanalysis'', since it analyzes the evolution of differences when two related plaintexts are encrypted under the same key. Differential cryptanalysis is the first published attack which is capable of breaking the full 16-round DES in less than $2^{55}$ complexity. The data analysis phase computes the key by analyzing about $2^{36}$ ciphertexts in $2^{37}$ time. The $2^{36}$ usable ciphertexts are obtained during the data collection phase from a larger pool of $2^{47}$ chosen plaintexts by a simple bit repetition criteria which discards more than 99.9\% of the ciphertexts as soon as they are generated. This attack can be applied to a wide variety of DES-like substitution/permutation cryptosystems, and it demonstrates the crucial role of each element in their design. In particular, we show that almost any structural modification of DES leads to a much weaker cryptosystem, and that DES reduced to eight rounds is so weak that it can be broken in two minutes on a personal computer. The attack is also applicable to bounded-round versions of the cryptosystems FEAL, Khafre, REDOC-II, LOKI and Lucifer, and to the hash functions Snefru and N-Hash.}

\T {Differential Cryptanalysis of the Full 16-Round DES}
\A {E. Biham}
\A {A. Shamir}
\J {Advances in Cryptology---CRYPTO'92, Lecture Notes in Computer Science}
\D {1993}

\T {Digest Message Format}
\A {F. Wancho}
\J {RFC 1153}
\D {1990}
\X {High traffic volume large mailing lists began to appear on the net in the mid-70s. The moderators of those lists developed a digest message format to enclose several messages into one composite message for redistribution to the mailing list addressees. This format reduces the mailer load in proportion to the number of messages contained within a digest message, and conserves network bandwidth by reducing the size of the headers of the enclosed messages. This RFC documents the digest message format so that others may follow this format in creating (digestifying) and separating (undigestifying) digest messages to maintain compatibility with the programs expecting this de facto standard. Any editorial functions performed at the discretion of a digest moderator, such as discarding submissions, editing content to correct spelling and punctuation errors, inserting comments, and reformatting paragraphs to conform to width conventions are beyond the scope of this memo. This memo describes the de facto standard Digest Message Format. It is not meant to supersede nor replace the generic message encapsulation format described in RFC 934. It merely documents a particular message encapsulation format that existed well before RFC 934 was published and continues to be the format of choice for digest messages.}

\T {A Digital Signature Scheme and a Public-Key Cryptosystemsbased on Elliptic Curves over ${Z}^1_m$}
\A {Ueli M. Maurer}
\J {Technical Report: 91--39, Centre for Discrete Mathemantics and Theoretical Computer Science (DIMACS) Computer Science (DIMACS) at Rutgers University, New Jersey}
\D {1991}

\T {The Digital Signature Standard, Proposal and Discussion}
\A {NIST}
\J {C ACM {\bf 35,} 7, pp. 36--54}
\D {1992}

\T {DIMACS Workshop on Distributed Computing and Cryptography}
\A {Feigenbaum}
\A {Merritt}
\J {Technical Report: 90--41, Centre for Discrete Mathemantics and Theoretical Computer Science (DIMACS) Computer Science (DIMACS) at Rutgers University, New Jersey}
\D {1990}

\T {Direct Demonstation of the Power to Break Public-Key Cryptosystems}
\A {Kenji Koyama}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {This paper describes a method of proving that a prover (or a cryptanalyst) really knows a secret plaintext or a new code-breaking algorithm for a particular public-key cryptosystem, without revealing any information about the plaintext or algorithm itself. We propose a secure direct protocol which is more efficient than the conventional protocols. This protocol requires only two transmissions between a prover and a verifier. A general form of the secure direct protocol is shown. The explicit forms for the RSA cryptosystem and the discrete logarithm problem are also proposed.}

\T {The Discrete Log is Very Discreet}
\A {A. W. Schrift}
\A {A. Shamir}
\J {Proc. of the 22nd Annual ACM Symposium on the Theory of Computing}
\D {1990}
\X {In this paper we consider the one-way function $f_{g,N}(X)=g^X(\mod N)$, where $N$ is a Blum integer. We prove that under the commonly assumed intractability of factoring Blum integers, almost all its bits are individually hard, and half of them are simultaneously hard. As a result, $f_{g,N}$ can be used in efficient pseudo-random bit generators and multi-bit commitment schemes, where messages can be drawn according to arbitrary probability distributions.}

\T {Distributed Primality Proving and the Primality of $(2^{3539}+1)/3$}
\A {Fran\c cois Morain}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {We explain how the Elliptic Curve Primality Proving algorithm can be implemented in a distributed way. Applications are given to the certification of large primes (more than 500 digits). As a result, we describe the successful attempt at proving the primality of the 1065-digit $(2^{3539}+1)/3,$ the first {\em ordinary\/} Titanic prime.}

\T {Distributed User Identification By Zero-Knowledge Acces Rights Proving}
\A {J. Domingo-Ferrer}
\J {Info. Proc. Letters {\bf 40,} 5}
\D {1991}
\X {A scheme for identifying the rights of users to access files in a computer
network with many servers is presented. Users are granted rights by an
authority, and servers need only a certified list of available access rights in
order to perform access control. A server stores no information about the
users, neither access matrix nor passwords---{\sl user portability\/}---, which
enables the authority to perform user registration, rights granting and rights
revocation independently of servers; moreover, the latter two are public
operations in the clear. The number of rights shared by more than one user
throughout the network is a lower bound for the number of secret pieces held by
each user, but {\sl his unshared rights can be increased indefinitely without
changing or increasing his secret information.} Rights possession proofs are
zero-knowledge and simultaneous.}

\T {Does Licensing Require New Access Control Techniques?}
\A {Ralf C. Hauser}
\J {CACM {\bf 37,} 11, pp.~48--55}
\D {1994}

\T {Draft Working Implementation Agreements For Open Systems Interconnection Protocols}
\A {OSI Implementors' Workshop}
\J {NIST, Gaithersburg, Maryland, June}
\D {1992}

\T {Dyadic Matrices and Their Potential Significance in Cryptography}
\A {Yang Yi Xian}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {The concept of dyadic matrix was initially proposed for the purpose of design orthogonal matrices and multi-valued codes with perfect autocorrelation property. By now much work had been done in this area. In the following text we will show some other new results about the reversibility of dyadic matrices and their potential significance in cryptography.}

\T {Eavesdropping On Quantum Cryptographical Systems}
\A {A. Ekert (\& others)}
\J {Physical Review A50, pp. 1047}
\D {1994}

\T {Eavesdropping Using Quantum-Nondemolition Measurements}
\A {M. J. Werner}
\A {G. J. Milburn}
\J {Physical Review A {\bf 47,} 1}
\D {1993}
\X {We investigate the effects of photon-number quantum-nondemolition measurements performed by an eavesdropper on a two-photon correlated state. The relation between this model and quantum cryptography is discussed. It is shown that violation of Bell's inequality is very sensitive to the probe amplitude of the measurement system.}

\T {EDI Security}
\A {Gordon Lennox}
\J {Computer Security and Industrial Cryptography, Lecture Notes in Computer Science(741), Springer-Verlag}
\D {1993}
\X {Gordon Lennox is responsible for security activities in the TEDIS programme, a Community programme dealing with systems for the electronic transfer of trade data. He has also been involved in other EC projects: projects which dealth with the confidentiality and security of data, the protection of computer programmes, and the information society and its environment.}

\T {Efficient Computation on Oblivious RAMs}
\A {Rafail Ostrovsky}
\J {Proc. of the 22nd Annual ACM Symposium on the Theory of Computing}
\D {1990}
\X {A machine is {\sl oblivious\/} if the sequence in which it accesses memory locations is equivalent for any two programs with the same running time. For example, an oblivious Turing machine is one for which the movement of the heads on the tapes is identical for each computation. (Thus, it is independent of the actual input.) What is the slowdown in the running time of any machine, if it is required to be oblivious? In 1979 Pippenger and Fischer showed how a two-tape {\sl oblivious\/} Turing machine can simulate, on-line, a one-tape Turing machine, with a logarithmic slowdown in the running time. We show a similar result for the random access machine (RAM) model of computation, solving an open problem posed by Goldreich. In particular, we show how to do an on-line simulation of an arbitrary RAM program by a probabilistic RAM whose memory access pattern is independent of the program which is being executed, and with a poly-logarithmic slowdown in the running time. Our proof yields a technique of efficiently hiding (through randomization) the access pattern into any composite data-structure. As one of the applications, we exhibit a simple and efficient software protection scheme for a generic one-processor RAM model of computation.}

\T {Efficient Cryptographic Schemes Provably as Secure as Subset Sum}
\A {Russel Impagliazzo}
\A {Moni Naor}
\J {IEEE ?}
\D {1991?}
\X {We show very efficient constructions for a pseudo-random generator and for a universal one-way hash function baed on the intractability of the subset sum problem for certain dimensions. (Pseudo-random generators can be used for private key encryption and universal one-way hash functions for signature schemes). The increase in efficiency in our construction is due to the fact that many bits can be generated/hashed with one application of the assumed one-way function. All our constructions can be implemented in NC using an optimal number of processors.}

\T {Efficient ID-based Key Distribution with Tamperfree Devices}
\A {T. Hwang}
\J {Info. Proc. Letters {\bf 44,} 1}
\D {1992}
\X {An efficient ID-based key distribution scheme with sender authentication is
proposed. The security of the scheme is based on the tamperfreeness of a device
as well as the security of the underlying private-key cryptosystems. Each
user's tamperfree device contains distinct supersecret keys.}

\T {An Efficient Probabilistic Encryption Scheme}
\A {L. Harn}
\A {T. Kiesler}
\J {Info. Proc. Letters {\bf 34,} 3}
\D {1990}

\T {Efficient Zero-Knowledge Identification Schemes for Smart Cards}
\A {M. V. D. Burmester}
\A {Y. G. Desmedt}
\A {T. Beth}
\J {Comp. J. {\bf 35,} pp. 21--29}
\D {1992}

\T {Encrypted Key Exchange: Password-Based Protocols Secure Against Dictionary Attacks}
\A {S. M. Bellovin}
\A {M. Merritt}
\J {Proc. of the 1992 IEEE Comp. Soc. Conf. on Research in Security and Privacy, pp. 72--84}
\D {1992}

\T {Essentially $\ell$-fold Secure Authentication Systems}
\A {Albrecht Beutelspacher}
\A {Ute Rosenbaum}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {In this paper we first introduce the notion of essentially $\ell$-fold secure authentication systems; these are authentication systems in which the Bad Guy's chance to cheat after having observed $\ell$ messages is---up to a constant---best possible. Then we shall construct classes of essentially $\ell$-fold secure authentication systems; these systems are based on finite geometries, in particular spreads and quadrics in finite projective spaces.}

\T {Evaluation Criteria for IT Security}
\A {D. W. Roberts}
\J {Computer Security and Industrial Cryptography, Lecture Notes in Computer Science(741), Springer-Verlag}
\D {1993}
\X {After and Introduction which gives an outline of the paper's scope the first main sections considers the History of the development of the various criteria. This leads to a discussion of the Aims and Purposes of the various authors and sponsors in the main thrust of each of these documents; it is interesting and relevant to know what the authors thought they were doing. Clearly some of the criteria were written with very limited scope in view while others had wider briefs. With an understanding of the aims and purposes of the criteria and their authors and sponsors it is possible to assess the level of Achievement in the various programs; we can ask to what extent they fulfilled the purposes. One of the most interesting aspects of systems security is the balance between the needs of the various sectors; the traditional dichotomy of Civil versus Military is very pronounced in this field. A final section looks at the Prospects for the Future, both in terms of the standards-making bodies and in terms of user needs.}

\T {Experimental Demonstration of Quantum Cryptography Using Polarized Photons in Optical Fibre Over More Than 1 km}
\A {A. Muller (\& others)}
\J {Europhysics Letters {\bf 23,} p. 383}
\D {1993}

\T {Experimental Quantum Cryptography}
\A {Charles H. Bennett}
\A {Fran\c cois Bessette}
\A {Gilles Brassard}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {We describe initial results from an apparatus and protocol designed to implement {\em quantum public key distribution,} by which two users, who share no secret information initially: 1) exchange a random quantum transmission, consisting of very faint flashes of polarized light; 2) by subsequent public discussion of the sent and received versions of this transmission estimate the extent of eavesdropping that might have taken place on it, and finally 3) if this estimate is small enough, can distill from the sent and received versions a smaller body of shared random information (key), which is certifiably secret in the sense that any third party's expected information on it is an exponentially small fraction of one bit. Because the system depends on the uncertainty principle of quantum physics, instead of usual mathematical assumptions such as the difficulty of factoring, it remains secure against an adversary with unlimited computing power.}

\T {Exponentiating Faster with Addition Chains}
\A {Y. Yacobi}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {The similarity between fast computations with huge numbers and data compression is investigated. For example, in data-compression, frequent messages are assigned short codes, while in fast computations we store and reuse the results of frequent computations. In compression we sometimes send the difference of consecutive messages, if its usually small ($\Delta$ modulation), while in fast computation we compute $x^{n+\Delta}=x^nx^\Delta,$ if $x^n$ is already known, and $\Delta\ll n.$ We demonstrate the similarity by applying a modification of the Lempel-Ziv data compression algorithm to fast exponentiation, to result runtine which is comparable to the best known methods, in the practical range (500--1000 bits), for random exponents. For compressible exponentss we gain on the average the compression ratio. This may be applicable to Diffie-Hellman like cryptographic systems. It is an open question whether compressible exponents are safe.}

\T {Factoring Numbers Using Singular Integers}
\A {Loenard M. Adleman}
\J {Proc. of the 23rd Annual ACM Symp. on the Th. of Computing, pp. 64--71}
\D {1991}
\X {Recently, A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse and J. M. Pollard have introduced a new algorithm fir factoring integers of special form. Based on earlier work of Coopersmith, Odlyzko and Schroeppel and of Pollard, the new algorithm, the `number field sieve', is the fastest known for factoring integers of the form $r^e\pm s$ where $e$ and $s$ are small. The above authors riased the issue of generalizing the number field sieve to produce an efficient algorithm for all numbers. Beginning with the author's suggestion, together with those of Buhler and Pomerance we produce such a general purpose number field sieve along with an heuristic argument that it factors numbers in random time: $e^{c+o(1))(\log n)^{1/3}(\log\log n)^{2/3}}$ where $c<2.$}

\T {Factoring with Two Large Primes}
\A {A. K. Lenstra}
\A {M. S. Manasse}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}

\T {A Fair Protocol for Signing Contracts}
\A {Michael Ben-Or}
\A {Oded Goldreich}
\A {Silvio Micali}
\A {Ronald L. Rivest}
\J {IEEE Trans. on Info. Th. {\bf 36,} 1}
\D {1990}
\X {Two parties, $A$ and $B,$ want to sign a contract $C$ over a communication network. To do so, they must ``simultaneously'' exchange their commitments to $C.$ Since simultaneous exchange is usually impossible in practice, protocols are needed to approximate simultaneity by exchanging partial commitments in piece by piece manner. During such a protocol, one party or another may have a slight advantage; a ``fair'' protocol keeps this advantage within acceptable limits. We present a new protocol that is fair in the sense that, at any stage in its execution, the conditional probability that one party cannot commit both parties to the contract given that the other party can, is close to zero. This is true even if $A$ and $B$ have vastly different computing powers, and is proved under very weak cryptographic assumptions. Our protocol has the following additional properties: (1) during the procedure the parties exchange probabilistic options for commiting both parties to the contract; (2) the protocol never terminates in an asymmetric situation where party $A$ knows that party $B$ is commited to the contract while he is not; (3) the protocol makes use of a weak form of a third party (judge). If both $A$ and $B$ are honest, the judge will never be called upon. Otherwise, the judge rules by performing a simple computation. No bookkeeping is required of the judge.}

\T {A Fast Algorithm for Optimal Length-Limited Huffman Codes}
\A {L. L. Larmore}
\A {D. S. Hirschberg}
\J {J ACM {\bf 37,} 3}
\D {1990}
\X {An $O(nL)$-time algorithm is introduced for constructing an optimal Huffman
code for a weighted alphabet of size $n,$ where each code string must have
length no greater than $L.$ Yhe algorithm uses $O(n)$ space.}

\T {A Fast Iterative Algorithm for a Shift Register Initial State Reconstruction Given the Noisy Output Sequence}
\A {Miodrag J. {Mihaljevi\'c}}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {A novel fast algorithm for the correlation attack on a class of stream ciphers is proposed. The algorithm is based on the error correction principle and the finite-state matrix representation of a linear feedback shift register. Some general properties of the algorithm are pointed out and illustrated by some experimental results.}

\T {A Fast Modular-multiplication Module for Smart Cards}
\A {Hikaru Morita}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}

\T {Fast Perfect-Information Leader-Election Protocol with Linear Immunity}
\A {Jason Cooper}
\A {Nathan Linial}
\J {25th ACM STOC}
\D {1993}
\X {In this paper we develop a leader electrion protocol $P$ with the following features: 1. The protocol runs in the {\em perfect information\/} model: Every step taken by a player is visible to all others. 2. It has {\em linear immunity\/}: If $P$ is run by $n$ players and a coalition of $c_1n$ players deviates from the protocol, attempting to have one of them elected, their probability of success is $<1-c_2,$ where $c_1,c_2>0$ are absolute constants. 3. It is {\em fast\/}: The running time of $P$ is poly-logarithmic in $n,$ the number of players. A previous protocol by Alon and Naor achieving linear immunity in the perfect information model has a linear time complexity. The main ingredient of our protocol is a {\em reduction\/} subprotocol. This is a way for $n$ players to elect a subset of themselves which has the following property. Assume that up to $\epsilon n$ of the players are bad and try to have as many of them elected to the subset. Then with high probability, the fraction of bad players among the elected ones will not exceed $\epsilon$ in a significant way. The existence of such a reduction protocol is first established by a probabilistic argument. Later an explicit construction is provided which is based on the spectral properties of Ramanujan graphs.}

\T {Fast Signature Generation with a Fiat Shamir-like Scheme}
\A {H. Ong}
\A {C. P. Schnorr}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {We propose two improvements to the Fiat Shamir authentication and signature scheme. We reduce the communication of the Fiat Shamir authentication scheme to a single round while preserving the efficiency of the scheme. This also reduces the length og Fiat Shamir signatures. Using secret keys consisting of small integers we reduce the time for signature generation by a facotr 3 to 4. We propose a variation of our scheme using class groups that may be secure even if factoring large integers becomes easy.}

\T {A Fast Signature Scheme Based on Congruential Polynomial Operations}
\A {Tatsuaki Okamoto}
\J {IEEE Trans. on Info. Th. {\bf 36,} 1}
\D {1990}
\X {A new digital signature scheme is proposed in which the computation time is much shorter than that of the Rivest-Shamir-Adleman (RSA) scheme, while the key length and signature length are comparable to those for the RSA scheme. Moreover, the proposed scheme can be implemented easily and is, therefore, more practical for many digital signature applications. This new scheme is based on congruential polynomial operations whose degrees are more than three. The secret key consists of two large prime numbers, $p$ and $q,$ and the public key is their product, $n=p^2q.$ The security of this scheme depends on the difficulty of factorizing the number $n.$ Variations using the number of zeros succeeding the significant bit are also proposed.}

\T {Fast Software Encryption Functions}
\A {R. Merkle}
\J {Advances in Cryptology---CRYPTO '90, pp. 476--501, Springer-Verlag}
\D {1991}

\T {FFT Hashing Is Not Collision-Free}
\A {T. Baritaud}
\A {H. Gilbert}
\A {M. Girault}
\J {Advances in Cryptology---EUROCRYPT'92, Springer-Verlag, pp. 35--44}
\D {1993}

\T {File Security in WordPerfect 5.0}
\A {H. A. Bergen}
\A {W. J. Caelli}
\J {Cryptologia {\bf 15,} 1, pp. 57--66}
\D {1991}

\T {Finite State Verifiers I: The Power of Interaction}
\A {Cynthia Dwork}
\A {Larry Stockmeyer}
\J {J ACM {\bf 39,} 4, pp. 800--828}
\D {1992}
\X {An investigation of interactive proof systems (IPSs) where the verifier is
a 2-way probabilistic finite state automaton (2pfa) is initiated. In this
model, it is shown: (1) IPSs in which the verifier uses private randomization
are strictly more powerful than IPSs in which the random choices of the
verifier are made public to the prover. (2) IPSs in which the verifier uses
public randomization are strictly more powerful than 2pfa's alone, that is,
without a prover. (3) Every language which can be accepted by some
deterministic Turing machine in exponential time can be accepted by some IPS.
Additional results concern two other classes of verifiers: 2pfa's that halt in
polynomial expected time, and 2-way probabilistic pushdown automata that halt
in polynomial time. In particular, IPSs with verifiers in the latter class are
as powerful as IPSs where verifiers are polynomial-time probabilistic
Turing machines. In a companion paper, zero knowledge IPSs with 2pfa verifiers
are investigated.}

\T {Finite State Verifiers II: Zero Knowledge}
\A {Cynthia Dwork}
\A {Larry Stockmeyer}
\J {J ACM {\bf 39,} 4, pp. 829--858}
\D {1992}
\X {The zero knowledge properties of interactive proof systems (IPSs) are
studied in the case that the verifier is a 2-way probabilistic finite state
automaton (2pfa). The following results are proved: (1) There is a language $L$
such that $L$ has an IPS with 2pfa verifiers but $L$ has no zero knowledge IPS
with 2pfa verifiers. (2) Consider the class of 2pfa's that are sweeping and
that halt in polynomial expected time. There is a language $L$ such that $L$
has a zero knowledge IPS with respect to this class of verifiers, and $L$
cannot be recognized by any verifier in the class on its own.}

\T {A Formal Proof to a Basic Fact in Pseudorandom Generation}
\A {Xiangdong Yu}
\J {Technical Report: CUCS-046-91, University of Columbia}
\D {1991}
\X {In the definition of cryptographically strong pseudorandom
generator $1/poly(n)$ is used as the criterion for the difference of
probabilities with which testers correctly predict the next bit of a
generator.  Intuitively, a super tester, such as an exponential time
tester, can predict with maximum accuracy and thus can make the maximum
difference from predicting by blind guessing.  We prove, this maximum
difference is always greater than $1/p(n)$ for $p(n)=2(n+1)$ therefore
no generator can be strong for a super tester. In other words,
pseudorandom is really ``pseudo'' with respect to this criterion.}

\T {Formal Specification and Verification of Secure Communication Protocols}
\A {Svein J. Knapskog}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}

\T {Further Comments on the Soviet Encryption Algorithm}
\A {C. Charnes}
\A {L. O'Connor}
\A {J. Pieprzyk}
\A {R. Safavi-Naini}
\A {Y. Zheng}
\J {Technical Report: 94--9, Dept. of Comp. Sc., University of Wollongong, NSW, Aust.}
\D {1994}
\X {The paper analyses components of GOST Russian encryption
algorithm. First general algebraic properties are described
and the GOST algorithm is compared to the DES algorithm.
Avalanche characteristic of the adder used to mix keys
and partial cryptograms is examined. Cyclic shifts used
to diffuse changes of bits is considered.
A part of the secret key in GOST are S-boxes. Later we
show how users can generate S-boxes for the algorithm.
At the end we comment on diffrential cryptanalysis and 
linear cryptanalysis of the GOST.}

\T {GAC---the Criterion for Global Avalanche Characteristics of Cryptographic Functions}
\A {J. Seberry}
\A {X. M. Zhang}
\A {Y. Zheng}
\J {Technical Report: 94--14, Dept. of Comp. Sc., University of Wollongong, NSW, Aust.}
\D {1994}
\X {We show that some widely accepted criteria for cryptographic
Boolean functions, including the strict avalanche criterion (SAC)
and the propagation criterion, have various limitations in 
capturing properties of vital importance to cryptographic
algorithms, and propose a new criterion called GAC to measure
the global avalanche characteristics of cryptographic functions.
We also introduce two indicators related to the new criterion,
one forecasts the {\em sum-of-squares\/} while the other
the {\em absolute\/} avalanche characteristics of a function. 
Lower and upper bounds on the two indicators are derived,
and two methods are presented to construct cryptographic
functions that achieve nearly optimal global avalanche
characteristics.}

\T {General Public Key Residue Cryptosystems and Mental Poker Protocols}
\A {Kaoru Kurosawa}
\A {Yutaka Katayama}
\A {Wakaha Ogata}
\A {Shigeo Tsujii}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {This paper presents a general method how to construct public key cryptosystems based on the $r$-th residue problem. Based on the proposed method, we present the first mental poker protocol which can shuffle any set of cards. Its fault tolerant version is given, too. An efficient zero knowledge interactive proof system for quadratic non-residuosity is also shown.}

\T {Generic Security Service API : C-bindings}
\A {J. Wray}
\J {RFC 1509}
\D {1993}
\X {This document specifies C language bindings for the Generic Security Service Application Program Interface (GSS-API), which is described at a language-independent conceptual level in other documents. The Generic Security Service Application Programming Interface (GSS- API) provides security services to its callers, and is intended for implementation atop alternative underlying cryptographic mechanisms. Typically, GSS-API callers will be application protocols into which security enhancements are integrated through invocation of services provided by the GSS-API. The GSS-API allows a caller application to authenticate a principal identity associated with a peer application, to delegate rights to a peer, and to apply security services such as confidentiality and integrity on a per-message basis.}

\T {Generic Security Service Application Program Interface}
\A {J. Linn}
\J {RFC 1508}
\D {1993}
\X {This Generic Security Service Application Program Interface (GSS-API) definition provides security services to callers in a generic fashion, supportable with a range of underlying mechanisms and technologies and hence allowing source-level portability of applications to different environments. This specification defines GSS-API services and primitives at a level independent of underlying mechanism and programming language environment, and is to be complemented by other, related specifications: Documents defining specific parameter bindings for particular language environments. Documents defining token formats, protocols, and procedures to be implemented in order to realize GSS-API services atop particular security mechanisms.}

\T {Guidelines for the Secure Operation of the Internet}
\A {S. Crocker}
\A {B. Fraser}
\A {R. Pethia}
\J {RFC 1281}
\D {1991}
\X {The purpose of this document is to provide a set of guidelines to aid in the secure operation of the Internet. During its history, the Internet has grown significantly and is now quite diverse. Its participants include government institutions and agencies, academic and research institutions, commercial network and electronic mail carriers, non-profit research centers and an increasing array of industrial organizations who are primarily users of the technology. Despite this dramatic growth, the system is still operated on a purely collaborative basis. Each participating network takes responsibility for its own operation. Service providers, private network operators, users and vendors all cooperate to keep the system functioning. It is important to recognize that the voluntary nature of the Internet system is both its strength and, perhaps, its most fragile aspect. Rules of operation, like the rules of etiquette, are voluntary and, largely, unenforceable, except where they happen to coincide with national laws, violation of which can lead to prosecution. A common set of rules for the successful and increasingly secure operation of the Internet can, at best, be voluntary, since the laws of various countries are not uniform regarding data networking. Indeed, the guidelines outlined below also can be only voluntary. However, since joining the Internet is optional, it is also fair to argue that any Internet rules of behavior are part of the bargain for joining and that failure to observe them, apart from any legal infrastructure available, are grounds for sanctions.}

\T {HAVAL --- One-Way Hashing Algorithm with Variable Length of Output, a}
\A {Yuliang Zheng}
\A {Josef Pieprzyk}
\A {Jennifer Seberry}
\J {Technical report: tr-93-9, Centre for Computer Security Research, University of Woolongong, NSW, Australia}
\D {1993}
\X {A one-way hashing algorithm is a deterministicalgorithm that compresses an arbitrary long message into a value of specified length.The output value represents the fingerprint or digest of the message.A cryptographically useful property of a one-way hashing algorithmis that it is infeasibleto find two distinct messages that have the same fingerprint. This paper proposes a one-way hashing algorithm called HAVAL.HAVAL compresses a message of arbitrary length into a fingerprint of128, 160, 192, 224 or 256 bits.In addition, HAVAL has a parameter that controls the number of passes a message block (of 1024 bits) is processed.A message block can be processed in 3, 4 or 5 passes.By combining output length with pass,we can provide fifteen (15) choices for practical applications where different levels of security are required.The algorithm is very efficient and particularly suited for32-bit computers which predominate the current workstation market. Experiments show that HAVAL is$60\%$ faster than MD5 when 3 passes are required,$15\%$ faster than MD5 when 4 passes are required,andas fast as MD5 when full 5 passes are required.It is conjectured that finding two collision messagesrequires the order of $2^{n/2}$ operations,where $n$ is the number of bits in a fingerprint.}

\T {Hiding Instances in Zero-Knowledge Proofs}
\A {D. Beaver}
\A {J. Feigenbaum}
\A {V. Shoup}
\J {Advances in Cryptology---CRYPTO '90, Springer-Verlag, pp. 326--338}
\D {1991}

\T {Highly Nonlinear Balanced Boolean Functions Satisfying High Degree Propagation Criterion}
\A {Jennifer Seberry}
\A {Xian-Mo Zhang}
\A {Yuliang Zheng}
\J {Technical report: tr-93-1, Centre for Computer Security Research, University of Woolongong, NSW, Australia}
\D {1993}
\X {Three of the most important nonlinearity criteria forcryptographically strong functions arebalancedness, nonlinearity and propagation criterion.In this paper we study systematic methods for constructinghighly nonlinear balanced Boolean functionssatisfying the high degree propagation criterion.In particular, we present a method for constructinghighly nonlinear balanced Boolean functionson $V_{2k+1}$ satisfying the propagation criterion with respect to{\em all but one\/} vectors in $V_{2k+1}$,and a method for constructing highly nonlinear balancedBoolean functionson $V_{2k}$ satisfying the propagation criterion with respect to{\em all but three\/} vectors in $V_{2k}$.We then show that the vectors where the propagation criterionis not satisfied can be moved upward in such a way thatthe functions constructed on $V_{2k+1}$satisfy the propagation criterion of degree $2k$,while the function constructed on $V_{2k}$satisfy the propagation criterion of degree $\frac{4}{3}k$.The moving technique does not alter the balancednessand nonlinearity of the functions.The methods are illustrated by concrete constructionsof such cryptographically strong functions.The algebraic degrees of the functions are also discussed.}

\T {The History and Status of the P versus NP Question}
\A {Michael Sipser}
\J {Proc. of the 24th Annual ACM Symp. on the Theory of Computing}
\D {1992}

\T {How to Broadcast a Secret}
\A {S. Berkovitz}
\J {Advances in Cryptology---EUROCRYPT'91, Lecture Notes in Computer Science, pp.~535--541}
\D {1991}

\T {How to Construct Pseudorandom Permutations from Single Pseudorandom Functions}
\A {Josef Pieprzyk}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {This paper examines permutation generators which are designed using four rounds of the Data Encryption Standard and a single pseudorandom function. We have proved that such generators are pseudorandom only if the pseudorandom function is used internally at least five times. The proof is given using two different approaches: deterministic and probabilistic. Some cryptographic implications are also discussed.}

\T {How to Predict Congruential Generators}
\A {Hugo Krawczyk}
\J {J. of Algorithms {\bf 13,} 4, pp. 527--545}
\D {1992}
\X {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_0,s_1,\ldots,$ where $s_i$ is computed by the recurrence
$s_i\equiv\sum_{j=1}^k\alpha_j\Phi_j(s_0,s_1,\ldots,s_{i-1})(\mod m)$ for
integers $m$ and $\alpha_j,$ and integer-valued functions $\Phi_j,$ $j=1,\ldots
k.$ The predictors know the functions $\Phi_j$ in advance and have access to
the elements of the sequence prior to the element begin predicted, but they do
not know the modulus $m$ or the coefficients $\alpha_j$ with which the
generator actually works. We prove that both the number of mistakes made by the
predictors and the time complexity of each prediction are bounded by a
polynomial in $k$ and log $m,$ provided that the functions $\Phi_j$ are
computable (over the integers) in polynomial time. This extends previous
results about the predictability of such generators. In particular, we prove
that multivariate polynomial generators, i.e., generators where $s_i\equiv
P(s_{i-n},\ldots,s_{i-1})(\mod m),$ for a polynomial $P$ of known degree in $n$
variables, are efficiently predictable.}

\T {How to Sign Given Any Trapdoor Permutation}
\A {Mihir Bellare}
\A {Silvio Micali}
\J {J ACM {\bf 39,} 1}
\D {1992}
\X {A digital signature scheme is presented, which is based on the existence of
any trapdoor permutation. The scheme is secure in the strongest possible
natural sense: namely, it is secure against existential forgery under adaptive
chosen message attack.}

\T {How to Time-Stamp a Digital Document}
\A {S. Haber}
\A {W. S. Stornetta}
\J {Advances in Cryptology--- Crypto '90, Proceedings, Springer-Verlag}
\D {1990}
\J {Technical Report: 90--80, Centre for Discrete Mathemantics and Theoretical Computer Science (DIMACS) Computer Science (DIMACS) at Rutgers University, New Jersey}
\D {1990}

\T {Identification Tokens or: Solving the Chess Grandmaster Problem}
\A {T. Beth}
\A {Y. Desmedt}
\J {Advances in Cryptology---CRYPTO'90, Lecture Notes in Computer Science, pp.~169--176}
\D {1991}

\T {An Identity-Based Identification Scheme Based on Discrete Logarithms Modulo a Composite Number}
\A {Marc Girault}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {We first describe a modification of Schnorr's identification scheme, in which the modulus is composite (instead of prime). This modificationhas some similarity with Brickell-McCurley's one, presented at the same conference. Then, by establishing a new set-up, we derive the first identity-based identification scheme based on discrete logatirhms. More precisely, it is based on discrete logarithm modulo a composite number, a problem known to be harder than factorization problem. This scheme has interesting and somewhat paradoxical features. In particular, any user can choose his own secret, and, provided the parameters have convenient sizes, even the trusted center is unable to retrieve it from the public key (contrary to any identity-based scheme known until now).}

\T {An Implementation for a Fast Public-Key Cryptosystem}
\A {G. B. Agnew}
\A {R. C. Mullin}
\A {I. M. Onyszchuk}
\A {S. A. Vanstone}
\J {J. of Cryptology {\bf 3,} 2, pp. 63--79}
\D {1991}

\T {Implementation Notes on bdes(1)}
\A {Matt Bishop}
\J {Dartmouth College Computer Science Technical Report PCS-TR91-158}
\D {1991}
\X {This note describes the implementation of bdes, the file encryption program being distributed in the 4.4 release of the Berkeley Software Distribution. It implements all modes of the Data Encryption Standard program.}

\T {Implementation of a Key Exchange Protocol Using Real Quadratic Fields}
\A {Renate Scheidler}
\A {Johannes A. Buchmann}
\A {Hugh C. Williams}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}

\T {The Implementation of Elliptic Curve Cryptosystems}
\A {Alfred Menezes}
\A {Scott Vanstone}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {Elliptic curves have been studied for amny years. Recent interest has revolved around their applicability to factoring integers and to cryptography. In this paper we explore the feasibility of implementing in hardware an arithmetic processor for doing elliptic curve computations over fields of characteristic two. The ellptic curve analogue of the ElGamal cryptosystem is also analyzed.}

\T {Improved Low-Density Subset Sum Algorithms}
\A {Matthijs J. Coster}
\A {Antoine Joux}
\A {Brian A. LaMacchia}
\A {Andrew M. Odlyzko}
\A {Claus-Peter Schnorr}
\A {Jacques Stern}
\J {Computational Complexity {\bf 2,} pp.~111--128}
\D {1992}
\X {The general subset sum problem is NP-complete. However, there are two algorithms, one due to Brickell and the other to Lagarias and Odlyzko, which in polynomial time solve almost all subset sum problems of sufficiently low density. Both methods rely on basis reduction algorithms to find short non-zero vectors in special lattices. The Lararias-Odlyzko algorithm would solve almost all subset sum problems of density $<0.6463\ldots$ in polynomial time if it could invoke a polynomial-time algorithm for finding the shortest non-zero vector in a lattice. This paper presents two modifications of that algorithm, either one of which would solve almost all problem of density $<0.9408\ldots$ if it could find shortest non-zero vectors in lattices. These modifications also yield dramatic improvements in practice when they are combined with known lattice basis reduction algorithms.}

\T {Improved Public Key Cryptosystems Secure Against Chosen Ciphertext Attacks}
\A {Y. Zheng}
\J {Department of Computer Science Technical Report, University of Wollongong, Preprint 94-1}
\D {1994}
\X {This note describes an improvement to the first two of the three public key cryptosystems proposed by Zheng and Seberry, which are provably secure against chosen ciphertext attacks. The improvement removes a shortcoming with the original cryptosystems, which occurs when they are used for both confidentiality and sender authentication purposes.}

\T {Improving the Critical Density of the Lagarias-Odlyzko Attack Against Subset Sum Problems}
\A {Antoine Joux}
\A {Jacques Stern}
\J {Fundamentals of Computation Theory, 8th International Conference, FCT'91, Proceedings, L.~Budach~(ed.) Lecture Notes in Computer Science (529), Springer-Verlag}
\D {1991}

\T {Improving the Efficiency and Reliability of Digital Time-Stamping}
\A {D. Bayer}
\A {S. Haber}
\A {W. S. Stornetta}
\J {Sequences II: Methods in Communication, Security, and Computer Science, Springer-Verlag, pp. 329--334.}
\D {1993}

\T {Improving the Security of Your UNIX System}
\A {David A. Curry}
\J {SRI International: ITSTD-721-FR-90-21, Menlo Park, CA, April}
\D {1990}

\T {Improving the Strict Avalanche Characteristics of Cryptographic Functions}
\A {Jennifer Seberry}
\A {Xian-Mo Zhang}
\A {Yuliang Zheng}
\J {Technical report: tr-93-9, Centre for Computer Security Research, University of Woolongong, NSW, Australia}
\D {1993}
\X {This letter presents a simple yet effectivemethod for transforming Boolean functionsthat do not satisfy the strict avalanche criterion (SAC)into ones that satisfy the criterion.Such a method has a wide range of applications in designing cryptographically strong functions,including substitution boxes (S-boxes) employedby common key block encryption algorithms.}

\T {Information Authentication: Hash Functions and Digital Signatures}
\A {Bart Preneel}
\A {Ren\'e Govaerts}
\A {Joos Vandewalle}
\J {Computer Security and Industrial Cryptography, Lecture Notes in Computer Science(741), Springer-Verlag}
\D {1993}
\X {The goal of this paper is to discuss technqiues for the protection of the authenticity of information. The theoretical background is sketched, but most attention is paid to overview the large number of practical constructions for symmetric authentication and digital signatures.}

\T {Inside RISKS: Alternative Passwords}
\A {Peter G. Neumann}
\J {C ACM {\bf 37,} 5, p.~146}
\D {1994}

\T {Inside RISKS: Expectations of Security and Privacy}
\A {Peter G. Neumann}
\J {C ACM {\bf 37,} 9, p.~138}
\D {1994}

\T {Inside RISKS: Risks of Passwords}
\A {Peter G. Neumann}
\J {C ACM {\bf 37,} 4, p.~126}
\D {1994}

\T {Inside RISKS: The Verdict on Plaintext Signatures: They're Legal}
\A {Benjamin Wright}
\J {C ACM {\bf 37,} 10, p.~122}
\D {1994}

\T {Instant Teleportation}
\A {Tony Sudbery}
\J {Nature {\bf 362,} pp. 586--587}
\D {15 April 1993}

\T {An Interactive Identification Scheme Based on Discrete Logarithms and Factoring}
\A {Ernest F. Brickell}
\A {Kevin S. McCurley}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {We desribe a modification of an interactive identification scheme of Schnorr intended for use by smart cards. Schnorr's original scheme had its security based on the difficulty of factoring discrete logarithms. The modification that we present here will remain secure if wither of two computational problems in infeasible, namely factoring a large integer and computing a discrete logarithm. For this enhanced security we require somewhat more communication and computational power, but the requirements remain quite modest, so that the scheme is well suited for use in smart cards.}

\T {Interactive Proof Systems with Polynomially Bounded Strategies}
\A {Ladner}
\A {Condon}
\J {Technical Report: TR 92-04-07, Dept. of Computer Science, University of Washington}
\D {1992}
\X {Interactive proof systems in which the Prover is restricted to have a
polynomial size strategy are investigated. The restriction of
polynomial size computation tree, visible to the Prover, or
logarithmically bounded number of coin flips by the Verifier guarantee
a polynomial size strategy. The additional restriction of logarithmic
space is also investigated. A main result of the paper is that
interactive proof systems in which the Prover is restricted to a
polynomial size strategy are equivalent to MA, Merlin-Arthur games,
defined by Babai and Moran. Polynomial tree size is also
equivalent to MA, but when logarithmic space is added as a
restriction, the power of polynomial tree size reduces to NP.
Logarithmically bounded number of coin flips are equivalent to NP, and
When logarithmic space is added as a restriction, the power is not
diminished. The proof that NP subseteq IP(log-space,
log-random-bits) illustrates an interesting application of the new
``fingerprinting'' method of Lipton. Public interactive proof
systems which have polynomial size strategies are also investigated.}

\T {Introduction to Prime Number Sieves}
\A {Jonathan Sorenson}
\J {Computer Science Technical Report TR 909, University of Wisconsin}
\D {1990}
\X {We discuss prime number sieves, that is, sieve algorithms that find all the prime numbers up to a bound $n$. We start with the classical Sieve of Eratosthenes, which uses $O(n\log\log n)$ additions and $O(n)$ bits of storage space. We then show how to improve both the time and space used by this algorithm. The fastest known improvement runs in $O( n /\log\log n)$ additions, and is due to Pritchard. The most space-efficient algorithms use only $O(\sqrt {n} )$ bits.}

\T {Inverting the Pseudo Exponentiation}
\A {Fritz {Bauspie\ss}}
\A {Hans-Joachim Knobloch}
\A {Peer Wichmann}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {At Eurocrypt'89 W.J.~Jaburek suggested an algorithm, which he called pseudo exponentiation, for use in generalized El-Gamal type public key cryptosystems. This pseudo exponentiation uses a modified form of binary addition in the place of multiplication in an ordinary exponentiation. In this paper we show that the pseudo exponentiation on the set GF$(2)^k$ of bitstrings of length $k$ has a considerable amount of mathematical structure. Using this structure we present an algorithm for inverting pseudo exponentiation that has a running time polynomial in $k.$}

\T {IP = PSPACE}
\A {Adi Shamir}
\J {J ACM {\bf 39,} 4, pp. 869--877}
\D {1992}
\X {In this paper, it is proven that when both randomization and interaction
are allowed, the proofs that can be verified in polynomial time are exactly
those proofs that can be generated with polynomial space.}

\T {IP = PSPACE: Simplified Proof}
\A {A. Shen}
\J {J ACM {\bf 39,} 4, pp. 878--880}
\X {Lund et al. have proved that PH is contained in IP. Shamir improved this
technique and proved that PSPACE = IP. In this note, a slightly simplified
version of Shamir's proof is presented, using degree reductions instead of
simple QBFs.}

\T {ISO-OSI Security Architecture}
\A {Jan Verschuren}
\A {Ren\'e Govaerts}
\A {Joos Vandewalle}
\J {Computer Security and Industrial Cryptography, Lecture Notes in Computer Science(741), Springer-Verlag}
\D {1993}
\X {The Reference Model for Open Systems Interconnection (OSI-RM) enables two APs -- residing on different end-systems -- to exchange information with each other. In case the information exchanged is transmitted via public telecommunication lines, certain attacks can be envisaged. Here the OSI-RM is described as well as the attacks threatening the transmitted information. Subsequently security services are indicated which can protect the communication between two APs. Equipping the OSI-RM with security services makes it possible for APs to exchange information in a secure way. Guideliness are given with respect to the integration of security services in the OSI-RM.}

\T {Is the Brain's Mind a Computer Program?}
\A {John R. Searle}
\J {Scientific American {\bf 262,} 1}
\D {1990}
\X {Many people working in artificial intelligence believe that a computer
simulation of mental processes could actually think. The author argues that
computer programs merely manipulate symbols, without reference to meaning, and
so are fundamentally incapable of understandin.}

\T {The $K$-ary GCD Algorithm}
\A {Jonathan Sorenson}
\J {Computer Science Technical Report TR 979, University of Wisconsin}
\D {1990}
\X {In this paper we introduce the new $k$-ary greatest common divisor (GCD) algorithm, a generalization of the binary algorithm. Interestingly, this new algorithm has both a sequential version that is very practical and parallel versions that rival the best previous parallel GCD algorithms. We show that for $k$ a prime power, the sequential $k$-ary GCD algorithm has a $\Theta(n^2)$ worst-case running time on $n$-bit inputs. However, in a multiple-precision implementation the $k$-ary algorithm outperforms several other GCD algorithms, including the binary algorithm by a factor of 2, and the Euclidean algorithm by a factor of 12. Parallel versions of the algorithm include the following for the CRCW PRAM model: an $O(n/\log n)$ time algorithm using $O(n^{1 + \epsilon } )$ processors, and for $d\ge1$, an $O(\log^d n)$ time algorithm using $\exp [O(n /\log^d n)]$ processors. The first algorithm matches the complexity of the best previous parallel GCD algorithm using a polynomial number of processors, and the second algorithm is the first deterministic polylog time GCD algorithm using a subexponential number of processors. We also give EREW and CREW PRAM versions of the algorithm.}

\T {Kerberos Network Authentication Service (V5), the}
\A {J. Kohl}
\J {RFC 1510}
\D {1993}
\X {This document gives an overview and specification of Version 5 of the protocol for the Kerberos network authentication system. Version 4, described elsewhere, is presently in production use at MIT's Project Athena, and at other Internet sites.}

\T {Key Management}
\A {Walter Fumy}
\J {Computer Security and Industrial Cryptography, Lecture Notes in Computer Science(741), Springer-Verlag}
\D {1993}
\X {The purpose of key management is to provide secure procedures for handling cryptographic keying material to be used in symmetric or asymmetric cryptographic mechanisms. This includes user registration, key generation, key distribution, key storage, and key deletion. Key management schemes depend on the type of keys to be distributed, on the given facilities and on the specific application. For almost all systems, it is necessary to distribute keys over the same communication channels by which actual data are transmitted. Secure key distribution over such a channel requires cryptographic protection and thus the availability of matching keys. This circularity has to be broken through prior distribution of keys by different means.}

\T {KEYMEX: An Expert System for the Design of Key Management Schemes}
\A {J. C. A. van der Lubbe}
\A {D. E. Boekee}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {This paper deals with the development of KEYMEX; an expert system for the design of mey management schemes. The main teask of KEYMEX us the detection of possible weaknesses in key management schemes. An outline of the structure of the system, which is based on semantical networks, is presented. The way in which the knowledge concerning the key management schemes to be tested is incorporated in the knowledge base of the expert system is discussed. Finally, the performance of the system is assessed on the basis of results which are obtained by application of the system to some well-known key management schemes and protocols.}

\T {Key Scheduling is DES Type Cryptosystems}
\A {Lawrence Brown}
\A {Jennifer Seberry}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {This paper reviews some possible design criteria for the key schedule in a DES style cryptosystem. The key schedule involves a Kay Rotation component, and the permutation $PC2.$ Together these provide for a diffusion of dependency of ciphertext bits on key bits. Some empirical rules which seem to account for the derivation of the key schedule used in the DES are first presented. A number of trials were run with various key schedules, and some further design rules were derived. An alternative form of key schedule was then tested. This used wither a null $PC2,$ or one in which permutations only occurred within the inputs to a given S-box, and a much larger rotation schedule than used in the DES. This was found to be as effective as the key schedule used in the current DES, and is proposed for use in new cryptosystems.}


\T {K-M Sequence is Forwardly Predictable}
\A {Yang Yi Xian}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {In a recent paper K. Kurosawa and K. Matsu showed a new kind of stream key sequence $(b_0,b_1,\ldots)$ (called K-M sequence here) with an exact proof that the {\sl backwardly\/} prediction of the K-M sequence is very very difficult. But we will point out in the following that the K-M sequence can be easily {\sl forwardly\/} predicted. Hence the K-M sequence is cryptographically insecure.}

\T {Knaves and Thieves}
\A {Amiga Computing}
\J {Amiga Computing, pp. 22--26, October}
\D {1991}
\X {Amiga Computing explains why ``pirates'' is too good a word for them.}

\T {A Known-Plaintext Attack on Two-Key Triple Encryption}
\A {Paul C. {van Oorschot}}
\A {Michael J. Wiener}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {A chosen-plaintext attack on two-key triple encryption noted by Merkle and Hellman is extended to a known-plaintext attack. The known-plaintext attack has lower memory requirements than the chosen-plaintext attack, but has a greater running time. The new attack is a significant improvement over a known-plaintext brute-force attack, but is still not seen as a serious threat to two-key triple encryption.}

\T {Large Primes in Stream Cipher Cryptography}
\A {Kencheng Zeng}
\A {C. H. Yang}
\A {T. R. N. Rao}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {The present research is motivated by the observation that if the period $T$ of a certain binary sequence is a prime, then its linear complexity will be bounded from below by the order of 2 modulo $T,$ i.e., $LC\ge Ord_T(2).$ A class of generators with state periods $T(q,n)=q\cdot 2^n-1$ are constructed for $q=3,5,7,9$ and arbitrary $n$ on the basis of a pair of $m$-sequence generators with the same number of stages, each controlling the clock of the other (bilateral stop-and-go clock control). A new test is derived to find the primes among the numbers $T(q,n)$ with the case $3|q$ and $3\notdiv q$ treated in a unified manner. The orders of 2 modulo some of the primes $T(q,n)$ are given and some additional cryptographic and implementational remarks are made.}

\T {Lattice Basis Reduction: Improved Practical Algorithms and Solving Subset Sum Problems}
\A {C. P. Schnorr}
\A {M. Euchner}
\J {Fundamentals of Computation Theory, 8th International Conference, FCT'91, Proceedings, L.~Budach~(ed.) Lecture Notes in Computer Science (529), Springer-Verlag}
\D {1991}
\X {We report on improved practical algorithms for lattice basis reduction. We present a variant of the L$^3$-algorithm with ``deep insertions'' and a practical algorithm for blockwise Korkine-Zolotarev reduction, a concept extending L$^3$-reduction, that has been introduced by Schnorr. Empirical tests show that the strongest of these algorithms solves almost all subset sum problems with up to 58 random weights of arbitrary bit length within at most a few hours on a UNISYS 6000/70 or within a couple of minutes on a SPARC 2 computer.}

\T {Lecture Notes on Probabilistic Algorithms and Pseudorandom Generators}
\A {Martin Tompa}
\J {Technical Report: TR 91-07-05, Dept. of Computer Science, University of Washington}
\D {1991}
\X {These are the lecture notes from CSE 522, a graduate algorithms
course I taught at the University of Washington in Winter 1991.  The
topic of the course was Probabilistic Algorithms and Pseudo-random
Generators.  These notes are not intended to be a survey of that area,
however, as there are numerous important results that I would have
liked to cover but did not have time.}

\T {Limitations of the Kerberos Protocol}
\A {S. M. Bellovin}
\A {M. Merritt}
\J {Winter 1991 USENIX Conference Proceedings, pp. 253--267}
\D {1991}

\T {Linear Approximation Versus Nonlinearity}
\A {Josef  Pieprzyk}
\A {Chris Charnes}
\A {Jennifer Seberry}
\J {Technical Report 94--11, Dept. of Computer Science, University of Wollongong, Wollongong, NSW 2522, Aust.}
\D {1994}
\X {Recently Matsui announced an attack on the DES algorithm.
The attack relies on approximation of S-boxes by linear
functions.  To find out the best linear approximation,
Matsui defines the linear approximation tables (LAT)
for S-boxes.  In this work we examine the relation between
Matsui's linear approximation tables and nonlinearities
of corresponding S-boxes.}

\T {The Linear Complexity Profile and the Jump Complexity of Keystream Sequences}
\A {Harald Niederreiter}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {We study the linear complexity profile and the jump complexity of keystream sequences in arbitrary finite fields. We solve counting problems connected with the jump complexity, establish formulas for the expected value and the variance of the jump complexity, and prove probabilistic theorems on the jump complexity profile of random sequences. We also extend earlier work on frequency distributions in the linear complexity profile to joint frequency distributions.}

\T {(Local Area) Network Security}
\A {Walter Fumy}
\J {Computer Security and Industrial Cryptography, Lecture Notes in Computer Science(741), Springer-Verlag}
\D {1993}
\X {The most obvious threats to information security are those concerning data while being transmitted over a network. A secure netowrk must provide for data confidentiality, for authentication of the originator of a message and for protection against unauthorized changes of the data transmitted. Since local area networks are not confined to small areas anymore, the needs for LAN security also has become commonly recognized. Only a few vendors of networking equipment have responded yet to this need, also progress in network security standards is relatively slow.}

\T {Local Randomness in Polynomial Random Number and Random Function Generators}
\A {H. Niederreiter}
\A {C. P. Schnorr}
\J {SIAM Journal on Computing, {\bf 22-4,} pp. 684--694}
\D {1993}
\X {A distribution on $n$-bit strings is called $(\varepsilon,e)$-locally random, if for every choice of $e \leq n$ positions the induced distribution on $e$-bit strings is in the $L_1$-norm at most $\varepsilon$ away from the uniform distribution on $e$-bit strings. Local randomness in polynomial random number generators (RNG) that are candidate one-way functions is established. Let $N$ be a squarefree integer and let $f_1,\ldots,f_{\ell}$ be polynomials with coefficients in $\bf Z_N = \bf Z/N{\bf Z}$. The RNG that stretches a random $x \in {\bf Z}_N$ into the sequence of least significant bits of $f_1(x),\ldots,f_{\ell}(x)$ is studied. It is shown that this RNG provides local randomness if for every prime divisor $p$ of $N$ the polynomials $f_1,\ldots,f_{\ell}$ are linearly independent modulo the subspace of polynomials of degree $\leq 1$ in ${\bf Z}_p[x]$. Also established is local randomness in polynomial random function generators. This yields candidates for cryptographic hash functions. The concept of local randomness in families of functions extends the concept of universal families of hash functions by Carter and Wegman [J. Comput. System Sci., 18 (1979) pp. 143--154]. The proofs of the results rely on upper bounds for exponential sums.}

\T {LOKI---A Cryptographic Primitive for Authentication and Secrecy Applications}
\A {L. Brown}
\A {J. Pieprzyk}
\A {J. Seberry}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {This paper provides an overview of the LOKI\footnote{LOKI -- God of mischeif and trickery in Scandanavian mythology. ``He is handsome and well made, but a very fickle mood and most evil disposition. He is of the giant race, but forced himself into the company of the gods, and seems to take pleasure in bringing them into difficulties, and in extracting them out of the danger by his cunning, wit and skill'' [Bulfinch's Mythology, Avenel Books, NY 1978].} encryption primitive which may be used to encrypt and decrypt a 64-bit block of data using a 64-bit key. The LOKI primitive may be used in any mode of operation currently defined for ISO DEA-1, with which it is interface compatible. Also described are two modes of operation of the LOKI primitive which compute a 64-bit, and 128-bit, Message Authentication Code (or hash value). These modes of operation may be used to provide authentication of a communications session, or of data files.}

\T {Lower Bounds for Arithmetic Problems}
\A {Jo\~ao Meid\^anis}
\J {Computer Science Technical Report TR 978, University of Wisconsin}
\D {1990}
\X {In this paper we obtain lower bounds on the number of arithmetic operations necessary to compute certain functions of integer inputs. The operations used are the four basic arithmetic operations plus the floor operation (or, equivalently, the div and mod operations), and comparison. The problems we study are {\em modular exponentiation,} and computing the {\em Jacobi symbol.} Both results are valid in the computation tree model, and the bound on modular exponentiation is also valid for random access machines with indirect addressing.}

\T {Lower Bounds for Authentication Codes with Splitting}
\A {Andrea Sgarro}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {The role of non-deterministic authentication coding (coding with splitting) is discussed; a new substitution attack is put forward which is argued to be more relevant than usual substitution for codes with splitting. A reduction theorem is proved which allows to extend ``abstract'' bounds for impersonation (including the new JS-bound, which is shown to hold on the large class of ``abstract'' authentication codes) to the new substitution attack.}

\T {Lower Bounds on the Weight Complexities of Cascaded Binary Sequences}
\A {Cunsheng Ding}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {The stability of linear complexity of sequences is a basic index for measuring the quality of the sequence when employed as a key stream of a stream cipher. Weight complexity is such a quantity which can be used to measure the stability of a sequence. Lower bounds on the weight complexities of a kind of cascaded binary sequences are presented in this correspondence.}

\T {Lower Bounds for the Linear Complexity of Sequences over Residue Rings}
\A {Zong-duo Dai}
\A {Thomas Beth}
\A {Dieter Gollmann}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {Linear feedback shift registers over the ring $\Z_{2^e}$ can be implemented efficiently on standard microprocessors. The most significant bits of the elements of a sequence in $\Z_{2^e}^\infty$ constitute a binary pseudo-random sequence. We derive lower bound for the linear complexity over $\F_2$ of these binary sequences.}

\T {Making Zero-Knowledge Provers Efficient}
\A {Mihir Bellare}
\A {Erez Petrank}
\J {Proc. of the 24th ACM Symp. on the Theory of Computing}
\D {1992}
\X {We loot at the question of how powerful a prover must be to give a zero-knowledge proof. We present the first unconditional bounds on the complexity of a statistical ZK prover. The result is that if a language possesses a statistical zero-knowledge then it also possesses a statistical zero-knowledge proof in which the prover runs in probabilistic, polynomial time with an NP oracle. Previously this was only known given the existence of one-way permutations. Extendeing these techniques to protocols of knowledge complexity $k(n)>0,$ we derive bounds on the time complexity of languages of ``small'' knowledge complexity. Underlying these results is a technique for efficiently generating an ``almost'' random element of a set $S\in$P. Namely, we construct a probabilistic machine with an NP oracle which, on input $1^n$ and $\delta>0$ runs in time polynomial in $n$ and lg $\delta^{-1}$, and outputs a random string from a distribution within distance $\delta$ of the uniform distribution on $S\cap\{0,1\}^n.$}

\T {Mandatory Security in an Object Oriented Database}
\A {G. Matunda Nyanchama}
\A {Sylvia L. Osborn}
\J {Technical Report \#317, Dept. of Computer Science, University of Western Ontario, London Ontario, Canada}
\D {1991}
\X {Database security is usually implemented in terms of access control. Mandatory security requires classification levels for objects and clearance levels for subjects. In Object Orientated Databases, all operations are invoked via {\em message passing.} Such operations belong to two categories: those that create new objects and those that do not. The security scheme must use differnet rules to handle the two categories of operations. This paper addresses the impact of database operations, which implement an {\em object algebra,} on {\em mandatory access control.}}

\T {Massively Parallel Computation of Discrete Logarithms}
\A {D. M. Gordon}
\A {K. S. McCurley}
\J {Advances in Cryptology ---Crypto '92, Proceedings, Springer-Verlag}
\D {1993}

\T {MD2 Message-Digest Algorithm, the}
\A {B. Kaliski}
\J {RFC 1319}
\D {1992}
\X {This document describes the MD2 message-digest algorithm. The algorithm takes as input a message of arbitrary length and produces as output a 128-bit ``fingerprint'' or ``message digest'' of the input. It is conjectured that it is computationally infeasible to produce two messages having the same message digest, or to produce any message having a given prespecified target message digest. The MD2 algorithm is intended for digital signature applications, where a large file must be ``compressed'' in a secure manner before being signed with a private (secret) key under a public-key cryptosystem such as RSA.}

\T {MD4 Message-Digest Algorithm, the}
\A {R. Rivest}
\J {RFC 1320}
\D {1992}
\J {RFC 1186}
\D {1990}
\X {This document describes the MD4 message-digest algorithm. The algorithm takes as input a message of arbitrary length and produces as output a 128-bit ``fingerprint'' or ``message digest'' of the input. It is conjectured that it is computationally infeasible to produce two messages having the same message digest, or to produce any message having a given prespecified target message digest. The MD4 algorithm is intended for digital signature applications, where a large file must be ``compressed'' in a secure manner before being encrypted with a private (secret) key under a public-key cryptosystem such as RSA.}

\T {MD5 Message-Digest Algorithm, the}
\A {R. Rivest}
\J {RFC 1321}
\D {1992}
\X {This document describes the MD5 message-digest algorithm. The algorithm takes as input a message of arbitrary length and produces as output a 128-bit ``fingerprint'' or ``message digest'' of the input. It is conjectured that it is computationally infeasible to produce two messages having the same message digest, or to produce any message having a given prespecified target message digest. The MD5 algorithm is intended for digital signature applications, where a large file must be ``compressed'' in a secure manner before being encrypted with a private (secret) key under a public-key cryptosystem such as RSA.}

\T {Meet-in-the-Middle Attack on Digital Signature Schemes}
\A {Kazuo Ohta}
\A {Kenji Koyama}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {The meet-in-the-middle attack can be used for forging signatures on mixed-type digital signature schemes, and takes less time than an exhaustive attack. This paper formulates a meet-in-the-middle attack on mixed-type digital signature schemes, shows the necessary conditions for success, and discusses the relationships between computational and space complexities as well as success probability during the attack. We also analyze an optimal strategy for forgers to apply this attack, pointing out than an intermediate value of 64 bit length is not secure for any mixed-type digital signature scheme. Finally, we show how to design secure mixed-type digital signature schemes.}

\T {Membership Authentication for Hierarchical Multigroups Using the Extended Fiat-Shamir Scheme}
\A {Kazuo Ohta}
\A {Tatsuaki Okamoto}
\A {Kenji Koyama}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {We propose two membership authentication schemes that allow an authorized user to construct one master secret key for accessing the set of hierarchically ordered groups defined by the user, without releasing any private user information. The key allows the user to prove his memebership of his true groups and all lower groups, without revealing his name or true groups. The user can calculate the secret member information needed to access a group from his master secret key, and can convince a verifier using the extended Fiat-Shamir scheme. Each of two proposed schemes can generate the master secret key. To ensure the user's privacy, one uses the blind signature and pseudonym encryption techniques, and the secret key, memory usage is very efficient. Moreover, veifiers can check membership validity using public information independent of the number of users in an off-line environment. Therefore, our schemes are suitable for smart card applications.}

\T {Min\`os: Extended User Authentication}
\A {Michael Newberry}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {Min\`os is a preprocessor for commands issued to the UNIX operating system. It uses information about how a user is working to continually authenticate them. Min\`os learns with the user as they develop new habits with the computer. This paper describes in detail the plans for Min\`os, and their realisation to date.}

\T {Network Security Policy Models}
\A {Vijay Varadharajan}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {This paper considers the development of security policy models for networks which can operate in a multilevel security environment. We outline an abstract security policy model which addresses the access control and information flow requirements in a multilevel network. The network security policy is formulated by drawing as much parallel as possible with the computer security policy. The model is defined and the associated security requirements are given and the model is used to prove that the security conditions are not violated by the defined network operations. In developing network security policies, it is necessary to relate them to specific layers of the network architecture. We conclude this paper by outlining another network security policy model with different network subjects and objects supported by different layers in the architecture.}

\T {A New Algorithm for the Generation of Binary de Bruijn Sequences}
\A {Yuejiang Huang}
\J {J. of Algorithms {\bf 11,} pp. 44--51}
\D {1990}

\T {New Binary Sequences with Perfect Staircase Profile of Linear Complexity}
\A {Yi Xian Yang}
\J {Info. Proc. Letters {\bf 46,} 1}
\D {1993}
\X {An open problem proposed by M.~Morrii and M.~Kasahara is solved by a few
new binary sequences with perfect staircase profile of linear complexity.
Moreoever, the PSP sequence with the smallest density is found.}

\T {A New Class of Cryptosystems Based on Interconnection Networks}
\A {Michael Portz}
\J {Technical Report: 91--04, University of Technolgy, Aachen, Germany}
\D {1991}
\X {Interconnection networks have been widely studied in the field of parallel processing. They have one property that makes them very interesting for cryptology, i.e. they give the opportunity to specify and perform permutations at the same time.  This paper introduces a new class of cryptosystems which is constructed using boolean functions and interconnection networks. The construction is secure in the sense that it can be used to construct pseudo-random permutation generators from pseudo-random Boolean function generators (as proposed by Luby and Rackoff and further investigated by Schnorr, Pieprzyk, Ohnishi etc. It
is proposed, to use simpler functions instead of pseudo-random functions to construct cryptosystems, e.g. theoretical pseudo-random number generators (as proposed by Yao, Blum, etc.), practical pseudo-random number generators (linear shift
register etc.) or oneway functions. The security of a specific cryptosystem based on boolean functions fulfilling the strict avalanche criterion (Lloydd) is investigated.}

\T {New Solutions to the Problem of Access Control in a Hierarchy}
\A {Yuliang Zheng}
\A {Thomas Hardjono}
\A {Jennifer Seberry}
\J {Technical report: tr-93-2, Centre for Computer Security Research, University of Woolongong, NSW, Australia}
\D {1993}
\X {The access control problem in a hierarchical organizationconsists of the management of information among a numberof users who are divided into different security classesaccording to their suitability in accessing the information.Within the scope of cryptographythe problem can be reduced togenerating a cryptographic key for each security classin such a waythat the key of a security class can be used to derive the keys of all lower security classes.This paper presents a new approach to solving the problem,based on pseudo-random function families,universal hash function familiesand in particular, sibling intractable function families.The approach is illustrated by two types of solutions.The first type of solution allows keys of lower security classesto be obtained indirectly from that of higher security classesthrough the calculation of the keys ofall intermediate security classes,while the second type of solutionallows keys of lower security classesto be obtained directly from that of higher security classeswithout involving other security classes.A formal definition of security forkey generation schemes is introducedandthe security of the proposed schemes is proven.Issues in key management are also addressedand several possible polices are suggested.The proposed solutions have theoretical significancein that their security relies only on the existence of any one-way function,and they also have practical applicationsin that they can be easily incorporated intoexisting information systems.}

\T {A New Trapdoor in Knapsacks}
\A {Valtteri Niemi}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {A public key scheme with trapdoor based on a group of modular knapsacks is proposed. In parallel architecture encryption and decryption are very fast.}

\T {New Types of Cryptanalytic Attacks Using Related Keys}
\A {E. Biham}
\J {Technical Report \#753, Computer Science Department, Technion, Israel Institute of Technology}
\D {1992}

\T {NIST Stumbles on Proposal for Public-Key Encryption}
\A {E. Messmer}
\J {Network World {\bf 9,} 30, July}
\D {1992}

\T {A Noisy Clock-Controlled Shift Register Cryptanalysis Concept Based on Sequence Comparison Approach}
\A {Jovan Dj. Golic}
\A {Miodrag J. Mihaljevic}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {A statistical cryptanalysis method for the initial state reconstruction of a noisy clock-controlled shift register using the noisy output sequence only, is proposed. The method is based on the sequence comparison approach.}

\T {Non-Boolean Derived Logics For Classical Systems}
\A {Michael D. Westmoreland}
\A {Benjamin W. Schumacher}
\J {Physical Review A {\bf 48,} 2, pp.~977--985}
\D {1993}
\X {Birkhoff and von Neumann proposed a nonstandard logic to describe quantum mechanics, in which the distributive laws of Boolean logic do not hold. In this paper we develop two algebras of propositions for {\sl classical\/} mechanics that, like the quantum logic algebra, are based on a measurement theory. We adopt a simple classical measurement theory that allows the determination of any continuous phase-space function to any finite precision. Surprisingly, the resulting ``classical logics'' are non-Boolean, though the distributive law holds. It appears that any physical theory with a mathematical space of physical states and an adequate description of measurement naturally yields a logiclike structure of experimental propositions, and that this ``derived logic'' can be non-Boolean even for theories much less radical than quantum theory.}

\T {Noninteractive Zero-Knowledge}
\A {Manuel Blum}
\A {Alfredo {de Santis}}
\A {Silvio Micali}
\A {Giuseppe Persiano}
\J {SIAM J. Computing {\bf 20,} 6, pp.~1084--1118}
\D {1991}
\X {This paper investigates the possibility of disposing of interaction between prover and verifier in a zero-knowledge proof if they share beforehand a short random string. Without any assumption, it is proven that noninteractive zero-knowledge proofs exist for some number-theoretic languages for which no efficient algorithm is known. If deciding quadratic residuosity (modulo composite integers whose factorization is not known) is computationally hard, it is shown that the NP-complete language of satisfiability also possesses noninteractive zero-knowledge proofs.}

\T {Nonlinear Generators of Binary Sequences with Controllable Complexity and Double Key}
\A {Gong Guang}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {This paper discusses analysis and synthesis of non-linear generators which consist of a single linear feedback shift register (LFSR) with a primitive connection polynomial, a random select generator and a non-linear feedforward logic. It is shown that the linear complexity of the generated keystream can be determined, realization is easy and its security is much better than the original feedforward system.}

\T {Nonlinearity and Propagation Characteristics of Balanced Boolean Functions}
\A {Jennifer Seberry}
\A {Xian-Mo Zhang}
\A {Yuliang Zheng}
\J {Technical report: tr-93-4, Centre for Computer Security Research, University of Woolongong, NSW, Australia}
\D {1993}
\X {Three of the most important criteria for cryptographicallystrong Boolean functions are the balancedness, the nonlinearity and the propagation criterion.The main contribution of this paperis to reveal a number of interesting propertiesof balancedness and nonlinearity,and to study systematic methods for constructingBoolean functions that satisfy some or all of the three criteria.We show that concatenating, splitting,modifying and multiplying (in the sense of Kronecker)sequences can yieldbalanced Boolean functions with a very high nonlinearity.In particular, we show that balanced Boolean functions obtainedby modifying and multiplying sequencesachieve a nonlinearity higher thanthat attainable by any previously known construction method.We also present methods for constructingbalanced Boolean functions that are highly nonlinearand satisfy the strict avalanche criterion (SAC).Furthermore we present methods for constructinghighly nonlinear balanced Boolean functionssatisfying the propagation criterion with respect to{\em all but one or three\/} vectors.A technique is developedto transform the vectors where the propagation criterionis not satisfied in such a way thatthe functions constructed satisfy the propagation criterion of high degreewhile preserving the balancednessand nonlinearity of the functions.The algebraic degrees of functions constructed are also discussed,together with examples illustrating the various constructions.}

\T {Non-Malleable Cryptography}
\A {Danny Dolev}
\A {Cynthia Dwork}
\A {Moni Naor}
\J {Proc. of the 23rd Annual ACM Symp. on the Th. of Computing}
\D {1991}
\X {The notion of {\em non-malleable\/} cryptography, an extension of semantically secure cryptography, is defined. Informally, the additional requirement is that given the ciphertext it is impossible to generate a {\em different\/} ciphertext so that the respective plaintexts are related. The same concept makes sense in the contexts of string commitment and zero-knowledge proofs of possession of knowledge. Non-malleable schemes for each of these three problems are presented. The schemes do not assume a trusted center; a user need not know anything about the number or identity of other system users. The results can be applied to contract bidding, even when the nonfaulty bidders are unaware of the existence of the faulty bidders, and the problem of a ``transparent intermediary'' in a zero-knowledge proof of possession of knowledge is solved.}

\T {Nonoblivious Hashing}
\A {Amos Fiat}
\A {Moni Naor}
\A {Jeanette P. Schmidt}
\A {Alan Siegel}
\J {J ACM {\bf 39,} 4, pp. 764--782}
\D {1992}
\X {Nonoblivious hashing, where information gathered from unsuccessful probes
is used to modify subsequent probe strategy, is introduced and used to obtain
the following results for static lookup on full tables: (1) An $O(1)$-time
worst-case scheme that uses only logarithmic additional memory, (and no memory
when the domain size is linear in the table size), which improves upon
prevously linear space requirements. (2) An almost sure $O(1)$-time
probabilistic worst-case scheme, which uses no additional memory and which
improves upon previously logairthmic time requirements. (3) Enhancements to
hashing: (1) and (2) are solved for multikey records, where search can be
performed under any key in time $O(1);$ these schemes also permit properties,
such as nearest neighbor and rank, to be determined in logarithmic time.}

\T {A (Non-Practical) Three-Pass Identification Protocol Using Coding Theory}
\A {Marc Girault}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {At EUROCRYPT '98, Stern has presented an identification scheme whose security is based on general linear decoding problem, which is NP-hard. The number of passes of the protocol he designed is five. In this paper, we propose an alternative protocol which works with only three passes and is much simpler to describe (that is good news) but which is not practical (the bad news).}

\T {Non-Supersingular Elliptic Curves for Public Key Cryptosystems}
\A {T. Beth}
\A {F. Schaefer}
\J {Advances in Cryptology---EUROCRYPT'91, Lecture Notes in Computer Science, pp.~316--327}
\D {1991}

\T {A Note On Cohen's Formal Model for Computer Viruses}
\A {Kimmo Kauranen}
\A {Erkki Makinen}
\J {Technical Report: A--1990--3, University of Tampere}
\D {1990}

\T {A Note On Efficient Zero-Knowledge Proofs and Arguments}
\A {Joe Kilian}
\J {Proc. of the 24th ACM Symp. on the Theory of Computing}
\D {1992}
\X {In this note, we present new zero-knowledge interactive proofs and arguments for languages in $NP.$ To show that $x\in L,$ with an error probability of at most $2^{-k},$ our zero-knowledge proof system requires $O(|X|^{c_1})+O(\lg^{c_2}|x|)k$ ideal bit commitments, where $c_1$ and $c_2$ depend only on $L.$ This construction is the first in the ideal bit commitment model that achieves large values of $k$ more efficiently than by running $k$ independent iteration of the base interactive proof system. Under suitable complexity assumptions, we exhibit a zero-knowledge arguments that require $O(\lg^c|x|)kl$ bits of communication, where $c$ depends only on $L$, and $l$ is the security parameter for the prover.\footnote{Typically, $l$ is the size of some problem the poly-time bounded prover is assumed to be unable to solve.} This is the first construction in which the total amount of communication can be less than that needed to transmit the $NP$ witness. Our protocols are based on efficiently checkable proofs for $NP.$}

\T {Notes On Cryptography}
\A {Charles Blair}
\J {Business Administration Dept., University of Illinois}
\D {1991}
\Q {002}
\X {Includes: Introduction to Number Theory. Encryption techniques based on powers and congruences. Subset-sum (knapsack) problems and their uses. Subset-sum problems and NP-completeness. A probabilistic test for primality. Probabilistic encryption. Pseudo-random number generators.}

\T {A Note on Strong Fibonacci Pseudoprimes}
\A {Rudolf Lidl}
\A {Winfried B. {M\"uller}}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {After summarizing some results on pseudoprimes, a characterization is presented of Fibonacci pseudoprimes of the $b$th kind for all integers $b.$ Subsequently, some generalizations of the concept of strong pseudoprimes are established.}

\T {The NP-Completeness Column: An Ongoing Guide}
\A {David S. Johnson}
\J {J. of Algorithms, {\bf 11,} pp. 144--151}
\D {1990}
\X {This is the 22nd edition of an (allegedly) quarterly column that covers new developments in the theory of NP-completeness. The presentation is modeled on that used by M.~R.~Garey and myself in our book ``Computers and Intractability: A Guide to the Theory of NP-Completeness,'' W.H. Freeman~\&~Co., New York, 1979 (hereinafter referred to as ``[G\&J]''; previous columns will be referred to by their dates). A back-ground equivalent to that provided by [G\&J] is assumed, and, when appropriate, cross-refernces will be given to that book and the list of problems (NP-complete and harder) presented there. Readers who have results they would like mentioned (NP-hardness, PSPACE-hardness, polynomial-time-solvability, etc.) or open problems they would like publicized should send them to David S. Johnson, Room 2D-150, AT\&T Bell Laboratories, Murray Hill, NJ 07974 (or to dsj@research.att.com). Please include details, or at least sketches, of any new proofs; full papers are preferred. If the results are unpublished, please state explicitly that you are willing for them to be mentioned. Comments and corrections are also welcome. For more details, see the December~1981 issue of this Journal.}

\T {The NP-Completeness Column: An Ongoing Guide}
\A {David S. Johnson}
\J {J. of Algorithms {\bf 13,} 3, pp. 502--524}
\D {1992}
\X {This is the 23rd edition of an irregularly appearing column that covers new
developments in the theory of NP-completeness. The presentation is modeled on
that used by M. R. Garey and myself in our book ``Computers and Intractability:
A Guide to the Theory of NP-Completeness,'' W.H. Freeman \& Co., New York, 1979
(hereinafter referred to as ``[G\&J]''; previous columns will be referred to by
their dates). A background equivalent to that provided by [G\&J] is assumed,
and, when appropriate, cross-references will be given to that book and the list
of problems (NP-complete and harder) presented there. Readers who have results
they would like mentioned (NP-hardness, PSPACE-hardness,
polynomial-time-solvability, etc.) or open problems they would like publicized,
should send them to David S. Johnson, Room 2D-150, AT\&T Bell Laboratories,
Murray Hill, NJ 07974 (or to dsj@research.att.com). Please include details, or
at least sketches, of any new proofs; full papers are preferred. If the results
are unpublished, please state explicitly that you are willing for them to be
mentioned. Comments and corrections are also welcome. For more details, see the
December 1981 issue of this Journal.}

\T {The Number Field Sieve}
\A {A. K. Lenstra}
\A {H. W. Lenstra Jr.}
\A {M. S. Mannasse}
\A {J. M. Pollard}
\J {Proc. of the 22nd Annual ACM Symposium on the Theory of Computing}
\D {1990}
\X {The number field sieve is an algorithm to factor integers of the form $r^e\pm s$ for small positive $r$ and $s$. This note is intended as a `report on work in progress' on this algorithm. We informally describe the algorithm, discuss several implementation related aspects, and present some of the factorizations obtained so far. We also mention some solutions to the problems encountered when generalizing the algorithm to general integers using an idea of Buhler and Pomerance. It is not unlikely that this leads to a general purpose factoring algorithm that is asymptotically substantially faster than the fastest factoring algorithms known so far, like the multiple polynomial quadratic sieve.}

\T {Numbers Can Be a Better Form of Cash Than Paper}
\A {David Chaum}
\J {Computer Security and Industrial Cryptography, Lecture Notes in Computer Science(741), Springer-Verlag}
\D {1993}

\T {Number Theoretic Algorithms and Cryptology}
\A {Johannes Buchmann}
\J {Fundamentals of Computation Theory, 8th International Conference, FCT'91, Proceedings, L.~Budach~(ed.) Lecture Notes in Computer Science (529), Springer-Verlag}
\D {1991}

\T {Oblivious Transfer Protecting Secrecy}
\A {Bert den Boer}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {We present a scheme for oblivious transfer in which contrary to earlier proposals the secrecy is protected (almost) unconditional and not by a cryptographic assumption. We also present a bit commitment scheme based on factoring where the secrecy is unconditional.}

\T {On Accessing and Hiding Information}
\A {Yenjo Han}
\J {Technical Report: TR 508, dept. of Comp. Sc., University of Rochester}
\J {Ph.D. Thesis, Dept. of Comp. Sc., University of Rochester}
\D {1994}
\X { In computational complexity theory, an oracle is an abstract form
of database that a computation with limited resources can
consult to get useful information at unit cost per access.
Throughout this thesis, we are interested in studying the power of
various methods of access to certain types of oracles.
In particular, we study three main issues: secure computation in the
presence of a powerful eavesdropper, access to oracles of low
information content, and filtered access to NP oracles.
In the presence of a very powerful eavesdropper who watches over all
transactions between a client and its oracle, it is reasonable to
assume that even the algorithm that the client uses is known to the
eavesdropper.  Thus, the only thing the client can hope to hide from
its adversary is the identity of its input.  We say that a client has
{\em secure access\/} to its oracle if no eavesdropper can distinguish
between input strings of the same length merely by
looking at the transactions between the client and the oracle.
We say that a client has
{\em oblivious access\/} to its oracle if the client achieves secure
access by blinding its own algorithm; while accessing the oracle,
the algorithm is prevented from
seeing the identity of the input string other than its length.
For the cases of bounded-error probabilistic and
bounded-error threshold clients,
though it seems likely that more languages can be recognized by secure
access to an oracle than by oblivious access to the same oracle, we show
that the existence of an oracle for which this is true would imply that
${\rm P}\ne{\rm PSPACE}$\null.
We also show that the class of languages recognized by bounded-error
probabilistic clients via secure access
to oracles is identical to the class of languages that have
one-oracle instance-hiding schemes that leak at most the length of
their inputs.
Since a sparse oracle may contain only a small number of strings at each
length, it can be considered a database of low information content.
In view of this observation, one can expect that hard problems in NP
do not reduce to any sparse set.
We confirm this expectation by showing that, unless ${\rm P}={\rm NP}$, SAT
does not conjunctively reduce to a sparse set.
Similar results have been shown in the literature regarding certain
types of truth-table reductions such as
many-one and bounded truth-table reductions.
We also show that the sets that reduce to a sparse set can indeed be reduced
to a relatively simple sparse set.
Lastly, we consider bounded truth-table reductions to NP oracles.
In the case of deterministic polynomial-time evaluators, a single bit of
parity information can be as powerful as unfiltered full
information from an NP oracle.
In contrast, in the case of nondeterministic polynomial-time evaluators,
we show that, unless the polynomial hierarchy collapses,
the parity information is strictly less powerful than the full
information obtained from queries to an NP oracle.
We also study the effect of filtering, by taking the remainder, modulo some
constant, of the count of positive answers obtained from queries to NP oracles.}

\T {On a Fundamental Theorem of Quantum Cryptography}
\A {K. J. Blow}
\A {Simon J. D. Phoenix}
\J {J. of Modern Optics {\bf 40,} 1, pp.~33--36}
\D {1993}
\X {A fundamental theorem of quantum cryptography is proved which states the conditions under which an eavesdropper can be detected. A corollary of this theorem is that any two-alphabet quantum cryptography scheme must sacrifice some of the potential key data to guarantee security.}

\T {On an Implementation of the Mohan-Adiga Algorithm}
\A {Gisela Meister}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {Several asymmetric cryptographic systems such as the RSA system require modular exponentiation of large integers. This paper discusses a modular routine which is suited for smart cards. It is based on the Mohan-Adiga algorithm. This algorithm is comparatively fast, if the leading half of the bits of the modulus is 1. It will be shown that this restriction has some severe implications on the number of suitable primes and on the security of the system. If one decrements the number of leading 1's then the security level of the system is increased while the speed is decreased.}

\T {On Constructions and Nonlinearity of Correlation Immune Functions}
\A {Jennifer Seberry}
\A {Xian-Mo Zhang}
\A {Yuliang Zheng}
\J {Technical report: tr-93-5, Centre for Computer Security Research, University of Woolongong, NSW, Australia}
\D {1993}
\X {A Boolean function is said to be correlation immuneif its output leaks no information about its input values.Such functions have many applications incomputer security practices including the construction of keystream generators from a set of shift registers.Finding methodsfor easy construction of correlation immune functions has beenan active research area since the introduction of the notionby Siegenthaler. In this paper we study balanced correlation immunefunctions using the theory of Hadamard matrices.First we present a simple method for directly constructingbalanced correlation immune functions of any order. Then we prove that our methodgenerates exactly the same set of functions as thatobtained using a method by Camion, Carlet, Charpin and Sendrier.Advantages of our methodover Camion et~al's include(1) it allows us to calculate the nonlinearity,which is a crucial criterion for cryptographically strong functions,of the functions obtained,and (2) it enables us to discuss the propagation characteristicsof the functions. Two examples are given toillustrate our construction method.Finally, we investigate methods for obtainingnew correlation immune functions fromknown correlation immune functions.These methods provide us with a new avenue towardsunderstanding correlation immune functions.}

\T {One-Way Functions are Necessary and Sufficient for Secure Signatures}
\A {John Rompel}
\J {Proc. of the 22nd Annual ACM Symposium on the Theory of Computing}
\D {1990}

\T {One-Way Permutations on Elliptic Curves}
\A {Burton S. Kaliski Jr.}
\J {J. of Cryptology {\bf 3,} pp. 187--199}
\D {1991}

\T {On Immunity Against Biham and Shamir's ``Differential Cryptanalysis''}
\A {C. M. Adams}
\J {Info. Proc. Letters {\bf 41,} 2}
\D {1992}

\T {On the Complexity of Finite Random Functions}
\A {Uriel Feige}
\J {Info. Proc. Letters {\bf 44,} 6}
\D {1992}
\X {We describe a method for relating the complexity of random finite functions
to the complexity of the most complex finite functions. Using this method we
derive an alternative proof for a known $\Omega(n\log n)$ lower bound on the
depth of noisy Boolean decision trees that compute random function.}

\T {On the Composition of Zero-Knowledge Proof Systems}
\A {Oded Goldreich}
\A {Hugo Krawczyk}
\J {Technical Report: 91--60, Centre for Discrete Mathemantics and Theoretical Computer Science (DIMACS) Computer Science (DIMACS) at Rutgers University, New Jersey}
\D {1991}

\T {On the Construction of Authentication Codes with Secrecy and Codes Withstanding Spoofing Attacks of Order $L\ge2$}
\A {Ben Smeets}
\A {Peter Vanroose}
\A {Zhe-xian Wan}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {We present an analysis of some known cartesian authentication coes and their modification into authentication coes with secrecy, with transmission rate $R=r/n,$ where $n=2,3,\ldots,$ and $1\le r\le n-1$ using $(n-r)(r+1)$ $q$-ary key digits. For this purpose we use a grouping technique. Essentially the same key grouping technique is used for the construction of codes that withstand spoofing attacks of order $L\ge2.$ The information rate of this scheme is also $r/n,$ and it requires $(L+r)(n-r)$ $q$-ary key digits. Moreover these codes allow that previously transmitted source states can be reused.}

\T {On the Construction of Run Permuted Sequences}
\A {Cees J. A. Jansen}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {This paper describes the construction of classes of binary sequence, which are obtained by permuting the runs of zeros and ones of some given periodic binary sequence $\underline{s}=(s_0,s_1,\ldots,s_{p-1})^\infty,$ $s_i\in GF(2).$ A large class of sequences is constructed by permuting the runs of zeros and ones of a DeBruijn sequence of given order. The properties of the sequences in this class are discussed. As is known, in this way all DeBruijn sequences of given order are obtained, but also many more sequence with higher complexities, all satisfying Golomb's first amd second randomness postulates. It is shown how to generate the sequences in this class with the use of enumerative coding techniques. A more efficient sequence generator, employing shift registers is also introduced. The binary sequence generator obtained in this way can be useful for cryptographic purposes, e.g. in streamcipher systems.}

\T {On the Design of Provably-Secure Cryptographic Hash Functions}
\A {Alfredo {De Santis}}
\A {Moti Yung}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {Recently, formal complexity-theoretic treatment of cryptographic hash functions was suggested. Two primitives of Collision-free hash functions and Universal one-way hash function families have been defined. The primitives have numerous applications in secure information compression, since their security implies that finding collisions is computationally hard. Most notably, Naor and Yung have shown that the most secure signature scheme can be reduced to the existence of universal one-way hash (this, in turn, gives the first trapdoor-less provably secure signature scheme). In this work, we first present reductions from various one-way function families to universal one-way hash functions. Our reductions are general and quite efficient and show how to base universal one-way hash functions on any of the known concrete candidates for one-way functions. We then show equivalence among various definitions of hardness for collision-free hash functions.}

\T {On the Deterministic Complexity of Factoring Polynomial Over Finite Fields}
\A {V. Shoup}
\J {Info. Proc. LEtters {\bf 33,} 5}
\D {1990}
\X {We present a new deterministic algorithm for factoring polynomials over
$\Z_p$ of degree $n.$ We show that the worst-case running time of our algorithm
is $O(p^{1/2}(\log p)^2n^{2+\epsilon}),$ which is faster than the running times
of previous deterministic algorithms with respect to both $n$ and $p.$ We also
show that our algorithm runs in polynomial time for all but at most an
exponentially small fraction of the polynomials of degree $n$ over $\Z_p.$
Specifically, we prove that the fraction of polynomials of degree $n$ over
$\Z_p$ for which our algorithms fails to halt in time $O((\log
p)^2n^{2+\epsilon})$ is $((n\log p)^2/p).$ Consequently, the average-case
running time of our algorithm is polynomial in $n$ and $\log p.$}

\T {On the Formal Analysis of PKCS Authentication Protocols}
\A {Klaus Gaarder}
\A {Einar Snekkenes}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {In the quest for open systems, standardisation of security mechanisms, framework and protocols are becoming increasingly important. This puts high demands on the correctness of the standards. In this paper we use a formal logic based approach to protocol analysis introduced by Burrows, Abadi and Needham in their paper ``Authentication: A Pratical Study in Belief and Action''. We extend this logic to deal with protocols using public key cryptgraphy, and with the notion of ``duration'' to capture some time related aspects. The extended logic is used to analyse an important CCITT standard, the X.509 Authentication Framework. Two claims relating the the assumptions necessary and the goals achieved using string two-way authentication are proved. We conclude that protocol analysis can benefit from the use of the notation and that it highlights important aspects of the protocol analysed. Some aspects of the formalism need further study.}

\T {On the Generation of Multivariate Polynomials which are Hard to Factor}
\A {Adi Shamir}
\J {25th ACM STOC}
\D {1993}
\X {In this paper we consider the difficulty of factoring multivariate polynomials $F(x,y,z,\ldots)$ modulo $n.$ we consider in particular the case in which $F$ is a product of two randomly chosen polynomials $P$ and $Q$ with algebraically specified coefficients, and $n$ is the product of two randomly chosen primes $p$ and $q.$ The general problem of factoring $F$ is known to be at least as hard as the factorization of $n,$ but in many restricted cases (when $P$ or $Q$ are known to have a particular form) the problem can be much easier. The main result of this paper is that (with one trivial exception), the problem of factoring $F$ is at least as hard as the factorization of $n$ whenever $P$ and $Q$ are randomly chosen from the same sample space, regardless of what may be known about its form.}

\T {On the Importance of Memory Resources in the Security of Key Exchange Protocols}
\A {George Davida}
\A {Yvo Desmedt}
\A {Ren\'e Peralta}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {We present aprotocol for key exchange which relies on the existence of permutations which are not necessarily trap-door, and which are one-way in a weaker sense than that usually assumed in the literature. Our main result is that, under this assumtpion, two players can exchange a secret key over an open channel in such a way that an eavesdropper must spend time proportional to $TIME\cdot SPACE,$ where $TIME$ is the time spent by the two players and $SPACE$ is the amount of information which can be stored and transmitted by the two players. Hence the importance of storage technology for security.}

\T {On the Maximum Length of Huffman Codes}
\A {M. Buro}
\J {Info. Proc. Letters {\bf 45,} 5}
\D {1993}
\X {In this paper the maximum length of binary Huffman codes is investigated
dependent on the two lowest probabilities of encoded symbols. Furthermore, the
structure of full binary trees with a given number of leaves, a limited depth,
and maximum external path length is examined to get an improved upper bound on
the external path length of Huffman trees.}

\T {On the Running Time of the Adleman-Pomerance-Rumely Primality Test}
\A {J. Pelikan}
\A {J. Pintz}
\A {Endre Szemeredi}
\J {Technical Report: 91--77, Centre for Discrete Mathemantics and Theoretical Computer Science (DIMACS) Computer Science (DIMACS) at Rutgers University, New Jersey}
\D {1991}

\T {On the Significance of the Directed Acyclic Word Graph in Cryptology}
\A {Cees J. A. Jansen}
\A {Dick E. Boekee}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {Blumer's algorithm can be used to build a Directed Acyclic Word Graph (DAWG) in linear time and memory from a given sequence of characters. In this paper we introduce the DAWG and show that Blumer's algorithm can be used very effectively to determine the maximum order (or nonlinear) complexity profile of a given sequence. We also show that this algorithm can be used to determine the period of a periodic sequence in linear time and memory. It also appears that the DAWG is an even more effective means of generating the sequence, given a number of characters, than e.g. the nonlinear feedback shift register equivalent of that sequence, as it always needs the least amount of characters to generate the remainder of the sequence.}

\T {Orthogonal Views in Object Oriented Database Security}
\A {G. Matunda Nyanchama}
\A {Sylvia L. Osborn}
\J {Technical Report \#308, Dept. of Computer Science, University of Western Ontario, Canada}
\D {1991}
\X {Database security may be realized by {\em access control methods,} i.e. {\em discrentionary or mandatory access control,} or a combination of both. These two methods of access control differ in the manner in which they achieve database protection. They may be implemented independently of each other or in combination. Whichever of these methods is chosen for protection, there must be a unit upon which access control is based, termed the {\em granularity of controls.} In Object Oriented Database Systems, {\em OODBS,} such a unit of control can be chosen to be the {\em class, instance or the instance variable/attribute.} Hence the issue of proection in {\em OODBS\/} involves three concepts: {\em mandatory access control, discretionary access control\/} and {\em granularity of controls.} We consider these three concepts to be {\bf orthogonal:} the choice of any one of them can be made independently of that of the others. To achieve protection, it is important to incorporate these protection mechanisms within the formal definitions of protection entities. To this end, each database object or part thereof, must have a {\em security specification.} Understanding these concepts, and how they mesh to realize secure systems, is important in the design of secure {\em OODBS.} The resulting models arising from various combinations of the foregoing provide insight into what viable {\em OODBS\/} models we can have. This insight is important in understanding and selection of protection models and helps anticipate the performance of such models.}

\T {Overview of Computer Viruses in a Research Environment, an}
\A {Matt Bishop}
\J {Dartmouth College Computer Science Technical Report PCS-TR91-156}
\D {1991}
\X {The threat of attack by computer viruses is in reality a very small part of a much more general threat, specifically attacks aimed at subverting computer security. This paper examines computer viruses as malicious logic in a research and development environment, relates them to various models of security and integrity, and examines current research techniques aimed at controlling the threats viruses in particular, and malicious logic in gerneral, pose to computer systems. Finally, a brief examination of the vulnerabilities of research and development systems that malicious logic and computer viruses may exploit is undertaken.}

\T {Parallel Generation of Pseudo-Random Sequences}
\A {Reihaneh Safavi-Naini}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {Nonlinear filtering of the states of LFSR is proposed to generate parallel pseuodorandom (PR) sequences. The result of filtering is a set of sequences over $GF(2^m)$ called exponent sequences. Each exponent sequence can be regarded as $m$ parallel component sequences. Assessment of the parallel generator is discussed and statistical properties of individual component sequences and their mutual statistical dependence are examined. upper bounds on the linear equivalence of exponent sequences and their associated component sequences are developed and it is shown that in both cases higher linear complexity can only be achieved in higher exponents. It is noticed that exponents that are prime to $2^m-1$ produce sequences of maximmum period and their component sequences have small cross correlation (equal to $-1$) and low statistical dependence. Finally directions for further research are proposed.}

\T {Perfect Cryptographic Security from Partially Independent Channels}
\A {Ueli M. Maurer}
\J {Proc. of the 23rd Annual ACM Symp. on the Th. of Computing}
\D {1991}
\X {Several protocols are presented that allow two parties Alice and Bob not sharing any secret information initially (except possibly a short key to be used for authentication) to generate a long shared secret key such that even an enemy Even with unlimited computing power is unable to obtain a non-negligible amount of information (in Shannon's sense) about this key. Two diferent models are considered. In a first model we assume that Alice can send information to Bob over a noisy main channel but that Eve is able to receive the same information over a parallel independent noisy channel from Alice to Eve. In a second, more general model we assume that Alice, Bob and Eve receive the output of a random source (e.g., a satellite broadcasting random bits) over three independent individual channels. The condition that the channels be independent can be replaced by the condition that they be independent only to a known, arbitrary small degree. We demonstrate that {\em even when Eve's channel is superior\/} (i.e., less noisy) to Alice's and Bob's channel(s), they can generate an information-theoretically secure secret key by communicating over a public (error-free) channel to which Eve is assumed to have unrestricted access. The results of this paper suggest to base the security of cryptographic systems on realistic statistical assumptions about the partial independence of two (three) channels and about a reasonable lower bound on the noise power on the enemy's channel, as an alternative to commonly used approaches based on an intractability hypothesis. This paper suggests two general conclusions: (1) for cryptographic purposes, a given noisy communication channel should not be converted into an error-free channel (by means of error-correcting codes) on which a conventional cryptographic protocol is executed, but rather {\em cryptographic coding and error-control coding should be combined,} and (2) a mere {\em difference\/} in the signals received by the enemy and the legitimate receiver, but not necessarily with an advantage to the receiver (such as his sharing of a secret key with a sender or knowledge of a trapdoor), may be sufficient for achieving cryptographic security. This observation seems to have broader applications in cryptography.}

\T {Perfectly Secure Message Transmission}
\A {Danny Dolev}
\A {Cynthia Dwork}
\A {Orli Waarts}
\A {Moti Yung}
\J {J ACM {\bf 40,} 1, pp. 17--47}
\D {1993}
\X {This paper studies the problem of perfectly secure communication in general
network in which processors and communication lines may be faulty. Lower bounds
are obtained on the connectivity required for successful secure communication.
Efficient algorithms are obtained that operate with this connectivity and rely
on no complexity-theoretic assumptions. These are the first algorithms for
secure communication in a general network to simultaneously achieve the three
goals of perfect secrecy, perfect resiliency, and worst-case time linear in the
diameter of the network.}

\T {Perfect Staircase Profile of Linear Complexity for Finite Sequences}
\A {Masakatu Morrii}
\A {Masao Kasahara}
\J {Info. Proc. Letters {\bf 44,} 2}
\D {1992}
\X {One of the most interesting themes in cryptology is the generating of
highly unpredictable pseudo-random sequences. Unfortunately, it is difficult
even to define what the highly unpredictable pseudo-random sequences are.
However, some measures for the unpredicatbiliy, or equivalently the randomness,
of finite sequences were proposed. The linear complexity is one of such
measures. We present new classes of sequences with the interesting growth
property of linear complexity.}

\T {Perfect Zero-Knowledge in Constant Rounds}
\A {Mihir Bellare}
\A {Silvio Micali}
\A {Rafail Ostrovsky}
\J {Proc. of the 22nd Annual ACM Symposium on the Theory of Computing}
\D {1990}
\X {Quadratic residuosity and graph isomorphism are classic problems and the canonical examples of zero-knowledge languages. However, despite much research effort, all previous zero-knowledge proofs for them required either unproven complexity assumptions or an unbounded number of rounds of message exchange. For both (and similar) languages, we exhibit zero-knowledge proofs that require 5 rounds and no unproven assumptions. Our solution is essentially optimal, in this setting, due to a recent lower bound argument of Goldreich and Krawczyk.}

\T {Permutation Generators of Alternating Groups}
\A {Josef Pieprzyk}
\A {Xian-Mo Zhang}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {The problem of generation of permutations from small ones is especially important from a cryptographic point of view. This work explores the case. This work addresses the design of cryptographic systems using elementary permutations, also called modules. These modules have a simple structure and are based on internal smaller permutations. Two cases have been considered. In the first case, the modules apply internal permutations only. It has been proved that the composition of modules generates the alternating group for the number of binary inputs bigger than 2. In the second, DES-like modules are considered and it has been shown that for a large enough number of binary inputs, they produce the alternating group, as well.}

\T {PKCS \#5: Password-Based Encryption Standard (ver 1.4)}
\A {RSA Data Security, Inc.}
\D {1991}

\T {A Plain Text on Crypto Policy}
\A {John Perry Barlow}
\J {C ACM {\bf 36,} 11}
\D {1993}

\T {The Practical Application of State of the Art Security in Real Environments}
\A {Ronald Ferreira}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}

\T {A Practical Electronic Voting Protocol Using Threshold schemes}
\A {Ahmad Baraani-Dastjerdi}
\A {Josef Pieprzyk}
\A {Rei Safavi-Naini}
\J {Technical Report 94--13, Dept. of Computer Science, University of Wollongong, Wollongong, NSW 2522, Aust.}
\D {1994}
\X {The paper presents a novel secret voting scheme which fully
conforms to the requirements of large scale elections.
The participants in the scheme are voters, candidates, an
administrator, and a counter. The scheme uses threshold encryption
to preserve the privacy and accuracy of the votes against dishonesty
of voters, candidates, the administrator, and the counter.
It also ensures verifiability, fairness, and soundness of the
voting process and hence neither administrator nor
candidates, or the counter is capable top produce false tally,
affecting the voting result, or corrupting/disrupting the election.}

\T {Practical Implementation of RSA Public Key Encryption}
\A {James Frykman}
\J {Technical Report CS-9005-14, Kent State University}
\D {1990}
\X {Despite its apparent advantages the public key encryption system proposed by Rivest, Shamir, and Adleman has not been adopted for widespread use. The principal reason is that if a computer program is used to do the computations for the RSA system then the encryption/decryption proceeds at a rate of a few hundred bits per second, far slower than the tens of thousands of bits per second needed for practical applications. This paper develops an algorithm as a circuit on a single chip with some rough calculations to show the feasibility of doing encryption/decryption for practical RSA public key systems at rates sufficiently high to be adopted for general use.}

\T {Practical Quantum Cryptography Based on Two-Photon Inferometry}
\A {Artur K. Ekert}
\A {John G. Rarity}
\A {Paul R. Tapster}
\A {G. Massimo Palma}
\J {Physical Review Letters {\bf 69,} 9}
\D {1992}
\X {We propose an experimental realization of a cryptographic-key-sharing scheme exploiting quantum correlations between pair photons. Our experimental setup consists of an external source of correlated photon pairs which propagate to widely separated unbalanced Mach-Zehnder inteferometers. The probability of detection of photon pairs in any two outputs of the inteferometers can be fully modulated by phase plates in either interferometer.}

\T {Practical Quantum Oblivious Transfer}
\A {C. H. Bennett}
\A {G. Brassard}
\A {C. Crepeau}
\A {M.-H. Skubiszewska}
\J {Advances in Cryptology---CRYPTO'91}
\D {1991}

\T {Precautions Taken Against Various Potential Attacks {\em in ISO/IEC DIS 9796 ``Digital Signature Scheme Giving Message Recovery''}}
\A {Louis Claude Guillou}
\A {Jean-Jacques Quisquater}
\A {Mike Walker}
\A {Peter Landrock}
\A {Caroline Shaer}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {This paper describes as ``{\em digital signature scheme giving message recovery\/}'' in order to submit it to the public scruting of IACR (the International Association for Cryptologic Research). This scheme is currently prepared by Subcommittee SC27, {\em Security Techniques,} inside Joint Technical Committee JTC1 , {\em Information Technology,} established by both ISO (the International Organization for Standardization) and IEC (the International Electrotechnical Commission). The digital signature scheme specified in DIS 9796 does not involve any hash-function. It allows a minimum resource requirement for verification. And it avoids various attacks against the generic algorithms in use.}

\T {A Preliminary Technical Analysis of Clipper and Skipjack}
\A {S. M. Bellovin}
\J {unpublished}
\D {1993}

\T {Privacy-Enhanced Electronic Mail}
\A {Matt Bishop}
\J {Distributed Computing and Cryptography, J.~Feigenbaum and M.~Merritt (eds.), American  Mathematical Soc., pp.~93--106}
\D {1991}
\J {Internetworking: Research and Experience {\bf 2,} pp.~199--233}
\D {1991}
\J {Dartmouth College Computer Science Technical Report PCS-TR91-150 Revision 3}
\D {1991}
\X {The security of electronic mail sent through the Internet may be described in exactly three words: there is none. The Privacy and Security Research Group has recommended implementing mechanisms designed to provide security enhancements. The first set of mechanisms provides a protocol to provide privacy, integrity, and authentication for electronic mail; the second provides a certificate-based key management infrastructure to support key distribution throughout the internet, to support the first set of mechanisms. This paper describes these mechanisms, as well as the reasons behind their selection and how these mechanisms can be used to provide some measure of securtiy in the exchange of electronic mail.}

\T {Privacy Enhancement for Internet Electronic Mail: Part I: Message Encryption and Authentication Procedures}
\A {J. Linn}
\J {RFC 1421}
\X {This document defines message encryption and authentication procedures, in order to provide privacy-enhanced mail (PEM) services for electronic mail transfer in the Internet. It is intended to become one member of a related set of four RFCs. The procedures defined in the current document are intended to be compatible with a wide range of key management approaches, including both symmetric (secret-key) and asymmetric (public-key) approaches for encryption of data encrypting keys. Use of symmetric cryptography for message text encryption and/or integrity check computation is anticipated. RFC 1422 specifies supporting key management mechanisms based on the use of public-key certificates. RFC 1423 specifies algorithms, modes, and associated identifiers relevant to the current RFC and to RFC 1422. RFC 1424 provides details of paper and electronic formats and procedures for the key management infrastructure being established in support of these services. Privacy enhancement services (confidentiality, authentication, message integrity assurance, and non-repudiation of origin) are offered through the use of end-to-end cryptography between originator and recipient processes at or above the User Agent level. No special processing requirements are imposed on the Message Transfer System at endpoints or at intermediate relay sites. This approach allows privacy enhancement facilities to be incorporated selectively on a site-by-site or user-by-user basis without impact on other Internet entities. Interoperability among heterogeneous components and mail transport facilities is supported. The current specification's scope is confined to PEM processing procedures for the RFC-822 textual mail environment, and defines the Content-Domain indicator value ``RFC822'' to signify this usage. Follow-on work in integration of PEM capabilities with other messaging environments (e.g., MIME) is anticipated and will be addressed in separate and/or successor documents, at which point additional Content-Domain indicator values will be defined.}

\T {Privacy Enhancement for Internet Electronic Mail: Part II: Certificate-Based Key Management}
\A {S. Kent}
\J {RFC 1422}
\X {This is one of a series of documents defining privacy enhancement mechanisms for electronic mail transferred using Internet mail protocols. RFC 1421 prescribes protocol extensions and processing procedures for RFC-822 mail messages, given that suitable cryptographic keys are held by originators and recipients as a necessary precondition. RFC 1423 specifies algorithms, modes and associated identifiers for use in processing privacy-enhanced messages, as called for in RFC 1421 and this document. This document defines a supporting key management architecture and infrastructure, based on public-key certificate techniques, to provide keying information to message originators and recipients. RFC 1424 provides additional specifications for services in conjunction with the key management infrastructure described herein. The key management architecture described in this document is compatible with the authentication framework described in CCITT 1988 X.509. This document goes beyond X.509 by establishing procedures and conventions for a key management infrastructure for use with Privacy Enhanced Mail (PEM) and with other protocols, from both the TCP/IP and OSI suites, in the future.}

\T {Privacy Enhancement for Internet Electronic Mail: Part III: Algorithms, Modes, and Identifiers}
\A {D. Balenson}
\J {RFC 1423}
\X {This document provides definitions, formats, references, and citations for cryptographic algorithms, usage modes, and associated identifiers and parameters used in support of Privacy Enhanced Mail (PEM) in the Internet community. It is intended to become one member of the set of related PEM RFCs. This document is organized into four primary sections, dealing with message encryption algorithms, message integrity check algorithms, symmetric key management algorithms, and asymmetric key management algorithms (including both asymmetric encryption and asymmetric signature algorithms). Some parts of this material are cited by other documents and it is anticipated that some of the material herein may be changed, added, or replaced without affecting the citing documents. Therefore, algorithm-specific material has been placed into this separate document. Use of other algorithms and/or modes will require case-by-case study to determine applicability and constraints. The use of additional algorithms may be documented first in Prototype or Experimental RFCs. As experience is gained, these protocols may be considered for incorporation into the standard. Additional algorithms and modes approved for use in PEM in this context will be specified in successors to this document.}

\T {Privacy Enhancement for Internet Electronic Mail: Part IV: Key Certification and Related Services}
\A {B. Kaliski}
\J {RFC 1424}
\X {This document describes three types of service in support of Internet Privacy-Enhanced Mail (PEM): key certification, certificate- revocation list (CRL) storage, and CRL retrieval. Such services are among those required of an RFC 1422 certification authority. Other services such as certificate revocation and certificate retrieval are left to the certification authority to define, although they may be based on the services described in this document. Each service involves an electronic-mail request and an electronic- mail reply. The request is either an RFC 1421 privacy-enhanced message or a message with a new syntax defined in this document. The new syntax follows the general RFC 1421 syntax but has a different process type, thereby distinguishing it from ordinary privacy- enhanced messages. The reply is either an RFC 1421 privacy-enhanced message, or an ordinary unstructured message. Replies that are privacy-enhanced messages can be processed like any other privacy-enhanced message, so that the new certificate or the retrieved CRLs can be inserted into the requestor's database during normal privacy-enhanced mail processing. Certification authorities may also require non-electronic forms of request and may return non-electronic replies. It is expected that descriptions of such forms, which are outside the scope of this document, will be available through a certification authority's ``information'' service.} 

\T {Privacy Policies and Practices: Inside the Organizational Maze}
\A {H. Jeff Smith}
\J {C ACM {\bf 36,} 12}
\D {1993}

\T {Private vs. Common Random Bits in Communication Complexity}
\A {I. Newman}
\J {Info. Proc. Letters {\bf 39,} 2}
\D {1991}
\X {We investigate the relative power of the common random string model vs. the
private random string model in communication complexity. We show that the two
models are essentially equal.}

\T {A Proactive Password Checker}
\A {Matt Bishop}
\J {Dartmouth College Computer Science Technical Report PCS-TR90-152}
\D {1990}
\X {Password selection has long been a difficult issue; traditionally, passwords are either assigned by the computer or chosen by the user. When the computer does the assignments, the passwords are often hard to remember; when the User makes the selection, the passwords are often easy to guess. This paper describes a technique, and a mechanism, to allow users to select passwords which to them are easy to remember but to others would be very difficult to guess. The technique is site, user, and group configurable, and allows rapid changing of constraints impossed upon the passwords. Although experience with this technique has been limited, it appears to have much promise.}

\T {Probabilistic Relaxation in the Cryptanalysis of Simple Substitution Ciphers}
\A {King}
\A {Bahler}
\J {Cryptologia {\bf 16,} 3, pp. 215--225}
\D {1992}

\T {Proofs that Yield Nothing But Their Validity or All Languages in NP Have
Zero Knowledge Proof Systems}
\A {O. Goldreich}
\A {S. Micali}
\A {A. Wigderson}
\J {J ACM {\bf 38,} 3}
\D {1991}
\X {In this paper the generality and wide applicability of {\em zero-knowledge
proofs,} a notion introduced by Goldwasser, Micali, and Rackoff is
demonstrated. There are probabilistic and interactive proofs that, for the
members of a language, efficiently demonstrate membership in the language
without conveying any additional knowledge. All previously known zero-knowledge
proofs were only for number-theoretic languages in NP $\cap$ CoNP. Under the
assumption that secure encryption functions exist or by using ``physical means
for hiding information,'' it is shown that all languages in NP have
zero-knowledge proofs. Loosely speaking, it is possible to demonstrate that a
CNF formula is satisfiable without revealing any other property of the formula,
in particular, without yielding neither a satisfying assignment nor properties
such as whether there is a satisfying assignment in which $x_1=x_3$ etc. It is
also demonstrated that zero-knowledge proof exits ``outside the domain o
cryptography and number theory.'' Using no assumptions, it is shown that both
graph isomorphism and graph nonisomorphism have zero-knowledge interactive
proofs. The mere existence of an interactive proof for graph nonisomorphism is
interesting, since graph nonisomorphism is not known to be in NP and hence no
efficient proofs were known before for demonstrating that two graphs are not
isomorphic.}

\T {Proof the DES is Not a Group}
\A {K. W. Campbell}
\A {M. J. Wiener}
\J {CRYPTO '92}
\D {1993}

\T {Propagation Characteristics of Boolean Functions}
\A {Bart Preneel}
\A {Werner Van Leekwijck}
\A {Luc Van Linden}
\A {Ren\'e Govaerts}
\A {Joos Vandewalle}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {The relation between the Walsh-Hadamard transform and the auto-correlation function of Boolean functions is used to study progation characteristics of these functions. The Strict Avalanche Criterion and the Perfect Nonlinearity Criterion are generalized in a Propagation Criterion of degree $k.$ New properties and constructions for Boolean bent functions are given and also the extension of the definition to odd values of $n$ is discussed. New properties of functions satisfying higher order SAC are derived. Finally a general framework is established to classify functions according to their propagation characteristic if a number of bits is kep constant.}

\T {Properties of Binary Functions}
\A {Sheelagh Lloyd}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}

\T {A Proposal for a New Block Encryption Standard}
\A {Xuejia Lai}
\A {James L. Massey}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {A new secret-key block cipher is proposed as a candidate for a new encryption standard. In the proposed cipher, the plaintext and the ciphertext are 64 bit blocks, while the secret key is 128 bit long. The cipher is based on the design concept of ``mixing operations from different algebraic groups''. The cipher structure was chosen to provide confusion and diffusion and to facilitate both hardware and software implementations.}

\T {Protocols for Group Orientated Secret Sharing}
\A {Tzonelih Hwang}
\J {Info. Proc. Letters {\bf 42,} 4}
\D {1992}
\X {A practical noninteractive scheme is proposed to simultaneously solve
several open problems in group orientated cryptography. The sender of the
information is allowed to determine teh encryption/decryption keys as well as
the information destination without any coordination with the receiving group.
The encrypted message is broadcasted to the receiving group and the receivers
may authenticate themselves for their legitmacy of the information directly
from the ciphertext. The security of the scheme can be shown to be equivalent
to the difficulty of solving the discrete logarithm problem.}

\T {A Protocol to Set Up Shared Secret Schemes Without the Assistance of a Mutually Trusted Party}
\A {Ingemar Ingemarsson}
\A {Gustavus J. Simmons}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}

\T {Provably Secure Key-Updating Schemes in Identity-Based Systems}
\A {S. Shinozaki}
\A {T. Itoh}
\A {A. Fujioka}
\A {S. Tsujii}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {In this paper, we present {\em Key-Updating Schemes\/} in identity-based (identification or signature) systems, and consider the security of the schemes. We propose two kinds of key-updating schemes, i.e., one is sequential type and the other is parallel type, and show that both schemes are equivalent to each other in a polynomial time snese, i.e., there exists a deterministic polynomial time algorithm that transforms the sequential key-updating scheme to the parallel one, and vice versa. We also show that even if any polynomially many entities conspire to find a secret-key of any other entities, both key-updating schemes are provably secure against polynomially many times key-updating if decrypting RSA is hard.}

\T {A Provably-Secure Strongly-Randomized Cipher}
\A {Ueli M. Maurer}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {Shannon's pessimistic theorem, which states that a cipher can be perfect only when the entropy of the secret key is at least as great as that of the plaintext is relativised by the demonstration of a randomized cipher in which the secret key is short but the plaintext can be very long. This cipher is shown to be ``perfect with high probability''. More precisely, the enemy is unable to obtain any information about the plaintext when a certain security event occurs, and the probability of this event is shown to be arbitrarily close to one unless the enemy performs an infeasible computation. This cipher exploits the existence of a publicly-accessible string of random bits whose length is much greater than that of all the plaintext to be encrypted before the secret key and the ramdomizer itself are changed. Two modifications of this cipher are discussed that may lead to practical provably-secure ciphers based on either of two assumptions that appear to be novel in cryptography, viz., the (sole) assumption that the enemy's memory capacity (but not his computing power) is restricted and the assumption that an explicit function is, in a specified sense, controllably-difficult to compute, but not necessarily one-way.}

\T {Pseudorandom Generators and the Frequency of Simplicity}
\A {Yenjo Han}
\A {Lane A. Hemaspaandra}
\J {Technical Report: TR-507, Dept. of Computer Science, University of Rochester}
\D {1994}
\X {Allender showed that if there are dense P
languages containing only a {\bf finite} set of Kolmogorov-simple
strings, then all pseudorandom generators are insecure.  We extend
this by proving that if there are dense P (or even BPP) languages
containing only a {\bf sparse} set of Kolmogorov-simple strings,
then all pseudorandom generators are insecure.}

\T {Pseudo-Random Generators under Uniform Assumptions}
\A {Johan H\aa stad}
\J {Proc. of the 22nd Annual ACM Symposium on the Theory of Computing}
\D {1990}
\X {We prove that given a function $f$ which is oneway in the uniform model (i.e. cannot be inverted except on a vanishing fraction of the inputs by a probabilistic polynomial time Turing machine) it is possible to construct a pseudo random bit-generator which passes all probabilistic polynomial time statistical tests.}

\T {Publication XX: Announcement and Specifications for a Digital Signature Standard (DSS)}
\A {NIST}
\J {NIST, August, 19}
\D {1992}

\T {Publication YY: Announcement and Specifications for a Secure Hash Standard (SHS)}
\A {NIST}
\J {NIST, January, 22}
\D {1992}

\T {Public Key Cryptography}
\A {Marijke {De Soete}}
\J {Computer Security and Industrial Cryptography, Lecture Notes in Computer Science(741), Springer-Verlag}
\D {1993}
\X {This paper deals with public key cryptosystems and some of their applications such as password encryption and digital signatures. The necessary mathematical background is also provided.}

\T {Public-Key Cryptography}
\A {James Nechvatal}
\J {Security Technology Group, National Computer Systems Lab., NIST, Gaithersburg, MD 20899}
\Q {003}
\D {1990}
\X {Includes: The theory of public-key cryptography. Comparisons to conventional (secret-key) cryptography. A largely self-contained summary of relevant mathematics. A survey of major existing public-key systems. An exploration of digital signatures and hash functions. A survey of public-key implementations in networks. An introduction to zero-knowledge protocols and probabilistic encryption. An exploration of security issues and key sizes.}

\T {Public-Key Cryptography}
\A {Arto Salomaa}
\J {EATCS Monographs on Theoretical Computer Science, W.~Brauer, G.~Rozenberg,
A.~Salomaa (eds.), Springer-Verlag}
\D {1990}
\X {Classical two-way cryptography, the idea of public keys, knapsack systems, RSA, other bases of cryptosystems, cryptographic protocols: surprising vistas for communication.}

\T {Public-Key Cryptography: State of the Art and Future Directions}
\A {T. Beth}
\A {M. Frisch}
\A {G.J. Simmons}
\J {Lecture Notes in Computer Science (578)}
\D {1992}

\T {A Public Key Cryptosystem Based on Lyndon Words}
\A {R. Siromoney}
\A {L. Mathew}
\J {Info. Proc. Letter {\bf 35,} 1}
\D {1990}

\T {Public-key Cryptosystems Provably Secure Against Chosen Ciphertext Attacks}
\A {Moni Naor}
\A {Moti Yung}
\J {Proc. of the 22nd Annual ACM Symposium on the Theory of Computing}
\D {1990}
\X {We show how to construct a public-key cryptosystem (as originally defined by Diffie and Hellman) secure against {\sl chosen ciphertext attacks,} given a public-key cryptosystem secure against passive eavesadropping and a non-interactive zero-knowledge proof system in the shared string model. No such secure cryptosystems were known before. A concrete implementation can be based on quadratic residuosity intractability.}

\T {Public-Randomness in Public-Key Cryptography}
\A {Alfredo De Santis}
\A {Giuseppe Persiano}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {In this work we investigate the power of Public Randomness in the context of Public-key cryptosystems. We consider the Diffie-Hellman Public-key model in which an additional short random string is shared by all users. This, which we call Public-Key Public-Randomness (PKPR) model, is very powerful as we show that it supports simple non-interactive implementations of important cryptographic primitives. We give the first {\em completely\/} non-interactive implementation of Oblivious Transfer. Our implementation is also secure against receivers with unlimited computational power. We propose the {\em first\/} implementation of non-interactive nature for Perfect Zero-Knowledge in the dual model of Brassaed, Cr\'epeau, and Chaum for all NP-languages.}

\T {Quantum Complexity Theory}
\A {Ethan Bernstein}
\A {Umesh Vazirani}
\J {25th ACM STOC}
\D {1993}

\T {Quantum Conference Key Distribution Systems}
\A {Yi Mu}
\A {Yuliang Zheng}
\A {Yan-Xia Lin}
\J {Technical Report: 94--6, Dept. of Computer Science, University of Wollongong, Wollongong, NSW 2522, Aust.}
\D {1994}
\X {We develop cryptographic protocols for conference key distribution systems based on the uncertainty principle in quantum physics. The information theoretical limits to the system correlation between users are demonstrated to describe quantum-cryptographically protected multi-user optical communication channels. An estimation of eveasdropping via ``intercept/resend" for each quantum system is given. It is shown that such attacks can be revealed from the information and correlation formalism.}

\T {Quantum Cryptographic Key Distribution Using An Optical Coupler}
\A {Yi Mu}
\A {Yuliang Zheng}
\J {Technical Report: 94--8, Dept. of Computer Science, University of Wollongong, Wollongong, NSW 2522, Aust.}
\D {1994}
\X {We develop a quantum cryptographic key distribution protocol
based on two non-commuting quantum states by utilizing an
optical coupler at the receiver side. Each bit of a cryptographic
signal is encoded using quadrature phase amplitudes, which
cannot be simultaneously measured, according to the uncertainty
principle in quantum physics. Quieter light output can be achieved
in comparison to a conventional theoretical model based on
two nonorthogonal quantum states, when a squeezed laser is used
as incident light of the coupler waveguide.}

\T {Quantum Cryptography}
\A {Charles H. Bennett}
\A {Giles Brassard}
\A {Artur K. Ekert}
\J {Scientific American {\bf 267,} 4}
\D {1992}
\X {The desire to communicate in total secrecy is probably as old as humankind.
Myriad codes and ciphers have been devised only to be broken by mathematicians.
Quantum physics may finally give the communicating parties a decisive edge.
Because observing a quantum phenomenon perturbs that which is seen, any attempt
at eavesdropping will alter the legitimate users.}

\T {Quantum Cryptography Based on Bell's Theorem}
\A {Artur K. Ekert}
\J {Physical Review Letters {\bf 67,} 6}
\D {1991}
\X {Practical application of the generalized Bell's theorem in the so-called key distribution process in cryptography is reported. The proposed scheme is based on the Bohm's version of the Einstein-Podolsky-Rosen {\em gedanken experiment\/} and Bell's theorem is used to test for eavesdropping.}

\T {Quantum Cryptography: Uncertainty in the Service of Privacy}
\A {Charles H. Bennett}
\J {Science {\bf 257}}
\D {7 August 1992}

\T {Quantum Cryptography Using Optical Fibers}
\A {J. D. Franson}
\A {H. Ilves}
\J {Applied Optics {\bf 33,} p. 2949}
\D {1994}

\T {Quantum Cryptography without Bell's Theorem}
\A {Charles H. Bennett}
\A {Gilles Brassard}
\A {N. David Mermin}
\J {Physical Review Letters {\bf 68,} 5}
\D {1992}
\X {Ekert has described a cryptographic scheme in which the Einstein-Podolsky-Rosen (EPR) pairs of particles are used to generate identical random numbers in remote places, while Bell's theorem certifies that the particles have not been measured in transit by an eavesdropper. We describe a related but simpler EPR scheme and, without invoking Bell's theorem, prove it secure against more general attacks, including substitution of a fake EPR source. Finally we show our scheme is equivalent to the original 1984 key distribution scheme of Bennett and Brassard, which uses single particles instead of EPR pairs.}

\T {A Quantum Cryptosystem Secure Against Beamsplitting Techniques}
\A {Yi Mu}
\A {Yuliang Zheng}
\A {Jennifer Seberry}
\A {Yan-Xia Lin}
\J {Technical Report: 94--5, Dept. of Computer Science, University of Wollongong, Wollongong, NSW 2522, Aust.}
\D {1994}
\X {This paper presents a quantum cryptosystem which is secure against beamsplitting and intercept/resend attacks. A mixed-state quantum key distribution based on Heisenberg's uncertainty principle is introduced for forcing an eavesdropper to use more signal energy in a eavesdropping process, thus loss of light intensity becomes detectable. Significantly, such a quantum key distribution allows us to use higher power photon signal, therefore a longer haul ciphertext communication becomes possible. In addition, a novel scheme of beamsplitting attack which was not known previously is also developed for an eavesdropper to extract information. We show that while a previously proposed quantum key exchange system is suspectable to the new attack, our system is immune to it.}

\T {A Quantum Revolution for Computing}
\A {Julian Brown}
\J {New Scientist}
\D {24 September 1994}
\X {By harnessing the bizarre properties of the quantum world, physicists believe they could construct a computer with undreamt-of power.}

\T {Randomized Algorithms and Pseudorandom Numbers}
\A {Howard J. Karloff}
\A {Prabhakar Raghavan}
\J {J ACM {\bf 40,} 3, pp. 454--476}
\D {1993}
\X {Randomized algorithms are analyzed as if unlimited amounts of perfect
randomness were available, while pseudorandom number generation is usually
studied from the perspective of cryptographuc security or for the statistical
properties of the numbers generated. Bach proposed studying the interaction
between pseudorandom number generators and randomized algorithms. This paper
follows Bach's lead; the authors assume that a (small) random seed is available
to start up a simple pseudorandom number generator that is them used for the
randomized algorithm. Randomized algorithms are studied for (1) sorting, (2)
selection, and (3) oblivious routing in networks.}

\T {Range Equations and Range Matrices: a Study in Statistical Database Security}
\A {V. S. Alagar}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {This paper studies range equations and matrices with range entries. Range equations and their solutions are generalizations of compositions for consecutive sets of integers. Consistency and reducibility of range equations are due to data dependant semantics and the restrictions set by the query response strategy in statistical databases. Having determined the probability that a random solution to a given range equation is reducible,t his paper relates it to the extend of security affordable in statistical databases and further generalizes it to matrices with range entries.}

\T {Rapid Solution of Problems by Quantum Computation}
\A {David Deutsch}
\A {Richard Jozsa}
\J {Proc. R. Soc. Lond. A. {\bf 439,} pp. 553--558}
\D {1992}
\X {A class of problems is described which can be solved more efficiently by quntum computation that by any classical or stochastic method. The quantum computation solves the problem with certainty in exponentially less time than any classical deterministic computation.}

\T {Recent Changes to Privacy Enhanced Electronic Mail}
\A {M. Bishop}
\J {Internetowrking: Research and Experiences}
\D {1993}

\T {Record Encryption in Distributed Databases}
\A {Thomas Hardjono}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {This paper investigates a possible application of the Rivest-Shamir-Adleman cryptosystem for the encryption of records in a distributed database system. A simple scheme is presented in which sites of the distributed database share a common modulus, while keeping another local secret modulus.}

\T {The Relationship Between  Propagation Characteristic and Nonlinearity of Cryptographic Functions}
\A {J. Seberry}
\A {X. M. Zhang}
\A {Y. Zheng}
\J {Technical Report: 94--7, Department of Computer Science, University of Wollongong}
\D {1994}
\X {The nonlinearity of a Boolean function indicates the
minimum distance between the function and all the affine
functions, while the propagation characteristic of a
Boolean function forecasts the avalanche behavior of the
function when some input bits to the function are
complemented. Both nonlinearity and propagation
characteristic are regarded as critical indicators of the
cryptographic strength of a Boolean function.  A main
contribution of this paper is to reveal the relationship
of the two cryptographic criteria. In particular, we prove
that (1) if $f$, a Boolean function on $V_{n}$,
 satisfies the propagation criterion with respect to
 all but a subset $\Re$ of vectors in $V_{n}$,
 then the nonlinearity of $f$ satisfies
 $N_{f}\geq 2^{n-1}-2^{\frac{1}{2}(n+t)-1}$,
 where $t$ is the rank of $\Re$, and
(2) When $|\Re| > 2$, the nonzero vectors in $\Re$
 are linearly dependent.
Furthermore we show that
(3) if $|\Re| = 2$ then $n$ must be odd 
 and the nonlinearity of $f$ satisfies
 $N_{f}\geq 2^{n-1}-2^{\frac{1}{2}(n-1)}$,
 and if $|\Re| = 4$ then $n$ must be even
  and the nonlinearity of $f$ satisfies
 $N_{f}\geq 2^{n-1}-2^{\frac{1}{2}n}$.
 In both cases,
 the nonzero vector(s) in $\Re$
 must be linear structure(s) of $f$.
(4) there exists no function on $V_n$
 such that $|\Re| = 3$.
We conclude that $|\Re| = 2$ (or 4) if and only if 
$f$ is a two-(or four-)repetition of 
a bent function on $V_{n-1}$ (or $V_{n-2}$).}

\T {Relationships Among Nonlinearity Criteria}
\A {J. Seberry}
\A {X. M. Zhang}
\A {Y. Zheng}
\J {Department of Computer Science Technical Report, University of Wollongong, Preprint 94-2}
\D {1994}
\X {An important question in designing cryptographic functions including substitution boxes (S-boxes) is the relationships among the various nonlinearity criteria each of which indicates the strength or weakness of a cryptographic function against a particular type of cryptanalytic attacks. In this paper we reveal, for the first time, interesting connections among the strict avalanche characteristics, differential characteristics, linear structures and nonlinearity of quadratic S-boxes. In addition, we show that our proof techniques allow us to treat in a unified fashion all quadratic permutations, regardless of the underlying construction methods. This greatly simplifies the proofs for a number of known results on nonlinearity characteristics of quadratic permutations. As a by-product, we obtain a negative answer to an open problem regarding the existence of differentially 2-uniform quadratic permutations on an even dimensional vector space. }

\T {A Remark on a Signature Scheme Where Forgery Can be Proved}
\A {gerrit Bleumer}
\A {Birgit Pfitzmann}
\A {Michael Waidner}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}

\T {A Remark on the Efficiency of Identification Schemes}
\A {Mike Burmester}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {The efficiency parameters of identification schemes (memory size, communication cost, computational complexity) are based on given security levels and should allow for the `worst-case' probability of error (forgery). We consider instances of schemes for which the efficiency is not as good as claimed.}

\T {Response to Comments on the NIST Proposed Digital Signatire Standard}
\A {M. E. Smid}
\A {D. K. Branstad}
\J {Advance in Cryptology---CRYPTO '92, Proceedings, Springer-Verlag}
\D {1993}

\T {Response to NIST's Proposal}
\A {R. L. Rivest}
\J {C ACM, {\bf 35,} pp. 41--47, July}
\D {1992}

\T {A Review Study on Electronic Election}
\A {Ahmad Baraani-Dastjerdi}
\A {Josef Pieprzyk}
\A {Rei Safavi-Naini}
\J {Technical Report: 94--12, Dept. of Comp. Sc., University of Wollongong, NSW, Aust.}
\D {1994}
\X {The paper reviews know solutions of electronic elections.
It describes main features of information protection
during the election process.}

\T {The Round Complexity of Secure Protocols}
\A {Donald Beaver}
\A {Silvio Micali}
\A {Phillip Rogaway}
\J {Proc. of the 22nd Annual ACM Symposium on the Theory of Computing}
\D {1990}
\X {In a netowrk of $n$ players, each player $i$ having private input $x_i$, we show how the players can collaboratively evaluate a function $f(x_1,\ldots,x_n)$ in a way that does not compromise the privacy of the players' inputs, and yet requires only a constant number of rounds of interaction. The underlying model of computation is a complete network of private channels, with broadcast, and a majority of the players must behave honestly. Our solution assumes the existence of a one-way function.}

\T {RSA as a Benchmark for Multiprocessor Machines}
\A {Rodney H. Cooper}
\A {Wayne Patterson}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}

\T {Scheme for Secure Digital Mobile Communications Based on Symmetric Key
Cryptography}
\A {T. Hwang}
\J {Info. Proc. Letters {\bf 48,} 1}
\D {1993}
\X {A scheme for secure digital mobile communications is proposed. In the
scheme user authentication as well as key distribution are provided
simultaneously. Due to the use of symmetric key cryptosystems, the scheme can
be easily implemented with hardware-limited terminals.}

\T {Schr\"odinger's Catflap}
\A {Ian Stewart}
\J {Nature {\bf 353,} 3~October}
\D {1991}

\T {Secret-Key Exchange with Authentication}
\A {Johan van Tilburg}
\J {Computer Security and Industrial Cryptography, Lecture Notes in Computer Science(741), Springer-Verlag}
\D {1993}
\X {This paper provides an outline for the second lecture on authentication protocols and deals with secret-key exchange protocols. The object is to encourage the interested reader to obtain and to study the original papers, and papers related to this subject.}

\T {Secure Cryptographic Initialisation of Remote Terminals in an Electronic Funds Transfer/Point of Sale System}
\A {Mark Ames}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {As Electronic Funds Transfer at Point of Sale (EFT/POS) systems expand and the need for more secure key management is recognised, it becomes desirable to develop secure remote initialisation strategies for terminals across public data networks. The Rivest, Shamir, Adleman (RSA) and Data Encryption standard (DES) algorithms are considered with attention to key management, logical security, and implementation requirements of each.}

\T {Secure Implementation of Identification Systems}
\A {S. Bengio}
\A {G. Brassard}
\A {Y. G. Desmedt}
\A {C. Goutier}
\A {J.-J. Quisquater}
\J {J. of Cryptology {\bf 4,} 3, pp. 175--184}
\D {1991}

\T {Secure Key Distribution System Based On Quantum Cryptography}
\A {P. D. Townsend}
\J {Electronics Letters {\bf 30,} p. 809}
\D {1994}

\T {Secure User Access Control for Public Networks}
\A {Pil Joong Lee}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {Secure authentication of users' identity to deny illegitimate accesses is one of the most important steps for preventing computer crime and losses of valuable network assets. The need for secure user access control for public networks increases rapidly as the open network architecture concept emerges and more network control is allowed to users. In this study a secure and convenient user identity authentication method is presented that provides the users with evidence of mutual authentication, based on public-key cryptographic techniques. This two-round protocol assumes that each user has a presonalized card issued by a trusted certification center and uses it at a user access terminal. This protocol provides a signed session key for users who want protection for their communications with a conventional one-key cryptosystem at no extra cost. By the use of an identity certificate, the need for a trusted public-key directory is eliminated. For the card issuing process, we considered two initialization protocols, with dumb cards and with smart cards. For the smart card case, it is shown that user's secrets need not be exposed even to the trusted certification center.}

\T {Security Analysis of Version 2 of the Network Time Protocol NTP: A Report to the Privacy and Security Research Group, a}
\A {Matt Bishop}
\J {Dartmouth College Computer Science Technical Report PCS-TR91-154}
\D {1991}
\X {The Network Time Protocol is being used throughout the Internet to provide an accurate time service. This paper examines the security requirements of such a service, analyzes version 2 of the NTP protocol to determine how well it meets these requirements, and suggests improvements where appropriate.}

\T {Security Aspects of Mobile Communications}
\A {Klaus Vedder}
\J {Computer Security and Industrial Cryptography, Lecture Notes in Computer Science(741), Springer-Verlag}
\D {1993}
\X {Security requirements and services of a mobile communication systems differ, due to the radio communication between the user and the base station, extensively from those of a fixed network. There is no physical link in the form of a  (fixed) telephone line between the user and the local exchange, which could serve to ``identify'' the user for routing and charging purposes. His identity has to be verified over an air interface. Authentication by means of cryptographic procedures is thus required to stop imposters from taking on the identity of somebody else and ``transferring'' calls and charges. Eavesdropping on the radio path and intercepting a conversation or data or tracing the whereabouts of a user by listening to signalling data are other serious threats. This paper discusses the countermeasures designed into one of the most advanced radio networks, the Global System for Mobile Communications, as well as some security aspects of the network management related to these measures. Some of the differences between this system and the planned Digital European Cordless Telephone system are highlighted.}

\T {Security Protocols for Version 2 of the Simple Network Management Protocol (SNMPv2)}
\A {J. Galvin}
\A {K. McCloghrie}
\J {RFC 1446}
\D {1993}
\X {This RFC specifes an IAB standards track protocol for the Internet community, and requests discussion and suggestions for improvements. Please refer to the current edition of the ``IAB Official Protocol Standards'' for the standardization state and status of this protocol.}

\T {Seizing the Enigma}
\A {David Kahn}
\J {Houghton Mifflin}
\D {1991}

\T {Separability and the Dection of Hidden Channels}
\A {Jeremy Jacob}
\J {Info. Proc. Letters {\bf 34,} 1}
\D {1990}
\X {This paper formalises and examines a method that is supposed to highlight
the absence or otherwise of unknown channels in a system. The mthod uses
separability and cutting channels. Separability has been formalised elsewhere;
formalising cutting channels is a main contribution of this paper. Another
contribution is determining an important property of the method.}

\T {Showing Credentials without Identification: Transferring Signatures between Unconditionall Unlinkable Pseudonyms}
\A {David Chaum}\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}

\T {Site Security Handbook}
\A {P. Holbrook}
\A {J. Reynolds}
\J {RFC 1244, FYI 8}
\D {1991}
\X {This FYI RFC is a first attempt at providing Internet users guidance on how to deal with security issues in the Internet. As such, this document is necessarily incomplete. There are some clear shortfalls; for example, this document focuses mostly on resources available in the United States. In the spirit of the Internet's "Request for Comments" series of notes, we encourage feedback from users of this handbook. In particular, those who utilize this document to craft their own policies and procedures. This handbook is meant to be a starting place for further research and should be viewed as a useful resource, but not the final authority. Different organizations and jurisdictions will have different resources and rules. Talk to your local organizations, consult an informed lawyer, or consult with local and national law enforcement. These groups can help fill in the gaps that this document cannot hope to cover.}

\T {SmartCash: A Practical Electronic Payment System}
\A {J. N. E. Bos}
\A {D. Chaum}
\J {Centrum voor Wiskunde en Informatica, Technical Report, CS-R9035, Amsterdam, The Netherlands}
\D {1990}
\X {SmartCash is an electronic privacy-protecting payment system that is realizable using current smart card technology. It is currently being implemented. Until now, there were two different electronic payment systems: systems using {\em private keys\/} and the ones which use {\em public keys.} Private key smart card payment systems provide either privacy protection (using one key for the whole system) or security (using one key per card), but never both. Public key payment systems are not feasible, because today's smart cards are not capable of doing such calculations. SmartCash uses a combination of private and public key methods to achieve both privacy and security. It only requires simple computations (DES) on the smart card, while it uses RSA to provide good privacy protection. A payment in the SmartCash system takes only a few milliseconds, so it can be used in high-speed applications.}

\T {Software Run-Time Protection: A Cryptographic Issue}
\A {Josep Domingo-Ferrer}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {A new method is featured which solves the software integrity problem by properly coding rather than enciphering. Adopting the lengthy and expensive solution which consists of having the whole rpogram signed/encryped by an authority would require full decryption and secure storage for the whole program before execution, whereas one signed instruction, pipe-lined decoding-executing, and secure recording of a few of the last read instructions suffice in our case. A general use of the proposed system could practically prevent any viral attack with minimum authority operation.}

\T {Solving a Class of Stream Ciphers}
\A {Ross J. Anderson}
\J {Cryptologia {\bf 14,} 3, pp. 285--288}
\D {1990}
\X {Jennings, and Beker and Piper, have proposed generating keystream 
sequences by combining the output of two linear feedback shift registers using
a multiplexer. Such sequences can be solved by a consistency check between the
observed keystream and the possible states of the shift register which provides
the address information ot the multiplexer.}

\T {Solving Equations in Sequences}
\A {Kencheng Zeng}
\A {Minqiang Huang}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}

\T {Some Remarks on Authentication Systems}
\A {Martin H. G. Anthony}
\A {Keith M. Martin}
\A {Jennifer Seberry}
\A {Peter Wild}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {Brickell, Simmons and others have discussed doubly perfect authentication systems in which an opponent's chance of deceiving the receiver is a minimum for a given number of encoding rules. Brickell has shown that in some instance to achieve this minimum the system needs to have splitting. Such a system uses a larger message space. Motivated by Brickell's ideas we consider authentication systems with splitting and the problems of reducing the message space.}

\T {Soviet Encryption Algorithm}
\A {Josef  Pieprzyk}
\A {Leonid Tombak}
\J {Technical Report: 94--10, Dept. of Comp. Sc., University of Wollongong, NSW, Aust.}
\D {1994}
\X {This report describes the Soviet (now Russian) encryption
algorithm.  The details of the algorithm were published
in 1990 as the Soviet Standard (GOST 28147-89).
The algorithm provides a level of security of information 
that is flexible and which can be used to protect information 
in computer systems and computer networks.  The algorithm
can be implemented in both hardware and software.}

\T {SPX Guide: Prototype Public-Key Authentication Service}
\A {K. Alagappan}
\A {J. Tardo}
\J {Digital Equipment Corp.}
\D {1991}

\T {The Spy Who Came In With a Code}
\A {Paul Andreas Overaa}
\J {Amiga Format {\bf12,} July, pp. 161--164}
\D {1990}
\X {Join the MI5, KGB and CIA in keeping your vital information secret, as Paul Andreas Overaa introduces encryption techniques for the Amiga.}

\T {Standardization of Cryptographic Techniques}
\A {Bart Preneel}
\J {Computer Security and Industrial Cryptography, Lecture Notes in Computer Science(741), Springer-Verlag}
\D {1993}
\X {An overview of standardization activities in the field of cryptography is given, including a description of worldwide, European, and North-American standard organizations. More details are given on the status of the work on open systems and within the committees ISO/TC68 and ISO/IEC JTC1/SC27.}

\T {String Searching Algorithms}
\A {Graham A Stephen}
\J {Lecture Notes in Computer Science}
\D {1994}
\X {String searching is a subject of both theoretical and practical interest in computer science. This book presents a bibliographic overview of the field and an anthology of detailed descriptions of the principal algorithms available. The aim is twofold: on the one hand, to provide an easy-to-read comparison of the available techniques in each area, and on the other, to furnish the reader with a reference to in-depth descriptions of the major algorithms. Topics covered include methods for finding exact and approximate string matches, calculating 'edit' distances between strings, finding common sequences and finding the longest repetitions within strings. For clarity, all the algorithms are presented in a uniform format and notation. Contents: Introduction; String Matching; String Distance and Common Sequences; Suffix Trees; Approximate String Matching; Repeated Substrings.}

\T {A Successful Attack Against the DES}
\A {F. Hendessi}
\A {M. R. Aref}
\J {Information Theory and Applications Proceedings, third Canadian Workshop,
Rockland, Ontario, Canada, pp.~79--90}
\D {1993}

\T {Superimposing}
\A {K. W. Yu}
\A {Tong Lai Yu}
\J {Communications of the ACM, {\bf 34,} 2}
\D {1991}

\T {Symmetry of Information and One-Way Functions}
\A {L. {Longpr\'e}}
\A {S. Mocas}
\J {Info. Proc. Letters {\bf 46,} 2}
\D {1993}
\X {Symmetry of information (in Kolmogorov complexity) is a concept that comes
from formalizing the idea of how much information about a string $y$ is
contained in a string $x.$ The situation is symmetric because it can be shown
that the amount of information contained in the string $y$ about the string $x$
is almost exactly the same as that contained in $x$ about $y.$ We address
symmetry of information in resource bounded enviromenents. While symmetry still
holds in space bounded environments, it probably does not hold in time bounded
environments. We show that if it holds for polynomial time bounds, then one-one
one-way functions cannot exist.}

\T {Systematic Design of Two-Party Authentication Protocols}
\A {R. Bird}
\A {I. Gopal}
\A {A. Herzberg}
\A {P. Janson}
\A {S. Kutten}
\A {R. Molva}
\A {M. Yung}
\J {Advances in Cryptology---CRYPTO'91, Lecture Notes in Computer Science, pp.~41--61}
\D {1992}


\T {Systematic Generation of Cryptographically Robust S-boxes}
\A {Jennifer Seberry}
\A {Xian-Mo Zhang}
\A {Yulianf Zheng}
\J {Technical report: tr-93-14, Centre for Computer Security Research, University of Woolongong, NSW, Australia}
\D {1993}
\X {Substitution boxes (S-boxes) are a crucial componentof DES-like block ciphers.This research addresses problems with previous approachestowards constructing S-boxes,and proposes a new definition for the robustness ofS-boxes to differential cryptanalysis,which is the most powerful cryptanalytic attack known to date.A novel method based on group Hadamard matricesis developed to systematically generate S-boxesthat {\em simultaneously\/} satisfy a number of criticalcryptographic properties.Among the properties arethe high nonlinearity, the strict avalanche characteristics,the balancedness,the robustness against differential cryptanalysis,and the immunity to linear cryptanalysis.An example is provided to illustratethe S-box generating method.}

\T {Technical Approaches to Thwart Computer Fraud}
\A {Joos Vandewalle}
\A {Ren\'e Govaerts}
\A {Bart Preneel}
\J {Computer Security and Industrial Cryptography, Lecture Notes in Computer Science(741), Springer-Verlag}
\D {1993}
\X {In our modern society the data protection and computer security needs can often be met by classical and/or public key cryptographic techniques. The status and the methods of cryptographic research on algorithms, hardware and software is described, emphasizing on DES and RSA public key. The importance of the cryptographic protection of the future Integrated Broadband Communication Network (IBCN) is overviewed. The evolution of IT security techniques methods and standardization is discussed.}

\T {THEO: An Interactive Proof Development System}
\A {J. Despeyroux}
\J {Technical Report: RT-0116, National Institute for Research in Computer and Control Sciences}
\D {1990}

\T {Thermodynamics of Computation and Information Distance}
\A {Charles H. Bennett}
\A {P\'eter {G\'acs}}
\A {Ming Li}
\A {Paul M.B. {Vit\'anyi}}
\A {Wojciech H. Zurek}
\J {25th ACM STOC}
\D {1993}
\X {Intuitively, the minimal information distance between $x$ and $y$ is the length of the shortest program for a universal computer to transform $x$ into $y$ and $y$ into $x.$ This measure wil be shown to be, up to a logarithmic additive term, equal to the {\em maximum\/} of the conditional Kolmogorov complexities $E_1(x,y)=\max\{K(y|x),K(x|y)\}.$ Any reasonable distance to measure similarity of pictures should be an effectively approximable, symmetric, positive function of $x$ and $y$ satisfying a reasonable normalization condition and obeying the triangle inequality. It turns out that $E_1$ is minimal up to an additive constant among all such distances. Hence it is a universal `picture distance', which accounts for any effective similarity between pictures. A third information distance, based on the idea that one should aim for dissipationless computations, and hence for reversible ones, is given by the length $E_2(x,y)=KR(y|x)=KR(x|y)$ of the shortest reversible program that transforms $x$ into $y$ and $y$ into $x$ on a universal reversible computer. It is shown that also $E_2=E_1,$ up to a logarithmic additive term. It is remarkable that three so differently motivated definitions turn out to define one and the same notion. Another transformation distance, $E_3,$ is obtained by minimizing the total amount of information flowing in and out during a reversible computation in which the program is not retained, in other words the number of extra bits (apart from $x$) that must be irreversibly supplied at the beginning, plus the number of garbage bits (apart from $y$) that must be irreversibly erased at the end of the computation to obtain a `clean' $y.$ This distance is within a logarithmic additive term of the sum of the conditional complexities, $E_3(x,y)=K(y|x)+K(x|y).$ Finally, using the physical theory of reversible computation, the simple difference $K(x)-K(y)$ is shown to be an appropriate (universal, antisymmetric, and transitive) measure of the amount of thermodynamic work required to transform string $x$ into string $y$ by the most efficient process.}

\T {The Three Faces of Information Security}
\A {John M. Carroll}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {CONFIDENTIALITY, INTEGRITY, and AVAILABILITY are the three faces of information security. These goals can all be achieved by use of cryptography. This paper will discuss: 1. Initial authentication of user and host using: (a) asymmetric ciphers; or (b) symmetric ciphers. 2. Exchange of cryptographic keys for: (a) privacy transformation; and (b) message authentication. 3. Continuous re-authentication to: (a) test user and host presence; and (b) assure channel integrity. 4. Implementation in all communication modes: (a) two-party (one-to-one); (b) broadcast (one-to-many); and (c) conference (many-to-many). The existence of umpires, network security officers or certificating authorities (CA) is not presumed, nor is it ruled out.}

\T {Time Models for Protocol Security}
\A {Nevin Heintze}
\A {J. D. Tygar}
\J {Technical report, CMU-CS-92-100, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213}
\D {1992}
\X {The notion of time is prerequisite for describing and verifying the security properties of key management protocols. Without it, properties relating to the expiration of keys and the freshness of messages and nonces cannot be formulated. Recently Burrows, Abadi and Needham proposed a formal system for protocol verification which includes an ability to reason about time. In essence their ``Logic of Authentication'' is a proof theory for reasoning about key management protocols. One difficulty with such a logic lies in justifying the iferences that can be made. We approach this problem by developing an accompanying model theory for protocol security. Model theoretic techniques have been used before in the protocol verification literature, but our approach is different in two respects. First we consider a model theory which includes a notion of time. Second, the purpose of much of the previous model theoretic work was aimed at developing protocol verification tools and so assumptions about specific kinds of protocols and methods for breaking protocols were built into the model, often implicitly. In contrast, our account is more general and centers on a justification of the notion of model itself. The main results of this work include (1) a model theoretic definition of protocol security that is provably equivalent to a variety of alternative definitions; (2) demonstration that some questions about protocol security properties are undeciable, and (3) a schema for demonstrating the validity of many protocols by the use of model checking.}

\T {To Decode Short Cryptograms}
\A {George W. Hart}
\J {CACM {\bf 37,} 9, pp. 102--108}
\D {1994}

\T {To Tap or Not to Tap}
\A {Dorothy E. Denning}
\J {C ACM {\bf 36,} 3}
\D {1993}
\X {Discusses U.S. line-tapping policy, includes comments by Mike Godwin,
William A. Bayse, Lewis and Anne Branscombe, Ronald L. Rivest, Andrew Grosso,
and Gary T. Marx}

\T {Tree Functions and Cipher Systems}
\A {Ross J. Anderson}
\J {Cryptologia {\bf 15,} 3, pp. 194--202}
\D {1991}
\X {A number of encryption systems work by combining each plaintext bit with a
hash function of the last n ciphertext bits. Such systems are self
synchronising in that they recover from ciphertext errors with an error
extension of n. We show firstly that if the hash function is a tree function,
then the system is vulnerable to a chosen ciphertext attack and, under certain
circumstances, to a chosen plaintext attack; secondly, that all hash functions
are equivalent to some tree function; thirdly, whether or not this gives a
computable attack on a given algorithm depends on the connectivity of a graph
associated with the hash function; and fourthly, the implications for DES, for
RSA key selection, and for algorithm design in general.}

\T {Trends in the Fight Against Computer-Related Delinquency}
\A {B. {De Schutter}}
\J {Computer Security and Industrial Cryptography, Lecture Notes in Computer Science(741), Springer-Verlag}
\D {1993}

\T {The (True) Complexity of Statistical Zero Knowledge}
\A {Mihir Bellare}
\A {Silvio Micali}
\A {Rafail Ostrovsky}
\J {Proc. of the 22nd Annual ACM Symposium on the Theory of Computing}
\D {1990}
\X {Statistical zero-knowledge is a very strong privacy constraint which is not dependent on computational limitations. In this paper we show that given a complexity assumption a much weaker condition suffices to attain statistical zero-knowledge. As a result we are able to simplify statistical zero-knowledge and to better characterize, on many counts, the class of languages that possess statistical zero-knowledge proofs.}

\T {Two Fast Implementations of the ``Minimal Standard'' Random Number
Generator}
\A {David G. Carta}
\J {C ACM {\bf 33,} 1}
\D {1990}
\X {This Pracnique illustrates how the minimal standard random number generator
can be implemented quite economically on 32-bit computers.}

\T {Two-Prover One-Round Proof Systems: Their Power and Their Problems}
\A {Uriel Feige}
\A {L\'aszl\'o {Lov\'asz}}
\J {Proc. of the 24th ACM Symp. on the Theory of Computing}
\D {1992}
\X {We characteriz the power of two-prover one-round $(MIP(2,1))$ proof systems, showing that $MIP(2,1)=NEXPTTIME.$ However, the following intriguing question remains open: Does parallel repetition decrease the error probability of $MIP(2,1)$ proof systems? We use techniques based on quadratic programming to study this problem, and prove the parallel repetition conjecture in some special cases. Interestingly, our work leads to a general polynomial time heuristic for any NP-problem. We prove the effectiveness of this heuristic for several problems, such as computing the chromatic number of perfect graphs.}

\T {Universal Logic Sequences}
\A {Ed Dawson}
\A {Bruce Goldburg}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}
\X {A sequence defined to be a generalized multiplexed sequence using several linear feedback shift registers (LFSR) to selcte from the stages of another LFSR can be shown to be zero-order correlation immune. By introducing one bit of memory it is shown how one can use a generalized multiplexed sequence in the construction of a sequence which is correlation immune. This new sequence is classified as a universal logic sequence. Several properties of universal logic sequences will be developed and empirical results on other properties will be given based on the results of simulation.}

\T {A Universal Statistical Test for Random Bit Generators}
\A {Ueli M. Maurer}
\J {Advances in Cryptology?}
\D {?}
\X {A new statistical test for random bit generators is presented that is universal in the sense that any significant deviation of the output statistics from the statistics of a perfect random bit generator is detected with high probability when the defective generator can be modeled as an ergodic stationary source with finite memory. This is in constrast to most presently used statistical tests which can detect only one type of non-randomness, for example, a bias in the distribution of 0's and 1's or a correlation between consecutive bits. Moreover, the new test, whose formulation was motivated by considering the universal data compression algorithms of Elias and of Willems, measures the entropy per output bit of a generator. This is shown to be the correct quality to measure for a random bit generator in cryptographic applications. A generator is thus rejected with high probability if and only if the cryptographic significance of a statistical dfect is above a specified threshold. The test is easy to implement and very fast and thus well-suited for practical applications.}

\T {Unix Security and Kerberos}
\A {Bart {De Decker}}
\J {Computer Security and Industrial Cryptography, Lecture Notes in Computer 
Science(741), Springer-Verlag}
\D {1993}
\X {This paper discusses some security issues related to the UNIX operating 
system, which is today the de facto standard Operating System. The
authentication mechanisms have been focused on, both in a central system and
in a network environment. It is shown that networking makes UNIX vulnerable if
no special masurements are taken. One of these could be the introduction of
the Kerberos authentication system which is also becoming a ``standard'' in
open network environments. The Kerberos protocols are described, and their
merits and limitations in a possibly hostile environment are discussed.}

\T {The Use of Genetic Algorithms in Cryptanalysis}
\A {Matthews}
\J {Cryptologia, {\bf XVII,} 2}
\D {1993}

\T {Use of Genetic Algorithms in Cryptanalysis of Simple Substitution Ciphers}
\A {R. Spillman}
\J {Cryptologia {\bf 17,} 1, pp. 31--44}
\D {1993}

\T {User Authorization Based on Keystroke Latencies}
\A {Rick Joyce}
\A {Gopal Gupta}
\J {C ACM {\bf 33,} 2}
\D {1990}
\X {A digital signture is an unique identifier as its human counterpart,
according to the authors who offer a user verification method to support their
claim.}

\T {Victor: an Efficient RSA Hardware Implementation}
\A {Holger Orup}
\A {Erik Svendsen}
\A {Erik Andreasen}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {The latest improvements of RSA chips are based on progress in implementation technology and strategy i.e. smaller circuits and higher clock frequencies. There has been no improvements in efficiency of the algorith,. The efficiency is here defined as the number of bits produced pr. 1000 clock cycles. We present algorithms which improve the efficiency by 300\%--400\%. The main strategy is multiple bit scan and parallel execution of two multiplications. Using these algorithms and the presented ahrdware architecture a bit rate greater than 90 Kbit/sec. can be achieved encrypting 512 bit blocks.}

\T {VLSI Design for Exponentiation in $GF(2^n)$}
\A {W. Geiselmann}
\A {D. Gollmann}
\J {Advances in Cryptology---AUSCRYPT '90, Lecture Notes in Computer Science (453), Springer-Verlag}
\D {1990}

\T {What Can Be Computed Locally?}
\A {Moni Naor}
\A {Larry Stockmeyer}
\J {25th ACM STOC}
\D {1993}
\X {The purpose of this paper is a study of computation that can be done locally in a distributed network. By locally we mean within time (or distance) independent of the size of the network. We consider {\em Locally Checkable Labeling\/} (LCL) problems, where the legality of a labeling can be checked locally (e.g., colouring). Our results include the following: There are non-trivial LCL problems that have local algorithms. There is a variant of the dining philosophers problem which can be solved locally. Randomization cannot make an LCL problem local; i.e., if a problem has a local randomized algorithm then it has a local deterministic algorithm. It is undecidable, in general, whether a given LCL has a local algorithm. However, it is decidable whether a given LCL has an algorithm that operates in a given time $t.$ Any LCL problem that has a local algorithm has one which is order-invariant (the algorithm depends only on the order of the processor id's).}

\T {Which New RSA Signatures Can Be Computed From Some Given RSA Signatures?}
\A {Jan-Hendrik Evertse}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {We consider protocols in which a signature authority issues RSA-signatures to an individual. These signatures are in general products of rational powers of residue classes modulo the composite number of the underlying RSA-system. These residue classes are chosen at random by the signature authority. Assuming that it is infeasible for the individual to compute RSA-roots on randomly chosen residue classes by himself, we give, as a consequence of our main theorem, necessary and sufficient conditions describing whether it is feasible for the individual to compute RSA-signatures of a prescribed type froms ignatures of other tpyes that he received before from the authority.}

\T {Why Cryptosystems Fail}
\A {Ross J. Anderson}
\J {CACM {\bf 37,} 11, pp.~32--40}
\D {1994}
\X {Designers of cryptographic systems are at a disadvantage to most other 
engineers, in that information on how their systems fail is hard to get: their
major users have traditionally been government agencies, which are very
secretive about their mistakes.  In this article, we present the results of a
survey of the failure modes of retail banking systems, which constitute the
next largest application of cryptology. It turns out that the threat model
commonly used by cryptosystem designers was wrong: most frauds were not caused
by cryptanalysis or other technical attacks, but by implementation errors and
management failures. This suggests that a paradigm shift is overdue in
computer security; we look at some of the alternatives, and see some signs
that this shift may be getting under way.}

\T {Witness Indistinguishable and Witness Hiding Protocols}
\A {Uriel Feige}
\A {Adi Shamir}
\J {Proc. of the 22nd Annual ACM Symposium on the Theory of Computing}
\D {1990}
\X {A two party protocol in which party $A$ uses one of several secret witnesses to an NP assertion is {\sl witness indistinguishable\/} if party $B$ cannot tell which witness $A$ is actually using. The protocol is {\sl witness hiding\/} if by the end of the protocol $B$ cannot compute any new witness which he did not know before the protocol began. Witness hiding is a natural security requirement, and can replace zero knowledge in many cryptographic protocols. We prove two central results: 1. Unlike zero knowledge protocols, witness indistinguishablity is preserved under arbitrary composition of protocols, including parallel execution. 2. If a statement has at least two independent witnesses, then any witness indistinguishable protocol for this statement is also witness hiding. Using these results, we show how to overcome some of the difficulties associated with cryptographic schemes based on zero knowledge protocols. In particular, we show how to parallelize identification protocols without loss of security, how to construct bounded round zero knowledge arguments for any NP statement under the sole assumption that oneway functions exist, and how to use the Bellare-Goldwasser signature scheme to sign polynomially many messages in a completely memoryless way.}

\T {Workshop Summary: Structural Complexity and Cryptography}
\A {Eric Allender}
\A {Jin-yi Cai}
\A {Joan Feigenbaum}
\J {Technical Report: 91--36, Centre for Discrete Mathemantics and Theoretical Computer Science (DIMACS) Computer Science (DIMACS) at Rutgers University, New Jersey}
\D {1991}

\T {Zero-Knowledge Undeniable Signatures}
\A {David Chaum}
\J {Advances in Cryptology---Eurocrypt '90, Lecture Notes in Computer Science (473), Springer-Verlag}
\D {1990}
\X {Undeniable signature protocols were introduced at Crypto '89. The present article contains new undeniable signature protocols, and these are the first that are zero-knowledge.}
\end{document}ÿ
