This paper presents a technique for providing users with anonymity tools without using conventional cryptography. The method, Anonymous Multi Party Computation (AMPC), provides a generic building block for providing electronic anonymity in various applications, e.g., electronic voting and oblivious transfer. It uses a variation of Chaum’s mix-nets that utilizes value-splitting to hide inputs, and hence requires no “conditionally-secure” operations of its users. This is achieved under the assumption that there are secure channels between good participants, and under a suitable resilience threshold assumption that, in our worst adversarial scenario, is a square-root of the system.