The increasing demand for high-performance computing in recent years has led to active research on massively parallel systems. The interconnection network in a massively parallel system interconnects hundreds of thousands of processing elements so that they can process large tasks while communicating among others. By regarding the processing elements as nodes and the links between processing elements as edges, respectively, we can discuss various problems of interconnection networks in the framework of the graph theory. Many topologies have been proposed for interconnection networks of massively parallel systems. The hypercube is a very popular topology and it has many variants. The cross-cube is such a topology, which can be obtained by adding one extra edge to each node of the hypercube. The cross-cube reduces the diameter of the hypercube, and allows cycles of odd lengths. Therefore, we focus on the cross-cube and propose an algorithm that constructs disjoint paths from a node to a set of nodes. We give a proof of correctness of the algorithm. Also, we show that the time complexity and the maximum path length of the algorithm are O(n3 log n) and 2n - 3, respectively. Moreover, we estimate that the average execution time of the algorithm is O(n2) based on a computer experiment.

Let f be a Boolean function in n variables. The Möbius transform and its converse of f can describe the transformation behaviors between the truth table of f and the coefficients of the monomials in the algebraic normal form representation of f. In this letter, we develop the Möbius transform and its converse into a more generalized form, which also includes the known result given by Reed in 1954. We hope that our new result can be used in the design of decoding schemes for linear codes and the cryptanalysis for symmetric cryptography. We also apply our new result to verify the basic idea of the cube attack in a very simple way, in which the cube attack is a powerful technique on the cryptanalysis for symmetric cryptography.

Nowadays, a rapid increase of demand on high-performance computation causes the enthusiastic research activities regarding massively parallel systems. An interconnection network in a massively parallel system interconnects a huge number of processing elements so that they can cooperate to process tasks by communicating among others. By regarding a processing element and a link between a pair of processing elements as a node and an edge, respectively, many problems with respect to communication and/or routing in an interconnection network are reducible to the problems in the graph theory. For interconnection networks of the massively parallel systems, many topologies have been proposed so far. The hypercube is a very popular topology and it has many variants. The bicube is a such topology and it can interconnect the same number of nodes with the same degree as the hypercube while its diameter is almost half of that of the hypercube. In addition, the bicube keeps the node-symmetric property. Hence, we focus on the bicube and propose an algorithm that gives a minimal or shortest path between an arbitrary pair of nodes. We give a proof of correctness of the algorithm and demonstrate its execution.

A rep-cube is a polyomino that is a net of a cube, and it can be divided into some polyominoes such that each of them can be folded into a cube. This notion was invented in 2017, which is inspired by the notions of polyomino and rep-tile, which were introduced by Solomon W. Golomb. A rep-cube is called regular if it can be divided into the nets of the same area. A regular rep-cube is of order k if it is divided into k nets. Moreover, it is called uniform if it can be divided into the congruent nets. In this paper, we focus on these special rep-cubes and solve several open problems.

In this paper, we propose a notion for high-dimensional generalizations of mutually orthogonal Latin squares (MOLS) and mutually orthogonal diagonal Latin squares (MODLS), called mutually dimensionally orthogonal d-cubes (MOC) and mutually dimensionally orthogonal diagonal d-cubes (MODC). Systematic constructions for MOC and MODC by using polynomials over finite fields are investigated. In particular, for 3-dimensional cubes, the results for the maximum possible number of MODC are improved by adopting the proposed construction.

Connecting a large number of servers with high bandwidth links is one of the most crucial and challenging tasks that the Data Center Network (DCN) must fulfill. DCN faces a lot of difficulties like the effective exploitation of DC components that, if highlighted, can aid in constructing high performance, scalable, reliable, and cost-effective DCN. In this paper, we investigate the server-centric structure. We observe that current DCs use servers that mostly come with dual ports. Effective exploitation of the ports of interest for building the topology structure can help in realizing the potentialities of reducing expensive topology. Our new network topology, named “Parallel Cubes” (PCube), is a duplicate defined structure that utilizes the ports in the servers and mini-switches to form a highly effective, scalable, and efficient network structure. P-Cube provides high performance in network latency and throughput and fault tolerance. Additionally, P-Cube is highly scalable to encompass hundreds of thousands of servers with a low stable diameter and high bisection width. We design a routing algorithm for P-Cube network that utilizes the P-Cube structure to strike a balance among the numerous links in the network. Finally, numerical results are provided to show that our proposed topology is a promising structure as it outperforms other topologies and it is superior to Fat-tree, BCube and DCell by approximately 24%, 16%, 8% respectively in terms of network throughput and latency. Moreover, P-Cube extremely outperforms Fat-tree, and BCube structures in terms of total cost, complexity of cabling and power consumption.

In this paper, we extend the notion of bijective connection graphs to introduce directed bijective connection graphs. We propose algorithms that solve the node-to-set node-disjoint paths problem and the node-to-node node-disjoint paths problem in a directed bijective connection graph. The time complexities of the algorithms are both O(n4), and the maximum path lengths are both 2n-1.

