In this talk, I will review some of the work performed by the research community in cryptology and security since the invention of public key cryptography by Diffie and Hellman in 1976. This community has developped many challenging lines of research. I will only focus on some of these, and moreover I will adopt an extremely specific perspective: for each chosen example, I will try to trace the original mathematics that underly the methods in use. Over the years, maybe due to my original training as a mathematician, I have come to consider that linking recent advances and challenges in cryptology and security to the work of past mathematicians is indeed fascinating. The range of examples will span both theory and practice: I will show that the celebrated RSA algorithm is intimately connected to mathematics that go back to the middle of the XVIIIth century. I will also cover alternatives to RSA, the method of "provable security", as well as some aspects of the security of electronic payments.

This paper introduces a simple alternative to the hash-and-sign paradigm, from the security point of view but for signing short messages, called twinning. A twin signature is obtained by signing twice a short message by a signature scheme. Analysis of the concept in different settings yields the following results:

The aim of electronic voting schemes is to provide a set of protocols that allow voters to cast ballots while a group of authorities collect the votes and output the final tally. In this paper we describe a practical multi-candidate election scheme that guarantees privacy of voters, public verifiability, and robustness against a coalition of malicious authorities. Furthermore, we address the problem of receipt-freeness and incoercibility of voters. Our new scheme is based on the Paillier cryptosystem and on some related zero-knowledge proof techniques. The voting schemes are very practical and can be efficiently implemented in a real system.

In response to the current need for fast, secure and cheap public-key cryptography largely induced by the fast development of electronic commerce, we propose a new on the fly signature scheme, i.e. a scheme that requires very small on-line work for the signer It combines provable security based on the factorization problem, short public and secret keys, short transmission and minimal on-line computation. It is the first RSA-like signature scheme that can be used for both efficient and secure applications based on low cost or contactless smart cards.

This paper describm a new pub~c-key cryptosystem based on the hardnxs of computing higher residuw modulo a composite MA integer.We introduce two versions of our scheme, one deterministic and the other probabi~stic.The deterministic version is practically oriented encryption amounts to a single exponentiation w.r.t. a modulus with at least 768 bits and a 160-bit exponent.Decryption can be suitably optimized so as to become less demanding than a couple RSA decryptions.Although slower than MA, the new sdeme is still reasonably competitive and has several specific applications.The probabilistic version exhibits an homomorphic encryption scheme whose expansion rate is much better than previously proposed such systems.Furthermore, it has se mantic security, relative to the hardness of computing higher residu~s for suitable moduE.

In this paper, we present new blind signature schemes based on the factorization problem.They are the first blind signat,ure schemes proved secure relatively to factorization.By security, we mean that no "one-more forgery" is possible even under a parallel attack.In other terms, a user that receives k electronic coins cannot manufacture K + 1.Those security definitions have been introduced by Pointcheval and Stern [lS] for use in electronic cash.In fact, blind signatures were defined with this aim and it is still their most important application, together with anonymous voting.In the following, we will present an efficient reduction of an attack to a factorization algorithm in the random oracle model [l].

The present paper investigates the possibility of designing zero-knowledge identification schemes based on hard problems from coding theory. Zero-knowledge proofs were introduced by Goldwasser, Micali, and Rackoff (1985). Their practical significance was soon demonstrated in the work of Fiat and Shamir [1986], who turned zero-knowledge proofs of quadratic residuosity into efficient means of establishing user identities. In the present paper, we propose a new identification scheme, based on error-correcting codes, which is zero-knowledge and seems of practical value. Furthermore, we describe several variants, including one which has an identity-based character. The security of our schemes depends on the hardness of finding a word of given syndrome and prescribed (small) weight with respect to some randomly generated binary linear error-correcting code. This is, of course, not the first attempt to design a cryptographic scheme using tools from coding theory. The difference is that identification protocols do not follow the public key paradigm based on trap-door functions and described in the seminal Diffie-Hellman paper [1976]. Rather, they only require one-way functions, which opens the way to using, in a rather direct manner, simple combinatorial problems of the kind provided by coding theory. The resulting schemes compare favorably to their number-theoretic analogs.

