Welcome to the resource topic for
**2005/092**

**Title:**

PRF Domain Extension Using DAGs

**Authors:**
Charanjit Jutla

**Abstract:**

We prove a general domain extension theorem for

pseudo-random functions (PRFs).

Given a PRF F from n bits to n bits,

it is well known that

employing F in a chaining mode (CBC-MAC)

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.

**ePrint:**
https://eprint.iacr.org/2005/092

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .