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.