In this work we study Invertible Bloom Lookup Tables (IBLTs) with small failure probabilities. IBLTs are highly versatile data structures that have found applications in set reconciliation protocols, error-correcting codes, and even the design of advanced cryptographic primitives. For storing n elements and ensuring correctness with probability at least 1 - δ, existing IBLT constructions require Ω(n((log(1/δ))/(log n))+1)) space and they crucially rely on fully random hash functions. We present new constructions of IBLTs that are simultaneously more space efficient and require less randomness. For storing n elements with a failure probability of at most δ, our data structure only requires O{n + log(1/δ)log log(1/δ)} space and O{log(log(n)/δ)}-wise independent hash functions. As a key technical ingredient we show that hashing n keys with any k-wise independent hash function h:U → [Cn] for some sufficiently large constant C guarantees with probability 1 - 2^{-Ω(k)} that at least n/2 keys will have a unique hash value. Proving this is non-trivial as k approaches n. We believe that the techniques used to prove this statement may be of independent interest. We apply our new IBLTs to the encrypted compression problem, recently studied by Fleischhacker, Larsen, Simkin (Eurocrypt 2023). We extend their approach to work for a more general class of encryption schemes and using our new IBLT we achieve an asymptotically better compression rate.

Multi-signatures allow for compressing many signatures for the same message that were generated under independent keys into one small aggregated signature. This primitive is particularly useful for proof-of-stake blockchains, like Ethereum, where the same block is signed by many signers, who vouch for the block's validity. Being able to compress all signatures for the same block into a short string significantly reduces the on-chain storage costs, which is an important efficiency metric for blockchains.

The focus of this work are multi-signatures schemes in the synchronized setting. A multi-signature scheme allows multiple signatures for the same message but from independent signers to be compressed into one short aggregated signature, which allows verifying all of the signatures simultaneously. In the synchronized setting, the signing algorithm takes the current time step as an additional input. It is assumed that no signer signs more than one message per time step and we aim to aggregate signatures for the same message and same time step. This setting is particularly useful in the context of blockchains, where validators are naturally synchronized by the blocks they sign.

A sanitizable signature scheme is a malleable signature scheme where a designated third party has the permission to modify certain parts of the message and adapt the signature accordingly. This primitive was introduced by Ateniese et al . (ESORICS 2005) and Brzuska et al . (PKC 2009) formalized the initially suggested five security properties. In the subsequent year, Brzuska et al . (PKC 2010) introduced a notion called unlinkability where the basic idea is that linking message‐signature pairs of the same document should be infeasible. Brzuska et al . formalized this notion and suggested a generic instantiation based on group signatures with a special structure. Unfortunately, the most efficient instantiations of group signatures do not have this property. In this work, we present the first efficient construction of unlinkable sanitizable signatures based on a novel type of signature schemes with re‐randomizable keys. This property allows one to re‐randomize both the signing and the verification key separately but consistently. Given a signature scheme with re‐randomizable keys, we obtain a sanitizable signature scheme by signing the message with a re‐randomized key and proving in zero‐knowledge that the derived key originates from either the signer or the sanitizer. To obtain an efficient instantiation, we instantiate this generic idea with Schnorr signatures and efficient ‐protocols that we turn into a non‐interactive zero‐knowledge proof via the Fiat‐Shamir transformation. In this work, we present an optimized version that is more efficient than the construction we suggested in the extended abstract of this work at PKC 2016.

Password authentication still constitutes the most widespread authentication concept on the Internet today, but the human incapability to memorize safe passwords has left this concept vulnerable to various attacks ever since. Affected enterprises such as Facebook now strive to mitigate such attacks by involving external cryptographic services that harden passwords. Everspaugh et al.~provided the first comprehensive formal treatment of such a service, and proposed the Pythia PRF-Service as a cryptographically secure solution (Usenix Security'15). Pythia relies on a novel cryptographic primitive called partially oblivious pseudorandom functions and its security is proven under a strong new interactive assumption in the random oracle model.

We develop a three-level hierarchy of privacy notions for (unforgeable) digital signature schemes. We first prove mutual independence of existing notions of anonymity and confidentiality, and then show that these are implied by higher privacy goals. The top notion in our hierarchy is pseudorandomness: signatures with this property hide the entire information about the signing process and cannot be recognized as signatures when transmitted over a public network. This implies very strong unlinkability guarantees across different signers and even different signing algorithms, and gives rise to new forms of private public-key authentication.

Energy is the most limiting factor in wireless sensor networks. Harvesting solar energy is a feasible solution to overcome the energy-constraint in some applications. It enables a theoretically infinite network lifetime, sustaining a mode of operation termed energy neutral consumption rate. The challenge arises, how can the harvested energy be utilized to maximize the performance of the sensor network. Considering a field monitoring application the performance is measured as the sustained sampling rate of the sensors. Maximizing the sampling rate needs to take the spatio-temporal distribution of load and energy into account, to prevent the over- loading of nodes. In [12] they introduced a optimal, theoretical solution based on perfect global knowledge. In this paper we propose the solar-aware distributed flow (SDF) approach. SDF enables each node to predict the harvested energy, calculate a sustainable flow and control its local neighborhood. Extensive simulations confirmed that SDF achieves over 80% of the theoretical optimum, while introducing negligible overhead. Keywords-Wireless Sensor Networks, Solar Harvesting, Energy Neutral Consumption Rate, Sampling Rate.