Practical parallel key-insulated encryption with multiple helper keys

Parallel key-insulated encryption (PKIE) usually allows two independent helper keys to be alternately used in temporary secret key update operations. At least half of temporary secret keys would be exposed and at least half of ciphertexts could be decrypted if one of the helper keys is exposed. In this paper, we propose a new PKIE scheme with $m$ helper keys, where $m\in Z,m>2$. If one of the helper keys is exposed, only $1/m$ temporary secret keys would be exposed and $1/m$ ciphertexts could be decrypted, so the new PKIE scheme can greatly decrease loss due to key-exposure. The scheme is provably secure without random oracles based on a bilinear group of composite order. Most important, the scheme is practical and much more efficient than the extended ones from the previous PKIE schemes.     

The best keying protocol for sensor networks

Many sensor networks (especially networks of mobile sensors or networks that are deployed to monitor crisis situations) are deployed in an arbitrary and unplanned fashion. Thus, any sensor in such a network can end up being adjacent to any other sensor in the network. To secure the communications between every pair of adjacent sensors in such a network, each sensor $x$ in the network needs to store $n?1$ symmetric keys that sensor $x$ shares with all the other sensors, where $n$ is an upper bound on the number of sensors in the network. This storage requirement of the keying protocol is rather severe, especially when $n$ is large and the available storage in each sensor is modest. Earlier efforts to redesign this keying protocol and reduce the number of keys to be stored in each sensor have produced protocols that are vulnerable to impersonation, eavesdropping, and collusion attacks. In this paper, we present a fully secure keying protocol where each sensor needs to store $(n+1)/2$ keys, which is much less than the $n?1$ keys that need to be stored in each sensor in the original keying protocol. We also show that in any fully secure keying protocol, each sensor needs to store at least $(n?1)/2$ keys.     

Eigenvalues of a real supersymmetric tensor

In this paper, we define the symmetric hyperdeterminant, eigenvalues and E-eigenvalues of a real supersymmetric tensor. We show that eigenvalues are roots of a one-dimensional polynomial, and when the order of the tensor is even, E-eigenvalues are roots of another one-dimensional polynomial. These two one-dimensional polynomials are associated with the symmetric hyperdeterminant. We call them the characteristic polynomial and the E-characteristic polynomial of that supersymmetric tensor. Real eigenvalues (E-eigenvalues) with real eigenvectors (E-eigenvectors) are called H-eigenvalues (Z-eigenvalues). When the order of the supersymmetric tensor is even, H-eigenvalues (Z-eigenvalues) exist and the supersymmetric tensor is positive definite if and only if all of its H-eigenvalues (Z-eigenvalues) are positive. An $m\mathrm{th}$-order $n$-dimensional supersymmetric tensor where $m$ is even has exactly $n{(m-1)}^{n-1}$ eigenvalues, and the number of its E-eigenvalues is strictly less than $n{(m-1)}^{n-1}$ when $m\ge 4$. We show that the product of all the eigenvalues is equal to the value of the symmetric hyperdeterminant, while the sum of all the eigenvalues is equal to the sum of the diagonal elements of that supersymmetric tensor, multiplied by ${(m-1)}^{n-1}$. The $n{(m-1)}^{n-1}$ eigenvalues are distributed in $n$ disks in $C$. The centers and radii of these $n$ disks are the diagonal elements, and the sums of the absolute values of the corresponding off-diagonal elements, of that supersymmetric tensor. On the other hand, E-eigenvalues are invariant under orthogonal transformations.     

The minimal polynomial of a sequence obtained from the componentwise linear transformation of a linear recurring sequence

Let $S=(s_1,s_2,\dots ,s_m,\dots )$ be a linear recurring sequence with terms in $GF\left(q^n\right)$ and $T$ be a linear transformation of $GF\left(q^n\right)$ over $GF\left(q\right)$. Denote $T\left(S\right)=(T\left(s_1\right),T\left(s_2\right),\dots ,T\left(s_m\right),\dots )$. In this paper, we first present counter examples to show that the main result in [A.M. Youssef, G. Gong, On linear complexity of sequences over $GF\left(2^n\right)$, Theoret. Comput. Sci., 352 (2006) 288–292] is not correct in general since Lemma 3 in that paper is incorrect. Then we determine the minimal polynomial of $T\left(S\right)$ if the canonical factorization of the minimal polynomial of $S$ without multiple roots is known and thus present the solution to the main problem which was considered in the above paper but incorrectly solved. Additionally, as a special case, we determine the minimal polynomial of $T\left(S\right)$ if the minimal polynomial of $S$ is primitive. Finally, we give an upper bound on the linear complexity of $T\left(S\right)$ when $T$ exhausts all possible linear transformations of $GF\left(q^n\right)$ over $GF\left(q\right)$. This bound is tight in some cases.     

