CN111539027B

CN111539027B - Information verification method and system based on privacy protection of two parties

Info

Publication number: CN111539027B
Application number: CN202010650216.8A
Authority: CN
Inventors: 张祺智; 李漓春; 殷山
Original assignee: Alipay Hangzhou Information Technology Co Ltd
Current assignee: Ant Blockchain Technology Shanghai Co Ltd
Priority date: 2020-07-08
Filing date: 2020-07-08
Publication date: 2020-11-06
Anticipated expiration: 2040-07-08
Also published as: CN111539027A

Abstract

The present disclosure relates to the field of information security, and in particular, to an information verification method and system based on privacy protection of two parties. The specification of the present specification discloses an information verification method and system based on both-party privacy protection, which is executed by a first party or a second party, for determining the position of a minimum non-0 item in a target sequence stored in both-party and shared forms in the form of private data. In the calculation and determination process, the method can complete the calculation and verification operation of the data information of both sides by only one interaction; the two parties only interact once, the communication quantity of each party is log | A |, the total communication quantity is 2log | A |, and compared with the existing scheme, the method greatly reduces the communication quantity and lightens the transmission pressure.

Description

Information verification method and system based on privacy protection of two parties

Technical Field

The present disclosure relates to the field of information security, and in particular, to an information verification method and system based on privacy protection of two parties.

Background

The secure multi-party computation is also called multi-party secure computation, namely, a plurality of parties compute the result of a function together without revealing the input data of each party of the function, and the computed result is disclosed to one or more parties. Therefore, through secure multi-party computation, the participating parties can determine the minimum non-zero item of a sequence for subsequent computation without exposing respective original data.

The determination of the minimum non-zero term is a step in the multi-party security computation, and it is desirable to minimize the number of interactions and the amount of data transmitted during the determination of the minimum non-zero term.

Disclosure of Invention

One embodiment of one aspect of the present specification provides an information verification method based on privacy protection of both parties, the method being performed by a first party and used for determining a position of a minimum non-0 item in a target sequence stored in a form of private data between both parties and a shared form, the method including: obtaining a first fragment of the target sequence held by the first party; obtaining a first fragment of a variant sequence based on the first fragment of the target sequence; the change sequences are stored in both sides in a shared form; acquiring a first sequence and a first intermediate fragment; the first intermediate fragment is obtained based on a second sequence and the first sequence; the first sequence and the second sequence are generated randomly; acquiring first transmission data held by a second party; the first transmission data is obtained based on a second fragment and a second intermediate fragment of the varying sequence; the first intermediate fragment and the second intermediate fragment are in a sum sharing form of the first sequence and the second sequence; sending second transmission data to the second party; the second transmission data is obtained based on the first transmission data, the first sequence, the first intermediate partition, and the first partition of the varying sequence; obtaining implicit position information held by the second party; the implicit location information is derived based at least on the second transmission data; determining a minimum non-0 item position of the target sequence based on the implicit position information and the first sequence.

In one aspect, one embodiment of the present specification provides an information verification method based on privacy protection of two parties, the method performed by a second party for determining a position of a minimum non-0 item in a target sequence stored in a form of private data between the two parties and a shared form, the method including: acquiring a second fragment of the target sequence held by the second party; obtaining a second fragment of the variant sequence based on the second fragment of the target sequence; the change sequences are stored in both sides in a shared form; acquiring a second sequence and a second intermediate fragment; the first intermediate fragment and the second intermediate fragment are in a sum sharing form of the first sequence and the second sequence; the first sequence and the second sequence are generated randomly; sending first transmission data to the first party; the first transmission data is obtained based on a second slice of the varying sequence and the second intermediate slice; acquiring second transmission data held by the first party; the second transmission data is obtained based on the first transmission data, the first sequence, a first intermediate fragment, and a first fragment of the varying sequence; the first intermediate partition is derived based on the first sequence and the second sequence.

Obtaining a position sequence based on the second sequence and second transmission data; the only non-0 item in the position sequence is implicit position information; acquiring the first sequence; determining a minimum non-0 item position of the target sequence based on the implicit position information and the first sequence.

In another embodiment of the present specification, an information verification system based on privacy protection of both parties is provided, where the system is executed by a first party and is configured to determine a location of a minimum non-0 item in a target sequence stored in a form of private data between both parties and in a shared form, and includes a first obtaining module, a first calculating module, a second obtaining module, a third obtaining module, a first sending module, a fourth obtaining module, and a second calculating module; the first acquisition module is used for acquiring a first fragment of the target sequence held by the first party; the first computing module is used for obtaining a first fragment of a variation sequence based on the first fragment of the target sequence; the change sequences are stored in both sides in a shared form; the second acquisition module is used for acquiring the first sequence and the first intermediate fragment; the first intermediate fragment is obtained based on a second sequence and the first sequence; the first sequence and the second sequence are generated randomly; the third acquisition module is used for acquiring first transmission data held by a second party; the first transmission data is obtained based on a second fragment and a second intermediate fragment of the varying sequence; the first intermediate fragment and the second intermediate fragment are in a sum sharing form of the first sequence and the second sequence; the first sending module is used for sending second transmission data to the second party; the second transmission data is obtained based on the first transmission data, the first sequence, the first intermediate partition, and the first partition of the varying sequence; the fourth obtaining module is configured to obtain implicit location information held by the second party; the implicit location information is derived based at least on the second transmission data; the second calculation module is configured to determine a minimum non-0 position of the target sequence based on the implicit position information and the first sequence.

In another embodiment of the present specification, an information verification system based on privacy protection of both parties is provided, where the system is executed by a second party and is configured to determine a location of a minimum non-0 item in a target sequence stored in a form of private data in both parties and in a shared form, and includes a fifth obtaining module, a third calculating module, a sixth obtaining module, a second sending module, a seventh obtaining module, a fourth calculating module, an eighth obtaining module, and a fifth calculating module; the fifth obtaining module is configured to obtain a second fragment of the target sequence held by the second party; the third computing module is configured to obtain a second segment of the varying sequence based on the second segment of the target sequence; the change sequences are stored in both sides in a shared form; the sixth obtaining module is configured to obtain a second sequence and a second intermediate fragment; the first intermediate fragment and the second intermediate fragment are in a sum sharing form of the first sequence and the second sequence; the first sequence and the second sequence are generated randomly; the second sending module is used for sending first transmission data to the first party; the first transmission data is obtained based on a second slice of the varying sequence and the second intermediate slice; the seventh obtaining module is configured to obtain second transmission data held by the first party; the second transmission data is obtained based on the first transmission data, the first sequence, a first intermediate fragment, and a first fragment of the varying sequence; the first intermediate fragment is obtained based on the first sequence and the second sequence; the fourth calculation module is configured to obtain a position sequence based on the second sequence and the second transmission data; the only non-0 item in the position sequence is implicit position information; the eighth obtaining module is configured to obtain the first sequence; the fifth calculation module is to determine a minimum non-0 position of the target sequence based on the implicit position information and the first sequence.