A set of spanning trees of a graphs G are called completely independent spanning trees (CISTs for short) if for every pair of vertices x, y∈V(G), the paths joining x and y in any two trees have neither vertex nor edge in common, except x and y. Constructing CISTs has applications on interconnection networks such as fault-tolerant routing and secure message transmission. In this paper, we investigate the problem of constructing two CISTs in the balanced hypercube BHn, which is a hypercube-variant network and is superior to hypercube due to having a smaller diameter. As a result, the diameter of CISTs we constructed equals to 9 for BH2 and 6n-2 for BHn when n≥3.

The security analysis of Keccak, the winner of SHA-3, has attracted considerable interest. Recently, some attention has been paid to distinguishing Keccak sponge function from random permutation. In EUROCRYPT'17, Huang et al. proposed conditional cube tester to recover the key of Keccak-MAC and Keyak and to construct practical distinguishing attacks on Keccak sponge function up to 7 rounds. In this paper, we improve the conditional cube tester model by refining the formulation of cube variables. By classifying cube variables into three different types and working the candidates of these types of cube variable carefully, we are able to establish a new theoretical distinguisher on 8-round Keccak sponge function. Our result is more efficient and greatly improves the existing results. Finally we remark that our distinguishing attack on the the reduced-round Keccak will not threat the security margin of the Keccak sponge function.

In a multiprocessor system, processors are connected based on various types of network topologies. A network topology is usually represented by a graph. Let G be a graph and u, v be any two distinct vertices of G. We say that G is pancyclic if G has a cycle C of every length l(C) satisfying 3≤l(C)≤|V(G)|, where |V(G)| denotes the total number of vertices in G. Moreover, G is panpositionably pancyclic from r if for any integer m satisfying $r leq m leq rac{|V(G)|}{2}$, G has a cycle C containing u and v such that dC(u,v)=m and 2m≤l(C)≤|V(G)|, where dC(u,v) denotes the distance of u and v in C. In this paper, we investigate the panpositionable pancyclicity problem with respect to the n-dimensional locally twisted cube LTQn, which is a popular topology derived from the hypercube. Let D(LTQn) denote the diameter of LTQn. We show that for n≥4 and for any integer m satisfying $D(LTQ_n) + 2 leq m leq rac{|V(LTQ_n)|}{2}$, there exists a cycle C of LTQn such that dC(u,v)=m, where (i) 2m+1≤l(C)≤|V(LTQn)| if m=D(LTQn)+2 and n is odd, and (ii) 2m≤l(C)≤|V(LTQn)| otherwise. This improves on the recent result that u and v can be positioned with a given distance on C only under the condition that l(C)=|V(LTQn)|. In parallel and distributed computing, if cycles of different lengths can be embedded, we can adjust the number of simulated processors and increase the flexibility of demand. This paper demonstrates that in LTQn, the cycle embedding containing any two distinct vertices with a feasible distance is extremely flexible.

We propose the cube-based perceptual encryption (C-PE), which consists of cube scrambling, cube rotation, cube negative/positive transformation, and cube color component shuffling, and describe its application to the encryption-then-compression (ETC) system of Motion JPEG (MJPEG). Especially, cube rotation replaces the blocks in the original frames with ones in not only the other frames but also the depth-wise cube sides (spatiotemporal sides) unlike conventional block-based perceptual encryption (B-PE). Since it makes intra-block observation more difficult and prevents unauthorized decryption from only a single frame, it is more robust than B-PE against attack methods without any decryption key. However, because the encrypted frames including the blocks from the spatiotemporal sides affect the MJPEG compression performance slightly, we also devise a version of C-PE with no spatiotemporal sides (NSS-C-PE) that hardly affects compression performance. C-PE makes the encrypted video sequence robust against the only single frame-based algorithmic brute force (ABF) attack with only 21 cubes. The experimental results show the compression efficiency and encryption robustness of the C-PE/NSS-C-PE-based ETC system. C-PE-based ETC system shows mixed results depending on videos, whereas NSS-C-PE-based ETC system shows that the BD-PSNR can be suppressed to about -0.03dB not depending on videos.

Last year, a new notion of rep-cube was proposed. A rep-cube is a polyomino that is a net of a cube, and it can be divided into some polyominoes such that each of them can be folded into a cube. This notion was inspired by the notions of polyomino and rep-tile, which were introduced by Solomon W. Golomb. It was proved that there are infinitely many distinct rep-cubes. In this paper, we investigate this new notion and show further results.

