Non-committing encryption from \(\Phi\)-hiding. (English) Zbl 1359.94605
Dodis, Yevgeniy (ed.) et al., Theory of cryptography. 12th theory of cryptography conference, TCC 2015, Warsaw, Poland, March 23–25, 2015. Proceedings, Part I. Heidelberg: Springer (ISBN 978-3-662-46493-9/pbk). Lecture Notes in Computer Science 9014, 591-608 (2015).
Summary: A multiparty computation protocol is said to be adaptively secure if it retains its security even in the presence of an adversary who can corrupt participants as the protocol proceeds. This is in contrast to the static corruption model where the adversary is forced to choose which participants to corrupt before the protocol begins.
A central tool for constructing adaptively secure protocols is noncommitting encryption [R. Canetti et al., Proceedings of the 28th annual ACM symposium on the theory of computing, STOC 1996. New York, NY: ACM, 639–646 (1996; Zbl 0922.68048)]. The original protocol of Canetti et al. had ciphertext expansion that was quadratic in the security parameter, and prior to this work, the best known constructions had ciphertext expansion that was linear in the security parameter. In this work, we present the first non-committing encryption scheme that achieves ciphertext expansion that is logarithmic in the message length.
Our construction has optimal round complexity (2-rounds), where (just as in all previous constructions) the first message consists of a public-key of size \(\tilde{\mathcal O}(n\lambda)\) where \(n\) is the message length and \(\lambda \) is the security parameter. The second message consists of a ciphertext of size \({\mathcal O}( n \log n + \lambda )\). The security of our scheme is proved based on the \(\Phi \)-hiding problem.
For the entire collection see [Zbl 1312.94005].
A central tool for constructing adaptively secure protocols is noncommitting encryption [R. Canetti et al., Proceedings of the 28th annual ACM symposium on the theory of computing, STOC 1996. New York, NY: ACM, 639–646 (1996; Zbl 0922.68048)]. The original protocol of Canetti et al. had ciphertext expansion that was quadratic in the security parameter, and prior to this work, the best known constructions had ciphertext expansion that was linear in the security parameter. In this work, we present the first non-committing encryption scheme that achieves ciphertext expansion that is logarithmic in the message length.
Our construction has optimal round complexity (2-rounds), where (just as in all previous constructions) the first message consists of a public-key of size \(\tilde{\mathcal O}(n\lambda)\) where \(n\) is the message length and \(\lambda \) is the security parameter. The second message consists of a ciphertext of size \({\mathcal O}( n \log n + \lambda )\). The security of our scheme is proved based on the \(\Phi \)-hiding problem.
For the entire collection see [Zbl 1312.94005].
MSC:
| 94A60 | Cryptography |
