Patent ID: 8180047

Claim:
A computer-implemented method comprising: generating a trapdoor pairing, wherein the trapdoor pairing comprises a keyed bilinear map e: G1×G2→G3 from a first elliptical curve group G1 and a second elliptical curve group G2 of elliptic curve E to a finite field third group G3, wherein the trapdoor pairing possesses properties including: a description of groups G1 and G2 having respective generators P and Q, and a Decisional Diffie-Hellman (DDH) problem with respect to group G1 and group G2 that is hard; secret trapdoor information with which the keyed bilinear map can be efficiently evaluated; and an evaluation of the trapdoor pairing using the secret trapdoor information to reveal that at least a part of the bilinear map does not reveal the secret trapdoor information, wherein the trapdoor pairing comprises a trapdoor pairing construction in which: the secret trapdoor information comprises an isogeny between two elliptic curves E1 and E2; public information includes <P>=ker(φ), <Q>=ker({circumflex over (φ)}); G3 comprises the mth roots of 1, wherein m is prime; and a trapdoor pairing function for generating and/or evaluating the trapdoor pairing using the secret trapdoor information is denoted by e φ (A, B):=e m (A, φ −1 B), wherein m denotes a degree of the isogeny that is equal to the size of the kernel of φ, the A comprises a point on elliptic curve E1 in the kernel of φ, the B denotes a point on elliptic curve E2 in the kernel of the dual isogeny {circumflex over (φ)}, wherein e m (A, φ −1 B) is the m th Weil pairing on the elliptic curve E1; and cryptographically processing data based on the trapdoor pairing, such that evaluations of random Diffie-Hellman triplets and random non-Diffie-Hellman triplets indicate 0 bits and 1 bits or 1 bits and 0 bits.