T 1925/11 (Modular reduction hardware/INSIDE SECURE) of 25.3.2015

Summary of Facts and Submissions

I. The appeal lies against the decision of the examining division dated 23 March 2011, for reasons referring to the communication dated 25 October 2010, to refuse the application for lack of clarity and support, Article 84 EPC, and for lack of an inventive step, Article 56 EPC, over the documents

D1: Dhem J.-F., "Efficient Modular Reduction Algorithm in Fq[x] and its Application to 'Left to Right' Mo­du­lar Multiplication in F2[x]", Proc. of CHES 2003, LNCS 2779, Springer-Verlag, pages 203-213,

D2: WO 2004/0111831 A2,

D3: US 2003/044014 A1, and

D4: US 2003/079139 A1

II. A notice of appeal was received on 1 June 2011, the appeal fee being paid on the same day. A statement of grounds of appeal was received on 21 June 2011. The appellant requested that the decision under appeal be set aside and a patent be granted on the basis of claims according to a main or auxiliary request as filed with the grounds of appeal, apparently in combi­nation with the application documents on file, namely drawings pages 1-2 and description pages 1-5, 8-11 as originally filed and description pages 6 and 7 as filed with letter of 8 April 2009.

III. With a summons to oral proceedings, the board informed the appellant about its preliminary opinion according to which the pending claims lacked clarity, Article 84 EPC 1973, and an inventive step, Article 56 EPC 1973 over D1-D4. In particular, the board questioned whether and to what extent the claimed subject matter could be said to be "cryptographically secure" and whether the claims established that the alleged technical effect of in­creased efficiency could be ascribed to the claimed subject matter due to its reliance on a "word-size" parameter w.

IV. In response to the summons, with letter dated 4 March 2015, the appellant filed amended claims 1-9 according to a main and a first auxiliary request and claims 1-5 according to a second auxiliary request and requested the grant of a patent based on one of these sets of claims. With the same letter the appellant informed the board that the appellant's re­presentative would not attend the oral proceedings. The appellant further filed a document contai­ning technical background on DSS (FIPS PUB 186-2), which is not relevant for the purpose of this decision, and a declaration by one of the in­ven­tors, Vincent Dupaquis, relating to how one skilled in the art would have read the description.

V. Claim 1 according to the main request reads as follows:

"A computer hardware-implemented cryptographic method comprising a modular polynomial reduction operation in a binary finite field, the modular polynomial reduction operation comprising:

precomputing and storing in memory a polynomial constant u(x) representing a bit-scaled reciprocal of a multi-word polynomial modulus m(x) having a length defined by a number of words;

estimating an approximate polynomial quotient q(x) for a polynomial p(x) to be reduced modulo m(x), wherein said estimating is executed upon p(x) in a computation unit by a polynomial multiplication over the binary finite field by said constant u(x);

characterized by:

generating in a random number generator a random polynomial error value E(x) having a degree that falls within a predetermined range and applying said polynomial error value to said approximate polynomial quotient to obtain a randomized polynomial quotient q'(x) = q(x) + E(x); and

calculating a polynomial remainder r'(x) = p(x) + q'(x)?m(x) in said computation unit by performing word-size shifts, said remainder r'(x) being of higher degree than said modulus m(x) but congruent to p(x) modulo m(x) and where the degree of p(x) is less than or equal to 2k+w, w being a word size in bits of the computer hardware and k being the length in bit number of the words representing the modulus m(x)."

Claim 5 of the main request reads as follows:

"A computational hardware for executing a cryptographic program comprising a polynomial modular reduction operation over a binary finite field, the hardware comprising:

a computation unit adapted to perform word-wide finite-field multiply and accumulate steps on polynomial operands retrieved from a memory and polynomial coefficient intermediate results from a set of working registers;

a random number generator for generating a random polynomial error value E(x) having a degree that falls within a predetermined range;

an operations sequencer comprising logic circuitry for controlling the computation unit and random number generator in accord with program instructions so as to carry out the method of one of claims 1 to 4."

The wording of the claims according to the dependent claims is immaterial for this decision.

VI. Oral proceedings were held in absence of the appellant on the scheduled day. At the end of oral proceedings, the chairman announced the decision of the board.

Reasons for the Decision

The invention

1. The application relates to cryptographic methods based on modular arithmetic in finite fields. Such methods, the AES/Rijndael cipher being mentioned as one example (p. 1, lines 20-26), rely on polynomial reduction by a speci­fied modulus.

