R. Impagliazzo
ABSTRACT
We present strong evidence that the implication, “if one-way permutations exist, then secure secret key agreement is possible”, is not provable by standard techniques. Since both sides of this implication are widely believed true in real life, to show that the implication is false requires a new model. We consider a world where all parties have access to a black box for a randomly selected permutation. Being totally random, this permutation will be strongly one-way in a provable, information-theoretic way. We show that, if P = N P, no protocol for secret key agreement is secure in such a setting. Thus, to prove that a secret key agreement protocol which uses a one-way permutation as a black box is secure is as hard as proving P ≠ N P. We also obtain, as a corollary, that there is an oracle relative to which the implication is false, i.e., there is a one-way permutation, yet secret-exchange is impossible. Thus, no technique which relativizes can prove that secret exchange can be based on any one-way permutation. Our results present a general framework for proving statements of the form, “Cryptographic application X is not likely possible based solely on complexity assumption Y.”
- BGS75.T. Baker, J. Gill, and R. Solovay. Relativizations of the P=NP question. SIAM J. Comp., 4 (1975) pp. 431-442.Google Scholar
Cross Ref
- BG81.C.H. Bennett and J. Gill. Relative to a random oracle A, pAneNpAneCo- NPA with probability 1. SIAM J. Comp. 10 (1981)Google ScholarCross Ref
- BCC87.G. Brassard, D. Chaum, and C. Crepeau. Minimum disclosure proofs of knowledge. Technical Report PM- tl.8710, Centre for Mathematics and Computer Science, Amsterdam, The Netherlands, 1987.Google Scholar
- Ben87.J. Cohen Benaloh. Verifiable Secret- Ballot Elections. PhD thesis, Yale University, Sept 1987. YALEU/DCS/TR- 561. Google ScholarDigital Library
- Blu81.M. Blum. Three ~pplic~tions of the oblivions transfer: Part i: Coin flipping by telephone; part ii: How to exchange secrets; part iii: How to send certified electronic mail. Department of EECS, University of CMifornia, Berkeley, CA, 1981.Google Scholar
- Blu82.M. Blum. Coin flipping by telephone: A protoc91 for solving impossible problems. In Proceedings of the 2,1th IEEE Computer Conference (CornpC'on), pages 133-137, 1982. reprinted in SIGACT News, vol. 15, no. 1, 1983, pp. 23-27.Google Scholar
- BM84.M. Blum and S. Micali. How to generate cryptogra~phicaily strong sequences of pseudo-random bits. SIAM J. Comp. 13 (1984) pp. 850-864 Google ScholarDigital Library
- Bra.G. Brassard. An optimally secure relativized cryptosystem. Advances in Cryptography, a Report on CR YPTO 81, Technical Report no. 82-04, Department of ECE, University of California, Santa Barbara, CA, 1982, pp. 54-58; reprinted in $IGACT News vol. 15, no. 1, 1983, pp. 28-a3.Google Scholar
- Bra83.G. Brassard. Relativized cryptography. IEEE Transactions on Information Theory, IT-19:877-894, t983.Google Scholar
- CKS81.A.K. Chandra, D. Kozen, and L. Stockmeyer. Alternation. JACM, 28:114- 133, 198t. Google ScholarDigital Library
- DH76.W. Diffie and M. E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, IT- 22:644-654, 1976.Google ScholarDigital Library
- FFS86.U. Feige, A. Fiat and A. Shamir. Zeroknowledge proofs of identity. STOC, 1987. Google ScholarDigital Library
- GGM84.O. Goldreich, S. Goldwasser, and S. Micall. How to construct random functions. In Proceedings of the 25th Annual Foundations of Computer Science. ACM, 1984.Google Scholar
- GMW87.O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game or a completeness theorem for protocols with honest majority. In Proceedings of the 19th Annual Symposium on Theory of Computing. ACM, 1987. Google ScholarDigital Library
- GM84.S. Goldwasser and S. Micali. Probabalistic Encryption. JCSS, 28:270-299, 1984.Google ScholarCross Ref
- GMR84.S. Goldwasser, S. Micali, and R. Rivest. A "paradoxical" solution to the signature problem. In Proceedings of the 25th Annual Foundations of Computer Science. ACM, 1984.Google ScholarDigital Library
- I88.R. Impagliazzo Proofs that relativize, and proofs that do not. Unpublished manuscript, 1988.Google Scholar
- IY87.R. impagli~Lzzo and M. Yung. Direct minimum-knowledge computations, in Proceedings of Advances in Cryptography. CRYPTO, 1987. Google ScholarDigital Library
- JVV86.Mark Jerrum, Leslie Valiant, and Vijay Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Scieace, 43:169-188, 1986. Google ScholarDigital Library
- LR86.M. Luby and C. Rackoff. How to construct pseudo-random permutations from pseudo-random functions. In P~'oceedings of the Eighteenth Annual A CM Symposium on Theory of Computing, 1986. Google ScholarDigital Library
- Mer78.tL. C. Merkle. Secure communications over insecure channels. CA CM, 21(4):294-299, April 1978. Google ScholarDigital Library
- NY.M. Naor and M. Yung. Universal One- Way Hash Functions and Their Applications. These precedings. Google ScholarDigital Library
- P74.G.P. Purdy A high security log-in procedure. CACM, 17:442-445, 1974. Google ScholarDigital Library
- Rab81.M.O. Rabin. How to exchange secrets by oblivious transfer. Technical Report TP~-81, Harva,rd University, 1981.Google Scholar
- Rac88.C. Rackoff. A basic theory of public and private cryptosystems. Cryp{o 88. Google ScholarDigital Library
- Yao82.A.C. Yao. Theory and applications of trapdoor functions. In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, pages 80-91/. IEEE, 1982.Google ScholarDigital Library
Index Terms
- Limits on the provable consequences of one-way permutations
Recommendations
Limits on the provable consequences of one-way permutations (invited talk)
CRYPTO '88: Proceedings on Advances in cryptologyWe present strong evidence that the implication, "if one-way permutations exist, then secure secret key agreement is possible", is not provable by standard techniques. Since both sides of this implication are widely believed true in real life, to show ...
Tag-KEM from set partial domain one-way permutations
ACISP'06: Proceedings of the 11th Australasian conference on Information Security and PrivacyRecently a framework called Tag-KEM/DEM was introduced to construct efficient hybrid encryption schemes. Although it is known that generic encode-then-encrypt construction of chosen ciphertext secure public-key encryption also applies to secure Tag-KEM ...
Comments