Document Zbl 1406.94024 - zbMATH Open
How to prove knowledge of small secrets. (English) Zbl 1406.94024
Robshaw, Matthew (ed.) et al., Advances in cryptology – CRYPTO 2016. 36th annual international cryptology conference, Santa Barbara, CA, USA, August 14–18, 2016. Proceedings. Part III. Berlin: Springer (ISBN 978-3-662-53014-6/pbk; 978-3-662-53015-3/ebook). Lecture Notes in Computer Science 9816, 478-498 (2016).
Summary: We propose a new zero-knowledge protocol applicable to additively homomorphic functions that map integer vectors to an Abelian group. The protocol demonstrates knowledge of a short preimage and achieves amortised efficiency comparable to the approach of R. Cramer and I. Damgård from Crypto 2009 (not 2010 as wrongly stated in the abstract) [Lect. Notes Comput. Sci. 5677, 177–191 (2009; Zbl 1252.94056)], but gives a much tighter bound on what we can extract from a dishonest prover. Towards achieving this result, we develop an analysis for bins-and-balls games that might be of independent interest. We also provide a general analysis of rewinding of a cut-and-choose protocol as well as a method to use Lyubachevsky’s rejection sampling technique efficiently in an interactive protocol when many proofs are given simultaneously.{
}
Our new protocol yields improved proofs of plaintext knowledge for (ring-)LWE-based cryptosystems, where such general techniques were not known before. Moreover, they can be extended to prove preimages of homomorphic hash functions as well.
For the entire collection see [Zbl 1344.94003].
MSC:
References:
| [1] | Benhamouda, F., Camenisch, J., Krenn, S., Lyubashevsky, V., Neven, G.: Better zero-knowledge proofs for lattice encryption and their application to group signatures. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 551–572. Springer, Heidelberg (2014) · Zbl 1306.94026 · doi:10.1007/978-3-662-45611-8_29 |
| [2] | Bendlin, R., Damgård, I., Orlandi, C., Zakarias, S.: Semi-homomorphic encryption and multiparty computation. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 169–188. Springer, Heidelberg (2011) · Zbl 1281.94015 · doi:10.1007/978-3-642-20465-4_11 |
| [3] | Baum, C., Damgård, I., Toft, T., Zakarias, R.: Better preprocessing for secure multiparty computation. In: Manulis, M., Sadeghi, A.-R., Schneider, S. (eds.) ACNS 2016. LNCS, vol. 9696, pp. 327–345. Springer, Heidelberg (2016). doi: 10.1007/978-3-319-39555-5_18 · Zbl 1346.68085 · doi:10.1007/978-3-319-39555-5_18 |
| [4] | Bellare, M., Goldreich, O.: On defining proofs of knowledge. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 390–420. Springer, Heidelberg (1993) · Zbl 0823.94016 · doi:10.1007/3-540-48071-4_28 |
| [5] | Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS 2012, pp. 309–325. ACM, New York (2012) · Zbl 1347.68120 · doi:10.1145/2090236.2090262 |
| [6] | Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. SIAM J. Comput. 43(2), 831–871 (2014) · Zbl 1302.94037 · doi:10.1137/120868669 |
| [7] | Cramer, R., Damgård, I.: On the amortized complexity of zero-knowledge protocols. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 177–191. Springer, Heidelberg (2009) · Zbl 1252.94056 · doi:10.1007/978-3-642-03356-8_11 |
| [8] | Damgård, I.B., Fujisaki, E.: A statistically-hiding integer commitment scheme based on groups with hidden order. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 125–142. Springer, Heidelberg (2002) · Zbl 1065.94545 |
| [9] | Damgård, I., Keller, M., Larraia, E., Pastro, V., Scholl, P., Smart, N.P.: Practical covertly secure MPC for dishonest majority – or: breaking the SPDZ limits. In: Crampton, J., Jajodia, S., Mayes, K. (eds.) ESORICS 2013. LNCS, vol. 8134, pp. 1–18. Springer, Heidelberg (2013) · Zbl 1406.94041 · doi:10.1007/978-3-642-40203-6_1 |
| [10] | Damgård, I., Pastro, V., Smart, N., Zakarias, S.: Multiparty computation from somewhat homomorphic encryption. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 643–662. Springer, Heidelberg (2012) · Zbl 1296.94104 · doi:10.1007/978-3-642-32009-5_38 |
| [11] | Goldreich, O., Goldwasser, S., Halevi, S.: Collision-free hashing from lattice problems. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 3, pp. 236–241 (1996) · Zbl 1343.94055 |
| [12] | Gentry, C., Sahai, A., Waters, B.: Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 75–92. Springer, Heidelberg (2013) · Zbl 1310.94148 · doi:10.1007/978-3-642-40041-4_5 |
| [13] | Katz, J., Lindell, Y.: Introduction to Modern Cryptography. CRC Press, Boca Raton (2014) · Zbl 1323.94001 |
| [14] | Lyubashevsky, V., Micciancio, D., Peikert, C., Rosen, A.: SWIFFT: a modest proposal for FFT hashing. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 54–72. Springer, Heidelberg (2008) · Zbl 1154.68403 · doi:10.1007/978-3-540-71039-4_4 |
| [15] | Ling, S., Nguyen, K., Stehlé, D., Wang, H.: Improved zero-knowledge proofs of knowledge for the ISIS problem, and applications. In: Hanaoka, G., Kurosawa, K. (eds.) PKC 2013. LNCS, vol. 7778, pp. 107–124. Springer, Heidelberg (2013) · Zbl 1314.94087 · doi:10.1007/978-3-642-36362-7_8 |
| [16] | Luby, M.: Lt codes. In: Proceedings of the 43rd Symposium on Foundations of Computer Science, p. 271. IEEE Computer Society (2002) · doi:10.1109/SFCS.2002.1181950 |
| [17] | Lyubashevsky, V.: Lattice-based identification schemes secure under active attacks. In: Cramer, R. (ed.) PKC 2008. LNCS, vol. 4939, pp. 162–179. Springer, Heidelberg (2008) · Zbl 1162.94388 · doi:10.1007/978-3-540-78440-1_10 |
| [18] | Lyubashevsky, V.: Fiat-Shamir with aborts: applications to lattice and factoring-based signatures. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 598–616. Springer, Heidelberg (2009) · Zbl 1267.94125 · doi:10.1007/978-3-642-10366-7_35 |
| [19] | Nielsen, J.B., Orlandi, C.: LEGO for two-party secure computation. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 368–386. Springer, Heidelberg (2009) · Zbl 1213.94124 · doi:10.1007/978-3-642-00457-5_22 |
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.