Anonymous token schemes are cryptographic protocols for limiting the access to online resources to credible users. The resource provider issues a set of access tokens to the credible user that they can later redeem anonymously, i.e., without the provider being able to link their redemptions. When combined with credibility tests such as CAPTCHAs, anonymous token schemes can significantly increase user experience and provider security, without exposing user access patterns to providers.Current anonymous token schemes such as the Privacy Pass protocol by Davidson et al. rely on oblivious pseudorandom functions (OPRFs), which let server and user jointly compute randomly looking access tokens. For those protocols, token issuing costs are linear in the number of requested tokens.In this work, we propose a new approach for building anonymous token schemes. Instead of relying on two-party computation to realize a privacy-preserving pseudorandom function evaluation, we propose to offload token generation to the user by using group verifiable random functions (GVRFs). GVRFs are a new cryptographic primitive that allow users to produce verifiable pseudorandomness. Opposed to standard VRFs, verification is anonymous within the group of credible users. We give a construction of group VRFs from the Dodis-Yampolskiy VRF and EquivalenceClass Signatures, based on pairings and a new Diffie-Hellman inversion assumption that we analyze in the Generic Group Model. Our construction enjoys compact public keys and proofs, while evaluation and verification costs are only slightly increased compared to the Dodis-Yampolskiy VRF.By deploying a group VRF instead of a OPRF, we obtain an anonymous token scheme where communication as well as server-side computation during the issuing phase is constant and independent of the number of tokens a user requests. Moreover, by means of our new concept of updatable token policies, the number of unspent tokens in circulation can retrospectively (i.e., even after the credibility check) be decreased or increased in order to react to the current or expected network situation. Our tokens are further countable and publicly verifiable. This comes at the cost of higher computational efforts for token redemption and verification as well as somewhat weaker unlinkability guarantees compared to Privacy Pass.

In the secure two-party computation (2PC), an adversary is often categorized as semi-honest or malicious, depending on whether it follows the protocol specifications. Covert security (Aumann and Lindell, 2010) first looks into the “middle ground”, such that an active adversary who cheats will be caught with a predefined probability. Other security notions, such as publicly auditable security (Baum et al., 2014) and (robust) accountability family (Küsters et al., 2010; Graf et al., 2023; Rivinius et al., 2022), achieve public verifiability as a stronger security guarantee by relying on heavy offline and online constructions with zero knowledge proofs and (or) a bulletin board functionality. In this work, we propose a new security notion called honorific security, where an external arbiter can identify the cheater without a bulletin board. Specifically, we delay and outsource the verification steps to the arbiter, so that the original online computation is thus accelerated. We show that a maliciously secure garbled circuit (GC) (Yao, 1986) protocol can be constructed with only slightly more overhead than a passively secure protocol. Our construction performs up to 2.37 times and 13.30 times as fast as the state-of-the-art protocols with covert and malicious security, respectively.

The use of Electronic Toll Collection (ETC) systems is on the rise, as these systems have a significant impact on reducing operational costs. Toll service providers (TSPs) access various information, including drivers' IDs and monthly toll fees, to bill drivers. While this is legitimate, such information could be misused for other purposes violating drivers' privacy, most prominent, to infer drivers' movement patterns. To this end, privacy-preserving ETC (PPETC) schemes have been designed to minimize the amount of information leaked while still allowing drivers to be charged. We demonstrate that merely applying such PPETC schemes to current ETC infrastructures may not ensure privacy. This is due to the (inevitable) minimal information leakage, such as monthly toll fees, which can potentially result in a privacy breach when combined with additional background information, such as road maps and statistical data. To show this, we provide a counterexample using the case study of Brisbane's ETC system. We present two attacks: the first, being a variant of the presence disclosure attack, tries to disclose the toll stations visited by a driver during a billing period as well as the frequency of visits. The second, being a stronger attack, aims to discover cycles of toll stations (e.g., the ones passed during a commute from home to work and back) and their frequencies. We evaluate the success rates of our attacks using real parameters and statistics from Brisbane's ETC system. In one scenario, the success rate of our toll station disclosure attack can be as high as 94%. This scenario affects about 61% of drivers. In the same scenario, our cycle disclosure attack can achieve a success rate of 51%. It is remarkable that these high success rates can be achieved by only using minimal information as input, which is, e.g., available to a driver's payment service provider or bank, and by following very simple attack strategies without exploiting optimizations. As a further contribution, we analyze how the choice of various parameters, such as the set of toll rates, the number of toll stations, and the billing period length, impact a driver's privacy level regarding our attacks.

