EUROCRYPT '94 CONFERENCE In the cryptographic world--at least, the cryptographic world outside the military--there are two major annual conferences: Crypto and Eurocrypt. Eurocrypt '94 was held in Perugia, Italy, on May 9-12. There were about 300 people in attendance, representing the best in academic cryptography from five continents (I didn't notice anyone from South America or Antarctica). A total of 37 papers were presented at the main session, and another twenty or so at an informal "rump session" one evening. Much of what was presented was very theoretical, and only of marginal interest to front-line programmers actually implementing this stuff. Here is a list of what I found useful and important: Feedback with Carry Shift Registers (FCSRs): Linear Feedback Shift Registers (LFSRs) have been the workhorse of military cryptography for years. Goresky and Klapper have discovered a new class of shift registers which should prove to be just as useful. There are analogues for most of the LFSR theory that apply to FCSRs. Algorithms that were implemented with LFSRs can be implemented with FCSRs, possibly with different degrees of security. Even more interesting should be cryptographic algorithms which use a mixture of LFSRs and FCSRs. I expect this development to dramatically change the development of stream ciphers. Synthesis of Public-Key Algorithms: There are a lot of public-key digital signature algorithms in the literature based on the problem of taking discrete logarithms in a finite field: ElGamal, Schnorr, and the Digital Signature Standard (DSS) are three examples. Nyberg and Rueppel presented a paper which unified all of these algorithms (108 in total) into one unified family. They also showed how to do encryption with all of them. What this does it allow further research to proceed on the entire family of algorithms, and not just on one particular one. It also lays to rest Schnorr's claim that the DSS infringed on his patent; it is now clear that both Schnorr and DSS are specific cases on this general algorithm. The Digital Signature Standard: Naccache, M'Raihi, Raphaeli, and Vaudenay presented enhancements to the DSS: one that increases speed, one that reduces storage requirements (important for smart-card implementations), etc. Their most interesting enhancement is the ability to verify multiple signatures in a single operation. A complaint against DSS is that signature verification is slow; the batch verification method in this paper should silence that complaint once and for all. Visual Cryptography: Shamir developed a one-time-pad cryptosystem that is suitable for encrypting visual images. The key is a pattern of black and white pixels on a transparency; the ciphertext is another pattern of black and white pixels. Overlay the key on the ciphertext and the message appears. This is unconditionally secure; even alien civilizations with undreamed- of computing power cannot break this cryptosystem. Applications include sending an encrypted message via fax: the receiver can carry the key transparency with him and can receive the encrypted fax from an insecure machine. Cool stuff. Designated Confirmer Signatures: Undeniable signatures are signatures which need permission from the signer to verify. Applications include computer publication of data. The recipient of the data wants to be able to verify the publisher's signature, so he knows that the data is authentic. The publisher only wants his signature to be verifiable by people who have paid for the data, and not by people who have pirated it. Undeniable signatures do that. Chaum's extension allows the publisher to designate an agent who can help receivers verify the signatures. Differential and Linear Cryptanalysis: Both of these techniques were further refined by several people. Two papers, one by Biham and another by Chabaud and Vaudenay, looked at similarities between the two. Matsui found an alternate order for the S-boxes that is resistant to linear cryptanalysis, but unfortunately it is weak against differential cryptanalysis. Self-Shrinking Generator: The shrinking generator was a big hit at Crypto '93. Basically, a LFSR is decimated by another LFSR. This stream algorithm is simple to implement, and looks very strong. Meyer and Staffelbach developed a variant of this generator, which uses a single LFSR. The even bits of the generator are used to decimate the odd bits. This is even simpler to implement and is just as strong. Formal Protocol Design: One of the problems with authentication protocols, like Kerberos, is proving that they are correct. There's nothing more embarrassing than fielding a protocol and finding a security problem two years later. Syverson and Meadows have developed an expert system that helps detect security problems in protocols. Several interesting papers were presented at the rump session. Biham presented a paper showing that triple-DES in cipher feedback mode, with triple-DES as the bock cipher, is more secure than a large number of variant possibilities. Knudsen found a class of "weak" keys for DES and LOKI when those algorithms are used as one-way hash functions. There is nothing to worry about; the odds of picking such a key at random is very small. Charnes and O'Connor presented some initial comments on the GOST algorithm, an encryption algorithm from the Soviet Union. Also interesting were the side discussions. At least two cryptographers are working on something called "higher-order differential cryptanalysis." Although this technique has had great success against DES with only 5 rounds, no one knows how to extend it to full 16-round DES. One cryptographer has developed an alternate set of DES S-boxes that is resistant to both differential and linear cryptanalysis, while another has developed a method for generating key-dependent S-boxes that increase the effective key size of DES beyond 56 bits. If there are going to be any more attacks against DES, this--and Hellman's attempts to combine differential and linear cryptanalysis--is where to watch for them. RSA-129 was recently factored. This is the 129-digit number, the product of two large primes, that was featured in Martin Gardner's original Scientific American column about the RSA algorithm. Although this doesn't affect the security of the 1024-bit numbers used in programs like PGP, it does show how far we've come in fifteen years. Gardner was sure this number would not be factored for millions of years. The other big news is a security problem with the Secure Hash Algorithm (SHA), discussed in the Apr 94 DDJ. The cryptographers at NSA have found a problem with the algorithm. They won't tell anyone what it is, or even how serious it is, but they promise a fix soon. Everyone is waiting with baited breath.