The Rabin cryptosystem over number fields

arXiv:2506.09569 · cs.CR, math.NT · Submitted 2025-06-11 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: We're looking at the paper: "The Rabin cryptosystem over number fields".

Elias: Here's the gist of the paper. The paper extends Rabin’s cryptosystem to general number fields, showing that decryption is as hard as integer factorization when the modulus is chosen carefully The scheme generalizes Rabin’s cryptosystem to rings of integers in number fields Generalization of the Scheme The scheme is performed in the quotient ring OK/n where n = pq, using two distinct non-zero prime ideals p and q in OK The public key is the modulus n and the private key is the pair (p, q) Encryption involves computing c = m squared in OK/n Decryption requires computing square roots of c modulo p and modulo q This involves a generalization of the Tonelli-Shanks algorithm for number rings Public Key Representation and Security The choice of the public key representation is crucial, as representing n as a list of generators or in Hermite normal form often allows factorization The best choices are prime ideals of the form p = (p), where p ∈ Z is prime and inert in K The security relies on the difficulty of computing the decomposition into prime ideals of n = pq If inertia degrees fp and fq are distinct, an efficient algorithm can factor n Square Root Computation Methods The paper provides several methods for computing square roots in OK/p and OK/q The explicit Chinese Remainder Theorem allows computing the inverse of the canonical isomorphism between OK/n and OK/p × OK/q A generalized Tonelli-Shanks algorithm is provided for number rings Furthermore, a fast square root extraction method exists when OK/p ≡ 3 (mod 4) Performance Analysis and Conclusions Encryption is described as being very fast in all cases, although running time increases with the degree of the number field Decryption is less efficient than for the classical Rabin scheme For a cubic number field example, decryption is relatively better than quadratic fields but still less efficient than classical Rabin The scheme is provably equivalent to the factorization problem of a large integer N if p and q are chosen carefully Choosing the Right Square Root To identify the original message among four possible square roots, one can use methods discussed in

4: applied to a single component of the message The requirement of taking inert primes p and q is helpful for identifying the correct square root by checking congruences modulo p and q If a coefficient is zero modulo both p and q, one should look at the next coefficient The paper concludes that semantic security requires random paddings because two extra-bits carry information about the degree zero term of the polynomial representing the message Key Generation Scenarios Key generation involves choosing a number field and then selecting inert primes p and q based on specific congruence conditions for quadratic, cyclotomic, or generic fields For the generic case, checking the irreducibility of g modulo p and q is time-consuming The construction of large primes p and q congruent to a specific value modulo D is used in these cases Security Limitations The scheme cannot be used for post quantum cryptography because an attacker with a quantum computer can factor the modulus via Shor’s algorithm Semantic security must be ensured by introducing random paddings, as the two extra-bits leak information about the degree zero term The scheme is provably equivalent to factoring N if p and q are chosen carefully The paper proposes a novel public-key cryptosystem extending Rabin’s scheme to general number fields Encryption performs very fast, but decryption is less efficient than for the classical Rabin scheme A more sophisticated variant for degree 3 number fields at least performs relatively better than the case of quadratic number fields The new scheme is provably equivalent to the factorisation problem of a large integer N if the prime ideals p and q dividing the modulus n are chosen carefully References

1: Y.

Nadia: Awad, A.

Elias: N.

Nadia: El-Kassar, and T.

Paper summary: Nadia: So we’re looking at this paper called The Rabin cryptosystem over number fields, and basically, they are taking Rabin's old idea and making it work for rings of integers in general number fields.

Elias: Right, so the main thesis here is that they show decryption in this new system is just as hard as integer factorization if you pick the modulus carefully. It extends Rabin's original scheme to these rings of integers.

Priya: So what does that mean for us? If we can find a way to decrypt this thing, it means we've found a way to factor the underlying number field structure, which is pretty big because it connects directly to the hard factorization problem.

Nadia: Exactly. They set up the scheme in some quotient ring called OK over n, where n is built from two distinct non-zero prime ideals p and q in that field. The public key is just this modulus n, and the private key is that pair of ideals p and q.

Elias: And the encryption part stays pretty standard: you take a message m in this ring and you compute c equals m squared. The decryption then requires finding the square roots of c modulo p and modulo q.

Priya: That's where it gets interesting for us, because they mention that this part involves a generalization of Tonelli-Shanks for number rings to handle those square root computations.

