Privacy in Non-private Environments

We study private computations in information-theoretical settings on networks that are not 2-connected. Non-2-connected networks are “non-private” in the sense that most functions cannot privately be computed on them. We relax the notion of privacy by introducing lossy private protocols, which generalize private protocols. We measure the information each player gains during the computation. Good protocols should minimize the amount of information they lose to the players. Throughout this work, privacy always means 1-privacy, i.e. players are not allowed to share their knowledge. Furthermore, the players are honest but curious, thus they never deviate from the given protocol.     

Unbounded-error quantum query complexity

This work studies the quantum query complexity of Boolean functions in an unbounded-error scenario where it is only required that the query algorithm succeeds with a probability strictly greater than 1/2. We show that, just as in the communication complexity model, the unbounded-error quantum query complexity is exactly half of its classical counterpart for any (partial or total) Boolean function. Moreover, connecting the query and communication complexity results, we show that the “black-box” approach to convert quantum query algorithms into communication protocols by Buhrman-Cleve—Wigderson [STOC’98] is optimal even in the unbounded-error setting.We also study a related setting, called the weakly unbounded-error setting, where the cost of a query algorithm is given by q+log(1/2(p−1/2)), where q is the number of queries made and p>1/2 is the success probability of the algorithm. In contrast to the case of communication complexity, we show a tight multiplicative Θ(logn) separation between quantum and classical query complexity in this setting for a partial Boolean function. The asymptotic equivalence between them is also shown for some well-studied total Boolean functions.     

Quantum communication and complexity

In the setting of communication complexity, two distributed parties want to compute a function depending on both their inputs, using as little communication as possible. The required communication can sometimes be significantly lowered if we allow the parties the use of quantum communication. We survey the main results of the young area of quantum communication complexity: its relation to teleportation and dense coding, the main examples of fast quantum communication protocols, lower bounds, and some applications.     

Bounds on tradeoffs between randomness and communication complexity

The power of randomness in improving the efficiency (or even possibility) of computations has been demonstrated in numerous contexts. A fundamental question ishow much randomness is required for these improvements, or how does the improvement grow as a function of the amount of randomness allowed. This quantitative question, restricted to the context of communication complexity, is the focus of our paper.We prove general lower bounds on the amount of randomness used in randomized protocols for computing a functionf, the input of which is split between two parties. The bounds depend on the number of bits communicated and the deterministic communication complexity off. Four models for communication complexity are considered: the random input of the parties may be public or private, and the communication may be one-way or two-way. (Unbounded advantage is allowed.)The bounds are shown to be tight; i.e., we demonstrate functions and protocols for these functions which meet the above bounds up to a constant factor. We do this for all the models, for all values of the deterministic communication complexity, and for all possible quantities of bits communicated.     

On private computation in incomplete networks

Suppose that some parties are connected by an incomplete network of reliable and private channels. The parties cooperate to execute some protocol. However, the parties are curious—after the protocol terminates each party tries to learn information from the communication it heard. We say that a function can be computed privately in a network if there is a protocol in which each processor learns only the information implied by its input and the output of the function (in the information theoretic sense). The question we address in this paper is what functions can be privately computed in a given incomplete network. Every function can be privately computed in two-connected networks with at least three parties. Thus, the question is interesting only for non two-connected networks. Generalizing results of (Bläser et al. in J. Cryptol, 19(3): 341–357, 2006), we characterize the functions that can be computed privately in simple networks—networks with one separating vertex and no leaves. We then deal with private computations in arbitrary non two-connected networks: we reduce this question to private computations of related functions on trees, and give some sufficient conditions and necessary conditions on the functions that can be privately computed on trees.     

Communication Protocols for Secure Distributed Computation of Binary Functions

A common task in parallel processing is the distributed computation of a function by a number of processors, each of which possesses partial information relevant to the value of that function. In this paper we develop communication protocols which allow for such computation to take place while maintaining the value of the function secret to an eavesdropper. Of interest is the communication complexity of such protocols. We begin by considering two processors and two channels, one secret and one public, and present a protocol which minimizes the number of bits exchanged over the secret channel, while maintaining -uncertainty about the value of the function for the eavesdropper. We show that all binary functions can be kept -secret using a constant number of bits independent of the size of their domain. We then generalize our results to N processors communicating over a network of arbitrary topology.     

LR-FEAD: leakage-tolerating and attribute-hiding functional encryption mechanism with delegation in affine subspaces

