Private set union (PSU) has been an emerging topic in recent years due to its variety of applications. In particular, we are interested in deploying PSU in a cloud setting such that two players, the sender and the receiver, may outsource their sets to the cloud and update their sets. Later, the receiver can submit a union query to the cloud and learn the union of the sets without knowing the intersection. Of course, there is no need to restrict this scenario to only two players. A PSU operation that satisfies these properties is called updatable delegated PSU (UD-PSU). Despite the apparent usefulness of such operations, no related research, even on delegated PSU, has been conducted since Abadi et al. (TDSC 2017) posed the open problem of constructing a delegated PSU protocol. In this work, we address the above problem by presenting the first protocol for multiparty UD-PSU. Our starting point is Abadi et al.'s protocol (FC 2022) for multiparty updatable delegated private set intersection (a.k.a. Feather) built on a polynomial representation of the intersection of sets. The challenging hurdle for delegated PSU is to obtain a polynomial representation of the union of sets without revealing any information about the sets beyond the result. We develop a delegated PSU protocol by exploiting a rational polynomial representation. We then extend this basic protocol to support update operations, i.e., UD-PSU. Second, we improve the update efficiency of the resulting UD-PSU protocol to$\tilde{O}(n\log {p})$, which works on polynomials of degree$n$over finite fields of order$p$. Finally, we implement our protocol in C++ and perform a comprehensive evaluation varying the cardinality of the sets and the number of players. Interestingly, the experimental results demonstrate that our protocol is comparable to Feather in overall performance. In particular, our update protocol shows an 8–12× improvement relative to Feather's update.

Fully homomorphic encryption (FHE) brings a paradigm shift in cryptographic engineering by enabling us to resolve various unsolved problems. Among them, this work solves the problem to design a private database query (PDQ) protocol that supports compound queries with wildcard conditions on encrypted databases using FHE. More precisely, we consider a setting where clients outsource an encrypted database using FHE to a remote server, and later request results of compound queries including a wildcard search condition-given a set of attribute values {A1; A2; ...; An} and a search pattern W, retrieve a set of all attribute values Ai's in which the pattern W occurs. To this end, we first develop an algorithm for testing whether an encrypted string contains an encrypted pattern without revealing any information of the pattern, taking auxiliary encryptions as additional inputs. Then, using this algorithm, we design PDQ protocols on encrypted databases, which support compound queries using wildcard search conditions. Finally, we demonstrate proof-of-concept implementation results of our protocols by exploiting single-instruction-multiple-data operations and multi-threading techniques.

Private query processing is a very attractive problem in the fields of both cryptography and databases. In this work, we restrict our attention to the efficiency aspect of the problem, particularly for basic queries with conditions on various combinations of equality. Without loss of generality, these conditions can be regarded as a Boolean function, and this Boolean function can then be evaluated at ciphertexts produced by a fully homomorphic encryption (FHE) scheme without decryption. From the efficiency perspective, the remaining concern is to efficiently test the equality function without severely downgrading the performance of FHE-based querying solutions. To this end, we first analyze the multiplicative depth required for an equality test algorithm with respect to the plaintext space inhabited by general FHE schemes. The primary reason for this approach is that given an equality test algorithm, its efficiency is measured in terms of the multiplicative depth required to construct its arithmetic circuit expression. Indeed, the implemented equality test algorithm dominates the entire performance of FHE-based query solutions, apart from the performance of the underlying FHE scheme. Then, we measure the multiplicative depth considering an FHE scheme that takes an extension field as its plaintext space and that supports the depth-free evaluation of Frobenius maps. According to our analysis, when the plaintext space of an FHE scheme is a field of characteristic 2, the equality test algorithm for `-bit messages requires the lowest multiplicative depth dlog`e. Furthermore, we design a set of private query protocols for conjunctive, disjunctive, and threshold queries based on the equality test algorithm. Similarly, applying the equality test algorithm over F2ℓ, our querying protocols require the minimum depths. More specifically, a multiplicative depth of [log ℓ] + [log (1 + ρ)] is required for conjunctive and disjunctive queries, and a depth of [log ℓ] + 2[log (1+ρ )] is required for threshold conjunctive queries, when their query conditions have p attributes to be compared. Finally, we provide a communication-efficient version of our solutions, though with additional computational costs, when an upper bound δ (0 ≤ δ ≤ 1) on the selectivity of a database is given. Consequently, we reduce the communication cost from n to approximately [δn] ciphertexts with [log n] additional depth when the database consists of n tuples.

