This survey summarizes the state-of-the-art research on network coding, mainly focusing on its applications to computer networking. Network coding generalizes traditional store-and-forward routing techniques by allowing intermediate nodes in networks to encode several received packets into a single coded packet before forwarding. Network coding was proposed in 2000, and since then, it has been studied extensively in the field of computer networking. In this survey, we first summarize linear network coding and provide a taxonomy of network coding research, i.e., the network coding design problem and network coding applications. Moreover, the latter is subdivided into throughput/capacity enhancement, robustness enhancement, network tomography, and security. We then discuss the fundamental characteristics of network coding and diverse applications of network coding in details, following the above taxonomy.

Non-Interactive Key Exchange (NIKE) is a cryptographic primitive that allows two users to compute a shared key without any interaction. The Diffie-Hellman key exchange scheme is probably the most well-known example of a NIKE scheme. Freire et al. (PKC 2013) defined four security notions for NIKE schemes, and showed implications among them. In these notions, we consider an adversary that is challenged to distinguish a shared key of a new pair of users from a random value, using only its knowledge of keys shared between other pairs of users. To take into account side-channel attacks such as tampering and fault-injection attacks, Bellare and Kohno (Eurocrypt 2003) formalized related-key attacks (RKA), where stronger adversaries are considered. In this paper, we introduce four RKA security notions for NIKE schemes. In these notions, we consider an adversary that can also manipulate the secret keys of users and obtain shared keys computed under the modified secret keys. We also show implications and separations among the security notions, and prove that one of the NIKE schemes proposed by Freire et al. is secure in the strongest RKA sense in the random oracle model under the Double Strong Diffie-Hellman (DSDH) assumption over the group of signed quadratic residues, which is implied by the factoring assumption.

In remote control, efficient compression or representation of control signals is essential to send them through rate-limited channels. For this purpose, we propose an approach of sparse control signal representation using the compressive sampling technique. The problem of obtaining sparse representation is formulated by cardinality-constrained 2 optimization of the control performance, which is reducible to 1-2 optimization. The low rate random sampling employed in the proposed method based on the compressive sampling, in addition to the fact that the 1-2 optimization can be effectively solved by a fast iteration method, enables us to generate the sparse control signal with reduced computational complexity, which is preferable in remote control systems where computation delays seriously degrade the performance. We give a theoretical result for control performance analysis based on the notion of restricted isometry property (RIP). An example is shown to illustrate the effectiveness of the proposed approach via numerical experiments.

In this paper, we consider network monitoring techniques to estimate communication qualities in wide-area mobile networks, where an enormous number of heterogeneous components such as base stations, routers, and servers are deployed. We assume that average delays of neighboring base stations are comparable, most of servers have small delays, and delays at core routers are negligible. Under these assumptions, we propose Heterogeneous Delay Tomography (HDT) to estimate the average delay at each network component from end-to-end round trip times (RTTs) between mobile terminals and servers. HDT employs a crowdsourcing approach to collecting RTTs, where voluntary mobile users report their empirical RTTs to a data collection center. From the collected RTTs, HDT estimates average delays at base stations in the Graph Fourier Transform (GFT) domain and average delays at servers, by means of Compressed Sensing (CS). In the crowdsourcing approach, the performance of HDT may be degraded when the voluntary mobile users are unevenly distributed. To resolve this problem, we further extend HDT by considering the number of voluntary mobile users. With simulation experiments, we evaluate the performance of HDT.

The concept of threshold public key encryption (TPKE) with the special property called key re-splittability (re-splittable TPKE, for short) was introduced by Hanaoka et al. (CT-RSA 2012), and used as one of the building blocks for constructing their proxy re-encryption scheme. In a re-splittable TPKE scheme, a secret key can be split into a set of secret key shares not only once, but also multiple times, and the security of the TPKE scheme is guaranteed as long as the number of corrupted secret key shares under the same splitting is smaller than the threshold. In this paper, we show several new constructions of a re-splittable TPKE scheme by extending the previous (ordinary) TPKE schemes. All of our proposed schemes are based on discrete logarithm (DL)-type assumptions. Therefore, our results suggest that key re-splittability is a very natural property for DL-type TPKE schemes.