In an aspect of an embodiment of the present specification, a computer-readable storage medium is provided, where the storage medium stores computer instructions, and when a computer reads the computer instructions in the storage medium, the computer executes the information verification method based on privacy protection of both parties as described above.

Drawings

The present description will be further explained by way of exemplary embodiments, which will be described in detail by way of the accompanying drawings. These embodiments are not intended to be limiting, and in these embodiments like numerals are used to indicate like structures, wherein:

FIG. 1 is a schematic diagram of an application scenario of an information verification system based on two-party privacy protection according to some embodiments of the present description;

FIG. 2 is an exemplary flow diagram of a method for information verification based on two-party privacy protection according to some embodiments of the present description;

FIG. 3 is a schematic diagram of a portion of an interaction of a method for information verification based on privacy protection of two parties, according to some embodiments of the present description;

FIG. 4 is an exemplary flow diagram of a method for information verification based on two-party privacy protection according to further embodiments of the present description;

FIG. 5 is an exemplary block diagram of an information verification system based on two-party privacy protection according to some embodiments of the present description;

FIG. 6 is an exemplary block diagram illustrating information verification based on two-party privacy protection according to further embodiments of the present description.

Detailed Description

In order to more clearly illustrate the technical solutions of the embodiments of the present disclosure, the drawings used in the description of the embodiments will be briefly described below. It is obvious that the drawings in the following description are only examples or embodiments of the present description, and that for a person skilled in the art, the present description can also be applied to other similar scenarios on the basis of these drawings without inventive effort. Unless otherwise apparent from the context, or otherwise indicated, like reference numbers in the figures refer to the same structure or operation.

It should be understood that "system", "device", "unit" and/or "module" as used in this specification is a method for distinguishing different components, elements, parts or assemblies at different levels. However, other words may be substituted by other expressions if they accomplish the same purpose.

As used in this specification and the appended claims, the terms "a," "an," "the," and/or "the" are not intended to be inclusive in the singular, but rather are intended to be inclusive in the plural, unless the context clearly dictates otherwise. In general, the terms "comprises" and "comprising" merely indicate that steps and elements are included which are explicitly identified, that the steps and elements do not form an exclusive list, and that a method or apparatus may include other steps or elements.

Flow charts are used in this description to illustrate operations performed by a system according to embodiments of the present description. It should be understood that the preceding or following operations are not necessarily performed in the exact order in which they are performed. Rather, the various steps may be processed in reverse order or simultaneously. Meanwhile, other operations may be added to the processes, or a certain step or several steps of operations may be removed from the processes.

For the purpose of illustrating embodiments of the present specification, reference will first be made to the mathematical knowledge involved therein.

In mathematics, a "group" in mathematics means an algebraic structure having a binary operation satisfying a closed property, satisfying a binding law, having a unit element and an inverse element, and includes an abelian group, homomorphism and conjugate class. Where the sign of the binary operation may be generally used as a sign of a multiplication sign "+" (which may be omitted when unambiguous) or an addition sign "+", it is noted that the binary operation is not necessarily equivalent to a multiplication or an addition in a four-way operation. The result of several elements through one or more binary operations may be referred to as a sum.

The binary operation of the group satisfies: 1. closed law, for any element a, b in G, a × b is still in G; 2. the binding law for any elements a, b and c in G is

(ii) a 3. With a unit cell, the element e being present in G, such that

(ii) a 4. With an inverse element, for any element a in G, b is present in G, such that

A and b are inverse elements of each other, and e is a unit element. It should be noted that e may be called zero and the inverse may be called negative for the binary operation denoted by "+", and a + (inverse of b) may be denoted by a-b for any of the elements a, b in G. The order of the group operations is important, element a is combined with element b, and the result is not necessarily the same as combining element b with element a; namely the law of exchange

It is not always true that a group satisfying the commutative law is called an abelian group (commutative group), a group not satisfying the commutative law is called a non-abelian group (non-commutative group), and the abelian group is composed of its own set G and binary operation.

In mathematics, a finite field is a field that contains a finite number of elements, the number of elements of the finite field being called its order. Like other fields, a finite field is a set that is defined for performing addition, subtraction, multiplication, and division operations and satisfies certain rules. The most common example of a finite field is when p is a prime number, an integer modulo p. The modulus operation is defined as the remainder of dividing one number by another number. For example, the modulo operation of dividend a and divisor n is written,

assuming that a =5 and n =2, it is known that the remainder of division of 5 by 2 is 1

=

。

In mathematics, a mapping is often equivalent to a function. For example, assuming that a and B are two non-empty sets, if for any element x in a, there is always a uniquely determined element y in B corresponding to it according to some rule (or law) f, the corresponding rule f is called a mapping from a to B. Record as

An image in which y is denoted by x is referred to as

And x is called the primary image of y, the set A is called the domain of the mapping f, and the set B is called the cosomain of f.

In mathematics, a group G is given, wherein the G mode refers to an Abelian group M generated after the group G is compatible with an Abelian group structure in M. Wherein for each G ∈ G, a ∈ M, there is onlyA determined product

M, and for any

And

all the requirements are that: (1) a

，(2)、

，(3)、

，

M is the left G module if the element is the unit element in the group G; if it is

M is called the trivial left G mode.

Further, the present description relates to a quotient group based on integer abelian group, the mathematical representation of which may be G: = Z/nZ, where Z is a set of integers, n is any positive integer, nZ is a subgroup of Z made up of all multiples of n, quotient Z/nZ is a cyclic group of order n modulo the remainder of n, equivalent to mod n. It should be noted that unless it is defined in the present specification that the sum is based on group addition/the product is based on group multiplication, the sum/product should be understood as a concept in a four-way operation. In addition, since the sum values in the four arithmetic operations are directly expressed by the sum values in the present specification, the sum values based on the group addition and the slices based on the group addition can be directly simplified into the sum values and the slices in the present specification without causing ambiguity.

