PPP/PPP-RTK Message Authentication

3.1 Authentication Message Considerations

Message authentication adds bandwidth overhead, so we focus on proposals that can be accommodated in the current schemes—at least QZSS CLAS and Galileo HAS. We start from the premise that an ideal authentication scheme is one that provides the required security level and does not degrade user performance before adding authentication. For high-accuracy services, we focus on accuracy and availability, but in order to facilitate analysis, we use delta age of data (ΔAOD) and reception time, referred to here as time to retrieve data (TTRD).

The AOD measures the time elapsed between when the input for correction is available (e.g., the measurements to estimate the orbits or clocks) and when the orbit and clock corrections are applied in the receiver. The AOD depends on system latencies (measurement reception at the orbit and clock estimator, correction computation, uplink to satellites) that we assume are not affected by authentication, i.e., the system infrastructure has enough capabilities to almost-instantaneously perform any cryptographic operations. We, therefore, focus on increases in the AOD due to the transmission of the message from the satellite to the receiver and refer to it as ΔAOD. Notice that ΔAOD increases due to authentication, but ΔAOD does not only represent the increase due to authentication. The AOD-accuracy relationship is particularly important for clock corrections, as characterized in Hirokawa and Fernandez-Hernandez (2020) for GPS, Galileo, GLONASS, and BDS clocks, where it is shown that some satellites may have a clock error above a decimeter if the correction is one-minute old. We calculate ΔAOD on a per-message basis, i.e., if the receiver needs to receive more than one message (e.g., clocks and orbits separately) for a full position, ΔAOD is calculated for each of them:

1

where t_app,j is the time of the application of message j at the receiver, and t_tx,j is the message j transmission start time by the satellite. We select application time and not reception time, as in the case of delayed disclosure, the correction may be received but not applied until it is authenticated. For digital signatures, we do not make this distinction, and consider the application time as the time when both the message and the signature are available.

TTRD measures the time it takes to receive all the corrections, from one to multiple messages, allowing the receiver to compute a corrected position:

2

where j = 1, …, N, and N is the total number of messages to be received. When message authentication is added, TTRD is equivalent to the time to first authenticated fix (TTFAF; Caparra, et al., 2016) or time to first authentication (Kerns et al., 2014), with multiple messages possibly transmitted and received in parallel. For the case of HAS, two messages (one for orbits, mask, etc. and one for clocks) are received (N=2). This allows for the transmission of a short clock message that can be applied almost instantaneously, without waiting to receive other, more slowly varying information such as orbit corrections or satellite biases. For the case of CLAS, a message with the local atmospheric corrections is also included (N=3).

ΔAOD and TTRD are illustrated in Figure 1 for two HAS messages: slow, which uses 80% of the bandwidth, and fast, which uses 20% of the bandwidth. Two satellite streams are represented in two rows of pages, where each cell represents one page. A slow message is transmitted during 50 seconds, and then changes. The start of the fast and slow messages is represented by the thin dotted lines labeled Fast/Slow message frame start. The messages are 16 (slow) and two (fast) pages long—both have to be received—and each page counts for reception, thanks to the HAS High-Parity Vertical Reed Solomon (HPVRS) encoding scheme used (Fernandez-Hernandez et al., 2020a). The receiver starts up at a random point (Receiver ON), then receives eight slow message pages (four per satellite), then four fast message pages (two per satellite), and then it continues receiving the remaining eight slow message pages to complete the 16-page slow message and apply all corrections at the second bold dashed line (All messages applied). In this example, the time to retrieve the fast message was 5 seconds (TTRD_fast = 5 s), the time to retrieve the slow message was 10 seconds (TTRD_slow = 10s), and the ΔAOD for the slow and fast cases were 24 and 6 seconds, respectively, as shown in the figure. Note that, thanks to the HPVRS scheme, the receiver startup point (Receiver ON) may occur after the start of the slow message transmission, yet the message can be retrieved. This property also holds if the message includes authentication pages, as shown later.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 1

