Abstract We propose BRCE (Braid-Ring Convolutional Encryption), a novel quantum-resilient group ring-based encryption scheme built over the non-abelian structure of braid groups and their integral group rings. The encryption mechanism applies convolution-based masking with randomized braid elements to achieve semantic obfuscation without relying on periodic structures. Our design embeds high-entropy messages into non-commutative algebraic carriers , resulting in ciphertexts that resist both classical and quantum algebraic attacks. We provide a provable security reduction from the Conjugacy Search Problem (CSP) in braid groups and show that the scheme satisfies IND-CPA and IND-CCA security notions under reasonable pseudorandomness assumptions. We anchor security in a new hardness assump-tion—the Group Ring Convolution Inversion Problem (GRCIP)—tailored to non-abelian group rings. Further, we demonstrate that the structure resists reductions to the Hidden Subgroup Problem (HSP), positioning BRCE as a competitive post-quantum candidate rooted in topological and algebraic hardness. MSC 2020: 94A60, 20F36, 68Q12, 11T71
Abstract We propose BRCE (Braid-Ring Convolutional Encryption), a novel quantum-resilient group ring-based encryption scheme built over the non-abelian structure of braid groups and their integral group rings. The encryption mechanism applies convolution-based masking with randomized braid elements to achieve semantic obfuscation without relying on periodic structures. Our design embeds high-entropy messages into non-commutative algebraic carriers , resulting in ciphertexts that resist both classical and quantum algebraic attacks. We provide a provable security reduction from the Conjugacy Search Problem (CSP) in braid groups and show that the scheme satisfies IND-CPA and IND-CCA security notions under reasonable pseudorandomness assumptions. We anchor security in a new hardness assump-tion—the Group Ring Convolution Inversion Problem (GRCIP)—tailored to non-abelian group rings. Further, we demonstrate that the structure resists reductions to the Hidden Subgroup Problem (HSP), positioning BRCE as a competitive post-quantum candidate rooted in topological and algebraic hardness. MSC 2020: 94A60, 20F36, 68Q12, 11T71
Abstract. We propose new cryptosystems based on self-distributive systems that are defined by conjugator searching problems (CSP) in noncommutative groups. Under certain assumptions, the ciphertexts of our basic construction are proven indistinguishable against chosen plaintext attacks (IND-CPA) in the standard model, and two extended schemes achieve the IND-CCA security in the random oracle model. Then, our proposal is instantiated with braid groups, and leads to a new braid-based encryption scheme that is directly based on the intractability assumption of CSP in braid groups. Furthermore, we quote an analysis to manifest that our newly derived braid-based cryptosystem has the potential to resist currently known quantum attacks. Keywords: Self-distributive systems, conjugator searching problem, braid groups, resistance to quantum attacks 1
The rapid development of quantum computing brings great challenges to public key cryptosystems.The braid group,which is non-commutative,provides a new platform of constructing cryptographic protocols.A convertible authenticated encryption scheme over braid group is proposed on the difficulty of conjugacy search problem and multiple conjugacy problem,in which only the designated receiver can recover and authenticate the message,when the sender repudiates the signature,the receiver can prove the dishonesty of the sender by converting the signature to an ordinary one without the cooperating of the sender.As for the resistance against quantum attacks,the proposed scheme has advantage over the schemes based on commutative algebraic structures.
Post-quantum cryptography (PQC) aims to develop cryptographic protocols resistant to attacks by quantum computers, which threaten classical schemes based on integer factorization and discrete logarithm problems. Among various approaches, lattice-based cryptography has emerged as one of the most promising candidates for PQC. Within this domain, ring theory plays a foundational role by providing the algebraic structures—specifically polynomial rings modulo cyclotomic polynomials—used to define hard problems like Ring Learning With Errors (Ring-LWE). These problems underpin efficient and secure cryptographic primitives such as key exchange, encryption, digital signatures, and homomorphic encryption. This paper explores the theoretical background of ring theory relevant to PQC and discusses how it enables the construction of cryptosystems with strong security assumptions and practical efficiency. We also analyze specific schemes that utilize ring-based lattices, including New Hope, NTRUEncrypt, and Dilithium, highlighting the advantages of ring structures in reducing key sizes and improving computational speed. Furthermore, we review the implementation challenges and potential future directions for integrating ring theory into next-generation cryptographic protocols suitable for a post-quantum world.
The idea of computing on encrypted data without decryption dates back to the notion of privacy homomorphisms introduced by Rivest, Adleman, and Dertouzos (1978). Their proposals built using the elegant structure of Chinese Remainder Theorem (CRT), were later shown to be insecure under simple known-plaintext attacks. Subsequent CRT-based fully homomorphic encryption (FHE) over the integers addresses this algebraic transparency by injecting noise and basing security on approximate common divisor–type assumptions, but the resulting designs are burdened by large public keys and costly ciphertext refresh procedures. In this work, we develop a new CRT-based FHE scheme whose security relies on the Ring-LWE (RLWE) hardness assumption. For this purpose, we introduce the CRT-RLWE problem. We show that the problem is at least as hard as the RLWE, thereby positioning our construction within the established post-quantum security landscape of RLWE-based cryptography. Our scheme retains an explicit CRT embedding, separating a message component modulo a prime-power plaintext modulus and an auxiliary CRT component, while using RLWE-style key and ring arithmetic for compactness and efficiency. Finally, we make it fully homomorphic by using a new bootstrapping procedure, that adopts the recryption paradigm for BGV/BFV schemes utilizing the linear transformation and digit extraction techniques.
Several public-key schemes base their security on the belief that inverting a unit of a group ring is hard. A recent result showed that this belief is false on a quantum computer when the group is abelian. To restore security, designers moved to non-abelian groups, especially dihedral groups, believing that the hardness of the dihedral hidden subgroup problem (HSP) would protect the scheme. This paper shows that unit inversion is a different problem and does not require an HSP solver. Instead, it can be solved by a change of basis that splits the group ring into small matrix blocks. We prove that unit inversion is polynomial-time, classically and quantumly, when an efficient generalized Fourier transform exists, the group ring is semisimple, and the largest matrix block has polynomial size. Dihedral group rings satisfy these conditions because their irreducible representations have dimension at most 2 and an efficient Fourier transform exists. We give an explicit reversible quantum circuit for the block-inversion step and validate it in a register-level simulator. We also identify the exact structural boundary where the method stops and propose a candidate construction in the surviving regime under a new, clearly stated security assumption. The constructive results are supported by reproducible software artifacts and experiments.
Group homomorphic encryption represents one of the most important building blocks in modern cryptography. It forms the basis of widely-used, more sophisticated primitives, such as CCA2-secure encryption or secure multiparty computation. Unfortunately, recent advances in quantum computation show that many of the existing schemes completely break down once quantum computers reach maturity (mainly due to Shor's algorithm). This leads to the challenge of constructing quantum-resistant group homomorphic cryptosystems. In this work, we prove the general impossibility of (abelian) group homomorphic encryption in the presence of quantum adversaries, when assuming the IND-CPA security notion as the minimal security requirement. To this end, we prove a new result on the probability of sampling generating sets of finite (sub-)groups if sampling is done with respect to an arbitrary, unknown distribution. Finally, we provide a sufficient condition on homomorphic encryption schemes for our quantum attack to work and discuss its satisfiability in non-group homomorphic cases. The impact of our results on recent fully homomorphic encryption schemes poses itself as an open question.