Black-Box Accumulation: Collecting Incentives in a Privacy-Preserving Way - Jager, Tibor; Rupp, Andy (PoPETs)

How to Generate and Use Universal Samplers - Hofheinz, Dennis; Jager, Tibor; Khurana, Dakshita; Sahai, Amit; Waters, Brent; Zhandry, Mark (Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part II)

Breaking PPTP VPNs via RADIUS Encryption - Horst, Matthias; Grothe, Martin; Jager, Tibor; Schwenk, Jörg (Cryptology and Network Security - 15th International Conference, CANS 2016, Milan, Italy, November 14-16, 2016, Proceedings)

On the Impossibility of Tight Cryptographic Reductions - Bader, Christoph; Jager, Tibor; Li, Yong; Schäge, Sven (Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II)

Public-Key Encryption with Simulation-Based Selective-Opening Security and Compact Ciphertexts - Hofheinz, Dennis; Jager, Tibor; Rupp, Andy (Theory of Cryptography - 14th International Conference, TCC 2016-B, Beijing, China, October 31 - November 3, 2016, Proceedings, Part II)

Verifiable Random Functions from Standard Assumptions - Hofheinz, Dennis; Jager, Tibor (Theory of Cryptography - 13th International Conference, TCC 2016-A, Tel Aviv, Israel, January 10-13, 2016, Proceedings, Part I)

Verification of AUTOSAR Software Architectures with Timed Automata - Beringer, Steffen; Wehrheim, Heike (Critical Systems: Formal Methods and Automated Verification - Joint 21st International Workshop on Formal Methods for Industrial Critical Systems and 16th International Workshop on Automated Verification of Critical Systems, FMICS-AVoCS 2016, Pisa, Italy, September 26-28, 2016, Proceedings)

Verification of Concurrent Programs on Weak Memory Models - Travkin, Oleg; Wehrheim, Heike (Theoretical Aspects of Computing - ICTAC 2016 - 13th International Colloquium, Taipei, Taiwan, ROC, October 24-31, 2016, Proceedings)

Towards a Thread-Local Proof Technique for Starvation Freedom - Schellhorn, Gerhard; Travkin, Oleg; Wehrheim, Heike (Integrated Formal Methods - 12th International Conference, IFM 2016, Reykjavik, Iceland, June 1-5, 2016, Proceedings)

Proving Opacity of a Pessimistic STM - Doherty, Simon; Dongol, Brijesh; Derrick, John; Schellhorn, Gerhard; Wehrheim, Heike (20th International Conference on Principles of Distributed Systems, OPODIS 2016, December 13-16, 2016, Madrid, Spain)

Deriving approximation tolerance constraints from verification runs - Isenberg, Tobias; Jakobs, Marie{-}Christine; Pauck, Felix; Wehrheim, Heike (CoRR)

Congestion Games with Mixed Objectives - Leder, Lennart

Comparison of different Definitions of Chosen-Ciphertext Security in Encryption schemes - Porzenheim, Laurens

Commitment Schemes - Definitions, Variants, and Security - Bemmann, Kai Sören

Churn- and DoS-resistant Overlay Networks Based on Network Reconfiguration - Drees, Maximilian; Gmyr, Robert; Scheideler, Christian (Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA))
We present three robust overlay networks: First, we present a network that organizes the nodes into an expander and is resistant to even massive adversarial churn. Second, we develop a network based on the hypercube that maintains connectivity under adversarial DoS-attacks. For the DoS-attacks we use the notion of a Omega(log log n)-late adversary which only has access to topological information that is at least Omega(log log n) rounds old. Finally, we develop a network that combines both churn- and DoS-resistance. The networks gain their robustness through constant network reconfiguration, i.e., the topology of the networks changes constantly. Our reconguration algorithms are based on node sampling primitives for expanders and hypercubes that allow each node to sample a logarithmic number of nodes uniformly at random in O(log log n) communication rounds. These primitives are specific to overlay networks and their optimal runtime represents an exponential improvement over known techniques. Our results have a wide range of applications, for example in the area of scalable and robust peer-to-peer systems.

On-The-Fly Construction of Provably Correct Service Compositions - Templates and Proofs - Walther, Sven; Wehrheim, Heike (Science of Computer Programming)
Today, service compositions often need to be assembled or changed on-the-fly, which leaves only little time for quality assurance. Moreover, quality assurance is complicated by service providers only giving information on their services in terms of domain specific concepts with only limited semantic meaning.In this paper, we propose a method for constructing service compositions based on pre-verified templates. Templates, given as workflow descriptions, are typed over a (domain-independent) template ontology defining concepts and predicates. Their meaning is defined by an abstract semantics, leaving the specific meaning of ontology concepts open, however, only up to given ontology rules. Templates are proven correct using a Hoare-style proof calculus, extended by a specific rule for service calls. Construction of service compositions amounts to instantiation of templates with domain-specific services. Correctness of an instantiation can then simply be checked by verifying that the domain ontology (a) adheres to the rules of the template ontology, and (b) fulfills the constraints of the employed template.

The Game of Reciprocation Habits - Polevoy, Gleb; de Weerdt, M.M.; Jonker, C.M. (Proceedings of the 2016 European Conference on Artificial Intelligence)
Keywords: agents; action; repeated reciprocation; fixed; floating; network; Nash equilibrium; social welfare; price of anarchy; price of stability; convex combination

The Convergence of Reciprocation - Polevoy, Gleb; de Weerdt, Mathijs; Jonker, Catholijn (Proceedings of the 2016 International Conference on Autonomous Agents and Multiagent Systems)
Keywords: agent's influence; behavior; convergence; perron-frobenius; reciprocal interaction; repeated reciprocation

On the Parameterized Parallel Complexity and the Vertex Cover Problem - Abu-Khzam, Faisal N.; Li, Shouwei; Markarian, Christine; Meyer auf der Heide, Friedhelm; Podlipyan, Pavel (Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA))
Efficiently parallelizable parameterized problems have been classified as being either in the class FPP (fixed-parameter parallelizable) or the class PNC (parameterized analog of NC), which contains FPP as a subclass. In this paper, we propose a more restrictive class of parallelizable parameterized problems called fixed-parameter parallel-tractable (FPPT). For a problem to be in FPPT, it should possess an efficient parallel algorithm not only from a theoretical standpoint but in practice as well. The primary distinction between FPPT and FPP is the parallel processor utilization, which is bounded by a polynomial function in the case of FPPT. We initiate the study of FPPT with the well-known k-vertex cover problem. In particular, we present a parallel algorithm that outperforms the best known parallel algorithm for this problem: using O(m) instead of O(n2) parallel processors, the running time improves from 4logn+O(kk) to O(k⋅log3n), where m is the number of edges, n is the number of vertices of the input graph, and k is an upper bound of the size of the sought vertex cover. We also note that a few P-complete problems fall into FPPT including the monotone circuit value problem (MCV) when the underlying graphs are bounded by a constant Euler genus.

Introduction to the Special Issue on SPAA 2014 (Transactions on Parallel Computing (TOPC))