3.5.06 – legalAND.tech

Masking a private key/CERTICOM – T 0556/ 14 – 28 July 2016

In this decision in a patent a method of masking a privat key is claimed. It is considered not to be a mathematical method as such, because storing on a smartcard (hardware) was claimed. The claimed method achieves some protection against power analysis attacks and thus have a technical effect. An inventive step is acknowledged if, having regard to the state of the art, the invention is not obvious to a person skilled in the art. It is not necessary that the invention is a technical improvement over the prior art. The claimed method is an alternative approach compared to the closest prior art and is not suggested.

Object of the Invention:

the invention relates to a method for masking a private key used in cryptographic operations on a security token such as a smartcard against power analysis attacks
the security of cryptographic systems relies on a particular piece of information being kept secret, and power analysis attacks try to extract information about the secret by statistically analysing the power consumption of the security token when carrying out the cryptographic operation
the attacker of the power analysis attack considers the security token “to be a black box which contains a known algorithm and an unknown key” and in order to obtain the required statistical information, repeatedly executes the algorithm with varying parameters under his control
masking is, roughly speaking, a technique of randomising the calculations carried out in each instance of the cryptographic algorithms, so that their result remains the same but no relevant statistical information about the key can be gathered by repeated execution
first a private key d, which in elliptic curve cryptography is multiplied with a point P to derive a public key Q = dP, is “divided” into a plurality of parts
specifically disclosed is a division into two parts b1 and b2 such that d = b1 + b2
then a random number π is generated and the values of the parts are updated as b1 = b1 + π mod n and b2 = b2 – π mod n, where n is the number of points on the elliptic curve used
the cryptographic operation, in which the private key is “used”, is then carried out by “utilizing” the individual and modified “new parts”

Board I (Art. 52 (2) and (3) EPC):

due to the express reference in claim 1 to a smart card on which the key parts and also the new parts are stored, the claimed method of masking is not a mathematical method as such (Claim 1: A method […] storing the new parts on the smart card […])
due to the reference to the smart card and in view of the description the skilled person would understand the claimed masking operation to be an automated one to be carried out on the smart card

Board II (technical effect of masking)

central to any masking method is the modification of a mathematical method in such a way that its repeated execution is less prone to a statistical analysis revealing the properties of a secret
since the result of the computation must not change, this means that masking, in essence, relies on replacing one mathematical method by another which has an equivalent result
however, the modified computation is meant to be better protected against power analysis (or other sidechannel) attacks when carried out on hardware
as such, the idea of masking is well-established in the art as a protection against such attacks
the board accepts as a technical problem the protection of a cryptographic computation against power analysis attacks – if, and only if, the computation is actually carried out on hardware and thus open to such attacks
claim 1 specifies a masking method carried out on hardware
even though claim 1 literally specifies only the storage of the key parts on a smart card, in the board’s view the skilled person can only understand the method of claim 1 as a fully computer-implemented method
the claimed randomisation steps, namely the calculation of two randomised key parts and the computation of Q = b1P + b2P instead of Q = dP, does achieve some protection against power analysis attacks and thus have a technical effect
à mathematical steps contribute to the technical character of claim 1

Board III (inventive step)

the differences between the claimed matter and D2 (closest prior art) are
- that D2 relates to RSA (Rivest-Shamir-Adleman = public-key cryptosystem) whereas claim 1 relates to elliptic curve cryptography (ECC), and
- the masking of the secret by randomised splitting
the problem solved by the invention over D2 can therefore be considered as adapting the masking method of D2 to other cryptographic operations particular side channel attacks

Respondent I (inventive step)

the randomised splitting steps do not make the claimed method more efficient than the one according to D2
on the contrary, in fact: while the method of D2 masks the given calculation by the addition of one multiplication and one addition, the claimed method would be adding two multiplications and one addition and thus be less efficient

Board IV (inventive step)

the disadvantage of a method may be outweighed by an advantage it may also have
for instance, a slower method might have a statistically significant protective advantage against particular side channel attacks
the board hastens to add that the patent contains no detail whatsoever that might allow a judgement or even a sophisticated guess as to the relative security of the proposed measure against any particular power analysis attack
however, the board considers that the comparison between the claimed method and that of D2 cannot be reduced to the number of additions and multiplications
inventive step is acknowledged if, having regard to the state of the art, the invention is not obvious to a person skilled in the art
it is not necessary that the invention is a technical improvement over the prior art
the claimed randomized splitting and the adding of an “effective zero” according to D2 are alternative approaches and that the change from the latter to the former is not suggested by the change from ECC to RSA
the respondent has also not put forward any fundamental mathematical considerations which would, to the board’s satisfaction, suggest this change
the respondent was not able to convince the board that the skilled person starting from D2 would be led, in an obvious way, to the randomized split according to the invention
–> the claimed method shows the required inventive step over D2

