Document Open Access Logo

Limits to Non-Malleability

Authors Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni, Tal Malkin

PDF

File

Thumbnail PDF
PDF
LIPIcs.ITCS.2020.80.pdf
  • Filesize: 0.66 MB
  • 32 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Security and privacy → Information-theoretic techniques
  • Security and privacy → Mathematical foundations of cryptography
  • Security and privacy → Cryptography
Keywords
  • non-malleable codes
  • black-box impossibility
  • tamper-resilient cryptogtaphy
  • average-case hardness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

There have been many successes in constructing explicit non-malleable codes for various classes of tampering functions in recent years, and strong existential results are also known. In this work we ask the following question:
When can we rule out the existence of a non-malleable code for a tampering class ℱ?
First, we start with some classes where positive results are well-known, and show that when these classes are extended in a natural way, non-malleable codes are no longer possible. Specifically, we show that no non-malleable codes exist for any of the following tampering classes: 
- Functions that change d/2 symbols, where d is the distance of the code; 
- Functions where each input symbol affects only a single output symbol; 
- Functions where each of the n output bits is a function of n-log n input bits. 
Furthermore, we rule out constructions of non-malleable codes for certain classes ℱ via reductions to the assumption that a distributional problem is hard for ℱ, that make black-box use of the tampering functions in the proof. In particular, this yields concrete obstacles for the construction of efficient codes for NC, even assuming average-case variants of P ⊈ NC.

Cite As Get BibTex

Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni, and Tal Malkin. Limits to Non-Malleability. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 80:1-80:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ITCS.2020.80

Author Details

Marshall Ball
  • Columbia University, New York City, NY, USA
Dana Dachman-Soled
  • University of Maryland, College Park, MD, USA
Mukul Kulkarni
  • University of Massachusetts Amherst, MA, USA
Tal Malkin
  • Columbia University, New York City, NY, USA

Funding

The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies, either express or implied, of ODNI, IARPA, or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright annotation therein.
  • Ball, Marshall: M. Ball is supported by an IBM Research PhD Fellowship. This research is based upon work supported in part by the Office of the Director of National Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA) via Contract No. 2019-1902070006.
  • Dachman-Soled, Dana: This work is supported in part by NSF grants #CNS-1933033, #CNS-1840893, #CNS-1453045 (CAREER), by a research partnership award from Cisco and by financial assistance award 70NANB15H328 from the U.S. Department of Commerce, National Institute of Standards and Technology.
  • Malkin, Tal: This research is based upon work supported in part by the Office of the Director of National Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA) via Contract No. 2019-1902070006.

