One-to-many matching with application to efficient privacy-preserving re-identification

Patent metadata

Field	Value
Publication number	US-9762393-B2
Application number	US-201514662939-A
Country	US
Kind code	B2
Filing date	Mar 19, 2015
Priority date	Mar 19, 2015
Publication date	Sep 12, 2017
Grant date	Sep 12, 2017

Abstract

Authentication methods are disclosed for determining whether a person or object to be authenticated is a member of a set of authorized persons or objects. A query signature is acquired comprising a vector whose elements store values of an ordered set of features for the person or object to be authenticated. The query signature is compared with an aggregate signature comprising a vector whose elements store values of the ordered set of features for the set of authorized persons or objects. The individual signatures for the authorized persons or objects are not stored; only the aggregate signature. It is determined whether the person or object to be authenticated is a member of the set of authorized persons or objects based on the comparison. The comparing may comprise computing an inner product of the query signature and the aggregate signature, with the determining being based on the inner product.

First claim

The invention claimed is:

1. An authentication system comprising:
an authenticator comprising:
an electronic data processing device;
a non-transitory storage medium storing instructions readable and executable by the electronic data processing device to perform an authentication process to determine whether a person or object to be authenticated belongs to a set of authorized persons or objects, the authentication process including the operations of:
acquiring a query signature comprising a vector whose elements store values of an ordered set of features for the person or object to be authenticated;
computing a single inner product of the query signature and a single aggregate signature comprising a vector whose elements store values of the ordered set of features for the set of authorized persons or objects wherein the single aggregate signature is not uniquely associated with any particular authorized person or object of the set of authorized persons or objects; and
determining whether the person or object to be authenticated is a member of the set of authorized persons or objects based on the single inner product of the query signature and the single aggregate signature; and

an authenticator training component comprising an electronic data processing device configured to generate the single aggregate signature representing the set of authorized persons or objects by operations including:
generating a set of authorized signatures by acquiring a signature for each authorized person or object comprising a vector whose elements store values of the ordered set of features for that authorized person or object; and
determining the single aggregate signature by whitening the authorized signatures using a set of background signatures that are not labeled as to membership in the set of authorized signatures and aggregating the whitened authorized signatures;
wherein the determining of the single aggregate signature does not use any signature that is labeled to indicate it is an unauthorized signature that is not in the set of authorized signatures.

2. The authentication system of claim 1 wherein the person or object to be authenticated is a person to be authenticated, the set of authorized persons or objects includes only authorized persons, and the operation of acquiring the query signature comprises:
acquiring biometric data for the person to be authenticated; and
extracting the values of the ordered set of features for the person to be authenticated from the acquired biometric data.

3. The authentication system of claim 2 wherein the biometric data including one of an electronic fingerprint, one or more face images, and an eye scan.

4. The authentication system of claim 2 further comprising:
a computer; and
an electronic fingerprint reader integral with the computer;
wherein the operation of acquiring biometric data comprises causing the electronic fingerprint reader to acquire a fingerprint of the person to be authenticated; and
wherein the computer is programmed to perform a login process in response to the authenticator determining the person to be authenticated is a member of the set of authorized persons.

5. The authentication system of claim 1 wherein the person or object to be authenticated is a vehicle to be authenticated, the set of authorized persons or objects is a set of authorized vehicles, and the operation of acquiring the query signature comprises:
acquiring an image of a license plate of the vehicle to be authenticated; and
extracting the values of the ordered set of features for the vehicle to be authenticated from the image of the license plate.

6. The authentication system of claim 5 further comprising:
a camera; and
a vehicle barrier gate;
wherein the operation of acquiring the image uses the camera to acquire the image of the license plate of the vehicle to be authenticated; and
wherein the vehicle barrier gate includes a gate actuator operatively connected to open the vehicle barrier gate in response to the authenticator determining the vehicle to be authenticated is a member of the set of authorized vehicles.

7. The authentication system of claim 1 wherein:
the operation of determining the single aggregate signature comprises determining the single aggregate signature to set the inner product of each authorized signature and the single aggregate signature to a target inner product value; and
the operation of determining whether the person or object to be authenticated is a member of the set of authorized persons or objects comprises comparing the single inner product of the query signature and the single aggregate signature with the target inner product value.

8. The authentication system of claim 1 wherein:
the operation of determining the single aggregate signature comprises sum aggregating the authorized signatures; and
the operation of determining whether the person or object to be authenticated is a member of the set of authorized persons or objects comprises performing a threshold operation on the single inner product of the query signature and the single aggregate signature.

9. The authentication system of claim 1 wherein the operation of determining the single aggregate signature is performed using generalized max pooling.

10. The authentication system of claim 9 wherein the generalized max pooling is performed using ridge regression.

11. The authentication system of claim 1 wherein:
the authenticator and the authenticator training component comprise different electronic data processing devices; and
the authenticator does not have access to the set of authorized signatures generated at the authenticator training component.

12. An authentication method for determining whether a person or object to be authenticated is a member of a set of authorized persons or objects, the authentication method comprising:
generating a set of authorized signatures for the set of authorized persons or objects by acquiring a signature for each authorized person or object comprising a vector whose elements store values of an ordered set of features for that authorized person or object;
determining a single aggregate signature whose elements store values of the ordered set of features for the set of authorized persons or objects by aggregating the authorized signatures of the set of authorized signatures;
acquiring a query signature comprising a vector whose elements store values of the ordered set of features for the person or object to be authenticated;
performing a single signature comparison comparing the query signature and the single aggregate signature; and
determining whether the person or object to be authenticated is a member of the set of authorized persons or objects based on the single signature comparison;
wherein one of:
(1) the determining of the single aggregate signature comprises determining the single aggregate signature to set the inner product of each authorized signature and the single aggregate signature to a target inner product value and the determining whether the person or object to be authenticated is a member of the set of authorized persons or objects comprises comparing the single inner product of the query signature and the single aggregate signature with the target inner product value; or
(2) the determining of the single aggregate signature comprises sum aggregating the authorized signatures and the determining whether the person or object to be authenticated is a member of the set of authorized persons or objects comprises performing a threshold operation on the single inner product of the query signature and the single aggregate signature.

13. The authentic

Assignees

• Xerox Corp
• Conduent Business Services Llc

Inventors

• Soldevila Albert Gordo
• Murray Naila
• Perronnin Florent C

Classifications

• H04L9/3231 Primary

  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) · CPC title

• G06Q10/00

  Administration; Management · CPC title

• H04L9/3247

  involving digital signatures · CPC title