Colin D. Walter
Publications

I hope these pages will be a useful resource to students and researchers around the world. Included are some lecture notes and presentation slides as well as publications.
I have now retired from Royal Holloway and my RHUL email address is no longer active. However, you can still contact me via the Information Security Group.

Publications by Topic

Some papers span several of the topics below, but they only appear in one of the lists. Please scan each relevant topic if searching for a particular paper.


Smart Cards – NFC

[5] Muhammad Qasim Saeed, Colin Walter, Pardis Pourghomi & Gheorghita Ghinea, Mobile Transactions over NFC and GSM, UBICOMM 2014, pp. 118-125.

[4] Muhammad Qasim Saeed, Zeeshan Bilal, & Colin D. Walter, An NFC based consumer-level counterfeit detection framework, PST 2013, pp. 135-142.

[3] M. Q. Saeed & C. D. Walter, Off-line NFC Tag Authentication, ICITST 2012, IEEE, pp. 730-735.

[2] M. Q. Saeed & C. D. Walter, An Attack on Signed NFC Records and Some Necessary Revisions of NFC Specifications, International Journal for Information Security Research (IJISR), Volume 2, Issue 1/2, March/June 2012, pp. 325-334.

[1] M. Q. Saeed & C. D. Walter, A Record Composition/Decomposition Attack on an NDEF Signature Record Type, ICITST 2011, IEEE, pp. 283-287.


Elliptic Curves

[1] C. D. Walter, Cryptographic Pairings, Cryptographic Engineering Course, EPFL, Lausanne, Sept 2011. Notes and Slides


Side Channel Attacks & Counter-Measures

[19] M. Msgari & C. D. Walter, Overview of PIC Microcontrollers and their usability for Cryptographic Algorithms, Chapter in Secure Smart Embedded Devices: Platforms and Applications, K. Markantonakis & K. Mayes (editors), Springer, 2014, pp. 475-495. ISBN 978-1-4614-7914-7.

[18] C. D. Walter, Side Channel Leakage from Modular Multiplication, chapter in Cryptographic Engineering, Çetin Koç (ed), Springer, 2008, pp. 431-449. ISBN: 978-0-387-71816-3

[17] C. D. Walter, Side Channel Leakage from Implementations of Modular Multiplication, Cryptographic Engineering Course, EPFL, Lausanne, Sept 2011.

[16] C. D. Walter, Randomised Algorithms for Reducing Side Channel Leakage, Cryptographic Engineering Course, EPFL, Lausanne, Sept 2006.

[15] W. Schindler & C.D. Walter, Optimal Recovery of Secret Keys from Weak Side Channel Traces, Cryptography and Coding, Proc. 12th IMA International Conference, Lecture Notes in Computer Science, vol. 5921, Springer-Verlag, 2009, pp. 446-468. Slides from the presentation.

[14] C. D. Walter, Recovering Secret Keys from Weak Side Channel Traces of Differing Lengths, Cryptographic Hardware and Embedded Systems – CHES 2008, Lecture Notes in Computer Science, Springer-Verlag, vol. 5154, pp. 214-227. Powerpoint Slides from the presentation.

[13] C. D. Walter, Longer Randomly Blinded RSA Keys May Be Weaker Than Shorter Ones, WISA 2007, Lecture Notes in Computer Science, Springer-Verlag, vol. 4867, 2008, pp. 303-316. Powerpoint Slides from the presentation.

[12] C. D. Walter & D. Samyde, Data Dependent Power Use in Multipliers, Proc. 17th IEEE Symposium on Computer Arithmetic, IEEE Press, 2005, pp. 4-12. Powerpoint Slides from the presentation.

[11] C. D. Walter, Simple Power Analysis of Unified Code for ECC Double and Add, Cryptographic Hardware and Embedded Systems – CHES 2004, Lecture Notes in Computer Science, Springer-Verlag, vol. 3156, pp. 191-204. Powerpoint Slides from the presentation.

