15 Dec 2023
In the previous post, we have seen that NTT is a special way of evaluating a polynomial (i.e. converting a polynomial from coefficient form to evaluation form) such that the evaluation points are all the $d$-th roots of unity. We then examined a few efficient ways (recursive and iterative) to implement NTT and iNTT routines. Lastly we learned that by carefully picking the right twiddle factors (generators) as roots of the polynomial modulus, we can perform modular polynomial multiplication in NTT form in the same degree as the multiplicand (without the need to extend the degree and perform additional reduction).
Putting everything we’ve learned so far, we can put together an efficient algorithm for multiply polynomials in a ring in $O(n \log{n})$ time. The recipe is as simple as:
Read more...
31 Aug 2023
If you have known me before, you might have come across my cryptography-related blog posts either from Medium or my personal blog higashi.tech.
Unfortunately,, I forgot to update my credit card info and hence didn’t renew the domain :/ And guess what? Someone else bought the domain and now I can never have my domain back. I tried negotiating a good price for it though:
But looks very unlikely.
Therefore, I have acquired a new domain higashi.blog, and have ported over most of the recent blog posts. I will be gradually moving over some of the Chinese blog posts here as well, under 中文博客 tab.
Have fun exploring! Do let me know if you notice and weirdness with LaTeX rendering as I’m switching from KaTeX to MathJax.
23 Jun 2023
Previously, we took a look at the problem of polynomial multiplication. Specifically, we saw that we can view polynomial multiplications as a form of convolution. To make things easier to compute, we often define a polynomial modulus, making it into a ring. The modulus defining the ring in our context is often special, making the convolution either circular or negative wrapped.
At the end of the last post, we saw a naive approach at speeding up computation of convolutions - by converting the polynomials into evaluation form so convolution is as simple as coordinate-wise multiplication. We end up on the problem of the conversion between coefficient form and evaluation form which is expensive and becomes the new bottleneck.
In this post, we will now look at an efficient solution: Number Theoretic Transform, or NTT for short.
Read more...
22 Mar 2023
Polynomials are everywhere. In fact, in Computer Science, they are really just fancy lists of numbers that have a particular way of doing arithmetic.
For example, adding two polynomials is as simple as just summing up their coefficients. Multiplying a polynomial by a constant is just multiplying every coefficient by that constant.
However, when we want to multiply polynomials, things get slightly more complicated.
Read more...
16 Feb 2022
Based on: PKP-IDS, Permutation based identification protocol.
Idea: PKP is a problem where one is give a random matrix $A$ and a vector $v$. Then they are asked to find a permutation $\pi$ such that $A v_\pi = 0$, i.e. $v_\pi$ is the right kernel of $A$.
Finding such permutation $\pi$ is an NP-hard problem. However, we could use a 5-round public-coin interactive protocol to prove knowledge of the secret permutation $\pi$.
We will try to explore how PKP-IDS works, and then follow Beullens et. al. 2018 to compress PKP-IDS into PKP-DSS.
Read more...