Efficient concurrent scalar product calculation

Abstract

A method and system for performing a calculation of a privacy preserving scalar product are provided. A first party and a second party (e.g., a first computer and a second computer) possessing a first vector and a second vector respectively, can concurrently determine the scalar product of the two vectors, without revealing either vector to the other party. Each vector can be masked and then encrypted using a public key of an asymmetric key pair. Using homomorphic encryption operations, the scalar product of the vectors can be determined while the vectors are still encrypted. Each party can compare the scalar product, or a value derived from the scalar product against a predetermined threshold. As an example, two parties can perform the scalar product to compare two biometric templates expressed as vectors without revealing the biometric templates to one another, preserving the privacy of persons corresponding to those biometrics.

Claims

1. A method comprising: transmitting, by a first computer, to a second computer, a first public key, a second public key, a first encrypted masked vector, and a first encrypted random vector, wherein the first encrypted masked vector is a first masked vector encrypted using the first public key, and the first encrypted random vector is a first random vector encrypted using the second public key; receiving, by the first computer, from the second computer, a third public key, a fourth public key, a second encrypted masked vector, and a second encrypted random vector, wherein the second encrypted masked vector is a second masked vector encrypted using the third public key and the second encrypted random vector is a second random vector encrypted using the fourth public key; receiving, by the first computer, from the second computer, a third permuted encrypted difference vector and a fourth permuted encrypted difference vector, wherein the third permuted encrypted difference vector is encrypted using the first public key and permuted using a third permutation, and wherein the fourth permuted encrypted difference vector is encrypted using the second public key and permuted using a fourth permutation; producing, by the first computer, a third permuted difference vector by decrypting the third permuted encrypted difference vector using a first private key corresponding to the first public key; producing, by the first computer, a fourth permuted difference vector by decrypting the fourth permuted encrypted difference vector using a second private key corresponding to the second public key; calculating, by the first computer, a scalar product of a first vector and a second vector based on the first masked vector, the first random vector, the third permuted difference vector, and the fourth permuted difference vector; comparing, by the first computer, the scalar product or a value derived from the scalar product to a first predetermined threshold; and if the scalar product or the value derived from the scalar product exceeds the first predetermined threshold, performing, by the first computer, an interaction with the second computer.

2. The method of claim 1, wherein calculating the scalar product of the first vector and the second vector comprises: calculating, by the first computer, a square magnitude of the first masked vector; calculating, by the first computer, a square magnitude of the first random vector; calculating, by the first computer, a square magnitude of the third permuted difference vector; calculating, by the first computer, a square magnitude of the fourth permuted difference vector; and calculating, by the first computer, the scalar product of the first vector and the second vector based on the square magnitude of the first masked vector, the square magnitude of the first random vector, the square magnitude of the third permuted difference vector, and the square magnitude of the fourth permuted difference vector.

3. The method of claim 1, wherein before transmitting, by the first computer, to the second computer, the first public key, the second public key, the first encrypted masked vector and the first encrypted random vector, the method further comprises: generating, by the first computer, the first random vector; generating, by the first computer, the first masked vector by combining the first vector and the first random vector; generating, by the first computer, a first permutation and a second permutation; generating, by the first computer, a first key pair comprising the first public key and the first private key; generating, by the first computer, a second key pair comprising the second public key and the second private key; encrypting, by the first computer, the first masked vector using the first public key; and encrypting, by the first computer, the first random vector using the second public key.

4. The method of claim 1, wherein the first public key, the first private key, the second public key, the second private key, the third public key, a third private key corresponding to the third public key, the fourth public key, and a fourth private key corresponding to the fourth public key are additive homomorphic cryptographic keys.

5. The method of claim 1, wherein before receiving, by the first computer, from the second computer, the third public key, the fourth public key, the second encrypted masked vector, and the second encrypted random vector: the second computer generates the second random vector; the second computer generates the second masked vector by combining the second vector and the second random vector; the second computer generates the third permutation and the fourth permutation; the second computer generates a third key pair comprising the third public key and a third private key; the second computer generates a fourth key pair comprising the fourth public key and a fourth private key; the second computer encrypts the second masked vector using the third public key; and the second computer encrypts the second random vector using the fourth public key.

6. The method of claim 1, wherein: the second computer generates a third encrypted negation vector by encrypting a second negation vector using the first public key; the second computer generates a third encrypted difference vector based on the first encrypted masked vector and the third encrypted negation vector; the second computer generates a fourth encrypted negation vector by encrypting the second negation vector using the second public key; the second computer generates a fourth encrypted difference vector based on the first encrypted random vector and the fourth encrypted negation vector; the second computer generates the third permuted encrypted difference vector using the third permutation and the third encrypted difference vector; and the second computer generates the fourth permuted encrypted difference vector using the fourth permutation and the fourth encrypted difference vector.

7. The method of claim 1, wherein the first vector and the second vector correspond to a first biometric template and a second biometric template respectively, and wherein the first predetermined threshold is a biometric match threshold.

8. The method of claim 1, wherein after receiving, by the first computer, from the second computer, the third public key, the fourth public key, the second encrypted masked vector and the second encrypted random vector, and before receiving, by the first computer, from the second computer, the third permuted difference vector and the fourth permuted difference vector, the method further comprises: generating, by the first computer, a first encrypted negation vector by encrypting a first negation vector using the third public key; generating, by the first computer, a first encrypted difference vector based on the second encrypted masked vector and the first encrypted negation vector; generating, by the first computer, a second encrypted negation vector by encrypting the first negation vector using the fourth public key; generating, by the first computer, a second encrypted difference vector based on the second encrypted random vector and the second encrypted negation vector; generating, by the first computer, a first permuted encrypted difference vector using a first permutation and the first encrypted difference vector; generating, by the first computer, a second permuted encrypted difference vector using a second permutation and the second encrypted difference vector; and transmitting, by the first computer, to the second computer, the first permuted encrypted difference vector and the second permuted encrypted difference vector.

9. The method of claim 8, wherein: the second computer generates a first permuted difference vector by decrypting the first permuted encrypted difference vector using a third private key corresponding to the third public key; the second computer generates a second permuted difference vector by decrypting the second permuted encrypted difference vector using a fourth private key corresponding to the fourth public key; the second computer calculates the scalar product of the first vector and the second vector based on the second masked vector, the second random vector, the first permuted difference vector and the second permuted difference vector; the second computer compares the scalar product or a value derived from the scalar product to a second predetermined threshold; and if the scalar product or the value derived from the scalar product exceeds the second predetermined threshold, the second computer performs an interaction with the first computer.

10. A first computer comprising: a processor; and a non-transitory computer readable medium coupled to the processor; the non-transitory computer readable medium comprising code, executable by the processor for implementing a method comprising: transmitting, to a second computer, a first public key, a second public key, a first encrypted masked vector, and a first encrypted random vector, wherein the first encrypted masked vector is a first masked vector encrypted using the first public key, and the first encrypted random vector is a first random vector encrypted using the second public key; receiving, from the second computer, a third public key, a fourth public key, a second encrypted masked vector, and a second encrypted random vector, wherein the second encrypted masked vector is a second masked vector encrypted using the third public key and the second encrypted random vector is a second random vector encrypted using the fourth public key; receiving, from the second computer, a third permuted encrypted difference vector and a fourth permuted encrypted difference vector, wherein the third permuted encrypted difference vector is encrypted using the first public key and permuted using a third permutation, and wherein the fourth permuted encrypted difference vector is encrypted using the second public key and permuted using a fourth permutation; producing a third permuted difference vector by decrypting the third permuted encrypted difference vector using a first private key corresponding to the first public key; producing a fourth permuted difference vector by decrypting the fourth permuted encrypted difference vector using a second private key corresponding to the second public key; calculating a scalar product of a first vector and a second vector based on the first masked vector, the first random vector, the third permuted difference vector, and the fourth permuted difference vector; comparing, by the first computer, the scalar product or a value derived from the scalar product to a first predetermined threshold; and if the scalar product or the value derived from the scalar product exceeds the first predetermined threshold, performing, by the first computer, an interaction with the second computer.

11. The first computer of claim 10, wherein calculating the scalar product of the first vector and the second vector comprises: calculating a square magnitude of the first masked vector; calculating a square magnitude of the first random vector; calculating a square magnitude of the third permuted difference vector; calculating a square magnitude of the fourth permuted difference vector; and calculating the scalar product of the first vector and the second vector based on the square magnitude of the first masked vector, the square magnitude of the first random vector, the square magnitude of the third permuted difference vector, and the square magnitude of the fourth permuted difference vector.

12. The first computer of claim 10, wherein before transmitting to the second computer, the first public key, the second public key, the first encrypted masked vector and the first encrypted random vector, the method further comprises: generating the first random vector; generating the first masked vector by combining the first vector and the first random vector; generating a first permutation and a second permutation; generating a first key pair comprising the first public key and the first private key; generating a second key pair comprising the second public key and the second private key; encrypting the first masked vector using the first public key; and encrypting the first random vector using the second public key.

13. The first computer of claim 10, wherein the first public key, the first private key, the second public key, the second private key, the third public key, a third private key corresponding to the third public key, the fourth public key, and a fourth private key corresponding to the fourth public key are additive homomorphic cryptographic keys.

14. The first computer of claim 10, wherein before receiving from the second computer, the third public key, the fourth public key, the second encrypted masked vector, and the second encrypted random vector: the second computer generates the second random vector; the second computer generates the second masked vector by combining the second vector and the second random vector; the second computer generates the third permutation and the fourth permutation; the second computer generates a third key pair comprising the third public key and a third private key; the second computer generates a fourth key pair comprising the fourth public key and a fourth private key; the second computer encrypts the second masked vector using the third public key; and the second computer encrypts the second random vector using the fourth public key.

15. The first computer of claim 10, wherein: the second computer generates a third encrypted negation vector by encrypting a second negation vector using the first public key; the second computer generates a third encrypted difference vector based on the first encrypted masked vector and the third encrypted negation vector; the second computer generates a fourth encrypted negation vector by encrypting the second negation vector using the second public key; the second computer generates a fourth encrypted difference vector based on the first encrypted random vector and the fourth encrypted negation vector; the second computer generates the third permuted encrypted difference vector using the third permutation and the third encrypted difference vector; and the second computer generates the fourth permuted encrypted difference vector using the fourth permutation and the fourth encrypted difference vector.

16. The first computer of claim 10, wherein the first vector and the second vector correspond to a first biometric template and a second biometric template respectively, and wherein the first predetermined threshold is a biometric match threshold.

17. The first computer of claim 10, wherein after receiving from the second computer, the third public key, the fourth public key, the second encrypted masked vector and the second encrypted random vector, and before receiving from the second computer, the third permuted difference vector and the fourth permuted difference vector, the method further comprises: generating a first encrypted negation vector by encrypting a first negation vector using the third public key; generating a first encrypted difference vector based on the second encrypted masked vector and the first encrypted negation vector; generating a second encrypted negation vector by encrypting the first negation vector using the fourth public key; generating a second encrypted difference vector based on the second encrypted random vector and the second encrypted negation vector; generating a first permuted encrypted difference vector using a first permutation and the first encrypted difference vector; generating a second permuted encrypted difference vector using a second permutation and the second encrypted difference vector; and transmitting to the second computer, the first permuted encrypted difference vector and the second permuted encrypted difference vector.

18. The first computer of claim 17, wherein: the second computer generates a first permuted difference vector by decrypting the first permuted encrypted difference vector using a third private key corresponding to the third public key; the second computer generates a second permuted difference vector by decrypting the second permuted encrypted difference vector using a fourth private key corresponding to the fourth public key; the second computer calculates the scalar product of the first vector and the second vector based on the second masked vector, the second random vector, the first permuted difference vector and the second permuted difference vector; the second computer compares the scalar product or a value derived from the scalar product to a second predetermined threshold; and if the scalar product or the value derived from the scalar product exceeds the second predetermined threshold, the second computer performs an interaction with the first computer.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 shows a block diagram of an exemplary system according to some embodiments of the invention.

