METHOD, APPARATUS, AND SYSTEM FOR AUTHENTICATING FULLY HOMOMORPHIC MESSAGE

• US 20160119346A1
• Filed: 12/31/2015
• Published: 04/28/2016
• Est. Priority Date: 06/30/2014
• Status: Active Grant

• Current Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Inventors: LEI, Hao, CHEN, Wenbin, YANG, Qinqin
• Granted Patent: US 10,009,343 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 63/0442 wherein the sending and receiving network entities apply asymmetric encryption, i.e. different keys for encryption and decryption cryptographic mechanisms or cryptographic arrangements for public-key encryption H04L9/30
• CPC Class Codes: H04L 63/0861 using biometrical features, e.g. fingerprint, retina-scan cryptographic mechanisms or cryptographic arrangements for entity authentication using biological data H04L9/3231
• CPC Class Codes: H04L 63/0876 based on the identity of the terminal or configuration, e.g. MAC address, hardware or software configuration or device fingerprint
• CPC Class Codes: H04L 63/123 received data contents, e.g. message integrity
• CPC Class Codes: H04L 63/126 the source of the received data
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• CPC Class Codes: H04L 9/32 including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
• CPC Class Codes: H04L 9/3231 Biological data, e.g. fingerprint, voice or retina network architectures or network communication protocols for supporting authentication of entities using biometrical features in a packet data network H04L63/0861

Abstract

Embodiments of the present disclosure provide a method, an apparatus, and a system for authenticating a fully homomorphic message, where the method includes: acquiring a message authentication key, where: the message authentication key includes a public key, a first character string, and a second character string; the first character string is a character string that consists of 0 and 1 and has a length of n; the second character string is a character string that consists of 0 and 1 and has a length of n; generating an authentication fingerprint corresponding to each bit of to-be-computed data; sending a computation request to a server; receiving an authentication fingerprint corresponding to the computation result; and performing correctness authentication on the computation result according to the received authentication fingerprint, which effectively reduces an amount of computation in a verification process.

Claims

1. A method for authenticating a fully homomorphic message, wherein the method is applied to a terminal and comprises:

acquiring a message authentication key that comprises a public key, a first character string, and a second character string;

the first character string is a character string that consists of 0 and 1 and has a length of n, and a quantity of characters 1 in the first character string is 2n/3;

the second character string is a character string that consists of 0 and 1 and has a length of n, and in the second character string, characters at locations corresponding to the character 1 in the first character string comprise character 0 whose quantity is n/3; and

n is an integer greater than or equal to 2;

generating, according to a first input character, the public key, and a pseudo random string, one of n ciphertexts corresponding to the i^th bit of to-be-computed data, and determining that the n ciphertexts are a second component of an authentication fingerprint corresponding to the i^th bit, wherein;

if the j^th character of the first character string is 0, the first input character is the i^th bit, or if the j^th character of the first character string is 1 and the j^th character of the second character string is 0, the first input character is 0, or if the j^th character of the first character string is 1 and the j^th character of the second character string is 1, the first input character is 1;

the authentication fingerprint corresponding to the i^th bit further comprises a first component;

i is an integer that is greater than or equal to 1 and less than or equal to a total quantity t of bits of the to-be-computed data, wherein t is greater than or equal to 1; and

j is an integer that is greater than or equal to 1 and less than or equal to n;

sending a computation request to a server comprising the to-be-computed data, an authentication fingerprint corresponding to each bit of the to-be-computed data, a pre-configured fully homomorphic encryption algorithm, and the message authentication key;

receiving a computation result of the to-be-computed data and an authentication fingerprint corresponding to the computation result that are returned by the server; and

performing correctness authentication on the computation result according to the received authentication fingerprint corresponding to the computation result.

2. The method according to claim 1, wherein the authentication fingerprint corresponding to the i^th bit is generated by executing the following steps:

generating, according to a pre-configured pseudo random function and a label of the i^th bit of the to-be-computed data, the first component of the authentication fingerprint corresponding to the i^th bit;

generating, according to the pseudo random function, n pseudo random strings corresponding to the i^th bit of the to-be-computed data; and

generating, according to the first character string, the second character string, and the n pseudo random strings, the n ciphertexts corresponding to the i^th bit, wherein the n ciphertexts serve as the second component of the authentication fingerprint corresponding to the i^th bit, wherein;

the i^th bit, the public key, and the j^th pseudo random string are input into the pre-configured encryption algorithm to generate a ciphertext if the j^th character of the first character string is 0;

