Nothing Special   »   [go: up one dir, main page]

CN110362537B - Full-parameter private information retrieval method based on sawtooth decoding - Google Patents

Full-parameter private information retrieval method based on sawtooth decoding Download PDF

Info

Publication number
CN110362537B
CN110362537B CN201910615099.9A CN201910615099A CN110362537B CN 110362537 B CN110362537 B CN 110362537B CN 201910615099 A CN201910615099 A CN 201910615099A CN 110362537 B CN110362537 B CN 110362537B
Authority
CN
China
Prior art keywords
matrix
node
packet
query
nodes
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
CN201910615099.9A
Other languages
Chinese (zh)
Other versions
CN110362537A (en
Inventor
代明军
郑子英
邓海燕
林晓辉
苏恭超
陈彬
王晖
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Shenzhen University
Original Assignee
Shenzhen University
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Shenzhen University filed Critical Shenzhen University
Priority to CN201910615099.9A priority Critical patent/CN110362537B/en
Publication of CN110362537A publication Critical patent/CN110362537A/en
Application granted granted Critical
Publication of CN110362537B publication Critical patent/CN110362537B/en
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/10—File systems; File servers
    • G06F16/14—Details of searching files based on file metadata
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/10—File systems; File servers
    • G06F16/18—File system types
    • G06F16/182—Distributed file systems
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L1/00—Arrangements for detecting or preventing errors in the information received
    • H04L1/004—Arrangements for detecting or preventing errors in the information received by using forward error control
    • H04L1/0056—Systems characterized by the type of code used
    • H04L1/0061—Error detection codes
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L67/00—Network arrangements or protocols for supporting network services or applications
    • H04L67/01—Protocols
    • H04L67/10—Protocols in which an application is distributed across nodes in the network
    • H04L67/1097—Protocols in which an application is distributed across nodes in the network for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Mining & Analysis (AREA)
  • Databases & Information Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Library & Information Science (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Error Detection And Correction (AREA)

Abstract

本发明公开了一种基于锯齿解码的全参数私有信息检索方法，包括以下步骤：步骤S10，将m个文件划分为kα个系统包，存储于分布式存储系统的k个系统节点中，确定编码矩阵，根据编码矩阵获取编码包，将编码包存储于α个奇偶校验节点中；步骤S20，生成查询矩阵，查询矩阵包括随机矩阵和检索矩阵，向分布式存储系统中进行查询；步骤S30，对从节点所返回的第二数据包进行数据解码，其中，节点包括系统节点和奇偶校验节点。本发明，能够适用于全参数的，提高适用范围，计算复杂度低，通信成本低。

Figure 201910615099

The invention discloses a full-parameter private information retrieval method based on sawtooth decoding, comprising the following steps: step S10, dividing m files into kα system packages, storing them in k system nodes of a distributed storage system, determining the code matrix, obtain the encoded packet according to the encoding matrix, and store the encoded packet in the α parity check nodes; step S20, generate a query matrix, the query matrix includes a random matrix and a retrieval matrix, and query the distributed storage system; step S30, Data decoding is performed on the second data packet returned from the node, wherein the node includes a system node and a parity check node. The present invention is applicable to all parameters, improves the scope of application, has low computational complexity and low communication cost.

Figure 201910615099

Description

Full-parameter private information retrieval method based on sawtooth decoding
Technical Field
The invention belongs to the technical field of information retrieval, and particularly relates to a full-parameter private information retrieval method based on sawtooth decoding.
Background
At present, the technology of information retrieval is becoming more mature, for example, patent application No. CN107992582A, which is named as a private information retrieval method based on zigzag decoding, and only (2k, k) private information retrieval based on zigzag decoding is performed, that is, the method is only applicable to the case where n is 2k, but in practice, n and k are arbitrary, and have certain limitations in application, and thus, the problem of low practicability exists.
Therefore, the prior art is to be improved.
Disclosure of Invention
The invention mainly aims to provide a full-parameter private information retrieval method based on sawtooth decoding, aims to solve the technical problems mentioned in the background technology, and can be suitable for (n, k) of full parameters in the aspect of information retrieval, thereby improving the application range.
The invention discloses a full-parameter private information retrieval method based on sawtooth decoding, which comprises the following steps:
step S10, m files S1,s2,…smDividing the system into k alpha system packets, storing the system packets in k system nodes of a distributed storage system, determining a coding matrix, obtaining a coding packet according to the coding matrix, and storing the coding packet in alpha parity check nodes, wherein the distributed storage system has n nodes in total, alpha is n-k, and the coding matrix
Figure BDA0002123667100000011
Step S20, generating a query matrix, wherein the query matrix comprises a random matrix U and a retrieval matrix Ef,lQuerying the distributed storage system;
and step S30, performing data decoding on the second data packet returned by the nodes, wherein the nodes comprise a system node and a parity check node.
Preferably, in step S10, the obtaining the encoded packet according to the encoding matrix includes:
and S100, shifting the corresponding bit of the systematic packet of each line of the file to the right according to the line vector element of the coding matrix T, and adding in a binary field to obtain a coding packet.
Preferably, step S30 specifically includes:
step S31, after receiving the query matrix, the nodes of the distributed storage system shift the first data packet stored in the nodes to the right by corresponding bits according to the row vector elements of the query matrix, then add in the binary domain to obtain the second data packet, and the nodes return the obtained second data packet;
step S32, a first result packet returned by the system node and a second result packet returned by the parity check node are obtained, the first result packet is right-shifted by corresponding bits according to the row vector elements of the CP-BZD code coding matrix, then binary field addition is carried out to obtain a third data packet, and then the third data packet and the second result packet are subjected to zigzag decoding to obtain a fourth data packet, wherein the second data packet comprises the first result packet and the second result packet;
step S33, performing zigzag decoding on the fourth packet, and solving a total of α k systematic packets.
Preferably, when n <2k, step S20 specifically includes:
in the step of S21,
generating a retrieval matrix and a random matrix in the query matrix, the random matrix being
Figure BDA0002123667100000021
The search matrix is Ef,l，
Figure BDA0002123667100000022
Ef,1Is the search matrix sent by the user to the first node, where r is n-k, and when l is 2, …, k, Ef,lIs composed of Ef,l-1The row vector is obtained by cyclic shift once;
in step S22, the user sends the query matrix to the corresponding node.
Preferably, when n ≧ 2k, step S20 specifically includes:
step S25, generating a retrieval matrix and a random matrix in the query matrix, wherein the random matrix is a random matrix
Figure BDA0002123667100000023
Retrieval matrix Ef,l＝[E1,…,Ef,…,Em],l∈{k+1,k+2,…,n}；
Step S26, sending the random matrix to the system node
Figure BDA0002123667100000031
The random matrix and the search matrix are sent to the parity check nodes.
The full-parameter private information retrieval method based on the sawtooth decoding has the following beneficial effects:
the invention is a private information retrieval scheme based on sawtooth decoding in a distributed storage system, which adopts a binary shift addition technology and can meet the requirements: the user downloads the file and does not display which file is being downloaded. Because binary shift-add and zigzag decoding are used, the computational complexity is relatively low. The communication cost is also low. The present invention can be applied to any (n, k) system, and is not limited to n ═ 2 k.
Drawings
FIG. 1 is a schematic flowchart of a full parameter private information retrieval method based on sawtooth decoding according to a first embodiment of the present invention;
fig. 2 is a schematic diagram illustrating a refinement process of obtaining a coded packet according to a coding matrix in a first embodiment;
fig. 3 is a detailed flowchart of step S30 in the first embodiment;
FIG. 4 is a detailed flowchart of step S20 if n is less than 2k in the first embodiment;
FIG. 5 is a schematic diagram illustrating a detailed flow of step S20 if n is greater than or equal to 2k in the first embodiment;
FIG. 6 is a diagram illustrating a full parameter private information retrieval method based on sawtooth decoding according to the present invention
Figure BDA0002123667100000032
A coded packet decoding process;
FIG. 7 is a diagram illustrating a full parameter private information retrieval method based on sawtooth decoding according to the present invention
Figure BDA0002123667100000033
A sawtooth decoding process.
The implementation, functional features and advantages of the objects of the present invention will be further explained with reference to the accompanying drawings.
Detailed Description
It should be understood that the specific embodiments described herein are merely illustrative of the invention and are not intended to limit the invention. It is noted that relative terms such as "first," "second," and the like may be used to describe various components, but these terms are not intended to limit the components. These terms are only used to distinguish one component from another component. For example, a first element could be termed a second element, and, similarly, a second element could be termed a first element, without departing from the scope of the present invention. The term "and/or" refers to a combination of any one or more of the associated items and the descriptive items.
As shown in fig. 1, fig. 1 is a schematic flowchart of a full-parameter private information retrieval method based on zigzag decoding according to a first embodiment of the present invention;
the invention discloses a full-parameter private information retrieval method based on sawtooth decoding, which comprises the following steps:
step S10, m files S1,s2,…smDividing into k alpha system packets, storing in k system nodes of distributed storage system, and using CP-BZD code to make m files s1,s2,…smEncoding is carried out, and an encoding matrix is determined according to k and alpha
Figure BDA0002123667100000041
Obtaining coded packets from a coding matrix
Figure BDA0002123667100000042
Storing the encoded packets in alpha parity check nodes, wherein n nodes are shared in the distributed storage system, and alpha is n-k, and the encoding matrix
Figure BDA0002123667100000043
In step S10, for example, such as
Figure BDA0002123667100000044
siRepresents the ith file, i ∈ {1,2, …, m },
Figure BDA0002123667100000045
to represent
Figure BDA0002123667100000046
The w-th bit of (a) e {1,2, …, α }, b e {1,2, …, k }; for coded packet
Figure BDA0002123667100000047
Wherein i represents the same as siThe files are related, x is obtained by encoding the x-th row of encoding vectors of the encoding matrix T, x belongs to {1,2, …, alpha }, y is the y-th encoding packet formed by encoding the same encoding vector of the same file, and y belongs to {1,2, …, alpha }. In particular, the document siThe system package in the jth column of (1) is stored in the jth node, j belongs to {1,2, …, k }, and the k nodes are called system nodes because the system package is stored; the coded packet obtained from the x-th row of coded vectors is stored in the k + x-th node, and since the coded packet is stored, the α -n-k nodes are called parity nodes.
For example, suppose that the distributed storage system has n-5 nodes, where k-3 nodes are used for storing system packets and are called system nodes, n-k-2 nodes are used for storing coding packets and are called parity check nodes, and the system stores m-3 files, each of which is s1,s2,s3. The user wants to retrieve a document sfI.e. f is 1 and α is n-k is 2, then the document siIs divided into 6 systematic packets, the bit length of each data packet is set as L10,
Figure BDA0002123667100000051
node 1 stores siFirst column of (2), node 2 stores siSecond column of (3), node 3 stores siThe third column of (c), since the system stores 3 files, each node stores 6 packets. Coding matrix
Figure BDA0002123667100000052
siAccording to the vector [0,1,2 ] in the matrix T]Bit shifting is carried out, and then the bit shifting and the binary field addition are carried out to obtain a coded packet which comprises
Figure BDA0002123667100000053
Figure BDA0002123667100000054
And stored in node 4. siAccording to the vector 0,2,4 in the matrix T]Bit shifting to obtain coded packet, the coded packet comprises
Figure BDA0002123667100000055
Figure BDA0002123667100000056
And stored in the node 5. I.e., nodes 4 and 5 are parity nodes. This example is used to explain a simple application of the present application, and the following examples are related to this example. Wherein a bit represents a bit value comprising the values of the row vector elements in the coding matrix.
Step S20, generating a query matrix, wherein the query matrix comprises a random matrix U and a retrieval matrix Ef,lQuerying the distributed storage system;
in step S20, when the user searches for a document, a query matrix is generated, where the query matrix includes a random matrix U and a search matrix Ef,lQuerying the distributed storage system; specific examples of step S20 of the present embodiment are described together with step S30, which will be described in the following embodiments.
And step S30, performing data decoding on the second data packet returned by the nodes, wherein the nodes comprise a system node and a parity check node.
The full-parameter private information retrieval method based on the sawtooth decoding has the following beneficial effects:
the invention is a private information retrieval scheme based on sawtooth decoding in a distributed storage system, which adopts a binary shift addition technology and can meet the requirements: the user downloads the file and does not display which file is being downloaded. Because binary shift-add and zigzag decoding are used, the computational complexity is relatively low. The communication cost is also low. The present invention can be applied to any (n, k) system, and is not limited to n ═ 2 k. The difference between the present invention and the comparison document mentioned in the background art lies in the difference of the coding matrix T constructed in step S10 and the document being divided into k α parts to adapt to the full parameters (n, k); n represents the total number of nodes in the distributed storage system, and k represents the number of system nodes; the nodes include system nodes and parity nodes.
As shown in fig. 2, preferably, in step S10, the obtaining of the encoded packet according to the encoding matrix includes:
step S100, using CP-BZD code to m files S1,s2,…smCoding is carried out, and the systematic packets in each row of the file are right-shifted by corresponding bits according to row vector elements of the coding matrix T;
step S101, adding in binary field to obtain coding packet.
For step S100 and step S101, for example, the coding matrix
Figure BDA0002123667100000061
siAccording to the vector [0,1,2 ] in the matrix T]Bit shifting and adding in binary domain to obtain coded packet
Figure BDA0002123667100000062
Figure BDA0002123667100000063
The encoded packets are stored in parity check nodes.
As shown in fig. 3, preferably, step S30 specifically includes:
step S31, after receiving the query matrix, the nodes of the distributed storage system shift the first data packet stored in the nodes to the right by corresponding bits according to the row vector elements of the query matrix, then add in the binary domain to obtain the second data packet, and the nodes return the obtained second data packet;
in step S31, together with step S20, for example, the user needs to send k ═ 3 times of queries to each node, and the three queries can unify the query contents sent by the user to each node into a 3 × 6 random matrix and a 3 × 6 searchAnd (4) matrix. Setting random matrix
Figure BDA0002123667100000071
Since r-n-k-2, the search matrix sent to node 1 is
Figure BDA0002123667100000072
The search matrix sent to node 2 passes through E1,1Is shifted to obtain
Figure BDA0002123667100000073
The search matrix sent to node 3 passes through E1,2Is shifted to obtain
Figure BDA0002123667100000074
E1,4＝E1,5＝[0]. So that the query matrix sent by the user to the node is Q1＝U+E1,1，Q2＝U+E1,2，Q3＝U+E1,3，Q4＝U，Q5The subscript of Q denotes a query matrix sent to the corresponding node, e.g. Q1Is the query matrix sent to node 1. The ith row of the query matrix is the ith query of the user for the node, i ∈ {1,2,3 }. Data stored by node 1 is according to Q1The row vector elements are subjected to bit shift and then correspondingly added in a binary domain to obtain
Figure BDA0002123667100000075
Three packets and then node 1 returns the three packets to the user. The nodes 2 will
Figure BDA0002123667100000076
Returning to the user, node 3 will
Figure BDA0002123667100000077
Returning to the user, node 4 will
Figure BDA0002123667100000078
Returning to the user, node 5 will
Figure BDA0002123667100000079
Returning to the user; i.e. the second packet comprises the return of node 1
Figure BDA00021236671000000710
Three data packets, node 2 returning
Figure BDA00021236671000000711
Three data packets, node 3 returns
Figure BDA00021236671000000712
Three data packets, node 4 returning
Figure BDA00021236671000000713
Three data packets and returned by node 5
Figure BDA00021236671000000714
Three data packets.
Step S32, obtaining a first result packet returned by the system node and a second result packet returned by the parity node, right-shifting the first result packet by corresponding bits according to the row vector element of the CP-BZD code encoding matrix, then performing binary field addition to obtain a third data packet, and performing zigzag decoding on the third data packet and the second result packet to obtain a fourth data packet, where the second data packet includes the first result packet and the second result packet.
Step S33, performing zigzag decoding on the fourth packet, and decoding α k systematic packets.
In the above steps S32 and S33, step S31, step S32 and step S33 are applied to both cases where n <2k and n ≧ 2 k.
For step S32 and step S33, for example, for
Figure BDA00021236671000000715
Right-shifting the corresponding bit with respect to (0,1,2) in the coding matrix T is performed and then binary field addition is performed to obtain a third packet, which is
Figure BDA0002123667100000081
Then to
Figure BDA0002123667100000082
Performing sawtooth decoding
Figure BDA0002123667100000083
As shown in fig. 6. To pair
Figure BDA0002123667100000084
Bit shifting with respect to the coding matrix T (0,2,4) is performed, and the third packet is binary field added to
Figure BDA0002123667100000085
Then to
Figure BDA0002123667100000086
Performing sawtooth decoding
Figure BDA0002123667100000087
Then to
Figure BDA0002123667100000088
Can be decoded by performing sawtooth decoding
Figure BDA0002123667100000089
As shown in fig. 1-2. In the same way, by
Figure BDA00021236671000000810
And
Figure BDA00021236671000000811
can be decoded respectively
Figure BDA00021236671000000812
And
Figure BDA00021236671000000813
thus document s1All of the 6 packets of (1) are obtained. Privacy communication cost for whole document retrieval
Figure BDA00021236671000000814
As shown in fig. 4, preferably, when n <2k, step S20 specifically includes:
step S21, generating a retrieval matrix and a random matrix in the query matrix, wherein the random matrix is
Figure BDA00021236671000000815
The random matrix is a matrix with the size of k multiplied by m alpha and is independent of the storage file, the ith row represents the ith query random vector, and the retrieval matrix is Ef,l， l＝1,2,...,k,
Figure BDA00021236671000000816
Ef,1Is the search matrix sent by the user to the first node, Ef,lAccording to Ef,l-1The row vector is obtained by cyclic shift once; when l is 2f,lIs composed of Ef,l-1The row vector of (a) is obtained by cyclic shifting once. When k is more than l and less than or equal to n, Ef,l＝[0]That is, the search matrix sent to the parity check node is a zero matrix. And when k is more than l and less than or equal to n, the retrieval matrix is a zero matrix.
In step S21, it is assumed that the user is to retrieve the document SfAnd f is equal to {1,2, …, m }, a user needs to inquire each node for k times, and returns one data packet from each node in each inquiry, so that a total of nk data packets are returned, and alpha k system packets need to be solved. Random matrix
Figure BDA00021236671000000817
Where row i represents the query random vector for the ith time. The size of the retrieval matrix is kXm alpha, wherein the ith row represents the retrieval vector of the ith query, i is more than or equal to 1 and less than or equal to k, and at most one 1 is arranged in each row and column;
step S22, the user sends the query matrix to the corresponding node; it can also be understood that: sending the retrieval matrix and the random matrix to corresponding nodes; in practice, the query matrix is composed of a search matrix and a random matrix, and sending the query matrix to the corresponding node is equivalent to sending the search matrix and the random matrix to the corresponding node.
As shown in FIG. 5, preferably, when n ≧ 2k, step S20 specifically includes:
step S25, generating a retrieval matrix and a random matrix in the query matrix, wherein the random matrix is a random matrix
Figure BDA0002123667100000091
Retrieval matrix Ef,l＝[E1,…,Ef,…,Em]L ∈ { k +1, k +2, …, n }; wherein E isqIs a k x α matrix, q ∈ {1,2, …, m }, f is the f-th file to be retrieved, EqOnly E in the sub-matrixfInstead of a zero matrix, the remaining m-1 sub-matrices are all zero matrices. Ef,k+1Submatrix E inf＝[Ik×k,0k×(α-k)]，Ef,k+2Submatrix E infIs Ef,k+1E in (A)f＝[Ik×k,0k×(α-k)]The column vector in (A) is circularly shifted to the right by one bit, and the like, Ef,lSubmatrix E infIs Ef,l-1E in (A)fThe column vector in (1) is obtained by circularly shifting right by one bit. Query matrix Q to be generated by a userxAnd sending the data to the corresponding node, wherein x represents sending to the x-th node.
Step S26, sending the random matrix to the system node
Figure BDA0002123667100000092
The random matrix and the search matrix are sent to the parity check nodes.
For n ≧ 2k, the privacy communication cost is the same as for the case of n <2 k.
For n ≧ 2k, for example, it is assumed that there are n ═ 5 nodes in the distributed storage system, where k ═ 2 nodes are used for storing system packets and are called system nodes, and the remaining n-k ═ 3 nodes are used for storing coded packets and are called parity nodes. Let the system store m equal to 3 files, s respectively1、s2、s3. Each file si(i e {1,2,3}) is divided into 2 equal-length data packets, and then each data packet is divided into a equal-length data packets, wherein α -n-k-3, namely
Figure BDA0002123667100000101
Each file is divided into 6 packets. siIs stored in the first column of nodes 1, siThe second column of (2) is stored in the node, and the storage system has 3 files coexisting, so each system node needs to store m α ═ 9 original packets, and each parity check node also needs to store m α ═ 9 coded packets. Coding matrix of CP-ZD adopted by (5,2) code
Figure BDA0002123667100000102
siIs right-shifted by the corresponding bit according to the first row element of the matrix T, and then added in binary field to obtain the second data packet
Figure BDA0002123667100000103
And is stored in the node 3. siRight-shifted by corresponding bits according to the second row element of the matrix T, and then added in binary domain to obtain a second data packet
Figure BDA0002123667100000104
And is stored in the node 4. siIs right-shifted by the corresponding bit according to the third row element of the matrix T, and then binary field addition is performed to obtain the second data packet
Figure BDA0002123667100000105
And is stored in the node 5. And i represents a data packet corresponding to the ith file.
Suppose that a user wants to retrieve a document s1If f is 1, the user needs to query the node for k 2 times to decode the file s1. Firstly, a user generates a random matrix with k × m α being 2 × 9
Figure BDA0002123667100000106
Query matrix Q to system nodes 1,21＝U,Q2A query matrix Q sent to the parity check nodes3＝U+E1,3，Q4＝U+E1,4，Q5＝U+E1,5Wherein
Figure BDA0002123667100000107
The ith row of the query matrix is the query vector for the ith query from the user to the node, i ∈ {1,2, …, k }.
After receiving the query matrix, the system nodes shift the stored data packets according to the query matrix, add the data packets in the binary domain, and each node can obtain two new data packets and return the data packets to the user. Downloaded from node 1 to
Figure BDA0002123667100000108
From node 2 to
Figure BDA0002123667100000109
Is downloaded from node 3 to
Figure BDA00021236671000001010
Downloaded from node 4 to
Figure BDA00021236671000001011
From node 5 to
Figure BDA00021236671000001012
When n ≧ 2k, data decoding is the same as when n <2k, and therefore, no description is given here.
According to the invention, when n is larger than or equal to 2k and n is smaller than 2k, the transmitted random matrix and the transmitted retrieval matrix are different, and the transmitted node objects are different, so that the full parameter (n, k) can be adapted.
The above description is only a preferred embodiment of the present invention, and not intended to limit the scope of the present invention, and all modifications of equivalent structures and equivalent processes, which are made by using the contents of the present specification and the accompanying drawings, or directly or indirectly applied to other related technical fields, are included in the scope of the present invention.

