Document Type : Research Article
Authors
Sharif University of Technology
Abstract
A non-malleable code is a variant of an encoding scheme which is resilient to tampering attacks. The main idea behind non-malleable coding is that the adversary should not be able to obtain any valuable information about the message. Non-malleable codes are used in tamper-resilient cryptography and protecting memories against tampering attacks. Many different types of non-malleability have already been formalized and defined in current literature, among which continuous non-malleability is the setup in which the messages are protected against adversaries who may issue polynomially many tampering queries. The first continuous non-malleable encoding scheme has been proposed by Faust et al. (FMNV) in 2014. In this article, we propose a new proof of continuous non-malleability of the FMNV scheme. The new proof will give rise to an improved and more efficient version of this scheme. Also, the new proof shows that one may achieve continuous non-malleability of the same security by using a leakage resilient storage scheme with fewer bits for the leakage bound. This shows that the new scheme is more efficient and practical for tamper-resilient applications.
Keywords
[1] Amir S. Mortazavi, Mahmoud Salmasizadeh, and Amir Daneshgar. FMNV continuous nonmalleable encoding scheme is more efficient than believed. In 2016 13th International Iranian Society of Cryptology Conference on Information Security and Cryptology (ISCISC), pages 72-78, Sept 2016.
[2] Sebastian Faust, Pratyay Mukherjee, Jesper Buus Nielsen, and Daniele Venturi. Continuous non-malleable codes. In Theory of Cryptography - 11th Theory of Cryptography Conference, TCC 2014, Proceedings, volume 8349 of Lecture Notes in Computer Science, pages 465-488. Springer, 2014.
[3] Ronald Cramer, Yevgeniy Dodis, Serge Fehr, Carles Padró, and Daniel Wichs. Detection of algebraic manipulation with applications to robust secret sharing and fuzzy extractors. In Advances in Cryptology - EUROCRYPT 2008, 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, volume 4965 of Lecture Notes in Computer Science, pages 471- 488. Springer, 2008.
[4] Francesco Davì, Stefan Dziembowski, and Daniele Venturi. Leakage-resilient storage. In Security and Cryptography for Networks, 7th International Conference, SCN 2010, Proceedings, volume 6280 of Lecture Notes in Computer Science, pages 121-137. Springer, 2010.
[5] Mahdi Cheraghchi and Venkatesan Guruswami. Non-malleable coding against bit-wise and split-state tampering. In Theory of Cryptography 11th Theory of Cryptography Conference, TCC 2014, Proceedings, volume 8349 of Lecture Notes in Computer Science, pages 440-464. Springer, 2014.
[6] Seung Geol Choi, Aggelos Kiayias, and Tal Malkin. Bitr: Built-in tamper resilience. In Advances in Cryptology - ASIACRYPT 2011 - 17th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, volume 7073 of Lecture Notes in Computer Science, pages 740-758. Springer, 2011.
[7] Feng-Hao Liu and Anna Lysyanskaya. Tamper and leakage resilience in the split-state model. In Advances in Cryptology - CRYPTO 2012 - 32nd Annual Cryptology Conference, Proceedings, volume 7417 of Lecture Notes in Computer Science, pages 517-532. Springer, 2012.
[8] Zahra Jafargholi and Daniel Wichs. Tamper detection and continuous non-malleable codes. In Theory of Cryptography - 12th Theory of Cryptography Conference, TCC 2015, Proceedings, Part I, volume 9014 of Lecture Notes in Computer Science, pages 451-480. Springer, 2015.
[9] Sebastian Faust, Pratyay Mukherjee, Daniele Venturi, and Daniel Wichs. Efficient nonmalleable codes and key-derivation for poly-size tampering circuits. In Advances in Cryptology- EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, volume 8441 of Lecture Notes in Computer Science, pages 111-128. Springer, 2014.
[10] Divesh Aggarwal, Yevgeniy Dodis, Tomasz Kazana, and Maciej Obremski. Non-malleable reductions and applications. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015 [18], pages 459-468.
[11] Nishanth Chandran, Vipul Goyal, Pratyay Mukherjee, Omkant Pandey, and Jalaj Upadhyay. Block-wise non-malleable codes. IACR Cryptology ePrint Archive, 2015.
[12] Stefan Dziembowski, Tomasz Kazana, and Maciej Obremski. Non-malleable codes from two source extractors. In Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Proceedings, Part II, volume 8043 of Lecture Notes in Computer Science, pages 239-257. Springer, 2013.
[13] Divesh Aggarwal, Yevgeniy Dodis, and Shachar Lovett. Non-malleable codes from additive combinatorics. In Symposium on Theory of Computing, STOC 2014, pages 774-783. ACM, 2014.
[14] Eshan Chattopadhyay and David Zuckerman. Non-malleable codes against constant split-state tampering. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, pages 306-315. IEEE Computer Society, 2014.
[15] Divesh Aggarwal, Yevgeniy Dodis, Tomasz Kazana, and Maciej Obremski. Non-malleable reductions and applications. In Proceedings of the Forty Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, pages 459-468. ACM, 2015.
[16] Shashank Agrawal, Divya Gupta, Hemanta K. Maji, Omkant Pandey, and Manoj Prabhakaran. Explicit non-malleable codes resistant to permutations. Electronic Colloquium on Computational Complexity (ECCC), 21:69, 2014.
[17] Per Austrin, Kai-Min Chung, Mohammad Mahmoody, Rafael Pass, and Karn Seth. On the impossibility of cryptography with tamperable randomness. In Advances in Cryptology – CRYPTO 2014 - 34th Annual Cryptology Conference, Proceedings, Part I, volume 8616 of Lecture Notes in Computer Science, pages 462-479. Springer, 2014.
[18] Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015. ACM, 2015.
[19] Mihir Bellare, David Cash, and Rachel Miller. Cryptography secure against related-key attacks and tampering. In Advances in Cryptology - ASI- ACRYPT 2011 - 17th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, volume 7073 of Lecture Notes in Computer Science, pages 486-503. Springer, 2011.
[20] Mihir Bellare and Tadayoshi Kohno. A theoretical treatment of related-key attacks: Rka-prps, rka-prfs, and applications. In Advances in Cryptology - EUROCRYPT 2003, International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, volume 2656 of Lecture Notes in Computer Science, pages 491-506. Springer, 2003.
[21] Shashank Agrawal, Divya Gupta, Hemanta K. Maji, Omkant Pandey, and Manoj Prabhakaran. Explicit non-malleable codes against bit-wise tampering and permutations. In Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Proceedings, Part I, volume 9215 of Lecture Notes in Computer Science, pages 538-557. Springer, 2015.
[22] Yuval Ishai, Manoj Prabhakaran, Amit Sahai, and David Wagner. Private circuits II: keeping secrets in tamper able circuits. In Advances in Cryptology - EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, volume 4004 of Lecture Notes in Computer Science, pages 308-327. Springer, 2006.
[23] Yuval Ishai, Amit Sahai, and David Wagner. Private circuits: Securing hardware against probing attacks. In Advances in Cryptology - CRYPTO
2003, 23rd Annual International Cryptology Conference, Proceedings, volume 2729 of Lecture Notes in Computer Science, pages 463-481. Springer, 2003.
[24] Dana Dachman-Soled, Feng-Hao Liu, Elaine Shi, and Hong-Sheng Zhou. Locally decodable and updatable non-malleable codes and their applications. In Theory of Cryptography - 12th Theory of Cryptography Conference, TCC 2015, Proceedings, Part I, volume 9014 of Lecture Notes in Computer Science, pages 427-450. Springer, 2015.
[25] Sandro Coretti, Ueli Maurer, Björn Tackmann, and Daniele Venturi. From single-bit to multi-bit public-key encryption via non-malleable codes. In Theory of Cryptography - 12th Theory of Cryptography Conference, TCC 2015, Proceedings, Part I, volume 9014 of Lecture Notes in Computer Science, pages 532-560. Springer, 2015.
[26] Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography, chapter 3. Chapman & Hall/CRC Press, 2 edition, 2015.
[27] Alfredo De Santis, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano, and Amit Sahai. Robust non-interactive zero knowledge. In Advances in Cryptology - CRYPTO 2001, 21st Annual International Cryptology Conference, Santa Barbara, 2001,volume 2139 of Lecture Notes in Computer Science, pages 566-598. Springer, 2001.
)