| 引用本文： |
-
赵冬冬,刘志晖,廖磊,向剑文,江浩.基于DES算法与整数分解的负数据库生成算法[J].信息安全学报,已采用 [点击复制]
- Zhao Dongdong,Liu Zhihui,Liao Lei,Xiang Jianwen,Jiang Hao.Negative Database Generation Algorithm based on DES Algorithm and Integer Factorization[J].Journal of Cyber Security,Accept [点击复制]
|
|
| 摘要: |
| 在计算机科学理论领域，SAT问题（Boolean Satisfiability Problem，布尔可满足性问题）是一项经典的数理逻辑问题，其在计算机学科中扮演着至关重要的角色。在隐私保护领域中，负数据库技术是一种新兴的隐私保护技术，其主要原理是通过存储原始数据的补集来实现对数据的保护。相较于传统的加解密算法，负数据库技术在大数据隐私保护领域展现出显著的效率优势，因而具备巨大的潜力与前景。值得注意的是，本文研究的负数据库方法等价于经典的SAT 问题，这一等价性表现在负数据库的实例表达与求解过程上，因此本文也是对SAT 问题的探索。现有的负数据库生成算法通常使用概率参数来进行生成，这种方法在面对一些最新的SAT求解器时，可能容易被求解。为此，本文提出了基于 DES（Data Encryption Standard，数据加密标准）算法的负数据库生成算法D-hidden和基于整数分解问题的负数据库生成算法F-hidden。实验表明，在D-hidden算法中，当隐藏串的长度与基准串的长度相等且轮数不小于5时，相较于目前经典的负数据库生成算法K-hidden，D-hidden算法生成了更加难解且更为稳定的负数据库，并且具有更高的生成效率。在F-hidden算法中，隐藏串长度在[50, 600]范围内相对于已有负数据库生成算法表现出显著的难解性。本工作是首个将负数据库技术与传统的加解密算法相结合的工作，为隐私保护领域提供新的思路，同时也为SAT领域提供新的研究视角。 |
| 关键词: 隐私保护，布尔可满足性问题，负数据库 |
| DOI： |
| 投稿时间：2023-12-03修订日期：2024-06-04 |
| 基金项目:国家自然科学基金项目（面上项目，重点项目，重大项目），重庆市自然科学基金，国家重点开发计划 |
|
| Negative Database Generation Algorithm based on DES Algorithm and Integer Factorization |
|
Zhao Dongdong1, Liu Zhihui1, Liao Lei1, Xiang Jianwen1, Jiang Hao2
|
| (1.Wuhan University of Technology;2.Anhui University) |
| Abstract: |
| In the domain of theoretical computer science, the Boolean Satisfiability Problem (SAT) constitutes a classical problem in mathematical logic, playing a crucial role within the field of computer science. In the domain of privacy protection, negative database technology is an emerging privacy safeguard technique, primarily based on the principle of protecting data by storing the complement of the original dataset. Compared to traditional encryption algorithms, negative database technology exhibits significant efficien-cy advantages in the domain of big data privacy protection, thus possessing substantial potential and prospects. It is noteworthy that the negative database method explored in this paper is equivalent to the classical SAT problem, with this equivalence manifested in the expression and solving processes of negative database instances. Consequently, this paper represents an exploration of the SAT problem. Existing negative database generation algorithms commonly employ probability parameters for generation, a method that may be susceptible to resolution when faced with some of the latest SAT solvers. To address this, the paper proposes negative database generation algorithms, namely D-hidden based on the Data Encryp-tion Standard (DES) algorithm and F-hidden based on the integer factorization problem. Experiments indicate that in the D-hidden algorithm, when the length of the hidden string is equal to the length of the baseline string and the num-ber of rounds is not less than 5, compared to the classic negative database generation algorithm K-hidden, the D-hidden algorithm generates a more challenging and stable negative database, with higher efficiency. In the F-hidden algorithm, within the range of hidden string lengths [50, 600], significant difficulty is observed relative to existing negative data-base generation algorithms. This work represents the first integration of negative database technology with traditional encryption algorithms, providing an innovative perspective for the field of privacy protection, and concurrently offering a novel research outlook for the SAT domain. |
| Key words: Privacy protection,Boolean satisfiability problem,Negative database |