Claims (3)

1.一种基于锯齿解码的全参数私有信息检索方法，其特征在于，包括以下步骤：1. a full-parameter private information retrieval method based on sawtooth decoding, is characterized in that, comprises the following steps: 步骤S10，将m个文件s1,s2,...sm划分为kα个系统包，存储于分布式存储系统的k个系统节点中，确定编码矩阵，根据编码矩阵获取编码包，将编码包存储于α个奇偶校验节点中，其中，分布式存储系统中共有n个节点，α＝n-k，编码矩阵
Figure FDA0003314285050000011
Step S10: Divide the m files s 1 , s 2 , . . . s m into kα system packets, store them in k system nodes of the distributed storage system, determine the encoding matrix, obtain the encoding packets according to the encoding matrix, and set the The encoded packet is stored in α parity check nodes, where there are n nodes in the distributed storage system, α=nk, the encoding matrix
Figure FDA0003314285050000011
 步骤S20，生成查询矩阵，查询矩阵包括随机矩阵U和检索矩阵Ef,l，向分布式存储系统中进行查询；Step S20, generating a query matrix, the query matrix including a random matrix U and a retrieval matrix E f,l , and querying the distributed storage system; 步骤S30，对从分布式存储系统的节点所返回的第二数据包进行数据解码，其中，节点包括系统节点和奇偶校验节点；Step S30, performing data decoding on the second data packet returned from the node of the distributed storage system, wherein the node includes a system node and a parity check node; 其中，当n＜2k时，所述步骤S20具体包括：Wherein, when n<2k, the step S20 specifically includes: 步骤S21，生成查询矩阵中的检索矩阵和随机矩阵，随机矩阵为
