Paper 2025/1589

A Symmetric Group-Based Public-Key Cryptosystem with Secret Partition-Dependent Decryption

Abstract

We present a purely theoretical public-key cryptosystem based on the symmetric group \( \Sym_n \) and a one-way function derived from conjugacy class sizes. The secret key is a carefully chosen partition \(\lambda \vdash n\), and the public key is \(f(\lambda) = |C_\lambda| \cdot m_1(\lambda)\). Decryption inherently requires knowledge of \(\lambda\) to compute \(\phi(f(\lambda))\) or equivalently to factor \(f(\lambda)\). The system combines combinatorial inversion hardness and integer factorization difficulty, ensuring that only someone who knows \(\lambda\) can decrypt. Historical context, worked examples, and theoretical security analysis are included.

Note: The previous version, titled "Symmetric Group-Based Public-Key Cryptosystem with Large Prime Moduli," contained some errors in encryption and decryption. We have revised it to present a theoretically correct version.