Home
The Latin Square Toolbox contains software tools for efficiently generating Latin squares and counting their transversals with various user-configurable options. It was built by Nathan Schmidt and Will Unger for the research thesis:
This open source release aims to help educate folks on Latin squares and their important applications to cryptography. This version contains three tools:
- Latin Square Generator (LSG)
- Latin Square Transversal Counter (LSTC)
- Latin Square Property Checker (LSPC)
For a description summary of each tool, we invite the reader to see the Summary section of the README.
Important 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 OS X and Windows.
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).
Example 0: The Cayley table of the group of integers with addition modulo 5 is a prime order-5 cyclic Latin square; see image below.
Example 1: The LSG can generate the prime order-5 cyclic Latin square that encodes the Cayley table of the group of integers with addition modulo 5 and print it in both ordered-triple form and human-readable form; see image below.
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.
Table 0: Today the number of Latin squares is known up to order-11 and is given by the OEIS Sequence A002860; see table below.
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 these 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).
Example 2: The LSG generates and prints a prime power order-32 super-symmetric Latin square that encodes the order-32 finite field; see image below.
Example 3: The LSG SS mode's recursive lifting-and-merging algorithm applies self-similarity to generate a prime power order-pd super-symmetric Latin square. Here, prime order-3 cyclic Latin squares are used as "building blocks" to construct larger prime power order-32 and order-33 super-symmetric Latin squares that are self-similar; see images below.
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.
Example 4: This prime order-5 cyclic Latin square encodes the group of integers with addition modulo 5 and the 5 entries for one of its transversals is marked in green parentheses; see image below. Can the reader find any of the other transersals?
Example 5: The LSG generates an order-5 Latin square and counts the number of its transversals to obtain 15, which turns out to be the maximum transversal count for any order-5 Latin square. In this case, the LSG also explicitly lists the 15 transversals in ordered-triple form; see image below.
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!
In the thesis, we conjecture that prime order-p cyclic Latin squares and prime power order-pd super-symmetric Latin squares (i.e. generated by the LSG SS mode's recursive, self-similar lifting-and-merging algorithm) may have maximum transversal counts. We confirmed that our prediction is correct for 3 ≤ pd ≤ 9. Is it possible to prove or disprove this conjecture for 9 < pd?
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.
Step 0: Install the Java Runtime Environment (JRE) and the Java Development Kit (JDK).
Step 1: Install Apache Maven (to handle the dependencies).
Step 2: Download the Latin Square Toolbox from either SourceForge or GitHub.
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.
- For Linux execute: $ ./linux_build.sh
- For Mac OS X execute: not yet implemented
- For Windows execute: not yet implemented
Uninstall Step: To clean/remove the Latin Square Toolbox's compiled jars, Javadocs, and scripts, execute the clean script for your operating system via the command-line interface.
- For Linux execute: $ ./linux_clean.sh
- For Mac OS X execute: not yet implemented
- For Windows execute: not yet implemented
In order to generate Latin squares, the general usage for the LSG is:
LSG Usage Example 0: To generate a data set with all order-5 Latin squares execute:
$ ./lsg -m ds -n 5 -s 0
LSG Usage Example 1: To generate a data set with 1 order-5 Latin square execute:
$ ./lsg -m ds -n 5 -s 1
LSG Usage Example 2: To generate a data set with 60 order-5 Latin squares execute:
$ ./lsg -m ds -n 5 -s 60
LSG Usage Example 3: To generate a data set with 60 order-5 Latin squares via preloading execute:
$ ./lsg -m dsp -n 5 -s 60
LSG Usage Example 4: To generate a single prime order-5 cyclic Latin square execute:
$ ./lsg -m ss -p 5 -d 1
LSG Usage Example 5: To generate a single prime power order-32 super-symmetric Latin square execute:
$ ./lsg -m ss -p 3 -d 2
LSG Usage Example 6: To generate a single prime power order-32 super-symmetric Latin square and count its transversals execute:
$ ./lsg -m ss -p 3 -d 2 -t
LSG Usage Example 7: To generate a single prime power order-32 super-symmetric Latin square, count its transversals, and print its transversal list execute:
$ ./lsg -m ss -p 3 -d 2 -T
LSG Usage Example 8: To generate a data set with 60 order-5 Latin squares and count the transversals for each execute:
$ ./lsg -m ds -n 5 -s 60 -t
LSG Usage 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 execute:
$ ./lsg -m ds -n 5 -s 60 -T
LSG Usage 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 execute:
$ ./lsg -m ds -n 5 -s 60 -T -j
LSG Usage 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 execute:
$ ./lsg -m ds -n 5 -s 60 -T -j -r
LSG Usage 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 execute:
$ ./lsg -m ds -n 5 -s 60 -T -j -h
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:
Note: 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 are stored in an input file (with an ordered-triple format) containing the default redirected output of the LSG.
LSTC Usage Example 0: To generate a data set with all order-5 Latin squares with LSG and then count their transversals with LSTC execute:
$ ./lsg -m ds -n 5 -s 0 > output.txt
$ ./lstc -f output.txt -n 5
LSTC Usage 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 execute:
$ ./lsg -m ds -n 5 -s 0 > output.txt
$ ./lstc -f output.txt -n 5 -T
LSTC Usage 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) execute:
$ ./lsg -m ds -n 5 -s 0 > output.txt
$ ./lstc -f output.txt -n 5 -T -r
LSTC Usage 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 execute:
$ ./lsg -m ds -n 5 -s 0 > output.txt
$ ./lstc -f output.txt -n 5 -j
LSTC Usage 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 execute:
$ ./lsg -m ds -n 5 -s 0 > output.txt
$ ./lstc -f output.txt -n 5 -j -h
LSTC Usage 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 execute:
$ ./lsg -m ds -n 5 -s 0 > output.txt
$ ./lstc -f output.txt -n 5 -j -q
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 Usage Example 0: To determine which order-5 squares in a file named "squares.txt" are actually Latin squares execute:
$ ./lspc -f squares.txt -n 5
LSPC Usage Example 1: To determine which order-5 squares in a file named "squares.txt" are actually Latin squares and print the job report summary execute:
$ ./lspc -f squares.txt -n 5 -j
LSPC Usage 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 execute:
$ ./lspc -f squares.txt -n 5 -j -r
For more detailed information, we recommend that the reader see the Latin Square Toolbox's README and corresponding thesis.
© 2017 Nathan O. Schmidt <c0ldc4lcul4ti0n@gmail.com>
© 2017 Will Unger <zomborg1@gmail.com>
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.