Private query processing on encrypted databases allows users to obtain data from encrypted databases in such a way that the users’ sensitive data will be protected from exposure. Given an encrypted database, users typically submit queries similar to the following examples: 1) How many employees in an organization make over U.S. $100000? 2) What is the average age of factory workers suffering from leukemia? Answering the questions requires one to search and then compute over the relevant encrypted data sets in sequence. In this paper, we are interested in efficiently processing queries that require both operations to be performed on fully encrypted databases. One immediate solution is to use several special-purpose encryption schemes simultaneously; however, this approach is associated with a high computational cost for maintaining multiple encryption contexts. Another solution is to use a privacy homomorphic scheme. However, no secure solutions have been developed that satisfy the efficiency requirements. In this paper, we construct a unified framework to efficiently and privately process queries with search and compute operations. For this purpose, the first part of our work involves devising several underlying circuits as primitives for queries on encrypted data. Second, we apply two optimization techniques to improve the efficiency of these circuit primitives. One technique involves exploiting single-instruction-multiple-data (SIMD) techniques to accelerate the basic circuit operations. Unlike general SIMD approaches, our SIMD implementation can be applied even to a single basic operation. The other technique is to use a large integer ring (e.g.,$\mathbb {Z}_{2^{t}}$) as a message space rather than a binary field. Even for an integer of$k$bits with$k>t$, addition can be performed using degree 1 circuits with lazy carry operations. Finally, we present various experiments performed by varying the considered parameters, such as the query type and the number of tuples.

In this paper, we revisit the private over-threshold data aggregation problem. We formally define the problem's security requirements as both data and user privacy goals. To achieve both goals, and to strike a balance between efficiency and functionality, we devise an efficient cryptographic construction and its proxy-based variant. Both schemes are provably secure in the semi-honest model. Our key idea for the constructions and their malicious variants is to compose two encryption functions tightly coupled in a way that the two functions are commutative and one public-key encryption has an additive homomorphism. We call that double encryption. We analyze the computational and communication complexities of our construction, and show that it is much more efficient than the existing protocols in the literature. Specifically, our protocol has linear complexity in computation and communication with respect to the number of users. Its round complexity is also linear in the number of users. Finally, we show that our basic protocol is efficiently transformed into a stronger protocol secure in the presence of malicious adversaries, and provide the resulting protocol's performance and security analysis.

Web search is increasingly becoming an essential activity as it is frequently the most effective and convenient way of finding information.However, it can be a threat for the privacy of users because their queries may reveal their sensitive information.Private web search (PWS) solutions allow users to find information in the Internet while preserving their privacy.In particular, cryptography-based PWS (CB-PWS) systems provide strong privacy guarantees.This paper introduces a constant-round CB-PWS protocol which remains computationally efficient, compared to known CB-PWS systems.Our construction is comparable to similar solutions regarding users' privacy.

As users begin to demand applications with superior user experience and high service quality, asymmetric multicore processors are increasingly adopted in embedded systems due to their architectural benefits in improved performance and power savings. While fair-share scheduling is a crucial kernel service for such applications, it is still in an early stage when it comes to performance-asymmetric multicore architecture. In this paper, we propose a new fair-share scheduler by adopting the notion of scaled CPU time which reflects performance asymmetry between different types of cores. Our scheduler can work with kernel's dynamic resource control mechanisms since it makes use of a varying performance ratio between cores and thus captures dynamic performance asymmetry such as a core's changing operating frequency. We develop our approach on top of ARM's big. LITTLE architecture which runs Linaro's scheduling framework. Since Linaro's relies on the completely fair scheduler(CFS) of the Linux kernel and CFS is virtual runtime based, we revise the notion of virtual runtime using the scaled CPU time and incorporate it into the proposed approach. As a result, our approach achieves fair-share scheduling by simply balancing tasks' virtual runtimes. To demonstrate its effectiveness, we have implemented the proposed scheduler and performed a series of experiments on ARM's Versatile Express TC2 board. We ran the SPEC CPU2006 and PARSEC benchmarks for three minutes and measured tasks' virtual runtimes. We observed that the maximum virtual runtime difference was only 0.69 seconds in our approach while the original CFS yielded the maximum difference of 8.35 seconds.

