T 0832/14 (Public key checking/CERTICOM) 07-03-2018

1. Admissibility of the appeals

Both appeals comply with the provisions of

Articles 106 to 108 EPC (cf. points II and III above) and are therefore admissible.

2. Article 52(2) EPC

The opponent had in writing raised an objection under Article 52(2)(d) EPC against auxiliary request 4 for lack of technicality of all the features of claims 1 and 2. Since most of the features which were objected to were already present in the set of granted claims and since this objection had not been raised by the opponent in its notice of opposition, the board considered it to be a fresh ground for opposition in the sense defined by G 1/95 and G 7/95. According to

G 9/91 (see Reasons 18), such a ground may be considered in appeal proceedings only with the patent proprietor's approval. The board also pointed out in its communication of 22 December 2017 that, in its view, the subject-matter of the claims did not relate to presentations of information (Article 52(2)(d) EPC) as such, or even to mathematical methods

(Article 52(2)(a) EPC) as such. In that respect, the board had indicated that, according to the case law of the boards of appeal (see for instance T 1326/06 and T 27/97), methods in the field of cryptography which clearly aimed at increasing the security of data communication between entities had to be regarded as inventions within the meaning of Article 52 EPC.

During the oral proceedings before the board, the patent proprietor, when asked, did not give its consent to dealing with this fresh ground for opposition. Thereupon, the board decided not to introduce the ground under Article 100(a) in conjunction with Article 52(2) EPC in the appeal proceedings.

3. Admission of D8 and the new pages of D6

These documents were submitted by the opponent with its statement of grounds of appeal. The opponent argued that they were submitted in response to the amendments introduced by the claims of auxiliary request 4 filed during the second day of the oral proceedings before the opposition division, in particular the features related to the checking of the public key when group G was an elliptic curve group. It pointed out that the new pages of D6 dealt with elliptic curve cryptography and that D8 was cited in D6. The patent proprietor held that these documents did not in any way address the checking of the public key, which was the gist of the features introduced by auxiliary request 4 with respect to the claims as granted.

Taking into account the arguments of both parties, the board decided to admit both documents into the appeal proceedings, in accordance with Article 12(4) RPBA. In particular, it considered that D6 was a textbook and that the additional pages of D6 addressed the technology in more detail rather than alternative embodiments. D8 was explicitly referred to in D6 and would have been considered by the skilled person in this context. The question whether these documents actually relate to checking of the public key must be assessed in the context of novelty and/or inventive step.

4. Article 84 EPC

Claim 1 comprises several alternatives in respect of the kind of group G used (multiplicative group or elliptic curve group), of the kind of checking performed on the message purported to be the public key, and of the further action decided in response to this checking. The opponent argued that the number of alternatives in claim 1 amounted to 24, such that the Article 84 EPC requirements for conciseness and clarity were not met. The board however considers that the skilled person can easily distinguish the alternatives in claim 1 from one another and can thus comprehend the claimed subject-matter without any difficulty.

The opponent further argued that claim 1 lacked the essential feature that subgroup S had to be cyclic in order to determine a generating element alpha of it. The board however holds that, as pointed out by the patent proprietor, group G being of order n is a cyclic group itself and every subgroup of G is a cyclic group. Therefore, it is implicit in claim 1 that S is also a cyclic group.

A further objection of the opponent was that claim 2 lacked the essential feature of defining further steps after the checking of the message purported to be the public key. In the board's judgement, claim 2 comprises all the steps necessary for the definition of the claimed invention, namely the establishment of a public key for securing the exchange between two correspondents. Any steps after the checking of the received public key, be it for instance a rejection or an acceptance of the generated public key, is not necessary for this definition.

For these reasons, the board judges that the claims meet the requirements of Article 84 EPC.

5. Article 123(2) EPC

The opponent objected that claim 1 did not meet the requirements of Article 123(2) EPC.

The opponent first argued that claim 1 did not define the transmission of the generated public key from one correspondent to the other, contrary to the teaching of the originally filed description on page 7,

lines 6 to 10 (corresponding to column 4, lines 52 to 56, of the published application). The board however holds that the feature of "receiving at the other of said correspondents a message purported to be the public key" present in claim 1 implies a transmission to the "other" correspondent from the "one of the correspondents" which is previously defined in the claim and which has generated the public key in question.

