| |
|
Video surveillance is a critical tool for a variety of tasks such as law enforcement, personal
safety, traffic control, resource planning, and security of assets, to name a few. Rapid
development/deployment of closed circuit television (CCTV) technology is playing a key role in
observing suspicious behavior. However, the proliferation in the use of cameras for surveillance
has introduced severe concerns of privacy. Everyone is constantly being watched on the
roads, offices, supermarkets, parking lots, airports, or any other commercial establishment. This
raises concerns such as, watching you in your private moments, locating you at a specific place
and time or with a person, spying on your everyday activities, or even implicitly controlling
some of your actions.
|
| |
|
Privacy, therefore, happens to be a serious concern in the Age of Video Surveillance. Widespread
usage of surveillance cameras raises the specter of an invasive `Big Brother' society. In this
regards, certain privacy laws have been introduced to guard an individuals privacy/rights. Despite
these, video surveillance remains vulnerable to abuse by unscrupulous operators with criminal or
voyeuristic aims and to institutional abuse for discriminatory purposes. These legitimate concerns
frequently slow the deployment of surveillance systems. The challange of introducing privacy and
security in such a practical surveillance system has been stifled by enormous computational and communication
overhead required by the solutions.
|
| |
|
Privacy preserving video surveillance addresses these contrasting requirements of confidentiality
and utility. The objective is to allow the general surveillance to continue, without disrupting the
privacy of an individual. This novel technology addresses the critical issue of “privacy invasion” in
an efficient and cost-effective way.
|
| |
| Thus, we address the question, "Can surveillance be done without
looking at the original video?"
|
| |
|
| |
|
We have proposed a 'cloud computing' based solution that utilizes the services of k > 2 non-colluding computational servers.
The privacy of our surveillance system is based on splitting the information in an image into multiple shares, such that no share by itself conveys anything meaningful about the original image. Each share is then sent to an independent server for processing/storage.
|
| |
The protocol in a nutshell:
The camera splits each captured frame, F, into k (>2) shares using a shatter function Φ(F) = [I1, I2, ..., Ik ]. Each share is then sent to an independent computation server for processing. Note: no meaningful information about the original frame can be learned from any share.
To carry out the basic operation f on the input image, each server carries out an equivalent binary operation f' on its share. This is equivalent to the corresponding basic operation being carried out on the original image.
The results of the operations on the shares are then integrated by the observer using a merge function, to obtain the final result.
|
| |
|
| |
| The approach is designed so as to satisfy the following concerns related to video surveillance. |
| |
| Preserves Privacy | Ensures that the person doing surveillance learns only the final results and nothing else. |
| Computationally Efficient | The image representation should allow efficient computations so as to realize surveillance algorithms in the encrypted domain itself. Moreover, the encoding at the sensor should be lightweight. |
| Efficient to Transmit | The encoding process should not blow up the size of the video data. |
| Secure Storage | One should be able to store the surveillance data in a secure fashion, so that breaking into a storage server do not compromise the privacy of the data. |
| Address Legal Issues | For legal or investigative purposes, someone with authorization should be able to reconstruct the plain video without client's help. |
|
| Mandatory and desirable characteristics of a secure, privacy-preserving video surveillance system. |
| |
| |
| While general purpose secure computation appears to be inherently complex and oftentimes impractical, we show that due to certain "suitable" properties of visual information, efficiency and security co-exists in the domain of computer vision! We exploit the following facts, which are valid for most of the computer vision tasks. Meaningful images from real-world has following properties that are of interest to us:
|
| |
Limited and fixed Range: The values that an algorithm can take is finite and is from a limited fixed range. And more importantly the range is known aprior. Thus, the algorithms that have multiple possible answers, but only one of them within this possible range, are as valid as solutions that have only one answer. Such algorithms need not be useful (or correct) for a general purpose (non-vision) tasks. In this paper, we exploit this by designing an efficient,
secure surveillance solutions that has infinite answers, but only one of them in the valid range. Interestingly, in this process, we also circumvent OT, thereby gaining in efficiency.
Scale Invariance: The information in the image remains practically unchanged even if we change the units of measurement or scale the whole data. This is not true for most non-image information. We exploit this to design a wrapper algorithm which converts a partially secure algorithm to a completely secure one. For example, consider a partially secure algorithm that may reveal the LSB of all the pixels. Suppose this algorithm is run on an input which is scaled (at least by a factor of two) with all the LSBs randomized. Then note that with practically no change in the output, the original input (before scaling) is completely secure.
Approximate Nature: The image captured by a camera is an approximate representation of the scene. In practice, the camera sensor that is used to capture an image, is itself noisy. That is, the probability that the camera would generate exactly same images of the scene captured at two different instances, under identical conditions (lighting etc) is negligible. In practice, this implies that the pixel value of 100 = 101, for the captured image. Thus adding negligible `hetrogeneous' noise to an image doesn't effect the information retained by the image.
Non-general Operands: A typical vision algorithm has several operators and operands. However there is no need to expect that all possible pairs could exist in any execution. While it is important to have the ability to implement all operators, it is not practically necessary to allow all possible operands. We design our algorithm over a set which is a finite field with very few exceptions (division by some specific apriori known numbers is forbidden). Fortunately, our approach allows one to choose these "forbidden" numbers. Therefore in principle as well as in practice, it is as powerful as having general operands.
|
| |
| Keeping in mind the above properties, we design a vision specific, distributed framework for surveillance tasks that preserves privacy. The emphasis is on performing this efficiently, thus faciliating proactive surveillance. In our framework, we shatter each video into shares and send each one to a different site in such a way that each site has no information about the scene (data-specific secret sharing). The complete algorithm runs in this distributed setup, such that at the end of the protocol, all that the observer recovers is the final output from the results obtained at each of the site.
|
| |
| Secret Sharing refers to a method for distributing a secret among a group of servers each of which is allocated a share of the secret. The secret can be reconstructed only when the shares are combined together; on their own, the individual shares gives no information of the secret. Several types of secret sharing schemes have been proposed in literature. Shamir's secret sharing scheme represents the secret as the y-intercept of an n-degree polynomial, and shares correspond to points on the polynomial. In contrast, Blakley's scheme specifies the secret as a point in n-dimensional space, and gives out shares that correspond to hyperplanes that intersect the secret point. The primary motivation behind SS is of securing a secret over multiple servers. However, computing functions on the input secretly shared among n-servers, requires highly communication intensive protocols (which relies on some sort of SMC). Furthermore, such schemes result in huge data expansion, which becomes in-efficient for large secrets, such as live-videos (as in our case). For example, Shamir's shares are each as large as the original secret, whereas Blakley's scheme is even less space-efficient than Shamir's.
|
| |
 |
