Message authentication code with blind factorization and randomization

A method of generating a message authentication code using blind randomization, comprising the steps of:

• a) a pair of sending and receiving correspondents agreeing upon on a set of elements {p1′, p2′, . . . , pL′,} which are relatively prime with respect to one another and which are further considered as a shared secret, the sending and receiving correspondents further agreeing upon an integer glεZpl, for each element pl, wherein Zp denotes the set {0, . . . , p} and L is an integer that denotes the number of prime numbers used in a basis β, and wherein N is a maximum number of bits of a message data block, where the value of N is dependent on a data embedding method that is also agreed upon by the sending and receiving correspondents, and wherein the message data bit string is a multiple of N, the sending and receiving correspondents further agreeing upon an upper limit for the number of bits to be used to represent the message authentication code and an initial vector for a set of message authentication code elements c−1,l, l=1, . . . , L, the sending and receiving correspondents further agreeing on a list of codes, wherein each code identifies a different sub-set of (L−1)elements out of a set of L′ shared secret elements, the sending and receiving correspondents further agreeing upon an element pL of the set {p1′, p2′, . . . , pL′,}, the element being used to carry information about the code used by the sending correspondent to select a sub-set of the elements {p1′, p2′, . . . , pL′,} which are used to form a basis, wherein the number of codes is (pL−1);
• the sending correspondent then performing the following steps:
• b) selecting a code at random from the list of agreed upon to select (L−1) elements {p1, p2, . . . , pL-1} from the elements {p1′, p2′, . . . , pL′,} to form the basis β={p1, p2, . . . , pL-1, pL};
• c) initializing an integer i as i=0, the following steps d) to e) then being repeated until all the message data blocks are processed, and incrementing l at each step:
• d) generating (L−1) integer values ki,l, where l=1, . . . , (L−1) such that 0≦ki,l<pl, from the i-th block of the message bit string using a data embedding method;
• e) computing the message authentication code elements ci,l modulo pl as ci,l=fl(ci-1,l, gl, ki,l) for l=1, . . . , (L−1), where fl(,) represents a modulo p function;
• f) embedding the bit strings of the code used by the sending correspondent to select the (L−1) elements {p1, p2, . . . , pL-1} into the integer value cu,L, such that 0≦cu,L≦pL using the data embedding method;
• g) combining the integer values cu,l for l=1, . . . , L to form a single integer vector {cu,1, cu,2, . . . , cu,L};
• h) converting the integer vector {cu,1, cu,2, . . . , cu,L} into an integer value C using the basis β and the Chinese Remainder Theorem, the integer value C being the message authentication code value;
• i) appending the bit string of the message authentication code integer value, C, to the message bit string and sending the concatenated bit string to the receiving correspondent;
• the receiving correspondent then performs the following steps:
• j) obtaining the message authentication code integer value C from the received message bit string;
• k) computing the message authentication code elements cu,L, modulo pl as cu,L=C mod pl for l=1, . . . , L;
• l) recovering the code used to define the set {p1, p2, . . . , pL-1} from the value cu,L;
• m) computing the message authentication code elements cu,l modulo pl as cu,l=C mod pl for l=1, . . . , (L−1);
• n) initializing the integer i as i=0, the following steps o) to p) then being repeated until all the received message data blocks are processed, and incrementing i at each step:
• o) generating (L−1) integer values ki,l, where l=1, . . . , (L−1), such that 0≦ki,l<pl, from the i-th block of the message bit string using the data embedding method;
• p) computing the message authentication code elements rci,l modulo pl as rci,l=fl(rci-1,l, gl, ki,l) for l=1, . . . , (L−1);
• and
• q) if Cu,l=rcu,l for l=1, . . . , (L−1), then the received message is authenticated.

A method of generating a message authentication code using blind randomization, comprising the steps of:

• a) sending and receiving correspondents agreeing upon on a set of elements {p1, p2, . . . , pL} which are relatively prime with respect to one another, the set of elements further being considered as a shared secret and which are further used to form a basis βs={p1, p2, . . . , pL}, the sending and receiving correspondents further agreeing upon an integer glεZpl for each element pl, where l=1, . . . , L, the sending and receiving correspondents further agreeing upon a data embedding method and an upper limit for the number of bits to be used to represent the message authentication code and an initial vector for the message authentication code elements c−1,l, l=1, . . . , L
• the sending correspondent then performing the following steps:
• b) selecting elements {q1′, q2′, . . . , qJ′,} wherein is an integer and J′>0, the elements being relatively prime with respect to one another and further being relatively prime with respect to the secret elements {p1, p2, . . . , pL}, the elements {q1′, q2′, . . . , qJ′,} being known to the sending correspondent only;
• c) selecting a random sub-set of elements from the set {qi,1, qi,2, . . . , qi,l}, wherein the number of bits needed to represent
• ∏
• l
• =
• 1
• L
• 
• 
• p
• l
• 
• ∏
• j
• =
• 1
• J
• 
• 
• q
• j
• is within the upper limit agreed upon by the sending and receiving correspondents;
• d) forming the basis β={p1, p2, . . . , pL, q1, q2, . . . , qJ} using the elements {p1, p2, . . . , pL-1} and the elements {q1, q2, . . . , qJ};
• e) initializing an integer i as i=0, then repeating the following steps f) to g) until all of the message data blocks are processed, and incrementing at each step:
• f) generating L integer values kl, where l=1, . . . , L, such that 0≦kl<pl from the lth block of the received message bit string using the data embedding method;
• g) computing the message authentication code elements ci,l modulo pl as ci,l=fl(ci-1,l, gl, ki,l) for l=1, . . . , L, wherein fl(,) represents a modulo p function;
• h) generating random values rj, where j=1, . . . , J, such that 0≦rj<qj for j=1, J;
• i) combining the integer values Cu,l for l=1, . . . , L and the values rj for j=1, . . . , J to form a single integer vector {cu,1, cu,2, . . . , cu,L, r1, r2, . . . , rJ};
• j) converting the integer vector {cu,1, cu,2, . . . , cu,L, r1, r2, . . . , rJ} into an integer value C using the basis β and the Chinese Remainder Theorem, the integer value C being the message authentication code value;
• k) appending the bit string of the message authentication code integer value, C, to the message bit string and sending the concatenated bit string to the receiving correspondent;
• the receiving correspondent then performing the following steps:
• l) obtaining the message authentication code integer value C from the received message bit string;
• m) computing the message authentication code elements cu,l modulo pl as cu,l=C mod pl for l=1, . . . , L;
• n) initializing the integer i as i=0, then repeating the following steps o) to p) until all of the received message data blocks are processed, and incrementing fat each step:
• o) generating L integer values kl, where l=1, . . . , L, such that 0≦kl<pl from the lth block of the received message bit string using the data embedding method;
• p) computing the message authentication code elements rci,l modulo pl as rci,l=fl(rci-1,l, gl, ki,l) for l=1, . . . , L;
• and
• q) if cu,l=rcu,l for all l, then the received message is authenticated.