2
$\begingroup$

Suppose Alice chooses a number field $K$ and a polynomial $f(x) \in K[x]$. She computes the splitting field $L$ along with an embedding $\varphi: K \rightarrow L$. In SageMath,

L.<a>, phi = f.splitting_field(map=True)

Is it possible to use $\varphi$ for homomorphic encryption? That is, Alice can encrypt data using $\varphi$ and send the data to Bob along with the defining polynomial of $L$. Bob can then perform operations in $L$ then send the encrypted data back to Alice.

If $[L:\mathbb{Q}] = d_L$ and $[K:\mathbb{Q}] = d_K$, then $\varphi$ is just a $d_L \times d_K$ matrix over $\mathbb{Q}$ and Alice would use the Moore-Penrose pseudo-inverse to decrypt.

In this case, $f(x)$, $K$, and $\varphi$ are kept secret.

Improve this question
$\endgroup$
4
  • $\begingroup$ You could use your system for homomorphic encryption, but you shouldn't expect any reasonable amount of security. Any rational number is mapped to itself by $\varphi$. For a non-rational number $x$ one can calculate the minimal polynomial $f$ of $\varphi(x)$ over $\mathbb{Q}$ (of degree at most $d_K$) and knows that $x$ is one of the degree($f$) roots of $f$. $\endgroup$
    – garfunkel
    Commented Aug 13 at 9:55
  • $\begingroup$ Makes sense. Certainly reveals $d_K$. Is it easy to find the roots of the minimal polynomial? For example: encrypted_message.minpoly() = $x^4 - 111967209786545552 x^3 - 14228056473109271632285301350992360 x^2 + 971999691980762534478292767540456871985942882837536 x + 2469262660794397892071753436844504569195624496738245239774676019424$ $\endgroup$
    – Jackson Walters
    Commented Aug 13 at 15:11
  • $\begingroup$ I'm not sure if it matters at all, if one can find the roots easily or not. The point is that there are only few choices (the field automorphism do not mix the plaintext and ciphertext spaces well). The only other secret remaining is your choice how to represent the fields $K$ and $L$. But if you want to calculate in your fields efficiently, your choices for the representations differ only by linear maps. An attacker will probably only have to solve a linear system to find your secret representation. This is not a proof that your idea couldn't work, but I wouldn't have much hope for it. $\endgroup$
    – garfunkel
    Commented Aug 14 at 9:05
  • $\begingroup$ @garfunkel I don't have much hope for this specific scheme either, perhaps a modification of it. It's not clear to me which linear system the attacker would be solving. Like, how do you get around not knowing what $K$ is beside the degree $d_K$? There are different ways to represent $K$, but there are just different $K$. $\endgroup$
    – Jackson Walters
    Commented Aug 14 at 9:39

1 Answer 1

Reset to default
2
$\begingroup$

The most common way to make homomorphic encryption work is to use some sort of learning with errors (LWE) scheme. A particular derivative of this problem is called ring-LWE and it is parameterized by a number field $K$ with ring of integers $R = \mathcal{O}_K$ and a (rational) integer modulus $q\geq2$ [1]. So you need only be given these three things to define a ring-LWE problem. From there the definition for a homomorphic encryption scheme comes naturally (see, e.g., BFV or TFHE).

I, unfortunately, have no knowledge in Hill ciphers. Maybe someone else can chime in on that.

[1]: Vadim Lyubashevsky, Chris Peikert, and Oded Regev. 2013. On Ideal Lattices and Learning with Errors over Rings. J. ACM 60, 6, Article 43 (November 2013), 35 pages. https://doi.org/10.1145/2535925

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the reference. The only other appearance of number fields I'm aware of in cryptography would be for elliptic curves. The scheme I'm proposing seems too simple, but I'd like to understand what's wrong with it. I'm basically just doing arithmetic in the "large" field. $\endgroup$
    – Jackson Walters
    Commented Aug 5 at 20:59
  • 1
    $\begingroup$ also you can add this treasure in your comment thelatticeclub.com it contains a lot of resources about lattice-based cryptography $\endgroup$
    – Don Freecs
    Commented Aug 6 at 11:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.