System and method for reducing computations in an implicit certificate scheme

A method of computing a private key from an implicit certificate associated with a certificate authority in a cryptographic communication system based on an underlying group of order n;

• the method being performed by a computing device in the communication system;
• the device comprising a cryptographic unit;
• the method comprising:
• the device generating an ephemeral private key;
• the device operating on the implicit certificate in the cryptographic unit to derive an integer e;
• the device deriving a pair of integers e1 and e2 from the integer e in the cryptographic unit, each of the integers e1 and e2 having a bit length less than the bit length of the integer e, and the ratio of the integers e1 and e2 corresponding to the integer e;
• and
• the device computing the private key by combining the integers e1 and e2 with the ephemeral private key and private key contribution data of the certificate authority,
• wherein the integers e1 and e2 are derived using a truncated Extended Euclidean Algorithm.

A device comprising a processor and memory, the device configured to compute a public key from an implicit certificate associated with a certificate authority in a cryptographic communication system based on an underlying group of order n, and the device configured to perform operations comprising:

• operating on the implicit certificate in the cryptographic unit to derive an integer e;
• deriving a pair of integers e1 and e2 from the integer e in said cryptographic unit, each of the integers e1 and e2 having a bit length less than the bit length of the integer e, and a ratio of the pair of integers e1 and e2 corresponding to the integer e;
• and
• computing the public key by combining the integers e1 and e2 with public key contribution data derived from said implicit certificate and a static public key of the certificate authority,
• wherein the pair of integers e1 and e2 are derived using a truncated Extended Euclidean Algorithm.

A device comprising a processor and memory, the device configured to compute a private key from an implicit certificate associated with a certificated authority in a cryptographic communication system based on an underlying group of order n, and the device configured to perform operations comprising:

• generating an ephemeral private key;
• operating on the implicit certificate in the cryptographic unit to derive an integer e;
• deriving a pair of integers e1 and e2 from the integer e in the cryptographic unit, each of the integers e1 and e2 having a bit length less than the bit length of the integer e, and a ratio of the integers e1 and e2 corresponding to the integer e;
• and
• computing the private key by combining the integers e1 and e2 with the ephemeral private key and private key contribution data of the certificate authority,
• wherein the integers e1 and e2 are derived using a truncated Extended Euclidean Algorithm.

A certificate authority comprising a processor and memory, the certificate authority configured to compute a private key from an implicit certificate associated with the certificate authority in a cryptographic communication system based on an underlying group of order n, and the certificate authority configured to perform operations comprising:

• generating an ephemeral private key;
• operating on the implicit certificate in the cryptographic unit to derive an integer e;
• deriving a pair of integers e1 and e2 from the integer e in the cryptographic unit, each of the integers e1 and e2 having a bit length less than the bit length if the integer e, and a ratio of the integers e1 and e2 corresponding to the integer e;
• and
• computing the private key by combining the integers e1 and e2 with the ephemeral private key and private key contribution data of the certificate authority,
• wherein the integers e1 and e2 are derived using a truncated Extended Euclidean Algorithm.