nach oben

Designs, Codes and Cryptography

Erschienen in:

16.03.2017

Improved, black-box, non-malleable encryption from semantic security

verfasst von: Seung Geol Choi, Dana Dachman-Soled, Tal Malkin, Hoeteck Wee

Erschienen in: Designs, Codes and Cryptography | Ausgabe 3/2018

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We give a new black-box transformation from any semantically secure encryption scheme into a non-malleable one which has a better rate than the best previous work of Coretti et al. (in: Kushilevitz and Malkin (eds) TCC 2016-A, Part I, Springer, Heidelberg, 2016). We achieve a better rate by departing from the “matrix encoding” methodology used by previous constructions, and working directly with a single codeword. We also use a Shamir secret-share packing technique to improve the rate of the underlying error-correcting code.

Vorheriger Artikel Connecting tweakable and multi-key blockcipher security

Nächster Artikel CCZ equivalence of power functions

Nur mit Berechtigung zugänglich

We note that the result of Coretti et al. [10] showed that (a generalization) of the construction of [9] achieves not only NM-CPA security, but also a stronger notion of security—indistinguishability under (chosen-ciphertext) self-destruct attacks (IND-SDA)—where the adversary gets access to an adaptive decryption oracle that stops decrypting after the first invalid ciphertext is submitted.

In fact, according to [9], the number \(\varTheta (k^2)\) of calls to IND-CPA encryption can be optimized to \(\varTheta (k \log ^2 k)\); to achieve a negligible soundness error, the scheme checks k random positions, but observe it’s enough to check \(\log ^2 k\) positions since we have \(1/2^{\log ^2 k} = \mathsf {negl}(k)\). However, we choose to compare the results by using the non-optimized \(O(k^2)\) calls, following the presentation of Coretti et al. [10].

Ball M., Dachman-Soled D., Kulkarni M., Malkin T.: Non-malleable codes for bounded depth, bounded fan-in circuits. In: Fischlin M., Coron J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 881–908. Springer, Heidelberg (2016).CrossRef

Bellare M., Namprempre C.: Authenticated encryption: relations among notions and analysis of the generic composition paradigm. J. Cryptol. 21(4), 469–491 (2008).MathSciNetCrossRefMATH

Bellare M., Sahai A.: Non-malleable encryption: equivalence between two notions, and an indistinguishability-based characterization. In: Weiner M.J. (ed.) CRYPTO’99. LNCS, vol. 1666, pp. 519–536. Springer, Heidelberg (1999).

Ben-Or M., Goldwasser S., Wigderson A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 1–10 (1988).

Berlekamp E.R., Welch L.R.: Error correction for algebraic block codes. US Patent 4,633,470 (1986).

Canetti R., Halevi S., Katz J.: Chosen-ciphertext security from identity-based encryption. In: Cachin C., Camenisch J. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 207–222. Springer, Heidelberg (2004).CrossRef

Cheraghchi M., Guruswami V.: Non-malleable coding against bit-wise and split-state tampering. In: Yehuda L. (ed.) TCC 2014. LNCS, vol. 8349, pp. 440–464. Springer, Heidelberg (2014).

Choi S.G., Dachman-Soled D., Malkin T., Wee H.: A black-box construction of non-malleable encryption from semantically secure encryption. (2016). Full version of [8] eprint/2016/720.

Choi S.G., Dachman-Soled D., Malkin T., Wee H.: Black-box construction of a non-malleable encryption scheme from any semantically secure one. In: Canetti R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 427–444. Springer, Heidelberg (2008).

10.

Coretti S., Dodis Y., Tackmann B., Venturi D.: Non-malleable encryption: simpler, shorter, stronger. In: Eyal K., Tal M. (eds.) TCC 2016-A. LNCS, vol. 9562, pp. 306–335. Springer, Heidelberg (2016).

11.

Cramer R., Shoup V.: Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack. SIAM J. Comput. 33(1), 167–226 (2003).MathSciNetCrossRefMATH

12.

Cramer R., Hanaoka G., Hofheinz D., Imai H., Kiltz E., Pass R., Shelat A., Vaikuntanathan V.: Bounded CCA2-secure encryption. Advances in Cryptology (ASIACRYPT 2007). Lecture Notes in Computer Science, vol. 4833. Springer, Berlin (2007).

13.

Cramer R., Damgård I.B., Döttling N., Fehr S., Spini G.: Linear secret sharing schemes from error correcting codes and universal hash functions. In: Elisabeth O., Fischlin M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 313–336. Springer, Heidelberg (2015).

14.

Dachman-Soled D., Malkin T., Raykova M., Yung M.: Efficient robust private set intersection. In Applied Cryptography and Network Security, 7th International Conference, ACNS 2009. Lecture Notes in Computer Science, vol. 5536 (2009).

15.

Decatur S.E., Goldreich O., Ron D.: Computational sample complexity. SIAM J. Comput. 29(3), 854–879 (1999).MathSciNetCrossRefMATH

16.

Dolev D., Dwork C., Naor M.: Nonmalleable cryptography. SIAM J. Comput. 30(2), 391–437 (2000).MathSciNetCrossRefMATH

17.

Franklin M.K., Yung, M.: Communication Complexity of Secure Computation (extended abstract). In: 24th ACM STOC. pp. 699–710. ACM Press, New York (1992).

18.

Gay R., Hofheinz D., Kiltz E., Wee H.: Tightly CCA-secure encryption without pairings. In: Fischlin M., Coron J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 1–27. Springer, Heidelberg (2016).CrossRef

