检索结果-内蒙古大学图书馆

Forward Private Verifiable Dynamic Searchable Symmetric Encryption With Efficient conjunctive query

IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING 2024年第2期21卷 746-763页

作者： Guo, Cheng Li, Wenfeng Tang, Xinyu Choo, Kim-Kwang Raymond Liu, Yining Dalian Univ Technol Key Lab Ubiquitous Network & Serv Software Liaonin Dalian 116620 Liaoning Peoples R China Dalian Univ Technol Sch Software Technol Dalian 116620 Liaoning Peoples R China Guilin Univ Elect Technol Guangxi Key Lab Trusted Software Guilin 541004 Guangxi Peoples R China Univ Texas San Antonio Dept Informat Syst & Cyber Secur San Antonio TX 78249 USA Univ Texas San Antonio Dept Elect & Comp Engn San Antonio TX 78249 USA

Dynamic searchable symmetric encryption (DSSE) allows efficient searches over encrypted databases and also supports clients in their updating of the data, such as those stored in a remote cloud server. However, recent attacks suggest the risk of leakage during such updates, which consequently impacts on the privacy of the queries. In addition, existing DSSE schemes that support forward privacy generally rely on the honest-but-curious server and support only single-keyword retrieval, which limits the application scenarios. In this paper, we present the design of a verifiable DSSE protocol, which supports efficient conjunctive query with forward privacy. In our scheme, the forward index is constructed by a novel form, i.e., $ t$t-puncturable PRFs, and the authentication tag is designed by symmetric cryptography. During conjunctive queries, we narrow the scope by an inverted index, and then we determine the results of the final query through the forward index. Meanwhile, we can use verification tag to check the correctness and completeness of the result. In addition, we present an extension to support backward privacy, and our experimental evaluations show that our proposed approach achieves better performance on both conjunctive queries and updates than other competing solutions and ensures efficient verification.

关键词： Indexes Security Privacy Encryption Protocols Servers query processing conjunctive query forward privacy puncturable pseudorandom function searchable symmetric encryption verification

来源：评论

学校读者我要写书评

暂无评论

Achieving Efficient and Privacy-Preserving Multi-Keyword conjunctive query Over Cloud

引用

IEEE ACCESS 2019年 7卷 165862-165872页

作者： Yin, Fan Zheng, Yandong Lu, Rongxing Tang, Xiaohu Southwest Jiaotong Univ Informat Secur & Natl Comp Grid Lab Chengdu 611756 Peoples R China Univ New Brunswick Fac Comp Sci Fredericton NB E3B 5A3 Canada

With the explosive growth of data, it has become increasingly popular to deploy the powerful cloud to manage data. Meanwhile, as the cloud is not always fully trusted, personal and sensitive data have to be encrypted before being outsourced to the cloud. Naturally, this brings a serious challenge for the cloud to provide secure and efficient query services over huge volumes of data. Although existing works have proposed some solutions to solve the above challenge, most of them just focus on the single keyword query and cannot directly support multi-keyword query. Even though some works have discussed solutions for the multi-keyword query, they cannot well balance the efficiency and privacy. Therefore, in this paper, we propose a novel multi-keyword conjunctive query scheme over cloud, which can achieve high query efficiency with small privacy leakage. In specific, we first design a tree-based index to support the multi-keyword conjunctive query and employ Boneh-Goh-Nissim (BGN) homomorphic encryption technique to protect its privacy. Then, based on the tree-based index, we propose a wildcard search algorithm to improve its query efficiency. Finally, the detailed security analysis shows that the proposed scheme is really privacy-preserving, and extensive simulation results also demonstrate its efficient.

关键词： Cloud computing conjunctive query homomorphic encryption multi-keyword query

来源：评论

学校读者我要写书评

暂无评论

Verifiable Searchable Symmetric Encryption Over Additive Homomorphism

引用

IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY 2025年 20卷 1320-1332页

作者： Ji, Licheng Li, Jiguo Zhang, Yicheng Lu, Yang Fujian Normal Univ Coll Comp & Cyber Secur Fuzhou 350117 Peoples R China Minist Educ Sch Math & Stat Fuzhou 350117 Fujian Peoples R China Minist Educ Key Lab Analyt Math & Applicat Fuzhou 350117 Fujian Peoples R China Fujian Prov Key Lab Network Secur & Cryptol Fuzhou 350117 Peoples R China Nanjing Normal Univ Sch Comp Sci & Technol Nanjing 210023 Peoples R China

