Microsoft Research

Displaying 1-40 of 77 results

  • White Papers // Jan 2014

    Using Formal Specifications to Monitor and Guide Simulation: Verifying the Cache Coherence Engine of the Alpha 21364 Microprocessor

    For hardware implementing a complex protocol, verification of consistency with high-level specifications is a very labor intensive process that is never entirely completed in practice. Simulation using random patterns or hand-written test programs is the only tool available for this purpose. Typically, the design is described in a hardware description...

    Provided By Microsoft Research

  • White Papers // Nov 2013

    ViceROI: Catching Click-Spam in Search Ad Networks

    Click-spam in online advertising, where unethical publishers use malware or trick users into clicking ads, siphons off hundreds of millions of advertiser dollars meant to support free websites and apps. Ad networks today, sadly, rely primarily on security through obscurity to defend against click-spam. In this paper, the authors present...

    Provided By Microsoft Research

  • White Papers // Oct 2013

    Elliptic and Hyperelliptic Curves: A Practical Security Analysis

    This is motivated by the advantages of using elliptic curves for discrete logarithm-based public-key cryptography, there is an active research area investigating the potential of using hyper-elliptic curves of genus 2. For both types of curves, the best known algorithms to solve the discrete logarithm problem are generic attacks such...

    Provided By Microsoft Research

  • White Papers // Jul 2013

    Exponentiating in Pairing Groups

    At the turn of the century it was shown that elliptic curves can be used to build powerful cryptographic primitives: bilinear pairings. Pairings are used in a large variety of protocols, and even when considering the recent breakthrough paper which shows how to instantiate multi-linear maps using ideal lattices, pairings...

    Provided By Microsoft Research

  • White Papers // Jun 2013

    Publicly Verifiable Grouped Aggregation Queries on Outsourced Data Streams

    Outsourcing data streams and desired computations to a third party such as the cloud is a desirable option to many companies. However, data outsourcing and remote computations intrinsically raise issues of trust, making it crucial to verify results returned by third parties. In this paper, the authors propose a novel...

    Provided By Microsoft Research

  • White Papers // May 2013

    Combining Active Sampling with Parameter Estimation and Prediction in Single Networks

    A typical assumption in network classification methods is that the full network is available to both learn the model and apply the model for prediction. Often this assumption is appropriate (publicly visible friendship links in social networks), however in other domains, while the underlying relational structure exists, there may be...

    Provided By Microsoft Research

  • White Papers // Dec 2012

    On the Impossibility of Sender-Deniable Public Key Encryption

    Recently, several open questions regarding the feasibility of deniable encryption have been resolved. A fundamental remaining open question is, whether it is possible to construct sender-deniable Encryption Schemes with super-polynomial security, where an adversary has negligible advantage in distinguishing real and fake openings. The primitive of simulatable Public Key Encryption...

    Provided By Microsoft Research

  • White Papers // Dec 2012

    ML Confidential: Machine Learning on Encrypted Data

    The authors demonstrate that, by using a recently proposed leveled homomorphic encryption scheme, it is possible to delegate the execution of a machine learning algorithm to a computing service while retaining confidentiality of the training and test data. Since the computational complexity of the homomorphic encryption scheme depends primarily on...

    Provided By Microsoft Research

  • White Papers // Dec 2012

    On The (In)Security of Fischlin's Paradigm

    The Fiat-Shamir paradigm was proposed as a way to remove interaction from 3-round proof of knowledge protocols and derive secure signature schemes. This generic transformation leads to very efficient schemes and has thus grown quite popular. However, this transformation is proven secure only in the random oracle model. In FOCS...

    Provided By Microsoft Research

  • White Papers // Dec 2012

    Non Observability in the Random Oracle Model

    The Random Oracle Model, introduced by Bellare and Rogaway, provides a method to heuristically argue about the security of cryptographic primitives and protocols. The basis of this heuristic is that secure hash functions are close enough to random functions in their behavior, and so, a primitive that is secure using...

    Provided By Microsoft Research

  • White Papers // Dec 2012

    Two is Greater than One

    Since its invention in the 1980's, elliptic curve cryptography has become a popular and standardized approach to instantiate public-key cryptography. In this paper, the authors highlight the benefits of using genus-2 curves in public-key cryptography. Compared to the standardized genus-1 curves, or elliptic curves, arithmetic on genus-2 curves is typically...

    Provided By Microsoft Research

  • White Papers // Sep 2012

    Pasture: Secure Offline Data Access Using Commodity Trusted Hardware

    This paper presents Pasture, a secure messaging and logging library that enables rich mobile experiences by providing secure offline data access. Without trusting users, applications, operating systems, or hypervisors, Pasture leverages commodity trusted hardware to provide two important safety properties: access-undeniability (a user cannot deny any offline data access obtained...

    Provided By Microsoft Research

  • White Papers // Sep 2012

    Salus: A System for Server-Aided Secure Function Evaluation

    Secure Function Evaluation (SFE) allows a set of mutually distrustful parties to evaluate a function of their joint inputs without revealing their inputs to each other. SFE has been the focus of active research and recent work suggests that it can be made practical. Unfortunately, current protocols and implementations have...

    Provided By Microsoft Research

  • White Papers // Sep 2012

    Dynamic Searchable Symmetric Encryption

    Searchable Symmetric Encryption (SSE) allows a client to encrypt its data in such a way that this data can still be searched. The most immediate application of SSE is to cloud storage, where it enables a client to securely outsource its data to an untrusted cloud provider without sacrificing the...

    Provided By Microsoft Research

  • White Papers // Sep 2012

    Succinct Malleable NIZKs and an Application to Compact Shuffles

    Depending on the application, malleability in cryptography can be viewed as either a flaw or - especially if sufficiently understood and restricted - a feature. In this vein, Chase, Kohlweiss, Lysyan-skaya, and Meiklejohn recently defined malleable zero-knowledge proofs, and showed how to control the set of allowable transformations on proofs....

    Provided By Microsoft Research

  • White Papers // Sep 2012

    Concurrent Zero Knowledge in the Bounded Player Model

    In this paper, the authors put forward the Bounded Player Model for secure computation. In this new model, the number of players that will ever be involved in secure computations is bounded, but the number of computations has no a priori bound. Indeed, while the number of devices and people...

    Provided By Microsoft Research

  • White Papers // Aug 2012

    Privacy Amplification with Asymptotically Optimal Entropy Loss

    The authors study the problem of "Privacy amplification": key agreement between two parties who both know a weak secret w, such as a password. (Such a setting is ubiquitous on the internet, where passwords are the most commonly used security device.). They assume that the key agreement protocol is taking...

    Provided By Microsoft Research

  • White Papers // Aug 2012

    Improved CRT Algorithm for Class Polynomials in Genus 2

    The authors present a generalization to genus 2 of the probabilistic algorithm in Sutherland for computing Hilbert class polynomials. The improvement over the algorithm presented for the genus 2 case, is that they do not need to find a curve in the isogeny class with endomorphism ring which is the...

    Provided By Microsoft Research

  • White Papers // Jun 2012

    Securing Circuits Against Constant-Rate Tampering

    The authors present a compiler that converts any circuit into one that remains secure even if a constant fraction of its wires are tampered with. Following the seminal work of Ishai et al. (Eurocrypt 2006), they consider adversaries who may choose an arbitrary set of wires to corrupt, and may...

    Provided By Microsoft Research

  • White Papers // Jun 2012

    Achieving Constant Round Leakage-Resilient Zero-Knowledge

    The concept of zero-knowledge interactive proofs, originating in the seminal work of Goldwasser, Micali, and Rackoff, is a fundamental concept in theoretical cryptography. Recently there has been a huge emphasis on constructing cryptographic protocols that maintain their security guarantees even in the presence of side channel attacks. Such attacks exploit...

    Provided By Microsoft Research

  • White Papers // May 2012

    RAMCube: Exploiting Network Proximity for RAM-Based Key-Value Store

    Disk-based storage is becoming increasingly problematic in meeting the needs of large-scale cloud applications. Recently RAM-based storage is proposed by aggregating the RAM of thousands of commodity servers in Data Center Networks (DCN). These studies focus on improving performance with low latency RPC and fast failure recovery. RAM-based storage brings...

    Provided By Microsoft Research

  • White Papers // May 2012

    Gecko: A Contention-Oblivious Design for Cloud Storage

    Disk contention is a fact of life in modern data centers, with multiple applications sharing the storage resources of a single physical machine. Log-structured storage designs are ideally suited for such high-contention settings, but historically have suffered from performance problems due to cleaning overheads. In this paper, the authors introduce...

    Provided By Microsoft Research

  • White Papers // Apr 2012

    Almost-Everywhere Secure Computation with Edge Corruptions

    The authors consider secure Multi-Party Computation (MPC) in a setting where the adversary can separately corrupt not only the parties (nodes) but also the communication channels (edges), and can furthermore choose selectively and adaptively which edges or nodes to corrupt. Note that if an adversary corrupts an edge, even if...

    Provided By Microsoft Research

  • White Papers // Mar 2012

    RecStore: An Extensible and Adaptive Framework for Online Recommender Queries inside the Database Engine

    Most recommendation methods (e.g., collaborative filtering) consist of a computationally intense offline phase that computes a recommender model based on users' opinions of items, and an online phase consisting of SQL-based queries that use the model (generated offline) to derive user preferences and provide recommendations for interesting items. Current application...

    Provided By Microsoft Research

  • White Papers // Mar 2012

    Bicliques for Permutations: Collision and Preimage Attacks in Stronger Settings

    The authors extend and improve biclique attacks, which were recently introduced for the cryptanalysis of block ciphers and hash functions. While previous attacks required a primitive to have a key or a message schedule, they show how to mount attacks on permutations with fixed or no parameters. To link the...

    Provided By Microsoft Research

  • White Papers // Jan 2012

    An Overview of Data Warehousing and OLAP Technology

    Data warehousing and On-Line Analytical Processing (OLAP) are essential elements of decision support, which has increasingly become a focus of the database industry. Many commercial products and services are now available, and all of the principal database management system vendors now have offerings in these areas. Decision support places some...

    Provided By Microsoft Research

  • White Papers // Nov 2011

    Near-Linear Unconditionally-Secure Multiparty Computation With a Dishonest Minority

    Secure MultiParty Computation (MPC) allows a set of n players to compute any public function, given as an arithmetic circuit, on private inputs, so that privacy of the inputs as well as correctness of the output are guaranteed. Of special importance both in cryptography and in complexity theory is the...

    Provided By Microsoft Research

  • White Papers // Jul 2011

    Latent Fault Detection in Cloud Services

    Large scale internet cloud services comprising of thou-sands of computers are ubiquitous. With so many machines, it is not reasonable to assume that all of them are working properly and are well configured. If faults are left unnoticed they might accumulate to the point where redundancy and fail-over mechanisms break....

    Provided By Microsoft Research

  • White Papers // Jun 2011

    A Domain Transformation for Structure-Preserving Signatures on Group Elements

    The authors present a generic transformation that allows one to use a large class of pairing-based signatures to construct schemes for signing group elements in a structure preserving way. As a result of the transformation they obtain a new efficient signature scheme for signing a vector of group elements that...

    Provided By Microsoft Research

  • White Papers // Jun 2011

    Collusion-Resistant Obfuscation and Functional Re-Encryption

    Program obfuscation is the problem of transforming a program into one which is functionally equivalent, yet whose inner workings are completely unintelligible to an adversary. Despite its immense cryptographic utility, program obfuscation has proved to be a hard and elusive goal, as evidenced by the wide-ranging impossibility results, starting with...

    Provided By Microsoft Research

  • White Papers // Jun 2011

    ZOZZLE: Fast and Precise In-Browser JavaScript Malware Detection

    JavaScript malware-based attacks account for a large fraction of successful mass-scale exploitation happening today. Attackers like JavaScript-based attacks because they can be mounted against an unsuspecting user visiting a seemingly innocent web page. While several techniques for addressing these types of exploits have been proposed, in-browser adoption has been slow,...

    Provided By Microsoft Research

  • White Papers // May 2011

    The Data Furnace: Heating Up With Cloud Computing

    In this paper, the authors argue that servers can be sent to homes and office buildings and used as a primary heat source. They call this approach the Data Furnace or DF. Data Furances have three advantages over traditional data centers: a smaller carbon footprint, reduced total cost of ownership...

    Provided By Microsoft Research

  • White Papers // May 2011

    Affine Pairings on ARM

    Pairings on elliptic curves are being used in an increasing number of cryptographic applications on many different devices and platforms, but few performance numbers for cryptographic pairings have been reported on embedded and mobile devices. In this paper, the authors give performance numbers for affine and projective pairings on a...

    Provided By Microsoft Research

  • White Papers // May 2011

    Towards Enforceable Data-Driven Privacy Policies

    A defining characteristic of current web applications is that they are personalized according to the interests and preferences of individual users; popular examples are Google News and Amazon.com. While this paradigm shift is generally viewed as positive by both users and content providers, it introduces privacy concerns, as the data...

    Provided By Microsoft Research

  • White Papers // Apr 2011

    Context-Based Online Configuration-Error Detection

    Software failures due to configuration errors are commonplace as computer systems continue to grow larger and more complex. Troubleshooting these configuration errors is a major administration cost, especially in server clusters where problems often go undetected without user interference. This paper presents CODE - a tool that automatically detects software...

    Provided By Microsoft Research

  • White Papers // Apr 2011

    Optimizing Data Partitioning for Data-Parallel Computing

    Performance of data-parallel computing (e.g., MapReduce, DryadLINQ) heavily depends on its data partitions. Solutions implemented by the current state of the art systems are far from optimal. Techniques proposed by the database community to find optimal data partitions are not directly applicable when complex user-defined functions and data models are...

    Provided By Microsoft Research

  • White Papers // Apr 2011

    Differentially Private Billing with Rebates

    A number of established and novel business models are based on fine grained billing, including pay-per-view, mobile messaging, voice calls, pay-as-you-drive insurance, smart metering for utility provision, private computing clouds and hosted services. These models apply fine-grained tariffs dependent on time-of-use or place of-use to readings to compute a bill....

    Provided By Microsoft Research

  • White Papers // Mar 2011

    Collaborative Personalization of Image Enhancement

    While most existing enhancement tools for photographs have universal auto-enhancement functionality, recent research shows that users can have personalized preferences. In this paper, the authors explore whether such personalized preferences in image enhancement tend to cluster and whether users can be grouped according to such preferences. To this end, they...

    Provided By Microsoft Research

  • White Papers // Mar 2011

    Real-Time Human Pose Recognition in Parts From Single Depth Images

    The authors propose a new method to quickly and accurately predict 3D positions of body joints from a single depth image, using no temporal information. They take an object recognition approach, designing an intermediate body parts representation that maps the difficult pose estimation problem into a simpler per-pixel classification problem....

    Provided By Microsoft Research

  • White Papers // Mar 2011

    SenseLess: A Database-Driven White Spaces Network

    The most recent FCC ruling proposes relying on a database of incumbents as the primary means of determining white space availability at any White Spaces Device (WSD). While the ruling provides broad guidelines for the database, the specifics of its design, features, implementation, and use are yet to be determined....

    Provided By Microsoft Research

  • White Papers // Sep 2012

    Pasture: Secure Offline Data Access Using Commodity Trusted Hardware

    This paper presents Pasture, a secure messaging and logging library that enables rich mobile experiences by providing secure offline data access. Without trusting users, applications, operating systems, or hypervisors, Pasture leverages commodity trusted hardware to provide two important safety properties: access-undeniability (a user cannot deny any offline data access obtained...

    Provided By Microsoft Research

  • White Papers // Dec 2012

    On the Impossibility of Sender-Deniable Public Key Encryption

    Recently, several open questions regarding the feasibility of deniable encryption have been resolved. A fundamental remaining open question is, whether it is possible to construct sender-deniable Encryption Schemes with super-polynomial security, where an adversary has negligible advantage in distinguishing real and fake openings. The primitive of simulatable Public Key Encryption...

    Provided By Microsoft Research

  • White Papers // Dec 2012

    On The (In)Security of Fischlin's Paradigm

    The Fiat-Shamir paradigm was proposed as a way to remove interaction from 3-round proof of knowledge protocols and derive secure signature schemes. This generic transformation leads to very efficient schemes and has thus grown quite popular. However, this transformation is proven secure only in the random oracle model. In FOCS...

    Provided By Microsoft Research

  • White Papers // Dec 2012

    Non Observability in the Random Oracle Model

    The Random Oracle Model, introduced by Bellare and Rogaway, provides a method to heuristically argue about the security of cryptographic primitives and protocols. The basis of this heuristic is that secure hash functions are close enough to random functions in their behavior, and so, a primitive that is secure using...

    Provided By Microsoft Research

  • White Papers // Dec 2012

    Two is Greater than One

    Since its invention in the 1980's, elliptic curve cryptography has become a popular and standardized approach to instantiate public-key cryptography. In this paper, the authors highlight the benefits of using genus-2 curves in public-key cryptography. Compared to the standardized genus-1 curves, or elliptic curves, arithmetic on genus-2 curves is typically...

    Provided By Microsoft Research

  • White Papers // Sep 2012

    Salus: A System for Server-Aided Secure Function Evaluation

    Secure Function Evaluation (SFE) allows a set of mutually distrustful parties to evaluate a function of their joint inputs without revealing their inputs to each other. SFE has been the focus of active research and recent work suggests that it can be made practical. Unfortunately, current protocols and implementations have...

    Provided By Microsoft Research

  • White Papers // Sep 2012

    Dynamic Searchable Symmetric Encryption

    Searchable Symmetric Encryption (SSE) allows a client to encrypt its data in such a way that this data can still be searched. The most immediate application of SSE is to cloud storage, where it enables a client to securely outsource its data to an untrusted cloud provider without sacrificing the...

    Provided By Microsoft Research

  • White Papers // Sep 2012

    Succinct Malleable NIZKs and an Application to Compact Shuffles

    Depending on the application, malleability in cryptography can be viewed as either a flaw or - especially if sufficiently understood and restricted - a feature. In this vein, Chase, Kohlweiss, Lysyan-skaya, and Meiklejohn recently defined malleable zero-knowledge proofs, and showed how to control the set of allowable transformations on proofs....

    Provided By Microsoft Research

  • White Papers // Aug 2012

    Privacy Amplification with Asymptotically Optimal Entropy Loss

    The authors study the problem of "Privacy amplification": key agreement between two parties who both know a weak secret w, such as a password. (Such a setting is ubiquitous on the internet, where passwords are the most commonly used security device.). They assume that the key agreement protocol is taking...

    Provided By Microsoft Research

  • White Papers // Aug 2012

    Improved CRT Algorithm for Class Polynomials in Genus 2

    The authors present a generalization to genus 2 of the probabilistic algorithm in Sutherland for computing Hilbert class polynomials. The improvement over the algorithm presented for the genus 2 case, is that they do not need to find a curve in the isogeny class with endomorphism ring which is the...

    Provided By Microsoft Research

  • White Papers // Jun 2012

    Securing Circuits Against Constant-Rate Tampering

    The authors present a compiler that converts any circuit into one that remains secure even if a constant fraction of its wires are tampered with. Following the seminal work of Ishai et al. (Eurocrypt 2006), they consider adversaries who may choose an arbitrary set of wires to corrupt, and may...

    Provided By Microsoft Research

  • White Papers // Jun 2012

    Achieving Constant Round Leakage-Resilient Zero-Knowledge

    The concept of zero-knowledge interactive proofs, originating in the seminal work of Goldwasser, Micali, and Rackoff, is a fundamental concept in theoretical cryptography. Recently there has been a huge emphasis on constructing cryptographic protocols that maintain their security guarantees even in the presence of side channel attacks. Such attacks exploit...

    Provided By Microsoft Research

  • White Papers // Dec 2012

    ML Confidential: Machine Learning on Encrypted Data

    The authors demonstrate that, by using a recently proposed leveled homomorphic encryption scheme, it is possible to delegate the execution of a machine learning algorithm to a computing service while retaining confidentiality of the training and test data. Since the computational complexity of the homomorphic encryption scheme depends primarily on...

    Provided By Microsoft Research

  • White Papers // Sep 2012

    Concurrent Zero Knowledge in the Bounded Player Model

    In this paper, the authors put forward the Bounded Player Model for secure computation. In this new model, the number of players that will ever be involved in secure computations is bounded, but the number of computations has no a priori bound. Indeed, while the number of devices and people...

    Provided By Microsoft Research

  • White Papers // Apr 2012

    Almost-Everywhere Secure Computation with Edge Corruptions

    The authors consider secure Multi-Party Computation (MPC) in a setting where the adversary can separately corrupt not only the parties (nodes) but also the communication channels (edges), and can furthermore choose selectively and adaptively which edges or nodes to corrupt. Note that if an adversary corrupts an edge, even if...

    Provided By Microsoft Research

  • White Papers // Oct 2009

    Analyzing the Aggregate Download Bandwidths in Peer-to-Peer Live Streaming Systems

    In a Peer-To-Peer (P2P) live streaming system, the streaming quality of an end user is much affected by the aggregate download bandwidth from the partners. In this paper, the authors propose a stochastic model for the P2P streaming system to analyze the asymptotic probability distribution of the aggregate download bandwidth...

    Provided By Microsoft Research

  • White Papers // Mar 2012

    RecStore: An Extensible and Adaptive Framework for Online Recommender Queries inside the Database Engine

    Most recommendation methods (e.g., collaborative filtering) consist of a computationally intense offline phase that computes a recommender model based on users' opinions of items, and an online phase consisting of SQL-based queries that use the model (generated offline) to derive user preferences and provide recommendations for interesting items. Current application...

    Provided By Microsoft Research

  • White Papers // Aug 2009

    Toward Practical Opportunistic Routing with Intra-Session Network Coding for Mesh Networks

    The authors consider opportunistic routing in wireless mesh networks. They exploit the inherent diversity of the broadcast nature of wireless by making use of multi-path routing. They present a novel optimization framework for opportunistic routing based on Network Utility Maximization (NUM) that enables them to derive optimal flow control, routing,...

    Provided By Microsoft Research

  • White Papers // Mar 2011

    SenseLess: A Database-Driven White Spaces Network

    The most recent FCC ruling proposes relying on a database of incumbents as the primary means of determining white space availability at any White Spaces Device (WSD). While the ruling provides broad guidelines for the database, the specifics of its design, features, implementation, and use are yet to be determined....

    Provided By Microsoft Research

  • White Papers // Jul 2011

    Latent Fault Detection in Cloud Services

    Large scale internet cloud services comprising of thou-sands of computers are ubiquitous. With so many machines, it is not reasonable to assume that all of them are working properly and are well configured. If faults are left unnoticed they might accumulate to the point where redundancy and fail-over mechanisms break....

    Provided By Microsoft Research

  • White Papers // Apr 2009

    Secure-TWS: Authenticating Node to Multi-User Communication in Shared Sensor Networks

    Recent works have shown the usefulness of network and application layer protocols that connect low power sensor nodes directly to multiple applications and users on the Internet. The authors propose a security solution for this scenario. While previous works have provided security support for various communication patterns in sensor networks,...

    Provided By Microsoft Research

  • White Papers // Oct 2009

    Rethinking Indoor Wireless: Low Power, Low Frequency, Full-Duplex

    One of the largest market segments for wireless are indoor wireless networks (e.g. home networks and enterprise networks). In such networks connectivity is limited both by physical obstacles and structural barriers such as walls, and by interference in the wireless spectrum. The most commonly used ISM bands for WiFi networks...

    Provided By Microsoft Research

  • White Papers // Mar 2009

    Efficiency and Fairness in Distributed Wireless Networks Through Self-Interference Cancellation and Scheduling

    Handling interference is one of the major challenges in the design of multi-user distributed wireless systems. In current systems, interference is managed through carrier sensing mechanisms such as CSMA/CA and through MAC algorithms based on random back-off. However, the asymmetry in channel sensing inevitably causes degraded throughput and fairness issues,...

    Provided By Microsoft Research

  • White Papers // Dec 2008

    Towards Unified Management of Networked Services in Wired and Wireless Enterprise Networks

    Organizations world-wide are adopting wireless networks at an impressive rate, and a new industry has sprung up to provide tools to manage these networks. Unfortunately, these tools do not integrate cleanly with traditional wired network management tools, leading to unsolved problems and frustration among the IT staff. The authors explore...

    Provided By Microsoft Research

  • White Papers // Sep 2009

    DirCast: A Practical and Efficient Wi-Fi Multicast System

    IP multicast applications such as live lecture broadcasts are being increasingly used in enterprise and campus networks. In many cases, end hosts access these multicast streams using Wi-Fi networks. However, multicast over Wi-Fi suffers from several well-known problems such as low data rate, high losses and unfairness vis-a-vis other contending...

    Provided By Microsoft Research

  • White Papers // Oct 2008

    Everest: Scaling Down Peak Loads Through I/O Off-Loading

    Bursts in data center workloads are a real problem for storage subsystems. Data volumes can experience peak I/O request rates that are over an order of magnitude higher than average load. This requires significant over provisioning, and often still results in significant I/O request latency during peaks. In order to...

    Provided By Microsoft Research

  • White Papers // Jan 2012

    An Overview of Data Warehousing and OLAP Technology

    Data warehousing and On-Line Analytical Processing (OLAP) are essential elements of decision support, which has increasingly become a focus of the database industry. Many commercial products and services are now available, and all of the principal database management system vendors now have offerings in these areas. Decision support places some...

    Provided By Microsoft Research

  • White Papers // May 2011

    Towards Enforceable Data-Driven Privacy Policies

    A defining characteristic of current web applications is that they are personalized according to the interests and preferences of individual users; popular examples are Google News and Amazon.com. While this paradigm shift is generally viewed as positive by both users and content providers, it introduces privacy concerns, as the data...

    Provided By Microsoft Research

  • White Papers // May 2010

    What You See Is What They Get Protecting Users From Unwanted Use of Microphones, Cameras, and Other Sensors

    Sensors such as cameras and microphones collect privacy-sensitive data streams without the user's explicit action. Conventional sensor access policies either hassle users to grant applications access to sensors or grant with no approval at all. Once access is granted, an application may collect sensor data even after the application's interface...

    Provided By Microsoft Research

  • White Papers // Nov 2011

    Near-Linear Unconditionally-Secure Multiparty Computation With a Dishonest Minority

    Secure MultiParty Computation (MPC) allows a set of n players to compute any public function, given as an arithmetic circuit, on private inputs, so that privacy of the inputs as well as correctness of the output are guaranteed. Of special importance both in cryptography and in complexity theory is the...

    Provided By Microsoft Research

  • White Papers // Mar 2012

    Bicliques for Permutations: Collision and Preimage Attacks in Stronger Settings

    The authors extend and improve biclique attacks, which were recently introduced for the cryptanalysis of block ciphers and hash functions. While previous attacks required a primitive to have a key or a message schedule, they show how to mount attacks on permutations with fixed or no parameters. To link the...

    Provided By Microsoft Research

  • White Papers // Apr 2011

    Context-Based Online Configuration-Error Detection

    Software failures due to configuration errors are commonplace as computer systems continue to grow larger and more complex. Troubleshooting these configuration errors is a major administration cost, especially in server clusters where problems often go undetected without user interference. This paper presents CODE - a tool that automatically detects software...

    Provided By Microsoft Research

  • White Papers // Apr 2011

    Optimizing Data Partitioning for Data-Parallel Computing

    Performance of data-parallel computing (e.g., MapReduce, DryadLINQ) heavily depends on its data partitions. Solutions implemented by the current state of the art systems are far from optimal. Techniques proposed by the database community to find optimal data partitions are not directly applicable when complex user-defined functions and data models are...

    Provided By Microsoft Research

  • White Papers // Jun 2010

    A Parameterizable Processor Architecture for Large Characteristic Pairing-Based Cryptography

    Cryptographic pairing (bilinear mapping) is a core algorithm for various cryptography protocols. It is computationally expensive and inefficiently computed with general purpose processors. Although, there has been previous work looking into efficient hardware designs for pairing, most of these systems use small characteristic curves which are incompatible with practical software...

    Provided By Microsoft Research

  • White Papers // May 2012

    Gecko: A Contention-Oblivious Design for Cloud Storage

    Disk contention is a fact of life in modern data centers, with multiple applications sharing the storage resources of a single physical machine. Log-structured storage designs are ideally suited for such high-contention settings, but historically have suffered from performance problems due to cleaning overheads. In this paper, the authors introduce...

    Provided By Microsoft Research

  • White Papers // May 2012

    RAMCube: Exploiting Network Proximity for RAM-Based Key-Value Store

    Disk-based storage is becoming increasingly problematic in meeting the needs of large-scale cloud applications. Recently RAM-based storage is proposed by aggregating the RAM of thousands of commodity servers in Data Center Networks (DCN). These studies focus on improving performance with low latency RPC and fast failure recovery. RAM-based storage brings...

    Provided By Microsoft Research

  • White Papers // Jan 2011

    Measure Transformer Semantics for Bayesian Machine Learning

    The Bayesian approach to machine learning amounts to inferring posterior distributions of random variables from a probabilistic model of how the variables are related (that is, a prior distribution) and a set of observations of variables. There is a trend in machine learning towards expressing Bayesian models as probabilistic programs....

    Provided By Microsoft Research

  • White Papers // Feb 2011

    Guiding a General-Purpose C Verifier to Prove Cryptographic Protocols

    The authors describe, for the first time, how to verify security properties of C code for cryptographic protocols by using a general-purpose verifier. The authors prove security theorems in the symbolic model of cryptography. The techniques include: use of ghost state to attach formal algebraic terms to concrete byte arrays...

    Provided By Microsoft Research

  • White Papers // Feb 2011

    Extracting and Verifying Cryptographic Models From C Protocol Code by Symbolic Execution

    Consider the problem of verifying security properties of a cryptographic protocol coded in C. The authors propose an automatic solution that needs neither a pre-existing protocol description nor manual inspection of source code. First, symbolically execute the C program to obtain symbolic expressions for the network message sent by the...

    Provided By Microsoft Research

  • White Papers // Apr 2011

    Differentially Private Billing with Rebates

    A number of established and novel business models are based on fine grained billing, including pay-per-view, mobile messaging, voice calls, pay-as-you-drive insurance, smart metering for utility provision, private computing clouds and hosted services. These models apply fine-grained tariffs dependent on time-of-use or place of-use to readings to compute a bill....

    Provided By Microsoft Research