A fault-tolerant aggregate signature (FT-AS) scheme is a variant of an aggregate signature scheme with the additional functionality to trace signers that create invalid signatures in case an aggregate signature is invalid. Several FT-AS schemes have been proposed so far, and some of them trace such rogue signers in multi-rounds, i.e., the setting where the signers repeatedly send their individual signatures. However, it has been overlooked that there exists a potential attack on the efficiency of bandwidth consumption in a multi-round FT-AS scheme. Since one of the merits of aggregate signature schemes is the efficiency of bandwidth consumption, such an attack might be critical for multi-round FT-AS schemes. In this paper, we propose a new multi-round FT-AS scheme that is tolerant of such an attack. We implement our scheme and experimentally show that it is more efficient than the existing multi-round FT-AS scheme if rogue signers randomly create invalid signatures with low probability, which for example captures spontaneous failures of devices in IoT systems.

To localize an unknown wave source in non-line-of-sight environments, a wave source localization scheme using multiple unmanned-aerial-vehicles (UAVs) is proposed. In this scheme, each UAV estimates the direction-of-arrivals (DoAs) of received signals and the wave source is localized from the estimated DoAs by means of maximum likelihood estimation. In this study, by extending the concept of this scheme, we propose a novel wave source localization scheme using a single UAV. In the proposed scheme, the UAV moves on the path comprising multiple measurement points and the wave source is sequentially localized from DoA distributions estimated at these measurement points. At each measurement point, with a moving path planning algorithm, the UAV determines the next measurement point from the estimated DoA distributions and measurement points that the UAV has already visited. We consider two moving path planning algorithms, and validate the proposed scheme through simulation experiments.

In the IEEE 802.11 MAC protocol, access points (APs) are given the same priority as wireless terminals in terms of acquiring the wireless link, even though they aggregate several downlink flows. This feature leads to a serious throughput degradation of downlink flows, compared with uplink flows. In this paper, we propose a dynamic contention window control scheme for the IEEE 802.11e EDCA-based wireless LANs, in order to achieve fairness between uplink and downlink TCP flows while guaranteeing QoS requirements for real-time traffic. The proposed scheme first determines the minimum contention window size in the best-effort access category at APs, based on the number of TCP flows. It then determines the minimum and maximum contention window sizes in higher priority access categories, such as voice and video, so as to guarantee QoS requirements for these real-time traffic. Note that the proposed scheme does not require any modification to the MAC protocol at wireless terminals. Through simulation experiments, we show the effectiveness of the proposed scheme.

In IEEE 802.11 wireless local area networks (WLANs), contention window (CW) in carrier sense multiple access with collision avoidance (CSMA/CA) is one of the most important techniques determining throughput performance. In this paper, we propose a novel CW control scheme to achieve high transmission efficiency in dense user environments. Whereas the standard CSMA/CA mechanism. Employs an adaptive CW control scheme that responds to the number of retransmissions, the proposed scheme uses the optimum CW size, which is shown to be a function of the number of terminal stations. In the proposed scheme, the number of terminal stations are estimated from the probability of packet collision measured at an access point (AP). The optimum CW size is then derived from a theoretical analysis based on a Markov chain model. We evaluate the performance of the proposed scheme with simulation experiments and show that it significantly improves the throughput performance.

Fault-tolerant aggregate signature (FT-AS) is a special type of aggregate signature that is equipped with the functionality for tracing signers who generated invalid signatures in the case an aggregate signature is detected as invalid. In existing FT-AS schemes (whose tracing functionality requires multi-rounds), a verifier needs to send a feedback to an aggregator for efficiently tracing the invalid signer(s). However, in practice, if this feedback is not responded to the aggregator in a sufficiently fast and timely manner, the tracing process will fail. Therefore, it is important to estimate whether this feedback can be responded and received in time on a real system. In this work, we measure the total processing time required for the feedback by implementing an existing FT-AS scheme, and evaluate whether the scheme works without problems in real systems. Our experimental results show that the time required for the feedback is 605.3 ms for a typical parameter setting, which indicates that if the acceptable feedback time is significantly larger than a few hundred ms, the existing FT-AS scheme would effectively work in such systems. However, there are situations where such feedback time is not acceptable, in which case the existing FT-AS scheme cannot be used. Therefore, we further propose a novel FT-AS scheme that does not require any feedback. We also implement our new scheme and show that a feedback in this scheme is completely eliminated but the size of its aggregate signature (affecting the communication cost from the aggregator to the verifier) is 144.9 times larger than that of the existing FT-AS scheme (with feedbacks) for a typical parameter setting, and thus has a trade-off between the feedback waiting time and the communication cost from the verifier to the aggregator with the existing FT-AS scheme.

