-
Notifications
You must be signed in to change notification settings - Fork 1
Latin Squares and Their Applications to Cryptography by N. O. Schmidt
License
nathanoschmidt/latin-square-toolbox
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Folders and files
Name | Name | Last commit message | Last commit date | |
---|---|---|---|---|
Repository files navigation
************************************************************************ ********************** LATIN SQUARE TOOLBOX v1.10 ********************** ************************************************************************ ***************** By Nathan O. Schmidt and Will Unger ****************** ************************************************************************ ************************************************************************ *** SUMMARY ************************************************************ ************************************************************************ Welcome to the Latin Square Toolbox! This version contains three tools: 0) Latin Square Generator (LSG) 1) Latin Square Transversal Counter (LSTC) 2) Latin Square Property Checker (LSPC) [Latin Square Generator Tool] First, let's summarize the LSG. The LSG contains three Latin square generation modes: 0) Data Set (DS) - The DS mode uses a recursive, selection-based algorithm to generate a data set with a specific number of order-n Latin squares. In theory, the algorithm is capable of generating the set of all Latin squares for a given order, but in practice this is only possible for relatively small orders and depends on hardware limitations. To date of writing, the total number of Latin squares for a given order-n are only known up for 1 <= n <= 11; for example, there are 61,479,419,904,000 order-7 Latin squares and 776,966,836,171,770,144,107,444,346,734,230,682,311,065,600,000 order-11 Latin squares; see OEIS sequence A002860. On a laptop computer, we've used the DS mode to generate proper subsets of Latin squares up to order-30 and beyond. The DS mode requires that the user specify the size of the data set and the order of the Latin squares to be generated. 1) Data Set Preloading (DSP) - The DSP mode's algorithm is nearly identical to the DS algorithm, but there is a difference in performance: the DSP mode is capable of generating data sets of Latin squares of higher orders faster than the DS mode, but the DSP mode may skip some of the Latin squares in the process. Therefore, if you want to generate larger data sets of higher order Latin squares faster and don't care if some of the Latin squares may be skipped, then the DSP mode may be more useful. Similarly to the DS mode, the DSP mode requires that the user specify the size of the data set and the order of the Latin squares to be generated. 2) Super-Symmetric (SS) - The SS mode uses a recursive, lifting-and -merging algorithm to generate a single prime power order-p^d super-symmetric Latin square, where p is prime and d > 1. If d = 1, then a single prime order-p cyclic Latin square is generated. In short, our new lifting-and-merging algorithm uses prime order-p cyclic Latin squares as "building blocks" to recursively construct order-p^d super-symmetric Latin squares that exhibit a self-similar structure; see [0] for details. In [0] we correctly predicted that this algorithm (also termed the "SS-LS-GA" in [0]) generates Latin squares that have the confirmed maximum transversal counts for 3 <= p^d <= 9, and we used this evidence to conjecture that any prime power order-p^d Latin square that is generated by this algorithm *may* have the maximum transversal counts for all any prime p with d >= 1. So if you wish to investigate this, then we invite you to experiment! Let’s see if our conjecture can stand the test of time! Can one prove or disprove this? In any case, the SS mode requires that the user specify the prime base p and the prime power d of the order-p^d of the Latin square to be generated. We'll note that the DS and DSP modes contain are our latest and fastest algorithms for generating Latin square data sets; these were our personal records that we achieved given the allocated time and resources. The DS and DSP modes evolved from several prior pre-release versions. Some of these details are discussed in [0] with benchmark comparisons. [Latin Square Transversal Counter Tool] Second, let's discuss the LSTC. The LSTC contains one mode for counting the number of transversals in a set of Latin squares. The LSTC requires that the user specify two parameters: the input file containing a set of order-n Latin squares (encoded in the ordered-triple format) and the order of the Latin squares in the file. In this current LSTC implementation, all Latin squares in the input file must have the same order, which must match the user-specified order (a constraint that we may remove in the near future, but for now this works well for speed and efficiency purposes). In any case, we'll also note that this LSTC mode implements our latest and fastest algorithm for counting transversals; through benchmark comparisons we discovered that this algorithm set our personal record; see [0] for some additional details. Now let's recall that the three previously mentioned LSG generation modes, the LSG requires the user to specify two parameters via command-line interface (no GUI... yet!). In this case, the LSG will generate and print the resulting Latin square(s) to standard output. Thus, the LSG output can simply be redirected to a file, where each square is separated by a blank line and represented as an n-by-n array of cells such that each cell is encoded as a 3D coordinate in the ordered-triple format (row,column,symbol) where each line of cells corresponds to a row of the Latin square. Thereafter, a tool such as the LSTC can post-process the Latin squares in an LSG output file to count and print the number of transversals in each. On the other hand, if the user supplies LSG with any optional parameters, then additional meta-data may be included in the output, which currently cannot be parsed and ignored by LSTC (a feature that we may add in the near future). So in short, if you want LSG's output to be LSTC's input, then just specify LSG's two required parameters for a given mode. [Latin Square Property Checker Tool] Finally, let's discuss the LSPC. The LSPC is the simplest tool in the toolbox: it checks a set of order-n *squares* to determine which ones are actually *Latin squares*; that is, it reports which squares in the set (if any) satisfy the Latin Square Property; in other words, it reports which order-n squares encode the Cayley table of an order-n quasi-group. Thus, for instance, if you have one or more squares in a file and you want to determine if any of your squares are Latin squares, then you may use the LSPC. You'll need to make sure that your squares are encoded in the ordered-triple format that is identical to the default LSG output because the LSPC requires this input file format (just like the LSTC). The LSPC requires that the user specify two parameters: the input file containing a set of order-n Latin squares (encoded as ordered-triples) and the order of the Latin squares in the file. In this current LSPC implementation, all Latin squares in the input file must have the same order, which must match the user-specified order. We hope that you find our Latin Square Toolbox to be educational and useful! Remember, this is released under the MIT License, so have fun, experiment, build, and learn! ************************************************************************ *** LATIN SQUARE BACKGROUND AND MOTIVATION ***************************** ************************************************************************ If you don't know what a Latin square or a transversal is, then you may find this section to be a helpful introduction. For more detailed information on Latin squares, we recommend [0] and the numerous rich references therein. Definition: A "Latin square" of order-n is an n-by-n array over a set of n symbols, where every symbol appears exactly once in each row and each column. Definition: A "quasi-group" of order-n is a set S of n symbols equipped a binary operation + that obeys the "Latin Square Property"; that is, for each a and b in S, there exist unique elements x and y in S such that a + x = b and y + a = b. Basically, this is an algebraic way to say that every element in S is a symbol that appears exactly once in each row and each column of S's Cayley table (which is a Latin square). So an order-n Latin square encodes the Cayley table of an order-n quasi-group. Thus, for every Latin square, there exists a corresponding quasi-group, and for every quasi-group, there exists a corresponding Latin square; so in this sense Latin squares and quasi-groups are equivalent! Therefore, a Latin square encodes features of its representative quasi-group, which is a fundamental algebraic structure for disciplines such as computing, cryptography, and cyber security. Certain quasi-groups, such as groups and finite fields, are used to construct cryptographic systems such as hash functions or encryption algorithms. For example, such cryptographic systems may be used to protect your passwords, web traffic, and privacy, etc. Certain features of such algebraic structures can impact the computational security of systems. In today's world, it is no secret that cryptography and cyber security are super important! Thus, to create and maintain strong cryptographic systems, it is essential for folks to use the scientific method and the mathematical method to construct and evaluate cryptographic systems and the underlying algebraic structures used to build these systems. It turns out that analyzing a Latin square is equivalent to analyzing its representative quasi-group (and vice-versa). In terms of security applications, a paramount feature of a Latin square is the following... Definition: A transversal of a Latin square is a set of entries which includes exactly one entry from each row and column, and one of each symbol. More specifically, the number of transversals in a Latin square is a key feature of interest when evaluating the computational security of a cryptographic system. The question regarding the existence of transversals in Latin squares that encode the Cayley tables of algebraic structures is far from being resolved and is an area of active investigation. It is known that counting the pairs of permutations over a finite field whose point-wise sum is also a permutation is equivalent to counting the transversals of a Latin square that encodes the Cayley table of the finite field's addition group. Therefore, in order to build strong cryptographic systems, it is desirable to find Latin squares with *maximum transversal counts* and then use those to build such systems; in other words, when an algebraic structure passes certain "Latin square tests", it is a candidate for use in the construction of cryptographic systems that can be applied to this modern digital age. Indeed, Latin squares are elemental to cryptography and cyber security! ************************************************************************ *** INSTALLATION ******************************************************* ************************************************************************ The Latin Square Toolbox is written in the Java programming language, so it should be compatible with systems that are equipped with the Java platform. We're using Apache Maven (https://maven.apache.org/) to manage the dependencies. Note: for this version of the release, the install and clean scripts have only been implemented and tested on Linux with Bash; they are currently not available for Mac OSX and Windows. [STEP 0] Install the Java Runtime Environment (JRE) and the Java Development Kit (JDK). [STEP 1] Install Apache Maven. [STEP 2] Download the Latin Square Toolbox from one of the following locations: 0) SourceForge (https://sourceforge.net/projects/latin-square-toolbox/) 1) GitHub (https://github.com/nathanoschmidt/latin-square-toolbox) [STEP 3] Once the download is complete, then use the command-line interface to nagivate to the Latin Square Toolbox's base directory. Note: If the toolbox is zipped and/or tarballed, then unzip and/or untar it first. :) [STEP 4] To compile the Latin Square Toolbox, execute the build script for your operating system via the command-line interface. 0) For Linux execute: ./linux_build.sh 1) For Mac OS X execute: <not yet implemented> 2) For Windows execute: <not yet implemented> If all goes well, then the toolbox should be compiled and and ready to go! :D [UNINSTALL] To clean/remove the Latin Square Toolbox's compiled binaries, Javadocs, and scripts, execute the clean script for your operating system via the command-line interface. 0) For Linux execute: ./linux_clean.sh 1) For Mac OS X execute: <not yet implemented> 2) For Windows execute: <not yet implemented> ************************************************************************ *** USAGE ************************************************************** ************************************************************************ [Latin Square Generator Tool] In order to generate Latin squares, the general usage for the LSG is: $ ./lsg -m <mode> <mode specific arg 1> <mode specific arg 2> [optional args] The user must specify one of the following generation mode algorithms for the "-m <mode>": -m ds # Generate an order-n Latin square data set of size s -m dsp # Generate an order-n Latin square data set of size s # with preloading -m ss # Generate one order-p^d super-symmetric Latin square The specifically required arguments for the data set generation modes "-m ds" and "-m dsp" are: -n <order> # The Latin square order-n (a positive integer) -s <size> # The data set size s (a non-negative integer); "-s 0" # generates all The specifically required arguments for the super-symmetric generation mode "-m ss" are: -p <base> # The base p of the order-p^d super-symmetric Latin # square (a prime integer) -d <power> # The power d of the order-p^d super-symmetric Latin # square (a positive integer) The optional arguments for any mode are: -t # Count and print the number of transversals for each # Latin square -T # Print the transversals for each Latin square (includes # "-t") -h # Print the transversal heat map for each Latin square # (also counts transversals) -r # Print each Latin square in human-readable (non-ordered # -triple) form -j # Print the job report summary upon completion We note that the LSG and LSTC both have the ability to count the transversals of Latin squares, but they differ in that the LSG can only count transversals "on the fly" as it generates each Latin square, whereas the LSTC counts the transversals of Latin squares that stored in an input file (with an ordered-triple format) containing the default redirected output of the LSG. (LSG Example 0) To generate a data set with *all* order-5 Latin squares use: $ ./lsg -m ds -n 5 -s 0 (LSG Example 1) To generate a data set with 1 order-5 Latin square use: $ ./lsg -m ds -n 5 -s 1 (LSG Example 2) To generate a data set with 60 order-5 Latin squares use: $ ./lsg -m ds -n 5 -s 60 (LSG Example 3) To generate a data set with 60 order-5 Latin squares via preloading use: $ ./lsg -m dsp -n 5 -s 60 (LSG Example 4) To generate a single prime order-5 cyclic Latin square use: $ ./lsg -m ss -p 5 -d 1 (LSG Example 5) To generate a single prime power order-3^2 super-symmetric Latin square use: $ ./lsg -m ss -p 3 -d 2 (LSG Example 6) To generate a single prime power order-3^2 super-symmetric Latin square and count its transversals use: $ ./lsg -m ss -p 3 -d 2 -t (LSG Example 7) To generate a single prime power order-3^2 super-symmetric Latin square, count its transversals, and print its transversal list use: $ ./lsg -m ss -p 3 -d 2 -T (LSG Example 8) To generate a data set with 60 order-5 Latin squares and count the transversals for each use: $ ./lsg -m ds -n 5 -s 60 -t (LSG Example 9) To generate a data set with 60 order-5 Latin squares, count the transversals for each, and print the transversal list for each use: $ ./lsg -m ds -n 5 -s 60 -T (LSG Example 10) To generate a data set with 60 order-5 Latin squares, count the transversals for each, print the transversal list for each, and print the job report summary use: $ ./lsg -m ds -n 5 -s 60 -T -j (LSG Example 11) To generate a data set with 60 order-5 Latin squares, count the transversals for each, print the transversal list for each, print each square in human-readable form (non-ordered-triple form), and print the job report summary use: $ ./lsg -m ds -n 5 -s 60 -T -j -r (LSG Example 12) To generate a data set with 60 order-5 Latin squares, count the transversals for each, print the transversal list for each, print the transversal heat maps for each, and print the job report summary use: $ ./lsg -m ds -n 5 -s 60 -T -j -h [Latin Square Transversal Counter Tool] In order to count the number of transversals in Latin squares stored in an input file (with the ordered-triple format), the general usage for the LSTC is: $ ./lstc -f <file> -n <order> [optional args] The required arguments are: -f <file> # The input file containing a set of order-n # Latin squares in ordered-triple format -n <order> # The Latin square order (a positive integer # that must match the input file squares) The optional arguments are: -q # Be quiet! (Don't print anything during the job) -T # Print the transversals for each Latin square -h # Print the transversal heat map for each Latin # square (also counts transversals) -r # Print each Latin square in human-readable # (non-ordered-triple) form -j # Print the job report summary upon completion (LSTC Example 0) To generate a data set with *all* order-5 Latin squares with LSG and then count their transversals with LSTC use: $ ./lsg -m ds -n 5 -s 0 > output.txt $ ./lstc -f output.txt -n 5 (LSTC Example 1) To generate a data set with *all* order-5 Latin squares with LSG and then count their transversals and print their transversal lists with LSTC use: $ ./lsg -m ds -n 5 -s 0 > output.txt $ ./lstc -f output.txt -n 5 -T (LSTC Example 2) To generate a data set with *all* order-5 Latin squares with LSG and then count their transversals and print each square in human-readable form (non-ordered-triple form) use: $ ./lsg -m ds -n 5 -s 0 > output.txt $ ./lstc -f output.txt -n 5 -T -r (LSTC Example 3) To generate a data set with *all* order-5 Latin squares with LSG and then count their transversals and print a job report summary with LSTC use: $ ./lsg -m ds -n 5 -s 0 > output.txt $ ./lstc -f output.txt -n 5 -j (LSTC Example 4) To generate a data set with *all* order-5 Latin squares with LSG and then count their transversals, print their transversal heat maps, and print a job report summary with LSTC use: $ ./lsg -m ds -n 5 -s 0 > output.txt $ ./lstc -f output.txt -n 5 -j -h (LSTC Example 5) To generate a data set with *all* order-5 Latin squares with LSG and then count their transversals (but be "quiet" and not print each individual square along with its transversal count) and print a job report summary with LSTC use: $ ./lsg -m ds -n 5 -s 0 > output.txt $ ./lstc -f output.txt -n 5 -j -q [Latin Square Property Checker Tool] In order to determine which squares stored in an input file (with the ordered-triple format) satisfy the Latin Square Property, the general usage for the LSPC is: $ ./lspc -f <file> -n <order> [optional args] The required arguments are: -f <file> # The input file containing a set of order-n # squares in ordered-triple format -n <order> # The square order (a positive integer that must # match the input file squares) The optional arguments are: -r # Print each Latin square in human-readable # (non-ordered-triple) form -j # Print the job report summary upon completion (LSPC Example 0) To determine which order-5 squares in a file named "squares.txt" are actually Latin squares use: $ ./lspc -f squares.txt -n 5 (LSPC Example 1) To determine which order-5 squares in a file named "squares.txt" are actually Latin squares and print the job report summary use: $ ./lspc -f squares.txt -n 5 -j (LSPC Example 2) To determine which order-5 squares in a file named "squares.txt" are actually Latin squares, print the squares in human- readable form, and print the job report summary use: $ ./lspc -f squares.txt -n 5 -j -r ************************************************************************ *** HISTORY / REFERENCE ************************************************ ************************************************************************ The Latin Square Toolbox was built for the M.S. Mathematics graduate thesis: [0] Schmidt, Nathan O., "Latin Squares and Their Applications to Cryptography" (2016). Boise State University Theses and Dissertations. 1223. http://scholarworks.boisestate.edu/td/1223 Nathan's thesis adviser was Dr. Liljana Babinkostova at the Department of Mathematics at Boise State University in Boise, Idaho, USA. In the beginning of the fall semester of 2015, Dr. Babinkostova discussed some of her new, cutting-edge research with Nathan, which involved applying Latin squares to cryptography. Nathan was interested in the idea and decided to pursue it as his thesis topic. This topic involved a thorough mathematical and computational investigation of Latin squares and their transversals for intended cryptographic application. To summarize, the primary objectives of the thesis were to: 0) Efficiently generate Latin squares. 1) Efficiently count Latin square transversals. 2) Predict which Latin squares have maximum (and minimum) transversal counts. 3) Apply the above results to build a new cryptographic system. Thereafter, Nathan began to learn about Latin squares and cryptography under the guidance of Dr. Babinkostova. In October of 2015, Nathan began to work on an abstract algebra project involving preliminary research on finite fields and Latin squares with fellow graduate students Will Unger, Sam Dworetzky, and Zeke Mihelcic. Nathan and Will began developing some preliminary software algorithms for generating Latin squares and counting their transversals. In December of 2015, the team presented the "Square Bandits" project's preliminary mathematical and computational Latin square results at the BoiseCrypt 2015 cryptography conference. Nathan needed to generate lots of Latin square data in order help direct the thesis research. In the spring semester of 2016, Nathan, along with his friend Will who volunteered to help with the research, continued to develop and upgrade their software algorithms for generating and analyzing Latin squares and transversals; they created, analyzed, and benchmarked numerous versions of the various implementations to achieve this data that would serve as evidence for supporting arguments and making decisions. This joint research operation primarily consisted of eating pizza, drinking coffee, programming computers, and solving math problems. They continued to search for Latin square features that might predict maximum transversal counts. This collaboration led to the construction of their new "lifting-and-merging" algorithm that uses prime order-p cyclic Latin squares (with maximum transversal counts) as "building blocks" to build larger prime power order-p^d Latin squares with a self-similar structure; this is the algorithm used in the SS mode of the LSG tool (termed the "SS-LS-GA" in [0]). Nathan and Will conjectured that these self-similar order-p^d Latin squares may have maximum transversal counts because the underlying, appropriately arranged prime order-p cyclic Latin square have confirmed maximum transversal counts for 2 <= p <= 9. Note: the order-2 Latin square both have transversal counts of zero, so the minimum and maximum counts are zero, but for 2^d with d > 1 the minimum no longer seems to apply! They generated several self-similar Latin squares and compared those transversal counts for 3 <= p^d <= 9 with the known confirmed maximum transversal counts in the literature (see the references cited in [0]) and discovered that their prediction was correct! The self-similar prime power order-p^d Latin squares have confirmed maximum transversal counts for 3 <= p^d <= 9. This ultimately led to Conjecture 2.100 of [0]. Upon further investigation, they realized that these self-similar Latin squares for prime power order-p^d were a generalization of a recent algorithm for generating order-2^d "super-symmetric" Latin squares created by a separate team (see reference [60] in [0]). Thus, Nathan and Will realized that the their order-p^d Latin squares were also "super-symmetric". Now while they had been viewing finite fields through an algebraic lense, they hadn't yet realized that one can apparently view finite fields geometrically! They had constructed the lifting-and-merging algorithm of the LSG's SS mode by viewing the Latin squares as geometric objects, but there was still some missing connection. Then, on one shocking Saturday, they realized that the addition Cayley tables of prime power order-p^d finite fields are actually prime power order-p^d super-symmetric Latin squares with a self-similar geometric construction! Therefore, Nathan used super-symmetric Latin squares to construct a new generalized and simplified version of the version of Grøstl hash function (an SHA-3 candidate), which operates over prime power order-p^d finite fields given some prime p and some d > 1. And this is the story of the Latin Square Toolbox. ************************************************************************ *** CREDIT / ACKNOWLEDGEMENTS ****************************************** ************************************************************************ Nathan wishes to thank: His adviser Dr. Liljana Babinkostova for her invaluable knowledge, insight, and guidance on this great subject. Will Unger for helping design and implement this Latin Square Toolbox, which ultimately led to Conjecture 2.100 of [0]. Dr. Samuel Coskey, Dr. Marion Scheepers, and Dr. Jyh-Haw Yeh for their helpful comments that improved the thesis. Sam Dworetzky for his collaboration during the "Square Bandits" project. Dr. Ian Wanless for answering his questions on Latin square transversals. His wife Marissa, for everything ************************************************************************ *** LICENSE ************************************************************ ************************************************************************ Copyright (C) 2017 Nathan O. Schmidt <[email protected]> Copyright (C) 2017 Will Unger <[email protected]> ************************************************************************ Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. ************************************************************************
About
Latin Squares and Their Applications to Cryptography by N. O. Schmidt
Topics
Resources
License
Stars
Watchers
Forks
Releases
No releases published
Packages 0
No packages published