ΔAOD and TTRD for two messages (N=2): slow (blue) and fast (different shades of red/brown) on Galileo HAS message stream from two satellites.

ΔAOD and TTRD are correlated, but they are both analyzed for the sake of completeness. In addition, we look at the receiver computational complexity to verify authentication.

3.2 Cryptographic Considerations

We propose some design considerations for the cryptographic protocol in this section:

1. One-way asymmetry: The authentication mechanism must be one-way and asymmetric, as opposed to symmetric authentication, based on a secret key in the possession of both the system and the receiver. This is the case of all other satnav civil authentication schemes. This asymmetry can be obtained by using digital signatures that can be verified using public information only, but not generated without the private key, as for elliptic curve cryptographic signatures like the Elliptic Curve Digital Signature Algorithm (ECDSA) or EC-Schnorr, or by time-delayed asymmetry, where a message authentication code (MAC) is transmitted and, after some delay, the key to generate it. The latter is the case of the abovementioned TESLA protocol. TESLA is primarily based on symmetric cryptography for the generation of the authentication code but achieves asymmetric properties thanks to the delayed disclosure of the key.

2. Long-term security, short-term validity: The underlying cryptography must be considered secure for the long term, understanding long term to be 20–30 years. While updates are not discarded, satnav infrastructure has long lead times on the system side of several years. Also, some users may have restrictions to update their firmware or software with new cryptographic functions. For this reason, we focus a priori on 128-bit security levels (SL) for the cryptographic keys and, when a solution deviates from that, it is highlighted and justified. Note that, in contrast, some of the data authenticated is very short-lived: clock corrections degrade in a few tens of seconds. However, this should not be a driver for cryptographic parameters: First, the target of the authentication scheme is that no data is spoofed, no matter if it is short-lived or not. Second, the relevant attacks depend on the cryptoperiod of the secret key (i.e., the TESLA seed key or the ECDSA private key), which can last several years, rather than the validity of the MACs or the digital signatures. For TESLA, in addition to SL=128, we consider 40-bit MACs to be sufficient given that an attacker has a spoofing success probability of 2⁻⁴⁰ per attempt, and the attack is detected when unsuccessful. The sensitivity of TESLA MACs and key lengths to data spoofing is analyzed in detail in Fernandez-Hernandez et al. (2021).

3. Standards: To the extent possible, we focus on message authentication solutions based on current standards to facilitate implementation in the receiver and widespread use. When this is not possible, we propose standards under development or proposals in the literature that, while not standardized, we consider plausible. Note that the TESLA protocol is standardized as part of the International Standards Organization (ISO) lightweight protocol standard (ISO, 2018a) and also proposed in several Internet Engineering Task Force (IETF) documents, such as Perrig et al. (2005) or Fries and Tschofenig (2006).

4. Post-Quantum Cryptography: One of the challenges of designing long-lifetime cryptosystems nowadays is the quantum threat. The National Institute of Standards and Technology (NIST) is developing post-quantum cryptography standards (NIST, 2020b). Three finalists were selected: Dilithium, Falcon, and Rainbow. Out of these, Rainbow seemed to be the best candidate for GNSS as it offers the shortest signatures, down to 528 bits. However, new attacks are being discovered (Beullens, 2020, 2022) so what is considered a secure signature size is not yet fixed. Table 1 compares the three NIST finalists, recent candidate Short Quaternion and Isogeny Signature (SQISign) showing promise, and with a comparatively short signature, a Great Multivariate Short Signature (GeMSS), which is not a NIST finalist but was preselected in previous rounds. It proposes the shortest signature of all (282 bits for SL=128) and has been proposed for GPS’s NTS3 experimental satellite as its signature fits best with the GPS L1C message structure (Hinks et al., 2021).

