| The design of provably secure communication protocols has been hindered by the lack of a rigorous, comprehensive definition of security in a multiparty network setting. Instead, a confusing variety of formal and informal criteria are considered necessary conditions for security. We examine two of these, chosen ciphertext security and untraceability, define them rigorously within formal models of a multiparty network, and present protocols which use various known cryptographic techniques to achieve them, provably, in their respective settings.;Zero-knowledge proofs of knowledge (ZKPKs) have been used to construct interactive public-key cryptosystems (PKCs) provably secure against chosen ciphertext attack (CCA). We introduce a revised setting, permitting definition of a non-interactive ZKPK (NIZKPK), which we then construct, in our setting, from a non-interactive zero-knowledge proof system (NIZKPS) for NP. We also give a formalization, in our model, of a stronger type of CCA than the previously-considered "lunchtime attack", and prove a non-interactive PKC based on a NIZKPK to be secure against it.;We also present a formal model of a network of synchronously communicating processors in which we define "untraceability" of messages, assuming various types of message-tracing, traffic-analyzing "adversary". For example, the adversary may control some of the processors, obtaining their private information or even altering their behaviour. We present efficient protocols which are provably secure against each type of adversary, using such known techniques as non-malleable cryptography, secure multiparty computation, and NIZKPS. The proofs of security also rely on an interesting general lemma about the rate of "mixing" achieved by certain kinds of random processes, or "shuffles", performed on a set of items. |