Nadia: Yeah, and they actually give some methods for computing those square roots in OK over p and OK over q. They mention using the explicit Chinese Remainder Theorem to compute the inverse of the isomorphism between the quotient ring OK over n and the product of quotients OK over p times OK over q.

Elias: And they also point out that there's a fast square root extraction method available when something called alpha, which is related to the size of OK over p, is congruent to three modulo four.

Priya: That sounds like a real performance gain for decryption, especially since they mention that for degree three number fields, decryption can be relatively better than in quadratic fields.

Nadia: It seems the authors are really focusing on making sure that when you choose the prime ideals p and q, you're not accidentally giving away information about the structure of n. They discuss how representing this modulus n is a subtle issue because doing it one way, like as a list of generators or in Hermite normal form, can let an attacker factor n.

Elias: So they conclude that the best choices for those prime ideals are rational primes p and q that are inert in the field K. This means they need conditions to make sure that a given rational prime actually stays prime inside the number field.

Priya: That condition about inertia degrees being distinct is important, because if fp and fq are not different, an efficient algorithm can factor n using that information. It’s like the structure of the field tells you something about how to break it down.

Nadia: And they do address how to find the original message after encryption. In the classical case, there was a method involving adding two extra bits to the ciphertext, specifically related to the parity and something called m raised to n modulo p and q.

Elias: The paper suggests that if you assume those prime ideals p and q are inert in K, then it’s still possible to uniquely identify the original message by adding those two extra bits.

Priya: That's a practical detail we need to consider for semantic security, because they say that if you don't add those random paddings, those two extra bits leak information about the degree zero term of the polynomial representing your message.

Nadia: So what’s the big picture here? This paper shows that Rabin’s method isn't just a toy for integer factorization; it scales up to general number fields, and if you pick p and q right, it remains secure against factorization attempts.

Elias: It also points out some limitations. They say encryption is fast, but decryption is generally less efficient than the classical Rabin scheme. Plus, they note that this scheme cannot be used for post quantum cryptography because a quantum computer with Shor's algorithm can factor the modulus pretty easily.

Priya: And they explicitly state that semantic security must be ensured by introducing random paddings because those two extra bits leak information about the message structure. That’s a clear requirement for any practical use of this system.

Nadia: So to sum up, this paper proposes a novel public-key cryptosystem extending Rabin's scheme to general number fields, showing that decryption is as hard as integer factorization when you choose the modulus carefully.

Elias: And they suggest that for degree three number fields, decryption can be relatively better than quadratic ones. The key thing is choosing those prime ideals p and q such that they are inert in the field K.

Priya: It’s a solid extension of Rabin’s work, but the performance trade-offs and the security requirements involving those paddings are definitely things we have to keep in mind when thinking about real deployment.

Conclusion: Nadia: So we’ve been looking at this paper, "The Rabin cryptosystem over number fields." Essentially, they’re taking Rabin's old encryption idea and applying it to rings of integers in general number fields.

Elias: Yeah. The core idea is that decryption in these new systems is just as hard as integer factorization if you pick the modulus correctly. It extends that original Rabin scheme to these specific algebraic structures.

Priya: So, what does that mean for us? If we can't factor the underlying number field structure, then we can't decrypt it easily either.

Nadia: Exactly. They set up this system in a quotient ring called OK over n, where n is built from two distinct prime ideals p and q in that field. The public key is just this modulus n, and the private key is that pair of ideals p and q.

Elias: And the encryption part stays pretty standard: you take a message m in this ring and you compute c equals m squared. Decryption then requires finding the square roots of c modulo p and modulo q.

Priya: That's where it gets interesting for us because they mention that this part involves a generalization of Tonelli-Shanks to handle those square root computations in number rings.

Nadia: Right, and they provide methods for computing those square roots in OK over p and OK over q. They even show you how to use the explicit Chinese Remainder Theorem to compute the inverse of the isomorphism between the quotient ring OK over n and the product of quotients OK over p times OK over q.

Elias: And there's a fast square root extraction method available when something called alpha, which is related to the size of OK over p, is congruent to three modulo four. That suggests potential speed gains for decryption on certain types of fields.

Priya: It sounds like they’re really pushing the performance aspect here because they note that for degree three number fields, decryption can be relatively better than in quadratic fields. But we gotta ask what kind of complexity that is really in practice.