Conclusion:

There are all necessary elements which are necessary that the mathematical method is considered for inventive step at the EPO:

a mathematical method
a use: computer implementation of the mathematical method on a smartcard
the use is technical: because it contributes to a technical effect, namely the protection of a cryptographic computation against power analysis attacks – if, and only if, the computation is actually carried out on hardware and thus open to such attacks

Koprozessor zur modularen Inversion/GIESECKE & DEVRIENT – T 2318/08 – 23. Mai 2012

This decision provides a known cryptographic coprocessor and a known Euclidean method. However, it is not known how to use free bit sections in the coprocessor to speed up the method. Therefore, the clever use of a known coprocessor to speed up the implementation of an equally known method solves a technical problem.

Object of the Invention:

the invention relates to a method for calculating the modular inverse of a value u to a modulus v, which is relevant in cryptographic methods
the invention is based on a known extended Euclidean method for calculating the modular inverse
the core idea of the method is not to represent the output values u and v “right-aligned” in the low-order bit positions as usual, but to shift them to higher-order positions to such an extent that space is created in the low-order positions for the other parameters of the method
only the calculation steps of the standard Euclidean method need to be carried out on the modified representation in order to obtain the results of the extended method
the new method therefore requires fewer calculation steps than the extended Euclidean method, but at the cost of a longer bit length for the input values
the practical relevance of the method results from the following observations:
- in cryptographic practice, modular inversion is typically performed with a coprocessor designed for operations on integers, whose bit length in turn depends on the usual key length in RSA (= Rivest-Shamir-Adleman = public-key cryptosystem)
- the so-called EC methods (= Elliptic Curve), which are an alternative to RSA, use significantly shorter keys so that modular inversion only has to be carried out for smaller numbers
- accordingly, if a coprocessor optimised for RSA is used for EC, a part of its bit system remains unused
- the method according to the invention utilises these already existing surplus bits to accelerate the desired method

Board:

the skilful use of a known coprocessor to accelerate the implementation of an equally known method solves a technical problem and can therefore in principle fulfil the requirements of Article 56 EPC

the examining division based its rejection on the fact that the subject-matter of independent claim 1 could not, according to its wording at the time, be said to provide a solution to this technical problem
to this end, it lacked, on the one hand, the limitation to a coprocessor “intended for integer calculations with at least the increased bit length” and, on the other hand, the indication that the auxiliary variables were carried in the low-order bits of the increased bit length
the present claim 1 is now limited as claimed:
- the claimed coprocessor is “provided” for a bit length greater than that required for the input values u and v
- according to the claim, the surplus bits are utilised by shifting u and v into higher “bit sections” by multiplication by an expansion factor, and introducing “disturbances” into the low-order bit sections thus freed up, which serve as output values for auxiliary variables of the subsequent calculation

from the fact that, on the one hand, cryptographic coprocessors and, on the other hand, the Euclidean method and its variants are known, it only follows that the implementation of Euclidean methods on cryptographic coprocessors would be obvious to the skilled person
however, this does not indicate that free bit sections in such a coprocessor can be used in the claimed manner to accelerate the method
–> inventive

Programmiersystem/RENNER – T 1539/09 – 18 July 2013

The invention is directed to a graphical programming language and environment that should enable a user to create programme code without a great deal of learning effort or special expertise. The definition and provision of a programming language does not contribute to the solution of a technical problem according to the Board.

Object of the Invention:

enable persons without special prior knowledge in the position to create their own computer programmes
the application proposes a graphical programming system as a solution
the system provides different “programme modules” which can be linked together according to predetermined rules
graphic symbols are assigned to the program modules, which the user can arrange on a “visualisation surface” and which are linked there by means of suitable lines to form a “structure diagram”
each programme module of a structure diagram corresponds to a “programme code section” and the entire structure diagram thus to a programme
thus, the user can define programme code “on a text basis” by manipulating graphic symbols on the computer screen without having to enter it directly
when the user selects a programme block, a display interface (e.g. a window) opens in which the user can edit the programme code section of this block

Board:

the invention is directed to a graphical programming language and environment that should enable a user to create programme code without a great deal of learning effort or special expertise
the effect of reducing the user’s mental effort when creating programmes is not in itself a technical one in the opinion of the Board
this is all the more true as it is aimed at equally for all programmes, regardless of the purpose of the developed programme

when programming – in the sense of formulating programme code, “coding” – the programmer must select those formulations from the repertoire of a programming language that lead to the desired result when the programme is executed
the programming language defines, on the one hand, which formulations are permissible as “well-formed” (syntax) and, on the other hand, which “behaviour” is attributed to a program (operational semantics)
in individual cases, the choice of programming language can influence how easily (and sometimes whether at all) the solution to a problem can be formulated as a programme

the activity of programming itself is an essentially mental process – comparable to the verbalisation of a thought or the formulation of a mathematical fact in a calculation – which, in the words of the Enlarged Board of Appeal in G 3/08 lacks “further technical considerations”
this applies at least if and to the extent that, as in the present case, the activity of programming does not serve to achieve a technical effect in a causal manner in the context of a specific application or environment.

–> the definition and provision of a programming language or programming language tools per se does not contribute to the solution of a technical problem

Configuring a system-of-systems with membrane computing/SIEMENS – T 1565/ 17 – 9 January 2018

In this decision the appellant argued inter alia, that it is not possible to prove the expected technical effect and that this obliged the board to accept the effect unless it could “falsify” it.

Object of the Invention:

the application relates to what is called the “configuration of a system-of-systems“
the term “system-of-systems” is said to have arisen in the systems engineering community, where it “reflects the concepts and developments” of real systems such as “smart grids, integrated supply chains, collaborative enterprises, and next-generation air traffic management“
a system-of-systems is “a collection of independent systems that work together to create a new, more complex system which offers more functionality and performance than simply the sum of the constituent systems“
configuration of a system-of-systems is said to be “the task of selecting the optimal subset of component systems, that can perform the required task“

the problem/task is rephrased in mathematical terms as a selection problem
the relevant “characteristics” C of any system-of-systems SoS are defined as a set of pairs of attributes A and values from a set Domain(A) of all values which the respective attributes can take: Hence, the set of all possible such characteristics is C(SoS) = union of all attribute-value pairs Ai x Domain(Ai)
the available components for any particular system are given as a set S of components Si, each having some characteristics: Thus C(Si) is a subset of C(SoS) for any Si
the required characteristics are given as a subset of all possible ones too: C(R) is a subset of C(SoS)
the configuration problem is then said to be the problem of finding an “optimal” subset Simpuls of the available components S so that their characteristics include the required ones: C(R) must be a subset of C(Simpuls)
the notion of optimality is not defined in the application

the declared objective of the invention is to solve this “system-of-systems configuration problem” with “membrane computing“, which is disclosed as being “a variation of” P-systems, a computational model “inspired” by biological processes
the invention is said to rely on “a new kind of solver” which is “constructed using membranes, also called P-systems, and uses metaphors of chemical reactions occurring in living cells”

Appellant I (issue to be decided)

use of “membrane computing” is the only difference over D1
this difference has the effect of making it “possible to solve the occurring NP-hard problems […] in linear time”
the objective technical problem solved by the invention thus has to be seen as “improv[ing] the time behavior of a method for the configuration of a system-of-systems“
the claimed invention involves an inventive step because “there is no teaching in the prior art that would have prompted the skilled person, faced with the objective technical problem, to modify” D1 “by means of membrane computing“
a “skilled person, confronted with the invention and with the information about” D2 “would accept” that by using “membrane computing” the “occurring NP-hard problems in the method” for the configuration of a complex system-of systems “can be solved in linear time“
D2 “is conclusive proof” of “the claimed technical effect“
“it is principally not possible for the applicant to prove the expected technical effect“, suggesting that the invention was “a theory in the empirical sciences“, which, according to Sir Karl Popper, “can only be falsified“
this obliged the board to accept the effect unless it could “falsify” it

Board I (clarity)

Claim 1 refers to “configuration of a system-of-systems without defining either “system-of-systems” or the problem of “configur[ing]” one, apart from mentioning that a “components system” has “roles described by […] participation statements” and “a set of requirements” which a configuration has to “fulfill”
both terms are unclear
there is no indication in the application that the term “system-of-systems“, or the problem of configuring one, has an established clear meaning in the art
the application itself uses these terms in two significantly different ways […]
D1 stresses further differing aspects of a “system-of-systems“, namely that the system components are related to each other by “use” relationships

