Skip to main content

Standard curve database

Search

Kachisa-Schaefer-Scott curves

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

k=16k = 16

p(z)=(z10+2z9+5z8+48z6+152z5+240z4+625z2+2398z+3125)/9801r(z)=z8+48z4+625t(z)=(2z5+41z+35)/35\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=18k = 18

p(z)=(z8+5z7+7z6+37z5+188z4+259z3+343z2+1763z+2401)/21r(z)=z6+37z3+343t(z)=(z4+16z+7)/7\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=36k = 36

p(z)=(z14−4z13+7z12+683z8−2510z7+4781z6+117649z2−386569z+823543)/28749r(z)=z12+683z6+117649t(z)=(2z7+757z+259)/259\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=40k = 40

p(z)=(z22−2z21+5z20+6232z12−10568z11+31160z10+9765625z2−13398638z+48828125)/1123380r(z)=z16+8z14+39z12+112z10−79z8+2800z6+24375z4+125000z2+390625t(z)=(2z11+6469z+1185)/1185\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:

y2≡x3+by^2 \equiv x^3 + b

where given zz such that p(z)p(z) is prime, a curve with a prime order subgroup of r(z)r(z) points can be found either via complex multiplication or by exhaustively trying small coefficients bb 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 curve


class 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)/35


class 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)/7


class 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)/259


class 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