| Example of Secret Sharing: Each secret share is a plane, and the secret is the point
at which three shares intersect. Two shares yield only a line intersection. |
| |
| Secret Sharing Using CRT |
| |
| There are many different versions of the Secret Sharing Scheme based on Chinese Remainder in literature.
Mignotte [Mignotte83] and Asumth et al [Asmuth83] used co-prime numbers pi's while
Goldreich et al [Goldreich00] focused only on prime numbers. We now describe the SS using
CRT as presented by Goldreich et al [Goldreich00]. In the remainder of this section, x \in_R S means that x is selected from S with an uniform probability. |
| |
| Initialization: |
| Let t+1 < l, where l is the number of shares and t+1 is the minimum number of shares needed to recover the secret. Consider the primes p0 < p1 < p2 < ... < pl. Each prime is uniquely associated with an independent server. The primes pi, which play a key role in computing the secret shares, are assumed to be public. The security of the system is based on the non-colluding nature of the servers.
|
| |
| Sharing: |
| Consider a secret r0 ≡ s ∈ Ζp_0 that is to be securely shared among the l servers. The data owner generates and distributes the secret shares as follows:
|
| |
Choose t uniform random numbers satisfying the constrain, r1 ∈R Ζp_1, ..., rt ∈R Ζp_t.
Determines Y ∈ ΖP where P ≡ t∏i=0 pi such that Y ≡ ri mod pi for i = 0,1, ..., t. This can be efficiently computed using CRT.
The secret is encoded in the resulting Y. We now wish to securely share the new secret Y. The secret shares are computed as, si = Y mod pi for i = 0,1, ..., l.
|
| |
| Reconstruction: |
| To reconstruct the secret s, a user needs to recollect atleast t+1 of the l shares held by different servers. Given a set of t+1 shares si: i ∈ I, the secret s is recovered as follows:
|
| |
Compute X ∈ Ζ ∏i ∈ I pi, such that X ≡ si mod pi for i ∈ I. This is efficiently computatable using CRT.
The actual secret s is given by s = X mod p0.
| |
| In the above reconstruction, note that the recovered X was nothing but the encoded Y. The secret s which was constrained to be ∈ Ζp_0 is correctly (uniquely) recovered by taking modulo p0 of the recovered X.
|
| |
| Limitation of Standard Secret Sharing Scheme |
| In the above scheme, each share is of size |pi| bits. The total share size is therefore given by i < l ∑i = 1 |pi| > l ... |p0|. Choosing an optimal p0 becomes curcial since it determines both the range of numbers we can correctly represent as well as the total size of the shares. To understand the data expansion, consider VJ face detector [VJ01] as the algorithm we want to securely execute on a 320*240 input frame. In the input video frame, each pixel is in range [0, 255], as an 8 bit integer. Now, during the execusion of the VJ, the maximum intermediate value we can expect is 320*240*255, a 21 bit integer. Hence our p0 has to be atleast 21 bits long. Therefore, every 8 bit pixel is expanded into shares with the total size of atleast 21 ... l bits. This is significant, since the camera needs to communicate the shares over to the servers, thus becoming the bottleneck for the complete system.
|
| |
| The primary motivation is proposing a paradigm shift for our real-time tasks was to reduce communication. We next show that visual-data has certain characteristic properties, which can be exploited to define a tailor made SS scheme exclusively for visual data. Compared to the standard CRT based SS schmes, our scheme significantly reduces the data expansion by atleast a factor of l, where l is the number of servers/shares. Such reduction is prominent for huge data such as live-video feeds, thus making privacy preserving video surveillance practical.
|
|
| |
| The modular transformation that forms the basis of our protocol is based on the chinese remainder theorem. In this section, we provide the intutive reasoning in utilizing the scaling and randomization to design the modular transformations. The modular transformations Φp() and μp() are given by:
|
| |
| The shatter function: Φp() is defined as: |
| |
| di = Φp (d, pi) = (d.s + η) mod pi |
| |
| where, d is a single pixel in the image, pi are the k primes defining the
RNS (each prime is uniquely associated with a unique server, and are public), s is a constant positive scale factor (assumbed to public), and η is a uniform random number in the range 0..s (the noise is random for each pixel of each frame) |
| |
 |