In some distributed scenarios, multiple parties are required to securely compute the value of a function, hereSecurity may refer to the correctness of the output result and the confidentiality of the input information and the output information. For example, in some machine learning scenarios, one party holds private feature data and the other holds private tag data. If a function value is directly calculated for private data (feature data/tag data), leakage of the function value may cause the private data to be inferred. For this reason, each party can split the private data x held by itself into two parts, and one of the two parts is reserved

And mixing the other part

The information is sent to the other party,

and

the sum of (a) is x. Then, the two parties operate a safety calculation protocol to respectively obtain a fragment of the function value. Sharded and shared versions of two parties

Namely, the function value, an attacker needs to obtain the two-party fragment if the attacker wants to know the private data.

Embodiments in this specification provide an information verification method and system based on two-party privacy protection, which may calculate and verify results required by two parties for private data of the two parties and fragments thereof, so as to ensure the accuracy of the calculation results and the verification results while protecting data privacy.

Fig. 1 is a schematic diagram of an application scenario of an information verification system based on two-party privacy protection according to some embodiments of the present specification.

As shown in fig. 1, more than two first parties 110, second parties 120, semi-trusted third parties 130, and networks 140 may be included in an application scenario. The first party 110 and the second party 120 may be computing devices of both parties participating in secure computing. The information verification system 100 can perform calculation and verification on data required by two parties on the premise of privacy protection of the two parties by implementing the method and/or process disclosed in the specification.

In some embodiments, the information verification system 100 may be applied in data computing scenarios for various industries, including but not limited to the financial industry, the internet industry, and the like. In the above industry, the information verification system 100 may be applied to the following scenarios: for example, the size of the multi-party data is compared, the number of times of solving the polynomial is calculated, the maximum value of several data is calculated, and the like under the security privacy protection.

In some embodiments, both the first party 110 and the second party 120 may perform data calculation operations and provide partially encrypted calculation data to the other party, and the accuracy of the required calculation data may be verified without destroying the private data information of both parties. The above-described method is merely for convenience of understanding, and the present system may also be implemented in other possible operation modes.

The first party 110 may refer to a node comprising a user terminal of a party or a cluster of user terminal devices belonging to a party and being connected to the access network via a network interface. In some embodiments, the cluster of devices may be centralized or distributed. In some embodiments, the cluster of devices may be regional or remote. A user terminal may refer to one or more terminal devices or software used by a user. The user terminal may include a processing unit, a display unit, an input/output unit, a sensing unit, a storage unit, and the like. The sensing unit may include, but is not limited to, a light sensor, a distance sensor, an acceleration sensor, a gyro sensor, a sound detector, and the like, or any combination thereof. In some embodiments, the user terminal may be one or any combination of a mobile device, a tablet computer, a laptop computer, a desktop computer, or other device having input and/or output capabilities. In some embodiments, the user terminal may be used by one or more users, and may include users who directly use the service, and may also include other related users.

The second party 120 may be for aggregation of multiple user nodes. The second party 120 may refer to a node comprising a single device of a party or a cluster of devices belonging to a party and connected to the access network via a network interface. In some embodiments, the cluster of devices may be centralized or distributed. In some embodiments, the cluster of devices may be regional or remote. In some embodiments, second party 120 may include a host, terminal, or like device. Such as servers, computers possessing computing resources, and the like.

Network 140 may connect the various components of the system and/or connect the system with external resource components. Network 140 enables communication between the various components and with other components outside the system to facilitate the exchange of data and/or information. In some embodiments, the network 140 may be any one or more of a wired network or a wireless network. For example, network 140 may include a cable network, a fiber optic network, a telecommunications network, the internet, a Local Area Network (LAN), a Wide Area Network (WAN), a Wireless Local Area Network (WLAN), a Metropolitan Area Network (MAN), a Public Switched Telephone Network (PSTN), a bluetooth network, a ZigBee network (ZigBee), Near Field Communication (NFC), an in-device bus, an in-device line, a cable connection, and the like, or any combination thereof. The network connection between the parts can be in one way or in multiple ways. In some embodiments, the network may be a point-to-point, shared, centralized, etc. variety of topologies or a combination of topologies. In some embodiments, network 140 may include one or more network access points. For example, the network 140 may include wired or wireless network access points, such as base stations and/or network switching points 140-1, 140-2, …. Through these access points, one or more components of system 100 may connect to network 140 to exchange data and/or information.

In some embodiments, the information verification system 100 may also include a semi-trusted third party 130. In some embodiments, the semi-trusted third party 130 is a server or device capable of performing computing operations. Such as cooperating computing devices, random number servers, and the like. The semi-trusted third party 130 may assist the two-party computing device in running a secure multiplication protocol.

In some embodiments, the product of two private data of group multiplication based on the secure multiplication protocol may be converted into two fragments based on group addition through a two-party secure multiplication protocol, and after multiple rounds of interactive computation, the first party 110 and the second party 120 each execute one fragment and ensure that the private data of either party is not leaked in the computation process. The transmission quantity is positively correlated with the sequence dimension of the calculated data in the two-party interaction, and the scheme has the problems of more interaction times and large transmission quantity, thereby bringing the problems of complicated calculation process and high complexity.

The method aims to solve the problems of multiple interaction times, complex calculation process and the like when a safe multiplication protocol is executed in some embodiments. In some embodiments, an information verification system 100 based on two-party privacy protection is provided, and the information verification system 100 can complete calculation and verification operations of two-party data information with a small number of interactions.

FIG. 2 is an exemplary flow diagram of a method for information verification based on two-party privacy protection according to some embodiments of the present description.

Fig. 3 is a partial interaction diagram of an information verification method based on two-party privacy protection according to some embodiments of the present disclosure.

As shown in fig. 2 and 3, the method 200 is used by the first party 110 to determine the location of the smallest non-0 item in the target sequence stored in the form of private data in the target sequence of both parties and in the shared form, and in some embodiments, one or more steps of the method 200 in fig. 2 may be performed by the system 100 in fig. 1, which includes the following steps:

step 210, obtaining a first fragment of the target sequence of the first party 110. In some embodiments, step 210 may be performed by the first obtaining module 510.