As part of Intelligent Transportation Systems (ITS), Electronic toll collection (ETC) is a type of toll collection system (TCS) which is getting more and more popular as it can not only help to finance the government’s road infrastructure but also it can play a crucial role in pollution reduction and congestion management. As most of the traditional ETC schemes (ETCS) require identifying their users, they enable location tracking. This violates user privacy and poses challenges regarding the compliance of such systems with privacy regulations such as the EU General Data Protection Regulation (GDPR). So far, several privacy-preserving ETC schemes have been proposed. To the best of our knowledge, this is the first survey that systematically reviews and compares various characteristics of these schemes, including components, technologies, security properties, privacy properties, and attacks on ETCS. This survey first categorizes the ETCS based on two technologies, GNSS and DSRC. Then under these categories, the schemes are classified based on whether they provide formal proof of security and support security analysis. We also demonstrate which schemes specifically are/are not resistant to collusion and physical attacks. Then, based on these classifications, several limitations and shortcomings in privacy-preserving ETCS are revealed. Finally, we identify several directions for future research.

Abstract In this paper we propose Privacy-preserving User-data Bookkeeping & Analytics (PUBA), a building block destined to enable the implementation of business models (e.g., targeted advertising) and regulations (e.g., fraud detection) requiring user-data analysis in a privacy-preserving way. In PUBA, users keep an unlinkable but authenticated cryptographic logbook containing their historic data on their device. This logbook can only be updated by the operator while its content is not revealed. Users can take part in a privacy-preserving analytics computation, where it is ensured that their logbook is up-to-date and authentic while the potentially secret analytics function is verified to be privacy-friendly. Taking constrained devices into account, users may also outsource analytic computations (to a potentially malicious proxy not colluding with the operator).We model our novel building block in the Universal Composability framework and provide a practical protocol instantiation. To demonstrate the flexibility of PUBA, we sketch instantiations of privacy-preserving fraud detection and targeted advertising, although it could be used in many more scenarios, e.g. data analytics for multi-modal transportation systems. We implemented our bookkeeping protocols and an exemplary outsourced analytics computation based on logistic regression using the MP-SPDZ MPC framework. Performance evaluations using a smartphone as user device and more powerful hardware for operator and proxy suggest that PUBA for smaller logbooks can indeed be practical.

Black-box accumulation (BBA) is a building block which enables a privacy-preserving implementation of point collection and redemption, a functionality required in a variety of user-centric applications including loyalty programs, incentive systems, and mobile payments. By definition, BBA+ schemes (Hartung et al. CCS ‘17) offer strong privacy and security guarantees, such as unlinkability of transactions and correctness of the balance flows of all (even malicious) users. Unfortunately, the instantiation of BBA+ presented at CCS ‘17 is, on modern smartphones, just fast enough for comfortable use. It is too slow for wearables, let alone smart-cards. Moreover, it lacks a crucial property: For the sake of efficiency, the user’s balance is presented in the clear when points are deducted. This may allow to track owners by just observing revealed balances, even though privacy is otherwise guaranteed. The authors intentionally forgo the use of costly range proofs, which would remedy this problem.

Abstract Electronic toll collection (ETC) is widely used all over the world not only to finance our road infrastructures, but also to realize advanced features like congestion management and pollution reduction by means of dynamic pricing. Unfortunately, existing systems rely on user identification and allow tracing a user’s movements. Several abuses of this personalized location data have already become public. In view of the planned Europeanwide interoperable tolling system EETS and the new EU General Data Protection Regulation, location privacy becomes of particular importance. In this paper, we propose a flexible security model and crypto protocol framework designed for privacy-preserving toll collection in the most dominant setting, i.e., Dedicated Short Range Communication (DSRC) ETC. A major challenge in designing the framework at hand was to combine provable security and practicality, where the latter includes practical performance figures and a suitable treatment of real-world issues, like broken onboard units etc. To the best of our knowledge, our work is the first in the DSRC setting with a rigorous security model and proof and arguably the most comprehensive formal treatment of ETC security and privacy overall. Additionally, we provide a prototypical implementation on realistic hardware which already features fairly practical performance figures. An interaction between an onboard unit and a road-side unit is estimated to take less than a second allowing for toll collection at full speed assuming one road-side unit per lane.

