GB2566039A

GB2566039A - Apparatus and method for processing data

Info

Publication number: GB2566039A
Application number: GB1713913.0A
Authority: GB
Inventors: Waller Adrian; Barnett Anthony; Stainton-Bygrave Charlie
Original assignee: Thales Holdings UK PLC
Current assignee: Thales Holdings UK PLC
Priority date: 2017-08-30
Filing date: 2017-08-30
Publication date: 2019-03-06
Anticipated expiration: 2037-08-30
Also published as: GB2566039B; GB201713913D0

Abstract

A method of classifying image data comprises: identifying features of interest and describing them in one or more feature vectors 44; applying to the feature vectors a Somewhat Homomorphic Encryption (SHE) algorithm 46, to produce a cryptodata element, the SHE algorithm supporting a multiplicative depth sufficient to evaluate a polynomial kernel of degree d; and producing an output bearing the cryptodata element; a classifying phase (S1-12), wherein a support vector machine (SVM) with polynomial kernel of degree no greater than d is applied to the cryptodata element to produce a classification output. The method allows a data provider to share sensitive image data with an algorithm provider, and for the algorithm provider to provide an image classification result to the data provider, in such a way that neither party is cognisant of the processes and/or information held by the other party. The method could find application in categorising land use from aerial or satellite images (20).

Description

Apparatus and method for processing data

FIELD

The present disclosure concerns machine based classification on encrypted data.

BACKGROUND

Image processing is used to automate the extraction of useful information from raw image data. An important example of this is object classification, in which real-life objects in an image are identified algorithmically. Object classification can comprise identification of an object as a vehicle, a person or an animal.

Algorithms for object classification are typically based around machine learning. Development of machine learning algorithms can involve a considerable amount of effort and expertise. This makes such algorithms valuable, and thus, owners of such algorithms have substantial motivation for ensuring that detailed information on their operation is not disseminated without restriction. However, there is substantial demand for use of these algorithms to classify objects in image data. Potential users of such algorithms may have multiple reasons for not wishing to hand over potentially sensitive image data to operators of such object classification algorithms.

So, a problem exists, in that operators of image processing algorithms cannot, or will not, disseminate their algorithms to 3^rd parties without restriction, and gatherers of image information do not wish to hand over their image data to operators of image processing algorithms.

Currently, this problem is circumvented contractually. One or other of the image data provider, and the algorithm provider, agreed to hand over their sensitive information to the other, and to trust the other party not to abuse it. This is not ideal, as it can be difficult to detect infringements of these contractual arrangements, and remedies will inevitably be costly and unsatisfactory. In particular, any remedy for a breach of confidentiality cannot reverse the breach; that is, the situation cannot be returned to the position before the breach occurred.

Thus, it is desirable that the above technical problems, and others related thereto, be ameliorated by technical means, rather than being circumvented by non-technical contractual means.

SUMMARY

In general terms, embodiments disclosed herein are concerned with transit of image data from one entity to another in an encrypted form. According to the disclosure, an at least somewhat homomorphic encryption (SHE) scheme is used to encrypt image data at an image data generator. The encrypted image data can then be passed to an image data classifier, running an object classification algorithm. Specifically, the object classification algorithm, of embodiments disclosed herein, employs a support vector machine (SVM) with a polynomial kernel, which can carry out classification on unencrypted data.

Embodiments disclosed herein allow the evaluation process of an SVM with polynomial kernel to be computed efficiently on encrypted data. This enables an algorithm provider, which has previously trained such an SVM, to perform object classifications without releasing details of the algorithm. Similarly, it allows providers of image data to make use of such object classification algorithms, without having to release unencrypted image data thereto.

DESCRIPTION OF DRAWINGS

Figure 1 illustrates a general arrangement of an image capture and processing system in accordance with an embodiment;

Figure 2 illustrates, schematically, a data processing centre of the embodiment illustrated in figure 1; and

Figure 3 illustrates a flow diagram of a process which can be performed by the apparatus of the described embodiment.

DESCRIPTION OF EMBODIMENTS

Embodiments disclosed herein provide means by which image classification using an SVM with a polynomial kernel can be carried out on encrypted data. This allows a data provider to offer up potentially sensitive image data to an algorithm provider, and for the algorithm provider to provide an image classification result to the data provider, in such a way that neither the data provider nor the algorithm provider is cognisant of the processes and/or information held by the other party.

Figure 1 illustrates a general arrangement of a communications system 10 in which an embodiment is implemented.

As shown, an observation satellite 20 is in orbit above the Earth, and is under the general control of a control centre 22. The observation satellite 20 is operable to generate raw image data defining images captured at the satellite 20. This raw image data is captured at the satellite 20 and sent to a data processing centre (DPC) 40 via a ground station 30. It will be noted by the reader that this could be protected using conventional encryption (for example asymmetric algorithm such as AES) at the satellite, and decrypted at the DPC 40.

