Anonymous communication systems allow users to communicate without revealing their identities and messages. The earliest design of an anonymous communication system goes back to Chaum [Cha81] who proposed the design of an encrypted email service that additionally hides the identities of the sender and the receiver. Since then, numerous approaches have been proposed to build anonymous routing schemes [Cha81, Cha88, Abe99, GRS99, SBS02, DMS04, ZZZR05, CGF10, BG12, CBM15, vdHLZZ15, TGL + 17] -a key component of anonymous communication systems. These include mix-nets [Cha81, Abe99, BG12], the Dining Cryptographers' nets [Cha88, CGF10, APY20], onion routing [GRS99, DMS04, CL05, DS18], multi-party-computation-based approaches [HEK12, AKTZ17, SA19], multi-server PIR-write [OS97, GIKM00, CBM15], as well as variants [ZZZR05, vdHLZZ15, TGL + 17].
However, all of these routing schemes are interactive, where many servers or routers engage in an interactive protocol to achieve routing. The security relies on threshold type assumptions, e.g., majority or at least one of the routers must be honest. This is unsatisfactory since the threshold-based trust model increases the barrier of adoption, the interactivity leads to higher network latency, and finally, the schemes provide no guarantees when all routers may be malicious, or worse yet, colluding with a subset of the receivers and senders.
The recent work of Shi and Wu [SW21] was the first to study the feasibility of non-interactive anonymous routing (NIAR) with a single, untrusted router which can additionally collude with a subset of senders and receivers. The setting is as follows: there are n senders and n receivers, and each sender u wants to talk to a unique receiver v = Ã(u) given by the routing permutation Ã. The NIAR scheme has a trusted setup that given a routing permutation à outputs encryption keys for senders, decryption keys for receivers, and a routing token for the router that secretly encrypts the routing permutation. In each time step, each sender uses its encryption key to encrypt a message. The router upon collecting all the n ciphertexts applies the routing token to permute them and convert them into n transformed ciphertexts, and delivers each receiver a single transformed ciphertext. Each receiver learns their message by decrypting the received ciphertext with their key. The computation of the permuted ciphertexts can be viewed as the router obliviously applying the routing permutation Ã, without learning Ã.
NIAR was shown to have numerous applications in [SW21] including realizing a non-interactive anonymous shuffle (NIAS) where n senders send encryptions of their private messages to an entity called shuffler who, upon decryption, learns a permutation of the senders' messages, without learning the mapping between each message and the corresponding sender. A NIAS scheme can be used to instantiate the shuffle model adopted in a line of work on distributed, differentially private mechanisms [CSU + 19, BBGN19b, GPV19, EFM + 19, BEM + 17, BBGN19a]. We can realize such a NIAS construction from NIAR by having the shuffler act on behalf of the NIAR router and all n receivers, as long as the underlying NIAR scheme provides meaningful security even when all the receivers collude with the router -termed as receiver-insider security by Shi and Wu [SW21].
Shi and Wu [SW21] give a NIAR scheme that satisfies receiver-insider security assuming the hardness of the decisional linear problem. Their scheme not only supports an unbounded number of time steps, but also has good efficiency features: each sender only needs to send O ¼ (1) bits per time step to encrypt a bit,foot_0 moreover, the sender and receiver keys are O ¼ (1) and the public parameters are O ¼ (n) in size. However, Shi and Wu's scheme suffers from two main drawbacks.
• First, their token size and router computation per time step are both quadratic in the number of users n, that is, O ¼ (n 2 ). We also stress that the quadratic router computation drawback pertains not only to the work of Shi and Wu [SW21]. As Gordon et al. [GKLX22] pointed out, even in classical, interactive anonymous routing constructions [Cha81, Cha88, HEK12, SA19], the total router computation is typically Ω(nm) where n and m denote the number of clients and routers, respectively -therefore, in a peer-to-peer environment where the clients also act as routers, the total computation would be quadratic in n.
• Shi and Wu's construction is proven secure only under static corruption, i.e., the adversary must specify all corrupt senders and receivers upfront. This leaves open an interesting question whether we can construct a NIAR scheme that is secure against adaptive corruptions, i.e., when the adversary can dynamically decide which players to corrupt.
The status quo gives rise to the following natural questions:
1. Can we have a NIAR scheme with subquadratic router computation?
2. Can we have a NIAR scheme secure against adaptive corruptions?
In this paper, we construct a new NIAR scheme that simultaneously answers both of the above questions affirmatively. In particular, our new NIAR construction achieves O ¼ (n) router computation per time step where O ¼ (•) hides both poly(¼, log n) factors; moreover, it achieves security in the presence of adaptive corruptions. In terms of assumptions, we need the existence of indistinguishability obfuscator (iO) [GGH + 13, JLS21, GP20, WW20, BDGM20] and one-way functions.
Theorem 1.1 (Informal: NIAR with subquadratic router computation). Let ¼ be a security parameter. Let n = n(¼) be the number of senders/receivers. Then, assuming the existence of indistinguishability obfuscator and one-way functions, there exists a NIAR scheme (in the receiver insider protection setting) that satisfies security under adaptive corruptions. Further, the asymptotical performance bounds are as follows:
1. the token size and router computation per time step is O ¼ (n);
2. the per-sender communication and encryption time per bit of the message is O ¼ (1);
3. each sender key is of length O ¼ (1), each receiver key is of length O ¼ (1).
Technical highlights. The above result is obtained through a sequence of stepping stones.
• Techniques for reasoning about a network of obfuscated programs. First, we show how to achieve the desired efficiency, but under a relaxed notion of security, that is, assuming static corruptions and a selective, single-challenge setting. To achieve this, we use a gate-by-gate obfuscation approach. Specifically, we break up one big circuit into a network of smaller circuits to obfuscate, through the use of a quasilinear-sized routing network. In this network, each smaller circuit is of size polylogarithmic in the number of senders, thus helping us meet our efficiency goals even after obfuscating each of the smaller circuits. We also devise new techniques for reasoning about a network of obfuscated programs. Specifically, we propose a new notion of a Somewhere Statistically Unforgeable (SSU) signature which may be of independent interest, and we show how to construct SSU signatures from either iO + one-way functions, or from fully homomorphic encryption.
• New techniques for upgrading from selective and static security to fully adaptive security. Next, we want to remove the static corruption and selective-single-challenge restrictions. What is interesting is that the standard complexity leveraging techniques completely fail in our context due to our efficiency requirements. Therefore, we devise various new techniques for upgrading the security of the scheme, which eventually gets us the final result. An important consequence of our techniques is that we only incur a polynomial security loss when performing the upgrades. A key insight in our upgrade is to consider the following single-inversion restriction on the adversary: it must submit two permutations seperated by a single inversion in the two worlds, i.e., the two permutations are almost identical except for swapping the destinations of a pair of senders. We prove that security w.r.t. a single inversion is in fact equivalent to security w.r.t two arbitrary permutations.
Along the way, we also explore the relationship of different definitions of NIAR security, and get several additional results (see Section 1.2) which may be of independent interest.
Impossibility of simulation security for adaptive corruptions. Shi and Wu [SW21] showed that assuming static corruption, indistinguishability-based security is equivalent to simulationbased security for NIAR. We revisit the two definitional approaches in the context of adaptive corruption. Somewhat surprisingly, we show that indistinguishability-based security and simulationbased security are not equivalent in the context of adaptive corruption. In our paper, we focus on achieving indistinguishability-based security under adaptive corruptions, since we prove that the simulation-based notion is impossible for adaptive corruptions. However, our construction does satisfy simulation-based security under static corruptions due to the equivalence of the two notions under static corruptions.
Theorem 1.2 (Informal: Impossibility of simulation security for adaptive corruptions). There does not exist a NIAR scheme (in the receiver insider protection setting) that achieves simulation-based security under adaptive corruptions (even with subexponential security assumptions).
Adaptively secure NIAR with O(n 2 ) router computation from standard assumptions.
Our techniques for upgrading from selective/static to adaptive security can be of independent interest. For example, we can apply the same upgrade techniques to the previous NIAR scheme by Shi and Wu [SW21], which gives an adaptively secure NIAR scheme with O ¼ (n 2 ) router computation from standard assumptions.
Corollary 1.3 (Informal: quadratic computation NIAR scheme assuming bilinear maps). Assume standard bilinear map assumptions. There exists a NIAR scheme (in the receiver insider protection setting) that satisfies security under adaptive corruptions, and the asymptotical performance bounds are as follows:
1. the token size and router computation per time step is O ¼ (n 2 );
2. the per-sender communication and encryption time per bit of the message is O ¼ (1);
3. each sender key is of length O ¼ (1), each receiver key is of length O ¼ (1).
Static-to-adaptive-corruption compiler for other settings. In Appendices H and I, we show that our static-to-adaptive-corruption compiler also works for non-interactive differentially anonymous router schemes as introduced by Bünz et al. [BHMS21], and NIAR schemes with sender insider protection as introduced by Bunn et al. [BKO22].
Techniques for reasoning about a network of obfuscated programs. To the best of our knowledge, the only other works that used the gate-by-gate obfuscation technique are the Jain and Jin [JJ22] and Canetti et al. [CLTV15]. However, our techniques are fundamentally different in nature from the previous works. With Jain and Jin's techniques, the evaluator will need to spend poly(n) time to evaluate each obfuscated gate whereas for our construction, each obfuscated gate takes only poly(¼, log n) time to evaluate, which is important for our efficiency claims. Our network of iOs idea also differs fundamentally from Canetti et al. [CLTV15], which builds leveled fully-homomorphic encryption scheme from iO. In our setting, there are multiple encrypters some of whom may be corrupt, whereas in the setting of Canetti et al. [CLTV15], there is a single encrypter who is assumed to be honest -so their setting is a lot easier. Another line of works [CHJV14, KLW15, BGL + 15, AJS17, JJ22] constructs indistinguishability obfuscation for Turing machines and RAM programs. A natural question is whether obfuscating the routing network modelled as a Turing machine or RAM program can result in the required sub-quadratic routing efficiency. Unfortunately, prior approaches [CHJV14, KLW15, BGL + 15, AJS17, JJ22] suffer from evaluation time that is polynomial in the input length -in the case of the routing network, it would result in poly(n) runtime. Therefore, we cannot directly use existing iO for Turing machines or RAMs as a blackbox to achieve the desired efficiency. This is also another way to see why our results are non-trivial.
Additional related work. The recent work of Bünz, Hu, Matsuo and Shi [BHMS21] made an attempt at answering the question. They could not fully achieve the above goal, but did suggest a scheme with O(¼ 1 µ • n 1+µ ) router computation for any µ ∈ (0, 1). Their scheme has two significant drawbacks. First, their subquadratic router computation comes at the price of relaxing the security definition to (ϵ, ¶)-differential privacy [DMNS06]. In other words, their scheme ensures that the adversary's views are indistinguishable only for two neighboring routing permutations (whereas full security requires indistinguishability for any two routing permutations). Not only is differential privacy a significantly weaker security notion, it can also leads to additional complications in terms of managing the privacy budget. Second, their poly(¼) dependency is not a fixed one -to improve the dependence on the parameter n, we want to choose an arbitrarily small µ, however, this would significantly blow up the polynomial dependence on the security parameter ¼.
Comparison with concurrent work. We stress that in this paper, we focus on constructing a NIAR scheme whose security is sufficient for instantiating a non-interactive anonymous shuffler. As mentioned earlier, the shuffler application is important in the context of distributed differentially private mechanisms in the so-called "shuffle model". For this application to work, we need the NIAR scheme to satisfy a notion of security called receiver-insider protection, that is, corrupt receivers (possibly colluding with the router and some corrupt senders) should not learn which honest senders have sent the message.
In comparison, the elegant concurrent work by Bunn, Kushilevitz, and Ostrovsky [BKO22] solves the dual problem as ours. Their syntax is the same as ours, but their security guarantees are for the sender insider protection setting, and are not sufficient for instantiating the shuffler application. In particular, in the sender insider protection setting, corrupt senders (possibly colluding with the router and some corrupt receivers) should not learn which honest receivers are receiving their messages.
From a technical standpoint, sender insider protection is akin to Private Information Retrieval (PIR) [CGKS95,CG97]. In fact, if we allow quadratic router computation, a NIAR scheme with a sender insider protection is implied by PIR which is known from standard, polynomial-strength assumptions. By contrast, PIR does not directly lead to NIAR with receiver-insider security (even if router computation efficiency is a non-concern). In fact, NIAR with receiver insider protection is technically akin to multi-client functional encryption (MCFE) with function-hiding security. Technically, a NIAR scheme with receiver-insider protection implies a function-hiding MCFE for the selection functionality with the bounded, upfront key queries 2 . So far, the only known way to achieve receiver-insider security (i.e., the work by Shi and Wu [SW21]) also uses function-hiding, multi-client functional encryption as a building block. For this reason, receiver insider protection is technically more challenging based on the existing knowledge and techniques.
Bunn et al. [BKO22] did not discuss the issue of adaptive corruption in the context of their primitive. Interestingly, our work's static-to-adaptive compiler can also be applied to their sender insider protection setting.
Finally, from a technical perspective, Bunn et al.'s main idea is to use a rate-1 PIR scheme where they reuse the clients' PIR queries at the router over multiple sessions. To cut the router computation to quasi-linear, they also rely an oblivious routing network. In their paper, they construct and analyze a new oblivious routing network for this purpose. Alternatively, they can also directly use the same oblivious routing network that we use in our paper, which is directly borrowed from the earlier algorithms literature [ACN + 20, RS21].
Open questions. Our feasibility results naturally raise several open questions for future work. Can we achieve subquadratic router computation from standard assumptions without using indistinguishability obfuscation? Can we construct a scheme with good concrete performance? Can we strengthen the security of the scheme to get full insider protection (as defined by [SW21]) from standard assumptions?
To get the above result, we had to go through multiple intermediate steps, where we first construct schemes with relaxed security notions and then gradually lift them to full security. In this process, we develop several interesting new techniques and building blocks that may be of independent interest. At a very high level, our blueprint and techniques are summarized below:
Our first step is to construct a NIAR scheme with quasilinear router computation, but we relax the definitions and only require security when the adversary has to upfront commit to 1) all corrupt senders and receivers and 2) a single challenge time step along with the corresponding challenge plaintext vectors. In this step, we encounter multiple challenges.
Definitional challenge for single, selective security. First, it turns out that even defining a meaningful selective notion of security (in the static corruption setting) is non-trivial, because it is unclear how the non-challenge rounds should behave. This definition should satisfy two goals: first, the non-challenge rounds should contain no information about the permutation. This is because our techniques below crucially rely on this. Second, the definition should generalize naturally to full security. We discuss these issues in more detail in Appendix D.
Gate-by-gate obfuscation for efficiency. Next, we consider how to get a NIAR scheme with quasilinear router computation under the relaxed security. To start with, it is helpful to imagine an inefficient scheme where the router's token is an obfuscated circuit that encodes the entire permutation à as well as encryption and decryption keys. Now, upon receiving the n incoming ciphertexts, the obfuscated circuit decrypts the incoming ciphertexts, applies the permutation Ã, and reencrypts the outcomes using each receiver's respective key. The intuition if we treat the obfuscation as a black box which completely hides its internals, then it should hide everything about à and the honest parties' plaintexts beyond what the corrupted parties are allowed to decrypt.
There are two problems with this approach. First, the seminal work of [BGI + 01] showed that it is impossible to achieve an "virtual black-box" (VBB) obfuscation scheme that perfectly hides its internals. Second, even forgetting about the security analysis, all known obfuscation schemes have large polynomial blowup in the input size; there is no obfuscation scheme that even comes close to a quadratic blowup, let alone subquadratic. This clearly does not meet our efficiency requirement.
Our idea to solve this efficiency problem is to break up one big circuit into a network of smaller circuits to obfuscate, through the use of a quasilinear-sized routing network. In this routing network, each gate has only polylogarithmically sized inputs and outputs, and there are O(n) such gates. Now, if we obfuscate each gate separately and create a network of obfuscated gates, then the total size of all obfuscated gates would be quasilinear.
It turns out that this idea would only work if the underlying routing network has a special "obliviousness" property, that is, a corrupt sender cannot infer from its own route the destinations of honest senders (see Definition B.1). Fortunately, we were able to get such a routing network using known techniques from the oblivious sorting literature (although the notion of "obliviousness" there is of a different nature).
New techniques for reasoning about a network of obfuscated programs. We now turn to the challenges involved in reasoning about the security of "networked obfuscated programs". To solve these challenges, we develop techniques which we believe have potential to be useful in future applications. In particular, when the output of one obfuscated gate is fed into another, we want to ensure that the adversary does not tamper with the output in between. To achieve this, we would like to have each obfuscated gate authenticate its own outputs, and have the next obfuscated gate verify the authentication information before proceeding to the computation.
As mentioned before, it is well-known that VBB obfuscation is impossible, and it is only possible to achieve a much more restrictive notion called indistinguishability obfuscation (iO). iO achieves a much weaker notion of security: it only guarantees that obfuscations of two functionally equivalent programs are indistinguishable. As is evident from prior works, computationally secure primitives are generally incompatible with the functional equivalence requirements of iO. Therefore, we need to develop new iO-compatible techniques for authentication.
A new notion of somewhere-statistically-unforgeable signatures. To this end, one of our contributions is to introduce a new building block called a Somewhere Statistically Unforgeable (SSU) signature scheme. Informally, in an SSU signature scheme, there are three modes to sample the signing and verification keys: normal mode, punctured mode, and the binding mode.
• Normal mode: the signing and verification keys behave same as in standard digital signatures.
• Punctured mode: the signing key is punctured w.r.t. a set of points X but the verification key is normal. Intuitively, this means that no valid signature can be computed using the signing algorithm for points outside of the set X when using the punctured signing key.
• Binding mode: here, both the signing and verification keys are binding w.r.t. a sets of points X. Intuitively, this means that, with overwhelming probability, no valid signatures exist for points outside of the set X w.r.t. a randomly sampled binding verification key. In other words, this means that statistical unforgeability holds somewhere (points outside the set X) in the binding mode.
SSU signatures can be used to sign/verify tuples of the form (t, m), where t denotes a round and m denotes a message. For a fixed round t * and message m * , we specifically focus on a set X t * ,m * which contains pairs (t, m) as follows:
• For all t ̸ = t * , (t, m) ∈ X t * ,m * for all m ∈ {0, 1} len .
• For t = t * , there is a single pair (t * , m * ) ∈ X t * ,m * , and for all
Intuitively, we can use this restriction to restrict the behavior of the network of circuits during the challenge round t * . Note that both the round t * and the message m * must be fixed when generating the keys of the signature scheme, hence (among other reasons) why the techniques here achieve a selective notion of security for the NIAR scheme.
For our network of iO proof to go through, we need the following important property from the SSU signature. We require that the distributions to be computationally indistinguishable: punctured signing key, normal verification key ≡ c binding signing key, binding verification key This property is critical when we perform a layer-by-layer hybrid argument in our proofs.
We stress that for technical reasons explained below, this property is important for our "networked obfuscated programs" techniques to work. This property also differentiates our SSU signature scheme from previous known puncturable signature schemes [HIJ + 17, BSW16, GWZ22]. The main difference from previous puncturable signature schemes is that we need the two verification keys to be indistinguishable even in the presence of some signing key, whereas the previous schemes required that the two verification keys be indistinguishable in absence of any signing key.
We show how to construct such a SSU signature scheme from puncturable PRFs, single-point binding (SPB) signatures, and single-point binding (SPB) hash functions 3 . In Section 2.4, we provide some intuition of how we constuct such SSU signatures. We know how to construct puncturable PRFs from one-way functions [GGM86, BW13, BGI14, KPTZ13], SPB signatures from one-way functions [GWZ22], and SPB hash function from indistinguishability obfuscation or leveled fully homomorphic encryption [GWZ22]. Plugging in these instantiations, we obtain the following theorem which may be of independent interest: Theorem 2.1 (Informal: SSU signatures). Assuming the existence of one-way functions and indistinguishability obfuscation, or assuming leveled fully homomorphic encryption, there exists a somewhere statistically unforgeable signature scheme for the family of sets X t * ,m * defined above.
Network of iOs: proof highlight. We sketch our proof outline, focusing on the part that makes use of the aforementioned property of our SSU signature. In our construction, a ciphertext encrypts the message as well as the route it should be sent along. Imprecisely speaking then, each gate does the following: decrypts the incoming ciphertexts and verifies the input message signature (to authenticate the message) and route signature (to authenticate the route); and if valid, it performs the routing, encrypts the output messages (along with the routing information), and uses an output signing key to sign them. Our proof goes through a sequence of hybrids sketched belowfoot_3 .
• First, starting from the real-world experiment, through a sequence of hybrids, we hard-wire the route signatures on corrupt wires (which are shared across all time steps) -we defer the details of these hybrids to the subsequent technical sections so we can focus on the part of proof that uses aforementioned property of our SSU signatures.
• Next, through a layer-by-layer hybrid sequence, we want to switch to a world in which for challenge time step t * , honest and filler wires' ciphertexts and signatures (for both messages and routes) are hard-wired in the obfuscated gate and the obfuscated gate only accepts an incoming ciphertext that matches the hiredwired one. Except for the honest-to-corrupt wires in the last layers which are hard-wired encryptions of the actual messages to be received by the corrupt receiver, for all other honest/filler wires, the hired-wired ciphertexts are encryptions of fillers.
In this new world, the challenge ciphertexts for honest senders are also random encryptions of fillers; therefore, for the challenge time step t * , the adversary's view contains no information about honest-to-honest and honest-to-corrupt routes, as well as honest-to-honest messages.
As described below, this layer-by-layer hybrid is where we critically need the aforementioned security property from the SSU signatures.
-Assuming that layer i's input verification key is already switched to binding, we can then switch layer i's output signing key to a punctured signing key by using iO security (since the binding verification key already ensure that the punctured messages will never pass through); -Next, we make the following replacement by relying on the security of the SSU signature scheme:
(punctured signing key: layer i, normal verification key: layer i + 1) =⇒ (binding signing key: layer i, binding verification key: layer i + 1)
-At this moment, by relying on iO security, we can hard-wire the ciphertexts and signatures for t * on honest/filler wires, such that the obfuscated gate only accepts the input on the wire if it matches the hard-wired value.
Recall that the techniques above are able to achieve a limited notion of security, which we call "selective single-challenge" security. The selective notion requires that the adversary submit not just two permutations à (0) and à (1) upfront, but additionally commit to both a challenge round t * and the set {x
u,t * } u∈H S of challenge plaintexts to be used during round t * for the honest senders H S , two for each honest sender. Recall that we use the SSU signature scheme above, and we puncture the signing and verification keys at round t * and at the target plaintexts, which we hardcode in the obfuscated gates during the inner hybrids. This is essentially why we need this data upfront.
Standard complexity leveraging fails. The standard tool to achieve such a transformation is complexity leveraging. Namely, to run the adaptive-query single-challenge with the selective scheme, we guess the values t * and {x
u,t * } u∈H S at the beginning of the experiment. This incurs a security loss proportional to 2 ³ , where ³ is the number of bits needed to represent t * and {x
u,t * } u∈H S . We stress that due to our efficiency requirements, complexity leveraging fails completely even if we are willing to accept the (sub-)exponential loss in the security reduction. More specifically, ³ can be as large as O(n), which means that the selective-secure NIAR scheme would have to be 2 O(n) -secure for the reduction to be meaningful. Thus we must adopt a security parameter greater than n in all the underlying primitives, including the iO scheme, resulting in poly(n) cost and thus defeating our efficiency goals. This problem seems inherent with our techniques, because as explained above, we hardcode information about each x (b) u,t * for all honest u in the obfuscated gates.
Removing the selective challenge restriction through equivalence to single-inversion security. For removing the selective challenge restriction, our key insight is to define a singleinversion notion of NIAR security, and using single-inversion security as a stepping stone. In normal NIAR security (under static corruption), we want security to hold for two arbitrary admissible permutations. In single-inversion security, we consider two admissible permutations where only a pair of honest senders' destinations are swapped.
If we can prove equivalence to single-inversion security, then we can do the selective-query to adaptive-query upgrade for single-inversion security. In this case, a standard complexity leveraging argument has only polynomial security loss as explained below. Specifically, with single-inversion security, the reduction only needs to guess the challenge time step t * and the challenge plaintexts of the two swapped honest users in the two worlds -without loss of generality, we can assume that each sender's plaintext is a single bit, since we can always get a multi-bit scheme by parallel composition of multiple single-bit schemes. Further, we assume that the reduction is given an upper bound on the p.p.t. adversary's running time. Therefore, the space of the guesses is polynomially bounded.
The remaining technicality is proving equivalence to single-inversion security. At first sight, it might be tempting to conclude that this is obvious, since given à (0) and à (1) , we can always swap a pair of honest senders at a time to eventually transform à (0) to à (1) . However, correctly implementing this idea is subtle. Specifically, we need any pair of adjacent hybrids to be not trivially distinguishable by the adversary, where the adversary is subject to the admissibility rules of the beginning and the end hybrids. We prove that given any beginning and end hybrids, we can indeed construct a sequence of intermediate hybrids, each time swapping a pair of honest senders' destinations and their messages, such that each pair of adjacent hybrids satisfy the aforementioned constraint.
So far, we have constructed a NIAR scheme that achieves security under static corruptions but adaptive queries. The last question remaining is how to upgrade the scheme to get security even under adaptive corruptions.
A first idea that comes to mind is to again attempt complexity leveraging. Again, unfortunately, due to our efficiency requirements, complexity leveraging completely does not work even if we are willing to suffer from (sub-)exponential losses in the reduction. Suppose that the reduction guesses which set of players the adversary will corrupt. Since there are 2 n possible guesses, for the parameters to work in the complexity leveraging, we must adopt a security parameter that is greater than n in the underlying iO scheme, which results in at least poly(n) blowup.
A new compiler for upgrading to adaptive corruptions. Instead of complexity leveraging, we construct a new compiler that compiles a NIAR scheme secure under static corruption to a NIAR scheme secure under adaptive corruption, with only polynomial loss in the security reduction.
The compiler is very simple: each sender will first encrypt their plaintext using a PRF that is secure against selective opening (which is implied by standard PRF security as shown by Abraham et al. [ACD + 19]), before encrypting it using the NIAR scheme that is secure under static corruption. For proving that this construction secure against adaptive corruptions, we will go through the following key steps:
• First, suppose we want to prove single-inversion security when all the receivers are corrupt. Now, when the reduction receives the two permutations à (0) and à (1) , it may assume that only the inverted pair of senders are honest. Therefore, in this case, security under adaptive corruption is the same as security under static corruption.
• Next, still assuming that all receivers are corrupt, we want to prove security under adaptive corruption for any two arbitrary permutations. For this step, we need to prove the equivalence of security under two arbitrary permutations and single-inversion security, but now for the scenario when the senders can be adaptively corrupted. The technicalities in this proof are similar to the counterpart for the static corruption case; however, the argument becomes somewhat more involved now that the senders can be adaptively corrupt.
• Finally, we show how to remove the assumption where the receivers must be all corrupted upfront, and allow the adversary to adaptively corrupt the receivers. This step will rely on the selective-opening security of the PRF which is implied by standard PRF security [ACD + 19].
In this section, we give an informal overview of our SSU signature construction. Our scheme is inspired by the well-known Merkle signature scheme [Mer79] which can upgrade a one-time signature scheme such as Lamport signatures [Lam79] to a multi-use signature. Recall that the Merkle signature construction works as follows:
• There is a signing key and verification key pair (for a one-time signature scheme) at every node u in the tree denoted (sk u , vk u ), and the pair (sk u , vk u ) are sampled using PRF k (u). The final verification key is vk root , and the secret signing key is (k, sk root ).
• To sign a new message m, pick the next unused leaf, and consider the path from the root to the leaf. Let {vk 0 = vk root , vk 1 , vk 2 , . . . , vk d } be the verification keys corresponding to nodes on the path from the root to the selected leaf, and let {vk ′ 1 , . . . , vk ′ d } denote the verification keys for the siblings of these nodes. The signer uses sk 0 to sign H(vk 1 , vk ′ 1 ), uses sk 1 to sign H(vk 2 , vk ′
2 ), and so on where we use H(•) to denote a hash function. Finally, use sk d to sign hash of the actual message H(m). The resulting signature contains all d + 1 signatures as well as
• Verification is done in the most natural manner.
Recall that we want to construct an SSU signature scheme for the set X t * ,m * , such that in the binding mode, the only message that can be signed for the time step t * is m * . We will modify the Merkle signature scheme as follows:
• Imagine that each leaf of the tree corresponds to some time step t. To sign a message x under the time step t, the signer will use the leaf node corresponding to t.
• We use a punctured PRF instead of a standard PRF to generate the (vk u , sk u ) pair for every tree node u.
• Instead of an arbitrary one-time signature scheme, we want to use a one-time signature scheme with a single-point binding (SPB) property, that is, there is a binding setup which takes a message m * as input, and generates a verification key vk * such that the only message that can pass verification is m * ; and moreover, a computationally bounded adversary cannot tell that vk * is generated using the binding mode.
• Instead of using a normal hash function H(•), we will use a single-point binding (SPB) hash function. We will create one SPB hash instance per level of the tree, and include the hash keys in both the signing and verification keys. An SPB hash function has a binding setup mode that takes m * as input and generates a binding hash key hk * such that m * does not have any collision; moreover, a computationally bounded adversary cannot tell that hk * is a binding key.
Punctured key. To puncture the signing key such that one can sign only x * at t * , puncture the PRF key such that one is unable to compute the signing and verification key pairs on the path from the root to the leaf t * . Additionally, we can use the unpunctured key to pre-sign the message m * and t * and include this signature in the punctured signing key.
Binding key. For the binding-mode setup, we want to generate a binding signing key and a binding verification key such that for t * , only the message x * has a unique valid signature. The binding mode also punctures the PRF key in the same way as the punctured mode. However, for the path from the root to the leaf at t * , we no longer generate the (sk u , vk u ) honestly by using the unpunctured PRF key. Instead, we will call the binding setup of the SPB signatures and SPB hashes. Specifically, on the path from the root to the leaf t * , we will run the binding setup algorithms of the SPB signature scheme such that at the leaf t * , we can only sign hash of t * ||x * ; and at any non-leaf node on the path, we can only sign a unique hash (of the two children's verification keys). Further, we run the binding setup algorithms of the SPB hash functions, such that at level i of the tree, the pair (vk i , vk ′ i ) to be hashed has no collisions, where (vk i , vk ′ i ) are verification keys corresponding to the level-i node on the path to leaf t * (recall that vk i is generated using the binding mode of the SPB signature), and its sibling. After we generate all these keys, we again pre-sign (t * , x * ) using these keys.
As a result, the binding verification key is vk root and the hash keys which are generated using the binding mode of the SPB signature and hash schemes; and the binding signing key is the punctured PRF key, as well as the pre-signed signature for (t * , m * ), and the binding hash keys.
Formal description and proofs. We defer the formal description of the SSU signature and its proofs to Section 5 and Appendix C.
Organization of rest of the paper. In Section 3, we define NIAR, and in Section 4 and Appendix B, we present preliminaries. In Section 5, we define SSU signatures and in Appendix C, we present a construction along with proofs of correctness and security. In Section 6, we construct a NIAR scheme secure against a static and all-receiver-corrupting adversary and present the security proof in Appendices D and E. In Appendix F, we present a compiler that transforms the above NIAR scheme to one with full security, i.e., removing the static and all-receiver-corrupting restrictions on the adversary. In Appendices H and I, we show that this compiler also works for differentially anonymous and sender insider protection settings. In Appendix G, we present the impossibility of NIAR simulation security for adaptive corruptions.
In this section, we define the syntax and security for NIAR, focusing on the strongest definition of full security against adaptive corruptions.
We begin with the syntax. A Non-Interactive Anonymous Router (NIAR) is a cryptographic scheme consisting of the following, possibly randomized algorithms:
len, n, Ã): the trusted Setup algorithm takes the security parameter 1 ¼ , the length of the messages len, the number of senders/receivers n, and a permuation Ã. The algorithm outputs a sender key for each sender denoted {ek u } u∈[n] , a receiver key for each receiver denoted {rk u } u∈[n] , and a token for the router denoted tk. • ct u,t ← Enc(ek u , x u,t , t): sender u uses its sender key ek u to encrypt the message x u,t ∈ {0, 1} len where t denotes the current time step. The Enc algorithm produces a ciphertext ct u,t . • (ct ′ 1,t , ct ′ 2,t , . . . , ct ′ n,t ) ← Rte(tk, ct 1,t , ct 2,t , . . . , ct n,t ): the routing algorithm Rte takes pk and its token tk (which encodes some permutation Ã), and n ciphertexts received from the n senders denoted ct 1,t , ct 2,t , . . . , ct n,t , and produces transformed ciphertexts ct ′ 1,t , ct ′ 2,t , . . . , ct ′ n,t where ct ′ u,t is destined for the receiver u ∈ [n]. • x ← Dec(rk u , ct ′ u,t , t): the decryption algorithm Dec takes a receiver key rk u , a transformed ciphertext ct ′ u,t , a time step t, and outputs a message x. Correctness of NIAR. Correctness requires that with probability 1, the following holds for any ¼, len ∈ N, any (x 1 , x 2 , . . . , x n ) ∈ {0, 1} len•n , and any t: let ({ek u
In this section, we present a security notion for NIAR against a very strong adversary. In particular, we allow such an adversary to (a) adaptively corrupt the set of senders and receivers, and (b) adaptively ask for encryptions of chosen plaintext under the senders' keys that are not yet corrupted. Our security definition is a strict generalization of the "receiver-insider corruption" notion introduced by Shi and Wu [SW21] which captured only static corruptions of users.
We formalize our definition via the experiment NIARFull b,A which is parametrized by some challenge bit b and a stateful non-uniform p.p.t. adversary A. At the beginning of the experiment, adversary A submits two challenge permutations à (0) and à (1) over [n] for its choice of n. At any time in the experiment, the adversary can choose to corrupt a sender or receiver, and it will receive the secret key for the newly corrupted player. The adversary receives tk, and then in each time step, it can submit two plaintext vectors {x
u,t } u∈H S for the set of currently honest senders H S . The challenger will encrypt the plaintexts indexed by b ∈ {0, 1}, and at the end of the experiment, the adversary's job is to distinguish which world b the challenger is in. The adversary must be subject to a set of admissibility rules such that it cannot trivially distinguish which world it is in.
More formally, our full NIAR security game is defined as follows, where Cor(•) is the following oracle: upon receiving a sender or receiver identity,
• return its corresponding secret key;
• in case the newly corrupted player is a sender, additionally return all the historical random coins consumed by the Enc algorithm during the previous time steps;
• update the honest sender set H S and honest receiver set H R accordingly.
NIAR full security experiment NIARFull b,A (1 ¼ ).
1. (n, len, Ã (0) , Ã (1) ) ← A(1 ¼ ).
2.
4. For t = 1, 2, . . .:
• for all u ∈ H S , CT u,t ← Enc(ek u , x (b) u,t , t).
A may halt and output an arbitrary function of its view. The experiment then also halts and returns the output of A.
In the above definition, if the adversary wants to specify an initially corrupt set, it can simply make calls to the corruption oracle Cor(•) at the beginning of t = 1. Therefore, without loss of generality, we may assume that the initially corrupt set before the challenger calls Setup is empty.
Admissibility. We state some admissibility rules on the adversary to make sure that the adversary cannot trivially distinguish whether it is in world b = 0 or b = 1. Our admissibility rule corresponds to the "receiver-insider protection" version of Shi and Wu [SW21], which is sufficient for building a non-interactive anonymous shuffler. Basically, we assume that senders know their receivers but receivers do not know their senders. Therefore, if the adversary corrupts some senders, the adversary will know the corrupt senders' receivers. We remark that Shi and Wu [SW21] additionally described a "full insider protection" notion where it is assumed that neither senders nor receivers know who they are paired with. Their "full insider protection" construction requires polynomial in n evaluation time and uses indistinguishable obfuscation and bilinear group assumptions [SW21]. It remains an open question how to reduce the evaluation time for the "full insider protection" version.
Henceforth, if a player remains honest at the end of the execution, we say that it is eventually honest; otherwise we say that it is eventually corrupt. We say that A is admissible iff with probability 1, the following holds where H S and H R refer to the eventually honest sender and receiver set, and define K R = [n] \ H R , K S = [n] \ H S to be the eventually corrupt sender and receiver sets:
1. For all eventually corrupt senders u ∈ K S , Ã (0) (u) = Ã (1) (u).
2. For any eventually corrupt sender u ∈ K S , for any t in which u was not corrupt yet, x (0)
In other words, here we require that in the two alternate worlds b = 0 or b = 1, every eventually corrupt sender should be sending the same message in all rounds before it was corrupted.
3. For all rounds t, and for any v
u 1 ,t where for b ∈ {0, 1}, u b := (Ã (b) ) -1 (v). In other words, here we require that in the two alternate worlds b = 0 or 1, every eventually corrupt receiver receiving from an eventually honest sender must receive the same message in all rounds. Definition 3.1 (NIAR full security). We say that a NIAR scheme is fully secure iff for any nonuniform p.p.t. admissible A, its views in the two experiments NIARFull 0,A (1 ¼ ) and NIARFull 1,A (1 ¼ ) are computationally indistinguishable.
Whenever we refer to an adversary in the paper henceforth, we implicitly mean it to be a non-uniform adversary. We discuss the notations next and defer the additional preliminaries to Appendix B.
We say that a function negl : N → R is negligible, if for every constant c > 0 and for all sufficiently large ¼ ∈ N we have negl(¼) < ¼ -c . Two distribution ensembles {X ¼ 0 } ¼ and {X ¼ 1 } ¼ are computationally indistinguishable if for every p.p.t. adversary A, there exists a negligible function negl(•) such that for all
. We use ' ' to denote that a value is irrelevant. For instance, in (a, , c) the second value is irrelevant and can be anything. Often times, we use a short hand {y i : i ∈ [n]} to denote an ordered sequence (y 1 , . . . , y n ). For instance,
In this section, we define SSU signatures and provide an informal construction.
We consider an SSU signature scheme where the signing and verification algorithms both take a counter t (i.e., time step) in addition to the message x to be signed. We refer to t as the round. Specifically, an SSU signature scheme contains the following algorithms:
• (sk, vk, pp) ← Setup(1 ¼ , tlen, len): takes as input the security parameter 1 ¼ , the length of the round tlen g 0, the length of the messages to be signed len > 0, and outputs a signing key sk, a verification key vk, and a public parameter pp.
• à ← Sign(pp, sk, t, x): a deterministic algorithm that takes as input a public paramter pp, a singing key sk, along with a round t ∈ {0, 1} tlen (t = § in case tlen = 0) and a message x ∈ {0, 1} len and outputs a signature à for x w.r.t. t.
• (0 or 1) ← Vf (pp, vk, t, x, Ã): takes as input a public paramter pp, a verification key vk, a round t, a message x, and a signature Ã, and outputs either 1 for accept or 0 for reject.
• (sk, sk, vk, pp) ← PuncturedSetup(1 ¼ , tlen, len, t * , x * ): takes as input the security parameter 1 ¼ , the length of the round tlen, the length of the messages to be signed len, a round t * ∈ {0, 1} tlen (t * = § in case tlen = 0) and a message x * ∈ {0, 1} len , and outputs a signing key sk, a punctured signing key sk, a verification key vk, and a public paramter pp.
• (sk * , vk * , pp * ) ← BindingSetup(1 ¼ , tlen, len, t * , x * ): takes as input the security parameter 1 ¼ , the length of the round tlen, the length of the messages to be signed len, a round t * ∈ {0, 1} tlen (t * = § in case tlen = 0) and message x * ∈ {0, 1} len , and outputs a binding signing key sk * , a binding verification key vk * , and a binding public paramter pp * .
• à ← PSign(pp, sk, t, x): a deterministic algorithm that takes as input a public paramter pp, a punctured signing key sk generated by PuncturedSetup, a round t and a message x, and outputs a signature à for x w.r.t. t.
Correctness of SSU signature. An SSU signature is said to be correct iff the following holds,
Definition 5.1 (Security for SSU Signatures). An SSU signature is said to be secure if it has the following properties:
• Identical distribution of normal keys output by Setup and PuncturedSetup. For any ¼, len, tlen ∈ N, any t * ∈ {0, 1} tlen , any x * ∈ {0, 1} len , we have the following where ≡ denotes identical distribution:
• Indistinguishability of punctured and binding setups. For any len and tlen that are polynomially bounded by ¼, any t * ∈ {0, 1} tlen , any x * ∈ {0, 1} len , we have the following where ≈ denotes computational indistinguishability:
• Statistical unforgeability at (t * , x * ). For any len, tlen that are polynomially bounded in ¼, there exists a negligible function negl(•), such that for any t * ∈ {0, 1} tlen , x * ∈ {0, 1} len , for any ¼,
Let Σ = (Σ.Gen, Σ.Sign, Σ.Vf , Σ.GenBind) be a single-point binding (SPB) signature scheme. Let H = (H.Gen, H.Hash, H.GenBind) be a single-point binding (SPB) hash function. Let PPRF be a puncturable PRF. The SSU signature scheme is based on a binary tree of SPB signatures intuitively described in Figures 1a and 1b. We present the formal construction in Appendix C. (a) Sign and PuncturedSetup. For each node u i , (sk ui , vk ui ) is generated using Σ.Gen with PPRF.Eval(K, u i ) as the randomness seed. A signature à on message x for t = 2 consists of à := ((à 0 , vk u1 , vk sib1 ), (à 1 , vk u2 , vk sib2 ), (à 2 , vk u3 , vk sib3 ), à 3 ). PuncturedSetup at the point (t, x) outputs a punctured key sk that consists of the PPRF key punctured at the set {u 0 , u 1 , u 2 , u 3 } and Ã.
( vk u3 , σ 3 ) = GenBind( Hash( hk 3 , t || x ) )
( vk u2 , σ 2 ) = GenBind( Hash( hk 2 , vk u3 || vk sib3 ) )
is generated using Σ.GenBind with PPRF.Eval(K, u i ) as the randomness seed. BindingSetup at the point (t, x) outputs a binding key sk * that consists of the PPRF key punctured at the set {u 0 , u 1 , u 2 , u 3 } and a signature à on message x for t = 2, where à := ((à 0 , vk u1 , vk sib1 ), (à 1 , vk u2 , vk sib2 ), (à 2 , vk u3 , vk sib3 ), à 3 ).
In this section, we first introduce a basic NIAR scheme which we prove secure under an adversary who is restricted to make all corruption queries upfront, and moreover, it must always corrupt all receivers -we call such an adversary a static, all-receiver-corrupting adversary. This is same as the adversary in the full security game in Definition 3.1 except with the aforementioned restrictions.
For sake of completeness, we define this version of security in Definition A.1.
Later in Appendix F, we give a compiler that transforms the scheme in this section to one with full security, i.e., removing the static and all-receiver-corrupting restrictions on the adversary. Notation. To describe our construction more formally, it will be helpful to introduce some notation for the routing network. Recall that a routing network for n senders and n receivers is a layered directed acyclic graph that has O(log n) layers numbered from 0, 1, . . . , L. Each sender u ∈ [n] is assigned to the (2u -1)-th wire in the input layer (i.e., layer-0), and each receiver v ∈ [n] is assigned to the (2v -1)-th wire in the output layer (i.e., layer-L). Let G be the number of gates contained in each of the L -1 intermediate layers. There are (L -1) • G gates overall, and we refer to the g-th gate in the ℓ-th layer by the tuple (ℓ, g)
be the number of incoming and outgoing wires in each gate. Overall, there are L × [2n] wires where we index the i-th wire in the ℓ-th layer by the tuple (ℓ, i) 5 We refer to the W incoming wires of every gate (ℓ, g) by the set Input (ℓ,g) ¦ [2n] and the W outgoing wires by the set Output (ℓ,g) ¦ [2n]. In other words, the wires coming into gate (ℓ, g) are the set {(ℓ, w)} w∈Input (ℓ,g) , and the wires outgoing from gate (ℓ, g) are the set {(ℓ + 1, w)} w∈Output (ℓ,g) . Finally, recall that a route rte u from sender u to receiver v is a sequence of wires (j 1 , . . . , j L ) where j ℓ is a wire in the ℓ-th layer for all ℓ ∈ [L]. Based on the description of routing network, also recall that
Simplifying assumption. Throughout this section, we shall assume that the message length len = 1. This assumption is without loss of generality, since we can always parallel-compose multiple NIAR schemes where len = 1 to get a NIAR scheme for len > 1.
We now describe our basic NIAR scheme in detail.
Keys associated with wires. In our construction, each wire (ℓ, i) in the routing network will have the following associated with it:
• A PRF key k (ℓ,i) , which will be used to encrypt and decrypt the (signed) message along with its routing information on the wire;
• A message signing key tuple (mpp (ℓ,i) , msk (ℓ,i) , mvk (ℓ,i) ), which will later be used by the correspending sender or obfuscated gate to sign the message to be sent to the wire;
• A route signing key tuple (rpp (ℓ,i) , rsk (ℓ,i) , rvk (ℓ,i) ), which will be used by the Setup algorithm to sign the routes and by the obfuscated gates to verify the routes before performing the routing.
Hardcoded values. Gate (ℓ,g) has hardcoded the following values:
• For each wire i ∈ Output (ℓ,g) in layer ℓ + 1: k (ℓ+1,i) , mpp (ℓ+1,i) , msk (ℓ+1,i) .
Procedure. Gate (ℓ,g) takes as input a round t and a set of ciphertexts {CT (ℓ,i) : i ∈ Input (ℓ,g) } corresponding to the input wires. It computes as follows.
1. For each input wire i ∈ Input (ℓ,g) :
(a) If ℓ = 1 and i is even, continue to next i. // Filler, ignored.
(b) Decrypt and authenticate the message/route:
) and parse y as (x, rte, msig).
ii. Abort if Sig.Vf (mpp (ℓ,i) , mvk (ℓ,i) , t, (x, rte), msig) = 0.
iii. If x = § filler and rte = § filler , continue to the next i. // Filler, ignored.
iv. Parse rte as (rte, rsig), rte as (j 1 , . . . , j L ), and rsig as (rsig 1 , . . . , rsig L ). Abort if
(c) Prepare the output ciphertext CT (ℓ+1,j ℓ+1 ) :
i. For convenience, set j = j ℓ+1 .
ii. If CT (ℓ+1,j) has already been computed, then abort.
iii. Else if ℓ + 1 < L (intermediate layer), first compute a new message signature msig ′ = Sig.Sign(mpp (ℓ+1,j) , msk (ℓ+1,j) , t, (x, rte)). Then, compute the ciphertext
2. For each j ∈ Output (ℓ,g) such that CT (ℓ+1,j) has not been computed yet, compute filler ciphertexts:
(a) Set x = § filler and rte = § filler .
(b) Compute msig ′ = Sig.Sign(mpp (ℓ+1,j) , msk (ℓ+1,j) , t, (x, rte)). Circuit for each gate. We first describe the circuit for each gate to be obfuscated later in our construction. The circuit Gate (ℓ,g) denotes the g-th gate in the ℓ-th layer. It receives a ciphertext on each input wire and decrypts it using a PRF key to obtain a tuple (x, rte, msig), where x is a message, rte is the authenticated route, and msig is a message signature. It verifies the message signature msig on the tuple (x, rte). Next, it performs route authentication and prepares the output ciphertext which varies depending on whether the wire is filler or not. A wire is filler if x = § filler and rte = § filler . For a filler input wire, no route authentication is performed as there is no route associated with it. Computing output ciphertext for filler output wires is deferred to later as the circuit does not know which are filler output wires at the moment. For a non-filler input wire i, the circuit parses rte = (rte, rsig) and verifies that the route rte is valid using rsig. Then, it parses rte = (j 1 , . . . , j L ). If j ℓ = i, then it finds the corresponding non-filler output wire j ℓ+1 from the rte and computes a new message signature msig ′ and then a new ciphertext for the output wire in the natural manner. At the end, all output wires which do not have any ciphertext assigned to them are interpreted as filler wires and the circuit computes message signature and ciphertext similarly by setting x = § filler and rte = § filler . In Figure 2 we describe the circuit formally and in more detail, where Sig is a SSU signature scheme constructed in Section 5 and PRF is a puncturable PRF.
We next describe the Setup algorithm.
Setup Algorithm. Given a routing permutation Ã, the Setup algorithm first sets tlen = log 2 (¼). Then, it runs the AssignRoutes algorithm to sample a set of edge-disjoint routes {rte u } u∈[n] between each sender/receiver pair. Then, for every wire (ℓ, i)
in the routing network we sample (a) PRF key k (ℓ,i) for encryption, (b) a signature key pair (rsk (ℓ,i) , rvk (ℓ,i) , rpp (ℓ,i) ) for signing routes, and (c) a signature key pair (msk (ℓ,i) , mvk (ℓ,i) , mpp (ℓ,i) ) for signing messages. Looking ahead, when proving security, the route signature keys for wires assigned to corrupt senders' routes, and the message signature keys for all other wires will be punctured to ensure "uniqueness of routes and plaintexts". Given the above set of keys, consider a sender/receiver pair (u, v) with route rte u = (j 1 , . . . , j L ). Then sender u's sender key ek u and receiver v's decryption key rk v are defined as follows, where rsig ℓ is the signature on rte u computed using the route public param rpp (ℓ,j ℓ ) and route signing key rsk (ℓ,j ℓ ) .
Lastly, the routing token tk is then defined as follows, where the circuit Gate (ℓ,g) is as described in Figure 2.
More formally, the Setup algorithm is as in Figure 3.
Setup(1 ¼ , len = 1, n, Ã): on inputs the security parameter 1 ¼ , the individual message length len = 1, the number of parties n, and the permutation Ã, Setup does the following:
1. Set tlen = log 2 (¼).
2. Sampling Routes: Run the AssignRoutes procedure (Appendix B.1) on inputs (1 ¼ , n, Ã). Abort if it outputs §. Else parse the output as a set of edge-disjoint routes {rte u } u∈[n] between each sender/receiver pair. Let 0, . . . , L be the layers in the resulting network.
Let G be the number of gates contained in each of the L -1 intermediate layers. Let W be the number of incoming and outgoing wires in each gate. Then, for all u ∈ [n], the size of the string rte u is len rte = L • log(2n).
3. Sampling Wire Keys:
(a) Sample PRF key k (ℓ,i) ← PRF.Gen(1 ¼ ) as the encryption key for this wire.
(b) To sign and verify routes of length len rte , sample route signature keys
Suppose that the resulting route signatures will be of size poly rsig (¼) for some polynomials poly rsig . Then, the messages signed will be of length
To sign and verify messages of length len m , sample message signature keys
For each sender u ∈ [n] do the following:
(a) Parse rte u = (j 1 , . . . , j L ). Sign rte u using route signing keys for each wire along rte u , that is, for ℓ ∈ [L] compute rsig ℓ = Sig.Sign(rpp (ℓ,j ℓ ) , rsk (ℓ,j ℓ ) , 1, rte).
(b) Set rte u = (rte u , rsig u = (rsig 1 , . . . , rsig L )).
5. Setting Routing Token:
6. Setting Sender Keys:
7. Setting Receiver Keys: Next, we describe how encryption, routing and decryption work.
Encryption Algorithm. For a sender u to send a message x to its receiver for time step t, the sender first computes a message signature msig for the tuple (x, rte u ) for round t, and encrypts the tuple (x, rte u , msig) using its PRF key.
Enc(ek u , x u , t) on input user u's encryption key ek u and plaintext x u and the round t, does the following:
1. Parse ek u as (k, mpp, msk, rte u ).
2. Compute the message signature msig = Sig.Sign(mpp, msk, t, (x u , rte u )).
Routing Algorithm. The router receives a routing token tk from the Setup algorithm. It consists of obfuscation of each gate in the routing network as described in Figure 2. During each round t, the router receives n ciphertexts CT 1 , . . . , CT n from the n senders. Before processing the ciphertexts through the routing network, the router sets the 2n ciphertexts CT (1,1) , . . . , CT (1,2n) for the first layer as follows. For all i ∈ [n], it sets CT (1,2i-1) = CT i as the real ciphertexts and CT (1,2i) = § filler as the filler ciphertexts, where § filler is a special string. Next, the router uses the token tk to route the 2n ciphertexts in the first layer through the routing network to obtain the 2n ciphertexts in the last layer L: CT (L,1) , . . . , CT (L,2n) . Finally, to all receivers i ∈ [n], the router sends the ciphertexts
. More formally, Rte(tk, t, CT 1 , CT 2 , . . . , CT n ) on input the router token tk along with the round number t, and ciphertexts CT 1 , . . . , CT n , does the following:
2. Compute ciphertexts for the input layer:
Compute network of iO obfuscated gates layer-by-layer, that is, for layer ℓ = 1, . . . , L -1, evaluate all the obfuscated gates at this layer as follows. For each g ∈ [G], let Input (ℓ,g) and Output (ℓ,g) be the set of input and output wires of gate Gate (ℓ,g) . Then, evaluate the circuit
Decryption Algorithm. A receiver u learns its intended message by just decrypting the received ciphertext using its PRF key. More formally, Dec(rk u , CT ′ u , t) on input user u's receiver key rk u , output ciphertext CT ′ u , and a time step t, does the following: Output y = CT ′ u • PRF(rk u , t).
Recall that we assume len = 1 since for multi-bit messages, since we can always parallel-compose multiple NIAR schemes where len = 1 to get a NIAR scheme for len > 1. In the analysis below, we argue that the router computation per time is bounded by O ¼ (n) where O ¼ hides poly(¼, log n) factors for some fixed poly(•).
Recall that the routing network consists of layers 0, . . . , L, where L = O(log n). In each of the L -1 intermediate layers, there are G = 2n/W number of gates, where W = O(log 2 ¼) is the number of incoming and outgoing wires in each gate.
Size of hardcoded values in each gate. Each incoming wire has the following hardcoded: PRF key of size poly(¼), route public parameters of size poly(¼) and route verification key of size poly(¼), message public parameters of size poly(¼) and message verification key of size poly(¼). Each outgoing wire has the following hardcoded: PRF key of size poly(¼), message public parameters of size poly(¼) and message signing key of size poly(¼, tlen) = poly(¼) as tlen = log 2 (¼).
Size of ciphertexts. Each route signature is of size poly rsig (¼). and each message signature is of size poly msig (¼). Therefore, the ciphertexts are of size tlen
Size and running time of each gate. Each gate has W incoming and outgoing wires and each gate processes W ciphertexts, where W = O(log 2 ¼). Therefore, each gate has poly(¼) amount of hardcoded information and processes poly(¼, log n) amount of inputs. Based on the operations inside each gate, we can then conclude that each gate is of size poly(¼, log n). Then, accounting for the polynomial blowup of the iO obfuscator, we can conclude that the size of each obfuscated gate is still poly(¼, log n) and the router can run each obfuscated circuit in time poly(¼, log n).
Router computation per time step. Observe that for each time step, the router computes each of the obfuscated circuits at most once. Since there are at most Õ(n) gates, we can conclude that the router computation per time step is bounded by O ¼ (n) where O ¼ hides poly(¼, log n) factors for some fixed poly(•).
Sender and recevier key sizes, computation and communication per time step. Sender key size is bounded by the size of the route which is O ¼ (1). For every sender, computation and communication per time step is O ¼ (1). Each receiver's key contains a PRF key which is O ¼ (1) in size. For every receiver, computation and communication per time step is O ¼ (1).
In Appendices D and E, we prove the following theorem, which shows that the above construction satisfies static security as long as the adversary always corrupts all receivers. In Appendix F, we give a compiler that further compiles the scheme to one that satisfies full security under adaptive corruptions, and without any restrictions on the adversary. Theorem 6.1. Suppose PRF is a secure puncturable PRF, Sig is a secure deterministic SSU signature scheme, and iO is a secure indistinguishability obfuscation scheme. Then, our NIAR construction in Section 6.1 satisfies full static corruption security (Definition A.1) subject to an all-receiver-corrupting adversary.
We give a proof roadmap of Theorem 6.1 below.
Proof roadmap. We prove Theorem 6.1 through a sequence of steps.
• In Definition D.1, we define indistinguishability w.r.t. inversions against an adversary that additionally satisfies the selective single-challenge restriction. Then, we present an Upgrade Theorem stated in Theorem D.2 which shows how to remove the selective single-challenge and inversion restrictions.
• Next, to complete the proof of Theorem 6.1, it suffices to prove security under the selective single-challenge and single inversion restrictions. We show this in Theorem E.1.
assigned destination vertex 2u -1 ∈ [2n]. Now, each producer wants to route one product to a distinct consumer, and the desired mapping between the producers and consumers is called the routing permutation Ã. Then, producer u is mapped to consumer Ã(u). In the routing network, this translates to routing producer u's product from source vertex 2u -1 to destination vertex 2Ã(u) -1. To avoid congestion, we want all n routes to be over edge-disjoint paths. Earlier works [ACN + 20, RS21] have constructed such a routing network with the following properties.
• Congestion-free routing. There exists a randomized algorithm AssignRoutes(1 ¼ , n, Ã) that takes in the security parameter ¼ and the routing permutation Ã, and with 1negl(¼) probability, outputs the following information for each producer u ∈ [n]: the path that producer u traverses to reach its consumer which is assigned to some destination vertex. Henceforth, the above information is called the route for producer u, often denoted rte u . As mentioned, all producers' routes are edge-disjoint. We allow the AssignRoutes(1 ¼ , n, Ã) algorithm to have a negligibly small failure probability in which case it outputs §.
• Layered construction. The network is layered. We may imagine that the source and destination vertices form two special layers numbered 0 and L, respectively, and all other intermediate-layer vertices are henceforth called gates. Directed edges, henceforth called wires, exist only between adjacent layers ℓ and ℓ + 1.
• Efficiency. Each gate has W = O(log
2 ¼) incoming wires and W outgoing wires. The network has O(log n) layers, and each intermediate layer has G = 2n/W gates. Each gate has O(log 2 ¼) incoming wires and O(log 2 ¼) outgoing wires. The number of wires between any two adjacent layers is exactly 2n.
• Obliviousness. The network and the corresponding AssignRoutes(1 ¼ , n, Ã) algorithm satisfies a privacy property. Informally speaking, imagine that a subset of the producers are corrupt, and they can learn their routes to their respective destinations (including which source nodes the corrupt producers are assigned to). We want that the choice of the corrupt producers' routes are independent of the honest producers' destinations. We will formally define this privacy property below.
Definition B.1 (Obliviousness of a routing network). We say that a routing network satisfies obliviousness, iff there exists another simulated AssignRoutes * algorithm and a negligible function negl(•), such that for any two routing permutations à 0 and à 1 on [n], let C(à 0 , à 1 ) be the set of senders that have the same destinations in à 0 and à 1 , it holds that for either b ∈ {0, 1}, the following two distributions have statistical distance at most negl(¼):
The definition says that the simulated AssignRoutes * algorithm takes in two routing permutations à 0 and à 1 . For a sender u ∈ C(à 0 , à 1 ) with the same destinations in à 0 and à 1 , AssignRoutes * outputs a single route rte u for u. For a sender u / ∈ C(à 0 , à 1 ) with different destinations in à 0 and à 1 , AssignRoutes * outputs two routes rte 0 u and rte 1 u for u. Not only so, for either b ∈ {0, 1}, the union of the routes for senders' in C(à 0 , à 1 ), and the b-th set of routes {rte b u } u / ∈C(à 0 ,à 1 ) for everyone else output by the simulated AssignRoutes * must be statistically indistinguishable from running the real-world AssignRoutes using permutation à b .
Intuitively, in our NIAR scheme, only those who are in C(Ã 0 , Ã 1 ) can possibly be corrupt. Therefore, the definition decomposes the generation of the possibly-corrupt sender' routes from the remaining honest senders' destinations. In this sense, the possibly-corrupt senders' routes do not leak information about honest senders' destinations (beyond what is already leaked by the possibly-corrupt senders' destinations, and barring a negligibly small statistical difference).
Remark B.2. Our definition of obliviousness is not the same as the "data obliviousness" notion of Asharov et al. [ACN + 20] and Ramachandran and Shi [RS21] -their notion requires that the access patterns of the routing algorithm not depend on the input data when executed on a RAM. On the other hand, our notion is closely related to a line of work called "oblivious routing" from the standard algorithms literature [R 02, HKLR05], where roughly speaking, we want that a player's route be independent of others' destinations.
Interestingly, it turns out that we can obtain a routing network that satisfies Definition B.
1 using techniques from Asharov et al. [ACN + 20] and Ramachandran and Shi [RS21]. Asharov et al. [ACN + 20] and Ramachandran and Shi [RS21] propose a butterfly network where each gate has polylogarithmically many incoming and outgoing wires. We can compose two instances of their butterfly network back-to-back. The first instance is to route each input element (i.e., those on input wires 2u -1 for u ∈ [n]) to a random and distinct wire in the output layer. The second instance will then route each element u to its correct destination, i.e., 2Ã(u) -1 of the output layer.
In our routing network, there are more wires in each layer than the number of producers or consumers. Therefore, some wires do not carry load. Henceforth in our paper, we also call such wires that do not carry actual load filler wires.
A puncturable pseudorandom function consists of the following algorithms:
• sk ← Gen(1 ¼ , 1 ℓ ): takes in a security parameter 1 ¼ , the length 1 ℓ of the input messages where ℓ := ℓ(¼) is a polynomial function in ¼, and outputs a PRF key K.
• Ã ← Eval(K, x): a deterministic function that takes in a PRF key K, a message x ∈ {0, 1} ℓ , and outputs the evaluation outcome Ã.
• K * ← Puncture(K, S = {x * 1 , . . . , x * |S| }): takes in a PRF key K, the set of messages S = {x * 1 , . . . , x * |S| } that the PRF key needs to be punctured on, and outputs a punctured key K * .
• Ã ← PEval(K * , x): a deterministic function that takes in a punctured PRF key K * , and a message x ∈ {0, 1} len , outputs the evaluation outcome Ã.
Correctness. We say that a puncturable PRF scheme satisfies correctness if the punctured key preserves functionality when evaluated at unpunctured points. Formally, we require that for any ¼, ℓ, any S = {x * 1 , . . . , x * |S| }, any x ∈ {0, 1} len such that x / ∈ S,
Security. We say that a puncturable PRF scheme is secure, if given a punctured key, the original PRF's evaluation outcomes at punctured points (i.e., points that the punctured key cannot evaluate) remain pseudorandom. Formally, consider the following experiment ExptPPRF A,b (1 ¼ , 1 ℓ ) parametrized by a bit b ∈ {0, 1}:
• The stateful adversary A sends a set S to the challenger. The challenger computes a PRF key K ← Gen(1 ¼ , 1 ℓ ). The challenger then computes the punctured key K * ← Puncture(K, S) and sends it back to the adversary.
• The adversary A can adaptively make evaluation queries on messages x i / ∈ S to the challenger. For each such query, the challenger responds as follows. If b = 0, it sends Eval(K, x i ) to the adversary. If b = 1, it sends a uniformly random string to the adversary.
• A outputs a guess b ′ ∈ {0, 1}, the experiment outputs b ′ . Definition B.3 (Puncturable PRF security). We say that a puncturable PRF scheme is secure iff for any ℓ polynomially bounded by ¼, for any non-uniform p.p.t. adversary A, its views in the two experiments
). If one-way functions exist, then for all efficiently computable ℓ(¼), there exists a secure puncturable PRF.
Shorthand notations. Sometimes for we use PRF(K, •) as a shorthand for PRF.Eval(K, •) and PRF(K * , •) as a shorthand for PRF.PEval(K * , •).
Single-point binding hash functions were introduced and constructed in Guan et al. [GWZ22] and Koppula et al. [KWZ22]. Here, we modify their defintion in that the GenBind algorithm additionally also outputs a normal hash key. A single-point binding hash function is a triple (Gen, Hash, GenBind) where:
• hk ← Gen(1 ¼ , 1 ℓ ): takes as input the security parameter ¼, and input length ℓ. It produces a hash key hk.
• h = Hash(hk, m ∈ {0, 1} ℓ ): deterministically produces a hash digest h whose length is some fixed polynomial in ¼ independent of ℓ.
• (hk, hk * ) ← GenBind(1 ¼ , 1 ℓ , m * ∈ {0, 1} ℓ ): takes as input ¼, input length ℓ, and a message m * , and outputs a normal hash key hk and a binding hash key hk * .
Correctness. An SPB hash function is said to be correct iff the following holds. For any ℓ which is upper bounded by some fixed polynomial function in ¼, there exists a negligible function negl(•) such that for any m * ∈ {0, 1} ℓ , for any ¼,
Security. An SPB hash function is said to be secure iff it satisfies the following properties.
• Identical distribution of normal hash keys. For any ¼, ℓ, m * ∈ {0, 1} ℓ , we have the following where ≡ denotes identical distribution.
• Indistinguishability of normal and binding hash keys. For all ℓ that is polynomially bounded by ¼, all m * ∈ {0, 1} ℓ , we have the following where ≈ denotes computational indistinguishability.
• Statistically binding at m * . For any ℓ that is polynomially bounded in ¼, there exists a negligible function negl(•), such that for all ¼, all m * ∈ {0, 1} ℓ ,
Instantiations. Guan et al. [GWZ22] provided two constructions of SPB hash functions, one from indistinguishability obfuscation, and the other from leveled fully homomorphic encryption.
Single-point binding signatures were introduced and constructed in Guan et al. [GWZ22] and Koppula et al. [KWZ22]. We will use it as a building block for our SSU signatures construction.
A single-point binding signature scheme is a quadruple of algorithms (Gen, Sign, Vf , GenBind) defined as follows:
• (sk, vk) ← Gen(1 ¼ , 1 ℓ ): is a randomized algorithm that takes as input the security parameter ¼ and message length ℓ := ℓ(¼) which is a polynomial function in ¼. It outputs a signing key sk and a verification key vk whose lengths are upper bounded by some fixed polynomial function in ¼ and ℓ.
• à ← Sign(sk, m ∈ {0, 1} ℓ ): is a deterministic algorithm that takes as input a signing key sk and a message m. It outputs a signature à whose length is upper bounded by a fixed polynomial function in ¼ and ℓ.
• (0 or 1) ← Vf (vk, m ∈ {0, 1} ℓ , Ã): is a deterministic algorithm that takes as input a verification key vk, a message m and a signature à on m and outputs 1 if the signature is valid, else 0.
: is a randomized algorithm that takes as input the security parameter ¼, message length ℓ, and a message m * . It outputs a binding verification key vk * and a signature à * on message m * .
Correctness. A single-point binding signature scheme is said to be correct iff the following holds.
• For all ¼, ℓ ∈ N, and all m ∈ {0, 1} ℓ ,
• For all ¼, ℓ ∈ N, and all m * ∈ {0, 1} ℓ ,
Security. A single-point binding signature scheme is said to be secure if it has the following properties:
• Indistinguishability of normal and binding keys. For any ℓ polynomially bounded by ¼, any m * ∈ {0, 1} ℓ , we have the following where ≈ denotes computational indistinguishability.
• Statistically binding at m * . For any ℓ polynomially bounded by ¼, there exists a negligible function negl(•) such that for all ¼, and all m * ∈ {0, 1} ℓ ,
This means that with overwhelming probability over the choice of the binding verification key vk * output by GenBind, any message m ̸ = m * does not have a valid signature that would be accepted by vk * . Further, there is a unique signature à * for message m * that vk * accepts.
Instantiations. Guan et al. [GWZ22] provided low-rate and high-rate constructions of SPB signature schemes. We will use the low-rate construction in this paper. Guan et al. [GWZ22] showed how to construct low-rate SPB signature scheme assuming one-way functions.
The notion of indistinguishability obfuscation (iO) was first defined in [BGI + 01]. Recent works have shown constructions from well-founded assumptions [JLS21, GP20, WW20, BDGM20]. We give the formal definition below, taken almost verbatim from Jain et al. [JLS21].
Definition B.5 (Indistinguishability Obfuscator (iO)). A uniform p.p.t. algorithm iO is called an indistinguishability obfuscator for polynomial-sized circuits if the following holds:
• Completeness: For every ¼ ∈ N, every circuit C with input length n, every input x ∈ {0, 1} n , we have that Pr
• Polynomial Security: For any two ensembles {C 0,¼ } ¼ , {C 1,¼ } ¼ of polynomial-sized circuits that have the same size, input length, and output length, and are functionally equivalent (i.e., C 0,¼ (x) = C 1,¼ (x) for every ¼ and x), the distributions {iO(1
In our proof for impossibility of fully simulation security of NIAR, we use the compression lemma that was formalized in earlier works [DTT10,GT20] which roughly means that it is impossible to compress every element in a set with cardinality c to a string less than log c bits long, even relative to a random string. We state the compression lemma here as a proposition.
Proposition B.6. Suppose there is an (not necessarily efficient) encoding procedure Encode :
and a (not necessarily efficient) decoding procedure Decode : Y × R → X such that Pr x∈X ,r∈R [Decode(Encode(x, r), r) = x] g ϵ, then log |Y| g log |X |log (1/ϵ). B.7 Selective Opening Security for PRFs In our adaptive corruption scheme, we need a PRF that is secure against selective opening attacks. The definition of such a PRF was given in the work of Abraham et al. [ACD + 19]. Moreover, they showed that the standard PRF security notion implies selective opening security except with a polynomial loss in the security failure probability. Specifically, selective opening security is defined as follows, borrowing verbatim from Abraham et al. [ACD + 19].
We consider a selective opening adversary that interacts with a challenger. The adversary can request to create new PRF instances, query existing instances with specified messages, selectively corrupt instances and obtain the secret keys of these instances, and finally, we would like to claim that for instances that have not been corrupt, the adversary is unable to distinguish the PRFs' evaluation outcomes on any future message from random values from an appropriate domain. More formally, we consider the following game between a challenger C and an adversary A.
) can adaptively interact with C through the following queries:
• Create instance. The challenger C creates a new PRF instance by calling the honest PRF key generation algorithm Gen(1 ¼ ). Henceforth, the instance will be assigned an index that corresponds to the number of "create instance" queries made so far. The i-th instance's secret key will be denoted sk i .
• Evaluate. The adversary A specifies an index i that corresponds to an instance already created and a message m, and the challenger computes r ← PRF sk i (m) and returns r to A.
• Corrupt. The adversary A specifies an index i, and the challenger C returns sk i to A (if the i-th instance has been created).
• Challenge. The adversary A specifies an index i * that must have been created and a message m. If b = 0, the challenger returns a completely random string of appropriate length. If b = 1, the challenger computes r ← PRF sk i * (m) and returns r to A.
We say that A is admissible iff with probability 1, every challenge tuple (i * , m) it submits satisfies the following: 1) A does not make a corruption query on i * throughout the game; and 2) A does not make any evaluation query on the tuple (i * , m). Definition B.7 (Selective opening security of a PRF family). We say that a PRF scheme satisfies pseudorandomness under selective opening iff for any admissible non-uniform p.p.t. adversary A, its views in PRFExpt A 0 (1 ¼ ) and PRFExpt A 1 (1 ¼ ) are computationally indistinguishable.
In this section we show how how to construct SSU Signatures and provide the security proof of the construction.
Let Σ = (Σ.Gen, Σ.Sign, Σ.Vf , Σ.GenBind) be a single-point binding (SPB) signature scheme as defined in Appendix B. 4. Let H = (H.Gen, H.Hash, H.GenBind) be a single-point binding (SPB) hash function as in Appendix B.3. Let PPRF be a puncturable PRF.
The SSU signature scheme is based on a binary tree of SPB signatures intuitively described in Figures 1a and 1b in Section 5.2. Formally, consider a binary tree of depth tlen + 1 consisting of levels 0, 1, . . . , tlen. At level tlen, there are 2 tlen leaf nodes, each corresponding to a time step t ∈ {0, 1} tlen based on the binary representation of t.
We describe the structure of this binary tree next.
• Every node has a unique identifier denoted as either u i or sib i in Figures 1a and 1b.
• At level 0, there is a root node u 0 whose associated SPB signature key tuple (sk u 0 , vk u 0 ) will be computed during the Setup algorithm.
• Each intermediate or leaf node u i will also have an associated SPB signature key tuple that can be computed on the fly using the PPRF key K. The keys will be computed as (sk
Here, we use the notation Σ.Gen(1 ¼ , 1 ℓ ; PPRF.Eval(K, u i )) to mean running the Σ.Gen(1 ¼ , 1 ℓ ) algorithm and seeding its random tape with the coins generated by PPRF.Eval(K, u i ).
• Each level j ∈ {0, 1, . . . , tlen} also has a hash key hk j associated with it that will be computed during Setup.
The SSU signature scheme is as follows. Recall that the SPB hash outputs a hash digest whose length is a fixed polynomial in ¼, and independent of the input length -henceforth let ℓ h (¼) denote this length. Let ℓ vk (¼) be the length of the verification key when we run Σ.Gen(1 ¼ , 1 ℓ h (¼) ).
Setup(1 ¼ , tlen, len):
4. Compute ³ 0 , . . . , ³ tlen as follows:
5. Sign the hash of the message ³ tlen with the signing key of the leaf node u tlen corresponding to t and also sign the hash of the verification keys of the nodes and their siblings (denoted ³ j for level j + 1) on the path (excluding root node) from root to t by their parent's signing key (denoted sk u j for level j) as follows.
for all j ∈ {0, . . . , tlen}: Ã j = Σ.Sign(sk u j , H.Hash(hk j , ³ j )).
6. Output à = ((à 0 , vk u 1 , vk sib 1 ), . . . , (à tlen-1 , vk u tlen , vk sib tlen ), à tlen ).
Vf (pp, vk, t, x, Ã):
1. Let the nodes on the path (excluding root node) from root to t be u 1 , . . . , u tlen and let their siblings be sib 1 , . . . , sib tlen .
2. Parse à = ((à 0 , vk u 1 , vk sib 1 ), . . . , (à tlen-1 , vk u tlen , vk sib tlen ), à tlen ), vk = vk u 0 , and pp = {hk j } j∈{0,...,tlen} .
3. Compute ³ 0 , . . . , ³ tlen as described in step 4 of Sign algorithm.
4. Output 1 iff all the following checks pass, else output 0.
for all j ∈ {0, . . . , tlen}: Σ.Vf (vk u j , H.Hash(hk j , ³ j ), Ã j ) = 1.
PuncturedSetup(1 ¼ , tlen, len, t * , x * ):
Compute (sk, vk, pp) just like in Setup algorithm. We spell out the details below for completeness.
3. For j ∈ {0, . . . , tlen -1}, let hk j ← H.Gen(1 ¼ , 1 2ℓ vk (¼) ); and let hk tlen ← H.Gen(1 ¼ , 1 len+tlen ).
4. Let sk = (sk u 0 , K), vk = vk u 0 , pp = {hk j } j∈{0,...,tlen} .
Compute signature à on (t * , x * ) just like in Sign algorithm. We spell out the details below for completeness.
5. Let the nodes on the path (excluding root node) from root to t * be u 1 , . . . , u tlen and let their siblings be sib 1 , . . . , sib tlen .
6. For all j ∈ [tlen], compute (sk u j , vk u j ) = Σ.Gen(1 ¼ , 1 ℓ h (¼) ; PPRF.Eval(K, u j )), and (sk sib j , vk sib j ) = Σ.Gen(1 ¼ , 1 ℓ h (¼) ; PPRF.Eval(K, sib j )).
7. Compute ³ 0 , . . . , ³ tlen as described in step 4 of Sign algorithm.
8. Compute the signature on (t * , x * ) and the signatures on the verification keys of the nodes and their siblings on the path (excluding root node) from root to t * : for all j ∈ {0, . . . , tlen}: Ã j = Σ.Sign(sk u j , H.Hash(hk j , ³ j ))
9. Let à = (( à 0 , vk u 1 , vk sib 1 ), . . . , ( à tlen-1 , vk u tlen , vk sib tlen ), à tlen ).
Puncture the PRF key and compute the outputs.
10. Compute K * ← PPRF.Puncture(K, {u j } j∈{0,1,...,tlen} ) as the punctured PRF key.
11. Let sk = ( Ã, t * , x * , K * ). Output (sk, sk, vk, pp).
BindingSetup(1 ¼ , tlen, len, t * , x * ):
1. Let the nodes on the path (excluding root node) from root to t * be u 1 , . . . , u tlen and let their siblings be sib 1 , . . . , sib tlen .
2. Compute K ← PPRF.Gen(1 ¼ , 1 tlen+1 ) and K * ← PPRF.Puncture(K, {u j } j∈{0,1,...,tlen} ).
3. For all j ∈ [tlen], compute (sk sib j , vk sib j ) = Σ.Gen(1 ¼ , 1 ℓ h (¼) ; PPRF.Eval(K, sib j )).
4. Compute the binding keys and associated signatures in the following sequence: ) , H.Hash(hk * tlen , ³ * tlen )). • For j = tlen -1, . . . , 0 in decreasing order:
7. Output (sk * , vk * , pp * ).
PSign(pp, sk, t, x):
1. Parse pp = {hk j } j∈{0,...,tlen} . and sk = ( Ã, t * , x * , K * ). Let the nodes on the path (excluding root node) from root to t * be u * 1 , . . . , u * tlen and let their siblings be sib * 1 , . . . , sib * tlen . Then, Ã = (( Ã 0 , vk u * 1 , vk sib * 1 ), . . . , ( Ã tlen-1 , vk u * tlen , vk sib * tlen ), Ã tlen ). 2. If t = t * and x = x * , output Ã.
3. Else if t = t * and x ̸ = x * , output §.
• Let the nodes on the path (excluding root node) from root to t be u 1 , . . . , u tlen and let their siblings be sib 1 , . . . , sib tlen . Suppose that the bit description of t and t * match in the first z ∈ {0, . . . , tlen -1} indices, that is, for j ∈ [z], u j = u * j and sib j = sib * j . Further, u z+1 = sib * z+1 and sib z+1 = u * z+1 .
• For all j ∈ [z + 1], choose vk sib j from sk. If z ̸ = tlen -1, then, for all j ∈ [tlen] \ [z + 1]: compute (sk sib j , vk sib j ) = Σ.Gen(1 ¼ , 1 ℓ h (¼) ; PPRF.PEval(K * , sib j )).
• For all j ∈ [z], choose vk u j from sk. For all j = [tlen] \ [z]: compute (sk
• Compute ³ 0 , . . . , ³ tlen as described in step 4 of Sign algorithm.
• Compute the signature on (t, x) and the signatures on the verification keys of the nodes and their siblings on the path (excluding root node) from root node to t as follows.
for all j ∈ {z + 1, . . . , tlen}: Ã j = Σ.Sign(sk u j , H.Hash(hk j , ³ j )) for all j ∈ {0, . . . , z}: Ã j = Ã j
• Output à = ((à 0 , vk u 1 , vk sib 1 ), . . . , (à tlen-1 , vk u tlen , vk sib tlen ), (à tlen , t, x)).
Key and signature sizes. In the above algorithm, the size of various keys and signatures are as follows:
• |sk| = |sk u 0 | + |K| = poly(¼, tlen) for some fixed polynomial poly.
• |pp| = |pp * | = (tlen + 1) • poly(¼) for some fixed polynomial poly.
• poly(¼) for some fixed polynomial poly.
• | sk| = |sk * | = len + poly(¼, tlen) for some fixed polynomial poly.
We prove the correctness of the above construction in Appendix C.2. Next, we present the main theorem statement of security of the above construction. We prove this theorem in Appendix C.3.
Theorem C.1. Suppose that PPRF is a secure puncturable PRF, Σ is a secure SPB signature scheme, and H is a secure SPB hash function. Then, the construction in Appendix C.1 is a secure SSU signature scheme (See Definition 5.1).
We know how to construct puncturable PRFs from one-way functions [GGM86, BW13, BGI14, KPTZ13], SPB signatures from one-way functions [GWZ22], and SPB hash function from indistinguishability obfuscation or leveled fully homomorphic encryption [GWZ22]. Plugging in these instantiations, we obtain the following corollary.
Assuming the existence of one-way functions and indistinguishability obfuscation, or assuming leveled fully homomorphic encryption, there exists a somewhere statistically unforgeable signature scheme.
For proving correctness, we need to show two things and we do them below.
First correctness requirement: we need to show that for all ¼, len, tlen ∈ N, t ∈ {0, 1} tlen , x ∈ {0, 1} len , Pr (sk, vk, pp) ← Setup(1 ¼ , tlen, len) Ã ← Sign(pp, sk, t, x) : Vf (pp, vk, t, x, Ã) = 1 = 1.
Recall that Vf outputs 1 if all the following checks pass.
for all j ∈ {0, . . . , tlen}: Σ.Vf (vk u j , H.Hash(hk j , ³ j ), Ã j ) = 1
If à is honestly computed using the Sign algorithm, then, we have that for all j ∈ {0, . . . , tlen}: à j = Σ.Sign(sk u j , H.Hash(hk j , ³ j )).
As the H.Hash algorithm of SPB hash function H is deterministic, therefore the values H.Hash(hk j , ³ j ) computed by Sign and Vf are the same. Then, all the verification checks will passs if the SPB signature scheme Σ satisfies correctness.
Second correctness requirement: we need to show that for any ¼, len, tlen ∈ N, t * , t ∈ {0, 1} tlen , x * , x ∈ {0, 1} len such that it is the case that either (t = t * and x = x * ) or (t ̸ = t * ), then the following holds true:
For the case (t = t * and x = x * ), observe that Sign(pp, sk, t, x) computes à = ((à 0 , vk u 1 , vk sib 1 ), . . . , (à tlen-1 , vk u tlen , vk sib tlen ), (à tlen , t, x)). On the other hand, PSign(pp, sk, t, x) computes à = (( à 0 , vk u 1 , vk sib 1 ), . . . , ( à tlen-1 , vk u tlen , vk sib tlen ), à tlen ) from sk. Notice that à is computed by PuncturedSetup in exactly the same as à by the Sign algorithm. Thus, the second correctness requirement is satisfied in this case.
For the case (t ̸ = t * ), let the nodes on the path (excluding root node) from root to t be u 1 , . . . , u tlen and let their siblings be sib 1 , . . . , sib tlen . Let t and t * have the same bit description upto first z bits for some z ∈ {0, 1, . . . , tlen -1}.
• For j ∈ [z + 1]: PSign chooses the verification key vk sib j of the sibling sib j from sk but Sign computes it on the fly. By the same argument as in the case of (t = t * and x = x * ), these verification keys are nevertheless the same.
• For j ∈ [tlen] \ [z + 1]: PSign computes the keys (sk sib j , vk sib j ) of the sibling sib j using PPRF.PEval(K * , sib j ) as the random tape for Σ.Gen. But, Sign computes it using PPRF.Eval(K, sib j ) as the random tape for Σ.Gen. But note that K * is not punctured on any of these sibling nodes. By correctness of puncturable PRFs, it follows that PPRF.Eval(K, sib j ) = PPRF.PEval(K * , sib j ). Therefore, the random tape used by Sign and PSign for computing these keys is the same, and hence, the keys of these siblings are also the same.
• For j ∈ [z]: PSign chooses vk u j from sk, but Sign computes them on the fly. By the same argument as in the case (t = t * and x = x * ), these values are nevertheless the same.
• For j ∈ [tlen]\[z]: PSign computes the keys (sk u j , vk u j ) of the node u j using PPRF.Eval(K * , u j ) as the random tape for Σ.Gen. But, Sign computes it using PPRF.PEval(K, u j ) as the random tape for Σ.Gen. But note that K * is not punctured on any of these nodes. By correctness of puncturable PRFs, it follows that PPRF.Eval(K, u j ) = PPRF.PEval(K * , u j ). Therefore, the random tape used by Sign and PSign for computing these keys is the same, and hence, the keys of these nodes are also the same.
• Observe then that Sign and PSign compute à tlen , à tlen-1 , . . . , à z+1 exactly the same way as Sign and PSign use the same the hash key and signing key for computing each of these signatures. But à z , . . . , à 0 are computed differently by Sign and PSign. PSign chooses these from sk, but Sign computes them on the fly. By the same argument as in the case (t = t * and x = x * ), these values are nevertheless the same.
Thus, the second correctness requirement is satisfied in this case as well.
In this section, we give the formal proof of security for our SSU signature scheme.
Theorem C.3 (Restatement of Theorem C.1). Suppose that PPRF is a secure puncturable PRF, Σ is a secure SPB signature scheme, and H is a secure SPB hash function. Then, the construction in Appendix C.1 is a secure SSU signature scheme (See Definition 5.1).
To prove the above theorem, we need to prove multiple properties about the construction. We do so in Lemmas C. Proof. We need to show that for any len and tlen that are polynomially bounded by ¼, any t * ∈ {0, 1} tlen , any x * ∈ {0, 1} len , we have the following where ≡ denotes identical distribution: {(sk, vk, pp) ← Setup(1 ¼ , tlen, len) : output (sk, vk, pp)} ≡{(sk, sk, vk, pp) ← PuncturedSetup(1 ¼ , tlen, len, t * , x * ) : output (sk, vk, pp)} Observe that sk, vk, pp are computed by PuncturedSetup in steps 1 to 4. This is the same as steps 1 to 4 of Setup. Hence, (sk, vk, pp) computed by PuncturedSetup and Setup are identically distributed.
Lemma C.5. Suppose that PPRF is a secure puncturable PRF. Suppose that Σ is a SPB signature scheme that satisfies computational indistinguishability of normal and binding keys (See Appendix B.4). Suppose that H is a SPB hash function that satisfies (i) identical distribution of normal hash keys and (ii)computational indistinguishability of normal and binding hash keys (See Appendix B.3). Then, the above construction satisfies computational indistinguishability of punctured and binding setup (See Definition 5.1).
Proof. We need to prove that for any len and tlen that are polynomially bounded by ¼, any t * ∈ {0, 1} tlen , any x * ∈ {0, 1} len , we have the following where ≈ denotes computational indistinguishability: {(sk, sk, vk, pp) ← PuncturedSetup(1 ¼ , tlen, len, t * , x * ) : output ( sk, vk, pp)} ≈{(sk * , vk * , pp * ) ← BindingSetup(1 ¼ , tlen, len, t * , x * ) : output (sk * , vk * , pp * )} Hencforth, we will denote the first distribution as D and the second distribution as D * . Next, we spell out the complete details of these two distributions.
Distribution D: Recall that the values computed by PuncturedSetup are vk = vk u 0 , pp = {hk j } j∈{0,...,tlen} , and sk = ( Ã, t * , x * , K * ), where à = (( à 0 , vk u 1 , vk sib 1 ), . . . , ( à tlen-1 , vk u tlen , vk sib tlen ), à tlen ). Plugging in these values, D is the following. {( à 0 , vk u 1 , vk sib 1 ), . . . , ( à tlen-1 , vk u tlen , vk sib tlen ), à tlen , t * , x * , K * , vk u 0 , {hk j } j∈{0,...,tlen} } Rearranging some of the terms for ease of understanding of the changes later, we can rewrite the distribution as follows.
D : {(vk u 0 , Ã 0 , hk 0 ), . . . , (vk u tlen , Ã tlen , hk tlen ), {vk sib j } j∈[tlen] , t * , x * , K * } Here, for all j ∈ {0, . . . , tlen}, hk j is computed using H.Gen. Further, vk u 0 is computed using Σ.Gen with its random tape containing uniformly random coins. For all j ∈ [tlen], vk u j is computed using Σ.Gen with its random tape PPRF.Eval(K, u j ).
Distribution D * : Recall that the values computed by BindingSetup are vk * = vk * u 0 , pp * = {hk * j } j∈{0,...,tlen} , and sk * = (à * , t * , x * , K * ), where à * = ((à * 0 , vk * u 1 , vk sib 1 ), . . . , (à * tlen-1 , vk * u tlen , vk sib tlen ), à * tlen ). Plugging in these values, D * is the following. {(à * 0 , vk * u 1 , vk sib 1 ), . . . , (à * tlen-1 , vk * u tlen , vk sib tlen ), à * tlen , t * , x * , K * , vk * u 0 , {hk * j } j∈{0,...,tlen} } Rearranging some of the terms as above, we can rewrite D * as follows. D * : {(vk * u 0 , à * 0 , hk * 0 ), . . . , (vk * u tlen , à * tlen , hk * tlen ), {vk sib j } j∈[tlen] , t * , x * , K * } D * differs from D in the terms highlighted in blue. In more detail, these are as follows. For all j ∈ {0, . . . , tlen}, hk * j is binding on the value ³ * j and is computed using H.GenBind. Further, vk * u 0
is binding on the value H.Hash(hk * 0 , ³ * 0 ) and is computed using Σ.GenBind with its random tape containing uniformly random coins. For all j ∈ [tlen], vk * u j is binding on the value H.Hash(hk * j , ³ * j ) and is computed using Σ.GenBind with its random tape containing uniformly random coins.
To prove D ≈ D * , consider the following sequence of hybrid distributions. Distribution D 0 : This is same as D except that for all j ∈ {0, . . . , tlen}, the normal hash key hk j is computed using H.GenBind instead of H.Gen as follows. Ifj ̸ = tlen, (hk j , hk *
Distribution D 1 : This is same as D 0 except that for all j ∈ [tlen], vk u j are computed using Σ.Gen(1 ¼ , 1 ℓ h (¼) ) with its random tape containing uniformly random coins instead of Σ.Gen(1 ¼ , 1 ℓ h (¼) ; PPRF.Eval(K, u j )).
Distribution D 2,i for all i ∈ {tlen + 1, . . . , 0}: The distribution is as follows.
It differs from distribution D 1 in the terms highlighted in blue. These differing values are computed in the following sequence:
• Compute (hk tlen , hk * tlen ) ← H.GenBind(1 ¼ , 1 len+tlen , ³ * tlen ).
• Compute (vk * u tlen , Ã * tlen ) = Σ.GenBind(1 ¼ , 1 ℓ h (¼) , H.Hash(hk * tlen , ³ * tlen )).
• For j = tlen -1, . . . , i in decreasing order:
To complete the proof, we will argue that
It differs from D 1 in only one term à tlen . In D 2,tlen+1 , the signature is à tlen = Σ.Sign(sk u tlen , H.Hash(hk tlen , ³ * tlen )). Whereas, in D 1 , the signature is à tlen = Σ.Sign(sk u tlen , H.Hash(hk tlen , ³ tlen )). As ³ * tlen = ³ tlen = t * ||x * , therefore, we get that à tlen in the two distributions are identically distributed. Hence, D 1 and D 2,tlen+1 are identically distributed.
This description is exactly same as that of D * . It follows then that D 2,0 and D * are identically distributed.
In Lemma C.6, we show that D ≡ D 0 . In Lemma C.7, we show that D 0 ≈ D 1 . In Lemma C.8, we show that D 2,i+1 ≈ D 2,i for all i ∈ {tlen, . . . , 0}. This completes the proof.
Lemma C.6. Suppose that H is a SPB hash function that satisfies identical distribution of normal hash keys, then, D ≡ D 0 .
Proof. The equivalence can be proven via a sequence of tlen + 1 hybrid distributions D 0,i for all i ∈ {0, . . . , tlen}. In D 0,i , for all j f i, hk j will be computed as normal hash keys output by H.GenBind(1 ¼ , 1 2ℓ vk (¼) , ³ j ) (or H.GenBind(1 ¼ , 1 tlen+len , ³ tlen ) in case j = tlen) and all other hash keys will be computed as normal hash keys output by H.Gen(1 ¼ , 1 2ℓ vk (¼) ) (or H.Gen(1 ¼ , 1 tlen+len ) in case j = tlen). Then, we can show that D ≡ D 0,0 ≡ D 0,1 ≡ . . . ≡ D 0,tlen . Notice that here every adjacent distribution differs only in how one hash key is chosen and the equivalence can then be argued by the identical distribution of normal hash keys of the SPB hash function H. Lastly, D 0,tlen is same as D 0 . This completes the proof.
Lemma C.7. Suppose that PPRF is a secure puncturable PRF, then, D 0 ≈ D 1 .
Proof. Suppose that the path (excluding root node) from the root to t * is u 1 , . . . , u tlen . Then, observe that both the distributions D 0 and D 1 contain the punctured PRF key K * punctured at strings u 1 , . . . , u tlen . For all i ∈ [tlen], vk u i are computed using Σ.Gen with its random tape differing in D 0 and D 1 as follows:
• In D 0 , the random tape is PPRF.Eval(K, u i ).
• In D 1 , the random tape contains uniformly random coins.
From security of puncturable PRFs, we know that the PRF evaluations on punctured points look indistinguishable from random. Therfore, if there exists a p.p.t. adversary A that can distinguish between D 0 and D 1 with non-neglegible advantage, then, a straightforward reduction B can be constructed that can break the PPRF security.
Lemma C.8. Suppose that Σ is a SPB signature scheme that satisfies computational indistinguishability of normal and binding verification keys (See Appendix B.4). Suppose that H is a SPB hash function that satisfies computational indistinguishability of normal and binding hash keys. Then, D 2,i+1 ≈ D 2,i for all i ∈ {tlen, . . . , 0}.
Proof. The difference between D 2,i+1 and D 2,i is as follows:
, where hk * i is binding on the value ³ * i , vk * u i is binding on the value H.Hash(hk * i , ³ * i ) and à * i is a signature on H.Hash(hk * i , ³ * i ).
• D 2,i+1 contains signature à i-1 on H.Hash(hk i-1 , ³ i-1 ) and D 2,i contains signature à i-1 on H.Hash(hk i , ³ * i-1 ). Essentially the two distributions are different in the i th SPB hash key, the i th SPB verification key and the signatures associated with them. To prove computational indistinguishability, we introduce an intermediate hybrid D ′ 2,i as follows.
Distribution D ′ 2,i for all i ∈ {0, . . . , tlen}: This is same as distribution D 2,i+1 except that the normal hash key hk i is replaced with the binding hash key hk * i . As a consequence, Ã i is now a signature on H.Hash(hk * i , ³ * i ) instead of H.Hash(hk i , ³ * i ). In Claim C.9, we show that D 2,i+1 ≈ D ′ 2,i . In Claim C.10, we show that D ′ 2,i ≈ D 2,i . This completes the proof.
Claim C.9. Suppose that H is a SPB hash function that satisfies computational indistinguishability of normal and binding hash keys. Then, for all i ∈ {0, . . . , tlen}, D 2,i+1 ≈ D ′ 2,i .
Proof. As noted in the description of D ′ 2,i , it essentially differs from D 2,i+1 in the i th SPB hash key and the signature associated with it.
Suppose that there exists a p.p.t. adversary A that can distinguish between D 2,i+1 and D ′
with non-neglegible advantage, then, we show a reduction B that can break the computational indistinguishability of normal and binding hash keys of the SPB hash function H as follows.
B receives (t * , x * ) as inputs from A. B computes the punctured PRF key K * as in BindingSetup algorithm. Then, B computes the following:
• For all j = tlen, . . . , i+1 in decreasing order, compute: (hk j , hk *
, where ³ * j is as defined in step 4 of BindingSetup algorithm.
• For j = i, B sends a challenge (1 2ℓ vk (¼) , ³ * i ) (or (1 tlen+len , ³ * i ) if i = tlen) to the SPB hash function challenger C, where ³ * i is as defined in step 4 of BindingSetup algorithm. C computes
• For all j = i -1, . . . , 0 in decreasing order, compute:
) and à j = Σ.Sign(sk u j , H.Hash(hk j , ³ j )). Here, ³ j is as defined in step 4 of Sign algorithm.
Finally, B sends the following to A. (vk u 0 , Ã 0 , hk 0 ), . . . , (vk
Observe that when C chooses b = 0, then, B perfectly simulates D 2,i+1 to A. And when C chooses b = 1, then, B perfectly simulates D ′ 2,i to A. Therefore, if A distinguish between its two view with non-neglegible advantage, then, B can distinguish between its two views in its game with C with the same non-neglegible advantage and thus break the computational indistinguishability of normal and binding hash keys of the SPB hash function H.
Claim C.10. Suppose that Σ is a SPB signature scheme that satisfies computational indistinguishability of normal and binding verification keys (See Appendix B.4). Then, for all i ∈ {0, . . . , tlen},
Proof. The difference between distributions D ′ 2,i and D 2,i is as follows.
Essentially the two distributions are different in the i th SPB verification key and the signatures associated with it.
Suppose that there exists a p.p.t. adversary A that can distinguish between D ′ 2,i and D 2,i with non-neglegible advantage, then, we show a reduction B that can break the computational indistinguishability of normal and binding verification keys of the SPB signature scheme Σ as follows.
B receives (t * , x * ) as inputs from A. B computes the punctured PRF key K * as in BindingSetup algorithm. Then, B computes the following where ℓ j = 2ℓ vk (¼) if j ̸ = tlen else ℓ j = tlen + len.
• For all j ∈ [tlen], compute (sk sib j , vk sib j ) ← Σ.Gen(1 ¼ , 1 ℓ h (¼) ).
• For all j = tlen, . . . , i + 1 in decreasing order, compute: (hk j , hk * j ) ← H.GenBind(1 ¼ , 1 ℓ j , ³ * j ) and compute (vk * u j , Ã * j ) ← Σ.GenBind(1 ¼ , 1 ℓ h (¼) , H.Hash(hk * j , ³ * j )), where ³ * j is as defined in step 4 of BindingSetup algorithm.
, where ³ * i is as defined in step 4 of BindingSetup algorithm.
B sends a challenge (1
• For all j = i -1, . . . , 0 in decreasing order, compute:
) and à j = Σ.Sign(sk u j , H.Hash(hk j , ³ j )). Here, ³ j is as defined in step 4 of Sign algorithm, except that it is as defined in the previous step when j = i -1.
Finally, B sends the following to A. (vk u 0 , Ã 0 , hk 0 ), . . . , (vk
Observe that when C chooses b = 0, then, B perfectly simulates D ′ 2,i to A. And when C chooses b = 1, then, B perfectly simulates D 2,i to A. Therefore, if A distinguish between its two view with non-neglegible advantage, then, B can distinguish between its two views in its game with C with the same non-neglegible advantage and thus break the computational indistinguishability of normal and binding verification keys of the SPB signatures scheme Σ.
Lemma C.11. Suppose that Σ is a SPB signature scheme satisfying statistical binding. Suppose that H is a SPB hash function satisfying statistical binding. Then, the construction in Appendix C.1 satisfies statistical unforgeability at (t * , x * ) (See Definition 5.1).
Proof. Let (sk * , vk * , pp * ) ← BindingSetup(1 ¼ , tlen, len, t * , x * ) and à * = PSign(pp * , sk * , t * , x * ). Then, vk * = vk * u 0 , pp * = {hk * j } j∈{0,...,tlen} . Let the nodes on the path (excluding root node) from root to t * be u 1 , . . . , u tlen and let their siblings be sib 1 , . . . , sib tlen . Then, à * is as follows.
We need to prove two things and we do them one after the other below.
(i) for t = t * , x = x * , there does not exist à ′ ̸ = à * such that Vf (pp * , vk * , t * , x * , à ′ ) = 1: We prove by contradiction. Suppose such a signature
. For all j ∈ {0, . . . , tlen -1}, define ³ ′ j with respect to vk ′ u j , vk ′ sib j the same way as ³ * j is defined with respect to vk * u j , vk sib j in step 4 of BindingSetup algorithm.
We now define a weaker security notion called selective single-challenge seucrity w.r.t. inversion.
In the security game, the adversary A must be subject to a set of restrictions (besides having to corrupt all players upfront):
• A must submit a pair of permutations à (0) and à (1) that differ by only a single inversion, i.e., à (1) can be obtained from à (0) by swapping a pair of senders' destinations -henceforth we use s and s ′ to denote this pair of senders; and
• there is only a single challenge time step, and A must commit to the challenge time step and challenge plaintexts for honest senders upfront.
Introducing a simulated setup algorithm. To make such a definition possible, we must first impose an additional requirement on the syntax. Specifically, we introduce a simulated setup algorithm Setup * that is never used in the real world, but needed for the security definition. Specifically, the simulated setup algorithm Setup * (1 ¼ , len, n, à (0) , à (1) ) takes in both permutations à (0) , à (1) that differ by one inversion pertaining to a pair of senders s and s ′ , and it outputs {ek u } u∈[n]\{s,s ′ } , (ek
s ′ ), (ek
, and tk. Importantly, observe that a single set of sender keys {ek u } u∈[n]\{s,s ′ } , for [n]\{s, s ′ } and the routing token tk must be simultaneously compatible with two different sets of sender keys (ek
s ′ ), for the swapped senders s and s ′ , corresponding to the two worlds b = 0 and b = 1, respectively. More precisely, we want the following property:
Marginal distribution of simulated setup statistically close as the real setup:
-for either b ∈ {0, 1}, the terms {ek u } u∈[n]\{s,s ′ } , (ek
, tk output by Setup * has negligibly small statistical distance from the output of the real Setup(1 ¼ , len, n, Ã (b) ).
With this additional simulated setup algorithm, we are ready to define selective single-challenge security for a single inversion.
Experiment NIARStatic-SelSingleCh-Inv b,A (1 ¼ ).
• n, len, K S , K R , Ã (0) , Ã (1) , t * , {x
, and for u ∈ {s, s ′ }, let CT u,t := Enc(ek
u , x u,t , t); for all other u ∈ H S , let CT u,t := Enc(ek u , x u,t , t);
The adversary is said to be admissible, iff with probability 1, Leak * (Ã (0) , K S , K R , {x
u,t * } u∈H S ) where where the function Leak * (Ã, K S , K R ), {x u,t * } u∈H S ) contains the destination of each corrupt sender and the contents of the messages from honest senders to corrupt receivers, as defined below:
Intuitively, the admissibility rule requires that the corrupt senders have the same destinations in the two worlds, and that corrupt receivers receive the same messages from honest senders in the two worlds.
Definition D.1 (Selective single-challenge security w.r.t. inversion under static corruption). We say that a NIAR scheme (augmented with a Setup * algorithm) satisfies selective security w.r.t. inversion under static corruption, iff for any non-uniform p.p.t. admissible adversary A which, with probability 1, submits two permutations à 0 and à 1 that differ by a single inverstion, A's views in NIARStatic-SelSingleCh-Inv 0,A (1 ¼ ) and NIARStatic-SelSingleCh-Inv 1,A (1 ¼ ) are computationally indistinguishable.
In this section, we prove an upgrade theorem for the static corruption setting: we start with a NIAR scheme that is secure when the adversary is subject to the single selective-challenge and single inversion restrictions, and show that the same scheme also satisfies security without the single selective-challenge and single inversion restrictions. It turns out that we only need to prove the upgrade theorem for the special case when the adversary always corrupts all receivers with probability 1. This is because later in Appendix F, we show how to compile a NIAR scheme secure under static corruption as long as the adversary always corrupt all receivers, to a NIAR scheme that is fully secure even under adaptive corruptions, and without the restriction that all receivers must be corrupt.
All-receiving-corrupting adversary. Henceforth, if an adversary corrupts all receivers with probability 1, we say that it is an "all-receiver-corrupting adversary". Moreover, if corruption is static, we also refer to such an adversary as a "static, all-receiver-corrupting adversary". Theorem D.2 (Upgrade theorem for static corruption: removing the selective single challenge and single inversion restrictions). Given a NIAR scheme which works for single-bit messages, and moreover satisfies selective security w.r.t. inversion (i.e., Definition D.1), under a static, all-receivercorrupting adversary, then it also satisfies full static corruption security (Definition A.1) subject to an all-receiver-corrupting adversary.
We prove Theorem D.2 in the remainder of this section.
We define an adaptive single-challenge notion also w.r.t. inversion, which removes the restriction that the adversary A must commit to the challenge t * and challenge plaintexts for honest users upfront.
We say that a NIAR scheme (augmented with a Setup * algorithm) satisfies adaptive singlechallenge security w.r.t. inversion under static corruption, iff for any non-uniform p.p.t. admissible adversary A, its views in the following experiments NIARStatic-AdSingleCh-Inv 0,A (1 ¼ ) and NIARStatic-AdSingleCh-Inv 1,A (1 ¼ ) are computationally indistinguishable.
Experiment NIARStatic-AdSingleCh-Inv b,A (1 ¼ ).
• n, len, K S , K R , Ã (0) , Ã (1) ← A(1 ¼ );
-else if ¶ t = "challenge", then for u ∈ H S , let CT u,t := Enc(ek
u,t , t) where ek
The adversary A is said to be admissible iff with probability 1, the following hold:
• There is a unique time step henceforth denoted t * in which A sets ¶ t to be "challenge"; and
u,t * } u∈H S ).
The lemma below shows that we can remove the selective single-challenge restriction for free and upgrade the security to adaptive single-challenge, under a single-inversion, all-receiver-corrupting, static-corruption adversary. The lemma considers a NIAR scheme where each sender's plaintext message in every time step is a single bit, i.e., len = 1. This assumption is without loss of generality, since we can always parallel-compose multiple NIAR schemes for len = 1 to get a NIAR scheme for len > 1. We need the len = 1 assumption for the proof to work because we want to make sure the reduction's guess is correct with 1/poly(¼) probability -see the proof for more details.
Lemma D.4 (Removing the selective restriction). Given any NIAR scheme which works for single-bit messages, and moreover satisfies selective single-challenge security w.r.t. a single inversion (Definition D.1) under a static, all-receiver-corrupting adversary, then it is also adaptive singlechallenge secure w.r.t. a single inversion (Definition D.3) under a static, all-receiver-corrupting adversary.
Proof. We consider a reduction B that interacts with an adaptive single-challenge adversary A and leverages it to break selective single-challenge security, w.r.t. inversion in both cases.
• At the start, A submits to B the terms n, len, the set of corrupt senders K S , and two permutations à (0) and à (1) that differ by a single inversion (recall also that A always corrupts all receivers). Let s, s ′ be the pair of senders whose destinations are swapped. By the admissibility rule on A, s and s ′ must be honest.
• Let T be the maximum number of queries made by A. B guesses at random t * $ ←[T ], guesses the plaintext messages x (0)
s ′ ,t * , and lets x
(1)
• With its own challenger, B corrupts all receivers, and all senders except s and s ′ . It submits the same permutations à (0) and à (1) , and the guessed t * , and the guessed plaintext messages x (0)
, and tk from its own challenger. B now passes {ek u } u∈K S , {rk u } u∈[n] , and tk to A.
• In the following, if A ever submits a challenge query during some t ̸ = t * , or it does not submit a challenge query during t * , B aborts.
• During every time step t ̸ = t * , whenever A submits {x
u,t } u∈H S , and ¶ t ∈ {0, 1} (assuming B has not aborted), B submits {x ( ¶t) u,t } u∈{s,s ′ } and ¶ t to its own challenger, and it gets back the encryptions CT s,t and CT s ′ ,t . For any u ∈ H S \{s, s ′ }, B simply uses ek u to encrypt x ( ¶t) u,t and obtains CT u,t . B returns to A the resulting {CT u,t } u∈H S .
• For t = t * , assuming the reduction B has not aborted, A must have specified t * to be the challenge time step. Now, check if the challenge plaintexts {x
u,t * } u∈H S A has submitted are consistent with the reduction B's guesses x (0)
s ′ ,t * . If not, the reduction B simply aborts. Now, B receives from its challenger CT s,t * and CT s ′ ,t * . For any u ∈ H S \{s, s ′ }, by the admissibility rule on A, it must be that x
u,t * . B now uses the corresponding ek u to compute an encryption of x (0) u,t * and let the result be CT u,t * . B now returns {CT u,t * } u∈H S to A.
• At the end, if B has not aborted, it outputs whatever A outputs.
Observe that the Setup * algorithm executed by B's challenger does not depend on the challenge time step t * or the challenge plaintexts. Therefore, if B's challenger is in world b = 0, and if the reduction did not abort, then A's view is identically distributed as in NIARStatic-AdSingleCh 0,A (subject to single inversion). Otherwise, if B's challenger is in world b = 1, and if the reduction did not abort, then A's view is identically distributed as in NIARStatic-AdSingleCh 1,A (subject to single inversion). The lemma follows by observing as long as the message length is only one bit, the probability that the reduction B guesses correctly is 1/poly(¼).
We now prove that we can further remove the single challenge restriction.
Lemma D.5 (Removing the single challenge restriction). Given any NIAR scheme that satisfies adaptive single-challenge security w.r.t. inversion (Definition D.3) subject to a static, all-receiver corrupting adversary, the same scheme also satisfies Definition A.1 subject to a static, singleinversion, all-receiver-corrupting adversary.
Proof. Let T be the maximum number of queries made by the adversary. We consider the following sequence of hybrids indexed by i ∈ {0, 1, . . . , T }, and recall that the permutations à (0) , à (1) submitted by the adversary A must differ by only one inversion where the swapped pair of senders is denoted s and s ′ below.
s , ek
u,t , t) where ek
A is said to be admissible iff it is subject to the same admissibility rules as Definition A.1; moreover, we also assume that A respects the single-inversion, and all-receiver-corruptingfoot_5 constraints. Since the marginal distribution of Setup * is statistical close to the real-world Setup algorithm, it holds that A's view in Hyb 0 is statistically close to NIARStatic 0,A , and its view in Hyb T is statistically close to NIARStatic 1,A . It suffices to prove that every adjacent pair of hybrids are computationally indistinguishable to the adversary. This can be shown through a straightforward reduction to the adaptive single-challenge security w.r.t. inversion (Definition D.3).
We next show how to remove the single inversion restriction on the adversary. Lemma D.6 (Removing the single inversion restriction (static corruption)). Given a NIAR scheme that satisfies Definition A.1 subject to a static, single-inversion, all-receiver-corrupting adversary, the same scheme also satisfies Definition A.1 subject to a static, all-receiver-corrupting adversary.
Proof. Given any two permutations à (0) and à (1) submitted by A, let C(à (0) , à (1) ) be the set of senders that have different destinations in à (0) and à (1) -by the admissibility rule on A, it must be that C(à (0) , à (1) ) are all honest senders. We define a sequence of permutations denoted à * 0 , . . . , à * n where à * 0 = à (0) , and for any 0 < i f n, à * i is almost the same as à * i-1 , except that if i f |C(à (0) , à (1) )|, then we additionally swap the destinations of the i-th honest sender in C(à (0) , à (1) ) denoted u * i and whoever is sending to à (1) (u * i ) in à * i-1 -by construction, the sender u * i is swapping destinations with another sender that must lie within the the set C(à (0) , à (1) ). Else if i > |C(à (0) , à (1) )|, then, à * i = à * i-1 . By construction, in à * i , the first i honest senders in C(à (0) , à (1) ) have their correct destinations as in à (1) , and thus à * n = à (1) . We now consider a sequence of hybrid experiments denoted Hyb i where i ∈ {0, 1, . . . , n}, in which a challenger interacts with an adversary A that has the same interface as a NIARStatic b,A adversary, and moreover, it always corrupts all receivers upfront. Namely, A submits n, len, K S , K R , à (0) , à (1) upfront where K R is guaranteed to be [n], and then in every time step t, it submits {x
u,t } u∈H S . In Hyb i , the challenger computes the responses to A as follows:
• It calls the Setup algorithm on the input len, n and the permutation à * i (which is uniquely determined given à (0) and à (1) submitted by A),
• During each time step t, upon receiving {x
u,t } u∈H S , do the following: for each u ∈ H S , let
u ′ ,t where u ′ = Ã (1) -1 (Ã * i (u)); now compute ct u,t = Enc(ek u , x * u,t , t).
By construction, and due to the admissibility rule on A, Hyb 0 is the same as NIARStatic 0,A , and Hyb n is the same as NIARStatic 1,A . It suffices to argue that the adversary's views in every pair of adjacent hybrids Hyb i and Hyb i+1 are computationally indistinguishable. This can be achieved through a reduction to the static single-inversion security under all-corrupt-receivers.
If à * i+1 = à * i , then by definition, Hyb i and Hyb i+1 are identically. Henceforth we focus on the case when à * i+1 and à * i differ by exactly one inversion. Consider a reduction B which receives n, len, K S , K R , à (0) , à (1) from A upfront where K R is guaranteed to be [n], B submits to its own challenger n, len, K S , K R , à * i , à * i+1 and passes the responses to A. In every time step t, B receives {x
u ′ ,t where u ′ = Ã (1) -1 (Ã * i (u)), and let
u ′ ,t where u ′ = Ã (1) -1 (Ã * i+1 (u)). It submits to its own challenger the challenge plaintexts {x * u,t , y * u,t } u∈H S , and passes the responses to A. B outputs whatever A outputs. If B's challenger is in world b = 0 and encrypts the plaintexts {x * u,t } u∈H S , then A's view is identically distributed as in Hyb i ; else B's challenger is in world b = 1 and encrypts the plaintexts {y * u,t } u∈H S , then A's view is identically distributed as in Hyb i+1 . Finally, by construction, if A respects its admissibility rules, then B respects its admissibility rules as well. Moreover, as mentioned earlier, B respects the single-inversion constraint. Therefore, B can translate A's advantage in distinguishing Hyb i and Hyb i+1 into its own advantage at breaking the single-inversion static-corruption security of NIAR (subject to all-corrupting receivers).
The proof of Theorem D.2 follows directly by combining Lemmas D.4 to D.6.
We now prove indistinguishability w.r.t. inversions against an adversary that additionally satisfies the selective single-challenge restriction. Formally, we have the following theorem.
Theorem E.1. Suppose that PRF is a secure puncturable PRF, Sig is a secure deterministic SSU signature scheme, and iO is a secure indistinguishability obfuscation scheme. Then our NIAR construction in Section 6.1 satisfies selective single-challenge security w.r.t. inversion under static corruption (Definition D.1) subject to an all-receiver-corrupting adversary.
In order to invoke Definition D.1, we next describe the Setup * algorithm. We will show in Claim E.2 that the Setup * algorithm satisfies the requirements that its marginal distribution is statistically close to the real setup.
Setup * (1 ¼ , len, n, à (0) , à (1) ): on inputs the security parameter 1 ¼ , the individual message length len, the number of parties n, the permutations à (0) and à (1) , does the following:
1. Set tlen = log 2 (¼).
2. Sampling Routes: Let the two senders that à (0) and à (1) differ on be s and s ′ . Run the AssignRoutes * procedure (Appendix B.1) on inputs (1 ¼ , n, à (0) , à (1) ). Abort if it outputs §. Else parse the output as ({rte u } u∈[n]\{s,s ′ } , {rte
u , rte
u } u∈{s,s ′ } ).
3. Sampling Wire Keys: Same as in Setup (Figure 3).
For each sender u ∈ [n] \ {s, s ′ } do the following:
(a) Parse rte u = (j 1 , . . . , j L ). Sign rte u using route signing keys for each wire along rte u , that is, for ℓ ∈ [L] compute rsig ℓ = Sig.Sign(rpp (ℓ,j ℓ ) , rsk (ℓ,j ℓ ) , 1, rte u ). // Same way as in Setup (Figure 3).
(b) Set rte u = (rte u , rsig u = (rsig 1 , . . . , rsig L )). // Same way as in Setup (Figure 3).
For each sender u ∈ {s, s ′ } and for each ´∈ {0, 1}, do the following:
(a) Parse rte
u using route signing keys for each wire along rte
// Same way as in Setup (Figure 3).
L )). // Same way as in Setup (Figure 3).
Setting Routing Token: Same as in Setup (Figure 3). 6. Setting Sender Keys: For each u ∈ [n] \ {s, s ′ }, set ek u = (k (1,j 1 ) , mpp (1,j 1 ) , msk (1,j 1 ) , rte u ). For each u ∈ {s, s ′ } and ´∈ {0, 1}, set ek
7. Setting Receiver Keys:
u , ek Claim E.2. If the routing network satisfies obliviousness as defined in Definition B.1, then the Setup * algorithm in Figure 4 satisfies the requirement that its marginal distribution is statistically close to the real setup. More formally, -for either b ∈ {0, 1}, the terms {ek u } u∈[n]\{s,s ′ } , (ek (b) s , ek
, tk output by Setup * (1 ¼ , len, Ã (0) , Ã (1) ) has negligibly small statistically distance from the output of the real Setup(1 ¼ , len, n, Ã (b) ).
Proof. For either b ∈ {0, 1}, the terms {ek u } u∈[n]\{s,s ′ } , (ek
, tk output by Setup * differs from the output of the real Setup only in the following way: while Setup samples the senders' routes using AssignRoutes, Setup * samples them using AssignRoutes * algorithm. Therefore, for either b ∈ {0, 1}, the indistinguishability of the terms ({ek u } u∈[n]\{s,s ′ } , (ek s , ek s ′ ), {rk u } u∈[n] , tk) output by the real Setup(1 ¼ , len, n, Ã (b) ) and the terms {ek u } u∈[n]\{s,s ′ } , (ek
, tk output by Setup * follows from the obliviousness of the routing network (Definition B.1).
The Hybrids for Theorem E.1
We are now ready to prove Theorem E.1. We do this via the sequence of hybrids below. In this sequence, Hyb
0 implements NIARStatic-SelSingleCh-Inv 0,A , and Hyb
(1) In the following, we say that a wire is "corrupt" or "honest" if it is on a path which originates with a corrupt or honest sender respectively, and we say that a wire is an "inversion" wire if it is on one of the paths that originate with the two honest senders s and s ′ . We say all wires apart from corrupt and honest wires to be "filler " wires. Also, we sometimes use the shorthand "wire (ℓ, j)" to refer to j th wire in the ℓ th layer.
In the real world hybrid Hyb (b) 0 , the adversary's view contains the sender keys of corrupt senders, the receiver keys of corrupt receivers, the routing token, non-challenge and challenge ciphertexts for honest senders. Let's understand which all of these terms contain information about the challenge bit b.
• As AssignRoutes * assigns a single route to each corrupt sender, hence, the sender keys of corrupt senders are independent of b. All receiver keys are independent of b.
• The non-challenge ciphertexts are independent of b. It is only the challenge ciphertexts that are dependent on b as follows. The challenger provides the following challenge ciphertexts to the adversary.
-for all u ∈ {s, s ′ }: CT u,t * = Enc(ek
CT u,t * contain information about b only for u ∈ {s, s ′ }: Observe that for senders u ∈ H S \ {s, s ′ }, Ã (0) (u) = Ã (1) (u). This means that the receiver remains the same across the two worlds for each such sender. And recall that we are proving security against an all-receivercorrupting adversary. The admissibility criteria requires then that each corrupt receiver must receive the same message across the two worlds. This implies that x
(0) u,t * = x
(1)
u,t * for all u ∈ H S \ {s, s ′ }. Hence, it follows that CT u,t * is independent of b for all such honest senders u. Therefore, the adversary's view contains information about b in only the challenge ciphertexts for u ∈ {s, s ′ }. Removing this information about bit b is non-trivial and requires an intricate sequence of hybrids as discussed below.
• From the description of the circuit Gate (ℓ,g) in Figure 2, it seems that the routing token contains no information of b. But, observe that the obfuscated gates treat filler and non-filler wires differently. More importantly, notice that its possible that a wire is an inversion wire when b = 0 and filler wire when b = 1 or vice versa. This is not the case for a corrupt wire or a honest non-inversion wire as AssignRoutes * only assigns a single route for all senders u / ∈ {s, s ′ }. Hence, one of the goals of our sequence of hybrids is to arrive at the final hybrid in which the obfuscated gates will treat the inversion and filler wires exactly the same in the challenge round t * .
Our sequence of hybrids is as follows.
(b) The foremost change we make is to ensure that for all the corrupt wires, the authenticated routes that the obfuscated gates obtain are as intended by Setup * . This change is accomplished in three steps.
• Hyb (b) 1 : For each corrupt wire in each layer, puncture the route signing key such that it can only sign the expected route that passes through that wire. Hyb
(b) 2 : For each corrupt wire in each layer, bind the route signing and verification key such that the verification key for a corrupt wire only accepts signature for the expected route that passes through that wire. Indistinguishability follows from indistinguishability of punctured and binding modes of SSU signatures.
• Hyb (b) 3 : For each corrupt wire in each layer, hardwire the expected route and expected route signatures. Further, update the route authentication check to directly compare routes and route signatures against hardcoded values. Indistinguishability follows from statistical unforgeability of the SSU signatures at the binding points and iO security.
4 : For all filler/inversion wires of layer ℓ = 1, puncture the message signing keys such that they can sign any message for non-challenge round t ̸ = t * and only the challenge message for the challenge round t = t * . Then, the adversary's view is identical as before (formal argument can be found in the transition from Hyb
(b) 3 to Hyb (b) 4 and Claim E.6). Hybrids Hyb (b)
5 : For all filler/inversion wires of layer ℓ = 1, bind the message signing and verification keys such that the verification key accepts signatures for any message for non-challenge round t ̸ = t * and only the challenge message for the challenge round t = t * . Indistinguishability follows from indistinguishability of punctured and binding modes of SSU signatures.
Layered hybrids. Now that we have shown how to change the message signing and verification keys for all filler/inversion wires in layer ℓ = 1, we show how to do the same for rest of the layers. This is done in a layer-by-layer fashion. Below, we describe how to do it for layer ℓ = 2 through a sequence of hybrids Hyb 6,1,5 : The goal of this set of hybrids is to reach a distribution where the message signing and verification keys for all filler/inversion wires of layer ℓ = 2 are in binding mode. We show how to reach this distribution via a sequence of steps.
• Hyb (b) 6,1,1 : For all filler/inversion wires in layer ℓ = 1, hardcode the expected message signatures and messages. Further, update the message authentication check to directly compare messages and message signatures against hardcoded values. Route authentication check remains the same as before.
• Hyb (b) 6,1,2 : For all filler/inversion wires in layer ℓ = 1, hardcode the expected input ciphertext and puncture the PRF keys. Further, replace message and route authentication checks with ciphertext comparison.
At this point, observe that for all filler/inversion wires in layer ℓ = 2, the unpunctured message signing keys can not be used to sign messages other than the challenge messages for the challenge round t * .
• Hyb (b) 6,1,3 : For all filler/inversion wires of layer ℓ = 2, puncture the message signing keys such that they can sign any message for non-challenge round t ̸ = t * and only the challenge message for the challenge round t = t * . These punctured message signing keys are hardcoded in the gates in the first layer ℓ = 1. Importantly, changing these message signing keys does not change the gate's functionality because as noted in the previous hybrid, the unpunctured signing keys for layer ℓ = 2 can not be used to sign messages other than the challenge messages for the challenge round t * either. Consequently, the security of indistinguishability obfuscation can be invoked to transition from Hyb • Hyb (b) 6,1,4 : For all filler/inversion wires of layer ℓ = 2, bind the message signing and verification keys such that the verification key accepts signatures for any message for non-challenge round t ̸ = t * and only the challenge message for the challenge round t = t * . Indistinguishability follows from indistinguishability of punctured and binding modes of SSU signatures. 7 : In this hybrid, we invoke the pseudorandomness of PRF at punctured points to change all the hardcoded ciphertexts to be uniformly random values except for a select few following wires. If an inversion wire in the last layer has the destination that is corrupt, then, we do not make any change to the hardwired outgoing ciphertexts in the last layer. Further, the challenge ciphertexts given out to the adversary for u ∈ {s, s ′ } are set in a manner consistent with the hardcoded input ciphertexts in layer ℓ = 1.
(b) 8 , Hyb (b) 9 : In Hyb (b) 7
, the only sources of information of challenge bit b are the hardwired message signing and verification keys for all filler/honest wires in all the circuits. So, in these hybrids, we unbind and unpuncture all the message signing and verification keys.
Analysis of the final hybrid: In hybrid Hyb (b) 9 , we claim that everything can be simulated from the leakage function which is identical in both worlds. In other words, this hybrid contains no information about the challenge bit b.
• Observe that the challenge ciphertext for u ∈ {s, s ′ } for the challenge round t * obtained by the adversary are random strings independent of challenge bit b.
• Observe that for all corrupt wires, while the punctured route verification keys and expected routes are hardwired in the obfuscated circuits, they are the same across the two worlds b = 0 and b = 1. Further, punctured PRF keys that are hardwired contain no information about b. Most hardwired ciphertexts in the obfuscated gates are uniformly random values and the ones that are not random (i.e., inversion wires with corrupt receiver as destination) have the same value across the two worlds by the admissibility criteria. Put in other words, for the challenge round t * , the circuit description (Figure 15) treats filler and inversion wires exactly the same.
Hence, Hyb
9 and Hyb
(1) 9 are identical. 0 except that during the algorithm Setup * , for all the corrupt wires, the challenger punctures the route signing keys at the corresponding routes and uses these punctured keys to generate the route signatures. More specifically, for each wire (ℓ, i = j ℓ ), where j ℓ ∈ rte * u for some sender u ∈ K S , we compute the route signatures as follows:
Hybrid Hyb 1 except that during the algorithm Setup * , the challenger generates binding route signature keys for all the corrupt wires. More specifically, for each wire (ℓ, i = j ℓ ), where j ℓ ∈ rte * u for some sender u ∈ K S , we compute the route signatures as follows:
Then, we replace the gates Gate (ℓ,g) for all ℓ ∈ [L -1], g ∈ [G] as described in Figure 5.
Notation. Let Input (ℓ,g) and Output (ℓ,g) be the set of input and output wires of gate Gate (ℓ,g) .
(b) 0 except that for each corrupt input wire i ∈ Input (ℓ,g) , route public parameter rpp * (ℓ,i) and route verification key rvk * (ℓ,i) are hardcoded instead of rpp (ℓ,i) and rvk (ℓ,i) .
(b) 0 . • In addition, the challenger hardcodes the punctured PRF key k (ℓ,i) at challenge round t * : k * (ℓ,i) ← PRF.Puncture(k (ℓ,i) , t * ).
Formally, the behavior of gate Gate (ℓ,g) for all g ∈ [G] as described in Figure 9.
Notation. Let Input (ℓ,g) and Output (ℓ,g) be the set of input and output wires of gate Gate (ℓ,g) .
Hardcoded values. Same as in Hyb (b) 6,ℓ,1 , except that for each filler/inversion wire i ∈ Input (ℓ,g) , CT * (ℓ,i) is hardcoded along with the corresponding challenge message x (ℓ,i) and route rte * , and msig * (ℓ,i) is not hardcoded anymore. In addition, the punctured PRF key k * (ℓ,i) is hardcoded instead of k (ℓ,i) , and is used for decrypting on wire (ℓ, i) during all rounds t ̸ = t * .
Procedure. Gate (ℓ,g) takes as input a round t and a set of ciphertexts {CT (ℓ,i) : i ∈ Input (ℓ,g) } corresponding to the input wires. Depending on the layer ℓ, it computes as follows.
• Step 1: For each input wire i ∈ Input (ℓ,g) , if t ̸ = t * or wire i is corrupt or is a non-inversion honest wire, then, compute as in Hyb Hybrid Hyb (b) 6,ℓ,3 for each ℓ ∈ [L -1]: This hybrid is identical to Hyb (b)
6,ℓ,2 , except that during Setup * , the challenger punctures the message signing keys for all filler/inversion wires (ℓ + 1, i) on the path rte * = rte * u (or rte * = § filler in case of filler wire) at the challenge round t * and challenge message x * (ℓ+1,i) = x (b) u,t * (or x * (ℓ+1,i) = § filler in case of filler wire), that is, for each such wire (ℓ + 1, i),
Consequently, the associated message signatures in the gates will be computed using Sig.PSign. Formally, the behavior of gate Gate (ℓ,g) for all g ∈ [G] is changed as described in Figure 10.
Hybrid Hyb 6,ℓ,3 , except that during Setup * , the challenger uses the binding setup to bind message signature keys for all filler/inversion wires (ℓ + 1, i) on the path rte * at the challenge round t * and challenge message x * (ℓ,i) = x u,t * (or x * (ℓ,i) = § filler in case of filler wire), that is, for each such wire (1, i), (msk * (ℓ+1,i) , mvk * (ℓ+1,i) , mpp * (ℓ+1,i) ) ← Sig.BindingSetup(1 ¼ , tlen, len m , t * , (x * (ℓ,i) , rte * )).
Then, the challenger replaces the gates Gate (ℓ,g) and Gate (ℓ+1,g) for all g ∈ [G] as described in Figure 11 and Figure 12.
Notation. Let Input (ℓ,g) and Output (ℓ,g) be the set of input and output wires of gate Gate (ℓ,g) .
Hardcoded values. Same as in Hyb (b) 6,ℓ,2 , except that for each filler/inversion wire i ∈ Output (ℓ,g) in the output layer ℓ + 1, the punctured message signing key msk ′ (ℓ+1,i) is hardcoded instead of msk (ℓ+1,i) .
Procedure.
• Step 1: For each input wire i ∈ Input (ℓ,g) , if t ̸ = t * or wire i is corrupt or is a non-inversion honest wire, compute as in Hyb (b) 6,ℓ,2 . Else: -Steps (a), (b) are same as in Hyb (b) 6,ℓ,2 . -Step (c): Prepare the output ciphertext CT (ℓ+1,j ℓ+1 ) : * Steps i and iii are same as in Hyb (b) 6,ℓ,2 . * Step ii: If ℓ < L -1, compute msig ′ = Sig.PSign(mpp (ℓ+1,j) , msk ′ (ℓ+1,j) , t * , (x (b) u,t * , rte * u )) and CT * (ℓ+1,j) = (x (b) u,t * , rte * u , msig ′ ) • PRF.Eval(k (ℓ+1,j) , t).
• Step 2: For each j ∈ Output (ℓ,g) such that CT (ℓ+1,j) has not been computed yet, compute filler ciphertexts as in Hyb Notation. Let Input (ℓ,g) and Output (ℓ,g) be the set of input and output wires of gate Gate (ℓ,g) .
Hardcoded values. Same as in Hyb (b) 6,ℓ,3 except that for each filler/inversion wire i ∈ Output (ℓ,g) , message public parameter mpp * (ℓ+1,i) and message signing key msk * (ℓ+1,i) are hardcoded instead of mpp (ℓ+1,i) , msk ′ (ℓ+1,i) .
Procedure. Same as in Hyb
(b) 6,ℓ,3 . that is, for each such wire (ℓ, i), (msk (ℓ,i) , mvk (ℓ,i) , mpp (ℓ,i) ) ← Sig.Setup(1 ¼ , tlen, len m ).
Then, whenever the challenger has to compute a message signature during Enc algorithm or inside a gate, it computes as: msig (ℓ,i) = Sig.Sign(mpp (ℓ,i) , msk (ℓ,i) , •, •).
To summarize, at this point the circuit Gate (ℓ,g) for all ℓ ∈ [L -1] and g ∈ [G] is as in Figure 14 and Figure 15.
Notation. Let Input (ℓ,g) and Output (ℓ,g) be the set of input and output wires of gate Gate (ℓ,g) .
Hardcoded values. Gate (ℓ,g) has hardcoded the following values:
• For each wire i ∈ Input (ℓ,g) in layer ℓ:
-if corrupt: the PRF key k (ℓ,i) , the message public parameter mpp (ℓ,i) , the message verification key mvk (ℓ,i) , the route public parameter rpp * (ℓ,i) , the route verification key rvk * (ℓ,i) , the expected route rte * u . -if filler/inversion: the PRF key k * (ℓ,i) , the message public parameter mpp (ℓ,i) , the message verification key mvk (ℓ,i) , the route public parameter rpp (ℓ,i) , the route verification key rvk (ℓ,i) , the expected challenge ciphertext CT * (ℓ,i) .
• For each wire i ∈ Output (ℓ,g) in layer ℓ + 1:
-if corrupt: the PRF key k (ℓ+1,i) , the message public parameter mpp (ℓ+1,i) . the message signing key msk (ℓ+1,i) .
-if filler/inversion: the PRF key k * (ℓ+1,i) , the message public parameter mpp (ℓ+1,i) , the message signing key msk (ℓ+1,i) , the expected challenge ciphertext CT * (ℓ+1,i) .
• The challenge round t * . 1 is that the for all the corrupt wires, the route signing keys are unpunctured in the former and punctured in the latter hybrid experiment. While no route signing keys are in the view of the adversary, the adversary does get route signatures for corrupt senders and these are computed differently across two hybrids. In the former, they are computed using Sig.Sign algorithm and in the latter they are computed using Sig.PSign algorithm. It follows from the correctness of the SSU signature scheme as defined in Section 5 that the input/output behaviour of these two algorithms is identical for all unpunctured points. As these signatures are generated by the challenger for some unpunctured points, hence, adversary A's views in Hyb 1 , for all the corrupt wires, the route signature key tuple (rsk ′ (ℓ,i) , rvk (ℓ,i) , rpp (ℓ,i) ) is used where the signing key is punctured and the verification key and public parameter are unpunctured. Whereas in hybrid Hyb 2 , for all the corrupt wires, the route signature key tuple (rsk * (ℓ,i) , rvk * (ℓ,i) , rpp * (ℓ,i) ) is used where all the keys are binding and are generated using binding setup. There are ¹ corrupt wires in each layer ℓ = 1, . . . , L. For the sake of simplicity, call these total of L • ¹ wires to be w 1 , . . . , w L•¹ . We will show that the adversary A's views in Hyb
(b) 1 and Hyb (b) 2 are computationally indistinguishable via a sequence of hybird H (b) 1,0 , . . . , H (b)
1,L•¹ where in H 1,i , for wire w j , the route signature key tuple (rsk * w j , rvk * w j , rpp * w j ) is used if j f i, else the pair (rsk ′ w j , rvk w j , rpp w j ) is used. With this sequence, observe that H
1,i are computationally indistinguishable. Let wire w i be on the route rte * u for some u ∈ K S . Observe that the difference between the two hybrids is that for wire w i in H
1,i , the route signature key tuple (rsk * w i , rvk * w i , rpp * w i ) is used. Then, we can create a simple reduction from the computational indistinguishability of the two hybrids to the computational indistinguishability of punctured and binding setup of SSU signature scheme which states that the following two distibutions are computationally indistinguishable.
We prove indistinguishability via a sequence of subhybrids Hyb ′ ³ , where ³ ∈ {1, . . . , 2n}. We define Hyb ′ ³ to produce programs {Gate (ℓ,g) } g∈[G] which verify all message signatures msig (ℓ,i) as in Hyb (b) 6,ℓ,1 when i < ³, and as in Hyb ³-1 and Hyb ′ ³ for all ³. Note that the only difference between Hyb ′ ³ and Hyb ′ ³-1 is in the behavior of a single Gate (ℓ,g) for g such that ³ ∈ Input (ℓ,g) . Provided that the circuits obfuscated in Hyb ′ ³-1 and Hyb ′ ³ to produce Gate (ℓ,g) are functionally equivalent, a simple reduction to security of the obfuscation scheme shows that Hyb ′ ³-1 and Hyb ′ ³ are computationally indistinguishable. Thus we have reduced the claim to showing functional equivalence of the two circuits in question.
To show functional equivalence, we observe that the only possible point at which the circuit outputs could differ is where CT (ℓ,³) is an encryption of some message (x (ℓ,³) , rte, msig (ℓ,³) ) with respect to round t * which was not generated honestly. It is clear that in Hyb ′ ³ , because the filler/inversion message x * (ℓ,i) , route rte * and signature msig (ℓ,³) are hardcoded, Gate (ℓ,g) rejects all dishonestly generated ciphertexts. Because of statistical unforgeability of the SSU signature scheme at point (t * , x * (ℓ,i) ) with respect to the key tuple (msk * (ℓ,³) , mvk * (ℓ,³) , mpp * (ℓ,³) ) which was generated by Sig.BindingSetup, the only message that is accepted by Sig.Vf is (x * (ℓ,i) , rte * ), and by the fact that the scheme is a determistic signature scheme, the only accepted signature is msig * (ℓ,³) . Thus, in Hyb ′ ³-1 at round t * , Gate (ℓ,g) also rejects all inputs where CT (ℓ,³) encrypts a message which was dishonestly generated. It follows that the circuits have identical behavior with respect to CT (ℓ,³) , and thus are functionally equivalent.
Claim E.9. For b ∈ {0, 1} and ℓ ∈ [L -1], assuming correctness of the punctured PRF scheme and the indistinguishability obfuscation scheme is secure, adversary A's views in Hyb 6,ℓ,2 , the obfuscated programs inversion/filler wire keys are punctured at t * , and during round t * inversion/filler wire ciphertexts CT (ℓ,i) are not decrypted directly, and instead are compared with a fixed value CT * (ℓ,i) , whose corresponding decryption is also hardcoded and used for the rest of the procedure.
We prove indistinguishability via a sequence of subhybrids Hyb ′ ³ , where ³ ∈ {1, . . . , 2n}. We define Hyb ′ ³ to produce programs {Gate (ℓ,g) } g∈[G] which are identical to those in Hyb (b) 6,ℓ,1 , except for the following differences:
• For all i < ³, if this is an inversion/filler wire, hardcode punctured key k * (ℓ,i) . Treat input inversion/filler wire ciphertexts CT (ℓ,i) in the same way as in Hyb (b) 6,ℓ,2 (i.e., do not decrypt directly, instead check whether CT (ℓ,i) = CT * (ℓ,i) , and if so, use corresponding hardcoded plaintext in the rest of the procedure.
• For all i g ³, hardcode non-punctured key k (ℓ,i) . Treat input inversion/filler wire ciphertexts CT (ℓ,i) in the same way as in Hyb ³-1 and Hyb ′ ³ for all ³. Note that the only difference between Hyb ′ ³ and Hyb ′ ³-1 is in the circuit Gate (ℓ,g) which is used to generate a single obfuscated program Gate (ℓ,g) for g such that ³ ∈ Input (ℓ,g) . Provided that the circuits obfuscated in Hyb ′ ³-1
and Hyb ′ ³ to produce Gate (ℓ,g) are functionally equivalent, a simple reduction to security of the obfuscation scheme shows that Hyb ′ ³-1 and Hyb ′ ³ are computationally indistinguishable. Thus we have reduced the claim to showing functional equivalence of the two circuits in question.
To show functional equivalence, note that the behavior of Gate (ℓ,g) only differs across Hyb ′ ³-1
and Hyb ′ ³ in terms of the behavior for the input wire (ℓ, ³ -1). We focus on this wire. In Hyb ′ ³-1 , Gate (ℓ,g) only accepts exactly one value for CT (ℓ,³-1) during round t * . This is because Gate (ℓ,g) decrypts CT (ℓ,³-1) and then compares the decrypted plaintext to fixed hardcoded values, and aborts if they are unequal. Since decryption is deterministic, only one such ciphertext CT (ℓ,³-1) does not cause an abort. Since in Hyb ′ ³ Gate (ℓ,g) hardcodes this exact ciphertext and the corresponding plaintext, the behavior with respect to round t * is identical. Because of correctness of the punctured PRF key at all non-punctured points t ̸ = t * , the behavior of Gate (ℓ,g) between Hyb ′ ³-1 and Hyb ′ ³ across all other rounds are also identical. Thus, Gate (ℓ,g) is functionally equivalent across these two subhybrids.
Claim E.10. For b ∈ {0, 1} and ℓ ∈ [L -1], assuming correctness of the SSU signature scheme, and assuming the indistinguishability obfuscation scheme is secure, adversary A's views in Hyb
(b) 6,ℓ,2 and Hyb (b) 6,ℓ,3 are computationally indistinguishable. Proof. The only difference between Hyb (b) 6,ℓ,3 and Hyb (b) 6,ℓ,2 is that in Hyb (b)
6,ℓ,3 , for inversion/filler output wires (ℓ + 1, i), the challenger hardcodes punctured message signing keys msk ′ (ℓ+1,i) instead of unpunctured ones. The obfuscated gates then use the punctured signing algorithm Sig.PSign when signing outgoing messages at layer ℓ + 1.
We prove indistinguishability via a sequence of subhybrids Hyb ′ ³ , where ³ ∈ {1, . . . , 2n}. We define Hyb ′ ³ to produce programs {Gate (ℓ,g) } g∈[G] which are identical to those in Hyb (b) 6,ℓ,2 , except for the following differences:
• For all i < ³, if wire i is an inversion/filler wire, hardcode punctured signing key msk ′ (ℓ+1,i) , and sign messages for output wire (ℓ + 1, i) using Sig.PSign.
• For all i g ³, hardcode non-punctured signing key msk (ℓ+1,i) , and sign messages for output wire (ℓ + 1, i) using Sig.Sign.
6,ℓ,2 and that Hyb ′ 2n = Hyb (b) 6,ℓ,3 . Proving the claim thus reduces to proving indistinguishability between Hyb ′ ³-1 and Hyb ′ ³ for all ³. Note that the only difference between Hyb ′ ³ and Hyb ′ ³-1 is in the circuit Gate (ℓ,g) which is used to generate a single obfuscated program Gate (ℓ,g) for g such that ³ ∈ Output (ℓ,g) . Provided that the circuits obfuscated in Hyb ′ ³-1 and Hyb ′ ³ to produce Gate (ℓ,g) are functionally equivalent, a simple reduction to security of the obfuscation scheme shows that Hyb ′ ³-1 and Hyb ′ ³ are computationally indistinguishable. Thus we have reduced the claim to showing functional equivalence of the two circuits in question. Functional equivalence follows directly from correctness of the SSU signature scheme and the observation that no message is ever signed with respect to round t * except for the exact binding message.
Claim E.11. For b ∈ {0, 1} and ℓ ∈ [L -1], assuming the SSU signature scheme satisfies computational indistinguishability of punctured and binding setups, adversary A's views in Hyb 6,ℓ,4 , the message signature key tuples for inversion/filler wires (ℓ + 1, i), i ∈ [2n] are all generated using Sig.BindingSetup, whereas in Hyb (b) 6,ℓ,3 they are generated using Sig.PuncturedSetup. We prove indistinguishability via a sequence of subhybrids Hyb ′ ³ , where ³ ∈ {1, . . . , 2n}. We define Hyb ′ ³ to generate message signature key tuples (msk (ℓ+1,i) , mvk (ℓ+1,i) , mpp (ℓ+1,i) ) using Sig.BindingSetup for all inversion/filler i < ³, and to generate (msk (ℓ+1,i) , mvk (ℓ+1,i) , mpp (ℓ+1,i) ) using Sig.PuncturedSetup for all i g ³. It is clear that Hyb ³ for all ³. Note that the only difference between Hyb ′ ³ and Hyb ′ ³-1 is in the key tuple (msk (ℓ+1,³-1) , mvk (ℓ+1,³-1) , mpp (ℓ+1,³-1) ). As such, a simple reduction to computational indistinguishability of the punctured and binding setups of the SSU signature scheme shows this indistinguishability. This proves the claim.
Claim E.12. For b ∈ {0, 1}, assuming the indistinguishability obfuscation scheme is secure, adversary A's views in Hyb
and outputs this value for wire (ℓ + 1, i). We prove indistinguishability via a sequence of subhybrids Hyb ′ ³ , where ³ ∈ {1, . . . , 2n}. We define Hyb ′ ³ to produce programs {Gate (ℓ,g) } g∈[G] which are identical to those in Hyb (b) 6,ℓ,4 , except for the following difference. During round t * :
• For all i < ³ such that (ℓ + 1, i) is a filler/inversion wire, output CT (ℓ+1,i) = CT * (ℓ+1,i) for this wire.
• For all i g ³, act as in Hyb ³-1 and Hyb ′ ³ for all ³. Note that the only difference between Hyb ′ ³ and Hyb ′ ³-1 is in the circuit Gate (ℓ,g) which is used to generate a single obfuscated program Gate (ℓ,g) for g such that ³ ∈ Output (ℓ,g) . Provided that the circuits obfuscated in Hyb ′ ³-1 and Hyb ′ ³ to produce Gate (ℓ,g) are functionally equivalent, a simple reduction to security of the obfuscation scheme shows that Hyb ′ ³-1 and Hyb ′ ³ are computationally indistinguishable. Thus we have reduced the claim to showing functional equivalence of the two circuits in question.
To show functional equivalence, observe that the only wire where the two circuits could possibly differ is the output wire (ℓ + 1, ³ -1). Functional equivalence then follows directly from the following facts:
• No corrupt wire from layer ℓ could be re-routed to a filler/inversion wire in layer ℓ + 1 because of the hardwired routes for corrupt wires in hybrid Hyb (b) 3 (Figure 6).
• During round t * , the plaintext (x, rte, msig ′ ) encrypted by Gate (ℓ,g) to form CT (ℓ+1,³-1) in Hyb ′ ³-1 has values x and rte are fixed and exactly equal to the corresponding plaintext components of CT * (ℓ+1,³-1) in Hyb ′ ³ , along with the fact that the SSU signature scheme produces deterministic signatures (which means that the signature msig ′ is also fixed and equal to the corresponding component of CT * (ℓ+1,³-1) ).
Claim E.13. For b ∈ {0, 1}, assuming pseudorandomness of the PRF at punctured points, adversary A's views in Hyb
(b) 6,L-1,5 and Hyb (b) 7 are computationally indistinguishable.
Proof. The difference between the two hybrids is in (i) how are the hardcoded ciphertexts for the challenge round t * for all the filler/inversion wires in all the layers (with the exception of inversion output wires directed towards corrupt receivers in the last layer) computed by the challenger, and (ii) the challenge ciphertexts for u ∈ {s, s ′ } given to the adversary for the challenge round t * . In Hyb 7 , the challenge ciphertexts for u ∈ {s, s ′ } given to the adversary for the challenge round t * are set consistent with the hardcoded incoming ciphertexts in the obfuscated gates in layer ℓ = 1 in those respective hybrids. To argue the computationally indistinguishability of adversary's view in these two hybrids, notice that the hardcoded PRF key k * (ℓ,i) is punctured at t * , whereas y * is the PRF evaluation at exactly this punctured point. So, one can use the pseudorandomness of the PRF at punctured points to show the computational indistinguishability. Claim E.14. For b ∈ {0, 1}, assuming the SSU signature scheme satisfies computational indistinguishability of punctured and binding setups, adversary A's views in Hyb
(b) 7 and Hyb (b) 8 are computationally indistinguishable.
Proof. Similar to Claim E.7, except that here the message verification keys and message public parameters are changed from binding to unbinding for all the filler/inversion wires (ℓ, i) in all the layers. Claim E.15. For b ∈ {0, 1}, assuming the SSU signatures scheme is correct, and the indistinguishability obfuscation scheme is secure, adversary A's views in Hyb
(b) 8 and Hyb (b) 9 are computationally indistinguishable.
Proof. The difference between the two hybrids is that in Hyb 9 , unpunctured message signing key msk (ℓ,i) is used. This difference reflects in how message signatures are computed in all the circuit contain no information about the challenge bit b. Observe that the gate circuit had no information about challenge bit b in the real world description. So, the only new sources of information about it could be the changes done to the circuit that are highlighted in the figures. We will now argue that all of them have no information about the challenge bit b.
• For each corrupt wire i ∈ Input (ℓ,i) , route information rte * u , binding route public parameter rpp * (ℓ,i) and binding route verification rvk * (ℓ,i) are hardwired, where the route public parameter and route verification key are binding at route rte * u . The admissibility criteria requires that for each u ∈ K S , Ã (0) (u) = Ã (1) (u). Hence, the hardcoded routes for corrupt senders have no information about the challenge bit b. It also follows then that the binding route public parameters and the binding verification keys for corrupt senders do not contain any information about the challenge bit b.
• For each filler/inversion wire i ∈ Input (ℓ,i) , the punctured PRF key k * (ℓ,i) is hardwired. This key is punctured at the challenge round t * , and hence has no information about the challenge bit b. For these wires, the expected challenge ciphertext CT * (ℓ,i) is also hardcoded. As all of these are uniformly random values, hence, it follows that they have no information about the challenge bit b.
• For each filler/inversion wire i ∈ Output (ℓ,i) , the punctured PRF key k * (ℓ+1,i) is hardwired. This key is punctured at the challenge round t * , and hence has no information about the challenge bit b. For these wires, the expected challenge ciphertext CT * (ℓ+1,i) is also hardcoded. If ℓ ̸ = L -1, all of these are uniformly random values, hence, it follows that they have no information about the challenge bit b. If ℓ = L -1 and the wire's destination is not a corrupt receiver, then also all of these are uniformly random values. Hence, it follows that they have no information about the challenge bit b. If ℓ = L -1 and the wire's destination is a corrupt receiver, then, the hardcoded value is the what the corrupt receiver would expect. The admissibility criteria dictates that if two different honest senders are sending some message to a corrupt receiver in the two worlds b = 0 and b = 1, then, the message values by the two honest senders should be the same. Hence, it follows that the same ciphertext value is hardcoded in the two worlds and consequently, it leaks no information about the challenge bit b.
• It is possible that a wire could be filler when b = 0 and inversion when b = 1. Hence, it could have different treatment by the circuit procedure in the two worlds. But notice that in both hybrids Hyb
(0) 9 and Hyb 9 , for the challenge round t = t * , the treatment of filler and inversion wires is exactly the same. Hence, it leaks no information about the challenge bit b.
From the above analysis, it follows that adversary A's views in Hyb
(0) 9 and Hyb In this section, we present a generic compiler that lifts any NIAR scheme that satisfies staticcorruption security to a NIAR scheme with full security under adaptive corruptions and adaptive queries (Definition 3.1).
Starting from a static corruption NIAR scheme denoted NIAR ′ , we will use an extra pseudorandom function PRF to encrypt the plaintext first, before encrypting it again with NIAR ′ , thus creating two layers of encryption. For the security proof, we will need the PRF to be secure against selectiveopening attacks (Definition B.7), which is implied by the standard security for pseudorandom functions as shown by Abraham et al. [ACD + 19]. We formally describe the compiler below. Now, imagine that the challenger has some randomness tape Γ[•, •] which can be viewed as a two dimensional array. The randomness tape is sampled at the beginning of the experiment Hyb b where b ∈ {0, 1}. Later, whenever the challenger needs to sample a random inner-message for some sender whose destination is u in à (b) , it will read the random coins Γ[u, t] off the randomness tape where t denotes the current time.
It suffices to prove that conditioned on any fixed choice of the randomness tape Γ, A's views in Hyb 0 and Hyb 1 are computationally indistinguishable. This can be accomplished through a straightforward reduction to the security of the underlying NIAR ′ scheme. Basically, consider a reduction B that interacts with its own challenger as well as A.
• B passes the terms (n, len, Ã (0) , Ã (1) ) sent by A directly to its own challenger, and gets back tk.
It passes tk to A.
• Further, B chooses the PRF key k u for every receiver u.
• B corrupts all receivers upfront with its own challenger, and receives {rk ′ u } u∈[n] .
• Whenever A submits an encryption query during some time step t, B computes the two corresponding inner-messages and pass them to its own challenger. It receives some ciphertexts from its own challenger and forwards them to A.
• Whenever A makes a corruption query for some receiver u, B sends to A its key (k u , rk ′ u ).
• Whenever A makes a corruption query for some sender, B forwards the query to its own challenger and passes the answer back to A. Moreover, it reveals the corresponding player's PRF key to A.
If A is admissible, then a corrupt sender must have the same receiver in both à (0) and à (1) , so B can always identify a unique PRF key to return to A.
• B outputs whatever A outputs. Now, if B's challenger is in world b = 0, then A's view is identically distributed as Hyb 0 . Else if B's challenger is in world b = 1, then A's view is identically distributed as Hyb 1 . Further, for a fixed randomness tape, B is admissible as long as A is admissible.
Completing the proof of Lemma F.4. Combining Claims I.8 and I.9, we have that NIARFull 0 ≈ c Hyb 0 ≈ c Hyb 1 ≈ c NIARFull 1 where ≈ c denotes computational indistinguishability. This completes the proof of Lemma F.4.
So far in our paper, we have used indistinguishability-based security definitions. Shi and Wu [SW21] showed that under static corruption, indistinguishability-based security is equivalent to simulationbased security. In this section, we introduce a natural simulation-based security notion for adaptive corruption, and somewhat surprisingly at first sight, we show that the same equivalence of indistinguishability-and simulation-based security no longer holds under adaptive corruption. We show this by first proving an impossibility result for simulation security under adaptive corruption.
• Sim receives {(Ã(u), x u,t )} u∈Ã(H S )∩K R , where K R = [n]\H R , i.e., the plaintexts received by every currently corrupt receiver that is paired with an honest sender. Sim now outputs {CT u,t } u∈H S .
Definition G.1 (NIAR full simulation security). We say that a NIAR scheme satisfies full simulation security, iff for any non-uniform p.p.t. adversary A, there exists a p.p.t. simulator Sim and a negligible function negl(•), such that A cannot distinguish Real A (1 ¼ ) and Ideal Sim,A (1 ¼ ) except with negl(¼) probability.
Theorem G.2. There does not exist any NIAR scheme that supports an unbounded (i.e., a-priori unknown) number of time steps while satisfying full simulation security.
Proof. The proof is very similar to Nielsen's result [Nie02]. For the same of reaching a contradiction, suppose there is a scheme denoted NIAR that supports an unbounded number of time steps while satisfying full simulation security. Since decryption must enjoy perfect correctness, without loss of generality, we may assume that the receiver's decryption algorithm is deterministic in NIAR. We show that there exists an encoding scheme that leverages NIAR to compress a long random string.
Let ℓ be a sufficiently large natural number, and let Ä $ ←{0, 1} ℓ be a long random string. To encode the string Ä with a common reference string r independent of Ä, we perform the following:
• First, initialize Sim with the random coins r.
• Next , call Sim with 1 ¼ for some sufficiently large ¼, len = 1, and n = 1, which outputs tk.
• Next, for t = 1, 2, . . . , ℓ, invoke Sim with no permitted leakage and receive a simulated ciphertext CT t .
• Finally, corrupt the only receiver and invoke Sim, providing it with the leaked messages Ä. Sim outputs a receiver key rk.
• The resulting encoding is defined as (tk, rk).
To decode a codeword of the form (tk, rk) with the same common reference string r independent of the message, perform the following:
• Initialize Sim with the same random string r.
• Call Sim with 1 ¼ , len = 1, and n = 1.
• Now, for t = 1, . . . , ℓ, we perform the following: 1) call Sim to produce CT t ; and 2) call the Rte algorithm which uses tk and transforms CT t to CT ′ t .
• Finally, we use rk to decrypt every CT ′ t , and output the decrypted bits.
Due to Definition G.1 and the fact that the receiver's decryption algorithm is polynomially bounded, it must be that the above decoding algorithm is correct except with negligible probability. The theorem follows by making ℓ a constant factor larger than the total length of the codeword (tk, rk), by Shannon's source coding theorem [Sha48] formalized in Proposition B.6.
1. We start from a NIAR secure with sender-insider protection w.r.t. inversion under a staticcorruption, all-sender-corrupting adversary. We prove that the same scheme is also secure with sender-insider protection w.r.t. inversion under an adaptive-corruption, all-sender-corrupting adversary (see Appendix I.2.1 and Lemma I.4).
2. Next, given a NIAR scheme secure with sender-insider protection w.r.t. inversion under an adaptive-corruption, all-sender-corrupting adversary, we remove the "inversion" restriction, and prove that it is also secure with sender-insider protection for an arbitrary pair of permutations under an adaptive-corruption, all-sender-corrupting adversary (see Appendix I.2.2 and Lemma I.5).
3. Finally, given a NIAR scheme that is secure with sender-insider protection under an adaptivecorruption, all-sender-corrupting adversary (for an arbitrary pair of permutations), we show that the static-to-adaptive compiler in Figure 16 gives a NIAR scheme secure under Definition I.1 (see Appendix I.2.3 and Lemma I.6).
Lemma I.4. If a NIAR scheme satisfies security with sender-insider protection under a staticcorruption, single-inversion, and all-sender-corrupting adversary, then it also satisfies security with sender-insider protection under a single-inversion adversary who corrupts all senders upfront, and corrupts receivers adaptively.
Proof. Consider a non-uniform p.p.t. admissible adversary A who corrupts all senders upfront and corrupts the receivers adaptively. A is trying to distinguish its views in experiments NIARFull 0,A (1 ¼ ) and NIARFull 1,A (1 ¼ ) subject to single inversion. Then, we construct a p.p.t. admissible adversary B that plays a game with its own challenger C and leverages A to distinguish between NIARStatic 0,B (1 ¼ ) and NIARStatic 1,B (1 ¼ ) subject to single inversion and all-sender-corruption. The description of B is as follows.
1. B gets (n, len, Ã (0) , Ã (1) ) from A(1 ¼ ). Let s 1 , s 2 be the two senders involved in the inversion. Let the corresponding receivers involved in the inversion be r 1 , r 2 . For its game with C, it chooses to corrupt the senders K ′ S = [n], the receivers K ′ R = [n] \ {r 1 , r 2 }, and it sends (n, len, K ′ S , K ′ R , Ã (0) , Ã (1) ) to C. Then, C computes ({ek u } u∈[n] , {rk u } u∈[n] , tk) ← Setup(1 ¼ , len, n, Ã (b) ) and gives the terms (tk, {ek u } u∈[n] , {rk u } u∈K ′ R ) to B. B now passes (tk, {ek u } u∈[n] ) to A since A always corrupts all senders upfront.
• A makes no encryption queries as H S = ∅.
• Upon receiving a corruption query to corrupt some receiver u ∈ [n], by the admissibility rule on A, u cannot be r 1 or r 2 . Therefore, B returns rk u to A.
Observe that if A is admissible and respects single inversion, then, B is also admissible and respects single inversion. By construction, B respects all-sender-corruption. Further, for b ∈ {0, 1}, when C uses the challenge bit b, A's view is identical to NIARFull b,A (1 ¼ ). Therefore, if A has non-negligible advantage in distinguishing NIARFull 0,A (1 ¼ ) and NIARFull 1,A (1 ¼ ), then B has nonnegligible advantage in distinguishing NIARStatic 0,B and NIARStatic 1,B .
Throughout the paper, we use O ¼ (•) to hide poly(λ) multiplicative factors where λ denotes the security parameter.
In this sense, our adaptive corruption result is also interesting in the context of function-hiding MCFE since how to get function-hiding MCFE under adaptive corruption was not known earlier. The recent work of Shi and Vanjani[SV23] showed a function-hiding MCFE scheme for inner-product computation under static corruption, relying on standard bilinear group assumptions.
Informally speaking, SPB signatures have a special single-point binding property which states that it is possible to generate a special verification key w.r.t. a message m * s.t. it only accepts a single signature for m * . Similarly, SPB hash functions have a special single-point binding property which states that it is possible to generate a special hash key w.r.t. a message m * s.t. no hash collisions exist on m * .
Our formal proof in the technical sections actually first proves single, selective-challenge, static security only for an adversary subject to the following restrictions: it must corrupt all receivers, and submit two permutations that differ by a single inversion. We prove that even this weaker version is sufficient for our upgrade all the way to full security under adaptive corruption.
To be more precise there are c • n wires in each layer for constant c ≥ 2, but for simplicity we assume c = 2 as this is achieved by our proposed instantiation.
The all-receiver-corrupting restriction is not important for this lemma, that is, the lemma and the proof still hold if we remove every occurrence of "all-receiver-corrupting".
Let (rskw i , rsk ′ w i , rvk w i , rpp w i ) ← Sig.PuncturedSetup(1 ¼ , 0, len rte , 1, rte * u ), and output (rsk ′ w i , rvk w i , rpp w i ).
Let (rsk* w i , rvk * w i , rpp * w i ) ← Sig.BindingSetup(1 ¼ , 0, len rte , 1, rte * u ), and output (rsk * w i , rvk * w i , rpp * w i ).
In our scheme, the receiver does not consume randomness during decryption. In this case, Cor(•) only needs to return the random coins used by a newly corrupted sender in all previous time steps.