[10] C. D. Walter, Issues of Security with the Oswald-Aigner Exponentiation Algorithm, Topics in Cryptology – CT-RSA 2004, Lecture Notes in Computer Science, Springer-Verlag, vol. 2964, pp. 208-221. Slides from the presentation.

[9] W. Schindler & C. D. Walter, More Detail for a Combined Timing and Power Attack against Implementations of RSA, Proc 9th IMA Internat. Conf. on Cryptography and Coding, Lecture Notes in Computer Science, Springer-Verlag, vol. 2898, 2003, pp. 245-263. Powerpoint Slides & Notes from the presentation.

[8] C. D. Walter, Longer Keys may facilitate Side Channel Attacks, Proc 10th Annual Workshop on Selected Areas in Cryptography – SAC 2003, Lecture Notes in Computer Science, Springer-Verlag, vol. 3006, pp. 42-57. Powerpoint Slides & Notes from the presentation.

[7] C. D. Walter, Security Constraints on the Oswald-Aigner Exponentiation Algorithm, Cryptology ePrint Archive: Report 2003/013, IACR, 22 Jan 2003.

[6] C. D. Walter, Seeing through Mist Given a Small Fraction of an RSA Private Key, Topics in Cryptology – CT-RSA 2003, Lecture Notes in Computer Science, vol. 2612, Springer-Verlag, 2003, pp. 391-402. Powerpoint Slides & Notes from the presentation.

[5] C. D. Walter, Breaking the Liardet-Smart Randomized Exponentiation Algorithm, Proc. CARDIS ’02, San Jose, 21-22 Nov 2002, USENIX Assoc, 2002, pp. 59-68. Powerpoint Slides & Notes from the presentation.

[4] C. D. Walter,  Is there Safety in Numbers against Side Channel Leakage?, RSA Europe Conference (crypto track), Amsterdam, 15-18th October, 2001 (unpublished). Powerpoint Slides & Notes from the presentation. (This conference was cancelled for security reasons.)

[3] C. D. Walter,  Improvements in, and relating to, Cryptographic Methods and Apparatus , UK Patent Application 0126317.7 (only draft available). This work is published in CT-RSA 2001 & CHES 2002.

[2] C. D. Walter,  Sliding Windows Succumbs to Big Mac Attack, Cryptographic Hardware and Embedded Systems – CHES 2001, Ç. Koç, D. Naccache & C. Paar (editors), Lecture Notes in Computer Science, vol. 2162, Springer-Verlag, 2001, pp. 286-299. Powerpoint Slides & Notes from the presentation.

[1] C. D. Walter and Susan Thompson,  Distinguishing Exponent Digits by Observing Modular Subtractions, Topics in Cryptology – CT-RSA 2001, D. Naccache (editor), Lecture Notes in Computer Science, vol. 2020, Springer-Verlag, 2001, pp. 192-207. (This is work supported by Datacard Consult P7.) Powerpoint slides from the conference presentation.


Exponentiation

Exponentiation (which is called scalar multiplication by those working on elliptic curves) is fundamental to most public key cryptography. There is a considerable overlap between this topic and those of modular multiplication and side channel analysis. Some papers below span several of these topics.
These are all important papers, but one highlight is [1], which provides one of the key ingredients for the fastest known resource-constrained implementations of public-key cryptography. How it applies is outlined in [6].

[8] C. D. Walter, The Montgomery and Joye Powering Ladders are Dual, IACR ePrint Archive 2017, No. 1081.

[7] C. D. Walter, A Duality in Space Usage between Left-to-Right and Right-to-Left Exponentiation, CT-RSA 2012, LNCS, Springer-Verlag, vol. 7178, pp. 84-97. Slides from the presentation.

[6] C. D. Walter, Fast Scalar Multiplication for ECC over GF(p) using Division Chains, WISA 2010, LNCS, Springer-Verlag, vol. 6513, 2010, pp. 61-75. Slides from the presentation.