Searchable symmetric encryption (SSE) allows the client to search encrypted documents on an untrusted server without revealing the document content and queried keywords. To improve search efficiency and enrich expressiveness, most SSE schemes leak some information that could be exploited for attacks, characterized by leakage patterns. The traditional leakage patterns encompass the search pattern, the access pattern and the response length pattern. Recent research has demonstrated that these three patterns could be exploited to launch attacks, resulting in a high probability of compromising the confidentiality of encrypted documents and queried keywords. Moreover, while there exist SSE schemes that hide multiple leakage patterns, most of them do not resist the malicious server, which may carry out incorrect search operations. In this paper, we propose a leakage-suppressed verifiable SSE (VSSE) scheme that not only hides the three patterns but also allows the client to verify the server's response. We utilize the privacy set intersection based on polynomial coding and additive symmetric homomorphism encryption to construct a VSSE scheme that supports a conjunctive query. Specifically, we design an efficient random token generation algorithm to protect the search pattern and a verification algorithm that does not require server-generated proofs. Formal security analysis shows that our scheme achieves the desired correctness, security and verifiability. Lastly, we simulate the proposed scheme and compare it with the recent leakage suppression schemes in multiple aspects. The comparison results show that our scheme achieves a good balance in expressiveness, efficiency and security.

关键词： Verifiable searchable symmetric encryption search pattern access pattern response length pattern private set intersection conjunctive query leakage suppression

来源：评论

学校读者我要写书评

暂无评论

Owner-free Distributed Symmetric Searchable Encryption Supporting conjunctive Queries

引用

ACM TRANSACTIONS ON STORAGE 2023年第4期19卷 1-25页

作者： Tong, Qiuyun Li, Xinghua Miao, Yinbin Wang, Yunwei Liu, Ximeng Deng, Robert H. Xidian Univ Sch Cyber Engn Xian 710071 Peoples R China Minist Educ Engn Res Ctr Big Data Secur Xian 710071 Peoples R China Fuzhou Univ Coll Comp & Data Sci Fuzhou 350108 Peoples R China Singapore Management Univ Sch Informat Syst Singapore 188065 Singapore

Symmetric Searchable Encryption (SSE), as an ideal primitive, can ensure data privacy while supporting retrieval over encrypted data. However, existing multi-user SSE schemes require the data owner to share the secret key with all query users or always be online to generate search tokens. While there are some solutions to this problem, they have at least one weakness, such as non-supporting conjunctive query, result decryption assistance of the data owner, and unauthorized access. To solve the above issues, we propose an Owner-free Distributed Symmetric searchable encryption supporting conjunctive query (ODiSC). Specifically, we first evaluate the Learning-Parity-with-Noise weak Pseudorandom Function (LPN-wPRF) in dual-cloud architecture to generate search tokens with the data owner free from sharing key and being online. Then, we provide fine-grained conjunctive query in the distributed architecture using additive secret sharing and symmetric-key hidden vector encryption. Finally, formal security analysis and empirical performance evaluation demonstrate that ODiSC is adaptively simulation-secure and efficient.

关键词： Symmetric searchable encryption multi-user conjunctive query dual-cloud architecture

来源：评论

学校读者我要写书评

暂无评论

When Do Homomorphism Counts Help in query Algorithms? 27

When Do Homomorphism Counts Help in Query Algorithms?

引用

27th International Conference on Database Theory (ICDT)

作者： ten Cate, Balder Dalmau, Victor Kolaitis, Phokion G. Wu, Wei-Lin Univ Amsterdam Amsterdam Netherlands Univ Pompeu Fabra Barcelona Spain Univ Calif Santa Cruz Santa Cruz CA 95064 USA IBM Almaden Res Ctr San Jose CA 95120 USA

ISBN: (纸本)9783959773126

A query algorithm based on homomorphism counts is a procedure for determining whether a given instance satisfies a property by counting homomorphisms between the given instance and finitely many predetermined instances. In a left query algorithm, we count homomorphisms from the predetermined instances to the given instance, while in a right query algorithm we count homomorphisms from the given instance to the predetermined instances. Homomorphisms are usually counted over the semiring N of non-negative integers;it is also meaningful, however, to count homomorphisms over the Boolean semiring B, in which case the homomorphism count indicates whether or not a homomorphism exists. We first characterize the properties that admit a left query algorithm over B by showing that these are precisely the properties that are both first-order definable and closed under homomorphic equivalence. After this, we turn attention to a comparison between left query algorithms over B and left query algorithms over N. In general, there are properties that admit a left query algorithm over N but not over B. The main result of this paper asserts that if a property is closed under homomorphic equivalence, then that property admits a left query algorithm over B if and only if it admits a left query algorithm over N. In other words and rather surprisingly, homomorphism counts over N do not help as regards properties that are closed under homomorphic equivalence. Finally, we characterize the properties that admit both a left query algorithm over B and a right query algorithm over B.

