Secure function evaluation for Boolean formulae Under the assumption that "secure" encryption exists, secure evaluation of functions represented by Boolean circuits is possible by  Yao's garbling scheme [Y1]. My question is whether secure evaluation of functions represented by Boolean formulae is an easier problem (i.e., possible in the information theoretic setting).

(This is true, for example for secret sharing: Benaloh and Lichter [BL] gave an perfect scheme for access structures described by monotone Boolean formulae, but for monotone Boolean circuits one needs to assume secure encryption [Y2].)

References:

[BL]: Benaloh and Lichter. Generalized secret sharing and monotone functions. Crypto’88

[Y1]: Yao. How to generate and exchange secrets. FOCS’86. 

[Y2]: Yao. Protocols for secure computations. FOCS'82
For log-depth circuits, it is possible to use an information-theoretic version of Yao's garbled circuits. Note that in a garbled gate, each key is used to encrypt twice. Thus, if the keys on the input wires are double the length of the keys on the output wires, then one-time pad encryption can be used and the result is information theoretically secure. 

See the paper Gate Evaluation Secret Sharing and Secure One-Round Two-Party Computation by Vlad Kolesnikov, and references within.