The field of post-quantum cryptography evolves very quickly. New attacks are being discovered and old attacks are being improved by new insights on a monthly basis. These developments necessitate updates in the security parameters of the designs which, in turn, impact the key lengths and signature sizes. At the time of writing this paper, it seems premature to advocate for post-quantum algorithms in a GNSS specification. Also, a challenge of some schemes such as Rainbow and GeMSS is the long public key. This may have a high impact in over-the-air rekeying (OTAR) if the new public keys are transmitted in the clear. This challenge can be overcome by having public keys already pre-stored in the receiver, encrypted with a short, symmetric key that is transmitted at the time of application (Caparra et al., 2017). In the sequel, we will focus the performance analysis on pre-quantum schemes, and assume that at least some post-quantum schemes will be close in performance to ECDSA. Further details about post-quantum schemes for GNSS can be found in Neish et al. (2019b).

4.1 PPP Message Authentication Proposals: Galileo HAS

Galileo HAS defines flexible correction messages in terms of update rate and content. However, we focus on a basic standard configuration where there is a slow update rate message, including the satellite mask, orbits, and biases, updated every 50 s, and a fast update rate message, including the clocks, updated every 10 s, as shown in Figure 1. We will call the slow message with the satellite mask, orbit corrections, and biases MT1-orb, and the fast message with the satellite clocks MT1-clk. MT1-clk occupies two pages out of 10, and the rest is devoted to MT1-orb. Each HAS page is transmitted every second and has 448 bits—24 bits for the header and 424 bits for the body.

Table 2 presents the size of the MT1-orb and MT1-clk messages for a certain configuration, based on the Galileo HAS Interface Control Document (ICD; EU, 2022). The MT1-orb fits in 16 pages and the MT1-clk fits in two pages for corrections of Galileo and GPS, including four code and phase biases for Galileo and two code and phase biases for GPS.

We define two authentication proposals: one with digital signatures (DSs) based on current standards and one with a hybrid approach including a digital signature and TESLA delayed disclosure (DD). The proposals focus on the design choices that are more relevant for user performance. Aspects like key-authenticating-keys and OTAR are presented but not treated in detail, and will be looked at more closely in future work.

Digital Signature: This proposal is based on the ECDSA (NIST, 2013), although other signatures are possible, including Rainbow, as abovementioned, or EC-Schnorr (ISO, 2018b; Schnorr, 1989). We assume a 4xSL (security level) digital signature size. The message includes one digital signature for each MT1-orb and one for each MT1-clk. For the MT1-orb, one 424-bit page would be sufficient, as it accommodates 424 + 188 (spare) = 612 bits, enough for a 512-bit signature (SL=128 bits) of a P-256/SHA-256 ECDSA signature. However, this would only leave 100 bits every 50 s (i.e., 2 bps) for OTAR/key management (e.g., signed root key of the key chain). As a design choice, we propose two pages for a total of 1,036 bits, as shown in Figure 2. This allows a margin for OTAR and other fields.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 2

Galileo HAS message with digital signature (DS) authentication, including HPVRS encoding; OTAR is included in the two DS pages of the MT1-orb.

For the MT1-clk authentication, having one extra page would give 424 + 80 (spare) = 504 bits. This is not sufficient for a 512-bit signature. However, given that the MT1-clk is only two pages long, adding another two pages for authentication implies a 100% overhead. Then, a shorter signature of 448 bits from the ECDSA P-224/SHA-224 is chosen, providing SL=112, which might be sufficient. This requires two different public keys: one for the MT1-clk and one for the MT1-orb where, if needed, the MT1-clk 112-bit key can be updated more often. Currently, 112-bit security is the minimum acceptable security level value through 2030, per NIST (2020a), recommending 128 bits onward. If a minimum SL=128 has to be used, HAS flexibility allows for the provision of a clock subset message instead of a full clock set message, and updates the most stable clocks with the MT1-orb message. An optimized DS scheme could also just transmit one signature in the MT1-clk, signing both MT1-orb and MT1-clk, and leaving the MT1-orb unchanged. This approach is left for further work.

