Universität Paderborn » SFB 901 » Projects » Project Area C » C1 » Abstract

Subproject C1

Robustness and Security


The project deals with the On-the-Fly scenario’s robustness and security. This includes methods for synchronization, behavior control and data management in dynamic networks. Dynamically changing cooperations also require suitable cryptographic methods - especially for authentication and for ensuring confidentiality, but also including access control -, which we will develop based on identity-based cryptography. Besides these security objectives, we also want to achieve data privacy and legal certainty for participants - leading to both technical and legal challenges.

Robust Distributed Systems

To guarantee a high availability in the OTF market, scalable and robust methods for synchronization, behavior management and data management have to be studied.


A central problem in the field of distributed systems is the distributed consensus. In a consensus problem, the set of all processes is required to agree on a common value, out of one of the values initially held by one of the processes. If all processes are fault-tolerant and work without delays, the consensus problem can easily be solved by using a leader selection protocol. In the case of presence of faulty processes, the consensus problem becomes much harder. The problem of distributed consensus has extensively been studied in the last decades. The known protocols are usually developed with the goal of maximizing the number of allowed adversaries (faulty processors). Such protocols often lead to a running time which is not acceptable for highly scalable systems. For instance, it is known that previously considered protocols for distributed consensus require on average a linear amount of time for every process, if the maximum number of possible faulty processes is allowed. Furthermore, previously presented protocols for distributed consensus usually are not self-stabilizing. Our goal is to determine up to which number of faulty processes an efficient protocol (a protocol with a maximum of polylogarithmic cost for each participant) is possible. Additionally, we aim to develop self-stabilizing protocols for the problem of distributed transactions, which are supposed to work correctly despite the presence of adversaries. In [1] we already presented a simple randomized algorithm that, with high probability, just needs O(log(m)loglog(n)+log(n)) time and work per process to arrive at an almost stable consensus for any set of m legal values as long as an adversary can corrupt the states of at most √n processes at any time. Without adversarial involvement, just O(logn) time and work is needed for a stable consensus, with high probability.

[1] B. Doerr, L. A. Goldberg, L. Minder, T. Sauerwald and C. Scheideler: "Stabilizing Consensus with the Power of Two Choices", in the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2011

Robust Data Management

In this subarea we examined the develoopment of distributed storage systems that are provably robust against DoS attacks by so called insiders. An insider is an adversary that knows everything about the system and has the ability to use this knowledge in order to block a huge fraction of the servers by a DoS attack.
Previous works only considered past insiders, i.e. adversaries that only have knowledge about the complete system up to a specific past point t in time.
In [1] and [2] Scheideler et al. presented a distributed storage system that is able to efficiently and correctly serve lookup and write requests that were inserted or updated after the time point t despite the existence of a past insider that blocked a huge fraction of the servers by a DoS attacks.

In the first funding period we developed a distributed information system, called IRIS, that can efficiently and correctly serve lookup requests despite a running DoS attack performed by a current insider [3].
To be more precise, IRIS is able to correctly serve any set of lookup requests (with at most a constant number of requests per non-blocked server) with only polylogarithmic time and work at every server although up to a constant fraction of the servers is under a DoS attack by a current insider. In order to guarantee this our system only requires a sublogarithmic redundancy.
Our system even works with only a constant redundancy, if we reduce the maximum number of blocked servers allowed to O(n^(1/loglogn)).
Based on IRIS we developed RoBuSt, a distributed storage system that provides the ability to serve lookup and write requests even while the system is under attack by an insider.
RoBuSt tolerates a current insider that blocks up to O(n^(1/loglogn)) servers by DoS attacks and can correctly answer any set of lookup and write requests (with at most a constant number of requests per non-blocked server) with only polylogarithmic time and work at every server.

An interesting further extension of IRIS and RoBuSt would be the handling of even stronger adversaries.
As an example one could consider a current insider that corrupts the storage of servers without the servers being aware of this. Even more challenging is the consideration of current insiders that choose a huge fraction of servers to be Byzantine.

[1] B. Awerbuch and C. Scheideler: "A denial-of-service resistant DHT", in 21st International Symposium on Distributed Computing (DISC), 2007
[2] M. Baumgart, C. Scheideler and S. Schmid: "A DoS-resilient information system for dynamic data management", in the 21st ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), 2009
[3] M. Eikel and C. Scheideler: "IRIS: A Robust Information System Against Insider DoS-Attacks", in Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2013
[4] M. Eikel, C. Scheideler and A. Setzer: "RoBuSt: A Crash-Failure-Resistant Distributed Storage System", in Proceedings of the 18th International Conference on Principles of Distributed Systems (OPODIS), 2014

Cryptographic Solutions in an On-The-Fly Computing System

Successful marketing and acceptance of On-The-Fly Computing systems require dealing with their security. The highly dynamic and heterogeneous nature of the visioned system as well as data protection and further legal requirements pose a challenge for modern cryptography and require novel cryptographic solutions.

During the course of the project we intend to design solutions for confidential and authenticated communication in dynamic groups based on identity-based cryptography. This requires key revocation and reduction of power of authority for identity-based schemes. Efficient allocation of services and data access control in On-The-Fly Computing systems also require novel cryptographic schemes, which we intend to realize based on the attribute-based encryption schemes.

