Search

## Kachisa-Schaefer-Scott curves

A class of pairing-friendly curves with embedding degree $k \in \{16,18,36,40\}$. Given an integer $z \in \mathbb{N}$ a KSS curve can be constructed over a prime field $\mathbb{F}_p$ with the number of points $r$ and a trace of Frobenius $t$ as follows:

### $k = 16$

\begin{aligned} p(z) &= (z^{10} + 2 z^9 + 5 z^8 + 48 z^6 + 152 z^5 + 240 z^4 + 625 z^2 + 2398 z + 3125)/9801\\ r(z) &= z^8 + 48 z^4 + 625\\ t(z) &= (2 z^5 + 41 z + 35)/35 \end{aligned}

### $k = 18$

\begin{aligned} p(z) &= (z^8 + 5 z^7 + 7 z^6 + 37 z^5 + 188 z^4 + 259 z^3 + 343 z^2 + 1763 z + 2401)/21\\ r(z) &= z^6 + 37 z^3 + 343\\ t(z) &= (z^4 + 16 z + 7)/7 \end{aligned}

### $k = 36$

\begin{aligned} p(z) &= (z^{14} - 4 z^{13} + 7 z^{12} + 683 z^8 - 2510 z^7 + 4781 z^6 + 117649 z^2 - 386569 z + 823543)/28749\\ r(z) &= z^{12} + 683 z^6 + 117649\\ t(z) &= (2 z^7 + 757 z + 259)/259 \end{aligned}

### $k = 40$

\begin{aligned} p(z) &= (z^{22} - 2 z^{21} + 5 z^{20} + 6232 z^{12} - 10568 z^{11} + 31160 z^{10} + 9765625 z^2 - 13398638 z + 48828125)/1123380\\ r(z) &= z^{16} + 8 z^{14} + 39 z^{12} + 112 z^{10} - 79 z^8 + 2800 z^6 + 24375 z^4 + 125000 z^2 + 390625\\ t(z) &= (2 z^{11} + 6469 z + 1185)/1185 \end{aligned}

The class of curves has the Short-Weierstrass form:

$y^2 \equiv x^3 + b$

where given $z$ such that $p(z)$ is prime, a curve with a prime order subgroup of $r(z)$ points can be found either via complex multiplication or by exhaustively trying small coefficients $b$ until a curve is found.

The following SageMath code generates KSS curves.

class KSS(object):    @classmethod    def generate_prime_order(cls, zbits):        while True:            z = randint(2^(zbits - 1), 2^zbits)            pz = int(cls.p(z))            if not is_prime(pz):                continue            rz = int(cls.r(z))            if not is_prime(rz):                continue            break        K = GF(pz)        b = 1        while True:            curve = EllipticCurve(K, [0, b])            card = curve.cardinality()            if card % rz == 0:                break            b += 1        return curveclass KSS16(KSS):    @staticmethod    def p(z):        return (z^10 + 2 * z^9 + 5 * z^8 + 48 * z^6 + 152 * z^5 + 240 * z^4 + 625 * z^2 + 2398 * z + 3125)/9801    @staticmethod    def r(z):        return z^8 + 48 * z^4 + 625    @staticmethod    def t(z):        return (2 * z^5 + 41 * z + 35)/35class KSS18(KSS):    @staticmethod    def p(z):        return (z^8 + 5 * z^7 + 7 * z^6 + 37 * z^5 + 188 * z^4 + 259 * z^3 + 343 * z^2 + 1763 * z + 2401)/21    @staticmethod    def r(z):        return z^6 + 37 * z^3 + 343    @staticmethod    def t(z):        return (z^4 + 16 * z + 7)/7class KSS36(KSS):    @staticmethod    def p(z):        return (z^14 - 4 * z^13 + 7 * z^12 + 683 * z^8 - 2510 * z^7 + 4781 * z^6 + 117649 * z^2 - 386569 * z + 823543)/28749    @staticmethod    def r(z):        return z^12 + 683 * z^6 + 117649    @staticmethod    def t(z):        return (2 * z^7 + 757 * z + 259)/259class KSS40(KSS):    @staticmethod    def p(z):        return (z^22 - 2 * z^21 + 5 * z^20 + 6232 * z^12 - 10568 * z^11 + 31160 * z^10 + 9765625 * z^2 - 13398638 * z + 48828125)/1123380    @staticmethod    def r(z):        return z^16 + 8 * z^14 + 39 * z^12 + 112 * z^10 - 79 * z^8 + 2800 * z^6 + 24375 * z^4 + 125000 * z^2 + 390625    @staticmethod    def t(z):        return (2 * z^11 + 6469 * z + 1185)/1185

#### References

© 2020 Jan Jancar | Built with Dox theme for Gatsby