Research Abstracts - 2006

Cascadable and Commutative Cryptographjy

Ronald L. Rivest & Stephen A. Weis

Performing a "cascade" of sequential cryptographic operations is an intuitive idea used in many applications. For instance, triple-DES (3DES) encryption performs three sequential DES encryption operations under different keys [2]. Public-key encryption operations are often cascaded as well. For example, messages are sequentially encrypted under different public keys in both mix networks for electronic voting [3] and privacy-enhancing onion routing [5].

Cascadable cryptosystems are a particular type of multiple encryption system. Multiple encryption systems encrypt data under several keys, possibly under different underlying cryptosystems. In general, a multiple cryptosystem does not necessarily specify the order of decryption operations or define intermediate states of partial decryption. The only requirement is that all keys used to encrypt a message must also be used to decrypt it. In cascadable cryptosystems, one may arbitrarily encrypt an existing ciphertext, or decrypt a ciphertext with a valid key. (Which keys are “valid” for a ciphertext will depend on the specific cryptosystem.)

Our research focuses on cascadable cryptosystems involving a single underlying encryption operator, as opposed to several independent encryption operators. Unfortunately, standard formal security definitions do not fully capture adversarial abilities in these settings. Adversaries performing chosen plaintext or chosen ciphertext attacks may be able to obtain encryptions or decryptions under a cascade of operations, rather than a single operation. Adversaries may also be able to distinguish ciphertexts by the history of operations that produced them. To address the absence of appropriate security definitions, we formally define cascadable semantic security and introduce a new notion of historical security.

The most basic cascadable cryptosystem has intuitive properties: one must decrypt in the opposite order of encryption operations. A plaintext encrypted under a sequence of keys x, y, denoted as c = e_y(e_x (m)), must be decrypted under the corresponding keys in reverse order, i.e. m = d_x(d_y(c)). For convenience, we will omit parentheses and represent the result of this sequence of encryption operations on a message mas the string e_ye_x(m). However, other classes of cascadable cryptosystems may allow different decryption orders. One particularly useful and interesting class of cascadable cryptosystems exhibit commutative properties, where one may decrypt with any key that a ciphertext has already been encrypted with. A ciphertext c = e_ye_x(m) may be decrypted as either m = d_yd_x(c) or m = d_xd_y(c).

Commutative cryptosystems, such as Pohlig-Hellman [7] and Massey-Omura [6], have existed for over 25 years and are the basis of many proposed applications. For instance, Shamir, Rivest, and Adleman's classic "Mental Poker" and three-pass key exchange protocols both rely on commutativity [18, 19]. More recently, Agrawal, Evfimievski, and Sriakant [1], and Clifton et al. [4] present data mining and private set intersection applications based on commutativity. To illustrate an application of commutativity, consider the three-pass key exchange protocol. In this protocol, Alice and Bob each have respective secret keys a and b. Alice wishes to share a secret s with Bob. If Alice and Bob have a cascadable, commutative cryptosystem at their disposal, they can engage in the following protocol:

Example: Three-Pass Key Exchange.

1. Given secret key a and input s, Alice sends Bob e_a(s).
2. Given secret key b, Bob sends Alice e_be_a(s)=e_ae_b(s).
3. Alice sends Bob d_ae_ae_b(s) = e_b(s).
4. Bob computes d_be_b(s) = s.

Commutativity is just one of many possible properties exhibited by cascadable cryptosystems. To model these various flavors, our cascadable cryptosystem definition incorporates string rewrite systems. String rewrite systems model cryptographic operations as strings of symbols, capturing the interaction between various symbols with rewrite rules. Rewrite systems will be a useful and flexible tool that may model a wide variety of cryptosystems.

References:

[1] Agrawal, R., Evfimievski, A., and Srikant, R. Information sharing across private databases. In International Conference on Management of Data - ACM SIGMOD (2003), pp. 86-87.

[2] Barker, W. C. Recommendation for the triple data encryption algorithm (TDEA) block cipher. Tech. Rep. 800-67, National Institute of Standards and Technology, 2004.

[3] Chaum, D. Untraceable electronic mail, return addresses, and digital pseudonyms. Communications of the ACM 4, 2. (February 1981), 84-90.

[4] Clifton, C., Kantarcioglu, M., Vaidya, J., Lin, X., and Zhu, M. Y. Tools for privacy preserving distributed data mining. SIGKDD Explorations 4, 2 (January 2003), 1-7.

[5] Goldschlag, D. M., Reed, M. G., and Syverson, P. F. Hiding routing information. In Informatin Hiding (1996), vol. 1174, pp. 137-150.

[6] Massey, J. L., and Omura, J. K. A new multiplicative algorithm over finite fields and its applicability in public key cryptography. Presented at EUROCRYPT 83, March 1983.

[7] Pohlig, S. C., and Hellman, M. E. An improved algorithm for computing logarithms over GF(P) and its cryptographic significance. IEEE Transactions on Information Theory IT-24 (1978), 106-110.

[8] Shamir, A. On the power of commutativity in cryptography. Presented at ICALP’80, July 1980.

[9] Shamir, A., Rivest, R. L., and Adleman, L. M. The Mathematical Gardner. Wadsworth International, 1981, ch. Mental Poker, pp. 37-43.