Jäger: Automated Telephone Call Traceback
David Adei Varun Madathil Sathvik Prasad Bradley Reaves Alessandra Scafuro

plain 
§ ABSTRACT 
Unsolicited telephone calls that facilitate fraud or unlawful telemarketing continue to overwhelm network users and the regulators who prosecute them.
The first step in prosecuting phone abuse is traceback — identifying the call originator. This fundamental investigative task currently requires hours of manual effort per call.
In this paper, we introduce , a distributed secure call traceback system.
can trace a call in a few seconds, even with partial deployment, while cryptographically preserving the privacy of call parties, carrier trade secrets like peers and call volume, and limiting the threat of bulk analysis.
We establish definitions and requirements of secure traceback, then develop a suite of protocols that meet these requirements using witness encryption, oblivious pseudorandom functions, and group signatures. We prove these protocols secure in the universal composibility framework.
We then demonstrate that has low compute and bandwidth costs per call, and these costs scale linearly with call volume.
provides an efficient, secure, privacy-preserving system to revolutionize telephone abuse investigation with minimal costs to operators.



  Aside from being a nuisance, illegal calls, like robocalls, are often associated with scams stealing millions of dollars each year. They are particularly detrimental to the financial safety of the vulnerable populations that fall prey to these activities. 
  Efforts made by law enforcement to trace illegal calls are manual and time-consuming, often taking several hours or even days to complete a traceback. In this paper, we present , 
  a provably secure system of protocols under the universal composability framework
  maybe replace with: "a system of protocols that is provably secure in the universal composability framework."
   We show that is feasibly fast and requires minimal resources in terms of CPU, Storage, and Bandwidth to handle over 10,000 calls per second across the network. With this tool and collaboration among phone providers, authorities can trace any phone call within a few seconds.
   I noticed that we do not mention any privacy property in the abstract. I am ok with it, I just noticed.


 

<ccs2012>
   <concept>
       <concept_id>10003033.10003106.10003113</concept_id>
       <concept_desc>Networks Mobile networks</concept_desc>
       <concept_significance>500</concept_significance>
       </concept>
   <concept>
       <concept_id>10002978.10003014.10003017</concept_id>
       <concept_desc>Security and privacy Mobile and wireless security</concept_desc>
       <concept_significance>500</concept_significance>
       </concept>
   <concept>
       <concept_id>10002978.10003006.10003013</concept_id>
       <concept_desc>Security and privacy Distributed systems security</concept_desc>
       <concept_significance>300</concept_significance>
       </concept>
 </ccs2012>


[500]Networks Mobile networks
[500]Security and privacy Mobile and wireless security
[300]Security and privacy Distributed systems security