In summary, the HAS-DS approach adds two pages to the MT1-orb and one page to the MT1-clk, for a total of 18 and three pages, respectively, as shown in Figure 2.

Delayed Disclosure (Hybrid): This approach introduces a TESLA-like configuration. It is not obvious how to benefit from the advantages of TESLA for HAS, where most of the data is provided in a single message, transmitted by all satellites in view, for which a digital signature can be provided at a low overhead. The delayed disclosure is not ideal as, if the data is not used until authenticated, its ΔAOD increases. In order to overcome this problem, we apply an approach where, under certain constraints, some data can be used before it is authenticated. This approach is also under analysis for SBAS, where some messages need to be instantaneously applied (Neish et al., 2019a). For PPP, we can assume the following check is performed prior to using a clock correction:

6

where is the clock correction (a scalar) at time t_i for satellite s, K is a constant depending on the tolerable false alert probability (PFA), and σ_allan,s is the Allan deviation for period t_i – t_i–1. For example, K = 3.5 would allow a PFA below 0.02%, assuming a normal clock error distribution. For a period of 10 seconds and σ_allan,s (10s) = 1 cm, if the delta correction were above 3.5 cm, it would be discarded and the satellite set to not monitored at the receiver. Note also that, as few-cm errors cannot lead to a successful spoofing attack for most applications, large K values could be used. Also, to simplify the process, a generic σ_allan for all satellites, including the worst case, could be used as well. In that case, one could assume a constant threshold for all corrections:

7

where τ_clk is the clock update rate. In our case, and based on the use-then-authenticate approach, the delayed-disclosure protocol we propose is as follows: the MT1-orb is still signed with the DS. Then, the MT1-clk is authenticated via a TESLA chain, as shown in Figure 3. In our scenario, there are 504 bits available: 80 spare bits and 424 from a new page. They can be used for the MAC, the TESLA key, and key management data, as they are more than sufficient for MACs of up to 40 bits and keys up to 128 bits (for a total of 168 bits), which we consider to be secure for GNSS-TESLA. As OTAR mainly goes in the MT1-clk, we allow MT1-orb authentication in one page instead of two pages, as in the DS case. We assume the TESLA OTAR field includes the digital signature of the TESLA root key, and that all satellites use the same TESLA key chain.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 3

Galileo HAS message with delayed-disclosure (DD) authentication: MT1-clk is authenticated through TESLA and MT1-orb is authenticated through DS, which includes HPVRS encoding.

While our configuration cannot accommodate the 168 TESLA authentication bits into the spare 80 bits, other configurations might reallocate the clock corrections (e.g., through clock subset corrections, as mentioned above) to make them fit in, and then OTAR data should be placed in the MT1-orb message. We did not pursue DD optimizations in our work because DS performance seems good enough, as is shown later.

4.2 PPP/PPP-RTK Message Authentication Proposals: QZSS CLAS

QZSS CLAS also defines multiple correction messages named compact State Space Representation (SSR) based on Radio Technical Commission for Maritime services (RTCM) SSR (Cabinet Office, 2021). There are slow update rate messages including the satellite and signal mask, orbits, user range accuracy (URA), signal biases, and local atmospheric corrections (ionospheric and tropospheric delay) updated every 30 seconds, as well as fast update rate messages, including satellite clocks, that are updated every 5 seconds, as shown in Figure 4. For the sake of consistency with the previous section, we will call the slow message with the satellite mask, orbit corrections, and biases MT-orb, with an update rate of 30 seconds. The message with the local atmospheric corrections is named MT-loc, with an update rate of 30 seconds, and the message with the satellite clocks and an update rate of 5 seconds is MT-clk, per Figure 4. Each QZSS L6 message is transmitted every second and has 2,000 bits— 49 bits for the header, 256 bits for Reed-Solomon error correction data, and 1,695 bits for the body (Cabinet Office, 2021). QZSS CLAS defines the subframe with an update rate of 5 seconds as having 8,475 bits, and includes multiple compact SSR messages. The major-frame with an update rate of 30 seconds includes six subframes.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 4