The structure of the DPC 40 is illustrated in figure 2. Function of the DPC 40, in conjunction with a classifier 50 as will be described in due course, is illustrated in figure

3.

Once the raw image data is received at the DPC 40 (step S1-2 in figure 3), it is decrypted in a satellite signal decryptor 41 (step S1-4) to render it ready for image processing algorithms to be applied. A pre-processor 42 of the DPC 40 first performs any non-sensitive pre-processing steps on the unencrypted data (step S1-6). For example, the raw image data could be subject to data preparation steps, such as a fast Fourier transform (FFT), or object detection algorithms to identify the area of an image that is of interest.

Then, features are extracted in a feature extractor 44 (step S1-8) to create feature vectors compatible with the model implemented by a classifier 50, operated by a socalled algorithm provider.

The described embodiment is flexible as to the exact nature and characteristic of a “feature” to be extracted from image data. This will, to some extent, be application specific. So, for example, if the image data is being collected and analysed for the purpose of agricultural land use survey, such as to determine the type and condition of crops being grown, it may be appropriate to extract data relating to the shape of crop allocations in fields, such as by identifying sharp transitions (edges) from one feature to another, indicative of the edge of a field. It may also be appropriate to extract data relating to the colour and intensity of a crop, which may be used later in the process to determine expected yield, for instance.

In general terms, therefore, a feature vector is a multi-scalar mathematical data entitity which stores information to define a pattern or characteristic of an image. As exemplified above, a feature vector might describe greyscale colour values of feature edges, blocks of a particular colour, shapes of objects, and so on.

Features in image processing are information derived from an image that are either of interest in their own right or useful for further processing (such as classification). Examples of features include pixel values, points, edges, objects, curves or boundaries between different image regions, or properties of these regions. The specific approach to feature extraction will, to some extent, depend on the application to which the feature extraction is being put.

SHE encryption is applied (step S1-10) to the extracted feature vectors in an SHE encryptor/decryptor 46, and the encrypted data is then sent to the external classifier 50. One aspect of this specific embodiment is that the feature extraction process is tailored to the SHE implementation. Indeed, as the reader will appreciate, the selection of a suitable SHE implementation and that of a suitable SVM classification algorithm are dependent on each other.

By way of background, a Somewhat Homomorphic Encryption (SHE) scheme is a Homomorphic Encryption scheme that can evaluate arithmetic circuits (i.e. circuits formed of additions and multiplications) of limited multiplicative depth. To put these in context, a Fully Homomorphic Encryption (FHE) scheme would be capable of evaluating circuits of any multiplicative depth. FHE schemes are typically constructed using SHE schemes, however, they tend to be much more inefficient. Some algorithms, for example classification using SVMs with polynomial kernels, only require limited depth arithmetic circuits. In these cases SHE schemes are sufficient, and much more efficient than FHE schemes.

There are many examples of SHE schemes that could be used with this embodiment. An example of a class of schemes that would be suitable are those based on the Learning With Errors (LWE) problem, and its generalisation to rings (the Ring-LWE problem). In particular, the reader’s attention is directed to known examples in the art, including:

• Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) fully homomorphic encryption without bootstrapping. In Shafi Goldwasser, editor, ITCS 2012, pages 309-325. ACM, January 2012.

• Zvika Brakerski and Vinod Vaikuntanathan. Efficient fully homomorphic encryption from (standard) LWE. In Rafail Ostrovsky, editor, 52nd FOCS, pages 97- 106. IEEE Computer Society Press, October 2011.

• Zvika Brakerski and Vinod Vaikuntanathan. Fully homomorphic encryption from ring-LWE and security for key dependent messages. In Phillip Rogaway, editor, CRYPTO 2011, volume 6841 of LNCS, pages 505-524. Springer, Heidelberg, August 2011.

These schemes have been optimized and implemented in a series of articles:

• Craig Gentry, Shai Halevi, and Nigel P. Smart. Better bootstrapping in fully homomorphic encryption. In Marc Fischlin, Johannes Buchmann, and Mark Manulis, editors, PKC 2012, volume 7293 of LNCS, pages 1-16. Springer, Heidelberg, May 2012.

• Craig Gentry, Shai Halevi, and Nigel P. Smart. Fully homomorphic encryption with polylog overhead. In David Pointcheval and Thomas Johansson, editors,

EUROCRYPT 2012, volume 7237 of LNCS, pages 465-482. Springer, Heidelberg, April 2012.

