Protecting against malicious modification in cryptographic operations

• US 9,509,665 B2
• Filed: 08/11/2014
• Issued: 11/29/2016
• Est. Priority Date: 08/11/2014
• Status: Active Grant

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Kumarasubramanian, Abishek, Kolesnikov, Vladimir Y.
• Primary Examiner(s): THIAW, CATHERINE B
• Application Number:
  US14/456,554
• Publication Number:
  US 20160044031A1
• Time in Patent Office: 841 Days
• US Class Current: 1/1
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• 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 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs
• CPC Class Codes: H04L 9/3242 involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC

Abstract

A message and an identifying parameter associated with the message are obtained. The message comprises a plurality of units. A plurality of one-unit message authentication codes is generated, wherein each one-unit message authentication code corresponds to a respective unit of the plurality of units of the message, and wherein each one-unit message authentication code is generated based on the identifying parameter associated with the message, a given one of the plurality of units, and the position of the given unit in the message. Verification of each unit of the message may then be efficiently performed inside a method of secure computation such as, by way of example only, a garbled circuit.

Claims

1. A method, comprising:

obtaining a message and an identifying parameter associated with the message, wherein the message comprises a plurality of units;

generating a plurality of one-unit message authentication codes, each one-unit message authentication code corresponding to a respective unit of the plurality of units of the message, wherein each one-unit message authentication code is generated based on the identifying parameter associated with the message, a given one of the plurality of units, and the position of the given unit in the message; and

providing two or more possible combinations of values of a first one of the one-unit message authentication codes and a corresponding first authenticator string as inputs to a garbled-circuit based secure computation protocol, wherein the garbled circuit-based secure computation protocol outputs an indication of the validity of the first one-unit message authentication code;

wherein the method is performed by at least one processing device; and

wherein the message comprises an encryption key.

2. The method of claim 1, wherein the encryption key comprises an XOR encryption key.

3. The method of claim 1, wherein the message comprises a plurality of bits, and each unit of said plurality of units consists of a single bit such that each of a plurality of one-bit message authentication codes is respectively generated for each of the plurality of bits of the message.

4. The method of claim 1, wherein the plurality of one-unit message authentication codes is respectively generated for the plurality of units of the message using a message authentication code key.

5. The method of claim 4, further comprising providing the plurality of one-unit message authentication codes to a holder of the message.

6. The method of claim 5, further comprising providing the message authentication code key to a verifier such that the verifier can verify the authenticity of a message which purports to be the message and which the verifier subsequently receives along with the plurality of one-unit message authentication codes.

7. The method of claim 6, wherein the purported message and the plurality of one-unit message authentication codes are provided to the garbled-circuit based secure computation protocol to perform the verification of authenticity of the purported message without revealing the content of the purported message to the verifier.

8. The method of claim 1, wherein the garbled circuit-based secure computation protocol is part of a private database system.

9. An article of manufacture comprising a processor-readable storage medium having embodied therein executable program code that when executed by the processing device causes the processing device to perform steps of claim 1.

10. A method, comprising:

receiving, at a verifier associated with a private database system, a given one of a plurality of one-unit message authentication codes and a corresponding authenticator string, the given one-unit message authentication code corresponding to a respective unit of a plurality of units of a message, wherein the given one-unit message authentication code is generated based on an identifying parameter associated with the message, a given one of the plurality of units, and a position of the given unit in the message; and

verifying, at the verifier, the validity of the given one-unit message authentication code, while preventing content of the message from being known to the verifier;

wherein the verifying step is performed by a processing device which implements the verifier as part of the private database system and comprises inputting into a garbled circuit-based secure computation protocol two or more possible combinations of values of the given one-unit message authentication code and corresponding authenticator string and receiving an output from the garbled circuit-based secure computation protocol indicating the validity of the first one-unit message authentication code; and

wherein the message comprises an encryption key.

11. The method of claim 10, wherein the encryption key comprises an XOR encryption key.

12. An apparatus comprising:

a memory; and

a processor operatively coupled to the memory and configured to;

obtain a message and an identifying parameter associated with the message, wherein the message comprises a plurality of units;

generate a plurality of one-unit message authentication codes, each one-unit message authentication code corresponding to a respective unit of the plurality of units of the message, wherein each one-unit message authentication code is generated based on the identifying parameter associated with the message, a given one of the plurality of units, and the position of the given unit in the message; and

providing two or more possible combinations of values of a first one of the one-unit message authentication codes and a corresponding first authenticator string as inputs to a garbled-circuit based secure computation protocol, wherein the garbled circuit-based secure computation protocol outputs an indication of the validity of the first one-unit message authentication code;

wherein the message comprises an encryption key.

13. The apparatus of claim 12, wherein the encryption key comprises an XOR encryption key.

14. The apparatus of claim 12, wherein the message comprises a plurality of bits, and each unit of said plurality of units consists of a single bit such that each of a plurality of one-bit message authentication codes is respectively generated for each of the plurality of bits of the message.

15. The apparatus of claim 12, wherein the plurality of one-unit message authentication codes is respectively generated for the plurality of units of the message using a message authentication code key.

16. The apparatus of claim 15, wherein the processor is further configured to provide the plurality of one-unit message authentication codes to a holder of the message.

17. The apparatus of claim 16, wherein the processor is further configured to provide the message authentication code key to a verifier such that the verifier can verify the authenticity of a message which purports to be the message and which the verifier subsequently receives along with the plurality of one-unit message authentication codes.

18. The apparatus of claim 17, wherein the purported message and the plurality of one-unit message authentication codes are provided to the garbled-circuit based secure computation protocol to perform the verification of authenticity of the purported message without revealing the content of the purported message to the verifier.

19. The apparatus of claim 12, wherein the garbled circuit-based secure computation protocol is part of a private database system.