We introduce a graphical calculus for multi-qutrit systems (the qutrit ZX-calculus) based on the framework of dagger symmetric monoidal categories. This graphical calculus consists of generators for building diagrams and rules for transforming diagrams, which is obviously different from the qubit ZX-calculus. As an application of the qutrit ZX-calculus, we give a graphical description of a (2, 3) threshold quantum secret sharing scheme. In this way, we prove the correctness of the secret sharing scheme in a intuitively clear manner instead of complicated linear algebraic operations.
Guangchun LUO Haifeng SUN Ke QIN Junbao ZHANG
The potential of infrastructureless vehicular ad hoc networks (VANETs) for providing multihop applications is quite significant. Although the Epidemic Routing protocol performs well in highly mobile and frequently disconnected VANETs with low vehicle densities or light packet traffic loads, its performance degrades greatly in environments of high vehicle density together with heavy packet traffic loads that create serious bandwidth contention and frequent collisions. We propose a new epidemic routing protocol in urban environments called Greedy Zone Epidemic Routing (GZER), in which the neighbors of a vehicle are divided into different zones according to their physical locations. Each vehicle maintains a summary vector (SV) of packets buffered locally and zone summary vectors (ZSVs) of all packets buffered in each zone. Whether the infection will be transmitted in each zone is decided by the difference between SV and ZSV. Simulation results show that the proposed GZER protocol outperforms the existing solutions significantly, especially in the environments of high vehicle densities together with heavy packet traffic loads.
Shingo HASEGAWA Shuji ISOBE Jun-ya IWAZAKI Eisuke KOIZUMI Hiroki SHIZUYA
Password-protected secret sharing (PPSS, for short) schemes were proposed by Bagherzandi, Jarecki, Saxena and Lu. In this paper, we consider another attack for PPSS schemes which is based on public parameters and documents. We show that the protocol proposed by Bagherzandi et al. is broken with the attack. We then propose an enhanced protocol which is secure against the attack.
Xiaojin ZHU Jingping BI Jianhang LIU
Video streaming uploading over vehicular ad hoc networks (VANETs) can support many interesting applications. Due to the high mobility and dynamic topology of VANETs, how to support video streaming using wireless communications between vehicles and road-side access points still remains an open issue. In this paper, we propose a geographical uploading scheme, called MPVUS, which uses the moving prediction to keep the stable forwarding and reduce the high link failure probability over VANETs. The scheme also decides the AP switch opportunity by traffic flow estimation, so as to adjust the forwarding direction timely to avoid the short-sighted switch decision. Simulation results demonstrate the effectiveness of our scheme, which can achieve good performance in terms of the start-up delay, playback interruption ratio and video frame distortion.
Jie REN Ling GAO Hai WANG Yan CHEN
The endurance time of smartphone still suffer from the limited battery capacity, and smartphone apps will increase the burden of the battery if they download large data over slow network. So how to manage the download tasks is an important work. To this end we propose a smartphone download strategy with low energy consumption which called CLSA (Concentrated Download and Low Power and Stable Link Selection Algorithm). The CLSA is intended to reduce the overhead of large data downloads by appropriate delay for the smartphone, and it based on three major factors: the current network situation, the length of download requests' queue and the local information of smartphone. We evaluate the CLSA using a music player implementation on ZTE V880 smartphone running the Android operation system, and compare it with the other two general download strategies, Minimum Delay and WiFi Only. Experiments show that our download algorithm can achieve a better trade-off between energy and delay than the other two.
Sangwook LEE Ji Eun SONG Wan Yeon LEE Young Woong KO Heejo LEE
For digital forensic investigations, the proposed scheme verifies the integrity of video contents in legacy surveillance camera systems with no built-in integrity protection. The scheme exploits video frames remaining in slack space of storage media, instead of timestamp information vulnerable to tampering. The scheme is applied to integrity verification of video contents formatted with AVI or MP4 files in automobile blackboxes.
Speeded up robust features (SURF) can detect/describe scale- and rotation-invariant features at high speed by relying on integral images for image convolutions. However, the time taken for matching SURF descriptors is still long, and this has been an obstacle for use in real-time applications. In addition, the matching time further increases in proportion to the number of features and the dimensionality of the descriptor. Therefore, we propose a fast matching method that rearranges the elements of SURF descriptors based on their entropies, divides SURF descriptors into sub-descriptors, and sequentially and analytically matches them to each other. Our results show that the matching time could be reduced by about 75% at the expense of a small drop in accuracy.
Headway irregularity not only increases average passenger waiting time but also causes additional energy consumption and more delay time. A real-time headway control model is proposed to maintain headway regularity in railway networks by adjusting the travel time on each segment for each train. The adjustment of travel time is based on a consensus algorithm. In the proposed consensus algorithm, the control law is obtained by solving the Riccati equation. The minimum running time on a segment is also considered. The computation time of the proposed method is analyzed and the analysis results show that it can satisfy the requirement on real-time operation. The proposed model is tested and the consensus trend of headways can be observed through simulation. The simulation results also demonstrate that the average passenger waiting time decreases from 52 to 50 seconds/passenger. Additionally, the delay time is reduced by 6.5% at least and energy consumption can be reduced by 0.1% at most after using the proposed method.
Given an edge-weighted tree with n vertices and a positive integer L, the length-constrained maximum-density path problem is to find a path of length at least L with maximum density in the tree. The density of a path is the sum of the weights of the edges in the path divided by the number of edges in the path. We present an O(n) time algorithm for the problem. The previously known algorithms run in O(nL) or O(n log n) time.
Hiroyuki HATANO Tomoya KITANI Masahiro FUJII Atsushi ITO Yu WATANABE Hironobu ONISHI Toru AOKI
For estimating user's location, Global Navigation Satellite System (GNSS) is very useful. Especially, Global Positioning System (GPS) by USA is very popular. A GPS receiver needs multiple satellites (usually 4 and more satellites). Propagation to the satellites needs line-of-sight. However, in urban area, there are many buildings. Received signals tend to become bad quality. Such signals are often called as non-line-of-sight (NLOS) or multipath signals. The problem is that the receiver cannot get line-of-sight signals from adequate number of the satellites coinstantaneously. This case leads to degradation of estimation quality or impossibility of estimation. In this paper, we will introduce a novel estimation algorithm, which can estimate own position with as low number of satellites as possible. The proposal achieves the estimation by only two satellites. The proposal also uses a traveling distance sensor which is often equipped on vehicles. By recorded satellite data, we will confirm our effectiveness.
Noriaki KAKIUCHI Kenichi SUNAGAWA Shunsuke KAMIJO
Pedestrian dead reckoning (PDR) is an effective positioning means that can be used in urban-canyon environments where the accuracy of GPS is significantly degraded. Magnetic disturbances caused by artificial objects affect the accuracy of positioning if the PDR system uses a magnetometer to estimate the heading direction. Conventional PDR systems consider magnetic disturbances as unpredictable error sources, but the error becomes predictable and removable if the amount of the deviation in the magnetic field can be calculated at any position. In this study, we propose a method to correct the heading direction by referring to a map of magnetic deviation. The experimental results show that our method reduced the error in the heading direction caused by magnetic disturbances. Our approach removed the error components that differ depending on the position, and consequently, the resultant trajectory represented better the shape of the true trajectory.
Sun-Mi PARK Ku-Young CHANG Dowon HONG Changho SEO
In several important applications, we often encounter with the computation of a Toeplitz matrix vector product (TMVP). In this work, we propose a k-way splitting method for a TMVP over any field F, which is a generalization of that over GF(2) presented by Hasan and Negre. Furthermore, as an application of the TMVP method over F, we present the first subquadratic space complexity multiplier over any finite field GF(pn) defined by an irreducible trinomial.
Masato UCHIDA Hideaki IIDUKA Isao SUGINO
In recent years, there has been growing interest in systems for sharing resources, which were originally used for personal purposes by individual users, among many unspecified users via a network. An example of such systems is a peer-to-peer (P2P) data storage system that enables users to share a portion of unused space in their own storage devices among themselves. In a recent paper on a P2P data storage system, the user behavior model was defined based on supply and demand functions that depend only on the storage space unit price in a virtual marketplace. However, it was implicitly assumed that other factors, such as unused space of storage devices possessed by users and additional storage space asked by users, did not affect the characteristics of the supply and demand functions. In addition, it was not clear how the values of parameters used in the user behavior model were determined. Therefore, in this paper, we modify the supply and demand functions and determine the values of their parameters by taking the above mentioned factors as well as the price structure of storage devices in a real marketplace into account. Moreover, we provide a numerical example to evaluate the social welfare realized by the P2P data storage system as a typical application of the modified supply and demand functions.
Primitive linear recurring sequences over rings are important in modern communication technology, and character sums of such sequences are used to analyze their statistical properties. We obtain a new upper bound for the character sum of primitive sequences of order n over the residue ring modulo a square-free odd integer m, and thereby improve previously known bound mn/2.
This paper briefly deals with a wide range of topics in information-theoretic cryptography. First, we focus on the results on symmetric-key encryption and authentication codes, since these protocols are fundamental in the field and well studied in the frameworks by Shannon and Simmons, respectively. Secondly, we explain several existing assumptions and security criteria whose merit mainly lies in realizing cryptographic protocols with short/weak shared secret-keys, correlated weak secret-keys, or no shared secrets. Thirdly, we consider research themes by three aspects for further development of information-theoretic cryptography. Finally, we refer to trends of technical approaches in information-theoretic cryptography and explain our recent results brought by using the approach.
At Eurocrypt 2011, Kiltz et al. presented two efficient authentication protocols for resource-constrained devices such as radio-frequency identification tags. Kiltz et al. proved that their protocols were provably secure against active attackers. However, they did not refer to the security against man-in-the-middle (MIM) attackers. In this paper, we analyze the security of the protocols against the MIM attacks and reveal the vulnerabilities. More concretely, we propose MIM attacks on them and evaluate authentication rounds required in these attacks precisely. We assume that the tag and reader share a 2l-bit secret key. The expected number of authentication rounds to recover the secret information in the first and second protocol is at most 2l+2 and 4l+4, respectively. These attacks do not contradict the proof of security since the MIM attack is located outside the attack model that Kiltz et al. considered.
Noboru BABAGUCHI Yuta NAKASHIMA
Our society has been getting more privacy-sensitive. Diverse information is given by users to information and communications technology (ICT) systems such as IC cards benefiting them. The information is stored as so-called big data, and there is concern over privacy violation. Visual information such as images and videos is also considered privacy-sensitive. The growing deployment of surveillance cameras and social network services has caused a privacy problem of information given from various sensors. To protect privacy of subjects presented in visual information, their face or figure is processed by means of pixelization or blurring. As image analysis technologies have made considerable progress, many attempts to automatically process flexible privacy protection have been made since 2000, and utilization of privacy information under some restrictions has been taken into account in recent years. This paper addresses the recent progress of privacy protection for visual information, showing our research projects: PriSurv, Digital Diorama (DD), and Mobile Privacy Protection (MPP). Furthermore, we discuss Harmonized Information Field (HIFI) for appropriate utilization of protected privacy information in a specific area.
Soohyun JANG Jaeyoung ROH Seongjoo LEE Yunho JUNG
In this letter, a robust time synchronization algorithm is proposed for MIMO-OFDM based WLAN systems. IEEE 802.11ac MIMO-OFDM WLAN standard specifies that the preamble with cyclic shift diversity (CSD) scheme is used for time and frequency synchronization. However, since the CSD scheme introduces multiple cross-correlation peaks at the receiver, serious performance degradation appears if the conventional cross-correlation based algorithm is applied. In the proposed algorithm, the time synchronization error due to multiple peaks is compensated by adding the cross-correlation value to its reverse cyclic-shifted version. Simulation results show that the proposed algorithm achieves an SNR gain of 1.5 to 4.5dB for the synchronization failure rate of 10-2 compared with the existing algorithms.
In this paper, we posit that extension of SDN to support deeply and flexibly programmable, software-defined data plane significantly enhance SDN and NFV and their interaction in terms of (1) enhanced interaction between applications and networks, (2) optimization of network functions, and (3) rapid development of new network protocols. All of these benefits are expected to contribute to improving the quality of diversifying communication networks and services. We identify three major technical challenges for enabling software-defined data plane as (1) ease of programming, (2) reasonable and predictable performance and (3) isolation among multiple concurrent logics. We also promote application-driving thinking towards defining software defined data-plane. We briefly introduce our project FLARE and its related technologies and review four use cases of flexible and deeply programmable data plane.