Figure FDA0003314285050000012
检索矩阵为
Figure FDA0003314285050000013
Ef,1是用户向第一个节点所发送的检索矩阵，其中r＝n-k，当l＝2,...,k时，Ef,l是由Ef,l-1的行向量循环移位一次得到，f∈{1,2,…,m}，f表示要检索的文件的序号；Step S21, generate a retrieval matrix and a random matrix in the query matrix, and the random matrix is
Figure FDA0003314285050000012
The search matrix is
Figure FDA0003314285050000013
E f,1 is the retrieval matrix sent by the user to the first node, where r=nk, when l=2,...,k, E f,l is the row vector cycle of E f,l-1 It is obtained by shifting once, f∈{1,2,…,m}, f represents the serial number of the file to be retrieved; 步骤S22，用户将查询矩阵发送给对应的节点；Step S22, the user sends the query matrix to the corresponding node; 其中，当n≥2k，所述步骤S20具体包括：Wherein, when n≥2k, the step S20 specifically includes: 步骤S25，生成查询矩阵中的检索矩阵和随机矩阵，随机矩阵
Figure FDA0003314285050000014
检索矩阵Ef,l＝[E1,…,Ef,…,Em],l∈{k+1,k+2,…,n}；Step S25, generate a retrieval matrix and a random matrix in the query matrix, and the random matrix
Figure FDA0003314285050000014
Retrieval matrix E f,l =[E 1 ,...,E f ,...,E m ],l∈{k+1,k+2,...,n}; 步骤S26，向系统节点发送随机矩阵
Figure FDA0003314285050000015
向奇偶校验节点发送随机矩阵和检索矩阵。Step S26, send the random matrix to the system node
Figure FDA0003314285050000015
Send random matrices and retrieval matrices to parity nodes. 2.如权利要求1所述基于锯齿解码的全参数私有信息检索方法，其特征在于，在步骤S10中，根据编码矩阵获取编码包包括：2. the full-parameter private information retrieval method based on sawtooth decoding as claimed in claim 1, is characterized in that, in step S10, according to the encoding matrix, obtains the encoding package and comprises: 步骤S100，文件的每一行的系统包根据编码矩阵T的行向量元素右移相应的比特；Step S100, the system packet of each row of the file shifts the corresponding bit to the right according to the row vector element of the encoding matrix T; 步骤S101，在二元域相加获得编码包。Step S101, adding in the binary domain to obtain an encoded packet. 3.如权利要求1所述基于锯齿解码的全参数私有信息检索方法，其特征在于，所述步骤S30具体包括：3. The full-parameter private information retrieval method based on sawtooth decoding as claimed in claim 1, wherein the step S30 specifically comprises: 步骤S31，分布式存储系统的节点收到查询矩阵后，对节点中存储的第一数据包按照查询矩阵的行向量元素右移相应的比特，然后在二元域相加获得第二数据包，节点将得到的第二数据包进行返回；Step S31, after the node of the distributed storage system receives the query matrix, right-shifts the first data packet stored in the node by the corresponding bit according to the row vector elements of the query matrix, and then adds in the binary domain to obtain the second data packet, The node returns the obtained second data packet; 步骤S32，获取系统节点所返回的第一结果包和奇偶校验节点返回的第二结果包，第一结果包按照CP-BZD码的编码矩阵的行向量元素右移相应的比特，然后二元域相加获取第三数据包，然后第三数据包和第二结果包锯齿解码得到第四数据包，其中，第二数据包包括第一结果包和第二结果包；Step S32, obtain the first result packet returned by the system node and the second result packet returned by the parity check node, the first result packet is shifted to the right by the corresponding bit according to the row vector element of the coding matrix of the CP-BZD code, and then the binary Domain addition obtains the third data packet, and then the third data packet and the second result packet are zigzag-decoded to obtain the fourth data packet, wherein the second data packet includes the first result packet and the second result packet; 步骤S33，对第四数据包进行锯齿解码，共解出αk个系统包。Step S33, perform sawtooth decoding on the fourth data packet, and obtain αk system packets in total.
CN201910615099.9A 2019-07-09 2019-07-09 Full-parameter private information retrieval method based on sawtooth decoding Active CN110362537B (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201910615099.9A CN110362537B (en) 2019-07-09 2019-07-09 Full-parameter private information retrieval method based on sawtooth decoding

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201910615099.9A CN110362537B (en) 2019-07-09 2019-07-09 Full-parameter private information retrieval method based on sawtooth decoding

Publications (2)

Publication Number Publication Date
CN110362537A CN110362537A (en) 2019-10-22
CN110362537B true CN110362537B (en) 2021-12-28

Family

ID=68218424

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201910615099.9A Active CN110362537B (en) 2019-07-09 2019-07-09 Full-parameter private information retrieval method based on sawtooth decoding

Country Status (1)

Country Link
CN (1) CN110362537B (en)

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN105703782A (en) * 2016-03-11 2016-06-22 深圳大学 Incremental shift matrix construction method, network coding method and system
CN107241414A (en) * 2017-06-09 2017-10-10 深圳大学 A kind of private information retrieval method and system decoded based on zigzag
CN107317844A (en) * 2017-06-02 2017-11-03 深圳大学 Distributed storage method and system based on the decodable minimum memory expense of sawtooth
CN107992582A (en) * 2017-12-07 2018-05-04 深圳大学 One kind is based on the decoded Private information retrieval method of sawtooth
CN108628697A (en) * 2017-12-15 2018-10-09 深圳大学 One kind being based on binary node restorative procedure and system

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6850647B1 (en) * 1999-07-30 2005-02-01 Michael L. Gough System, method and article of manufacture for decompressing digital camera sensor data

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN105703782A (en) * 2016-03-11 2016-06-22 深圳大学 Incremental shift matrix construction method, network coding method and system
CN107317844A (en) * 2017-06-02 2017-11-03 深圳大学 Distributed storage method and system based on the decodable minimum memory expense of sawtooth
CN107241414A (en) * 2017-06-09 2017-10-10 深圳大学 A kind of private information retrieval method and system decoded based on zigzag
CN107992582A (en) * 2017-12-07 2018-05-04 深圳大学 One kind is based on the decoded Private information retrieval method of sawtooth
CN108628697A (en) * 2017-12-15 2018-10-09 深圳大学 One kind being based on binary node restorative procedure and system

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
"Bandwidth Overhead-Free Data Reconstruction Scheme for Distributed Storage Code With Low Decoding Complexity";Mingjun Dai等;《IEEE Access》;20170427;第6824-6832页 *
"Bandwidth Overhead-Free Data Reconstruction Scheme for Distributed Storage Code With Low Decoding Complexity";范永骏;《中国优秀硕士学位论文全文数据库 信息科技辑》;20170515;全文 *

Also Published As

Publication number Publication date
CN110362537A (en) 2019-10-22

Similar Documents

Publication Publication Date Title
Kumar et al. Achieving maximum distance separable private information retrieval capacity with linear codes
Mirmohseni et al. Private function retrieval
Wang et al. Symmetric private information retrieval for MDS coded distributed storage
Melchor et al. A lattice-based computationally-efficient private information retrieval protocol
Davidson et al. Frodopir: Simple, scalable, single-server private information retrieval
CN107241414B (en) A private information retrieval method and system based on zigzag decoding
Wang et al. Symmetric private information retrieval from MDS coded distributed storage with non-colluding and colluding servers
Agrawal et al. Explicit non-malleable codes against bit-wise tampering and permutations
Baldimtsi et al. Sorting and searching behind the curtain
Chang et al. On the upload versus download cost for secure and private matrix multiplication
Li et al. A survey on the applications of Niho exponents
Vithana et al. Semantic private information retrieval
Henry Polynomial batch codes for efficient IT-PIR
Tajeddine et al. Robust private information retrieval on coded data
Gordon et al. Simple and efficient two-server ORAM
Lin et al. An MDS-PIR capacity-achieving protocol for distributed storage using non-MDS linear codes
Dinur et al. Improved practical attacks on round-reduced Keccak
Obead et al. Capacity of private linear computation for coded databases
CN107992582B (en) Private information retrieval method based on sawtooth decoding
Mariot et al. A cryptographic and coding-theoretic perspective on the global rules of cellular automata
Lin et al. On the fundamental limit of private information retrieval for coded distributed storage
CN110362537B (en) Full-parameter private information retrieval method based on sawtooth decoding
WO2022110691A1 (en) Coding method, decoding method, electronic device and storage medium
Obead et al. Private polynomial function computation for noncolluding coded databases
CN118332159A (en) Numerical range query method for protecting privacy, index construction method and device

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant
EE01 Entry into force of recordation of patent licensing contract
EE01 Entry into force of recordation of patent licensing contract

Application publication date: 20191022

Assignee: Shenzhen Yunchuang Netcom Information Technology Co.,Ltd.

Assignor: SHENZHEN University

Contract record no.: X2023980047247

Denomination of invention: A Full Parameter Private Information Retrieval Method Based on Sawtooth Decoding

Granted publication date: 20211228

License type: Common License

Record date: 20231116

Application publication date: 20191022

Assignee: Yuncheng Holding (Shenzhen) Co.,Ltd.

Assignor: SHENZHEN University

Contract record no.: X2023980047231

Denomination of invention: A Full Parameter Private Information Retrieval Method Based on Sawtooth Decoding

Granted publication date: 20211228

License type: Common License

Record date: 20231116

Application publication date: 20191022

Assignee: Shenzhen Suowei Information Technology Co.,Ltd.

Assignor: SHENZHEN University

Contract record no.: X2023980047180

Denomination of invention: A Full Parameter Private Information Retrieval Method Based on Sawtooth Decoding

Granted publication date: 20211228

License type: Common License

Record date: 20231115

Application publication date: 20191022

Assignee: Sankexiaocao (Shenzhen) Internet of Things Technology Co.,Ltd.

Assignor: SHENZHEN University

Contract record no.: X2023980047154

Denomination of invention: A Full Parameter Private Information Retrieval Method Based on Sawtooth Decoding

Granted publication date: 20211228

License type: Common License

Record date: 20231115

EE01 Entry into force of recordation of patent licensing contract

Application publication date: 20191022

Assignee: Shenzhen chuangyue Precision Machinery Co.,Ltd.

Assignor: SHENZHEN University

Contract record no.: X2023980048053

Denomination of invention: A Full Parameter Private Information Retrieval Method Based on Sawtooth Decoding

Granted publication date: 20211228

License type: Common License

Record date: 20231123

Application publication date: 20191022

Assignee: Aixunda Technology (Shenzhen) Co.,Ltd.

Assignor: SHENZHEN University

Contract record no.: X2023980048047

Denomination of invention: A Full Parameter Private Information Retrieval Method Based on Sawtooth Decoding

Granted publication date: 20211228

License type: Common License

Record date: 20231123

Application publication date: 20191022

Assignee: SHENZHEN DING TUO DA ELECTROMECHANICAL Co.,Ltd.

Assignor: SHENZHEN University

Contract record no.: X2023980048382

Denomination of invention: A Full Parameter Private Information Retrieval Method Based on Sawtooth Decoding

Granted publication date: 20211228

License type: Common License

Record date: 20231124

Application publication date: 20191022

Assignee: Shenzhen Jiahui Education Technology Co.,Ltd.

Assignor: SHENZHEN University

Contract record no.: X2023980048376

Denomination of invention: A Full Parameter Private Information Retrieval Method Based on Sawtooth Decoding

Granted publication date: 20211228

License type: Common License

Record date: 20231124

Application publication date: 20191022

Assignee: Shenzhen Huihong Information Technology Co.,Ltd.

Assignor: SHENZHEN University

Contract record no.: X2023980048375

Denomination of invention: A Full Parameter Private Information Retrieval Method Based on Sawtooth Decoding

Granted publication date: 20211228

License type: Common License

Record date: 20231124

Application publication date: 20191022

Assignee: Shenzhen Guangwang Bozhan Technology Co.,Ltd.

Assignor: SHENZHEN University

Contract record no.: X2023980048373

Denomination of invention: A Full Parameter Private Information Retrieval Method Based on Sawtooth Decoding

Granted publication date: 20211228

License type: Common License

Record date: 20231124

Application publication date: 20191022

Assignee: DISCOVERY TECHNOLOGY (SHENZHEN) Co.,Ltd.

Assignor: SHENZHEN University

Contract record no.: X2023980048372

Denomination of invention: A Full Parameter Private Information Retrieval Method Based on Sawtooth Decoding

Granted publication date: 20211228

License type: Common License

Record date: 20231124

EE01 Entry into force of recordation of patent licensing contract
EE01 Entry into force of recordation of patent licensing contract
EE01 Entry into force of recordation of patent licensing contract

Application publication date: 20191022

Assignee: Shenzhen Zhihui Computer Technology Co.,Ltd.

Assignor: SHENZHEN University

Contract record no.: X2023980048429

Denomination of invention: A Full Parameter Private Information Retrieval Method Based on Sawtooth Decoding

Granted publication date: 20211228

License type: Common License

Record date: 20231127

Application publication date: 20191022

Assignee: Shenzhen Foresea Allchips Information & Technology Co.,Ltd.

Assignor: SHENZHEN University

Contract record no.: X2023980048420

Denomination of invention: A Full Parameter Private Information Retrieval Method Based on Sawtooth Decoding

Granted publication date: 20211228

License type: Common License

Record date: 20231127

Application publication date: 20191022

Assignee: Easy to sign chain (Shenzhen) Technology Co.,Ltd.

Assignor: SHENZHEN University

Contract record no.: X2023980048402

Denomination of invention: A Full Parameter Private Information Retrieval Method Based on Sawtooth Decoding

Granted publication date: 20211228

License type: Common License

Record date: 20231127

Application publication date: 20191022

Assignee: Shenzhen Ruibotong Technology Co.,Ltd.

Assignor: SHENZHEN University

Contract record no.: X2023980048397

Denomination of invention: A Full Parameter Private Information Retrieval Method Based on Sawtooth Decoding

Granted publication date: 20211228

License type: Common License

Record date: 20231127

Application publication date: 20191022

Assignee: SHENZHEN LIHAI HONGJIN TECHNOLOGY CO.,LTD.

Assignor: SHENZHEN University

Contract record no.: X2023980048392

Denomination of invention: A Full Parameter Private Information Retrieval Method Based on Sawtooth Decoding

Granted publication date: 20211228

License type: Common License

Record date: 20231127

Application publication date: 20191022

Assignee: SHENZHEN MAGIC-RAY TECHNOLOGY Co.,Ltd.

Assignor: SHENZHEN University

Contract record no.: X2023980048336

Denomination of invention: A Full Parameter Private Information Retrieval Method Based on Sawtooth Decoding

Granted publication date: 20211228

License type: Common License

Record date: 20231127

Application publication date: 20191022

Assignee: Shenzhen Lingyu Technology Co.,Ltd.

Assignor: SHENZHEN University

Contract record no.: X2023980048332

Denomination of invention: A Full Parameter Private Information Retrieval Method Based on Sawtooth Decoding

Granted publication date: 20211228

License type: Common License

Record date: 20231124

Application publication date: 20191022

Assignee: Matrix Origin (Shenzhen) Information Technology Co.,Ltd.

Assignor: SHENZHEN University

Contract record no.: X2023980048322

Denomination of invention: A Full Parameter Private Information Retrieval Method Based on Sawtooth Decoding

Granted publication date: 20211228

License type: Common License

Record date: 20231124

EE01 Entry into force of recordation of patent licensing contract
EE01 Entry into force of recordation of patent licensing contract

Application publication date: 20191022

Assignee: JIUZHOU YANGGUANG POWER SUPPLY (SHENZHEN) CO.,LTD.

Assignor: SHENZHEN University

Contract record no.: X2023980050235

Denomination of invention: A Full Parameter Private Information Retrieval Method Based on Sawtooth Decoding

Granted publication date: 20211228

License type: Common License

Record date: 20231206

Application publication date: 20191022

Assignee: Shenzhen Huike Energy Technology Co.,Ltd.

Assignor: SHENZHEN University

Contract record no.: X2023980050230

Denomination of invention: A Full Parameter Private Information Retrieval Method Based on Sawtooth Decoding

Granted publication date: 20211228

License type: Common License

Record date: 20231206

Application publication date: 20191022

Assignee: Shenzhen Huike Storage Technology Co.,Ltd.

Assignor: SHENZHEN University

Contract record no.: X2023980050228

Denomination of invention: A Full Parameter Private Information Retrieval Method Based on Sawtooth Decoding

Granted publication date: 20211228

License type: Common License

Record date: 20231205

Application publication date: 20191022

Assignee: Shenzhen Youyou Internet Co.,Ltd.

Assignor: SHENZHEN University

Contract record no.: X2023980049890

Denomination of invention: A Full Parameter Private Information Retrieval Method Based on Sawtooth Decoding

Granted publication date: 20211228

License type: Common License

Record date: 20231204

EE01 Entry into force of recordation of patent licensing contract
EE01 Entry into force of recordation of patent licensing contract

Application publication date: 20191022

Assignee: SHENZHEN QIANHAI MYTIME TECHNOLOGY HOLDING Co.,Ltd.

Assignor: SHENZHEN University

Contract record no.: X2023980051425

Denomination of invention: A Full Parameter Private Information Retrieval Method Based on Sawtooth Decoding

Granted publication date: 20211228

License type: Common License

Record date: 20231211

EE01 Entry into force of recordation of patent licensing contract
EE01 Entry into force of recordation of patent licensing contract

Application publication date: 20191022

Assignee: SHENZHEN HUIKE PRECISION INDUSTRY Co.,Ltd.

Assignor: SHENZHEN University

Contract record no.: X2023980052469

Denomination of invention: A Full Parameter Private Information Retrieval Method Based on Sawtooth Decoding

Granted publication date: 20211228

License type: Common License

Record date: 20231214

Application publication date: 20191022

Assignee: Xingang Intellectual Property Technology (Shenzhen) Co.,Ltd.

Assignor: SHENZHEN University

Contract record no.: X2023980052131

Denomination of invention: A Full Parameter Private Information Retrieval Method Based on Sawtooth Decoding

Granted publication date: 20211228

License type: Common License

Record date: 20231214

Application publication date: 20191022

Assignee: Shenzhen Shoucheng Enterprise Management Consulting Co.,Ltd.

Assignor: SHENZHEN University

Contract record no.: X2023980052091

Denomination of invention: A Full Parameter Private Information Retrieval Method Based on Sawtooth Decoding

Granted publication date: 20211228

License type: Common License

Record date: 20231213