The minimum non-0 item refers to the first non-0 element in the sequence, and the position of the minimum non-0 item refers to the arrangement position of the corresponding first non-0 element in the corresponding sequence. For example only, assume that the target sequence is x, and that the target sequence x belongs to a finite field

In which the sequence

Is an n-dimensional 0-1 vector (the elements in the vector are only 0 or 1) on a finite field F, p is the number of the elements in the finite field, and a segment can be understood as an element in the finite field. Assume that the first fragment of the target sequence x is

The second fragment of the target sequence x is

Then the sum of the target sequence x is shared in the form of

. Assuming that the target sequence x = (0,0,1,0,1,0,1), it can be known that the minimum non-0 element of the target sequence x is the element "1" arranged at the 3 rd position, the 5 th position in the sequence is also "1", but the third position is earlier than the fifth position, i.e. the minimum position is the smallest position. Note that, when determining the position of the minimum non-0 entry, the position of the first element in the sequence is denoted as "0 th bit", and therefore, it can be found that the position of the minimum non-0 entry in the target sequence x = (0,0,1,0,1,0,1) is the 2 nd bit.

In some embodiments, a first fragment of a target sequence x held by a first party 110 may be obtained

. The first party 110 and the second party 120 are the two parties involved in the information verification method. In some embodiments, a first fragment of a target sequence x held by a first party 110 may be obtained

. Wherein the first segment

Invisible to the second party 120 for private data stored at the first party 110; in the same way, the second section

To be private data stored at the second party 120, is not visible to the first party 110.

Step 220, obtaining a first fragment of the variant sequence based on the first fragment of the target sequence. Step 220 may be performed by the first calculation module 520 in some embodiments.

The variant sequence is calculated from the target sequence x. For example only, assume that the change sequence is y and the target sequence x = (0,0,1,0,1,0,1), i.e., n = 7. The rule for calculating the variation sequence y by the target sequence x is: firstly, the elements in a target sequence x are accumulated bit by bit to obtain

= (0,0,1,1,2,2,3), then use

Subtracting 2 times of the original target sequence x to obtain

= (0,0,1,1,2,2,3) - (0,0,2,0, 2) = (0,0, -1,1,0,2,1), and finally use

Adding 1 to obtain

= (1,1,0,2,1,3, 2). It can be seen that the position of the minimum non-0 item of the target sequence x is the 2 nd bit, and the position of the change sequence y, which is the only 0 item, is the 2 nd bit, i.e. the position of the change sequence y, which is the only 0 item, is the position of the minimum non-0 item of the target sequence x.

In some embodiments, the first partition, which may be based on the target sequence x, may be

Obtaining a first fragment of varying sequence y

. Since the variation sequence y can be obtained based on the target sequence x with the aforementioned calculation rule, the first slice of the variation sequence y

The acquisition rule of (a) may refer to an acquisition rule for calculating the variant sequence y based on the target sequence x, i.e. slicing the first fragment of the target sequence x

After input into the first party 110 to execute the above-mentioned acquisition rule, the first fragment of the variation sequence y can be obtained

。

In some embodiments, the variation sequence y may be stored in both parties in a shared form. That is, in some embodiments, the sum share of the variation sequence y may be expressed as:

（1）

wherein,

for the second fragment of the variant sequence y, the second party 120, in some embodiments, is compared to the first fragment of the variant sequence

Similarly, a second partition based on the target sequence x may be used

And (4) calculating.

Step 230, obtain the first sequence and the first intermediate segment. In some embodiments, step 230 may be performed by the second acquisition module 530.

For example only, let the first sequence be g, the second sequence be u, and the first intermediate segment be

The second intermediate segment is

. In some embodiments, the first sequence g and the second sequence u may be generated randomly.

In some embodiments, the first sequence g and the second sequence u may be randomly generated by the semi-trusted third party 130. The manner of generating the random numbers and the random sequences is a common technique in the art, and will not be described herein in too much detail.

In some embodiments, the first intermediate shard

Can be derived based on the second sequence u and the first sequence g. By way of example only, a first intermediate slice

The privacy data are split in the first sequence g; wherein the first sequence G belongs to a finite group G, the second sequence u is a sequence in an Abelian group A, the second intermediate slice

Is the private data split out in the second sequence u, and a is the G-module. In some embodiments, the first intermediate shard

And a second intermediate slice

In the form of a sum share of a first sequence g and a second sequence u. In some embodiments, this may be expressed as:

（2）

wherein the first sequence g and the second sequence in the formula (2)The column u is randomly generated by the semi-trusted third party 130, and gu is the contribution of the group G on a (G-mode). Thus, if the second intermediate slice is randomly generated

In the second party 120, a first intermediate patch may be calculated based on equation (2)

(ii) a Similarly, if the first intermediate fragment is randomly generated

A second intermediate patch can be calculated

. In some embodiments, the semi-trusted third party 130 may send the calculated (g,

) To the first party 110, the calculated (u,

) To the second party 120. Wherein the content of (g,

) Private data, which is the first party 110, is not visible to the second party 120; (u is a unit of time for which,

) Is private data of the second party 120, not visible to the first party 110.

In some embodiments, the first sequence g may include a shift vector and a random sequence having a length that is the same as the length of the target sequence x. For example only, assume a shift vector of

The random sequence is

. In some embodiments, this may be expressed as:

（3）

wherein, the random sequence in the formula (3)

Is represented by

Multiplying each element in the multiplied vector by a randomly generated vector k bit by bit and dividing the multiplied vector k by p, wherein k is the randomly generated vector with the same length as the target sequence, and the element in the random vector k is a finite field

Elements 1 to p in (1). Shift vector

It means "shift each element in the target vector left by j units", where j is a randomly generated integer with a value of 1 to n-1. Random sequence

And a shift vector

The calculations of (a) are exemplified hereinafter.

At step 240, the first transmission data of the second party 120 is obtained. In some embodiments, step 240 may be performed by third acquisition module 540.

The first transmission data is the interactive data that the second party 120 calculates and sends to the first party 110. In some embodiments, the first transmission data may be based on the second intermediate shard

For the second part of the variation sequence y

And a perturbation. For example only, assuming that the first transmission data is c, in some embodiments, it may be expressed as:

（4）

wherein the second intermediate segment in the formula

May be sent by the semi-trusted third party to the second party 120 in step 230.

In some embodiments, due to the second section

And a second intermediate slice

