Definition 1 Advanced Computational Diffie-Hellman [BFPV11])
8.3 Future Work and Prospects
Future work on SIMPLs will likely concentrate on developing new protocols for SIMPL systems, and on devising formal security proofs for these protocols. For example, it seems interesting if time-restricted, but still useful variants of secure multi-party com- putation could be implemented by SIMPLs, and how the security of such constructions could be proven. But perhaps the greater challenge lies on the hardware side: Even though there are several promising candidates (see Section 7), the issue of finding a highly secure, practical, and cheap implementation appears not to be fully settled yet.
If such an implementation is found, or if the existing implementation candidates are shown to possess all necessary properties, this could potentially change the way we exercise cryptography and security today.
Acknowledgements. The author would like to thank J¨urg Wullschleger for suggesting the presented coin flipping protocol, and Ulf Schlichtmann, Stefan Wolf, J¨urg Wullschleger, Georg Sigl, Srinivas Devadas, Miodrag Potkonjak and Farinaz Koushan- far for very useful discussions on the general topic of SIMPLs/PPUFs, and David Nac- cache for a very helpful exchange on quasi-SIMPLs. This work was done within the physical cryptography project at the TU M¨unchen.
2The reader can verify the plausibility of the latter unclonability property by considering the op- tical implementation of section 7.3: Even if the positions of all scattering centers and the other irregularities in the scattering medium were known in full detail, it would still be infeasible to rebuild the scattering medium with perfect precision.
References
1. http://www.cbsnews.com/stories/2010/02/15/business/
main6209772.shtml
2. http://www.bbc.co.uk/news/10569081
3. http://www.eurosmart.com/images/doc/Eurosmart-in-the-press/
2006/cardtechnologytoday_dec2006.pdf
4. http://www.gsaietsemiconductorforum.com/2010/delegate/
documents/GASSELGSALondon20100518presented.pdf.(Slide 23)
5. Eisenbarth, T., Kasper, T., Moradi, A., Paar, C., Salmasizadeh, M., Manzuri Shalmani, M.T.:
On the power of power analysis in the real world: A complete break of theKEELOQcode hop- ping scheme. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 203–220. Springer, Heidelberg (2008)
6. Kasper, T., Silbermann, M., Paar, C.: All you can eat or breaking a real-world contactless payment system. In: Sion, R. (ed.) FC 2010. LNCS, vol. 6052, pp. 343–350. Springer, Hei- delberg (2010)
7. Anderson, R.J.: Security Engineering: A Guide to Building Dependable Distributed Systems, 2nd edn. Wiley, Chichester (2008) ISBN: 978-0-470-06852-6
8. Pappu, R., Recht, B., Taylor, J., Gershenfeld, N.: Physical One-Way Functions. Science 297, 2026–2030 (2002)
9. Pappu, R.: Physical One-Way Functions, PhD Thesis, MIT
10. Gassend, B., Clarke, D.E., van Dijk, M., Devadas, S.: Silicon physical random functions. In:
ACM Conference on Computer and Communications Security 2002, pp. 148–160 (2002) 11. Gassend, B., Lim, D., Clarke, D., van Dijk, M., Devadas, S.: Identification and authentication
of integrated circuits. Concurrency and Computation: Practice & Experience 16(11), 1077–
1098 (2004)
12. Tuyls, P., Skoric, B.: Strong Authentication with Physical Unclonable Functions. In:
Petkovic, M., Jonker, W. (eds.) Security, Privacy and Trust in Modern Data Management.
Springer, Heidelberg (2007)
13. Edward Suh, G., Devadas, S.: Physical Unclonable Functions for Device Authentication and Secret Key Generation. In: DAC 2007, pp. 9–14 (2007)
14. Gassend, B., van Dijk, M., Clarke, D.E., Torlak, E., Tuyls, P., Devadas, S.: Controlled phys- ical random functions and applications. ACM Trans. Inf. Syst. Secur. 10(4) (2008)
15. R¨uhrmair, U.: Oblivious Transfer Based on Physical Unclonable Functions. In: Acquisti, A., Smith, S.W., Sadeghi, A.-R. (eds.) TRUST 2010. LNCS, vol. 6101, pp. 430–440. Springer, Heidelberg (2010)
16. R¨uhrmair, U.: SIMPL Systems: On a Public Key Variant of Physical Unclonable Functions.
Cryptology ePrint Archive, Report 2009/255 (2009)
17. R¨uhrmair, U., Chen, Q., Lugli, P., Schlichtmann, U., Stutzmann, M., Csaba, G.: Towards Electrical, Integrated Implementations of SIMPL Systems. Cryptology ePrint Archive, Re- port 2009/278 (2009)
18. Chen, Q., Csaba, G., Ju, X., Natarajan, S.B., Lugli, P., Stutzmann, M., Schlichtmann, U., R¨uhrmair, U.: Analog Circuits for Physical Cryptography. In: 12th International Symposium on Integrated Circuits (ISIC 2009), Singapore, December 14-16 (2009)
19. R¨uhrmair, U., Chen, Q., Stutzmann, M., Lugli, P., Schlichtmann, U., Csaba, G.: Towards electrical, integrated implementations of SIMPL systems. In: Samarati, P., Tunstall, M., Posegga, J., Markantonakis, K., Sauveron, D. (eds.) WISTP 2010. LNCS, vol. 6033, pp.
277–292. Springer, Heidelberg (2010)
20. R¨uhrmair, U.: SIMPL systems, or: Can we design cryptographic hardware without secret key information? In: ˇCern´a, I., Gyim´othy, T., Hromkoviˇc, J., Jefferey, K., Kr´alovi´c, R., Vukoli´c, M., Wolf, S. (eds.) SOFSEM 2011. LNCS, vol. 6543, pp. 26–45. Springer, Heidelberg (2011)
21. Chen, Q., Csaba, G., Lugli, P., Schlichtmann, U., Stutzmann, M., R¨uhrmair, U.: Circuit-based approaches to SIMPL systems. Journal of Circuits, Systems, and Computers, JCSC 20, 107–
123 (2011), doi:10.1142/S0218126611007098
22. Chua, L.O., Roska, T., Kozek, T., Zarandy, A.: CNN Universal Chips crank up the computing power. IEEE Circuits and Devices Magazine 12(4), 18–28 (1996)
23. Roska, T.: Cellular Wave Computers for Nano-Tera-Scale Technology — beyond spatial- temporal logic in million processor devices. Electronics Letters 43(8) (April 12, 2007) 24. Beckmann, N., Potkonjak, M.: Hardware-based public-key cryptography with public phys-
ically unclonable functions. In: Katzenbeisser, S., Sadeghi, A.-R. (eds.) IH 2009. LNCS, vol. 5806, pp. 206–220. Springer, Heidelberg (2009)
25. Koushanfar, F., Potkonjak, M.: CAD-based Security, Cryptography, and Digital Rights Man- agement. In: DAC 2007, pp. 268–269 (2007)
26. Majzoobi, M., Elnably, A., Koushanfar, F.: FPGA Time-Bounded Unclonable Authentica- tion. In: B¨ohme, R., Fong, P.W.L., Safavi-Naini, R. (eds.) IH 2010. LNCS, vol. 6387, pp.
1–16. Springer, Heidelberg (2010)
27. R¨uhrmair, U., S¨olter, J., Sehnke, F.: On the Foundations of Physical Unclonable Functions.
IACR Cryptology E-print Archive, Report No. 227/2009 (2009)
28. R¨uhrmair, U., Busch, H., Katzenbeisser, S.: Strong PUFs: Models, Constructions and Secu- rity Proofs. In: Sadeghi, A.-R., Naccache, D. (eds.) Towards Hardware Intrinsic Security:
Foundation and Practice. Springer, Heidelberg (2010)
29. Gassend, B.: Physical Random Functions, MSc Thesis, MIT (2003)
30. Guajardo, J., Kumar, S.S., Schrijen, G.-J., Tuyls, P.: FPGA Intrinsic PUFs and Their Use for IP Protection. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp.
63–80. Springer, Heidelberg (2007)
31. R¨uhrmair, U., Sehnke, F., S¨olter, J., Dror, G., Devadas, S., Schmidhuber, J.: Modeling Attacks on Physical Unclonable Functions. In: 17th ACM Conference on Computer and Communi- cations Security (2010); Previous versions available from Cryptology ePrint Archive, Report 251/2010
32. Feynman, R.P.: Simulating physics with computers. International Journal of Theoretical Physics (1982)
33. Naccache, D., Raihi David, M.: Procede de Generation de Signature Numeriques de Mes- sages. French Patent, Publication Number 2733378, National Registration Number 9504753 (1995)
34. Naccache, D.: Method for the Generation of Electronic Signatures, in particular for Smart Cards. US Patent Number 5,910,989 (1999)
35. Blum, M.: Coin flipping by telephone. In: Proc. IEEE Spring COMPCOM, pp. 133–137.
IEEE, Los Alamitos (1982)
36. Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game. In: Proceedings of The Nineteenth Annual ACM Symposium on Theory of Computing (1987)
37. Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity and a methodology of cryptographic protocol design. In: 27th Annual Symposium on the Founda- tions of Computer Science, FOCS (1986)
38. Halevi, S., Krawczyk, H.: MMH: Software Message Authentication in the Gbit/Second Rates. In: Biham, E. (ed.) FSE 1997. LNCS, vol. 1267, pp. 172–189. Springer, Heidelberg (1997)
39. DeJean, G., Kirovski, D.: RF-DNA: Radio-Frequency Certificates of Authenticity. In: Pail- lier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 346–363. Springer, Hei- delberg (2007)
40. Kariakin, Y.: Authentication of Articles. Patent Writing, WO/1997/024699 (1995), available fromhttp://www.wipo.int/pctdb/en/wo.jsp?wo=1997024699
41. Vijaywargi, D., Lewis, D., Kirovski, D.: Optical DNA. In: Dingledine, R., Golle, P. (eds.) FC 2009. LNCS, vol. 5628, pp. 222–229. Springer, Heidelberg (2009)
42. Hammouri, G., Dana, A., Sunar, B.: CDs Have Fingerprints Too. In: Clavier, C., Gaj, K.
(eds.) CHES 2009. LNCS, vol. 5747, pp. 348–362. Springer, Heidelberg (2009)
43. Diffie, W., Hellman, M.E.: New Directions in Cryptography. IEEE Transactions on Informa- tion Theory IT-22, 644–654 (1976)
44. Naor, M., Ostrovsky, R., Venkatesan, R., Yung, M.: Perfect zero-knowledge arguments for NP using any one-way function. Journal of Cryptology 11(2), 87–108 (1998)
45. Savvides, G.: Interactive Hashing and reductions between Oblivious Transfer variants. PhD thesis, McGill University, Montreal (2007)
46. Haitner, I., Reingold, O.: A new interactive hashing theorem. In: IEEE Conference on Com- putational Complexity (2007)
47. Blum, M.: Coin flipping by telephone. In: Gersho, A. (ed.) Advances in Cryptography, pp.
11–15. University of California, Santa Barbara (1982)
48. Goldreich, O.: The Foundations of Cryptography, vol. 1. Cambridge University Press, Cam- bridge (2001)
49. Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the Association for Com- puting Machinery 38(3), 691–729 (1991)
50. Brassard, G., Chaum, D., Crepeau, C.: Minimum disclosure proofs of knowledge. JCSS 37, 156–189 (1988)
51. Kilian, J.: Founding cryptography on oblivious transfer. In: Proc. 20th ACM Symposium on Theory of Computing, pp. 20–31. ACM Press, Chicago (1988)
52. Yao, A.C.-C.: Classical physics and the Church-Turing Thesis. Journal of the ACM 50(1), 100–105 (2003)
53. Aaronson, S.: NP-complete Problems and Physical Reality. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 026 (2005)
54. Shor, P.W.: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput. 26(5), 1484–1509 (1997)
55. Csaba, G., Ju, X., Ma, Z., Chen, Q., Porod, W., Schmidhuber, J., Schlichtmann, U., Lugli, P., R¨uhrmair, U.: Application of Mismatched Cellular Nonlinear Networks for Physical Cryp- tography. In: IEEE CNNA (2010)
56. Lim, D.: Extracting Secret Keys from Integrated Circuits. M.Sc. Thesis, MIT (2004) 57. Suh, G.E., O’Donnell, C.W., Sachdev, I., Devadas, S.: Design and Implementation of the
AEGIS Single-Chip Secure Processor Using Physical Random Functions. In: Proc. 32nd ISCA, New York (2005)
58. Yu, M. D.M., Devadas, S.: Secure and Robust Error Correction for Physical Unclonable Functions. IEEE Design & Test of Computers 27(1), 48–65 (2010)
59. Armknecht, F., Maes, R., Sadeghi, A.-R., Sunar, B., Tuyls, P.: Memory Leakage-Resilient Encryption Based on Physically Unclonable Functions. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 685–702. Springer, Heidelberg (2009)
60. R¨uhrmair, U., Weiersh¨auser, A., Urban, S., Hilgers, C., Finley, J.: Secure Integrated Optical Physical Unclonable Functions (2010) (in preparation)
61. Lipson, S.G.: Optical Physics, 3rd edn. Cambridge University Press, Cambridge (1995) ISBN 0-5214-3631-1
62. Demtr¨oder, W.: Experimentalphysik 2: Elektrizit¨at und Optik. Springer, Heidelberg (2004) ISBN-10: 3540202102
63. Zhou, D., Mawst, L.J.: Two-dimensional phase-locked antiguided vertical-cavity surface- emitting laser arrays. Applied Physics Letters (2000)
Automata
Peter Schmidt-Nielsen, Kailiang Chen, Jonathan Bachrach, Scott Greenwald, Forrest Green, and Neil Gershenfeld
MIT Center for Bits and Atoms, Cambridge, MA
Abstract. We introduce the use of asynchronous logic automata (ALA) for cryptography. ALA aligns the descriptions of hardware and software for portability, programmability, and scalability. An implementation of the A5/1 stream cipher is provided as a design example in a concise hard- ware description language, Snap, and we discuss a power- and timing- balanced cell design.
Keywords: asynchronous, cellular, cryptography, stream cipher, power balance.
1 Introduction
Cellular architectures have long been attractive for cryptography [1,2,3,4,5]. Cel- lular automata, by discretizing time, space, and state, with cell transitions de- fined by indexing a rule table with a bit string representing states in a local neighborhood, offer bit-level parallelism with simple local dynamics.
These have, however, had little impact on technological practice. Field Pro- grammable Gate Arrays are now routinely used to implement high-performance cryptosystems [6]. CAs, in comparison, have lacked both hardware platforms and design workflows to implement cryptographic algorithms.
Use of FPGAs does conventionally assume synchronously clocked logic. Self- timed cryptographic circuits have been developed [7,8]; these can have benefits for speed, power consumption, and robustness against side-channel attacks, but have typically been developed for special-purpose applications rather than as a general-purpose architecture.
FPGAs also rely on a fitter to map a design onto a gate array, which can require significant extra effort in logic synthesis, and has led to the introduction of increasingly large functional modules on the die. Because chip edges differ from their interiors, there is not a straightforward route to divide a single design across multiple gate arrays.
We present an alternative approach to implementing cryptosystems that lies at the intersection of cellular logic, gate arrays, and asynchronous circuits. It is based on Asynchronous Logic Automata (ALA), a model of computation that seeks to align the descriptions of hardware and software. In the following sections we introduce ALA, illustrate its use with an implementation of the A5/1 stream cipher used in GSM, and discuss the design and balancing of circuits.
D. Naccache (Ed.): Quisquater Festschrift, LNCS 6805, pp. 355–363, 2012.
c Springer-Verlag Berlin Heidelberg 2012