The opponent further stated that the definition of a "message purported to be the public key" was not present in the application documents as originally filed, in particular in the passage on page 7,

lines 6 to 10, which related to the reception by one correspondent of the public key sent by the other correspondent. The board however agrees with the patent proprietor that the description clearly mentions that one correspondent (A) sends a public key to the other correspondent (B), see column 1, line 46 to 50, and that an active adversary (E) may replace this public key with a different value, see column 2, lines 27 to 30. According to these passages, correspondent B expects to receive a public key of the form alphax from correspondent A, while not being aware that E may have modified it. The formulation "a message purported to be the public key alphax" is thus fully supported by the description.

The opponent further argued that the feature of "exponentiating the message with a value t where t is a divisor of the order n and checking if a resultant value corresponds to the group identity where the order q is not prime" had no support. The opponent relied for its argumentation on the first paragraph of page 7 (corresponding to the passage from column 4, line 47, to column 5, line 7, of the published application), which taught that the message should be exponentiated with the value t for each small divisor of (p-1), i.e for each small divisor of the order n = p-1 of group G, and not only for a divisor of the order n as defined in claim 1. In the board's view, the vague wording "small divisor of (p-1)" is not restrictive and may be seen to encompass all the divisors of n = p-1, except n itself. Further, the skilled person would understand from the above-mentioned passage that each time the message is raised to a power t, a check for the group identity is subsequently performed. Therefore, the exponentiation of the message to a value t, where t is a divisor of the order n, followed by the checking of the result of the exponentiation with the group identity, as actually defined in claim 1, is supported by the description as originally filed.

Furthermore, the opponent argued that the four termination alternatives defined in the last step of claim 1, namely rejecting the message or checking further if:

- the message corresponds to the group identity, or

- if the message corresponds to the tabulated value, or

- if the resultant value corresponds to the group identity, or

- if the resultant value corresponds to the tabulated value,

were not disclosed in the originally filed description on page 7, first paragraph (corresponding to the passage from column 4, line 47, to column 5, line 7, of the published application), which mentioned only one alternative, namely that the key exchange was terminated if the result of the checking of the exponentiated message was 1.

The board however notes that the checking step of

claim 1 defines three different alternatives:

- when the order q is prime:

- checking the message with respect to the group identity,

- when the order q is not prime:

- checking the resultant value with respect to the group identity, or

- checking the message with respect to a tabulated value.

The skilled person would thus consider that the rejecting step actually comprises three alternatives corresponding to the three alternatives of the checking step. The first alternative is described in column 4, lines 28 to 36, the second is disclosed in column 4, lines 47 to 58, and the third is described in column 5, lines 10 to 13. Therefore the board holds that the last step of claim 1 is supported by the application documents as originally filed.

For these reasons, the board judges that auxiliary request 4 meets the requirements of Article 123(2) EPC.

6. Article 54 EPC

6.1 The opponent argued that the subject-matter of claim 1 was already known from D6.

6.2 D6 on pages 10 and 11 (see the paragraph "NSIT Signature Scheme") discloses a method of establishing at a user a public key y of the form g**(x)mod p, utilising a multiplicative group ZP**(*) of order p-1, where p is prime, and comprising the steps of:

- establishing a subgroup of the multiplicative group of order q,

- determining an element g of the subgroup to generate the q elements of the subgroup,

- utilising said element g to generate the user's public key y of the form g**(x)mod p, where x is an integer and the private key of the user.

D6 further discloses on page 8, lines 22 and 23, and on page 13, lines 11 to 13, that an elliptic curve over a finite field can be used to implement the NSIT signature scheme. The public key y disclosed in D6 being used in a signature scheme, it can be considered as having been established by a first correspondent ("user" on page 11, line 4) and received by a second correspondent, which verifies the signature by making use of the public key (page 11, lines 13 to 17), for securing the exchange of data with the second correspondent.

Moreover, since multiplication in a finite multiplicative group or addition in an additive group, such as an elliptic curve group, must always, according to mathematical group theory, be performed modulo the order of the group plus one, the notation alpha**(x)used in claim 1 has to be understood as alpha**(x)mod p.