Is the sequence in abelian group a, it is obvious that the first transmission data c is also the sequence in abelian group a, so the data of the first party 110, i.e. the data transmission amount of the second party 120 in step 240 is

。

In step 250, in embodiments where the second transmission data is sent to the second party 120, step 250 may be performed by the first sending module 550.

The second transmission data is the interactive data that the first party 110 calculates and then sends to the second party 120. In some embodiments, the second transmission data may be based on the first transmission data c, the first sequence g, the first intermediate slice

And a first fragment of varying sequence y

Thus obtaining the product. For example only, assuming that the second transmission data is d, in some embodiments, it may be expressed as:

（5）

wherein g in formula (5) is the first sequence g in step 230, and is generated by the semi-trusted third party 130;

for the first intermediate slice in step 230

，

For the first slice of the changed sequence y in step 220

And c is the first transmission data c in step 240.

In some embodiments, since the calculated elements in the second transmission data d are all sequences in abelian group a, it is obvious that the second transmission data d is also sequences in abelian group a, the data transmission amount of the first party 110, i.e. the second party 120, in step 250 is as follows

。

Step 260, obtaining the implicit location information of the second party 120. In some embodiments, step 260 may be performed by a fourth acquisition module 560.

The position sequence is denoted as w, it should be noted that the position sequence w includes implicit position information, where the implicit position information refers to a unique position of a non-0 item in the change sequence y, or a unique zero position in the position sequence w. For example only, assuming that the implicit location information is i, the expression of the implicit location information i may be: the position of the position sequence w which is only 0 item is the ith bit. For example only, assuming a position sequence w = (1,0,1,1,2), it can be derived that the position of the unique 0 entry in the sequence w is the 1 st bit, i.e., for the position sequence w, the implicit position information i = 1.

In some embodiments, the sequence of positions w may be derived based on at least the second transmission data d. In some embodiments, this may be expressed as:

(6)

where d in equation (6) is the second transmission data d in step 250, u is the second sequence u in step 230, and the second sequence u may be generated by the semi-trusted third party 130.

In some embodiments, the sequence of positions w is equivalent to a second intermediate slice of the second party 120 variation sequence y

That is to say that,

= w, while referring to equation (3), in some embodiments, equation (1) may be further expressed as:

（7）

where w is the sequence in group A and gw is the effect of group G on A (G mode). Continuing with the example in step 210, taking n =7 and p =11, assume that the change sequence y = (1,1,0,2,1,3,2), shift vector

Has a random number j =4 and a random sequence of

Medium vector k = (9,1,2,3,6,4,8), n =7, p = 11. It is understood that the variation sequence y can be obtained by shifting each element in the position sequence w by 4 units to the left and multiplying the elements in the vector k by mod 11, which is obtained byWhen the variation sequence y is known, to calculate the position sequence, each of the variation sequences y is shifted to the right by 4 units to obtain (2,1,3,2,1,1,0), i.e. the sequence is

Then, from the vector k = (9,1,2,3,6,4,8), that is, the result of bit-wise multiplying the vector k by each element in the position sequence w is (2,1,3,2,1,1,0), the position sequence w = (10,1,7,8,2,3,0) is easily calculated. It can be further derived that the position of the position sequence w held by the second party 120, which is only 0, is the 6 th bit, i.e. the implicit position information i =6 held by the first party 110 and the second party.

It should be noted that the first party 110 implies the position information i and does not obtain the position sequence w containing the position information i, so that there is no risk of data leakage in the interaction.

Step 270, determining a minimum non-0 item position of the target sequence based on the implicit position information and the first sequence. In some embodiments, step 270 may be performed by second calculation module 570.

In some embodiments, the shift vector may be based on implicit location information i and

the position of the only 0 entry in the change sequence y is determined. Continuing with the example in step 260, finding the position sequence w = (10,1,7,8,2,3,0) may in turn yield that the position of the position sequence w, which is only 0 entry, is the 6 th bit, i.e. implicit position information i = 6. In some embodiments, the first party 110 random number j =4, i =6 obtained in step 260, is substituted into the formula:

（8）

therefore, it can be derived from equation (8) that the position of the smallest non-0 term in the target sequence x is the 2 nd bit.

In some embodiments, the only non-0 term position in the variant sequence is the smallest non-0 term position of the target sequence. That is, the only position 2 of 0 in the obtained change sequence y is the minimum non-0 position of the target sequence x, the first party 110 implies the position information i in the calculation, and does not obtain the position sequence w containing the position information i, so that the change sequence y and the target sequence x cannot be calculated, and the private data of both parties are protected. For the description of the specific calculation process, reference may be made to the foregoing description, and details are not repeated here.

FIG. 4 is an exemplary flow diagram of a method for information verification based on two-party privacy protection according to further embodiments of the present disclosure.

As shown in fig. 3 and 4, the method 300 is used by the second party 120 to determine the location of the smallest non-0 item in the target sequence stored in the form of private data in the target sequence of both parties and in the shared form, and in some embodiments, one or more steps of the method 300 in fig. 4 may be performed by the system 100 in fig. 1, which includes the following steps:

step 310, obtain the second fragment of the target sequence of the second party 120. In some embodiments, step 310 may be performed by the fifth obtaining module 610.

Second fragment for target sequence x

The obtaining can be referred to as step 210, and is not described herein.

Step 320, a second partition of the variant sequence is obtained based on the second partition of the target sequence. In some embodiments, step 320 may be performed by the third calculation module 620.

Second section for a sequence of variations y

Can be seen in the first slice based on the target sequence x in step 210

Obtaining a first fragment of a sequence of variations y

The obtaining rule of (2) is not described herein again.

Step 330, a second sequence and a second intermediate segment are obtained. In some embodiments, step 330 may be performed by a sixth acquisition module 630.

With respect to the second sequence u and the second intermediate slice

For the acquisition, see step 230, which is not described herein again.

In step 340, the first transmission data is sent to the first party 110, and in some embodiments, step 340 is performed by the second sending module 640.

For the sending and obtaining of the first transmission data c, refer to step 240, and are not described herein.

Step 350, obtaining second transmission data of the first party 110. In some embodiments, step 350 is performed by seventh acquisition module 650.

For the sending and obtaining of the second transmission data d, refer to step 250, which is not described herein.

And 360, obtaining a position sequence based on the second sequence and the second transmission data. In some embodiments, step 360 is performed by a fourth calculation module 660.