1.1 Since this reduction operation is one of the most ex­pen­­­sive ope­rations in cryptography, a number of dedi­ca­ted fast methods have been developed, one of which by Barrett­. The application presents the necessary for­mu­lae for Barrett's algorithm adapted to modular reduc­tion of polynomials in a binary finite field (see p. 8, lines 29-34, and p. 9, esp. lines 18 and 28).

1.2 The application mentions in general terms that "[m]a­the­matical compu­tations performed by crypto­graphic sys­tems may be susceptible to power analysis and timing attacks" (p. 1, lines 26-28). Elsewhere, reference is made to "crypt[]analytic attacks that rely upon consis­tency in power usage to determine the modulus" (p. 11, lines 6-8).

1.3 The invention sets out to make Barrett's algorithm "more secure against crypt[]analysis attacks, while still providing fast and accurate results". To achieve this effect, the application proposes to "[inject] a random polynomial error E(x) [...] into the computed po­lynomial quotient to obtain a randomized quo­tient" (p. 10, lines 4-7).

1.4 The description discloses the mathematical steps to be performed in a "polynomial reduction operation", and then that "[f]or a modulus of high degree (multi-word) the operation can be performed with word shifts rather than bit shifts" (p. 9, lines 20-32). To this end, the formulae used are reformulated in terms of the "word size w", more precisely in terms of divisions by x**((2k+w)) and x**((k-w)) (see p. 9, lines 32-34). This is said to "sim­­­­pli­f[y] handling of the polynomial quanti­ties on computa­tio­nal hardware" (see p. 9, line 35 - p. 10, line 3).

1.5 The description further explains that the multi-word modular reduction is to be carried out on computational hardware which locates the operands within the RAM by means of a pointer and an indication of the operand length in terms of number of words (see p. 4, lines 7-25, esp. lines 20-25).

2. In the board's opinion it is evident for the skilled reader that "the operation" mentioned on page 9, line 31, refers to the polynomial reduction operation as a whole and, in particular, to the calculation of q(x) and u(x). Furthermore, in the board's view, the state­ment that the operation "can be performed with word shifts rather than bit shifts" (emphasis by the board) must be read as stating that bit shifts are replaced by word shifts throughout the operation.

2.1 In its summons the board had noted that divisions by x**((2k+w)) and x**((k-w))correspond to word-size right shifts only if k is a multiple of w. The appellant agreed with this observation and argued that this was a matter of necessity and thus self-evident for the skilled reader (see letter of 4 March 2015, p. 2, 6th para., and the declaration by the inventor).

2.2 The board follows the appellant's argument and con­si­ders that the description, by introducing the modi­fied formulae as enabling an implementation "with word shifts rather than bit shifts", discloses implicitly that for the purpose of the modified algorithm the degree k of the modulus must be a multiple of w.

The prior art

3. D1 discloses a variant of Barrett's method generalized to polynomial reduction in a bi­nary finite field which is substantially equivalent to the one presented in the application (see D1, abstract, lines 6-7, and in parti­cular p. 204, equation (1)) except for the exponents in the cen­tral formula (loc. cit.) which define the number of bit shifts to be performed. The central formula is based on bit shifts defined in terms of p, the degree of the mo­dulus N(x), and "some value of beta to be defined later" (see sec. 2, the para. just above equation (1)). In the sequel of the paper, it is noted that the calculation can be simpli­fied for "beta >= alpha" and, in particular, for "beta = alpha", where alpha=deg(U)-deg(N) is the diffe­rence be­tween the degrees of the polynomial to be reduced and of the mo­dulus (see sec. 1, 1st para. and the sentences just be­low equa­tions (4) and (7)).

Article 84 EPC

4. The decision under appeal objected (see points 1 - 1.1.3) that the independent claims lacked clarity due to the reference of the pertinent binary finite field as GF(2**(n)) and the lack of a definition of the relative sizes of n and the degree k of the modulus. Since the re­ference to GF(2**(n)) was deleted from the claims, this clarity objection has become moot. The board is also of the opinion that referring to a binary finite field without mentioning n does not cause any clarity prob­lems in its own right. The board notes that present claims 1 and 5 now explicitly specify that the claimed operation is part of a computer-hardware implemented cryptographic method, as suggested by the examining division (see decision under appeal, point 1.2, penult. sentence). The board is also of the opinion that the ope­ration being masked is properly and clearly referred to as a "modular polynomial reduction operation" even if, for inappropriate choices of E(x) vis-à-vis p(x), the operation may not actually be a reduction (see de­ci­sion under appeal, point 1.2). The board not having any clarity concerns of its own is thus satisfied that the claims of the main request conform with Article 84 EPC 1973.

