Partial sha-based hash function

A computer-implemented method of proving an integrity of part of a pre-image corresponding to a hash digest generated by hashing the pre-image with a SHA-based hash function, wherein the pre-image comprises a first message and a second message, and wherein the method is performed by a proving party and comprises:

• a) generating an iteration input vector, wherein the iteration input vector is generated by partially executing the SHA-based hash function, wherein partially executing the SHA-based hash function comprises:
• i) obtaining a first sequence of blocks, wherein the first sequence of blocks is obtained by either padding a binary representation of the pre-image to generate a first padded sequence, and splitting the first padded sequence into a first sequence of blocks, or by splitting a binary representation of the first message into the first sequence of blocks, and
• ii) performing an iteration of a SHA-based hash computation for each of the first sequence of blocks in order of a respective position in the first sequence of blocks, up until a block that comprises one or more bits representing the second message;
• and
• b) making the iteration input vector available to a verifying party.

Computer equipment comprising:

• memory comprising one or more memory units;
• and
• processing apparatus comprising one or more processing units, wherein the memory stores code arranged to run on the processing apparatus, the code being configured so as when run on the processing apparatus, the processing apparatus performs a method of verifying an integrity of part of a pre-image corresponding to a hash digest generated by hashing the pre-image with a SHA-based hash function, wherein the pre-image comprises a first message and a second message, and wherein the method is performed by a verifying party and comprises:
• a) receiving an iteration input vector, wherein the iteration input vector is generated by partially executing the SHA-based hash function, wherein partially executing the SHA-based hash function comprises:
• i) obtaining a first sequence of blocks, wherein the first sequence of blocks is obtained by either padding a binary representation of the pre-image to generate a first padded sequence, and splitting the first padded sequence into a first sequence of blocks, or by splitting a binary representation of the first message into the first sequence of blocks, and
• ii) performing an iteration of a SHA-based hash computation for each of the first sequence of blocks in order of a respective position in the first sequence of blocks, up until a block that comprises one or more bits representing the second message;
• b) obtaining a second sequence of blocks, wherein the second sequence of blocks is generated by:
• i) padding a binary representation of the second message to generate a second padded sequence,
• ii) splitting the second padded sequence into the second sequence of blocks;
• c) generating a final iteration output vector by performing an iteration of the SHA-based hash computation for each of the second sequence of blocks in order of a respective position in the second sequence of blocks, wherein the iteration of the SHA-based hash computation performed on a first one of the second sequence of blocks is based on the obtained iteration input vector;
• and
• d) generating a candidate hash digest based on the final iteration output vector, the candidate hash digest being for comparison with the hash digest.

A computer program embodied on non-transitory computer-readable storage media and configured so as, when run on one or more processors, the one or more processors to perform a method of verifying an integrity of part of a pre-image corresponding to a hash digest generated by hashing the pre-image with a SHA-based hash function, wherein the pre-image comprises a first message and a second message, and wherein the method is performed by a verifying party and comprises:

• a) receiving an iteration input vector, wherein the iteration input vector is generated by partially executing the SHA-based hash function, wherein partially executing the SHA-based hash function comprises:
• i) obtaining a first sequence of blocks, wherein the first sequence of blocks is obtained by either padding a binary representation of the pre-image to generate a first padded sequence, and splitting the first padded sequence into a first sequence of blocks, or by splitting a binary representation of the first message into the first sequence of blocks, and
• ii) performing an iteration of a SHA-based hash computation for each of the first sequence of blocks in order of a respective position in the first sequence of blocks, up until a block that comprises one or more bits representing the second message;
• b) obtaining a second sequence of blocks, wherein the second sequence of blocks is generated by:
• i) padding a binary representation of the second message to generate a second padded sequence,
• ii) splitting the second padded sequence into the second sequence of blocks;
• c) generating a final iteration output vector by performing an iteration of the SHA-based hash computation for each of the second sequence of blocks in order of a respective position in the second sequence of blocks, wherein the iteration of the SHA-based hash computation performed on a first one of the second sequence of blocks is based on the obtained iteration input vector;
• and
• d) generating a candidate hash digest based on the final iteration output vector, the candidate hash digest being for comparison with the hash digest.