Best uniform polynomial approximation of some rational functions

In this research paper using the Chebyshev expansion, we explicitly determine the best uniform polynomial approximation out of $P_{qn}$ (the space of polynomials of degree at most $qn$) to a class of rational functions of the form $1/(T_q\left(a\right)\pm T_q\left(x\right))$ on $[?1,1]$, where $T_q\left(x\right)$ is the first kind of Chebyshev polynomial of degree $q$ and $a^2>1$. In this way we give some new theorems about the best approximation of this class of rational functions. Furthermore we obtain the alternating set of this class of functions.     

Hardness of approximating the Shortest Vector Problem in high ℓp norms

We present a new hardness of approximation result for the Shortest Vector Problem in ${\ell }_p$ norm (denoted by ${\mathrm{SVP}}_p$). Assuming NP $⊈$ ZPP, we show that for every $\epsilon >0$, there is a constant $p(\epsilon )$ such that for all integers $p⩾p(\epsilon )$, the problem ${\mathrm{SVP}}_p$ has no polynomial time approximation algorithm with approximation ratio $p^{1-\epsilon }$.     

Precise contact motion planning for deformable planar curved shapes

We present a precise contact motion planning algorithm for a deformable robot in a planar environment with stationary obstacles. The robot and obstacles are both represented with $C^1$-continuous implicit or parametric curves. The robot is changing its shape using a single degree of freedom (via a one-parameter family of deformable curves). In order to reduce the dimensionality of the configuration space, geometrically constrained yet collision free contact motions are sought, that have $K(=2,3)$ simultaneous tangential contact points between the robot and the obstacles. The $K$-contact motion analysis effectively reduces the degrees of freedom of the robot, which enables a more efficient motion planning. The geometric conditions for the $K$-contact motions can be formulated as a system of non-linear polynomial equations, which can be solved precisely using a multivariate equation solver. The solutions for $K$-contact motions are represented as curves in a 4-dimensional $(x,y,\theta ,t)$ space, where $x,y,\theta$ are the degrees of freedom of the rigid motion and $t$ is the deformation’s parameter. Using the graph structure of the solution curves for the $K$-contact motions, our algorithm efficiently finds a feasible path connecting two configurations via a graph searching algorithm, whenever available. We demonstrate the effectiveness of the proposed approach using several examples.     

Trees with minimal Laplacian coefficients

Let $G$ be a simple undirected graph with the characteristic polynomial of its Laplacian matrix $L\left(G\right)$, $P(G,\mu )={\sum }_{k=0}^n{(?1)}^k{c}_k{\mu }^{n?k}$. It is well known that for trees the Laplacian coefficient $c_{n?2}$ is equal to the Wiener index of $G$, while $c_{n?3}$ is equal to the modified hyper-Wiener index of the graph. In this paper, we characterize $n$-vertex trees with given matching number $m$ which simultaneously minimize all Laplacian coefficients. The extremal tree $A(n,m)$ is a spur, obtained from the star graph $S_{n?m+1}$ with $n?m+1$ vertices by attaching a pendant edge to each of certain $m?1$ non-central vertices of $S_{n?m+1}$. In particular, $A(n,m)$ minimizes the Wiener index, the modified hyper-Wiener index and the recently introduced Incidence energy of trees, defined as $IE\left(G\right)={\sum }_{k=0}^n\sqrt{{\mu }_k}$, where ${\mu }_k$ are the eigenvalues of signless Laplacian matrix $Q\left(G\right)=D\left(G\right)+A\left(G\right)$. We introduced a general $\rho$ transformation which decreases all Laplacian coefficients simultaneously. In conclusion, we illustrate on examples of Wiener index and Incidence energy that the opposite problem of simultaneously maximizing all Laplacian coefficients has no solution.     

Infeasibility of instance compression and succinct PCPs for NP

