×

The secret life of keys: on the calculation of mechanical lock systems. (English) Zbl 1370.90232

Summary: Keys and locks are an omnipresent fixture in our daily life, limiting physical access to privileged resources or spaces. While most of us may have marveled at the intricate shape of a key, the usually hidden mechanical complexity within a cylinder lock is even more awe-inspiring, containing a multitude of tiny movable parts such as springs and pins that have been precision-manufactured from highly customized materials using specialized fabrication techniques.
It is perhaps unknown that mechanical cylinder locks possess a number of important design constraints that uniquely distinguish them from their electronic counterparts. Aside from manufacturing costs, a cylinder’s most significant limitations are the upper bound on its outer dimensions as well as the lower bound on the size of its internal mechanical security features (pins). Cylinders cannot be very large so that they still fit into doors and avoid the need for large keys. Pins cannot be too small in order to withstand wear and tear and provide appropriate physical security.
Even more complex than a single cylinder is the design of an ensemble of “related” locks as may occur in an apartment, office building, factory, or hospital, for example. Instead of controlling access to one resource, the set of open/not open relationships between all the keys and locks of such a lock system may encode a complex and diverse hierarchy of privileges for each individual key, from the benign opening of the front entrance by all staff to heavily restricted access to confidential documents or hazardous materials by selected personnel only.
For the mathematician or computer scientist, lock system design poses a fascinating array of theoretical and computational challenges. Abstraction via an algebraic model shows that cylinders and keys of a lock system can be represented within an upper semilattice, where the induced partial ordering establishes the must open/must not open functions. Finding an “equivalent” sub-semilattice within the semilattice over the set of those cylinders that are mechanically realizable then embodies the heart of the lock system calculation problem.
From the graph-theory point of view, finding such a sub-semilattice is exactly the famous graph subgraph isomorphism problem, which is known to be NP hard. As problem size increases, the solution via deterministic algorithms from combinatorial optimization quickly becomes intractable. In particular, conventional branch-and-bound strategies such as pruning, designed to limit systematic examination of the full search space, are ineffective for the graphs arising from lock systems.
For this reason, a pragmatic approach has to resort to randomized search space exploration via probabilistic heuristics that are by their very nature not guaranteed to work in all cases, but do yield results quickly enough to be useful for many relevant practical cases. Among the class of randomized optimization algorithms, simulated annealing proves to be particularly relevant for our setting. However, the vast available search space makes a vanilla algorithm impractical and adaptations are necessary. Parameters such as the cooling strategy have to be carefully tuned and the design of the error function for evaluating the quality of the tentative isomorphisms must weigh the tradeoff between expressiveness and runtime costs. Finally, in order to steer the algorithm toward promising choices in the search space, we combine annealing with a prefilter that guides selection based on an encoding computed in a preprocessing step.
The research described within this article was conducted in a research partnership between academia and industry; its goal is to develop a formalized model and an automated lock system calculation approach suitable for commercial use. Moreover, we wish to spark interest in the broader mathematics and computer science community in the challenging questions arising from this exciting industrial application.

MSC:

90C27 Combinatorial optimization
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
06A12 Semilattices
68W20 Randomized algorithms
90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] E. Aarts and J. Korst, {\it Simulated Annealing and Boltzmann Machines}, Wiley, New York, 1988. · Zbl 0674.90059
[2] E. Aarts and J. K. Lenstra, {\it Local Search in Combinatorial Optimization}, Princeton University Press, Princeton, NJ, 2003. · Zbl 1106.90002
[3] J. L. Adams, {\it Good Products, Bad Products}, McGraw-Hill, New York, 2012.
[4] A. V. Aho, M. R. Garey, and J. D. Ullman, {\it The transitive reduction of a directed graph}, SIAM J. Comput., 1 (1972), pp. 131-137, . · Zbl 0247.05128
[5] H. Aït-Kaci, R. Boyer, P. Lincoln, and R. Nasr, {\it Efficient implementation of lattice operations}, ACM Trans. Program. Lang. Syst., 11 (1989), pp. 115-146.
[6] P. R. Amestoy, I. S. Duff, and C. Vömel, {\it Task scheduling in an asynchronous distributed memory multifrontal solver}, SIAM J. Matrix Anal. Appl., 26 (2005), pp. 544-565, . · Zbl 1075.65039
[7] R. J. Anderson, {\it Security Engineering: A Guide to Building Dependable Distributed Systems}, Wiley, New York, 2008.
[8] A. Auger and B. Doerr, {\it Theory of Randomized Search Heuristics: Foundations and Recent Developments}, World Scientific, River Edge, NJ, 2011. · Zbl 1233.90005
[9] G. Birkhoff, {\it Lattice Theory}, revised ed., AMS, New York, 1948. · Zbl 0033.10103
[10] E. K. Burke and G. Kendall, {\it Search Methodologies}, 2nd ed., Springer, New York, 2014.
[11] Y. Caseau, {\it Efficient handling of multiple inheritance hierarchies}, SIGPLAN Not., 28 (1993), pp. 271-287.
[12] Y. Caseau, M. Habib, L. Nourine, and O. Raynaud, {\it Encoding of multiple inheritance hierarchies and partial orders}, Comput. Intell., 15 (1999), pp. 50-62.
[13] V. Černý, {\it Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm}, J. Optim. Theory Appl., 45 (1985), pp. 41-51. · Zbl 0534.90091
[14] P. Colomb, O. Raynaud, and E. Thierry, {\it Generalized polychotomic encoding: A very short bit-vector encoding of tree hierarchies}, in Modelling, Computation and Optimization in Information Systems and Management Sciences, Comm. Comput. Inf. Sci. 14, Springer, New York, 2008, pp. 77-86. · Zbl 1160.90702
[15] L. P. Cordella, P. Foggia, C. Sansone, and M. Vento, {\it An improved algorithm for matching large graphs}, in Proceedings of the 3rd IAPR-TC15 Workshop on Graph-Based Representations in Pattern Recognition, Cuen, 2001, pp. 149-159.
[16] L. P. Cordella, P. Foggia, C. Sansone, and M. Vento, {\it A (sub)graph isomorphism algorithm for matching large graphs}, IEEE Trans. Patt. Anal. Mach. Int., 26 (2004), pp. 1367-1372.
[17] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, {\it Introduction to Algorithms}, 3rd ed., MIT Press, Cambridge, MA, 2009. · Zbl 1187.68679
[18] T. M. Cover and J. A. Thomas, {\it Elements of Information Theory}, 2nd ed., Wiley, New York, 2006. · Zbl 1140.94001
[19] B. A. Davey and H. A. Priestley, {\it Introduction to Lattices and Order}, 2nd ed., Cambridge University Press, Cambridge, UK, 2002. · Zbl 1002.06001
[20] A. Dekkers and E. Aarts, {\it Global optimization and simulated annealing}, Math. Program., 50 (1991), pp. 367-393. · Zbl 0753.90060
[21] D. Ellerman, {\it The logic of partitions: Introduction to the dual of the logic of subsets}, Rev. Symb. Log., 3 (2010), pp. 287-350. · Zbl 1211.03101
[22] L. Fennelly, {\it Effective Physical Security}, 4th ed., Butterworth-Heinemann, London, 2012.
[23] N. Ferguson, B. Schneier, and T. Kohno, {\it Cryptography Engineering: Design Principles and Practical Applications}, Wiley, New York, 2010.
[24] M. R. Garey and D. S. Johnson, {\it Computers and Intractability: A Guide to the Theory of NP-Completeness}, W. H. Freeman, New York, 1979. · Zbl 0411.68039
[25] J. C. Giarratano and G. D. Riley, {\it Expert Systems: Principles and Programming}, 4th ed., Thomson Course Technology, 2005.
[26] B. Glover and H. Bhatt, {\it RFID Essentials}, O’Reilly Media, Sebastopol, CA, 2006.
[27] F. Glover and M. Laguna, {\it Tabu Search}, Kluwer Academic, Norwell, MA, 1997.
[28] M. Habib and L. Nourine, {\it Bit-vector encoding for partially ordered sets}, in Orders, Algorithms, and Applications, Lecture Notes in Comput. Sci. 831, Springer, New York, 1994, pp. 1-12. · Zbl 0953.06500
[29] M. Habib, L. Nourine, O. Raynaud, and E. Thierry, {\it Computational aspects of the \(2\)-dimension of partially ordered sets}, Theoret. Comput. Sci., 312 (2004), pp. 401-431. · Zbl 1070.68051
[30] D. Henning and C. Reynolds, {\it Houdini: His Legend and His Magic}, Warner Books, New York, 1977.
[31] L. Hérault, R. Horaud, F. Veillon, and J.-J. Niez, {\it Symbolic image matching by simulated annealing}, in Proceedings of the 4th British Machine Vision Conference (BMVC ’90), British Machine Vision Association (BMVA), 1990, pp. 319-324.
[32] P. Jackson, {\it Introduction To Expert Systems}, 3rd ed., Addison-Wesley, Reading, MA, 1998. · Zbl 0634.68086
[33] G. James, D. Witten, T. Hastie, and R. Tibshirani, {\it An Introduction to Statistical Learning}, Springer, New York, 2013. · Zbl 1281.62147
[34] L. Jones and T. de Castella, {\it Is the traditional metal key becoming obsolete?} BBC News Mag., October 30, 2014, bbc.com/news/magazine-29817520.
[35] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, {\it Optimization by simulated annealing}, Science, 220 (1983), pp. 671-680. · Zbl 1225.90162
[36] J. Kleinberg and E. Tardos, {\it Algorithm Design}, 1st international ed., Pearson, London, 2013.
[37] B. Korte and J. Vygen, {\it Combinatorial Optimization: Theory and Algorithms}, 5th ed., Springer, New York, 2012. · Zbl 1237.90001
[38] A. Krall, J. Vitek, and R. Horspool, {\it Near optimal hierarchical encoding of types}, in ECOOP’97–Object-Oriented Programming, Lecture Notes in Comput. Sci. 1241, Springer, New York, 1997, pp. 128-145.
[39] M. Kuramochi and G. Karypis, {\it Frequent subgraph discovery}, in Proceedings of the 2001 IEEE International Conference on Data Mining (ICDM ’01), IEEE Computer Society Press, 2001, pp. 313-320.
[40] S. Kurutz, {\it Losing the key}, The New York Times, June 11, 2014.
[41] A. Lawer, {\it Calculation of Lock Systems}, Master’s degree project, trita-na-e04081, Royal Institute of Technology, Stockholm, Sweden, 2004.
[42] R. Leighton and R. P. Feynman, {\it Surely You’re Joking, Mr. Feynman!}, Vintage, New York, 1992.
[43] D. J. C. MacKay, {\it Information Theory, Inference and Learning Algorithms}, Cambridge University Press, New York, 2003. · Zbl 1055.94001
[44] G. Markowsky, {\it The representation of posets and lattices by sets}, Algebra Universalis, 11 (1980), pp. 173-192. · Zbl 0449.06007
[45] G. Markowsky, {\it An overview of the poset of irreducibles}, in Combinatorial and Computational Mathematics: Present and Future, World Scientific, River Edge, NJ, 2001, pp. 162-177. · Zbl 1016.06004
[46] M. McCloud, G. de Santos, and M. Jugurdzija, {\it Visual Guide to Lock Picking}, 3rd ed., Standard Publications, Champaign, IL, 2007.
[47] Z. Michalewicz, {\it Genetic Algorithms + Data Structures = Evolution Programs}, 3rd ed., Springer, New York, 2008. · Zbl 0841.68047
[48] Z. Michalewicz and D. B. Fogel, {\it How to Solve It: Modern Heuristics}, 2nd ed., Springer, New York, 2004. · Zbl 1058.68105
[49] C. Moore and S. Mertens, {\it The Nature of Computation}, Oxford University Press, Oxford, 2011. · Zbl 1237.68004
[50] D. Ollam, {\it Practical Lock Picking, Second Edition: A Physical Penetration Tester’s Training Guide}, 2nd ed., Syngress, Maryland Heights, MO, 2012.
[51] R. Paige and R. E. Tarjan, {\it Three partition refinement algorithms}, SIAM J. Comput., 16 (1987), pp. 973-989, . · Zbl 0654.68072
[52] C. H. Papadimitriou and K. Steiglitz, {\it Combinatorial Optimization: Algorithms and Complexity}, Dover, New York, 1998. · Zbl 0944.90066
[53] B. Phillips, {\it The Complete Book of Locks and Locksmithing}, 6th ed., McGraw-Hill Professional, New York, 2005.
[54] O. Raynaud and E. Thierry, {\it The complexity of embedding orders into small products of chains}, Order, 27 (2010), pp. 365-381. · Zbl 1205.06001
[55] C. Robert and G. Casella, {\it Monte Carlo Statistical Methods}, 2nd ed., Springer, New York, 2010. · Zbl 1096.62003
[56] S. Roman, {\it Coding and Information Theory}, Springer, New York, 1992. · Zbl 0752.94001
[57] S. Russell and P. Norvig, {\it Artificial Intelligence: A Modern Approach}, 3rd ed., Pearson, London, 2010. · Zbl 0835.68093
[58] P. Salamon, P. Sibani, and R. Frost, {\it Facts, Conjectures, and Improvements for Simulated Annealing}, SIAM, Philadelphia, 2002. · Zbl 1070.90137
[59] J. J. Schneider and S. Kirkpatrick, {\it Stochastic Optimization}, Springer, New York, 2006. · Zbl 1116.90083
[60] B. Schröder, {\it Ordered Sets}, Birkhäuser, Cambridge, MA, 2003. · Zbl 1010.06001
[61] J. G. Siek, {\it An Implementation of Graph Isomorphism Testing}, 2001; available at boost.org/doc.
[62] J. G. Siek, L.-Q. Lee, and A. Lumsdaine, {\it The Boost Graph Library. User Guide and Reference Manual. (C++ in Depth)}, Addison-Wesley Longman, Amsterdam, 2002.
[63] D. Simon, {\it Evolutionary Optimization Algorithms}, Wiley, New York, 2013.
[64] R. Singleton, {\it Maximum distance \(q\)-nary codes}, IEEE Trans. Information Theory, 10 (1964), pp. 116-118. · Zbl 0124.11505
[65] S. S. Skiena, {\it The Algorithm Design Manual}, 2nd ed., Springer, New York, 2008. · Zbl 1149.68081
[66] C. Swedberg, {\it ASSA ABLOY creates NFC solution that uses phones to open doors, grant computer access}, RFID J., September 12, 2012, .
[67] J. R. Ullmann, {\it An algorithm for subgraph isomorphism}, J. ACM, 23 (1976), pp. 31-42. · Zbl 0323.05138
[68] J. R. Ullmann, {\it Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism}, ACM J. Exp. Algorithmics, 15 (2010), article 1.6. · Zbl 1284.68529
[69] M. van Bommel and P. Wang, {\it Hierarchy encoding with multiple genes}, in Database and Expert Systems Applications, Lecture Notes in Comput. Sci. 5181, Springer, New York, 2008, pp. 761-769.
[70] J. H. van Lint, {\it Introduction to Coding Theory}, 3rd ed., Springer, New York, 1998. · Zbl 0747.94018
[71] L. R. Vermani, {\it Elements of Algebraic Coding Theory}, Chapman Hall/CRC, Boca Raton, FL, 1996. · Zbl 0922.94010
[72] D. H. Wolpert and W. G. Macready, {\it No free lunch theorems for optimization}, IEEE Trans. Evol. Comput., 1 (1997), pp. 67-82.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.