关键词： query algorithms homomorphism homomorphism counts conjunctive query constraint satisfaction

来源：评论

学校读者我要写书评

暂无评论

Practical Non-interactive Encrypted conjunctive Search with Leakage Suppression 24

Practical Non-interactive Encrypted Conjunctive Search with ...

引用

31st Conference on Computer and Communications Security

作者： Wang, Yunling Sun, Shi-Feng Wang, Jianfeng Chen, Xiaofeng Liu, Joseph K. Gu, Dawu Xian Univ Posts & Telecommun Sch Cyberspace Secur Xian Peoples R China Shanghai Jiao Tong Univ Shanghai Peoples R China Blockchain Adv Res Ctr Wuxi Jiangsu Peoples R China Xidian Univ Sch Cyber Engn Xian Peoples R China Monash Univ Fac Informat Technol Melbourne Vic Australia

ISBN: (纸本)9798400706363

Encrypted conjunctive search enables server to perform efficient conjunctive query over encrypted data while guaranteeing data and query privacy. The well-known Oblivious Cross-Tags (OXT) protocol (by Cash et al. in CRYPTO 2013) is the first to realize efficient conjunctive search with some well-defined leakage, such as the keyword pair result pattern (KPRP) leakage and the cross-query intersection result pattern (IP) leakage. To mitigate the potential threats brought by the leakage, much effort has been made to reduce the information leaked by OXT. However, it is still open to achieve encrypted conjunctive search without revealing both KPRP and IP, while preserving high-efficiency. Encrypted multi-map is a crucial primitive for designing searchable encryption with optimal search complexity. In this paper, we present the first non-interactive encrypted conjunctive multi-map, Doris, without KPRP and IP leakage. To this end, we design a novel data structure for performing conjunctive query, that enables the client to generate "encrypted" label/value pairs without interaction. Then, we introduce a new cryptographic primitive dubbed Symmetric Subset Predicate Encryption, which supports checking if one set is entirely contained within another without leaking any information than the subset predicate. Finally, we implement Doris and provide a detailed comparison with the most related works HXT (by Lai et al. in CCS 2018) and ConjFilter (by Patel et al. in ASIACRYPT 2021). The experimental results demonstrate that Doris can achieve a speedup of 6x and 1.07x compared to HXT and ConjFilter in search latency respectively for 2 labels querying, while increasing to 42x and 1.1x respectively for 10 labels, even with a stronger security guarantee.

关键词： Symmetric Searchable Encryption Encrypted Multi-Map conjunctive query Leakage Suppression

来源：评论

学校读者我要写书评

暂无评论

Finding Smallest Witnesses for conjunctive Queries 27

Finding Smallest Witnesses for Conjunctive Queries

引用

27th International Conference on Database Theory (ICDT)

作者： Hu, Xiao Sintos, Stavros Univ Waterloo Waterloo ON Canada Univ Illinois Chicago IL USA

ISBN: (纸本)9783959773126

A witness is a sub-database that preserves the query results of the original database but of much smaller size. It has wide applications in query rewriting and debugging, query explanation, IoT analytics, multi-layer network routing, etc. In this paper, we study the smallest witness problem (SWP) for the class of conjunctive queries (CQs) without self-joins. We first establish the dichotomy that SWP for a CQ can be computed in polynomial time if and only if it has head-cluster property, unless P = NP. We next turn to the approximated version by relaxing the size of a witness from being minimum. We surprisingly find that the head-domination property - that has been identified for the deletion propagation problem [31] - can also precisely capture the hardness of the approximated smallest witness problem. In polynomial time, SWP for any CQ with head-domination property can be approximated within a constant factor, while SWP for any CQ without such a property cannot be approximated within a logarithmic factor, unless P = NP. We further explore efficient approximation algorithms for CQs without head-domination property: (1) we show a trivial algorithm which achieves a polynomially large approximation ratio for general CQs;(2) for any CQ with only one non-output attribute, such as star CQs, we show a greedy algorithm with a logarithmic approximation ratio;(3) for line CQs, which contain at least two non-output attributes, we relate SWP problem to the directed steiner forest problem, whose algorithms can be applied to line CQs directly. Meanwhile, we establish a much higher lower bound, exponentially larger than the logarithmic lower bound obtained above. It remains open to close the gap between the lower and upper bound of the approximated SWP for CQs without head-domination property.