[
    [
    
=====








§ INTRODUCTION






Telephone networks are inundated with unsolicited “robocalls” for telemarketing
or outright fraud. 
While individuals are bothered by the seemingly constant ringing of the phone,
government agencies, enterprises, and non-profits now have greater
difficulties reaching stakeholders for legitimate, desirable purposes.
Public outcry has motivated policy makers, public
officials, and phone providers to all take actions <cit.> meant to 
address the problem. 


Prior to the recent spate of incessant robocalls, the Federal Trade Commission (FTC) established the Telemarketing Sales Rule <cit.>
to set the bounds on what forms of automated calls are considered permissible.
A general summary is that callers
must have affirmative, opt-in consent from the called party to dial them for 
commercial purposes. The FTC also maintains a “do-not-call” list that 
should prevent unsolicited calls to registered individuals. These measures are
legal, not technical, so violations are pursued through regulatory
action. These measures have clearly not been effective.

In late 2019, a sudden outbreak of bipartisanship struck the United States
Congress, who passed the TRACED Act to combat illegal calling. Among other
measures, the law further expanded penalties for illegal calling and empowered
regulators to make substantial changes to network policy to reduce robocalls.
These changes to date have included requiring providers to register and submit
Robocall Mitigation Plans to the FCC, the mandatory blocking of calls claiming
to originate from invalid numbers, encouraging the labeling of suspect calls
by providers, setting deadlines on participation in robocall investigations, 
and mandating that all providers implement a call authentication mechanism
known as STIR/SHAKEN (). requires originating providers to sign
outbound call requests to indicate their actual source, similar to DKIM, expecting that it would allow regulators to identify the source of the call,
prevent caller ID spoofing, and give robocallers “no place to hide.”

In practice, all of these efforts have failed to significantly change the
state of affairs. Call labelling is unreliable, robocallers have moved to 
using legitimate numbers for a very short period, and the majority of calls in
the network arrive without a signature <cit.> because pre-VoIP networks cannot be
modified to support .

Robocallers continue to operate for a simple reason: it is profitable and low
risk. While regulators and law enforcement have been successful in winning
judgements against accused robocall operators, with fines into many millions
of dollars, the defendants often return to their schemes under assumed
identities or are replaced by other “entrepreneuers” using similar
techniques. Because the robocalling problem is so vast, it is reasonable to
assume that they will not face penalties given how painstaking it is to bring
a case against a single robocaller and how small the relevant agency staffs are.

One of the biggest hurdles is identifying the source of a call. The
telephone network is a network-of-networks, like the Internet, and a given
call often passes through many networks before reaching its
destination. Routes change rapidly and unpredictably, and
providers routing the call only know the previous “hop” and the next
“hop.” Fortunately, providers keep meticulous records on calls they
route for billing or paying peers. To identify the
source of a call, an investigator must start at the destination with
knowledge of the call time, call destination, and claimed call source, and go 
hop-by-hop until they reach the originator. This process is termed
traceback.

Prior to 2019, a traceback, could take multiple subpoenas and months to complete for a
single call <cit.>. The 2019 TRACED Act mandated the creation of a
clearinghouse to handle tracebacks, and it also mandated timely
responses to traceback requests by providers. The result was the creation of
the Industry Traceback Group (ITG) <cit.>, and the FCC reported to Congress that
currently a traceback can be completed in under 24 hours with the help of ITG.

Unfortunately, tracebacks are
still largely manual, and the ITG has a skeleton staff of a few employees.
They are (rightfully) proud that they manage to complete around 300
tracebacks per month, though this is far from sufficient
to deal with millions of robocalls each month. It will certainly become
a bottleneck if we want law enforcement to target perpetrators of high-touch
fraud schemes like digital kidnapping, where a fraudster provides a convincing
story and fabricated voice of the loved one of a target to extort a ransom.



Automation is needed to scale traceback to a significant fraction
of the current abuse, but simple approaches will be unacceptable to some
portion of current stakeholders. If each carrier were required to implement an
API for traceback, it runs the risk of a malicious carrier fabricating
incorrect responses. Note that some smaller carriers are known to skirt or
outright violate laws for profit, including facilitating illegal robocalls. If
each provider were required to submit their call routing records to a central
source, subscribers would justifiably worry that their social networks and
telephone activity could be leaked. Providers would balk at revealing 
peering arrangements and call volumes, and the central database would be a
magnet for curious intelligence agencies and law enforcement dragnets.



In this paper, we present [, pronounced “YAYger,” is German for “hunter.” It can also refer to Jägermeister, a popular liqueur, making it an appropriate name for a protocol to supplement .], a distributed system and protocol suite to
provide rapid, automated traceback for phone calls. To trace an illegal call, an investigator will obtain the caller's and recipient's telephone numbers along with precise timing details about the call. This information is typically sourced from public complaints, industry honeypots, the ITG's data collection, consumer voicemails, or other commercial channels. enables the investigator with the call details to identify its originating network. The originating network can then be held liable or identify the customer responsible for the illegal call. 


The key insight is to
allow traceback over encrypted call records, with the caveat that only a party
with detailed knowledge of the call can identify or decrypt the routing records for a given call. Our solution
requires no modifications to the existing telephone network. Instead, we
assume access to the billing systems that already maintain the records we
need. We do not require interaction between providers at any point. The
compute, storage, and bandwidth costs for providers are modest and scale
linearly with call volume, so small carriers need few resources. 
We provide
for cryptographic mechanisms to ensure that authorized traceback users can be
appropriately rate-limited to prevent bulk abuse. 
Our system is robust against
a single provider on a call who fabricates or does not submit a routing record
for a call. Encrypted call records do not reveal the provider who submitted
them, but a provider who submits an invalid or incorrect record can be
identified. 
Because the purpose of traceback is to identify the source of a call, we do not actually need every routing record for a call to be present in . Ideally, at least the first, originating record, will be present, but if it isn't, any other record will still improve traceback performance.
Our scheme will provide benefits even if some providers do not
participate, so it can be deployed incrementally.


We make the following contributions:




  * We specify and define the key properties and requirements for secure
   telephone call traceback.


  * We design protocols that meet the requirements for secure
traceback, and implement them in a prototype distributed system dubbed
. 


  * We provide formal guaranties by proving the security of these protocols in the Universal Composability
(UC) framework.


  * We demonstrate that has low compute and bandwidth costs per call, and these costs scale linearly with call volume. In the process, we
also develop a performant witness encryption library in C++. Code for that library and our full implementation is available <cit.>. 



Robocall enforcement is ultimately a legal problem, albeit with technical challenges. fills a technical need for effective investigative tools, though , cannot independently determine whether a call was illegal.
Nevertheless, because the telephone ecosystem is heavily regulated, honest participation can be incentivized through the risk of civil or criminal prosecution.

 

§ BACKGROUND






This section discusses background information on the state of the telephone network abuse and prosecuting violators. In doing so, we described challenges with locating abuse actors.



 §.§ Telephone Network Abuse




Phone network abuse is a global problem, with the United States being one of the most severely 
affected countries.
One of the most common forms of abuse is pre-recorded automated bulk phone calls, or robocalls.   
Many robocalls violate US law, including sales calls made without affirmative opt-in.
Fraudulent calls often impersonate government officials and steal millions of dollars from victims.

Federal statues prescribe eyewatering financial penalties for each and every illegal call,
but penalties require enforcement to deter abuse. Currently, 
phone abusers avoid prosecution by using spoofed or short-term telephone numbers, regularly
changing service providers, and altogether vastly exceeding available enforcement resources.







 §.§ Routing Phone Calls through the Network


Determining the source of a single call currently requires significant
investigative effort, and part of the reason is that the phone network
is a network-of-networks with no global vantage point and no single end-to-end
authentication of identity.

A given telephone provider will connect with one or more other providers to 
send and receive call traffic. 
When a subscriber places a call, her provider “originates” the call and then 
uses a signalling protocol to communicate with its peer networks to find a route
to the called party's network. When the call is finally set-up, over potentially many intermediate ,  the call is considered
“terminated” and the call audio will begin.

Call routes are selected considering carrier[In this work, we will use carrier and provider interchangeably.] charges, network maintenance, and agreements with other carriers, and these factors change moment-to-moment.
Each provider that carries the call will bill the provider who sent it, and Call Detail Records (CDRs) are kept to support this. However, only the originating provider knows any details about the call originator beyond the phone number the subscriber claimed when they set up the call.[Most businesses expect to be able to specify the “from” field shown for caller ID. A common case is to allow a desk line to appear to be coming from the corporate switchboard number, but this feature is abused by illegal callers.] No provider ever knows more about the call than the previous and next provider in the route. To identify a party responsible for an illegal call, an investigator must first find the originating provider, which is unknown to the terminating provider who delivered the call to its recipient.




This section provides an overview of a call between Alice and Bob, as shown in Figure <ref>.
In our example, the call path between Alice and Bob is illustrated with a red line from carrier P_1 (“originating carrier”), through P_2 and P_3 (“transit carriers”) to P_4 (“terminating carrier”) in Figure <ref>. 
When Alice dials Bob's number, her phone sends a call initiation request along with the dialed number to her Voice Service Provider.
This provider routes the call to Bob through the phone network.
The originating carrier often knows her true identity, but this information is not propagated within the call initiation signal being shared between the carriers involved.

Telecom operators have one or more connections with other operators, expanding the route options available to connect a call from the origin to its destination.
Each route may have a different cost based on carrier charges, network maintenance, and agreements with other carriers.
If Bob were on the same carrier's network as Alice, the call would be established on the same network (the process of connecting a call is called call termination).
Otherwise, the carrier interacts with neighboring networks (“transit carriers”) to find the optimal path to Bob based on the least-cost routing (LCR) policy. 
The LCR aims to minimize the cost of routing outbound traffic by considering factors like call rates, reliability, and inter-carrier agreements. 

Signal messages are exchanged between the participating carriers to establish and disconnect a phone call.
The messages are based on a call signaling protocol.
Common fields in these messages include the calling party's “claimed” number, the called party's number, the call timestamp, and other details.
Each carrier in the call path generates and stores Call Detail Records (CDRs) for billing purposes and as evidence of the call for regulatory compliance.

Each carrier[In this work, we will use carrier and provider interchangeably.], operating as an independent call processing entity, only knows the previous carrier it received the call from and the subsequent carrier it routes to.
This setting encourages competition, reduces complexity management, and prevents bad actors from mapping the entire network.
However, it complicates the process of identifying the originating point of a phone call (a process called traceback). 
To pinpoint a call's source, entities must iterate through each carrier, starting from the terminating carrier until they reach the originating carrier.
The following section describes the process of locating the source of illegal robocalls.





 §.§ Locating Abuse Actors


Authorities must find and prosecute perpetrators responsible for generating illegal calls.
In the United States, the TRACED Act of 2019 <cit.> requires the FCC to mandate the caller authentication framework. 
Although in principle S/S can be used to traceback illegal robocalls from their destination to their origin, there are several limitations.
Industry reports from October 2023 estimate <cit.> more than half of all voice traffic in the US is still not signed using S/S, making it impossible to track the origin of such calls using S/S information alone.
Industry insiders attribute this large portion of unauthenticated voice traffic to legacy infrastructure that does not support S/S. 
Furthermore, phone calls originating outside the US often do not contain S/S information since the framework is not mandated in other countries.
Therefore, regulators, enforcement agencies, and other entities rely exclusively on manual traceback processes to identify the source of illegal robocalls <cit.>.





 §.§ Manual Traceback Process


As the TRACED Act requires, the FCC has designated the Industry Traceback Group (ITG) <cit.> to serve as the central entity to coordinate the traceback process.
The ITG manages the labor-intensive and time-consuming tasks of identifying the source of suspected illegal robocalls.
The ITG constantly monitors active robocall campaigns using data from honeypots <cit.>, consumer reports, and other sources.
After assessing the legality of the robocall, the ITG initiates a traceback request and manually coordinates across numerous carriers to pinpoint the source of suspected illegal robocalls.
The traceback process involves tracing the call path from the terminating carrier through transit carriers and ultimately to the originating carrier to identify the source of the call. 

Traceback has proven to be a crucial tool for regulators and enforcement agencies to combat illegal robocalls. It has been used in almost every enforcement action filed by regulators against robocalling operations.
However, successfully completing a traceback often takes several hours or days, with substantial effort from the ITG and the participating carriers.
The manual and time-consuming nature of the traceback process significantly limits its effectiveness.
Although the volume of illegal robocalls targeting US subscribers is estimated to be in the hundreds of millions per year, less than 3,000 tracebacks were completed over eleven months in 2022 <cit.>.
By developing an automated, secure, and scalable traceback system, we can swiftly uncover the source of such calls, deter bad actors, and empower stakeholders to protect phone users from illegal robocalls.



 §.§ Cryptographic Primitives


This section introduces the cryptographic primitives that serve as the building blocks for our protocol. 


Witness Encryption Based on Signatures A Witness Encryption scheme based on Signatures (WES) was recently proposed in <cit.> and <cit.>. These are encryption schemes where the encryption key is a tuple of a signature verification key (denoted ) and a string chosen by the encryptor (denoted ℓ).  The decryption key is a valid signature (denoted σ) on the string, such that the signature can be verified by the verification key. 
More specifically, a witness encryption based on signatures has two algorithms - ., ., where .((, ℓ), m) →, and .(σ, ) → m. m denotes the plaintext, (, ℓ) corresponds to the encryption key, and σ = (, ℓ) corresponds to the decryption key if .(, ℓ, σ) = 1. Here (···) and .(···) are the sign and verify procedures for the signature scheme.  
We acknowledge that using signature verification keys to encrypt messages and using signatures to decrypt ciphertexts is not intuitive, and the notation can be confusing. Observe that we denote witness encryption and decryption keys as tuples containing signing and verification keys, while the signature keys are written as single variables. 
 <cit.> and <cit.> show that it is possible to construct such WES schemes efficiently based on BLS signatures <cit.>.





Group Signatures Group signatures <cit.> are a cryptographic primitive that allows group members to anonymously sign messages on behalf of the group. 
A designated authority, the group manager, generates a common public key  and issues a unique group member signing key _i for each group member i. Any signature signed by any _j in the group will verify with . The group manager can also deanonymize signatures and identify the signer. Group signatures allow for anonymity while maintaining accountability. 

Oblivious PRF A pseudorandom function (PRF)  F_k is a keyed function whose outputs look random to anyone without the secret key k. An oblivious pseudorandom function (OPRF) <cit.> is a two-party protocol where a server holds a secret key k for the PRF, and a client holds a secret input x to be evaluated. At the end of the protocol, the client learns F_k(x) while the server learns nothing.


























  



§ PROBLEM STATEMENT


We begin this section by identifying the major stakeholders and adversaries impacting . We also specify the functional and security requirements which we aim to achieve.



 §.§ Stakeholders and Adversaries


The ecosystem involves various stakeholders with distinct roles and interests, including service providers, the ITG, subscribers, and law enforcement agencies. Each group's goals and actions follow.

Providers They route phone calls through the telephone network. By law <cit.>, they are required to maintain the CDRs of each call and actively participate in the traceback process. They prioritize efficient record insertion and complete and correct traceback responses. Providers also desire the confidentiality of their customers, peering partners, and traffic volumes.

Subscribers Subscribers initiate and receive phone calls. They also report fraudulent calls to authorities or their service provider. Subscribers seek to minimize receiving illegal robocalls and expect confidentiality for their call records.

Industry Traceback Group The ITG oversees the tracing of illegal calls to their source by working with providers.
They prioritize swift and accurate responses to traceback requests.

Regulatory and Law Enforcement Agencies (LEAs) These entities work in conjunction with industry stakeholders to maintain secure and lawful communication networks. Their responsibilities include investigating suspected illegal calls, enforcing compliance, public education, and policy development. LEAs often submit traceback requests to the ITG,  emphasizing the need for a timely response.

Adversaries
Adversaries may seek partial or full call records of one, many, or all subscribers. They may also seek  privileged information about providers or the network structure. They may also aim to violate the integrity or availability of to prevent detection or investigation of illegal calls.
Adversaries can include outside parties like private investigators<cit.>, identity thieves, or even foreign intelligence agencies<cit.>. Insiders, including subscribers, providers, regulators and LEAs, and operators of entities may also
behave dishonestly at any point. We design such that no single compromised entity alone can violate its security properties, and in many cases is resilient against collusion by more than one malicious entity. 



 §.§ Requirements


The main objective of is to enable secure and efficient traceback given a valid request containing source and destination telephone numbers along with the call timestamp.

Functional Requirements To achieve this objective, the system is designed with the following key requirements: 


    
  * Resilience: A valid traceback request returns all available records for a call.
    
    
  * Precision: A valid traceback request only returns relevant records. Malicious or incorrect records are still “relevant” if they match the traceback request. 

    
  * Scalability: must handle effectively arbitrary call volumes. For all entities, cost should scale linearly in the number of calls and/or participants (as appropriate). 

    
  * Efficiency: All operations should perform comparably to similar non-secure approaches. The financial costs should be a minor fraction of the total network revenue. 

    
  * Information Gain: Every traceback request should provide information to an investigator. A traceback request will result in one or more of the following:
    
        
  * Identify the originating provider for the call.
        
  * Reveal at least one claimed non-originating provider and shorten manual traceback.
        
  * Provide direct evidence that one or more providers act in bad faith (e.g., submitting false or contradictory records or no records for a call).
    
    In settings where is mandatory, all of these properties are obvious. Either one obtains a complete and consistent traceback, or at least one provider is violating the mandate. In partial deployment, these properties will still hold if at least one on-path provider participates.


Security Requirements 
The guiding principle of secure traceback should be that no entity gains information about subscribers or providers in the absence of an authorized traceback request, even in the presence of a compromised entity.
Additionally, no entity can provide false information without risk of detection and accountability. More formally, this mandates the following principles:


    
  * Trace authorization: An entity can only trace a call
    they have definite knowledge of, and they must also have
    explicit authorization from a third party.

    
  * Call confidentiality: No entity should determine source, destination, time, or route details about a call they do not already have without authorization for a traceback. 

    
  * Trade secret protection: No party should learn aggregate information about a provider's call volumes and peering relations except those revealed by an authorized, valid traceback or an authorized accountability request. 

    
  * Record integrity: Only authorized parties may contribute records.

    
  * Record accountability: It must be possible to identify the contributor of a traceback record. 


CDR metadata are inherently sensitive. They can disclose significant details about the communicators' relationships, potentially making them targets of focused observation <cit.> or widespread surveillance by intelligence agencies <cit.>. It is imperative to protect the privacy of individual callers. In the phone network, call paths constantly change, and no single entity has complete knowledge of a given call's path. This opaque visibility protects the network from abuse as call paths reveal information about inter-carrier peering relationships. CDRs could be used to construct call graphs. A direct connection between two network nodes trivially signifies a inter-carrier peering agreement. The phone network is a competitive environment; even partial knowledge of inter-carrier relationship or traffic patterns can be exploited for unfair practices such as undercutting prices, manipulating market dynamics, or degrading services on certain routes to impact competitors. An automated traceback solution must ensure confidentiality of inter-carrier relationship and network trends. Additionally, any collaborative computer system has other security concerns, including compromised parties, data breaches, insider threats and collusion. We therefore formulate that a secure traceback system should meet the following security requirements: 



    
    
  *  Record confidentiality: The route (the “hops”) of a call can only be viewed by authorized parties.
    
    
  *  Privacy of individual callers: Information about a call (sender and receiver, time) can only be learned by the carriers involved in routing the call and no one else.

    
  *  Blind network trends and provider relationships: 
Confidentiality of inter-carrier relationship information and network volume information should be maintained.
    
    
  *  Carrier Anonymity and Accountability: No single entity can link a provider to their contributions to a traceback request from their records alone. However, if tracing reveals that contributions are malformed, the responsible carriers should be identified. This requirement is necessary for blinding network trends.


The insight to these requirements is that no new information other than what the parties already know should be revealed.






 

§ OUR APPROACH



In the previous section, we specified requirements for secure traceback.
To show how satisfies those requirements, in this section
we will describe a functional but insecure strawman solution and iteratively improve it until it meets all of the security requirements.



 §.§ Overview


An Insecure Strawman Approach
To enable traceback, we first introduce a central Record Store() that collects and stores Call Detail Records (CDRs) from  in a database . Any  P_i in a call path, for instance, P_1 → P_2 → P_3 → P_4, already keeps a CDR for each call they originate, transmit, or terminate. We model a CDR  as a tuple  (, , _i,  P_i-1,  P_i,  P_i+1) and further divide it into two parts: = (_i) and = (P_i-1P_iP_i+1), 
where in ,  and  are source and destination telephone numbers common to all providers in the call path, _i(unique to P_i) is the time at which P_i receives the call and = (P_i-1 P_iP_i+1) are the previous hop, current hop and next hop respectively. Phone call setup takes time to traverse through the network, and we assume an upper-bound setup time . Any CDR pertinent to the same call will have a ^* in the range of [_i - , _i + ].

To enable traceback, each  P_i contributes by sending command  (, P_i, , ) to the .
The  will then add the record to their database . 
Later, if a party wishes to trace a certain call with = (_i), they can send
the command   to , who will fetch all hops that have = (^*), ∀^* ∈ [_i - , _i + ].  


Modeling a _i for a  _i as (P_i-1P_iP_i+1) allows _i attest to their upstream and downstream 's involvement in the call. This means that given a _2 from only P_2, we know the path P_1 → P_2 → P_3, so a traceback does not necessarily require records from P_1 and P_3. This design decision helps in partial deployment.

In the event of conflicting hops, for e.g., say P_2 submits _2 = (P_1  P_2  P_3) indicating P_1 and P_3 as its previous and next hops. P_1 submits _1 = (P_4  P_1  P_3). P_3 submits  _3 = (P_1  P_3  P_6). In this case, an investigator cannot tell if P_2 is misbehaving or P_1 and P_3 are misbehaving. Therefore the investigator will go to each of these  and have them show their corresponding call records to identify and punish the misbehaving (s). 


This strawman solution trivially meets the functional requirements of the system, but none of the security requirements we described in Sec. <ref>. Indeed, since records are stored in the clear for , no confidentiality is guaranteed to subscribers or . Furthermore, traceback could be done by any party with access to the records.

Toward Record Confidentiality 
To achieve record confidentiality, the first natural step is to encrypt the  and the . Assume all  use a shared public key () to encrypt the  and  using an IND-CPA secure encryption scheme.
This means that will store a set of ciphertexts, and hence cannot learn anything about the CDR content.
This guarantees the confidentiality of the records but unfortunately prevents the tracing process. Suppose an authorized party P_j wants to trace call  = (_j), they must send an encryption of  under  to . However, the cannot find a matching record in the database, since the encryption scheme is not deterministic. 
Alternatively, the sends all the ciphertexts in the database to P_j, and the latter decrypts each ciphertext until it finds the call records pertinent to their call. This approach is inefficient and loses call confidentiality for other calls. 
To solve this problem, we introduce a deterministic index to identify ciphertexts related to a given . Now upon receiving this index, the can return exactly one ciphertext to the . We elaborate on this below. 


Adding Pseudorandom Labels to the Database
To identify the correct ciphertexts, we index each entry with a label, , that can be computed only with the knowledge of . When a  P_i sends their contribution, they will send a pair (_i, ctx_i) to the where ctx_i is an encryption of _i by P_i. Later, when a party  P_j wants to trace a call =(_j), they can use this information to compute , and will be able to identify the ctx that is indexed with . Note that P_j will compute all  ^* for = (^*) ∀^* ∈ [ - ,  + ] to retrieve all possible ciphertexts that belong to the call as specified earlier.



What function should we use to compute ?
Perhaps the most natural candidate would be a hash function, i.e., = H(). 
However, this approach jeopardizes the confidentiality of the records once again. Indeed, anyone who gets access to the database  maintained by can “check” if a certain call () took place by simply computing the hash of the call details and checking for that label in .
Adding a large nonce as input to the hash function i.e. = H(nonce) is not helpful since during trace the   will have to guess the nonce and this is infeasible in polynomial time. 

This attack suggests that the label should not be computed using a public function that anyone can compute. Pseudorandom Functions (PRF) are the perfect candidate. They are deterministic, just like hash functions, but they can be evaluated only with the knowledge of a key.
A label can be computed as = F_k(), where k is a key known only by the   and F is a PRF.
Hence, no one else, except carriers, can compute labels.
However, this solution is not robust in our threat model, where could collude with  .
Indeed, it would be sufficient for only one   to leak the PRF secret key k to expose records.

We solve this problem using a cryptographic tool called an Oblivious PRF <cit.>  (OPRF). 
In an OPRF, the PRF is evaluated through a protocol between two parties: a server, who knows the key k, and a client, who knows the input x. At the end of the protocol, the client learns only the output of the PRF, while the server learns nothing.
In our system, we introduce a new party called the Traceback Authority (denoted ), which holds the secret key of the PRF and allows the   to evaluate the PRF to compute labels. The , however, does not learn anything about the . 


To contribute a record, P_i will interact with the to compute _i from , and then compute _i=H(_i).
Next, P_i will encrypt the _i under  into ctx_i (as specified earlier) and submit (_i, ctx_i) to .  The lookup index _i is a hash of the _i so that if a record and/or the OPRF key is ever compromised, the _i is not directly exposed. 

Traceback would work as follows: An authorized party P_j  who wants to trace   first obtains the label _j from , then sends _j = H(_j) to . will use _j to identify and return the corresponding ciphertext.



However, there is still a problem:  
Recall that all ciphertexts are encrypted under the same key. Thus any   (potentially unauthorized) colluding with the can potentially decrypt all ciphertexts trivially. 
Conversely, if each   encrypts its record using a unique key, the party attempting to perform a traceback will obtain ciphertexts under different keys, requiring all  to help with decryption. This defeats the purpose of the system. 


Towards Encrypting Records
One potential solution is to have  encrypt using the 's public key.  Thereafter, during the traceback, the   retrieves the ciphertexts from the and interacts with the to decrypt the ciphertexts.
While this is a viable solution, we want to formally enforce the following properties:  

    
  * Knowledge of call: A party can trace a call only if they were part of the call i.e they already know the . The party must be a  in the call path.
    
  * Trace Authorization: A party can trace a call only if they were authorized by the to trace that particular call.


To this end we use an asymetric encryption scheme called “witness encryption” that allows carriers to encrypt the  such that only with the knowledge of the  and an authorization from the can they decrypt the ciphertext. 
In witness encryption, the encryption key is a verification key  for a signature scheme and an arbitrary string ℓ (chosen by the encryptor). A ciphertext can be decrypted only with the knowledge of the string ℓ and a signature on ℓ that verifies under .
In our case, we replace ℓ with  to enforce property (1). We enforce property (2) by requiring a signature on  signed by the . 

Now to contribute records, P_i will compute _i, _i = H(_i) and encrypt _i using (, _i) as the encryption key. Then P_i will send (_i, ctx_i) to . Using hash digests as indices instead of s further enforces property (1) above. Since the is not part of the call path, it should not know the .



Once the ciphertexts are retrieved from the , P_i must request authorization from the , in our case, a signature on . This construction ensures that a ciphertext related to a call can be decrypted only by someone who knows a valid signature on the corresponding . 









Adding Carrier Anonymity and Accountability Recall that to contribute, each  sends authenticated encrypted records signed under their unique public key to . The can map their contributions to their identity, potentially learning trends about their activities. On the other hand, we cannot simply have the  submit their records anonymously since we still need to hold them accountable for malformed or falsified contributions. 
 
To protect carriers' business privacy but hold them accountable, we replace the regular signature scheme (used for authentication) with an anonymous group signature scheme. 

Group signatures are anonymous signatures that can be validated on behalf of a group – in our case, the group of all carriers. More importantly, we choose group signatures instead of primitives like ring signatures because group signatures are efficient and allow us to trace traitors. Here, we use group signatures only for authenticating contribution requests and not for the witness encryption scheme. 

In our system, the plays the role of the group manager and adds carriers to the group by assigning them group secret keys. Moreover, the is also responsible for the deanonymization of the group signatures in case any of the carriers submit bad requests. 

Network Layer Anonymity
The group signature scheme for authenticating contribution requests guarantees anonymity at the application layer. Unfortunately, network features like IP addresses may still identify . There are a number of solutions to this problem that are orthogonal to , including proxy services like commercial VPNs. A  may still be concerned that IP traffic volume might leak information about call volumes to the proxy.  Providers can address this issue by splitting their traffic across multiple proxy services and/or  transmit redundant or invalid records as  cover traffic. 




 §.§ Threat Model and Resiliency


mandates the security requirements outlined in Sec <ref>. 
The system includes two entities besides providers: the and the . 
We assume that the and the do not collude and only one of the two entities may be malicious. We also allow collusion between and the corrupt entity. We show that even when the is malicious and is colluding with providers, none of the security requirements are violated. On the other hand, when the is corrupt, cannot guarantee record accountability. 

We can improve the trustworthiness of the with several orthogonal techniques, described below. All of these options are feasible, but they add complexity and cost.

Splitting responsibilities In the architecture of , the is responsible for group management, label generation, and authorizing traceback.
Assigning these jobs to different entities will limit the damage should one be compromised, and our prototype actually already implements them independently. 

Distributing Trust
Each of the operations can also be split among multiple entities using existing multiparty computation schemes, including threshold constructions of OPRFs<cit.>, group signatures<cit.>, and BLS signatures
for use in Witness Encryption. 


An Additional Layer of Protection In our threat model, we model the record store and the traceback authority as non-colluding entities. Consequently, we prove security of our scheme only when either one of the two entities is corrupt. Consider the case when the is corrupt, and the database  stored by the is leaked. This is equivalent to the case that both the and the are corrupt and colluding, and is clearly outside of our threat model. In this case the has access to all the records within . Since we store H() instead of  in , the can only decrypt records for which it correctly guesses their s. Thus, we ensure that even if the database is leaked, there is an additional layer of protection that does not allow the to decrypt all the records without brute-forcing.


 






 §.§ Frequently Asked Questions


In this section, we address some of the frequently asked questions that we have encountered.

If automates traceback, why go through all this trouble?
The Public Switched Telephone Network (PSTN) is heterogeneous. Legacy infrastructure drops signatures along the call path, making it ineffective for tracing call origins <cit.>. 
Call requests are signed by providers using a JSON Web Token in the SIP INVITE message with an 𝚡5𝚞 field pointing to the signing certificate. Malicious providers can exploit this by setting 𝚡5𝚞 to a timing-out link, increasing latency and forcing call transmission, posing a challenge for providers. Traceback attempts using such signatures reach dead ends, so manual processes are still needed. Additionally, the deployment of remains limited. According to the Robocall Mitigation Database in the US (Feb 7, 2024) <cit.>, among 7,109 providers, only 39.94% have fully implemented it, 23.96% are partially implemented, and 36.11% have no or unknown implementation status. We clarify that does not authenticate caller ID or block robocalls in real-time. Instead, it is a central repository of encrypted CDRs for traceback purposes. 

Why can't we just put traceback info in headers
Implementing traceback information in headers faces the same hurdles as S/S.

Why develop a new protocol instead of automating the manual tasks done by groups in ITG? The ITG currently maintains a semi-automated traceback system that sends notifications to  who are mandated to respond within 24 hours. Automating the current traceback tasks will require all providers to implement a traceback API that integrates with the ITG systems. While this automates the process, the gain on “traceback throughput”, the number of computable traceback requests per month, remains low as the process is still serial and involves  active participation for every traceback request. Tracebacks would run into dead-ends if a single  does not cooperate, their portal goes down, responds with misleading information, or partial deployment. 

For , this alternative adds an additional cost of maintaining an inbound traceback system. An adversary could exploit vulnerable API implementations of this mandate to access affected ' sensitive data. Note that compromising a carrier's API server exposes its peers and  network trends as well as subscriber call history, and well-funded companies who use industry best-practices are regularly breached. 
We designed as a centralized distributed system to alleviate serial traceback lookups, enabling providers to be passive entities rather than active for traceback computation. This design choice not only enhances the traceback throughput but also centralizes security management from several thousand providers to two organizations responsible for overseeing . Moreover, if any single entity is compromised, no plaintext data is leaked.

Why require participation from all providers if only the originating provider's records are needed? If only originating providers submit records, traceback fails because malicious carriers likely won't comply. Limiting submissions to the originator and second hop is infeasible because providers cannot determine their sequence in the call path. Thus, requiring all providers to submit records becomes essential to trace back and identify people facilitating bad calls. Having the ability to construct the full call path has added advantages such as trace-forwards to debug call routing or blocking errors.

Who will operate the and ?
The telephone network is the ideal environment for because regulators like the FCC already designate trusted third parties that provide singleton functions. Examples include toll-free numbering, local number portability (LNP) databases, certificate authority governance, and the current traceback clearinghouse, ITG. The FCC periodically solicits applications to serve as these entities and a fair and competitive process among several for-profit enterprises follows. The selected entities can then charge reasonable fees for the service they provide.

For , there are two entities to recruit. The roughly corresponds to an entity like the LNP databases, and many vendors have the technical ability to serve in this role. 
The TA performs functions similar to the current ITG, like registering providers to their system and determining if a traceback query is appropriate, so modifying that existing role would provide a straightforward on-ramp to deployment.

What if  refuse to participate? must be mandated to be effective. Regulation can compel  to participate or have their network access revoked. Unlike , is compatible with all network technologies in use.
 

 



§ SYSTEM AND PROTOCOL DESIGN
 

In this section, we discuss 's system architecture and detailed protocol.




 §.§ Architecture


Figure <ref> shows a high-level diagram of 's system architecture.




There are three kinds of entities in our system: 

Carriers 𝐏_𝐢 
A carrier P_i receives calls from either the source () or from a previous carrier (P_i-1) and forwards the call to either the destination () or the next carrier P_i+1. A call is identified by its = () where  is the time at which the call reaches the carrier. 



Record Store ()
The   maintains a database that stores encryptions of the hops associated with a call.  Recall that a  hop is a tuple := (P_i-1P_iP_i+1).










Traceback Authority ()
The has the following functions: 

    
  * Authorizing Trace Requests: The provides the signatures that enable a carrier to decrypt records retrieved from the . These signatures are computed on the call labels.

    
  * Managing '  Anonymous Authentication:
    The  manages the group signatures for the carriers. This consists of adding legitimate  to the group and providing them with credential to sign on behalf of the group. The is responsible for accountability, it can deanonymize signatures in case of misbehavior and hold the corresponding entity responsible.
    
    
  * Generating Pseudorandom Labels: The interacts with carriers to compute s.


  








 





 


 








 §.§ Protocol Overview

  consists of four protocols:  , , , and , which we describe in detail below.


Cryptographic Primitives 
As discussed in Sec. <ref>,
uses a witness encryption scheme for signatures (WES)<cit.>, a group signature scheme<cit.>, an oblivious PRF protocol<cit.>, signature schemes, and a hash function. The notations used in our protocols are described in Table <ref>. We present the protocol in detail in Appendix <ref>. Below we present an overview of the protocol. 







 Protocol
The protocol is described in Fig. <ref>.
This protocol is run by the and carriers to set up their keys. 


TA Setup:
The sets up (1) the group with a group master key and secret key. (2) the PRF key for the oblivious PRF and announces a public key (denoted _) corresponding to the PRF key. (3) two signature key pairs (_T, _T) and (_R, _R) and announces _T and _R to all entities. Here, signatures using _T will be used to decrypt the witness encryption ciphertexts, and _R will be used to authorize trace requests. 


Carrier 𝐏_𝐢 Setup:
Each  (denoted P_i) joins the system by first interacting with the to get a distinct group signing key _i, which they can use to sign anonymously on behalf of the group. They generate a regular signing key pair (_i, _i) for authenticated communication with the and (during trace). 

Finally the initializes a database  and sets up a signature key pair (_, _) and announces _


 Protocol

record the s with the using the protocol. We consider the case of submitting a single  to the  in Fig. <ref>. Each  in the call path parses the CDR into =()  and = P_i-1P_iP_i+1 as defined in Sec <ref>. To contribute call records, the  P_i anonymously submits a witness encryption of the message = (P_i-1P_iP_i+1) to , with a pseudorandom label associated with it and a group signature for authentication.
The ciphertext and the label leak no information about the call thus providing confidentiality of the call, and the group signature leaks no information about the  sending this information, thus providing anonymity to the carrier.
We elaborate on how the label, the encryption, and the signature are computed below.

The protocol consists of two phases: the label generation phase and the submission phase. In the label generation phase,  the label is computed with the help of the , using an oblivious PRF protocol.  The acts as a server and holds a PRF key, and the  acts as a client with the input. 
We assume that each  is associated with an epoch,  truncated to nearest centisecond, denoted .
The  uses = (ep) as input and the output of the protocol (denoted  ) is learned only by the . We note that with the help of _, the  can compute an efficient pairing check to verify that the output received from the is indeed correct, and  that the PRF key k was used to compute the  as detailed in Fig. <ref>.
The  then computes = H(). Recall that  is used instead of  to index the ciphertexts to prevent the from trivially decrypting all ciphertexts in the case that the database of ciphertexts and s  are leaked. 

In the submission phase, the   prepares the encryption as follows. P_i samples a λ-bit uniform  from ^λ and encrypts  with the WES scheme using  (_T, ) as the encryption key to get a ciphertext ct_1. The WES scheme ensures that the ciphertext can only be decrypted using a signature on  signed using _T by the . P_i further computes _2 = ⊕ H(), where H is modeled as a random oracle. 
Note that we require  as input to the hash function to extract the  in the proof of security. 
Finally, the  signs the message ((ct_1, ct_2), ) using the group signature scheme, obtains σ, and sends the resulting tuple ((ct_1, ct_2), , σ) to the . Upon receiving a submission request, validates the group signature σ and stores the tuple in the database; if verification fails, the request is dropped. 





Protocol
To trace a call, the  must retrieve all the s corresponding to a call from the . Fig. <ref> illustrates the sequence of events in the trace protocol. Initially, the  needs to obtain the labels corresponding to these calls. For this purpose, the  computes the labels with the assistance of the using the OPRF protocol described above. We assume an upper limit  on the duration of a call setup from the source to the destination. The  computes epochs  corresponding to the timestamps * ∈ [ - ,  + ] and computes the labels associated with the  for each of these epochs. 

Before we describe how the  gets the full trace, we note that a malicious  colluding with the could potentially compute labels on arbitrary  and check with if such labels exist in the store, revealing information about the existence of a call between a certain initiator and recipient. If the  attempts to perform this attack for a specific initiator and recipient, we call it a “targeted attack”. If the adversary's goal is to map the network by trying to compute labels on arbitrary , we refer to such attacks as “grinding attacks”. 
To mitigate the grinding attack, we implement rate-limiting on the number of requests a  can make. For this purpose, when the  interacts with the to compute a , the maintains a count of requests made by a  and will not authorize further requests if a certain limit is exceeded. To give authorization on this request, the will sign  = H() using _R, and this signature σ_R serves as an authorization for traceback. 
Moreover, consider the case that the is malicious (and the is honest) and is colluding with a , then they can easily mount the grinding attack described above by computing arbitrary labels and requesting the corresponding  from the . To mitigate this, we will also require the to implement rate-limiting on trace requests. This will ensure that a  colluding with a cannot mount grinding attacks. 

The  requests the for the ciphertexts corresponding to the . The first checks that the signature σ_R is verifiable using _R. It rejects the request if this is not the case. 
The identifies the ciphertexts corresponding to the  in  and sends _1, _2, , σ_, where σ_ = (_RS, (_1, _2, )).
The  then asks the for a signature on the  and uses these signatures to decrypt the ciphertexts and compute the s. 






 Protocol
Some  may provide wrong hops to frame others. Since the encrypted hops are anonymously submitted to the , we need a mechanism to catch the malicious s. Our group signature protocol allows the to open any group signature and reveal the  that signed a message. Thus, if a trace seems malformed, the  submits all ciphertexts, hops, and signatures for the call retrieved from the and sends it to the . The  runs a   function that outputs the set of faulty hops. The  then identifies the signatures that correspond to these hops and deanonymizes them to return the set of  that submitted malformed/wrong hops. 



 








 §.§ Traceback Validation

Once a  has s, they must assemble the hops into the complete path. We call this step “Traceback Validation” because it will identify the correct path or detect inconsistencies or missing records that should be manually investigated.

We validate a traceback by inserting decrypted records into a directed multi-graph.
In a multi-graph, two nodes can be connected by multiple edges. 
Each record is a graph with three nodes: _i-1, _i and _i+1; and two edges: _i-1→_i, and _i→_i+1. 
A traceback is the multi-graph union of such individual sub-graphs(hops). 







Ideal Scenario Each _i contributes a valid record for a given call. Figure <ref>(Full Path) visualizes this ideal scenario. Let deg_in and deg_out denotes in and out degrees respectively. The originating  _1 has deg_in=0 and deg_out=2. Here, one edge of deg_out (denoted by solid line) indicates its assertion to P_2 while the other edge (denoted by dashed-line) indicates P_2's assertion to P_1. The terminating  _4 has deg_in=2 and deg_out=0 for reasons symmetrical to one provided for the originating provider. Finally, each transit  (_2 and _3) has deg_in=2 and deg_out=2.
Any deviation from the ideal case helps us determine “faulty hops”—hops that are conflicting.


Determining Faulty Hops We detect faulty hops by checking four properties formulated from the ideal scenario:

Origin invariant: A call can have only one originator. This property holds if there is exactly one node in the directed multi-graph with deg_in=0 and deg_out∈{1, 2}. Otherwise, the originating record is missing, or some _i submitted malformed records. Note that deg_out = 1 does not necessarily imply a malicious originator since true originators will still have deg_out = 1 if there is a missing record from their downstream . If there is more than one node with deg_out = 2, then there are conflicting originators; in this case, we construct different call paths for each originator.

Terminating invariant: A call can have only one terminating provider. This property holds if there is exactly one node with deg_in∈{1, 2} and deg_out = 0. Otherwise, the terminating record is missing, or a _i submitted malformed records. This is symmetric to the origin invariant except that values for deg_in and deg_out are swapped.

Transit invariant: This property identifies all transit providers and validates for nodes having deg_in∈{1, 2} and deg_out∈{1, 2}.

Connectivity invariant: This property determines if the full call path can be recovered. It holds if there is a path between every pair of vertices in the traceback graph.

Figure <ref> presents the detailed algorithm for determining the faulty hops from the decrypted records and the ability to reconstruct the call path.



Traceback Robustness and Partial Deployment 
In a scenario where all parties are honest, we derive all the benefits of the scheme. Importantly, even in partial deployment scenarios where only certain providers submit their records, our scheme can identify the call originator under certain conditions. For example, if the originating provider is the sole contributor for a call, the system can still successfully identify the call origin without the contributions from any other provider in the call path.
If the second hop provider participates, our system can identify the origin even if no other provider participates. If there are ever conflicting origin claims, we initiate a manual investigation to identify the source and punish the dishonest party. If any other intermediate party participates honestly, we can still reduce manual traceback time. With the call path recovery algorithm, there may be cases where we can precisely identify the bad actor. However, this is an “added bonus” and not the main goal of the scheme.
The tracing algorithm relies on a best-effort strategy, and we believe that societal incentives, including civil or criminal liability, will motivate the entities to behave honestly. In Sec. <ref>, we present an evaluation of in partial deployment.













 



 §.§ Security of  

In this section we provide informal arguments that   achieves the security properties outlined in Sec <ref>. The formal proof in the UC framework is in Appendix <ref> our extended technical report <cit.> . 



 [Informal] Assuming the CPA security of the witness-encryption scheme, the unforgeability of the signature scheme, the security of the group signature scheme, the security of the OPRF protocol, and secure hash functions,  achieves record confidentiality, the privacy of individual caller, blinds network trends and  associations. Moreover if the is honest, additionally achieves  accountability. 




Trace Authorization Since a  requires a signature from  the to decrypt the ciphertexts, and a  needs to know the  to request this signature, only authorized parties can perform a trace successfully. 






Call Confidentiality Recall that the , information of the call is used only to compute the label. Since the computation of the label is through an OPRF, we guarantee that the does not learn the  and  of the call. Since the OPRF output is pseudorandom, the label by itself will also not reveal any information about the caller and the callee of the call. 


Trade Secret Protection Recall that each  is encrypted and stored at the . Decrypting the encrypted  requires knowledge of the labels and a signature on the , information accessible only to entities involved in the call or those accurately guessing the source, destination, and call time. The unforgeability property of the signature scheme ensures that an entity cannot forge a signature on behalf of the , preventing unauthorized decryption of the s. Additionally, the CPA security of the WES scheme safeguards the contents of these ciphertexts.
As previously described, a malicious  might attempt to guess arbitrary call details, create corresponding labels, and decrypt records stored at the , i.e. they try to mount a grinding attack. To mitigate this risk, we implement rate-limiting on such requests by having the  restrict the number of authorizations granted to each . 

Record integrity Since all contributed records are signed using a group signature, and the verifies this signature before adding the record to the database, we ensure that only authorized users can contribute records. 

Record Accountability We achieve  anonymity since each submission to the  does not include any identifier of the . They are instead signed using the group signature scheme, ensuring that the  is anonymous within the group. When a  is misbehaving (e.g. by sending a malformed ) the group signature can be opened by thus revealing the  that signed the submitted . 
We note that if the is malicious they may just not reveal any identity and accountability may not be guaranteed. But even if the is malicious they cannot frame an honest  as the sender of the record. 










    














    
    








































































































    
    




















 

 



§ IMPLEMENTATION





This section describes the prototype implementation of and how we obtained CDR data to evaluate it. 









 §.§ Prototype Implementation




We describe a prototype implementation for each component of , which enables us to evaluate its performance.





Traceback Authority We implement the as an HTTP server that uses BLS Signatures <cit.> to compute authorization signatures. For this function, we exposed an endpoint for authorizing trace requests. We set up our group signature scheme using short group signatures <cit.> implemented by IBM's  <cit.> and exposed an endpoint for opening signatures. Finally, we used the  elliptic curve ( Python package) for our OPRF protocol <cit.>. The exposes an API endpoint for label generation.

Record Store The  is an HTTP server with a database for storing records. We use the  columnar database. The  exposes endpoints for contribution and traceback queries.

Carrier We implement a carrier as a process that runs the protocol and interacts with other components in the system. For performance, we implemented the witness encryption scheme in C++ using the  elliptic curve  library<cit.> and wrote Python bindings using . 


 §.§ Data Generation


Because CDRs are data protected by US laws, they are unobtainable. We are unaware of work that models contemporary PSTN call records so we develop a PSTN model to algorithmically generate data. We first generate a graph to represent the 's peering relationships. We then model a social graph of telephone users and assign users to carriers. We then generate CDRs for calls between users. While we believe our model is reasonably accurate, in Section <ref>, we show that even if call volumes are significantly higher, will be practical. 

Telephone Network We use an iterative graph generation algorithm to construct a network consistent with real-world telephone topology. We have identified three properties that a reasonable model generator must consider:

Preferential Attachment: New carriers prioritize connecting with larger carriers that handle a significant traffic volume, so providers with wider coverage generally acquire more new customers. In our model, the number of carrier connections is proportional to its current degree.

Market fitness: Smaller providers can attract new customers but rarely surpass larger providers' market share. This feature enables us to mirror real-world scenarios, such as AT&T maintaining a higher market share even as the network evolves.

Inter-carrier agreements: Represents financial agreements, such as mutual compensation for handling each other's traffic, rates for different types of traffic, and billing arrangements. 

We use the Bianconi-Barabasi model <cit.> to achieve these properties. Our network consists of N nodes, each labeled P_i representing a unique carrier node. The weight of an edge between any two carrier nodes signifies the inter-carrier agreement amount, which we use in the shortest path computation. We assume each carrier node seeks to minimize the cost of transmitting call connections, a notion that aligns with real-world practices.

Subscribers Network We model subscribers' social interactions using a scale-free network. We create a total of S subscribers, each represented by a phone number in the NPA-NXX-XXXX format. We allocate phone numbers to subscribers based on each carrier's market share. We constructed a Barabási-Albert <cit.> graph denoted as G_s=(V_s, E_s) for the subscribers. Since is primarily interested in scenarios where the caller and the called party belong to different carrier networks, we minimized the probability that neighboring nodes of a given subscriber s_i are on the same network as s_i.

CDR generation Each edge in the social network G_s represents a call between two subscribers s_i and s_j. 
For each call s_is_j, we represent the call path as the shortest path between their respective providers in the topology. Each hop within the call path represents a CDR record.   

§ EVALUATION


0.004
0.003
0.282
0.009

3.152
2.887
4.541
0.140

0.113
0.102
0.196
0.010

1.473
1.341
2.055
0.072

10000
[group-separator=,]

10000
[group-separator=,]

0.073
0.066
0.166
0.007
int(1000/)

[group-separator=,]

1.693
1.477
6.573
0.323

2.479
2.171
3.904
0.143

0.847
0.780
1.064
0.039

4.143
3.708
5.980
0.173
int(1000/)

[group-separator=,]

0.419
0.376
0.615
0.023

0.419
0.376
0.615
0.023



2.310
2.118
2.865
0.098

int(1000/)

[group-separator=,]

0.147
0.134
0.193
0.009
 For  to succeed, runtime performance, queries, and insertions of records need to be fast to handle the volume of call traffic being processed daily by the network. Our prototype implementation allows us to test its performance for each protocol phase. We consider the following metrics: storage growth rate, minimum vCPUs required, time for each protocol, and the minimum bandwidth required as shown in Table <ref>.

gray




Experiment Setup
Our Experiments were run on a Linux virtual machine with 32 vCPU and 64GB of memory. The host was a Super Micro Server with an Intel Xeon Gold 6130, ECC DDR RAM, and 12Gbps SAS drives. In experiment 1, we benchmark individual tasks such as label generation, record encryption and decryption, opening signatures, signing, and verifying signatures. We executed each process in a single thread 1,000 times to obtain the average, minimum, maximum, and standard deviation (SD) of the runtime.

In Experiment 2, we generated a network graph with 7,000<cit.> carriers and simulated R_C = 10,000 calls per second. No entity currently has visibility into the call volumes of all carriers in the United States. As a result, we did not find well-supported statistics on the overall call volume in the United States. We are especially concerned with the number of calls that transit multiple carriers, and, of course, this figure is even less attested. Of the statistics we found, many had no citations, did not describe their methodology, or were otherwise suspect in accuracy. As a result, we settled on the round number of 10,000 calls per second for the North American phone network. This corresponds to roughly 800,000,000 calls per day. We admit that this choice is arbitrary, but as we see later, our system has substantial headroom and is also horizontally scalable. Our evaluation in the following sections considers the and as singletons. 



 §.§ Protocol Evaluation

Protocol The  is less than 10ms for all entities. Storing the identity of group members (providers) at the grows linearly in the number of providers. 


 Protocol
We measure the time and minimum system requirements to complete the protocol for the label generation and submission phases.

Label generation:
 request a PRF evaluation from the . Table <ref> shows that a single label generation takes ms on average (SD = ms). Hence, the can evaluate  labels on average on a single vCPU per second.

Bandwidth for label generation: We estimate the minimum bandwidth required to generate labels between  and the over an HTTP connection from: 

    B_w = R_rec· (S_req + S_res) · (1 + O_http)
 

R_rec is the rate at which records are generated across the network, S_req and S_res are request size, response size, and O_http additional overhead (in percentage) introduced by HTTP, respectively. On average, calls generated by our network have 5 hops[ITG reports that tracebacks usually go through 4 or more hops<cit.>], thus R_rec = 5 · R_C. Each request payload is 32 bytes; thus, S_req = 256 bits, likewise, S_res = S_req since the PRF is length-preserving. We compute overhead using: 
    O_http = Overhead per Request /  Batch Size


We measured the average overhead of about 652 bytes per request for the minimal headers when using HTTP/1.1. The group signature forms a significant fraction of this overhead. The can handle label-generation requests even with substantial network overhead since 25 Mbps is vastly below nominal internet throughput.



Record Submission:
We measure the time it takes to contribute 1 CDR record. From Table <ref>, contributing 1 CDR takes ms on average with a SD of ms. A provider can process  records in a second on a single vCPU. At a rate of 50,000 records per second[For an average of 5 hops per call, 10,000 calls per second correspond to 50,000 CDRs per second], a minimum of 208 vCPUs are required to encrypt all records. This may seem high, but recall we estimated 7,000 providers, so the CPU requirements are small in practice for .

Bandwidth for record submission: The record submission request payload is 1,900 bytes in size (15,200 bits), comprising a label, ciphertext, and signature. Using Equation <ref>, we estimate the minimum bandwidth for submitting records as 800 Mbps. Therefore, with 800 Mbps the  can handle submission requests for the entire network.

Once the  receives the submission request, it verifies the signature and inserts it into the database. Table <ref> shows that verifying a group signature takes ms on average with a SD of ms. Hence, the  can verify  submissions per core per second, thus requiring a minimum of 24 vCPUs to validate contribution requests.



Record Store
Our second experiment evaluates the growth of storage and how that affects querying and inserting records. As shown in Figure <ref>, we observed that the time it takes to insert records into the database is independent of the database size, averaging about 24.28ms with a SD of 1.681ms. Note that 23.28ms represents the average time to process a single INSERT statement with 1 VALUE row. Insertion overhead could significantly improve if multiple values are appended to a single insert statement.  The can process 43 insert statements in a second on a single vCPU. To cover the rate at  calls per second requires a minimum of 233 vCPUs. The database size grows at a rate of 1.5 TB per day, roughly $100 per day. Deployment consideration may require that records are only retained for a given period, after which they get expunged.

 Protocol
We consider the  protocol for a single traceback.
Label generation is the same as before.  Whenever authorization for a traceback is requested, the  records this in the database along with the . Storage grows linearly with the number of traceback requests. To decrypt a record, we need a signature on the label. Signing a label takes a mean time of 0.419ms with an SD of 0.023ms. We measured that decrypting a single record takes 0.847ms on average with a SD of 0.039ms. A single vCPU can decrypt 1,180 ciphertexts per second.

 Protocol
In the  protocol, we determine the faulty hops from the decrypted records as described in section <ref>. We measured the runtime for analyzing the records and determining the faulty hops to be 0.052ms. Opening a signature takes ms on average with a SD of ms as shown in Table <ref>. 




 §.§ Traceback Evaluation

Throughput We estimate the compute time for one traceback as the sum of the following components: 1) label generation, 2) trace authorization, 3) retrieving records from , and 4) decrypting records. In Section <ref>, we generate all labels in the range = {(^*) |∀* ∈ [ - t_max,  + t_max]}. Assuming t_max = 10 seconds and ep is in seconds, we retrieve records for 21 labels (2· t_max + 1). The estimated average compute time for one traceback is 0.75 seconds. Without communication latency, we can complete close to 3.5 million tracebacks in a month, increasing the current throughput by a multiplicative factor of 11,520. Communication latency would reduce this number, but the result remains a significant fraction of the current abuse.

