CS Paper Radar

Cryptanalysis of operad-based cryptography

Ambrogio Maria Bernardelli

cs.CR ·submitted 2026-11-06 19:01 UTC · v1

Abstract

Commutative operads have been proposed as a platform for public-key cryptography, with protocols for key agreement, key exchange, encryption and authentication, together with a masking technique and families of algebras with secret parameters intended to strengthen them. We show that breaking key agreement, key exchange and encryption reduces to two problems over the centralizer of the public operations: an interpolation problem for key agreement and a division problem for the other two. Neither problem requires recovering a secret, and the set from which secrets are drawn plays no role in these attacks. For the operad platforms in the two original papers (fields, the integers, residue rings, the tropical semiring with finite entries, convexors and the masked tropical algebras), the relevant problems can be solved in polynomial time in the input models specified here, and masking does not affect these attacks. The authentication protocol fails for a more elementary reason: as originally stated it does not bind the prover to any public key, and even with a registered public key the response expected by the verifier can be computed from public data. In the masked variant, verification requires the secret mask; on the concrete string platforms, one observed session with an invertible challenge entry suffices for forgery. We also observe that one of the auxiliary constructions satisfies the algebra axioms only in a degenerate case, although the corresponding protocol remains correct. The attacks are implemented and verified on random instances of representative platforms.

Closest papers

Nearest neighbours by meaning across the whole index.

zk-DEAP: A Zero-Knowledge Decentralized Encrypted Aggregation Protocol

cs.CR ·2026-11-04 ·Jude Ramanan, Georgiana Haldeman, Noah Apthorpe
similarity 0.61
Abstract · 19 pages, 5 figures, 5 tables

Secure aggregation in domains such as federated learning, Internet of Things, and voting requires operating on private inputs while preserving confidentiality, verifying that each input satisfies constraints, and avoiding trusted parties. Existing protocols achieve at most two of these requirements. We present zk-DEAP, a protocol combining lifted ElGamal homomorphic encryption, FROST threshold cryptography, and zero-knowledge proofs (Bulletproofs, zk-SNARKs, or zk-STARKs) for fully decentralized, verifiable, privacy-preserving aggregation. Our core technical contribution is a cryptographic binding mechanism preventing substitution attacks, where a valid proof for one input is paired with a ciphertext encrypting a different, malicious value. For Bulletproofs, we bind via ciphertext-derived randomness modification. For zk-SNARKs/zk-STARKs, to bind across algebraic structures (a well-known challenge in practical cryptography), we introduce a novel blinded arithmetic hash commitment with an embedded Schnorr constraint. These binding techniques force the ZKP's private witness to equal the encrypted value, ensuring any circuit-verified constraint applies to the ciphertext. We implement three production-ready, defense-in-depth variants in Rust and evaluate across 5-500 participants. Compared to unverified aggregation, zk-DEAP adds modest overhead while providing cryptographic guarantees against input manipulation that statistical defenses cannot match.

0.28

Critical sets of Latin squares based on autoparatopisms

cs.CR math.CO ·2026-09-18 ·Manuel González-Regadera, Raúl M. Falcón, María Dolores Frau
publishedunusual similarity 0.59
Abstract · 31 pages, 2 figures, 10 tables

In cryptography, critical sets of Latin squares have particularly been implemented to design secret sharing schemes. A main problem in these cryptographic protocols arises from absent holders of pieces of information that are common to different critical sets, because they become indispensable to recover the secret. This paper solves this problem by making use of the orbits of entries described by the autoparatopism group of the Latin square under consideration. To this end, we introduce the more general problem of computing critical sets of Latin squares having a given paratopism in their autoparatopism group. These critical sets depend only on the conjugacy class of the autoparatopism and the main class of the Latin square under consideration. Based on this fact, as an illustrative example, we determine the smallest and largest sizes of critical sets associated with autoparatopisms of Latin squares of order up to six. We implement this approach in the design of a new secret sharing scheme.

0.45

A Broadcast Authenticated Encryption with Keyword Search in the Standard Model: Tightly Secure in Multi-User, Multi-Challenge Settings

cs.CR ·2026-08-29 ·Sayantan Mukherjee
theory similarity 0.58
Abstract

However, no known work considered the functionality requirement in its most realistic setting. We propose a new security definition of BAEKS in the multi-user (with adaptive corruptions) and multi-challenge (both in terms of ciphertext and trapdoor in an interleaved manner) settings. We also study the question of the unforgeability of BAEKS. In fact, our strong hiding requirement already implies a significant amount of unforgeability. We then propose a new BAEKS construction in the bilinear pairing groups. We prove this scheme achieves adaptive tight full-hiding security under (almost) standard MDDH assumptions. Restricting our BAEKS construction for a single receiver also gives an efficient and tightly secure PAEKS construction. We further run experiments to implement and evaluate our scheme.

0.22

AI Grinding for Fun and Cryptanalysis

cs.CR ·2026-08-22 ·Lukasz Olejnik, Bartosz Naskrecki
similarity 0.56
Abstract