TCP/IP is a key technology in the next generation mobile communication networks. A significant amount of wireless traffic will be carried in the Internet, and wireless connections will have to share network resources with wired connections. However, in a wireless network environment, TCP suffers significant throughput degradation due to the lossy characteristic of a wireless link. Therefore, to design the next generation mobile networks, it is necessary to know how much the wireless connection suffers from the degradation in comparison to the wired connection. In this paper, we discuss the fairness issue between TCP connections over wireless and wired links, and theoretically analyze the fairness of throughput between TCP over wireless link with ARQ (Automatic Repeat reQuest)-based link layer error recovery and TCP over error-free wired link. We validate our analysis by comparing the numerical results obtained from the analysis with the results obtained from computer simulation. The numerical results show that the fairness is sensitive to network propagation delay and variation rapidity of wireless link characteristic. We also obtain the theoretical lower bound of fairness.

In wireless links between ground stations and UAVs (Unmanned Aerial Vehicles), wireless signals may be attenuated by obstructions such as buildings. A three-dimensional RSS (Received Signal Strength) map (3D-RSS map), which represents a set of RSSs at various reception points in a three-dimensional area, is a promising geographical database that can be used to design reliable ground-to-air wireless links. The construction of a 3D-RSS map requires higher computational complexity, especially for a large 3D area. In order to sequentially estimate a 3D-RSS map from partial observations of RSS values in the 3D area, we propose a graph Laplacian-based sequential smooth estimator. In the proposed estimator, the 3D area is divided into voxels, and a UAV observes the RSS values at the voxels along a predetermined path. By considering the voxels as vertices in an undirected graph, a measurement graph is dynamically constructed using vertices from which recent observations were obtained and their neighboring vertices, and the 3D-RSS map is sequentially estimated by performing graph Laplacian regularized least square estimation.

In this paper, we propose a similarity searchable encryption in the symmetric key setting for the weighted Euclidean distance, by extending the functional encryption scheme for inner product proposed by Bishop et al. [4]. Our scheme performs predetermined encoding independently of vectors x and y, and it obtains the weighted Euclidean distance between the two vectors while they remain encrypted.

In the mobile Internet, a handover brings significant performance degradation of TCP due to bursty packet losses during handover processing. In this paper, we propose a new bandwidth control for improving the TCP performance. In the proposed system, when a mobile node changes its accessing base station, an intermediate router suppresses an available bandwidth to the corresponding TCP flow. Because suppressing the bandwidth results in reducing mis-forwarded packets to the old base station, the bursty packet losses can be avoided. In the hierarchical mobile network structure, which is recently developed in order to realize micro-mobility protocol, all packets transferred to mobile nodes are converged to several gateways such as mobility anchor points (MAP) in hierarchical Mobile IPv6 (HMIPv6). Therefore, the proposed system is suited to the hierarchical structure because it can be easily implemented at such gateways. Computer simulation results show that the proposed system can improve the TCP performance degradation especially in a situation where handovers frequently occur.

Network tomography is an inference technique for internal network characteristics such as link loss rate and link delay from end-to-end measurements. In this paper, we consider network tomography for link loss rates, which is referred to as loss tomography. We propose a loss tomography scheme with bitwise operation-based in-network processing. Intermediate nodes generate coded packets by performing bitwise-operations on received packets so as to embed information about paths along which those packets have been transmitted. The coded packets are then forwarded to downstream nodes. In this way, receiver nodes obtain information about paths along which packets are transmitted successfully. Moreover, we show a recursion to compute the likelihood function of path loss rates, which can be utilized in estimating link loss rates from path loss information.