Private set intersection cardinality (PSI-CA) and private intersection-sum with cardinality (PSI-CA-sum) are two primitives that enable data owners to learn the intersection cardinality of their data sets, with the difference that PSI-CA-sum additionally outputs the sum of the associated integer values of all the data that belongs to the intersection (i.e., intersection-sum). However, to the best of our knowledge, all existing multi-party PSI-CA (MPSI-CA) protocols are either limited by high computational cost or face security challenges under arbitrary collusion. As for multi-party PSI-CA-sum (MPSI-CA-sum), there is even no formalization for this notion at present, not to mention secure constructions for it. In this paper, we first present an efficient MPSI-CA protocol with two non-colluding parties. This protocol significantly decreases the number of parties involved in expensive interactive procedures, leading to a significant enhancement in runtime efficiency. Our numeric results demonstrate that the running time of this protocol is merely one-quarter of the time required by our proposed MPSI-CA protocol that is secure against arbitrary collusion. Therefore, in scenarios where performance is a priority, this protocol stands out as an excellent choice. Second, we successfully construct the first MPSI-CA protocol that achieves simultaneous practicality and security against arbitrary collusion. Additionally, we also conduct implementation to verify its practicality (while the previous results under arbitrary collusion only present theoretical analysis of performance, lacking real implementation). Numeric results show that by shifting the costly operations to an offline phase, the online computation can be completed in just 12.805 seconds, even in the dishonest majority setting, where 15 parties each hold a set of size 2 16 . Third, we formalize the concept of MPSI-CA-sum and present the first realization that ensures simultaneous practicality and security against arbitrary collusion. The computational complexity of this protocol is roughly twice that of our MPSI-CA protocol. Besides the main results, we introduce the concepts and efficient constructions of two novel building blocks: multi-party secret-shared shuffle and multi-party oblivious zero-sum check, which may be of independent interest.

Ring confidential transaction (RingCT) protocol is widely used in cryptocurrency to protect the privacy of both users’ identities and transaction amounts. Most recently, a new RingCT protocol (called RingCT 2.0) was proposed by leveraging cryptographic accumulators, which can achieve a constant-size output theoretically but still far from being practical due to the heavy zero-knowledge associated with the accumulator. In this article, we revisit the design of ring confidential transaction protocol and put forward a more efficient privacy-preserving payment protocol, which is built upon an extended version of one-out-of-many proof and a special multi-signature. Compared with previous works, the new protocol is not only more practical, but also does not suffer from a trusted setup. Besides, we show that the protocol satisfies the security requirements provided that the underlying cryptographic primitives are secure in the random oracle model. We implement our new payment protocol in Java, and the experimental results show that it is efficient enough to be used in practice.

Linear regression is a widely used machine learning model for applications such as personalized health-care prediction, recommendation systems, and policy making etc. Nowadays one important trend of applying this model (also others) is privacy-preserving linear regression, in which multiple parties, each possessing a part of dataset, jointly perform the learning process, while paying a specific attention to the goal of preserving privacy of their data. Consequently some works on how to achieve this goal with various properties appear in recent years.

Vertical federated learning (VFL) is a privacy-preserving machine learning framework in which the training dataset is vertically partitioned and distributed over multiple parties, i.e., for each sample each party only possesses some attributes of it. In this paper we address the problem of computing private set intersection (PSI) in VLF, in which a private set denotes the data possessed by a party satisfying some distinguishing constraint. This problem actually asks how the parties jointly compute the common IDs of their private sets, which plays a key role in many learning tasks such as Decision Tree Learning. Currently all known PSI protocols, to our knowledge, either involve expensive cryptographic operations, or are designed for the two-party scenario originally which will leak privacy-sensitive information in multi-party scenario if applied to each pair of parties gradually. In this paper we propose a new multi-party PSI protocol in VFL, which can even handle the case that some parties drop out in the running of the protocol. Our protocol achieves the security that any coalition of corrupted parties, which number is less than a threshold, cannot learn any secret information of honest parties, thus realizing the goal of preserving the privacy of the involved parties. Moreover, it only relies on light cryptographic primitives (i.e. PRGs) and thus works more efficiently compared to the known protocols, especially when the sample number of dataset gets larger and larger. Our starting point to solve the PSI problem in VFL is to reduce it to computing the AND operation of multiple bit-vectors, each held by one party, which are used to identify parties' private sets in their data. Then our main technical contribution is to present an efficient protocol for summing up these vectors, called MulSUM, and then adapt it to a desired protocol, called MulAND, to compute the AND of these vectors, which result actually identifies the intersection of private sets of all (online) parties, thus accomplishing the PSI issue.

