Paper 2005/092
PRF Domain Extension Using DAGs
Charanjit Jutla
Abstract
We prove a general domain extension theorem for pseudorandom functions (PRFs). Given a PRF $F$ from $n$ bits to $n$ bits, it is well known that employing $F$ in a chaining mode (CBCMAC) yields a PRF on the bigger domain. Viewing each application of $F$ in this chaining mode to be a node in a graph, and the chaining as the edges between the nodes, the resulting graph is just a line graph. In this paper, we show that the underlying graph can be an arbitrary directed acyclic graph (DAG), and the resulting function on the larger domain is still a PRF. The only requirement on the graph is that it have unique source and sink nodes, and no two nodes have the same set of incident nodes. A new highly parallelizable MAC construction follows which has a critical path of only $3+\log ^{*} n $ applications of $F$.\\ \hspace*{0.1in} If we allow Galois field arithmetic, we can consider edge colored DAGs, where the colors represent multiplication in the field by the color number. We prove an even more general theorem, where the only restriction on the colored DAGs is that if two nodes ($u$ and $v$) have the same set of incident nodes $W$, then at least one $w$ in $W$ is incident on $u$ and $v$ with a different colored edge. PMAC (parallelizable message authentication \cite{black}) is a simple example of such graphs. The general thoerem allows one to have further optimizations over PMAC, and many modes which deal with variable lengths.
Metadata
 Available format(s)
 PS
 Category
 Foundations
 Publication info
 Published elsewhere. Unknown where it was published
 Contact author(s)
 csjutla @ watson ibm com
 History
 20050509: last of 2 revisions
 20050325: received
 See all versions
 Short URL
 https://ia.cr/2005/092
 License

CC BY
BibTeX
@misc{cryptoeprint:2005/092, author = {Charanjit Jutla}, title = {{PRF} Domain Extension Using {DAGs}}, howpublished = {Cryptology ePrint Archive, Paper 2005/092}, year = {2005}, note = {\url{https://eprint.iacr.org/2005/092}}, url = {https://eprint.iacr.org/2005/092} }