Another important market mechanism in On-The-Fly Computing Systems is an anonymous reputation system which enables clients to rate products and services and gives incentives to providers to improve their services. Hence, in this part of the project we develop new models of security and schemes to build a highly flexible and secure reputation system.

Our Goals and Research Focus

One of our current goals is to develop secure, efficient and flexible access control systems for On-The-Fly Computing Data Centers and On-The-Fly service providers. A promising approach is to use attribute-based encryption schemes. These novel schemes use techniques from pairing-based cryptography and are related to identity-based cryptography too.

In the ciphertext-policy attribute-based encryption schemes, the owner of data defines an access policy for each data and encrypts it once using this policy. The policies for different data are Boolean formulas over predefined attributes. In order to provide access to the encrypted data, the owner of data gets each customer with a special decryption key. Every key is related to a set of attributes. A customer will be able to decrypt a ciphertext if and only if the attributes of his/her key satisfy the policy of the ciphertext.

In the following example, the manager of Map Data Center wants to ensure a fine-grained access control to the road maps for its customers (routing services). Therefore, restricting access to the full data base, to the maps of continents, and to the maps of each single country will be realized. Each map is encrypted once with an appropriate policy. For example, the map of Germany's roads is encrypted with the policy "World OR Europe OR Germany". Every customer who gets a key with one of the attributes "World", "Europe", or "Germany" will be able to decrypt the appropriate ciphertext and obtain access to Germany's road maps.

The attribute-based approach simplifies the realization of data access control systems, which then can be even stored on an untrusted server. The data access control is completely realized by the encryption and all the data must be encrypted only once for all the customers.

In this area, our research focus is on the development of efficient and flexible attribute-based encryption schemes. The policies of the existing schemes are restricted to several classes of functions and are quite inefficient. On the one hand, we are interested in the development of schemes which can be applied to general function classes. On the other hand, we are looking for more efficient methods when realizing restricted function classes. Other modifications of the schemes will be also necessary when considering further questions arising from privacy protection and further legal requirements.

A second goal is to develop anonymous reputation systems. To provide trustworthy, reliable, and honest ratings there is a need for anonymous reputation systems that also guarantee that customers rate products only once. To further increase trust in the system, everyone – even outsiders – should be able to verify the validity of ratings. Some of these properties have been studied in the context of group signatures. However, the concept of group signatures does not meet all the requirements for reputation systems. In particular, reputation systems do not consist of a single group of users. Rather one can think of reputation systems as a family of group signature schemes – one for each product. Moreover, we may have providers with several products. Hence, when looking at security and anonymity group signature schemes for different products can not be considered in isolation. Finally, known constructions of group signatures do not provide all properties that we need for a secure and anonymous reputation system and do not provide them simultaneously.

The research focus in the area of reputation systems is the development of new security models and efficient, flexible and secure schemes which meet all our requirements. Here we mainly consider group signatures, but also attribute-based signatures and anonymous credential systems will be taken into account.

Privacy-Preserving DRM for the OTF-Computing

Our Vision of Software Provision and Execution in the OTF-Computing

In our vision of the On-The-Fly Computing, the traditional way of software distribution and execution changes dramatically. Software will be provided by specialized software providers to users, and users will be able to freely choose the computing centers where the software should be executed, such as in computing centers with available resources and which provide their computing resources at a discount. Thus, the bonding between software provision and execution, which is predominant in many cloud computing services nowadays, becomes less important. Users may ask for new price models when buying or renting software from software providers. For example, licenses that allow the software to be executed for at most n times are imaginable. In order to enforce license checking in the OTF-Computing and restrict users to execute software in computing centers without having the proper rights available, a digital rights management (DRM) solution needs to be in place.

The introduction of a DRM system can involve some severe privacy challenges. If an online license check with the software provider is performed during each software execution by the computing center, the software provider is able to build software usage profiles of its users. A solution to this problem that takes only user anonymity into account, for example, by introducing an anonymous payment scheme to pay for the software, is not enough. Such a solution may be prone to profile building under pseudonym, meaning that the software provider does not know the identity of its users but it is able to relate individual software executions to each other - based on a pseudonym. In many cases, it may suffice to link some background information to such a usage profile under pseudonym to still reveal the user's identity.

Our Goals and Research Focus

Our goal is to develop a DRM system for the OTF-Computing that preserves the users' privacy. We are especially interested in the question of how licenses can be checked before each software execution, for example, to be able to provide an execution at most n times-like price models, but without relating the license check to a certain user, which means to protect the software provider from profile building - even under pseudonym. We even go a step further by requiring that a computing center must not be able to recognize a user that has executed a certain software before. This is a challenging task and an interesting research question, as this requirement rules out a composition of "standard" cryptographic primitives to build a DRM system.

Our Approach to Privacy Protection

We have already developed solutions for a privacy-preserving DRM scheme for the OTF-Computing based on secret sharing and homomorphic encryption, as well as on proxy re-encryption. See the publication page for more details. At the moment we are working on a solution based on trusted computing. We are investigating how attribute-based encryption schemes can be used in our scenarios as well.