For these reasons, the board holds that the public key alpha**(x)of claim 1 can be read onto the public key y in D6.

D6 further discloses on page 10, last line, that the order q of the subgroup is between 2**(159)and 2**(160)and on page 11, last paragraph, that the security of the system is based on the difficulty of the discrete logarithm problem in the subgroup of order q of Z**(*)p generated by g. Since it is common knowledge that the difficulty of the discrete logarithm problem in a cyclic group increases with the order of the group, the board holds that the two above-mentioned passages clearly anticipate the broad and vague feature of

claim 1 that the order q of the subgroup S is sufficiently large that a brute force approach against the public key is impractical.

6.3 The opponent alleged that D6 further disclosed checking whether the message corresponded to the group identity, wherein the order q was prime and wherein the group G was a group of points on an elliptic curve, i.e one of the several alternatives defined by claim 1. To this end the opponent relied on passages of D6 dealing with public key generation in multiplicative groups (pages 2, 3, 5, 8, 10 and 11) and with mathematical operations on a group of points on an elliptic curve (pages 13, 17 and 18). According to the opponent, D6 teaches on page 18 to check if one of two points of the elliptic curve is the group identity before performing an addition of the two points, and the skilled person would have to apply this checking to a public key generated in an elliptic curve group when it is sent to the second correspondent. The board however considers that the passages of D6 relating to operations in an elliptic curve group do not in any way mention the generation, let alone the checking, of a public key. Therefore, in the board's judgement, the alternative of claim 1 in respect of the checking which was the only one referred to in the opponent's argumentation is not disclosed in D6.

6.4 The board thus considers that D6 discloses all features of claim 1 except for the last two steps of checking and rejecting or checking further.

Therefore, the board judges that the subject-matter of claim 1 is novel (Article 54 EPC) having regard to the disclosure of D6.

7. Article 56 EPC

7.1 Claim 1

The opponent argued that the skilled person, being aware of the possibility of a man-in-the-middle attack on the transmitted public key, would obviously consider a check on the received public key at the second correspondent. Checking if the public key corresponds to the group identity is obvious, taking into account that D6, in particular on page 18, discloses checking each operand for the group identity before performing the operation, i.e. the additive operation modulo n in the elliptic curve group.

The patent proprietor however plausibly argued that the attack described first in column 2, lines 11 to 45, and further in column 4, lines 28 to 36, of the published application was not known at the priority date of the application. The board notes in that respect that none of the prior-art documents deal with such a substitution attack. It further agrees with the patent proprietor that, the attack not being known, the skilled person would not have been incited to check the public key for the group identity but would rather have assumed that the transmitted public key, irrespective of whether or not its value was identical to the group identity, was a valid non-substituted public key.

The board thus considers that the alternative of claim 1 involving an elliptic curve group and a checking of the public key for the group identity, which is the only alternative of claim 1 that the opponent had objected to, is not obvious having regard to the disclosure of D6. Since the opponent did not object to the other alternatives of claim 1, the board judges that the subject-matter of claim 1 involves an inventive step (Article 56 EPC), having regard to the disclosure of D6.

7.2 Claim 2

Claim 2 relates to the alternative of claim 1 wherein the group G is an elliptic curve group and the subgroup S has a prime order, but with the omission of the last step of rejecting and checking further.

The opponent's Article 56 EPC objection in respect of claim 1 was directed only against this alternative. Further, the board considered in point 7.1 that the decisive feature for the issue of inventive step was the checking of the received public key and not a further step depending on the result of this checking (see also point 4, where the board decided that the step after checking was not an essential feature of claim 2). For these reasons, the board decides that the subject-matter of claim 2 involves an inventive step, having regard to the disclosure of D6.

8. In conclusion, the board judges that the grounds for opposition under Article 100(a) and (c) EPC pursued by the opponent in the appeal proceedings do not prejudice the maintenance of the patent as amended according to auxiliary request 4. Given that auxiliary request 4 is identical to the second auxiliary request on which the decision under appeal was based, this finding confirms the interlocutory decision of the opposition division.