# US 10,873,447 B2 · Efficient concurrent scalar product calculation

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,873,447 B2
- Document ID: US10873447B2
- Status: Granted
- Kind: B2
- Application number: 16/428,514
- Filed: 2019-05-31
- Published: 2019-11-28
- Granted: 2020-12-22
- Earliest claimed: 2018-05-24
- Assignees: Visa International Service Association
- Applicants: Visa International Service Association
- Inventors: Kim Wagner
- Web page: https://patentgrep.com/patent/US10873447B2

## CPC

- H04L 9/008: {involving homomorphic encryption}
- G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)}
- G06Q 20/20: Point-of-sale [POS] network systems
- G06Q 20/367: {involving electronic purses or money safes}
- G06Q 20/401: {Transaction verification}
- G06Q 20/40145: {Biometric identity checks}
- G06Q 20/4018: {using the card verification value [CVV] associated with the card}
- H04L 9/14: using a plurality of keys or algorithms
- H04L 9/30: Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
- H04L 9/302: {involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes}
- H04L 9/3231: {Biological data, e.g. fingerprint, voice or retina (network architectures or network communication protocols for supporting authentication of entities using biometrical features in a packet data network H04L63/0861)}
- H04L 9/3234: {involving additional secure or trusted devices, e.g. TPM, smartcard, USB or software token (network architectures or network communication protocols for supporting authentication of entities using an additional device in a packet data network H04L63/0853)}
- G06Q 2220/00: Business processing using cryptography
- H04L 2209/04: Masking or blinding
- H04L 2209/46: Secure multiparty computation, e.g. millionaire problem
- H04L 2209/56: Financial cryptography, e.g. electronic payment or e-cash
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 1)

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.

### Claim 7 (depends on 1)

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.

### Claim 8 (depends on 1)

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.

### Claim 9 (depends on 8)

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.

### Claim 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.

### Claim 11 (depends on 10)

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.

### Claim 12 (depends on 10)

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.

### Claim 13 (depends on 10)

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.

### Claim 14 (depends on 10)

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.

### Claim 15 (depends on 10)

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.

### Claim 16 (depends on 10)

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.

### Claim 17 (depends on 10)

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.

### Claim 18 (depends on 17)

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.