T 1402/20 (Shared key exchange using proxy/NTT) 21-09-2022
Download and more information:
KEY-EXCHANGE METHOD, KEY-EXCHANGE SYSTEM, KEY DEVICE, TERMINAL DEVICE, AND PROGRAM
I. This appeal is against the examining division's decision posted on 29 January 2020, refusing
European patent application No. 16 737 330.7. The application was refused for lack of inventive step (Article 56 EPC) of a single request in view of:
D4: A. Fujioka et al., "Ephemeral Key Leakage Resilient and Efficient ID-AKEs That Can Share Identities, Private and Master Keys", 1 December 2010, 187-205, in combination with:
D1: EP 2 634 760 for the first group of claims of the request and in view of:
D5: S. Chatterjee et al., "Reusing Static Keys in Key Agreement Protocols", 13 December 2009, 39-56, in combination with D1 for the second group of claims of the request
II. Notice of appeal was received on 7 April 2020, and the appeal fee was paid the same day. The statement setting out the grounds of appeal was received on
4 June 2020. The appellant requested that the decision be set aside and that a patent be granted on the basis of claims 1 to 8 on which the decision was based and which were re-filed with the statement setting out the grounds of appeal. Oral proceedings were requested as an auxiliary request.
III. A summons to oral proceedings was issued on
25 January 2022. In a communication pursuant to Article 15(1) RPBA, sent on 25 July 2022, the board gave its preliminary opinion that claims 1, 4, 6 and 8 did not meet the requirements of Article 56 EPC having regard to D4 in combination with D1 and taking into account the common general knowledge of the skilled person. Furthermore, the board gave its preliminary opinion that claims 2, 5, 7 and 8 did not meet the requirements of Article 56 EPC having regard to the combination of D5 and D1 and taking into account the common general knowledge of the skilled person.
IV. Oral proceedings were held on 21 September 2022. The appellant requested that the decision under appeal be set aside and that a patent be granted on the basis of claims 1 to 8 on which the decision was based. At the end of the oral proceedings, the chair announced the board's decision.
V. Claim 1 of the sole request reads as follows:
A key exchange method, wherein
G1 , G2 , and GT are assumed to be cyclic groups whose order is a prime number q with K bit length, g1, g2 , and gT are assumed to be generators of the groups G1, G2, and GT, respectively, e: G1 x G2 -> GT is assumed to be pairing that satisfies gT = e(g1, g2 ), H: {0, 1}**(*)-> {0, 1}**(K), H1 : {0, 1}**(*)-> G1 , and H2 : {0, 1}**(*)-> G2 are assumed to be cryptographic hash functions, m is assumed to be a natural number which is greater than or equal to 2, an assumption is made that i = 1, ..., m holds, ci,o,o , ci,0,1 , ci,1,0 , and ci,1,1 are assumed to be constants, pi beongs to Zq[uo , u1 , vo , v1] is assumed to be m polynomials which are defined by a formula below:
FORMULA/TABLE/GRAPHIC z belongs to Zq is assumed to be a master secret key,Z1 = g1**(z) belongs to Gi and Z2 = g2**(Z) belongs to G2 are assumed to be master public keys, IDA is assumed to be an identifier of a terminal device (11 ), QA,1 = H1(IDA) belongs to G1 andQA,2 = H2(IDA ) belongs to G2 are assumed to be public keys, IDB is assumed to be an identifier of other terminal device (12), QB,1 = H1(IDB ) belongs to G1 and QB,2 = H2(IDB ) belongs to G2 are assumed to be public keys, DA,1 = QA,1**(z)and DA,2 = QA,2**(z)are assumed to be secret keys of the terminal device (11), DB,1 = QB,1**(z)and DB,2 = QB,2**(z)are assumed to be secret keys of the other terminal device (12), xA belongs to Zq is assumed to be a short-term secret key of the terminal device (11), XA,1 = g1**(xA)and XA,2 = g2**(xA)are assumed to be short-term public keys of the terminal device (11), xB belongs to Zq is assumed to be a short-term secret key of the other terminal device (12),XB,1 = g1**(xB)and XB,2 = g2**(xB)are assumed to be short-term public keys of the other terminal device (12), Pi,B is assumed to be a value which is defined by a formula below:
FORMULA/TABLE/GRAPHIC ri1 and ri2 are assumed to be arbitrary numbers, si1 and si2 are assumed to be random numbers which are mutually prime, and s'i1 and s'i2 are assumed to be random numbers which satisfy a predetermined relationship with the random numbers si1 and si2 ,
in a storage (20) of a key device (2), the secret keys DA,1 and DA,2 of the terminal device (1i) are stored, and
the key exchange method includes:a random number generating step in which the terminal device (1i) generates the random numbers sil , si2 , s'i1, and s'i2 ;a proxy calculation step in which the key device (2) calculates a first commission result zetai1 fori = 1, ..., m by a formula below: FORMULA/TABLE/GRAPHIC
and calculates a second commission result zetai2 fori = 1, ..., m by a formula below: FORMULA/TABLE/GRAPHIC anda verification step in which the terminal device (11) verifies whether or not a first verification value and a second verification value coincide with each other for i = 1, ..., m by a formula below:
FORMULA/TABLE/GRAPHICcharacterized in that the key exchange method further includes:a public keys randomizing step in which the terminal device (11) calculates first randomized public keys information for i = 1, ..., m by a formula below:
FORMULA/TABLE/GRAPHIC and calculates second randomized public keys information for i = 1, ..., m by a formula below:
FORMULA/TABLE/GRAPHICa common key calculation step in which, if the first verification value and the second verification value coincide with each other, the terminal device (l1) generates a common key by using values sigma1 , ..., sigmam , wherein the value sigmai for i = 1, ..., m is obtained by a formula below:
FORMULA/TABLE/GRAPHIC
after calculating the commission result zetai fori = 1, ..., m is obtained by a formula below:
FORMULA/TABLE/GRAPHIC
Claim 2 of the sole request reads as follows: A key exchange method, wherein
G is assumed to be a cyclic group whose order is a prime number q with K bit length, g is assumed to be a generator of the group G, g1 and g2 are assumed to be elements which are not unit elements of the group G, m is assumed to be a natural number which is greater than or equal to 2, an assumption is made that i = 1, ..., m holds, ci,o,o, ci,o,1, c i,1,o, and ci,1,1 are assumed to be constants, pi belongs to Zq[uo , u1 , vo , v1] is assumed to be m polynomials which are defined by a formula below:
FORMULA/TABLE/GRAPHIC
sA belongs to Zq is assumed to be a secret key of a terminal device (11), SA = g**(sA) belongs to G is assumed to be a public key of the terminal device (11), sB belongs to Zq is assumed to be a secret key of the other terminal device (12 ),SB = g**(sB) belongs to G is assumed to be a public key of the other terminal device (12), XA belongs to Zq is assumed to be a short-term secret key of the terminal device (11),XA = g**(xA) belongs to G is assumed to be a short-term public key of the terminal device (11), XB belongs to Zq is assumed to be a short-term secret key of the other terminal device (12), XB = g**(xB) belongs to G is assumed to be a short-term public key of the other terminal device (12), FA is assumed to be a homomorphism which is FA : G -> G, h -> h**(sA), alphaB,i is assumed to be a value which is defined by a formula below:
FORMULA/TABLE/GRAPHIC
si1 and si2 are assumed to be random numbers which are mutually prime, and s'i1 and s'i2 are assumed to be random numbers which satisfy a predetermined relationship with the random numbers si1 and si2 ,
in a storage (20) of a key device (2), the secret key sA of the terminal device (11) is stored, and
the key exchange method includes:a random number generating step in which the terminal device (11) generates the random numbers sil , si2 , s'i1, and s'i2;a proxy calculation step in which the key device (2) calculates a first commission result zetai1 fori = 1, ..., m by a formula below:
FORMULA/TABLE/GRAPHIC
and calculates a second commission result zetai2 fori = 1, ..., m by a formula below:
FORMULA/TABLE/GRAPHIC
a verification step in which the terminal device (11) verifies whether or not a first verification value and a second verification value coincide with each other for i = 1, ..., m by a formula below:
FORMULA/TABLE/GRAPHIC
characterized in that the key exchange method further includes:a public keys randomizing step in which the terminal device (11) calculates first randomized public keys information for i = 1, ..., m by a formula below:
FORMULA/TABLE/GRAPHIC
and calculates second randomized public keys information for i = 1, ..., m by a formula below:
FORMULA/TABLE/GRAPHIC
a common key calculation step in which, if the first verification value and the second verification value coincide with each other, the terminal device (l1 ) generates a common key by using values sigma1 , ..., sigmam , wherein the value sigmai for i = 1, ..., m is obtained by a formula below:
FORMULA/TABLE/GRAPHIC
after calculating the commission result zetai fori = 1, ..., m is obtained by a formula below:
FORMULA/TABLE/GRAPHIC
The sole request comprises further independent claims directed to:- a system (claim 4), a terminal device (claim 6) and a computer program (claim 8) corresponding to claim 1 - a system (claim 5), a terminal device (claim 7) and a computer program (claim 8) corresponding to claim 2
1. Claim 1
1.1 It was common ground in the examination procedure and in the oral proceedings before the board that D4 represented the closest prior art to the subject-matter of claim 1. The appellant has not rebutted the detailed analysis of the disclosure of D4 for the features of claim 1 as stated in points 5.1 and 5.1.1 of the decision.
Based on the distinguishing features between claim 1 and D4 established in point 5.1.1, the decision formulated the objective technical problem to be solved as how to delegate the computation involving the private key to a proxy, the proxy holding the private keys but not being able to know the computed result.
However, this formulation is not in line with the principles underlying the problem-solution approach as established by the case law of the boards since it contains a pointer to part of the solution, namely to use a proxy in the computation of the common key. Thus, the board agrees with the formulation of the problem proposed by the appellant, namely to reduce computational load for the terminal device without leaking the common key.
1.2 The appellant has argued that the skilled person starting from D4 as the closest prior art and trying to solve the above-mentioned problem would not consider the disclosure of D1 since this document does not relate to the exchange of shared secrets. However, the board holds that the skilled person seeking to first reduce the computational load for the terminal device would consult D1 since it generally relates to the use of a proxy for providing a computing capability to a cryptographic apparatus without leaking secret information (see paragraph [0006]).
1.3 By trying to add the proxy scheme of D1 to the shared secret generation scheme of D4, the skilled
person would have to address the following issues.
D1 discloses a capability providing apparatus, i.e. a proxy, that computes a decryption function f(x) for decrypting a ciphertext x using a decryption key s stored in the capability apparatus (see paragraphs [0044] and [0045]). Therefore, D1 is based on the assumption that the decryption key s is shared between the proxy and the terminal device requesting the decryption.
On the other hand, D4 discloses that the shared secrets sigmai necessary for calculating the session key K are, for example, given by the relation
sigma1 =e(DAZ**(xA), QBXB) (see section 4.2, step 3). Since both QB=H1(IDB) and XB = g**(xB) are satisfied, QBXB is encrypted data of a public key H1(IDB) using an ephemeral private key xB. The decision found that QBXB of D4 corresponds to the ciphertext x of D1 and e(DAZ**(xA), QBXB) of D4 corresponds to f(x) of D1, namely that e(DAZ**(xA), x) corresponds f(x).
Since D1 is based on the assumption that the decryption key s used in the decryption function f(x) is shared between the terminal device and the capability providing apparatus, the process of D4 could integrate the process of D1 as long as the key DAZ**(xA) used in
e(DAZ**(xA), x) is shared between the capability providing apparatus and the terminal device. However, in the current invention defined by claim 1, the key device, i.e. the capability providing apparatus, knows the secret key DA1 in advance, but it will never know the short-term secret key xA. The skilled person, when combining D4 and D1, would thus have to cope with the issue that the values sigmai in D4, i.e. in a conventional ID-AKE protocol, defined by the equation in the first line on page 5 of the statement of grounds, cannot be calculated at all by the key device since both parts of sigmai are based on a pairing calculation involving xA.
For these reasons, the board agrees with the appellant that the combination of D4 with D1 does not lead to the subject-matter of claim 1 since the key xA is not defined in claim 1 as being known by the key device because xA is defined as a short-term key, and no transfer of xA from the terminal device to the key device is specified in claim 1.
Thus, to implement the computation disclosed in D4 without sharing the short-term secret key xA, the skilled person must perform further steps. To this end, claim 1 involves a formula transformation that utilises the bi-linearity of the pairing operation and divides the computation into one part to be computed with the secret key DA1 by the capability providing apparatus, i.e. the key device, and another part to be computed with the short-term secret key xA by the terminal device. The appellant detailed that by using the bi-linearity of the pairing e, the formula defining sigmai is transformed in claim 1 (see page 3 of claim 1, line 5 in combination with page 2, line 10) by using a formula transformation which divides the computation into two parts, one part being computed by the terminal with the short-term secret key xA of the terminal device, and the other part being computed by the key device with the secret key of the terminal device, known to the key device.
The appellant plausibly argued that the skilled person would not make use of the above-mentioned formula transformation without the exercise of inventive skill since D1 did not hint at not sharing the key xA.
1.4 For these reasons, the board holds that claim 1 and corresponding system claim 4, terminal device claim 6 and computer program claim 8 meet the requirements of Article 56 EPC having regard to the prior art of D4 and D1.
2. Claim 2
Similarly and based on the findings of the decision for the features distinguishing the subject-matter of independent claim 2 from D5 (see points 5.2.1 and 5.2.2), claim 2 and corresponding system claim 5, terminal device claim 7 and computer program claim 8 meet the requirements of Article 56 EPC having regard to the prior art of D5 and D1.
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 patent in the following version.
Claims:
No. 1-8 as submitted with the statement of grounds of appeal
Description:
Pages 1, 2, 5 to 24, 26 to 33, 35 to 48, 51 to 59, 61 to 68 and 70 to 80 as originally filed
Pages 3, 4, 4a, 4b, 25, 34, 60 and 69 filed with the letter of 11 September 2018
Pages 49 and 50 filed with the letter of 1 March 2019
Drawings:
Sheets 1/13 to 13/13 as originally filed