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
    Commented Oct 21, 2023 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$ Commented Oct 21, 2023 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
    Commented Oct 21, 2023 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
    Commented Oct 22, 2023 at 9:11
  • $\begingroup$ If we make a generous interpretation of "no arithmetic operations" to mean the tag itself does not involve any "computation" during signing, then one solution is to get creative with the key space. $\endgroup$ Commented Jan 22 at 11:07


Browse other questions tagged or ask your own question.