Some Results on Nonlinear Zigzag Functions

Zigzag functions were defined by Brassard, Crépeau, and Sántha [1] in connection with an application to the construction of oblivious transfers (a useful tool in cryptographic protocols). They proved that linear zigzag functions are equivalent to self-intersecting codes, which have been studied by several researchers.

In this paper, we begin an investigation of general (linear or nonlinear) zigzag functions.
In particular, we prove some bounds (i.e., necessary conditions for the existence of zigzag functions) that generalize known bounds for linear zigzag functions.