(2) FIG. 2 shows a block diagram of an exemplary first computer according to some embodiments.

(3) FIG. 3 shows a block diagram of an exemplary second computer according to some embodiments.

(4) FIG. 4 shows a flowchart overview of a method of calculating the scalar product of two vectors and performing an interaction according to some embodiments.

(5) FIG. 5 shows a flowchart of a setup phase, part of a method of calculating the scalar product of two vectors according to some embodiments.

(6) FIG. 6 shows a flowchart of an intermediate calculation phase, part of a method of calculating the scalar product of two vectors according to some embodiments.

(7) FIG. 7 shows a flowchart of a scalar product calculation phase, part of a method of calculating the scalar product of two vectors according to some embodiments.

(8) FIG. 8 shows a first exemplary interaction, comprising a payment transaction between a user of a first computer and a resource provider.

(9) FIG. 9 shows a second exemplary interaction, comprising a building entry authentication process between a user of a first computer and a resource provider.

DETAILED DESCRIPTION

(10) Because embodiments are directed to privacy-preserving methods and systems for calculating the scalar product of two vectors, a brief primer on vectors may be useful in better understanding embodiments.

(11) While the term vector has different meanings throughout the sciences, generally a vector refers to an ordered list of components. In some cases, a vector can also be represented as a paired magnitude and angle or direction. For example, the vector [north: 1 mile, west: 1 mile] represents a straight path between a first point in space and a second point in space exactly one mile north and one mile west of the first point. This vector can alternatively be represented as [magnitude: 1.414 miles, direction: 45 degrees], indicating that the vector points 1.414 miles, 45 degrees clockwise from north. Both representations are equivalent because they describe the same path. As variables in mathematical equations, vectors are often represented by a symbol with an arrow over the top, for example: {right arrow over (c)}. Vectors are subject to many mathematical relationships that other variables are subject to, for example, similar vectors can be added together or subtracted from one another.

(12) Many forms of data can be vectorized, i.e., converted into vectors or represented by vectors. As an example, a person's health statistics (e.g., height, weight, age) could be represented by a vector such as [height: 68 inches, weight: 140 lbs, age: 25 years]. Vectorization is useful because it allows data to be compared objectively using vector operations that can be quickly performed by a computer.

(13) For example, one method of comparing two sets of data is vectorising each set of data and determining the angle between the two vectors. Vectors that are alike have a small angle between them, while vectors that are different have a large angle between them. The angle between two identical vectors (e.g., [north: 1 mile, west: 0 miles] and [north: 1 mile, west: 0 miles]) is zero, while two orthogonal vectors (e.g., [north: 1 mile, west: 0 miles] and [north: 0 miles, west: 1 mile]) have a 90 degree angle between them, and two opposite vectors (e.g., [north: 1 mile, west: 0 miles] and [south: 1 mile, west: 0 miles]) have a 180 degree angle between them. The angle between two vectorized sets of data (e.g., health statistics corresponding to a first person and health statistics corresponding to a second person), or a trigonometric function (e.g., cosine) of the angle between two vectorized sets of data can be used as a similarity or difference metric to evaluate the similarity or difference between those two sets of data.

(14) Similarly, vector operations such as the scalar product can be used to evaluate the similarity or difference between two vectors. The scalar product of two vectors can be calculated by multiplying each component of the first vector by the corresponding component of the second vector and summing the result, i.e.:
{right arrow over (c)}.Math.{right arrow over (d)}:=.sub.i=1.sup.nc.sub.id.sub.i

(15) As an example, the scalar product of {right arrow over (c)}=[1, 3, 5] and {right arrow over (d)}=[4, 2, 1] equals:
(1*4)+(3*2)+(5*1)=3

(16) The scalar product is useful because, among other reasons, it is proportional to the angle between the two vectors, as shown by the following equality:
{right arrow over (c)}.Math.{right arrow over (d)}={right arrow over (c)}{right arrow over (d)}cos()

(17) Where {right arrow over (c)} is the magnitude (i.e., the size) of vector {right arrow over (c)}, {right arrow over (d)} is the magnitude of vector {right arrow over (d)}, and is the angle between the two vectors. As such, the scalar product of two vectorized sets of data can be used to determine similarities or differences between those sets of data.

(18) Vectorization can be used to simplify or accelerate the comparison of data such as biometrics. In one example, a captured biometric can be compared against a biometric or biometric template stored in a database, in order to identify or authenticate a person corresponding to the biometric. One example is fingerprinting, whereby images of a person's fingerprints are captured (biometric) and compared to fingerprints stored in a fingerprint database in order to identify that person. If the captured fingerprints and the fingerprints stored in the fingerprint database are vectorized, it is possible to determine if the captured fingerprints match a set of fingerprints stored in the fingerprint database using vector operations, such as calculating the scalar product of the captured vectorized fingerprints and the vectorized fingerprints stored in the database.

(19) Exact methods of vectorising biometrics or biometric templates are beyond the scope of this disclosure. However, the following example is provided in order to illustrate how an exemplary biometric may be vectorized.

(20) An iris code (a biometric typically comprising 256 bytes that can be used to perform iris recognition) can be vectorized by converting it into a vector with 256 components, each component corresponding to one byte of the corresponding iris code. As an alternative, the iris code could be converted into a binary vector comprising 2048 components, each comprising one bit of the corresponding iris code, or alternatively, a vector with 128 components, each component corresponding to two bytes of the corresponding iris code. There are a number of ways in which a biometric, such as an iris code can be converted into a vector, and other biometrics (e.g., fingerprints, facial scans, etc.) can be converted into vectors using similar methods.

(21) While there are numerous methods and techniques for comparing biometrics, vectorized or otherwise, few techniques are oriented toward preserving the privacy of the subject. As an example, when a person is subject to a fingerprint scan, they typically have to provide their fingerprints (the biometric) to an entity (e.g., a law enforcement agency) in order for the entity to compare those fingerprints to fingerprints stored in a database. This however exposes the person to the risk of identity theft. A fraudster can impersonate a legitimate entity and request the person's biometrics as part of an apparently legitimate authentication request (e.g., via an email phishing attack). The fraudster can then use those biometrics in order to impersonate the person as part of an identity theft scheme.

(22) Embodiments of the present disclosure, however, provide for methods for two entities (e.g., two computers, such as a smart phone belonging to a user and a remote server) to calculate the scalar product of two vectors (e.g., two vectorized biometrics) without either entity revealing its respective biometric to the other entity. As such, a remote server can determine if a person's biometric matches a biometric stored in a biometric database without actually receiving the person's biometric itself. This results in a tangible increase in information security and prevents identity theft schemes, such as the one described above.

(23) Embodiments accomplish this by using additive homomorphic encryption, using cryptosystems such as the Paillier cryptosystem. Additive homomorphic encryption allows the participating entities to calculate the sum of encrypted data without first decrypting the data. Particularly, in the Paillier cryptosystem, the product of two ciphertexts (i.e., encrypted data) is equal to the encrypted sum of the corresponding plaintexts:
E(c)*E(d)=E(c+d)

(24) Embodiments of the present disclosure make use of this property to enable two computers to calculate the scalar product of two vectors while the components of the vectors are encrypted. As the private keys used to decrypt the vectors are only known by their respective entity (i.e., a first computer knows private keys that are unknown to a second computer, and vis-versa), each entity can prevent the other entity from learning of its vector, while still calculating the scalar product of the two vectors.

(25) FIG. 1 shows a block diagram of an exemplary system 100, comprising a first computer 102, a second computer 104, a resource provider computer 106, and a user 108. The computers of system 100 may be in operative communication with one another via one or more communications networks.

(26) A communications network can take any suitable form, which may be any one and/or the combination of the following: a direct interconnection; the Internet; a Local Area Network (LAN); a Metropolitan Area Network (MAN); an Operating Missions as Nodes on the Internet (OMNI); a secured custom connection; a Wide Area Network (WAN); a wireless network (e.g., employing protocols such as but not limited to a Wireless Application Protocol (WAP), I-mode, and/or the like); and/or the like. Messages between the entities, providers, users, devices, computers and networks may be transmitted using a secure communications protocol such as, but not limited to, File Transfer Protocol (FTP); HyperText transfer Protocol (HTTP); Secure HyperText Transfer Protocol (HTTPS), Secure Socket Layer (SSL), ISO (e.g., ISO 8583) and/or the like.

(27) Methods according to embodiments enable the first computer 102 and the second computer 104 to calculate the scalar product of a first vector 102A and a second vector 104A without each computer revealing their respective vector or the calculated scalar product to the other computer. Through a series of phases, described below with reference to FIGS. 4-7, the first computer 102 and second computer 104 can prepare and exchange information that allows the first computer 102 and second computer 104 to concurrently calculate the scalar product of the first vector 102A and the second vector 104A. The first computer 102 and second computer 104 can each concurrently compare the calculated scalar product or a value derived from the scalar product (e.g., an angle between the two vectors) to predetermined thresholds. If the scalar product of the value derived from the scalar product exceeds the predetermined thresholds, the first computer 102 and second computer 104 may perform an interaction with one another. This interaction can additionally comprise a resource provider, who may own or operate a resource provider computer 106.

(28) Exemplary interactions are described in greater detail below with reference to FIGS. 8 and 9. Generally, the comparison of the scalar product or a value derived from the scalar product to a predetermined threshold may be performed as part of an authentication procedure, and the interaction may take place provided authentication was successful (i.e., the scalar product or a value derived from the scalar product exceeds the predetermined threshold). For example, if the first vector 102A is a biometric vector stored on the first computer 102 (e.g., a smart phone owned by user 108) corresponding to the user 108, and the second vector 104A is a biometric vector corresponding to the user 108 that is stored on the second computer 104 (e.g., a biometric vector on file corresponding to user 108), the scalar product of the first vector 102A and the second vector 104A may be used to authenticate the user 108. Once the user 108 is authenticated, an interaction can take place, such as a payment transaction between the user 108 and a merchant (i.e., a resource provider operating resource provider computer 106).

(29) FIG. 2 shows an exemplary first computer 200 according to some embodiments. Particularly, FIG. 2 shows the first computer 200 as a mobile device (e.g., a smart phone). It should be understood however, that the first computer 200 may take many forms, such as any appropriate communications device as defined above in the terms section.

(30) First computer 200 may include circuitry that is used to enable certain device functions, such as wireless communication or telephony. The functional elements responsible for enabling those functions may include a processor 202 that can execute instructions that implement the functions and operations of the device. Processor 202 my access data storage 210 (or another suitable memory region or element) to retrieve instruction or data used in executing the instructions. Data input/output element 206, such as a keyboard or touchscreen, may be used to enable a user to operate the first computer 200 (for example, allowing the user to navigate to a mobile wallet application 214). Data input/output 206 may also be configured to output data (via a speaker, for example). Display 204 may also be used to output data to a user. Communications element 208 may be used to enable data transfer between first computer 200 and a wired or wireless network (via antenna 224, for example), enable data transfer functions, and may be used to assist in connectivity to the Internet or another network. First computer 200 may also include contactless element interface 220 to enable data transfer between contactless element 222 and other elements of the device. Contactless element 222 may include a secure memory and a near field communication data transfer element (or another form of short range communication technology). As noted, cellular phones, smart phones, wearable devices, laptop computers, or other similar devices are examples of mobile devices, and thereby examples of first computers in accordance with embodiments.

