We introduce a secure data-independent priority queue which supports polylogarithmic-time insertion operations and constant-time deletions and read-front (aka peek) operations as opposed to the originally introduced queue by Toft (PODC '11). Moreover, we minimize the number of comparisons required to perform different operations on Toft's priority queue. Data-independent data structures—first identified explicitly by Toft, and further elaborated by Mitchell and Zimmerman (STACS '14)—serve the purpose of computing on encrypted data without executing branching code which can be used to avoid prohibitively expensive operations in secure computation applications. Focusing on the costly sorting operations, we show significant asymptotic improvements over prior privacy preserving dark pool applications. Dark pools are securities-trading venues which attain ad-hoc order privacy, by matching orders outside of publicly visible exchanges via the so-called dark pool operators. In this paper, we describe an efficient and secure dark pool (implementing a full continuous double auction) based on our new priority queue. Our construction's security guarantees are cryptographic based on secure multiparty computation (MPC), and do not require that the dark pool operators are trusted. Our construction improves upon the asymptotic efficiency attained by previous efforts. Existing cryptographic dark pools process new orders in time which grows linearly in the size of the standing order book; ours does so in polylogarithmic time. We describe a concrete implementation of our MPC protocol with malicious security in the honest majority setting. We also report benchmarks of our implementation and compare them to prior works. Our protocol reduces the total running time by several orders of magnitude over prior secure dark pool solutions.

We explore a new security model for secure computation on large datasets. We assume that two servers have been employed to compute on private data that was collected from many users, and, in order to improve the efficiency of their computation, we establish a new tradeoff with privacy. Specifically, instead of claiming that the servers learn nothing about the input values, we claim that what they do learn from the computation preserves the differential privacy of the input. Leveraging this relaxation of the security model allows us to build a protocol that leaks some information in the form of access patterns to memory, while also providing a formal bound on what is learned from the leakage. We then demonstrate that this leakage is useful in a broad class of computations. We show that computations such as histograms, PageRank and matrix factorization, which can be performed in common graph-parallel frameworks such as MapReduce or Pregel, benefit from our relaxation. We implement a protocol for securely executing graph-parallel computations, and evaluate the performance on the three examples just mentioned above. We demonstrate marked improvement over prior implementations for these computations.

Homogeneous wireless sensor networks (HWSNs) are a class of WSNs in which nodes have identical hardware configurations. A HWSN inherits the same constraints from WSNs such as limited processing capacity and resources. However, the unique characteristic of HWSNs gets more attention for recent security applications. The environment of these applications mandates lightweight security provisions, especially a key management protocol that endures security threats such as node capture attack. On the other hand, the limited computation and communication capabilities of sensor nodes make it hard to deal with such security threats. Thus, in this paper, we introduce a novel clustering paradigm to be used in a key pre-distribution key management scheme designed for HWSNs. Then, we develop a cluster-based key pre-distribution based on this paradigm. Our developed scheme improves the security dramatically by partitioning sensor nodes to the disjointed clusters and letting clusters to be inter-connected via randomly selected nodes as consular nodes from all the clusters to form a universal cluster. As opposed to the adopted schemes, we provide a comprehensive analysis for both sensor node connectivity, and resiliency against node capture attack, and also computational results are presented.

Image encryption is somehow different from text encryption due to some inherent features of image such as bulk data capacity and high correlation among pixels, which are generally difficult to handle by traditional methods. The exceptionally desirable properties of the chaotic maps such as sensitivity to initial conditions and random-like behavior have attracted the attention of cryptographers to develop new encryption algorithms. This paper proposes a new symmetric image cipher based on the widely used confusion-diffusion architecture which utilizes the chaotic 2D Standard map and 1D Logistic map. It is specifically designed for the color images, which are 3D arrays of data streams. We prefer chaotic Standard map to Baker and Cat maps since the key space of the chaotic Standard map is large enough as compared to the Baker and Cat maps, which makes the brute-force attack infeasible. The initial conditions and system parameters of the chaotic maps constitute the secret key of the algorithm. To further enhance the security, the control parameters used in the confusion stage and the keystream employed for diffusion stage are distinct in different rounds and related to the plain-image. These control parameters are generated by a Tent map. For getting higher security and higher complexity, the current scheme employs two kinds of diffusion processes namely the horizontal and vertical diffusions which are completed by mixing the properties of horizontally and vertically adjacent pixels using a Logistic map, respectively. The results of several experiments, including the most important ones like key space analysis, key sensitivity test, statistical analysis, and visual test by histograms of encrypted images, the correlation coefficients of adjacent pixels, and differential analysis, demonstrate the satisfactory security and efficiency of the proposed image encryption scheme for real-time image encryption and transmission.