Score:2

Proving a derived MAC is secure via reduction

jp flag

I don't have a very specific question, but reductions have been a weaker suit of mine and I was wondering if there is a secure MAC scheme, and a derived MAC' that uses MAC but modifies it in some way, how could you prove that MAC' is secure via reduction? I know how to do reductions for PRGs and PRFs, but not sure how to use it for MACs. I don't have a concrete example, but a walkthrough of the general process would be helpful, thanks!

Score:2
us flag

A simple example would be the following: Suppose you have a secure MAC scheme $M=(K,T,V)$ with the keygen, tagging and verification algorithms. Then define the new scheme $M'=(K,T',V')$ with $T'(k,m)=T(k,m)\|s$ for some constant string $s$ and $V'$ checking with a reject for the presence of $s$ before returning whatever $V$ would have returned on the shortened input.

The security reduction for $M'$ would then usually go as follows: You're given an adversary $\mathcal A$ against the sEUF-CMA security of $M'$ and need to construct $\mathcal R$ running the sEUF-CMA experiment to break $M$ using $\mathcal A$ as a sub-routine.
For any MAC'ing query from $\mathcal A$ you would then forward and on the way backwards, you'd add $s$ at the end of the tag.
For any Verifying query from $\mathcal A$ you then check if $s$ is present at the end of the tag and if not, immediately respond with the reject and otherwise forward the stripped tag-message pair also forwarding the result.
In the end, if $\mathcal A$ wins, it needs to have sent you a valid verify query which passed forwarded verification which also means the reduction adversary $\mathcal R$ has won.

SEJPM avatar
us flag
@kelalaka I have renamed $\mathcal A'$ to $\mathcal R$ to avoid this confusion.
kelalaka avatar
in flag
Well, I was rather on that adversary of $M$ should be $\mathcal A$ and adversary of $M'$ $\mathcal A'$, the reverse was conflicting my mind ( maybe just me) and have to read more than once :). You can delete this, too.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.