Provably Secure Symmetric Private Information Retrieval with Quantum Cryptography

Private information retrieval (PIR) is a database query protocol that provides user privacy in that the user can learn a particular entry of the database of his interest but his query would be hidden from the data centre. Symmetric private information retrieval (SPIR) takes PIR further by additionally offering database privacy, where the user cannot learn any additional entries of the database. Unconditionally secure SPIR solutions with multiple databases are known classically, but are unrealistic because they require long shared secret keys between the parties for secure communication and shared randomness in the protocol. Here, we propose using quantum key distribution (QKD) instead for a practical implementation, which can realise both the secure communication and shared randomness requirements. We prove that QKD maintains the security of the SPIR protocol and that it is also secure against any external eavesdropper. We also show how such a classical-quantum system could be implemented practically, using the example of a two-database SPIR protocol with keys generated by measurement device-independent QKD. Through key rate calculations, we show that such an implementation is feasible at the metropolitan level with current QKD technology.     

Bottleneck Problems: An Information and Estimation-Theoretic View

Information bottleneck (IB) and privacy funnel (PF) are two closely related optimization problems which have found applications in machine learning, design of privacy algorithms, capacity problems (e.g., Mrs. Gerber’s Lemma), and strong data processing inequalities, among others. In this work, we first investigate the functional properties of IB and PF through a unified theoretical framework. We then connect them to three information-theoretic coding problems, namely hypothesis testing against independence, noisy source coding, and dependence dilution. Leveraging these connections, we prove a new cardinality bound on the auxiliary variable in IB, making its computation more tractable for discrete random variables. In the second part, we introduce a general family of optimization problems, termed “bottleneck problems”, by replacing mutual information in IB and PF with other notions of mutual information, namely f-information and Arimoto’s mutual information. We then argue that, unlike IB and PF, these problems lead to easily interpretable guarantees in a variety of inference tasks with statistical constraints on accuracy and privacy. While the underlying optimization problems are non-convex, we develop a technique to evaluate bottleneck problems in closed form by equivalently expressing them in terms of lower convex or upper concave envelope of certain functions. By applying this technique to a binary case, we derive closed form expressions for several bottleneck problems.     

Multi-Bit Quantum Private Query

Most of the existing Quantum Private Queries(QPQ) protocols provide only single-bit queries service,thus have to be repeated several times when more bits are retrieved. Wei et al.'s scheme for block queries requires a high-dimension quantum key distribution system to sustain, which is still restricted in the laboratory. Here, based on Markus Jakobi et al.'s single-bit QPQ protocol, we propose a multi-bit quantum private query protocol, in which the user can get access to several bits within one single query. We also extend the proposed protocol to block queries, using a binary matrix to guard database security. Analysis in this paper shows that our protocol has better communication complexity, implementability and can achieve a considerable level of security.     

Multi-Bit Quantum Private Query

Most of the existing Quantum Private Queries (QPQ) protocols provide only single-bit queries service, thus have to be repeated several times when more bits are retrieved. Wei et al.'s scheme for block queries requires a high-dimension quantum key distribution system to sustain, which is still restricted in the laboratory. Here, based on Markus Jakobi et al.'s single-bit QPQ protocol, we propose a multi-bit quantum private query protocol, in which the user can get access to several bits within one single query. We also extend the proposed protocol to block queries, using a binary matrix to guard database security. Analysis in this paper shows that our protocol has better communication complexity, implementability and can achieve a considerable level of security.     

The Information Interpretation and the Conceptual Problems of Quantum Mechanics

It has been traditionally considered that Quantum Mechanics has two conceptual kinds of problems, namely, those related with local-realism and the so-called measurement problem. That is, the uniqueness of the result when we make a measurement. With the development of what is called generically Quantum Information Theory, a new form of the Copenhagen interpretation of the formalism has taken shape.⁽¹⁾ In this paper, we will analyse if this information interpretation is able to clarify these old problems. Although this interpretation seems to be the most promising approach we have, we have reached the conclusion that the answer cannot be given in a positive and clear way yet.     

Adaptive Block-Based Compressed Video Sensing Based on Saliency Detection and Side Information

