International Journal of Foundations of Computer Science

Multikey fully homomorphic encryption (MFHE) allows homomorphic operations between ciphertexts encrypted under different keys. In applications for secure multiparty computation (MPC) protocols, MFHE can be more advantageous than usual fully homomorphic encryption (FHE) since users do not need to agree with a common public key before the computation when using MFHE. In EUROCRYPT 2016, Mukherjee and Wichs constructed a secure MPC protocol in only two rounds via MFHE which deals with a common random/reference string (CRS) in key generation. After then, Brakerski et al. replaced the role of CRS with the distributed setup for CRS calculation to form a four round secure MPC protocol. Thus, recent improvements in round complexity of MPC protocols have been made using MFHE.

In this paper, we go further to obtain round-efficient and secure MPC protocols. The underlying MFHE schemes in previous works still involve the common value, CRS, it seems to weaken the power of using MFHE to allow users to independently generate their own keys. Therefore, we resolve the issue by constructing an MFHE scheme without CRS based on LWE assumption, and then we obtain a secure MPC protocol against semi-malicious security in three rounds. We also define a new security notion “multikey-CPA security” to prove that a multikey ciphertext cannot be decrypted unless all the secret keys are gathered and our scheme is multikey-CPA secure.

Certificateless cryptosystems have attracted great interests in cryptographic research since its invention. Because compared with traditional public key cryptosystems or identity-based cryptosystems, they could not only simplify the certificate management, but also alleviate the key escrow problem. In certificateless cryptosystems, user revocation is a challenging issue. To address this issue, one popular method is to update the key via public channels. However, most of the existing schemes in this approach are impractical because of the following two shortcomings. Firstly, the user needs to maintain a list of decryption keys, but the size of the list will keep increasing. Secondly, the revoked user can still recover the plaintexts of the encrypted data prior to revocation, and this is a particular threat in some applications. To solve these problems, this paper presents revocable certificateless encryption with ciphertext evolution. We give a generic construction and then describe how it can be initialized concretely. In our proposed scheme, the user only needs to keep one decryption key, and once a user is revoked, it can no longer decrypt any ciphertext in the server. Moreover, the IND-CCA security model is defined against three types of attacks. And our schemes are formally proved to satisfy these security requirements.

In 2013, the revelation of Edward Snowden rekindled cryptographic researchers’ interest in subversion attacks. Since then, many works have been carried out to explore the power of subversion attacks and feasible effective countermeasures as well. In this work, we investigate the study of subversion attacks against cloud auditing protocol, which has been well-known as useful primitive for secure cloud storage. We demonstrate that subverted auditing protocol enables the cloud server to recover secret information stored on the data owner side. Particularly, we first define an asymmetric subversion attack model for auditing protocol. This model serves as the principle for analyzing the undetectability and key recovery of subversion attacks against auditing protocols. We then show a general framework of asymmetric subversion attacks against auditing protocols with index-coefficient challenge. To illustrate the feasibility of our paradigm, several concrete auditing protocols are provided. As a feasible countermeasure, we propose a subversion-resilient auditing protocol with index-coefficient challenge.

Let $(n=pq,e=n^{\beta })$ be an RSA public key with private exponent $d=n^{\delta },$ where $p$ and $q$ are large primes of the same bit size. At Eurocrypt 96, Coppersmith presented a polynomial-time algorithm for finding small roots of univariate modular equations based on lattice reduction and then succussed to factorize the RSA modulus. Since then, a series of attacks on the key equation $ed-k\varphi (n)=1$ of RSA have been presented. In this paper, we show that many of such attacks can be unified in a single attack using a new notion called Coppersmith’s interval. We determine a Coppersmith’s interval for a given RSA public key $(n,e).$ The interval is valid for any variant of RSA, such as Multi-Prime RSA, that uses the key equation. Then we show that RSA is insecure if $\delta <\beta +\frac{1}{3}\alpha -\frac{1}{3}\sqrt{12\alpha \beta +4{\alpha }^2}$ provided that we have approximation $p_0\ge \sqrt{n}$ of $p$ with $\left|p-p_0\right|\le \frac{1}{2}{n}^{\alpha },$ $\alpha \le \frac{1}{2}.$ The attack is an extension of Coppersmith’s result.

The topology properties of multi-processors interconnection networks are important to the performance of high performance computers. The hypercube network $Q_n$ has been proved to be one of the most popular interconnection networks. The $n$-dimensional locally twisted cube $LT{Q}_n$ is an important variant of $Q_n$. Fault diameter and wide diameter are two communication performance evaluation parameters of a network. Let $D(LT{Q}_n$), $D_{n-1}^f(LT{Q}_n)$ and $D_n(LT{Q}_n)$ denote the diameter, the $n-1$ fault diameter and the wide diameter of $LT{Q}_n$, respectively. In this paper, we prove that $D_{n-1}^f(LT{Q}_n)=D_n(LT{Q}_n)=D(LT{Q}_n)+2$ if $n$ is an odd integer with $n\ge 7$, $D(LT{Q}_n)+1\le D_{n-1}^f(LT{Q}_n)\le D_n(LT{Q}_n)\le D(LT{Q}_n)+2$ if $n$ is an even integer with $n\ge 8$.

We consider the maximum common connected edge subgraph problem and the maximum common connected induced subgraph problem for simple graphs with labeled vertices (or labeled edges). The former is to find a connected graph with the maximum number of edges that is isomorphic to a subgraph of each of the two input graphs. The latter is to find a common connected induced subgraph with the maximum number of vertices. We prove that both problems are NP-hard for 3-outerplanar labeled graphs even if the maximum vertex degree is bounded by 4. Since the reductions used in the proofs construct graphs with treewidth at most 4, both problems are NP-hard also for such graphs, which significantly improves the previous hardness results for graphs with treewidth 11. We also present improved exponential-time algorithms for both problems on labeled graphs of bounded treewidth and bounded vertex degree.

In this paper, we consider a restricted covering problem, in which a convex polygon $P$ with $n$ vertices and an integer $k$ are given, the objective is to cover the entire region of $P$ using $k$ congruent disks of minimum radius $r_{opt}$, centered on the boundary of $P$. For $k\ge 7$ and any $𝜖>0$, we propose an $(1+\frac{7}{k}+\frac{7𝜖}{k}+𝜖)$-factor approximation algorithm for this problem, which runs in $O((n+k)(\left|\mathrm{\text{log}}{r}_{opt}\right|+\mathrm{\text{log}}\lceil \frac{1}{𝜖}\rceil ))$ time. The best known approximation factor of the algorithm for the problem in the literature is 1.8841 [H. Du and Y. Xu: An approximation algorithm for $k$-center problem on a convex polygon, J. Comb. Optim. 27(3) (2014) 504–518].