or 0, the public key, and the j^th pseudo random string are input into the pre-configured encryption algorithm to generate a ciphertext if the j^th character of the first character string is 1 and the j^th character of the second character string is 0;

or 1, the public key, and the j^th pseudo random string are input into the pre-configured encryption algorithm to generate a ciphertext if the j^th character of the first character string is 1 and j^th character of the second character string is 1.

3. The method according to claim 2, wherein the performing correctness authentication on the computation result according to the received authentication fingerprint corresponding to the computation result comprises:

acquiring a first component of the authentication fingerprint corresponding to the computation result, wherein the first component is obtained by means of recomputation;

determining, by means of comparison, whether a first component of the received authentication fingerprint corresponding to the computation result is equal to the first component of the authentication fingerprint corresponding to the computation result, wherein the latter is obtained by means of recomputation; and

performing correctness authentication on the computation result if the first component of the received authentication fingerprint corresponding to the computation result is equal to the first component of the authentication fingerprint corresponding to the computation result, wherein the latter is obtained by means of recomputation;

or determining that the computation result is incorrect if the two are unequal.

4. The method according to claim 3, wherein the acquiring a first component of the authentication fingerprint corresponding to the computation result, wherein the first component is obtained by means of recomputation comprises:

acquiring, according to first components of t authentication fingerprints corresponding to the t bits of the to-be-computed data and by using a computation function used to compute the to-be-computed data, the first component of the authentication fingerprint corresponding to the computation result, wherein the first component is obtained by means of recomputation, wherein

the computation function used to compute the to-be-computed data is a hash tree, wherein the hash tree comprises t inputs and one output, and each node in the hash tree is a pre-configured secure hash function.

5. The method according to claim 3, wherein the acquiring a first component of the authentication fingerprint corresponding to the computation result, wherein the first component is obtained by means of recomputation comprises:

sending first components of t authentication fingerprints corresponding to the t bits of the to-be-computed data to a third-party device, so that the third-party device acquires, according to the received first components of the t authentication fingerprints corresponding to the t bits of the to-be-computed data and by using a pre-configured computation function used to compute the to-be-computed data, the first component of the authentication fingerprint corresponding to the computation result, wherein the first component is obtained by means of recomputation; and

receiving the first component of the authentication fingerprint corresponding to the computation result, wherein the first component is obtained by means of recomputation and returned by the third-party device, and

the computation function used to compute the to-be-computed data is a hash tree, wherein the hash tree comprises t inputs and one output, and each node in the hash tree is a secure hash function.

6. The method according to claim 3, wherein the message authentication key further comprises a private key, and the continuing performing correctness authentication on the computation result if the first component of the received authentication fingerprint corresponding to the computation result is equal to the first component of the authentication fingerprint corresponding to the computation result, wherein the first component is obtained by means of recomputation comprises:

separately computing, according to the private key, n plaintexts corresponding to n second components of the received authentication fingerprint corresponding to the computation result; and

determining that the computation result is correct if the n plaintexts are all the same as the computation result.

7. A method for authenticating a fully homomorphic message, wherein the method is applied to a server and comprises:

receiving a computation request sent by a terminal, wherein the computation request comprises;

to-be-computed data, an authentication fingerprint corresponding to each bit of the to-be-computed data, a pre-configured fully homomorphic encryption algorithm, and a message authentication key;

obtaining, by means of computation, a computation result of the to-be-computed data according to the to-be-computed data and a pre-configured computation function used to compute the to-be-computed data;

computing an authentication fingerprint corresponding to the computation result according to the pre-configured computation function used to compute the to-be-computed data, the computation result of the to-be-computed data, the authentication fingerprint corresponding to each bit of the to-be-computed data, the pre-configured fully homomorphic encryption algorithm, and the message authentication key; and

returning, to the terminal, the computation result of the to-be-computed data and the authentication fingerprint corresponding to the computation result, so that the terminal performs correctness authentication on the computation result according to the received authentication fingerprint corresponding to the computation result.

8. The method according to claim 7, wherein the obtaining, by means of computation, a computation result of the to-be-computed data according to the to-be-computed data and a pre-configured computation function used to compute the to-be-computed data comprises:

acquiring the computation result of the to-be-computed data according to t bits of the to-be-computed data and by using the pre-configured computation function used to compute the to-be-computed data, wherein

the pre-configured computation function used to compute the to-be-computed data is a hash tree, wherein;

the hash tree comprises t inputs and one output, and each node in the hash tree is a pre-configured secure hash function; and

t is a total quantity of bits of the to-be-computed data.