Nadia: That's the trade-off. They also spend a lot of time on how to choose the public key representation because if you represent n as a list of generators or in Hermite normal form, it can actually let an attacker factor n.

Elias: So they conclude that the best choices are rational primes p and q that are inert in the field K. They have to make sure those rational primes actually stay prime inside the number field structure, which requires some specific congruence conditions.

Priya: That condition about inertia degrees being distinct is important too because if fp and fq aren't different, an efficient algorithm can factor n using that structural information. It’s like the field itself gives a hint to the attacker.

Nadia: And they do address how to find the original message among the four possible square roots of the ciphertext c equals m squared. They show that if you assume those prime ideals p and q are inert, you can uniquely identify the original message by adding two extra bits to the ciphertext.

Elias: So semantic security has a catch here. They say that if you don't add those random paddings, those two extra bits leak information about the degree zero term of the polynomial representing your message. You have to add them in for real security.

Priya: That makes sense from a data perspective. If those bits leak structural information, then we aren't actually hiding anything unless we pad it randomly to obscure that structure. It’s a necessary addition for practical use.

Nadia: Overall, the paper shows that Rabin’s method scales up to general number fields without losing its security if you pick the prime ideals p and q carefully. It proves it's fundamentally equivalent to the factorization problem of a large integer N under those right conditions.

Elias: And they do flag some limitations for us. First, this system cannot be used for post quantum cryptography because a quantum computer with Shor’s algorithm can factor that modulus pretty easily.

Priya: Exactly, so we’re looking at classical security only for now. Plus, encryption is fast, but decryption is still less efficient than the old classical Rabin scheme in some cases.

Nadia: That's the summary. The authors are proving the concept works across different number fields by focusing on how you choose those prime ideals p and q to maintain that factorization hardness. Next up, we’re going to look at what this means for real-world key generation scenarios and which fields they even tested.

cs.CR, math.NT

Submitted: 2025-06-11

Updated: 2026-11-09

Comments: 16 pages; several changes according to referee's report

Code: https://github.com/alecobbe/RabinNF

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 75/100

The gist: The paper extends Rabin’s cryptosystem to general number fields, showing that decryption is as hard as integer factorization when the modulus is chosen carefully The scheme generalizes Rabin’s…

Key concepts

Number Field
A number field K is an extension of the rational numbers Q, meaning every element in K can be expressed as a linear combination of powers of a single element (a primitive element) with rational coefficients. This structure allows for algebraic operations beyond simple integers.
Prime Ideal
In the context of a number field's ring of integers OK, prime ideals are the generalization of prime numbers. They are non-zero, non-unit elements that behave like prime factors in the ring, and choosing specific inert primes p and q is key to ensuring security.
Inert Prime Ideal
An inert prime ideal p in a number field K means that when the rational prime p is considered as an element of the ring of integers OK, it remains a prime element. This condition on the choice of n=pq ensures that factoring n into its component ideals corresponds to factoring the original integer N.
Square Root Computation
Decryption in this scheme requires finding square roots modulo p and modulo q. The paper provides generalized Tonelli-Shanks algorithms for these computations, which are necessary because the ring structure is more complex than simple integers.

Terminology

Summary

The paper extends Rabin’s cryptosystem to general number fields, showing that decryption is as hard as integer factorization when the modulus is chosen carefully The scheme generalizes Rabin’s cryptosystem to rings of integers in number fields

Generalization of the Scheme

The scheme is performed in the quotient ring OK/n where n = pq, using two distinct non-zero prime ideals p and q in OK The public key is the modulus n and the private key is the pair (p, q) Encryption involves computing c = m squared in OK/n Decryption requires computing square roots of c modulo p and modulo q This involves a generalization of the Tonelli-Shanks algorithm for number rings

Public Key Representation and Security

The choice of the public key representation is crucial, as representing n as a list of generators or in Hermite normal form often allows factorization The best choices are prime ideals of the form p = (p), where p ∈ Z is prime and inert in K The security relies on the difficulty of computing the decomposition into prime ideals of n = pq If inertia degrees fp and fq are distinct, an efficient algorithm can factor n

Square Root Computation Methods

