Question states what is one time MAc security is and asks to define a scheme the satisfies the one time secure MAC

The MAC scheme should not be using any primitives like PRG, PRF or PRP. Ok what could be possible solution if we ignore the statement "

  • 3
    $\begingroup$ Perhaps a Carter-Wegman Message Authentication Code using arithmetic in a binary field? But does this match the vague "not use any arithmetic operations" ? $\endgroup$
    – fgrieu
    Oct 21 at 8:49
  • 3
    $\begingroup$ That "not use any arithmetic operations" is either really hard or meaningless. Everything computers do other than a load or a store is an arithmetic operation ("logical" operations are just arithmetic operations in the Boolean algebra) or nothing is (arithmetic operations are just applications of Boolean circuits). You could write a Carter-Wegman MAC algorithm with nothing but the multi-input boolean functions available in FPGA LUTs, after all, and it could be made quite efficient. But I doubt that's what the assignment wants. $\endgroup$ Oct 21 at 15:37
  • $\begingroup$ Although the question is interesting I've closed it until the last sentence is cleared up, as I don't think it is possible to answer this without clarification. Please hit edit and clarify! $\endgroup$
    – Maarten Bodewes
    Oct 21 at 18:14
  • 1
    $\begingroup$ We have to guess what the modified question wants to be ignored. Another reason to keep the question closed is that it is a straight dump of homework, without showing what was attempted, or even retyping it LaTex. The simplest that could be an answer goes: work in a binary field $(F_{2^n},+,\cdot)$, and use a "one-time Message Authentication Code" $m\mapsto a\cdot m+b$ with key $(a,b)$ in $\left(\{0,1\}^n\right)^2$. If the large key and MAC are an issue (e.g. contradict definitions given that require $n$ to grow faster than the MAC size), move to a "Carter-Wegman Message Authentication Code". $\endgroup$
    – fgrieu
    Oct 22 at 9:11


Browse other questions tagged or ask your own question.