Article 123 (2) EPC and claim construction

5. Claim 1 is substantially based on claim 1 as originally filed. That the modulus has a "length defined by a number of words" is disclosed on page 4 (lines 20-25) which explains that the operand lengths are given in "number[s] of word" (see also original claim 8), that w is the word size of the computer hardware is disclosed inter alia in original claim 9, and that k is "the length in bit number of the words representing the modulus m(x)" is disclosed by the last paragraph on page 9 according to the interpretation given above.

5.1 Claim 1 of the main request contains the phrase "cal­culating a polynomial remainder r'(x)=p(x)+q'(x)?m(x) in said computation by performing word-size shifts" which literally suggests that the word-size shifts are used in particular, and possibly only, in the calcula­tion of r'(x). In contrast, the only possi­bly relevant disclosure on page 9, last paragraph, states that it is "the operation [which is] performed with word shifts", i.e. the modular polynomial opera­­tion as a whole, and, in particular, the calcu­lation of q(x). The calculation of the polynomial remainder r'(x) on the other hand is mentioned only on page 10, lines 23-32, based on a for­mu­la which does not require any word or bit shifts at all.

5.2 Therefore, the literal wording of claim 1 is not dis­closed in the application as originally filed. At the same time, the board is of the opinion that the skilled reader of claim 1 would notice that the refe­rence to word-size shifts cannot reasonably apply to the calcu­la­tion of the polynomial remainder according to the gi­ven formula r'(x)=p(x)+q'(x) ?m(x) alone and further in view of the description (loc. cit.).

5.3 The board also notes that the appellant, when it argued why amended claim 1 conformed with Article 123 (2) EPC in its submission dated 4 March 2015, explained by re­fe­rence to page 9, lines 30-32, that "the computa­tion of q(x) [...] can be performed with word shifts".

5.4 The board therefore considers that the mentioned phrase contains an obvious error by the appellant contrary to its express intentions which the skilled person would however be able to identify and interpret correctly, on the basis of the application as originally filed, as spe­­­cifying "the operation" - as a whole, rather than the calculation of the polynomial remainder - "be­ing performed by word-size shifts".

5.5 In the following, the board assumes this interpre­ta­tion.

Inventive step

6. D1 is not concerned with crypt­analytic side channel attacks and thus has no occasion to disclose anything about protection against such attacks. D1 also does not mention the choice of beta in view of the chosen hardware platform nor the exploitation of word shifts in the implementation of the algorithm.

7. The claimed invention therefore differs from D1 by

(a) the generation of a randomized polynomial quotient q'(x) based on a random polynomial error value E(x), and

(b) the calculation of the polynomial reduction operation by performing word shifts.

7.1 These features address different problems. Difference (a) is meant to increase security against crypt[]ana­ly­sis attacks" (see description, p. 2, penult. para., and letter of 4 March 2015, p. 3, 6th para.) while diffe­rence (b) is argued to allow for a more efficient imple­mentation on hardware with multi-word operands and instructions (see also p. 2, last para., and letter of 3 March 2015, p. 4, 3rd para.).

7.2 The preamble of claim 1 refers to a "cryp­tographic me­thod comprising a modular polynomial re­duc­tion opera­tion". The body of claim 1 does not state, how­ever, where specifically in the cryptographic method the mo­dular polynomial reduction is to be performed and what its parameters mean in that context.

7.3 For that reason, the board has its doubts - as indica­ted in the summons (point 6.3) - whether difference (a) in the claimed modular polynomial reduction operation could be said to increase cryp­tographic security as long as the claims did not specify that the masked ope­ra­tion indeed relate to a "secret" of the crypto­gra­phic method which might be the target of a crypta­nalytic attack (see summons, point 6.3).

7.4 As regards difference (b), the board is satisfied that, as explained in the description (p. 1, lines 20-26), commonly known cryptographic methods rely on modular polynomial reduction opera­tions, and that, therefore, such methods may profit from a different, possibly more efficient, imple­men­­tation of modular polynomial reduc­tion - inde­pendent of whether they "relate to a secret" or not.