Partial Deployment
was explicitly designed to support partial deployment because of lessons learned from S/S and proposals like RPKI to secure Internet communications. Given that both of those systems failed to meet their goals at the current levels of deployment, it is worth considering how might perform. 

First, though, we will need to establish definitions and deployment models. We say that a traceback is successful if the record store has at least one record that identifies the originating hop in the call path.
For this analysis, we call providers that deploy “adopters,” and define “adoption rate” as the fraction of all providers who are adopters. 
In S/S, the largest networks tended to be the earliest adopters, and only small networks continue operating without S/S (excluding, of course, legacy networks that are incompatible).
This trend held because regulatory agencies gave smaller networks more time to comply with deployment mandates than larger ones.
Published tracebacks and successful enforcement actions report that the vast majority of illegal calls come from small networks. 

We used our network model from Section <ref> to estimate traceback success in partial deployment. We simulate randomly dialed robocalls originating from the smallest r% of carriers and adopters as the largest a% of carriers. We find that if robocalls originate from the bottom 10% of networks, with adoption by only the largest 2% of carriers, can still successfully traceback 27% of all robocalls. When adoption increases to 10%, which is still lower than the current rate of adoption of S/S, traceback success leaps to 55% of robocalls. 

Given that robocallers place millions or billions of calls, even at low adoption would produce mountains of evidence that could lead to takedown of illegal robocalling operations. Of course, these results are likely sensitive to our model choices. Still, even if this estimate is wrong by an order of magnitude, tracing even a small fraction of the thousands or millions of robocalls is a vast improvement compared to 300 per month we see today.

 