Claim 1 states that the configuration of the system-of-systems is computed “by means of membrane computing“
the term “membrane computing“, and the notion of computing something “by means of” membrane computing, to be unclear in this generality […]

in response to the board’s objections relating to clarity, the appellant has merely asserted that the claims are “clear enough” for the relevant skilled person
this sweeping asserting does not sway the board’s opinion
in this respect it is only of passing relevance that the skilled person is insufficiently characterised as having an unspecified “academic” education and “scientific work experience”
claim 1 does not specify in clear terms the problem addressed (“configuration of a system-of-systems”) or the solution proposed (at least with regard to the phrase “by means of membrane computing”) and is thus unclear

Board II (further remarks)

since claim 1 does not specify the problem to be solved or its solution, it is impossible to determine the complexity class of the problem or the computational complexity of the solution
for this reason alone, the appellant’s allegation that the claimed invention solved “the occurring NP-hard problems […] in linear time” is without merit

the board notes at this point that computational complexity theory is not, as the appellant seems to suggest, an empirical theory which is not amenable to proof
to the contrary, complexity theorems are established by mathematical proof and their limits are precisely indicated
therefore, if the appellant’s inventive step argument turns on an improved time behaviour, a rather specific one in particular, it is for the appellant to establish that the proposed solution has the claimed time complexity, and in which situations or under which circumstances it applies

Expert system/SCHINDLER – T 1817/ 14 – 4 July 2017

This decision concerns information modelling by a user to create a data structure, where this modelling has no technical effect. Therefore, the modelling steps are considered as an aim to be achieved in a non-technical field and used for the formulation of the technical problem (COMVIK II). The data structure created by the user also has no technical advantage for a claimed subsequent query processing.

Object of the Invention:

expert system for aiding patent administration and jurisprudence by providing (semi)automated support for assessing a patent or patent application (or other “endeavour”) for novelty and inventive step in view of “a national patent system or its Highest court precedents”
the invention proposes to obtain from a patent (or patent application) p and any prior art document i elements of their respective technical teachings TT.p and TT.i
the TT.i’s of the prior-art document i are collectively referred to as “RS” (reference set) and, in combination with the TT.p’s, as “PTR” (pair of TT.p and RS)
the elements and their “relations”, expressing anticipation and contradiction between elements or sets of elements, are arranged in what is called an ANC matrix (“anticipates/non-ants/contradicts”)
the information in this matrix can be queried by and is then displayed to the user

Board I (claim construction)

the claimed method has two phases: the first phase leads to the creation of the ANC matrix which, in the second phase is used to “automatically and instantly” produce responses to user queries
the major part of the first phase is done by the user
only the processing of user queries is meant to be automated

Board II (technical effects and inventive step)

the major part of claim 1 is a modelling procedure during which the user considers the items in the domain of interest, extracts their relevant properties, and “compiles” them “into” a formal language
following T 49/99, this procedure of information modelling to be an intellectual activity
(effectively a method for performing mental acts, Article 52(2)(c) EPC) which does not, per se, contribute to the technical character of an invention
for this conclusion it is immaterial that the present application does not even relate to the modelling (let alone simulation) of a physical system but to the modelling of what a given set of documents discloses and how they relate to each other
accordingly, a technical contribution of the present invention could only lie in the way in which the generation and use of the model are implemented

Appellant I (technical effects and inventive step)

particular features of the ANC data structure had to be considered to be technical
in particular that the ANC had to reflect the analysis of documents in terms of two different levels of granularity (“elements” and “fundamental facts of these elements”) and that it contained novel fields (e.g. “anticipates/not-anticipates-and-not-contradicts/contradicts” as claimed)

Board III (technical effects and inventive step)

the appellant did not argue that the particular ANC data structure had a specific technical advantage for the subsequent query processing
the appellant was thus unable to convince the board that the modelling steps caused any technical effect
when, however, the modelling steps are assumed to be taken as an aim to be achieved in a non-technical field – according to established jurisprudence of the boards of appeal (see T 641/00, headnote 2) – the form of the ANC is determined by the model and thus obvious
the computer support specified in claim 1 does not go beyond the general statement that a computer is used to support the users in their task
likewise, the feature that users may query the “items” in the ANC and the method replies “automatically and instantly by displaying to the user this item’s information and all its such relations to other items” does not, in the board’s judgement, go beyond the statement that the information in the ANC may be accessed by user queries, as is known from prior-art database systems
–> claim 1 lacks inventive step in view of common knowledge, as an obvious way of providing computer support to an essentially non-technical method