In large-scale networks, such as cloud computing and Internet of Things, functional encryption mechanism provides a flexible and powerful cryptographic primitive in constructing the secure transmission and communication protocols. However, as the side-channel attacks in open environments, the attacker can gain partial sensitive information from the pre-defined system by virtue of the time, power analysis, cold-boot attacks, etc. In this work, we design a leakage-resilient functional encryption scheme, which tolerates amount of bounded master-key leakage and user private-key leakage. In our scheme, encryption policies are specified as point vectors and decryption roles are defined as affine subspaces. Role delegation is implemented by specifying the affine transformation over subspaces. Our scheme achieves payload hiding and attribute hiding in the sense that the attacker is able to specify any efficiently computable leakage functions and learns the function outputs taking the master/private keys as inputs. Also, our scheme can tolerate the continual leakage for master key and private key, since we can periodically update the master key and the private key to generate a new and re-randomized key with the same distribution to the previous keys. We construct the scheme in composite-order bilinear groups and prove the security with dual system encryption methodology. We also analyze and discuss the performance of allowable leakage bound, leakage ratio and possible leakage probability. Our scheme has flexible applications in secure data communication and authorization delegation in open cloud computing systems.     

An efficient and secure authentication protocol for RFID systems

The use of radio frequency identification (RFID) tags may cause privacy violation of users carrying an RFID tag. Due to the unique identification number of the RFID tag, the possible privacy threats are information leakage of a tag, traceability of the consumer, denial of service attack, replay attack and impersonation of a tag, etc. There are a number of challenges in providing privacy and security in the RFID tag due to the limited computation, storage and communication ability of low-cost RFID tags. Many research works have already been conducted using hash functions and pseudorandom numbers. As the same random number can recur many times, the adversary can use the response derived from the same random number for replay attack and it can cause a break in location privacy. This paper proposes an RFID authentication protocol using a static identifier, a monotonically increasing timestamp, a tag side random number and a hash function to protect the RFID system from adversary attacks. The proposed protocol also indicates that it requires less storage and computation than previous existing RFID authentication protocols but offers a larger range of security protection. A simulation is also conducted to verify some of the privacy and security properties of the proposed protocol.     

Towards practical private processing of database queries over public data

Privacy is a major concern when users query public online data services. The privacy of millions of people has been jeopardized in numerous user data leakage incidents in many popular online applications. To address the critical problem of personal data leakage through queries, we enable private querying on public data services so that the contents of user queries and any user data are hidden and therefore not revealed to the online service providers. We propose two protocols for private processing of database queries, namely BHE and HHE. The two protocols provide strong query privacy by using Paillier’s homomorphic encryption, and support common database queries such as range and join queries by relying on the bucketization of public data. In contrast to traditional Private Information Retrieval proposals, BHE and HHE only incur one round of client server communication for processing a single query. BHE is a basic private query processing protocol that provides complete query privacy but still incurs expensive computation and communication costs. Built upon BHE, HHE is a hybrid protocol that applies ciphertext computation and communication on a subset of the data, such that this subset not only covers the actual requested data but also resembles some frequent query patterns of common users, thus achieving practical query performance while ensuring adequate privacy levels. By using frequent query patterns and data specific privacy protection, HHE is not vulnerable to the traditional attacks on k-Anonymity that exploit data similarity and skewness. Moreover, HHE consistently protects user query privacy for a sequence of queries in a single query session.     

Fault tolerant deterministic quantum communications using GHZ states over collective-noise channels

This study proposes two new coding functions for a GHZ state and a GHZ-like state, respectively. Based on these coding functions, two fault tolerant deterministic quantum communication (DQC) protocols are proposed. Each of the new DQC’s is robust under one kind of collective noises: collective-dephasing noise and collective-rotation noise, respectively. The sender can use the proposed coding functions to encode his/her message, and the receiver can perform the Bell measurement to obtain the sender’s message. In comparison to the existing fault tolerant DQC protocols over collective-noise channels, the proposed protocols provide the best qubit efficiency. Moreover, the proposed protocols are also free from the ordinary eavesdropping and the information leakage.     

An analytical model for end-to-end communication channel over PLCN based on QBDs

The performance analysis of packet loss in end-to-end communication channel is the basis of adaptive end-to-end protocol design. However, existing analytical models of packet loss cannot provide quantitative information of lossy channel systems. In this paper, an analysis on balance state of end-to-end communication channel over probabilistic lossy communication networks (PLCN) is performed firstly. We then discuss the process of modeling end-to-end communication channel over PLCN using Quasi Birth–Death models (QBDs) in detail. Finally, some characteristics of end-to-end communication channel, such as the stability of channel and the performance of channel packet loss, are analyzed. The experimental results show that the proposed model can analyze quantitatively the stability of end-to-end communication channel and the packet loss probability during time interval [0,t]. The results in the work are helpful for designing adaptive end-to-end communication protocols.     

Function-algebraic characterizations of log and polylog parallel time

The main results of this paper are recursion-theoretic characterizations of two parallel complexity classes: the functions computable by uniform bounded fan-in circuit families of log and polylog depth (or equivalently, the functions bitwise computable by alternating Turing machines in log and polylog time). The present characterizations avoid the complex base functions, function constructors, anda priori size or depth bounds typical of previous work on these classes. This simplicity is achieved by extending the tiered recursion techniques of Leivant and Bellantoni & Cook.     

Efficient protocols for heavy hitter identification with local differential privacy