The paper provides several methods for computing square roots in OK/p and OK/q The explicit Chinese Remainder Theorem allows computing the inverse of the canonical isomorphism between OK/n and OK/p × OK/q A generalized Tonelli-Shanks algorithm is provided for number rings Furthermore, a fast square root extraction method exists when OK/p ≡ 3 (mod 4)

Performance Analysis and Conclusions

Encryption is described as being very fast in all cases, although running time increases with the degree of the number field Decryption is less efficient than for the classical Rabin scheme For a cubic number field example, decryption is relatively better than quadratic fields but still less efficient than classical Rabin The scheme is provably equivalent to the factorization problem of a large integer N if p and q are chosen carefully

Choosing the Right Square Root

To identify the original message among four possible square roots, one can use methods discussed in [4] applied to a single component of the message The requirement of taking inert primes p and q is helpful for identifying the correct square root by checking congruences modulo p and q If a coefficient is zero modulo both p and q, one should look at the next coefficient The paper concludes that semantic security requires random paddings because two extra-bits carry information about the degree zero term of the polynomial representing the message

Key Generation Scenarios

Key generation involves choosing a number field and then selecting inert primes p and q based on specific congruence conditions for quadratic, cyclotomic, or generic fields For the generic case, checking the irreducibility of g modulo p and q is time-consuming The construction of large primes p and q congruent to a specific value modulo D is used in these cases

Security Limitations

The scheme cannot be used for post quantum cryptography because an attacker with a quantum computer can factor the modulus via Shor’s algorithm Semantic security must be ensured by introducing random paddings, as the two extra-bits leak information about the degree zero term The scheme is provably equivalent to factoring N if p and q are chosen carefully

Conclusion

The paper proposes a novel public-key cryptosystem extending Rabin’s scheme to general number fields Encryption performs very fast, but decryption is less efficient than for the classical Rabin scheme A more sophisticated variant for degree 3 number fields at least performs relatively better than the case of quadratic number fields The new scheme is provably equivalent to the factorisation problem of a large integer N if the prime ideals p and q dividing the modulus n are chosen carefully

References

[1] Y. Awad, A. N. El-Kassar, and T. p. 0 Kadri

[2] H. Cohen

[3] H. Cohen

[4] M. Elia, M. Piva, and D. Schipani

[5] K. Mahler

[6] K. A. Petukhova and S. p. 1 N. Tronin

[7] M. O Rabin

[8] P. W Shor

[9] L. C. Washington

[10] H. C Williams

--- Page 1 ---

THE RABIN CRYPTOSYSTEM OVER NUMBER FIELDS

Pruning redundant reasoning tokens

Rabin’s cryptosystem [7] was the first asymmetric public-key cryptosystem for which it was shown that any algorithm which finds one of the possible plaintexts for every Rabin-encrypted ciphertext can be used to factor the modulus It is performed in the quotient ring Z/NZ where N = pq is the product of two large distinct prime numbers The public key is N and the private key is the pair (p, q) Encryption is very simple: To encrypt a message m ∈ Z/NZ one just computes its square; so c = m2 is the ciphertext For decryption, one uses the knowledge of p and q to compute the square roots of c (mod p) and c (mod q)

How the training signal is built

In this paper, we generalise Rabin’s scheme to rings of integers in number fields So let us fix a number field K with ring of integers OK and choose two distinct non-zero prime ideals p and q in OK Our scheme is performed in the quotient ring OK/n where n = pq The public key is the modulus n and the private key is the pair (p, q) The ciphertext of a message m ∈ OK/n is again c = m squared For decryption one has to compute the square roots of c modulo p and modulo q

Where the gains come from

In order to speed up decryption, we also provide an easy and fast way to compute square roots modulo primes p in OK under certain restrictions on p, thereby generalising the above method for primes p ≡ 3 (mod 4) This approach works particularly well in number fields of degree 3, but does not work in any quadratic number field This is one reason why we need to allow more freedom in choosing the field K Indeed, our runtime analysis shows that decryption of ciphertexts of comparable size becomes a lot faster over carefully chosen cubic than over quadratic fields

It turns out that it is a subtle question how to represent the public key n There are two reasonable ways to do this: either as a list of generators or in Hermite normal form We show that for most choices of p and q this is not secure It indeed allows us to factor n Our considerations led us to the conclusion that the best choices are prime ideals of the form p = (p), where p ∈ Z is prime, i.e. we consider rational primes p which are inert in K So we also need conditions that guarantee us that a given rational prime remains prime in K We will provide a class of number fields, where this can be checked by a simple congruence condition So the public key in our scheme is just N = pq where p, q ∈ Z are primes that are inert in K Then, as in Rabin’s original scheme, an algorithm which finds one of the possible plaintexts for each ciphertext allows N to be factored