[5] C. D. Walter, Randomised Exponentiation Algorithms, chapter in Cryptographic Engineering, Çetin Koç (ed), Springer, 2008, pp. 451-473. ISBN: 978-0-387-71816-3

[4] C. D. Walter,  Some Security Aspects of the MIST Randomized Exponentiation Algorithm, Cryptographic Hardware and Embedded Systems – CHES 2002, Lecture Notes in Computer Science, vol. 2523, Springer-Verlag, 2002, pp. 276-290. Powerpoint Slides & Notes from the presentation.

[3] C. D. Walter,  MIST: An Efficient, Randomized Exponentiation Algorithm for Resisting Power Analysis, Topics in Cryptology – CT-RSA 2002, Lecture Notes in Computer Science, Springer-Verlag, vol. 2271, 2001, pp. 53-66. Powerpoint Slides & Notes from the presentation.

[2] C. D. Walter,  Montgomery Exponentiation Needs No Final Subtractions, Electronics Letters, vol. 35 no. 21, October 1999, pp 1831-1832.

[1] C. D. Walter,  Exponentiation using Division Chains, IEEE Transactions on Computers, vol. 47, No. 7, July 1998, pp. 757-765. (This is an extended and improved version of what was presented at Arith 13, Asilomar, Proceedings, IEEE Press, 1997, pp. 92-98.)

Warnings for the benefit of those submitting papers for publication: This experience of refereeing really takes the biscuit for incompetence: [7] and [9] were rejected by a top international conference and top international journal as “parallel submissions”. There is a slight overlap in content between the two, with §6 of [9] summarising some of [7] from a different viewpoint because [7] had not been published at the time. However, any mathematics student, even only at secondary school, could easily tell they have different aims and content.
Upon submission, you may not even get as far as the refereeing stage. An early version of [7] was rejected by a famous journal of algorithms without it even being read, the reason given amounting to “we don't do algorithms”.
Not many referees even know that it is exponentiation algorithms that are used for scalar multiplication on elliptic curves. (Hence my reminder at the top of this section.) One famous cryptography expert even wrote in a review that random numbers had no place in cryptography! In my experience, nowadays it is very rare for all the referees of a paper to be competent even for journals and conferences at the highest international level. Indeed, if you were to use a subjunctive or the passive voice, your paper could be rejected on the grounds of “poor English”. Consequently, papers are rejected more often than not because of an incompetent referee's report rather because of insufficient quality. This situation has arisen mainly over the last 40 years. In the '70s (before the internet) refereeing was generally excellent and reliable.
The conclusion is that you should keep on submitting papers until they are accepted. Rejection is not much of an indication of quality. Moreover, if you want to enhance your career don't pick an old research area like exponentiation where there are few researchers likely to cite your work. Pick a new (and therefore easier) area with many researchers, such as NFC (above). People will think you're great because many more authors cite you and citations are what matters, not content.

[9] C. D. Walter,  Compact Exponentiation Schemes, 2011. (Unpublished. Updated to contain a couple of newer references such as [8], which develops some of the content a bit further.)


Modular Multiplication & Systolic Arrays

Two classic papers which I recommend reading are [11] and [5].

[16] C. D. Walter, Hardware Aspects of Montgomery Modular Multiplication, Chapter 3 of Topics in Computational Number Theory Inspired by Peter L. Montgomery, edited by Joppe W. Bos and Arjen K. Lenstra, Cambridge University Press, 2017.

[15] S. Contini, Ç. K. Koç & C. D. Walter, Modular Arithmetic, Encyclopedia of Cryptography and Security, Henk van Tilborg (ed), 2nd Ed, Springer 2010.

[14] Ç. K. Koç & C. D. Walter, Montgomery Multiplication, Encyclopedia of Cryptography and Security, Henk van Tilborg (ed), 2nd Ed, Springer 2010.

[13] S. Contini, Ç. K. Koç & C. D. Walter, Modular Arithmetic, Encyclopedia of Cryptography and Security, Henk van Tilborg (ed), 1st Ed, Springer 2005.