An important and long-standing question in computational learning theory is how to learn $\textrm{AC}^0$ circuits with respect to any distribution (i.e. PAC learning). All previous results either require that the underlying distribution is uniform Linial et al. (1993) (or simple variants of the uniform distribution) or restrict the depths of circuits being learned to 1 Valiant (1984) and 2 Klivans and Servedio (2004). As for the circuits of depth 3 or more, it is currently unknown how to PAC learn them. \newline In this paper we present an algorithm to PAC learn depth-3 $\textrm{AC}^0$ circuits of bounded top fanin over $(x_1,\cdots,x_n,\overline{x}_1,\cdots,\overline{x}_n)$. Our result is that every depth-3 $\textrm{AC}^0$ circuit of top fanin $K$ can be computed by a polynomial threshold function (PTF) of degree $\widetilde{O}(K\cdot n^{\frac{1}{2}})$, which means that it can be PAC learned in time $2^{\widetilde{O}(K\cdot n^{\frac{1}{2}})}$. In particular, when $K=O(n^{\epsilon_0})$ for any $\epsilon_0<\frac{1}{2}$, the time for learning is sub-exponential. We note that instead of employing some known tools we use some specific approximation in expressing such circuits in PTFs which can thus save a factor of $\textrm{polylog}(n)$ in degrees of the PTFs.

Agnostic learning is an extremely hard task in computational learning theory. In this paper we revisit the results in [Kalai et al. SIAM J. Comput. 2008] on agnostically learning boolean functions with finite polynomial representation and those that can be approximated by the former. An example of the former is the class of all boolean low-degree polynomials. For the former, [Kalai et al. SIAM J. Comput. 2008] introduces the l_1-polynomial regression method to learn them to error opt+epsilon. We present a simple instantiation for one step in the method and accordingly give the analysis. Moreover, we show that even ignoring this step can bring a learning result of error 2opt+epsilon as well. Then we consider applying the result for learning concept classes that can be approximated by the former to learn richer specific classes. Our result is that the class of s-term DNF formulae can be agnostically learned to error opt+epsilon with respect to arbitrary distributions for any epsilon in time poly(n^d, 1/epsilon), where d=O(\sqrt{n}\cdot s\cdot \log s\log^2(1/epsilon)).

The problem of securely outsourcing computation has received widespread attention due to the development of cloud computing and mobile devices. In this paper, we first propose a secure verifiable outsourcing algorithm of single modular exponentiation based on the one-malicious model of two untrusted servers. The outsourcer could detect any failure with probability 1 if one of the servers misbehaves. We also present the other verifiable outsourcing algorithm for multiple modular exponentiations based on the same model. Compared with the state-of-the-art algorithms, the proposed algorithms improve both checkability and efficiency for the outsourcer. Finally, we utilize the proposed algorithms as two subroutines to achieve outsource-secure polynomial evaluation and ciphertext-policy attributed-based encryption (CP-ABE) scheme with verifiable outsourced encryption and decryption.

In an identity-based encryption (IBE) scheme, how to revoke users from the system is a difficult problem when their private keys are compromised. The private key generator (PKG) updates the private keys for all unrevoked users and has high computation load when a large number of users are included. We propose an IBE scheme with verifiable outsourced revocation based on the one-malicious model of two servers. In the proposed scheme, PKG delegates the key update operations to the two servers for all unrevoked users. The PKG can detect the failure with probability 1 if one of the servers misbehaves. Our scheme is proven fully secure and verifiable against chosen-plaintext attack (CPA) without random oracles. The servers cannot execute the key update operations for any revoked user even if they collude. The experiment shows the time cost for PKG in the outsourcing algorithm is much smaller than that for directly updating the private keys for all unrevoked users.