Probabilistic Encryption

Shafi Goldwasser, Silvio Micali, 1984, Journal of Computer and System Sciences

About this paper

This paper is under a licence that does not allow it to be reproduced, so what is here is its front matter and a short abstract. Read it at the publisher's page.

Tiếng Việt
English

Mã hóa xác suất*

Shafi Goldwasser and Silvio Micali

Laboratory of Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Nhận ngày 3 tháng 2 năm 1983; sửa đổi ngày 8 tháng 11 năm 1983

Một mô hình xác suất mới của mã hóa dữ liệu được giới thiệu. Đối với mô hình này, dưới các giả định độ phức tạp thích hợp, người ta chứng minh rằng việc trích xuất bất kỳ thông tin nào về bản rõ từ bản mã là khó trên trung bình đối với một đối phương có tài nguyên tính toán bị chặn đa thức. Chứng minh áp dụng cho mọi không gian thông điệp với mọi phân phối xác suất. Cài đặt đầu tiên của mô hình này được trình bày. Tính bảo mật của cài đặt này được chứng minh dựa trên giả định không thể giải quyết được bài toán quyết định Tính dư bậc hai modulo các số hợp thành mà phép phân tích nhân tử của chúng là không xác định.

Laboratory of Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Received February 3, 1983; revised November 8, 1983

A new probabilistic model of data encryption is introduced. For this model, under suitable complexity assumptions, it is proved that extracting any information about the cleartext from the cyphertext is hard on the average for an adversary with polynomially bounded computational resources. The proof holds for any message space with any probability distribution. The first implementation of this model is presented. The security of this implementation is proved under the intractability assumption of deciding Quadratic Residuosity modulo composite numbers whose factorization is unknown.

This section is missing here.

1 Introduction

This section is missing here.

2 *Survey of Public Key Cryptosystems Based on Trapdoor Functions*

This section is missing here.

3 UNAPPROXIMABLE TRAPDOOR PREDICATES

This section is missing here.

4 Public Key Cryptosystems and Probabilistic Public Key Cryptosystems

This section is missing here.

5 THE SECURITY OF A PUBLIC KEY CRYPTOSYSTEM

This section is missing here.

6 THE QUADRATIC RESIDUOSITY PROBLEM (QRP)

This section is missing here.

7 FINAL REMARKS

This section is missing here.

Acknowledgments

References

  1. L. Adleman, K. Manders, and G. Miller, On taking roots in finite fields, in “Proceedings of the 18th Annual IEEE Symposium on Foundations of Computer Science,” pp. 175–177, 1977.
  2. L. Adleman, On distinguishing prime numbers from composite numbers, in “Proceedings of the 21st IEEE Symposium on the Foundations of Computer Science,” pp. 387–408, Syracuse, N.Y., 1980.
  3. M. BLUM, Coin flipping by telephone, in "Proceedings of the IEEE, Spring Comp-Con, pp. 133-137, 1982.
  4. L. BLUM, M. BLUM, AND M. SHUB, "A Simple Secure Pseudo-Random Number Generator," CRYPTO, 1982.
  5. M. BLUM AND S. MICALI, How to generate cryptographically strong sequences of pseudo random bits, in "Proceedings of the 23rd IEEE on the Foundations of Computer Science," Chicago, Ill., 1982.
  6. G. BRASSARD, Relativized cryptography, in "Proceedings of the 20th IEEE Symposium on the Foundations of Computer Science," pp. 383-391, San Juan, Puerto Rico, 1979.
  7. G. BRASSARD, On computationally secure authentication tags requiring short secret shared keys, CRYPTO, 1982.
  8. C. F. GAUSS, "Disquisitiones Arithmeticae," 1801, translated by A. Arthur and S. J. Clark, Yale Univ. Press, New Haven, 1966.
  9. W. DIFFIE AND M. E. HELLMAN, New direction in cryptography, IEEE Trans. Inform. Theory IT-22 (6) (1976), 644-654.
  10. S. GOLDWASSER AND S. MICALI, "A Bit by Bit Secure Public Key Cryptosystem," Memorandum No. UCB/ERL M81/88, University of California, Berkeley, December 1981.
  11. S. GOLDWASSER AND S. MICALI, Probabilistic encryption & how to play mental poker, keeping secret all partial information, in "Proceeding of 14th STOC Conference," San Francisco, 1982.
  12. S. GOLDWASSER, S. MICALI, AND P. TONG, Why and how to establish a private code in a public network, in "Proceedings of the 23rd Symposium on Foundations of Computer Science," Chicago, Ill., 1982.
  13. S. GOLDWASSER, "Probabilistic Encryption: Theory and Applications," Ph.D. thesis, Univ. of California at Berkeley, 1983.
  14. S. GOLDWASSER, S. MICALI, AND A. YAO, Strong signature schemes and authentication, in "Proceedings, 15th STOC," Boston, Mass., 1983.
  15. K. R. GUY, How to factor a number, in "Proceedings of Fifth Manitoba Conference on Numerical Math.," pp. 49-89, 1975.
  16. D. KNUTH, "The Art of Computer Programming," Vol. 2, 2nd ed., Addison-Wellesley, Reading, Mass., 1981.
  17. R. LIPTON, How to cheat at mental poker, in "Proceeding of the AMS Short Course on Cryptology," January 1981.
  18. G. MILLER, Riemann's hypothesis and tests for primality, Ph.D. thesis, U.C. Berkeley, 1975.
  19. M. LUBY, S. MICALI, AND C. RACKOFF, How to simultaneously exchange a secret bit by flipping a symmetrically-biased coin, FOCS 1983.
  20. M. RABIN, Digitalized signatures and public-key functions as intractable as factorization, MIT/LCS/TR-212, Technical Memo MIT, 1979.
  21. R. RIVEST, A. SHAMIR, AND L. ADLEMAN, A method for obtaining digital signatures and public key cryptosystems, Communications of the ACM, February 1978.
  22. A. SHAMIR, R. RIVEST, AND L. ADLEMAN, "Mental Poker," MIT Technical Report, 1978.
  23. C. E. SHANNON, Communication theory of secrecy systems, Bell System Tech. J. 28 (1949), 656-715.
  24. D. SHANKS, "Solved and Unsolved Problems in Number Theory," Chelsea, New York, 1978.
  25. V. VAZIRANI AND U. VAZIRANI, Secure one-bit disclosures using a pseudo random number generator, in "Proceedings, FOCS," 1983.
  26. A. YAO, On the theory and application of trapdoor functions, in "Proceedings of the 23rd Symposium on the Foundations of Computer Science," Chicago, Ill., November 1982.

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8. Translated into Tiếng Việt by gpt-5, against glossary version 7. Translated from the English.

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8.