The setting of the measurement number for each block is very important for a block-based compressed sensing system. However, in practical applications, we only have the initial measurement results of the original signal on the sampling side instead of the original signal itself, therefore, we cannot directly allocate the appropriate measurement number for each block without the sparsity of the original signal. To solve this problem, we propose an adaptive block-based compressed video sensing scheme based on saliency detection and side information. According to the Johnson–Lindenstrauss lemma, we can use the initial measurement results to perform saliency detection and then obtain the saliency value for each block. Meanwhile, a side information frame which is an estimate of the current frame is generated on the reconstruction side by the proposed probability fusion model, and the significant coefficient proportion of each block is estimated through the side information frame. Both the saliency value and significant coefficient proportion can reflect the sparsity of the block. Finally, these two estimates of block sparsity are fused, so that we can simultaneously use intra-frame and inter-frame correlation for block sparsity estimation. Then the measurement number of each block can be allocated according to the fusion sparsity. Besides, we propose a global recovery model based on weighting, which can reduce the block effect of reconstructed frames. The experimental results show that, compared with existing schemes, the proposed scheme can achieve a significant improvement in peak signal-to-noise ratio (PSNR) at the same sampling rate.     

Partial Information Decomposition and the Information Delta: A Geometric Unification Disentangling Non-Pairwise Information

Information theory provides robust measures of multivariable interdependence, but classically does little to characterize the multivariable relationships it detects. The Partial Information Decomposition (PID) characterizes the mutual information between variables by decomposing it into unique, redundant, and synergistic components. This has been usefully applied, particularly in neuroscience, but there is currently no generally accepted method for its computation. Independently, the Information Delta framework characterizes non-pairwise dependencies in genetic datasets. This framework has developed an intuitive geometric interpretation for how discrete functions encode information, but lacks some important generalizations. This paper shows that the PID and Delta frameworks are largely equivalent. We equate their key expressions, allowing for results in one framework to apply towards open questions in the other. For example, we find that the approach of Bertschinger et al. is useful for the open Information Delta question of how to deal with linkage disequilibrium. We also show how PID solutions can be mapped onto the space of delta measures. Using Bertschinger et al. as an example solution, we identify a specific plane in delta-space on which this approach’s optimization is constrained, and compute it for all possible three-variable discrete functions of a three-letter alphabet. This yields a clear geometric picture of how a given solution decomposes information.     

Interpreting Social Accounting Matrix (SAM) as an Information Channel

Information theory, and the concept of information channel, allows us to calculate the mutual information between the source (input) and the receiver (output), both represented by probability distributions over their possible states. In this paper, we use the theory behind the information channel to provide an enhanced interpretation to a Social Accounting Matrix (SAM), a square matrix whose columns and rows present the expenditure and receipt accounts of economic actors. Under our interpretation, the SAM’s coefficients, which, conceptually, can be viewed as a Markov chain, can be interpreted as an information channel, allowing us to optimize the desired level of aggregation within the SAM. In addition, the developed information measures can describe accurately the evolution of a SAM over time. Interpreting the SAM matrix as an ergodic chain could show the effect of a shock on the economy after several periods or economic cycles. Under our new framework, finding the power limit of the matrix allows one to check (and confirm) whether the matrix is well-constructed (irreducible and aperiodic), and obtain new optimization functions to balance the SAM matrix. In addition to the theory, we also provide two empirical examples that support our channel concept and help to understand the associated measures.     

Information flow in sensory neurons

Summary Recent experiments show that the neural codes at work in a wide range of creatures share some common features. At first sight, these observations seem unrelated. However, we show that all of these features of the code arise naturally in a simple threshold crossing model when we choose the threshold to maximize the transmitted information. This maximization process requires neural adaptation to not only the d.c. signal level, as in conventional light and dark adaptation (for example), but also to the statistical structure of the signal and noise distributions. Interestingly, if we fix the threshold level, we can observe a peak in the transmitted information at a finite value of the input signal-to-noise ratio. However, when we allow the threshold to adapt to the statistical structure of the signal and noise, the transmitted information is always monotonically increasing with increasing input signal-to-noise ratio. Paper presented at the International Workshop ?Fluctuations in Physics and Biology: Stochastic Resonance, Signal Processing and Related Phenomena?, Elba, 5–10 June 1994.     

Information Theories with Adversaries,Intrinsic Information,and Entanglement

There are aspects of privacy theory that are analogous to quantum theory. In particular one can define distillable key and key cost in parallel to distillable entanglement and entanglement cost. We present here classical privacy theory as a particular case of information theory with adversaries, where similar general laws hold as in entanglement theory. We place the result of Renner and Wolf—that intrinsic information is lower bound for key cost—into this general formalism. Then we show that the question of whether intrinsic information is equal to key cost is equivalent to the question of whether Alice and Bob can create a distribution product with Eve using I_M bits of secret key. We also propose a natural analogue of relative entropy of entanglement in privacy theory and show that it is equal to the intrinsic information. We also provide a formula analogous to the entanglement of formation for classical distributions. It is our pleasure to dedicate this paper to Asher Peres on the occasion of his seventieth birthday.     

