We define the following problem termed n × 1-out-of-n oblivious transfer (n × 1-out-of-n OT): in a system with one server and n clients, how to securely and efficiently assign n secrets to n clients by the server, with each client getting a unique secret from the server, and the server and clients remain unknown of how the secrets are distributed? This is a novel problem that is fundamentally different than 1-out-of-n OT repeated n times, and is different than k-out-of-n OT as well. Nevertheless, the proposed OT has many practical applications such as privacy-preserving data aggregation in smart grids. It can also be employed to design crypto protocols for anonymous communications and group signatures. In this paper, we propose the first algorithm to efficiently and effectively implement the n × 1-out-of-n OT. We construct hidden permutation circuits to obliviously assign n secrets to n clients by the server within O(lg(n)) time. A rigorous theoretical analysis is also carried out to investigate the security strength and performance of the protocol.

Matrix inverse computation is one of the most fundamental mathematical problems in large-scale data analytics and computing. It is often too expensive to be solved in resource-constrained devices such as sensors. Outsourcing the computation task to a cloud server or a fog server is a potential approach as the server is able to perform large-scale scientific computations on behalf of resource-constrained users with special software. However, outsourcing brings in new security concerns and challenges such as data privacy violations and result invalidation. In this paper, we propose a secure and verifiable outsourcing scheme to compute the matrix inverse in a server. In our scheme, the client generates two secret key sets based on two chaotic systems, which are utilized to create two sparse matrices whose permuted versions are used for matrix encryption and decryption to protect input and output privacy. The server computes the inverse over the ciphertext matrix and returns the result to the client who can verify the validity of the inverse. We analyze the proposed scheme in terms of correctness, security, verifiability, and attack resistance, and compare its performance (computation, storage, and communication overheads) with those of the state-of-the-art. Our theoretical results and comparison study demonstrate that the proposed scheme provides a secure and efficient outsourcing mechanism for matrix inverse computation.

We describe a practical and provably good algorithm for approximating center points in any number of dimensions. Here c is a center point of a point set P in ℝd if every closed halfspace containing c contains at least |P|/(d+1) points of P. Our algorithm has a small constant factor and is the first approximate center point algorithm whose complexity is subexponential in d. Moreover, it can be optimally parallelized to require O(log2 d loglog n) time. Our algorithm has been used in mesh partitioning methods, and has the potential to improve results in practice for constructing weak ε-nets and other geometric algorithms. We derive a variant of our algorithm with a time bound fully polynomial in d, and show how to combine our approach with previous techniques to compute high quality center points more quickly.

Let K be any field, and let F: K/sup n/ to K/sup n/ be a bijection with the property that both F and F/sup -1/ are computable using only arithmetic operations from K. Motivated by cryptographic considerations, the authors concern themselves with the relationship between the arithmetic complexity of F and the arithmetic complexity of F/sup -1/. They give strong relations between the complexity of F and F/sup -1/ when F is an automorphism in the sense of algebraic geometry (i.e. a formal bijection defined by n polynomials in n variables with a formal inverse of the same form). These constitute all such bijections in the case in which K is infinite. The authors show that at polynomially bounded degree, if an automorphism F has a polynomial-size arithmetic circuit, then F/sup -1/ has a polynomial-size arithmetic circuit. Furthermore, this result is uniform in the sense that there is an efficient algorithm for finding such a circuit for F/sup -1/, given such a circuit for F. This algorithm can also be used to check whether a circuit defines an automorphism F. If K is the Boolean field GF(2), then a circuit defining a bijection does not necessarily define an automorphism. However, it is shown in this case that, given any K/sup n/ to K/sup n/ bijection, there always exists an automorphism defining that bijection. This is not generally true for an arbitrary finite field.>