• Craig Gentry, Shai Halevi, and Nigel P. Smart. Homomorphic evaluation of the AES circuit. In Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, pages 850- 867. Springer, Heidelberg, August 2012.

Also, an implementation, “HElib” has been made freely available, such as at shaih.github.io/HElib. HElib is a software library that implements homomorphic encryption, using the Brakerski-Gentry-Vaikuntanathan (BGV) scheme identified in the above publications.

On receipt of the SHE encrypted data, the classifier 50 applies (step S1-12) its polynomial kernel SVM object classification algorithm to obtain an encrypted classification result.

There is a relationship between the degree, d, of the polynomial kernel, and the multiplicative depth supported by the SHE algorithm. In essence, the multiplicative depth supported by the SHE algorithm should be sufficient to enable evaluation of a polynomial kernel of degree d. The value of d is application specific.

Mindful of the fact that the classifier 50 is operating on encrypted feature data, it is desirable that the feature extraction process is tailored to “strip down” the amount of feature data provided to the classifier 50. That is, the feature extraction process is adapted to the fact that the resultant feature vectors are encrypted before classification. This ameliorates any problems which may arise through the computational complexity of running a classifier on encrypted data.

By providing less information to the classifier, but of the most desirable type, the performance of the classifier can be improved. This takes account of the fact that, offering less information to the classifier may reduce the accuracy of classification results, but enables it to operate at a practical speed.

Finally, the encrypted result is returned to the DPC 40, wherein the SHE encryptor/decryptor 46 reverses the previously applied encryption (step S1-14) to obtain the desired classification information. This is then integrated (step S1-16) with the original image data at an image data integrator 48 and presented as annotated image information to a user computer 60, to enable the presentation of the classification information to a user.

It will be noted by the reader that it could, in theory, be possible for the model parameters defining the classification algorithm operated by the algorithm provider 50 to be discerned by obtaining multiple classification results and solving a series of simultaneous equations based on these results. It is uncertain whether or not this is practically achievable, and it probably depends on the complexity of the polynomial kernel employed by the classifier. Using a sufficiently complex polynomial kernel will probably increase the complexity of this reverse engineering process to the extent that it is effectively intractable.

However, in order to provide additional security against this possibility, further techniques may be employed to secure the processes and data defining the algorithm used in the classifier 50. For example, the classifier 50 may in unmodified form be configured to output a classification result which is a signed number. The sign of the number may be indicative of the classification outcome, that is, whether or not a given formation in the input data is or is not an instance of a particular class of objects. The magnitude of the classification result may be indicative of the confidence associated with the classification. That is, a relatively low magnitude classification result is indicative of a low degree of confidence to be attached to the classification, while a relatively high number indicates that the classification has a high level of certainty attached to it.

The classifier 50 is set up on the basis of sets of training data. For increased classifier performance, the classifier 50 implements a support vector machine which constructs a function which can be used to determine whether a particular point, in input space, is one side of a classification boundary or another. The boundary is defined by machine learning from the training data.

Classifying data points as being of one type or not of that type can be complex. It may be difficult to determine a simple function which will enable a clear decision to be taken. Commonly, sets of data (i.e. whether a data point is a member of a particular class or not) may not be linearly separable. In such circumstances, the present embodiment implements a kernel function, to map the input space to a kernel space in which the boundary can be resolved into a simpler expression and, ideally, a hyperplane. Then, determination of distance of an input from the boundary can be calculated efficiently, as the dot product can be calculated without computational complexity.

In this embodiment, the kernel function is polynomial. The precise coefficients of the kernel function are determined by training, ideally on clear data rather than encrypted data. Then, due to the nature of the cryptographic method, i.e. SHE, the kernel will achieve classification results even though crypto data is input in use. This is because, SHE encryption does not change arithmetic relationships between scalar quantities making up a feature vector. This enables use of the classification equation, known to machine learning, on an encrypted feature vector.

The outcome of classification is a classification result. The classification result is a number, specifically a real number. The sign of the classification result returned by the classifier is an indication as to the side of the classification boundary, defined by the kernel function, on which the classified input is determined to lie. However, the magnitude of the number also provides a measure of uncertainty in the classification.

In general terms, the magnitude of the classification result indicates the level of certainty that can be assumed of the result. A relatively high magnitude classification result tells the observer, or a next stage in a data processing algorithm, that a relatively high level of certainty can be applied to the result.

Results that are closer to zero in value indicate substantial uncertainty as to whether the classification is correct. This uncertainty can be conveyed to users and/or later stages in a data processing algorithm.

It is known to use logistic regression to obtain a confidence graph, which maps the magnitude to a confidence value between 0 and 1. This can be achieved through training on a number of sample images, and obtaining data on the magnitude of the results paired with whether the classification is correct or not. The resulting curve provides classifications that effectively hide the number returned by the classifier and prevent reverse engineering of the model. As an additional benefit, they also return confidence values that are of use to the end user.