For the calculation of the position sequence w, see step 260, and will not be described in detail herein.

In some embodiments, the only 0 entries in the sequence of positions w are the implicit position information i. For the determination of the implicit information position i, see step 230, it is not described herein.

At step 370, a first sequence is obtained. In some embodiments, step 370 is performed by the second acquisition module 670.

For the calculation of the first sequence g, see step 230, which is not described herein.

It should be noted that, in some embodiments, the first sequence g may include a random sequence

And a shift vector

Referring to equation (8), only the shift vector is needed to calculate the minimum non-0 position

The medium random number j, in some embodiments, the second party 120 obtains the first party 110 vector

Or a random number j.

Step 380, determining the minimum non-0 item position of the target sequence based on the implicit position information and the first sequence. In some embodiments, step 380 is performed by a fifth calculation module 680.

For the determination of the minimum non-0 item position of the target sequence x, see step 270. Based on the above steps, since the first party 110 holds the random number j and the second party 120 holds the implicit location information i, when both or any one of the parties need to verify the calculation result, only the random number j or the implicit location information i held by the other party needs to be acquired, so that the private data of both parties is protected in security. In addition, the initiator other than the first party 110 and the second party 120 may perform calculation result verification, and the initiator may obtain the random number j and the implicit location information i from the first party 110 and the second party 120 respectively during calculation, so that the initiator cannot deduce the target sequence based on only the random number j and the implicit location information i, thereby ensuring security of privacy information of both parties.

FIG. 5 is a schematic diagram of an information verification system based on two-party privacy protection according to some embodiments of the present description.

As shown in fig. 5, the system 500 executed by the first party 110 for determining the location of the minimum non-0 item in the target sequence stored in both the party and the shared form in the form of private data includes a first obtaining module 510, a first calculating module 520, a second obtaining module 530, a third obtaining module 540, a first sending module 550, a fourth obtaining module 560, and a second calculating module 570. In some embodiments, the first acquisition module 510 is configured to acquire a first fragment of a target sequence held by the first party 110. In some embodiments, the first calculation module 520 is configured to derive a first partition of the variant sequence based on the first partition of the target sequence. Wherein the change sequence is stored in both of them in a shared form. In some embodiments, the second obtaining module 530 is configured to obtain the first sequence and the first intermediate slice. The first intermediate fragment is obtained based on the second sequence and the first sequence, and the first sequence and the second sequence are generated randomly. In some embodiments, the third obtaining module 540 is configured to obtain the first transmission data of the second party 120, where the first transmission data is obtained based on the second sequence of the second slices and the second intermediate slices, and the first intermediate slices and the second intermediate slices are in a sum sharing form of the first sequence and the second sequence.

In some embodiments, the first sending module 550 is configured to send the second transmission data to the second party 120, the second transmission data being obtained based on the first transmission data, the first sequence, the first intermediate fragment, and the first fragment of the varying sequence. In some embodiments, the fourth obtaining module 560 is used to obtain implicit location information for the second party 120. Wherein the implicit location information is derived based on at least the second transmission data. In some embodiments, the second calculation module 570 is to determine a minimum non-0 item position of the target sequence based on the implicit position information and the first sequence.

In some embodiments, the shift vector is generated randomly and the random sequence is the same length as the target sequence.

In some embodiments, the minimum non-0-term position of the target sequence may be determined based on the position information and the shift vector, including: the only 0-entry position in the change sequence is determined based on the position information and the shift vector. Wherein the only 0-term position in the variation sequence is the minimum non-0-term position of the target sequence.

In some embodiments, the first sequence and the second sequence are randomly generated by a semi-trusted third party.

FIG. 6 is a schematic diagram of an information verification system based on two-party privacy protection according to further embodiments of the present description.

As shown in fig. 6, the system 600 is executed by the second party 120 for determining the position of the minimum non-0 item in the target sequence stored in the form of private data in the target sequence of both parties and in the shared form, and includes a fifth obtaining module 610, a third calculating module 620, a sixth obtaining module 630, a second sending module 640, a seventh obtaining module 650, a fourth calculating module 660, an eighth obtaining module 670, and a fifth calculating module 680. In some embodiments, the fifth obtaining module 640 is configured to obtain a second fragment of the target sequence held by the second party 120. In some embodiments, the third calculation module 620 is configured to derive a second slice of the varying sequence based on the second slice of the target sequence. Wherein the change sequence is stored in both of them in a shared form. In some embodiments, the sixth obtaining module 630 is configured to obtain the second sequence and the second intermediate slice. The first intermediate fragment and the second intermediate fragment are in a sum sharing form of a first sequence and a second sequence, and the first sequence and the second sequence are generated randomly. In some embodiments, the second sending module 640 is configured to send the first transmission data to the first party 110, the first transmission data being obtained based on the second segment and the second intermediate segment of the varying sequence. In some embodiments, the seventh obtaining module 650 is configured to obtain the second transmission data of the first party 110. The second transmission data is obtained based on the first transmission data, the first sequence, the first intermediate fragment and the first fragment of the change sequence, and the first intermediate fragment is obtained based on the first sequence and the second sequence. In some embodiments, the fourth calculation module 660 is configured to obtain the position sequence based on the second sequence and the second transmission data, wherein only non-0 item in the position sequence is the implicit position information. In some embodiments, the eighth acquiring module is configured to acquire the first sequence. In some embodiments, the fifth calculation module is to determine a minimum non-0 item position of the target sequence based on the implicit position information and the first sequence.

In some embodiments, the first sequence comprises a randomly generated shift vector and a random sequence of the same length as the target sequence.

In some embodiments, the minimum non-0 item position of the target sequence may be determined based on the implicit position information and the first sequence, including: the unique non-0 entry position in the varying sequence is determined based on the implicit position information and the shift vector. Wherein the only non-0 item position in the change sequence is the minimum non-0 item position of the target sequence.

It should be noted that the above description of the system and its modules is for convenience only and should not limit the present disclosure to the illustrated embodiments. It will be appreciated by those skilled in the art that, given the teachings of the system, any combination of modules or sub-system configurations may be used to connect to other modules without departing from such teachings. For example, in some embodiments, the obtaining module and the calculating module may be two modules, or may be combined into one module. Such variations are within the scope of the present disclosure.