9. The method according to claim 8, wherein the authentication fingerprint corresponding to each bit of the to-be-computed data comprises a first component and n second components, the message authentication key comprises a computation key, and the computing an authentication fingerprint corresponding to the computation result according to the pre-configured computation function used to compute the to-be-computed data, the computation result of the to-be-computed data, the authentication fingerprint corresponding to each bit of the to-be-computed data, the pre-configured fully homomorphic encryption algorithm, and the message authentication key comprises:

acquiring, according to first components of t authentication fingerprints corresponding to the t bits of the to-be-computed data and by using the pre-configured computation function used to compute the to-be-computed data, a first component of the authentication fingerprint corresponding to the computation result; and

acquiring, according to the computation result, the n second components of the authentication fingerprint corresponding to each bit of the to-be-computed data, and the computation key, and by using a ciphertext computation function in the pre-configured fully homomorphic encryption algorithm, n second components of the authentication fingerprint corresponding to the computation result.

10. An apparatus for authenticating a fully homomorphic message, comprising:

an acquiring module, configured to acquire a message authentication key, wherein;

the message authentication key comprises a public key, a first character string, and a second character string;

the first character string is a character string that consists of 0 and 1 and has a length of n, and a quantity of characters 1 in the first character string is 2n/3;

the second character string is a character string that consists of 0 and 1 and has a length of n, and in the second character string, characters at locations corresponding to the characters 1 in the first character string comprise characters 0 whose quantity is n/3; and

n is an integer greater than or equal to 2;

a generating module, configured to;

generate, according to a first input character, the public key, and a pseudo random string, one of n ciphertexts corresponding to the i^th bit of to-be-computed data, and determine that the n ciphertexts are a second component of an authentication fingerprint corresponding to the i^th bit, wherein;

if the j^th character of the first character string is 0, the first input character is the i^th bit, or if the j^th character of the first character string is 1 and the j^th character of the second character string is 0, the first input character is 0, or if the j^th character of the first character string is 1 and the j^th character of the second character string is 1, the first input character is 1;

the authentication fingerprint corresponding to the i^th bit further comprises a first component;

i is an integer that is greater than or equal to 1 and less than or equal to a total quantity t of bits of the to-be-computed data, wherein t is greater than or equal to 1; and

j is an integer that is greater than or equal to 1 and less than or equal to n;

a transceiver module, configured to send a computation request to a server, wherein the computation request comprises;

the to-be-computed data, an authentication fingerprint corresponding to each bit of the to-be-computed data, a pre-configured fully homomorphic encryption algorithm, and the message authentication key, wherein

the transceiver module is further configured to receive a computation result of the to-be-computed data and an authentication fingerprint corresponding to the computation result that are returned by the server; and

a processing module, configured to perform correctness authentication on the computation result according to the authentication fingerprint corresponding to the computation result that is received by the transceiver module.

11. The apparatus according to claim 10, wherein the generating module is specifically configured to:

generate, according to a pre-configured pseudo random function and a label of the i^th bit of the to-be-computed data, the first component of the authentication fingerprint corresponding to the i^th bit;

generate, according to the pseudo random function, n pseudo random strings corresponding to the i^th bit of the to-be-computed data; and

generate, according to the first character string, the second character string, and the n pseudo random strings, the n ciphertexts corresponding to the i^th bit, wherein the n ciphertexts serve as the second component of the authentication fingerprint corresponding to the i^th bit, wherein;

the i^th bit, the public key, and the j^th pseudo random string are input into the pre-configured encryption algorithm to generate a ciphertext if the j^th character of the first character string is 0;

or 0, the public key, and the j^th pseudo random string are input into the pre-configured encryption algorithm to generate a ciphertext if the j^th character of the first character string is 1 and the j^th character of the second character string is 0;

or 1, the public key, and the j^th pseudo random string are input into the pre-configured encryption algorithm to generate a ciphertext if the j^th character of the first character string is 1 and the j^th character of the second character string is 1.

12. The apparatus according to claim 10, wherein the processing module is specifically configured to:

acquire a first component of the authentication fingerprint corresponding to the computation result, wherein the first component is obtained by means of recomputation;

determine, by means of comparison, whether a first component of the received authentication fingerprint corresponding to the computation result is equal to the first component of the authentication fingerprint corresponding to the computation result, wherein the latter is obtained by means of recomputation; and

continue performing correctness authentication on the computation result if the first component of the received authentication fingerprint corresponding to the computation result is equal to the first component of the authentication fingerprint corresponding to the computation result, wherein the latter is obtained by means of recomputation;

or determine that the computation result is incorrect if the two are unequal.