A spherical code is a finite set X of points lying on the unit sphere of R/sup n/. For such a set, we define /spl rho/(X) as the minimum of the squared distances /spl par/x-y/spl par//sup 2/, when x, y/spl isin/X and x/spl ne/y. Define R(/spl rho/)=lim sup n/spl rarr//spl infin/, /spl rho/(X)=p log/sub 2/CardX/n. Chabauty in 1953 and Shannon in 1959 have given a lower bound for R(/spl rho/), namely, R(/spl rho/)>R/sub CS/(/spl rho/)=1-1/3log/sub 2//spl rho/(4-p). The complexity of construction of the spherical codes used in order to get this bound is doubly exponential. The polynomially constructible spherical bound R/sub pol/(/spl rho/) is defined as above with the additional restriction that only families of codes with polynomial complexity of construction are considered. We prove R/sub pol/(/spl rho/)/spl ges/R/sub CS/(/spl rho/)/2, if /spl rho//spl les/1.535. Denote by /spl tau//sub X/(n) the number of spheres of equal radius that touch one sphere in the n-dimensional space given by some explicit family X, that is, a family of arrangements of spheres). The asymptotic polynomially constructible kissing number is /spl theta//sub pol/=lim sup(log/sub 2//spl tau//sub X/(n))/n, when X ranges over all polynomially constructible families. We prove /spl theta//sub pol//spl ges/2/15=0.133/spl middot//spl middot//spl middot/.>

We prove the following about the Nearest Lattice Vector Problem (in any l/sub p/ norm), the Nearest Code-word Problem for binary codes, the problem of learning a halfspace in the presence of errors, and some other problems. 1. Approximating the optimum within any constant factor is NP-hard. 2. If for some /spl epsiv/>0 there exists a polynomial time algorithm that approximates the optimum within a factor of 2/sup log(0.5-/spl epsiv/)/ /sup n/ then NP is in quasi-polynomial deterministic time: NP/spl sube/DTIME(n/sup poly(log/ /sup n)/). Moreover, we show that result 2 also holds for the Shortest Lattice Vector Problem in the l/sub /spl infin// norm. Improving the factor 2/sup log(0.5-/spl epsiv/)/ /sup n/ to /spl radic/(dim) for either of the lattice problems would imply the hardness of the Shortest Vector Problem in l/sub 2/ norm; an old open problem. Our proofs use reductions from few-prover, one-round interactive proof systems, either directly, or through a set-cover problem.>

This paper discusses the predictability of the sequence given by outputing a constant proportion α of the leading bits of the numbers produced by a linear congruential generator. First, we make the assumption that the modulus of the generator is the only known parameter and we prove that, almost surely, a significant proportion of the bits can be predicted from the previous ones, once the generator has been used K times successively where K is O(√log m). Next, we assume that all parameters of the generator are secret and we show how repeated observations of sequences of outputs of length K will probably allow an opponent to cryptanalyze the full sequence.

The original aim of this paper was to show that forcing provided a useful and unifying tool in the model theory of finite and admissible languages. Roughly speaking, any result obtained by a Henkin proof, by Makkai's method or by an omitting type argument can be given an alternative proof via forcing. Finally, instead of giving new proofs of a number of known theorems, we have chosen to focus on the interpolation theorem for many-sorted languages. The main result of this paper is thus a generalization of Feferman's theorems ([2], [3]) with a completely different proof; this was announced in [8] and [9]. For more on forcing techniques in model theory the reader should consult [4] as well as [5]. He should also compare forcing and boolean-valued models developed in [6] for the classical case and in [7] for admissible languages. Throughout the paper familiarity with the standard concepts of model theory is assumed. The author wishes to express his gratitude to J. L. Krivine and K. McAloon for supervising his work. Thanks are also due to J. P. Ressayre for helpful suggestions and to R. L. Vaught for an interesting discussion on forcing in model theory. Finally, an interesting application has been pointed out by S. Feferman and has been included with his permission.