Krittaphas Thanaphongphaisan*, Purich Lamsrichan*, Wasanont Pongsawat, Kanes Sumetpipat
Kamnoetvidya Science Academy
*Email: ,
Introduction
In the present day, a vast amount of communication takes place through online messaging platforms. This process has been developed and refined over a long period, making access to communication and information exchange both effortless and rapid. However, as communication technology advances, there are inevitably malicious individuals who seek to intercept and access transmitted messages. This has led to the emergence of a new field known as cryptography, which involves encryption systems that transform plaintext messages into encoded text.
Encryption systems such as Data Encryption Standard and Advanced Encryption Standard have been developed progressively. These systems draw on group theory, an extension of algebra, to provide insights into empty sets, operation, and pattern. Group theory is also employed in permutation, ring, and field.
Our cryptographic system is rooted in Amidakuji, which is a Japanese game for assigning jobs by lot. Players begin on top and swap lines on “direction-changer” bars, yielding diverse outputs. The game’s permutation guarantees distinct maps and no overlap. Group theory augments Amidakuji’s structure and cryptographic use.
Unlike other permutation-based cryptographic methods, which often rely on simple cyclic or transposition-based permutations, Amidakuji permutations exhibit structured randomness due to their dependency on interconnected paths. This structure makes it harder to predict outputs without knowing the exact Amidakuji configuration. Additionally, since the Amidakuji permutation involves layered swaps instead of direct positional changes, it resists conventional permutation-based attacks that exploit predictable cycles or fixed patterns.
Method
In general, messages transmitted during communication are composed of letters or numbers, which are not directly compatible with the Amidakuji game. Therefore, the data must first be converted into an Amidakuji structure before it can be used. The sender and receiver must then agree on a specific set of Amidakuji games, denoted as P, which will be used for encryption and decryption.
The first step involves transforming the text message into integer values using ASCII encoding. After converting the text, encryption cannot proceed without a key. In this system, the key consists of a specific set of Amidakuji structures known only to the two communicating parties, ensuring that an adversary cannot access it. The protocol used for key exchange was the Diffie-Hellman protocol, which is described as follows:
Let G represent an Amidakuji structure with k vertical lines, and let n be the order of G, defined as the smallest positive integer such that applying G n times results in the identity transformation. The two communicating parties are referred to as Alice and Bob, while an adversary attempting to intercept or manipulate the data is called Eve.
In the diagram below, Alice and Bob each have their own private keys, α and β, respectively, where 1 ≤ α, β ≤ n – 1. The middle column represents public information that was known to everyone, including Eve, while the left and right column contain private information known only to Alice and Bob, respectively.
Alice begins by applying the Amidakuji structure G to itself α times, resulting in G^α, which she then sends to Bob. After receiving G^β from Bob, she applies it α more times, obtaining (G^β)^α, which is defined as the Amidakuji structure P.
Similarly, Bob applies G to itself β times, resulting in G^β, which he then sends to Alice. After receiving G^α from Alice, he applies it β times, obtaining (G^α)^β, which is also defined as P.
Once Alice has obtained P, she applies it to the ASCII-encoded message, transforming it using P before sending the encrypted message to Bob.
The values of α, β, and n should not be chosen entirely at random, as certain combinations may lead to weak security. For instance, values like α = 2, β = 3, and n = 5 make it easy for an attacker to determine the key since P = G
To ensure security, n should be a large prime or a product of large primes, minimizing cycles that lead to predictable patterns. Additionally, α and β should be chosen such that their greatest common divisor (gcd) with n is 1, ensuring they fully utilize the structure of the Amidakuji group. Furthermore, α and β should be selected using a cryptographically secure random generator. to prevent bias that could be exploited in attacks.
In practice, each party may not know whether the other has satisfied the GCD condition. To address this, the system can be augmented to include a public verification step by requiring gcd (α, n) = 1 in the key generation algorithm.
Our encryption scheme is a stream cipher, where the Amidakuji permutation P = G^(αβ) is applied to the ASCII representation of the message. However, if the same key P is used to encrypt multiple messages, attackers may perform statistical analysis to deduce patterns and partially infer plaintext content. We emphasize that for strong security, each message must be encrypted with a newly negotiated key P, derived from fresh α and β.
Result
After the cryptosystem was created, we simulated encryption and cracking with different ladders, resulting in the graph below.
From the graph, the results show the order from 1-5*10^6, where cracking time grows linearly and the encryption has a value in some interval. Theoretically, if the order reaches 10^12, the cracking time will be 31 years, while the encryption time average is 0.03 seconds
Our cracking method was based on the assumption of brute-force attacks, where an adversary attempts to exhaust all possible values of P = G^x for x ∈ [1, n]. However, we acknowledge this estimate may not represent the most efficient possible attack. More advanced methods (meet-in-the-middle, algebraic solving, quantum algorithms) may reduce this time depending on the structure of the group and the attacker’s resources.
Comparison with other cryptography
We compared our cryptography with others: AES, 3DES, DES, RC6, Blowfish, and RC2. The graph shows the relationship between the encryption time and input size
Conclusion
We have developed and tested a cryptographic system based on the Amidakuji structure, modeled as a group. Results show that increasing the group order improves security while maintaining fast encryption, especially for large data sizes.
Our system performs competitively, ranking among the fastest for data sizes larger than 800 KB. However, as a stream cipher, it is vulnerable to key reuse, which must be avoided.
While our initial estimate suggested that a group order of 10^12 would yield a cracking time of approximately 31 years under brute-force attack assumptions, we acknowledge that this is a theoretical upper bound. The actual security depends on the attack model, and more efficient cryptanalytic techniques may exist.
This work demonstrates that Amidakuji-based encryption is promising for high-speed encryption of large data. Future improvements may involve refining key generation protocols, enforcing coprime selection constraints, or combining Amidakuji with other cryptographic primitives to enhance resilience against advanced attacks.
References
Ash, R. B. (2013). Basic abstract algebra: For graduate students and advanced undergraduates. Courier Corporation.
Di Salvo, P. (2021). Amidakuji: Gray code algorithms for listing ladder lotteries (Doctoral dissertation, University of Guelph). University of Guelph Institutional Repository.
Elbirt, A. J. (2009). Understanding and applying cryptography and data security. CRC Press.
Elminaam, D. S. A., Kader, H. M. A., & Hadhoud, M. M. (2008). Performance evaluation of symmetric encryption algorithms. International Journal of Computer Science and Network Security (IJCSNS), 8(12), 280–286.