Zero-knowledge arguments have become practical, and widely used, especially in the world of Blockchain, for example in Zcash. This work revisits zero-knowledge proofs in the discrete logarithm setting. First, we identify and carve out basic techniques (partly being used implicitly before) to optimise proofs in this setting. In particular, the linear combination of protocols is a useful tool to obtain zero-knowledge and/or reduce communication. With these techniques, we are able to devise zero-knowledge variants of the logarithmic communication arguments by Bootle et al. (EUROCRYPT '16) and Bünz et al. (S&P '18) thereby introducing almost no overhead. We then construct a conceptually simple commit-and-prove argument for satisfiability of a set of quadratic equations. Unlike previous work, we are not restricted to rank 1 constraint systems (R1CS). This is, to the best of our knowledge, the first work demonstrating that general quadratic constraints, not just R1CS, are a natural relation in the dlog (or ideal linear commitment) setting. This enables new possibilities for optimisation, as, eg., any degree n2 polynomial f(X) can now be "evaluated" with at most 2n quadratic constraints. Our protocols are modular. We easily construct an efficient, logarithmic size shuffle proof, which can be used in electronic voting. Additionally, we take a closer look at quantitative security measures, eg. the efficiency of an extractor. We formalise short-circuit extraction, which allows us to give tighter bounds on the efficiency of an extractor.

Black-box accumulation (BBA) has recently been introduced as a building-block for a variety of user-centric protocols such as loyalty, refund, and incentive systems. Loosely speaking, this building block may be viewed as a cryptographic "piggy bank" that allows a user to collect points (aka incentives, coins, etc.) in an anonymous and unlinkable way. A piggy bank may be "robbed" at some point by a user, letting her spend the collected points, thereby only revealing the total amount inside the piggy bank and its unique serial number.

Bilinear groups form the algebraic setting for a multitude of important cryptographic protocols including anonymous credentials, e-cash, e-voting, e-coupon, and loyalty systems. It is typical of such crypto protocols that participating parties need to repeatedly verify that certain equations over bilinear groups are satisfied, e.g., to check that computed signatures are valid, commitments can be opened, or non-interactive zero-knowledge proofs verify correctly. Depending on the form and number of equations this part can quickly become a performance bottleneck due to the costly evaluation of the bilinear map.

Abstract We formalize and construct black-box accumulation (BBA), a useful building block for numerous important user-centric protocols including loyalty systems, refund systems, and incentive systems (as, e.g., employed in participatory sensing and vehicle-to-grid scenarios). A core requirement all these systems share is a mechanism to let users collect and sum up values (call it incentives, bonus points, reputation points, etc.) issued by some other parties in a privacy-preserving way such that curious operators may not be able to link the different transactions of a user. At the same time, a group of malicious users may not be able to cheat the system by pretending to have collected a higher amount than what was actually issued to them. As a first contribution, we fully formalize the core functionality and properties of this important building block. Furthermore, we present a generic and non-interactive construction of a BBA system based on homomorphic commitments, digital signatures, and non-interactive zero-knowledge proofs of knowledge. For our construction, we formally prove security and privacy properties. Finally, we propose a concrete instantiation of our construction using Groth-Sahai commitments and proofs as well as the optimal structure-preserving signature scheme of Abe et al. and analyze its efficiency.

We propose a new lightweight cryptographic payment scheme for transit systems, called P4R (Privacy-Preserving Pre-Payments with Refunds), which is suitable for low-cost user devices with limited capabilities. Using P4R, users deposit money to obtain one-show credentials, where each credential allows the user to make an arbitrary ride on the system. The trip fare is determined on-the-fly at the end of the trip. If the deposit for the credential exceeds this fare, the user obtains a refund. Refund values collected over several trips are aggregated in a single token, thereby saving memory and increasing privacy. Our solution builds on Brands’s e-cash scheme to realize the prepayment system and on Boneh-Lynn-Shacham (BLS) signatures to implement the refund capabilities. Compared to a Brands-only solution for transportation payment systems, P4R allows us to minimize the number of coins a user needs to pay for his rides and thus minimizes the number of expensive withdrawal transactions, as well as storage requirements for the fairly large coins. Moreover, P4R enables flexible pricing because it allows for exact payments of arbitrary amounts (within a certain range) using a single fast paying (and refund) transaction. Fortunately, the mechanisms enabling these features require very little computational overhead. Choosing contemporary security parameters, we implemented P4R on a prototyping payment device and show its suitability for future transit payment systems. Estimation results demonstrate that the data required for 20 rides consume less than 10KB of memory, and the payment and refund transactions during a ride take less than half a second. We show that malicious users are not able to cheat the system by receiving a refund that exceeds the overall deposit minus the overall fare and can be identified during double-spending checks. At the same time, the system protects the privacy of honest users in that transactions are anonymous (except for deposits) and trips are unlinkable.