19.

Gertner Y., Malkin T., Myers S.: Towards a separation of semantic and CCA security for public key encryption. In: Proceedings of the 4th Theory of Cryptography Conference, TCC 2007. Lecture Notes in Computer Science, vol. 4392, pp. 434–455 (2007).

20.

Gilbert E.N.: A comparison of signalling alphabets. Bell Syst. Tech. J. 31, 504–522 (1952).CrossRef

21.

Goyal V., Lee C.-K., Ostrovsky R., Visconti I.: Constructing non-malleable commitments: a black-box approach. In: 53rd FOCS. pp. 51–60. IEEE Computer Society Press, Washington, DC (2012).

22.

Goyal V., Ostrovsky R., Scafuro A., Visconti I.: Black-box non-black-box zero knowledge. In: Shmoys D.B. (ed.) 46th ACM STOC, pp. 515–524. ACM Press, New York (2014).

23.

Herranz J., Hofheinz D., Kiltz E.: Some (in)sufficient conditions for secure hybrid encryption. Inf. Comput. 208(11), 1243–1257 (2010).MathSciNetCrossRefMATH

24.

Hofheinz D., Jager T.: Tightly secure signatures and public-key encryption. In: Safavi-Naini R., Canetti R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 590–607. Springer, Heidelberg (2012).CrossRef

25.

Kiltz E., Wee H.: Quasi-adaptive NIZK for linear subspaces revisited. In: Oswald E., Fischlin M. (eds.) EUROCRYPT 2015, Part II. LNCS, vol. 9057, pp. 101–128. Springer, Heidelberg (2015).

26.

Kiyoshima S.: Round-efficient black-box construction of composable multi-party computation. In: Garay J.A., Gennaro R. (eds.) CRYPTO 2014. LNCS. Springer, Heidelberg (2014).

27.

Kiyoshima S., Manabe Y., Okamoto T.: Constant-round black-box construction of composable multi-party computation protocol. In: Lindell Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 343–367. Springer, Heidelberg (2014).

28.

Lamport L.: Constructing digital signatures from a one-way function. Technical Report SRI-CSL-98, SRI International Computer Science Laboratory (1979).

29.

Libert B., Peters T., Joye M., Yung M.: Non-malleability from malleability: simulation-sound quasi-adaptive NIZK proofs and CCA2-secure encryption from homomorphic signatures. In: Nguyen P.Q., Oswald E. (eds.) EUROCRYPT 2014. LNCS. vol. 8441, pp. 514–532. Springer, Heidelberg (2014).

30.

Libert B., Peters T., Joye M., Yung M.: Compactly hiding linear spans—tightly secure constant-size simulation-sound QA-NIZK proofs and applications. In: Iwata T., Cheon J.H. (eds.) ASIACRYPT 2015, Part I. LNCS, vol. 9452, pp. 681–707. Springer, Heidelberg (2015).

31.

Lin H., Pass R.: Black-box constructions of composable protocols without set-up. In: Safavi-Naini R., Canetti R. (eds.) CRYPTO 2012. LNCS, vol. 7417. Springer, Heidelberg (2012).

32.

Myers S., Shelat A.: Bit encryption is complete. In: 50th FOCS. pp. 607–616. IEEE Computer Society Press, New York (2009)

33.

Pass R., Wee H.: Black-box constructions of two-party protocols from one-way functions. In: Proceedings of the 6th Theory of Cryptography Conference, TCC 2009, Lecture Notes in Computer Science, vol. 5444, pp. 403–418 (2009).

34.

Pass R., Shelat A., Vaikuntanathan V.: Construction of a non-malleable encryption scheme from any semantically secure one. In: Advances in Cryptology (CRYPTO 2006). Lecture Notes in Computer Science, vol. 4117, pp. 271–289 (2006).

35.

Peikert C., Waters B.: Lossy trapdoor functions and their applications. In: Ladner R.E., Dwork C. (eds.) 40th ACM STOC, pp. 187–196. ACM Press, New York (2008).

36.

Rompel, J.: One-way functions are necessary and sufficient for secure signatures. In: Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing. pp. 387–394 (1990).

37.

Rosen A., Segev G.: Chosen-ciphertext security via correlated products. SIAM J. Comput. 39(7), 3058–3088 (2010).MathSciNetCrossRefMATH

38.

Varshamov R.R.: Estimate of the number of signals in error correcting codes. Doklady Akad. Nauk SSSR 117, 739–741 (1957).MathSciNetMATH

39.

Wee H.: Black-box, round-efficient secure computation via non-malleability amplification. 51st FOCS, pp. 531–540. IEEE Computer Society Press, New York (2010).

40.

Wee H.: Dual projective hashing and its applications—lossy trapdoor functions and more. In: Pointcheval D., Johansson T. (eds.) EUROCRYPT 2012. LNCS, pp. 246–262. Springer, Heidelberg (2012).CrossRef

Titel: Improved, black-box, non-malleable encryption from semantic security
verfasst von: Seung Geol Choi
Dana Dachman-Soled
Tal Malkin
Hoeteck Wee
Publikationsdatum: 16.03.2017
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 3/2018
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-017-0348-2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 3/2018

Extension sets, affine designs, and Hamada’s conjecture

Connecting tweakable and multi-key blockcipher security

On Bonisoli’s theorem and the block codes of Steiner triple systems

-double cyclic codes

Tightly CCA-secure identity-based encryption with ciphertext pseudorandomness

Editor’s note