关键词： conjunctive query smallest witness head-cluster head-domination

来源：评论

学校读者我要写书评

暂无评论

Achieve Efficient and Verifiable conjunctive and Fuzzy Queries over Encrypted Data in Cloud

引用

IEEE TRANSACTIONS ON SERVICES COMPUTING 2022年第1期15卷 124-137页

作者： Shao, Jun Lu, Rongxing Guan, Yunguo Wei, Guiyi Zhejiang Gongshang Univ Dept Informat Secur Hangzhou 310018 Peoples R China Univ New Brunswick Fac Comp Sci Fredericton NB E3B 5A3 Canada

Due to the high demands of searchability over encrypted data, searchable encryption (SE) has recently received considerable attention and been widely suggested in encrypted cloud storage. Typically, the cloud server is assumed to be honest-butcurious in most SE-based cloud storage systems, i.e., the cloud server should follow the protocol to return valid and complete search results to users. However, this trust assumption is not always true due to some unanticipated situations, such as misconfigurations and malfunctions. Therefore, the function of verifiability of search results becomes crucial for the success of SE-based cloud storage systems. For this reason, many verifiable SE schemes have been proposed;however, they either fail to support query operators "OR", "AND", "*" and "?" simultaneously, or require many time-consuming operations. Aiming at addressing this problem, in this paper, we propose a new verifiable SE scheme for encrypted cloud storage. The proposed scheme is characterized by integrating various techniques, i.e., bitmap index, radix tree, format preserving encryption, keyed-hash message authentication code and symmetric key encryption, for achieving efficient and verifiable conjunctive and fuzzy queries over encrypted data in the cloud. Detailed security analysis shows that our proposed scheme holds the confidentiality of data and verifiability of search results at the same time. In addition, extensive experiments are conducted, and the results demonstrate our proposed scheme is efficient and suitable for users to retrieve their data from the cloud to their mobile devices.

关键词： Cloud storage verifiable searchability searchable encryption conjunctive query fuzzy query

来源：评论

学校读者我要写书评

暂无评论

Applications of Information Inequalities to Database Theory Problems 38

Applications of Information Inequalities to Database Theory ...

引用

38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)

作者： Suciu, Dan Univ Washington Paul G Allen Sch Comp Sci & Engn Seattle WA 98195 USA

ISBN: (纸本)9798350335873

The paper describes several applications of information inequalities to problems in database theory. The problems discussed include: upper bounds of a query's output, worst-case optimal join algorithms, the query domination problem, and the implication problem for approximate integrity constraints. The paper is self-contained: all required concepts and results from information inequalities are introduced here, gradually, and motivated by database problems.

关键词： conjunctive query information inequality worst case optimal join algorithm approximate constraint implication

来源：评论

学校读者我要写书评

暂无评论

conjunctive Queries With Self-Joins, Towards a Fine-Grained Enumeration Complexity Analysis 23

Conjunctive Queries With Self-Joins, Towards a Fine-Grained ...

引用

42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS)

作者： Carmeli, Nofar Segoufin, Luc Univ PSL DI ENS ENS CNRSInria Paris France ENS Paris INRIA PSL Paris France

ISBN: (纸本)9798400701276

Even though query evaluation is a fundamental task in databases, known classifications of conjunctive queries by their fine-grained complexity only apply to queries without self-joins. We study how self-joins affect enumeration complexity, with the aim of building upon the known results to achieve general classifications. We do this by examining the extension of two known dichotomies: one with respect to linear delay, and one with respect to constant delay after linear preprocessing. As this turns out to be an intricate investigation, this paper is structured as an example-driven discussion that initiates this analysis. We show enumeration algorithms that rely on self-joins to efficiently evaluate queries that otherwise (i.e., if the relation names were replaced to eliminate self-joins) cannot be answered with the same guarantees. Due to these additional tractable cases, the hardness proofs are more complex than the self-join-free case. We show how to harness a known tagging technique to prove hardness of queries with self-joins. Our study offers sufficient conditions and necessary conditions for tractability and settles the cases of queries of low arity and queries with cyclic cores. Nevertheless, many cases remain open.

关键词： conjunctive query self-joins enumeration fine-grained complexity constant delay

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：