Private Function Encryption (PFE) enables two parties, one holding a private input$x$and the other in possession of a private function$f$, to compute$f(x)$in such that each party learns nothing substantial beyond$f(x)$. PFE is typically achieved by evaluating Yao's two-party computation protocol over a universal circuit that encodes the private function into a private input. Thus, the efficiency of the PFE protocol highly relies on the size of the underlying universal circuit. A universal circuit (UC) is a general-purpose circuit that can simulate arbitrary circuits (up to a certain size$n$). In 1976, Valiant provided a recursive construction of universal circuits and gave a theoretical construction of UC of asymptotic (multiplicative) size$4.75 n\log n$respectively, which matches the asymptotic lower bound$\Omega (n\log n)$up to some constant factor. More recently, (Kiss et al. 2016) validated the practicality of universal circuits in real-world privacy-preserving applications. Subsequent work by (Günther et al. 2017) and (Alhassan et al. 2020) enhanced UCs’ practicality through hybrid constructions with various optimizations. This work focuses on optimizing the size efficiency of universal circuits. Our contributions are three-fold:•Optimized component:We first optimize the underlying component of Valiant's universal circuits to achieve an asymptotic size of$4.5 n\log n$4.5nlogn.•More efficient framework:We propose an improved framework for constructing universal circuits, under which we give a UC construction of asymptotic size$3n\log n$3nlogn. This improves the previous state-of-the-art construction by 33%, which corresponds to the same fraction of reduction in the communication cost of UC-based PFE protocols.•Tigher lower bound:To complement our constructive results, we show that the (multiplicative) size of the universal circuits is lower bounded by$2n\log n$2nlogn.We implement the 2-way universal circuits and evaluate their performance against other implementations, confirming our theoretical analysis.

Abstract The Learning Parity with Noise (LPN) problem represents the average-case analogue of the NP-Complete problem “decoding linear codes”, and it has been extensively studied in learning theory, coding theory and cryptography with applications to quantum-resistant cryptographic schemes. However, LPN also suffers from large public key size which is the common drawback that hinders code-based cryptography from being practical. In this paper, we study a sparse variant of LPN whose public matrix consists of sparse vectors instead of following uniform distribution. We show a win–win argument that at least one of the following assumption is true: (i) either the hardness of sparse LPN is implied by that of the standard LPN under the same noise rate; (ii) or there exists new black-box constructions of public-key encryption schemes and oblivious transfer protocols from standard LPN. Since the second assumption relies on the infeasible noise regimes for LPN-based public-key cryptography, we believe that the first assumption is more likely to hold, i.e. sparse LPN is as hard as standard LPN. Finally, we give a (heuristic) method to further compress the sparse public matrix by evaluating pseudorandom functions with keys made public, whose security again resorts to the aforementioned win–win technique.

Today's content delivery is characterized by key trends such as converged media delivery over HTTP, increasing volumes of multimedia content delivered over IP, and elevated user expectations on quality-of-experience. In this respect, server provisioning is a critical phase of CDN management, which affects both incumbent and entrant CDN operators as well as internet service providers. However, existing tools and approaches to solve server placement problems have serious shortcomings: they offer only coarse tuning knobs and limit servers to a set of candidate sites givena priori. Our conversations with CDN operators reveal that a new provisioning mechanism is necessary to take advantage of emerging opportunities such as faster speed to roll out new locations and more access networks. In this paper, we present the design of DISC, a decision support system to help CDN operators systematically investigate different design tradeoffs and evaluate what-if scenarios. The key enabler underlying DISC is a network coordinate-based data analysis workflow that can flexibly embed different cost, performance, and workload characteristics without sacrificing the fidelity. We describe practical use cases and experiences in applying DISC to a large country-wide deployment. The results show that DISC significantly reduces average latency, deployment cost, and interdomain traffic.

We present$\sf {Tentacle}$, a decision support framework to provision edge servers for online services providers (OSPs).$\sf {Tentacle}$takes advantage of the increasingly flexible edge server placement, which is enabled by new technologies such as edge computing platforms, cloudlets and network function virtualization, to optimize the overall performance and cost of edge infrastructures. The key difference between$\sf {Tentacle}$and traditional server placement approaches lies on that$\sf {Tentacle}$can discover proper unforeseen edge locations which significantly improve the efficiency and reduce the cost of edge provisioning. We show how$\sf {Tentacle}$effectively identifies promising edge locations which are close to a collection of users merely with inaccurate network distance estimation methods, e.g., geographic coordinate (GC) and network coordinate systems (NC). We also show how$\sf {Tentacle}$comprehensively considers various pragmatic concerns in edge provisioning, such as traffic limits by law or ISP policy, edge site deployment and resource usage cost, over-provisioning for fault tolerance, etc., with a simple optimization model. We simulate$\sf {Tentacle}$using real network data at global and county-wide scales. Measurement-driven simulations show that with a given cost budget$\sf {Tentacle}$can improve user performance by around 10-45 percent at global scale networks and 15-35 percent at a country-wide scale network.