References

  1. Masayuki Abe, Jens Groth, and Miyako Ohkubo. Separating Short Structure-Preserving Signatures from Non-interactive Assumptions. In Dong Hoon Lee and Xiaoyun Wang, editors, ASIACRYPT 2011, volume 7073 of LNCS, pages 628-646. Springer, Heidelberg, December 2011. URL: https://doi.org/10.1007/978-3-642-25385-0_34.
  2. Divesh Aggarwal, Shashank Agrawal, Divya Gupta, Hemanta K. Maji, Omkant Pandey, and Manoj Prabhakaran. Optimal Computational Split-state Non-malleable Codes. In Eyal Kushilevitz and Tal Malkin, editors, TCC 2016-A, Part II, volume 9563 of LNCS, pages 393-417. Springer, Heidelberg, January 2016. URL: https://doi.org/10.1007/978-3-662-49099-0_15.
  3. Divesh Aggarwal, Yevgeniy Dodis, Tomasz Kazana, and Maciej Obremski. Non-malleable Reductions and Applications. In Rocco A. Servedio and Ronitt Rubinfeld, editors, 47th ACM STOC, pages 459-468. ACM Press, June 2015. URL: https://doi.org/10.1145/2746539.2746544.
  4. Divesh Aggarwal, Yevgeniy Dodis, and Shachar Lovett. Non-malleable codes from additive combinatorics. In David B. Shmoys, editor, 46th ACM STOC, pages 774-783. ACM Press, May/June 2014. URL: https://doi.org/10.1145/2591796.2591804.
  5. Divesh Aggarwal, Nico Döttling, Jesper Buus Nielsen, Maciej Obremski, and Erick Purwanto. Continuous Non-Malleable Codes in the 8-Split-State Model. In Yuval Ishai and Vincent Rijmen, editors, EUROCRYPT 2019, Part I, volume 11476 of LNCS, pages 531-561. Springer, Heidelberg, May 2019. URL: https://doi.org/10.1007/978-3-030-17653-2_18.
  6. Divesh Aggarwal, Stefan Dziembowski, Tomasz Kazana, and Maciej Obremski. Leakage-Resilient Non-malleable Codes. In Yevgeniy Dodis and Jesper Buus Nielsen, editors, TCC 2015, Part I, volume 9014 of LNCS, pages 398-426. Springer, Heidelberg, March 2015. URL: https://doi.org/10.1007/978-3-662-46494-6_17.
  7. Divesh Aggarwal and Maciej Obremski. Inception makes non-malleable codes shorter as well! Cryptology ePrint Archive, Report 2019/399, 2019. URL: https://eprint.iacr.org/2019/399.
  8. Shashank Agrawal, Divya Gupta, Hemanta K. Maji, Omkant Pandey, and Manoj Prabhakaran. A Rate-Optimizing Compiler for Non-malleable Codes Against Bit-Wise Tampering and Permutations. In Yevgeniy Dodis and Jesper Buus Nielsen, editors, TCC 2015, Part I, volume 9014 of LNCS, pages 375-397. Springer, Heidelberg, March 2015. URL: https://doi.org/10.1007/978-3-662-46494-6_16.
  9. Shashank Agrawal, Divya Gupta, Hemanta K. Maji, Omkant Pandey, and Manoj Prabhakaran. Explicit Non-malleable Codes Against Bit-Wise Tampering and Permutations. In Rosario Gennaro and Matthew J. B. Robshaw, editors, CRYPTO 2015, Part I, volume 9215 of LNCS, pages 538-557. Springer, Heidelberg, August 2015. URL: https://doi.org/10.1007/978-3-662-47989-6_26.
  10. Miklós Ajtai, János Komlós, and Endre Szemerédi. An O(n log n) Sorting Network. In David S. Johnson, Ronald Fagin, Michael L. Fredman, David Harel, Richard M. Karp, Nancy A. Lynch, Christos H. Papadimitriou, Ronald L. Rivest, Walter L. Ruzzo, and Joel I. Seiferas, editors, Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA, pages 1-9. ACM, 1983. URL: https://doi.org/10.1145/800061.808726.
  11. Marcin Andrychowicz, Ivan Damgård, Stefan Dziembowski, Sebastian Faust, and Antigoni Polychroniadou. Efficient Leakage Resilient Circuit Compilers. In Kaisa Nyberg, editor, CT-RSA 2015, volume 9048 of LNCS, pages 311-329. Springer, Heidelberg, April 2015. URL: https://doi.org/10.1007/978-3-319-16715-2_17.
  12. Benny Applebaum. Cryptography in Constant Parallel Time. Information Security and Cryptography. Springer, 2014. URL: https://doi.org/10.1007/978-3-642-17367-7.
  13. Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. Cryptography in NC⁰. In 45th FOCS, pages 166-175. IEEE Computer Society Press, October 2004. URL: https://doi.org/10.1109/FOCS.2004.20.
  14. Benny Applebaum and Pavel Raykov. On the Relationship Between Statistical Zero-Knowledge and Statistical Randomized Encodings. In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part III, volume 9816 of LNCS, pages 449-477. Springer, Heidelberg, August 2016. URL: https://doi.org/10.1007/978-3-662-53015-3_16.
  15. Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, and Li-Yang Tan. Non-Malleable Codes for Small-Depth Circuits. In Mikkel Thorup, editor, 59th FOCS, pages 826-837. IEEE Computer Society Press, October 2018. URL: https://doi.org/10.1109/FOCS.2018.00083.
  16. Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni, Huijia Lin, and Tal Malkin. Non-Malleable Codes Against Bounded Polynomial Time Tampering. In Yuval Ishai and Vincent Rijmen, editors, EUROCRYPT 2019, Part I, volume 11476 of LNCS, pages 501-530. Springer, Heidelberg, May 2019. URL: https://doi.org/10.1007/978-3-030-17653-2_17.
  17. Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni, and Tal Malkin. Non-malleable Codes for Bounded Depth, Bounded Fan-In Circuits. In Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, Part II, volume 9666 of LNCS, pages 881-908. Springer, Heidelberg, May 2016. URL: https://doi.org/10.1007/978-3-662-49896-5_31.
  18. Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni, and Tal Malkin. Non-malleable Codes from Average-Case Hardness: AC⁰, Decision Trees, and Streaming Space-Bounded Tampering. In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part III, volume 10822 of LNCS, pages 618-650. Springer, Heidelberg, April/May 2018. URL: https://doi.org/10.1007/978-3-319-78372-7_20.
  19. Marshall Ball, Siyao Guo, and Daniel Wichs. Non-Malleable Codes for Decision Trees. IACR Cryptology ePrint Archive, 2019:379, 2019. Google Scholar
  20. Boaz Barak and Mohammad Mahmoody-Ghidary. Merkle puzzles are optimal - an O(n²)-query attack on any key exchange from a random oracle. In Shai Halevi, editor, CRYPTO 2009, volume 5677 of LNCS, pages 374-390. Springer, Heidelberg, August 2009. URL: https://doi.org/10.1007/978-3-642-03356-8_22.
  21. Nir Bitansky, Shafi Goldwasser, Abhishek Jain, Omer Paneth, Vinod Vaikuntanathan, and Brent Waters. Time-Lock Puzzles from Randomized Encodings. In Madhu Sudan, editor, ITCS 2016, pages 345-356. ACM, January 2016. URL: https://doi.org/10.1145/2840728.2840745.
  22. Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci., 288(1):21-43, 2002. URL: https://doi.org/10.1016/S0304-3975(01)00144-X.
  23. Nishanth Chandran, Vipul Goyal, Pratyay Mukherjee, Omkant Pandey, and Jalaj Upadhyay. Block-Wise Non-Malleable Codes. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, ICALP 2016, volume 55 of LIPIcs, pages 31:1-31:14. Schloss Dagstuhl, July 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.31.
  24. Nishanth Chandran, Bhavana Kanukurthi, and Rafail Ostrovsky. Locally Updatable and Locally Decodable Codes. In Yehuda Lindell, editor, TCC 2014, volume 8349 of LNCS, pages 489-514. Springer, Heidelberg, February 2014. URL: https://doi.org/10.1007/978-3-642-54242-8_21.
  25. Nishanth Chandran, Bhavana Kanukurthi, and Srinivasan Raghuraman. Information-Theoretic Local Non-malleable Codes and Their Applications. In Eyal Kushilevitz and Tal Malkin, editors, TCC 2016-A, Part II, volume 9563 of LNCS, pages 367-392. Springer, Heidelberg, January 2016. URL: https://doi.org/10.1007/978-3-662-49099-0_14.
  26. Eshan Chattopadhyay, Vipul Goyal, and Xin Li. Non-malleable extractors and codes, with their many tampered extensions. In Daniel Wichs and Yishay Mansour, editors, 48th ACM STOC, pages 285-298. ACM Press, June 2016. URL: https://doi.org/10.1145/2897518.2897547.
  27. Eshan Chattopadhyay, Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, and Sruthi Sekar. Privacy Amplification from Non-malleable Codes. Cryptology ePrint Archive, Report 2018/293, 2018. URL: https://eprint.iacr.org/2018/293.
  28. Eshan Chattopadhyay and Xin Li. Non-malleable codes and extractors for small-depth circuits, and affine functions. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 1171-1184. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055483.
  29. Eshan Chattopadhyay and Xin Li. Non-malleable codes and extractors for small-depth circuits, and affine functions. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, 49th ACM STOC, pages 1171-1184. ACM Press, June 2017. Google Scholar
  30. Eshan Chattopadhyay and Xin Li. Non-Malleable Extractors and Codes for Composition of Tampering, Interleaved Tampering and More. Cryptology ePrint Archive, Report 2018/1069, 2018. URL: https://eprint.iacr.org/2018/1069.
  31. Eshan Chattopadhyay and David Zuckerman. Non-malleable Codes against Constant Split-State Tampering. In 55th FOCS, pages 306-315. IEEE Computer Society Press, October 2014. URL: https://doi.org/10.1109/FOCS.2014.40.
  32. Binyi Chen, Yilei Chen, Kristina Hostáková, and Pratyay Mukherjee. Continuous Space-Bounded Non-malleable Codes from Stronger Proofs-of-Space. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part I, volume 11692 of LNCS, pages 467-495. Springer, Heidelberg, August 2019. URL: https://doi.org/10.1007/978-3-030-26948-7_17.
  33. Mahdi Cheraghchi and Venkatesan Guruswami. Capacity of non-malleable codes. In Moni Naor, editor, ITCS 2014, pages 155-168. ACM, January 2014. URL: https://doi.org/10.1145/2554797.2554814.
  34. Mahdi Cheraghchi and Venkatesan Guruswami. Non-malleable Coding against Bit-Wise and Split-State Tampering. In Yehuda Lindell, editor, TCC 2014, volume 8349 of LNCS, pages 440-464. Springer, Heidelberg, February 2014. URL: https://doi.org/10.1007/978-3-642-54242-8_19.
  35. Sandro Coretti, Antonio Faonio, and Daniele Venturi. Rate-Optimizing Compilers for Continuously Non-Malleable Codes. Cryptology ePrint Archive, Report 2019/055, 2019. URL: https://eprint.iacr.org/2019/055.
  36. Jean-Sébastien Coron. Security Proof for Partial-Domain Hash Signature Schemes. In Moti Yung, editor, CRYPTO 2002, volume 2442 of LNCS, pages 613-626. Springer, Heidelberg, August 2002. URL: https://doi.org/10.1007/3-540-45708-9_39.
  37. Dana Dachman-Soled and Mukul Kulkarni. Upper and Lower Bounds for Continuous Non-Malleable Codes. In Dongdai Lin and Kazue Sako, editors, PKC 2019, Part I, volume 11442 of LNCS, pages 519-548. Springer, Heidelberg, April 2019. URL: https://doi.org/10.1007/978-3-030-17253-4_18.
  38. Dana Dachman-Soled, Mukul Kulkarni, and Aria Shahverdi. Tight Upper and Lower Bounds for Leakage-Resilient, Locally Decodable and Updatable Non-malleable Codes. In Serge Fehr, editor, PKC 2017, Part I, volume 10174 of LNCS, pages 310-332. Springer, Heidelberg, March 2017. URL: https://doi.org/10.1007/978-3-662-54365-8_13.
  39. Dana Dachman-Soled, Mukul Kulkarni, and Aria Shahverdi. Local Non-malleable Codes in the Bounded Retrieval Model. In Michel Abdalla and Ricardo Dahab, editors, PKC 2018, Part II, volume 10770 of LNCS, pages 281-311. Springer, Heidelberg, March 2018. URL: https://doi.org/10.1007/978-3-319-76581-5_10.
  40. Dana Dachman-Soled, Feng-Hao Liu, Elaine Shi, and Hong-Sheng Zhou. Locally Decodable and Updatable Non-malleable Codes and Their Applications. In Yevgeniy Dodis and Jesper Buus Nielsen, editors, TCC 2015, Part I, volume 9014 of LNCS, pages 427-450. Springer, Heidelberg, March 2015. URL: https://doi.org/10.1007/978-3-662-46494-6_18.
  41. Akshay Degwekar, Vinod Vaikuntanathan, and Prashant Nalini Vasudevan. Fine-Grained Cryptography. In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part III, volume 9816 of LNCS, pages 533-562. Springer, Heidelberg, August 2016. URL: https://doi.org/10.1007/978-3-662-53015-3_19.
  42. Stefan Dziembowski, Tomasz Kazana, and Maciej Obremski. Non-malleable Codes from Two-Source Extractors. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part II, volume 8043 of LNCS, pages 239-257. Springer, Heidelberg, August 2013. URL: https://doi.org/10.1007/978-3-642-40084-1_14.
  43. Stefan Dziembowski, Krzysztof Pietrzak, and Daniel Wichs. Non-Malleable Codes. J. ACM, 65(4):20:1-20:32, April 2018. Extended abstract appeared in Innovations in Computer Science (ICS) 2010. URL: https://doi.org/10.1145/3178432.
  44. Antonio Faonio, Jesper Buus Nielsen, Mark Simkin, and Daniele Venturi. Continuously Non-malleable Codes with Split-State Refresh. In Bart Preneel and Frederik Vercauteren, editors, ACNS 18, volume 10892 of LNCS, pages 121-139. Springer, Heidelberg, July 2018. URL: https://doi.org/10.1007/978-3-319-93387-0_7.
  45. Sebastian Faust, Kristina Hostáková, Pratyay Mukherjee, and Daniele Venturi. Non-Malleable Codes for Space-Bounded Tampering. In Jonathan Katz and Hovav Shacham, editors, CRYPTO 2017, Part II, volume 10402 of LNCS, pages 95-126. Springer, Heidelberg, August 2017. URL: https://doi.org/10.1007/978-3-319-63715-0_4.
  46. Sebastian Faust, Pratyay Mukherjee, Jesper Buus Nielsen, and Daniele Venturi. Continuous Non-malleable Codes. In Yehuda Lindell, editor, TCC 2014, volume 8349 of LNCS, pages 465-488. Springer, Heidelberg, February 2014. URL: https://doi.org/10.1007/978-3-642-54242-8_20.
  47. Sebastian Faust, Pratyay Mukherjee, Jesper Buus Nielsen, and Daniele Venturi. A Tamper and Leakage Resilient von Neumann Architecture. In Jonathan Katz, editor, PKC 2015, volume 9020 of LNCS, pages 579-603. Springer, Heidelberg, March/April 2015. URL: https://doi.org/10.1007/978-3-662-46447-2_26.
  48. Sebastian Faust, Pratyay Mukherjee, Daniele Venturi, and Daniel Wichs. Efficient Non-malleable Codes and Key-Derivation for Poly-size Tampering Circuits. In Phong Q. Nguyen and Elisabeth Oswald, editors, EUROCRYPT 2014, volume 8441 of LNCS, pages 111-128. Springer, Heidelberg, May 2014. URL: https://doi.org/10.1007/978-3-642-55220-5_7.
  49. Marc Fischlin and Dominique Schröder. On the Impossibility of Three-Move Blind Signature Schemes. In Henri Gilbert, editor, EUROCRYPT 2010, volume 6110 of LNCS, pages 197-215. Springer, Heidelberg, May/June 2010. URL: https://doi.org/10.1007/978-3-642-13190-5_10.
  50. Georg Fuchsbauer, Momchil Konstantinov, Krzysztof Pietrzak, and Vanishree Rao. Adaptive Security of Constrained PRFs. In Palash Sarkar and Tetsu Iwata, editors, ASIACRYPT 2014, Part II, volume 8874 of LNCS, pages 82-101. Springer, Heidelberg, December 2014. URL: https://doi.org/10.1007/978-3-662-45608-8_5.
  51. Sanjam Garg, Raghav Bhaskar, and Satyanarayana V. Lokam. Improved Bounds on Security Reductions for Discrete Log Based Signatures. In David Wagner, editor, CRYPTO 2008, volume 5157 of LNCS, pages 93-107. Springer, Heidelberg, August 2008. URL: https://doi.org/10.1007/978-3-540-85174-5_6.
  52. Craig Gentry and Daniel Wichs. Separating succinct non-interactive arguments from all falsifiable assumptions. In Lance Fortnow and Salil P. Vadhan, editors, 43rd ACM STOC, pages 99-108. ACM Press, June 2011. URL: https://doi.org/10.1145/1993636.1993651.
  53. Yael Gertner, Sampath Kannan, Tal Malkin, Omer Reingold, and Mahesh Viswanathan. The Relationship between Public Key Encryption and Oblivious Transfer. In 41st FOCS, pages 325-335. IEEE Computer Society Press, November 2000. URL: https://doi.org/10.1109/SFCS.2000.892121.
  54. Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to Construct Random Functions (Extended Abstract). In 25th FOCS, pages 464-479. IEEE Computer Society Press, October 1984. URL: https://doi.org/10.1109/SFCS.1984.715949.
  55. Russell Impagliazzo. Hard-Core Distributions for Somewhat Hard Problems. In 36th FOCS, pages 538-545. IEEE Computer Society Press, October 1995. URL: https://doi.org/10.1109/SFCS.1995.492584.
  56. Russell Impagliazzo and Steven Rudich. Limits on the Provable Consequences of One-Way Permutations. In 21st ACM STOC, pages 44-61. ACM Press, May 1989. URL: https://doi.org/10.1145/73007.73012.
  57. Zahra Jafargholi and Daniel Wichs. Tamper Detection and Continuous Non-malleable Codes. In Yevgeniy Dodis and Jesper Buus Nielsen, editors, TCC 2015, Part I, volume 9014 of LNCS, pages 451-480. Springer, Heidelberg, March 2015. URL: https://doi.org/10.1007/978-3-662-46494-6_19.
  58. Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, and Sruthi Sekar. Four-State Non-malleable Codes with Explicit Constant Rate. In Yael Kalai and Leonid Reyzin, editors, TCC 2017, Part II, volume 10678 of LNCS, pages 344-375. Springer, Heidelberg, November 2017. URL: https://doi.org/10.1007/978-3-319-70503-3_11.
  59. Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, and Sruthi Sekar. Non-malleable Randomness Encoders and Their Applications. In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part III, volume 10822 of LNCS, pages 589-617. Springer, Heidelberg, April/May 2018. URL: https://doi.org/10.1007/978-3-319-78372-7_19.
  60. Aggelos Kiayias, Feng-Hao Liu, and Yiannis Tselekounis. Practical Non-Malleable Codes from l-more Extractable Hash Functions. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 2016, pages 1317-1328. ACM Press, October 2016. URL: https://doi.org/10.1145/2976749.2978352.
  61. Aggelos Kiayias, Feng-Hao Liu, and Yiannis Tselekounis. Non-Malleable Codes for Partial Functions with Manipulation Detection. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part III, volume 10993 of LNCS, pages 577-607. Springer, Heidelberg, August 2018. URL: https://doi.org/10.1007/978-3-319-96878-0_20.
  62. Xin Li. Improved non-malleable extractors, non-malleable codes and independent source extractors. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, 49th ACM STOC, pages 1144-1156. ACM Press, June 2017. URL: https://doi.org/10.1145/3055399.3055486.
  63. Xin Li. Non-Malleable Extractors and Non-Malleable Codes: Partially Optimal Constructions. Cryptology ePrint Archive, Report 2018/353, 2018. URL: https://eprint.iacr.org/2018/353.
  64. Feng-Hao Liu and Anna Lysyanskaya. Tamper and Leakage Resilience in the Split-State Model. In Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, pages 517-532. Springer, Heidelberg, August 2012. URL: https://doi.org/10.1007/978-3-642-32009-5_30.
  65. Rafail Ostrovsky, Giuseppe Persiano, Daniele Venturi, and Ivan Visconti. Continuously Non-Malleable Codes in the Split-State Model from Minimal Assumptions. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part III, volume 10993 of LNCS, pages 608-639. Springer, Heidelberg, August 2018. URL: https://doi.org/10.1007/978-3-319-96878-0_21.
  66. Pascal Paillier and Damien Vergnaud. Discrete-Log-Based Signatures May Not Be Equivalent to Discrete Log. In Bimal K. Roy, editor, ASIACRYPT 2005, volume 3788 of LNCS, pages 1-20. Springer, Heidelberg, December 2005. URL: https://doi.org/10.1007/11593447_1.
  67. Rafael Pass. Limits of provable security from standard assumptions. In Lance Fortnow and Salil P. Vadhan, editors, 43rd ACM STOC, pages 109-118. ACM Press, June 2011. URL: https://doi.org/10.1145/1993636.1993652.
  68. Peter M. R. Rasmussen and Amit Sahai. Expander Graphs are Non-Malleable Codes. Cryptology ePrint Archive, Report 2018/929, 2018. URL: https://eprint.iacr.org/2018/929.
  69. Omer Reingold, Luca Trevisan, and Salil P. Vadhan. Notions of Reducibility between Cryptographic Primitives. In Moni Naor, editor, TCC 2004, volume 2951 of LNCS, pages 1-20. Springer, Heidelberg, February 2004. URL: https://doi.org/10.1007/978-3-540-24638-1_1.
  70. Yannick Seurin. On the Exact Security of Schnorr-Type Signatures in the Random Oracle Model. In David Pointcheval and Thomas Johansson, editors, EUROCRYPT 2012, volume 7237 of LNCS, pages 554-571. Springer, Heidelberg, April 2012. URL: https://doi.org/10.1007/978-3-642-29011-4_33.
  71. Daniel R. Simon. Finding Collisions on a One-Way Street: Can Secure Hash Functions Be Based on General Assumptions? In Kaisa Nyberg, editor, EUROCRYPT'98, volume 1403 of LNCS, pages 334-345. Springer, Heidelberg, May/June 1998. URL: https://doi.org/10.1007/BFb0054137.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact