{'fraction_non_alphanumeric': 0.029370055232124197, 'fraction_numerical': 0.0060083594566353185, 'mean_word_length': 4.814059448904318, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Practical implementation of identification codes

Identification is a communication paradigm that promises some exponential advantages over transmission for applications that do not actually require all messages to be reliably transmitted, but where only few selected messages are important. Notably, the identification capacity theorems prove the identification is capable of exponentially larger rates than what can be transmitted, which we demonstrate with little compromise with respect to latency for certain ranges of parameters. However, there exist more trade-offs that are not captured by these capacity theorems, like, notably, the delay introduced by computations at the encoder and decoder. Here, we implement one of the known identification codes using software-defined radios and show that unless care is taken, these factors can compromise the advantage given by the exponentially large identification rates. Still, there are further advantages provided by identification that require future test in practical implementations.


I. INTRODUCTION
Shannon's transmission theory of communication [1] together with technological advancements have allowed unparalleled progress and increased the speed of information transmission. Much of this progress is still ongoing today [2] and only recently we started to reach its limits in some areas [3]. Shannon's transmission models apply in any setting where any of a given set of messages needs to be reliably transmitted from a sender to a receiver. While Shannon's transmission is widely general, and triggered an avalanche of applications beyond what was thought to be possible, there do exist other models of communication beyond it, like Post Shannon Theory [4]. One such example is identification [5], [6]. In identification, the goal is to allow the receiver to reliably verify whether he has chosen the same identity like the sender out of a given set of identities. In contrast, we would fall back into transmission if we required the receiver to reliably find which identity was chosen by the sender. Thus we can think of identification as a relaxation of transmission. Transmission codes satisfy the conditions of identification codes but not vice versa. The advantage is that as we move onto identification codes that do not allow for transmission, otherwise said, if we sacrifice the ability to decode at the receiver and only keep the ability to verify, then we find an exponential increase in the number of identities that we can reliably verify, which means a doubly exponential number of identities in the block-length of the channel [5]. While achieving this double exponential increase comes at a high computational cost, this result can be used also in the opposite direction where we can see an exponential reduction in the needed block-length compared to transmission for sets of identities and messages of the same size. Thus identification can potentially find application to control systems [7], watermarking [8], [9], automotive [10], recommendation systems [11], and in general any setting characterized by the need for quick or small checks, leading to unprecedented capabilities or reduction in congestion.
Here, we continue the study toward practical implementations of identification initiated in [11]. We take the composition of Reed-Solomon codes introduced in [12] as described in [11], and use it to perform identification across wireless communication. For most of the parameter ranges, our preliminary implementation and results suggest that different codes need to be used if the delay introduced by the identification codes at the sender and receiver crucially affect the key performance indicator of the applications. For a small subset of parameters, we find the identification code to be much faster and having end-to-end delays of the order of ms that, while slower, still comparable to those of transmission. For applications where delays of this size are acceptable, these identification codes might offer meaningful reductions in the transmission load. Still, the advantages of identification are not limited to potential reductions in the end-to-end delays. Identification reduces exponentially the load put on the communication network and allows for information-theoretic security to be implemented at comparable costs of computational security [13], and our hardware setup will provide us with the testing platform for these future works.
The paper is structured as follows. In section II we overview the identification problem, its coding, and the identification codes considered here. In section III, we analyze the scenario of multiple parties concurrently using identification. In section IV, we analyze the performance of the identification-code implementations and report our data. In section V, we describe the experimental setup before concluding the paper.

II. IDENTIFICATION
Identification can be reduced to transmission via a preprocessing step at the sender and a post-processing step at the receiver [5], which we can think of without loss of generality as a random "challenge" sent by the sender with identity i and verified at the receiver with identity j. In order to create the challenge, to each identity i is associated a function t i . The challenge is composed of a randomly chosen input r (the randomness) and the output t i (r) [6], which we call a tag [11]. This randomness-tag pair is the challenge and is sent to the receiver via a transmission code (to avoid transmission errors) which outputs r , t . The receiver with identity j then verifies the challenge by recomputing the tag on the received randomness r with t j , who concludes that j = i (accept) if the computed tag and the received tag are the same (t j (r ) = t ), and concludes that i = j (reject) otherwise. The collection of these functions is sometimes itself known as an identification code, since it alone defines the whole identification code if the channel is noiseless, we will thus refer to it as a noiseless identification code, or 0-ID code since it corresponds to ε 1 = 0 below. Formally, such an identification code looks as follow. Let R and T be integers and let M = RT . For an integer N , we let while for every other identity j the verifier accepts (v = 1) or rejects (v = 0) if he receives any of r, t j (r): Indeed, it was shown in [5], [12] that the false reject and false accept errors respectively satisfy where EW n V (v|i, j) := x n ,y n E(x n |i)W n (y n |x n )V (v|y n , j).
The reduction of the probability ε 1 of false rejects (concluding that the identities differ even though they are equal) is achieved by using better transmission codes, but the reduction of the probability ε 1 + ε 2 of false accepts (concluding that the identities are the same even though they are different) is achieved mainly by reducing ε 2 using functions that coincide on fewer inputs. The most important result in identification theory is that the capacity is doubly exponential and, in that scaling, equal to the Shannon capacity. Namely, for every error ε ≤ 1/2 lim inf n→∞ 1 n log log I(n, ε) = sup where I(n, ε) is the maximum size of (n, I, ε) identification codes, and where main difference to the transmission capacity is the use of log log instead of log in the calculation of the best finite rate. Moreover, given a capacity achieving transmission code, explicit constructions of capacity achieving identification codes are known [12]. The double exponential grows unimaginably fast; already at practical blocklengths the identification code sizes will be beyond the size of the universe. Regardless, it also means that for the encoder and verifier to access an identity, they need to access an exponential number of bits, which is already computational inefficient without counting any computation after that. However, the result can be used in the opposite direction too: for a given code size, we see an exponential reduction in blocklegth with respect to transmission. The challenge is then to actually show this potential advantage in a practical setting. As observed in [11] the noiseless identification codes are in one-to-one correspondence to error correction codes, by mapping each codeword c i to the function t i (r) = c ir outputting the symbols of the codeword when given a symbol location. A bound on the distance of the code is then a bound on the amount of collisions of the noiseless identification code and thus in the error ε 2 . Using Reed-Solomon codes, that are already themselves generated by the output of polynomials over finite fields, translates to using the sets of polynomials of a given degree as the functions corresponding to identities [8], [11], [12]. Here, we continue the study of the noiseless identification code introduced in [12], obtained by concatenating two maximal sizes Reed-Solomon codes. Let [q, k] RS be the Reed-Solomon code over the field of size q generated by the polynomials with degree less than k. Given parameters q > k > δ, we concatenate a [q k , q k−δ ] RS with a [q, k] RS to obtains functions from F q k × F q → F q , which we can call the concatenated Reed-Solomon noiseless identification code, or [q, k, δ] RS2 0-ID code for short. A challenge is thus composed of k + 2 symbols in F q , with k + 1 of them being randomness and only one being the tag.
Remark 1: We can view the composition of error-correction codes directly as a composition of noiseless identification codes. Namely, if Then a symbol is chosen by the randomness pair r , r as Proper functional composition is recovered if we consider the randomness itself a function on the codewords (i.e. r(c i ) := c ir ), then: The challenges of such concatenated noiseless identification codes then looks like namely a sequence of random inputs, one for each code in the concatenation, with a final concatenation-computed tag. Since the size of identities can be a drawback, such a trick can allow the tag to be computed as the identity is being streamed in the encoded/verifier, as is the case for Reed-Solomon noiseless identification codes.
In the following section we analyze the viability of identification codes based on the concatenated Reed-Solomon noiseless identification code.

III. MULTIPLE IDENTITIES
We can use the identities to encode data or identify multiple receivers, a positive verification can then be used to trigger further action. For example, we could use an identification code to hail a receiver among many, and subsequently the stream of status data from the identified receiver. However, not all such scenarios display an advantage over simply transmitting a unique string identifying the receiver. If all possible identities verify the challenge, then actually many of them will verify a false positive. Since the tag is the only thing differentiating the identities in the verification process, the average fraction of identities accepting a tag is exactly 1/T . Indeed, let I t /I be the fraction of identities producing the tag t at a certain randomness, then the average of the possible tags is exactly t I t /I/T = I/I/T = 1/T .
For the identification codes that we consider, the situation is even simpler: the fraction of identities that accept any given tag is exactly 1/T = 1/q. This means that for any n c number of challenges sent, the fraction of identities that will accept will be exactly 1/q nc , with only one of them being a true accept. This is a general property of identification codes created by maximum-distance separable codes, as shown in the observation below. This is verified as expected by the estimations of the collision probability in fig. 1.
Observation 2: Consider a linear code with a generator matrix G (generating codewords via left multiplication m · G), and n c positions for which the corresponding columns of G are linearly independent. Then the row span of these columns (i.e. the k × n c submatrix of G) is (F q ) nc . Also, if you multiply all possible length-k message vectors to this matrix, every vector in (F q ) nc appears the same number of times, more precisely q k−nc times (which is the cardinality of the left kernel of the k × n c matrix). For a Reed-Solomon code (or more generally for any maximum-distance separable code), any n c ≤ k columns of a generator matrix are linearly independent [14, Theorem 5.3.7, p. 237]. For the concatenated Reed-Solomon identification code used here each challenge is k + 2 symbols in F q , while a unique identity is determined by kq k−δ symbols. This means that while up to q identities can be uniquely addressed with a single challenge, and up to challenges can be generated before it becomes shorter to simply send the kq k−δ symbols determining the identity. Of course, in any scenario the penalty incurred by computing the multiple identities will degrade any advantage long before reaching this bound. Still, it means that we can recover the transmission capability of addressing doubly exponentially many identities at the same time by just sending an exponential number of challenges.
If the set of receiver is fixed, then identification cannot be an advantage over transmission in this multiple-receivers scenario. Indeed, for an advantage to exist the number of receivers must me at least M = RT and at that point the probability of false positive will be quite large (especially for identification-capacity achieving codes where R T ). Thus implementations such as [15] may not necessarily show an advantage without additional considerations.
Instead, identification might show an advantage if the set of receiver is a variable subset in a larger set of total possible receivers. Even the size of the set of receivers itself can be variable, since we can send multiple challenges to accommodate for a larger number of receivers. A number of challenges n c will see an average fraction 1/T nc of identities accepting all the challenges.

A. Use Case 1: Autonomous Driving
A scenario displaying variable receivers in variable numbers is the case of autonomous driving. Given the response time of an autonomous car and the amount of traffic, the number and the set of other cars that are relevant for consideration is variable. A fast identification code could allow for faster response times of the cars and prevent congestion and latency in future networks with many autonomous cars interacting with each other. The overhead incurred by the transmission of the randomness can be mitigated using time-or location based common randomness or pseudo-randomness. Much like one-time-password soft tokens, the randomness can be synchronized among all the senders and receivers, since no information about the identity is contained in the randomness. If all identities generate challenges on the same randomness, then by the birthday paradox this will increase the overall amount of false positives, thus a compromise between synchronized and transmitted randomness might need to be considered. The use of common randomness will be subject of future work.

B. Use Case 2: Next Generation Cellular Networks
Another scenario that could highly benefit from identification is the next generation, i.e., 6G, mobile cellular network, where the number of connected devices will increase manifold in comparison with 5G networks. By using identification, not only spectral efficiency but also security in the radio access network (RAN) can be further improved.
Under this paradigm, each user equipment (UE), regardless of whether it is a human or a machine, will be assigned an identity i, while its associated tag t i (r) will be used as a secure means for wireless communication with the base station (BS), similar to the classical identifiers assigned to handsets today, e.g., the International Mobile Equipment Identity (IMEI) and Subscriber Permanent and Concealed Identity (SUPI/SUCI).
In paging scenarios, the search for a UE within the subset of identities in a tracking area code (TAC) will be void of potential collisions caused by ε 2 if the NR Cell Identity (NCI) of a random BS in the TAC is used for generating the randomness r. Furthermore, the changing nature of t i (r) according to random NCI and TAC addresses the long-standing IMSI catching security breach in a more efficient way without employing computation-intensive encryption methods, such as the elliptic curve integrated encryption scheme (ECIES) in 5G.
As described in sections III-A and III-B, in such applications identification can exponentially reduce the load on the transmission network. However, if power consumption and latency are also key performance indicators, then the advantage of identification is dependent on whether the challenge generation incurs less latency or power consumption with respect to simply transmitting a unique identifier. The computation time of the concatenated Reed-Solomon noiseless identification code was considered in [11]. In the next section will expand the set of explored parameters and implement it on real hardware.

IV. SINGLE CHALLENGE
In this section we discuss and compare a single instance of identification against the corresponding transmission needed to send the whole identity. We consider [2 m , k, δ] RS2 0-ID code which generate a challenge directly composed of m * (k + 2) bits. The size of this noiseless identification code is the size of the first Reed-Solomon code, thus q kq k−δ = 2 mk2 m(k−δ) . Since a tag must computed both at the sender and at the receiver the computation time is doubled. In general, the computation of the tag results to be computationally time expensive, confirming the exponential growth observed in [11]. However, the Sagemath implementation using Zech's tables (blue data points) displays possibly advantageous computation times, which has been reproduced with standard deviations too small to discern in the graph. These tables, however, are only used for small sizes of m and k, namely for mk < 16 as displayed by the bottom figure. The computation time is compared to the time needed to send the unique identifier of an identity (green data points). A single challenge computation using Zech's tables is in some cases faster than simple transmission, however, due to the fact that the challenge must be computed twice, transmission is always faster than end-to-end identification. and thus mk2 m(k−δ) bits are needed to define an identity. Due to time constraints, we limit ourselves to instances with a challenge computation time of s · 10 4 ∼ 6h (cf fig. 2). The maximum number of identities achieved with this constraint is roughly 2 32 bits ∼ 4Gbits, achieved for m, k, δ = 13, 7, 5 for which the challenge is just merely 117 bits. In this respect, the identification code puts a practically undetectable load on the network. As displayed in fig. 2, this come at the cost of an exponential computational load at the sender and receiver. The parameter δ determines a trade-off between the computation time and the size of the identification code, for example the parameters m, k, δ = 13, 7, 6 halves the computation time but reduces quadratically the number of identities. Similarly for m, with the addition that m is also a trade-off between the challenge length and the false positive probability (which scales as k/2 m + 1/q δ [11, Eq. 45]). We compare the time spent generating and verifying the challenge (which for simplicity we calculate as twice the computation time of the generation) with the time needed to send the mk2 m(k−δ) bits of identity directly. In our implementation, we integrated the identification in the experimental setup, thus also transmitting the challenge. However, due to limitations between the software interfaces, this setup presents an overhead of few seconds, which will need to be improved in future work. Therefore here we compare the computation time of calculation of the challenge only, estimated offline. Even then, we find that simply transmitting the identity is always faster than performing identification. The concatenated Reed-Solomon identification codes have been implemented in Python using the finite field library offered by Sagemath, which uses three different C libraries depending on the finite field size. For binary fields of less that 16 bits, Sagemath uses Zech's table to speed up the computation. These are tables of logarithms for all the elements in a finite field, that can be used to speed up computation so that multiplications and additions will take approximately the same time. As shown in fig. 2, we find that for mk < 16, highlighted by the blue data points, the identification codes perform much faster than the other parameters, but most importantly its computation time is comparable, although slower, to the delay induced by transmission. Depending on the application, such small delay overhead might be justifiable in order to achieve the reduction in the load of the network obtained by sending these exponentially smaller challenges. For the largest of these identification codes we have identities of the size ∼ 64kbits with challenges of size ∼ 40bits.

V. EXPERIMENTAL SETUP
Our experimental setup consists of multiple NI USRPs 2954R software defined-radios (SDR) that are connected via a dedicated Local Area Network (LAN) with controllers where the challenge generation, signal processing, and hypothesis verification takes respectively place.
In order to demonstrate experimentally the advantages of identification in wireless networks, we deployed a downlink single-carrier transmission system, that has been implemented using a modular approach. Under this paradigm, the encoder has been abstracted at the transmitter side using an application programming interface (API) for the challenge generation based on a given input parameter m. The output of this operation is a variable-length code word containing the computed tag, t i (r), for constant values of k and δ.
This code word is next encapsulated into protocol data units (PDUs), which are individually sent over the channel using the frame structure shown in fig. 3. In order to minimize regular transmission errors, i.e., errors of the first kind caused by ε 1 , a preamble is attached to each PDU for countering negative channel effects at the receiver. Our setup uses a Barker code of length N sync = 13 for frame synchronization [16], that is repeated twice at the beginning of the preamble. For channel estimation and equalization we employ a Gold sequence of length N pilot = 128 [17]. The PDU size N PDU has been adapted according to the tag length. Once the frame has been assembled, its preamble is modulated using BPSK, while the QPSK is used for the PDU. The lower modulation order for the synchronization signals has been chosen in our system with the purpose of increasing the robustness in the communication. The modulated I/Q samples are pulse shaped using a square-root-raised-cosine digital filter before being upsampled as part of the digital signal processing (DSP) that takes place at the transmitter. The baseband I/Q samples are then converted into the analog domain by the SDR thanks to its 16-bit digital-to-analog converter (DAC). The analog signal is finally upconverted using the carrier frequency f c and sent over the channel. The steps at the transmitter have been illustrated in fig. 4. At the receiver end, the RF front-end of the SDR bandpassfilters the amplified received signal in order to attenuate potential image signals during downconvertion to baseband. The 14-bit analog-to-digital converter (ADC) is then responsible of delivering upsampled I/Q symbols at a rate f s to the DSP. We use phase-locked loop (PLL) based algorithms for carrier frequency and phase offset estimation before matched filtering. For symbol synchronization, a timing error detector based on the zero-crossing method [18] is used, while frame synchronization is done using a cross-correlation algorithm that exploits the autocorrelation properties of the Barker code in the preamble. Once the beginning of the frame is identified, the pilot symbols are used for phase ambiguity resolution. These are also used for channel estimation using a least-squares approach. The equalized symbols are finally demodulated into a bitstream that is fed for identification hypothesis evaluation. Fig. 5 depicts graphically these procedures.
At both transmitter and receiver ends, frame and signal processing are carried out in parallel to the actual transmission/reception in order to ensure a continuous operation, i.e. the former queues I/Q samples in a shared buffer that is periodically monitored by the thread responsible of the transmission/reception. Finally, table I summarizes the main configuration parameters used in our hardware setup for transmission delay measurements, which are shown in fig. 2. Our measurements have been performed by reading the SDR's internal clock state immediately before and after the transmission takes place.

VI. CONCLUSION
Identification promises potential exponential advantages for applications where transmission is not strictly necessary. This is reminiscent of the example of recommendation systems, where an exponential speedup is possible if one requires only just samples of recommendations rather than the whole recommendation vector [19]. However, for these advantages to be displayed the computation time introduced by the noiseless identification codes needs to be taken into account. We have seen that identification can incur exponentially large computation times compared to transmission, which can affect the viability depending on the application. In particular, we find the importance of fast implementations of the needed operations, which, when available, allow for time performances comparable to transmission and thus allow to achieve the exponential reduction in the transmitted traffic with small compromise. The use of Zech's table allows the concatenated Reed-Solomon noiseless identification code to achieve computation times comparable with transmission times, giving access to the advantages of identification with little tradeoff. However, these tables are not scalable to larger fields sizes, hinting that noiseless identification codes based on Reed-Müller codes might be the solution toward large identification codes using finite fields of limited size. Regardless, the small size of the tags and the independence of the identities from the randomness, opens identification to other advantages like the use of common randomness and information-theoretic security. Recently, some efficient functions have been shown to provide semantic security [20], which is necessary to provide security to identification. Thus, future work will be devoted to exploring the practical viability of these application and of more efficient noiseless identification codes.