Within cloud computing containerization has become ubiquitous. As the availability of pre-built containers increases there is a need for methods capable of efficiently securing large repositories of software containers. We present a “Trustworthy Container Repository” (TCR) system which provides security assurances (confidentiality, integrity, and authenticity) regarding such a repository in a scalable manner. Trust within the TCR architecture is rooted in a low-complexity, tamper-resistant trusted module, which leverages index-ordered Merkle trees (IOMTs) to efficiently track a large number of container images and provide assurances of repository integrity to its users. The key contributions of the study are, identification of the required security model, a novel TCR data-structure, and verifiable algorithms to operate on it. Through experiment, we observe closely logarithmic time complexity of the proposed system up to a high container count ( N = 2 25 ≈ 10 7 ).

Closed labs have provided hands-on experience for students under supervised conditions. Microlabs extend this approach into the lecture format with very short hands-on activities in the "middle of the lecture." We have tested this approach using tablets as small as 7 inches; student laptops can also be used. Logical microlabs allow students to solve a conceptual problem in computer science that does not involve any programming. Solutions are entered graphically and submitted for evaluation. Code magnet microlabs allow students to construct a method to solve the same problem programmatically. The code is compiled and, if successful, evaluated by a sequence of unit tests. These are integrated into a Microlab Learning Cycle of exploration (the logical microlab), invention (the instructor guides the students toward an algorithm during lecture), and application (the code magnet microlab). This approach has been evaluated at three universities and proven to be popular with students and educationally effective. This work is supported, in part, by three National Science Foundation grants.

In storage outsourcing services, clients store their data on a potentially untrusted server, which has more computational power and storage capacity than the individual clients. In this model, security properties such as integrity, authenticity, and freshness of stored data ought to be provided, while minimizing computational costs at the client, and communication costs between the client and the server. Using trusted computing technology on the server's side, we propose practical constructions in the provable data possession model that provide integrity and freshness in a dynamic, multi-user setting, where groups of users can update their shared files on the remote, untrusted server. Unlike previous solutions based on a single-user, single-device model, we consider a multi-user, multi-device model. Using trusted hardware on the server helps us to eliminate some of the previously known challenges with this model, such as forking and rollback attacks by the server. We logically separate bulk storage and data authentication issues to different untrusted remote services, which can be implemented either on the same or different physical servers. With only minor modifications to existing services, the bulk storage component can be provided by large-scale storage providers such as Google, CloudDrive, DropBox, and a smaller specialized server equipped with a trusted hardware chip can be used for providing data authentication. Our constructions eliminate client-side storage costs (clients do not need to maintain persistent state), and are suitable for situations in which multiple clients work collaboratively on remotely stored, outsourced data.

In this paper, we show how Trusted Platform Modules (TPMs), standard security hardware devices, can be used with minor modification to efficiently support Secure Function Evaluation (SFE), a fundamental and extremely powerful cryptographic operation. Prior research by others has shown how SFE can benefit from using security hardware, but prior work has used either custom hardware tokens or powerful secure co-processors which require significant changes to current computing systems. In this paper we show that similar techniques can be supported by TPMs with enhancements that are at the level of a firmware upgrade (albeit a secure firmware upgrade endorsed by the TPM manufacturer) - specifically, no new physical devices would need to be purchased or added to most modern business-class systems. This paper describes the specific changes that need to be made, and evaluates efficiency for a simple example in location-based privacy. Our evaluation shows that performance is reasonable for supporting simple privacy-enhanced applications.

When asymmetric cryptography techniques are used in wireless networks, the public keys of the nodes need to be widely available and signed by a Certificate Authority (CA). However, the existence of a single CA in large wireless networks such as mobile ad hoc networks and wireless sensor networks can lead the hotspot problem and become a security weakness. In this work, we propose a distributed technique to cache the public keys on regular nodes. Due to the limited memory size that each node is allowed to dedicate for key caching, only some keys can be cached. In our proposed technique, each node caches the public keys of a mix of local and remote nodes. Access to the public keys of other nodes is possible based on a chain of trust. Multiple copies of public keys from different chains of trusted nodes provide fault tolerance. We explain our technique in detail and investigate its salient features in this work. An interesting observation is the need to balance caching public keys of local nodes and remote nodes.

In this paper, we present a new system for anonymous authentication, which allows a user to prove possession of an authenticated credential while not revealing his or her identity. Our system is an extension of an existing group signature scheme, providing additional features drawn from work on traceable signatures and direct anonymous attestation. Our first extension, a property taken from traceable signatures, allows a signer to later "claim" a signature, proving that they are indeed the individual who created this signature. Our second extension, taken from the work on direct anonymous attestation, allows a prover and verifier to agree on the degree of linkability of transactions, ranging from completely unlinkable transactions, to being able to link transactions made within a fixed time period (like a day), to completely linkable transactions. Our scheme is efficient enough to be practical, and is proved to be secure under the strong RSA assumption and the decisional Diffie-Hellman assumption

