Advances in Cryptology – crypto 2020
Download 262.96 Kb. Pdf ko'rish
|
2020 Bookmatter AdvancesInCryptologyCRYPTO2020
- Bu sahifa navigatsiya:
- Document Outline
|
Lecture Notes in Computer Science 12170
Founding Editors Gerhard Goos Karlsruhe Institute of Technology, Karlsruhe, Germany Juris Hartmanis Cornell University, Ithaca, NY, USA Editorial Board Members Elisa Bertino Purdue University, West Lafayette, IN, USA Wen Gao Peking University, Beijing, China Bernhard Steffen TU Dortmund University, Dortmund, Germany Gerhard Woeginger RWTH Aachen, Aachen, Germany Moti Yung Columbia University, New York, NY, USA More information about this series at http://www.springer.com/series/7410 Daniele Micciancio • Thomas Ristenpart (Eds.) Advances in Cryptology – CRYPTO 2020 40th Annual International Cryptology Conference, CRYPTO 2020 Santa Barbara, CA, USA, August 17 –21, 2020 Proceedings, Part I 123
Editors Daniele Micciancio UC San Diego La Jolla, CA, USA Thomas Ristenpart Cornell Tech New York, NY, USA ISSN 0302-9743 ISSN 1611-3349 (electronic) Lecture Notes in Computer Science ISBN 978-3-030-56783-5 ISBN 978-3-030-56784-2 (eBook)
https://doi.org/10.1007/978-3-030-56784-2 LNCS Sublibrary: SL4 – Security and Cryptology © International Association for Cryptologic Research 2020 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, speci fically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on micro films or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a speci fic statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, expressed or implied, with respect to the material contained herein or for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictional claims in published maps and institutional af filiations. This Springer imprint is published by the registered company Springer Nature Switzerland AG The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland
Preface The 40th International Cryptology Conference (Crypto 2020), sponsored by the International Association of Cryptologic Research (IACR), was exceptional in many ways. The COVID-19 pandemic meant that for the first time in the conference’s 40-year history, Crypto was not held at the University of California, Santa Barbara. Safety mandated that we shift to an online-only virtual conference. Crypto 2020 received 371 submissions. Review occurred during what, for many countries, was the height thus far of pandemic spread and lockdowns. We thank the 54 person Program Committee (PC) and the 286 external reviewers for their efforts to ensure that, in the face of challenging work environments, illness, and death, we nevertheless were able to perform a standard double-blind review process in which papers received multiple independent reviews, authors were allowed a rebuttal, and papers were subsequently further reviewed and discussed. The two program chairs were not allowed to submit a paper, and PC members were limited to two submissions each. The PC ultimately selected 85 papers for acceptance, a record number for Crypto. The PC selected four papers to receive recognition via awards, via a voting-based process that took into account con flicts of interest (including for the program chairs). Three papers were selected to receive a Best Paper award and were invited to the Journal of Cryptology: “Improved Differential-Linear Attacks with Applications to ARX Ciphers ” by Christof Beierle, Gregor Leander, and Yosuke Todo; “Breaking the Decisional Dif fie-Hellman Problem for Class Group Actions using Genus Theory” by Wouter Castryck, Jana Sot áková, and Frederik Vercauteren; and “Chosen Ciphertext Security from Injective Trapdoor Functions ” by Susan Hohenberger, Venkata Koppula, and Brent Waters. One paper was selected to receive the Best Paper by Early Career Researchers award: “Handling Adaptive Compromise for Practical Encryption Schemes
” by Joseph Jaeger and Nirvan Tyagi. In addition to the regular program, Crypto 2020 included the IACR Distinguished Lecture by Silvio Micali on “Our Models and Us” and an invited talk by Seny Kamara on “Crypto for the People”. Crypto 2020 carried forward the long-standing tradition of having a rump session, this year organized in a virtual format by Antigoni Polychro- niadou, Bertram Poettering, and Martijn Stam. The chairs would also like to thank the many people whose hard work helped ensure Crypto 2020 was a success: – Leonid Reyzin (Boston University) – Crypto 2020 general chair. – Sophia Yakoubov for helping with general chair duties, and Muthuramakrishnan Venkitasubramaniam, Tal Rabin, and Fabrice Benhamouda for providing valuable advice to the general chair. – Carmit Hazay (Bar Ilan University) – Crypto 2020 workshop chair. – Antigoni Polychroniadou, Bertram Poettering, and Martijn Stam – Crypto 2020 rump session chairs.
– Chris Peikert for his role in overseeing reviews and the Best Paper by Early Career Researchers award selection for which the program chairs were con flicted. – Kevin McCurley and Christian Cachin for their critical assistance in setting up and managing a (new for Crypto) paper submission and review system. – Kevin McCurley, Kay McKelly, and members of the IACR’s emergency pandemic team for their work in designing and running the virtual format. – Whitney Morris and Eriko Macdonald from UCSB event services for their help navigating the COVID-19 shutdown logistics. – Anna Kramer and her colleagues at Springer. July 2020 Daniele Micciancio Thomas Ristenpart vi Preface Organization General Chair Leonid Reyzin Boston University, USA Program Committee Chairs Daniele Micciancio UC San Diego, USA Thomas Ristenpart Cornell Tech, USA Program Committee Adi Akavia University of Haifa, Israel Martin Albrecht Royal Holloway, University of London, UK Roberto Avanzi ARM, Germany Lejla Batina Radboud University, The Netherlands Jeremiah Blocki Purdue University, USA David Cash University of Chicago, USA Melissa Chase Microsoft Research, USA Hao Chen Microsoft Research, USA Ilaria Chillotti KU Leuven, Zama, Belgium Henry Corrigan-Gibbs EPFL, Switzerland, and MIT CSAIL, USA Craig Costello Microsoft Research, USA Joan Daemen Radboud University, The Netherlands Thomas Eisenbarth University of L übeck, Germany Pooya Farshim University of York, UK Sanjam Garg UC Berkeley, USA Daniel Genkin University of Michigan, USA Steven Goldfeder Cornell Tech, USA Shay Gueron University of Haifa, Israel, and AWS, USA Felix G
ünther ETH Zurich, Switzerland Tetsu Iwata Nagoya University, Japan Tibor Jager Bergische Universitaet, Germany Antoine Joux CISPA
– Helmholtz Center for Information Security, Germany
Jonathan Katz George Mason Univeristy, USA Eike Kiltz Ruhr University Bochum, Germany Elena Kirshanova I.Kant Baltic Federal University, Russia Venkata Koppula Weizmann Institute of Science, Isarel Anna Lysyanskaya Brown University, USA Vadim Lyubashevsky IBM Research Zurich, Switzerland Mohammad Mahmoody University of Virginia, USA Giulio Malavolta Carnegie Mellon University and UC Berkeley, USA Florian Mendel In fineon Technologies, Germany Mar ía Naya-Plasencia Inria, France Adam O
’Neill University of Massachusetts, USA Olya Ohrimenko The University of Melbourne, Australia Claudio Orlandi Aarhus University, Denmark Elisabeth Oswald University of Klagenfurt, Austria Chris Peikert University of Michigan, USA Bertram Poettering IBM Research Zurich, Switzerland Antigoni Polychroniadou JP Morgan AI Research, USA Ananth Raghunathan Google, USA Mariana Raykova Google, USA Christian Rechberger TU Graz, Austria Alon Rosen IDC, Israel Mike Rosulek Oregon State University, USA Alessandra Scafuro NC State University, USA Dominique Schroeder Florida Atlantic University, USA Thomas Shrimpton University of Florida, USA Fang Song Texas A&M University, USA Marc Stevens CWI Amsterdam, The Netherlands Dominique Unruh University of Tartu, Estonia Michael Walter IST, Austria David Wu University of Virginia, USA Additional Reviewers Masayuki Abe Shweta Agrawal Shashank Agrawal Shweta Agrawal Gorjan Alagic Navid Alamati Greg Alpar Joel Alwen Elena Andreeva Gilad Asharov Thomas Attema Saikrishna Badrinarayanan Shi Bai
Foteini Baldimtsi Marshall Ball James Bartusek Carsten Baum Asli Bay Mihir Bellare Fabrice Benhamouda Sebastian Berndt Ward Beullens Ritam Bhaumik Nina Bindel Alex Block Xavier Bonnetain Charlotte Bonte Carl Bootland Jonathan Bootle Raphael Bost Christina Boura Elette Boyle Zvika Brakerski Benedikt B ünz
Matteo Campanelli Anne Canteaut Andr é Chailloux Suvradip Chakraborty viii
Organization Yilei Chen Jie Chen
Nai-Hui Chia Arka Rai Choudhuri Kai-Min Chung Michele Ciampi Carlos Cid Michael Clear Ran Cohen Kelong Cong Aisling Connolly Sandro Coretti Daniele Cozzo Tingting Cui Benjamin Curtis Jan Czajkowski Dana Dachman-Soled Alex Davidson Leo De Castro Luca De Feo Thomas Debris Jean Paul Degabriele Cyprien Delpech de Saint Guilhem Patrick Derbez Apoorvaa Deshpande Benjamin Diamond Christoph Dobraunig Nico Doettling Benjamin Dowling Yfke Dulek Stefan Dziembowski Christoph Egger Maria Eichlseder Daniel Escudero Saba Eskandarian Serge Fehr Rex Fernando Dario Fiore Ben Fisch Wieland Fischer Nils Fleischhacker Daniele Friolo Georg Fuchsbauer Tommaso Gagliardoni Juan Garay Romain Gay Nicholas Genise Rosario Gennaro Marios Georgiou Riddhi Ghosal Satrajit Ghosh Esha Ghosh Koustabh Ghosh Irene Giacomelli Andras Gilyen S. Dov Gordon Rishab Goyal Lorenzo Grassi Matthew Green Hannes Gross Aldo Gunsing Tim G
üneysu Mohammad Hajiabadi Shai Halevi Koki Hamada Dominik Hartmann Eduard Hauck Carmit Hazay Alexander Helm Lukas Helminger Julia Hesse Dennis Hofheinz Alex Hoover Akinori Hosoyamada Kathrin H övelmanns Andreas H ülsing Ilia Iliashenko Gorka Irazoqui Joseph Jaeger Eli Jaffe Abhishek Jain Aayush Jain Samuel Jaques Stanislaw Jarecki Zhengfeng Ji Zhengzhong Jin Saqib Kakvi Daniel Kales Chethan Kamath Akinori Kawachi Mahimna Kelkar Hamidreza Khoshakhlagh Organization ix
Dakshita Khurana Sam Kim
Michael Kim Susumu Kiyoshima Karen Klein Dmitry Kogan Markulf Kohlweiss Ilan Komargodski Daniel Kuijsters Mukul Kulkarni Ashutosh Kumar Stefan K
ölbl Thijs Laarhoven Russell W. F. Lai Kim Laine Virginie Lallemand Changmin Lee Tancrede Lepoint Antonin Leroux Ga ëtan Leurent Kevin Lewi Baiyu Li
Xin Li Xiao Liang Feng-Hao Liu Alex Lombardi Julian Loss Ji Luo
Fermi Ma Bernardo Magri Urmila Mahadev Christian Majenz Eleftheria Makri Nathan Manohar Sai Krishna Deepak Maram Daniel Masny Eleanor McMurtry Sarah Meiklejohn Bart Mennink Peihan Miao Tarik Moataz Esfandiar Mohammadi Hart Montgomery Tal Moran Andrew Morgan Fabrice Mouhartem Pratyay Mukherjee Michael Naehrig Samuel Neves Ruth Francis Ng Ngoc Khanh Nguyen Valeria Nikolaenko Ryo Nishimaki Satoshi Obana Sabine Oechsner Jiaxin Pan Omer Paneth Lorenz Panny Sunoo Park Alain Passel ègue Valerio Pastro Jacques Patarin Kenneth Paterson Alice Pellet –Mary
Zack Pepin Ludovic Perret L éo Perrin Peter Pessl Jeroen Pijnenburg Benny Pinkas Rachel Player Oxana Poburinnaya Eamonn Postlethwaite Robert Primas Willy Quach Rahul Rachuri Ahmadreza Rahimi Divya Ravi Ling Ren
Joost Renes M. Sadegh Riazi Jo ão L. Ribeiro Silas Richelson Doreen Riepel Dragos Rotaru Ron Rothblum Adeline Roux-Langlois Arnab Roy Carla R àfols
Paul R ösler
Simona Samardjiska Yu Sasaki x Organization John Schanck Patrick Schaumont Martin Schl äffer
Jonas Schneider-Bensch Peter Scholl Andr é Schrottenloher Sven Sch äge
Adam Sealfon Gil Segev Gregor Seiler Okan Seker Nicolas Sendrier Sacha Servan-Schreiber Karn Seth Yannick Seurin Siamak Shahandashti Devika Sharma Sina Shiehian Omer Shlomovits Omri Shmueli Mark Simkin Boris Škorić
Yongsoo Song Pratik Soni Florian Speelman Nicholas Spooner Akshayaram Srinivasan Douglas Stebila Damien Stehl é Noah Stephens-Davidowitz Younes Talibi Alaoui Titouan Tanguy Stefano Tessaro Aravind Thyagarajan Radu Titiu Yosuke Todo Ni Trieu Rotem Tsabary Daniel Tschudi Vinod Vaikuntanathan Thyla van der Merwe Prashant Vasudevan Marloes Venema Muthuramakrishnan Venkitasubramaniam Damien Vergnaud Thomas Vidick Fernando Virdia Ivan Visconti Satyanarayana Vusirikala Riad Wahby Xiao Wang Brent Waters Hoeteck Wee Christian Weinert Weiqiang Wen Erich Wenger Daniel Wichs Luca Wilke Keita Xagawa Min Xu Sophia Yakoubov Rupeng Yang Eylon Yogev Yu Yu Greg Zaverucha Mark Zhandry Tina Zhang Fan Zhang Yupeng Zhang Vassilis Zikas Organization xi
Contents – Part I
Security Models Handling Adaptive Compromise for Practical Encryption Schemes . . . . . . . . 3 Joseph Jaeger and Nirvan Tyagi Overcoming Impossibility Results in Composable Security Using Interval-Wise Guarantees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 Daniel Jost and Ueli Maurer Indifferentiability for Public Key Cryptosystems . . . . . . . . . . . . . . . . . . . . . 63 Mark Zhandry and Cong Zhang Quantifying the Security Cost of Migrating Protocols to Practice . . . . . . . . . 94 Christopher Patton and Thomas Shrimpton Symmetric and Real World Cryptography The Memory-Tightness of Authenticated Encryption . . . . . . . . . . . . . . . . . . 127 Ashrujit Ghoshal, Joseph Jaeger, and Stefano Tessaro Time-Space Tradeoffs and Short Collisions in Merkle-Damg ård
Hash Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
Akshima, David Cash, Andrew Drucker, and Hoeteck Wee The Summation-Truncation Hybrid: Reusing Discarded Bits for Free. . . . . . . 187 Aldo Gunsing and Bart Mennink Security Analysis of NIST CTR-DRBG . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
Viet Tung Hoang and Yaobin Shen Security Analysis and Improvements for the IETF MLS Standard for Group Messaging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
Jo ël Alwen, Sandro Coretti, Yevgeniy Dodis, and Yiannis Tselekounis Universally Composable Relaxed Password Authenticated Key Exchange . . . . 278
Michel Abdalla, Manuel Barbosa, Tatiana Bradley, Stanis ław Jarecki, Jonathan Katz, and Jiayu Xu Anonymous Tokens with Private Metadata Bit . . . . . . . . . . . . . . . . . . . . . . 308 Ben Kreuter, Tancr ède Lepoint, Michele Orrù, and Mariana Raykova Hardware Security and Leakage Resilience Random Probing Security: Verification, Composition, Expansion and New Constructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
Sonia Bela ïd, Jean-Sébastien Coron, Emmanuel Prouff, Matthieu Rivain, and Abdul Rahman Taleb Mode-Level vs. Implementation-Level Physical Security in Symmetric Cryptography: A Practical Guide Through the Leakage-Resistance Jungle . . . 369
Davide Bellizia, Olivier Bronchain, Ga ëtan Cassiers, Vincent Grosso, Chun Guo, Charles Momin, Olivier Pereira, Thomas Peters, and Fran
çois-Xavier Standaert Leakage-Resilient Key Exchange and Two-Seed Extractors . . . . . . . . . . . . . 401 Xin Li, Fermi Ma, Willy Quach, and Daniel Wichs Outsourced Encryption Lower Bounds for Encrypted Multi-Maps and Searchable Encryption in the Leakage Cell Probe Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433
Sarvar Patel, Giuseppe Persiano, and Kevin Yeo Fast and Secure Updatable Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464 Colin Boyd, Gareth T. Davies, Kristian Gj østeen, and Yao Jiang Incompressible Encodings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494 Tal Moran and Daniel Wichs Constructions New Constructions of Hinting PRGs, OWFs with Encryption, and More . . . . 527 Rishab Goyal, Satyanarayana Vusirikala, and Brent Waters Adaptively Secure Constrained Pseudorandom Functions in the Standard Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 559 Alex Davidson, Shuichi Katsumata, Ryo Nishimaki, Shota Yamada, and Takashi Yamakawa Collusion Resistant Watermarkable PRFs from Standard Assumptions . . . . . . 590 Rupeng Yang, Man Ho Au, Zuoxia Yu, and Qiuliang Xu Verifiable Registration-Based Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . 621
Rishab Goyal and Satyanarayana Vusirikala New Techniques for Traitor Tracing: Size N 1 =3
652 Mark Zhandry xiv Contents
– Part I Public Key Cryptography Functional Encryption for Attribute-Weighted Sums from k-Lin . . . . . . . . . . 685 Michel Abdalla, Junqing Gong, and Hoeteck Wee Amplifying the Security of Functional Encryption, Unconditionally . . . . . . . . 717
Aayush Jain, Alexis Korb, Nathan Manohar, and Amit Sahai Dynamic Decentralized Functional Encryption . . . . . . . . . . . . . . . . . . . . . . 747 J
Duong Hieu Phan, and David Pointcheval On Succinct Arguments and Witness Encryption from Groups . . . . . . . . . . . 776 Ohad Barta, Yuval Ishai, Rafail Ostrovsky, and David J. Wu Fully Deniable Interactive Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . 807
Ran Canetti, Sunoo Park, and Oxana Poburinnaya Chosen Ciphertext Security from Injective Trapdoor Functions . . . . . . . . . . . 836 Susan Hohenberger, Venkata Koppula, and Brent Waters Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 867 Contents
– Part I xv
Contents – Part II Public Key Cryptanalysis A Polynomial-Time Algorithm for Solving the Hidden Subset Sum Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Jean-S ébastien Coron and Agnese Gini Asymptotic Complexities of Discrete Logarithm Algorithms in Pairing-Relevant Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Gabrielle De Micheli, Pierrick Gaudry, and C écile Pierrot Comparing the Difficulty of Factorization and Discrete Logarithm: A 240-Digit Experiment. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thom é, and Paul Zimmermann Breaking the Decisional Diffie-Hellman Problem for Class Group Actions Using Genus Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 Wouter Castryck, Jana Sot áková, and Frederik Vercauteren A Classification of Computational Assumptions in the Algebraic Group Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
Balthazar Bauer, Georg Fuchsbauer, and Julian Loss Lattice Algorithms and Cryptanalysis Fast Reduction of Algebraic Lattices over Cyclotomic Fields . . . . . . . . . . . . 155
Paul Kirchner, Thomas Espitau, and Pierre-Alain Fouque Faster Enumeration-Based Lattice Reduction: Root Hermite Factor k 1 =ð2kÞ Time k k =8 þ oðkÞ . . . . . . . . . . . . . . . . . . . . . . . . . 186
Martin R. Albrecht, Shi Bai, Pierre-Alain Fouque, Paul Kirchner, Damien Stehl é, and Weiqiang Wen Lattice Reduction for Modules, or How to Reduce ModuleSVP to ModuleSVP . . . . . . . . . . . . . . . . . . . . . . 213
Tamalika Mukherjee and Noah Stephens-Davidowitz Random Self-reducibility of Ideal-SVP via Arakelov Random Walks. . . . . . . 243 Koen de Boer, L éo Ducas, Alice Pellet-Mary, and Benjamin Wesolowski Slide Reduction, Revisited —Filling the Gaps in SVP Approximation . . . . . . 274
Divesh Aggarwal, Jianwei Li, Phong Q. Nguyen, and Noah Stephens-Davidowitz Rounding in the Rings. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
Feng-Hao Liu and Zhedong Wang Lattice-Based and Post-quantum Cryptography LWE with Side Information: Attacks and Concrete Security Estimation . . . . . 329
Dana Dachman-Soled, L éo Ducas, Huijing Gong, and Mélissa Rossi A Key-Recovery Timing Attack on Post-quantum Primitives Using the Fujisaki-Okamoto Transformation and Its Application on FrodoKEM . . . . 359 Qian Guo, Thomas Johansson, and Alexander Nilsson Efficient Pseudorandom Correlation Generators from Ring-LPN . . . . . . . . . . 387
Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl Scalable Pseudorandom Quantum States. . . . . . . . . . . . . . . . . . . . . . . . . . . 417
Zvika Brakerski and Omri Shmueli A Non-PCP Approach to Succinct Quantum-Safe Zero-Knowledge . . . . . . . . 441 Jonathan Bootle, Vadim Lyubashevsky, Ngoc Khanh Nguyen, and Gregor Seiler Practical Product Proofs for Lattice Commitments . . . . . . . . . . . . . . . . . . . . 470 Thomas Attema, Vadim Lyubashevsky, and Gregor Seiler Lattice-Based Blind Signatures, Revisited. . . . . . . . . . . . . . . . . . . . . . . . . . 500
Eduard Hauck, Eike Kiltz, Julian Loss, and Ngoc Khanh Nguyen Multi-party computation Round-Optimal Black-Box Commit-and-Prove with Succinct Communication. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533 Susumu Kiyoshima Efficient Constant-Round MPC with Identifiable Abort and Public Verifiability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 562 Carsten Baum, Emmanuela Orsini, Peter Scholl, and Eduardo Soria-Vazquez Black-Box Use of One-Way Functions is Useless for Optimal Fair Coin-Tossing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593
Hemanta K. Maji and Mingyuan Wang Guaranteed Output Delivery Comes Free in Honest Majority MPC . . . . . . . . 618 Vipul Goyal, Yifan Song, and Chenzhi Zhu xviii Contents
– Part II Black-Box Transformations from Passive to Covert Security with Public Verifiability. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 647 Ivan Damg ård, Claudio Orlandi, and Mark Simkin MPC with Friends and Foes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 677 Bar Alon, Eran Omri, and Anat Paskin-Cherniavsky Always Have a Backup Plan: Fully Secure Synchronous MPC with Asynchronous Fallback . . . . . . . . . . . . . . . . . . . . . 707 Erica Blum, Chen-Da Liu-Zhang, and Julian Loss Reverse Firewalls for Actively Secure MPCs . . . . . . . . . . . . . . . . . . . . . . . 732
Suvradip Chakraborty, Stefan Dziembowski, and Jesper Buus Nielsen Stacked Garbling: Garbled Circuit Proportional to Longest Execution Path . . . 763 David Heath and Vladimir Kolesnikov Better Concrete Security for Half-Gates Garbling (in the Multi-instance Setting). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 793 Chun Guo, Jonathan Katz, Xiao Wang, Chenkai Weng, and Yu Yu Improved Primitives for MPC over Mixed Arithmetic-Binary Circuits . . . . . . 823
Daniel Escudero, Satrajit Ghosh, Marcel Keller, Rahul Rachuri, and Peter Scholl Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 853 Contents
– Part II xix
Contents – Part III Multi-party Computation Two-Sided Malicious Security for Private Intersection-Sum with Cardinality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Peihan Miao, Sarvar Patel, Mariana Raykova, Karn Seth, and Moti Yung Private Set Intersection in the Internet Setting from Lightweight Oblivious PRF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Melissa Chase and Peihan Miao Multiparty Generation of an RSA Modulus . . . . . . . . . . . . . . . . . . . . . . . . 64 Megan Chen, Ran Cohen, Jack Doerner, Yashvanth Kondi, Eysa Lee, Schuyler Rosefield, and Abhi Shelat Secret Sharing Non-malleability Against Polynomial Tampering. . . . . . . . . . . . . . . . . . . . . 97 Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, Tal Malkin, and Li-Yang Tan Non-malleable Secret Sharing Against Bounded Joint-Tampering Attacks in the Plain Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
Gianluca Brian, Antonio Faonio, Maciej Obremski, Mark Simkin, and Daniele Venturi Nearly Optimal Robust Secret Sharing Against Rushing Adversaries . . . . . . . 156
Pasin Manurangsi, Akshayaram Srinivasan, and Prashant Nalini Vasudevan Cryptanalysis Cryptanalytic Extraction of Neural Network Models . . . . . . . . . . . . . . . . . . 189 Nicholas Carlini, Matthew Jagielski, and Ilya Mironov Automatic Verification of Differential Characteristics: Application to Reduced Gimli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 Fukang Liu, Takanori Isobe, and Willi Meier The MALICIOUS Framework: Embedding Backdoors into Tweakable Block Ciphers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 Thomas Peyrin and Haoyang Wang Cryptanalysis of the Lifted Unbalanced Oil Vinegar Signature Scheme . . . . . 279
Jintai Ding, Joshua Deaton, Kurt Schmidt, Vishakha, and Zheng Zhang Out of Oddity – New Cryptanalytic Techniques Against Symmetric Primitives Optimized for Integrity Proof Systems . . . . . . . . . . . . . . . . . . . . 299 Tim Beyne, Anne Canteaut, Itai Dinur, Maria Eichlseder, Gregor Leander, Ga ëtan Leurent, María Naya-Plasencia, Léo Perrin, Yu Sasaki, Yosuke Todo, and Friedrich Wiemer Improved Differential-Linear Attacks with Applications to ARX Ciphers . . . . 329 Christof Beierle, Gregor Leander, and Yosuke Todo Cryptanalysis Results on Spook: Bringing Full-Round Shadow-512 to the Light . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359 Patrick Derbez, Paul Huynh, Virginie Lallemand, Mar ía Naya-Plasencia, Léo Perrin, and André Schrottenloher Cryptanalysis of LEDAcrypt. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389
Daniel Apon, Ray Perlner, Angela Robinson, and Paolo Santini Alzette: A 64-Bit ARX-box: (Feat. CRAX and TRAX) . . . . . . . . . . . . . . . . 419 Christof Beierle, Alex Biryukov, Luan Cardoso dos Santos, Johann Gro ßschädl, Léo Perrin, Aleksei Udovenko, Vesselin Velichkov, and Qingju Wang Delay Functions Order-Fairness for Byzantine Consensus . . . . . . . . . . . . . . . . . . . . . . . . . . 451
Mahimna Kelkar, Fan Zhang, Steven Goldfeder, and Ari Juels Generically Speeding-Up Repeated Squaring Is Equivalent to Factoring: Sharp Thresholds for All Generic-Ring Delay Functions . . . . . . . . . . . . . . . 481
Lior Rotem and Gil Segev Zero Knowledge Compressed R-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513
Thomas Attema and Ronald Cramer A Tight Parallel Repetition Theorem for Partially Simulatable Interactive Arguments via Smooth KL-Divergence . . . . . . . . . . . . . . . . . . . . . . . . . . . 544
Itay Berman, Iftach Haitner, and Eliad Tsfadia Interactive Proofs for Social Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 574 Liran Katzir, Clara Shikhelman, and Eylon Yogev xxii Contents
– Part III The Measure-and-Reprogram Technique 2.0: Multi-round Fiat-Shamir and More . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 602 Jelle Don, Serge Fehr, and Christian Majenz Fiat-Shamir for Repeated Squaring with Applications to PPAD-Hardness and VDFs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 632 Alex Lombardi and Vinod Vaikuntanathan Delegation with Updatable Unambiguous Proofs and PPAD-Hardness . . . . . . 652
Yael Tauman Kalai, Omer Paneth, and Lisa Yang New Techniques for Zero-Knowledge: Leveraging Inefficient Provers to Reduce Assumptions, Interaction, and Trust . . . . . . . . . . . . . . . . . . . . . . 674
Marshall Ball, Dana Dachman-Soled, and Mukul Kulkarni Spartan: Efficient and General-Purpose zkSNARKs Without Trusted Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 704
Srinath Setty NIZK from LPN and Trapdoor Hash via Correlation Intractability for Approximable Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 738
Zvika Brakerski, Venkata Koppula, and Tamer Mour Shorter Non-interactive Zero-Knowledge Arguments and ZAPs for Algebraic Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 768
Geoffroy Couteau and Dominik Hartmann Non-interactive Zero-Knowledge Arguments for QMA, with Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 799
Andrea Coladangelo, Thomas Vidick, and Tina Zhang Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 829
Contents – Part III xxiii Document Outline
Download 262.96 Kb. Do'stlaringiz bilan baham: 
|