QZSS CLAS message configuration page stream from one satellite: The blue parts represent MT-orb, the green parts represent MT-loc, and red parts represent MT-clk.

Table 3 presents the size of the MT-orb, MT-clk, and MT-loc messages according to the QZSS CLAS ICD (Cabinet Office, 2021). The parameters chosen for this example came from nationwide PPP-RTK services such as QZSS CLAS.

MT-orb requires 3,202 bits, which fits in the first subframe, and MT-clk requires 337 bits for each subframe, including corrections for 20 satellites (nine from GPS, eight from Galileo, and three from QZSS), and three code and phase biases for GPS, Galileo, and QZSS. The MT-loc atmospheric corrections of 5,575 bits include 12 areas with a total of 212 grid points.

As for Galileo HAS, we define two authentication schemes: digital signature (DS) and delayed disclosure (DD):

Digital Signature: This proposal is based on the ECDSA (NIST, 2013) as Galileo HAS. The change to the message consists in just adding a digital signature for each subframe including MT-orb, MT-clk, and MT-loc. In this paper, we assume that SL=128 is enough, and the 512-bit signature of a P-256/SHA-256 ECDSA is applied. For the data for OTAR/key management, we assume 804 bits, which is comparable to the Galileo HAS DS case. In QZSS CLAS, each 5-second subframe includes both slow corrections (such as orbit and/or atmospheric correction) and fast corrections (including clock), and we do not apply the shortened P-224 signature as for Galileo HAS. In summary, the CLAS-DS approach adds a DS for MT-orb, MT-clk, and MT-loc at the end of the first subframe, a DS for MT-clk and MT-loc at the end of the next four subframes, and a DS for MT-clk and MT-loc with OTAR and other fields at the end of the last subframe, respectively, as shown in Figure 5. The six digital signatures with a 512-bit length with OTAR and other fields require 3,876 bits for 30 seconds, or 129.2 bps. For the case of nationwide PPP-RTK, it consumes 63.3 bps to include the correction data for a satellite; the required data rate for authentication (129.2 bps) is approximately the same as the correction data for two satellites.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 5

QZSS CLAS message with digital signature (DS) authentication: OTAR is included in the last DS with MT-clk and MT-loc.

Delayed Disclosure: This approach introduces a TESLA-like configuration based on the use-then-authenticate approach, such as that used for Galileo HAS. Each subframe is authenticated via a TESLA chain, as shown in Figure 6. MACs of up to 40 bits and keys of up to 128 bits are included for Galileo HAS, and 804 bits are assigned for OTAR with key management for DSs. The required data for authentication is 1,812 bits or 60.4 bps—approximately the same as the correction data for one satellite.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 6

QZSS CLAS message with delayed disclosure (DD) authentication: Each subframe is authenticated through TESLA and OTAR is included in the last subframe.

4.3 Summary

A summary of the proposals is provided in Table 4, including the security bits, authentication bits, number of extra pages (HAS) or subframes (CLAS) per authentication, the authentication bit distribution in signatures, keys, MACs, and the rest (OTAR/spare), as well as the OTAR/spare bandwidth available.

5.1 Message Authentication Scenarios

