We propose HERMES, a scalable, secure, and privacy-enhancing system for users to share and access vehicles. HERMES securely outsources operations of vehicle access token (AT) generation to a set of untrusted servers. It builds on an earlier proposal, namely, SePCAR, and extends the system design for improved efficiency and scalability. To cater to system and user needs for secure and private computations, HERMES utilizes and combines several cryptographic primitives with secure multiparty computation (MPC) efficiently. It conceals secret keys of vehicles and transaction details from the servers, including vehicle booking details, AT information, and user and vehicle identities. It also provides user accountability in case of disputes. Besides, we provide semantic security analysis and prove that HERMES meets its security and privacy requirements. Last but not least, we demonstrate that HERMES is efficient and, in contrast to SePCAR, scales to a large number of users and vehicles, making it practical for real-world deployments. We build our evaluations with two different MPC protocols: 1) HtMAC-MiMC and 2) CBC-MAC-AES. Our results demonstrate that HERMES is in the range of milliseconds for generating an AT, whether it operates for a single-vehicle owner or a large rental-company branch with over 1000 vehicles; handling 546 and 84 AT generations per second, respectively. As a result, HERMES is an order of magnitude faster compared to SePCAR. Specifically, it delivers 696 (with HtMAC-MiMC) and 42 (with CBC-MAC-AES) more ATs compared to in SePCAR for a single-vehicle owner AT generation. Furthermore, we show that HERMES is practical on the vehicle side, too, as AT operations performed on a prototype vehicle on-board unit take only$\approx 62 $ms.

Secure multiparty generation of an RSA biprime is a challenging task, which increasingly receives attention, due to the numerous privacy-preserving applications that require it. In this work, we construct a new protocol for the RSA biprime generation task, secure against a malicious adversary, who can corrupt any subset of protocol participants. Our protocol is designed with generic multiparty computation (MPC), making it both platform-independent and allowing for weaker security models to be assumed (e.g., honest majority), should the application scenario require it. By carefully "postponing" the check of possible inconsistencies in the shares provided by malicious adversaries, we achieve noteworthy efficiency improvements. Concretely, we are able to produce additive sharings of the prime candidates, from multiplicative sharings via a semi-honest multiplication, without degrading the overall (active) security of our protocol. This is the core of our sieving technique, increasing the probability of our protocol sampling a biprime. Similarly, we perform the first biprimality test, requiring several repetitions, without checking input share consistency, and perform the more costly consistency check only in case of success of the Jacobi symbol based biprimality test. Moreover, we propose a protocol to convert an additive sharing over a ring, into an additive sharing over the integers. Besides being a necessary sub-protocol for the RSA biprime generation, this conversion protocol is of independent interest. The cost analysis of our protocol demonstrated that our approach improves the current state-of-the-art (Chen et al.-Crypto 2020), in terms of communication efficiency. Concretely, for the two-party case with malicious security, and primes of 2048bits, our protocol improves communication by a factor of ~37.

We discuss the design of symmetric primitives, in particular Pseudo-Random Functions (PRFs) which are suitable for use in a secret-sharing based MPC system. We consider three different PRFs: the Naor-Reingold PRF, a PRF based on the Legendre symbol, and a specialized block cipher design called MiMC. We present protocols for implementing these PRFs within a secret-sharing based MPC system, and discuss possible applications. We then compare the performance of our protocols. Depending on the application, different PRFs may offer different optimizations and advantages over the classic AES benchmark. Thus, we cannot conclude that there is one optimal PRF to be used in all situations.