Matthew Robshaw Jonathan Katz (Eds.) 4 1 8 Advances in Cryptology – 9 S C CRYPTO 2016 N L 36th Annual International Cryptology Conference Santa Barbara, CA, USA, August 14–18, 2016 Proceedings, Part I 123 Lecture Notes in Computer Science 9814 Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen Editorial Board David Hutchison Lancaster University, Lancaster, UK Takeo Kanade Carnegie Mellon University, Pittsburgh, PA, USA Josef Kittler University of Surrey, Guildford, UK Jon M. Kleinberg Cornell University, Ithaca, NY, USA Friedemann Mattern ETH Zurich, Zürich, Switzerland John C. Mitchell Stanford University, Stanford, CA, USA Moni Naor Weizmann Institute of Science, Rehovot, Israel C. Pandu Rangan Indian Institute of Technology, Madras, India Bernhard Steffen TU Dortmund University, Dortmund, Germany Demetri Terzopoulos University of California, Los Angeles, CA, USA Doug Tygar University of California, Berkeley, CA, USA Gerhard Weikum Max Planck Institute for Informatics, Saarbrücken, Germany More information about this series at http://www.springer.com/series/7410 Matthew Robshaw Jonathan Katz (Eds.) (cid:129) – Advances in Cryptology CRYPTO 2016 36th Annual International Cryptology Conference – Santa Barbara, CA, USA, August 14 18, 2016 Proceedings, Part I 123 Editors MatthewRobshaw JonathanKatz Impinj, Inc. University of Maryland Seattle, WA CollegePark, MD USA USA ISSN 0302-9743 ISSN 1611-3349 (electronic) Lecture Notesin Computer Science ISBN 978-3-662-53017-7 ISBN978-3-662-53018-4 (eBook) DOI 10.1007/978-3-662-53018-4 LibraryofCongressControlNumber:2016945783 LNCSSublibrary:SL4–SecurityandCryptology ©InternationalAssociationforCryptologicResearch2016 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartofthe material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodologynow knownorhereafterdeveloped. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Thepublisher,theauthorsandtheeditorsaresafetoassumethattheadviceandinformationinthisbookare believedtobetrueandaccurateatthedateofpublication.Neitherthepublishernortheauthorsortheeditors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissionsthatmayhavebeenmade. Printedonacid-freepaper ThisSpringerimprintispublishedbySpringerNature TheregisteredcompanyisSpringer-VerlagGmbHBerlinHeidelberg Preface The36thInternationalCryptologyConference(Crypto2016)washeldatUCSB,Santa Barbara, CA, USA, during August 14–18, 2016. The workshop was sponsored by the International Association for Cryptologic Research. Cryptocontinuestogrow.ThisyeartheProgramCommitteeevaluatedarecord274 submissionsoutofwhich70werechosenforinclusionintheprogram.Eachpaperwas reviewed by at least three independent reviewers, with papers from Program Com- mittee members receiving at least five reviews. Reviewers with potential conflicts of interest for specificpaperswereexcludedfromalldiscussionsaboutthose papers,and this policy was extended to the program chairs as well. The 44 members of the Program Committee were aided in this complex and time-consumingtaskbymanyexternalreviewers.Wewouldliketothankthemallfor their service, their expert opinions, and their spirited contributions to the review pro- cess.Itwasatremendouslydifficulttasktochoosetheprogramforthisconference,as the quality of the submissions was very high. It was even harder to identify a single best paper, but our congratulations go to Elette Boyle, Niv Gilboa, and Yuval Ishai from IDC Herzliya, Ben Gurion University, and the Technion, respectively, whose paper “Breaking the Circuit Size Barrier for Secure Computation Under DDH” was awarded Best Paper. Our congratulations also go to Mark Zhandry of MIT and Princeton University who won the award for the Best Student Paper “The Magic of ELFs.” TheinvitedspeakersatCrypto2016wereBrianSniffen,ChiefSecurityArchitectat Akamai Technologies, Inc., and Paul Kocher, founder of Cryptography Research. Brian’s presentation cast a fascinating light on the issues of real-world cryptographic deploymentwhilePaul’spresentation, ajointinvitation fromtheprogramco-chairs of both Crypto 2016 and CHES 2016, marked 20 years since his publication of the first paper on side-channel attacks at Crypto 1996. We are, of course, indebted to Brian LaMacchia, the general chair, as well as the local Organizing Committee, who together proved ideal liaisons for establishing the layout of the program and for supporting the speakers. Our job as program co-chairs wasmademucheasierbytheexcellenttoolsdevelopedbyShaiHalevi; bothShaiand Brian were always available at short notice to answer our queries. Finally, we would liketothankalltheauthorswhosubmittedtheirworktoCrypto2016.Withoutyouthe conference would not exist. August 2016 Matthew Robshaw Jonathan Katz Crypto 2016 The 36th IACR International Cryptology Conference University of California, Santa Barbara, CA, USA August 14–18, 2016 Sponsored by the International Association for Cryptologic Research General Chair Brian LaMacchia Microsoft Program Chairs Matthew Robshaw Impinj, USA Jonathan Katz University of Maryland, USA Program Committee Alex Biryukov University of Luxembourg, Luxembourg Anne Canteaut Inria, France Dario Catalano Università di Catania, Italy Nishanth Chandran Microsoft Research, India Melissa Chase Microsoft Research, USA Joan Daemen STMicroelectronics,BelgiumandRadboudUniversity, The Netherlands Martin Van Dijk University of Connecticut, USA Itai Dinur Ben-Gurion University, Israel Pierre-Alain Fouque Université Rennes 1, France Steven Galbraith Auckland University, New Zealand Sanjam Garg University of California, Berkeley, USA S. Dov Gordon George Mason University, USA Jens Groth University College London, UK Sorina Ionica Université de Picardie, France Tetsu Iwata Nagoya University, Japan Aggelos Kiayias National and Kapodistrian University of Athens, Greece Gregor Leander Ruhr Universität Bochum, Germany Shengli Liu Shanghai Jiao Tong University, China Alexander May Ruhr Universität Bochum, Germany Willi Meier FHNW, Switzerland Payman Mohassel Visa Research, USA VIII Crypto 2016 Elke De Mulder Cryptographic Research, France Steven Myers Indiana University, USA Phong Nguyen Inria,FranceandCNRS/JFLIandUniversityofTokyo, Japan Kaisa Nyberg Aalto University, Finland Kenny Paterson Royal Holloway University of London, UK Thomas Peyrin Nanyang Technological University, Singapore Benny Pinkas Bar-Ilan University, Israel David Pointcheval École Normale Supérieure, France Manoj Prabhakaran University of Illinois, USA Bart Preneel KU Leuven, Belgium Mariana Raykova Yale University, USA Christian Rechberger TU-Graz, Austria and DTU, Denmark Mike Rosulek Oregon State University, USA Rei Safavi-Naini University of Calgary, Canada Alessandra Scafuro Boston University and Northeastern University, USA Patrick Schaumont Virginia Tech, USA Dominique Schröder Saarland University, Germany Jae Hong Seo Myongji University, Korea Yannick Seurin ANSSI, France Abhi Shelat University of Virginia, USA Nigel Smart University of Bristol, UK Ron Steinfeld Monash University, Australia Mehdi Tibouchi NTT Secure Platform Laboratories, Japan Additional Reviewers Michel Abdalla Foteini Baldimtsi Dan Boneh Masayuki Abe Paulo Barreto Jonathan Bootle Arash Afshar Gilles Barthe Raphael Bost Shashank Agrawal Lejla Batina Christina Boura Shweta Agrawal Christof Beierle Florian Bourse Ayo Akinyele Mihir Bellare Cyril Bouvier Martin Albrecht Fabrice Benhamouda Elette Boyle Gergely Alpar Sanjay Bhattacherjee Zvika Brakerski Jacob Alperin-Sheriff Jean-Francois Biasse Lus Brandão Elena Andreeva Begul Bilgin Anne Broadbent Daniel Apon Gaetan Bisson Christina Brzuska Gilad Asharov Nir Bitansky Christian Cachin Gilles Van Assche Simon Blackburn Ran Canetti Nuttapong Attrapadung Olivier Blazy Angelo De Caro Saikrishna Matthieu Bloch Guilhem Castagnos Badrinarayanan Céline Blondeau Andrea Cerulli Josep Balasch Andrej Bogdanov Pyrros Chaidos Crypto2016 IX André Chailloux Divya Gupta Daniel Kraschewski Jie Chen Felix Günther Anna Krasnova Céline Chevalier Shai Halevi Hugo Krawczyk Chongwon Cho Mike Hamburg Fernando Krell Seung Geol Choi Shuai Han Stephan Krenn Ashish Choudhury Helena Handschuh Ranjit Kumaresan Sherman Chow Christian Hanser Alptekin Kupcu Kai-Min Chung Carmit Hazay Fabien Laguillaumie Michele Ciampi Ethan Heilman Virginie Lallemand Michael Clear Ryan Henry Enrique Larraia Ran Cohen Gottfried Herold Changmin Lee Geoffroy Couteau Felix Heuer Hyung Tae Lee Dana Dachman-Soled Viet Tung Hoang Kwangsu Lee Deepesh Data Dennis Hofheinz Nikos Leonardos Jean Paul Degabriele Ziyuan Hu Tancrède Lepoint David Derler Yan Huang Anthony Leverrier Daniel Dinu Michael Hutter Benoit Libert Christoph Dobraunig Malika Izabachene Fuchun Lin Yevgeniy Dodis Håkon Jacobsen Rachel Lin Nico Döttling Mahavir Jhawar Yehuda Lindell Natnatee Dokmai Dingding Jia Feng-Hao Liu Leo Ducas Keting Jia Yi-Kai Liu Tuyet Duong Thomas Johansson Patrick Longa Keita Emura Aaron Johnson Steve Lu Frederic Ezerman Kimmo Järvinen Stefan Lucks Pooya Farshim Yael Tauman Kalai Atul Luykx Sebastian Faust Bhavana Kanukurthi Anna Lysyanskaya Dario Fiore Petteri Kaski Lin Lyu Marc Fischlin Marcel Keller Vadim Lyubashevsky Joe Fitzsimons Nathan Keller Mohammad Mahmoody Nils Fleischhacker Carmen Kempka Hemanta Maji Emmanuel Fouotsa Iordanis Kerenidis Giulio Malavolta Georg Fuchsbauer Dmitry Khovratovich Tal Malkin Eiichiro Fujisaki Dakshita Khurana Alex Malozemoff Martin Gagne Eike Kiltz Mark Marson François Le Gall Jinsu Kim Daniel Masny Chaya Ganesh Taechan Kim Takahiro Matsuda Juan Garay Paul Kirchner Florian Mendel Christina Garman Elena Kirshanova Bart Mennink Romain Gay Susumu Kiyoshima Thyla van der Merwe Essam Ghadafi Simon Knellwolf Peihan Miao Benedikt Gierlichs Stefan Koelbl Christof Michel Niv Gilboa Vlad Kolesnikov Ian Miers Vipul Goyal Takeshi Koshiba Andrew Miller Frédéric Grosshans Luke Kowalczyk Brice Minaud Aurore Guillevic Thorsten Kranz Kazuhiko Minematsu X Crypto2016 Ilya Mironov Carla Rafols Jean-Pierre Tillich Ameer Mohammad Srinivasan Raghuraman Yosuke Todo Amir Moradi Vanishree Rao Yiannis Tselekounis Tal Moran Manuel Reinert Michael Tunstall Nicky Mouha Oscar Reparaz Himanshu Tyagi Pratyay Mukherjee Silas Richelson Aleksei Udovenko Jörn Müller-Quade Thomas Ristenpart Jon Ullman Valérie Nachef Damien Robert Dominique Unruh Michael Naehrig Alon Rosen Prashant Vasudevan Maria Naya-Plasencia Adeline Roux-Langlois Vesselin Velichkov Soheil Nemati Arnab Roy Muthu Khoa Nguyen Tim Ruffing Venkitasubramaniam Ivica Nikolic Hansol Ryu Frederik Vercauteren Ventzi Nikov Sondre Rønjom Damien Vergnaud Ryo Nishimaki Akshayaram Srinivasan Jorge Villar Anca Nitulescu Amin Sakzad Dhinakaran Adam O’Neill Katerina Samari Vinayagamurthy Miyako Ohkubo Ruediger Schack Ivan Visconti Go Ohtake Christian Schaffner Michael Walter Tatsuaki Okamoto John Schanck Pengwei Wang Ozgur Oksuz Thomas Schneider Qingju Wang Cristina Onete Peter Scholl Xiao Wang Claudio Orlandi Peter Schwabe Hoeteck Wee Elisabeth Oswald Sven Schäge Mor Weiss Léo Paul Perrin Adam Sealfon Yunhua Wen Jiaxin Pan Setareh Sharifian Carolyn Whitnall Giorgos Panagiotakos Tom Shrimpton Daniel Wichs Omkant Pandey Sandeep Shukla Xiaodi Wu Kostas Siang Meng Sim Keita Xagawa Pappagiannopoulos Luisa Siniscalchi Sophia Yakoubov Anat Paskin-Cherniavsky Daniel Slamanig Shota Yamada Rafael Pass Yongsoo Song Kan Yasuda Valerio Pastro Kannan Srinathan Arkady Yerukhimovich Arpita Patra Akshayaram Srinivasan Ouyang Yingkai Souradyuti Paul Douglas Stebila Thomas Zacharias Christopher Peikert Damien Stehlé Mark Zhandry Rene Peralta John Steinberger Bingsheng Zhang Trevor Perrin Marc Stevens Liang Feng Zhang Giuseppe Persiano Valentin Suder Xiao Zhang Christophe Petit Willy Susilo Yupeng Zhang Rafael Del Pino Björn Tackmann Hong-Sheng Zhou Oxana Poburinnaya Katsuyuki Takashima Vassilis Zikas Antigoni Polychroniadou Qiang Tang Dionysis Zindros Orazio Puglisi Stefano Tessaro Baodong Qin Aishwarya Max Rabkin Thiruvengadam