We define three scenarios to test the impact of authentication in ΔAOD and TTRD. The scenarios are defined as a function of the number of transmitting satellites (of the PPP/PPP-RTK data) and page error rate (PER). The PERs are based on a land-mobile satellite model using experimental measurements described in Arndt et al. (2012), and then simplified for Galileo using conservative PER bounds as described in Fernandez-Hernandez et al. (2017). As the purpose of the analysis is to compare different schemes, we considered the model, even if simple, to be good enough for our purpose with one exception: The model did not take into account the previous state to determine the PER, which was just randomly allocated. In order to take into account error bursts, which occur often in environments such as those under study, a Markov chain for the PER determination should be added. We heuristically assumed a factor of three, i.e., after a message is lost, the PER would be augmented by three (e.g., from 20% to 60%), which is a way to model bursts for low PER values. The model in question is based on Fuller et al. (2000) and depicted in Figure 7.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 7

Markov chain burst model diagram

The Markov chain probabilities are related to the PERs as follows:

8

where PER takes the values of Table 5, and B is the Markov chain burst factor (B = 3). For each scenario (open sky [OS], urban [U], and hard urban [HU]), PER values were statically assigned per satellite according to Table 5 (e.g., every hard urban Monte-Carlo run would use two satellite-ground channels with PER values of 0.1 and 0.2). Notice that the PER value should be associated with certain signal power reception conditions and depends on the coding schemes implemented for each system: QZSS uses Reed-Solomon (RS) (Cabinet Office, 2021), and Galileo HAS uses HPVRS at the message level and a convolutional code at the page level. Also, the conditions presented are pessimistic, particularly the hard urban case for QZSS, given that at least one QZSS satellite is expected to be visible at the zenith in Japan. However, as our purpose is just to assess the relative impact of authentication under various conditions, we consider the model to be fit for its purpose— simple and broad enough.

The performance indicators TTRD and ΔAOD are calculated as follows: For each instance, a receiver in a given scenario (OS/U/HU) starts at a random point and collects messages until all corrections are received. The time elapsed is measured as TTRD. In addition, the ΔAOD values of both the clock (fast) and orbit/bias (slow) corrections (and local, for QZSS) are measured. A Monte-Carlo simulation with 10,000 instances is run for each scenario and authentication scheme combination in order to derive statistically meaningful results.

5.2 Other Schemes for Comparison

In addition to the DS and DD schemes, the scenario models a scheme without authentication as a reference, as well as a scheme named Full Delay Disclosure (FDD). The purpose of the FDD scheme is to illustrate the effect of a standard TESLA implementation (i.e., without the use-then-authenticate approach). As the reader may anticipate, this increases the TTRD and ΔAOD due to the disclosure time, especially in the case of HAS, but we provide it as a reference in the test results. For HAS, FDD is based on one extra page for the orbit message (i.e., 17 pages in total), with 30-s/10-s update rates for the orbit/clock messages, respectively, following a standard TESLA approach in which each message contains its MAC (not shown in the figure), and the next orbit message at the next 30-s interval contains the related key. The HAS scheme is shown in Figure 8. The CLAS case is similar, but with a DD of only 5 seconds.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 8

Full Delay Disclosure scheme for HAS based on a TESLA chain with a loose time sync requirement of 30 seconds, as well as MT1-Orb and MT1-Clk update rates of 30 s and 10 s, respectively

5.3 TTRD and ΔAOD Results

The TTRD and ΔAOD results for Galileo HAS are shown in Table 6 for the average and 95th percentile. The results show that, on average, the DS and DD schemes performed very closely to one another, and with only a small degradation with respect to the reference case, of about 1–2 seconds in open sky and urban environments, and up to 5 seconds in hard urban environments for the TTRD. The ΔAOD was degraded by approximately 2 seconds. This degradation seems affordable, especially for decimeter-level applications. The full probability cumulative distribution functions (CDFs) for Galileo HAS can be seen on the right side of Figure 9, while the left side shows the TTRD for all instances of all scenarios and schemes from which the statistics were derived. One can appreciate a slight degradation of DS with respect to DD, particularly for the hard urban case.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 9

Monte-Carlo simulations (left) and CDFs (right) for the TTRD including conditions of no authentication, DS, DD, and FDD, for the open sky, urban, and hard urban cases for Galileo HAS

