Manabu MIKAMI Kohei MOTO Koichi SERIZAWA Hitoshi YOSHINO
Fifth generation mobile communication system (5G) mobile operators need to explore new use cases and/or applications together with vertical industries, the industries that are potential users of 5G, in order to fully exploit the new 5G capabilities in terms of its application. Vehicle-to-Everything (V2X) communications for platooning are considered to be one of new 5G use cases requiring low-latency and ultra-reliability are required. This paper presents our field trial of dynamic mode switching for 5G New Radio (NR) based V2X sidelink communications towards application to truck platooning. The authors build a field trial environment, for V2X communications of truck platooning, with actual large-size trucks and a prototype system employing 5G NR technologies, and performed some field trials in rural areas. In this paper, we introduce the 5G NR-V2X prototype system. Its most distinctive characteristic is that the prototype system is equipped with vehicle-to-vehicle (V2V) Direct communication radio interface (i.e., sidelink), in addition to the traditional radio interfaces between base station (BS) and user equipment (UE), i.e., downlink and uplink. Moreover, it is also most distinctive that the sidelink (SL) interface supports a new function of dynamic mode switching between two modes of BS In-Coverage mode (SL Mode-1) and BS Out-of-Coverage mode (SL Mode-2) in order to achieve seamless V2V communications between BS in-coverage area and BS out-of-coverage area. Then, we present the evaluation results on over-the-air latency performance on the V2V Direct communication of the prototype using SL dynamic mode switching with two experimental base station antenna sites in a public express highway environment towards application to truck platooning. The results demonstrate that our developed the SL dynamic mode switching achieves the seamless V2V Direct communications between in-coverage area and out-of-coverage area.
Yi LU Keisuke HARA Keisuke TANAKA
Receiver selective opening (RSO) attack for public key encryption (PKE) captures a situation where one sender sends messages to multiple receivers, an adversary can corrupt a set of receivers and get their messages and secret keys. Security against RSO attack for a PKE scheme ensures confidentiality of other uncorrupted receivers' ciphertexts. Among all of the RSO security notions, simulation-based RSO security against chosen ciphertext attack (SIM-RSO-CCA security) is the strongest notion. In this paper, we explore constructions of SIM-RSO-CCA secure PKE from various computational assumptions. Toward this goal, we show that a SIM-RSO-CCA secure PKE scheme can be constructed based on an IND-CPA secure PKE scheme and a designated-verifier non-interactive zero-knowledge (DV-NIZK) argument satisfying one-time simulation soundness. Moreover, we give the first construction of DV-NIZK argument satisfying one-time simulation soundness. Consequently, through our generic construction, we obtain the first SIM-RSO-CCA secure PKE scheme under the computational Diffie-Hellman (CDH) or learning parity with noise (LPN) assumption.
In this paper, we present an algorithm that counts the number of empty quadrilaterals whose corners are chosen from a given set S of n points in general position. Our algorithm can separately count the number of convex or non-convex empty quadrilaterals in O(T) time, where T denotes the number of empty triangles in S. Note that T varies from Ω(n2) and O(n3) and the expected value of T is known to be Θ(n2) when the n points in S are chosen uniformly and independently at random from a convex and bounded body in the plane. We also show how to enumerate all convex and/or non-convex empty quadrilaterals in S in time proportional to the number of reported quadrilaterals, after O(T)-time preprocessing.
Yanjun LI Haibin KAN Jie PENG Chik How TAN Baixiang LIU
Permutation polynomials and their compositional inverses are crucial for construction of Maiorana-McFarland bent functions and their dual functions, which have the optimal nonlinearity for resisting against the linear attack on block ciphers and on stream ciphers. In this letter, we give the explicit compositional inverse of the permutation binomial $f(z)=z^{2^{r}+2}+alpha zinmathbb{F}_{2^{2r}}[z]$. Based on that, we obtain the dual of monomial bent function $f(x)={ m Tr}_1^{4r}(x^{2^{2r}+2^{r+1}+1})$. Our result suggests that the dual of f is not a monomial any more, and it is not always EA-equivalent to f.
Hiroki OKADA Atsushi TAKAYASU Kazuhide FUKUSHIMA Shinsaku KIYOMOTO Tsuyoshi TAKAGI
We propose a new lattice-based digital signature scheme MLWRSign by modifying Dilithium, which is one of the second-round candidates of NIST's call for post-quantum cryptographic standards. To the best of our knowledge, our scheme MLWRSign is the first signature scheme whose security is based on the (module) learning with rounding (LWR) problem. Due to the simplicity of the LWR, the secret key size is reduced by approximately 30% in our scheme compared to Dilithium, while achieving the same level of security. Moreover, we implemented MLWRSign and observed that the running time of our scheme is comparable to that of Dilithium.
Masayuki TEZUKA Keisuke TANAKA
Redactable signature allows anyone to remove parts of a signed message without invalidating the signature. The need to prove the validity of digital documents issued by governments is increasing. When governments disclose documents, they must remove private information concerning individuals. Redactable signature is useful for such a situation. However, in most redactable signature schemes, to remove parts of the signed message, we need pieces of information for each part we want to remove. If a signed message consists of ℓ elements, the number of elements in an original signature is at least linear in ℓ. As far as we know, in some redactable signature schemes, the number of elements in an original signature is constant, regardless of the number of elements in a message to be signed. However, these constructions have drawbacks in that the use of the random oracle model or generic group model. In this paper, we construct an efficient redactable signature to overcome these drawbacks. Our redactable signature is obtained by combining set-commitment proposed in the recent work by Fuchsbauer et al. (JoC 2019) and digital signatures.
Manabu MIKAMI Koichi SERIZAWA Kohei MOTO Hitoshi YOSHINO
Fifth generation mobile communication system (5G) mobile operators need to explore new use cases and/or applications together with vertical industries, the industries which are potential users of 5G, in order to fully exploit the new 5G capabilities in terms of its application. Vehicular communications for platooning are considered to be one of new use cases of 5G whose low-latency and ultra-reliability are required. This paper presents our field evaluations on latency and reliability performance of 5G V2V Direct communication towards application to truck platooning. The authors build a field experimental environment, for V2X communications of truck platooning, with actual large-size trucks and a prototype system employing 5G New Radio (NR) technologies, and performed some field experiments in rural areas. In this paper, we introduce the 5G NR-V2X prototype system. Its most distinctive feature is that the prototype system is equipped with V2V Direct communication radio interface (i.e., sidelink), in addition to the traditional radio interfaces between BS and UE (i.e., downlink and uplink). Then, we present the field evaluation results of radio propagation environment results and over-the-air transmission performance of latency and reliability characteristics on the V2V Direct communication of the prototype in real public express highway environment including tunnel area as well as tunnel outside area, in order to assess 5G NR-V2X system applying to truck platooning. The radio propagation and the latency performance evaluation results clarify that the latency performance is degraded due to Hybrid Automatic Repeat reQuest (HARQ) retransmission at the outside of tunnel more possibly than the inside of tunnel, since larger path loss values can be observed at the outside of tunnel than the inside of tunnel, in V2V Direct communications of truck platooning. The over-the-air latency and reliability evaluation results confirm that it is important to set an appropriate maximum number of HARQ retransmissions since there is a trade-off problem in order to realize low latency and high reliability simultaneously.
Sakae NAGAOKA Mark BROWN Daniel DELAHAYE
Air traffic management (ATM) systems around the world are being modernized to accommodate shifts towards performance- and trajectory-based operations. These shifts will require new indices for safety, efficiency and complexity. The authors have been developing an index for evaluating air traffic control (ATC) difficulty that utilizes the relative positions and velocity vectors of aircraft pairs as input data. Prior to practical application of the index, it is necessary to understand the effects of input data error, i.e. errors in the positions and velocities of a pair of aircraft, on the estimated difficulty value. Two sensitivity analyses were therefore performed for a pair of aircraft cruising at constant speeds on intersecting linear tracks at the same altitude. Sensitivity analysis examines how uncertainty in inputs relates to uncertainty in outputs. Firstly, an analysis of propagation error was carried out. The formula of the propagation error at a certain point was derived based on the assumed input error, and the distribution of propagation error was investigated for all possible situations and compared with the distribution of difficulty values to clarify its characteristics. Secondly, a sensitivity analysis based on variance was carried out that evaluated the effect of each input parameter using a conditional variance value called the Sobol indices. Using a Monte Carlo method, we investigated the effect of each input parameter on the calculated difficulty value for all possible situations of aircraft pairs on intersecting trajectories. As a result, it was found that the parameter that most affects the difficulty value is the intersection angle of the trajectories.
Rei NAKAGAWA Satoshi OHZAHATA Ryo YAMAMOTO Toshihiko KATO
Recently, information centric network (ICN) has attracted attention because cached content delivery from router's cache storage improves quality of service (QoS) by reducing redundant traffic. Then, adaptive video streaming is applied to ICN to improve client's quality of experience (QoE). However, in the previous approaches for the cache control, the router implicitly caches the content requested by a user for the other users who may request the same content subsequently. As a result, these approaches are not able to use the cache effectively to improve client's QoE because the cached contents are not always requested by the other users. In addition, since the previous cache control does not consider network congestion state, the adaptive bitrate (ABR) algorithm works incorrectly and causes congestion, and then QoE degrades due to unnecessary congestion. In this paper, we propose an explicit cache placement notification for congestion-aware adaptive video streaming over ICN (CASwECPN) to mitigate congestion. CASwECPN encourages explicit feedback according to the congestion detection in the router on the communication path. While congestion is detected, the router caches the requested content to its cache storage and explicitly notifies the client that the requested content is cached (explicit cache placement and notification) to mitigate congestion quickly. Then the client retrieve the explicitly cached content in the router detecting congestion according to the general procedures of ICN. The simulation experiments show that CASwECPN improves both QoS and client's QoE in adaptive video streaming that adjusts the bitrate adaptively every video segment download. As a result, CASwECPN effectively uses router's cache storage as compared to the conventional cache control policies.
Sungho PARK Youngjun KIM Hyungoo CHOI Yeunwoong KYUNG Jinwoo PARK
HTTP Distributed Denial of Service (DDoS) flooding attack aims to deplete the connection resources of a targeted web server by transmitting a massive amount of HTTP request packets using botnets. This type of attack seriously deteriorates the service quality of the web server by tying up its connection resources and uselessly holds up lots of network resources like link capacity and switching capability. This paper proposes a defense method for mitigating HTTP DDoS flooding attack based on software-defined networking (SDN). It is demonstrated in this paper that the proposed method can effectively defend the web server and preserve network resources against HTTP DDoS flooding attacks.
Hironori KIYA Katsuki OHTO Hirotaka ONO
DAIHINMIN, which means Grand Pauper, is a popular playing-card game in Japan. TANHINMIN is a simplified variant of DAIHINMIN, which was proposed by Nishino in 2007 in order to investigate the mathematical properties of DAIHINMIN. In this paper, we consider a 2-player generalized TANHINMIN, where the deck size is arbitrary n. We present a linear-time algorithm that determines which player has a winning strategy after all cards are distributed to the players.
Takashi HORIYAMA Shin-ichi NAKANO Toshiki SAITOH Koki SUETSUGU Akira SUZUKI Ryuhei UEHARA Takeaki UNO Kunihiro WASA
Given a set P of n points on which facilities can be placed and an integer k, we want to place k facilities on some points so that the minimum distance between facilities is maximized. The problem is called the k-dispersion problem. In this paper, we consider the 3-dispersion problem when P is a set of points on a plane (2-dimensional space). Note that the 2-dispersion problem corresponds to the diameter problem. We give an O(n) time algorithm to solve the 3-dispersion problem in the L∞ metric, and an O(n) time algorithm to solve the 3-dispersion problem in the L1 metric. Also, we give an O(n2 log n) time algorithm to solve the 3-dispersion problem in the L2 metric.
Chuzo IWAMOTO Tatsuaki IBUSUKI
The art gallery problem is to find a set of guards who together can observe every point of the interior of a polygon P. We study a chromatic variant of the problem, where each guard is assigned one of k distinct colors. The chromatic art gallery problem is to find a guard set for P such that no two guards with the same color have overlapping visibility regions. We study the decision version of this problem for orthogonal polygons with r-visibility when the number of colors is k=2. Here, two points are r-visible if the smallest axis-aligned rectangle containing them lies entirely within the polygon. In this paper, it is shown that determining whether there is an r-visibility guard set for an orthogonal polygon with holes such that no two guards with the same color have overlapping visibility regions is NP-hard when the number of colors is k=2.
Hiroshi FUJIWARA Ken ENDO Hiroaki YAMAMOTO
In the bin packing problem, we are asked to place given items, each being of size between zero and one, into bins of capacity one. The goal is to minimize the number of bins that contain at least one item. An online algorithm for the bin packing problem decides where to place each item one by one when it arrives. The asymptotic approximation ratio of the bin packing problem is defined as the performance of an optimal online algorithm for the problem. That value indicates the intrinsic hardness of the bin packing problem. In this paper we study the bin packing problem in which every item is of either size α or size β (≤ α). While the asymptotic approximation ratio for $alpha > rac{1}{2}$ was already identified, that for $alpha leq rac{1}{2}$ is only partially known. This paper is the first to give a lower bound on the asymptotic approximation ratio for any $alpha leq rac{1}{2}$, by formulating linear optimization problems. Furthermore, we derive another lower bound in a closed form by constructing dual feasible solutions.
In a convex grid drawing of a plane graph, all edges are drawn as straight-line segments without any edge-intersection, all vertices are put on grid points and all facial cycles are drawn as convex polygons. A plane graph G has a convex drawing if and only if G is internally triconnected, and an internally triconnected plane graph G has a convex grid drawing on an (n-1)×(n-1) grid if either G is triconnected or the triconnected component decomposition tree T(G) of G has two or three leaves, where n is the number of vertices in G. An internally triconnected plane graph G has a convex grid drawing on a 2n×2n grid if T(G) has exactly four leaves. Furthermore, an internally triconnected plane graph G has a convex grid drawing on a 6n×n2 grid if T(G) has exactly five leaves. In this paper, we show that an internally triconnected plane graph G has a convex grid drawing on a 20n×16n grid if T(G) has exactly five leaves. We also present an algorithm to find such a drawing in linear time. This is the first algorithm that finds a convex grid drawing of such a plane graph G in a grid of O(n2) size.
Masayuki FUKUMITSU Shingo HASEGAWA
The Schnorr signature is one of the representative signature schemes and its security was widely discussed. In the random oracle model (ROM), it is provable from the DL assumption, whereas there is negative circumstantial evidence in the standard model. Fleischhacker, Jager, and Schröder showed that the tight security of the Schnorr signature is unprovable from a strong cryptographic assumption, such as the One-More DL (OM-DL) assumption and the computational and decisional Diffie-Hellman assumption, in the ROM via a generic reduction as long as the underlying cryptographic assumption holds. However, it remains open whether or not the impossibility of the provable security of the Schnorr signature from a strong assumption via a non-tight and reasonable reduction. In this paper, we show that the security of the Schnorr signature is unprovable from the OM-DL assumption in the non-programmable ROM as long as the OM-DL assumption holds. Our impossibility result is proven via a non-tight Turing reduction.
Akinori HOSOYAMADA Tetsu IWATA
We provide a formal proof for the indifferentiability of SKINNY-HASH internal function from a random oracle. SKINNY-HASH is a family of sponge-based hash functions that use functions (instead of permutations) as primitives, and it was selected as one of the second round candidates of the NIST lightweight cryptography competition. Its internal function is constructed from the tweakable block cipher SKINNY. The construction of the internal function is very simple and the designers claim n-bit security, where n is the block length of SKINNY. However, a formal security proof of this claim is not given in the original specification of SKINNY-HASH. In this paper, we formally prove that the internal function of SKINNY-HASH has n-bit security, i.e., it is indifferentiable from a random oracle up to O(2n) queries, substantiating the security claim of the designers.
Nobuhide NONAKA Kazushi MURAOKA Tatsuki OKUYAMA Satoshi SUYAMA Yukihiko OKUMURA Takahiro ASAI Yoshihiro MATSUMURA
In order to enhance the fifth generation (5G) mobile communication system further toward 5G Evolution, high bit-rate transmission using high SHF bands (28GHz or EHF bands) should be more stable even in high-mobility environments such as high speed trains. Of particular importance, dynamic changes in the beam direction and the larger Doppler frequency shift can degrade transmission performances in such high frequency bands. Thus, we conduct the world's first 28 GHz-band 5G experimental trial on an actual Shinkansen running at a speed of 283km/h in Japan. This paper introduces the 28GHz-band experimental system used in the 5G experimental trial using the Shinkansen, and then it presents the experimental configuration in which three base stations (BSs) are deployed along the Tokaido Shinkansen railway and a mobile station is located in the train. In addition, transmission performances measured in this ultra high-mobility environment, show that a peak throughput of exceeding 1.0Gbps and successful consecutive BS connection among the three BSs.
Tatsuki OKUYAMA Nobuhide NONAKA Satoshi SUYAMA Yukihiko OKUMURA Takahiro ASAI
The fifth-generation (5G) mobile communications system initially introduced massive multiple-input multiple-output (M-MIMO) with analog beamforming (BF) to compensate for the larger path-loss in millimeter-wave (mmW) bands. To solve a coverage issue and support high mobility of the mmW bands, base station (BS) cooperation technologies have been investigated in high-mobility environments. However, previous works assume one mobile station (MS) scenario and analog BF that does not suppress interference among MSs. In order to improve system performance in the mmW bands, fully digital BF that includes digital precoding should be employed to suppress the interference even when MSs travel in high mobility. This paper proposes two mmW BS cooperation technologies that are inter-baseband unit (inter-BBU) and intra-BBU cooperation for the fully digital BF. The inter-BBU cooperation exploits two M-MIMO antennas in two BBUs connected to one central unit by limited-bandwidth fronthaul, and the intra-BBU cooperates two M-MIMO antennas connected to one BBU with Doppler frequency shift compensation. This paper verifies effectiveness of the BS cooperation technologies by both computer simulations and outdoor experimental trials. First, it is shown that that the intra-BBU cooperation can achieve an excellent transmission performance in cases of two and four MSs moving at a velocity of 90km/h by computer simulations. Second, the outdoor experimental trials clarifies that the inter-BBU cooperation maintains the maximum throughput in a wider area than non-BS cooperation when only one MS moves at a maximum velocity of 120km/h.
Naoto TSUMACHI Masaya SHIBAYAMA Ryuji KOBAYASHI Issei KANNO Yasuhiro SUEGARA
In March 2020, the 5th generation mobile communication system (5G) was launched in Japan. Frequency bands of 3.7GHz, 4.5GHz and 28GHz were allocated for 5G services, and the 5G use cases fall into three broad categories: Enhanced Mobile Broadband (eMBB), Massive Machine Type Communication (mMTC) and Ultra-Reliable Low Latency Communication (URLLC). The use cases and services that take advantage of the characteristics of each category are expected to be put to practical use, and experiments of practical use are underway. This paper introduces and demonstrates a touchless gate that can identify, authenticate and allow passage through the gate by using these features and 5G beam tracking to estimate location by taking advantage of the low latency of 5G and the straightness of the 28GHz band radio wave and its resistance to spreading. Since position estimation error due to reflected waves and other factors has been a problem, we implement an algorithm that tracks the beam and estimates the user's line of movement, and by using an infrared sensor, we made it possible to identify the gate through which the user passes with high probability. We confirmed that the 5G touchless gate is feasible for gate passage. In addition, we demonstrate that a new service based on high-speed high-capacity communication is possible at gate passage by taking advantage of the wide bandwidth of the 28GHz band. Furthermore, as a use case study of the 5G touchless gate, we conducted a joint experiment with an airline company.