(31) The data storage 210 may comprise a computer readable medium that may also comprise a number of software modules, such as a communications module 212, a mobile wallet application 214, a biometrics application 216, and a scalar product calculation module 218.

(32) The communications module 212 may comprise code enabling the processor 202 to implement or enable communications between the first computer 200 and other devices, such as other mobile devices, access terminals, or a second computer. The communications module 212 may allow communication according to any appropriate protocol, such as TCP, UDP, IS-IS, OSPF, IGRP, EIGRP, RIP, BGP, etc. It may enable secure communications by enabling the processor 202 to establish a secure or encrypted communication channel between the first computer 200 and other devices. For example, the communication module 212 may comprise code executable by the processor 202 for performing a key exchange (such as a Diffie-Hellman key exchange) between mobile device 200 and another device. The communication module 212 may further allow the transmission of access tokens, including payment tokens, to other devices, such as an access terminal, in addition to allowing the transmission of encrypted or unencrypted vectors and cryptographic keys.

(33) The mobile wallet application 214 may comprise code enabling the first computer 200 to manage tokens. For example, the mobile wallet application 214 may comprise code enabling the processor 202 to retrieve access tokens stored in the secure memory 222 via contactless element interface 220. The mobile wallet application 214 may further comprise code enabling the first computer 200 to display any suitable token information, for example, the time and date during which an access token was provisioned, an alias or identifier for the access token, the time and date of the most recent interaction or transaction involving the access token, etc. Further the mobile wallet application 214 may comprise code enabling the processor 202 to display a graphical user interface (GUI) that enables a user to activate token related functionality. Further, the mobile wallet application 214 may comprise code enabling the first computer 200 to send tokens to an access terminal, for example, during a transaction with a merchant.

(34) Biometrics application 216 may comprise code enabling the first computer 200 to capture biometric instances via data input/output 206. For example, during an enrollment process (such as enrollment phase 402 from FIG. 4, described in further detail below), the first computer 200 may be used to capture a biometric instance such as a face scan, using a data input/output element 206 such as a camera. Biometrics application 216 may be used to capture this biometric instance and store the biometric instance, either in encrypted or unencrypted form on secure memory 220. Biometrics application 216 may additionally include code or instructions, executable by the processor 202 to vectorize biometric instances, i.e., generate biometric vectors corresponding to those biometric instances. Biometrics application 216 may also include code or instructions, executable by the processor 202 for participating in a biometric based interaction system, such as a biometrics-based transaction system. These code or instructions may include code for communicating with an access terminal and performing functions such as transmitting biometric vectors to the access terminal.

(35) The scalar product calculation module 218 may comprise code or instructions, executable by processor 202 for performing a privacy-preserving calculation of the scalar product of two vectors according to some embodiments. These methods may be better understood with reference to FIGS. 4-7 below. The code or instructions may include the generation of random number or random vectors, the generation of masked vectors, private cryptographic keys (including additive homomorphic cryptographic keys, such as Paillier keys), encrypting and decrypting vectors, generating negation vectors, difference vectors, permutations, calculating square magnitudes, and calculating the scalar product of two vectors, among other things, as described below with reference to FIGS. 4-7.

(36) FIG. 3 shows an exemplary second computer 300 according to some embodiments of the present disclosure. The second computer 300 may comprise a processor 302, a communications interface 304, and a computer readable medium 306. The computer readable medium 306 may comprise a number of software modules, including a communications module 308, an enrollment module 310, a scalar product calculation module 312, an interaction module 314, and a vector database 316, among others.

(37) Processor 302 may be any suitable processing apparatus or device as described in the terms section above. Communications interface 304 may comprise a network interface that enables the second computer 300 to communicate with other computers or systems (e.g., the first computer) over a network such as the Internet.

(38) Communication module 308 may comprise code or software, executable by processor 302 for establishing communication between second computer 300 and other entities, including the first computer. As an example, communications module 308 may comprise code enabling the generation of UDP (User Datagram Protocol) or TCP (Transmission Control Protocol) packets, or any other appropriate form of network communication. Second computer 300 may use the communications module 308 to transmit and receive data from entities, such as the first computer. These data may include vectors, encrypted, permuted, or otherwise, and cryptographic keys, as described below with reference to first transmission phase 406 and second transmission phase 408 of FIG. 4.