The exchanged hypercube, denoted by EH(s,t), is a graph obtained by systematically removing edges from the corresponding hypercube, while preserving many of the hypercube's attractive properties. Moreover, ring-connected topology is one of the most promising topologies in Wavelength Division Multiplexing (WDM) optical networks. Let Rn denote a ring-connected topology. In this paper, we address the routing and wavelength assignment problem for implementing the EH(s,t) communication pattern on Rn, where n=s+t+1. We design an embedding scheme. Based on the embedding scheme, a near-optimal wavelength assignment algorithm using 2s+t-2+⌊2t/3⌋ wavelengths is proposed. We also show that the wavelength assignment algorithm uses no more than an additional 25 percent of (or ⌊2t-1/3⌋) wavelengths, compared to the optimal wavelength assignment algorithm.

This paper presents a low-latency, low-cost architecture for computing square and cube roots in the fixed-point format. The proposed architecture is designed based on a non-iterative root calculation scheme to achieve fast computations. While previous non-iterative root calculators are restricted to a square-root operation due to the limitation of their mathematical property, the root computation is generalized in this paper to apply an approximation method to the non-iterative scheme. On top of that, a recurrent method is proposed to select parameters, which enables us to reduce the table size while keeping the maximum relative error value low. Consequently, the proposed root calculator can support both square and cube roots at the expense of small delay and low area overheads. This extension can be generalized to compute the nth roots, where n is a positive integer.

In the topologies for interconnected nodes, it is desirable to have a low degree and a small diameter. For the same number of nodes, a dual-cube topology has almost half the degree compared to a hypercube while increasing the diameter by just one. Hence, it is a promising topology for interconnection networks of massively parallel systems. We propose here a stochastic fault-tolerant routing algorithm to find a non-faulty path from a source node to a destination node in a dual-cube.

The Möbius cube is a variant of the hypercube. Its advantage is that it can connect the same number of nodes as a hypercube but with almost half the diameter of the hypercube. We propose an algorithm to solve the node-to-node disjoint paths problem in n-Möbius cubes in polynomial-order time of n. We provide a proof of correctness of the algorithm and estimate that the time complexity is O(n2) and the maximum path length is 3n-5.

This paper proposes an algorithm that solves the node-to-set disjoint paths problem in an n-Möbius cube in polynomial-order time of n. It also gives a proof of correctness of the algorithm as well as estimating the time complexity, O(n4), and the maximum path length, 2n-1. A computer experiment is conducted for n=1,2,...,31 to measure the average performance of the algorithm. The results show that the average time complexity is gradually approaching to O(n3) and that the maximum path lengths cannot be attained easily over the range of n in the experiment.

Recent small cube satellites use higher frequency bands such as Ku-band for higher throughput communications. This requires high-frequency link in an earth radio station as well. As one of the solutions, we propose usage of bidirectional radio-on-fiber link employing a wavelength multiplexing scheme. It was numerically shown that the response linearity of the electro-absorption modulator integrated laser (EML) is sufficient and that the spurious emissions are lower enough or can be reduced by the radio-frequency filters. From the frequency response and the single-sideband phase noise measurements, the EML was proved to be used in a radio-on-fiber system of the cube satellite earth station.

A graph G is two-disjoint-cycle-cover r-pancyclic if for any integer l satisfying r≤l≤|V(G)|-r, there exist two vertex-disjoint cycles C1 and C2 in G such that the lengths of C1 and C2 are |V(G)|-l and l, respectively, where |V(G)| denotes the total number of vertices in G. In particular, the graph G is two-disjoint-cycle-cover vertex r-pancyclic if for any two distinct vertices u and v of G, there exist two vertex-disjoint cycles C1 and C2 in G such that (i) C1 contains u, (ii) C2 contains v, and (iii) the lengths of C1 and C2 are |V(G)|-l and l, respectively, for any integer l satisfying r≤l≤|V(G)|-r. Moreover, G is two-disjoint-cycle-cover edge r-pancyclic if for any two vertex-disjoint edges (u,v) and (x,y) of G, there exist two vertex-disjoint cycles C1 and C2 in G such that (i) C1 contains (u,v), (ii) C2 contains (x,y), and (iii) the lengths of C1 and C2 are |V(G)|-l and l, respectively, for any integer l satisfying r≤l≤|V(G)|-r. In this paper, we first give Dirac-type sufficient conditions for general graphs to be two-disjoint-cycle-cover vertex/edge 3-pancyclic, and we also prove that the n-dimensional crossed cube CQn is two-disjoint-cycle-cover 4-pancyclic for n≥3, vertex 4-pancyclic for n≥5, and edge 6-pancyclic for n≥5.

In this paper, we investigate the fault-tolerant Hamiltonian problems of crossed cubes with a faulty path. More precisely, let P denote any path in an n-dimensional crossed cube CQn for n ≥ 5, and let V(P) be the vertex set of P. We show that CQn-V(P) is Hamiltonian if |V(P)|≤n and is Hamiltonian connected if |V(P)| ≤ n-1. Compared with the previous results showing that the crossed cube is (n-2)-fault-tolerant Hamiltonian and (n-3)-fault-tolerant Hamiltonian connected for arbitrary faults, the contribution of this paper indicates that the crossed cube can tolerate more faulty vertices if these vertices happen to form some specific types of structures.