@inproceedings{44855, abstract = {{Market transactions are subject to information asymmetry about the delivered value proposition, causing transaction costs and adverse market effects among buyers and sellers. Information systems research has investigated how review systems can reduce information asymmetry in business-to-consumer markets. However, these systems cannot be readily applied to business-to-business markets, are vulnerable to manipulation, and suffer from conceptual weak spots since they use textual data or star ratings. Building on design science research, we conceptualize a new class of reputation systems based on monetary-based payments as quantitative ratings for each transaction stored on a blockchain. Using cryptography, we show that our system assures content confidentiality so that buyers can share and sell their ratings selectively, establishing a reputation ecosystem. Our prescriptive insights advance the design of reputation systems and offer new paths to understanding the antecedents, dynamics, and consequences to reduce information asymmetry in B2B transactions.}}, author = {{Hemmrich, Simon and Bobolz, Jan and Beverungen, Daniel and Blömer, Johannes}}, booktitle = {{ECIS 2023 Research Papers}}, title = {{{Designing Business Reputation Ecosystems — A Method for Issuing and Trading Monetary Ratings on a Blockchain}}}, year = {{2023}}, } @article{45192, author = {{Götte, Thorsten and Hinnenthal, Kristian and Scheideler, Christian and Werthmann, Julian}}, journal = {{Distributed Computing}}, title = {{{Time-Optimal Construction of Overlays}}}, doi = {{https://doi.org/10.1007/s00446-023-00442-4}}, year = {{2023}}, } @inbook{45891, author = {{Blömer, Johannes and Eidens, Fabian and Jager, Tibor and Niehues, David and Scheideler, Christian}}, booktitle = {{On-The-Fly Computing -- Individualized IT-services in dynamic markets}}, editor = {{Haake, Claus-Jochen and Meyer auf der Heide, Friedhelm and Platzner, Marco and Wachsmuth, Henning and Wehrheim, Heike}}, pages = {{145--164}}, publisher = {{Heinz Nixdorf Institut, Universität Paderborn}}, title = {{{Robustness and Security}}}, doi = {{10.5281/zenodo.8068629}}, volume = {{412}}, year = {{2023}}, } @book{45863, abstract = {{In the proposal for our CRC in 2011, we formulated a vision of markets for IT services that describes an approach to the provision of such services that was novel at that time and, to a large extent, remains so today: „Our vision of on-the-fly computing is that of IT services individually and automatically configured and brought to execution from flexibly combinable services traded on markets. At the same time, we aim at organizing markets whose participants maintain a lively market of services through appropriate entrepreneurial actions.“ Over the last 12 years, we have developed methods and techniques to address problems critical to the convenient, efficient, and secure use of on-the-fly computing. Among other things, we have made the description of services more convenient by allowing natural language input, increased the quality of configured services through (natural language) interaction and more efficient configuration processes and analysis procedures, made the quality of (the products of) providers in the marketplace transparent through reputation systems, and increased the resource efficiency of execution through reconfigurable heterogeneous computing nodes and an integrated treatment of service description and configuration. We have also developed network infrastructures that have a high degree of adaptivity, scalability, efficiency, and reliability, and provide cryptographic guarantees of anonymity and security for market participants and their products and services. To demonstrate the pervasiveness of the OTF computing approach, we have implemented a proof-of-concept for OTF computing that can run typical scenarios of an OTF market. We illustrated the approach using a cutting-edge application scenario – automated machine learning (AutoML). Finally, we have been pushing our work for the perpetuation of On-The-Fly Computing beyond the SFB and sharing the expertise gained in the SFB in events with industry partners as well as transfer projects. This work required a broad spectrum of expertise. Computer scientists and economists with research interests such as computer networks and distributed algorithms, security and cryptography, software engineering and verification, configuration and machine learning, computer engineering and HPC, microeconomics and game theory, business informatics and management have successfully collaborated here.}}, author = {{Haake, Claus-Jochen and Meyer auf der Heide, Friedhelm and Platzner, Marco and Wachsmuth, Henning and Wehrheim, Heike}}, pages = {{247}}, publisher = {{Heinz Nixdorf Institut, Universität Paderborn}}, title = {{{On-The-Fly Computing -- Individualized IT-services in dynamic markets}}}, doi = {{10.17619/UNIPB/1-1797}}, volume = {{412}}, year = {{2023}}, } @inproceedings{35014, author = {{Blömer, Johannes and Bobolz, Jan and Bröcher, Henrik}}, location = {{Taipeh, Taiwan}}, title = {{{On the impossibility of surviving (iterated) deletion of weakly dominated strategies in rational MPC}}}, year = {{2023}}, } @inproceedings{43458, author = {{Blömer, Johannes and Bobolz, Jan and Porzenheim, Laurens Alexander}}, location = {{Guangzhou, China}}, title = {{{A Generic Construction of an Anonymous Reputation System and Instantiations from Lattices}}}, year = {{2023}}, } @inproceedings{32602, author = {{Padalkin, Andreas and Scheideler, Christian and Warner, Daniel}}, booktitle = {{28th International Conference on DNA Computing and Molecular Programming (DNA 28)}}, editor = {{Ouldridge, Thomas E. and Wickham, Shelley F. J.}}, isbn = {{978-3-95977-253-2}}, issn = {{1868-8969}}, pages = {{8:1–8:22}}, publisher = {{Schloss Dagstuhl – Leibniz-Zentrum für Informatik}}, title = {{{The Structural Power of Reconfigurable Circuits in the Amoebot Model}}}, doi = {{10.4230/LIPIcs.DNA.28.8}}, volume = {{238}}, year = {{2022}}, } @inproceedings{32603, author = {{Kostitsyna, Irina and Scheideler, Christian and Warner, Daniel}}, booktitle = {{28th International Conference on DNA Computing and Molecular Programming (DNA 28)}}, editor = {{Ouldridge, Thomas E. and Wickham, Shelley F. J.}}, isbn = {{978-3-95977-253-2}}, issn = {{1868-8969}}, pages = {{9:1–9:22}}, publisher = {{Schloss Dagstuhl – Leibniz-Zentrum für Informatik}}, title = {{{Fault-Tolerant Shape Formation in the Amoebot Model}}}, doi = {{10.4230/LIPIcs.DNA.28.9}}, volume = {{238}}, year = {{2022}}, } @inproceedings{33240, author = {{Götte, Thorsten and Scheideler, Christian}}, booktitle = {{SPAA ’22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11 - 14, 2022}}, editor = {{Agrawal, Kunal and Lee, I-Ting Angelina}}, pages = {{99–101}}, publisher = {{ACM}}, title = {{{Brief Announcement: The (Limited) Power of Multiple Identities: Asynchronous Byzantine Reliable Broadcast with Improved Resilience through Collusion}}}, doi = {{10.1145/3490148.3538556}}, year = {{2022}}, } @inproceedings{30987, author = {{Kostitsyna, Irina and Scheideler, Christian and Warner, Daniel}}, booktitle = {{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)}}, editor = {{Aspnes, James and Michail, Othon}}, isbn = {{978-3-95977-224-2}}, issn = {{1868-8969}}, pages = {{23:1–23:3}}, publisher = {{Schloss Dagstuhl – Leibniz-Zentrum für Informatik}}, title = {{{Brief Announcement: Fault-Tolerant Shape Formation in the Amoebot Model}}}, doi = {{10.4230/LIPIcs.SAND.2022.23}}, volume = {{221}}, year = {{2022}}, } @inproceedings{22283, abstract = {{ We show how to construct an overlay network of constant degree and diameter $O(\log n)$ in time $O(\log n)$ starting from an arbitrary weakly connected graph. We assume a synchronous communication network in which nodes can send messages to nodes they know the identifier of and establish new connections by sending node identifiers. If the initial network's graph is weakly connected and has constant degree, then our algorithm constructs the desired topology with each node sending and receiving only $O(\log n)$ messages in each round in time $O(\log n)$, w.h.p., which beats the currently best $O(\log^{3/2} n)$ time algorithm of [Götte et al., SIROCCO'19]. Since the problem cannot be solved faster than by using pointer jumping for $O(\log n)$ rounds (which would even require each node to communicate $\Omega(n)$ bits), our algorithm is asymptotically optimal. We achieve this speedup by using short random walks to repeatedly establish random connections between the nodes that quickly reduce the conductance of the graph using an observation of [Kwok and Lau, APPROX'14]. Additionally, we show how our algorithm can be used to efficiently solve graph problems in \emph{hybrid networks} [Augustine et al., SODA'20]. Motivated by the idea that nodes possess two different modes of communication, we assume that communication of the \emph{initial} edges is unrestricted. In contrast, only polylogarithmically many messages can be communicated over edges that have been established throughout an algorithm's execution. For an (undirected) graph $G$ with arbitrary degree, we show how to compute connected components, a spanning tree, and biconnected components in time $O(\log n)$, w.h.p. Furthermore, we show how to compute an MIS in time $O(\log d + \log \log n)$, w.h.p., where $d$ is the initial degree of $G$.}}, author = {{Götte, Thorsten and Hinnenthal, Kristian and Scheideler, Christian and Werthmann, Julian}}, booktitle = {{Proc. of the 40th ACM Symposium on Principles of Distributed Computing (PODC '21)}}, editor = {{Censor-Hillel, Keren}}, location = {{Virtual}}, publisher = {{ACM}}, title = {{{Time-Optimal Construction of Overlays}}}, doi = {{10.1145/3465084.3467932}}, year = {{2021}}, } @inbook{22057, abstract = {{We construct more efficient cryptosystems with provable security against adaptive attacks, based on simple and natural hardness assumptions in the standard model. Concretely, we describe: – An adaptively-secure variant of the efficient, selectively-secure LWE- based identity-based encryption (IBE) scheme of Agrawal, Boneh, and Boyen (EUROCRYPT 2010). In comparison to the previously most efficient such scheme by Yamada (CRYPTO 2017) we achieve smaller lattice parameters and shorter public keys of size O(log λ), where λ is the security parameter. – Adaptively-secure variants of two efficient selectively-secure pairing- based IBEs of Boneh and Boyen (EUROCRYPT 2004). One is based on the DBDH assumption, has the same ciphertext size as the cor- responding BB04 scheme, and achieves full adaptive security with public parameters of size only O(log λ). The other is based on a q- type assumption and has public key size O(λ), but a ciphertext is only a single group element and the security reduction is quadrat- ically tighter than the corresponding scheme by Jager and Kurek (ASIACRYPT 2018). – A very efficient adaptively-secure verifiable random function where proofs, public keys, and secret keys have size O(log λ). As a technical contribution we introduce blockwise partitioning, which leverages the assumption that a cryptographic hash function is weak near-collision resistant to prove full adaptive security of cryptosystems.}}, author = {{Jager, Tibor and Kurek, Rafael and Niehues, David}}, booktitle = {{Public-Key Cryptography – PKC 2021}}, isbn = {{9783030752446}}, issn = {{0302-9743}}, title = {{{Efficient Adaptively-Secure IB-KEMs and VRFs via Near-Collision Resistance}}}, doi = {{10.1007/978-3-030-75245-3_22}}, year = {{2021}}, } @inbook{22059, abstract = {{Verifiable random functions (VRFs), introduced by Micali, Rabin and Vadhan (FOCS’99), are the public-key equivalent of pseudo- random functions. A public verification key and proofs accompanying the output enable all parties to verify the correctness of the output. How- ever, all known standard model VRFs have a reduction loss that is much worse than what one would expect from known optimal constructions of closely related primitives like unique signatures. We show that: 1. Every security proof for a VRF that relies on a non-interactive assumption has to lose a factor of Q, where Q is the number of adver- sarial queries. To that end, we extend the meta-reduction technique of Bader et al. (EUROCRYPT’16) to also cover VRFs. 2. This raises the question: Is this bound optimal? We answer this ques- tion in the affirmative by presenting the first VRF with a reduction from the non-interactive qDBDHI assumption to the security of VRF that achieves this optimal loss. We thus paint a complete picture of the achievability of tight verifiable random functions: We show that a security loss of Q is unavoidable and present the first construction that achieves this bound.}}, author = {{Niehues, David}}, booktitle = {{Public-Key Cryptography – PKC 2021}}, isbn = {{9783030752477}}, issn = {{0302-9743}}, title = {{{Verifiable Random Functions with Optimal Tightness}}}, doi = {{10.1007/978-3-030-75248-4_3}}, year = {{2021}}, } @unpublished{26645, author = {{Bobolz, Jan and Eidens, Fabian and Heitjohann, Raphael and Fell, Jeremy}}, publisher = {{IACR eprint}}, title = {{{Cryptimeleon: A Library for Fast Prototyping of Privacy-Preserving Cryptographic Schemes}}}, year = {{2021}}, } @inproceedings{29566, author = {{Bobolz, Jan and Eidens, Fabian and Krenn, Stephan and Ramacher, Sebastian and Samelin, Kai}}, booktitle = {{Cryptology and Network Security}}, isbn = {{9783030925475}}, issn = {{0302-9743}}, publisher = {{Springer International Publishing}}, title = {{{Issuer-Hiding Attribute-Based Credentials}}}, doi = {{10.1007/978-3-030-92548-2_9}}, year = {{2021}}, } @inproceedings{19551, author = {{Kurek, Rafael}}, booktitle = {{Information Security and Privacy - 25th Australasian Conference, {ACISP} 2020, Perth, WA, Australia, November 30 - December 2, 2020, Proceedings}}, editor = {{K. Liu, Joseph and Cui, Hui}}, pages = {{330--349}}, publisher = {{Springer}}, title = {{{Efficient Forward-Secure Threshold Public Key Encryption}}}, doi = {{10.1007/978-3-030-55304-3\_17}}, volume = {{12248}}, year = {{2020}}, } @inproceedings{19553, author = {{Kurek, Rafael}}, booktitle = {{Advances in Information and Computer Security - 15th International Workshop on Security, {IWSEC} 2020, Fukui, Japan, September 2-4, 2020, Proceedings}}, editor = {{Aoki, Kazumaro and Kanaoka, Akira}}, pages = {{239--260}}, publisher = {{Springer}}, title = {{{Efficient Forward-Secure Threshold Signatures}}}, doi = {{10.1007/978-3-030-58208-1\_14}}, volume = {{12231}}, year = {{2020}}, } @inbook{21396, abstract = {{Verifiable random functions (VRFs) are essentially digital signatures with additional properties, namely verifiable uniqueness and pseudorandomness, which make VRFs a useful tool, e.g., to prevent enumeration in DNSSEC Authenticated Denial of Existence and the CONIKS key management system, or in the random committee selection of the Algorand blockchain. Most standard-model VRFs rely on admissible hash functions (AHFs) to achieve security against adaptive attacks in the standard model. Known AHF constructions are based on error-correcting codes, which yield asymptotically efficient constructions. However, previous works do not clarify how the code should be instantiated concretely in the real world. The rate and the minimal distance of the selected code have significant impact on the efficiency of the resulting cryptosystem, therefore it is unclear if and how the aforementioned constructions can be used in practice. First, we explain inherent limitations of code-based AHFs. Concretely, we assume that even if we were given codes that achieve the well-known Gilbert-Varshamov or McEliece-Rodemich-Rumsey-Welch bounds, existing AHF-based constructions of verifiable random functions (VRFs) can only be instantiated quite inefficiently. Then we introduce and construct computational AHFs (cAHFs). While classical AHFs are information-theoretic, and therefore work even in presence of computationally unbounded adversaries, cAHFs provide only security against computationally bounded adversaries. However, we show that cAHFs can be instantiated significantly more efficiently. Finally, we use our cAHF to construct the currently most efficient verifiable random function with full adaptive security in the standard model.}}, author = {{Jager, Tibor and Niehues, David}}, booktitle = {{Lecture Notes in Computer Science}}, isbn = {{9783030384708}}, issn = {{0302-9743}}, keywords = {{Admissible hash functions, Verifiable random functions, Error-correcting codes, Provable security}}, location = {{Waterloo, Canada}}, title = {{{On the Real-World Instantiability of Admissible Hash Functions and Efficient Verifiable Random Functions}}}, doi = {{10.1007/978-3-030-38471-5_13}}, year = {{2020}}, } @article{13770, author = {{Karl, Holger and Kundisch, Dennis and Meyer auf der Heide, Friedhelm and Wehrheim, Heike}}, journal = {{Business & Information Systems Engineering}}, number = {{6}}, pages = {{467--481}}, publisher = {{Springer}}, title = {{{A Case for a New IT Ecosystem: On-The-Fly Computing}}}, doi = {{10.1007/s12599-019-00627-x}}, volume = {{62}}, year = {{2020}}, } @inproceedings{6976, abstract = {{We investigate the maintenance of overlay networks under massive churn, i.e. nodes joining and leaving the network. We assume an adversary that may churn a constant fraction $\alpha n$ of nodes over the course of $\mathcal{O}(\log n)$ rounds. In particular, the adversary has an almost up-to-date information of the network topology as it can observe an only slightly outdated topology that is at least $2$ rounds old. Other than that, we only have the provably minimal restriction that new nodes can only join the network via nodes that have taken part in the network for at least one round. Our contributions are as follows: First, we show that it is impossible to maintain a connected topology if adversary has up-to-date information about the nodes' connections. Further, we show that our restriction concerning the join is also necessary. As our main result present an algorithm that constructs a new overlay- completely independent of all previous overlays - every $2$ rounds. Furthermore, each node sends and receives only $\mathcal{O}(\log^3 n)$ messages each round. As part of our solution we propose the Linearized DeBruijn Swarm (LDS), a highly churn resistant overlay, which will be maintained by the algorithm. However, our approaches can be transferred to a variety of classical P2P Topologies where nodes are mapped into the $[0,1)$-interval.}}, author = {{Götte, Thorsten and Vijayalakshmi, Vipin Ravindran and Scheideler, Christian}}, booktitle = {{Proceedings of the 2019 IEEE 33rd International Parallel and Distributed Processing Symposium (IPDPS '19)}}, location = {{Rio de Janeiro, Brazil}}, publisher = {{IEEE}}, title = {{{Always be Two Steps Ahead of Your Enemy - Maintaining a Routable Overlay under Massive Churn with an Almost Up-to-date Adversary}}}, year = {{2019}}, }