Mix networks have been the subject of significant research, commercial activity, and actual use since they were first disclosed by the present applicant in 1979. Such prior art mixing, however, generally performs public-key cryptographic processing on messages as they travel through the network. This is believed to result in significant commercial disadvantages in terms of efficiency and efficacy relative to the present invention. Moreover, use of mix networks has been limited largely to providing unlinkability of communication, whereas aspects of the present invention not only extend mixing's protections to transactions but also offer other types of protections that address broader needs of communication and interaction of users.
Novel cryptographic apparatus and methods disclosed here allow mixing that is believed significantly more efficient in terms of the amount of computation performed in realtime and consequently allow reduction both in overall delay of messages and cryptographic processing capacity. This is of commercial significance at least because it is believed that efficiency has limited the adoption as well as the efficacy of, and relates to the cost of, mixing systems both used and proposed. It is also believed of commercial significance because delay through each of a number of stages of mixing adds up, which tends towards more batches, use of less stages, reduced protections for users, and consequently less attractive offerings to users. The improved efficiency is believed further of commercial significance because it improves the reduced utilization and related hardware cost of cryptographic processing of prior art schemes. Moreover, users are believed sensitive, especially with increasingly popular portable devices, to computation time and energy usage. Also, some prior-art mixing has been based on stronger assumptions about underlying cryptographic primitives and thus may be more vulnerable to cryptanalytic attack.
In brief non-limiting summary some exemplary embodiments of some inventive aspects will now be provided. A so-called “cascade” or series of n mix devices, called here “nodes,” receives b messages, each message associated with a corresponding entity/device here called a “user,” “user device,” or “subscriber.” Included in the messages are encryptions formed by the subscribers. In what may here be called an “unpermuted” phase, each mix node processes these b inputs into what here may be called a “normalized” form, using non-pubic information held in common pairwise by nodes and corresponding subscribers, and typically employing a mathematically commutative property. Then in what may here be called a “permuting” phase, each of the b messages is transformed successively through each of the n nodes, during which the encryption remaining after normalization is removed and each node permutes the order of the b inputs it processes. The output of the cascade contains the b messages sent by potentially identified subscribers but in an order believed unpredictable to any proper subset of non-colluding nodes.
For clarity a particular non-limiting but concrete example will be described using modular exponentiation as the encryption, first without pre-computation and including successive processing in the unpermuted phase. Each of the b messages is sent by a distinct subscriber, each of which has established a different secret key in common with each of the n mix nodes. A subscriber raises its actual message content c to the power computed as the product of the secrets that subscriber shares with all the nodes, in a group where discrete log is at least believed hard. Then, in an unpermuted phase, each node successively normalizes by raising to a computed secret power that both cancels the unique subscriber power and leaves in place a single round secret power that node uses for all messages in the batch. In the permuting phase, each node permutes the b messages it receives from the preceding node in the cascade and raises each message in the batch to a power that cancels that node's single round power, so that the final output batch contains each original message content c unencrypted but re-ordered by the composition of the permutations applied by the successive nodes.
In an exemplary simplified non-limiting pre-computation embodiment described for clarity, the nodes first cooperate to produce a so-called “shared public key” for homomorphic encryption, such as one that includes independent private keys from each node. The nodes then in effect go through the motions of the two real-time phases already described, unpermuted and permuted, but instead of encrypting a message payload they homomorphicly combine keys injected at each stage, the same keys that will be used again at the corresponding stages of the realtime processing. The final accumulation of individual keys that apply to a particular position in the overall output of the cascade is then recovered by the nodes cooperating in decryption of the homomorphic encryption for that output position. Inputs for realtime processing can use the same group operation as that of the homomorphic encryption, so that the set of key group elements that are combined by the group operation with the message to encrypt the message payload in the output can be cancelled by combining with the inverse of what is recovered by decrypting the final result of the homomorphic encryption.
In some exemplary non-limiting functionality extensions, believed adaptable for mixing more generally, message types and protocols for their use are disclosed allowing applications such as, encrypted email, untraceable return addresses, polling/anti-spam, credential mechanisms, and payments including so-called “payer anonymity.” The novel unpermuted phase of processing, with pairwise secured communication between subscribers and nodes, allows nodes to optionally at least partly independently verify aspects of user identity and various transaction parameters.