§ DEPLOYMENT CONSIDERATIONS


In this section, we discuss practical deployment concerns relating to incentives, engineering concerns, and the trace authorization process.

Deployment Incentives When integrating a new security mandate into an existing system, it is essential to consider incentives. How will a provider benefit from deploying ? Eliminating bulk illegal calls aligns with providers’ interests since these calls are often unanswered and do not generate revenue. However, this motivation alone may not be enough. Fortunately, the S/S framework has shown that regulatory mandates can drive widespread network changes.

Engineering Concerns In our discussions with practitioners, we identified engineering concerns that, while challenging, are manageable. We anticipate that carriers will face hurdles integrating with billing systems and managing new cryptographic infrastructure. However, we anticipate that deployment will still be easier than S/S because it involves only latency-insensitive backends. Jäger itself will face typical site reliability engineering challenges, such as replication and public key infrastructure issues like governance. The industry has successfully navigated similar challenges with S/S, so we can have confidence that these engineering concerns are surmountable.

Rate Limiting and Authorization Our performance evaluation assumed that traceback authorization would be instantaneous. In reality, there will be some processing time. Human intervention may be required to review requests 
before or after they are system-signed. In some cases, the trace authorizer could
automatically approve requests, such as requests from honeypots for calls to their own numbers. Given that honeypots receive thousands of calls daily <cit.>, scalable traceback will significantly enhance investigative processes. 

§ RELATED WORK



Telecom fraud <cit.> is a long-standing problem <cit.> that continues to impact carriers <cit.> and subscribers <cit.>.
Most fraud schemes stem from inadequate authentication mechanisms <cit.> and security flaws in legacy telecom signaling protocols <cit.>.
Attempts to address these problems through protocol enhancements <cit.> and defenses <cit.> have had limited success. Illegal robocalling, a form of telecom fraud, frustrates phone users, carriers, and regulators.
Over the past decade, widespread adoption of VoIP technology has led to a surge of scams <cit.> perpetrated using robocalls.
To study the operational characteristics of robocallers, researchers have employed a wide range of techniques such as CDR data mining <cit.>, machine learning <cit.>, audio processing <cit.>, carrier collaboration <cit.>, and reputation scoring  <cit.>. 
Mitigation techniques based on caller ID authentication <cit.>, spam filtering <cit.>, call-blocking apps <cit.>, and increased penalties <cit.> have been proposed.
However, they have failed to significantly deter bad actors from originating illegal robocalls. 

In Dec 2019, the US Congress passed the TRACED Act <cit.> to protect consumers from illegal robocalls. Consequently, the FCC designated the Industry Traceback Group (ITG) <cit.> to track down entities responsible for originating illegal robocall traffic using traceback.
Tracebacks remain invaluable in uncovering and prosecuting numerous illegal robocalling operations <cit.>.
However, its effectiveness is limited since it is a manual, iterative, and time-consuming process. Each traceback requires cooperation among carriers spanning multiple days to pinpoint the source of illegal robocall traffic.
Network traceback methods like packet marking and router logging <cit.> are ineffective to traceback phone calls <cit.> due to general IP traceback limitations.

Our automated traceback technique addresses these challenges and encompasses all transit carriers. 
Notably, does not require modifications to existing infrastructure, making it compatible with other protocols. 

§ CONCLUSION



In this paper, we described the design of , a distributed system to facilitate automatic call traceback. facilitates the anonymous-but-traceable submission of encrypted call records to a central source, which after vetting from an authorizer allows traceback only by parties with information about a call to be traced. We demonstrate that despite the expensive cryptographic primitives and coordination cost, the system is practical today with modest hardware and low latency. 
In so doing, we show that represents a powerful new tool to combat telephone abuse.


 
We thank our anonymous shepherd and reviewers for their support of the paper. 
This material is based upon work supported by the National Science Foundation under Award No. CNS-2142930. Funds from the 2020 Internet Defense Prize also supported portions of this work.
 
abbrv
























    
















































    










    

















































































§ IDEAL FUNCTIONALITY FOR 

In this section we formalize the security properties of   in the UC framework <cit.>. We define an ideal functionality  (Figure <ref>) that captures the correctness and the security properties of the   system. 

The  functionality maintains a database  
and provides the following interface: 

    
  * : Enables carriers to register with the system. Since this is public information, the identity of the carrier is leaked to the adversary. 
    
  * : Allows carriers to submit records to the system. Recall that in the real world, an adversary can always learn when a record is submitted but does not learn the contents of the record, nor the identity of the carrier that submits the record. Therefore, the only information that is leaked to the adversary is the  which gives an indication of what time a call record was submitted. This captures the anonymity and the confidentiality guarantees. 
    
  * : Allows the adversary to delete or add records to the database. 
    
  * : Enables carriers to retrieve the s relevant to a specific call. All the s that are currently in the database along with any  that the adversary wants to append are returned to the carrier. Before sending these s to the carrier, the functionality sends  command to the , and only if the  responds with (, ) are these s sent to the carrier. This captures the trace authorization requirement and ensures that a carrier cannot request a trace too many times and hence rate-limits their requests. 
    
  * : Allows a carrier to deanonymize the sender of s that are malformed or conflicting. If the  is honest, the functionality runs a  predicate to determine the malicious/conflicting hops and returns the identities of the corresponding carriers. On the other hand if the  is malicious, the adversary is allowed to return the identities of any of the  carriers. This captures the property that accountability is guaranteed as long as the  is honest.  


     


§ THE PROTOCOL

We need the following ingredients: 

    
  * Group signatures as defined in <cit.> 
    
  * An OPRF scheme
    
  * Witness Encryption scheme for signatures. 


In the presentation of   below we will instantiate the OPRF scheme using the 2HashDH OPRF scheme of Jarecki et. al. <cit.> and the witness encryption scheme presented in <cit.><cit.>. 

  consists of four protocols:  , , , and  protocols, which we describe in detail below. 

Before we describe the protocol we present details of the OPRF scheme of <cit.> in Figure <ref> and the Witness Encryption scheme of <cit.> in Figure <ref>. 








 §.§ 
 

The Traceback Authority  does: 

    
  * Generate BLS signature keys (_T, _T) .(1^λ) and (_R, _R) .(1^λ)
    
  * Generate OPRF key k _q and announce the corresponding public key _ = g^k
    
  * Run the  algorithm of the group signature scheme and announce (, _0)  which are the group manager public key and  the initial group information. 
    
  * The  initializes a counter _i corresponding to each P_i. 


Each provider P_i does: 

    
  * Run the interactive joining protocol  with  and receive _i 
    
  * Generate signing keys (_i, _i) .(1^λ) and announce _i. 


The Record Store  does: 

    
  * Initialize the database 
    
  * Generate signing keys (_, _) .(1^λ) and announce _




 §.§ 


Each provider P_i with input () and = (P_i-1P_iP_i+1) does: 

    
  * Compute = () and run the OPRF protocol with  using inputs  = () as follows: 
    
        
  * Pick r_q and compute a = H_1()^r and send a to 
        
  * The  computes b = a^k and sends it back to P_i
        
  * P_i checks the following pairing equation to verify the OPRF was evaluated correctly: e(_, H_1()) = e(g, b^1/r)[The groups are pairing friendly, and hence we can verify the correctness of the OPRF via pairing equations <cit.>].

  * Output = H_2(_, , b^1/r ) 
    
    
  * The provider then encrypts the  as follows:
    
        
  * Sample a random key {0,1}^λ
        
  * Encrypt  as as _1 = .((_T, ), )
        
  * Compute _2 = H_3() ⊕ 
    
    
  * The provider signs the ciphertexts and the H() using the group signature scheme: σ = (_i, (_1, _2, H())) and sends (H(), (_1, ), σ) to 


The Record Store  upon receiving  (H(), (_1, ), σ) does the following:

    
  * Check (, (H(), (_1, )), σ) = 1. 
    
  * If yes, write (H(), (_1, ), σ) to the database. Else ignore the message. 





 §.§ 


Each provider P_i with input () does: 

    
  * For * ∈ [ - ,  + ] compute ^* = (^*) 
    
  * For each * compute ^* as above with inputs ^* = (^*) by running the OPRF protocol with the 
    
  * Request a signature on = H(^*) from . 
    
  * The  checks if _i > T, if yes, reject the request, else the  computes σ_R = (_R, ) and sends it back to P_i. 
    
  * Send (^*, σ_R) to  and receive the corresponding records back ((^*, _1^*, _2^*, σ^*), σ_) if they exist.
    
  * Verify (_,((^*, _1^*, _2^*, σ^*), σ_)) = 1. If not, reject. 
    
  * Request a signature on each ^* from  by sending σ_i = (_i, ^*) to the . The  compute σ_T = (_T, ^*) and sends it to P_i. 
    
    
    
  * Decrypt the ciphertexts as follows:
    
        
  * Compute ^* = .(σ_T, _1^*)
        
  * Compute ^* = H_3(^*^*) ⊕_2
    
    
  * Append ^* to _




 §.§ 


If a ^* is malformed or conflicts with another record, the provider P_i can request the  to open the corresponding signature to deanonymize that provider and hold them accountable. 


    
  * P_i sends ,^*, _1^*, _2^*, σ^*), the list of {}  to the 
    
  * The  runs  algorithm  to determine if the provider is misbehaving and needs to be deanonymized. 
    
  * The  computes P_j^* = (, (^*, _1^*, _2^*, σ^*)) and returns P_j^*




§ FORMAL PROOFS OF SECURITY OF  


In this section we will present the formal proofs of security. We will consider three cases of corruption: (1) Only a subset of the providers are corrupt (2) The record store  is corrupt and can collude with any of the providers and (3) the traceback authority  is corrupt and can collude with any of the providers. 

For completeness we first show a simulator where no parties are corrupt. 

Case 0: No entities are corrupt


Simulate the  Traceback Authority: 

    
  * Generate BLS signature keys (_T, _T) .(1^λ) and (_R, _R) .(1^λ)
    
  * Generate OPRF key k _q and announce the corresponding public key _ = g^k
    
  * Run the  algorithm of the group signature scheme and announce (, _0)  which are the group manager public key and  the initial group information. 


Simulate honest providers: Upon receiving (, P_i) from : Generate signing keys (_i, _i) .(1^λ) and announce _i. 




Simulating honest contributions: Upon receiving (,) from , just store (, (·)) in a database  and return (, ) to . 






  

Honest trace request:

    
  * Upon receiving (,) from , send ∅ back to 
    
  * Upon receiving (, P_i) from , send (, P_i, ) back to . 












 §.§ Case 1: Only a subset of the providers are corrupt and the and are honest

To prove UC security we need to show that there exists a simulator that produces a transcript in the ideal world that is indistinguishable from the real world. Below we present the simulator for the case when only a subset of the providers are malicious and all other entities are honest. 


Simulate the  Traceback Authority: 

    
  * Generate BLS signature keys (_T, _T) .(1^λ)  and (_R, _R) .(1^λ)
    
  * Generate OPRF key k _q and announce the corresponding public key _ = g^k
    
  * Run the  algorithm of the group signature scheme and announce (, _0)  which are the group manager public key and  the initial group information. 


Simulate honest providers: Upon receiving (, P_i) from : Generate signing keys (_i, _i) .(1^λ) and announce _i. 

Malicious provider P_j: Simulate the interactive joining protocol  with P_j, and send (, P_i) to . 



Simulating honest contributions: The simulator does not need to simulate interactions between honest providers and  and , since this is not in the view of the malicious providers. Therefore, upon receiving (, ) from , just store (, (·)) in a database  and return (, ) to . 


Simulating random oracle invocations: 

    
  * Upon receiving input x for random oracle H_1, check if (x, y) exists in _1. If yes return y, else sample a random y, store (x,y) ∈_1 and return y. 
    
  * Upon receiving input x for random oracle H_2, check if (x, y) exists in _2. If yes return y, else sample a random y, store (x,y) ∈_2 and return y. 
     
  * Upon receiving input x for random oracle H_3, check if (x, y) exists in _3. If yes return y, else sample a random y, store (x,y) ∈_3 and return y. 


Simulating malicious contributions: 

    
  * Upon receiving a on behalf of  from the adversary, compute b = a^k and send it back to the . 
    
  * Upon receiving (, _1, _2, σ) from :
    
        
  * Check (x, ) exists in Q_2. If not, abort with _2. 
        
  * Else parse x as (_, , b^*) 
        
  * Check that (, y) exists in Q_1. If not, abort with _1. 
        
  * Check that e(_, y) = e(g, b^*). If not, abort with 
        
  * Check ((^*), z) exists in _3. If not, abort with _3. 
        
  * Else compute ^* = z ⊕_2 

    
  * If all checks pass, compute P_j^* = (_i, (, _1, _2, σ)). If P_j^* corresponds to that of an honest party, abort with . 
    
  * Send (, , ) on behalf of P_j^* to . 
    
  * Receive (, ) from  and store (, (P_j, , )) in . 


 
We consider two cases: 1) an honest trace request 2) a malicious trace request 

 

  * Honest trace request:

    
  * Upon receiving (,) from , send ∅ back to 
    
  * Upon receiving (, P_i) from , send (, P_i, ) back to . 



  * Malicious trace request:

    
  * Upon receiving (^*, σ^*) from  (on behalf of P_j^*): 
    
    
  * if σ^* verifies under a honest party P_i's  abort with  
        
  * If ^*, (·) exists in the list of ciphertexts, send (^*, (_1, _2, σ)) to . Else:
        
  * Check (x, ) exists in Q_2. If not, abort with _2. 
        
  * Else parse x as (_, , b^*) 
        
  * Check that (, y) exists in Q_1. If not, abort with _1. 
        
  * Check that e(_, y) = e(g, b^*). If not, abort with 
    
    
  * Send (, , P_j^*) on behalf of P_j^* to  
    
  * Receive ({}) from . If any of the  correspond to that of a malicious contribution, send {, P_j, , } to . 
    
  * Upon receiving  from , check that requesting provider has not requested too many records and send (, ) to . 
    
  * Receive _ from . 
    
  * Encrypt each of the  using the corresponding  and _T in the following way:
    
        
  * Sample a random key {0,1}^λ 
        
  * Compute _1 = .((, _T), )
        
  * Sample a random  _2. Set H_3() = _2⊕
    
    
  * Using the group signature scheme, compute σ on behalf of P_i, where P_i is the honest sender of the record. 
    
  * Compute σ_RS = ((^*, _1^*, _2^*, σ^*))
    
  * Send the (^*, _1^*, _2^*, σ^*), σ_RS that correspond to ^* to the adversary. 






 Upon receiving  request from  for a particular record, (^*, _1^*, _2^*, σ^*), σ_RS, check that σ_RS is a signature that was computed by the simulator, if not abort with _2. Else send , , _ to  and output whatever  returns. 


Proof By Hybrids Now to prove that the simulated world and the real world are indistinguishable we proceed via a sequence of hybrids, starting from the real world until we reach the ideal world. We show that each of these hybrids are indistinguishable and therefore the real world and the simulated world are indistinguishable. 


    
  _0 This is the real world protocol 
    
  _1 This hybrid is identical to the previous hybrid except that the simulator may abort with . By the non-frameability property of the group signature scheme, the simulator aborts with negligible probability and therefore this hybrid is indistinguishable from the previous one. 
    
  _2 This hybrid is identical to the previous hybrid except that the simulator may abort with _1. Since we use a random oracle and require the adversary to use the RO, the probability of this event occurring is negligible, and therefore this hybrid is indistinguishable from the previous one. 
    
  _3 This hybrid is identical to the previous hybrid except that the simulator may abort with _2.Since we use a random oracle and require the adversary to use the RO, the probability of this event occurring is negligible, and therefore this hybrid is indistinguishable from the previous one. 
    
  _4 This hybrid is identical to the previous hybrid except that the simulator may abort with _3. Since we use a random oracle and require the adversary to use the RO, the probability of this event occurring is negligible, and therefore this hybrid is indistinguishable from the previous one. 
    
  _5 This hybrid is identical to the previous hybrid except that the simulator may abort with . Since we use unforgeable signatures, this event occurs with negligible probability and therefore the two hybrids are indistinguishable. 
    
  _6 This hybrid is identical to the previous hybrid except that the simulator may abort with _2. Since we use unforgeable signatures, this event occurs with negligible probability and therefore the two hybrids are indistinguishable. 


Since this hybrid is identical to the simulated world, we have shown that the real world and ideal world are indistinguishable, and that concludes the proof of security for the case when only a subset of carriers are corrupt. 




 §.§ Case 2: and subset of providers are corrupt, and is honest

We present the simulator for this case below: 


The adversary  runs the algorithms of the . Receive _T, _, (, _0)  from 

Simulate honest providers: Upon receiving (, P_i) from : 

    
  * Generate signing keys (_i, _i) .(1^λ) and announce _i. 
    
  * Interact with  to run the  protocol and learn _i.  


Malicious provider P_j: Upon receiving  (, P_j^*) from  on behalf of , send (, P_j^*) to . 





Simulating honest contributions: Note that the simulator only simulates the computation of the label, since that is the only interaction with the adversary. Since the  is honest the simulator does not need to compute the ciphertexts or interact with . Therefore, upon receiving (, ) from : 

    
  * Compute a label as follows: 
    
        
  * Sample random r _q and compute a = H_1(0)^r and send a to  on behalf of . 
        
  * Receive b from . 
        
  * Check that e(_, H_1(0)) = e(g, b^1/r)     
        
  * Output = H_2(_, 0, b^1/r)   and store (, ). 
    


Simulating random oracle invocations: 

    
  * Upon receiving input x for random oracle H_1, check if (x, y) exists in _1. If yes return y, else sample a random y, store (x,y) ∈_1 and return y. 
    
  * Upon receiving input x for random oracle H_2, check if (x, y) exists in _2. If yes return y, else sample a random y, store (x,y) ∈_2 and return y. 
     
  * Upon receiving input x for random oracle H_3, check if (x, y) exists in _3. If yes return y, else sample a random y, store (x,y) ∈_3 and return y. 


Simulating malicious contributions: 
 
    
  * Upon receiving (, _1, _2, σ) from :
    
        
  * Check (x, ) exists in Q_2. If not, abort with _2. 
        
  * Else parse x as (_, , b^*) 
        
  * Check that (, y) exists in Q_1. If not, abort with _1. 
        
  * Check that e(_, y) = e(g, b^*). If not, abort with 
        
  * Check ((^*), z) exists in _3. If not, abort with _3. 
        
  * Else compute ^* = z ⊕_2 
    
    
  * Send (, , ) on behalf of  to . 
    
  * Receive (, ) from  and store (, (, , )) in . 


 
We consider two cases: 1) an honest trace request 2) a malicious trace request 

 

  * Honest trace request: Upon receiving (,) from 

    
  * If (, (, , )) ∈
    
        
  * Sample random r _q and compute a = H_1()^r and send a to 
        
  * Receive b from . 
        
  * Check that e(_, H_1()) = e(g, b^1/r).      
        
  * Output ^* = H_2(_, , b^1/r) 
        
  * Request  for a signature on ^*. 
        
  * If no signature received send ∅ to . And upon receiving (, P_i) from , return (, )
        
  * Else Decrypt _1, _2 corresponding to ^* if it exists and send , , , to . And upon receiving (, P_i) from , return (, )
        
  * If no ciphertexts exist corresponding to this ^* abort with failure .
        
    
    
  * If (, (, , )) ∉, 
    
        
  * simulate the computation of a label as in honest contribution
        
  * Sample a random string ^* . 
        
  * Request  for a signature on ^*. If a signature is received, send (, ) to , else send (, ) upon receiving (, P_i) from . 
    



  * Malicious trace request: 

    
  * Upon receiving (^*, σ_i, σ_R) from  (on behalf of P_j^*): 
    
    
  * If σ_i corresponds to that of an honest party, abort with . 
        
  * If ^*, (·) exists in the list of ciphertexts, send (^*, (_1, _2, σ)) to . Else:
        
  * Check (x, ) exists in Q_2. If not, abort with _2. 
        
  * Else parse x as (_, , b^*) 
        
  * Check that (, y) exists in Q_1. If not, abort with _1. 
        
  * Check that e(_, y) = e(g, b^*). If not, abort with 
    
    
  * Send (, , P_j^*) on behalf of P_j^* to  
    
  * Receive ({}) from . If any of the  correspond to that of a malicious contribution, send {, P_j, , } to . 
    
  * Upon receiving  from ,  send 
(, ) to . 
    
  * Receive _ from . 
    
  * Encrypt each of the  using the corresponding  and _T in the following way:
    
        
  * Sample a random key {0,1}^λ 
        
  * Compute _1 = .((, _T), )
        
  * Sample a random  _2. Set H_3() = _2⊕
    
    
  * Using the group signature scheme, compute σ on behalf of P_i, where P_i is the honest sender of the record. 
    
  * Compute σ_RS = ((^*, _1^*, _2^*, σ^*))
    
  * Send the (^*, _1^*, _2^*, σ^*), σ_RS that correspond to ^* to the adversary. 






 Upon receiving (, , _) request from   send  request to  and output whatever  returns. 

    
  * If the adversary opens a signature submitted by a malicious party as an honest party's identity abort with . 
    
  * If the adversary opens a record (^*, _1^*, _2^*, σ^*), σ_RS where σ_RS was not computed by the simulator abort with _2. 




Proof By Hybrids Now to prove that the simulated world and the real world are indistinguishable we proceed via a sequence of hybrids, starting from the real world until we reach the ideal world. We show that each of these hybrids are indistinguishable and therefore the real world and the simulated world are indistinguishable. 


    
  _0 This is the real world protocol 
    
  _1 This hybrid is identical to the previous hybrid except that the simulator may abort with . By the non-frameability property of the group signature scheme, the simulator aborts with negligible probability and therefore this hybrid is indistinguishable from the previous one. 
    
  _2 This hybrid is identical to the previous hybrid except that the simulator may abort with _1. Since we use a random oracle and require the adversary to use the RO, the probability of this event occurring is negligible, and therefore this hybrid is indistinguishable from the previous one. 
    
  _3 This hybrid is identical to the previous hybrid except that the simulator may abort with _2.Since we use a random oracle and require the adversary to use the RO, the probability of this event occurring is negligible, and therefore this hybrid is indistinguishable from the previous one. 
    
  _4 This hybrid is identical to the previous hybrid except that the simulator may abort with _3. Since we use a random oracle and require the adversary to use the RO, the probability of this event occurring is negligible, and therefore this hybrid is indistinguishable from the previous one. 
    
  _5 This hybrid is identical to the previous hybrid except that the simulator may abort with . Since we use unforgeable signatures, this event occurs with negligible probability and therefore the two hybrids are indistinguishable. 
    
  _6 This hybrid is identical to the previous hybrid except that the simulator may abort with . Since we use a verifiable OPRF scheme this occurs with negligible probability. 
    
  _7 This hybrid is identical to the previous hybrid except that the simulator simulates the OPRF calls using 0 as input instead of the . By the obliviousness property of the underlying OPRF scheme, these two hybrids are indistinguishable. 
    
  _8 This hybrid is identical to the previous hybrid except that the simulator may abort with _2. Since we use unforgeable signatures, this event occurs with negligible probability and therefore the two hybrids are indistinguishable. 


Since this hybrid is identical to the simulated world, we have shown that the real world and ideal world are indistinguishable, and that concludes the proof of security for the case when only a subset of carriers are corrupt. 



 §.§ Case 3: and a subset of the providers are corrupt, and is honest
 


Simulate the  Traceback Authority: 

    
  * Generate BLS signature keys (_T, _T) .(1^λ)  and (_R, _R) .(1^λ)
    
  * Generate OPRF key k _q and announce the corresponding public key _ = g^k
    
  * Run the  algorithm of the group signature scheme and announce (, _0)  which are the group manager public key and  the initial group information. 


