Advances in Cryptology — EUROCRYPT ’96: International Conference on the Theory and Application of Cryptographic Techniques Saragossa, Spain, May 12–16, 1996 Proceedings

Don Coppersmith, Matthew Franklin, Jacques Patarin, Michael Reiter (auth.), Ueli Maurer (eds.)354061186X, 9783540611868

The EUROCRYPT ’96 conference was sponsored by the International Asso- ation for Cryptologic Research (IACR)l, in cooperation with the University of Saragossa. It took place at the Palacio de Congresos in Saragossa, Spain, during May 12-16, 1996. This was the fifteenth annual EUROCRYPT conference (this name has been used since the third conference held in 1984), each of which has been held in a different city in Europe. For the second time, proceedings were available at the conference. JosC Pastor Franco, the General Chair, was resp- sible for local organization and registration. His contribution to the snccess of the conference is gratefully acknowledged. The Program Committee considered 126 submitted papers and selected 34 for presentation. Each paper was sent to all members of the Program Committee and was assigned to at least three of them for careful evaluation. There were also two invited talks. James L. Massey, this year’s IACR Distinguished Ltcturer, gave a lecture entitled “The difficulty with difficulty”. Massey is the third to receive this honor, the first two being Gustavus Simmons and Adi Shamir. Shafi Goldwasser gave an invited talk entitled “Multi party secure protocols: past and present”. These proceedings contain revised versions of the 34 contributed talks. While the papers were carefully selected, they have not been refereed like submissions to a refereed journal. The authors bear full responsibility for the contents of their papers. Some authors may write final versions of their papers for publication in a refereed journal.

---

Table of contents :
Low-Exponent RSA with Related Messages….Pages 1-9
Generating EIGamal Signatures Without Knowing the Secret Key….Pages 10-18
On the Security of Two MAC Algorithms….Pages 19-32
Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms….Pages 33-48
A Public Key Cryptosystem Based on Elliptic Curves over ℤ/ n ℤ Equivalent to Factoring….Pages 49-59
Public Key Encryption and Signature Schemes Based on Polynomials over ℤ n ….Pages 60-71
Multi-Authority Secret-Ballot Elections with Linear Work….Pages 72-83
Asymmetric Fingerprinting….Pages 84-95
Homomorphisms of Secret Sharing Schemes: A Tool for Verifiable Signature Sharing….Pages 96-106
Efficient Multiplicative Sharing Schemes….Pages 107-118
Equivocable Oblivious Transfer….Pages 119-130
Short Discreet Proofs….Pages 131-142
Designated Verifier Proofs and Their Applications….Pages 143-154
Finding a Small Root of a Univariate Modular Equation….Pages 155-165
New Modular Multiplication Algorithms for Fast Modular Exponentiation….Pages 166-177
Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known….Pages 178-189
Publicly Verifiable Secret Sharing….Pages 190-199
Optimum Secret Sharing Scheme Secure against Cheating….Pages 200-211
The Security of the Gabidulin Public Key Cryptosystem….Pages 212-223
Non-Linear Approximations in Linear Cryptanalysis….Pages 224-236
On the Difficulty of Software Key Escrow….Pages 237-244
An Efficient Pseudo-Random Generator Provably as Secure as Syndrome Decoding….Pages 245-255
On the Existence of Secure Feedback Registers….Pages 256-267
Fast Low Order Approximation of Cryptographic Functions….Pages 268-282
Construction of t -Resilient Functions over a Finite Alphabet….Pages 283-293
Auto-Correlations and New Bounds on the Nonlinearity of Boolean Functions….Pages 294-306
Foiling Birthday Attacks in Length-Doubling Transformations….Pages 307-320
Session Key Distribution Using Smart Cards….Pages 321-331
On Diffie-Hellman Key Agreement with Short Exponents….Pages 332-343
On the Security of a Practical Identification Scheme….Pages 344-353
Robust Threshold DSS Signatures….Pages 354-371
New Convertible Undeniable Signature Schemes….Pages 372-386
Security Proofs for Signature Schemes….Pages 387-398
The Exact Security of Digital Signatures-How to Sign with RSA and Rabin….Pages 399-416