Partitioned encryption and achieving simultaneity by partitioning. (English) Zbl 0637.94015
Summary: We present a method called partitioned encryption whose main property is its simplicity. It is an extension of probabilistic public-key encryption, which can be used in designing cryptographic protocols and can be applied to distributed problem solving. We also give a modification of secret sharing called partitioned secret sharing. We demonstrate the power of partitioned encryption: combining it with the partitioning of the user set gives a solution scheme for ‘verifiable secret sharing’ and ‘simultaneous broadcast in the presence of faults’, which are important primitives of fault-tolerant distributed computing introduced by Chor, Goldwasser, Micali and Awerbuch (1985). The scheme is fully polynomial, simple, and efficient in terms of communication rounds. The basic partitioning methods are suggested as general tools for distributed computing, which are easy to implement and analyze.
Keywords:
cryptography; fault-tolerant distributed computing; cryptographic protocol; zero-knowledge interactive proof-system; verifiable secret- sharing; simultaneous broadcast; partitioned encryption; probabilistic public-key encryptionReferences:
| [1] | Alexi, W.; Chor, B.; Goldreich, O.; Schnorr, C. P., RSA/rabin bits are \(12+(1poly(k))\) secure, Proc. 25th IEEE FOCS, 449-457 (1984) |
| [2] | Alon, N.; Galil, Z.; Yung, M., Majority assignment and fault tolerant cryptographic protocols (1986), Unpublished manuscript |
| [3] | Blum, L.; Blum, M.; Shub, M., Comparisons of two pseudo-random number generators, Proc. Crypto, 82, 61-78 (1982) · Zbl 0543.68031 |
| [4] | Blum, M., Three Applications of the Oblivious Transfer (September 1981), Univ. of California: Univ. of California Berkeley, Rept. |
| [5] | Blum, M.; Goldwasser, S., An efficient probabilistic public-key scheme which hides all partial information, Proc. Crypto, 84, 289-301 (1985) · Zbl 0602.94010 |
| [6] | Bracha, G., An O(log \(n)\) expected rounds randomized Byzantine generals algorithm, Proc. 17th ACM-SIGACT STOC, 316-326 (1985) |
| [7] | Chor, B.; Dwork, C., Randomized algorithms for distributed agreement (1986), Unpublished manuscript |
| [8] | Chor, B.; Goldreich, O.; Goldwasser, S., The bit security of modular squaring given partial factorization of the modulus, Proc. Crypto, 85, 448-457 (1985) · Zbl 0593.94015 |
| [9] | Chor, B.; Goldwasser, S.; Micali, S.; Awerbuch, B., Verifiable secret sharing and achieving simultaneity in the presence of faults, Proc. 26th IEEE FOCS, 383-395 (1985) |
| [10] | Dwork, C.; Shmoys, D.; Stockmayer, L., Flipping persuasively in constant expected time, Proc. 27th IEEE FOCS, 222-232 (1986) |
| [11] | Even, S.; Goldreich, O.; Lempel, A., A randomized protocol for signing contracts, Comm. ACM, 28, 6, 637-647 (1985) · Zbl 0538.94011 |
| [12] | Feldman, P.; Micali, S., Byzantine agreement in constant time (and trusting no one), Proc. 26th IEEE FOCS, 267-276 (1985) |
| [13] | Feldman, P.; Micali, S., Efficient simultaneous broadcast (1986), Unpublished manuscript |
| [14] | Goldreich, O.; Micali, S.; Wigderson, A., Proofs that yield nothing but their validity and a methodology of cryptographic protocol design, Proc. 27th IEEE FOCS, 174-187 (1986) |
| [15] | Goldwasser, S.; Micali, S., Probabilistic encryption and how to play mental poker keeping secret all partial information, Proc. 14th Ann. ACM-SIGACT Symp. on Theory of Computing, 365-377 (1982) |
| [16] | Goldwasser, S.; Micali, S.; Rackoff, C., The knowledge complexity of interactive proof-systems, Proc. 17th ACM-SIGACT STOC, 291-304 (1985) · Zbl 0900.94025 |
| [17] | Halpern, J.; Rabin, M. O., A logic to reason about likelihood, Proc. 15th ACM STOC, 310-319 (1983) |
| [18] | Rackoff, C.; Micali, S.; Fischer, M., A secure protocol for the oblivious transfer, La Sorbonne, Paris. La Sorbonne, Paris, Proc. Eurocrypt’84 (April 1984) |
| [19] | Rivest, R.; Shamir, A.; Adleman, L., A method for obtaining digital signatures and public key cryptosystems, Comm. ACM, 21, 2, 120-126 (1978) · Zbl 0368.94005 |
| [20] | Shamir, A., How to share a secret, Comm. ACM, 22, 11, 612-613 (1979) · Zbl 0414.94021 |
| [21] | Vazirani, U.; Vazirani, V., Efficient and secure pseudo-random number generation, Proc. 25th IEEE FOCS, 458-463 (1984) |
| [22] | Yao, A. C., Theory and applications of trapdoor functions, Proc. 23rd IEEE FOCS, 80-91 (1982) |
| [23] | Yung, M., Cryptoprotocols: Subscription to a public-key, the secret blocking and the multi-player mental poker game, Proc. Crypto, 84, 439-453 (1985) · Zbl 1359.94633 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