Simulate honest providers: Upon receiving (, P_i) from : Generate signing keys (_i, _i) .(1^λ) and announce _i. 

Malicious provider P_j: Simulate the interactive joining protocol  with P_j, and send (, P_i) to . 



Simulating honest contributions: Upon receiving (, ) from ,

    
  * Sample a random 
    
  * Send a random  and compute _1 = .((_T, ), )
    
  * Sample a random string _2 
    
  * Compute a group signature σ on behalf of some honest party P_i
    
  * Send (_1, _2, , σ) to  and send (, ) to . Store (, , _1, _2). 

 


Simulating random oracle invocations: 

    
  * Upon receiving input x for random oracle H_1, check if (x, y) exists in _1. If yes return y, else sample a random y, store (x,y) ∈_1 and return y. 
    
  * Upon receiving input x for random oracle H_2, check if (x, y) exists in _2. If yes return y, else sample a random y, store (x,y) ∈_2 and return y. 
     
  * Upon receiving input x for random oracle H_3, check if (x, y) exists in _3. If yes return y, else sample a random y, store (x,y) ∈_3 and return y. 


Simulating malicious contributions: Note that since the  is corrupt, the simulator only needs to simulate the label generation. 

    
  * Upon receiving a on behalf of  from the adversary, compute b = a^k and send it back to the . 


 
We consider two cases: 1) an honest trace request 2) a malicious trace request 

 

  * Honest trace request: 

    
  * Upon receiving (,, ) from ,
    
        
  * Retrieve   that corresponds to  if it exists. 
        
  * Send (, σ_R) to  and receive (, _1, _2, σ). If no such record was received, send (, (, ) to )
        
  * If no  exists, compute = H_2(_,, H_1()^k) and send  to . If any _1, _2, ,σ received, first check if σ corresponds to that of an honest party, if this is the case abort the simulation with  else decrypt the ciphertexts to retrieve the  and send (, (, (P_j^*, , ))) to . 
        Upon receiving , send , P_j^*, , to . 

    
  * Upon receiving (, P_i) from , send (, P_i, ) back to . 



  * Malicious trace request:


  * Upon receiving a query for H_3 on , send (, , P_i) to  and receive back _ = {, }. 
    
  * Retrieve (_1, _2, , σ) that correspond to  and check that this is the same  that was encrypted in _1. If yes, compute z = _2 ⊕ and send z in response and store ((), z) in _3.  If not, sample a random z {0,1}^λ and send z in response. 








 Upon receiving  request from  for a particular record, send , , _ to  and output whatever  returns. 


Proof By Hybrids Now to prove that the simulated world and the real world are indistinguishable we proceed via a sequence of hybrids, starting from the real world until we reach the ideal world. We show that each of these hybrids are indistinguishable and therefore the real world and the simulated world are indistinguishable. 


    
  _0 This is the real world protocol 
    
  _1 This hybrid is identical to the previous hybrid except that the simulator may abort with . By the non-frameability property of the group signature scheme, the simulator aborts with negligible probability and therefore this hybrid is indistinguishable from the previous one. 
    
  _2 This hybrid is identical to the previous hybrid except that the simulator may abort with _1. Since we use a random oracle and require the adversary to use the RO, the probability of this event occurring is negligible, and therefore this hybrid is indistinguishable from the previous one. 
    
  _3 This hybrid is identical to the previous hybrid except that the simulator may abort with _2.Since we use a random oracle and require the adversary to use the RO, the probability of this event occurring is negligible, and therefore this hybrid is indistinguishable from the previous one. 
    
  _4 This hybrid is identical to the previous hybrid except that the simulator may abort with _3. Since we use a random oracle and require the adversary to use the RO, the probability of this event occurring is negligible, and therefore this hybrid is indistinguishable from the previous one. 
    
  _5 This hybrid is identical to the previous hybrid except that the simulator may abort with . Since we use unforgeable signatures, this event occurs with negligible probability and therefore the two hybrids are indistinguishable. 
    
  _6 This hybrid is identical to the previous hybrid except that the simulator simulates the honest contributions by sampling a random . By the pseudorandomness property of the underlying OPRF scheme, these two hybrids are indistinguishable. 
    
  _7 This hybrid is identical to the previous hybrid except that the ciphertext _2 is a randomly sampled string. By the perfect security of the stream cipher (OTP), these two hybrids are indistinguishable. 
    
  _8 This hybrid is identical to the previous hybrid except that the group signature corresponds to that of a random honest party. By the anonymity guarantees of the underlying group signature scheme, these two hybrids are indistinguishable. 


Since this hybrid is identical to the simulated world, we have shown that the real world and ideal world are indistinguishable, and that concludes the proof of security for the case when only a subset of carriers are corrupt.      
        





§ ARTIFACT APPENDIX





 §.§ Abstract

We developed a prototype of the  system and conducted a thorough performance evaluation. The  artifact is composed of four key components: Group Membership Management, Label Generation, Trace Authorization, and Record Storage. Each of these components was containerized using Docker, and we orchestrated them together with Docker Compose. Additionally, we integrated auxiliary services, including a web-based GUI, to facilitate interaction with the database.

We generated a dataset of Call Detail Records and evaluated 's performance. Our experimental results indicate that  incurs minimal computational and bandwidth overhead per call, with these costs scaling linearly with the increase in call volume.





 §.§ Description & Requirements

The  prototype comprises four integral components:

Membership Management
The Group Manager (GM) oversees membership management. This component enables the GM to issue new group membership keys or revoke existing ones, and it also facilitates the tracing of traitors. Within our implementation, the  assumes the role of the GM.

Label Generation
Label generation is controlled by the Label Manager (LM). The LM collaborates with providers to evaluate pseudorandom functions using the Oblivious Pseudorandom Function protocol. In our system, the  also fulfills the role of the LM.

Trace Authorization
This component is responsible for generating authorization signatures required to decrypt ciphertexts. The  acts as the Trace Authorizer in our implementation.

Record Storage
The Record Storage component stores ciphertexts and provides the results of match trace queries.


All the above components are implemented in Python. However, for performance optimization, we implemented the witness encryption in C++ and created Python bindings to integrate the library into our prototype.




  §.§.§ Security, privacy, and ethical concerns

None





  §.§.§ How to access

We have archived the witness encryption and the  prototype into a zip file, which is publicly accessible on Zenodo at the following link: https://zenodo.org/doi/10.5281/zenodo.12733869https://zenodo.org/doi/10.5281/zenodo.12733869. Additionally, we maintain an active version of the artifact in our GitHub repositories. The source code for Witness Encryption can be found at https://github.com/wspr-ncsu/BLS-Witness-Encryptionhttps://github.com/wspr-ncsu/BLS-Witness-Encryption, while the  prototype is available at https://github.com/wspr-ncsu/jaegerhttps://github.com/wspr-ncsu/jaeger.






  §.§.§ Hardware dependencies

Running  does not necessitate any specific hardware requirements. However, to achieve results comparable to those presented in the paper, our experiments were conducted on a Linux virtual machine equipped with 32 vCPUs and 64 GB of memory. The underlying host was a Super Micro Server featuring an Intel Xeon Gold 6130 processor, ECC DDR RAM, and 12 Gbps SAS drives.






  §.§.§ Software dependencies

For ease of setup, we recommend configuring the project using Docker. If you prefer not to use Docker, our repositories provide detailed instructions on how to set up the project without it. For the remainder of this artifact appendix, we will focus exclusively on the setup and execution of experiments using Docker.





  §.§.§ Benchmarks

None





 §.§ Set Up



  §.§.§ Installation
 
You need to install the appropriate version of Docker based on your operating system. If your Docker installation does not include the Docker Compose plugin, be sure to install Docker Compose separately. Additionally, download the  prototype source code from either the GitHub repository or Zenodo.

We have published the  Docker image on Docker Hub as . If this image is not available, navigate to the root directory and build the  Docker image using the following command:


Note that the  option does not necessarily need to be . We use  to align with the image on dockerhub.





  §.§.§ Basic test

Generate secret keys for label generation, group master and public keys for group management, as well as private and public keys for BLS signatures and witness encryption by running the following command:



The  option instructs the script to generate all necessary keys. If you only need to generate keys for specific components, use the following options:  for label generation,  for group management, and  for trace authorization/witness encryption. After running the command, verify that the  and  files have been created and that the variables within are populated with the appropriate keys.





 §.§ Evaluation Workflow






  §.§.§ Major claims



  (C1): 
The average runtime for the following operations are as follows: Label generation takes 0.073 ms, the contribution protocol takes 4.143 ms, trace authorization takes 0.419 ms, decryption takes 0.847 ms, opening a signature takes 0.147 ms, and verifying a group signature takes 2.310 ms. Experiment (E1) substantiates these performance metrics.
























  §.§.§ Experiments



  (E1): Benchmark  operations in Table <ref>.
  
  
  Preparation: Run the Docker Compose command to start the services, and then log in to the Docker container by executing: 



  Execution: To benchmark the operations, run the following command: 

  
This will display the results on the console and create a  folder inside the project root.  

  
  Results: 
      The file  contains a summary of the benchmarks, while  records the individual runs. We used  to determine the mean, min, max, and standard deviations. To aggregate the benchmark results from , as shown in Table <ref> (in the paper), run . This script generates a CSV file  with the aggregated results.



  (E2): Determine Bandwidth, Storage Growth, and Query Performance as illustrated in Fig. <ref>.
    
        
  Preparation: Data generation 
            
                
  * Run Docker Compose to start the services, and log in to the Docker container as demonstrated in E1.
                
  * Generate telephone and social network data by running the command: . The  option specifies the number of carriers,  specifies the number of subscribers,  determines whether CDRs should be generated, and  skips all prompts. Note that in the paper,  is set to 7000 and  is set to 300M.
                
  * View the Generated Dataset: We will connect to the ClickHouse database using a web browser. Ensure that your browser has network access to both ports 5521 and 8123. We have added a UI service that allows you to connect to the database. Visit  in your browser.
                
                    
  * Enter  as the ClickHouse URL,  as the Username, and  as the Password, then click the  button. Once successful, click the  link.
		          
  * On the home page, select  in the database field, which will load the tables. You can then click on any table to view its Details, Schema, or preview rows. 
		          
  * If you prefer to run your own SQL queries, click on the new file icon/button with the orange background. Type  in the query field and click the  button. 
                
            
        
  Execution: To run the contributions protocol, execute the command: . The  option specifies the number of batches, which is the number of times you wish to run the contribution experiment (it defaults to ). After each batch, database stats are measured and stored in the  folder. The  option is required and specifies the number of records per batch.
        
  Results: The results are saved in  and . To generate the fetch and insert query performance graph shown in Fig. <ref> from the results in , run . This creates a PNG file at .
    
    


  (E3): Run a Traceback (Optional)
    
        
  Preparation: Start the Docker services and log in to the Docker container as described in E1. Visit  in your browser, and execute the SQL command . Refer to the E2 preparation section for instructions on executing the SQL query. The results from this query are the calls whose ciphertexts have been submitted to the RS.
        
        
  Execution: Run the following command: . Replace , , and  with the values from any row in the query results obtained in the preparation step above.
        
        
  Results: This command will:
            
    		
  * Generate call labels within the [ - ,  + ] range
    		
  * Request authorization signatures from the TA
    		
  * Retrieve ciphertexts from the RS
    		
  * Decrypt and analyze the records to determine the origin and call path.
                
  * Display the results to your console.
            
    








 §.§ Notes on Reusability

Our implementation includes Docker services defined in the  file. Once the compose-up command is running, the following services are exposed via :

    
  * The Group Management server runs on . The implementation is defined in .
    
  * The Label Generation server runs on . The implementation is defined in .
    
  * The Trace Authorization server runs on . The implementation is defined in .
    
  * The Record Store server runs on . The implementation is defined in .


For more information on the commands available for customizing our implementation, please refer to our GitHub repository.






 §.§ Version

Based on the LaTeX template for Artifact Evaluation V20220926.













     