We also address the question how to find the original message m among the usually four square roots of the ciphertext c = m squared In the classical case, Williams [10] proposed a method whenever both primes p and q are congruent to 3 modulo 4 It suffices to add two extra bits to the ciphertext: the parity and the Legendre symbol m N of the message m If we assume in addition that p and q are inert in K, we will show that it is still possible to uniquely identify the original message by adding two extra bits Finally, we note that Petukhova and Tronin [6] have generalised the RSA scheme to general Dedekind domains with finite residue fields However, they have not addressed the following questions: (i) how to find such Dedekind domains, (ii) how to make the required computations explicit, (iii) when is the scheme secure

  1. The public key 1. p. 01. Number fields and rings of integers Let us first explain how we represent number fields Let K be a number field of degree d over Q Let θ ∈ K be a primitive element so that K = Q(θ), which means that 1 = θ 0, θ, θ2,. p. 1.., θd−1 constitute a Q-basis of K The minimal polynomial of θ is the unique monic polynomial gθ ∈ Q[x] of lowest degree with root θ It is irreducible of degree d and there is a field isomorphism (1) Q[x]/(gθ) ≃−→ K = Q(θ), x 7→ θ So if we ‘choose’ a number field, we really pick a monic irreducible polynomial g ∈ Q[x] and consider the field Q[x]/(g) If we want to view this field as a subfield of the complex numbers, we choose a root θ ∈ C of g and apply (1) Then one has gθ = g and the set of embeddings of Q[x]/(g) into C is in one-to-one correspondence with the roots of g

Let OK be the ring of integers in K Then one can always choose θ ∈ OK so that gθ has integral coefficients The isomorphism (1) then induces an isomorphism of rings Z[x]/(gθ) ≃ Z[θ] The ring Z[θ] is always contained in OK, but we do not have equality in general This will be crucial in the following, as we get the ring Z[θ] for free once we have gθ, but it might be rather expensive to compute OK in general For instance, Zassenhaus’s Round 2 Algorithm [2, §6.1.4] first factors the discriminant of gθ, which is a hard problem when the discriminant is large Luckily, it will not be necessary to determine OK for our purposes (this will be explained below) Alternatively, one can stick to (classes of) number fields, where the ring of integers has been determined

Example 1.1 (Quadratic number fields) Let δ ∈ Z be square-free, δ ̸= 0, 1 Then x squared − δ ∈ Z[x] is irreducible and Q[x]/(x squared − δ) ≃ Q(√δ) The ring of integers in Q(√δ) is Z[ω], where ω = √δ if δ ≡ 2 or 3 (mod 4), whereas ω = (1 + √δ)/2 if δ ≡ 1 (mod 4) (see [2, Proposition 5. p. 21.1], for example) So in the latter case the index of Z[√δ] in OQ(√δ) is 2

Example 1.2 (Cyclotomic fields) Let m be a positive integer such that m ̸≡ 2 (mod 4) Let ζm ∈ C be a primitive m-th root of unity Then Q(ζm) has degree φ(m) over Q, where φ denotes Euler’s totient function Here one always has OQ(ζm) = Z[ζm] by [2, Proposition 9. p. 21.2]

Every α ∈ K can uniquely be written as α = P d−1 i=0 a iθ i with rational coefficients a 0,..., a d−1 If we use this representation for elements in K, addition becomes very easy For multiplication one essentially has to compute once the representations for θ d+k with 0 ≤ k < d − 1 We denote the norm of α ∈ K by N(α)

Example 1.3.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Generalization of Rabin's cryptosystem to number fields allows for key generation based on choosing prime ideals p and q that are inert in K, which simplifies computation and maximizes information transmitted with the protocol.

  2. Decryption can utilize a fast square root extraction method where, if |OK/p| is congruent to 3 modulo 4, a specific formula provides a square root directly without needing the full Tonelli-Shanks algorithm.

  3. The system can determine which of the four possible square roots is the original message by checking which coefficient aij coincides with ai0, addressing unicity in decryption by using parity and Legendre symbol bits as extra information.

Related papers