There are plenty of non-trivial deterministic protocols that achieve semi-honest or standalone security.
In Privacy and Communication Complexity, Kushilevitz characterized which functions have a deterministic semi-honest protocol. Here is one example: The function is the maximum function, where Alice has an input from $\{1, 3, \ldots, 2n+1\}$ and Bob has an input from $\{0, 2, \ldots, 2n\}$. The deterministic protocol proceeds as follows:
- Alice announces whether she has input $2n+1$. If she does, then the protocol ends.
- Bob announces whether he has input $2n$. If he does, then the protocol ends.
- etc etc
Sometimes this particular protocol is called the "Dutch flower auction" protocol. It's possible to show that the protocol achieves semi-honest security --- given just the ideal function's output, it's easy to simulate the transcript.
Kushilevitz defines a "decomposable" function and shows that a function has a (perfectly secure) semi-honest protocol if and only if it is decomposable. Furthermore, every decomposable function has a deterministic protocol!
So in this security model, deterministic protocols are the norm, not the exception!
This particular protocol is also secure in the standalone model, although the security reasoning is less obvious. In section 5 of Complexity of Multi-party Computation Problems, we characterize which functions have standalone-secure protocols of this form.