We present an autonomous cryptanalysis workflow in which agents generate, test, and refine hypotheses before human review. The autonomous stage returns reproducible candidates with exact witnesses, controls, code, and run records. A researcher then decides whether the evidence establishes a break, defect, or coverage gap. Two failure modes recur. First, a public algebraic map or input representation erases or exposes a relation that a construction must hide. Examples include multiplication by zero, boundary coefficients of a polynomial product, quotients, characters, Schur squares, and variable-length byte encodings without boundaries. Second, a simulator, error law, or parameter certification uses a distribution different from the one claimed. Several targets fail in both ways. Every result has an exact witness and a discriminating control; every stated boundary has a proof. Three further targets yielded no attack but support narrower guarantees than a generic reading suggests. Eight published constructions fail at stated parameters or claims. A Ring-LWR commitment opens to every message with probability one. One ciphertext reveals two middle-product encryption rows. A lattice e-voting protocol loses receipt-freeness. A permutation-recovery attack against updatable encryption extends by linear algebra to the old decryption key. An explicit normal basis splits a degree-63 instance into seven degree-nine instances. A signature hash outside the lattice setting maps two printable equal-length messages to the same digest. A rerandomisable scheme's accept bit is a threshold oracle on its decryption noise. Separately, a group-ring decision claim and a multivariate MinRank hardening fail at the assumption or accounting level rather than as complete construction breaks. Each failure occurs one level above its supporting assumption.

0.28

Cryptanalysis of a Class of Ideal Secret Sharing Schemes Based on the CRT for Polynomial Rings

cs.CR cs.IT ·2026-10-05 ·Jian Ding, Zhiyuan Guo, Hongju Li, Yuying Man
similarity 0.55
Abstract

Based on the CRT for polynomial rings, Yang, Zhu, Fu and Xia (ISIT 2026) proposed a compartmented secret sharing scheme for the compartmented access structure with lower bounds, claiming it can be ideal. We exhibit three families of unauthorized subsets that reconstruct the secret. The scheme is therefore insecure, except for a degenerate choice of parameters in which the only authorized subset is the whole participant set. The flaw in the security analysis is that it does not take all published polynomials into account. Similar flaws appear in the same first author's hierarchical schemes (ISIT 2024, 2026).

0.29

Tensor--Action Ko--Lee Cryptography: A Framework and Structural Cryptanalysis of Commuting Subgroup Constructions

cs.CR ·2026-08-15 ·Ziyan Chen, Yuqiao Wang
similarity 0.54
Abstract · 28 pages, 3 images, 1 table

Tensor isomorphism has been studied as an algebraic problem relevant to post-quantum cryptography, while its use in public-key encryption remains open. In this paper, we formulate a Ko--Lee-style framework for public-key encryption from cubic tensor actions and prove its formal correctness. We then show that the framework is generically insecure when the commuting matrix subgroups are given by public finite generating sets. Viewing a cubic tensor as a vector in a $d^3$-dimensional space, a linear decomposition attack recovers the shared tensor from the public transcript in polynomial time without recovering either secret action. We also cryptanalyze three natural commuting-subgroup constructions---field-extension, block-diagonal, and tensor-product constructions---and give toy-scale experiments illustrating their specific structural leakage. Finally, we examine the lower-dimensional leakage caused by scaled-block structure. The contribution is therefore a framework proposal together with its cryptanalysis; it does not provide a secure public-key encryption scheme.

0.10

MCSI: A Masked Commutative Supersingular Isogeny Key Exchange with Blinded Ephemeral Keys

cs.CR math.NT ·2026-08-23 ·Furkan Cifci, Osman Emre Donder, Reyyan Cifci
theorycode/data similarity 0.54
Abstract · 38 pages, 6 figures, 6 tables. Reference implementation included as ancillary files and at https://github.com/FurkanCifci/mcsi-key-exchange

We introduce MCSI, a two message key exchange we design over the CSIDH class group action, in which each party sends its ephemeral public element under an authenticated encryption keyed by the value the two static keys determine. The design gives implicit mutual authentication, hides the ephemeral element from an eavesdropper, and lets a recipient discard an unauthenticated message after one tag check rather than after an evaluation of the group action, which is four orders of magnitude more expensive. On the analytic side, we prove that our protocol is correct with zero error, and prove three statements in the random oracle model, all reducing to the strong parallelisation problem: indistinguishability of the session key against a passive adversary, confidentiality of the blinded ephemeral element, and integrity of the blinded transport. None uses the decisional group action assumption, which is false for class group actions of non-prime discriminant. We also show that a blinding key cannot come from the session secret it is meant to establish. To instantiate the design we select parameters and show that a prime chosen for elliptic curve discrete logarithms is unusable: for $p = 2^{521}-1$, the NIST P-521 prime, the action admits no efficiently evaluable generator. On the practical side, we build and test the design. We implement the protocol twice, in C and independently in Python, cross check the two, and measure what a session costs in field operations, time and memory. We also audit our code for secret dependent control flow: the field arithmetic and the symmetric layer show none, while the group action leaks the key by construction, and two hundred timings separate two keys whose one-norms differ by five out of 370. Finally, we state what we do not prove, among them security under ephemeral key reveal, forward secrecy of the blinding, and constant time execution.

0.42

How to break the Miranda signature scheme over matrix Gabidulin codes

cs.CR ·2026-09-25 ·Adrien Vinçotte
similarity 0.54
Abstract · 21 pages, 3 tables, 2 algorithms

The Miranda signature scheme relies on masking a matrix code which disposes of a masked underlying structure, and the knowledge of which allows for efficient error decoding. We consider a Gabidulin code which is expanded into a matrix code, that is only \Fq-linear. An additional masking is then applied to it. The attack proposed here shares similarities with that of [Le26, https://arxiv.org/abs/2608.03328] on the EGMC encryption scheme, which also follows the paradigm described above. It consists in recovering the Fqm-linear structure of a masked matrix Gabidulin code by reducing to a MinRank instance to be solved over the extension field Fqm, but where the matrices have coefficients in Fq. Such an instance can be efficiently solved. However, unlike the previous attack, it is possible to reduce in polynomial time to such a MinRank instance in the case of the Miranda signature scheme. This results in a particularly efficient key recovery attack against the parameters proposed for Miranda. For example, for the proposed parameter set with m=79, the complexity drops from 146 bits to 46 bits in this attack.

0.31