Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
