Review of  the
IACR Crypto,
Santa Barbara, CA, USA
August 17-21, 2003

Review by Richard Schroeppel
September 15, 2003


Notes on Some Talks at Crypto 2003, by Rich Schroeppel

The leadoff talk was "Factoring Large Numbers with the TWIRL device", by Eran Tromer and Adi Shamir. The slides were excellent; I hope they appear on the web soon. The authors have continued to improve the TWIRL concept. The idea is to use a special chip for implementing the hard part of the Number Field Sieve, the sieving step. To factor a 1024-bit number, the authors estimate a setup cost of $20M, plus $10M per sieving machine. The machine would use 600 wafers and run for a year. It would sieve 3x10^23 values (half of Avogadro's Number), using a factor base of 3.5G primes. Each clock cycle (at 1GHz) would process 16000 values per wafer. For a 512-bit number, they estimate one $15K wafer could do the necessary sieving in ten minutes. The TWIRL webpage http://www.wisdom.weizmann.ac.il/~tromer/twirl/ has the paper along with more details. A preprint (to appear in Asiacrypt 2003) discusses parameter selection for the 1024-bit RSA challenge number. The biggest technical uncertainty in the design seems to be the wafer-scale integration: The design uses a very wide bus and needs a lot of inter-chip and inter-wafer connections. The design of factoring machines is a very active area of investigation, with several groups offering designs and sharing ideas. This work reinforces the notion that long-term security for RSA requires keys longer than 1024 bits.

"Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems Using Grobner Bases", by Antoine Joux and Jean-Charles Faugere, presents more efficient algorithms for computing Grobner bases. They find that HFE cryptosystems generate systems of quadratic equations that are easier to solve than random systems of the same size, and conclude that HFE-based systems can be cryptanalyzed in polynomial time when the degree of the secret polynomial is fixed. Although the security estimates for HFE must be revised downward, repair may be possible by increasing parameter sizes.

The first invited talk was "Cryptographic Assumptions and Challenges" by Moni Naor. The security of common cryptographic primitives rests on the assumed difficulty of various hard problems. Naor presents a new scheme for classifying these cryptographic assumptions, based on the difficulty of falsification. He examines the logic of challenge problems, and the costs of checking solutions to challenges. He proposes several meta-problems, such as constructing a competitive block cipher based on an efficiently falsifiable assumption.

"A Polynomial Time Algorithm for the Braid Diffie-Hellman Conjugacy Problem", by Jung Hee Cheon and Byungheup Jun, develops an attack on the straightforward braid-group key exchange. Their new algorithm begins by converting the braid problem into a linear algebra problem, using the Lawrence-Krammer representation of the braid group. They simplify the linear algebra problem, and apply Gaussian elimination, eventually recovering a pseudo-key, equivalent to Alice's secret key. The complexity is O(N^14) for braid-index N. The attack is based on the group structure, and fails against some braid group key agreement methods that depart from the group structure.

"Cryptanalysis of SAFER++", by Alex Biryukov, Christophe De Canniere, and Gustaf Dellkrantz, presents several attacks. The best result breaks 5.5 rounds of SAFER++. (The actual cipher is 7 rounds.) The attacks use either multisets (like the Square attack), or a nice application of Wagner's boomerang. The attacks take advantage of some algebraic properties of the SAFER sboxes. A three-round version of the multiset attack is practical, and was implemented and tested.

"Primality Proving via One Round in ECPP and One Iteration in AKS", by Qi Cheng, is another improvment on the polynomial-time prime proving algorithm discovered last year by Agrawal, Kayal, and Saxena. The key idea: Berrizbeita discovered a subset of cheaply-provable primes. Cheng has expanded the subset. A general B-bit prime can be proven in heuristic time roughly O(B^4), by using one round of Elliptic Curve Prime Proving to reduce the general prime to a cheaply-provable prime. The new algorithms are still less efficient than existing heuristic probable-prime tests, but a remarkable amount of progress has been made in the year since AKS was discovered.

"Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication", by Elad Barkan, Eli Biham, and Nathan Keller, introduces several new attacks against cell phone ciphers and protocols. The attacks are very practical, with simulations taking less than a second on one PC. Once again, the risks of non-publicly- vetted encryption are apparent.

The Rump Session talk "Analysis of an electronic voting system", by Yoshi Kohno, Adam Stubblefield, Avi Rubin, and Dan Wallach, sketched out some problems with Diebold voting machines. The audience reaction ranged from incredulity to wild laughter. Details of the analysis are available at http://avirubin.com/vote.