This paper presents a time-area efficient hardware architecture for the multivariate signature scheme Rainbow. As a part of this architecture, a high-performance hardware optimized variant of the well-known Gaussian elimination over GF(2l) and its efficient implementation are presented. The resulting signature generation core of Rainbow requires 63,593 gate equivalents and signs a message in just 804 clock cycles at 67 MHz using AMI 0.35μm CMOS technology. Thus, Rainbow provides significant performance improvements compared to RSA and ECDSA.

This paper deals with the design of an area-time efficient hardware architecture for the multivariate signature scheme, Rainbow. As a part of this architecture, a high-performance hardware optimized variant of the well-known Gaussian elimination over GF(2l) and its efficient implementation is presented. Besides solving LSEs, the architecture is also re-used for the linear transformation operations of the scheme, thereby saving on area. The resulting signature generation core of Rainbow requires 63,593 gate equivalents and signs a message in just 804 clock cycles. A comparison of our architecture with implementations of the RSA, the ECDSA and the en-TTS scheme shows that Rainbow in hardware provides significant performance improvements.

Cryptanalysis of ciphers usually involves massive computations. The security parameters of cryptographic algorithms are commonly chosen so that attacks are infeasible with available computing resources. This contribution presents a variety of cryptanalytical applications utilizing the COPACOBANA (Cost-Optimized Parallel Code Breaker) machine which is a high-performance, low-cost cluster consisting of 120 Field Programmable Gate Arrays (FPGA). COPACOBANA appears to be the only such reconfigurable parallel FPGA machine optimized for code breaking tasks reported in the open literature. Depending on the actual algorithm, the parallel hardware architecture can outperform conventional computers by several orders of magnitude. In this work, we will focus on novel implementations of cryptanalytical algorithms, utilizing the impressive computational power of COPACOBANA. We describe various exhaustive key search attacks on symmetric ciphers and demonstrate an attack on a security mechanism employed in the electronic passport. Furthermore, we describe time-memory tradeoff techniques which can, e.g., be used for attacking the popular A5/1 algorithm used in GSM voice encryption. In addition, we introduce efficient implementations of more complex cryptanalysis on asymmetric cryptosystems, e.g., Elliptic Curve Cryptosystems (ECC) and number co-factorization for RSA.

This paper presents a hardware-optimized variant of the well-known Gaussian elimination over GF(2) and its highly efficient implementation. The proposed hardware architecture can solve any regular and (uniquely solvable) overdetermined linear system of equations (LSE) and is not limited to matrices of a certain structure. Besides solving LSEs, the architecture at hand can also accomplish the related problem of matrix inversion extremely fast. Its average running time for n times n binary matrices with uniformly distributed entries equals 2n (clock cycles) as opposed to about frac14n3in software. The average running time remains very close to 2n for matrices with densities much greater or lower than 0.5. The architecture has a worst-case time complexity of O(n2) and also a space complexity of O(n2). With these characteristics the architecture is particularly suited to efficiently solve medium-sized LSEs as they for example appear in the cryptanalysis of certain stream cipher classes. Moreover, we propose a hardware-optimized algorithm for matrix-by-matrix multiplication over GF(2) which runs in linear time and quadratic space on a similar architecture. This opens up the possibility of building a more complex architecture for efficiently solving larger LSEs by means of Strassen's algorithm which could significantly improve the time complexity of algebraic attacks on various ciphers. As proof-of-concept we realized our architecture on a contemporary low-cost FPGA. The implementation for a 50 times 50 LSE can be clocked with a frequency of up to 300 MHz and computes the solution in 0.33 mus on average

Evaluating network components such as network intrusion detection systems, firewalls, routers, or switches suffers from the lack of available network traffic traces that on the one hand are appropriate for a specific test environment but on the other hand have the same characteristics as actual traffic. Instead of just capturing traffic and replaying the trace, we identify a set of packet trace manipulation operations that enable us to generate a trace bottom-up: our trace primitives can be traces from different environments or artificially generated ones; our basic operations include merging of two traces, moving a flow across time, duplicating a flow, and stretching a flow's time-scale. After discussing the potential as ell as the dangers of each operation with respect to analysis at different protocol layers, we present a framework within which these operations can be realized and show an example configuration for our prototype.