1
$\begingroup$

Background

I am interested in lattice-based cryptography. Recently I got familiar with the NTRU cryptosystem and found out that it can be extended onto hypercomplex numbers, like Quaternions (QTRU) or Octonions (OTRU).

I wanted to prepare a short presentation on how the procedure works so I have first implemented the original NTRU in SageMath (using a free online notebook server: https://cocalc.com/) following the exact polynomial values presented on Wikipedia. It worked and I was able to fully reproduce that example. Therefore I moved to complex numbers and tried to prepare an analogous example which would involve the complex-multiplication step. Unfortunately, this is where I run into problems. It seems I cannot get it right so I have prepared two tests:

  1. The first thing I tried was to prepare a notebook with a general framework of NTRU on $\mathbb{C}$ but with every imaginary component of every element set to zero polynomial. I call it NTRU-2D-1D because it essentially boils down to working on one-dimensional ring of polynomials. That test passed i.e. each step of the procedure yields expected results.
  2. The second thing I tried was to modify the test just a little, to get all imaginary parts of all elements the same as all real parts. I call this test NTRU-2D-2D. That means where previously I had $X = (X_1, 0)$ now I set $X = (X_1, X_1)$, where $X$ are elements of the underlying algebra and $X_1$ is the polynomial. This test fails i.e. I am not able to recover the original message $M$ after encryption-decryption.

Unfortunately, mathoverflow does not allow to attach HTML files to questions and so I have converted my notebooks to images and attached them below. I think this is a better solution then to host these files externally (for completeness and clarity, links will probably break in future). Could you please take a look and let me know where do I make an error? I just don't understand why is it incorrect now...

About the notebooks:

  • I manually follow the multiplication definition: $(a,b)(c,d) = (ac-db, da+bc)$
  • whenever you see a suffix in a variable name _1 or just 1 it means that it is the real part of the complex number, _2 and 2 denote imaginary part, respectively.
  • in order to make it easy to check the results this is still the exact same example from NTRU Wikipedia page.
  • I print variables after every operation to track the values better.

NTRU 2D-1D

1D

NTRU 2D-2D

2D

Improve this question
$\endgroup$
2
  • $\begingroup$ I’m voting to close this because i believe that "check my code" questions are not research level mathematical questions. $\endgroup$
    – KonKan
    Commented Jun 22, 2021 at 12:56
  • 2
    $\begingroup$ This is not a "check my code" question, as you nicely put it because the same code (with different input) produces expected output in 1D but not in 2D. This suggest that there is some conceptual flaw which I do not understand, but thanks for your valuable input. $\endgroup$
    – maciek
    Commented Jun 22, 2021 at 13:55

0

Reset to default

Your Answer

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