The embodiment of the specification also provides a computer readable storage medium. The storage medium stores computer instructions, and after the computer reads the computer instructions in the storage medium, the computer realizes the information verification method based on both-party privacy protection.

The beneficial effects that may be brought by the embodiments of the present description include, but are not limited to: (1) in the calculation and determination process, the information verification method based on the privacy protection of the two parties can finish the calculation and verification operation of the data information of the two parties only by interacting once; (2) the two parties only interact once and the communication volume of each party is

Total amount of traffic

Compared with a safe multiplication calculation scheme, the method greatly reduces communication quantity and lightens transmission pressure; (3) the two parties do not reveal the private data of each party in the calculation process, and the safety protection of the private data of each party is realized. It is to be noted that different embodiments may produce different advantages, and in different embodiments, any one or combination of the above advantages may be produced, or any other advantages may be obtained.

Having thus described the basic concept, it will be apparent to those skilled in the art that the foregoing detailed disclosure is to be regarded as illustrative only and not as limiting the present specification. Various modifications, improvements and adaptations to the present description may occur to those skilled in the art, although not explicitly described herein. Such modifications, improvements and adaptations are proposed in the present specification and thus fall within the spirit and scope of the exemplary embodiments of the present specification.

Also, the description uses specific words to describe embodiments of the description. Reference throughout this specification to "one embodiment," "an embodiment," and/or "some embodiments" means that a particular feature, structure, or characteristic described in connection with at least one embodiment of the specification is included. Therefore, it is emphasized and should be appreciated that two or more references to "an embodiment" or "one embodiment" or "an alternative embodiment" in various places throughout this specification are not necessarily all referring to the same embodiment. Furthermore, some features, structures, or characteristics of one or more embodiments of the specification may be combined as appropriate.

Moreover, those skilled in the art will appreciate that aspects of the present description may be illustrated and described in terms of several patentable species or situations, including any new and useful combination of processes, machines, manufacture, or materials, or any new and useful improvement thereof. Accordingly, aspects of this description may be performed entirely by hardware, entirely by software (including firmware, resident software, micro-code, etc.), or by a combination of hardware and software. The above hardware or software may be referred to as "data block," module, "" engine, "" unit, "" component, "or" system. Furthermore, aspects of the present description may be represented as a computer product, including computer readable program code, embodied in one or more computer readable media.

The computer storage medium may comprise a propagated data signal with the computer program code embodied therewith, for example, on baseband or as part of a carrier wave. The propagated signal may take any of a variety of forms, including electromagnetic, optical, etc., or any suitable combination. A computer storage medium may be any computer-readable medium that can communicate, propagate, or transport a program for use by or in connection with an instruction execution system, apparatus, or device. Program code located on a computer storage medium may be propagated over any suitable medium, including radio, cable, fiber optic cable, RF, or the like, or any combination of the preceding.

Computer program code required for the operation of various portions of this specification may be written in any one or more programming languages, including an object oriented programming language such as Java, Scala, Smalltalk, Eiffel, JADE, Emerald, C + +, C #, VB.NET, Python, and the like, a conventional programming language such as C, Visual Basic, Fortran2003, Perl, COBOL2002, PHP, ABAP, a dynamic programming language such as Python, Ruby, and Groovy, or other programming languages. The program code may execute entirely on the user's computer, partly on the user's computer, as a stand-alone software package, partly on the user's computer and partly on a remote computer or entirely on the remote computer or processing device. In the latter scenario, the remote computer may be connected to the user's computer through any network format, such as a Local Area Network (LAN) or a Wide Area Network (WAN), or the connection may be made to an external computer (for example, through the Internet), or in a cloud computing environment, or as a service, such as a software as a service (SaaS).

Additionally, the order in which the elements and sequences of the process are recited in the specification, the use of alphanumeric characters, or other designations, is not intended to limit the order in which the processes and methods of the specification occur, unless otherwise specified in the claims. While various presently contemplated embodiments of the invention have been discussed in the foregoing disclosure by way of example, it is to be understood that such detail is solely for that purpose and that the appended claims are not limited to the disclosed embodiments, but, on the contrary, are intended to cover all modifications and equivalent arrangements that are within the spirit and scope of the embodiments herein. For example, although the system components described above may be implemented by hardware devices, they may also be implemented by software-only solutions, such as installing the described system on an existing processing device or mobile device.

Similarly, it should be noted that in the preceding description of embodiments of the present specification, various features are sometimes grouped together in a single embodiment, figure, or description thereof for the purpose of streamlining the disclosure aiding in the understanding of one or more of the embodiments. This method of disclosure, however, is not intended to imply that more features than are expressly recited in a claim. Indeed, the embodiments may be characterized as having less than all of the features of a single embodiment disclosed above.

Numerals describing the number of components, attributes, etc. are used in some embodiments, it being understood that such numerals used in the description of the embodiments are modified in some instances by the use of the modifier "about", "approximately" or "substantially". Unless otherwise indicated, "about", "approximately" or "substantially" indicates that the number allows a variation of ± 20%. Accordingly, in some embodiments, the numerical parameters used in the specification and claims are approximations that may vary depending upon the desired properties of the individual embodiments. In some embodiments, the numerical parameter should take into account the specified significant digits and employ a general digit preserving approach. Notwithstanding that the numerical ranges and parameters setting forth the broad scope of the range are approximations, in the specific examples, such numerical values are set forth as precisely as possible within the scope of the application.

For each patent, patent specification disclosure, and other materials cited in this specification, such as articles, books, specifications, publications, documents, etc., the entire contents of which are hereby incorporated by reference into this specification. Except for files in the history of the specification that are inconsistent or conflicting with the contents of the specification, and files that are limiting of the broadest scope of the claims that are appended to the specification (whether currently or later-added to the specification). It is to be understood that the descriptions, definitions and/or uses of terms in the accompanying materials of this specification shall control if they are inconsistent or contrary to the descriptions and/or uses of terms in this specification.

Finally, it should be understood that the embodiments described herein are merely illustrative of the principles of the embodiments of the present disclosure. Other variations are also possible within the scope of the present description. Thus, by way of example, and not limitation, alternative configurations of the embodiments of the specification can be considered consistent with the teachings of the specification. Accordingly, the embodiments of the present description are not limited to only those embodiments explicitly described and depicted herein.

Claims

1. An information verification method based on privacy protection of both parties, the method being performed by a first party for determining a location of a minimum non-0 item in a target sequence stored in private data form in both parties and in a shared form, comprising:

obtaining a first fragment of the target sequence held by the first party;

obtaining a first fragment of a variant sequence based on the first fragment of the target sequence; the change sequence is stored in a sharing mode of a first fragment of the change sequence and a second fragment of the change sequence;

acquiring a first sequence and a first intermediate fragment; the first intermediate fragment is obtained based on a second sequence and the first sequence; the first sequence and the second sequence are randomly generated by a semi-trusted third party;

acquiring first transmission data held by a second party; the first transmission data is obtained based on a second fragment and a second intermediate fragment of the varying sequence; the first and second intermediate slices constitute a sum-shared version of the first and second sequences;

sending second transmission data to the second party; the second transmission data is obtained based on the first transmission data, the first sequence, the first intermediate partition, and the first partition of the varying sequence;

obtaining implicit position information held by the second party; the implicit location information is derived based at least on the second transmission data;

determining a minimum non-0 item position of the target sequence based on the implicit position information and the first sequence.

2. The method of claim 1, the first sequence comprising:

a randomly generated shift vector and a random sequence of the same length as the target sequence.

3. The method of claim 2, determining a minimum non-0 term position of the target sequence based on the implicit position information and the shift vector, comprising:

determining a unique 0-item position in the varying sequence based on the implicit position information and the shift vector; the only 0-term position in the variant sequence is the smallest non-0-term position of the target sequence.

4. An information verification system based on both-party privacy protection is used for determining the position of the minimum non-0 item in a target sequence stored in both parties and in a sharing mode in a privacy data mode, and comprises a first acquisition module, a first calculation module, a second acquisition module, a third acquisition module, a first sending module, a fourth acquisition module and a second calculation module;

the first acquisition module is used for acquiring a first fragment of the target sequence held by a first party;

the first computing module is used for obtaining a first fragment of a variation sequence based on the first fragment of the target sequence; the change sequence is stored in a sharing mode of a first fragment of the change sequence and a second fragment of the change sequence;

the second acquisition module is used for acquiring the first sequence and the first intermediate fragment; the first intermediate fragment is obtained based on a second sequence and the first sequence; the first sequence and the second sequence are randomly generated by a semi-trusted third party;

the third acquisition module is used for acquiring first transmission data held by a second party; the first transmission data is obtained based on a second fragment and a second intermediate fragment of the varying sequence; the first and second intermediate slices constitute a sum-shared version of the first and second sequences;

the first sending module is used for sending second transmission data to the second party; the second transmission data is obtained based on the first transmission data, the first sequence, the first intermediate partition, and the first partition of the varying sequence;

the fourth obtaining module is configured to obtain implicit location information held by the second party; the implicit location information is derived based at least on the second transmission data;

the second calculation module is configured to determine a minimum non-0 position of the target sequence based on the implicit position information and the first sequence.

5. The system of claim 4, the first sequence comprising:

6. The system of claim 5, determining a minimum non-0 term position of the target sequence based on the implicit position information and the shift vector, comprising:

7. A computer-readable storage medium storing computer instructions, wherein when the computer instructions in the storage medium are read by a computer, the computer executes the information verification method based on two-party privacy protection according to any one of claims 1 to 3.

8. An information verification method based on privacy protection of both parties, the method being performed by a second party for determining a location of a minimum non-0 item in a target sequence stored in both parties and in a shared form as private data, comprising:

acquiring a second fragment of the target sequence held by the second party;

obtaining a second fragment of the variant sequence based on the second fragment of the target sequence; the change sequence is stored in a sharing mode of a first fragment of the change sequence and a second fragment of the change sequence;

acquiring a second sequence and a second intermediate fragment; the first intermediate shard and the second intermediate shard form a sum sharing form of a first sequence and the second sequence; the first sequence and the second sequence are randomly generated by a semi-trusted third party;

sending the first transmission data to the first party; the first transmission data is obtained based on a second slice of the varying sequence and the second intermediate slice;

acquiring second transmission data held by the first party; the second transmission data is obtained based on the first transmission data, the first sequence, the first intermediate partition, and the first partition of the varying sequence; the first intermediate fragment is obtained based on the first sequence and the second sequence;

obtaining a position sequence based on the second sequence and second transmission data; the only 0 item in the position sequence is implicit position information;

acquiring the first sequence;

9. The method of claim 8, the first sequence comprising:

10. The method of claim 9, determining a minimum non-0 item position of the target sequence based on the implicit position information and the first sequence, comprising:

11. An information verification system based on both-party privacy protection is used for determining the position of the minimum non-0 item in a target sequence stored in both parties and in a sharing mode in a privacy data mode, and comprises a fifth acquisition module, a third calculation module, a sixth acquisition module, a second sending module, a seventh acquisition module, a fourth calculation module, an eighth acquisition module and a fifth calculation module;

the fifth obtaining module is configured to obtain a second fragment of the target sequence held by a second party;

the third computing module is configured to obtain a second segment of the varying sequence based on the second segment of the target sequence; the change sequence is stored in a sharing mode of a first fragment of the change sequence and a second fragment of the change sequence;

the sixth obtaining module is configured to obtain a second sequence and a second intermediate fragment; the first intermediate shard and the second intermediate shard form a sum sharing form of a first sequence and the second sequence; the first sequence and the second sequence are randomly generated by a semi-trusted third party;

the second sending module is used for sending the first transmission data to the first party; the first transmission data is obtained based on a second slice of the varying sequence and the second intermediate slice;

the seventh obtaining module is configured to obtain second transmission data held by the first party; the second transmission data is obtained based on the first transmission data, the first sequence, the first intermediate partition, and the first partition of the varying sequence; the first intermediate fragment is obtained based on the first sequence and the second sequence;

the fourth calculation module is configured to obtain a position sequence based on the second sequence and the second transmission data; the only non-0 item in the position sequence is implicit position information;

the eighth obtaining module is configured to obtain the first sequence;

the fifth calculation module is to determine a minimum non-0 position of the target sequence based on the implicit position information and the first sequence.

12. The system of claim 11, the first sequence comprising:

13. The system of claim 12, determining a minimum non-0 item position of the target sequence based on the implicit position information and the first sequence, comprising:

14. A computer-readable storage medium storing computer instructions, wherein when the computer instructions in the storage medium are read by a computer, the computer executes the information verification method based on two-party privacy protection according to any one of claims 8 to 10.