Parallel computation is an important aspect of multi-party computation, not only in terms of improving efficiency, but also in terms of providing privacy for computation involving conditional branching based on private data. While applying multi-party computation in parallel over several sets of input data is straightforward if the partitioning of the input data into sets is publicly known, the problem becomes much more challenging when this partitioning is private. This setting is relevant to broad class of secure computations, in particular to secure graph and database analysis in which the underlying data (graph or database) is private. In this paper, we consider a general class of functions which can be expressed via the iterative evaluation of a binary associative operation, and propose efficient protocols for evaluating such functions in parallel over privately partitioned input data. Our protocols are optimal in terms of the required number of evaluations of the underlying binary operation (i.e.\ N-1 evaluations for total input size N), while simultaneously achieving a round complexity which is only logarithmic in the total size of the input data (i.e.\ O(łog N)).

In this paper we propose efficient two-party protocols for obliviously applying a (possibly random) linear group action to a data set. Our protocols capture various applications such as oblivious shuffles, circular shifts, matrix multiplications, to name just a few. A notable feature enjoyed by our protocols, is that they admit a round-optimal (more precisely, one-round) online computation phase, once an input-independent off-line computation phase has been completed. Our oblivious shuffle is the first to achieve a round-optimal online phase. The most efficient instantiations of our protocols are obtained in the so-called client-aided client-server setting, where the offline phase is run by a semi-honest input party (client) who will then distribute the generated correlated randomness to the computing parties (servers). When comparing the total running time to the previous best two-party oblivious shuffle protocol by Chase et al. (Asiacrypt 2020), our shuffle protocol in this client-aided setting is up to 105 times and 152 times faster, in the LAN and WAN setting, respectively. We additionally show how the Chase et al. protocol (which is a standard two-party protocol) can be modified to leverage the advantages of the client-aided setting, but show that, even doing so, our scheme is still two times faster in the online phase and 1.34 times faster in total on average.

We construct an efficient two-level homomorphic public-key encryption in prime-order bilinear groups. Such a scheme supports polynomially many homomorphic additions and one multiplication over encrypted data, similar to the cryptosystem of Boneh, Goh, and Nissim (BGN, presented at TCC 2005), which was constructed in composite-order bilinear groups. Prior to our work, the state-of-the-art for two-level homomorphic public-key encryption is the Freeman scheme (presented at Eurocrypt 2010), which is indeed the prime-order realization of the BGN scheme. Our proposed scheme significantly improves efficiency for almost all the aspects of the Freeman scheme, while retains the same ciphertext sizes. Our scheme is surprisingly simple as it is indeed (a concatenation of two copies of) the ElGamal encryption "in the exponent'' resided in an asymmetric bilinear groups.

Functional encryption is an extension of the ordinary public key encryption where decryption results vary depending on the functions (or key attributes) associated to secret keys. In this paper, we show an embedding lemma for functional encryption, which provides a sufficient criterion for implication from one FE to FE with another function class. The lemma is an extension of the embedding lemma for attribute-based encryption that was introduced in the previous work by Boneh and Hamburg (Asiacrypt 2008). As an application of our lemma, we show that FE for cubic forms can be constructed from FE for inner product or FE for quadratic forms.

The randomness assumption (RA) over lattices was introduced by Schnorr (STACS 2003) to model the behavior of sampling algorithms (SAs). SAs are used in random sampling reduction algorithms and their variants to efficiently generate relatively short vectors. Assuming the validity of RA, Fukase and Kashiwabara (JIP 2015, Vol.23, No.1) proposed an estimation of the squared length of lattice vectors generated by SA, and a strategy to reduce lattice bases efficiently. However, recently, several researchers pointed out that RA might not hold without providing any numerical evidence of their claim. Therefore, in this paper, we provide a simple numerical experiment to investigate the trustworthiness of RA through the behavior of SA. Our experimental result shows that RA describes many of the behaviors of SA. We note that ac-cording to the observation made by Ludwig (TU Darmstadt PhD Thesis 2015), our result captures where RA does not hold. We conclude that although RA cannot be said to completely hold, it seems to be capturing the behavior of SA in practice to some extent.

A ciphertext-policy attribute-based encryption protocol uses bilinear pairings to provide control access mechanisms, where the set of user's attributes is specified by means of a linear secret sharing scheme. In this paper we present the design of a software cryptographic library that achieves record timings for the computation of a 126-bit security level attribute-based encryption scheme. We developed all the required auxiliary building blocks and compared the computational weight that each of them adds to the overall performance of this protocol. In particular, our single pairing and multi-pairing implementations achieve state-of-the-art time performance at the 126-bit security level.