A remaining difficulty is that evaluating a logistic regression curve is not possible with an SHE scheme. However, the curve can be effectively approximated by a taylor series expansion of low degree which can be directly evaluated by the Algorithm Provider on the encrypted result using an SHE scheme.

It should be noted by the reader that approximation using a taylor series expansion is only accurate for small values of the magnitude of the classification result. However, it is for small values that the confidence value is of use and value. Larger values correspond to high certainty, and therefore if the taylor series returns curve returns erroneous results greater than 1 or less than 0 these can simply be mapped by the end user back to 0 and 1 respectively without loss of value in the results, or incorrect classification.

While certain embodiments have been described, these embodiments have been presented by way of example only, and are not intended to limit the scope of the inventions. Indeed, the novel devices described herein may be embodied in a variety of other forms; furthermore, various omissions, substitutions and changes in the form of the methods and systems described herein may be made without departing from the sprit of the inventions. The accompanying claims and their equivalents are intended to cover such forms or modifications as would fall within the scope and spirit of the inventions.

Claims

CLAIMS:

1. An image classification system comprising an image data processor operable to process a data element comprising image data and a classifying machine for classifying received data elements and to provide a classification output, wherein the image data processor comprises:

a feature vector extractor operable to identify, from the data element, characteristics in the data element indicative of features of interest and to describe such characteristics in one or more feature vectors;

an encryptor operable to apply, to the feature vectors, an encryption algorithm, the encryption algorithm being at least a Somewhat Homomorphic Encryption, SHE, algorithm, to produce a cryptodata element, the SHE algorithm supporting at least a multiplicative depth sufficient to evaluate a polynomial kernel of degree d; and wherein the image data processor is operable to produce an output bearing the cryptodata element;

and wherein the classifying machine comprises a support vector machine, SVM, with polynomial kernel of degree no greater than d, the classifying machine being operable on a cryptodata element to produce a classification output.

2. An image classification system in accordance with claim 1 and further comprising a pre-processor operable to apply image processing to a data element to produce a pre-processed data element.

3. An image classification system in accordance with claim 2 wherein the preprocessor is operable to assemble, from a sequence of data captures, a preprocessed data element indicative of image features common to the data captures.

4. An image classification system in accordance with any one of the preceding claims wherein the feature vector extractor is operable to identify, from the data element, a characteristic of an image represented by the data element.

5. An image classification system in accordance with claim 4 wherein the feature vector extractor is operable to identify a characteristic defined in terms of satisfaction of a condition by a particular pixel or group of pixels of the image.

6. An image classification system in accordance with claim 5 wherein the feature vector extractor is operable to define a feature vector identifying said one or more pixels of an image satisfying said condition.

7. An image classification system in accordance with claim 4 wherein the feature vector extractor is operable to identify a characteristic defined in terms of satisfaction of a condition by a boundary between two pixels, or two groups of pixels, of the image.

8. An image classification system in accordance with claim 7 wherein the feature vector extractor is operable to define a feature vector identifying said boundary satisfying said condition.

9. An image data processor operable to process a data structure comprising image data, the image data processor comprising:

a feature vector extractor operable to identify, from the data structure, characteristics in the data structure indicative of features of interest and to describe such characteristics in one or more feature vectors;

an encryptor operable to apply, to the feature vectors, an encryption algorithm, the encryption algorithm being at least a Somewhat Homomorphic Encryption, SHE, algorithm, to produce a cryptodata element, the SHE algorithm supporting a multiplicative depth sufficient to evaluate a polynomial kernel of degree d; and wherein the image data processor is operable to produce an output bearing the cryptodata element, and to send the output to a classifying machine which comprises a support vector machine, SVM, with polynomial kernel of degree no greater than d, and to receive a classification output from the classifying machine.

10. A method of classifying image data comprising an image data processing phase for processing a data element comprising image data and a classifying phase for classifying received data elements and to provide a classification output, wherein the image data processing phase comprises:

identifying, from the data element, characteristics in the data element indicative of features of interest and describing such characteristics in one or more feature vectors;

applying, to the feature vectors, an encryption algorithm, the encryption algorithm being at least a Somewhat Homomorphic Encryption, SHE, algorithm, to produce a cryptodata element, the SHE algorithm supporting at least a multiplicative depth sufficient to evaluate a polynomial kernel of degree d; and producing an output bearing the cryptodata element;

and wherein the classifying phase comprises implementing a support vector machine, SVM, with polynomial kernel of degree no greater than d, and applying the SVM to the cryptodata element to produce a classification output.