# Are there any (asymmetric) cryptographic primitives not relying on arithmetic over prime fields and/or finite fields?

Trying to figure out if any (asymmetric) cryptographic primitives exists, which do not rely on arithmetic over a prime field and/or arithmetic over a finite field, some people might get lost in research. Therefore, here’s the related question (inspired by this comment):

Does any asymmetric cryptographic primitive exist, that doesn’t rely on arithmetic over prime fields and/or finite fields?

• If, which one(s) would that be?
• If not, it would be nice if you would also explain why not?

Braid cryptography? Knapsack cryptosystems, like Nasako–Murikami?

Lattice-based cryptography tends to work in polynomial rings or modules with coefficients in finite fields, but whose higher-level structure is not a field.

Also: don't forget RSA! RSA works in a ring, not a field.

Cryptography over quasi-fields (which are not field, but where non-invertible elements are hard to find) is very common. This includes many cryptosystems such as RSA, but also Rabin, Goldwasser-Micali, Benaloh, Okamoto-Uchiyama, Naccache-Stern, Paillier, Damgard-Jurik, BCP, and many other related cryptosystems. This also includes all works based on composite-order elliptic curves, such as the BGN cryptosystem.

These quasi-fields, that we usually call RSA groups, have nice properties that are not easily found in prime order field. This allows for the construction of cryptosystems with very cool properties: Cock's cryptosystem is a simple identity-based encryption scheme, BCP (mentioned above) has a double trapdoor mechanism (many public key / private key pairs can be generated, and a global master secret key can decrypt them all), Paillier is additively homomorphic, with efficient decryption, etc.

Composite-order rings also have the advantage of containing groups of unknown order. For example, the subgroup of squares over an RSA group of order $n = pq$ has order $\varphi(n)/4 = (p-1)(q-1)/4$, which is unknown as knowing it is equivalent to knowing the factorisation. This allows for example to build constant size range proofs (zero-knowledge arguments for membership to an interval).

The phi-hiding assumption over composite order groups also gives rise to cryptographic schemes with efficiency properties that are very hard to obtain otherwise, such as private information retrieval schemes.

In elliptic curve cryptography, it is now very common to first design schemes over composite-order elliptic curves, which are far easier to manipulate because they contain "hidden subgroups" in which all secret informations are placed (these groups can only be "accessed" given the factorization), before trying to reproduce these results on prime order groups - and for several constructions, we still don't know if using prime order groups is possible.

• Now I'm wondering to what extent the quasi-field property can be said to be essential for RSA. On one hand, RSA encryption and decryption still work just fine even for the non-invertible ring elements. On the other hand, if you find a non-invertible element (other than zero), then you've found a factor of the modulus... – Ilmari Karonen Dec 27 '17 at 21:37
• I tend to see these "quasi-fields" as essential for cryptography, as you can see them as "fields with a trapdoor": roughly, for every party that knows only the public information, they are fields, but for the owner of the secret trapdoor, they are not and non-invertible elements can be found easily. This asymmetry is at the heart of public-key cryptosystems that use these rings and seems to me like a very natural crypto tool. This gives RSA groups many features you do not find in prime order fields. – Geoffroy Couteau Dec 28 '17 at 7:56
• To develop a bit on your question, I added some details on the properties of RSA groups that make them so nice in crypto (I gave a short sample of some core properties). Sure, you can design cryptosystem without quasi-fields, but RSA groups are really powerful for advanced cryptographic applications. Their main issue is that they rely on factorization, for which we have a subexponential algorithm, hence they require large parameters, so when one can obtain a similar scheme on a prime order field, it will usually be more efficient. – Geoffroy Couteau Dec 28 '17 at 8:22
• Your first three words surprised me, as there is an algebraic structure with the name quasifield, but I haven't seen any application of it (outside math). Maybe you could use the name "almost field" instead. – j.p. Dec 28 '17 at 17:02
• Yeah, to be honest, I wasn't sure of this word either: I directly translated a french word that I had seen several times (quasicorps), but I had never seen it in english. I like the fact that it carries the intuition that this is not a field, but it's hard to "distiguish it" from a field. Almost field is perhaps a better word, I dunno if there is a standard technical term in english to refer to such structures – Geoffroy Couteau Dec 28 '17 at 17:35

Hash-based signatures also seem to fit the bill and have not yet been mentioned. E.g. Merkle signatures and their variants.

(For it to qualify the hash function used cannot be based on prime fields or finite fields.)

There is a public key cryptosystem mentioned oh so briefly in Fully Homomorphic Encryption Over The Integers, built from a secret key cryptosystem.

It operates by distributing encryptions of 0 as a public key, which can be used to create a randomized encryption of 0 that can then have the message added to it.

The cipher operates over integers, but does still utilize modular reduction in the algorithm.

Merkle's Puzzles are often considered to be the first example of public-key cryptography.

Bob generates a large number of independent puzzles and sends them all, in random order, to Alice. Alice chooses one at random and solves the puzzle. The solution to each puzzle reveals a (unique) session key and identifier. Alice sends the identifier (in cleartext) with her encrypted message (Symmetric-key encrypted using the session key corresponding to that identifier) back to Bob.

The difficulty level of each puzzle and the number of puzzles sent are specifically selected to be large enough to make it infeasible for any eavesdropper Eve to learn the plaintext contents of Alice's message.

If we select the right sort of puzzle and the right sort of symmetric-key encryption, none of this depends on arithmetic over prime fields and/or arithmetic over finite fields.