Fast allocation of large blocks of physically contiguous memory plays a crucial role to boost the performance of multimedia applications in modern memory-constrained portable devices, such as smartphones, tablets, etc. Existing systems have addressed this issue by provisioning a large statically reserved memory area (SRA) in which only dedicated applications can allocate pages. However, this in turn degrades the performance of applications that are prohibited to utilize the SRA due to the reduced available memory pool. To overcome this drawback while maintaining the benefits of the SRA, we propose a new memory management scheme that uses a special memory region, called page-cache-preferred area (PCPA), in concert with a quick memory reclaiming algorithm. The key of the proposed scheme is to enhance the memory utilization efficiency by enabling to allocate page-cached pages of all applications in the PCPA until predetermined applications require to allocate big chunks of contiguous memory. At this point, clean page-cached pages in the PCPA are rapidly evicted without write-back to a secondary storage. Compared to the SRA scheme, experimental results show that the average launch time of real-world applications and the execution time of I/O-intensive benchmarks are reduced by 9.2% and 24.7%, respectively.

Multi-core CPU/GPU heterogeneous platforms became popular in embedded systems. A full system simulator is typically used to observe the internal system behavior by running complete software stacks without modification on simulation models of CPUs and other devices in the system. However, there are few known full system simulators for CPU/GPU heterogeneous platforms and existent GPU simulators are prohibitively slow for running application software. In this paper, we propose a hardware-in-the-loop simulation technique that integrates GPU hardware into a full system simulator. A novel interfacing mechanism between CPU simulator and the development board, where GPU hardware is integrated, is devised. In the experiments, we took Exynos 4412 as a case study, where gem5 simulator is used to simulate mainly a quad-core ARM CPU in the platform and an Exynos development board is used to run the Mali GPU hardware. We could successfully run Android apps on the proposed hardware-in-the-loop simulation framework with up to 1.5 M cycles per second performance.

ARM's big.LITTLE architecture introduces the opportunity to optimize power consumption by selecting the core type most suitable for a level of processing demand. To take advantage of this new axis of optimization, we introduce processor utilization into the Linux kernel's load balancing algorithm. Our method improves the Linux kernel's ability to schedule tasks in an energy efficient manner without making it directly aware of the available core types. Experimental results show an energy consumption improvement over the standard Linux scheduler up to 11.35% with almost no reduction in performance.

Encounter-based social networks and encounter-based systems link users who share a location at the same time, as opposed to the traditional social network paradigm of linking users who have an offline friendship. This new approach presents challenges that are fundamentally different from those tackled by previous social network designs. In this paper, we explore the functional and security requirements for these new systems, such as availability, security, and privacy, and present several design options for building secure encounter-based social networks. To highlight these challenges, we examine one recently proposed encounter-based social network design and compare it to a set of idealized security and functionality requirements. We show that it is vulnerable to several attacks, including impersonation, collusion, and privacy breaching, even though it was designed specifically for security. Mindful of the possible pitfalls, we construct a flexible framework for secure encounter-based social networks, which can be used to construct networks that offer different security, privacy, and availability guarantees. We describe two example constructions derived from this framework, and consider each in terms of the ideal requirements. Some of our new designs fulfill more requirements in terms of system security, reliability, and privacy than previous work. We also evaluate real-world performance of one of our designs by implementing a proof-of-concept iPhone application called MeetUp. Experiments highlight the potential of our system and hint at the deployability of our designs on a large scale.

While Linux is the most favored operating system for an open source-based cloud data center, it falls short of expectations when it comes to fair share multicore scheduling. The primary task scheduler of the mainline Linux kernel, CFS, cannot provide a desired level of fairness in a multicore system. CFS uses a weight-based load balancing mechanism to evenly distribute task weights among all cores. Contrary to expectations, this mechanism cannot guarantee fair share scheduling since balancing loads among cores has nothing to do with bounding differences in the virtual runtimes of tasks. To make matters worse, CFS allows a persistent load imbalance among cores. This paper presents a virtual runtime-based task migration algorithm which directly bounds the maximum virtual runtime difference among tasks. For a given pair of cores, our algorithm periodically partitions run able tasks into two groups depending on their virtual runtimes and assigns each group to a dedicated core. In doing so, it bounds the load difference between two cores by the largest weight in the task set and makes the core with larger virtual runtimes receive a larger load and thus run more slowly. It bounds the virtual runtime difference of any pair of tasks running on these cores by a constant. We have implemented the algorithm into the Linux kernel 2.6.38.8. Experimental results show that the maximal virtual runtime difference is 50.53 time units while incurring only 0.14% more run-time overhead than CFS.