[12] Ç. K. Koç & C. D. Walter, Montgomery Multiplication, Encyclopedia of Cryptography and Security, Henk van Tilborg (ed), 1st Ed, Springer 2005.

[11] C. D. Walter,  Precise Bounds for Montgomery Modular Multiplication and Some Potentially Insecure RSA Moduli, Topics in Cryptology – CT-RSA 2002, Lecture Notes in Computer Science, vol. 2271, Springer-Verlag, 2001, pp. 30-39. Powerpoint Slides & Notes from the presentation.

[10] C. D. Walter,  Improved Linear Systolic Array for Fast Modular Exponentiation, IEE Computers and Digital Techniques, vol. 147, no. 5, September 2000, pp. 323-328.

[9] C. D. Walter,  An Overview of Montgomery’s Multiplication Technique: How to make it Smaller and Faster, (invited talk) Proc. Workshop on Cryptographic Hardware and Embedded Systems, CHES 99, Worcester, MA, Aug 12-13, 1999, Christof Paar & Çetin Koç, editors, Springer Lecture Notes in Computer Science, vol. 1717, pp 80-93. Powerpoint slides from the presentation.

[8] C. D. Walter, Techniques for the Hardware Implementation of Modular Multiplication, Proc. 2nd IMACS Internat. Conf. on Circuits, Systems & Computers, Athens, Oct 1998, vol. 2, pp 945-949.

[7] C. D. Walter, Space-Time Trade-Offs for Higher Radix Modular Multiplication using Repeated Addition, IEEE Transactions on Computers, 46 (1997), No. 2, pp. 139-141.

[6] C. D. Walter, Still Faster Modular Multiplication, Electronics Letters 31 (1995) No 4, pp. 263-264.

[5] C. D. Walter, Systolic Modular Multiplication, IEEE Transactions on Computers 42 (1993), pp. 376-378.

[4] S. E. Eldridge & C. D. Walter, Hardware Implementation of Montgomery’s Modular Multiplication Algorithm, IEEE Transactions on Computers 42 (1993), pp. 693-9.

[3] C. D. Walter, Faster Modular Multiplication by Operand Scaling, Proc. CRYPTO ’91, Lecture Notes in Computer Science 576 (1992), pp. 313-323, Springer-Verlag.

[2] C. D. Walter, Fast Modular Multiplication using 2-Power Radix, International J. of Computer Mathematics, 3 (1991), pp. 21-28.

[1] C. D. Walter & S. E. Eldridge, A Verification of Brickell’s Fast Modular Multiplication Algorithm, International J. of Computer Mathematics 33 (1990), pp. 153-169. 


Miscellaneous Computer Arithmetic

There are several themes in these papers. Apart from on-line and LNS arithmetic, readers may be interested in one or two which are relevant to cryptographic implementations. They are concerned with testing and fault-finding both before and during execution.

[9] M. Arnold, T. Bailey, J. Cowles & C. Walter, Fast Fourier Transforms using the Complex Logarithm Number System, J. VLSI Signal Proc., vol. 33, pp. 325-335, 2003.

[8] M. G. Arnold & C. D. Walter,  Unrestricted Faithful Rounding is Good Enough for some LNS Applications, Proc. 15th IEEE Symposium on Computer Arithmetic (ARITH 15), Vail, Colorado, 11-13 June, 2001, IEEE Press, 2001, pp 237-246.

[7] C. D. Walter,  Data Integrity in Hardware for Modular Arithmetic, Proc. Cryptographic Hardware and Embedded Systems (CHES 2000), Worcester, MA, Aug 17-18, 2000, Christof Paar & Çetin Koç, editors, Springer Lecture Notes in Computer Science, vol. 1965, pp. 204-215. Powerpoint slides from the presentation.

[6] C. D. Walter, Moduli for Testing Implementations of the RSA Cryptosystem , Proc. 14th IEEE Symposium on Computer Arithmetic (ARITH 14), Adelaide, 14-16 April, 1999, IEEE Press, 1999, pp 78-85.