The OR-SAT problem asks, given Boolean formulae ${?}_1,\dots ,{?}_m$ each of size at most n, whether at least one of the ${?}_i$'s is satisfiable. We show that there is no reduction from OR-SAT to any set A where the length of the output is bounded by a polynomial in n, unless $\mathsf{NP}?\mathsf{coNP}/\mathrm{poly}$, and the Polynomial-Time Hierarchy collapses. This result settles an open problem proposed by Bodlaender et al. (2008) [6] and Harnik and Naor (2006) [20] and has a number of implications. (i) A number of parametric $\mathsf{NP}$ problems, including Satisfiability, Clique, Dominating Set and Integer Programming, are not instance compressible or polynomially kernelizable unless $\mathsf{NP}?\mathsf{coNP}/\mathrm{poly}$. (ii) Satisfiability does not have PCPs of size polynomial in the number of variables unless $\mathsf{NP}?\mathsf{coNP}/\mathrm{poly}$. (iii) An approach of Harnik and Naor to constructing collision-resistant hash functions from one-way functions is unlikely to be viable in its present form. (iv) (Buhrman–Hitchcock) There are no subexponential-size hard sets for NP unless NP is in co-NP/poly. We also study probabilistic variants of compression, and show various results about and connections between these variants. To this end, we introduce a new strong derandomization hypothesis, the Oracle Derandomization Hypothesis, and discuss how it relates to traditional derandomization assumptions.     

On the definition of the intuitionistic fuzzy subgroups

In this paper, a new kind of intuitionistic fuzzy subgroup theory, which is different from that of Ma, Zhan and Davvaz (2008) [22], [23], is presented. First, based on the concept of cut sets on intuitionistic fuzzy sets, we establish the neighborhood relations between a fuzzy point $x_a$ and an intuitionistic fuzzy set $A$. Then we give the definitions of the grades of $x_a$ belonging to $A$, $x_a$ quasi-coincident with $A$, $x_a$ belonging to and quasi-coincident with $A$ and $x_a$ belonging to or quasi-coincident with $A$, respectively. Second, by applying the 3-valued Lukasiewicz implication, we give the definition of $(\alpha ,\beta )$-intuitionistic fuzzy subgroups of a group $G$ for $\alpha ,\beta \in \{\in ,q,\in \wedge q,\in \vee q\}$, and we show that, in 16 kinds of $(\alpha ,\beta )$-intuitionistic fuzzy subgroups, the significant ones are the $(\in ,\in )$-intuitionistic fuzzy subgroup, the $(\in ,\in \vee q)$-intuitionistic fuzzy subgroup and the $(\in \wedge q,\in )$-intuitionistic fuzzy subgroup. We also show that $A$ is a $(\in ,\in )$-intuitionistic fuzzy subgroup of $G$ if and only if, for any $a\in (0,1]$, the cut set $A_a$ of $A$ is a 3-valued fuzzy subgroup of $G$, and $A$ is a $(\in ,\in \vee q)$-intuitionistic fuzzy subgroup (or $(\in ,\in \vee q)$-intuitionistic fuzzy subgroup) of $G$ if and only if, for any $a\in (0,0.5]$(or for any $a\in (0.5,1]$), the cut set $A_a$ of $A$ is a 3-valued fuzzy subgroup of $G$. At last, we generalize the $(\in ,\in )$-intuitionistic fuzzy subgroup, $(\in ,\in \vee q)$-intuitionistic fuzzy subgroup and $(\in \wedge q,\in )$-intuitionistic fuzzy subgroup to intuitionistic fuzzy subgroups with thresholds, i.e., $(s,t]$-intuitionistic fuzzy subgroups. We show that $A$ is a $(s,t]$-intuitionistic fuzzy subgroup of $G$ if and only if, for any $a\in (s,t]$, the cut set $A_a$ of $A$ is a 3-valued fuzzy subgroup of $G$. We also characterize the $(s,t]$-intuitionistic fuzzy subgroup by the neighborhood relations between a fuzzy point $x_a$ and an intuitionistic fuzzy set $A$.     

The Steiner traveling salesman problem with online advanced edge blockages

The package delivery in an urban road network is formulated as an online Steiner traveling salesman problem, where the driver (i.e. the salesman) receives road (i.e. edge) blockage messages when he is at a certain distance to the respective blocked edges. Such road blockages are referred to as advanced information. With these online advanced road blockages, the driver wishes to deliver all the packages to their respective customers and returns back to the service depot through a shortest route. During the entire delivery process, there will be at most k road blockages, and they are non-recoverable. When the driver knows about road blockages at a distance $\alpha \mathrm{OPT}$, where $\alpha \in [0,1]$ is referred to as the forecasting ratio and OPT denotes the length of the offline shortest route, we first prove that $\max \left\{\right(1-2\alpha )k+1,1\}$ is a lower bound on the competitive ratio. We then present a polynomial time online algorithm with a competitive ratio very close to this lower bound. Computational results show that our algorithm is efficient and produces near optimal solutions. Similar results for a variation, in which the driver does not need to return to the service depot, are also achieved.