Redundant Information Neural Estimation

We introduce the Redundant Information Neural Estimator (RINE), a method that allows efficient estimation for the component of information about a target variable that is common to a set of sources, known as the “redundant information”. We show that existing definitions of the redundant information can be recast in terms of an optimization over a family of functions. In contrast to previous information decompositions, which can only be evaluated for discrete variables over small alphabets, we show that optimizing over functions enables the approximation of the redundant information for high-dimensional and continuous predictors. We demonstrate this on high-dimensional image classification and motor-neuroscience tasks.     

论动态信息理论

本文综述了作者的研究成果.近十年,作者将现有静态统计信息理论拓展至动态过程,建立了以表述动态信息演化规律的动态信息演化方程为核心的动态统计信息理论.基于服从随机性规律的动力学系统(如随机动力学系统和非平衡态统计物理系统)与遵守确定性规律的动力学系统(如电动力学系统)的态变量概率密度演化方程都可看成是其信息符号演化方程,推导出了动态信息(熵)演化方程.它们表明:对于服从随机性规律的动力学系统,动态信息密度随时间的变化率是由其在系统内部的态变量空间和传递过程的坐标空间的漂移、扩散和耗损三者引起的,而动态信息熵密度随时间的变化率则是由其在系统内部的态变量空间和传递过程的坐标空间的漂移、扩散和产生三者引起的.对于遵守确定性规律的动力学系统,动态信息(熵)演化方程与前者的相比,除动态信息(熵)密度在系统内部的态变量空间仅有漂移外,其余皆相同.信息和熵已与系统的状态和变化规律结合在一起,信息扩散和信息耗损同时存在.当空间噪声可略去时,将会出现信息波.若仅研究系统内部的信息变化,动态信息演化方程就约化为与表述上述动力学系统变化规律的动力学方程相对应的信息方程,它既可看成是表述动力学系统动态信息的演化规律,亦可看成是动力学系统的变化规律都可由信息方程表述.进而给出了漂移和扩散信息流公式、信息耗散率公式和信息熵产生率公式及动力学系统退化和进化的统一信息表述公式.得到了反映信息在传递过程中耗散特性的动态互信息公式和动态信道容量公式,它们在信道长度和信号传递速度之比趋于零的极限情况下变为现有的静态互信息公式和静态信道容量公式.所有这些新的理论公式和结果都是从动态信息演化方程统一推导出的.     

Mutual Information and Quantum Discord in Quantum State Discrimination with a Fixed Rate of Inconclusive Outcomes

We studied the mutual information and quantum discord that Alice and Bob share when Bob implements a discrimination with a fixed rate of inconclusive outcomes (FRIO) onto two pure non-orthogonal quantum states, generated with arbitrary a priori probabilities. FRIO discrimination interpolates between minimum error (ME) and unambiguous state discrimination (UD). ME and UD are well known discrimination protocols with several applications in quantum information theory. FRIO discrimination provides a more general framework where the discrimination process together with its applications can be studied. In this setting, we compared the performance of optimum probability of discrimination, mutual information, and quantum discord. We found that the accessible information is obtained when Bob implements the ME strategy. The most (least) efficient discrimination scheme is ME (UD), from the point of view of correlations that are lost in the initial state and remain in the final state, after Bob’s measurement.     

Information theories for time-dependent harmonic oscillator

Information theories for the general time-dependent harmonic oscillator are described on the basis of invariant operator method. We obtained entropic uncertainty relation of the system and discussed whether it is always larger than or equal to the physically allowed minimum value. Shannon information and Fisher information are derived by means of density operator that satisfies Liouville–von Neumann equation and their characteristics are investigated. Shannon information is independent of time, but Fisher information is explicitly dependent on time as the time functions of the Hamiltonian vary. We can regard that the Fisher information is a local measure since its time behavior is largely affected by local arrangements of the density, whilst the Shannon information plays the role of a global measure of the spreading of density. To promote the understanding, our theory is applied to special systems, the so-called quantum oscillator with time-dependent frequency and strongly pulsating mass system.     

Neural Estimator of Information for Time-Series Data with Dependency