(39) Enrollment module 310 may comprise code enabling a user (e.g., user 108 from FIG. 1) to enroll in a vector-based authentication system, such as a biometric vector authentication system. In some methods according to embodiments, enrollment may be optional. As such, enrollment module 310 may be optional as well. The enrollment module 310 may comprise code enabling the second computer 300 to associate a biometric vector corresponding to a user or a first computer to an identity of the user or an identifier corresponding to the user. For example, the enrollment module 310 may comprise code enabling the second computer 300 to associate a biometric vector corresponding to an iris scan to a user John Doe. The enrollment module 310 may additionally comprise code enabling the second computer 300 to store the exemplary biometric vector, in association with an identifier corresponding to John Doe, in biometric database 316. At a later time, a first computer corresponding to John Doe (e.g., John's smart phone) and the second computer 300 can perform a privacy-preserving scalar product calculation of the biometric vector stored in biometric database 318 and a biometric vector stored on the first computer, in order to authenticate John Doe and perform an interaction.

(40) Scalar product calculation module 312 may comprise code, executable by processor 302, for performing a privacy-preserving scalar product calculation according to some embodiments. Privacy-preserving scalar product calculations may be better understood with reference to the flowcharts of FIGS. 4-7. Scalar product calculation module 312 may comprise code enabling the generation of random vectors, masked vectors, cryptographic keys, permuted vectors, etc., as described below, in addition to mathematical operations used to calculate the sums of vectors, differences between vectors, and the magnitude or square magnitude of vectors.

(41) Interaction module 314 may comprise code, executable by the processor 302 for performing an interaction with the first computer. This interaction may comprise, for example, authenticating the first computer to a resource provider, such that the first computer or a user associated with the first computer can gain access to a resource. For example, the resource provider may be a merchant, the resource may be a good or service that a customer wishes to buy, the first computer may be a smart phone owned by the customer, and the second computer 300 may be a server computer associated with a payment processing network. The interaction may comprise enacting a payment transaction between the user and the merchant, and interaction module 314 may comprise code, executable by processor 302 for enacting the payment transaction between the user and the merchant.

(42) As a second exemplary interaction, a resource provider may be a computer system controlling access to a building via a locked, computerized door. The interaction between the first computer and second computer 300 may comprise the second computer allowing an owner of the first computer to access the building, e.g., by sending a control signal to the resource provider computer instructing the door be opened, or by providing the first computer with an access token or another credential that the first computer can provide to the resource provider computer, such that the resource provider computer opens the door.

(43) The vector database 316 may comprise any appropriate database, file, or memory structure containing vectors. These vectors may include, for example, biometric vectors corresponding to a plurality of enrolled users. Second computer 300 may retrieve a vector from vector database 316 in order to calculate the scalar product of that vector and another vector corresponding to a first computer.

(44) FIG. 4 shows a flowchart overview of a method 400 of calculating the scalar product of a first vector {right arrow over (a)} and a second vector {right arrow over (b)} according to some embodiments. The method is divided into seven phases: enrollment phase 402, setup phase 404, first transmission phase 406, intermediate calculation phase 408, second transmission phase 410, scalar product calculation phase 412, and interaction phase 414.

(45) Enrollment phase 402 may be optional, i.e., in some embodiments, enrollment phase 402 may be performed and in other embodiments, enrollment phase 402 may not be performed. The characteristics of enrollment phase 402 may depend on the characteristics of the first vector {right arrow over (a)} and second vector {right arrow over (b)}, and of the nature of the interaction performed in the interaction phase 414.

(46) As an example, the vectors may correspond to biometric instances, and the scalar product of the two vectors may correspond to the similarity between the two biometric instances. As such, the scalar product may be calculated in order to determine whether the two biometric instances match to a sufficient degree of certainty (e.g., 75% match, 95% match, 99% match, etc.). In this case, enrollment phase 402 may comprise a biometric enrollment process. This biometric enrollment process may comprise, for example, capturing a biometric from an enrolling user (for example, by capturing an image of the user's iris, performing a thumb or fingerprint scan, etc.), converting the captured biometric (e.g., into an iris code or other appropriate digital representation of the biometric), and securely storing the biometric instance (e.g., in a secure element on a first computer and/or in a secure database on a second computer.

(47) As stated above, the characteristics of enrollment phase 402 may depend on the characteristics of interaction phase 414 and the interaction. As one example, method 400 of FIG. 4 could be applied to a biometric authorization system for making payments. A customer's biometric instance, represented as a first vector {right arrow over (a)}, could be compared to the customer's biometric instance, represented as a second vector {right arrow over (b)} and stored on a payment processing server. If the biometric vectors match (determined based on the scalar product of the first vector and the second vector), the payment processing server can authenticate the customer and approve a transaction (i.e., the interaction of interaction phase 414) between the customer and a merchant. In this case, as the interaction is a transaction, the enrollment phase 402 may additionally comprise associating a payment credential (such as a PAN) with the biometric vector (second vector {right arrow over (b)}) stored at the payment processing server (second computer). In this example, enrollment phase 402 may additionally comprise the user or consumer filling out a web form with information such as the user's PAN, which may then be encrypted and transmitted to the second computer so that it can be stored in association with the second vector {right arrow over (b)}.

(48) However, as stated above, in some embodiments, enrollment phase 402 may be optional. This may occur in embodiments where the first computer and the second computer do not need to receive the first vector {right arrow over (a)} and second vector {right arrow over (b)} respectively from an external source (e.g., via a biometric capture). For example, the first vector {right arrow over (a)} may represent the location of a user, determined from the GPS of the user's smart phone, and the second vector {right arrow over (b)} may represent the location of a business, such as a caf that the user is trying to navigate to. As such, the first computer may comprise the user's smart phone, and the second computer may comprise a server computer associated with a navigation or mapping service. The scalar product of the two vectors may be used by the user's smart phone in order to help the user navigate to the caf. Because the user's location vector can be inferred from GPS data, and because the navigation service may already know the location of the caf, there may be no need to perform enrollment phase 402.

(49) Setup phase 404 may be better understood with reference to FIG. 5. In general, the setup phase may comprise steps that may take place before any data is transmitted between the first computer and the second computer.

(50) FIG. 5 shows a flowchart of the steps performed during the setup phase of a method according to embodiments. It may be helpful to note that the subscript A generally refers to vectors or values generated or used by the first computer, while the subscript B generally refers to vectors, values, or cryptographic keys generated or used by the second computer.

(51) At step 502A, the first computer can securely retrieve the first vector {right arrow over (a)}. In some embodiments, the first computer may be a smart phone associated with a user. In these embodiments, the first computer may securely retrieve the first vector {right arrow over (a)} from a secure element of the first computer (using for example, contactless element interface 220 from FIG. 2).

(52) Likewise, at step 502B, the second computer can securely retrieve the second vector {right arrow over (b)}. In some embodiments, the second computer may be a remote server computer associated with some form of authenticating entity (e.g., a government agency or a payment processing server associated with a payment processing network). The second computer may securely retrieve the second vector {right arrow over (b)} from a secure or encrypted database.

(53) In some embodiments, the first vector {right arrow over (a)} and the second vector {right arrow over (b)} may be biometric vectors, that is, the first vector {right arrow over (a)} and the second vector {right arrow over (b)} may correspond to a first biometric template and a second biometric template (e.g., iris codes, digital representations of fingerprints, voice samples, DNA segments, etc.). The first vector {right arrow over (a)} and the second vector {right arrow over (b)} may be of equal length, that is, possess the same number of components.

(54) At step 504A the first computer may generate a first random vector {right arrow over (r.sub.A)}. The first random vector {right arrow over (r.sub.A )} may be generated according to any appropriate means, including the use of cryptographically secure pseudorandom number generators (CSPRNGs). The first random vector {right arrow over (r.sub.A)} may be of equal length to the first vector {right arrow over (a)}, that is, the first vector {right arrow over (a)} and the first random vector {right arrow over (r.sub.A)} may possess the same number of components. For example, if the first vector {right arrow over (a)} comprises a vectorized iris code comprising 256 1-byte components, the first random vector {right arrow over (r.sub.A)} may comprise 256 randomly generated bytes.

(55) Likewise, at step 504B, the second computer may generate a second random vector {right arrow over (r.sub.B)}. The second random vector {right arrow over (r.sub.B)} may similarly be generated using any appropriate means, including the use of CSPRNGs. The second random vector {right arrow over (r.sub.B)} may be of equal length to the second vector {right arrow over (b)}, that is, the second vector {right arrow over (b)} and the second random vector {right arrow over (r.sub.B)} may possess the same number of components.

(56) At step 506A, the first computer can generate the first masked vector {right arrow over (a)} by combining the first vector {right arrow over (a)} and the first random vector {right arrow over (r.sub.A)}. In some embodiments, the first masked vector {right arrow over (a)} may be equal to the sum of the first vector {right arrow over (a)} and the first random vector {right arrow over (r.sub.A)}:
{right arrow over (a)}={right arrow over (a)}+{right arrow over (r.sub.A)}=[a.sub.1+r.sub.A1a.sub.2+r.sub.A2. . . a.sub.n+r.sub.An]

(57) Likewise, at step 506B, the second computer can generate the second masked vector {right arrow over (b)} by combining the second vector {right arrow over (b)} and the second random vector {right arrow over (r.sub.B)}. In some embodiments, the second masked vector {right arrow over (b)} may be equal to the sum of the second vector {right arrow over (b)} and the second random vector {right arrow over (r.sub.B )}:
{right arrow over (b)}={right arrow over (b)}+{right arrow over (r.sub.B)}=[b.sub.1+r.sub.B1b.sub.2+r.sub.B2. . . b.sub.n+r.sub.Bn]

(58) At step 508A, the first computer can generate a first key pair comprising a first public key Pb.sub.A and a first private key Pr.sub.A. The first public key Pb.sub.A may enable the use of the encryption function E.sub.A, and the first private key Pr.sub.A may enable the use of the decryption function D.sub.A. That is, data (e.g., vectors) encrypted with the first public key Pb.sub.A may be decrypted with the first private key Pr.sub.A.

(59) At step 510A, the first computer can generate a second key pair comprising a second public key Pb.sub.A and a second private key Pr.sub.A. The second public key Pb.sub.A may enable the use of the encryption function E.sub.A, and the second private key Pr.sub.A may enable the use of the decryption function D.sub.A. That is, data (e.g., vectors) encrypted with the second public key Pb.sub.A may decrypted with the second private key Pr.sub.A.

(60) Likewise, at step 508B, the second computer can generate a third key pair comprising a third public key Pb.sub.B and a third private key Pr.sub.B. The third public key Pb.sub.B may enable the use of the encryption function E.sub.B, and the third private key Pr.sub.B may enable the use of the decryption function D.sub.B. That is, data (e.g., vectors) encrypted with the third public key Pb.sub.B may be decrypted with the third private key Pr.sub.B.

(61) Similarly, at step 510B, the second computer can generate a fourth key pair comprising a fourth public key Pb.sub.B and a fourth private key Pr.sub.B. The fourth public key Pb.sub.B may enable the use of the encryption function E.sub.B, and the fourth private key Pr.sub.B may enable the use of the decryption function D.sub.B. That is, data (e.g., vectors) encrypted with the fourth public key Pb.sub.B may be decrypted with the fourth private key Pr.sub.B.

(62) In some embodiments, the first public key Pb.sub.A, the first private key Pr.sub.A, the second public key Pb.sub.A, the second private key Pr.sub.A, the third public key Pb.sub.B, the third private key Pr.sub.B, the fourth public key Pb.sub.B, and the fourth private key Pr.sub.B may be additive homomorphic cryptographic keys, such as Paillier cryptographic keys.

(63) The generation of these cryptographic key pairs depends on the nature of the cryptosystem being used. The following example method of generating cryptographic key pairs corresponds to the use of the Paillier cryptosystem. First, the first computer or second computer can choose two large prime numbers p and q randomly and independently, such that the greatest common denominator of pq and (p1)(q1) is 1. Second, the first computer or second computer can compute n=p*q and =lcm(p1, q1), where lcm is a function used to determine the least common multiple. Third, the first computer or second computer can generate a random integer g such that g.sub.n.sub.2*. Fourth, the first computer or second computer can calculate

(64) $=\frac{n}{g^{}\mathrm{mod}{n}^2-1}\mathrm{mod}n.$
The public key (used for encryption) is the pair (n, g), while the private key (used for decryption) is the pair (, ). This process can be repeated based on the number of keys to be generated, e.g., the first computer can repeat this process twice to generate the first public key Pb.sub.A, the first private key Pr.sub.A, the second public key Pb.sub.A, and the second private key Pr.sub.A, and the second computer can repeat the process twice to generate the third public key Pb.sub.B, the third private key Pr.sub.B, the fourth public key Pb.sub.B, and the fourth private key Pr.sub.B.

(65) At step 512A, the first computer can generate a first encrypted masked vector E.sub.A({right arrow over (a)}) by encrypting the first masked vector {right arrow over (a)} using the first public key Pb.sub.A.

(66) Likewise, at step 514A, the first computer can generate a first encrypted random vector E.sub.A({right arrow over (a)}) by encrypting the first random vector {right arrow over (r)} using the second public key Pb.sub.A.

(67) At step 512B, the second computer can generate a second encrypted masked vector E.sub.B({right arrow over (b)}) by encrypting the second masked vector {right arrow over (b)} using the third public key Pb.sub.B.

(68) Likewise, at step 514B, the second computer can generate a second encrypted random vector E.sub.B({right arrow over (r.sub.B )}) by encrypting the second random vector {right arrow over (r.sub.B )} using the fourth public key Pb.sub.B.

(69) Generally, in embodiments of the present disclosure, an encrypted vector refers to a vector for which each component of the vector is encrypted. For example, for the first encrypted masked vector E.sub.A({right arrow over (a)}):
E.sub.A({right arrow over (a)}):=(E.sub.A(a.sub.1), . . . ,E.sub.A(a.sub.n))

(70) Returning to FIG. 4, following setup phase 404 is first transmission phase 406. In the first transmission phase 406, the first computer and the second computer can transmit data to one another. This data may be used in subsequent intermediate calculation phase 408 and scalar product calculation phase 412.

(71) More specifically, in first transmission phase 406, the first computer may transmit to the second computer, a first public key Pb.sub.A, a second public key Pb.sub.A, a first encrypted masked vector E.sub.A({right arrow over (a)}), and a first encrypted random vector E.sub.A({right arrow over (r.sub.A)}), wherein the first encrypted masked vector E.sub.A({right arrow over (a)}) is a first masked vector {right arrow over (a)} encrypted using the first public key Pb.sub.A, and the first encrypted random vector E.sub.A({right arrow over (r.sub.A)}) is a first random vector {right arrow over (r.sub.A)} encrypted using the second public key Pb.sub.A.

(72) Additionally, the first transmission phase 406 may comprise the first computer receiving, from the second computer, a third public key Pb.sub.B, a fourth public key Pb.sub.B, a second encrypted masked vector E.sub.B({right arrow over (b)}), and a second encrypted random vector E.sub.B({right arrow over (r.sub.B)}), wherein the second encrypted masked vector E.sub.B({right arrow over (b)}) is a second masked vector {right arrow over (b)} encrypted using the third public key Pb.sub.B and the second encrypted random vector is a second random vector {right arrow over (r.sub.B )} encrypted using the fourth public key Pb.sub.B.

(73) These data (i.e., the first public key Pb.sub.A, the second public key Pb.sub.A, the third public key Pb.sub.B, the fourth public key Pb.sub.B, the first encrypted masked vector E.sub.A({right arrow over (a)}), the second encrypted masked vector E.sub.B ({right arrow over (b)}), the first encrypted random vector E.sub.A({right arrow over (r.sub.A)}), and the second encrypted random vector E.sub.B({right arrow over (r.sub.B )})) may be transmitted over any appropriate network in any appropriate form. For example, these data may be transmitted over a network such as the Internet in data packets such as UDP or TCP packets.

(74) After first transmission phase 406, the first computer and the second computer 408 can advance to intermediate calculation phase 408, which may be better understood with reference to FIG. 6

(75) FIG. 6 shows a flowchart of the steps performed during the intermediate calculation phase of a method according to embodiments.

(76) At step 602A, the first computer can generate a first negation vector {right arrow over (a)}. The first negation vector {right arrow over (a)} may comprise the negation of the first vector {right arrow over (a)}, i.e., each component of the first negation vector {right arrow over (a)} may equal the negative value of the corresponding component of the first vector {right arrow over (a)}. For example, for a first vector {right arrow over (a)}=[1, 2, 3], the first negation vector {right arrow over (a)}=[1, 2, 3].

(77) Likewise, at step 602B, the second computer can generate a second negation vector {right arrow over (b)}. The second negation vector {right arrow over (b)} may comprise the negation of the second vector {right arrow over (b)}, i.e., each component of the second negation vector {right arrow over (b)} may equal the negative value of the corresponding component of the second vector {right arrow over (b)}. For example, for a second vector {right arrow over (b)}=[4, 5, 6], the second negation vector {right arrow over (b)}=[4, 5, 6].

(78) At step 604A, the first computer can generate a first encrypted negation vector E.sub.B({right arrow over (a)}) by encrypting the first negation vector {right arrow over (a)} using the third public key Pb.sub.B. The third public key Pb.sub.B could have been previously generated by the second computer during the setup phase (setup phase 404 from FIG. 4) and transmitted to the first computer during the first transmission phase (first transmission phase 406 from FIG. 4).

(79) At step 606A, the first computer can generate a first encrypted difference vector E.sub.B ({right arrow over (b)}{right arrow over (a)}) based on the second encrypted masked vector E.sub.B ({right arrow over (b)}) and the first encrypted negation vector E.sub.B({right arrow over (a)}). The second encrypted masked vector E.sub.B({right arrow over (b)}) may have been received by the first computer from the second computer during the first transmission phase. In some embodiments, the first computer may make use of the properties of additive homomorphic cryptography to generate the first encrypted difference vector E.sub.B({right arrow over (b)}{right arrow over (a)}). This may enable the first computer to generate the first encrypted difference vector E.sub.B({right arrow over (b)}{right arrow over (a)}) without first decrypting the second encrypted masked vector E.sub.B({right arrow over (b)}).

(80) For example, in the Paillier cryptosystem, generally, the product of two ciphertexts c and d is equal to the encrypted sum of the corresponding plaintext, i.e.:
E(c)E(d)=E(c+d)

(81) As a result, the first computer can generate the first encrypted difference vector E.sub.B({right arrow over (b)}{right arrow over (a)}) by multiplying each component of the second encrypted masked vector E.sub.B({right arrow over (b)}) by the corresponding component of the first encrypted negation vector E.sub.B({right arrow over (a)}):
E.sub.B({right arrow over (a)})=[E.sub.BE.sub.B(a.sub.2), . . . E.sub.B(a.sub.n)]
E.sub.B({right arrow over (b)})=[E.sub.B(b.sub.1),E.sub.B(b.sub.2), . . . ,E.sub.B(b.sub.n)]
E.sub.B({right arrow over (b)}{right arrow over (a)})=[E.sub.B(b.sub.1)E.sub.B(a.sub.1),E.sub.B(b.sub.2)E.sub.B(a.sub.2), . . . ,E.sub.B(b.sub.n)E.sub.B(a.sub.n)]
E.sub.B({right arrow over (b)}{right arrow over (a)})=[E.sub.B(b.sub.1a.sub.1),E.sub.B(b.sub.2a.sub.2), . . . ,E.sub.B(b.sub.na.sub.n)]

(82) At step 608A, the first computer can generate a second encrypted negation vector E.sub.B({right arrow over (a)}) by encrypting the first negation vector {right arrow over (a)} using the fourth public key Pb.sub.B. The fourth public key Pb.sub.B could have been generated by the second computer during the setup phase and transmitted to the first computer during the first transmission phase.

(83) At step 610A, the first computer can generate a second encrypted difference vector E.sub.B({right arrow over (r.sub.B)}{right arrow over (a)}) based on the second encrypted random vector E.sub.B({right arrow over (r.sub.B )}) and the second encrypted negation vector E.sub.B({right arrow over (a)}). The second encrypted random vector E.sub.B({right arrow over (r.sub.B)}) may have been received from the second computer during the first transmission phase. In some embodiments, the first computer may make use of the properties of additive homomorphic cryptography to generate the second encrypted difference vector E.sub.B({right arrow over (r.sub.B)}{right arrow over (a)}). This may be accomplished using a similar series of steps or operations as used to generate the first encrypted difference vector at step 606A, i.e., multiplying each encrypted component of the second encrypted random vector E.sub.B({right arrow over (r.sub.B)}) by the corresponding component of the second encrypted negation vector E.sub.B({right arrow over (a)}):
E.sub.B({right arrow over (a)})=[E.sub.B(a.sub.1),E.sub.B(a.sub.2), . . . ,E.sub.B(a.sub.n)]
E.sub.B({right arrow over (r.sub.B)})=[E.sub.B(r.sub.B1),E.sub.B(r.sub.B2), . . . ,E.sub.B(r.sub.Bn)]
E.sub.B({right arrow over (r.sub.B)}{right arrow over (a)})=[E.sub.B(r.sub.B1)E.sub.B(a.sub.1),E.sub.B(r.sub.B2)E.sub.B(a.sub.2), . . . ,E.sub.B(r.sub.Bn)E.sub.B(a.sub.n)]
E.sub.B({right arrow over (r.sub.B)}{right arrow over (a)})=[E.sub.B(r.sub.B1a.sub.1),E.sub.B(r.sub.B2a.sub.2), . . . ,E.sub.B(r.sub.Bna.sub.n)]

(84) At step 604B, the second computer can generate a third encrypted negation vector E.sub.A({right arrow over (b)}) by encrypting the second negation vector {right arrow over (b)} using the first public key Pb.sub.A. The first public key Pb.sub.A could have been generated by the first computer during the setup phase and transmitted to the second computer during the first transmission phase.

(85) At step 606B, the second computer can generate a third encrypted difference vector E.sub.A({right arrow over (a)}{right arrow over (b)}) based on the first encrypted masked vector E.sub.A({right arrow over (a)}) and the third encrypted negation vector E.sub.A({right arrow over (b)}). The second computer may have received the first encrypted masked vector E.sub.A({right arrow over (a)}) from the first computer during the first transmission phase. In some embodiments, the second computer may make use of the properties of additive homomorphic cryptography to generate the third encrypted difference vector E.sub.A({right arrow over (a)}{right arrow over (b)}). This may be accomplished using a similar series of steps or operations as used to generate the first encrypted difference vector at step 606A, i.e., multiplying each encrypted component of the first encrypted masked vector E.sub.A({right arrow over (a)}) with the corresponding encrypted component of the third encrypted negation vector E.sub.A({right arrow over (b)}).
E.sub.A({right arrow over (b)})=[E.sub.A(b.sub.1),E.sub.A(b.sub.2), . . . ,E.sub.A(b.sub.n)]
E.sub.A({right arrow over (a)})=[E.sub.A(a.sub.1),E.sub.A(a.sub.2), . . . ,E.sub.A(a.sub.n)]
E.sub.A({right arrow over (a)}{right arrow over (b)})=[E.sub.A(a.sub.1)E.sub.A(b.sub.1),E.sub.A(a.sub.2)E.sub.A(b.sub.2), . . . ,E.sub.A(a.sub.n)E.sub.A(b.sub.n)]
E.sub.A({right arrow over (a)}{right arrow over (b)})=[E.sub.A(a.sub.1b.sub.1),E.sub.A(a.sub.2b.sub.2), . . . ,E.sub.A(a.sub.nb.sub.n)]

(86) At step 608B, the second computer can generate a fourth encrypted negation vector E.sub.A({right arrow over (b)}) by encrypting the second negation vector {right arrow over (b)} using the second public key Pb.sub.A. The second public key Pb.sub.A could have previously been generated by the first computer during the setup phase and transmitted to the second computer during the first transmission phase.

(87) At step 610B, the second computer can generate a fourth encrypted difference vector E.sub.A({right arrow over (r.sub.A)}{right arrow over (b)}) based on the first encrypted random vector E.sub.A({right arrow over (r.sub.A)}) and the fourth encrypted negation vector E.sub.A({right arrow over (b)}). The second computer may have received the first encrypted random vector from the first computer during the first transmission phase. In some embodiments, the second computer may make use of the properties of additive homomorphic cryptography to generate the fourth encrypted difference vector E.sub.A({right arrow over (r.sub.A)}{right arrow over (b)}). This may be accomplished using a similar series of steps or operations used to generate the third encrypted difference vector at step 606B, i.e., multiplying each encrypted component of the second encrypted random vector E.sub.A({right arrow over (r.sub.A)}) by the corresponding encrypted component of the second encrypted negation vector E.sub.A({right arrow over (b)}):
E.sub.A({right arrow over (b)})=[E.sub.A(b.sub.1),E.sub.A(b.sub.2), . . . ,E.sub.A(b.sub.n)]
E.sub.A({right arrow over (r.sub.A)})=[E.sub.A(r.sub.A1),E.sub.A(r.sub.A2), . . . ,E.sub.A(r.sub.An)]
E.sub.A({right arrow over (r.sub.A)}{right arrow over (b)})=[E.sub.A(r.sub.A1)E.sub.A(b.sub.1),E.sub.A(r.sub.A2)E.sub.A(b.sub.2), . . . ,E.sub.A(r.sub.An)E.sub.A(b.sub.n)]
E.sub.A({right arrow over (r.sub.A)}{right arrow over (b)})=[E.sub.A(r.sub.A1b.sub.1),E.sub.A(r.sub.A2b.sub.2), . . . ,E.sub.A(r.sub.Anb.sub.n)]

(88) At step 612A the first computer can generate a first permutation .sub.A1 and a second permutation .sub.A2. As described above, a permutation is a way in which a set or number of things can be ordered or arranged. A permutation may be used to permute something in accordance with the permutation, and a permutation may be represented as a vector. As an example, the permutation =[3, 1, 2] may indicate that, for a vector comprising three components, the third component should be placed in the first position, the first component should be placed in the second position, and the second component should be placed in the third position. For example, the permutation =[3, 1, 2] applied to vector {right arrow over ()}=[7,8,9] can result in a permuted vector ({right arrow over ()})=[9,7,8].

(89) The first computer can generate the first permutation .sub.A1 and second permutation .sub.A2 in any number of ways. As an example, the first computer may use an algorithm (such as the Fisher-Yates shuffle) to shuffle an ordered sequence (i.e., [1, 2, . . . , n]). The shuffled ordered sequence may be used as the first permutation .sub.A1. The first computer can use a similar process to generate the second permutation, shuffling an ordered sequence a second time and using the result as the second permutation .sub.A2. The first permutation .sub.A1 and second permutation .sub.A2 may have the same number of components as the first vector {right arrow over (a)}.

(90) At step 612B, the second computer can generate a third permutation .sub.B1 and a fourth permutation .sub.B2. As described above with reference to the first permutation .sub.A1 and the second permutation .sub.A2, the third permutation .sub.B1 and the fourth permutation .sub.B2 can be generated in any number of ways, e.g., shuffling an ordered sequence using a shuffling algorithm, e.g., Fisher-Yates.

(91) At step 614A, the first computer can generate a first permuted encrypted difference vector .sub.A1(E.sub.B({right arrow over (b)}{right arrow over (a)})) using the first permutation .sub.A1 and the first encrypted difference vector E.sub.B({right arrow over (b)}{right arrow over (a)}). The first computer may generate the first permuted encrypted difference vector .sub.A1(E.sub.B({right arrow over (b)}{right arrow over (a)})) by permuting the first encrypted difference vector E.sub.B({right arrow over (b)}{right arrow over (a)}) using the first permutation .sub.A1, i.e., applying the first permutation .sub.A1 to the first encrypted difference vector E.sub.B({right arrow over (b)}{right arrow over (a)}). This may be accomplished by using the values or components of the first permutation .sub.A1 as indices to reorder the first encrypted difference vector E.sub.B({right arrow over (b)}{right arrow over (a)}). To repeat the example used above, the permutation =[3,1,2] applied to vector {right arrow over ()}=[7, 8, 9] can result in a permuted vector ({right arrow over ()})=[9, 7, 8]. In a similar manner, the first permutation .sub.A1 applied to the first encrypted difference vector E.sub.B({right arrow over (b)}{right arrow over (a)}) can result in the first permuted encrypted difference vector .sub.A1(E.sub.B({right arrow over (b)}{right arrow over (a)})).

(92) At step 616A, the first computer can generate a second permuted encrypted difference vector .sub.A2(E.sub.B(E.sub.B{right arrow over (a)})) using the second permutation .sub.A2 and the second encrypted difference vector E.sub.B({right arrow over (r.sub.B)}{right arrow over (a)}). This may be accomplished in substantially the same manner as described above with reference to step 614A, i.e., the first computer can use the second permutation .sub.A2 to reorder the components of the second encrypted difference vector E.sub.B({right arrow over (r.sub.B)}{right arrow over (a)}), producing the second permuted encrypted difference vector .sub.A2(E.sub.B({right arrow over (r.sub.B)}{right arrow over (a)})).

(93) At step 614B, the second computer can generate a third permuted encrypted difference vector .sub.B1(E.sub.A({right arrow over (a)}{right arrow over (b)})) using the third permutation .sub.B1 and the third encrypted difference vector E.sub.A({right arrow over (a)}{right arrow over (b)}). This may be accomplished in substantially the same manner as described above with reference to steps 614A and 616A, i.e., the second computer can use the third permutation .sub.B1 to reorder the components of the third encrypted difference vector E.sub.A({right arrow over (a)}{right arrow over (b)}) to produce the third permuted encrypted difference vector .sub.B1(E.sub.A({right arrow over (a)}{right arrow over (b)})).

(94) At step 616B, the second computer can generate a fourth permuted encrypted difference vector .sub.B2(E.sub.A({right arrow over (r.sub.A)}{right arrow over (b)}) using the fourth permutation .sub.B2 and the fourth encrypted difference vector E.sub.A({right arrow over (r.sub.A)}{right arrow over (b)}). This may be accomplished in substantially the same manner as described above with reference to steps 614A, 614B, and 616A, i.e., the second computer can use the fourth permutation .sub.B2 to reorder the components of the fourth encrypted difference vector E.sub.A({right arrow over (r.sub.A)}{right arrow over (b)}) to produce the fourth permuted encrypted difference vector .sub.B2(E.sub.A({right arrow over (r.sub.A)}{right arrow over (b)})).

(95) It should be understood that in some embodiments, some steps performed during the intermediate calculation phase may instead be performed at an earlier or later phase. As an example, the first permutation .sub.A1, second permutation .sub.A2, third permutation .sub.B1 and fourth permutation .sub.B2 may be generated during the setup phase (setup phase 404 from FIG. 4). Likewise, the first negation vector {right arrow over (a)}, and the second negation vector {right arrow over (b)} may also be generated during the setup phase, rather than during the intermediate calculation phase as described.

(96) Returning to FIG. 4, following intermediate calculation phase 408, the first computer and the second computer may perform second transmission phase 410. In second transmission phase 410, the first computer and the second computer may transmit data generated during intermediate calculation phase 408 to one another. These data may be used to calculate the scalar product {right arrow over (a)}.Math.{right arrow over (b)} in scalar product calculation phase 412, as described below.

(97) More specifically, in second transmission phase 410, the first computer may transmit, to the second computer, the first permuted encrypted difference vector .sub.A1(E.sub.B ({right arrow over (b)}{right arrow over (a)})) and the second permuted encrypted difference vector .sub.A2(E.sub.B({right arrow over (r.sub.B)}{right arrow over (a)})) Likewise, in second transmission phase 410, the first computer may receive, from the second computer, a third permuted encrypted difference vector .sub.B1(E.sub.A({right arrow over (a)}{right arrow over (b)})) and a fourth permuted encrypted difference vector .sub.B2(E.sub.A({right arrow over (r.sub.A)}{right arrow over (b)})), wherein the third permuted encrypted difference vector .sub.B1(E.sub.A({right arrow over (a)}{right arrow over (b)})) is encrypted using the first public key Pb.sub.A and permuted using a third permutation .sub.B1, and wherein the fourth permuted encrypted difference vector .sub.B2(E.sub.A({right arrow over (r.sub.A)}{right arrow over (b)}) is encrypted using the second public key Pb.sub.A and permuted using a fourth permutation .sub.B2.

(98) As in first transmission phase 406, these data (i.e., the first permuted encrypted difference vector .sub.A1(E.sub.B({right arrow over (b)}{right arrow over (a)})), the second permuted encrypted difference vector .sub.A2(E.sub.B({right arrow over (r.sub.B)}{right arrow over (a)})), the third permuted encrypted difference vector .sub.B1(E.sub.A({right arrow over (a)}{right arrow over (b)})) and the fourth permuted encrypted difference vector .sub.B2(E.sub.A({right arrow over (r.sub.A)}{right arrow over (b)})) may be transmitted over any appropriate network in any appropriate form. For example, these data may be transmitted over a network such as the Internet in data packets such as UDP or TCP packets.

(99) Following second transmission phase 410, the first computer and the second computer may proceed to scalar product calculation phase 412, in which the first computer and the second computer calculate the scalar product of the first vector {right arrow over (a)} and the second vector {right arrow over (b)}. Scalar product calculation phase 412 may be better understood with reference to FIG. 7.

(100) At step 702A, the first computer can produce a third permuted difference vector {right arrow over (d.sub.A)}:=.sub.B1({right arrow over (a)}{right arrow over (b)}) by decrypting the third permuted encrypted difference vector .sub.B1(E.sub.A ({right arrow over (a)}{right arrow over (b)})) using the first private key Pr.sub.A. Although the first computer knows the value of the components of the first masked vector {right arrow over (a)}, because the third permutation .sub.B1 is unknown to the first computer, the first computer cannot determine the value of the components of the second vector {right arrow over (b)}. Thus, the second vector {right arrow over (b)} is protected from the first computer. This may maintain the privacy of a person corresponding to the second vector {right arrow over (b)} (e.g., if the second vector {right arrow over (b)} is a biometric vector corresponding to the person).

(101) At step 702B, the second computer can produce a first permuted difference vector {right arrow over (d.sub.B)}:=.sub.A1({right arrow over (b)}{right arrow over (a)}) by decrypting the first permuted encrypted difference vector .sub.A1(E.sub.B({right arrow over (b)}{right arrow over (a)})) using the third private key Pr.sub.B. Although the second computer knows the value of the components of the second masked vector {right arrow over (b)}, because the first permutation .sub.A1 is unknown to the second computer, the second computer cannot determine the value of the components of the first vector {right arrow over (a)}. Thus the first vector {right arrow over (a)} is protected from the second computer. This may maintain the privacy of a person corresponding to the first vector {right arrow over (a)} (e.g., if the first vector {right arrow over (a)} is a biometric vector corresponding to the person).

(102) At step 704A, the first computer can produce a fourth permuted difference vector {right arrow over (s.sub.A)}:=.sub.B2({right arrow over (r.sub.A)}{right arrow over (b)}) by decrypting the fourth permuted encrypted difference vector .sub.B2(E.sub.A({right arrow over (r.sub.A)}{right arrow over (b)})) using the second private key Pr.sub.A. Again, the second vector {right arrow over (b)} is protected from the first computer, because although the first computer knows the value of the components of the first random vector {right arrow over (r.sub.A)}, the first computer does not know the fourth permutation .sub.B2.

(103) At step 704B, the second computer can produce a second permuted difference vector {right arrow over (s.sub.B)}:=.sub.A2({right arrow over (r.sub.B)}{right arrow over (a)}) by decrypting the second permuted encrypted difference vector .sub.A2(E.sub.B({right arrow over (r.sub.B)}{right arrow over (a)})) using the fourth private key Pr.sub.B. Again, the first vector {right arrow over (a)} is protected from the second computer, because although the second computer knows the value of the components of the second random vector {right arrow over (r.sub.B)}, the second computer does not know the second permutation .sub.A2.

(104) At step 706A, the first computer can calculate a square magnitude of the first masked vector . The value of the square magnitude of the first masked vector is equal to the scalar product of the first masked vector {right arrow over (a)} with itself, i.e.:
={right arrow over (a)}.Math.{right arrow over (a)}

(105) The first computer may square the value of each component of the first masked vector {right arrow over (a)}, then sum the resulting squares, i.e., the first computer may calculate the square magnitude of the first masked vector according to the following formula:
=.sub.i=1.sup.na.sub.i.sup.2

(106) Likewise, at step 706B, the second computer can calculate the square magnitude of the second masked vector . The value of the square magnitude of the second masked vector is equal to the scalar product of the second masked vector {right arrow over (b)} with itself, i.e.:
={right arrow over (b)}.Math.{right arrow over (b)}

(107) The second computer may square the value of each component of the second masked vector {right arrow over (b)}, then sum the resulting squares, i.e., the second computer may calculate the square magnitude of the second masked vector according to the following formula:
=.sub.i=1.sup.nb.sub.i.sup.2

(108) At step 708A, the first computer can calculate a square magnitude of the first random vector .sub.A. The value of the square magnitude of the first random vector .sub.A is equal to the scalar product of the first random vector {right arrow over (r.sub.A )} with itself, i.e.:
.sub.A={right arrow over (r.sub.A)}.Math.{right arrow over (r.sub.A)}

(109) The first computer may square the value of each component of the first random vector {right arrow over (r.sub.A)}, then sum the resulting squares, i.e., the first computer may calculate the square magnitude of the first random vector .sub.A according to the following formula:
.sub.A=.sub.i=1.sup.nr.sub.Ai.sup.2

(110) Likewise, at step 708B, the second computer can calculate the square magnitude of the second random vector .sub.B. The value of the square magnitude of the second random vector is equal to the scalar product of the second random vector {right arrow over (r.sub.B)} with itself, i.e.:
.sub.B={right arrow over (r.sub.B)}.Math.{right arrow over (r.sub.B)}

(111) The second computer may square the value of each component of the second random vector {right arrow over (r.sub.B)}, then sum the resulting squares, i.e., the second computer may calculate the square magnitude of the second random vector .sub.B according to the following formula:
.sub.B=.sub.i=1.sup.nr.sub.Bi.sup.2

(112) At step 710A, the first computer can calculate the square magnitude of the third permuted difference vector .sub.A. The value of the square magnitude of the third permuted difference vector .sub.A is equal to the scalar product of the third permuted difference vector {right arrow over (d.sub.A)}=.sub.B1({right arrow over (a)}{right arrow over (b)}) with itself, i.e.:
.sub.A={right arrow over (d.sub.A)}.Math.{right arrow over (d.sub.A)}

(113) The first computer may square the value of each component of the third permuted difference vector {right arrow over (d.sub.A)}=.sub.B1({right arrow over (a)}{right arrow over (b)}), then sum the resulting squares, i.e., the first computer may calculate the square magnitude of the third permuted difference vector .sub.A according to the following formula:
.sub.A=.sub.i=1.sup.nd.sub.Ai.sup.2

(114) Likewise, at step 710B, the second computer can calculate the square magnitude of the first permuted difference vector .sub.B. The value of the square magnitude of the first permuted difference vector .sub.B is equal to the scalar product of the first permuted difference vector {right arrow over (d.sub.B)}:=.sub.A1({right arrow over (b)}{right arrow over (a)}) with itself, i.e.:
.sub.B={right arrow over (d.sub.B)}.Math.{right arrow over (d.sub.B)}

(115) The second computer may square the value of each component of the first permuted difference vector {right arrow over (d.sub.B)}:=.sub.A1({right arrow over (b)}{right arrow over (a)}), then sum the resulting squares, i.e., the second computer may calculate the square magnitude of the first permuted difference vector .sub.B according to the following formula:
.sub.B=.sub.i=1.sup.nd.sub.Bi.sup.2

(116) At step 712A, the first computer can calculate the square magnitude of the fourth permuted difference vector .sub.A. The value of the square magnitude of the fourth permuted difference vector .sub.A is equal to the scalar product of the fourth permuted difference vector {right arrow over (s.sub.A)}:=.sub.B2({right arrow over (r.sub.A)}{right arrow over (b)}) with itself, i.e.:
.sub.A={right arrow over (s.sub.A)}.Math.{right arrow over (s.sub.A)}

(117) The first computer may square the value of each component of the fourth permuted difference vector {right arrow over (s.sub.A)}:=.sub.B2({right arrow over (r.sub.A)}{right arrow over (b)}), then sum the resulting squares, i.e., the first computer may calculate the square magnitude of the fourth permuted difference vector .sub.A according to the following formula:
.sub.A=.sub.i=1.sup.ns.sub.Ai.sup.2

(118) Likewise, at step 712B, the second computer can calculate the square magnitude of the second permuted difference vector .sub.B. The value of the square magnitude of the second permuted difference vector .sub.B is equal to the scalar product of the second permuted difference vector {right arrow over (s.sub.B)}:=.sub.A2({right arrow over (r.sub.B)}{right arrow over (a)}) with itself, i.e.:
.sub.B={right arrow over (s.sub.B)}.Math.{right arrow over (s.sub.B)}

(119) The second computer may square the value of each component of the second permuted difference vector {right arrow over (s.sub.B)}:=.sub.A2({right arrow over (r.sub.B)}{right arrow over (a)}), then sum the resulting squares, i.e., the second computer may calculate the square magnitude of the fourth permuted difference vector .sub.B according to the following formula:
.sub.B=.sub.i=1.sup.ns.sub.Bi.sup.2

(120) At step 714A, the first computer may calculate the scalar product of the first vector {right arrow over (a)} and the second vector {right arrow over (b)} based on the square magnitude of the first masked vector , the square magnitude of the first random vector .sub.A, the square magnitude of the third permuted difference vector .sub.A, and the square magnitude of the fourth permuted difference vector .sub.A. In some embodiments, the first computer may calculate the scalar product of the first vector {right arrow over (a)} and the second vector {right arrow over (b)} based on the following formula:
{right arrow over (a)}.Math.{right arrow over (b)}=(.sub.A.sub.A+.sub.A)

(121) Likewise, at step 714B, the second computer may calculate the scalar product of the first vector {right arrow over (a)} and the second vector {right arrow over (b)} based on the square magnitude of the second masked vector {right arrow over ()}, the square magnitude of the second random vector .sub.B, the square magnitude of the first permuted vector .sub.B, and the square magnitude of the second permuted vector .sub.B. In some embodiments, the second computer may calculate the scalar product of the first vector {right arrow over (a)} and the second vector {right arrow over (b)} based on the following formula:
{right arrow over (a)}.Math.{right arrow over (b)}=(.sub.B.sub.B+.sub.B)

(122) As a brief aside, it may be helpful to show that the methods used by the first computer and the second computer to calculate the scalar product of the first vector {right arrow over (a)} and the second vector {right arrow over (b)} accurately calculate the scalar product as described above.

(123) Recall that by definition, the scalar product of two vectors is equal to the sum of the product of the components of each vector:
{right arrow over (a)}.Math.{right arrow over (b)}:=E.sub.i=1.sup.na.sub.ib.sub.i

(124) As stated above, the first computer calculates the scalar product of the first vector {right arrow over (a)} and the second vector {right arrow over (b)} using the square magnitude of the first masked vector , the square magnitude of the first random vector .sub.A, the square magnitude of the third permuted vector .sub.A and the square magnitude of the fourth permuted vector .sub.A according to the following formula:
{right arrow over (a)}.Math.{right arrow over (b)}=(.sub.A.sub.A+.sub.A)

(125) As a reminder, the square magnitude of a given vector {right arrow over (c)} is defined as the sum of the components of the vector {right arrow over (c)} squared:
{right arrow over (c)}:=E.sub.i=1.sup.nc.sub.i.sup.2

(126) As defined above, the third permuted difference vector {right arrow over (d.sub.A)}=.sub.B1({right arrow over (a)}{right arrow over (b)}) The square magnitude of the third permuted difference vector .sub.A can be expressed as follows:
.sub.A=E.sub.i=1.sup.n.sub.B1(a.sub.ib.sub.i).sup.2

(127) Because of the commutative property of addition, the sum is independent of the permutation, hence:
.sub.A=.sub.i=1.sup.n(a.sub.ib.sub.i).sup.2
.sub.A=.sub.i=1.sup.n(a.sub.i.sup.22a.sub.ib.sub.i+b.sub.i.sup.2)
.sub.A=.sub.i=1.sup.na.sub.i.sup.22.sub.i=1.sup.na.sub.ib.sub.i+.sub.i=1.sup.nb.sub.i.sup.2

(128) By the definition of the scalar product and the square magnitude of the first masked vector , the square magnitude of the third permuted difference vector .sub.A can be further expressed as:
.sub.A=2({right arrow over (a)}.Math.{right arrow over (b)})+{right arrow over (b)}.Math.{right arrow over (b)}

(129) Using a similar line of reasoning, the fourth permuted difference vector .sub.A can be expressed as follows:
.sub.A:=.sub.i=1.sup.ns.sub.Ai.sup.2
{right arrow over (s.sub.A)}:=.sub.B2({right arrow over (r.sub.A)}{right arrow over (b)})
.sub.A=.sub.i=1.sup.n.sub.B2(r.sub.Aib.sub.i).sup.2
.sub.A=.sub.i=1.sup.n(r.sub.Aib.sub.i).sup.2
.sub.A=.sub.i=1.sup.n(r.sub.Ai.sup.22r.sub.Aib.sub.i+b.sub.i.sup.2)
.sub.A=.sub.i=1.sup.nr.sub.Ai.sup.22.sub.i=1.sup.nr.sub.Aib.sub.i+.sub.i=1.sup.nb.sub.i.sup.2
.sub.A=.sub.A2({right arrow over (r.sub.A)}.Math.{right arrow over (b)})+{right arrow over (b)}.Math.{right arrow over (b)}

(130) Returning to the expression for the scalar product and substituting the expressions for the square magnitude of the third permuted difference vector .sub.A and the square magnitude of the fourth permuted difference vector .sub.A:
{right arrow over (a)}.Math.{right arrow over (b)}=(.sub.A.sub.A+.sub.A)
{right arrow over (a)}.Math.{right arrow over (b)}=(.sub.A(2({right arrow over (a)}.Math.{right arrow over (b)})+{right arrow over (b)}.Math.{right arrow over (b)})+(.sub.A2({right arrow over (r.sub.A)}.Math.{right arrow over (b)})+{right arrow over (b)}.Math.{right arrow over (b)}))

(131) Grouping alike terms:
{right arrow over (a)}.Math.{right arrow over (b)}=(2({right arrow over (a)}.Math.{right arrow over (b)}{right arrow over (r.sub.A)}.Math.{right arrow over (b)})+()+(.sub.A.sub.A)+({right arrow over (b)}.Math.{right arrow over (b)}{right arrow over (b)}.Math.{right arrow over (b)}))
{right arrow over (a)}.Math.{right arrow over (b)}={right arrow over (a)}.Math.{right arrow over (b)}{right arrow over (r.sub.A)}.Math.{right arrow over (b)}

(132) Recall that the first masked vector {right arrow over (a)} is equal to the sum of the first vector {right arrow over (a)} and the first random vector {right arrow over (r.sub.A)}:
{right arrow over (a)}:={right arrow over (a)}+{right arrow over (r.sub.A)}

(133) The expression for the scalar product can be simplified as follows:
{right arrow over (a)}.Math.{right arrow over (b)}=({right arrow over (a)}+{right arrow over (r.sub.A)}).Math.{right arrow over (b)}{right arrow over (r.sub.A)}.Math.{right arrow over (b)}
{right arrow over (a)}.Math.{right arrow over (b)}={right arrow over (a)}.Math.{right arrow over (b)}+({right arrow over (r.sub.A)}.Math.{right arrow over (b)}{right arrow over (r.sub.A)}.Math.{right arrow over (b)})
{right arrow over (a)}.Math.{right arrow over (b)}={right arrow over (a)}.Math.{right arrow over (b)}

(134) This demonstrates the accuracy of the formula used by the first computer to calculate the scalar product of the first vector {right arrow over (a)} and the second vector {right arrow over (b)}.

(135) Similarly, the second computer calculates the scalar product of the first vector {right arrow over (a)} and the second vector {right arrow over (b)} using the square magnitude of the second masked vector , the square magnitude of the second random vector .sub.B, the square magnitude of the first permuted difference vector .sub.B and the square magnitude of the second permuted difference vector .sub.B according to the following formula:
{right arrow over (a)}.Math.{right arrow over (b)}=(.sub.B.sub.B+.sub.B)

(136) Using a similar line of reasoning, an expression for the square magnitude of the first permuted difference vector .sub.B can be determined:
.sub.B:=.sub.i=1.sup.nd.sub.Bi.sup.2
{right arrow over (d.sub.B)}:=.sub.A1({right arrow over (a)}{right arrow over (b)})
.sub.B=.sub.i=1.sup.n.sub.A1(b.sub.ia.sub.i).sup.2
.sub.B=.sub.i=1.sup.n(b.sub.ia.sub.i).sup.2
.sub.B=.sub.i=1.sup.n(b.sub.i.sup.22b.sub.ia.sub.i+a.sub.i.sup.2)
.sub.B=.sub.i=1.sup.nb.sub.i.sup.22.sub.i=1.sup.nb.sub.ia.sub.i+.sub.i=1.sup.na.sub.i.sup.2
.sub.B=2({right arrow over (b)}.Math.{right arrow over (a)})+{right arrow over (a)}.Math.{right arrow over (a)}

(137) Likewise, an expression for the square magnitude of the second permuted difference vector .sub.B can be determined:
.sub.B:=.sub.i=1.sup.ns.sub.Bi.sup.2
{right arrow over (s.sub.B)}:=.sub.A2({right arrow over (r.sub.B)}{right arrow over (a)})
.sub.B=.sub.i=1.sup.n.sub.A2(r.sub.Bia.sub.i).sup.2
.sub.B=.sub.i=1.sup.n(r.sub.Bia.sub.i).sup.2
.sub.B=.sub.i=1.sup.n(r.sub.Bi.sup.22r.sub.Bia.sub.i+a.sub.i.sup.2)
.sub.B=.sub.i=1.sup.nr.sub.Bi.sup.22.sub.i=1.sup.nr.sub.Bia.sub.i+.sub.i=1.sup.na.sub.i.sup.2
.sub.B=.sub.B2({right arrow over (r.sub.B)}.Math.{right arrow over (a)})+{right arrow over (a)}.Math.{right arrow over (a)}

(138) Returning to the expression for the scalar product and substituting expressions for the square magnitude of the first permuted difference vector .sub.3 and the square magnitude of the second permuted difference vector .sub.B:
{right arrow over (a)}.Math.{right arrow over (b)}=(.sub.B.sub.B+.sub.B)
{right arrow over (a)}.Math.{right arrow over (b)}=(.sub.B(2({right arrow over (b)}.Math.{right arrow over (a)})+{right arrow over (a)}.Math.{right arrow over (a)})+(.sub.B2({right arrow over (r.sub.B)}.Math.{right arrow over (a)})+{right arrow over (a)}.Math.{right arrow over (a)}))
Grouping alike terms:
{right arrow over (a)}.Math.{right arrow over (b)}=(2({right arrow over (b)}.Math.{right arrow over (a)}{right arrow over (r.sub.B)}.Math.{right arrow over (a)})+()+(.sub.B.sub.B)+({right arrow over (a)}.Math.{right arrow over (a)}{right arrow over (a)}.Math.a))
{right arrow over (a)}.Math.{right arrow over (b)}={right arrow over (b)}.Math.{right arrow over (a)}{right arrow over (r.sub.B)}.Math.{right arrow over (a)}

(139) The second masked vector {right arrow over (b)} is equal to the sum of the second vector {right arrow over (b)} and the second random vector {right arrow over (r.sub.B)}:
{right arrow over (b)}:={right arrow over (b)}+{right arrow over (r.sub.B)}:

(140) The expression for the scalar product can be simplified as follows:
{right arrow over (a)}.Math.{right arrow over (b)}=({right arrow over (b)}+{right arrow over (r.sub.B)}).Math.{right arrow over (a)}{right arrow over (r.sub.B)}.Math.{right arrow over (a)}
{right arrow over (a)}.Math.{right arrow over (b)}={right arrow over (b)}+{right arrow over (a)}+({right arrow over (r.sub.B)}.Math.{right arrow over (a)}{right arrow over (r.sub.B)}.Math.{right arrow over (a)})
{right arrow over (a)}.Math.{right arrow over (b)}={right arrow over (b)}.Math.{right arrow over (a)}

(141) This demonstrates that the equation used by the second computer the calculate the scalar product of the first vector {right arrow over (a)} and the second vector {right arrow over (b)} is accurate.

(142) Returning to FIG. 7, at step 716A, the first computer can compare the scalar product or a value derived from the scalar product to a first predetermined threshold T.sub.A and if the scalar product or the value derived from the scalar product exceeds the first predetermined threshold (i.e., (.sub.A.sub.A+.sub.A)>T.sub.A), the first computer may perform an interaction with the second computer (i.e., during interaction phase 414 of FIG. 4), such as a payment transaction or gaining entry into a secure building for a user or owner of the first computer. Examples of values that could be derived from scalar products include the angle between the first vector {right arrow over (a)} and the second vector {right arrow over (b)}, or the cosine of the angle between the first vector {right arrow over (a)} and the second vector {right arrow over (b)}, or another trigonometric function of the angle between the first vector {right arrow over (a)} and the second vector {right arrow over (b)}, or some other value, such as a match score, distance metric, etc.

(143) As an example, if the match criteria is that the angle between the first vector {right arrow over (a)} and the second vector {right arrow over (b)} is 5 degrees or less, and the value derived from the scalar product is the cosine of the angle between the first vector {right arrow over (a)} and the second vector {right arrow over (b)}, the first predetermined threshold T.sub.A could equal cos(5)=0.996. If the value derived from the scalar product is greater than the first predetermined threshold T.sub.A, it indicates that the angular difference between the first vector {right arrow over (a)} and second vector {right arrow over (b)} is 5 degrees or less, potentially indicating a match.

(144) In some embodiments, the first vector {right arrow over (a)} and the second vector {right arrow over (b)} can correspond to a first biometric template and a second biometric template respectively, and the first predetermined threshold T.sub.A may be a biometric match threshold.

(145) At step 716B, the second computer can compare the scalar product or a value derived from the scalar product (e.g., an angle between the first vector {right arrow over (a)} and the second vector {right arrow over (b)}, or a trigonometric function of the angle between the first vector {right arrow over (a)} and the second vector {right arrow over (b)}) to a second predetermined threshold T.sub.B, and if the scalar product or the value derived from the scalar product exceeds the second predetermined threshold (i.e., (.sub.B.sub.B+.sub.B)>T.sub.B), the second computer can perform an interaction with the first computer (i.e., during interaction phase 414 from FIG. 4), such as performing a payment transaction or allowing a user of the first computer access to a secure building.

(146) In some embodiments, the first predetermined threshold T.sub.A and the second predetermined threshold T.sub.B may be unequal, indicating that either the first computer or the second computer may have a higher threshold for performing an interaction. However, in other embodiments it may be advantageous for the first predetermined threshold T.sub.A and the second predetermined threshold T.sub.B to be equal.

(147) In some embodiments, after comparing the scalar product or a value derived from the scalar product to the first predetermined threshold T.sub.A, the first computer may transmit an indication message to the second computer, indicating that the first computer is satisfied with the comparison and will proceed with an interaction. Likewise, after comparing the scalar product or a value derived from the scalar product to the second predetermined threshold T.sub.B, the second computer may transmit an indication message to the first computer, indicating that the second computer is satisfied with the comparison and will proceed with an interaction. Alternatively or additionally, each of the first and/or second computer can include an indicator (e.g., on a display) when an appropriate match is determined (e.g., a green light) or is not determined (e.g., a red light).

(148) An advantage of both computers comparing the scalar product to their respective thresholds is that both computers can confirm that the scalar exceeds their respective thresholds. If, for example, only the first computer compared the scalar product to its respective threshold, the second computer has to trust that the first computer calculated the scalar product correctly and that the first computer honestly indicated that the scalar product exceeded the first predetermined threshold. However, because both computers calculate the scalar product and compare the scalar product or a value derived from the scalar product to their respective threshold, each computer can confirm the calculation and neither computer can cheat the other.

(149) Returning to FIG. 4, following scalar product calculation phase 412, the first computer and the second computer may perform an interaction in interaction phase 414. The interaction may be performed if the scalar product, or a value derived from the scalar product (e.g., an angle, a heuristic estimate of the angle, a cosine of an angle, a heuristic estimate of the cosine of an angle, another distance metric, etc.) exceeds a predetermined threshold, as described with reference to FIG. 7.

(150) The interaction of interaction phase 414 may take many forms. FIG. 8 shows a block diagram of a first exemplary interaction, a payment transaction. FIG. 9 shows a block diagram of a second exemplary interaction, a building access sequence.

(151) FIG. 8 shows an exemplary transaction processing system. This transaction processing system may be used as part of a first exemplary interaction between first computer 804 and second computer 806.

(152) User 802 may be a customer operating first computer 804 (e.g., a smart phone). User 802 may wish to purchase a good or service from a resource provider (e.g., a merchant, operating resource provider computer 810). The resource provider may additionally operate an access terminal 808 (e.g., a point of sale terminal). The resource provider computer 810 may communicate with an issuer computer 816 via an acquirer computer 812 and a payment processing network 814.

(153) The payment processing network 814 may include data processing subsystems, networks, and operations used to support and deliver authorization services, exception file services, and clearing and settlement services. An exemplary payment processing network 814 may include VisaNet. Payment processing networks such as VisaNet are able to process credit card transactions, debit card transactions, and other types of commercial transactions. VisaNet, in particular, includes a VIP system (Visa Integrated Payments system) that processes authorization requests and a BASE II system which performs clearing and settlement services. The payment processing network may use an suitable wired or wireless network, including the Internet.

(154) An exemplary payment transaction using a biometric vector based privacy-preserving scalar product calculation can be described as follows. The user 802 may bring the first computer 804 into contact with access terminal 808 such that first computer 804 and access terminal 808 can communicate, via for example, near field communication. The first computer 804 can communicate to access terminal 808 that the user 802 wishes to pay for goods or services. The access terminal 808 may request a credential, such as an access token that can be used to enact a payment between a payment account associated with the user 802, managed by an issuer and a payment account associated with the resource provider, managed by an acquirer.

(155) To acquire the access token, the first computer 804 and the second computer 806 may perform a privacy preserving scalar product calculation, in order to calculate the scalar product of the first biometric vector, stored on the first computer 804, and a second biometric vector, stored in a biometric vector database on the second computer 806. The first computer 804 and second computer 806 may perform the scalar product calculation as described above with reference to FIGS. 4-7. Upon calculating the scalar product, the second computer 806 may compare the scalar product or a value derived from the scalar product to a predetermined threshold. If the scalar product or the value derived from the scalar product exceeds the predetermined threshold, the second computer 806 may transmit an access token to first computer 804 (this transmission may comprise the interaction between the first computer 804 and the second computer 806).

(156) Having received the access token from second computer 806, the first computer 804 may transmit the access token and any additional access credentials to the access terminal 808. The resource provider computer 810, operating in communication with access terminal 808, may then generate an authorization request message that includes the information received by the access terminal 808 along with any additional transaction information (e.g., a transaction amount, merchant specific information, etc.) and electronically transmits this information to acquirer computer 812. The acquirer computer 812 may then receive, process, and forward the authorization request message to the issuer computer 816 via the payment processing network 814 for authorization. The issuer computer 816 may reply with an authorization response message. The authorization response message may be transmitted from the issuer computer 816 to the access terminal 808 via the resource provider computer 810, the acquirer computer 812, and the payment processing network 814.

(157) At the end of the day or at some other suitable time interval, a clearing and settlement process between the acquirer computer 812, the payment processing network 814, and the issuer computer 816 may be performed on the transaction.

(158) FIG. 9 shows a second exemplary interaction according to some embodiments. A user 902 wishes to gain access to building 910, a secure facility (i.e., a secure apartment complex or government administrative building). The door to building 910 is locked and controlled by a resource provider computer 908. In order to gain access to building 910, the user 902 needs to provide an access token or another credential to resource provider computer 908, via first computer 904 (e.g., user's 902 smart phone).

(159) User 902 can have previously enrolled in a biometric authentication system involving a second computer 906. The second computer 906 may store a biometric vector (second vector) corresponding to user 902 in a biometric database. Similarly, the first computer 904 may store a saved biometric vector (first vector) corresponding to the user 902 on a secure element. Alternatively, the user 902 may use first computer 904 to capture a biometric instance and vectorize the captured biometric instance, e.g., by pointing a smart phone camera at their eye and taking a picture.

(160) As part of the biometric authentication system, the first computer 904 and second computer 906 can calculate the scalar product of the first vector and second vector in order to authenticate user 902. After calculating the scalar product (as described above with reference to FIGS. 4-7), the second computer 906 can compare the scalar product or a value derived from the scalar product (e.g., the angle between the first vector and the second vector) to a predetermined threshold. If the scalar product or the value derived from the scalar product exceeds the predetermined threshold, the user 902 may be authenticated. Subsequently, the second computer 906 can transmit an instruction to the resource provider computer 908, instructing the resource provider computer 908 to open the door and allow user 902 access to building 910. Alternatively, the second computer 906 can issue an access token to first computer 904. The first computer 904 can subsequently provide this access token to resource provider 908 (e.g., via near field communication or via a network such as the Internet or a LAN). The resource provider computer 908 can verify the access token and grant user 902 access to building 910.

(161) Any of the computer systems mentioned herein may utilize any suitable number of subsystems. In some embodiments, a computer system includes a single computer apparatus, where the subsystems can be components of the computer apparatus. In other embodiments, a computer system can include multiple computer apparatuses, each being a subsystem, with internal components.

(162) A computer system can include a plurality of the components or subsystems, e.g., connected together by external interface or by an internal interface. In some embodiments, computer systems, subsystems, or apparatuses can communicate over a network. In such instances, one computer can be considered a client and another computer a server, where each can be part of a same computer system. A client and a server can each include multiple systems, subsystems, or components.

(163) It should be understood that any of the embodiments of the present invention can be implemented in the form of control logic using hardware (e.g., an application specific integrated circuit or field programmable gate array) and/or using computer software with a generally programmable processor in a modular or integrated manner. As used herein a processor includes a single-core processor, multi-core processor on a same integrated chip, or multiple processing units on a single circuit board or networked. Based on the disclosure and teachings provided herein, a person of ordinary skill in the art will know and appreciate other ways and/or methods to implement embodiments of the present invention using hardware and a combination of hardware and software.

(164) Any of the software components or functions described in this application may be implemented as software code to be executed by a processor using any suitable computer language such as, for example, Java, C, C++, C#, Objective-C, Swift, or scripting language such as Perl or Python using, for example, conventional or object-oriented techniques. The software code may be stored as a series of instructions or commands on a computer readable medium for storage and/or transmission, suitable media include random access memory (RAM), a read only memory (ROM), a magnetic medium such as a hard-drive or a floppy disk, or an optical medium such as a compact disk (CD) or DVD (digital versatile disk), flash memory, and the like. The computer readable medium may be any combination of such storage or transmission devices.

(165) Such programs may also be encoded and transmitted using carrier signals adapted for transmission via wired, optical, and/or wireless networks conforming to a variety of protocols, including the Internet. As such, a computer readable medium according to an embodiment of the present invention may be created using a data signal encoded with such programs. Computer readable media encoded with the program code may be packaged with a compatible device or provided separately from other devices (e.g., via Internet download). Any such computer readable medium may reside on or within a single computer product (e.g. a hard drive, a CD, or an entire computer system), and may be present on or within different computer products within a system or network. A computer system may include a monitor, printer or other suitable display for providing any of the results mentioned herein to a user.

(166) Any of the methods described herein may be totally or partially performed with a computer system including one or more processors, which can be configured to perform the steps. Thus, embodiments can be involve computer systems configured to perform the steps of any of the methods described herein, potentially with different components performing a respective steps or a respective group of steps. Although presented as numbered steps, steps of methods herein can be performed at a same time or in a different order. Additionally, portions of these steps may be used with portions of other steps from other methods. Also, all or portions of a step may be optional. Additionally, and of the steps of any of the methods can be performed with modules, circuits, or other means for performing these steps.

(167) The specific details of particular embodiments may be combined in any suitable manner without departing from the spirit and scope of embodiments of the invention. However, other embodiments of the invention may be involve specific embodiments relating to each individual aspect, or specific combinations of these individual aspects. The above description of exemplary embodiments of the invention has been presented for the purpose of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form described, and many modifications and variations are possible in light of the teaching above. The embodiments were chosen and described in order to best explain the principles of the invention and its practical applications to thereby enable others skilled in the art to best utilize the invention in various embodiments and with various modifications as are suited to the particular use contemplated.

(168) A recitation of a, an or the is intended to mean one or more unless specifically indicated to the contrary. The use of or is intended to mean an inclusive or, and not an exclusive or unless specifically indicated to the contrary.

(169) All patents, patent applications, publications and description mentioned herein are incorporated by reference in their entirety for all purposes. None is admitted to be prior art.