Vehicle Authentication with Threshold Signatures Master’s thesis in Computer science and engineering Tommi-Roy Karlsson Lam Nguyen Department of Computer Science and Engineering CHALMERS UNIVERSITY OF TECHNOLOGY UNIVERSITY OF GOTHENBURG Gothenburg, Sweden 2023 Master’s thesis 2023 Vehicle Authentication with Threshold Signatures Tommi-Roy Karlsson Lam Nguyen Department of Computer Science and Engineering Chalmers University of Technology University of Gothenburg Gothenburg, Sweden 2023 Vehicle Authentication with Threshold Signatures Tommi-Roy Karlsson Lam Nguyen © Lam Nguyen Tommi-Roy Karlsson, 2023. Supervisor: Elena Pagnin, Department of Computer Science and Engineering, Chalmers University of Technology Advisors: Ivan Oleinikov, Chalmers University of Technology, Tomas Carlfalk, Jeffrey Spång, Anton Lundén, and Jens Andersson Examiner: Magnus Almgren, Department of Computer Science and Engineering, Chalmers University of Technology Master’s Thesis 2023 Department of Computer Science and Engineering Chalmers University of Technology and University of Gothenburg SE-412 96 Gothenburg Telephone +46 31 772 1000 Typeset in LATEX Gothenburg, Sweden 2023 iv Vehicle Authentication with Threshold Signatures Lam Nguyen & Tommi-Roy Karlsson Department of Computer Science and Engineering Chalmers University of Technology and University of Gothenburg Abstract This thesis work aims to evaluate the practical application of threshold signature schemes in vehicular settings, with a specific focus on strengthening the security and redundancy of private keys used in mutual TLS (mTLS) in vehicle-to-everything (V2X) communication. The proposed VATS (Vehicular Application of Threshold Signature) scheme introduces an innovative approach to secure key sharing among electronic control units (ECUs) within vehicles, significantly enhancing key man- agement security. Using a carefully designed secure secret sharing scheme, the VATS scheme enables the reconstruction of the private key by using a predeter- mined threshold of ECUs. This approach ensures that no single ECU possesses the complete private key, mitigating the risks associated with key compromise or unau- thorized access. Instead, multiple ECUs collaboratively contribute their shares to reconstruct the private key, thus establishing a higher level of security and resilience in vehicular networks. To validate the effectiveness and practicality of the VATS scheme, extensive evaluations and benchmarking have been performed. The perfor- mance of the scheme, including execution time, resource utilization, and scalability, has been measured and analyzed. These evaluations provide valuable insights into the scheme’s efficiency and its ability to handle various amounts of participants in the scheme. Keywords: Thershold Signature, RSA, ECDSA, EdDSA, Schnorr, Cryptography, VSS, PSS, Accountability v Acknowledgements We would like to express our sincere gratitude to our supervisors Elene Pagnin and Ivan Oleinikov, for their invaluable help and guidance throughout the project. We would also like to thank Tomas Carlfalk, Jeffrey Spång, Anton Lundén, and Jens Andersson for their support and guidance as company supervisors. Tommi-Roy Karlsson & Lam Nguyen, Gothenburg, 2023-09-18 vii Contents List of Figures xiii List of Tables xv 1 Introduction 1 1.1 Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Problems and Challenges . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.3 Purpose . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.4 Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.5 Scope and Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.5.1 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.5.2 Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.6 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.7 Thesis outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2 Background 9 2.1 Threshold Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Digital signature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.1 Schnorr Signature . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.2 EdDSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2.3 RSA Signature . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 Extended Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3.1 Interactive and Non-Interactive . . . . . . . . . . . . . . . . . 13 2.3.2 Verifiable secret sharing . . . . . . . . . . . . . . . . . . . . . 13 2.3.3 Publicly Verifiable Secret Sharing . . . . . . . . . . . . . . . . 14 2.3.4 Accountability . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3.5 Proactive Secret Sharing . . . . . . . . . . . . . . . . . . . . . 15 2.3.6 Distributed Key Generation . . . . . . . . . . . . . . . . . . . 16 2.4 TLS in vehicles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3 Related Work 19 4 Methods 23 4.1 Research Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.2 Reference Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.3 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 ix Contents 4.3.1 Programming Language . . . . . . . . . . . . . . . . . . . . . 25 4.3.2 Libraries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.4 Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 5 Scheme 29 5.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.2 Scheme Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.2.1 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.2.2 Key Generation (KeyGen) . . . . . . . . . . . . . . . . . . . . 30 5.2.3 Committee selection . . . . . . . . . . . . . . . . . . . . . . . 31 5.2.4 Key Aggregation (KeyAgg) . . . . . . . . . . . . . . . . . . . 31 5.2.5 Offline Signing Phase (SignOff and SignAgg) . . . . . . . . . . 32 5.2.6 Online Signing Phase (SignOn, SignAgg2 and Sign) . . . . . . 32 5.2.7 Verification (Ver) . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.2.8 Key Update (KeyUpd) . . . . . . . . . . . . . . . . . . . . . . 33 5.3 Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 6 Proofs 43 6.1 Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 6.1.1 Correctness of Signature . . . . . . . . . . . . . . . . . . . . . 43 6.1.2 Correctness of Key Updating . . . . . . . . . . . . . . . . . . 45 6.2 Security Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 6.2.1 Random Oracle Model (ROM) . . . . . . . . . . . . . . . . . . 47 6.2.2 Discrete Logarithm (DL) / One-More DL . . . . . . . . . . . . 47 6.2.3 Simulating Signatures . . . . . . . . . . . . . . . . . . . . . . 47 6.3 Reduction Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 6.3.1 Programmable Random Oracle Model (PROM) . . . . . . . . 49 6.3.2 Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 6.3.3 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 6.4 Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 6.5 Security Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 7 Evaluation 57 7.1 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 57 7.1.1 General Purpose Evaluation . . . . . . . . . . . . . . . . . . . 57 7.1.2 Architecture Specific Evaluation . . . . . . . . . . . . . . . . . 60 7.2 Data Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 7.3 Memory Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 8 Discussion 67 8.1 Design Choice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 8.2 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 8.3 Data and Memory Complexity . . . . . . . . . . . . . . . . . . . . . . 70 8.4 Risk Analysis and Ethical Considerations . . . . . . . . . . . . . . . . 70 8.4.1 Software Engineering Code of Ethics . . . . . . . . . . . . . . 71 8.4.1.1 Product . . . . . . . . . . . . . . . . . . . . . . . . . 71 8.4.1.2 Public . . . . . . . . . . . . . . . . . . . . . . . . . . 71 x Contents 8.4.1.3 Judgment and profession . . . . . . . . . . . . . . . . 72 8.4.2 Risk Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 8.5 Sustainability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 8.6 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 9 Conclusion 75 Bibliography 77 xi Contents xii List of Figures 1.1 Over-the-air updates sent to vehicles. (© 2008 IEEE) [3] . . . . . . . 2 2.1 Shamir’s Secret Sharing scheme . . . . . . . . . . . . . . . . . . . . . 9 2.2 Schnorr Signature with Alice and Bob . . . . . . . . . . . . . . . . . 11 4.1 Internal car architecture . . . . . . . . . . . . . . . . . . . . . . . . . 25 5.1 An illustration of (t, n) key generation and distribution scheme. . . . 31 5.2 The signing procedure is separated into two phases, online and offline phase. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 6.1 Reduction overview between MuSig2 and VATS . . . . . . . . . . . . 49 6.2 Reduction overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 7.1 Execution time for Key generation (KeyGen) with different values of (t,n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 7.2 Execution time for Sign Offline (SignOff) with different values of (t,n) 58 7.3 Execution time for Sign Online(SignOn) with different values of (t,n) 59 7.4 Execution time for Second Signing Aggregation (SignAgg2) with dif- ferent values of (t,n) . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 7.5 Execution time for Verification (Ver) with different values of (t,n) . . 60 7.6 Execution time for Key updating (KeyUpd) with different values of (t,n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 7.7 Execution time for Key generation (KeyGen) in accordance with the architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 7.8 Execution time for Sign Offline (SignOff) in accordance with the ar- chitecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 7.9 Execution time for Sign Online(SignOn) in accordance with the ar- chitecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 7.10 Execution time for Second Signing Aggregation (SignAgg2) in accor- dance with the architecture . . . . . . . . . . . . . . . . . . . . . . . 62 7.11 Execution time for Verification (Ver) in accordance with the architecture 63 7.12 Execution time for Key updating (KeyUpd) in accordance with the architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 xiii List of Figures xiv List of Tables 1.1 Scheme properties comparison . . . . . . . . . . . . . . . . . . . . . . 7 xv List of Tables xvi 1 Introduction This chapter briefly introduces the challenges, motivations, and goals of this project. 1.1 Context In the Internet of Things era, billions of devices are connected, presenting new possibilities and exposing us to greater security and privacy risks. Therefore, man- ufacturers must address user privacy in detail and pay more attention to security during technology development [1]. Modern vehicles can communicate and share information with each other or with servers through vehicle-to-everything communication (V2X). This capability enables them to carry out over-the-air operations, such as updating the vehicle’s firmware or software, without being physically brought to a dealership. This convenient feature is becoming increasingly favoured by original equipment manufacturers (OEMs), but it also comes with the risk of being infiltrated by malicious actors. Severe conse- quences can be caused by such security breaches in a vehicle. These consequences include the potential loss of users’ confidential data, vehicle failure due to sabotaged critical components that leads to malfunctions, and so on. Therefore, OEMs have increasingly focused on automotive cybersecurity to combat these emerging threats. As the result of this effort, proposed over-the-air schemes, such as the one offered by Shavit et al. [2], help mitigate this issue by providing firmware updates over the Internet, as seen in figure 1.1. This is just one example from a long list of challenges and risks that intelligent vehicles face in the new age of the Internet of Things. One of the most challenging aspects of wireless communications is ensuring confi- dentiality, integrity, and authentication. There are existing secure communication protocols that can address this issue. Many of these protocols require some private key to be kept secret. Losing this key would compromise the privacy and security of the conversation and its participants. The protection mechanism for private keys in existing protocols has not been thoroughly discussed. 1.2 Problems and Challenges Cryptography is a technique used to secure communication in the presence of adver- sarial behaviour, playing a significant role in ensuring privacy and improving security. 1 1. Introduction Figure 1.1: Over-the-air updates sent to vehicles. (© 2008 IEEE) [3] Transport Layer Security (TLS) is a widely adopted security protocol that facilitates privacy and secures communication over the Internet [4]. The implemented TLS in a vehicle can establish a secure communication channel between the said vehicle and external entities, such as OEM servers, traffic lights, or other vehicles. In TLS, the digital identity of the communicating parties can be verified using asymmetric cryptography, which consists of a private key and a public key for signing, and veri- fying messages, respectively. It is critical to ensure the confidentiality of the private key. A compromised private key allows the adversary to forge the victim’s digital identity, violating future communications’ integrity. TLS plays an essential role in securing communication with V2X. It ensures that only trusted parties can communicate and interact with the vehicle, preventing malicious attacks and unauthorised control over the vehicle. Using TLS to secure V2X com- munication implies the existence of a private key, which has to be stored somewhere in the vehicle to ensure that the said vehicle assumes the right digital identity during communication. Such storage can come from one of several embedded computers distributed around the vehicle, called electrical control units (ECUs). These ECUs control various vehicle functions, including external communication. In mutual TLS (mTLS) both parties are required to present valid signatures before establishing a secure communication channel with each other [5]. Keeping the private key secure is not trivial. There are several methods for creating, storing, and reconstructing a private key in the event of loss or corruption. There- fore, meticulous evaluation and strategic alignment with the security needs of the vehicular communication system are vital to ensure confidentiality and integrity in secure V2X communications. Mismanagement when creating or storing keys can lead to disastrous outcomes. Even having an unintentional malfunctioning ECU 2 1. Introduction with the private key could make it impossible for the affected vehicle to communi- cate externally, creating a single point of failure in certificate-based authentication used when establishing TLS communication in V2X communication. As such, there is an urgent need to fortify security protocols surrounding private key management while simplifying creation processes. 1.3 Purpose Several methods can increase private key security, strengthen redundancy, and avoid single points of failure when working with private keys. However, replicating the private key and storing it in several electronic control units (ECUs) around the vehicle can expose the key to significant security risks. This is because an attacker must only compromise a single ECU to extract the private key and falsify the victim’s digital identity. Instead, a multisignature scheme can be useful to prioritise strong security. Multisignature refers to the ability of a group of signers to collectively sign a message and produce a signature in an interactive signing protocol [6]. This technique requires a quorum of ECUs to sign a message that verifies the vehicle’s identity and establishes TLS-protected communication. Compared to the replication technique, multi-signature offers better security of the vehicle’s identity but lacks the redundancy needed in case of ECU failures since all ECUs in the designated quorum must actively sign the message. To simultaneously address these properties, threshold signature protocols can be considered. A cryptographic primitive called threshold signature [7] allows a group of partici- pants to jointly own a numerical secret. In a (t, n) threshold signature scheme, the secret is distributed among n participants, and it requires at least t of them to work together to produce a valid digital signature. These schemes provide good security since no single ECU stores the private key, thus eliminating the risk of a single point of failure. As long as enough ECUs remain operational in the vehicle to cooperate and generate a signature for authentication, redundancy is ensured. This thesis work aims to develop and evaluate the application of threshold signature schemes in vehicular settings to strengthen the security and redundancy of private keys used in mTLS communication. 1.4 Goals The goal is to design a (t, n) threshold signature scheme suitable for vehicular use. This means that with the help of n ECUs, the key can be shared among the ECUs to improve the security of key management in vehicles. Here, the threshold t is the minimum number of ECUs needed to be able to reconstruct the secret and authenticate the vehicle. This is implemented with the help of a secret sharing scheme that allows reconstruction of the private key using t ECUs. There are a few standard techniques to revise the secret key, such as using the surviving ECUs to reconstruct the private key and resharing the signing key to 3 1. Introduction trusted devices. However, this could cause problems with the security of the private key. Therefore, it could be more beneficial to use alternatives to these resharing methods that do not involve reconstructing the secret key s. The objective of this project is to discover solutions to the following questions: • How can a threshold signature scheme be utilized to improve security while avoiding the single-point-of-failure problem of private key employed in TLS communication? • What are the various techniques to sign an electronic message and distribute keys in a threshold signature scheme and how do they compare with each other? • Can these methods be feasibly, practically and efficiently implemented in resource-constrained devices like ECUs found in automobiles? • What properties of a threshold signature scheme are desirable in a vehicular setting, and can a new protocol be created using existing schemes to achieve said properties? 1.5 Scope and Limitations Evaluating the limitations and setting a clear scope for the thesis work helps to keep the project’s focus more aligned with the goals. These are the limitations and scope of this work. 1.5.1 Limitations One notable limitation in implementing the proposed protocol is the challenge of testing it in a real vehicular environment. Such testing would require access to the ECUs of an actual vehicle, which is costly and overly complex for the scope of this thesis. Instead, a proof-of-concept implementation in a simulated environment that closely resembles modern vehicle ECU networks would have to suffice in this project. This alternative approach can substantially reduce the testing effort required without compromising the validity of the implementation of the protocol. Moreover, the design of ECUs is often protected by intellectual property rights held by manufacturers or third parties, which presents a significant obstacle to adapting them to test the proposed protocol. As such, conducting simulations is a more feasible and practical approach to testing the protocol’s performance in a controlled environment. Apart from the aforementioned constraints, it is crucial to consider the limitations of computational resources. Assuming that the ECUs in a vehicle possess hard- ware specifications similar to those of a contemporary personal computer is not a realistic assumption for this project. This may result in the exclusion of effective protocols that are computationally intensive. Communication restrictions between ECUs, such as bandwidth and capacity, must also be considered. Non-interactive 4 1. Introduction protocols are preferable since they do not strain the communication link between ECUs. Reduced communication also reduces the likelihood of information leakage during transmission, in addition to TLS measures. Although scalability is typically a critical aspect when designing protocols, it is less significant in this project since the number of ECUs in a vehicular setting is limited. Therefore, efficiency and security are of greater significance than scalability. 1.5.2 Scope Many techniques could be considered to address the challenges mentioned in Sec- tion 1.2. But the scope of this thesis work is limited to using cryptographical approaches and threshold signatures, in particular, to address these issues. The in- ternal communication network of a vehicle could vary for different vehicles depend- ing on the manufacturers’ design of choice. Therefore, finding a generic solution for every possible network design is not practical. Therefore, this thesis focuses on vehicles with similar communication mechanisms and network designs as described in the next Section 4.2. The development of a new cryptographic protocol from scratch is generally discour- aged due to the considerable knowledge and expertise required and the need for rigorous study, review, and peer approval to ensure its soundness. Given the time- line for this thesis project, undertaking these steps may not be feasible without sacrificing other essential aspects of the work. Therefore, the focus will be on adapt- ing and enhancing existing, well-established, and proven protocols to simplify the creation process and enhance the new protocol’s security analysis. Consequently, the proposed protocol draws inspiration from an established and proven cryptographic protocol. 1.6 Contributions The project develops a new scheme explicitly designed for V2X communication. To ensure its practicality and effectiveness, the protocol has been designed to have cer- tain desired properties, which include: • Threshold tolerance with the ability to accommodate up to n possible signers and at least t signers. • Committee selection • Multi-signing capabilities • Verifiable secret sharing (VSS): The validity of a share as part of the secret is verifiable. • Accountability/traceability for the signing committee: The non-repudiation property of the signing committee. 5 1. Introduction • Publicly verifiable secret sharing (PVSS): The ability to verify the validity of other participants’ shares. • Proactive verifiable secret sharing to renew keys (PSS): The ability to renew shares at will without changing the original secret. • Effective communication between parties. • A proven and secure design. Each of the desired properties listed for the protocol plays a vital role in ensuring the security and reliability of vehicular communication. Threshold tolerance with the ability to accommodate up to a certain number of signers, is essential in a distributed system such as vehicular communication, where nodes may be lost or compromised. The ability to tolerate a certain number of faults or attackers is critical to maintaining the integrity of the communication. The selection of committees is essential to ensure that the appropriate nodes are chosen to participate in the communication process. This can help prevent malicious or unreliable nodes from participating in the protocol. Multisigning capabilities, including verifiable secret sharing, accountability, and traceability for each signer, proactive verifiable secret sharing for key renewal, and publicly verifiable secret sharing, are critical to ensuring the protocol is secure and reliable in long-lived systems. In addition, these capabilities help ensure that com- munication is protected against attacks while also providing a way to hold individual signers accountable if necessary. Effective communication between parties is essential to ensure that the protocol functions appropriately and that all nodes can understand and participate in the communication. Finally, a proven and secure design is vital to ensure that the protocol is reliable and can be trusted to protect communication. A secure design ensures that the protocol is resistant to attacks and can be relied upon to function correctly in a real-world vehicular communication environment. To develop a suitable scheme for real-world application, all the aforementioned prop- erties should be considered. Including all these properties strengthens the ratio- nale for implementing the scheme proposed for use in the real world. The pro- posed scheme will be nicknamed Vehicle Authentication using Threshold Signature (VATS). In their papers, FROST [7], ICE-FROST [8], and Musig2 [6], the authors mention possible applications of their respective schemes in cryptocurrency. Theoretically, these schemes can also be applied to other applications, including in a vehicular setting. However, the suitability and practicality of this idea have not been tested or mentioned. Therefore, another contribution of this work is the evaluation of the said schemes in our particular setting. We have also combined these well-regarded schemes into a threshold multisignature scheme with the desired properties as shown in table 1.1, which makes it more practical and suitable for vehicular applications. 6 1. Introduction Schnorr signature [9] FROST [7] ICE- FROST [8] MuSig2 [6] VATS (Scheme 5) Threshold tolerant 7 3 3 7 3 Committee selection 7 7 7 7 3 Multi-signing 7 3 3 3 3 VSS 7 3 3 7 3 Accountability 3 7 7 3 3 PVSS 7 3 3 7 3 PSS 7 7 3 7 3 Table 1.1: Scheme properties comparison 1.7 Thesis outline This chapter of the thesis provides an overview of the project, including its definition, objectives, and limitations. The following is a list of the remaining chapters of the thesis. • Chapter 1 gives context and introduces the problem that vehicular authen- tication is facing, as well as presenting our motivations and goals with the project. • Chapter 2 introduces various cryptographic schemes, signatures, and proper- ties that give context to the work done in this thesis. It will also discuss the security implications of these schemes and how they can be used to protect data and communications. This background should assist in comprehending how the scheme proposed in this thesis is constructed. • Chapter 3 is the section of related work where important papers for developing the proposed scheme are presented. This section provides an overview of the existing literature and explains how different schemes work. Additionally, it should provide a comparison between the proposed scheme and the existing ones and should explain why the proposed scheme is improved compared to the existing ones for vehicular implementation. • Chapter 4 outlines the methods used in creating the proposed scheme and describes how the implementation was carried out so that the scheme could be tested. The types of tests that are important to evaluate the scheme are described, such as execution time, resource usage, and scalability, and why they are specifically tested. • Chapter 5 presents the VATS scheme and its components. • Chapter 6 describes the proofs for the scheme to ensure that the scheme is correct and secure. • Chapter 7 is the section where the scheme evaluation and performance are presented and gives the results of the testing conducted on the scheme’s im- 7 1. Introduction plementation. • Chapter 8 discusses the design choices made for the scheme, which gives a context as to why the scheme is done in specific ways, and it also discusses the result of the testing done in evaluation to give context to the graphs and calculations presented. In addition, the ethical aspects of the project are discussed, as well as future work. • Chapter 9 provides the conclusion of the thesis on the scheme and its usability. 8 2 Background This chapter presents fundamental background knowledge in the research area, cov- ering cryptographic schemes and the attributes that may be desired for a scheme. 2.1 Threshold Cryptography Figure 2.1: Shamir’s Secret Sharing scheme The secret-sharing schemes of Shamir and Blakley [10] [11] allow a collection of n nodes to share a secret value, such that any t, (t ≤ n) nodes can collaborate to perform operations using the secret. The secret is only compromised when an adversary controls t or more nodes. 9 2. Background Shamir’s Secret Sharing scheme is shown in figure 2.1 and is described as follows. • Key generation: 1. Choose a prime number p such that p > n, where n is the total number of shares, and t is the threshold for reconstruction. 2. Choose a random secret key s ∈ 0, 1, . . . , p− 1. 3. Define the polynomial f(x) = s + a1x + a2x 2 + · · ·+ at−1x t−1, where the coefficients ai are chosen randomly and uniformly from 0, 1, . . . , p− 1, and at−1 ̸= 0. 4. Compute f(i) for i = 1, 2, . . . , n, and distribute the shares (i, f(i)) to n different participants. • Secret reconstruction: 1. Choose any t shares, for example (x1, y1), (x2, y2), . . . , (xt, yt), where x1, x2, . . . , xt are distinct. 2. Define the Lagrange polynomial Li(x) as follows: Li(x) = t∏ j ̸=i,j=1 x− xj xi − xj , i = 1, 2, . . . , t. In this work, the Lagrange polynomial Li(x) is denoted by δi,j. 3. Compute the secret key s as: s = f(0) = t∑ i=1 yi · δi,0 = t∑ i=1 yi · t∏ j ̸=i,j=1 xj xj − xi There are many desirable properties that a protocol can have. Depending on different use cases, certain properties are more suitable than others. Some of these properties are described in Section 2.3. It can be noted that by setting n equal to t, one would instead get multi-signature where all participant’s shares have to be used in the calculations to reconstruct the secret key s. 2.2 Digital signature This section explains the different digital signature schemes known for being rigor- ously proven to be sound and commonly used. By understanding the differences and workings of these schemes, the readers can better grasp the different digital signatures that are discussed in the paper. 2.2.1 Schnorr Signature The Schnorr signature scheme, proposed by Claus-Peter Schnorr [12], utilises a prime order cyclic group G with prime order p, a generator g from the group, and a hash function H. 10 2. Background Here is an overview of how Schnorr works: • Key Generation: To generate a private/public key pair, a private key x ∈ (0, . . . , p− 1) ∈ G is chosen, and the corresponding public key is Y = gx. • Signing: Signing a message involves selecting a random integer r ∈ Zp and computing a "number used once" (nonce) R = gr, which is used to provide a unique signature. The challenge c = H(X, R, m) is then obtained by applying the hash function H to the concatenation of the public key Y , the nonce R, and the message to be signed. Finally, the signature is calculated as s = r + cx, and the pair (R, s) is used as the signature. • Verification: The validity of a signature can be verified by checking if gs = RY c. Figure 2.2: Schnorr Signature with Alice and Bob 2.2.2 EdDSA EdDSA (Edwards-curve Digital Signature Algorithm) is a digital signature scheme based on elliptic curve cryptography. It was developed by Bernstein et al. [13], and has since become widely used in various cryptographic applications. Here is an overview of how EdDSA works: 11 2. Background • Key Generation: A private key, x, is randomly generated from a secure random number genera- tor. A public key, Y , is then derived from the private key by scalar multiplica- tion with a base point on the chosen elliptic curve: Y = [x] ·G, where ([x] ·G) denotes the scalar multiplication of G with x, where G is the base point on the elliptic curve. • Signing: To sign a message, the signer computes a random value, r, using a secure random number generator. A nonce, R, is then computed as the scalar multi- plication of R = [r] ·G. The signer then computes a hash of the message and the nonce, H(m, R). A scalar value, S, is then calculated as S = r+H(m, R)·x. The signature is then the pair (R, S). • Verification: To verify a signature, the verifier first checks that the public key, Y , is valid by ensuring that it lies on the elliptic curve and is not the point at infinity. The verifier then computes the hash of the message and the nonce, H(m, R), and computes a scalar value, u, as u = H(m, R) · Y + S ·G. The signature is valid if the point u equals R. An example of a curve that can be used with EdDSA is curve25519, defined as a prime number 2255 − 19 and using the base point x = 9, Curve25519 offers 128-bit security [14]. 2.2.3 RSA Signature RSA (Rivest-Shamir-Adleman) signing by Rivest et al. [15] is used to generate a signature for a message using a private key, which can be verified using the corre- sponding public key. Here is an overview of the RSA signing protocol: • Key Generation: A private key, d, is generated by selecting two large prime numbers, p, q, the modulus is calculated n = p · q and then computing the totient d = (p − 1)(q − 1). A public key, e, is then generated by selecting a value that is co-prime to d, typically a small odd integer such as 65537. The pair (n, e) is the public key, and (n, d) is the private key. • Message Padding: The message to be signed is first padded to ensure that it is the same length as the RSA modulus n. Various padding schemes, such as PKCS#1 v1.5 or RSA-PSS, can be used. • Signature Generation: To generate a signature for the message, the signer first computes a hash value of the padded message using a secure hash function, such as SHA-512. The hash value, h, is then encrypted using the private key, d, to produce the signature, s : s = hd mod n. 12 2. Background • Verification: To verify the signature, the verifier first decrypts the signature using the public key, e : h′ = se mod n. The verifier then computes a hash value of the original message using the same hash function as the signer and compares it to h′. If they are equal, then the signature is valid. In February 2023, the National Institute of Standards and Technology, NIST, pub- lished the Digital Signature Standard (DSS) [16]. Of the algorithms specified in that document, two of them, EdDSA and ECDSA, are variants of the Schnorr digital sig- nature, and the last one is based on RSA. The recommended bit length for modulus in RSA is currently 2048 bits. Meanwhile, the EdDSA and ECDSA’s recommended bit lengths are significantly lower (greater than 256 bits). 2.3 Extended Properties Several modifications can be implemented to better manage the private key in ve- hicular authentication to increase the security of the private key, strengthen redun- dancy, and avoid a single point of failure. As such, these properties can be used to strengthen the scheme and are used together with the signature schemes described previously. 2.3.1 Interactive and Non-Interactive In an interactive protocol, the interaction between participants is allowed [17]. Said interaction is considered to be messages sent over a communication channel. Non- interactive protocols, on the other hand, only allow a certain participant called a dealer to communicate with the rest of the participants. 2.3.2 Verifiable secret sharing Verifiable secret sharing (VSS) is one of the fundamental ways of ensuring that the secrets shared by the dealer in a threshold cryptographic scheme are indeed valid shares of the bigger secret. Something that was introduced primarily by Chor et al. in [18]. Feldman [19] introduces a noninteractive VSS which widens the applicability of VSS to scenarios in which interaction is infeasible, such as sharing a secret among an entire nation. Also, several executions of noninteractive protocols may be run in parallel. On the contrary, interactive schemes may have to run serially. Thus, noninteraction allows us to use VSS as a subroutine without increasing the round complexity. To facilitate the verification of the distributed shares, Feldman [19] [20] proposes a scheme where the dealer also broadcasts a public commitment vector. Feldman’s (t, n) threshold VSS scheme, where t is the threshold and n is the total number of participants, for secret s, s ∈ Zg is as follows: • Let g be of a group of order p (p is a large prime). 13 2. Background • Dealer chooses a random polynomial: a(X) = s + u1X + ... + utX t where uj ∈R Zp, 1 ≤ j ≤ t. • The dealer sends the secret shares si = a(i) to participants Pi in private for i = 1, ....., n. • The dealer also Broadcasts commitments Bj = guj , 0 ≤ j ≤ t • When Participant Pi receives their share si, they are able to verify their share with the commitment: gsi = ∏t j=0 B ij j Reconstruction: • Each participant’s share (Pi) is verified with gsi = ∏t j=0 B ij j • The secret is then recoverable with Shamir’s Scheme such that s = a(0) Pederson’s VSS scheme [17] works similarly to Feldman’s. However, it is different from Feldman’s scheme in that it does not assume that the a priori distribution of s used by the dealer is the uniform distribution on Zn, and instead ensures that the security of the secret is not dependent on the a priori distribution of s. That said, the major difference is the commitments. 2.3.3 Publicly Verifiable Secret Sharing VSS enables participants to verify the validity of their own shares but they do not know if other participants in the protocols also received valid shares. If an ill-intended dealer distributes invalid shares to a subset of participants and these participants accept those shares, the reconstruction of the original secret will fail. Publicly verifiable secret sharing, PVSS, is defined informally as the ability to verify the validity of any other share in addition to the participant’s own share [21]. Assume a public encryption function Ei with respective decryption function Di where only the corresponding participant i knows Di. The set of all n participants is denoted by L. In a PVSS scheme, each share is encrypted before being distributed by the dealer: Si = Ei(si) , i ∈ L. Verification of all the encrypted shares is carried out using an algorithm PubVerify with the following property: ∃ u ∀ i ∈ L : (PubV erify({Si | i ∈ L}) = 1) =⇒ Recover({Di(Si) | i ∈ L}) = u Simply put, if the function PubVerify validates the validity of a set of encrypted shares to be good, then honest participants can decrypt them and recover the secret. One requirement in PubVerify is that it must be executable even if the participants have not received their shares. 14 2. Background 2.3.4 Accountability With accountability, one can ensure with threshold signature that the shares are used to sign the message, something that helps to know which devices were active in the signature process. This way, it enables the message receiver to identify whether some devices are compromised or not. A protocol is suggested by Boneh et al. [22] that uses an accountable signature and a private signature, which is called a thresh- old, accountable, and private signature (TAPS). During the key generation phase, they also create a tracing key, which helps trace the signature back to the quorum that generated it. The TAPS protocol achieves the private threshold signature by giving the tracing key to only trusted parties. If the tracing key goes public, the pro- tocol becomes a "normal" accountable threshold signature scheme, whilst destroying the key would simply make it a private threshold signature scheme. Keeping the signature private and accountable simultaneously would require that the trace key remain in the possession of the trusted parties [22]. 2.3.5 Proactive Secret Sharing Ensuring that key shares remain secret forever in a long-lived system is not realistic, as nodes can become compromised or fail over time, potentially exposing secret key shares. This gives the possible adversary more time to collect shares and recover the secret. Proactive secret sharing schemes (PSS) [23] address this issue by using a secret sharing regeneration protocol, which allows one to keep the main secret the same while refreshing the shares of trusted devices. This renders old key shares useless, and mobile adversaries trying to compromise the system for a longer period than the refreshing of shares will not be able to meet the threshold t to reconstruct the secret. Refined PSS schemes allow for the renewal of existing shares and the distribution of new shares to different signers, meaning that new members are able to hold a share of the secret. This can be seen as a redistribution of shares instead of renewals. By periodically updating the shared secret, parties can ensure that the data remains secure even if one or more parties become compromised [8]. Here is how a proactive secret sharing scheme works [23]: • Proactive secret sharing involves periodically updating the shares of a secret among a set of n participants. Assume that there is a (t, n) secret sharing scheme and that each participant has a valid share. • At regular intervals of T time units, a subset of α participants is selected from the set of n participants. • Each selected participant constructs a random polynomial fi(x) of degree t−1 such that fi(0) is the participant’s current share of the secret. fi(x) = si + ai,1 + . . . + ai,t−1 • The coefficients of fi(x), ai,0, ai,1, . . . , ai,t−1, are chosen randomly from Zp, where p is a large prime number. 15 2. Background • Each selected participant sends its share of the updated secret, which is the value of fi(j) for j = 1, 2, . . . , n, to all other correct participants in the system. • Each nonselected node updates its share of the secret by computing uj,i = fj(i) for all j in the subset of selected nodes and then updating its share as xt+1 i = xt i + ut 1,i + ut 2,i + · · · + ut t,i, where t is the time interval in which the shares are valid. • All nodes store the updated shares and use them to reconstruct the secret key whenever necessary. Secret reconstruction: The secret key can be reconstructed using the same pro- cedure as in the non-proactive secret sharing scheme like Shamir’s [10]. All of the non-updated shares an attacker accumulated become useless. An attacker can only recover the secret if they can find enough other non-updated shares to reach the threshold. This situation should not happen because the participants delete their old shares. The dealer can change the threshold number while distributing updates, but must always remain vigilant of participants keeping expired shares. However, this is a somewhat limited view since the original method gives the community of servers the ability to be the re-sharing dealer and the regenerator of lost shares. 2.3.6 Distributed Key Generation Distributed key generation (DKG) allows participants P = {P1, ...., Pn} to generate a public and secret key together. This excludes the need for any dealer to be trusted. Something that was originally proposed by Pederson [24]. In this scheme, each participant Pi creates their own secret si and then creates the corresponding shares for all other participants. The scheme requires two rounds: • Public communication round: Each party broadcasts a commitment to si and the coefficients of the corre- sponding polynomial. • Secure communication round: Secret shares of si are securely sent to all other participants by each participant Pi. After receiving a share from Pi, each participant checks if the received share is consistent with the previously published commitment. The received share is designated as qualified if this is the case. By adding up all the qualified shares that each participant has received, they are able to determine their total share. Any party does not compute the secret shared value s itself: however, it is equal to the sum of the shared si, which passed commitment checks by all recipients of the shares. 2.4 TLS in vehicles TLS is a cryptographic protocol that enables secure communication over a network. It is commonly used to secure web browsing sessions and email communications, among other things. TLS ensures the confidentiality, integrity and authentication 16 2. Background of data exchanged between two parties using encryption algorithms and digital cer- tificates. An example use case is when a user connects to a website using HTTPS (HTTP Secure), the web server and the user’s browser initiate a TLS handshake to establish a secure connection. During the handshake, the server presents a digital certificate that verifies its identity to the user’s browser. The browser then uses public key cryptography to authenticate the certificate and establish a secure session key for the connection. This session key is used to encrypt and decrypt data exchanged between the server and the browser, ensuring that the data remains confidential and secure. There are mainly two TLS versions used today, version 1.2 and version 1.3. The TLS 1.3 protocol provides several improvements over TLS 1.2, such as reduced latency and improved security. One significant change is the replacement of several older cryptographic algorithms with newer, more secure ones. For instance, TLS 1.3 no longer supports the RSA key exchange algorithm and instead relies on Diffie-Hellman key exchange, which is more secure against attacks. Various ECUs are responsible for controlling various functions, such as the engine, transmission, and infotainment system. These ECUs need to communicate with each other to ensure that the vehicle operates correctly. Therefore, it is vital to estab- lish a secure internal communication protocol that can transmit messages between ECUs safely. To achieve this, Zelle et al. [25] propose using TLS for internal vehicle communication. TLS can provide authentication, confidentiality, and integrity for data exchanged between ECUs, ensuring that messages are secure and trustworthy. Implementing TLS in internal vehicle communication can protect against potential attacks and ensure the safety and reliability of the vehicle. However, implement- ing TLS in-vehicle communication systems can be challenging due to the limited resources available in ECUs. 17 2. Background 18 3 Related Work The threshold signature concept has been around for a long time [26] and has gained much traction along with the cryptocurrency uprising. This chapter looks closely at some publications that are closely related to and inspired this thesis work. In multiparty computation, having as few communication rounds between partic- ipants as possible is desirable because these interactive rounds are inefficient and costly in terms of time and network bandwidth. To our knowledge, two-round com- munication is still the lower limit for Schnorr-based multiparty computed digital signature schemes. In distributed signing, the aggregated signature includes ran- domness from each signing party for security reasons. Hence, it takes at least one round of communication for nonce exchange and one other round for the actual signing of the message. Constructing multi-party Schnorr-based signing schemes with optimal communi- cation efficiency is not trivial. Although, there have been several multisignature schemes that could archive it, for example, the preliminary version of the Musig [27] by Maxwell et al. or Bagherzadi et al. scheme [28]. The idea of doing multisig- nature in these schemes is to have the signing committee exchanges nonces, which are aggregated in later steps and then hashed to create a challenge c. This chal- lenge c is embedded together with each signer’s self-generated nonce and secret key to create its partial signature. An aggregated Schnorr-like signature is the sum of all the partial signatures. It can be verified just like a non-distributedly generated signature. The respective papers refer to more details and the actual algorithm of these schemes. Unfortunately, these schemes have been proven flawed under normal discrete-logarithmic assumptions by Drijvers et al. [29]. Their work on the security of two-round multi- signature proves that all the known two-round Schnorr-based signature schemes are insecure in a parallel setting. Drijvers et al. build the attack around the adversary’s ability to open concurrent signing sessions to collect other signers’ commitments and manipulate the challenge c to produce a valid signature. The challenge c is a num- ber that is mapped onto group G from a hash of the public key Y , the commitment R, and the message m. With the commitment and message embedded in the hash, falsifying only the message would create a different output than the valid hash, thus failing the challenge calculation and, eventually, verifying the signature. But if the adversary manipulates the commitment and hashes it with the forged message, they can potentially generate a hash with the same mapping as if the hash was genuine. 19 3. Related Work Attacking the hash function itself is computationally impractical and borderline in- feasible. But attacking the hash function mapping over to the cyclic group can be reduced to subexponential complexity with the help of Wagner’s algorithm [30]. Using Wagner’s technique, the adversary can find a commitment which, together with the falsified message, generates the same challenge as a legitimate combination of commitment and message. This commitment is then sent to the honest signers, who are tricked into signing a fraudulent message. The final step of the attack is for the adversary to collect all the necessary partial signatures, aggregate them, and produce a legitimate signature for the falsified message. The attack is explained by Drijvers et al. in their paper [29] or in the MuSig2 paper [6]. Even though Drijvers et al. propose an attack on multi-signature schemes, the same technique can be abused to attack threshold signature schemes with two rounds of communication. Komlo and Goldberg touched on this concern in their paper, proposing a solution for the vulnerability of existing two-round multiparty signing digital signatures. In their paper [7], they propose a simple two-round Schnorr (t, n) threshold signature scheme, FROST, that addresses the forgery attack under concurrent signing. Their scheme relies on the idea of using a linear combination of multiple nonces to achieve better parallelism for two-round signing schemes while avoiding breaking the security proof under the pure discrete-logarithmic assumption. The efficiency of FROST can be further increased by a pre-processing stage, which reduces the number of interactive rounds while signing to only one. FROST has a distributed key generation to generate a secret, which ensures that none of the participants singlehandedly manipulates the private key. The way the proposed scheme VATS achieves the threshold property for a Schnorr- like digital signature scheme is based on Shamir’s secret-sharing technique. But still, our scheme takes a lot of inspiration from FROST on how to thresholdize a Schnorr digital signature scheme. Regarding key generation algorithms, FROST proposes distributed key generation to avoid reliance on a trusted dealer. Meanwhile, VATS uses the traditional verifiable secret-sharing scheme proposed by Feldman [19] because of the assumption that the share generation or reinitialization is only carried out by authorised entities. The dealer in the secret-sharing scheme for the setting is considered to be trusted. In addition, the private key, which is the secret to be thresholdized, is predetermined and, therefore, cannot be easily randomly generated by a distributed key generation protocol. Based on FROST, ICE-FROST [8] is another threshold signature scheme which is proposed to add robustness to FROST’s key generation. The authors define robustness as the property that finishes the execution of the protocol once it is started. FROST’s key generation lacks robustness, making it unable to create and distribute the shares if any participants are corrupted. ICE-FROST prevents this by a mechanism called identifiable cheating entity, which enables participants to iden- tify and exclude rogue participants from the key generation phase. Another worth mentioning property, which ICE-FROST offers over FROST, is proactivization. Pro- tactivization enables refreshing distributed shares while keeping the original private key unchanged. ICE-FROST implements this property by having participants accu- mulatively change the random polynomial without either revealing or changing the 20 3. Related Work original secret. The key-update procedure proposed in this work takes inspiration from this idea. FROST and ICE-FROST consider digital signatures in a threshold setting. The same logic of using a linear combination of nonces can also be applied to multisigna- ture schemes to reduce a communication round, as shown in the MuSig2 signature scheme [6]. Multisignature can be seen as a particular case of threshold signature where the threshold t equals the number of participants n. For this reason, MuSig2 is better optimised to handle the case (n, n) compared to the threshold signature (n, n) that FROST can provide. FROST, ICE-FROST, and MuSig2 all have in common the ability to partially do the signing operation offline. The preprocessing phase that FROST and ICE-FROST have is still an interactive protocol, but it can be done even before knowing the message to sign and actually signing said message. This speeds up the actual signing phase and improves other Schnorr digital signature schemes prior to their work. Though the MuSig2 scheme is not explicitly divided into a preprocessing phase and a signing phase, the authors touched on the ability to partially do the signing offline, just like in FROST and ICE-FROST. VATS inherits this ability from MuSig2. One of the important properties that VATS achieves is having the accountability of the signing committee. In threshold signature schemes such as FROST and ICE- FROST, accountability is not included since those schemes enjoy the anonymity of the committee. In other words, different signing committees produce the same signa- ture once the required signer’s threshold is passed. Being a multisignature scheme, MuSig2 guarantees that all committee signers participate and sign the message. VATS achieves accountability along with the threshold property by thresholding MuSig2. The digital signature produced by VATS proves the knowledge of the pri- vate key of the signing committee, as in threshold signature schemes, as well as the identity of each signer, similar to multi-signature schemes. 21 3. Related Work 22 4 Methods To achieve the goals set out in Section 1.4, this project was carried out in two main phases: research and development. This chapter gives an overview of what and why. 4.1 Research Methodology Before seeking solutions, it is crucial to understand the problem clearly. Therefore, the project began with a comprehensive literature review to better understand the problem. Smart vehicles are rising, significantly changing how internal and external vehicle communication is handled [31]. Therefore, considerable time was spent on this topic to understand the current and future landscape better. Initial research confirmed the need for better redundancy for the private key used in V2X com- munication, and the project was deemed potentially significant for industry and academia. When searching for a cryptographic solution to the problem, the idea of distributing the private key among many parties was of interest. Consequently, many different secret-sharing schemes were studied, focussing on Shamir secret sharing, the funda- mental technique that enables threshold signatures. A broad survey of threshold signature schemes was also conducted to gain an idea of the existing techniques and their pros and cons. This helps narrow the scope of this thesis, accelerating the research phase. From the initial research on threshold signature schemes, it was ob- served that, among EdDSA, RSA, and Schnorr digital signature schemes, Schnorr schemes have some desirable properties for a vehicular setting. Therefore, an in- depth study of threshold signature schemes that produce Schnorr or Schnorr-like signatures was performed. A threshold signature scheme can have many different properties, such as identifi- able cheater, accountability, and verifiability of the signers. The selection of the features that a protocol should have to be the most suitable and beneficial for V2X communication is based on the supervisors’ recommendations in the company where the scheme is developed. Among these properties, some were essential and must- haves, while others were less important. The decision on whether to include these non-essential protocols depended on the possible extra complexity they would have added to the signature schemes and hardware constraints. With a clear view of all the properties and features (shown in Table 1.1) that thresh- 23 4. Methods old schemes should have, the existing protocols studied were re-evaluated again. The most suitable schemes were then selected to be further developed. This concludes the review of the literature for this project. 4.2 Reference Architecture Since the protocol for this thesis is intended for use in a vehicular environment, it is necessary that the vehicle specifications are suitable for such an implementation. In addition, depending on the car’s internal network communication, some of the communication might be too limiting for the protocol to be used effectively. There- fore, it would be beneficial to work with a predefined internal network, allowing the implementation to be adapted to some reference vehicles. The electrical system architectures of vehicles vary greatly depending on the man- ufacturer, type, and even configuration. As there is no generic architecture, we consider an abstract architecture with different domains. ECUs are separated into distinct domains based on their functionality. For instance, a powertrain domain can contain ECUs responsible for engine control and gear shift, while the infotainment domain provides functions such as a radio or navigation system [32]. For the sake of simplicity, an assumption like that is illustrated in figure 4.1. The vehicle consists of multiple local ECUs capable of executing minor tasks to reduce the load on the central ECU. The domain ECU manages all local ECUs in a particular section of the vehicle. Each domain ECU is linked to the central communication ECU, which provides external connectivity through the Telematics Control Unit (TCU). The TCU establishes connections with other vehicles and infrastructure using V2X communication and the Internet through cellular connections. These domain ECUs could serve as shareholders (and signers) in a potential threshold signature scheme, considering their direct connection to the central ECU, minimising the chance for faulty ECUs in between the connection to the central ECU. For intra-vehicle communications, CAN with a bandwidth capacity of around 1 MB/s [33] is traditionally used. But in modern vehicles, many other networks are integrated and used to enable communication between ECUs. One of them is Ethernet, which offers much higher capacity (up to 1 GB/s). For this project, it is assumed that all connections are implemented using automotive Ethernet. Ethernet is beneficial since it can handle network communication protocols like TCP, which can be wrapped with a security protocol [25]. 4.3 Implementation Some protocols work in theory but are impossible to implement or impractical to use because of certain constraints. Considering the goal of this project, which was to have a practical scheme suitable for automotive applications, the scheme needed to be implemented. A functioning implementation is crucial to evaluating the per- formance and usability of a developed protocol. Considering the lack of a simulated 24 4. Methods Figure 4.1: Internal car architecture environment compared to an actual vehicle, it was decided to implement the scheme, including network communication capabilities. Therefore, it was possible to simulate an actual implementation as accurately as possible. By releasing the code publicly anyone interested is able to contribute, add, or take inspiration from the code. 4.3.1 Programming Language Rust is becoming increasingly popular for cryptography, as it offers secure mem- ory management, reducing the risk of buffer overflows and other memory-related vulnerabilities and making it safer than other high-performance languages. Rust is designed to support concurrent and parallel computations and can run on most mod- ern hardware. Rust’s design allows it to map directly to the hardware, making it an efficient programming language because it can control memory representations and support stack allocation and contiguous record storage directly [34]. Several well- built and well-maintained cryptographic libraries are available in Rust. Therefore, it was chosen when implementing a proof-of-concept VATS scheme. 4.3.2 Libraries Implementing a cryptographical scheme requires algebraic operations performed in a finite field. To accomplish this task, Ed25519-dalek [35] was chosen. It is a fast and efficient Rust implementation of ed25519 key generation, signing, and verifica- tion. A proof-of-concept implementation of the project scheme is implemented in Rust using Risttreto over curve25519 as the group operations. Therefore, it makes significant use of the Ed25519-dalek library. The Dalek Library is frequently used for cryptographic schemes and is used in implementations of FROST and ICE-FROST, 25 4. Methods Ed25519-daleks implementation of correctness, safety, and clarity as a priority and a secondary goal of performance makes it a very suitable library for a scheme like VATS. Since VATS implementation is created to be a secure signature scheme but also feasible and measured to be practical, it requires security and performance. To effectively handle asynchronicity in communications between network partici- pants, Tokio was used. Tokio [36] is an asynchronous runtime for the Rust pro- gramming language that provides the functions necessary to write networking appli- cations. It is flexible and can target various systems, from large servers with dozens of cores to small embedded devices such as vehicle ECUs. Furthermore, Tokio helps to ensure that a functional network interface is present in the vehicle and adaptable to the internal network infrastructure of the vehicle (Fig. 4.1). At a high level, Tokio provides a few major components that make networking efficient and possible. • A multithreaded runtime to execute asynchronous code. • An asynchronous version of the standard library. • A large ecosystem of libraries. Also, as part of the underlining network to test the implementation of VATS, Warp was used to enable communication between participants. Warp [37] is a composable web server framework for creating a fast and reliable server and client communication. Warp is also adaptable to be used with TLS, where the user can provide locally stored keys and signatures. Since secure communication will be essential to the ECU’s internal communication, Warp with TLS enabled helps ensure that such communication is secure against man-in-the-middle attacks. In addition, Warp can use custom input certificates in its TLS communication, making it easy to provide it with a certificate authority made locally for testing and official certificate authorities used in real-world implementations. 4.4 Testing This project evaluates the practicality of implementing the scheme (VATS) in a vehic- ular setting with an automotive application in mind. The protocol’s functionality is tested in a simulated environment where the vehicle’s internal communication between different ECUs and external communication with cloud instances can be simulated. To simulate this environment, Docker creates Docker containers to run the applica- tion as an independent entity, just like an ECU in a vehicle. The advantage of using Docker is the ability to port applications to different machines and environments [38]. Each Docker container can be considered a possible ECU, and the communication between each Docker is similar to that of Ethernet connections in a vehicle. The scheme’s feasibility is evaluated through various measurements, such as execu- tion time, data complexity, and memory complexity. Multiple graphs are presented to show efficiency in vehicle architecture that allows greater or lesser numbers of 26 4. Methods ECUs, providing a perspective and allowing for discussion of the scheme’s practical- ity. These metrics are desirable to analyse: • Execution Time: The time the scheme took to perform various operations, such as key generation, signing, and verification, was measured. This metric provides information on the speed and responsiveness of the scheme in real- world scenarios. • Resource Utilisation: The utilisation of system resources, including data com- plexity and memory complexity was analysed in the implementation of the scheme. Understanding the scheme’s resource requirements helps evaluate its efficiency and potential impact on system performance. • Scalability: The scalability of the scheme was examined, considering an in- creasing number of participants or increasing data size. Scalability assess- ment is crucial to determine whether the scheme can handle larger workloads or accommodate a growing number of users without significant performance degradation. However, it is not the primary consideration during the scheme’s development because the vehicle has quite a few signers, according to the architecture in Section 4.2. The idea is to benchmark the performance of the scheme so that the evaluation gives an estimate of the scheme’s performance in a real-world application. These metrics and the choices for the number of participants (n) and the threshold (t) are inspired by other papers that perform similar measurements, such as ICE-FROST [8]. How- ever, ICE-FROST only benchmarked its key generation and signing. Whereas, in the case of VATS, benchmarking is intended to be conducted for several crucial com- ponents individually, therefore, having a more transparent performance evaluation. 27 4. Methods 28 5 Scheme This chapter shows in detail the preliminaries and description of VATS. A pseu- docode is also provided for clarity and ease of implementation. 5.1 Preliminaries Security parameter The security parameter is denoted κ, and is borrowed from the MuSig2 papers [6]. Nick et al. defined their security parameter as the result of one of their proofs and is described as: Sampling an element of a sampleable set S uniformly at random and assigning it to s can be denoted as s←$ S. For a randomised algorithm A, the operation of running A on inputs x1, . . . and random coins ρ, and assigning its output to y, can be represented as y ← A(x1, . . . ; ρ). If random coins ρ are chosen uniformly at random, the notation y ← A(x1, . . .) can be used instead. Given a GameA parameterized by the adversary A, we define the advantage of A in GameA as AdvGame A (κ) := Pr[GameA(κ) = true] How exactly these proof games work is given in the MuSig2 paper [6]. Group Description. A group description is a triple (G, p, g), where G is a cyclic group of order p and g is a generator of G. A group generation algorithm, denoted by GrGen, is a prime-order algorithm that takes a security parameter κ as input and returns a group description (G, p, g), where p is a prime number of κ bits. In this group, the group operation is multiplication, and group elements and their encodings are equivalent when passed as input to hash functions. Given an element X ∈ G, we use logg(X) to denote the discrete logarithm of X in base g. In other words, logg(X) is the unique integer x ∈ Zp such that X = gx. Selection of v. Choosing the number of v, the number of nonces to generate, can affect the scheme’s performance. So, it is beneficial to select a v as small as possible, but choosing v too small risks the protocol’s security, as proven in Section 6.2.3. In their paper, Nick et al. [6] mention that having [v = 2] saves multiexponentiation of size three plus single exponentiation, as well as three group elements of communication in the first round (all per signer). They proved in the reduction from the random oracle model that [v = 4] is secure, and in the random 29 5. Scheme oracle model with the algebraic group model that MuSig2[v = 2] is secure. Nick et al. state that they could not find evidence of choosing [v = 2] to be insecure and that it yields the best performance if one can accept the weaker proof (since the proof with an algebraic group model is strictly weaker than the generic group model, since it places fewer restrictions on the proof). Committee Selection. Choosing the proper committee to sign a document can significantly improve the signing process’s efficiency. However, limiting the pool of possible signers can be considered wasteful, and excluding specific signers could lead to confusion about their ability to produce a valid signature. In this protocol, the committee is randomly selected based on the credibility of the signers to gen- erate a correct signature. If specific signers do not sign, they lose credibility. To minimise communication traffic, the signing aggregator subjectively assesses each signer’s credibility, which is not shared with others. 5.2 Scheme Description In this section, we introduce the detailed description and pseudocode for the com- ponents in the proposed scheme VATS. The scheme needs n shareholders and a threshold t, where the algorithm is made such that it is from the point of view of the participant Pi, where 1 ≤ i ≤ n. 5.2.1 Setup In the setup with input 1κ, the setup algorithm runs (G, p, g) ← GroupGen(1κ), selects four hash functions (Hagg, Hnon, Hsig, Hupd) from {0, 1}∗ to Zp, and returns par := ((G, p, g), Hagg, Hnon, Hsig, Hupd). 5.2.2 Key Generation (KeyGen) Share Generation: A trusted dealer takes in two parameters, the number of signers n and a threshold t, and samples t random values such that (a1, ...., a(t−1))←$ Zt p. The dealer will also define the global public key as Y = ga0 ∈ G; this key will be the one certified by the OEM. Each participant will receive their share of the key depending on their index x, so f(x) will be sent to the participant x, similar to Shamir’s secret sharing scheme [10]. The dealer then creates commitments B := (ga0 , ..., gat−1) that are broadcasted. With the help of Shamir’s secret sharing scheme in this step, Threshold Tolerance is acquired, and with the commitments, VSS is achievable. Share Verification (ShareVer): Share verification helps ensure that each participant x receives their rightful share. This is done with the help of Feldman’s verifiable secret sharing [19], where the participant Pi can check with gsi =? ∏t−1 j=0 Bij j ; then they can be sure that the share is indeed the right one. Setting gsi = Yx, participant Pi gets their personal 30 5. Scheme public key and calculates the global public key B0 = Y . The verification of shares in this step can also be used for PVSS, since it can be calculated for anyone with a public key. An illustration of the key generation protocol is shown in figure 5.1. Figure 5.1: An illustration of (t, n) key generation and distribution scheme. 5.2.3 Committee selection The signing committee for each signing session contains at least t signers randomly selected from n participants. The signing aggregator keeps a record of how well each participant has performed in producing valid signatures. This performance metric is increased every time a participant successfully signs a message or decreased if the participant produces an incorrect signature. Participants with a higher performance metric have a better chance of being selected for the next signing session. In this way, we create a committee selection that is based on cheating scores. All participants have a chance to be selected and increase their score as long as they do not repeat producing incorrect partial signatures. It is possible for a participant to get excluded (due to their score being lowered) if they fail their signature frequently. 5.2.4 Key Aggregation (KeyAgg) The public keys of the selected committee are denoted by {Y1, ..., Yt} := L ∈ Gt. To create the coefficient ρi of key aggregators using the committee L and the public 31 5. Scheme key Yx, the coefficient is obtained for the participant x, with ρi through Hagg(L, Yx). The corresponding aggregated key for L is then given by ‹Y := ∏t x=1 Y ρi x ∈ G. In this way, creating a public key for that selected committee is possible. 5.2.5 Offline Signing Phase (SignOff and SignAgg) SignOff : Every committee member has the ability to perform the signing process offline and locally. Every participant creates j ∈ {1, .., v} random values ri,j ←$ Zp and calculate Ri,j := gri,j ∈ G. They then generate and provide v nonces, represented as (Ri,1, ..., Ri,v). SignAgg: Assuming that there are t participants, the aggregator obtains the re- sults (R1,1, . . . , R1,v), . . . , (Rt,1, . . . , Rt,v) from all participants. The aggregator then aggregates the results by calculating Rj = ∏t x=1 Rx,j for each j ∈ 1, . . . , v, and finally produces the output (R1, . . . , Rv). 5.2.6 Online Signing Phase (SignOn, SignAgg2 and Sign) Let Yi and si be the public and private keys of a specific signer, respectively. Let m denote the message that must be signed, {Y1, ..., Yt} be the public keys of the participants in the signing committee, and {Y1, ..., Yt} := L ∈ Gt represent the multiset of all the public keys involved in the signing process. SignOn: SignOn works as follows. First, the signer applies the key aggregation algorithm to compute ‹Y , and then stores its own key aggregation coefficient ρx := Hagg(L, Yi). Next, after receiving the aggregate first-round output (R̃1, ..., R̃v), the signer computes b := Hnon(‹Y , (R̃1, ..., R̃v), m). The signer then combines the message with the nonces to prevent replayability by setting R̃ := ∏v j=1 Rbj−1 j ∈ G. The challenge is calculated as c := Hsig(Y, R̃, m), where Y represents the signer’s public key. Additionally, the signer calculates Ri :=∏v j=1 Rbj−1 i,j ∈ G, so that the signing aggregator can verify the partial signature. To create their own unique signature, the signer computes their own Lagrange co- efficient λi = ∏t j=1,i ̸=j j j−i and then applies the formula: zi := c · (si · ρi + λi · si) + ∑v j=1 rbj−i i,j mod p. Finally, the output of the signing algorithm is the following, state′ i := R̃ ; out′ i := (zi, Ri). SignAgg2: The aggregator receives the output ((z1, R1), ..., (zt, Rt)) of all signers and verifies them by checking gzx =? RxY c(ρx+λx) x ∈ G for each signer, after reacre- ating the challenge c := Hsig(Y, R̃, m) and the individual ρx := Hagg(L, Yx) for each committee member. This check helps validate the partial signature of the signer x, thus identifying any cheating (providing individual accountability). Then, the signing aggregator aggregates the signatures by summing z := ∑t x=1 zx mod p. Sign: The signer receives z and returns the signature σ := (R, z). An illustration of the signing procedure is shown in figure 5.2. 32 5. Scheme Figure 5.2: The signing procedure is separated into two phases, online and offline phase. 5.2.7 Verification (Ver) Given the global public key, the multiset of all public keys involved in the committee {Y1, ..., Yt} := L ∈ Gt, the message m and σ := (R, z) the verifier is able to calculate‹Y by aggregating the multiset of public keys. The verifier can also recreate the challenge by running c := Hsig(Y, R, m). By adding Y and ‹Y the verifier creates Y ′ = ‹Y · Y such that, by checking the signature, gz =? R · Y ′c, the verifiers can be confident that the signature is correct for that specific committee. By having two keys, such that there is one public key for the committee (‹Y ) but also a public key for the original secret (Y ) this scheme achieves accountability for that committee in verification. 5.2.8 Key Update (KeyUpd) First Round: For each committee member chosen to participate in the key updat- ing protocol, each participant samples t random values such that (ai,0, ...., ai,(t−1))←$ Z. Each participant in the committee calculates a polynomial with their secret fi(x) := si + ∑t−1 j=i ai,jx j mod p for each n share. Now, each member must compute a proof of knowledge of the corresponding secret ai,0. First, by creating a nonce: k ←$ Zp, Ri := gk ∈ G 33 5. Scheme followed by a hash with a context string Φ selected at random from the signing aggregator, ĉi := Hupd(i, Φ, gai,0 , Ri) Then each participant makes ẑi, ẑi := k + ai,0 · ĉi mod p and generates, σ′ i := (Ri, ẑi) now each participant generates t − 1 commitments, creates −→ C i := (Ai,0, ..., Ai,(t−1)) and broadcasts −→ C i, σ′ i. Upon receiving −→ C x, σx from participants 1 ≤ x ≤ n, x ̸= i, the participant does the following validation for each received message: (Rx, ẑx) := σ′ x ĉx := H(x, Φ, Ax,0, Rx) aborting on failure by checking: Rx =? gẑx · A−ĉx x,0 Upon success, each participant deletes {σ′ x : 1 ≤ x ≤ n} Second Round: Each participant in the committee sends Px: (x, fi(x)) to the other n − 1 participants. Upon receiving (i, fx(i)), Pi verifies their shares by calculating gfx(i) =? ∏t−1 k=0 Axk xk mod p. The participant P1 then calculates si := ∑n x=1 fx(i) · λx mod p. where λi is the Lagrange coefficient corresponding to the participant Pi. Then the participant Pi stores si securely and deletes each fx(i). Yi := gsi ∈ G. Each participant can get their public key by calculating Y := ∏n j=1 Y λj j ∈ G. Moreover, any participant can calculate the public verification share of any other participant by calculating Yx := ∏n j=1( ∏t−1 k=0 Axk jk )λj mod p ∈ G. The key updating protocol ends with the outputs ski := si, pki := Yi. With the help of KeyUpd the scheme achieves PSS, such that new shares are renewed at decided intervals. 5.3 Pseudocode This section presents pseudocode for the proposed scheme. Algorithm 1: Setup (1κ) 1 (G, p, g)← GroupGen(1κ) // Select three hash functions: 2 (Hagg, Hnon, Hsig, Hupd) : {0, 1}∗ → Zp 3 par := ((G, p, g), Hagg, Hnon, Hsig, Hupd) 4 return (par) 34 5. Scheme Algorithm 2: KeyGen(t, n) // Sample t random values 1 (a1, ...., a(t−1))←$ Zt p // the secret is denoted by s 2 a0 = s // Create a global public key 3 Y = gs ∈ G // Use the t random values as coefficients to define a degree t− 1 polynomial, and index x of participants (1 ≤ x ≤ n) 4 for x := 1..n do 5 f(x) := ∑t−1 j=0 ajx j mod p 6 end // Dealer creates the commitments to be broadcasted 7 B := (ga0 , ..., gat−1) ∈ G // Send f(x) to each participant x, and broadcast B 8 return (f(x), B) Algorithm 3: ShareVer(B := (ga0 , ..., gat−1), f(i)) // Upon receiving the share, each participant Pi verifies its validity by evaluating the following 1 si := f(i) // on failure (bad share), request a new share from the trusted dealer by checking 2 gsi =? ∏t−1 j=0 Bij j ∈ G 3 ski := si 4 pki := gsi 5 pk = B0 6 return (ski, pki, pk) 35 5. Scheme Algorithm 4: ComSelect() // t signers are selected from n participants 1 P := (P0, ..., Pn−1) 2 Scores = (score0, ..., scoren−1) // Participants with higher performance scores are more likely to be selected. 3 L := (P0, ..., Pt−1) ∈ P // Start signing procedure with committee L 4 signing_successed = true 5 for j := 1..t, j ∈ L do // Evaluate performance based on partial signature verification in SignAgg2 6 if Pj’s partial signature verified then 7 Scorej = Scorej + 1 8 end 9 else 10 Scorej = Scorej − 1 11 signing_successed = false 12 end 13 end 14 if signing_successed is false then // Restart ComSelect() 15 end 16 return signature Algorithm 5: KeyAgg(L) 1 {Y1, ..., Yt} := L ∈ Gt 2 for x := 1..t do 3 ρx := Hagg(L, Yx) 4 end 5 return ‹Y := ∏t x=1 Y ρx x ∈ G 36 5. Scheme Algorithm 6: SignOff(v) // Each participant Pi generates v random nonces 1 for j := 1..v do 2 ri,j ←$ Zp 3 Ri,j := gri,j ∈ G 4 end 5 outi := (Ri,1, ..., Ri,v) 6 statei := (ri,1, ..., ri,v) 7 return (outi, statei) Algorithm 7: SignAgg(out1, .., outt) 1 for x := 1..t do 2 (Rx,1, ..., Rx,v) := outi 3 end 4 for j := 1..v do 5 Rj := ∏t x=1 Rx,j ∈ G 6 end 7 out = (R̃1, ..., R̃v) ∈ Gv 8 return out 37 5. Scheme Algorithm 8: SignOn(statei, out, ski, m, (pk1, pk2, ..., pkt), outi) // Signing must be called at most once per state. // Assemble parameters 1 (ri,1, ..., ri,v) := statei 2 si := ski, Yi := gsi 3 {Y1, ..., Yt} := (pk1, ..., pkt) 4 (R̃1, ..., R̃v) := out ∈ Gv 5 (Ri,1, ..., Ri,v) := outi ∈ Gv 6 L := {Y1, ..., Yt} // Recreating keys public keys to match signing 7 ρi := Hagg(L, Yi) 8 ‹Y := KeyAgg(L) 9 b := Hnon(‹Y , (R̃1, ..., R̃v), m) 10 R̃ := ∏v j=1 R̃bj−1 j ∈ G 11 c := Hsig(Y, R̃, m) // Creating the Lagrange coefficient 12 λi = ∏t j=1,i ̸=j j j−1 13 Ri := ∏v j=1 Rbj−1 i,j ∈ G // Calculating partial signature locally 14 zi := c · (si · ρi + λi · si) + ∑v j=1 ri,j · bj−1 mod p 15 out′ i := (zi, Ri) 16 return (R̃, out′ i) 38 5. Scheme Algorithm 9: SignAgg2((out′ 1, .., out′ t), L, m, R̃, Y ) 1 ((z1, R1), ..., (zt, Rt)) := (out′ 1, ..., out′ t) 2 {Y1, ..., Yt} := L ∈ Gt // Verification of partial signatures: 3 c := Hsig(Y, R̃, m) 4 for x := 1..t do 5 ρx := Hagg(L, Yx) // on failure, reduce participants score and abort by checking 6 gzx =? RxY c(ρx+λx) x ∈ G 7 end // Summing the shares 8 z := ∑t x=1 zx mod p 9 return (out′ := z) Algorithm 10: Sign(out′, state′ 1) 1 R̃ := state′ i; z := out′ 2 return (σ := (R̃, z)) Algorithm 11: Ver(pk, L, m, σ) 1 {Y1, ..., Yt} := L ∈ Gt 2 Y := pk ∈ G 3 (R, z) := σ ∈ G× Zp // Accountability ensured by recalculating ‹Y 4 ‹Y := KeyAgg(L) // Recreate challenge for verification 5 c := Hsig(Y, R, m) 6 Y ′ := ‹Y · Y 7 return gz =? R · Y ′c 39 5. Scheme Algorithm 12: KeyUpd(L, ski) // –––––––––-Round 1–––––––––––––- // Run by each member of L // Sample t random values 1 si := ski 2 (ai,0, ...., ai,(t−1))←$ Z 3 for x := 1..n do 4 fi(x) := si + ∑t−1 j=i ai,jx j mod p 5 end // Computes a proof of knowledge to the corresponding secret ai,0 6 k ←$ Zp 7 Ri := gk ∈ G // Φ is a context string to prevent replay attacks. 8 ĉi := Hupd(i, Φ, gai,0 , Ri) 9 ẑi := k + ai,0 · ĉi mod p 10 σ′ i := (Ri, ẑi) // Compute public commitments 11 for j := 0..(t− 1) do 12 Ai,j := gai,j ∈ G 13 end // commitment list 14 −→ C i := (Ai,0, ..., Ai,(t−1)) // BroadCast −→ C i, σ′ i // –––––––––-Verification of shares–––––––––––––- // Upon receiving −→ C x, σx from participants 1 ≤ x ≤ n, x ̸= i 15 for x := 1..n, x ̸= i do 16 (Rx, ẑx) := σ′ x 17 ĉx := H(x, Φ, Ax,0, Rx) // aborting on failure, by checking 18 Rx =? gẑx · A−ĉx x,0 19 end // Upon success, delete {σ′ x : 1 ≤ x ≤ n} 40 5. Scheme // –––––––––-Round 2–––––––––––––- // Pi sends 1 for x := 1..n, x ̸= 1 do 2 Send Px: (x, fi(x)) 3 end // Upon receiving (i, fx(i)), Pi verifies their shares by calculating: // abort on failure, by checking 4 gfx(i) =? ∏t−1 k=0 Axk xk mod p // Pi calculates: 5 si := ∑n x=1 fx(i) · λx mod p // where λi is the Lagrange coefficient corresponding to Pi. 6 Then Pi stores si securely, and deletes each fx(i). // Calculate and store public key: 7 Yi := gsi ∈ G 8 Y := ∏n j=1 Y λj j ∈ G // Any participant can compute the public verification share of any other participant by calculating 9 Yx := ∏n j=1( ∏t−1 k=0 Axk jk )λj mod p ∈ G 10 ski := si, pki := Yi 11 return (ski, pki, Y ) 41 5. Scheme 42 6 Proofs In order to provide a secure scheme, there needs to be proofs. Considering that other schemes inspire VATS, many of the underlying schemes are already secure; hence, this security carries over to the security of VATS. To clarify how exactly this is done, some proofs are given in this chapter. 6.1 Correctness The first criterion for a digital signature scheme to be usable is its correctness, which guarantees that under correct assumptions, the scheme produces a verifiable signature. This section goes over the correctness proof of the signature and the key updating scheme. 6.1.1 Correctness of Signature Assume the existence of all the preliminaries mentioned in Chapter 5. Then, the correctness of our VATS scheme can be proven by verifying that any subset L with at least t honest members can produce a valid signature on message m. A valid signature is a Schnorr signature that returns a true value when passed in as input to the verification method Ver defined in Chapter 5. Assume that there is an honest committee L, which has t members whose index i ranges from (1, ..., t). Since the signing committee L is honest, correct behaviour and communication between signing participants are assumed. This means the following assumptions hold: • Every participant follows and completes the algorithms in a reasonable time- line. • If the participant A sends a message to participant B, then B gets that mes- sage. Assume also that the vehicle in question has a pair of secret and public keys (sk, pk) where pk = Y . In order for function Ver to verify the signature and return true, equation gz = R̃ · Y ′c (6.1) 43 6. Proofs must hold. The right-hand side of the equation, RHS, could be expanded as follows: RHS = R̃ · Y ′c = R̃ ·‹Y · Y (6.2) Where: R̃ = v∏ j=1 R̃bj−1 j = v∏ j=1 g ∑t i=1 ri,j ·bj−1 = t∏ i=1 v∏ j=1 gri,j ·bj−1‹Y = t∏ i=1 Y ρi x = t∏ i=1 gsi·ρi Y = gs (6.3) The right-hand side equation 6.2 can be rewritten as: RHS = t∏ i=1 v∏ j=1 gri,j ·bj−1 · ( t∏ i=1 gsi·ρi · gs) c = t∏ i=1 v∏ j=1 gri,j ·bj−1 · t∏ i=1 (gsi·ρi)c · (gs)c = t∏ i=1 v∏ j=1 gri,j ·bj−1 · t∏ i=1 gc·si·ρi · gc·s (6.4) The left-hand side of the equation in 6.1, LHS is the aggregated signature and can be expanded, as shown below. LHS = gz = g ∑t x=1 zx = t∏ i=1 gzx = t∏ i=1 gc·(si·ρi+λi·si)+ ∑v j=1 ri,j ·bj−1 = t∏ i=1 gc·si·ρi · gc·λi·si · g ∑v j=1 ri,j ·bj−1 = t∏ i=1 gc·si·ρi · t∏ i=1 gc·λi·si · t∏ i=1 g ∑v j=1 ri,j ·bj−1 = t∏ i=1 gc·si·ρi t∏ i=1 gc·λi·si t∏ i=1 v∏ j=1 gri,j ·bj−1 (6.5) 44 6. Proofs Since signing participants hold shares generated according to Shamir’s algorithm [10], the original secret can be reconstructed with enough shares (equal or more than t shares) with the help of Lagrange interpolation. In other words, s = t∏ i=1 λi · si ⇔ gc·s = gc·( ∑t i=1 λi·si) (6.6) Equation 6.5 can be rewritten as follows: LHS = t∏ i=1 gc·si·ρi · t∏ i=1 v∏ j=1 gri,j ·bj−1 · gc·s (6.7) Based on equations 6.4 and 6.7, it can be concluded that equation 6.1 holds if all the signing participants in the committee L are honest. In other words, the generated signature is verified, and the function Ver returns true. 6.1.2 Correctness of Key Updating Assume that all the following preliminaries and assumptions described in section 5.1 are met. At least t honest participants in the network come together to form a committee L to refresh the share of all the signing participants. Assume that the vehicle has the secret key s, which is mathematically embedded in the aggregated signature to be verified against the respective public key Y during verification. Since there are t honest participants in the key updating committee, that committee can together reconstruct s and correctly perform the digital signing of any given message. Denote the secret share of each member of L as sx where x is the index of the respective participant. The following equation holds: s = t∑ x=1 sx · δx,0 = s1 · δ1,0 + s2 · δ2,0 + ... + st · δt,0 (6.8) where δx,0 is the Lagrange polynomial as defined in Section 2.1. According to VATS, Shamir’s secret-sharing technique is used to further divide each participant’s secret share sx into n share parts, which will be distributed among n signing participants later. Sharing is done so that using any t share parts, sx can be reconstructed with Lagrange interpolation, just like Shamir’s secret sharing. Notice here that each share sx is split into n parts. But reconstructing sx requires only the sum of at least t share parts with respective Lagrange interpolation. s1 = δ1,0 · s1,1 + ... + δn,0 · s1,n s2 = δ1,0 · s2,1 + ... + δn,0 · s2,n ... st = δ1,0 · st,1 + ... + δn,0 · st,n (6.9) 45 6. Proofs Equation 6.8 can now be rewritten as: s = δ1,0 · s1 + δ2,0 · s2 + ... + δt,0 · st = δ1,0 · (δ1,0 · s1,1 + ... + δn,0 · s1,n)+ δ2,0 · (δ1,0 · s2,1 + ... + δn,0 · s2,n)+ ... δt,0 · (δ1,0 · st,1 + ... + δn,0 · st,n) = t,n∑ i=1,j=1 δi,0 · δj,0 · si,j (6.10) After running the key updating scheme, signing participant x has the following share: sx = δ1,0 · s1,x + ... + δt,0 · st,x (6.11) Reconstructing the original secret can be done with the collective contribution of t out of n participants, as shown in the equation below. sgen = t∑ j=1 δj,0 · (δ1,0 · s1,j + ... + δt,0 · st,j) = t∑ j=1 δj,0 · t∑ i=1 δi,0 · si,j = t∑ i=1,j=1 δi,0 · δj,0 · si,j (6.12) From equations 6.10 and 6.12, it can be concluded that s = sgen. In other words, the reconstructed secret is the same as the original secret; hence, the signing scheme holds its correctness with the same s. In conclusion, the key updating scheme presented in VATS refreshes the shares of each honest participant without affecting the correctness of the generated digital signature. 46 6. Proofs 6.2 Security Proof 6.2.1 Random Oracle Model (ROM) The main property of the Random Oracle Model (ROM) is to provide a publicly available random function. The idea is that ROM provides all protocol parties with good and bad intentions with access to a public function h and then proves the protocol correct, assuming that h maps each input to a truly random output. Thus, it behaves like a genuinely random oracle [39]. In practice, h would be a hash function. In this sense, it’s viewed as a generator for perfectly secure hash functions. In proofs, the ROM provides heuristic support for actual security when a real hash function such as MD5, SHA-1 and SHA-256 would be used instead. The ROM enables security proofs for many schemes like MuSig2, as reductions can leverage the different properties of the ROM that can only be realized to a limited extent (if at all) in a standard model. 6.2.2 Discrete Logarithm (DL) / One-More DL The one-more discrete logarithm (OMDL) is an extension of the discrete logarithm (DL) problem, as introduced by Bellare et al. in their paper [40]. In the DL problem, the adversary is given a group element X and needs to compute its discrete logarithm with respect to a given basis group. In the OMDL problem, the adversary has more flexibility. It can request multiple challenges, denoted Xi, from the challenger. Additionally, the adversary has access to an oracle that can provide the discrete logarithm of any group element submitted by the adversary. The adversary’s objective in the OMDL problem is to compute the discrete logarithm of all the challenges Xi. In particular, the adversary must succeed in computing the discrete logarithm of at least one more challenge than the total number of calls made to the discrete logarithm oracle. OMDL allows the adversary to obtain multiple challenges and exploit an oracle that returns discrete logarithms. The goal is to compute the discrete logarithms of the challenges, ensuring success in obtaining one more discrete logarithm than the number of oracle queries made. 6.2.3 Simulating Signatures Nick et al. [6] demonstrate in their security proof about "The difficulty of simulating signature" how the first paper MuSig by Maxwell et al. [27], also referred to as "InsecureMuSig" is insecure since they claimed concurrent security under the one- more discrete logarithm assumption, but their proof turned out to be flawed. Details are mentioned in the forking lemma [41]. In MuSig2, the reduction process for handling the reduction is modified. It assumes a parameter v = 2 (number of nonces generated), indicating that the reduction will 47 6. Proofs receive two group elements, namely Ri,1 and Ri,2, as discrete DL from the OMDL during the initial round of each signing session. This change enables the reduction to perform two discrete logarithmic queries per signing session, allowing it to simulate signatures even if the adversary forces different signature hashes (c ̸= c′) in the two executions. By incorporating this modification, MuSig2 enhances the reduction’s ability to handle different scenarios and ensures the secure execution of the scheme. Considering the VATS scheme, the same type of nonce generation used in the key aggregation stage of the MuSig2 paper by Nick et al. is applied. This means that VATS solves the issue by having the signers effectively use the linear combination of Ri = Ri,1R b i,2 nonce, and thus get b := Hnon(‹Y , (∏n j=1 Rj,1, ∏n j=1 Rj,2), m). By programming the functions Hnon and Hsig appropriately, the reduction ensures that if the adversary responds differently in the second execution with c ̸= c′, the values b and b′ will also differ. This leads to two DL queries made by the reduction producing two linearly independent equations: zi = ri,1 + bri,2 + aicsi and z′ i = ri,1 + b′ri,2 + aic ′s′ i. These equations involve the signatures zi and z′ i, the nonce components ri,1 and ri,2. After the reduction has extracted si from the forgeries output by the adversary in the two executions, it can solve those equations for the unknowns ri,1 and ri,2, which are the discrete logarithms of the DL challenges Ri,1 and Ri,2. Similarly, in the case that c = c′, the reduction ensures that b = b′ and, thus, requires only one DL query to simulate the honest signer in both executions. This allows it to use the free DL query to obtain a second linear independent equation. The reduction would work equally well in the case where the adversary controls the signature hash computed as Hsig(‹Y , R, m) and instead is able to choose the message m or the set of signers in the committee L (not just c); thus being able to aggregate the key ‹Y after seeing the honest signers’ nonces. This enables the scheme to possess a preprocessing stage and broadcast the nonces without first choosing a committee and the message to sign. According to Nick et al., there is no evidence that v = 2 is unsafe. However, since the reduction needs to fork the adversary twice to support key aggregation, it needs to handle four possible executions of the adversary. Therefore, Nick et al. prove that using four DL queries as well as v = 4 is secure. Further clarification can be found in the MuSig2 paper [6]. 6.3 Reduction Proof A reduction proof is a powerful mathematical technique used to establish the rela- tive difficulty or security of two problems. By demonstrating that a solution to one problem can be used to construct a solution to the other problem, or vice versa, a reduction proof establishes the equivalence between the two problems. This tech- nique is particularly valuable for analysing the security of cryptographic protocols [42]. 48 6. Proofs C-MuSig2 challenger B-Sim Simulator A-VATS Adversary Figure 6.1: Reduction overview between MuSig2 and VATS In the context of VATS and MuSig2, a reduction proof is employed to establish the security relationship between the two protocols. This proof allows us to conclude that if an adversary can successfully win in VATS, they would also be able to win in MuSig2, consequently compromising the security of the OMDL problem, which MuSig2 reduces to. The reduction process involves mapping the actions of the VATS adversary, who believes they are playing and attempting to break the VATS game, to the corresponding actions in the MuSig2 game, guided by a simulator. This reduction process is visually represented in Figure 6.1. Through the reduction proof, we can confidently assert that VATS is at least as secure as MuSig2. It provides a formal justification for the security equivalence between the two protocols, reinforcing VATS’s reliability and trustworthiness within the OMDL problem’s broader context. 6.3.1 Programmable Random Oracle Model (PROM) One property of the ROM is programmability, where a random oracle can be imple- mented and output dynamically selected values that are still correct, where they are distributed uniformly on the specific range; any method for selecting these values is considered correct [43]. A Programmable Random Oracle Model (PROM) is used in this reduction. The PROM extends the random oracle abstraction by allowing the behaviour of the oracle to be controlled programmatically during the execution of cryptographic protocols. It enables dynamic adaptation of the oracle’s behaviour. The PROM is utilized in this reduction, where a simulator (B-Sim) can interact and manipulate all hash functions called by the adversary (A-VATS). This interaction enables the reduction of the VATS scheme to the MuSig2 scheme without the hashes used in the two schemes being different. By utilizing the programmability of the random oracle, the possibility of changing the hashes of A-VATS becomes simplified, such that A-VATS does not notice that the inputs that it receives from the simulator have been manipulated. 6.3.2 Theorem If MuSig2 is ECU-CMA secured in ROM, then VATS is also Game-VATS secure in the programmable random oracle model. We claim that for any probabilistic polynomial time (PPT) adversary A, there is a negligible function that | Pr[AGame−V AT S(κ) = 1]− Pr[BEUF −CMA(κ) = 1] | ≤ negl(κ) 49 6. Proofs 6.3.3 Description Before diving into the actual description of the proof, this is a quick reminder of some mathematical symbols’ used in our paper. zx = Partial Signature λx = Langrage coefficient ρx = Hagg(L, Yx) b := Hnon(‹Y , (R̃1, ..., R̃v), message) c := Hsig(Y, R̃, message) Here is the step-by-step description and algorithms in Section 6.4 of the interaction between the challenger, simulator and adversary. • Exchange of nonce commitments: The adversary calls Oracle SignOff() to ob- tain the nonce commitment of the honest party. The Simulator then queries the Oracle Sign() to the challenger and returns the honest party’s nonce com- mitment (1). The simulator holds on to the nonce commitment out1, which will be modified before returning it to the adversary. • The adversary