Novel approaches to estimate information measures using neural networks are well-celebrated in recent years both in the information theory and machine learning communities. These neural-based estimators are shown to converge to the true values when estimating mutual information and conditional mutual information using independent samples. However, if the samples in the dataset are not independent, the consistency of these estimators requires further investigation. This is of particular interest for a more complex measure such as the directed information, which is pivotal in characterizing causality and is meaningful over time-dependent variables. The extension of the convergence proof for such cases is not trivial and demands further assumptions on the data. In this paper, we show that our neural estimator for conditional mutual information is consistent when the dataset is generated with samples of a stationary and ergodic source. In other words, we show that our information estimator using neural networks converges asymptotically to the true value with probability one. Besides universal functional approximation of neural networks, a core lemma to show the convergence is Birkhoff’s ergodic theorem. Additionally, we use the technique to estimate directed information and demonstrate the effectiveness of our approach in simulations.     

量子稀疏图码的反馈式迭代译码

量子稀疏图码的译码可以由基于错误图样的和积译码算法来实现.本文在此基础上构建了一个新的反馈式迭代译码算法.其反馈策略不仅仅重新利用了错误图样,而且还利用了稳定子上相应元素的值和信道的错误模型.由此,本方法一方面可以克服传统的量子和积译码算法中遇到的所谓对称简并错误,另一方面还能反馈更多的有用信息到译码器中,帮助其产生有效的译码结果,大大提高译码器的译码能力.另外,本算法并没有增加量子测量的复杂度,而是对测量中所能获得的信息的更充分利用.     

Scheduling to Minimize Age of Incorrect Information with Imperfect Channel State Information

In this paper, we study a slotted-time system where a base station needs to update multiple users at the same time. Due to the limited resources, only part of the users can be updated in each time slot. We consider the problem of minimizing the Age of Incorrect Information (AoII) when imperfect Channel State Information (CSI) is available. Leveraging the notion of the Markov Decision Process (MDP), we obtain the structural properties of the optimal policy. By introducing a relaxed version of the original problem, we develop the Whittle’s index policy under a simple condition. However, indexability is required to ensure the existence of Whittle’s index. To avoid indexability, we develop Indexed priority policy based on the optimal policy for the relaxed problem. Finally, numerical results are laid out to showcase the application of the derived structural properties and highlight the performance of the developed scheduling policies.     

Common Information Components Analysis

Wyner’s common information is a measure that quantifies and assesses the commonality between two random variables. Based on this, we introduce a novel two-step procedure to construct features from data, referred to as Common Information Components Analysis (CICA). The first step can be interpreted as an extraction of Wyner’s common information. The second step is a form of back-projection of the common information onto the original variables, leading to the extracted features. A free parameter γ controls the complexity of the extracted features. We establish that, in the case of Gaussian statistics, CICA precisely reduces to Canonical Correlation Analysis (CCA), where the parameter γ determines the number of CCA components that are extracted. In this sense, we establish a novel rigorous connection between information measures and CCA, and CICA is a strict generalization of the latter. It is shown that CICA has several desirable features, including a natural extension to beyond just two data sets.     

Channel Quality-Based Optimal Status Update for Information Freshness in Internet of Things

This paper investigates the status updating policy for information freshness in Internet of things (IoT) systems, where the channel quality is fed back to the sensor at the beginning of each time slot. Based on the channel quality, we aim to strike a balance between the information freshness and the update cost by minimizing the weighted sum of the age of information (AoI) and the energy consumption. The optimal status updating problem is formulated as a Markov decision process (MDP), and the structure of the optimal updating policy is investigated. We prove that, given the channel quality, the optimal policy is of a threshold type with respect to the AoI. In particular, the sensor remains idle when the AoI is smaller than the threshold, while the sensor transmits the update packet when the AoI is greater than the threshold. Moreover, the threshold is proven to be a non-increasing function of channel state. A numerical-based algorithm for efficiently computing the optimal thresholds is proposed for a special case where the channel is quantized into two states. Simulation results show that our proposed policy performs better than two baseline policies.     

Discovering Higher-Order Interactions Through Neural Information Decomposition

If regularity in data takes the form of higher-order functions among groups of variables, models which are biased towards lower-order functions may easily mistake the data for noise. To distinguish whether this is the case, one must be able to quantify the contribution of different orders of dependence to the total information. Recent work in information theory attempts to do this through measures of multivariate mutual information (MMI) and information decomposition (ID). Despite substantial theoretical progress, practical issues related to tractability and learnability of higher-order functions are still largely unaddressed. In this work, we introduce a new approach to information decomposition—termed Neural Information Decomposition (NID)—which is both theoretically grounded, and can be efficiently estimated in practice using neural networks. We show on synthetic data that NID can learn to distinguish higher-order functions from noise, while many unsupervised probability models cannot. Additionally, we demonstrate the usefulness of this framework as a tool for exploring biological and artificial neural networks.