Ronald Cramer - Secure Multiparty Computation and Secret Sharing

Secure Multiparty Computation and Secret Sharing

In a data-driven society, individuals and companies encounter numerous situations where private information is an important resource. How can parties handle confidential data if they do not trust everyone involved? This text is the first to present a comprehensive treatment of unconditionally secure techniques for multiparty computation (MPC) and secret sharing. In a secure MPC, each party possesses some private data, whereas secret sharing provides a way for one party to spread information on a secret such that all parties together hold full information, yet no single party has all the information. The authors present basic feasibility results from the last thirty years, generalizations to arbitrary access structures using linear secret sharing, some recent techniques for efficiency improvements, and a general treatment of the theory of secret sharing, focusing on asymptotic results with interesting applications related to MPC.

R ONALD C RAMER leads the Cryptology Group at CWI Amsterdam, the national research institute for mathematics and computer science in the Netherlands, and is Professor at the Mathematical Institute, Leiden University. He is Fellow of the International Association for Cryptologic Research and Member of the Royal Netherlands Academy of Arts and Sciences.

I VAN B JERRE D AMGRD leads the Cryptology Group in the Department of Computer Science, Aarhus University, and is a professor in the same department. He is a Fellow of the International Association for Cryptologic Research, and he received the RSA conference 2015 award for outstanding achievements in mathematics. He is a co-founder of the companies Cryptomathic and Partisia.

J ESPER B UUS N IELSEN is an associate professor in the Department of Computer Science, Aarhus University. He is a co-founder of the company Partisia.

Secure Multiparty Computation and Secret Sharing

Ronald Cramer

CWI & Leiden University

Ivan Bjerre Damgrd

Aarhus University

Jesper Buus Nielsen

Aarhus University

32 Avenue of the Americas, New York, NY 10013-2473, USA

Cambridge University Press is part of the University of Cambridge.

It furthers the Universitys mission by disseminating knowledge in the pursuit of education, learning, and research at the highest international levels of excellence.

www.cambridge.org

Information on this title: www.cambridge.org/9781107043053

Ronald Cramer, Ivan Bjerre Damgrd, Jesper Buus Nielsen 2015

This publication is in copyright. Subject to statutory exception and to the provisions of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press.

First published 2015

Printed in the United States of America

A catalog record for this publication is available from the British Library.

Library of Congress Cataloging in Publication Data

Cramer, Ronald, 1968

Secure multiparty computation and secret sharing / Ronald Cramer, CWI & Leiden University, Ivan Damgrd, Aarhus University, Jesper Buus Nielsen, Aarhus University.

pages cm

Includes bibliographical references and index.

ISBN 978-1-107-04305-3 (hardback)

1. Computer networksSecurity measures. 2. Computer security. 3. Computer network protocols. 4. Information theory. I. Damgaard, Ivan, 1956 II. Nielsen, Jesper Buus, 1973 III. Title.

TK5105.59.C685 2015

005.8dc23 2015002282

ISBN 978-1-107-04305-3 Hardback

Cambridge University Press has no responsibility for the persistence or accuracy of URLs for external or third-party Internet websites referred to in this publication and does not guarantee that any content on such websites is, or will remain, accurate or appropriate.

This is a book on information theoretically secure multiparty computation (MPC) and secret sharing and about the intimate and fascinating relationship between the two notions. We decided to write this book because we felt that a comprehensive treatment of unconditionally secure techniques for MPC was missing in the literature. In particular, because some of the first general protocols were found before appropriate definitions of security had crystallized, proofs of those basic solutions have been missing so far.

We present the basic feasibility results for unconditionally secure MPC from the late 1980s, generalizations to arbitrary access structures using linear secret sharing, and a selection of more recent techniques for efficiency improvements. We also present our own simplified variant of the Universally Composable (UC) framework in order to be able to give complete and modular proofs for the protocols we present.

We also present a general treatment of the theory of secret sharing, in particular, secret-sharing schemes with additional algebraic properties, which is also a subject missing in textbooks. One of the things we focus on is asymptotic results for multiplicative secret sharing, which has various interesting applications that we present in the MPC part.

Our ambition has been to create a book that will be of interest to both computer scientists and mathematicians and can be used for teaching at several different levels. We have therefore tried to make , we reintroduce the notion, but as a general concept that is interesting in its own right and with a comprehensive treatment of the mathematical background.

This book is intended to be self-contained enough to be read by advanced undergraduate students, and the authors have used large parts of the material in the book for teaching courses at this level. By covering a selection of more advanced material, the book can also be used for a graduate course.

For a course on the advanced undergrad level for computer science students, we recommend covering , which is basically a survey of cryptographically secure solutions.

For a graduate-level computer science course, we recommend including also because they contain several recent techniques and survey some open problems.

For a course in mathematics on secret sharing and applications, we recommend covering can be used to present some of the more advanced applications.

We thank Alp Bassa, Morten D. Bech, Wieb Bosma, Ignacio Cascudo, Iwan Duursma, Morten Dahl Jgensen, Serge Fehr, Helene Flyvholm Haagh, Irene Giacomelli, Lingfei Jin, Michiel Kosters, Carolin Lunemann, Antonio Macedone, Diego Mirandola, Carles Padr, Gabriele Spini, Anders Vinther, Chaoping Xing, and Sarah Zakarias for doing an enormous amount of work in proofreading and commenting. We also thank Sarah Zakarias for writing some of the simulation proofs and helping us to avoid many more mistakes than are present now.

RC would like to warmly thank the School of Mathematical Sciences at Nanyang Technological University in Singapore for its excellent hospitality during his frequent visits throughout the years for research and work on parts of this book.

In a modern information-driven society, the everyday life of individuals and companies is full of cases where various kinds of private information are important resources. While a cryptographer might think of PIN codes and keys in this context, these types of secrets are not our main concern here. Rather, we will talk about information that is closer to the primary business of an individual or a company. For a private person, this may be data concerning his or her economic situation, such as income, loans, and tax data, or information about his or her health, such as diseases and medicine usage. For a company, it might be the customer database or information on how the business is running, such as turnover, profits, and salaries.