13. The apparatus according to claim 12, wherein the processing module is further configured to acquire, according to acquired first components of t authentication fingerprints corresponding to the t bits of the to-be-computed data and by using a computation function used to compute the to-be-computed data, the first component of the authentication fingerprint corresponding to the computation result, wherein the first component is obtained by means of recomputation, wherein

the computation function used to compute the to-be-computed data is a hash tree, wherein the hash tree comprises t inputs and one output, and each node in the hash tree is a pre-configured secure hash function.

14. The apparatus according to claim 12, wherein the transceiver module is further configured to:

send first components of t authentication fingerprints corresponding to the t bits of the to-be-computed data to a third-party device, so that the third-party device acquires, according to the received first components of the t authentication fingerprints corresponding to the t bits of the to-be-computed data and by using a pre-configured computation function used to compute the to-be-computed data, the first component of the authentication fingerprint corresponding to the computation result, wherein the first component is obtained by means of recomputation; and

receive the first component of the authentication fingerprint corresponding to the computation result, wherein the first component is obtained by means of recomputation and returned by the third-party device, and

the computation function used to compute the to-be-computed data is a hash tree, wherein the hash tree comprises t inputs and one output, and each node in the hash tree is the secure hash function.

15. The apparatus according to claim 12, wherein the message authentication key further comprises a private key, and the processing module is further configured to:

separately compute, according to the private key, n plaintexts corresponding to n second components of the received authentication fingerprint corresponding to the computation result; and

determine that the computation result is correct if the n plaintexts are all the same as the computation result.

16. An apparatus for authenticating a fully homomorphic message, comprising:

a transceiver module, configured to receive a computation request sent by a terminal, wherein the computation request comprises;

to-be-computed data, an authentication fingerprint corresponding to each bit of the to-be-computed data, a pre-configured fully homomorphic encryption algorithm, and a message authentication key; and

a processing module, configured to obtain, by means of computation, a computation result of the to-be-computed data according to the to-be-computed data and a pre-configured computation function used to compute the to-be-computed data, wherein

the processing module is further configured to compute an authentication fingerprint corresponding to the computation result according to the pre-configured computation function used to compute the to-be-computed data, the computation result of the to-be-computed data, the authentication fingerprint corresponding to each bit of the to-be-computed data, the pre-configured fully homomorphic encryption algorithm, and the message authentication key; and

the transceiver module is further configured to return, to the terminal, the computation result of the to-be-computed data and the authentication fingerprint corresponding to the computation result, so that the terminal performs correctness authentication on the computation result according to the received authentication fingerprint corresponding to the computation result.

17. The apparatus according to claim 16, wherein the processing module is specifically configured to:

acquire the computation result of the to-be-computed data according to t bits of the to-be-computed data and by using the pre-configured computation function used to compute the to-be-computed data, wherein

the pre-configured computation function used to compute the to-be-computed data is a hash tree, wherein;

the hash tree comprises t inputs and one output, and each node in the hash tree is a pre-configured secure hash function; and

t is a total quantity of bits of the to-be-computed data.

18. The apparatus according to claim 17, wherein the authentication fingerprint corresponding to each bit of the to-be-computed data comprises a first component and n second components, the message authentication key comprises a computation key, and the processing module is further configured to:

acquire, according to first components of t authentication fingerprints corresponding to the t bits of the to-be-computed data and by using the pre-configured computation function used to compute the to-be-computed data, a first component of the authentication fingerprint corresponding to the computation result; and

acquire, according to the computation result, the n second components of the authentication fingerprint corresponding to each bit of the to-be-computed data, and the computation key, and by using a ciphertext computation function in the pre-configured fully homomorphic encryption algorithm, n second components of the authentication fingerprint corresponding to the computation result.

19. A system for authenticating a fully homomorphic message, wherein the system comprises a terminal and a server, wherein:

the terminal is configured to;

acquire a message authentication key, wherein;

the message authentication key comprises a first character string and a second character string;

the first character string is a character string that consists of 0 and 1 and has a length of n, and a quantity of characters 1 in the first character string is 2n/3;

the second character string is a character string that consists of 0 and 1 and has a length of n, and in the second character string, characters at locations corresponding to the characters 1 in the first character string comprise characters 0 whose quantity is n/3; and

n is an integer greater than or equal to 2;

generate, according to a first input character, the public key, and a pseudo random string, one of n ciphertexts corresponding to the i^th bit of to-be-computed data, and determine that the n ciphertexts are a second component of an authentication fingerprint corresponding to the i^th bit, wherein;

if the j^th character of the first character string is 0, the first input character is the i^th bit, or if the j^th character of the first character string is 1 and the j^th character of the second character string is 0, the first input character is 0, or if the j^th character of the first character string is 1 and the j^th character of the second character string is 1, the first input character is 1;

the authentication fingerprint corresponding to the i^th bit further comprises a first component;

i is an integer that is greater than or equal to 1 and less than or equal to a total quantity t of bits of the to-be-computed data, wherein t is greater than or equal to 1; and

j is an integer that is greater than or equal to 1 and less than or equal to n;

send a computation request to the server, wherein the computation request comprises;

the to-be-computed data, an authentication fingerprint corresponding to each bit of the to-be-computed data, a pre-configured fully homomorphic encryption algorithm, and the message authentication key;

receive a computation result of the to-be-computed data and an authentication fingerprint corresponding to the computation result that are returned by the server; and

perform correctness authentication on the computation result according to the received authentication fingerprint corresponding to the computation result; and

the server is configured to;

receive the computation request sent by the terminal;

obtain, by means of computation, the computation result of the to-be-computed data according to the to-be-computed data and a pre-configured computation function used to compute the to-be-computed data;

compute the authentication fingerprint corresponding to the computation result according to the pre-configured computation function used to compute the to-be-computed data, the computation result of the to-be-computed data, the authentication fingerprint corresponding to each bit of the to-be-computed data, the pre-configured fully homomorphic encryption algorithm, and the message authentication key; and

return, to the terminal, the computation result of the to-be-computed data and the authentication fingerprint corresponding to the computation result, so that the terminal performs correctness authentication on the computation result according to the received authentication fingerprint corresponding to the computation result.

20. The system according to claim 19, wherein the terminal is specifically configured to:

generate, according to a pre-configured pseudo random function and a label of the i^th bit of the to-be-computed data, the first component of the authentication fingerprint corresponding to the i^th bit;

generate, according to the pseudo random function, n pseudo random strings corresponding to the i^th bit of the to-be-computed data; and

generate, according to the first character string, the second character string, and the n pseudo random strings, the n ciphertexts corresponding to the i^th bit, wherein the n ciphertexts serve as the second component of the authentication fingerprint corresponding to the i^th bit, wherein;

the i^th bit, the public key, and the j^th pseudo random string are input into the pre-configured encryption algorithm to generate a ciphertext if the j^th character of the first character string is 0;

or 0, the public key, and j^th pseudo random string are input into the pre-configured encryption algorithm to generate the ciphertext if the j^th character of the first character string is 1 and j^th character of the second character string is 0;

or 1, the public key, and the j^th pseudo random string are input into the pre-configured encryption algorithm to generate the ciphertext if the j^th character of the first character string is 1 and the j^th character of the second character string is 1, wherein i is an integer that is greater than or equal to 1 and less than or equal to the total quantity t of the bits of the to-be-computed data, and j is an integer that is greater than or equal to 1 and less than or equal to n.

21. A method for authenticating, comprising:

acquiring a message authentication key, wherein the message authentication key comprises a public key, a first character string consisting of 0 and 1 with a length of n with a quantity of characters 1 of 2n/3, and a second character string consisting of 0 and 1 and has a length of n;

generating, according to a first input character, the public key, and a pseudo random string, a plurality of ciphertexts corresponding to the i^th bit of to-be-computed data, and determining that the plurality of ciphertexts are a second component of an authentication fingerprint corresponding to the i^th bit,

sending a computation request to a server, wherein the computation request comprises the to-be-computed data, an authentication fingerprint corresponding to each bit of the to-be-computed data, a pre-configured fully homomorphic encryption algorithm, and the message authentication key;

receiving a computation result of the to-be-computed data and an authentication fingerprint corresponding to the computation result that are returned by the server; and

performing correctness authentication on the computation result according to the received authentication fingerprint corresponding to the computation result.

22. The method of claim 21, wherein if the j^th character of the first character string is 0, the first input character is the i^th bit.

23. The method of claim 21, wherein if the j^th character of the first character string is 1 and the j^th character of the second character string is 0, the first input character is 0.

24. The method of claim 21, wherein if the j^th character of the first character string is 1 and the j^th character of the second character string is 1, the first input character is 1.

25. The method of claim 21, wherein the authentication fingerprint corresponding to the i^th bit further comprises a first component, i, that is an integer that is greater than or equal to 1 and less than or equal to a total quantity t of bits of the to-be-computed data, wherein t is greater than or equal to 1;

and j is an integer that is greater than or equal to 1 and less than or equal to n.