so the idea is that I really wanted a simple way to compute the max function with homomorphic encryption. I have some alternatives by using MPC/secret-sharing (or even FHE) by approximating the sign function with polynomials. That's good and all but the tropical idea is way cuter. Not to mention, if we had an encryption function which was a tropical semifield homomorphism, that would be a new FHE setting that could do ReLu cheaply, so it could find uses for private AI even. there's one paper[^1] that started this whole tropical cryptography thing, got 88 citations — a lot of which are cryptanalysis[^4] with successful attacks — and two sequels[^2][^3]. it started because one of the authors (Shpilrain) found an attack[^6] on Stickel's key exchange protocol — which is a generalization of DH to non-abelian groups — using linear algebra methods, and thought that by using tropical algebra he could avoid it, since most tropical matrices are not invertible and solving tropical linear systems and a lot of related problems are in NP. two methods are proposed in the original paper: 1. a very direct analogue of Stickel's scheme; and 2. a method based on birational automorphisms I'm mostly interested in the second one, because it can lend itself very naturally to a homomorphic variant (as per Remark 2 in the paper[^1]) as I've mentioned the first scheme got repeatedly refuted during the last decade, but I could find no attack directly to the second one. Maybe it's supposed to be obvious, since the attacks rely on patterns on the tropical powers, but still, it's curious that this other formulation gathered little attention the second paper[^2], based on semidirect products (which you would probably enjoy as well, since it has some cute math, but I won't focus on it much), was also attacked. there's also a third paper[^3], and while it did get two different attacks[^5][^8] still in preprint phase, they got patched and since then, it didn't get broken again, as far as I can tell there are also other interesting attempts in the literature, ranging from using min/max-times rings to circulant matrices etc, that may be of interest with that (lengthy, sorry) introduction out of the way, what I'm trying to figure out: 1. is the birational automorphism scheme on the first paper also refuted by the same attacks on the Stickel-like scheme? 2. can we study the covering attacks on the Stickel-like scheme, and maybe tweak parameters a bit, so that the valid systems yield coverings more difficult to compute (since it's worst-case NP, but in practice easy to brute-force) 3. there's that independent mathematical question on the first paper, about triangular and monomial automorphisms being generators for all tropical quotient semifield automorphisms 4. the scheme on the appendix of the third paper seems unrefuted as of now. is it really safe? can we turn it into a partial homomorphic one? also note: for my practical purposes I don’t really care about decryption cost, and I have a certain peculiar requirement that would make a cyphertext preserving homormophic scheme more useful than one like tFHE that has noise added to it. I understand that it's an undesirable property in most settings, but for the MPC protocol I'm designing it would be preferable ## references [^1]: [[tropical crypto I.pdf]] [^2]: [[tropical crypto II.pdf]] [^3]: [[tropical crypto III.pdf]] [^4]: [[analysis tropical crypto I.pdf]] [^5]: [[+forging tropical signatures.pdf]] [^6]: [[stickel attack.pdf]] [^8]: https://eprint.iacr.org/2023/1748 (there's a version of this that was published in a journal but I don't think there were any substantial changes)