In this paper we study the problem of determining an optimal investment strategy for investors with different attitudes towards the trade-offs of risk and profit. The probability distribution of the return values of the stocks that are considered by the investor are assumed to be known, while the joint distribution is unknown. The problem is to find the best investment strategy in order to minimize the probability of losing a certain percentage of the invested capital based on different attitudes of the investors towards future outcomes of the stock market. We show that for portfolios made up of two stocks, we can exactly and quickly solve the problem of finding an optimal portfolio for aggressive or risk-averse investors, using an algorithm based on a fast greedy solution to a maximum flow problem. However, an investor looking for an average-case guarantee (so is neither aggressive or risk-averse) must deal with a more difficult problem. In particular, we show that computing the distribution function associated with the average-case bound is ♯P-complete. On the positive side, we show how to use random sampling techniques similar to those for high-dimensional volume estimation to provide approximate answers. When k> 2 stocks are considered, we show that a simple solution based on the same flow concepts as our 2-stock algorithm would imply that P = NP, so is highly unlikely. We give approximation algorithms for this case as well as exact algorithms for some important special cases.

In this paper we examine problems motivated by on-line financial problems and stochastic games. In particular, we consider a sequence of entirely arbitrary distinct values arriving in random order, and must devise strategies for selecting low values followed by high values in such a way as to maximize the expected gain in rank from low values to high values. First, we consider a scenario in which only one low value and one high value may be selected. We give an optimal on-line algorithm for this scenario, and analyze it to show that, surprisingly, the expected gain is n-O(1), and so differs from the best possible off-line gain by only a constant additive term (which is, in fact, fairly small---at most 15). In a second scenario, we allow multiple nonoverlapping low/high selections, where the total gain for our algorithm is the sum of the individual pair gains. We also give an optimal on-line algorithm for this problem, where the expected gain is $n^2/8-\Theta(n\log n)$. An analysis shows that the optimal expected off-line gain is $n^2/6+\Theta(1)$, so the performance of our on-line algorithm is within a factor of 3/4 of the best off-line strategy.

Summary form only given. The Burrows-Wheeler transform (BWT) compression technique is based on sorting substrings of the input, and has a performance rivalling the best previously known techniques. We show that the ordering used in the sorting stage of the BWT, an aspect hitherto ignored, can have a significant impact on the size of the compressed data. We modify the sorting order in two separate ways. First, we try reordering the symbol alphabet, and doing a standard sort based on the permuted character set. This is particularly interesting because the BWT's sensitivity to alphabet ordering is fairly unique among general-purpose compression schemes. Previous techniques, including statistical techniques (such as the PPM algorithms) and dictionary techniques (represented by LZ77, LZ78, and their descendants), are largely based on pattern matching which is entirely independent of the encoding used for the source alphabet. On files in which the alphabet is arbitrarily ordered, such as ASCII text and certain domain-specific encoding; such as the geo file from the Calgary Compression Corpus, this technique improved the compression ratio of the BWT-based compression algorithm. On the other hand, data which already had a significant alphabet ordering, such as image data, showed little improvement with this technique. The second modified sorting technique was to modify the sorting algorithm itself to order strings in a manner analogous to reflected Gray codes. In particular, we alternated increasing and decreasing order on the second character position, changing whenever the character in the first position changed.

In this paper, we consider a model of lossless image compression in which each band of a multispectral image is coded using a prediction function involving values from a previously coded band of the compression, and examine how the ordering of the bands affects the achievable compression. We present an efficient algorithm for computing the optimal band ordering for a multispectral image. This algorithm has time complexity O(n/sup -/) for an n-band image, while the naive algorithm takes time /spl Omega/(n!). A slight variant of the optimal ordering problem that is motivated by some practical concerns is shown to be NP-hard, and hence, computationally infeasible, in all cases except for the most trivial possibility. In addition, we report on our experimental findings using the algorithms designed in this paper applied to real multispectral satellite data. The results show that the techniques described here hold great promise for application to real-world compression needs.

The author has extensively studied the benefits and problems associated with reordering the bands of a multispectral image for performing lossless compression. Under a reasonable model of inter-band prediction, he has shown how to efficiently compute the optimal compression band ordering. In addition, he has formalized the restrictions that arise when bands need to be extracted individually from a compressed archive, and has shown that computing the optimal ordering under these restrictions is NP-hard, except in the most simple case.>

Parallel tree contraction has been found to be a useful and quite powerful tool for the design of a wide class of efficient graph algorithms. We propose a corresponding technique for the parallel solution of incremental problems. As our computational model, we assume a variant of the CRCW PRAM where we can dynamically activate processors by a forking operation.

