2022 Vol. 59 No. 8
2022, 59(8): 1637-1638.
DOI: 10.7544/issn1000-1239.qy20220801
2022, 59(8): 1639-1652.
DOI: 10.7544/issn1000-1239.20220053
Abstract：
Numerical label noise in regression may misguide the model training and weaken the generalization ability. As a popular technique, noise filtering could reduce the noise level by removing mislabeled samples, but it could rarely ensure a better generalization performance. Some filters care about the noise level so much that many noise-free samples are also removed. Although the existing sample selection framework could balance the number of removals and the noise level, it is too complicated to be understood intuitively and applied in reality. A generalization error bound is proposed for data with numerical label noise according to the learning theory in the noise-free regression task. It clarifies the key data factors, including data size and noise level, that affect the generalization ability. On this basis, an interpretable noise filtering framework is proposed, the goal of which is to minimize the noise level with a low cost of sample removal. Meanwhile, the relationship between noise and key indicators (center and radius) of the covering interval is theoretically analyzed for noise estimation. Then a relative noise estimator is proposed. The relative noise filtering (RNF) algorithm is designed by integrating the proposed framework with the estimator. The effectiveness of RNF is verified on the benchmark datasets and age estimation dataset. Experimental results show that RNF can be adapted to various types of noises and significantly improve the generalization ability of the regression model. On the age estimation dataset, RNF detects some samples with label noises. It effectively improves the data quality and model prediction performance.
Numerical label noise in regression may misguide the model training and weaken the generalization ability. As a popular technique, noise filtering could reduce the noise level by removing mislabeled samples, but it could rarely ensure a better generalization performance. Some filters care about the noise level so much that many noise-free samples are also removed. Although the existing sample selection framework could balance the number of removals and the noise level, it is too complicated to be understood intuitively and applied in reality. A generalization error bound is proposed for data with numerical label noise according to the learning theory in the noise-free regression task. It clarifies the key data factors, including data size and noise level, that affect the generalization ability. On this basis, an interpretable noise filtering framework is proposed, the goal of which is to minimize the noise level with a low cost of sample removal. Meanwhile, the relationship between noise and key indicators (center and radius) of the covering interval is theoretically analyzed for noise estimation. Then a relative noise estimator is proposed. The relative noise filtering (RNF) algorithm is designed by integrating the proposed framework with the estimator. The effectiveness of RNF is verified on the benchmark datasets and age estimation dataset. Experimental results show that RNF can be adapted to various types of noises and significantly improve the generalization ability of the regression model. On the age estimation dataset, RNF detects some samples with label noises. It effectively improves the data quality and model prediction performance.
2022, 59(8): 1653-1667.
DOI: 10.7544/issn1000-1239.20211112
Abstract：
Multi-view classification is an important research issue in multi-view machine learning. Existing studies indicate that the effective fusion operators play a key role for performance improvement of multi-view classification tasks. Hence, one of the hot topics for multi-view classification research is to design effective fusion operators. As the number of views increases (task with more than three views, named many-view task), the existing fusion operators confront two problems: 1) the dimension of the fused vector obtained by using the fusion operators with stronger expressiveness ability exponentially increases with the increasing number of views; while the expressive ability of the fusion operators having nothing to do with the number of views is weaker; 2) currently, most of these methods use a fusion operator to directly fuse all view features and obtain the final fused vector. When there are many views, it is difficult to model relationship among views via the strategy. To address these issues, inspired by multigranulation, this article proposes a multi-granulation fusion method (MGF) for multi-view classification. MGF hierarchically models relation among view features from three level of granularities. Specifically, firstly, it uses a fusion operator to model the relation between pair of two views at the first level of granularity, then uses a fusion operator to model the relation between a view and other views at the second level of granularity, and finally a fusion operator is used to model the relation among all views at the third level of granularity. The experimental results conducted on four large-scale multi-view datasets demonstrate that our proposed method can statistically achieve better performance than the compared methods.
Multi-view classification is an important research issue in multi-view machine learning. Existing studies indicate that the effective fusion operators play a key role for performance improvement of multi-view classification tasks. Hence, one of the hot topics for multi-view classification research is to design effective fusion operators. As the number of views increases (task with more than three views, named many-view task), the existing fusion operators confront two problems: 1) the dimension of the fused vector obtained by using the fusion operators with stronger expressiveness ability exponentially increases with the increasing number of views; while the expressive ability of the fusion operators having nothing to do with the number of views is weaker; 2) currently, most of these methods use a fusion operator to directly fuse all view features and obtain the final fused vector. When there are many views, it is difficult to model relationship among views via the strategy. To address these issues, inspired by multigranulation, this article proposes a multi-granulation fusion method (MGF) for multi-view classification. MGF hierarchically models relation among view features from three level of granularities. Specifically, firstly, it uses a fusion operator to model the relation between pair of two views at the first level of granularity, then uses a fusion operator to model the relation between a view and other views at the second level of granularity, and finally a fusion operator is used to model the relation among all views at the third level of granularity. The experimental results conducted on four large-scale multi-view datasets demonstrate that our proposed method can statistically achieve better performance than the compared methods.
2022, 59(8): 1668-1682.
DOI: 10.7544/issn1000-1239.20220073
Abstract：
In recent years, online learning has been extensively studied due to its huge application value. However, in many open environment application scenarios, the data may have new features at the current moment, and only part of the original features at the next moment are inherited. For example, in environment monitoring, with the deployment of new sensors, new features appear; when some of the old sensors are out of operation, only some of the original features of the data are retained. In this paper, such data is called streaming data with inheritably increasing and decreasing features. Traditional online learning algorithms are based on the fixed feature space, and cannot directly deal with data with inheritably increasing and decreasing features. To solve the problem, we propose online classification with feature inheritably increasing and decreasing (OFID), together with its two variants. When new features appear, the classifiers on the original features and new features are updated by combining the online passive-aggressive algorithm and the principle of structural risk minimization. When the old features disappear, the frequent-directions algorithm is used to complete the data matrix which allows the old classifier to continue to update. We theoretically analyze the performance bounds of the proposed algorithms and extensive experiments demonstrate the effectiveness of our algorithms.
In recent years, online learning has been extensively studied due to its huge application value. However, in many open environment application scenarios, the data may have new features at the current moment, and only part of the original features at the next moment are inherited. For example, in environment monitoring, with the deployment of new sensors, new features appear; when some of the old sensors are out of operation, only some of the original features of the data are retained. In this paper, such data is called streaming data with inheritably increasing and decreasing features. Traditional online learning algorithms are based on the fixed feature space, and cannot directly deal with data with inheritably increasing and decreasing features. To solve the problem, we propose online classification with feature inheritably increasing and decreasing (OFID), together with its two variants. When new features appear, the classifiers on the original features and new features are updated by combining the online passive-aggressive algorithm and the principle of structural risk minimization. When the old features disappear, the frequent-directions algorithm is used to complete the data matrix which allows the old classifier to continue to update. We theoretically analyze the performance bounds of the proposed algorithms and extensive experiments demonstrate the effectiveness of our algorithms.
2022, 59(8): 1683-1693.
DOI: 10.7544/issn1000-1239.20220063
Abstract：
Heterogeneous network embedding is to embed the rich structural and semantic information of heterogeneous networks into the low dimensional node representations. Graph convolutional networks are effective methods to process network data, and they are also used to research the representation of multi-type nodes and multi-dimensional relationships of heterogeneous networks. The existing graph convolutional network models mainly use meta-path to represent semantic relationship between nodes with different types. However, a single meta-path cannot accurately characterize the specific complex semantics between nodes, that is, it cannot make full use of high-order indirect semantic relationship between nodes. To address the above limitations, it is proposed that an embedding learning algorithm for heterogeneous network, named MGCN(meta-graph convolutional network). The algorithm includes two stages of heterogeneous adjacency matrices calculation based on meta-graph and learning node embedding. The heterogeneous adjacency matrix fuses different semantic information from multiple meta-paths and mines high-order indirect relationship between nodes. In addition, it can aggregate the neighborhood features of nodes into a unified pattern. This method reduces the embedding dimension, and then reduces the calculation time. Extensive experiments on two public heterogeneous network datasets show that the proposed MGCN can outperform baselines in basic research tasks of social computing like node classification and need less model training time.
Heterogeneous network embedding is to embed the rich structural and semantic information of heterogeneous networks into the low dimensional node representations. Graph convolutional networks are effective methods to process network data, and they are also used to research the representation of multi-type nodes and multi-dimensional relationships of heterogeneous networks. The existing graph convolutional network models mainly use meta-path to represent semantic relationship between nodes with different types. However, a single meta-path cannot accurately characterize the specific complex semantics between nodes, that is, it cannot make full use of high-order indirect semantic relationship between nodes. To address the above limitations, it is proposed that an embedding learning algorithm for heterogeneous network, named MGCN(meta-graph convolutional network). The algorithm includes two stages of heterogeneous adjacency matrices calculation based on meta-graph and learning node embedding. The heterogeneous adjacency matrix fuses different semantic information from multiple meta-paths and mines high-order indirect relationship between nodes. In addition, it can aggregate the neighborhood features of nodes into a unified pattern. This method reduces the embedding dimension, and then reduces the calculation time. Extensive experiments on two public heterogeneous network datasets show that the proposed MGCN can outperform baselines in basic research tasks of social computing like node classification and need less model training time.
2022, 59(8): 1694-1722.
DOI: 10.7544/issn1000-1239.20211264
Abstract：
Knowledge graph (KG) is a form of data representation that uses graph structure to model the connections between things. It is an important foundation for realizing cognitive intelligence and has received extensive attention from academia and industry. The research of knowledge graph includes four parts: knowledge representation, knowledge extraction, knowledge fusion, knowledge reasoning. Currently, there are still some challenges in the research of knowledge graphs. For example, knowledge extraction methods face difficulty in obtaining labeled data, while distantly supervised training samples have noise problems. The interpretability and reliability of the knowledge reasoning methods need to be further improved. Knowledge representation methods also have problems such as relying on manually defined rules or prior knowledge. Knowledge fusion methods fail to fully model the interdependence between entities. Environment-driven reinforcement learning (RL) algorithms are suitable for sequential decision-making problems. By modeling the research problem of the knowledge graph into a path (sequence) problem, and applying reinforcement learning methods, the above-mentioned problems in the knowledge graph can be solved, which has important application value. The basic knowledge of KG and RL are introduced firstly. Secondly, a research of KG based on RL are comprehensively reviewed. Then, it focuses on how the KG method based on RL can be applied to practical application areas such as intelligent recommendation, conversation system, game, biology, medicine prediction, finance and cybersecurity. Finally, the future directions of KG and RL are discussed in detail.
Knowledge graph (KG) is a form of data representation that uses graph structure to model the connections between things. It is an important foundation for realizing cognitive intelligence and has received extensive attention from academia and industry. The research of knowledge graph includes four parts: knowledge representation, knowledge extraction, knowledge fusion, knowledge reasoning. Currently, there are still some challenges in the research of knowledge graphs. For example, knowledge extraction methods face difficulty in obtaining labeled data, while distantly supervised training samples have noise problems. The interpretability and reliability of the knowledge reasoning methods need to be further improved. Knowledge representation methods also have problems such as relying on manually defined rules or prior knowledge. Knowledge fusion methods fail to fully model the interdependence between entities. Environment-driven reinforcement learning (RL) algorithms are suitable for sequential decision-making problems. By modeling the research problem of the knowledge graph into a path (sequence) problem, and applying reinforcement learning methods, the above-mentioned problems in the knowledge graph can be solved, which has important application value. The basic knowledge of KG and RL are introduced firstly. Secondly, a research of KG based on RL are comprehensively reviewed. Then, it focuses on how the KG method based on RL can be applied to practical application areas such as intelligent recommendation, conversation system, game, biology, medicine prediction, finance and cybersecurity. Finally, the future directions of KG and RL are discussed in detail.
2022, 59(8): 1723-1731.
DOI: 10.7544/issn1000-1239.20220071
Abstract：
In recent years, multi-instance learning (MIL) has been widely used in complicated data problems, but the existing MIL methods often study a fixed number of categories in a closed environment. However, in real applications, novel categories are constantly added to the system, such as the continuous emergence of new topics in the development of science or social media. Due to storage restrictions or confidentiality agreements, old data may become invisible over time, which makes the model forget the previously learned knowledge when directly learning new categories. Incremental learning is often used to deal with the aforementioned problems. The mining of multi-instance learning with incremental classes is very meaningful, but the current works on this is rare to be focused. We propose a novel multi-instance incremental data mining method based on both attention mechanism and prototype classifier mapping. Through the attention mechanism, the MIL bags are selectively merged into unified feature representations, which will be used to generate the corresponding storable category prototypes. Through the prototype classifier mapping, each category prototype is mapped into an unbiased and robust classifier. The prediction results of the classifier generated in the previous incremental stage are used to perform knowledge distillation on the prediction results of the classifier generated in novel incremental stages, so that the model can retain the old knowledge with very low storage under MIL. Experimental results on benchmarks of three different tasks show that our proposed method have achieved effective performance in MIL with incremental classes.
In recent years, multi-instance learning (MIL) has been widely used in complicated data problems, but the existing MIL methods often study a fixed number of categories in a closed environment. However, in real applications, novel categories are constantly added to the system, such as the continuous emergence of new topics in the development of science or social media. Due to storage restrictions or confidentiality agreements, old data may become invisible over time, which makes the model forget the previously learned knowledge when directly learning new categories. Incremental learning is often used to deal with the aforementioned problems. The mining of multi-instance learning with incremental classes is very meaningful, but the current works on this is rare to be focused. We propose a novel multi-instance incremental data mining method based on both attention mechanism and prototype classifier mapping. Through the attention mechanism, the MIL bags are selectively merged into unified feature representations, which will be used to generate the corresponding storable category prototypes. Through the prototype classifier mapping, each category prototype is mapped into an unbiased and robust classifier. The prediction results of the classifier generated in the previous incremental stage are used to perform knowledge distillation on the prediction results of the classifier generated in novel incremental stages, so that the model can retain the old knowledge with very low storage under MIL. Experimental results on benchmarks of three different tasks show that our proposed method have achieved effective performance in MIL with incremental classes.
2022, 59(8): 1732-1741.
DOI: 10.7544/issn1000-1239.20220042
Abstract：
Data mining is the process of extracting hidden and potential information in large datasets by artificial intelligence and other methods, which provides an effective way to obtain valuable knowledge from a large amount of information. Data mining is omnipresent in the process of solving point cloud registration task by deep learning. Extracting global features and estimating rigid body transformation are two key stages of corresponding-free point cloud registration. Mining abundant information hidden in two stages is one of the important tasks of point cloud registration. However, recently proposed methods are easy to ignore low-dimensional local features when extracting global features, resulting in the loss of numerous point cloud information, which makes the accuracy of solving transformation parameters in the subsequent rigid body transformation estimation stage unable to reach the expectation. Firstly, a features mining network based on multi-dimensional information fusion is devised, which fully excavates the high-dimensional global information and low-dimensional local information in point cloud, and effectively offsets the lack of local features in the global feature extraction stage of point cloud registration. Secondly, dual quaternion is utilized to estimate pose in the rigid body transformation estimation stage, which can represent rotation and translation simultaneously within a common framework and provide a compact and precise representation for pose estimation. Finally, extensive experiments on ModelNet40 dataset are conducted. The results illustrate that, compared with the existing corresponding-free point cloud registration methods, the proposed method can obtain higher accuracy, while being highly robust with respect to noise.
Data mining is the process of extracting hidden and potential information in large datasets by artificial intelligence and other methods, which provides an effective way to obtain valuable knowledge from a large amount of information. Data mining is omnipresent in the process of solving point cloud registration task by deep learning. Extracting global features and estimating rigid body transformation are two key stages of corresponding-free point cloud registration. Mining abundant information hidden in two stages is one of the important tasks of point cloud registration. However, recently proposed methods are easy to ignore low-dimensional local features when extracting global features, resulting in the loss of numerous point cloud information, which makes the accuracy of solving transformation parameters in the subsequent rigid body transformation estimation stage unable to reach the expectation. Firstly, a features mining network based on multi-dimensional information fusion is devised, which fully excavates the high-dimensional global information and low-dimensional local information in point cloud, and effectively offsets the lack of local features in the global feature extraction stage of point cloud registration. Secondly, dual quaternion is utilized to estimate pose in the rigid body transformation estimation stage, which can represent rotation and translation simultaneously within a common framework and provide a compact and precise representation for pose estimation. Finally, extensive experiments on ModelNet40 dataset are conducted. The results illustrate that, compared with the existing corresponding-free point cloud registration methods, the proposed method can obtain higher accuracy, while being highly robust with respect to noise.
2022, 59(8): 1742-1756.
DOI: 10.7544/issn1000-1239.20220074
Abstract：
As an extension of the knowledge graph, the knowledge hypergraph has a strong ability to express n-ary relational facts. Using the knowledge hypergraph to model known facts in the real world and discover unknown facts through link prediction has become a current research hotspot. Among existing knowledge hypergraph (or knowledge graph) link prediction methods, constructing the loss function using true labels of samples and their predicted labels is a key step, where negative samples have a great influence on the training of the link prediction model. However, when applying the negative sampling methods for knowledge graph link prediction (e.g., the uniformly random sampling) to the knowledge hypergraph, we may face problems such as low quality of negative samples and high complexity of models. As a result, we design a generative adversarial negative sampling method, named HyperGAN, for knowledge hypergraph link prediction, which generates high-quality negative samples through adversarial training to solve the zero loss problem, thereby improving the accuracy of the link prediction model. Besides, HyperGAN does not require pre-training, which makes it more efficient than previous negative sampling methods in assisting the training of link prediction models. Comparative experiments on multiple real-world datasets show that HyperGAN outperforms the baselines in terms of performance and efficiency. In addition, the case study and quantitative analysis further validate our method in improving the quality of negative samples.
As an extension of the knowledge graph, the knowledge hypergraph has a strong ability to express n-ary relational facts. Using the knowledge hypergraph to model known facts in the real world and discover unknown facts through link prediction has become a current research hotspot. Among existing knowledge hypergraph (or knowledge graph) link prediction methods, constructing the loss function using true labels of samples and their predicted labels is a key step, where negative samples have a great influence on the training of the link prediction model. However, when applying the negative sampling methods for knowledge graph link prediction (e.g., the uniformly random sampling) to the knowledge hypergraph, we may face problems such as low quality of negative samples and high complexity of models. As a result, we design a generative adversarial negative sampling method, named HyperGAN, for knowledge hypergraph link prediction, which generates high-quality negative samples through adversarial training to solve the zero loss problem, thereby improving the accuracy of the link prediction model. Besides, HyperGAN does not require pre-training, which makes it more efficient than previous negative sampling methods in assisting the training of link prediction models. Comparative experiments on multiple real-world datasets show that HyperGAN outperforms the baselines in terms of performance and efficiency. In addition, the case study and quantitative analysis further validate our method in improving the quality of negative samples.
2022, 59(8): 1757-1769.
DOI: 10.7544/issn1000-1239.20220064
Abstract：
With the increasing popularity and wide application of social networks, information diffusion prediction has gradually become a hot research topic in the field of social network analysis. Most previous studies either only use the information diffusion sequence or only use the social network between users to make prediction, failing to effectively model the complexity of the information diffusion process. In addition, recurrent neural network (RNN) and its variants, which are commonly used in information diffusion prediction, are difficult to capture the correlation between information effectively. To address the above problems, we propose a novel social network information diffusion prediction model called STT based on spatial-temporal Transformer. First, we construct a heterogeneous graph composed of a social network graph and a dynamic diffusion graph, and use graph convolutional network (GCN) to learn the users’ structural features. Then, the users’ temporal features and structural features are put into the Transformer for fusion to obtain users’ spatial-temporal features. In order to effectively fuse the users’ temporal features and structural features, a novel residual fusion method is proposed to replace the original residual connection in Transformer. Finally, the Transformer is used for information diffusion prediction. Extensive experiments on real datasets demonstrate the effectiveness of our proposed model STT.
With the increasing popularity and wide application of social networks, information diffusion prediction has gradually become a hot research topic in the field of social network analysis. Most previous studies either only use the information diffusion sequence or only use the social network between users to make prediction, failing to effectively model the complexity of the information diffusion process. In addition, recurrent neural network (RNN) and its variants, which are commonly used in information diffusion prediction, are difficult to capture the correlation between information effectively. To address the above problems, we propose a novel social network information diffusion prediction model called STT based on spatial-temporal Transformer. First, we construct a heterogeneous graph composed of a social network graph and a dynamic diffusion graph, and use graph convolutional network (GCN) to learn the users’ structural features. Then, the users’ temporal features and structural features are put into the Transformer for fusion to obtain users’ spatial-temporal features. In order to effectively fuse the users’ temporal features and structural features, a novel residual fusion method is proposed to replace the original residual connection in Transformer. Finally, the Transformer is used for information diffusion prediction. Extensive experiments on real datasets demonstrate the effectiveness of our proposed model STT.
2022, 59(8): 1770-1781.
DOI: 10.7544/issn1000-1239.20220060
Abstract：
Student performance prediction aims to predict students’ future academic performance based on student-related information. With the growing advancement of campus IT applications, the network authentication system on campus is getting more perfect, and universities have accumulated rich data on students’ online behavior. Due to the fact that human behavior and learning ability are highly correlated, from the perspective of campus online behavior awareness, seeks to predict students’ performance by mining their online logs. To this end, we collect a real dataset consisting of both students’ online behavior and performance data, and proves the correlation between them via data analysis. On this basis, we propose an end-to-end dual-level self-attention network (DEAN), which introduces a hierarchical self-attention mechanism to separately capture the local and global characteristics of students’ daily and long-term online behavior, solving the problem of long behavior sequence modeling better. Besides, the multi-task learning is used to simultaneously conduct student performance prediction for different majors under a unified framework, and the cost-sensitive learning is designed according to the difference between students’ rankings to further improve the method performance. Experimental results demonstrate that the proposed method can make more accurate predictions in comparison with the traditional sequence modeling methods.
Student performance prediction aims to predict students’ future academic performance based on student-related information. With the growing advancement of campus IT applications, the network authentication system on campus is getting more perfect, and universities have accumulated rich data on students’ online behavior. Due to the fact that human behavior and learning ability are highly correlated, from the perspective of campus online behavior awareness, seeks to predict students’ performance by mining their online logs. To this end, we collect a real dataset consisting of both students’ online behavior and performance data, and proves the correlation between them via data analysis. On this basis, we propose an end-to-end dual-level self-attention network (DEAN), which introduces a hierarchical self-attention mechanism to separately capture the local and global characteristics of students’ daily and long-term online behavior, solving the problem of long behavior sequence modeling better. Besides, the multi-task learning is used to simultaneously conduct student performance prediction for different majors under a unified framework, and the cost-sensitive learning is designed according to the difference between students’ rankings to further improve the method performance. Experimental results demonstrate that the proposed method can make more accurate predictions in comparison with the traditional sequence modeling methods.
2022, 59(8): 1782-1799.
DOI: 10.7544/issn1000-1239.20210685
Abstract：
With the development of Internet of things and big data technology, increasing distributed applications are booming in the personal computers and mobile phones. However, the existing distributed data processing methods have not met the needs of privacy protection. As a typical privacy-preserving technology for distributed set computation, private set intersection (PSI) protocols allow the participants to input individual sets and jointly calculate the intersection of these sets without disclosing any information except the intersection. As an important application of secure multiparty computation, PSI protocols have been widely used in privacy-preserving computation, which has theoretical and practical significance. Many PSI protocols have been emerged, but due to the lack of related surveys on PSI, we have written this paper. This paper introduces the fundamentals of PSI protocols such as the cryptographic technology, adversary model, security proof and implementation framework. And then the paper systematically summarizes the cryptographic framework of traditional PSI protocol from three aspects: the framework based on public key cryptosystem, garbled circuit, and oblivious transfer. Some of the key technologies in the set element comparison are introduced such as oblivious pseudo-random function, oblivious polynomial evaluation, and Bloom filter. Furthermore, a few of emerging PSI application scenarios are described in detail such as cloud-based PSI, unbalanced PSI, threshold PSI, and multiparty PSI. Finally, the paper summarizes the problems to be solved and prospects some possible development directions of PSI.
With the development of Internet of things and big data technology, increasing distributed applications are booming in the personal computers and mobile phones. However, the existing distributed data processing methods have not met the needs of privacy protection. As a typical privacy-preserving technology for distributed set computation, private set intersection (PSI) protocols allow the participants to input individual sets and jointly calculate the intersection of these sets without disclosing any information except the intersection. As an important application of secure multiparty computation, PSI protocols have been widely used in privacy-preserving computation, which has theoretical and practical significance. Many PSI protocols have been emerged, but due to the lack of related surveys on PSI, we have written this paper. This paper introduces the fundamentals of PSI protocols such as the cryptographic technology, adversary model, security proof and implementation framework. And then the paper systematically summarizes the cryptographic framework of traditional PSI protocol from three aspects: the framework based on public key cryptosystem, garbled circuit, and oblivious transfer. Some of the key technologies in the set element comparison are introduced such as oblivious pseudo-random function, oblivious polynomial evaluation, and Bloom filter. Furthermore, a few of emerging PSI application scenarios are described in detail such as cloud-based PSI, unbalanced PSI, threshold PSI, and multiparty PSI. Finally, the paper summarizes the problems to be solved and prospects some possible development directions of PSI.
2022, 59(8): 1800-1818.
DOI: 10.7544/issn1000-1239.20210664
Abstract：
Cut-and-Choose is a widely used technique in cryptography, which plays an important role in the design of secure multi-party computation (MPC) protocols. The main idea of Cut-and-Choose is that one party constructs multiple copies of the objective garbled circuit, and the other party randomly chooses some of the circuits to be opened for correctness check. If the check passes, the parties evaluate the remaining circuits and determine the final output of the computation task. In the early research works, Cut-and-Choose was mainly used in MPC in malicious model, and a lot of excellent research results were proposed. Although this technology was also applied in the covert security model, it did not attract much attention at that time. In recent years, with in-depth research on covert adversaries, Cut-and-Choose technique and ideas based on this technique have also been used to obtain publicly verifiable covert secure MPC protocols. Some representative research works have emerged. In this work, we summarize the main research advance of Cut-and-Choose in malicious security model and covert security model, and present the achievements of this technology in the publicly verifiable covert security model. We make a detailed summary and analysis of relevant results in this research field and point out possible research directions in the future.
Cut-and-Choose is a widely used technique in cryptography, which plays an important role in the design of secure multi-party computation (MPC) protocols. The main idea of Cut-and-Choose is that one party constructs multiple copies of the objective garbled circuit, and the other party randomly chooses some of the circuits to be opened for correctness check. If the check passes, the parties evaluate the remaining circuits and determine the final output of the computation task. In the early research works, Cut-and-Choose was mainly used in MPC in malicious model, and a lot of excellent research results were proposed. Although this technology was also applied in the covert security model, it did not attract much attention at that time. In recent years, with in-depth research on covert adversaries, Cut-and-Choose technique and ideas based on this technique have also been used to obtain publicly verifiable covert secure MPC protocols. Some representative research works have emerged. In this work, we summarize the main research advance of Cut-and-Choose in malicious security model and covert security model, and present the achievements of this technology in the publicly verifiable covert security model. We make a detailed summary and analysis of relevant results in this research field and point out possible research directions in the future.
2022, 59(8): 1819-1830.
DOI: 10.7544/issn1000-1239.20210563
Abstract：
Approximate pattern matching (APM) is the most suitable for practical applications among the variants of pattern matching, whose function is to determine whether the Hamming distance between two strings is less than a given threshold value. Due to its practicality, APM has a wide range of applications in face recognition, gene matching, etc. However, owing to the sensitivity of private data, data owners are often reluctant to share their private data. Fortunately, secure approximate pattern matching (SAPM) can accomplish the matching function without revealing the data. In this paper, we propose a secure and practical approximate pattern matching protocol based on oblivious transfer (OT), homomorphic encryption (HE), oblivious polynomial evaluation (OPE) and private equality test (PEQT) for the first time, and demonstrate that the protocol has semi-honest adversary security through ideal/realistic simulation paradigm. In terms of efficiency, compared with currently available secure approximate pattern matching works, our protocol has an advantage in the aspect of computation complexity by reducing the complexity from O(nm) to O(nτ), where n is the text length, m is the pattern length, and τ is a given threshold value. Finally, to examine the efficiency, we evaluate the performance of the protocol. The performance result shows that the protocol takes only 10 s to run when the pattern length is 2\+6 and the text length is 2\+\{12\}.
Approximate pattern matching (APM) is the most suitable for practical applications among the variants of pattern matching, whose function is to determine whether the Hamming distance between two strings is less than a given threshold value. Due to its practicality, APM has a wide range of applications in face recognition, gene matching, etc. However, owing to the sensitivity of private data, data owners are often reluctant to share their private data. Fortunately, secure approximate pattern matching (SAPM) can accomplish the matching function without revealing the data. In this paper, we propose a secure and practical approximate pattern matching protocol based on oblivious transfer (OT), homomorphic encryption (HE), oblivious polynomial evaluation (OPE) and private equality test (PEQT) for the first time, and demonstrate that the protocol has semi-honest adversary security through ideal/realistic simulation paradigm. In terms of efficiency, compared with currently available secure approximate pattern matching works, our protocol has an advantage in the aspect of computation complexity by reducing the complexity from O(nm) to O(nτ), where n is the text length, m is the pattern length, and τ is a given threshold value. Finally, to examine the efficiency, we evaluate the performance of the protocol. The performance result shows that the protocol takes only 10 s to run when the pattern length is 2\+6 and the text length is 2\+\{12\}.
2022, 59(8): 1831-1840.
DOI: 10.7544/issn1000-1239.20210411
Abstract：
Data hiding technology embeds additional data by modifying the digital media signal and does not affect the use value of the media itself. Reversible data hiding can not only hide additional data and extract additional data, but also recover the original image without distortion, so it is the research focuses currently. Because JPEG is the most widely used image format, reversible data hiding methods can be divided into two categories: the first one embeds additional data by modifying the DCT coefficients domain, which results in file-size expansion and visual quality distortion. The second one modifies the entropy coding domain, and the encrypted image generated by this method has no signal distortion compared with the original image, but the payload is limited, and the higher the payload is, the larger the file expansion is. To mitigate the problems existing in these two kinds of methods above, a multi-domain reversible data hiding algorithm for JPEG images is designed, which embeds the additional data by modifying the DCT coefficients domain and the entropy coding domain. Since two domains have different effects on visual quality distortion and file expansion, this paper focuses on distributing the payload reasonably. In this paper, the reason of file expansion is analyzed firstly when embedding the additional data in entropy coding domain, then a payload distribution algorithm based on VLC frequency histogram is designed to minimize file expansion and visual quality distortion. Experimental results demonstrate that the proposed algorithm significantly outperforms state-of-the-arts in file size expansion and visual quality.
Data hiding technology embeds additional data by modifying the digital media signal and does not affect the use value of the media itself. Reversible data hiding can not only hide additional data and extract additional data, but also recover the original image without distortion, so it is the research focuses currently. Because JPEG is the most widely used image format, reversible data hiding methods can be divided into two categories: the first one embeds additional data by modifying the DCT coefficients domain, which results in file-size expansion and visual quality distortion. The second one modifies the entropy coding domain, and the encrypted image generated by this method has no signal distortion compared with the original image, but the payload is limited, and the higher the payload is, the larger the file expansion is. To mitigate the problems existing in these two kinds of methods above, a multi-domain reversible data hiding algorithm for JPEG images is designed, which embeds the additional data by modifying the DCT coefficients domain and the entropy coding domain. Since two domains have different effects on visual quality distortion and file expansion, this paper focuses on distributing the payload reasonably. In this paper, the reason of file expansion is analyzed firstly when embedding the additional data in entropy coding domain, then a payload distribution algorithm based on VLC frequency histogram is designed to minimize file expansion and visual quality distortion. Experimental results demonstrate that the proposed algorithm significantly outperforms state-of-the-arts in file size expansion and visual quality.
2022, 59(8): 1841-1852.
DOI: 10.7544/issn1000-1239.20200605
Abstract：
In view of the searchable encryption technology in cloud storage services, this paper solves the following three problems：Firstly, most of the traditional searchable encryption methods only support single keyword search, and when the security index is too large, the search time cost is too high; Secondly, most of the existing schemes use inverted index for quick search, but inverted index does not support dynamic keyword update; Thirdly, most of the existing schemes can’t sort the search files efficiently according to the importance of keywords for some on-demand users. In this paper, a top-k boolean searchable encryption scheme based on multiple keywords (TBSE) is proposed. In the scheme, Goldwasser-Micalli and 2DNF encryption algorithms are used to construct a secure, index supporting dynamic update. Based on the set theory and boolean search, keyword intersection index and intersection search token are constructed to realize boolean search for multiple keywords. The top-k sorting is realized by fractional index constructed by using TF-IDF weighting technology and security coprocessor. The security analysis shows that the scheme can fully guarantee the security of the given ciphertext model and the known background model. The experiments prove that the scheme improves the efficiency of multi keywords Boolean search and index storage.
In view of the searchable encryption technology in cloud storage services, this paper solves the following three problems：Firstly, most of the traditional searchable encryption methods only support single keyword search, and when the security index is too large, the search time cost is too high; Secondly, most of the existing schemes use inverted index for quick search, but inverted index does not support dynamic keyword update; Thirdly, most of the existing schemes can’t sort the search files efficiently according to the importance of keywords for some on-demand users. In this paper, a top-k boolean searchable encryption scheme based on multiple keywords (TBSE) is proposed. In the scheme, Goldwasser-Micalli and 2DNF encryption algorithms are used to construct a secure, index supporting dynamic update. Based on the set theory and boolean search, keyword intersection index and intersection search token are constructed to realize boolean search for multiple keywords. The top-k sorting is realized by fractional index constructed by using TF-IDF weighting technology and security coprocessor. The security analysis shows that the scheme can fully guarantee the security of the given ciphertext model and the known background model. The experiments prove that the scheme improves the efficiency of multi keywords Boolean search and index storage.
2022, 59(8): 1853-1866.
DOI: 10.7544/issn1000-1239.20210260
Abstract：
The forward secure searchable encryption scheme has attracted widespread attention because it can resist the file injection attacks. It ensures that after the document is updated, the newly added document will not disclose the keyword information of the previous document. As for as the forward secure searchable encryption scheme is concerned, improving its security and operation efficiency is the current research hotspot. However, in order to improve security, the existing forward secure searchable encryption schemes often only support single-keyword query or sacrifice part of the query function. Aiming at the problem of privacy leakage and imcomplete search function during documents update in searchable encryption, a forward secure searchable encryption scheme supporting conjunctive keyword search is proposed. The scheme uses a cuckoo filter on the cloud server to filter documents that meet the query conditions, and supports dynamic update operations. The ciphertext equality test technology is introduced to hide the keywords and search without revealing the keywords and documents information in the search phase. Security analysis and experiments show that the proposed scheme achieves adaptive security, provides multi-keyword search, supports flexible update operations and efficient, so it is more suitable for practical application scenarios such as data outsourcing and email systems.
The forward secure searchable encryption scheme has attracted widespread attention because it can resist the file injection attacks. It ensures that after the document is updated, the newly added document will not disclose the keyword information of the previous document. As for as the forward secure searchable encryption scheme is concerned, improving its security and operation efficiency is the current research hotspot. However, in order to improve security, the existing forward secure searchable encryption schemes often only support single-keyword query or sacrifice part of the query function. Aiming at the problem of privacy leakage and imcomplete search function during documents update in searchable encryption, a forward secure searchable encryption scheme supporting conjunctive keyword search is proposed. The scheme uses a cuckoo filter on the cloud server to filter documents that meet the query conditions, and supports dynamic update operations. The ciphertext equality test technology is introduced to hide the keywords and search without revealing the keywords and documents information in the search phase. Security analysis and experiments show that the proposed scheme achieves adaptive security, provides multi-keyword search, supports flexible update operations and efficient, so it is more suitable for practical application scenarios such as data outsourcing and email systems.
