With the widespread availability of cloud computing and big data, homomorphic encryption has become a crucial technique employed to protect the data privacy in outsourced computation. However, the existing outsourced computation toolkits based on homomorphic encryption either require all participants to share the same key or result in enormous computational and communication overheads. In order to address these shortcomings, we put forward a toolkit for efficient and secure outsourced computation in multiple key scenarios (ESCM). ESCM can permit the servers to process the most frequently used arithmetic operations such as multiplication, division, sorting and so on across different encrypted domains. Moreover, to tackle the security concerns that may arise from collusion among some servers, as well as the problem of service disruption due to server outages, we propose the distributed two trapdoor cryptosystem with threshold decryption, the core cryptographic primitive, which is able to support (k, n) threshold decryption. Theoretical analysis validates the security of the proposed ESCM and compares the computation and communication complexity with existing most advanced solutions. Finally, simulation experiments illustrate the practicality and efficiency of ESCM.

De Bruijn sequences can be categorized by the weight of the truth tables of the generating functions. Among all the weight classes, the numbers of de Bruijn sequences with minimum and maximum weights draw much attention. Fredricksen and Mayhew proposed six conjectures about them, some of which have remained unsolved for about forty years. In this paper, we give the exact formulas of de Bruijn sequences with extremal weights and then prove all the conjectures in the affirmative.

In this paper, we investigate the power function$F(x)=x^{d}$over the finite field$\mathbb {F}_{2^{4n}}$, where$n$is a positive integer and$d=2^{3n}+2^{2n}+2^{n}-1$. We prove that this power function is AP$c\text{N}$with respect to all$c\in \mathbb {F}_{2^{4n}}\setminus \{1\}$satisfying$c^{2^{2n}+1}=1$, and we determine its$c$-differential spectrum. To the best of our knowledge, this is the second class of AP$c\text{N}$power functions over finite fields of even characteristic. By the same proof ideas, we completely determine the differential spectrum of this function, and give an affirmative answer to a recent conjecture proposed by Budaghyan, Calderini, Carlet, Davidova and Kaleyski.

Given a binary sequence with length$n$, determining its minimal rational fraction representation (MRFR) has important applications in the design and cryptanalysis of stream ciphers. There are many studies of this problem since Klapper and Goresky first introduced an adaptive rational approximation algorithm with a time complexity of$O(n^{2}\log n\log \log n)$. In this paper, we revisit this problem by considering both adaptive and non-adaptive efficient algorithms. Compared with the state-of-art methods, we make several contributions to the problem of finding MRFR. Firstly, we find a general and precise recursive relationship between the minimal bases for two adjacent lattices generated by successive truncation sequences. This enables us to improve the currently fastest adaptive algorithm proposed by Liet al.. Secondly, by optimizing a time-consuming step of the well-known Lagrange reduction algorithm for 2-dimensional lattices, we obtain a non-adaptive, and yet practically faster MRFR-solving algorithm namedglobalEuclidean algorithm. Thirdly, we identify theoretical flaws on some non-adaptive methods in the literature by counter-examples and correct the problems by designing modified Euclidean algorithm namedpartialEuclidean algorithm. Meanwhile, we further reduce the time complexity of existing algorithm from$O(n^{2})$to$O(n\log ^{2}n\log \log n)$by invoking the half-gcd algorithm. We also conduct a comprehensive experimental comparative analysis on the above algorithms to validate our theoretical analysis.

De Bruijn sequences and l-sequences are defined to be the maximum-period sequences generated by feedback shift registers (FSRs) and feedback with carry shift registers (FCSRs), respectively. In this paper we give some relationships between de Bruijn sequences and l-sequences, and we propose an efficient method to generate de Bruijn sequences from l-sequences. The experimental results indicate that this method should be able to generate de Bruijn sequences of any order.

In this paper, we analyze the weight class distribution of de Bruijn sequences. The main tool we use is the generating function theory, proposed recently by Coppersmith et al. By analyzing the weights of cycles generated by the pure circulating register, we give explicit formulas for the numbers of de Bruijn sequences in the extremal weight classes. Moreover, we use these formulas to prove some conjectures proposed by Fredricksen and Mayhew, which seems have been opened for a long time. In addition to these theoretical results, some experimental results are also provided.

A Grain-like structure is a cascade connection of a primitive LFSR into an NFSR. It is well known that such structures generate sequences with periods multiples of the period of primitive LFSR sequences. In this paper, we study weak Grainlike structures, i.e., Grain-like structures generating at least one sequence with minimum period. Assume the orders of LFSR and NFSR are n and m respectively. We prove that weak Grain-like structures always exist when m > n. For m = n, we give three classes of weak Grain-like structures. Then we extend the method in the second class to prove that weak Grain-like structures exist when m ≥ n - lg n + 4. Moreover, our experimental data shows that, the ratio of weak Grain-like structures approximates a value which is a little more than 63% for small m = n, and weak Grain-like structures exist with m = 3 or 4 when n ≤ 18.

A nonlinear feedback shift register (NFSR) of n-stage is called irreducible if, the family of output sequences of any NFSR of stage less than $n$ is not included in that of the NFSR. Tian and Qi in this paper [IEEE-IT, 2013(6),4006-4012] gave a lower bound on the density of irreducible NFSRs. In this paper, we improve their lower bound and also give an upper bound on the density of irreducible NFSRs. Moreover, the gap between our upper and lower bounds is less than 0.04.

Let a and b be primitive sequences over ℤ/(pe) with odd prime p and e ≥ 2. For certain compressing maps, we consider the distribution properties of compressing sequences of a and b, and prove that a = b if the compressing sequences are equal at the times t such that α(t) = k, where α is a sequence related to a. We also discuss the s-uniform distribution property of compressing sequences. For some compressing maps, we obtain that there exist different primitive sequences such that the compressing sequences are s-uniform. We also discuss that for how many elements s, compressing sequences of different primitive sequences can be s-uniform.