The authors demonstrate the power of combining the techniques of algebraic computation with ones of numerical computation. They do this by improving the known methods for polynomial evaluation on a set of real points and for simulation of n charged particles on the plane. In both cases they approximate (rather than exactly compute) the solutions and do this by exploiting algebraic techniques of the algorithm design.>

A Threshold Circuit consists of an acyclic digraph of unbounded fanin, where each node computes a threshold function or its negation. This paper investigates the computational power of Threshold Circuits. A surprising relationship is uncovered between Threshold Circuits and another class of unbounded fanin circuits which are denoted Finite Field $Z_{P(n)} $ Circuits, where each node computes either multiple sums or products of integers modulo a prime $P(n)$. In particular, it is proved that all functions computed by Threshold Circuits of size $S(n) \geq n$ and depth $D(n)$ can also be computed by $Z_{P(n)} $ Circuits of size $O(S(n)\log S(n) + nP(n)\log P(n))$ and depth $O(D(n))$. Furthermore, it is shown that all functions computed by $Z_{P(n)} $ Circuits of size $S(n)$ and depth $D(n)$ can be computed by Threshold Circuits of size $O((1/\epsilon ^2 )(S(n)\log P(n))^{1 + \epsilon } )$ and depth $O((1/\epsilon ^5 )D(n))$. These are the main results of this paper. There are many useful and quite surprising consequences of this result. For example, an integer reciprocal can be computed in size $n^{O(1)} $ and depth $O(1)$. More generally, any analytic function with a convergent rational polynomial power series (such as sine, cosine, exponentiation, square root, and logarithm) can be computed within accuracy $2^{ - n^c } $, for any constant c, by Threshold Circuits of polynomial size and constant depth. In addition, integer and polynomial FFT, polynomial interpolation, Chinese Remaindering, all the elementary symmetric functions, banded matrix inverse, and triangular Toeplitz matrix inverse can be exactly computed by Threshold Circuits of polynomial size and constant depth. All these results and simulations hold for polytime uniform circuits. This paper also gives a corresponding simulation of logspace uniform $Z_{P(n)} $ Circuits by logspace uniform Threshold Circuits requiring an additional multiplying factor of $O(\log \log \log P(n))$ depth. Finally, purely algebraic methods for lower bounds for $Z_{P(n)} $ Circuits are developed. Using degree arguments, a Depth Hierarchy Theorem for $Z_{P(n)} $ Circuits is proved: for any $S(n) \geq n$, $D(n) = O(S(n)^{c'} )$ for some constant $c' < 1$, and prime $P(n)$ where $6(S(n)/D(n)^{D(n)} < P(n) \leq 2^n $, there exist explicitly constructible functions computable by $Z_{P(n)} $ Circuits of size $S(n)$ and depth $D(n)$, but provably not computable by $Z_{P(n)} $ Circuits of size $S(n)^c $ and depth $o(D(n))$ for any constant $c \geq 1$.

Division is a fundamental problem for arithmetic and algebraic computation. This paper describes Boolean circuits (of bounded fan-in) for integer division (finding reciprocals) that have size $O(M(n))$ and depth $O(\log n \log \log n)$, where $M(n)$ is the size complexity of $O(\log n)$ depth integer multiplication circuits. Currently, $M(n)$ is known to be $O(\log n \log \log n)$, but any improvement in this bound that preserves circuit depth will be reflected by a similar improvement in the size complexity of our division algorithm. Previously, no one has been able to derive a division circuit with size $O(n \log^c n)$ for any c, and simultaneous depth less than $\Omega (\log^2 n)$. The circuit families described in this paper are logspace uniform; that is, they can be constructed by a deterministic Turing machine in space $O(\log n)$. The results match the best-known depth bounds for logspace uniform circuits, and are optimal in size. The general method of high-order iterative formulas is of independent interest as a way of efficiently using parallel processors to solve algebraic problems. In particular, this algorithm implies that any rational function can be evaluated in these complexity bounds. As an introduction to high-order iterative methods a circuit is first presented for finding polynomial reciprocals (where the coefficients come from an arbitrary ring, and ring operations are unit cost in the circuit) in size $O(PM(n))$ and depth $O(\log n \log \log n)$, where $PM(n)$ is the size complexity of optimal depth polynomial multiplication.

Division is a fundamental problem for arithmetic and algebraic computation. This paper describes Boolean circuits (of bounded fan-in) for integer division (finding reciprocals) that have size Ο(M(n)) and depth Ο(lognlog logn), where M(n) is the size complexity of Ο(logn) depth integer multiplication circuits. Currently, M(n) is known to be Ο(nlogn log,n), but any improvement in this bound that preserves circuit depth will be reflected by a similar improvement in the size complexity of our division algorithm. Previously, no one has been able to derive a division circuit with size Ο(n logc n) for any c, and simultaneous depth less than Ω(log2 n). Our circuits are logspace uniform; that is, they can be constructed by a deterministic Turing machine in space Ο(log n).