[5] C. D. Walter, Analysis of Delays in Converting from a Redundant Representation, IEE Computers & Digital Techniques, 144 No 4, (July 1997), pp. 219-221.

[4] C. D. Walter, Verification of Hardware combining Multiplication, Division & Square Root, Microprocessors & Microsystems 19 (1995), pp. 243-245.

[3] C. D. Walter, Optimal Parameters for Fully On-Line Arithmetic, International J. of Computer Mathematics 56 (1995), pp.11-18.

[2] C. D. Walter, Logarithmic Speed Modular Multiplication, Electronics Letters 30 (1994), No 17, pp. 1397-8.

[1] C. D. Walter, Improving Average Delay for On-Line Algorithms, Electronics Letters 30 (1994), No. 23, pp. 1925-6.


Functional Programming – Pattern-Matching

[4] N. Nedjah, C. D. Walter & S. E. Eldridge, Efficient Automata-Driven Pattern Matching for Equational Programs, Software Practice & Experience, vol. 29, no. 9, 1999, pp. 793-813.

[3] N. Nedjah, C. D. Walter & S. E. Eldridge, More efficient Pattern-Matching Automata for Overlapping Patterns, Proc. International Workshop on the Implementation of Functional Languages, St Andrews, Sept 1997, pp 341-350.  

[2] N. Nedjah, C. D. Walter & S. E. Eldridge, Optimal Left-to-Right Pattern-Matching Automata for Equational Programs, Proc. of ALP97 & HOA97, Lecture Notes in Computer Science, vol. 1298, 1997, pp. 273-286.

[1] C. D. Walter,   UMIST OBJ Manual, version 1.0, Technical Report, Computation Department, UMIST, 1986, 28+iii pp.


Formal Methods

[3] C. D. Walter,  Formal Methods, Concise Encyclopedia of Software Engineering, D. Morris & B. Tamm editors, Pergamon Press, 1991, pp. 135-138.

[2] C. D. Walter & S. E. Eldridge,   Specification and Verification of Software, Concise Encyclopedia of Software Engineering, D. Morris & B. Tamm editors, Pergamon Press, 1991, pp. 331-338.

[1] (Book) R. Dowsing, V. J. Rayward-Smith & C. D. Walter, A First Course in Formal Logic and its Applications in Computer Science, Blackwell Scientific Publications, Oxford, 1986 (265pp + vi).


Graph Theory

Here are my contributions to the graph isomorphism problem:

[2] C. D. Walter, Adjacency matrices, SIAM J. Algebraic & Discrete Methods, 7 (1986) pp. 18-29.

[1] C. D. Walter, Intersection numbers for coherent configurations and the spectrum of a graph, J. of Combinatorial Theory (B) 35(1983), pp. 201-204.


Algebraic Number Theory

From the good old days before Fermat’s Last Theorem had been proved, here are some of my contributions to the subject: (Some over bars etc may not be clear in the post script files, and some symbols may not print properly – particularly symbols for the rational integers and rational field – contact me for the sources if you wish.)

[6] C. D. Walter,  Pure fields of degree 9 with class number prime to 3, Annales de l’Institut Fourier, Grenoble 30 (1980), pp. 1-16.

[5] C. D. Walter,  The ambiguous class group and the genus group of certain non-normal extensions, Mathematika 26 (1979), pp. 113-124.

[4] C. D. Walter,  Kuroda’s class number relation, Acta Arithmetica 35 (1979), pp. 41-51.

[3] C. D. Walter,  Brauer’s class number relation, Acta Arithmetica 35 (1979), pp. 33-40.

[2] C. D. Walter,  A class number relation in Frobenius extensions of number fields, Mathematika 24 (1977), pp. 216-225.

[1] C. D. Walter & C. J. Parry,  The class number of pure fields of prime degree, Mathematika 23 (1976), pp. 220-226.


Copyright © 2015 Colin D. Walter,     Last Updated: 7th November 2015.