Abstract
In this paper we investigate a primitive called a questionable encryption that is related to oblivious transfer. We consider a mobile agent that asymmetrically encrypts plaintext data from the host machine that it resides on and then broadcasts the resulting ciphertext so that it can be obtained by the creator of the agent. We formally define the notion of a questionable encryption scheme that can be used to perform this operation. The user of a questionable encryption scheme chooses to generate a real or fake public key. The choice is conveyed to the key generation algorithm which then outputs a poly-sized witness and either a real or fake key pair. If the public key is ‘real’ then it produces decipherable encryptions and the poly-sized witness proves this. If the key is generated to be ‘fake’ then it produces indecipherable encryptions (even with the private key) and the poly-sized witness proves this. Without knowledge of the witness it is intractable to distinguish between the two types of public keys. We present a construction for a questionable encryption scheme based on the Paillier cryptosystem. We prove the security of the scheme based on the difficulty of deciding n th degree composite residuosity. When applied to this application, the creator of the agent retains the exclusive ability to reveal whether or not the agent in fact transmits plaintexts. Our results show that agents that appear to compute asymmetric encryptions may in fact not (in a provable sense). We present other applications of questionable encryptions as well.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bach, E., Shallit, J.: Algorithmic Number Theory: Efficient Algorithms - Solving Equations over Finite Fields, ch. 7, vol. I. MIT Press, Cambridge (1996)
Blum, M., Goldwasser, S.: An efficient probabilistic public-key encryption scheme which hides all partial information. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 289–302. Springer, Heidelberg (1985)
Blum, L., Blum, M., Shub, M.: A simple unpredictable pseudo-random number generator. SIAM Journal on Computing 15(2), 364–383 (1986)
Brassard, G., Crépeau, C., Robert, J.M.: All-or-nothing disclosure of secrets. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 234–238. Springer, Heidelberg (1987)
Brassard, G., Crépeau, C., Robert, J.M.: Information Theoretic Reductions among Disclosure Problems. In: IEEE Symposium on Foundations of Computer Science, pp. 168–173 (1986)
Berger, R., Peralta, R., Tedrick, T.: A Provably Secure Oblivious Transfer Protocol. In: Beth, T., Cot, N., Ingemarsson, I. (eds.) EUROCRYPT 1984. LNCS, vol. 209, pp. 379–386. Springer, Heidelberg (1985)
Blum, M.: Three applications of the oblivious transfer: Part I: Coin flipping by telephone; Part II: How to exchange secrets; Part III: How to send certified electronic mail. UC Berkeley (1981)
Boneh, D.: The Decision Diffie-Hellman Problem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 48–63. Springer, Heidelberg (1998)
Cachin, C., Micali, S., Stadler, M.: Computationally Private Information Retrieval with Polylogarithmic Communication. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 402–414. Springer, Heidelberg (1999)
Canetti, R., Dwork, C., Naor, M., Ostrovsky, R.: Deniable Encryption. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 90–104. Springer, Heidelberg (1997)
Cramer, R., Shoup, V.: A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 13–25. Springer, Heidelberg (1998)
El Gamal, T.: A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Trans. Inform. Theory 31, 469–472 (1985)
Goldwasser, S., Bellare, M.: Lecture Notes on Cryptography (manuscript) (July 10, 1996)
Goldwasser, S., Micali, S.: Probabilistic Encryption. JCSS 28(2), 270–299 (1984)
Kilian, J.: Founding cryptography on oblivious transfer. In: ACM STOC, pp. 20–31 (1988)
Kilian, J.: Uses of randomness in algorithms and protocols. MIT Press, Cambridge (1990)
Kushilevitz, E., Ostrovsky, R.: Replication is not needed: Single database, computationally-private information retrieval. IEEE Foundations of Computer Science, 364–373 (1997)
PKCS #1-RSA Cryptography Standard, version 2.1, available from http://www.rsa.com/rsalabs/pkcs
Paillier, P.: Public-Key Cryptosystems based on Composite Degree Residue Classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999)
Rabin, M.: How to exchange secrets by oblivious transfer. Harvard Aiken Comp. Lab., TR-81 (1981)
Rivest, R., Shamir, A., Adleman, L.: A method for obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM 21(2), 120–126 (1978)
Tsiounis, Y., Yung, M.: On the security of ElGamal-based encryption. In: Imai, H., Zheng, Y. (eds.) PKC 1998. LNCS, vol. 1431, pp. 117–134. Springer, Heidelberg (1998)
Young, A., Yung, M.: Deniable Password Snatching: On the Possibility of Evasive Electronic Espionage. In: IEEE Symposium on Security and Privacy, pp. 224–235 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Young, A., Yung, M. (2005). Questionable Encryption and Its Applications. In: Dawson, E., Vaudenay, S. (eds) Progress in Cryptology – Mycrypt 2005. Mycrypt 2005. Lecture Notes in Computer Science, vol 3715. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11554868_15
Download citation
DOI: https://doi.org/10.1007/11554868_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28938-8
Online ISBN: 978-3-540-32066-1
eBook Packages: Computer ScienceComputer Science (R0)