Taking into account the similar performance of DS and DD, and that DD requires some assumptions on the data processing (use-then-authenticate) and loose time synchronization, DS seems to be a better choice. The main factor that can lean the design closer toward DD is computational cost, which is generally lower for symmetric operations, like MAC computations, than for asymmetric ones, like the ECDSA. In the following subsection, we analyze the differences in computational cost based on existing recent literature. The figure also shows a staircase shape in the FDD’s CDF for HAS. The reason for this is that the TTRD ends when the TESLA key is received (usually in 60 s), leading to a uniform TTRD probability distribution for each random start time and a staircase shape in the CDF. The FDD approach also causes a delay of at least 30 seconds for HAS with respect to the DS and DD cases.

The TTRD and ΔAOD for QZSS CLAS results are also shown in Table 7 for the average and 95th percentile. For QZSS CLAS, the results show that, on average, the DS and DD schemes performed very closely to one another in open sky and urban environments as they did for Galileo HAS, where the degradation with respect to the reference case was about 1–2 seconds. The performance was degraded for the hard urban case for the TTRD, where the degradation was up to 11 seconds. The ΔAOD was degraded by approximately 2 seconds, as it had for Galileo HAS. Because of the changes in the message framing, the QZSS CLAS case shows a slight improvement in ΔAOD-loc at 95% due to authentication, but a slight degradation in most other parameters and cases. The full probability CDFs can be seen on the right side of Figure 10, while the left side shows the TTRD of all instances for all scenarios and schemes from which the statistics were derived. The FDD approach also caused a delay, with respect to the DS and DD cases, of at least 5 seconds which is the time it takes to receive the TESLA key in the next subframe.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 10

Monte-Carlo simulations (left) and CDFs (right) for the TTRD including conditions of no authentication, DS, DD, and FDD, for the open sky, urban, and hard urban cases for QZSS CLAS

5.4 Computational Cost

The computational cost of ECDSA and TESLA authentication has been analyzed in Cancela et al. (2019). Table 8 shows the averaged CPU time for several devices, including portable ones, for the ECDSA and Hash-based Message Authentication Code (HMAC)-SHA256, which is used for OSNMA MACs and is representative of the delayed disclosure (DD) schemes here. The table shows that, with the selected processors, both operations are affordable, although as expected, the hash-based message authentication code (HMAC) operation was significantly lighter. GNSS receiver processors may have a lower clock rate, though, on the order of 100–200 MHz. Curran and Hanley (2019) show an average processing time of 49–26 ms for ECDSA-P224 and 84–180 MHz for Advanced RISC (reduced instruction set computer) Machine (ARM) processors, which could be representative of GNSS receivers. Also, Troglia et al. (2021) presents a detailed profiling of OSNMA crypto functions in ARM-based platforms, showing results in the same range.

Based on these figures, we assume that a high accuracy receiver can afford to perform ECDSA digital signature verifications at least once every 5–10 seconds without a significant increase in CPU load. In fact, Troglia et al. (2021) shows a computational cost of a standard per-second position, velocity, and time (PVT) computation, excluding carrier-phase processing and ambiguity estimation, for a 1.5-GHz ARM processor on a Raspberry device, of approximately 17 ms, while the ECDSA-P256 verification cost is below 1 ms. Note also that PPP/PPP-RTK receivers need to perform multi-frequency, multi-GNSS tracking including carrier-phase processing and possibly integer ambiguity resolution.

To complement the analysis of pre-quantum schemes, and leaving aside the recent attacks mentioned and their potential impact, Rainbow performs well compared to other postquantum schemes. According to the Rainbow submission documents, we have the following timings on an ARM Cortex-M4 processor running at 16 MHz: signature generation of 47 ms and signature verification of 15 ms. Therefore, the Rainbow signature verification cost also seems affordable for PPP/PPP-RTK receivers.