| Data Obfuscation: Information retained in a shattered share for various scale factors and the corresponding η distributions. |
| |
| Given the correlation between the neighboring pixels in an image, the modulo remainder reveals significant information about the secret (image). However, as shown above, choosing an optimal scale factor and the corresponding noise distribution will result in completely random looking shares. |
| |
| |
| The Merge function: μp() is defined as: |
| |
| d = μp(di, pi) = CRT(di, pi) / s |
| |
| where, CRT is the function given by Chinese Remainder Theorem. CRT recovers (d.s + η), which is then appropriately scaled down (integer division by the scale factor) to get the actual value of d. The solution is unique if all the intermediate values (di, f'(di)) are less than the product of the primes pi's. Note that, η which was randomly choosen for each pixel is not used for recovering the secret. The CRT hence forms our recovery transformation μp(), at the pixel level.
|
| |
| In a nutshell: |
| |
We achieve efficiency by working in the modulo domain, thus avoiding
communication overheads of solutions such as SMC.
Working in modular domain does not ensure privacy (since residue is
revealed). This is more serious for visual data, since modular image would
retain most of the information of the original image. We achieve privacy by
adding random numbers to every pixel before taking the mod.
Evidently, directly adding random noise is a poor solution, since accuracy is
traded off. We scale pixel values before adding random numbers to maintain
accuracy. We can select the scale factor, the random numbers
and the prime divisors to achieve perfect accuracy while maintaining complete
privacy.
The surveillance algorithm runs independently on each of the servers.
Interaction is limited and for evaluation of functions which require merging
of results, eg: thresholding. This is again secured by randomization/shuffle and use of
another untrusted server.
CRT is used to recover the result from the output of each server.
|
| |
| We have presented experimental results on a range of tasks and data (change detection, optical flow tracking, face detection). The results presented are aimed at understanding the computational and communication overheads at each stage, any loss in accuracy incurred by computation in the proposed framework, as well as the effectiveness of the data obfusction for privacy.
|
| |
 |
| Change Detection: (b,c) are the shattered shares seen by one of the compute servers, (d) is the obfuscated difference image obtained after a pixel shuffle, (e) is the output as available with the observer, (f) output image overlayed with the original frame.
|
| |
 |
| Face Detection: (a) Captured Input Image, (b) Detected RoI as received by the observer, (c) Detection Result, if run on plain image.
|
| |
| The above two figures shows the outputs of the face detection algorithm and motion detection as computed in our distributed setup. The corresponding plain domain results are also shown for comparision. For more details of the experimental setup, please refer to the paper. |
| |
 |
| Time required to shatter/merge a frame with increasing number of servers. |
| |
| The above figure shows the time required for each shattering and merging operation for a frame. We note that the time required for merging is considerably higher due to the use of large-number arithmetic when dealing with scaled numbers. Even then, the system is able to do these operations in well under a second.
|
| |
 |
| Average Data Size (without compression) VS the amount of parallelization |
| |
| The above table shows the average number of bits in an encoded frame and the total image size. An interesting observation from the Table is that as the number of compute servers (or primes) increases, the average bits in the resultant image first decreases, and then increases. The increase in the later part is due to the need of using larger primes, which drives up the size of the resulting image. One can always choose an optimal number of servers as explained in the paper.
|
| |
 |
 |
| Additional Results. |
