Nexus of Information and Computation Theories Secrecy and Privacy Theme March 21 – April 1, 2016
Titles, Abstracts, and Videos
Amos Beimel (Ben Gurion University) Secret Sharing Schemes and Distribution Designs Abstract: A secretsharing scheme is a method by which a dealer distributes shares to parties such that only authorized subsets of parties can reconstruct the secret and all other sets get no information on the secret. Secretsharing schemes are an important tool in cryptography and they are used as a building box in many secure protocols, e.g., general protocol for multiparty computation, Byzantine agreement, threshold cryptography, access control, attributebased encryption, and generalized oblivious transfer.
In this talk, I will describe the most important constructions of secretsharing schemes. In particular, I will describe linear secret sharing schemes, which are schemes where the shares are computed using a linear mapping. Most known secretsharing schemes are linear.
I will then describe distribution designs – a generalization of secret sharing schemes. The goal of distribution design is to find a joint distribution on n random variables that satisfies a given set of constraints on the marginal distributions.
Matthieu Bloch (Georgia Tech) (Video)
Secure and covert communications over noisy channels Abstract: The benefits offered by ubiquitous communication networks are now mitigated by the relative ease with which malicious users can interfere or tamper with sensitive data. The past decade has thus witnessed a growing concern for the issues of privacy, confidentiality, and integrity of communications. In particular, users in a communication network now often wish to communicate without being detected by others.
In this talk, we will present a framework to analyze the fundamental limits of covert communication over noisy channels based on the concepts of source and channel resolvability. Source and channel resolvability are canonical informationtheoretic problems that exploit errorcontrol codes as a means to shape the distribution of stochastic processes. This conceptual approach allows us to extend prior work by developing a complete characterization of the fundamental limits of covert communications for pointtopoint channels. In particular, we show that, irrespective of the quality of the channels, it is possible to communicate \(O(\sqrt{n})\) reliable and covert bits over \(n\) channel uses if the transmitter and the receiver share a key of size \(O(\sqrt{n})\); this improves upon earlier results requiring a key of size \(O(\sqrt{n}\log n)\) bits. Second, we show that, under certain conditions, it is possible to communicate \(O(\sqrt{n})\) reliable and covert bits over \(n\) channel uses without a secret key; this generalizes an earlier result established for binary symmetric channels.
The main technical problem that we address is how to develop concentration inequalities for “lowweight” sequences; the crux of our approach is to define suitably modified typical sets that are amenable to concentration inequalities. We will also highlight how the conceptual approach allows us to analyze the fundamental limits of covert communication in multiterminal problems.
Elette Boyle (IDC Herzliya) Is There an Oblivious RAM Lower Bound? Abstract: An Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (JACM 1996), is a (probabilistic) RAM that hides its access pattern, i.e. for every input the observed locations accessed are similarly distributed. Great progress has been made in recent years in minimizing the overhead of ORAM constructions, with the goal of obtaining the smallest overhead possible.
We revisit the lower bound on the overhead required to obliviously simulate programs, due to Goldreich and Ostrovsky. While the lower bound is fairly general, including the offline case, when the simulator is given the reads and writes ahead of time, it does assume that the simulator behaves in a “balls and bins” fashion. That is, the simulator must act by shuffling data items around, and is not allowed to have sophisticated encoding of the data.
We prove that for the OFFLINE case, showing a lower bound without the above restriction is related to the size of the circuits for sorting. Our proof is constructive, and uses a bitslicing approach which manipulates the bit representations of data in the simulation. This implies that without obtaining yet unknown superlinear lower bounds on the size of such circuits, we cannot hope to get lower bounds on offline (unrestricted) ORAMs.
Kamalika Chaudhuri (UC San Diego) (Video)
Privacypreserving Analysis of Correlated Data
Abstract: Many modern machine learning applications involve private and sensitive data that are highly correlated. Examples are mining of time series of physical activity measurements, or mining user data from social networks. Unfortunately, differential privacy, the standard notion of privacy in statistical databases, does not apply directly to such data, and as a result, there is a need for privacy mechanisms that work on correlated data and can still provide privacy.
In this talk, we consider Pufferfish, a generalization of differential privacy, that applies to correlated data. We provide novel privacy mechanisms for Pufferfish, and establish performance guarantees on them. Finally we look at a case study – analyzing aggregate statistics of a time series of physical activity measurements – with Pufferfish privacy.
Imre Csiszár (Renyi Institute, Budapest) (Video)
Secret Key Capacities for Source and Channel Models Abstract: This talk surveys fundamental limits for the problem of generating secret key (SK) for two or several parties, i.e., common randomness concealed from an eavesdropper. The largest rate at which SK can be generated, using resources specified by a given model such as correlated randomness and permissible communication, is the SK capacity of that model.
Attention will be restricted to models that admit the eavesdropper listen to but not interfere with the communication of the legal parties. The
(strong) SK capacity will be established for several twoparty and multiparty models of this kind. We focus on models where the providers of correlated randomness are memoryless sources or channels, but give hints also to models involving general sources or channels. Conclusive results are available primarily for models where the adversary has no other information than the communication she observes.
Achievablity results are proved via the familiar twostep approach:
First, common randomness is generated not requiring secrecy, and in the next ‘‘privacy amplification’’ step a (deterministic) extractor is applied to yield a function of this common randomness concealed from the eavesdropper in a strong sense. Converse results are proved via formal manipulations of information quantities, using the Csisz'arK"orner sum identity.
Main reference: I. Csisz'ar and J. K"orner, Information Theory: Coding
Theorems for Discrete Memoryless Systems, Second Edition, Cambridge University Press, 2011.
Yevgeniy Dodis (NYU) (Video)
Randomness in Cryptography
Abstract: Unlike many other fields in computer science, randomness is essential for cryptography: secrets must have uncertainty to the attacker, and many cryptographic algorithms must be randomized (e.g., two stateless encryptions of the same message must look different). Traditionally, one assumes the existence of perfect randomness. However, this assumption is often unrealistic. In this talk I will survey what is know about basing cryptography of various (realistic) sources of randomness. We will ask the following questions:
1) Does Cryptography need nearly perfect (“extractable”) sources of randomness, or is entropy sufficient? 2) What if the secret key is imperfect but “local” (or public) perfect randomness is available?
As we will see, the answer to the first question is largely negative, while the second questions leads to many positive answers, some of which found many applications beyond cryptography.
Cynthia Dwork (Microsoft Research) (Video)
Differentially Private False Discovery Control
Stefan Dziembowski (University of Warsaw) (Video)
Modelling SideChannel Leakage Abstract: Physical sidechannel attacks that exploit leakage emitting from devices are an important threat for cryptographic implementations. A recent trend in cryptography is to construct cryptographic algorithms that are secure given leakage model. Over the past 15 years there has been a number of such models proposed in the literature, starting with the probing model of Ishai et al [CRYPTO 2003], where the computation is modelled as a Boolean circuit, and the adversary can learn a limited number of them. Other models studied in the theory community include the boundedleakage paradigm [Dziembowski, TCC 2006],[Akavia et al, TCC 2009], theonly computation leaks model [Micali and Reyzin, TCC 2004], the independent leakage model [Dziembowski and Pietrzak, FOCS 2008], the auxiliary input model [Dodis et al, TCC 2010], and many others.
Some of these models have been received with skepticism by the practitioners, who often argued that it is much more realistic to model leakage as a noisy function of the secret data. The first model for such noisy leakagewas proposed by Chari et al, [CRYPTO’99], and fully formalized by Prouff and Rivain [Eurocrypt 2013]. Somewhat surprisingly, recently Duc, Dziembowski, and Faust [Eurocrypt 2014] have shown that in fact the noisy leakage model of Prouff and Rivain can be reduced the probing model (i.e.: every noisy leakage function can be simulated be a probing function), which, in particular, greatly simplifies several proofs in the noisy leakage model, and can be viewed as closing the gap between theory and practice in this area.
In this talk we will give an overview of the leakage models used in the literature and present the reduction from the Duc et al paper. If time permits we will also talk about the followup work of Dziembowski, Faust and Skórski [Eurocrypt 2015].
Elza Erkip (Polytechnic Institute of NYU)
Anonymity in Social Networks: Fundamental Bounds and Connections to Community Detection Abstract: Social networks provide abundant amount of data for research on population dynamics and enhancing the user experience, such as individualized advertisements. An important concern while analyzing the network data is protecting the privacy of the users. Recent attacks on disclosed network data suggest that keeping the users anonymous is not enough for protecting the identities due to potential help of other publicly available information for successful deanonymization.
Social networks are known to follow a community structure, where nodes within a community have a higher chance of being connected among themselves than to nodes outside of their community. There has recently been significant interest in understanding the fundamental limits of and designing computationally efficient algorithms for detecting communities in social networks. Community detection problem has implications well beyond social networks, in areas including machine learning, genetics, and ecology, among others.
In the talk, we treat the deanonymization problem to recover user identities in a social network as a matching problem between two samples of a random graph conforming to a community structure. We formalize the optimal estimate of the attacker and find fundamental bounds on deanonymizability. The context we introduce allows us to explore the relationship between the problems of deanonymization and community detection, and suggests a number of interesting future research directions.
Joint work with Efe Onaran and Siddharth Garg
Iftach Haitner (Tel Aviv University) (Video: Part 1, Part 2, Part 3)
Leo Reyzin (Boston University) Pseudoentropy and pseudorandomness Abstract: If you see a cryptographic hash of my password, how can I quantify your uncertainty about the password? Entropy – a traditional measure of uncertainty – is of little help: conditioned on your knowledge of the hash value, the distribution of my passwords has small support, and yet your knowledge should not of be of much help to you in guessing my password. Conversely, if you see a cryptographic hash of a long document, how can you quantify my certainty about the document? Entropy is again of little help: there are many possible documents that hash to the same value, and yet you can be fairly certain that I know at most one of them.
Computational analogues of entropy provide answers to these questions and enable a host of cryptographic applications. In fact, the right notion of entropy and a toolbox of lemmas can make for beautifully simple proofs. This talk will survey some of the notions, lemmas, and applications.
Masahito Hayashi (Nagoya University) Shannon Theoretic Analysis for Classical and Quantum Information Security Abstract: Generating secure key from correlated random number is fundamental and important task in information theory. In the i.i.d. setting, it is known that the asymptotic optimal secure key generation rate
is the conditional entropy when the leaked information is classical or
quantum. On the other hand, source and channel coding problems, there are
many results for the exponential decreasing rate of decoding error
probability. In this talk, we adopt two kinds of security criteria, One is
the modified mutual information, which is defined by the relative enetropy
between the ideal distribution and true distribution. We show the validity
of this criterion. The other is the L_1 norm criterion, which is
defined as the variational distance between the same distributions as the
above. The former is used in the information theory community and the
latter is used in the community of cryprography. As our result, we derive
the optimal exponential decreasing rates for both criteria in the
i.i.d. case when the leaked information is classical. In the
latter security criterion, the collision entropy plays a more important
role than the minimum entropy. Further, in this case, we generalize the
modified mutual information, and derive the asymptotic optimal secure key
generation rate and the optimal exponential decreasing rates under the
generalization. Finally, we also consider the quantum case, i.e., the
case when the leaked information is quantum. We discuss how can we
generalize our results to the quantum case partially. Further, we
also discuss what kinds of hash function is effective for our purpose. We also discuss the extension to the Markovian case. Finally,
we discuss the relation with blind computation.
These results contain collaborations with Vincent Tan, Shun Watanabe,
Toyohiro Tsurumaru, and Tomoyuki Morimae
Yuval Ishai (Technion) (Video: Part 1, Part 2, Part 3, Part 4)
Manoj Prabhakaran (University of Illinois)
A minicourse on Secure Multiparty Computation  Part I
Abstract: Secure multiparty computation allows two or more parties to perform a distributed computation on their local inputs while hiding the inputs from each other. This part of the minicourse will give a broad overview of research in the area, covering definitions, known results, connections with other problems, and open questions. A minicourse on Secure Multiparty Computation  Part I Abstract: In this part we will cover in greater detail certain information theoretic aspects of secure multiparty computation (MPC). Specifically we will discuss capacity questions related to MPC.
Delaram Kahrobaei (City University of New York) (Video)
Cryptosystems Based on GroupTheoretic Problems: A Survey, New Results, Open Problems Abstract: In this talk I will survey some of the cryptosystems based on group theoretic problems and their computational complexity such as Conjugacy, Membership, Endomorphism, Word, Twisted Conjugacy, and Geodesic Length Problems. I will speak about some nonabelian groups that have been proposed as platforms for such cryptosystems: Braid, Polycyclic, Metabelian, Grigorchuk, Thompson, Matrix, Hyperbolic, Small Cancellation, right angled Artin Groups and free nilpotent pgroups.
The focus of the talk will be on infinite polycyclic groupbased cryptosystems as well as a cryptosystem based on semidirect product of (semi)groups. The latter is a joint work with V. Shpilrain.
There will be open problems related to both computational complexity of group theoretic problems and cryptographic problems that I will mention at the end of the talk.
Negar Kiyavash (UIUC) (Video)
Privacypreserving Data Analytics on Social Networks: Limits of Deanonymizablity Abstract: Social networks are an integral part of our lives. They provide significant amount of explicit and implicit information about their users. On one hand this data could be analyzed and harnessed for multitude of purposes: conducting polls, market analysis, etc. On the other hand, release of data could seriously compromise user privacy. Thus, before its release, the data must be processed in a manner that minimizes the risk of sharing private information of the users while allowing for performing the desired data analytics.
In this talk we study the limits of deanonymizability of social networks by casting the problem as graph matching. Specifically, for the class of ErdosRenyi random graph models, we ask when does the correlation induced by the structural properties of the graph allow the users to be deanonymized? We provide achievability and converse bounds that differ by a factor of two throughout the parameter space.
Joerg Kliewer (New Jersey Institute of Technology) (Video)
Lossy Compression with Privacy Constraints: Optimality of Polar Codes
Yingbin Liang (Syracuse University) (Video)
Kernelbased Detection of Anomalous Structures over Large Networks Abstract: This talk will focus on a type of problems, the goal of which is to detect existence of an anomalous object over a network. An anomalous object, if it exists, corresponds to a cluster of nodes in the network that take data samples generated by an anomalous distribution q whereas all other nodes in the network receive samples generated by a distinct distribution p. Such a problem models a variety of applications such as detection of an anomalous intrusion via sensor networks and detection of an anomalous segment in a DNA sequence. All previous studies of this problem have taken parametric models, i.e., distributions p and q are known. Our work studies the nonparametric model, in which distributions can be arbitrary and unknown a priori.
In this talk, I will first introduce the approach that we apply, which is based on mean embedding of distributions into a reproducing kernel Hilbert space (RKHS). In particular, we adopt the quantity of maximum mean discrepancy (MMD) as a metric of distance between mean embeddings of two distributions. I will then present our construction of MMDbased tests for anomalous detection over networks and our analysis of performance guarantee of the proposed tests. I will finally present a number of numerical results to demonstrate our results. Towards the end of the talk, I will discuss some related problems and conclude with a few future directions.
Huijia Lin (University of California, Santa Barbara) (Video)
Zero Knowledge Protocols Abstract: Zeroknowledge protocols, introduced by Goldwasser, Micali, and Rackoff [STOC 1985], are fascinating constructs in cryptography: They provide the paradoxical guarantee that a player, the prover, can convince another player, the verifier, of the validity of a mathematical statement, without revealing any information beyond the validity. Since their introduction, zeroknowledge protocols have played an important role in the development of many cryptographic tools and systems; most typically, zeroknowledge protocols are used to force malicious adversaries to follow the specified protocol without deviation.
In this talk, we will present the definition of zeroknowledge protocols, their basic constructions, and some recent developments on variants of zeroknowledge protocols.
Moni Naor (Wezimann Institute of Science) (Video)
How to Share a Secret, Infinitely Abstract: Secret sharing schemes allow a dealer to distribute a secret piece of information among several parties such that only qualified subsets of parties can reconstruct the secret. The collection of qualified subsets is called an access structure. The best known example is the \(k\)threshold access structure, where the qualified subsets are those of size at least \(k\). When \(k=2\) and there are \(n\) parties, there are schemes where the size of the share each party gets is roughly \(\log n\) bits, and this is tight even for secrets of
\(1\) bit. In these schemes, the number of parties n must be given in advance to the dealer.
We consider the case where the set of parties is not known in advanced and could potentially be infinite. Our goal is to give the party arriving at step \(t\) a small share as possible as a function of \(t\). Our main result is such a scheme for the \(k\)threshold access structure where the share size of
party \(t\) is \((k1) \log t\) plus \(o(\log t) \mathrm{poly}(k)\). For \(k=2\) we observe an equivalence to prefix codes and present matching upper and lower bounds of the form \(\log t + \log \log t + \log \log \log t + \cdots + O(1)\).
Finally, we show that for any access structure there exists such a secret sharing scheme with shares of size \(2^{t1}\).
Joint work with Ilan Komargoski and Eylon Yogev
Aleksandar Nikolov (University of Toronto)
Optimal Mechanism for Small Databases Using Convex Programming Abstract: We study the problem of answering a workload of linear queries Q on a database of size at most n drawn from a universe U under the constraint of (approximate) differential privacy. Nikolov, Talwar, and Zhang (STOC13) proposed an efficient mechanism that, for any given Q and n, answers the queries with average error that is at most a factor polynomial in log Q and log U worse than the best possible. We improve on this guarantee and give a mechanism whose competitiveness ratio is at most polynomial in log n and log U, and has no dependence on the number of queries. Our mechanism is based on the projection mechanism of Nikolov, Talwar, and Zhang, but in place of an adhoc noise distribution, we use a distribution which is in a sense optimal for the projection mechanism, and analyze it using convex duality and the restricted invertibility principle.
Kobbi Nissim (BenGurion University) (Video)
Accessing Data while Preserving Privacy
Sirin Nitinawarat (Qualcomm Technologies, Inc.) (Video)
Duality in Combinatorial Optimization and Information Theoretic Secrecy Abstract: We show that an old result from NashWilliams and Tutte on the duality in maximal spanning tree packing in multigraphs carries an informationtheoretic significance in the context of largest multiterminal secret key generation from pairwise independent secret keys. This information theoretic interpretation leads to a new form for the dual term in the result of NashWilliams and Tutte. We then discuss a natural generalization of the multiterminal secret key generation with the presence of a helper. In an interesting case with the ‘‘weak’’ helper, we show that the duality generalizes to maximal Steiner tree packing, which is NPhard.
Sewoong Oh (University of Illinois) (Video)
Operational interpretation of differential privacy and its applications. Abstract: Interactive querying of a database degrades the privacy level. In this paper we answer the fundamental question of characterizing the level of differential privacy degradation as a function of the number of adaptive interactions and the differential privacy levels maintained by the individual queries. Our solution is complete: the privacy degradation guarantee is true for every privacy mechanism and, further, we demonstrate a sequence of privacy mechanisms that do degrade in the characterized manner. The key innovation is the introduction of an operational interpretation (involving hypothesis testing) to differential privacy and the use of the corresponding data processing inequalities. Our result improves over the state of the art and has immediate applications to several problems studied in the literature.
Krzysztof Pietrzak (IST Austria) (Video)
Recent Advances and Challenges in Pseudoentropy
Abstract: We present some recent results and open problems concerning computational notions of entropy, aka. pseudoentropy.
Manoj Prabhakaran (University of Illinois at UrbanaChampaign) (Video)
Questions in Cryptographic Complexity
Abstract: I will briefly survey some of the results on measuring “cryptographic complexity” of (multiparty) functions, and describe some important open problems in this area.
Lalitha Sankar (Arizona State University) (Video)
Informationtheoretic Privacy: The Utility of an AverageCase Approach
Abstract: As information about individuals and enterprises moves to an entirely digital medium, keeping certain aspects of the data confidential (even) from the legitimate data users, i.e., information privacy, is becoming an important and immediate societal problem. While the benefits (utility) of electronic data are multifold, there is a need to provide precise guarantees and limits on the private data leaked and quantify the tradeoff between utility and privacy, irrespective of the application. In this talk, we introduce an informationtheoretic (IT) framework to formulate and study the utilityprivacy tradeoff problem. We illustrate the application of the framework to three broad classes of privacy problems: (i) database privacy in which the privacy of the individuals in the database has to be preserved while ensuring statistical utility of the data; (ii) consumer privacy in which we bound the inferences possible from streaming timeseries data used to remotely monitoring consumers; and (iii) competitive (interactive) privacy in which distributed agents (with possibly competing interests) seek to exchange data minimally for a desired system performance while preserving the confidentiality/privacy of specific aspects of their data – for this interactive setting, we also present a composition rule. Finally, we compare the utilityprivacy performance of ITprivacy with the worstcase privacy guarantees offered by differential privacy for a data set whose statistics are not precisely known but restricted to a class of distributions and for a utility constraint quantified by Hamming distortion.
Adam Smith (Penn State) (Video: Part 1, Part 2, Part 3)
Tutorial on Differential Privacy
Abstract: The tutorial will introduce differential privacy, a widely used
definition of privacy for statistical databases.
We will begin with the motivation for rigorous definitions of privacy
in statistical databases, covering several examples of how seemingly
aggregate, highlevel statistics can leak information about
individuals in a data set. We will then define differential privacy,
illustrate the definition with several examples, and discuss its
properties. The bulk of the tutorial will cover the principal
techniques used for the design of differentially private algorithms.
Time permitting, we will touch on applications of differential privacy
to problems having no immediate connection to privacy, such as equilibrium selection in game theory and adaptive data analysis in statistics and machine learning.
Stefano Tessaro (University of California, Santa Barbara) (Video)
A Cryptographic Perspective on Informationtheoretic Security
Abstract: Over the last few decades, the information theory and the cryptography communities have often studied related security problems. However, they have more than often adopted very different approaches and techniques.
The main purpose of this talk is to contribute to bridging this gap, by providing a cryptographic viewpoint on some security problems considered in the informationtheory and physicallayer communities. The hope is to convey how to cryptographic approach (both on security metrics and proofs) can be beneficial to information theorists, but also, conversely, how informationtheoretic insights can be helpful to cryptographers. I will start this talk with the classical wiretap setting, and then hopefully move on to other topics.
(The talk is partially based on joint works with Mihir Bellare and Alexander Vardy.)
Luca Trevisan (University of California, Berkeley) (Video)
Quantum lower bound for inverting a permutation with advice Abstract: Hellman proved that any permutation can be inverted nontrivially fast given precomputed information. Any permutation \(f:
[N] > [N]\) can be inverted in time T given a precomputed data structure of size \(N/T\), up to lowerorder terms. In the blackbox model, Yao proved the optimality of this tradeoff. In particular, a data structure of size of the order of \(\sqrt{N}\) allows inversion time of the order of \(\sqrt{N}\).
Using Grover's algorithm, a quantum algorithm is able to invert any permutation \(f: [N] > [N]\) in time order of \(\sqrt{N}\). What gain is possible given precomputed data? Could we hope for time and data size to be both of the order of \(N^{1/4}\)?
In the blackbox model, we show that, given data of size \(S\), the time as to be at least of the order of \(\sqrt{N/S}\), and so either time or size have to be at least \(N^{1/3}\).
Our lower bound is not known to be tight, and probably it is not: we believe that, in the blackbox model, there is no quantum algorithm that achieves time less than \(\sqrt{N}\) using data size less than \(\sqrt{N}\).
(Joint work with Nayebi, Aaronson and Belov)
Himanshu Tyagi (Indian Institute of Science, Bangalore) (Video: Part 1, Part 2, Part 3)
Shun Watanabe (Tokyo University of Agriculture and Technology) Information Theoretic Secrecy and Interactive Communication Abstract: Information theoretic secrecy refers to unconditional
secrecy against a computationally unbounded adversary with any
statistical procedure at his or her disposal. As is wellknown, in absence
of any additional resources, information theoretic secrecy is either
not feasible from scratch. However, if the legitimate parties share
some correlated randomness, many of the classical cryptographic primitives can be realized with information theoretic secrecy. Such correlated randomness can be accessed, for instance, from physical observations such as the fade of the wireless communication channel shared by the parties or can
be purchased from trusted servers as in commoditybased cryptography. In this tutorial talk, we shall consider multiparty secret key agreement and secure multiparty (as well as twoparty) computing problems, when the parties can access correlated randomness. In addition, the parties are allowed to
communicate interactively over an authenticated, noiseless public
channel. We will review the basic results that emerged over the last
two decades in the information theory literature, which exhibit a
close connection between secrecy generation and compression using interactive communication. The class of problems considered is very rich and
connects to many basic problems in information theory, cryptography,
and communication complexity. The list of topics to be covered
include notions of secrecy, two party secret key agreement
(information reconciliation and privacy amplification), multiparty
secret key agreement and common randomness decomposition, two party
secure computing, and multiparty secure computing with trusted
parties. We shall also discuss some of our own results, namely a new
upper bound for secret key length using interactive public
communication and its role in characterising the minimum amount of
communication needed for simulation of interactive protocols.
Jonathan Ullman (Northeastern University) (Video)
Privacy and the Complexity of Simple Queries Abstract: Abstract: I will present some new, nearlyoptimal lower bounds on the amount of data required to release differentially private statistics on highdimensional datasets, both in informationtheoretic and computational settings. These results show that there is a significant “price of differential privacy” in highdimensional datasets. We prove these lower bounds using two closelyrelated cryptographic primitives fingerprinting codes (in information theoretic setting) and traitortracing schemes (in the computational setting) that we show are closely connected to differentially private data analysis. I will also discuss how these lower bounds are related to realistic attacks on released datasets.
Sennur Ulukus (University of Maryland) (Video)
Physical Layer Security with No Eavesdropper Channel State Information Abstract: While informationtheoretic physicallayer security is a powerful technique that guarantees unconditional security, early work in this field developed secrecy capacity and secure degrees of freedom results based on perfect knowledge of the channel state of the adversary. Eavesdropping adversaries are passive, and it is hard or impossible to attain information about their channel state. In this talk, we will summarize recent results on optimal signaling schemes when no channel state information is available about the adversary’s channel.
Alex Vardy (University of California, San Diego) (Video)
Private Information Retrieval without Storage Overhead: Coding Instead of Replication Abstract: Private information retrieval protocols allow a user to retrieve
a data item from a database without revealing any information
about the identity of the item being retrieved. Specifically, in
informationtheoretic \(k\)server PIR, the database is replicated
among \(k\) noncommunicating servers, and each server learns nothing
about the item retrieved by the user. The effectiveness of PIR
protocols is usually measured in terms of their communication
complexity, which is the total number of bits exchanged between
the user and the servers. However, another important cost parameter
is the storage overhead, which is the ratio between the total
number of bits stored on all the servers and the number of bits in
the database. Since singleserver informationtheoretic PIR is
impossible, the storage overhead of all existing PIR protocols
is at least \(2\) (or \(k\), in the case of \(k\)server PIR).
In this work, we show that informationtheoretic PIR can be
achieved with storage overhead arbitrarily close to the optimal
value of \(1\), without sacrificing the communication complexity.
Specifically, we prove that all known \(k\)server PIR
protocols can be efficiently emulated, while preserving both
privacy and communication complexity but significantly reducing
the storage overhead. To this end, we distribute the \(n\) bits
of the database among \(s+r\) servers, each storing \(n/s\) coded
bits (rather than replicas). Notably, our coding scheme remains
the same, regardless of the specific \(k\)server PIR protocol being
emulated. For every fixed \(k\), the resulting storage overhead
\((s+r)/s\) approaches \(1\) as \(s\) grows; explicitly we have
\(r \le k \sqrt{s}\bigl(1 + o(1)\bigr)\). Moreover, in the special
case \(k = 2\), the storage overhead is only \(1 + \frac{1}{s}\).
In order to achieve these results, we introduce and study a new
kind of binary linear codes, called here \(k\)server PIR codes.
We then show how such codes can be constructed from Steiner systems,
from onestep majoritylogic decodable codes, from constantweight
codes, and from certain locally recoverable codes. We also establish
several bounds on the parameters of \(k\)server PIR codes, and tabulate
the results for all \(s \le 32\) and \(k \le 16\).
[Based on joint work with Arman Fazeli, Sankeerth Rao, and Eitan Yaakobi]
Ye Wang (Mitsubishi Electric Research Laboratories) (Video)
On the Role of Common Information in Security and Privacy Abstract: Common information aims to characterize the common randomness between two random variables. Two distinct, but related, definitions for common information were proposed in the 1970s by Gács and Körner and by Wyner, each with operational significance for particular coding problems. In this talk, we will show how these classical measures are useful tools in the characterization and derivation of several recent results in security and privacy. In particular, common information characterizes which channels are complete for secure twoparty computation, as well as playing a key role in the simplified converse proof. Common information also characterizes which joint distributions are trivial to securely sample, which has applications in realizing correlated equilibria for games preceded by communication. In the problem of privacypreserving data release, common information characterizes whether the best privacyutility tradeoffs attainable by an output perturbation mechanism will be generally optimal or strictly suboptimal.
Hoeteck Wee (ENS, Paris) (Video)
Functional Encryption and InformationTheoretic Cryptography Abstract: Can we encrypt data while enabling finegrained access control and selective computation? In this talk, we will survey how addressing this question led to new connections and questions in informationtheoretic cryptography.
Stephanie Wehner (Delft University of Technology) (Video)
Deviceindependence in quantum cryptography Abstract: While quantum cryptography offers interesting security guarantees, it is challenging to build good quantum devices. In practise, we will therefore typically rely on devices built by someone else, whose properties are difficult to characterize and which exhibit inherent imperfections that may threaten security.
The goal of device independent quantum cryptography is to develop tests that allow (partially) unknown and uncharacterized quantum devices to be used safely. Specifically, we imagine that quantum devices act as black boxes, which we can only ask to perform certain quantum measurements and collect the resulting measurement outcomes. However, the quantum state or actual measurements performed by the device are unknown. Security guarantees should then be given purely as a function of such classical input/output behaviour.
This talk will be an introduction to the concept of device independence in quantum cryptography that does not assume any knowledge of quantum information. We briefly review results in device independent quantum key distribution, before exhibiting very recent work on device independent twoparty quantum cryptography. Finally, we will discuss some of the many open challenges in certifying properties of quantum devices based on classically observed statistics.
Daniel Wichs (Northeastern) Adaptively Secure Garbled Circuits from OneWay Functions Abstract: A garbling scheme is used to garble a circuit C and an input x in a way that reveals the output C(x) but hides everything else. In many settings, the circuit can be garbled offline without strict constraints on efficiency, but the input must be garbled very efficiently online, in time which is much smaller than the circuit size C. Yao's garbling scheme only achieves this under oneway functions in the selective security setting. It has remained as an open problem to achieve the stronger notion of adaptive security where the adversary can choose the input x adaptively after seeing the garbled circuit.
In this work, we modify Yao's scheme in a way that maintains all of its desirable features, while allowing us to prove adaptive security in various parameter regimes under oneway functions. As our main instantiation, we get a scheme where the size of the garbled input is only proportional to the width of the circuit, which is related to the space complexity of the computation, but independent of the circuit's depth. More broadly, we develop a connection between adaptive security in our framework and a certain type of pebble complexity}
As our main tool, of independent interest, we develop a new notion of somewhere equivocal encryption, which allows us to efficiently equivocate on a small subset of the message bits.
Frans Willems (Eindhoven University of Technology) Information Leakage in Security Systems Based on SRAMPUFs Abstract: In this lecture we discuss hardwareintrinsic security systems based on physical unclonable functions (PUFs) realised by static randomaccess memory (SRAM). We first focus on the fingerprinting behaviour of SRAM during powerup. We then connect this behaviour with the notion of secretkey capacity (Mauer (1993), Ahlswede & Csiszar (1993)). In the unbiased case the SRAM can be modelled as a binary symmetric channel and the secret key capacity can be achieved in principle with the XORmethod and linear errorcorrecting codes.
We first study the multipleobservation statistics of SRAM and discuss a notion of symmetry in multipleobservation settings. This notion allows us to investigate, for the XORmethod, the information leakage, i.e., the information that the helper data contains about the secret key. We show that in multipleenrolment scenario’s with new keys there is no leakage, and even if the same key is enrolled several times the leakage is zero, if the SRAM satisfies our notion of symmetry. Leakage however can occur if two keys are enrolled on the same SRAM with different codes, producing two helper data streams. We show this by an example.
Andreas Winter (Universitat Autonoma de Barcelona) (Video)
Constructions and Limitations of Quantum Data Hiding Abstract: Quantum data hiding, originally invented as a limitation on local operations and classical communications (LOCC) in distinguishing
globally orthogonal states, is actually a phenomenon arising generically
in statistics whenever comparing a 'strong’ set of measurements (i.e.,
decision rules) with a 'weak’ one. The classical statistical analogue of
this would be secret sharing, in which two perfectly distinguishable
multipartite hypotheses appear to be indistinguishable when accessing
only a marginal. The quantum versions are richer in that for example
LOCC allows for state tomography, so the states cannot be come
perfectly indistinguishable but only nearly so, and hence the question
is one of efficiency. The issues covered in the talk are going to be the
following:
1. We will revisit a construction by Hayden/Leung/Smith for multiparty
LOCC data hiding, and as a new result show that it meets a universal
bound on the information efficiency of any data hiding scheme.
2. Gaussian operations and classical computation (GOCC): Not very
surprisingly, GOCC cannot distinguish optimally even two coherent
states of a single mode (Takeoka & Sasaki, PRA 78:022320, 2008).
But we can find states, each a mixture of multimode coherent states,
which are almost perfectly distinguishable by suitable measurements,
by when restricted to GOCC, i.e. linear optics and postprocessing, the
states appear almost identical. The construction is random and relies
on coding arguments. Open questions include whether one can give
a constructive version of the argument, and whether for instance
even thermal states can be used, or how efficient the hiding is.
