(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210228130.5 (22)申请日 2022.03.08 (71)申请人 中山大学 地址 510275 广东省广州市海珠区新港西 路135号 (72)发明人 张方国　陈建彰　 (74)专利代理 机构 广州粤高专利商标代理有限 公司 44102 专利代理师 王晓玲 (51)Int.Cl. H04L 9/40(2022.01) H04L 9/32(2006.01) H04L 9/08(2006.01) (54)发明名称 基于区块链存储的可验证的可搜索对称加 密方法 (57)摘要 本发明属于信息检索和密码学技术领域， 更 具体地， 涉及一种基于区块链存储的可验证的可 搜索对称加密方法。 本发明为方便查找表数据结 构和可搜索对称加密方案的设计与实现， 对区块 链的存储机制进行高层次的功能抽象， 屏蔽了区 块链具体实现的细节； 为实现紧密的空间存储和 高效的检索性能， 本发明基于二叉搜索树提出了 一个高效的查找表数据结构实现， 其中节点使用 仅追加块存储的数据块进行紧密的打包存储， 而 检索操作则使用二分查找的思路来减少查询工 作量； 为实现可搜索对称加密的可验证性， 本发 明使用消息认证码， 对与关键字所关联的次序和 结果等信息进行了签名， 实现了结果的可验证性 和不可伪造性， 从而抵御了恶意服务器的伪造行 为。 权利要求书4页 说明书10页 附图4页 CN 114615050 A 2022.06.10 CN 114615050 A 1.一种基于区块链存 储的可验证的可搜索对称加密方法， 其特 征在于， 包括： S1.密钥生成算法： 运行于数据用户端， 数据用户输入安全参数λ， 密钥生成算法使用随 机数生成算法产生密钥K， K ′ ←{0， 1}λ， 之后， 数据用户将密钥K， K ′妥善保存在本地存 储中； S2.初始化算法： 运行于数据用户端， 用户输入密钥K， K ′， 以及数据库DB， 初始化算法为 数据库DB生成加密数据库EDB＝(LT1， LT2)， 并写入到仅追加块存储ABS模型中； 其中， LT1存 储了加密数据库， 用于加密搜索； 而LT2存储了每个关键字对应的证据， 用于结果验证； S3.令牌生成算法： 运行于数据用户端， 用户输入待搜索关键字w， 以及密钥K1， K2， 令牌 生成算法生成一个与待搜索关键字w相关联的搜索令牌τ＝(K1， K2， label)， 并将搜索令牌τ 发送至服 务提供者端； S4.搜索算法： 运行于服务提供者端， 当服务提供者收到数据用户发来的搜索令牌τ后， 对保存在ABS模型的加密数据库EDB＝(LT1， LT2)进行检索， 调用搜索算法从LT1中得到相匹 配的文件标识符集 合 并从LT2提取出相应的证据prf， 最后将 和prf发送至数据用户端； S5.验证算法： 运行于数据用户端， 当数据用户收到服务提供者返回的结果 后， 输入上述结果、 密钥K ′以及令牌生 成阶段输出的label， 验证算法校验服务提供者返回的结 果是否正确， 如果结果正确， 则读取结果集合 的文件标识符进行后续的操作； 否则， 数据 用户选择继续和其 他服务提供者沟通， 重新执 行搜索算法和验证算法以获取 可靠的结果。 2.根据权利要求1所述的基于区块链存储的可验证的可搜索对称加密方法， 其特征在 于， 所述的仅追加块存储ABS模型用于对区块链存储进 行高层次的功能抽象， 以屏蔽区块链 的运作细节， 以便基于区块链存储的可搜索对称加密方法的设计与分析； ABS模 型使用数据 块的结构组织数据， 不能修改或删除已写入的块， 只能将新的块写入到存储中； 当一个块被 写入后， ABS模 型会返回指向该块的地址； ABS模型的数据块长度是固定的， 由公共参数γ指 定； 当待写入数据的长度大于γ时， ABS模型终止写入而不会切分数据； 如果待写入数据的 长度小于块的长度， ABS模型在写入前使用足够多个0填充数据， 直至数据长度等于块的长 度。 3.根据权利要求2所述的基于区块链存储的可验证的可搜索对称加密方法， 其特征在 于， 所述的ABS模型包括： ABS←Init(γ)： 初始化ABS算法， 其接受一个公开参数γ作为输入， 并输出一个仅追加 块存储ABS， 其中γ指定块的长度； v/⊥←Get(ABS， addr)： 获取块数据算法， 其输入一个仅追加块存储ABS和一个块地址 addr， 如果ad dr指定的块存在， 它返回该块所有的内容v； 否则， 它返回空指示符 ⊥； (ABS′， addr)←Put(ABS， v)： 写入块数据算法， 其输入一个仅追加块存储ABS和一个要 写入的数据v， 如果v的长度大于块长度y， 算法就会终止； 否则， 算法输出更新后的仅追加块 存储ABS′以及该数据所在的块 地址addr。 4.根据权利要求3所述的基于区块链存储的可验证的可搜索对称加密方法， 其特征在 于， 还包括基于区块链存储的静态查找表数据结构的实现方法， 用于在区块链存储中实现 较高效的键 ‑值存储和读取效率， 包括： (LT， ABS′)←LTInit({(l1， v1)， ...， (ln， vn)}， ABS)： 初始化算法LTInit， 其接受一组键 ‑ 值对{(li， vi)}1≤i≤n和仅追加块存储ABS作为输入， 然后输出更新后的块存储ABS ′， 以及存储 在ABS′中的查找 表LT；权　利　要　求　书 1/4 页 2 CN 114615050 A 2v/⊥←LTGet(l， LT， ABS)： 查找表检索算法LTGet， 其接受一个键l、 查找表LT以及仅追 加块存储ABS作为输入， 如果查找表 LT中存在键为l的项， 则输出对应的值v； 否则， 输出空指 示符⊥。 5.根据权利要求4所述的基于区块链存储的可验证的可搜索对称加密方法， 其特征在 于， 基于二叉搜索树的思想， 给出具体的基于区块链存储的静态查找表数据结构的实现方 法， 即BinST； 给定n个键 ‑值对{(l1， v1)， ...， (ln， vn)}， M阶Bi nST的初始化 算法LTInit包括： 若n＝0， 返回空树， 其中根节点地址表示为空指示 符⊥； 否则， 对{(l1， v1)， ...， (ln， vn)} 按键的非降序进行排序， 结果 为{(l′1， v′1)， ...， (l′n， v′n)}； 将有序的键 ‑值对{(l′1， v′1)， ...， (l′n， v′n)}切分为 个子集合 为简化表示， 使用符号 Bi来表示第i个子集 合； 对于子集合列表 调用以下子例程自底向上地构造Bi nST： 读取子例程的输入， 即子集合列表B＝{B1， B2， ...， Bm}； 若列表B为空， 输出空树， 其中根 节点地址表示为空指示符 ⊥； 否则， 从列表B中选择中间元素 构造BinST结点x， 将 中的键‑值对按序写入到结点x的相应数据成员中； 对于位于 左边的子列表 递归调用该子例程生成左子树bl， 将bl的根结点作为x的左孩子； 同理， 对 于位于 右边的子列表 递归调用该子例程生成右子树br， 将br的根结 点作为x的右孩子； 通过调用方法(ABS， addrx)←Put(ABS， x)， 将节点x写入到块存储ABS中， 输出以结点x为 根的BinST子树b， 其中b的根节点 地址为ad drx； 在BinSTb(其中b的根节点表示为b.root， 而根节点地址表示为addrb.root)中查找键l详 细步骤， 即查找 表检索算法LTGet包括： 根据b的根节点地址addrb.root， 如果addrb.root为空指示符 ⊥， 则b为空树， 查找失败， 算 法结束； 否则， 调用方法b.ro ot←Get(ABS， ad drb.root)读取b.ro ot的详细数据； 若l小于b.ro ot的最小键， 则根据b.ro ot的左孩 子地址， 递归搜索左子树； 若l大于b.root的最大键， 则根据b.root的右孩子地址， 递归搜索右子树， 重复查找步 骤； 否则， 对b.root中包含 的键集合进行二分查找， 如果查找成功， 返回相应的值； 否则， 查找失 败， 算法结束。 6.根据权利要求5所述的基于区块链存储的可验证的可搜索对称加密方法， 其特征在 于， S2中的初始化 算法具体包括： S21.初始化两个空列表L1， L2； S22.对于数据库DB包 含的每一个关键 字w， 进行以下操作： 计算K1←F(1||w)， K2←F(2||w)， 并 初始化一个用于计数的变量c ←0以及一个空字符串 对于包含于DB(w)的每一个文档标识符id， 计算l ←F(K1， c)， d←E(K2， id)， 并自增计数 器c←c+1， 然后将二元组(l， d)添加至列表L1中， 并将id追加到 字符串 上， 即 计算labelw←F(K3， w)， 以及 并将二元组(labelw， prfw)添 加到列表L2中； S23.对列表L2按字典序的增序进行排序；权　利　要　求　书 2/4 页 3 CN 114615050 A 3