Local differential privacy (LDP), which is a technique that employs unbiased statistical estimations instead of real data, is usually adopted in data collection, as it can protect every user’s privacy and prevent the leakage of sensitive information. The segment pairs method (SPM), multiple-channel method (MCM) and prefix extending method (PEM) are three known LDP protocols for heavy hitter identification as well as the frequency oracle (FO) problem with large domains. However, the low scalability of these three LDP algorithms often limits their application. Specifically, communication and computation strongly affect their efficiency. Moreover, excessive grouping or sharing of privacy budgets makes the results inaccurate. To address the above-mentioned problems, this study proposes independent channel (IC) and mixed independent channel (MIC), which are efficient LDP protocols for FO with a large domains. We design a flexible method for splitting a large domain to reduce the number of sub-domains. Further, we employ the false positive rate with interaction to obtain an accurate estimation. Numerical experiments demonstrate that IC outperforms all the existing solutions under the same privacy guarantee while MIC performs well under a small privacy budget with the lowest communication cost.     

一种面向车联网通信的条件隐私保护认证协议

车联网可有效提高交通的效率和安全性,但通信过程中存在的隐私泄露问题严重阻碍了其应用落地。提出一种面向车联网V2X通信的条件隐私保护认证协议。针对现有协议大多仅支持车辆认证的局限性,基于用户身份和车辆身份信息生成车与用户绑定的生物密钥,使协议支持单车多用户或单用户多车认证。在保护用户和车辆身份的条件下完成对消息发送方的身份认证,并在特定情况下追溯车辆和用户的真实身份,从而实现对车辆和用户的条件隐私保护。同时,在协议中添加批量验证功能以提高验证效率。形式化的安全性分析和性能评估结果表明,该协议是安全且高效的。     

Privacy in geo-social networks: proximity notification with untrusted service providers and curious buddies

A major feature of the emerging geo-social networks is the ability to notify a user when any of his friends (also called buddies) happens to be geographically in proximity. This proximity service is usually offered by the network itself or by a third party service provider (SP) using location data acquired from the users. This paper provides a rigorous theoretical and experimental analysis of the existing solutions for the location privacy problem in proximity services. This is a serious problem for users who do not trust the SP to handle their location data and would only like to release their location information in a generalized form to participating buddies. The paper presents two new protocols providing complete privacy with respect to the SP and controllable privacy with respect to the buddies. The analytical and experimental analysis of the protocols takes into account privacy, service precision, and computation and communication costs, showing the superiority of the new protocols compared to those appeared in the literature to date. The proposed protocols have also been tested in a full system implementation of the proximity service.     

半可信云服务器辅助的高效隐私交集计算协议

隐私集合交集（private set intersection,PSI）是隐私计算中的热点,其允许参与两方在不泄露任何额外信息的要求下计算交集.现有的隐私集合交集计算方案对参与双方的计算能力要求高,且计算能力差的参与方无法在保证集合数据隐私的前提下将计算安全外包给云服务器.设计了一种新的不经意两方分布式伪随机函数,允许半可信的云服务器参与相等性测试,又不泄露参与方任何集合信息.基于该不经意伪随机函数构建了半可信云服务器辅助的隐私集合交集计算协议,将主要计算量外包给云服务器.在半诚实模型下证明了协议的安全性.同时,该协议可保密地计算隐私集合交集的基数.通过与现有协议分析与实验性能比较,该协议效率高,计算复杂度与通信复杂度均与集合大小呈线性关系,适用于客户端设备受限的应用场景.     

Computational complexity of real functions

Recursive analysis, the theory of computation of functions on real numbers, has been studied from various aspects. We investigate the computational complexity of real functions using the methods of recursive function theory. Partial recursive real functions are defined and their domains are characterized as the recursively open sets. We define the time complexity of recursive real continuous functions and show that the time complexity and the modulus of uniform continuity of a function are closely related. We study the complexity of the roots and the differentiability of polynomial time computable real functions. In particular, a polynomial time computable real function may have a root of arbitrarily high complexity and may be nowhere differentiable. The concepts of the space complexity and nondeterministic computation are used to study the complexity of the integrals and the maximum values of real functions. These problems are shown to be related to the “P=?NP” and the “P=?PSPACE” questions.     

Authenticated semiquantum dialogue with secure delegated quantum computation over a collective noise channel

Semiquantum communication permits a communication party with only limited quantum ability (i.e., “classical” ability) to communicate securely with a powerful quantum counterpart and will obtain a significant advantage in practice when the completely quantum world has not been built up. At present, various semiquantum schemes for key distribution, secret sharing and secure communication have been proposed. In a quantum dialogue (QD) scenario, two communicants mutually transmit their respective secret messages and may have equal power (such as two classical parties). Based on delegated quantum computation model, this work extends the original semiquantum model to the authenticated semiquantum dialogue (ASQD) protocols, where two “classical” participants can mutually transmit secret messages without any information leakage and quantum operations are securely delegated to a quantum server. To make the proposed ASQD protocols more practical, we assume that the quantum channel is a collective noise channel and the quantum server is untrusted. The security analysis shows that the proposed protocols are robust even when the delegated quantum server is a powerful adversary.