7.5 Further with regard to difference (b), the board consi­ders that the use of word shifts rather than bit shifts may be more efficient under certain circumstances, in par­ti­cular for certain sizes of the modulus and the poly­no­mi­al to be reduced, but doubts that this can be said for all such values. An increase of efficiency can hence not be attributed to the claimed method over its entire breadth, and the descrip­tion provides no basis for the skilled person to determine the pertinent cir­cumstances.

7.6 The board is, however, satisfied that the claimed im­plementation of the operation by word shifts, i.e. diffe­rence (b), enables a different implementation of the known algorithm exploiting a particular multi-word operand addressing scheme. In this regard the board notes specifically that for an operand given in terms of a pointer and a length in number of words (see de­scription, p. 4, lines 20-25), a right shift by, say, one word can be implemented by a mere decrement of the ope­rand length.

8. As mentioned above, D1 does not disclose or suggest the selection of the exponent beta in terms of the word size w of the given computer hardware in view of imple­menting the algorithm in terms of word shifts. Nor do documents D2-D4 which rather relate to the security aspect of the present invention (by way of "masking", "brouillage" or "Verfremdung", resp.). Since, moreover, the board does not consider this modification of the known modular po­lynomial reduction operation to be ob­vious from common knowledge alone, the board comes to the conclu­sion that claim 1 shows the required inven­tive step over D1 in view of D2-D4, Article 56 EPC 1973. The same applies to claim 5 by virtue of its ex­pli­cit reference to method claim 1.

9. As a consequence, the inventive merit of difference (a) vis-à-vis D1 and, in particular, the ques­tions of whe­ther it contributes to increased cryptogra­phic security and the technical character of the claimed method can be left open.

10. According to the preceding analysis, the decision under appeal must be set aside. Moreover, the board deems the claims of the main request allowable vis-à-vis the pri­or art to hand. The board considered whether there was any indication on file that the claims according to the main request might not have been covered by the search, in which case the board would have had to remit the case for further prosecution under Article 111 (1) EPC. As a matter of fact, however, the claims as ori­gi­nally filed did refer to the algorithm modified in terms of word size (see claims 2, 4, 5, and 9-11) and some of them had been considered as a possible ba­sis for an allow­able application according to the Ex­ten­ded Euro­pe­an Search Report. The board therefore must assume that the search examiner was aware of the "word-size shift" feature and accordingly that the search must have co­vered this feature. The board therefore con­cludes that a remittal for further prosecution is not appropriate.

The description

11. The board notes that the description has not been adap­ted to the amended claims as required by Article 84 EPC 1973.

11.1 Specifically, the present description (p. 9, lines 30-32) discloses the use of word shifts as an option rather than, accor­ding to the present claims, an obli­ga­tory feature of the pre­sent invention.

11.2 The board also notes that the description mentions Barrett's method to "replac[e] the long division with multiplications and word or bit shifts [...] in order to estimate the quotient" (p. 8, lines 22-27). The board tends to consider that the mention of word shifts in this sentence may give the impression that a word-shift version of Barrett's method may have been known in the art. This is, however, contrary to the position consistently taken by the appellant in its submissions during examination and appeal according to which the word shifts were non-obvious over the prior art and es­tablished an inventive step. Since, as noted above, the search must be assumed to have covered this feature the board has no reason to question the appellant's posi­tion on this point. Even though the board therefore takes it that the reference to "word shifts" in that sentence refers to the version of Barrett's method presented in the application, the board considers that the sentence should be amended to avoid any possible confusion.

Summary

12. Since the board comes to the conclusion that inde­pen­dent claims 1 and 5 show the required inventive step and are clear and originally disclosed based on the only reasonable interpretation, the board considers that a patent should be granted based on claims 1-9 according to the main request. Given the fact, however, that the examining division must give the appellant an opportunity anyway to adapt the descrip­tion, the board deems it also appropriate that the appellant should be allowed to correct the error in claim 1 to conform with the appropriate interpretation as explained above (see in particular point 5.4).

Order

For these reasons it is decided that:

1. The decision under appeal is set aside.

2. The case is remitted to the examining division with the order to grant a European patent on the basis of claims 1-9 of the main request, filed 4 March 2015, together with any necessary amendment to the description.