arXiv CSopen access

I-(OT)^2: A Client-optimal Oblivious Transfer Protocol for IoT Devices

I-(OT )2 : A CLIENT-OPTIMAL OBLIVIOUS TRANSFER PROTOCOL FOR IOT DEVICES Elia Onofri ⋆, , Andrea Ciccotelli , Roberto Di Pietro

arXiv:2606.02344v1 [cs.CR] 1 Jun 2026

King Abdullah University of Science and Technology (KAUST) Computer, Electrical and Mathematical Sciences and Engineering (CEMSE) Division, Thuwal 23955, Saudi Arabia

Abstract. Oblivious Transfer (OT) is a fundamental cryptographic primitive enabling privacypreserving computation and constitutes a core building block for secure multi-party computation while supporting a wide range of security-sensitive applications: private information retrieval, zeroknowledge proofs, and password-authenticated key exchange, to cite a few. While recent advances in OT extension have significantly reduced amortised costs, their reliance on batches of random base OTs and substantial pre-computation phases limits their practicality in scenarios where the number of transfers is modest or where communication latency and client-side computation are critical constraints. In such settings, efficient base OT protocols remain both relevant and necessary. In this work, we introduce I-(OT )2 , a novel base 1-out-of-2 OT protocol grounded in the quadratic residuosity problem, specifically designed to minimise receiver-side computation and interaction. Our construction is particularly appealing on client–server architectures in which the receiver operates on low-power hardware, such as Internet of Things (IoT) devices. Through a lightweight offline pre-computation phase, I-(OT )2 shifts the on-transfer computational burden almost entirely to the Sender, while reducing online communication to only six messages and four digests exchanged. We provide a detailed description of the protocol, accompanied by a formal proof of its security. Moreover, to demonstrate the viability of I-(OT )2 , we also present an open-source proof-of-concept implementation (in C language) evaluated on real IoT hardware. Results are staggering: for 128-bit security using a 3072-bit RSA modulus, the receiver incurs an average online cost per OT as low as 2.80 µs on desktop platforms and 39.90 µs on IoT devices, more than 10× faster than the well known SimplestOT. These results show that I-(OT )2 effectively bridges the gap between theoretical security and practical efficiency, enabling OT deployment in real-world resource-constrained environments. Keywords: Oblivious Transfer · Internet of Things · Quadratic Residue · Resource-Constrained Devices · Privacy · Security.

Contents 1. Introduction 1.1. Technical Contributions 1.2. Paper Organisation 2. Related Work 3. Notation and Background 4. The I-(OT )2 Protocol 4.1. The system and security models 4.2. The threat models 4.3. The scheme 4.4. Transfer complexity analysis 5. Security of I-(OT )2 5.1. Security Analysis 5.2. Working with untrusted senders 6. I-(OT )2 Proof-of-concept

2 2 3 4 6 8 8 9 10 13 15 15 17 19

⋆ Corresponding Author, (Q) [email protected]

6.1. The experimental setting 6.2. Results 6.3. Comparison with SimplestOT 7. Conclusion and Future Work References Appendix A. Probabilistic and Bayesian Analysis of the CheckCongruency Game A.1. Best malicious sender strategy A.2. Bayesian approach to the effective size of the test set Appendix B. Security Games B.1. Choice Obliviousness Game B.2. Receiver Message Obliviousness Game

19 19 21 22 23

25 26 27 29 29 30

2

1. Introduction The security of modern cryptographic systems, particularly in distributed environments, relies on the ability to perform computations while preserving data privacy. One of the fundamental cryptographic primitives enabling such privacy-preserving computations is Oblivious Transfer (OT). Originally introduced by Rabin in 1981 [1] as a technique to probabilistically transmit encrypted messages, OT protocols quickly became a fundamental building block of secure multi-party computation (MPC), allowing a Sender to transfer one of multiple possible messages to a Receiver without revealing any additional information. Specifically, in its simplest form of 1-out-of-2 OT (OT21 ), the Sender possesses two messages (M0 , M1 ) and the Receiver can select one of the two (b ∈ {0, 1}); OT21 then ensures that the Receiver learns Mb while remaining oblivious to M1−b and the Sender learns nothing at all about the choice b (see Figure 1). Nowadays, OT serves as a critical building block in numerous cryptographic protocols, including private information retrieval (PIR), secure voting, password-authenticated key exchange (PAKE), and zero-knowledge proofs, to name a few. Its ability to enable selective data transfer while ensuring privacy for both parties makes it essential for security-sensitive applications [2, 3, 4, 5, 6]. Despite its theoretical significance, OT also presents notable computational and efficiency challenges in practical applications. Traditional secure OT schemes often rely on hardness assumptions from number theory, like the Diffie-Hellman assumptions or the lattice-based hardness assumptions, to guarantee security [1, 7, 8, 9, 10]. While these cryptographic foundations provide strong security guarantees, they frequently suffer from high computational and communication overhead, making them impractical for large-scale deployments or resource-constrained environments. Although OT extension schemes [11, 12] appear to render further work on base OT obsolete, they rely fundamentally on a batch of random base OTs and require a substantial pre-computation phase before any extension can be performed. As a consequence, research has largely concentrated on reducing the number of random base OTs, rather than optimising the classical 1-out-of-2 OT itself. In applications where the total number of OTs remains modest, the cost of this initial setup cannot be effectively amortised: on commonly found implementations, random base OTs typically become advantageous on the order of tens to hundreds of thousands invocations, and deriving a standard OT21 from a random OT introduces additional computational overhead. For these scenarios, focusing on efficient base OT still remains both relevant and necessary. Additionally, some existing OT schemes require an initial message exchange phase before data transfer can begin, further increasing latency and inefficiency. This is e.g. the case of the state-of-theart solution for OT extension [13], which requires a 3-round interaction for its base random OT. This issue is particularly problematic in client-server architectures where the client operates on low-power hardware, such as Internet of Things (IoT) devices, and where communication channels are unstable or present sensible throttling. Optimising OT protocols to reduce both communication complexity and client-side computation is therefore crucial to expanding their applicability in real-world scenarios. To fill the above-highlighted gaps, we propose a novel protocol under the name of I-(OT )2 , focusing on a highly efficient transfer and Receiver design capable of providing security even in the presence of active adversaries. 1.1. Technical Contributions. In this work, we propose a novel OT protocol designed to achieve high computational Receiver efficiency at a reduced communication cost (only two rounds of interaction are needed) while preserving security guarantees. The solution is particularly suited for client-server architectures, where the server operates on standard hardware while the client is a resource-constrained IoT device. By minimising client-side operations and further optimising them under a savvy precomputation phase, we enable OT to be deployed in scenarios where traditional schemes would be computationally prohibitive. The proposed protocol is grounded in the ring Zn , where n = p · q as usual, and p ≡4 q ≡4 1 is required. In particular, it leverages: (i) pseudo-randomness generated from a Key Derivation Function (KDF) F to ensure message confidentiality; (ii) the quadratic residuosity problem to enforce security guarantees; and, (iii) a cryptographic hash function H(·) to disambiguate roots in Zn .

3 b ∈ {0, 1}

M0 , M1

OT Sender

⊥

Mb

Receiver

Fig. 1. Abstraction of a Base OT protocol. In detail, I-(OT )2 introduces several technical contributions, synthesised in the following: Minimal message exchanges:: The proposed solution eliminates the need for an initial message exchange from the Sender to the Receiver. The Receiver sends a single ring element (masked key) to the Sender, which then responds with a nonce for the KDF (say one ring element to ease exposition), 4 ciphertexts, and four key digests (typically 256 bits). This results in a total of two ring elements, four messages, and four digests, optimising communication overhead. Security against a malicious Sender:: Different from other OT proposals, which are designed in the context of honest-but-curious senders, our transfers are secure by design against malicious behaviours. Malicious senders can still poison the protocol during setup by modifying the required congruencies on p and q; however, we define a probabilistic game that any Receiver can run to validate the modulus trustworthiness. A full probabilistic analysis of said game is also provided and the game framework itself can be extended to different hypothesis testing. Optimal Receiver-side overhead:: By requiring only one random ring element sampling, a single call to the Hash function and the KDF, one modular squaring, one message xor, and at most one subtraction, the proposed scheme is, to the best of our knowledge, the most efficient classical OT scheme Receiver-side. Furthermore, all the operations, but for the XOR and the KDF evaluation, can be precomputed offline, making it extremely competitive in the online transfer phase despite the primitive computational impact, and hence particularly suitable in the context of IoT. Open source code and testing: We realised an open source implementation1 (proof-of-concept) in C language, running the scheme on a single machine to assess its performance. In particular, we benchmark it against both a desktop personal computer and an IoT Raspberry Pi Zero 2W, achieving, to the best of our knowledge, the lowest online computational burden on the Receiver side (more than 10× faster than the online execution of [14], often used as a benchmark in the literature). We also release a python multi-machine implementation to show its feasibility in real contexts. By combining these innovations, our protocol achieves a lightweight, efficient, and secure OT mechanism, making it particularly well-suited for IoT applications. 1.2. Paper Organisation. The remainder of this manuscript is organised as follows. In Section 2, we present the OT context and the related literature. A short introduction of the notation and the mathematical background follows in Section 3. Within Section 4, we present our novel approach to OT, or I-(OT )2 , formally discussing the system model and its corresponding expected security (Section 4.1), the various threat models (Section 4.2), the actual scheme (Section 4.3), and the computational complexity of the transfer itself (Section 4.4). In Section 5, we then proceed to present the security under the proposed threat models (Section 5.1, see Appendix B for a formal definition of the security games involved), which also covers the setting of untrusted senders, as detailed in Section 5.2, where we present an innovative game to assess sender trustworthiness (a detailed discussion on the game’s success probability can be found in Appendix A). In Section 6, we explore the details of our experimental campaign, presenting the settings of our proof-of-concept implementation (Section 6.1) and discussing the corresponding results (Section 6.2). Finally, Section 7 concludes the paper, summarising the contribution and discussing future work. 1Online available at https://github.com/eOnofri04/IOT2.

4

2. Related Work Oblivious Transfer (OT), first introduced by Rabin in 1981 [1], laid the foundation for secure multiparty computation by proposing a method to exchange secrets without either party learning superfluous information. Rabin’s protocol leverages quadratic residues and public-key cryptography to ensure the Sender remains oblivious to the recipient’s choice, inspiring extensive research on OT efficiency and security. Building upon Rabin’s foundation, Even, Goldreich, and Lempel formalised the one-out-of-two variant of OT in 1985 [15], establishing it as a cornerstone for secure multi-party computation, private information retrieval, and privacy-preserving cryptographic protocols. We refer the reader to Yadav et al. [35] for a broader survey of OT protocols and their applications. OT21 protocols can be extended to OTn1 and OTnk , allowing the Receiver to select one or multiple messages out of n while preserving obliviousness and message privacy [36]. Such extensions underpin advanced cryptographic functionalities, including secure function evaluation and private set intersection. As a result, OT has been extensively studied under a variety of assumptions, including classical number-theoretic assumptions (e.g., DDH, CDH), lattice-based primitives, and generic dual-mode public-key encryption frameworks [19]. Naor and Pinkas [8] improved OT by constructing efficient 1-out-of-n OT schemes from the DDH assumption, with logarithmic overhead in the selection domain and round-efficient communication, becoming a reference point for many practical implementations. Subsequent works refined OT under different security and communication models, including adaptive queries [36], noisy channels [18], and information-theoretic Receiver privacy [7]. A closely related primitive is Random Oblivious Transfer (ROT), also referred to as OT with random inputs, in which the Sender does not choose the messages but instead learns two uniformly random strings generated by the protocol, while the Receiver learns exactly one of them. Introduced and formalised by Crépeau in the context of noisy-channel cryptography [18], ROT was shown to be equivalent to standard OT21 , as each primitive can be obtained from the other via local post-processing. This equivalence has made ROT the preferred abstraction in modern protocol design, particularly in settings where correlated randomness is generated independently of application-level inputs. A major line of work focuses on OT extensions. Ishai et al. [12] introduced the OT extension paradigm, enabling a large number of OTs using only a small number of expensive base (R)OTs and predominantly symmetric-key operations. This paradigm was later refined to achieve stronger guarantees, including malicious security [10], and is now the de facto standard for large-scale secure computation. More recently, Couteau et al. [30] proposed QuietOT, an OT-extension framework with a public-key setup, allowing parties to generate pseudorandom OT correlations after a one-time publickey phase and with only lightweight online operations. Unlike traditional OT extension, QuietOT reduces the need for an interactive base-OT setup. As a result, however, the concrete cost of the initial batch of base OTs is often treated as negligible, an assumption that holds only when the number of extended OTs is sufficiently large. Beyond OT extension, several frameworks construct OT generically from public-key encryption (PKE). Peikert, Vaikuntanathan, and Waters [19] proposed a composable framework yielding UCsecure OT in the CRS model under assumptions such as DDH, quadratic residuosity, and LWE. Followup works, including endemic OT [23] and subsequent optimizations [27], further improved efficiency and multi-user security. However, public-key operations remain computationally expensive and often impractical on low-power devices. A complementary line of inquiry concerns the formal relationship between OT and Private Information Retrieval (PIR), in which a Receiver privately fetches an entry from a remote database. The two primitives are tightly intertwined: Di Crescenzo et al. [37] showed that any non-trivial single-server PIR implies OT, while conversely 1-out-of-n OT directly realises symmetric PIR (SPIR). Modern PIR research has substantially advanced the communication efficiency of single-server retrieval, yet these constructions typically rely on heavy public-key or homomorphic primitives that remain prohibitive on constrained Receivers — a constraint that further motivates lightweight base OT designs of the kind proposed here.

Protocol

Year

1985 [15] 1989 [16] 1999 [17] 2004 [7] 2005 [18] 2008 [19] 2011 [20] 2012 [21] 2015 [10] 2015 [14] § [14] 2019 [22] 2019 [23] 2020 [24] 2020 [25] 2020 [9] 2020 [13] 2021 [26] 2022 [27] 2024 [28] 2024 [29] 2024 [30] 2025 [31] 2025 [32] 2025 [33] 2026 [34] 2026 I-(OT )2

3 1 2 2 2 2 2 2 2 2 – 2 2 2 2 3 3 2 2 2 4 2 2 2 2 4 2

Choosable inputs ✓ ✓

✓ ✓

✓ ✓ ✓

– ✓ ✓ ✓ ✓ ✓

✓ ✓ ✓ ✓

Communication Transfer Rounds

✓ ✓ ✓ ✓

Resilience to malicious adv. ✓

✓ ✓

✓

✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ – ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓

No Trusted Third Party required ✓

✓

✓ ✓

✓ ✓

✓ ✓ ✓ ✓ ✓ – ✓ ✓ ✓ ✓ ✓ ✓

✓

✓ ✓

Proof-of-concept implementation‡

Cryptographic primitives¶ PKE CDH Trusted initializer DDH Noisy channel PKE (DDH/LWE) ROM DDH DDH DH – Ideal lattice PKE (LWE, RO) CDH ROM (RQC-III) LWE CDH Isogeny PKE (ROM) QR + LPN NI NI + LWE + ROM DDH Quantum ent. Quantum ent. NI QR 164

✓

✓ ✓

530 2366

∼350 N/A∆

1760†

✓

✓ ✓

∼ 200

✓

Transfer global exec. time [µs] ∼ 3680 114 257

Sender execution time [µs]

✓ ✓ –

Allows for Receiver pre-computation⋆

Receiver (IoT) online exec. [µs]

Receiver online exec. [µs]

567.04 Not addressed by authors.

68.91

Not addr.

Not addressed by authors.

Not addressed by authors.

Not addressed by authors.

2350.93

2.80

39.90

Not addressed by authors.

✓

✓

Not addr.

Not addressed by authors.

Not addressed by authors.

Not addressed by authors.

Not addressed by authors.

Not addressed by authors.

✓

✓

✓ ✓

Open Source (✓)

Not addressed by authors.

1080†

Not addressed by authors.

503.33†

Not addressed by authors.

Not addressed by authors.

76.76

Not addressed by authors.

Not addressed by authors.

Not addressed by authors.

Not addressed by authors.

Not addressed by authors.

Not addressed by authors.

Not addressed by authors.

Not addressed by authors.

Not addressed by authors.

Not addressed by authors.

Language ✓ ✓

✓ ✓

✓

✓ ✓ ✓

C++ C/Python

C++ C

Relic

unspecified

Assembly

C (of [19]) Assembly C

5

Table 1. Summary of the structural features and structural statistics of 20 representative OT protocols from the literature, here compared against the proposed I-(OT )2 protocol.

¶ Acronyms: (ROM) Random Oracle Model; (CDH) Computational Diffie–Hellman; (DDH) Decisional Diffie–Hellman; (NI) Non-interactive tech.; (LWE) Learning With Errors; (QR) Quadratic Residues; (LPN) Learning Parity with Noise. ‡ Computational security is set to 128 bits in all works, but [29], which relies on unconditional security based on NI. ⋆ (✓) allows pre-computation, yet with minor impact on overall performance (< 2×). ∆ OT Extension relies on non-interactive PKE setup, hence no baseOT is assessable. † Performances evaluated in CPU cycles and estimated at 3GHz. § Results obtained over our porting of the library.

6

Considerable effort has also been devoted to optimising the concrete efficiency of base OT protocols. The Simplest OT protocol by Chou and Orlandi [14] (whose security has been revised in [38] and further re-examined in [39]) achieves extremely low concrete cost using elliptic-curve cryptography (ECC) and is widely adopted in practice, despite offering weaker security guarantees than modern simulation-based frameworks. More recent protocols, such as Blazing OT [13], achieve UC security with competitive performance, but still rely on ECC and often benefit from hardware acceleration, which is typically unavailable on constrained low-power platforms. Several works further refine communication and round complexity in the batch setting; for example, Branco, Döttling, and Srinivasan [28] propose a two-round batch OT protocol with near-optimal communication based on quadratic residuosity and the Learning Parity with Noise assumption. Alternative directions explore different assumptions and frontiers, including LWE-based OT [9], isogeny-based OT [26], and quantum or post-quantum OT variants [40, 41], typically targeting powerful platforms. Other applications of the OT protocol include machine learning and AI implementation. These studies [42, 43] demonstrate significant throughput improvements in large-scale secure computation and privacy-preserving machine learning by exploiting massive parallelism and hardware acceleration. In parallel to classical software-oriented OT designs, several recent works also explore orthogonal directions that differentiate from the traditional setting. A first line of research investigates quantum variants of OT, extending the primitive to quantum messages or even to unknown unitary operations applied remotely: these protocols rely on entanglement [32], Bell-state measurements [33], and quantum communication to achieve all-or-nothing semantics, and are primarily motivated by the intrinsic privacy-preserving properties inherently provided by distributed quantum computations. Finally, more closely related to the present contribution, Abadi and Desmedt [29] introduced Supersonic OT, an ultra-efficient OT extension protocol achieving unconditional security without public-key cryptography, later generalized to OTn1 and OTnk [44]. A step forward is provided in [34], where SupersonicOT is embedded in a more general framework offering delegated-query and multi-receiver OT, while targeting also low-end devices. Although achieving remarkable concrete performance, the solution relies on a trusted preprocessed setup, a trusted proxy mediation, and is not devised to decouple sender and receiver interactions. The connection between OT and quadratic residues originates from Rabin’s protocol [1] and is further developed in modern QR-based constructions [19, 28]. Rather than aiming for maximum generality or asymptotic efficiency, our construction explicitly targets scenarios where the Receiver is severely resource-limited. By delegating most cryptographic workload to the Sender or to an offline phase, the Receiver’s online computation is reduced to a minimal set of operations, making the protocol practical even on IoT devices. Table 1 summarises representative OT protocols and contrasts them with our proposal I-(OT )2 in terms of structural properties and computational analysis. 3. Notation and Background In what follows, we identify with Zn the ring of integers modulo n = p · q (with p, q primes) and we say that a given a ∈ Zn is positive if a < n/2. All of the operations, if not differently specified, are carried out in Zn . We state with λ the size of the modulus n and we report with κ the corresponding (symmetric) security parameter (e.g. λ = 3072 ⇒ κ = 128, see [45]). Quadratic residues modulo n are identified by the set QRn := {x ∈ Zn | ∃t ∈ Zn , t2 ≡n x} (or simply QR) and we recall that evaluating whether x ∈ QR is considered hard, the so-called Quadratic Residuosity Assumption (QRA), unless the factorisation of n is known; in such case, many different approaches do exist, including the Tonelli-Shanks algorithm which also allows evaluating the two couples of roots in Zp and Zq which can be combined into four roots in Zn according to the Chinese Remainder Theorem (CRT), i.e. solving a modular system of two equations. We recall a Key Derivation Function (KDF) being a function transforming keying material into one or more cryptographically strong outputs. Typical goals are entropy stretching and domain separation,

7

Table 2. Table of symbols, divided by phase and ownership. Var

Definition

Owner

Description

Setup p, q

≡4 1

Sender

RSA-like prime numbers

n Zn λ κ F K Y H

=p·q — = log2 (n) — K × Zn → Y — — Zn → H

Shared Shared — — — — — —

— √ −1

Integer modulus Ring of integers modulo n Bit size of the modulus n Security parameter Family of KDF Key space for the KDF Codomain of the KDF (message space) Cryptographic hash function (used for roots digests) Root tag/digest space

Sender

Square root of −1 mod n

H I

=

—

Transfer phase M0 , M 1 k d t k̂

∈Y ∈ Zn H(k) = k2 mod n ∈ Zn

Sender Receiver Receiver Receiver —

Oblivious transfer messages Oblivious transfer session key Session key digest Residue of the session key Conjugate of the session key

b r s

∈ {0, 1} ∈ Zn ∈K

Receiver Shared Shared

Oblivious transfer choice Residue hiding the choice Key for the KDF F

(j)

∈ Zn ∈ {b, 1 − b} ∈ {0, 1}

Sender Shared Shared

Set of plausible session keys Receiver possible choices Receiver conjugate index

{ki } i j ĵ

∈ {0, 1}

Receiver

Actual conjugate index

{ci }

(j)

= Mi ⊕ K i

Shared

Set of ciphertexts

{di }

(j)

= H(ki )

(j)

Shared

Plausible session key digests

(j)

= Fs (ki ) = Fs (k)

(j)

Sender Receiver

Set of plausible message keys Actual message key

{Ki } K

(j)

Check congruency phase ℓ X c

— ∈ Zℓn ∈ {1, 2}

Shared Receiver Receiver

Number of tests Test set Challenge choice

y r R

= −xc mod n ∈ {T, F} {r | c = 1}

Shared Shared Receiver

Challenge value Challenge response Response set of c = 1 answers

with Kessak-based KDF (SHAKE-based, [46]) being a widely deployed construction. Here, different useful properties do hold, including pre-image and second-preimage resistance. More formally, the core of KDFs can be abstracted as Pseudorandom Functions (PRFs), i.e. keyed family of functions F :K×X →Y such that, for any random key k ∈ K, Fk (·) is computationally indistinguishable from a random function. In what follows, we assume X = Zn .

8

We define a message M as a generic bit-string, M ∈ {0, 1}∗ = P, and we denote with ⊕ the bit-wise xor. In what follows, we assume P = Y, namely the message is compatible with the output of F so that messages can be efficiently encrypted à la One Time Pad (OTP) as c = M ⊕ y. Finally, we define with H a generic cryptographic hash function over Zn : H : Zn → H . (j)

In our construction, H(·) is later used to discriminate over quadratic residues (see later di ), hence it is important to recall that pre-image and second-preimage resistance hold; however, digests of H might be modest in size, if compared with n. For the reader’s convenience, we provide in Table 2 a list of all symbols adopted within the manuscript, arranged according to the protocol’s phases. 4. The I-(OT )2 Protocol In this section, we describe the architecture of the proposed I-(OT )2 model, our novel lightweight OT encryption scheme based on the problem of quadratic residuals, able to deliver an OT21 -transfer to the Receiver requiring only a few transmissions and operations. We recall that operations are carried out within the ring Zn if not differently specified. Here n = p · q, with p, q being primes chosen by the Sender such that p, q ≡4 1 (this ensures that −1 ∈ QR, i.e. ∃I ∈ Zn such that I 2 ≡n 1, I ̸= 1, √ I := −1) and (eventually) validated by the Receiver with a dedicated protocol (see later Section 5.2 for a discussion on untrusted senders). 4.1. The system and security models. We rely on the classical OT model, which we briefly recall here for completeness. The system consists of two logical entities interacting over a public communication channel Sender: The Sender holds pairs of messages (M0 , M1 ) and is responsible for executing the transmission protocol. The Sender is assumed to be computationally capable, and can efficiently perform expensive operations such as square root extraction in Zp × Zq . For what concerns security properties, the server might be modelled as an unbounded party (being the security of the choice obliviousness, see below, proved under unconditional, information-theoretic, guarantees). (Set of ) Receiver(s): The Receiver selects a bit b ∈ {0, 1} and interacts with the Sender to retrieve specifically the message Mb . Receivers are assumed to be computationally constrained and are required to perform only lightweight operations. Importantly, our security guarantees do not rely on this assumption, and remain valid even when Receivers are capable of heavycomputation (or can delegate them to others). We can then formalise the scheme as follows. Scheme 1 (OT21 ). An OT21 scheme consists of the following three algorithms: Setup(κ) → (sk, pk):: is the initialisation algorithm run by the Sender to set up a pair of public keys (pk = n) and a secret key (sk = (p, q)) starting from a security parameter κ (κ determines the length λ of the generated modulus). Transfer(pk, b) → (Mb , ⊥):: is the online interactive transfer that is run by the Receiver who selects a message b ∈ {0, 1} and queries the Sender for the two messages M0 and M1 (properly encrypted), of which only Mb will be decryptable by the Receiver itself. CheckReveal() → sk:: is an optional phase where the Receiver queries the Sender for its secret key so that he can check the entire protocol was played fairly. In particular, the transfer phase is required to satisfy the following security properties: Choice obliviousness: The Sender and any external attacker learn no information regarding the Receiver’s choice bit b. Messages obliviousness: The Receiver learns no information about M1−b , while external adversaries learn nothing about either message.

9

Do notice that the optional CheckRevealphase allows the Receiver to verify that the protocol was executed fairly. In fact, while the Receiver is unable to cheat the Sender by design, the Sender may trivially send identical (or slightly modified) messages as (M0 , M1 ), a typical drawback affecting OTprotocols. The CheckRevealmechanism hence enables post-hoc detection of such misbehaviour, making it a valuable tool for the Receiver. For what concerns protocol security, it is in general not possible to provide unconditional (informationtheoretic) guarantees on both the Receiver and the Sender at the same time. In particular, as we will see later in Section 5, our design offers unconditional choice obliviousness while granting computational message security. 4.2. The threat models. We are now ready to describe the threat model for I-(OT )2 . Let us consider the following four entities involved in the protocol: Sender (s-): In what follows, we assume the Sender being semi-trusted (honest-but-curious), meaning that it follows the protocol honestly (i.e., it does not deviate from the prescribed steps) but tries to learn as much as possible about the choice b from the communications it receives during the execution of the protocol itself. We will discuss specifically the security of malicious senders in Section 5.2. Receiver(s) (c-): We assume the Receiver(s) as untrusted, meaning that it (they) can deviate from the protocol and use any strategy to try breaking the messages’ obliviousness or the protocol’s cryptographic security. Passive attacker (p-): We consider computational bounded passive attacker capable of eavesdropping all the communication occurring on the public channels, including multiple independent communications. Active attacker (a-): We suppose active attackers being able to control the communication channel and, hence, capable of read, intercept, modify, and generate messages at will. We do not consider poisoning attacks since we discuss the security against malicious receivers in what follows and against malicious senders later. In particular, we identify the following eight threats: (s-i): Sender breaking choice obliviousness: the Sender successfully retrieves the choice b operated by the Receiver during the transfer phase. (c-i): Receiver breaking cryptographic primitive: the Receiver is able to manipulate the protocol to break the security of the key n, i.e. retrieve its factorisation p, q. (c-ii): Receiver breaking messages obliviousness: the Receiver is not able to break the primitive, but it is able to manipulate the protocol to successfully retrieve both messages M0 and M1 regardless of the choice b operated. (c-iii): Receivers collusion: multiple receivers adopting the very same Sender key-pair can collude to gain a non-negligible advantage on any two of the previous tasks. (p-i): Eavesdropping attack: An external attacker can retrieve either the message(s) or the Receiver’s choice by solely monitoring the traffic. (a-i): Receiver impersonation attack: The attacker can impersonate the Receiver during the transfer phase to retrieve one (or both) the messages. (a-ii): Sender impersonation attack: The attacker can impersonate the Sender during the transfer phase to communicate a fake, valid message (for breaking choice obliviousness, see (s-i)). (a-iii): MitM attack: An external attacker can break into an active transfer to retrieve the messages, the bit choice, or to transmit chosen messages by acting as a man-in-the-middle, i.e. potentially modifying the messages passing through the public channel without the parties noticing it. We briefly discuss the corresponding security in what follows, and we resume the key concepts in Table 3. The choice obliviousness (s-i) is unconditionally secure by design, while the security of the cryptographic primitive (c-i) and the messages obliviousness (c-ii) for single messages is guaranteed under

10

Table 3. Threat model and security assumptions. Attacker

Model

Target

Security assumption

Sender

(s-i)

Choice obliviousness

Unconditionally secure

(c-i)

Factorisation of n

(c-ii)

Message obliviousness

indistinguishability + reduction

(c-iii)

Collusion

tNM-CCA

(p-i)

Eavesdrop messages

indistinguishability + tNM-CCA

(a-i)

Receiver impersonation

–†

(a-ii)

Sender impersonation

(a-iii)

MitM

Public-key security

Receiver

Passive

Active

† Can be achieved with Receiver single-side authentication layer.

the properties of the KDF and secure hash functions combined with a classical reduction to the factorisation problem. Receivers’ collusion-resistance (c-iii), as well as security for (c-i) and (c-ii) against message combination, are discussed under chosen ciphertext attacks with tag-non-malleability (see also [47]). In particular, here we recall a protocol being non malleable (NM) whether an attacker is not able to create a valid ciphertext with some arbitrary correlation with known ciphertexts [48]. Tag-non-malleability under Chosen ciphertext Attack (tNM-CCA1) implies in this context that the Receiver is not able to reconstruct a valid ciphertext with tag s without breaking the security of the protocol, even if it is able to decrypt polynomially many OT instances using different tags s′ ̸= s [49]. We also recall that NM-CCA1 also implies indistinguishability under the same assumption (IND-CCA1, [48, 3.1]). Eavesdropping resistance (p-i) is obtained under ciphertext indistinguishability and tag-non-malleability. Conversely, Sender impersonation during the transfer phase (a-ii) is unfeasible due to the impossibility of breaking the public key (as it is either for the Receiver itself). As a consequence, MitM attacks (a-iii) are unfeasible as well, as the attacker would be unable to impersonate the Sender with the Receiver or retrieve the messages encrypted with the Receiver key. Finally, being the Receiver not involved during the setup phase, an attacker is always able to impersonate a not-authenticated Receiver (a-i); however, this is endemic with the setting itself and can be easily mitigated by adding a single-side authentication layer between the Receiver and the Sender during the transfer phase. 4.3. The scheme. In what follows, we present the three algorithms, also depicted in Figures 2 and 3, that build our method as presented in Scheme 1. 4.3.1. Setup phase. During the setup phase, the Sender is required to build a public modulus n as a public key-pair of size λ, with λ chosen according to [45] depending on the required security level κ. In particular, it is important to notice that the setup requires no interaction with the Receiver, actually making it a Sender-exclusive phase: this also allows the Sender to use the same setup even with different receivers, which can potentially help each other to ensure the trustworthiness of the Sender (see later Section 5.2). In detail (see also Figure 2), the Sender chooses two large primes p, q exercising all due caution, like requiring that p − q is big, and evaluates n = p · q. In particular, values are chosen such that n ∼ 2λ and p, q ≡4 1 must hold as this ensures that I ∈ QR mod n, which is required for the protocol to be oblivious from the Sender side. In this phase, the Sender can also pre-evaluate I to later speed up the transfer phase.

11

Sender

Public

Receiver

choose security parameter κ, λ choose p ̸= q primes s.t. p · q ∼ 2λ and p, q ≡4 1 n

n ←− p · q

7−−−−→

precompute I =

√

n

−1

Fig. 2. Setup phase of the oblivious transfer. 4.3.2. Transfer phase. Let M0 , M1 ∈ Y be the two messages the Sender is willing to transfer to the Receiver. Conversely to a classical OT21 where the transfer phase is opened with the Sender sending two nonces to the Receiver to be used as message keys/discriminant, in our protocol the Receiver session key k is unique and it √ is generated by the Receiver itself as a random positive value in Zn (the usual caution of choosing k > n and gcd(k, n) = 1 must be exerted). This is particularly relevant since, apart from reducing the number of required rounds, it allows the Receiver to pre-evaluate k and subsequently pre-compute its corresponding residue t = k 2 (mod n) and its digest d = H(k). The Receiver then operates a choice on which message to pick, say b ∈ {0, 1}, and masks k by squaring it and communicating either r = t or r = −t (mod n) (i.e. r = n − t), depending on whether b = 0 or b = 1 respectively. Here it is important to recall that under the assumption p, q ≡4 1, x ∈ QR has exactly four roots in the form a, −a, b, −b and, since both −1, k 2 ∈ QR, we have that both r, −r ∈ QR. In fact, if b = 0 we have ( r = t = k2 (mod n) , −r = −t = −k 2 (mod n) while if b = 1 we have ( r = −t = −k 2 −r = t = k 2

(mod n) . (mod n)

√ √ It follows that the Sender is able to compute both r (mod n) and −r (mod n) using the pre(0) (1) (0) (1) computed I; let k0 , k0 be the two positive roots of r and let k1 , k1 be the two positive roots of −r. (j) In particular, do notice that k ∈ {ki }i,j∈{0,1} . However, the Sender is not able to determine î ≡ b, (j)

that is î ∈ {0, 1}, such that k ∈ {kî }j∈{0,1} . Concurrently, the Receiver must remain oblivious to (j)

(j)

the second root k̂ in {kî } as it is conjugate with k, namely {kî } = {k, k̂} and its disclosure would break the factorisation of n. In this regard, let s be a transfer nonce sampled by the Sender from K and communicated to the Receiver. Here s is used to agree with the Receiver upon a KDF Fs (·) to (j) (j) (j) hide the values of {ki }, hence generating four plausible session keys Ki = Fs (ki ). Being randomly distributed due to the properties of Fs (·), the Sender can then use the two couples of session keys to encrypt the messages M0 and M1 with a simple bit-wise xor operation, hence producing (j) (j) (j) four ciphertexts of the form ci = Mi ⊕ Ki = Mi ⊕ Fs (ki ). These ciphertexts are finally sent to (j) (j) the Receiver alongside with the digest of the four plausible roots di = H(ki ) for the Receiver to be 2 able to match the correct î = b and ĵ . 2Do note that here a possible alternative is to use some sort of small tag f to be prefixed/postfixed to the message (j)

instead of sending {di }. In particular, this avoids executing the hash operation at the cost of restricting the message space by the size (in bits) of f . Left for future work.

12

Pre-computation (Offline) Sender

Receiver

retrieve:

retrieve:

n, p, q, I

n

precompute:

precompute:

s ←$ Zn

k ←$ Zn/2 s.t. gcd(k, n) = 1 t ←− k 2

mod n

d ←− H(k)

Transfer (Online) Sender

Public

M0 , M1 ∈ Y

choose b ∈ {0, 1} message r

←−−−−−−[

r

s

7−−−−−−→ (0) ) k0 (1) k0 (0) ) k1 (1) k1

←−

←−

√

√

r

, chosen in Zn/2

r·I

, chosen in Zn/2

(j)

←− Mi ⊕ Fs ki

(j)

←− H(ki ),

ci

di

Receiver

(j)

(j)

,

i, j = 0, 1

i, j = 0, 1

r ←− (−1)b · t

mod n

s K ←− Fs (k)

{c

(j)

}

i 7−−−− −−→

{d

(j)

}

i 7−−−− −−→

(0)

(1)

(0)

(1)

(0)

(1)

(0)

(1)

c0 , c0 , c1 , c1

d0 , d0 , d1 , d1

(j)

let ĵ ∈ {0, 1} s.t. d = db (ĵ)

M ←− cb ⊕ K

Fig. 3. Transfer phase of I-(OT )2 divided into offline and online operations.

(ĵ)

Upon delivery, the Receiver is able to determine which message cb he can decrypt with k by (j) checking which digest db equals the precomputed d = H(k). The transfer phase is finally concluded by decrypting Mb : this can be done by simply evaluating K = Fs (k) and xor-ing it from the correct (ĵ)

ciphertext cb . 4.3.3. CheckReveal phase. The check-reveal phase corresponds to breaking down the scheme to ensure that the protocol was run fairly. It consists of the Sender revealing p and q to the Receiver. This clearly allows the Receiver to evaluate all the roots of r and −r and hence to verify that messages M0 and M1 were actually (j) different, as they can be decrypted from the corresponding {ci } with ease. It is interesting to notice that Receiver-side, obliviousness is maintained in this scenario (and hence also in the case of a compromising of the system, see later the upcoming Section 5.1). If the context requires the Receiver’s choice to be provable too, then the Receiver can reveal k as well, so that the Sender can determine which î is such that k ∈ {kîj }j∈{0,1} ; in this case, k should be communicated

13

prior to the factorisation of n in order to be trustworthy (otherwise the Receiver can evaluate the other roots with ease). Also, it is notable that the choice reveal does not require the Sender to interact with the Receiver, hence requiring no disregarding of the entire system; a similar outcome can be achieved also on the Sender side, actually mounting a partial check-reveal that allows the Sender provably reveal both messages while keeping the system intact. To do so, a simple yet effective way is, for example, to let the Sender generate two more message nonces s0 and s1 , and to send the Receiver the digests M̂i = H(Mi ⊕ si ) along with the ciphertexts; this allows the Receiver to verify M1−b if M1−b and s1−b are revealed, while not compromising the obliviousness of M1−b , even in the case of short messages (i.e. when plaintext space is small enough to allow a brute force search). 4.4. Transfer complexity analysis. In this section, we analyse the computational complexity of the proposed I-(OT )2 protocol in terms of the key size λ. In particular, all the operations (but H(·), Fs (·) and ⊕ evaluations) are performed in Zn where, typically, optimal algorithms do exist that execute either in O(log n) or O(log p + log q) bit operations, with n = p · q. Here we can recall that log n ∼ λ and, due to the typical cryptographic constraints on p and q, we can claim log p ∼ λ/2 ∼ log q, hence bounding most operations (including also bit-wise xor) to O(λ). In what follows, we separately assess the operations executed by the Receiver during transfer (online) and prior to engage it (offline) and by the Sender, as well as the relative communication cost. 4.4.1. Receiver-side complexity. The Receiver’s overhead is purposely kept minimal to accommodate resource-constrained devices as it is common in IoT applications. For this reason, we design simpler operations on the Receiver side, a complexity analysis of which is detailed in what follows and summarised in Table 4. Random choices: The Receiver is required to offline uniformly sample (or choose) a choice bit b and a positive ring element k ←$ Zn/2 , accounting for O(λ) random bit generations. Fur√ thermore, ensuring gcd(k, n) = 1 and k > n can also be carried out within O(λ) operations in the worst case. Modular squaring: To evaluate the quadratic residue r = (−1)b · k 2 mod n, the Receiver performs one squaring and one additive inversion modulo n, summing up to one addition (n − t if b = 1) and one multiplication which can be carried out with O(λ2 ) bit operations under classical algorithms. Squaring can be performed offline, while inversion depends on the individual interaction (yet offering nearly negligible overhead). Message decryption: In order to determine the correct ciphertext to decrypt, the Receiver must perform a single hash evaluation H(k), typically requiring O(λ) bit operations, which can be pre-evaluated. Then, at transfer time, a single evaluation of Fs (·) and a single xor are sufficient to retrieve Mb . Here, evaluating Fs (·) clearly dominates the online phase, potentially leading to unexpected increases in complexity. However, different solutions do exist to keep the computational burden low, while maintaining the essential properties required for securely and correctly run the protocol; in our implementation (see later Section 6), e.g., we considered the sponge hash function SHA-3 [46] in its XOF form (namely SHAKE-256/512), actually instantiating Fs (k) = H3 (s + k), where s is chosen in Zn for simplicity and H3 represent SHAKE-256. This keeps the computational burden bounded to O(λ)3. 4.4.2. Sender-side complexity. Conversely to the Receiver, the Sender is assumed to be computationally capable of executing more intense operations with ease, namely executing the Tonelli-Shanks algorithm for evaluating QR root sets and applying the CRT for combining said roots. The complexity of each individual function is summarised in Table 5 while an in-depth description follows: 3Here, to be precise, computational cost is O(2λ · γ e ), for some e ∈ (1, 2], where γ represent the required security level of the hash function under collision, namely an attacker is required O(2γ ) attempts to find a collision.

14

Table 4. Transfer phase (Offline and Online) computational cost in bit-operations (Receiver-side). Operation

Cost per op

Number of op

Total cost

Pre-computation (Offline) Bit generation Greatest common divisor Modular multiplication Hashing

O(1) O(λ) O(λ2 ) O(λ)

O(λ) 1 1 1

O(λ) O(λ) O(λ2 ) O(λ)

1–2 1

O(λ) O(λ)⋆

Transfer (Online) Bit-wise xor KDF

O(λ) O(λ)⋆

⋆ depending on the design/implementation of F (·). s

Square roots evaluation: Exploiting the knowledge of p and q, the Sender can evaluate the roots of a QR by evaluating the roots individually in Zp and Zq and later combining them according to the CRT. In particular, the four roots of r can be evaluated by applying the Tonelli–Shanks algorithm, hence resulting in a computational cost of O(log p)) ∼ O(λ/2) operations each, while combining roots of size λ again costs O(λ) operations (mainly to evaluate the Extended Euclidean Algorithm). Conversely, evaluating the four roots of (−r) benefits the pre-evaluation of I, actually allowing saving most of the computation (only 2 multiplications and at most two subtractions are needed). However, in both cases, it is important to notice that multiplications, divisions, and squarings are involved, actually prompting a total cost of O(4λ3 ) operations for both cases. Random choices: The Sender is required to uniformly sample the nonce s (ring element), requiring O(λ) random bit generations. This is the only operation the Sender can anticipate in an offline phase. ciphertext evaluations: Building ciphertexts requires the same set of operations already described for the Receiver decryption, all caveats of the case included. However, the Sender is required to process four different ciphertexts, including four evaluations of Fs (·), hence assessable as O(4λ) in total. (j) Digests evaluation: The Sender is required to evaluate the digests di for the four plausible roots, actually incurring in four evaluations of H(·), i.e. O(4λ) bit operations.

4.4.3. Communication cost. In IoT applications, particularly in the oblivious transfer context, minimising communication costs is crucial to ensure energy efficiency, reduce latency, and enable reliable operation in resource-constrained or bandwidth-limited networks. For this reason, the protocol was designed to reduce as much as possible the message exchange between the Sender and the Receiver. In particular, here a single transfer requires the Receiver communicating the quadratic residue r and the Sender responding with the KDF key s, both being elements of Zn in our implementation. Apart from this initial exchange, the other sole transfer consists of two ciphertexts per message along with the digest of the four corresponding keys. If needed, digests communication can be circumvented by solutions like the one proposed in Footnote 2; however, in practical implementations, digests are typically small in size (say 256 bits) if compared to modulus n (say at least 2048 bits), hence making a single ring element larger than the 4 digests themselves. The total communication complexity can be therefore bound with 2 ring elements and 4 messages (encrypted).

15

Table 5. Transfer phase (Offline and Online) computational cost in bit-operations (Sender-side). Operation

Cost per op

Number of op

Total cost

Pre-computation (Offline) Bit generation

O(1)

O(λ)

O(λ)

Transfer (Online) Tonelli-Shanks CRT Modular multiplication

O(λ3 ) O(λ3 ) O(λ2 )

2 4 2

O(2λ3 ) O(4λ3 ) O(2λ2 )

KDF Bit-wise xor Hashing

O(λ)⋆ O(λ) O(λ)

4 4 4

O(4λ)⋆ O(4λ) O(4λ)

⋆ depending on the design/implementation of F (·). s

5. Security of I-(OT )2 In this section, we discuss the security of the proposed protocol and its obliviousness (see Section 4.1) w.r.t. the threat models introduced in Section 4.2 and summarised in Table 3. In particular, we structure the discussion considering one attacking entity at a time, namely the semi-trusted Sender, the malicious Receiver, the passive attacker, and the active attacker. Finally, we consider the case of a malicious Sender and we show how the Receiver can play a game to check whether the Sender is acting honestly. 5.1. Security Analysis. We now proceed to discuss the security of our model against the threats introduced in the previous section. In particular, we analyse the security of our solution from the perspective of one involved entity at a time. 5.1.1. (s) Honest-but-curious Sender. We start by observing that breaking the obliviousness of the Receiver’s choice would require the Sender to determine whether the value r received during the transfer phase is of the form r = k 2 or r = −k 2 for some k ∈ Zn . Since r is the sole value communicated by the Receiver to the Sender, any such attack must rely exclusively on distinguishing quadratic residues of the form k 2 from those of the form −k 2 . However, since the modulus n = pq is generated with p ≡ q ≡ 1 (mod 4), it follows that −1 ∈ QRn . Consequently, both k 2 and −k 2 are quadratic residues modulo n. Moreover, since gcd(k, n) = 1, each of the values ±k 2 admits exactly four square roots modulo n, two of which are positive. In particular, (j) all four positive roots {ki } of ±k 2 are equally likely and induce the same multiset {k 2 , −k 2 }, making the Receiver’s choice bit b (that determines which element of the pair is transmitted) perfectly hidden. Since k is sampled uniformly at random from Zn , from the Sender’s perspective the two possible choices for b are therefore equiprobable. We note that pathological cases in which gcd(k, n) ̸= 1 would reduce the number of square roots and could, in principle, leak information; however, such events occur with negligible probability and would otherwise imply an accidental factorisation of n. These intuitions, which can be formalised via an indistinguishability game as presented in Appendix B, show that threat (s-i) is prevented by design and that choice obliviousness holds unconditionally, provided the setup phase is executed honestly. 5.1.2. (c) Honest-but-curious Receiver(s). We now consider the security of the protocol against an honest-but-curious Receiver. As such, the Receiver follows the protocol specification but attempts to extract additional information from the received messages, beyond the intended output Mb . We recall that each transfer consists of the Receiver selecting a session key k ∈ Zn and a choice bit b ∈ {0, 1}, and transmitting the value r = (−1)b k 2 mod n to the Sender. In response, the Sender

16 (j)

(j)

provides four ciphertexts {ci }, encrypted under four distinct message keys {Ki } derived from the (j) square roots {ki } of ±r via a keyed KDF Fs (·), where the KDF key s ←$ Zn is freshly and uniformly (j) chosen by the Sender. Additionally, the Sender provides digests {di } that allow the Receiver to (ĵ)

identify the unique index ĵ such that kb

= k, and hence to recover Mb . (ĵ) (1−ĵ) Given knowledge of k = kb , computing the conjugate root kb is known to be computationally

equivalent to factoring n, since (ĵ)

(1−ĵ)

gcd n, kb − kb

(j)

reveals a non-trivial factor of n [1]. Similarly, computing any root k1−b of −r would imply evaluating √ I = −1 mod n, which is hard under the same assumption. Therefore, deriving any additional root from (k, r) is computationally infeasible. (j) Under the security properties of the KDF Fs (·), each key Ki is computationally indistinguishable (j) (j) from random unless the corresponding root ki is known. Consequently, all ciphertexts ci except the one indexed by (b, ĵ) are indistinguishable from encryptions under random keys. Furthermore, even the knowledge of the plaintext Mb , partial knowledge of the plaintext space, or access to a decrypting (j) oracle (which would allow recovering all Ki ) reveals no information about the underlying roots due (j) to the pre-image resistance of Fs (·). The same argument applies to the digests {di }, which, under standard hash-function security assumptions, do not enable recovery, testing, or correlation of unknown roots in the absence of the corresponding root. Here, in fact, we stress that cryptographic hiding and key indistinguishability rely exclusively on the Fs (·), while the hash function H is used solely as an identification mechanism. These observations, which can be formalised via the message obliviousness game presented in Appendix B, guarantee primitive security (c-i) and message obliviousness (c-ii) for a single transfer. If multiple transfers are considered under the same KDF key s, the security properties of Fs (·) guarantee that all additional ciphertexts and digests remain computationally indistinguishable from random for the Receiver. If different KDF keys are used across transfers, the independence of the KDF family {Fu (·)}u∈K ensures that no combination of prior information yields a non-negligible advantage on any new transfer. Consequently, even when allowing adaptive access to previous ciphertexts and plaintexts, an honestbut-curious Receiver cannot exploit prior queries to create valid ciphertexts or infer unknown roots. Generating a valid ciphertext would require either computing unknown roots from k and r (equivalent to factoring n) or breaking the KDF security. Therefore, the protocol achieves transfer-level nonmalleable CCA security (tNM-CCA). Finally, collusion of polynomially many Receivers (c-iii) does not provide any additional advantage beyond what a single Receiver could achieve by executing the same number of transfers individually. When each Receiver receive independent messages, collusion yields no new information. If identical messages are used across users, the system only reveals what is inherently observable from the choice selection and does not compromise the protocol’s obliviousness guarantees. 5.1.3. (c-u) Untrusted Receiver(s). Let us now consider the possible enhanced behaviours of a malicious Receiver. As already stated for (c), a malicious Receiver can influence the protocol only slightly. In fact, its active role involves the transfer of the sole value r, which can be: (i) random valid (i.e. a value obtained by squaring a random number); (ii) chosen valid (i.e. obtained from a chosen k); or, (iii) possibly invalid i.e. r random or chosen. The first case corresponds to not modifying the scheme, hence there is nothing to prove as it reduces to the honest Receiver case already analysed. In the second case, the Receiver can choose k to try achieving an advantage amongst different transmissions, e.g. sending multiple times the same r or trying to exploit a combination of multiple ks; however, the Sender entrusts the random choice of the nonce s which will be different for each transmission; as a consequence, for each transfer a given key k is sent to a different randomly-picked value K, ensuring session independence of the derived keys, so that combining multiple protocol executions yields no additional information. Hence, no advantages can be gained this way as well. Finally, if r is chosen

17

without regard of k (either randomly or not), then the Receiver loses its ability to know a root, and then it is unable to decrypt both messages; moreover, with a probability of 3/4, a random value for r yields a non-quadratic residue, making the Sender aware of the tampering. This proves the ineffectiveness of malicious Receiver behaviours as well. 5.1.4. (p) Passive attacker. The security under a passive attacker is directly guaranteed by the previous security statements: since the Sender learns strictly more information than a passive attacker, any (j) attack by the latter would contradict Sender obliviousness. In fact, with the sole knowledge of r, {ci }, (j) {di } and s, the attacker is neither able to retrieve the roots of r to decrypt the messages (due to the hardness of the square root problem), nor to decide on the choice of b (as the more powerful/informed Sender is unable as well). Furthermore, as discussed for the Receiver, the combination of transfers is not exploitable as well, hence granting security under the passive attacker (p-i). 5.1.5. (a) Active attacker. As already discussed, Receiver authentication is not addressed by the protocol, as no mechanism is provided to bind a transfer to a specific Receiver identity. Consequently, Receiver spoofing (a-iii) is outside the threat model and can only be mitigated by external authentication mechanisms. Such mechanisms are orthogonal to the obliviousness guarantees of the protocol and can be realised, for instance, at the transport layer or via standard public-key authentication, without impacting the protocol design. Concurrently, Sender spoofing during the transfer phase (a-ii) is computationally infeasible. In order to produce a ciphertext that the Receiver would successfully accept (and hence decrypt), an attacker must derive the specific root k selected by the Receiver in order to evaluate both H(k) and Fs (k). However, given only r, the Receiver’s key k is computationally hidden among the four square roots of ±r, and identifying it without the factorisation of n is equivalent to factoring n itself. Therefore, forging valid Sender responses is as hard as breaking the underlying quadratic residuosity or factorisation assumptions. Finally, consider an attacker acting as a man-in-the-middle, capable of intercepting, modifying, or dropping messages. To succeed without detection, the attacker would need to alter protocol messages while preserving Receiver decryptability. However, any modification of the value r results in a mismatch between the Receiver’s secret key k and the roots used to generate ciphertexts, making successful decryption impossible. As in the case of Sender spoofing, producing consistent ciphertexts would require recovering the Receiver’s root k, which is computationally infeasible. Therefore, the protocol resists active tampering and man-in-the-middle attacks at the transfer level, showing the security under (a-i) and concluding the discussion. 5.2. Working with untrusted senders. We conclude the security discussion by considering the case of an untrusted Sender. In particular, for what concerns the transfer phase, behaving maliciously does not make the Sender achieve any advantage over the Receiver. In fact, the Receiver choices (k and b) are independent of the Sender actions and occur prior to any interaction, hence being not misdirectable by the actions of the Sender. Furthermore, even in the case of a protocol corruption during the generation of the ciphertexts/digests couples, the Sender gains no significant advantage apart from being able to send the same message twice; however, the latter behaviour is not related to the malicious execution of the protocol but rather on the malicious input itself and it is usually solved with the potential check reveal phase, as already discussed. It is also rather clear that the Sender can generate a valid encryption for, say, m0 and an invalid one for m1 ; then, if b = 0 the tampering will be transparent to the Receiver, while if b = 1 the Receiver will be unable to decrypt m1 , hence potentially revealing b to the Sender. However, this behaviour is commonly accepted in literature as the Receiver becomes aware of the malicious conduct with probability 1/2. Conversely, behaving maliciously during the setup phase leads to much more interesting outcomes. In particular, choosing p, q ≡4 3 leads to catastrophic security results, allowing the Sender to break the obliviousness of the Receiver’s choice with ease. In fact, it is well known that if p, q ̸≡4 1 then −1 ̸∈ QR, hence −k 2 ̸∈ QR. As a consequence, the Sender is simply required to check whether r ∈ QR

18

Sender

Public

Receiver X ←$ Zℓn s.t. ∀x ∈ X gcd(x, n) = 1 for x ∈ X repeat: |

c ←$ {1, 2}

y

y

←−−[

|

y = −xc mod n

r = isQR(y)

7−−→

r

|

r

|

if c = 1:

|

|

|

elif r = T:

|

|

|

else:

|

|

save r in R

continue

Stop!

check that

( T R∼ F

w.p. 1/4 w.p. 3/4

Fig. 4. Check-congruency phase of the oblivious transfer.

(and hence b = 0) or r ̸∈ QR (hence −r ∈ QR and b = 1) and can still produce a valid encryption for Mb ; clearly no valid encryptions are allowed for M1−b in this case, but the Receiver remains unaware of the tampering until a Check Reveal is issued. To mitigate this problem, a simple yet clearly sub-optimal solution is requiring a trusted third party (TTP) to generate (or at least validate) p and q. Despite being effective and completely resolving all the related security issues, this solution misrepresents the scope and nature of OT protocols, which are typically run in distributed environments where no trust is enforced by any entity. Hence, we propose a second solution (TTP-free) relying on a probabilistic game that the Receiver can run to check whether the Sender generated a valid n or not. It is worth noticing that this solution is novel and interesting per se, as it can be generalised with ease to test most modularity properties of the factors involved in the creation of n (however, this is out of scope of the present work, as it deserves proper discussion on its own). Furthermore, multiple receivers can potentially collaborate in the game to reduce the moderate burden required. The game is presented in Figure 4 and described as follows under the name of Check Congruency. 5.2.1. Check congruency phase. During the Check Congruency phase (after setup, before transfers), the Receiver challenges the Sender to prove that −1 ∈ QR by asking to distinguish between negative squares −x2 , which should be quadratic residues with probability 1 (and are non-residues if congruency fails), and random numbers x, which can be either residue or not with probability respectively 1/4 and 3/4. In detail, ℓ numbers are randomly picked and potentially squared with probability 1/2 (or any other probability known to the Receiver solely), i.e. a random variable exponent c is sampled from {1, 2}. Then, the resulting values are multiplied by −1 and transmitted to the Sender which is required to answer whether those numbers are quadratic residues or not. For each value x ∈ Zn , if x is squared (c = 2), then a negative response yields a proof of guilty as −x2 ̸∈ QR if and only if at least one factor of n, say p, is such that p ̸≡4 1 (a positive response gives no further hints and can be discarded); conversely, if x was not squared (c = 1), then the response is stored in a response set R in order to check whether is distributed accordingly the expected distribution of 3/4 negative, 1/4 positive, i.e. R ∼

19

Bernoulli(1/4) or  R∼

T F

with prob with prob

1/4 3/4

 .

We proved (see Appendix A) that the closest response a malicious Sender can provide leads to R ∼ Bernoulli(3/4), actually prompting that the Receiver can decide whether the Sender is behaving maliciously with probability (> 1 − 10−6 ) when |R| > 75 (i.e. ℓ ∼ 215) by simply checking whether |{r = T | r ∈ R}| < ℓ/2. The interested reader can find in Appendix A a complete discussion on this topic, including the proof for the best strategy a malicious Sender can apply and all the probabilistic estimates formalised under both classical and Bayesian approaches. It is worth noticing that the computational cost of a single test is even lighter than a transfer since it does not require evaluating either hashes or square roots. From the Receiver’s perspective, the check congruency phase only involves ℓ random generation and (on average) ℓ/2 modular squarings, making it feasible even with a few hundred tests. Furthermore, communication-wise, the entire phase only requires the transmission of ℓ elements of Zn and ℓ booleans that can be packed together with ease. Finally, it is also possible for mutually trusted receivers to collaborate in generating and sending test values and hence assessing the trustworthiness of the Sender. 6. I-(OT )2 Proof-of-concept In this section, we present an empirical evaluation of the proposed I-(OT )2 protocol. We first outline the hardware and software choices, as well as the network conditions under which our proofof-concept (PoC) implementation was tested. We then report the experimental results, focusing on protocol performance, correctness, and suitability for constrained IoT environments. 6.1. The experimental setting. Our experimental setup involves two devices: an IoT embedded platform and a desktop general-purpose system. For the IoT configuration, we executed the protocol on a Raspberry Pi Zero 2W, equipped with a 1.0 GHz CPU and 512 MB of RAM, running the standard 32-bit Raspbian operating system. For the desktop configuration, we employed a Dell XPS 15 9530 laptop running Ubuntu 24.04.1 LTS. The system was equipped with an Intel Core i9-13900H processor clocked at ∼ 3 Ghz, 32 GB of RAM, and a 2 TB SSD. To ensure stable and reproducible performance measurements, the laptop remained connected to a power supply throughout the experiments and was not subjected to any additional compute-intensive workloads. We conducted two separate experiments, one per device, in which both the Sender and the Receiver defined by our protocol were executed on the same machine. The two entities communicated logically in a simulated Receiver–Sender setting. Network traffic was not routed through an external router, as our evaluation focuses exclusively on protocol-level performance, specifically execution time and CPU cycle consumption. 6.2. Results. In what follows, we discuss the results obtained during our test campaign. To recreate reasonably realistic conditions, we configured the Sender part to generate prime factors as RSA keys using OpenSSL. This ensures that typical security requirements are met and that the results are obtained using realistic modulus sizes and values. Both Python and C implementations of OpenSSL allowed us to run tests for λ ∈ {1024, 2048, 3072, 4096} corresponding to κ ∈ {80, 82, 128, 1504}, as values below 1024 are no longer considered secure and are therefore not supported. For each transfer, we independently generated two random messages of size λ (elements of Zn , for ease of simplicity) on the Sender side and a choice bit on the Receiver side, then executed the benchmark synchronously. We considered the processing time as offline for the operations that the two parties can pre-compute, and online for the operations that shall be computed during active transfer (cf. Figure 3). 4The estimation between 4096-bit RSA and 150-bit of symmetric security is proposed for comparison in [50]. We report it for comparability as 4096-bit RSA keys are still widely adopted in practice.

Total transfer

Sender

Receiver online

Receiver offline

3.38 2.89 10.67 2.43 1.45 1.05 1.03 1.58 0.96 0.09 252.84 254.56 295.50 206.98 24.24 258.45 260.10 300.44 211.00 24.59

std

mean median max min std

mean median

max min std

mean median max min std

1024 80

mean median max min

Key Size λ Security κ

977.28 973.34 1214.02 789.23 125.76

1202.89 779.61 126.01

967.49 963.79

1.90 1.88 2.27 1.77 0.08

2.12

6.26 5.68 16.88 4.21

2366.16 2413.22 2976.93 1897.70 345.09

2961.89 1882.48 346.33

2350.93 2398.10

2.80 2.78 3.32 2.60 0.11

2.80

10.32 9.71 22.63 6.93

5049.07 5081.51 6656.60 3755.69 827.11

6635.94 3734.19 827.79

5026.96 5064.36

3.83 3.82 4.39 3.51 0.19

3.69

15.95 15.49 31.41 9.59

Timings Desktop [µs] 2048 3072 4096 112 128 1504

5645.85 5620.96 6540.52 4740.26 544.74

6411.25 4612.29 549.78

5502.52 5486.07

21.70 21.51 36.20 21.04 1.53

15.73

91.40 89.14 159.22 70.83

1024 80

2.10e+04 2.12e+04 2.59e+04 1.69e+04 2760.59

2.57e+04 1.67e+04 2757.27

2.08e+04 2.10e+04

30.43 30.42 31.93 29.95 0.34

13.96

145.00 140.86 202.92 119.43

5.52e+04 5.53e+04 6.88e+04 4.22e+04 9142.22

6.85e+04 4.19e+04 9148.81

5.49e+04 5.50e+04

39.90 39.77 43.33 39.11 0.68

23.63

214.63 205.91 345.62 193.12

Timings IoT [µs] 2048 3072 112 128

1.15e+05 1.15e+05 1.45e+05 8.65e+04 2.03e+04

1.44e+05 8.61e+04 2.03e+04

1.14e+05 1.15e+05

49.37 49.17 51.88 48.54 0.67

18.81

283.93 276.04 365.83 268.12

4096 1504

5645.57 5620.70 6540.21 4739.95 544.74

6410.83 4611.98 549.78

5502.21 5485.81

21.50 21.30 35.99 20.83 1.53

15.73

91.19 88.96 159.06 70.62

2.10e+04 2.12e+04 2.59e+04 1.69e+04 2760.58

2.57e+04 1.67e+04 2757.27

2.08e+04 2.10e+04

30.22 30.16 31.72 29.74 0.34

13.96

144.79 140.60 202.76 119.27

5.52e+04 5.53e+04 6.88e+04 4.22e+04 9142.22

6.85e+04 4.19e+04 9148.81

5.49e+04 5.50e+04

39.69 39.58 43.12 38.91 0.68

23.64

214.37 205.68 345.37 192.97

1.15e+05 1.15e+05 1.45e+05 8.65e+04 2.03e+04

1.44e+05 8.61e+04 2.03e+04

1.14e+05 1.15e+05

49.14 48.96 51.67 48.33 0.67

18.81

283.71 275.78 365.57 267.92

Cycles [kilocycles, eval on Rpi] 1024 2048 3072 4096 80 112 128 1504

20

Table 6. Performance comparison (timings and cycles) between IoT- and Desktoplike devices across various key sizes.

Cycles [kilocycles]

21

102

Receiver online 101

1024

2048

Receiver offline 3072

4096

Key size λ [bits]

Fig. 5. Performances (in kilocycles) achieved during receiver online and offline phases of the transfer. The average Sender-side processing time was primarily dominated by the composite square-root operation required by the protocol, whereas the Receiver overhead remained minimal. The latter mainly consisted of a single modular squaring operation –that can be computed offline– and a one hash computation during the online phase (see Section 4.4). As expected, in all tests, the selected messages were always correctly retrieved. As Table 6 reports, the results from our experiments show that I-(OT )2 performs efficiently, with an average Receiver-side processing time of 39.90 µs and 214.63 µs respectively during the online and the offline phase to transfer a message using a 3072-bit key (κ = 128) on the Raspberry Pi Zero 2W. Furthermore, it can be observed that the computational load is overwhelmingly handled by the Sender, accounting for more than 99% of the total processing time. As the key size increases, the Sender’s required processing time grows, yet it remains consistently below 7 ms, reaching a maximum peak of 6.85 ms in the worst-case scenario. In contrast, the Receiver’s processing time is only marginally affected by variations in the key size. On the Desktop device, the average computation time required to complete the online phase for λ ∈ 1024, 2048, 3072, 4096 is 1.05, 1.90, 2.80, and 3.83 µs, respectively. The Receiver remains efficient even on IoT hardware, exhibiting computation times of 21.70, 30.43, 39.90, and 49.37 µs for the same set of operations. The results in terms of kilocycles (evaluated on the Raspberry Pi) are also reported in Figure 5. In summary, considering the advantage of the pre-computation of the computationally expensive components required by the protocol –actually computed only once during the entire protocol life– regardless of the configuration, performance remains satisfactory for typical usage, confirming the feasibility of our I-(OT )2 protocol in low-power IoT environments. 6.3. Comparison with SimplestOT. In order to provide a meaningful comparison with the state of the art, we decided to benchmark our approach against one of the most competitive (and widely adopted) references in the literature: SimplestOT protocol by Chou and Orlandi, originally presented in [14, 38]. Also known as CO-OT, Simplest OT presents many similarities in design if compared to I-(OT )2 , due to its simplicity in definition (driven by Diffie-Hellman key exchange) and global efficiency (also due to the usage of ECC). Furthermore, SimplestOT also might benefit from off-line pre-computation, despite not being exploited nor implemented in its original implementation: for this reason, we decided to make a porting of the original assembly code5 in C, implementing an online vs. offline benchmark. Here, it is important to notice that our C porting clearly degraded the original performances claimed; however, results suggest our re-implementation remains competitive and valid, with a nearly negligible overhead of 2× (cf. Table 1), expected under the change of language (as a reference, our Python implementation is three order of magnitude slower than the C implementation). 5The code is taken from https://github.com/secretflow/simplest-ot as the original link on the paper raise 404.

22

104 Time (µs)

I-(OT)2 10

SimplestOT

3

102 101 100

Sender

[Desktop] [IoT] Receiver Offline

[Desktop] [IoT] Receiver Online

Fig. 6. Performance (in µs) comparison between our I-(OT )2 and our C porting of SimplestOT [14]. We present a detailed comparison of the two approaches in Figure 6, which shows how I-(OT )2 protocol preserves superior efficiency on the Receiver’s online phase, achieving 14× the performance on the IoT machine (25× resp. on the desktop machine). Most notably, I-(OT )2 outperforms SimplestOT in the Receiver’s online phase, even cross-platform, actually achieving lower execution time on the IoT device, even if compared with SimplestOT running on the desktop machine. This result represents a significant step forward, as it clearly indicates that, in large-scale deployment scenarios, expensive, high-performance hardware can be potentially replaced with low-cost IoT devices, while still achieving better performance during OT execution. Overall, these results validate the proposed design: the computational burden is effectively shifted to a well-resourced Sender –which can scale to higher performance depending on the setting– ensuring lightweight requirements on the IoT Receiver. 7. Conclusion and Future Work In this paper, we presented I-(OT )2 , a novel Oblivious Transfer protocol optimised for efficiency and security in client–server architectures, with a particular focus on resource-constrained environments such as IoT devices. Our scheme substantially reduces Receiver-side computation and minimises communication overhead (achieving a 10× performance improvement), while ensuring message confidentiality and non-malleability, thereby addressing key limitations of many existing OT constructions. These design choices make I-(OT )2 particularly suited for contexts in which the number of required OTs is limited, and setup costs of extension protocols cannot be effectively amortised, favouring direct and lightweight base OT solutions. We show the practical feasibility of I-(OT )2 through an open-source proof-of-concept implementation evaluated on both desktop- and IoT-like settings. The results show extremely low receiver-side online computational cost, with execution times as low as 39.90 µs for 128-bit security (3072-bit RSA modulus). These findings confirm that I-(OT )2 is well-suited for real-world deployments requiring lightweight cryptographic operations, low interaction latency, and limited client capabilities. Several directions remain open for further research. First, while I-(OT )2 targets classical security settings, it is not secure against quantum adversaries. In this direction, we plan to explore postquantum adaptations on lattice-based assumptions, such as (R-)LWE. Second, extending the protocol to support batch or adaptive OT could further reduce overhead when multiple transfers are required. Third, integrating I-(OT )2 within stronger composability frameworks, such as Universal Composability (UC) [51], would enable more comprehensive security guarantees. Finally, at the implementation level, we aim at providing a more comprehensive framework to test our solution (and the major ones in the literature) in the context of extremely resource-constrained devices, like microcontrollers without OS support.

23

References [1] M. O. Rabin, How to exchange secrets with oblivious transfer, IACR Cryptol. ePrint Arch. (1981 (2005)) 187. URL http://eprint.iacr.org/2005/187 [2] A. Rajagopalan, K. Singh, B. Jayashrri, A. E. John, Zero knowledge bi-party computation using oblivious transfers for recommender systems (Mar. 2024). doi:10.21203/rs.3.rs-3228844/v5. [3] P. Schmitt, A. Edmundson, A. Mankin, N. Feamster, Oblivious DNS: practical privacy for DNS queries, Proc. Priv. Enhancing Technol. 2019 (2) (2019) 228–244. doi:10.2478/POPETS-2019-0028. [4] Z. Chen, S. Yu, M. Fan, X. Liu, R. H. Deng, Privacy-enhancing and robust backdoor defense for federated learning on heterogeneous data, IEEE Trans. Inf. Forensics Secur. 19 (2024) 693–707. doi:10.1109/TIFS.2023.3326983. [5] L. Töbke, O. Grote, A. Ahrens, A practical approach to quantum resilient cloud usage obtaining data privacy, in: 2023 International Interdisciplinary PhD Workshop (IIPhDW), IEEE, 2023, pp. 1–4. doi:10.1109/IIPhDW54739. 2023.10124397. [6] Z. G. Al-Mekhlafi, S. A. Lashari, J. M. H. Altmemi, M. A. Al-Shareeda, B. A. Mohammed, A. A. Sallam, B. A. AlQatab, M. T. Alshammari, A. M. Alayba, Oblivious transfer-based authentication and privacy-preserving protocol for 5g-enabled vehicular fog computing, IEEE Access 12 (2024) 100152–100166. doi:10.1109/ACCESS.2024.3429179. [7] W. Tzeng, Efficient 1-out-of-n oblivious transfer schemes with universally usable parameters, IEEE Trans. Computers 53 (2) (2004) 232–240. doi:10.1109/TC.2004.1261831. [8] M. Naor, B. Pinkas, Efficient oblivious transfer protocols, in: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’01, Society for Industrial and Applied Mathematics, USA, 2001, pp. 448–457. URL https://dl.acm.org/doi/10.5555/365411.365502 [9] V. Goyal, A. Jain, Z. Jin, G. Malavolta, Statistical zaps and new oblivious transfer protocols, in: A. Canteaut, Y. Ishai (Eds.), Advances in Cryptology - EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10-14, 2020, Proceedings, Part III, Vol. 12107 of Lecture Notes in Computer Science, Springer, 2020, pp. 668–699. doi:10.1007/978-3-030-45727-3_23. [10] G. Asharov, Y. Lindell, T. Schneider, M. Zohner, More efficient oblivious transfer extensions with security for malicious adversaries, in: E. Oswald, M. Fischlin (Eds.), Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I, Vol. 9056 of Lecture Notes in Computer Science, Springer, 2015, pp. 673– 701. doi:10.1007/978-3-662-46800-5_26. [11] D. Beaver, Correlated pseudorandomness and the complexity of private computations, in: G. L. Miller (Ed.), Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, ACM, 1996, pp. 479–488. doi:10.1145/237814.237996. [12] Y. Ishai, J. Kilian, K. Nissim, E. Petrank, Extending Oblivious Transfers Efficiently, Springer Berlin Heidelberg, 2003, pp. 145–161. doi:10.1007/978-3-540-45146-4_9. [13] R. Canetti, A. K. Sarkar, C. Wang, Blazing fast oblivious transfer from pseudorandomness, in: Public-Key Cryptography – PKC 2020, Springer, 2020, pp. 327–356. doi:10.1007/978-3-030-45388-6_11. [14] T. Chou, C. Orlandi, The simplest protocol for oblivious transfer, in: Progress in Cryptology – LATINCRYPT 2015, Springer International Publishing, 2015, p. 40–58. doi:10.1007/978-3-319-22174-8_3. [15] S. Even, O. Goldreich, A. Lempel, A randomized protocol for signing contracts, Commun. ACM 28 (6) (1985) 637–647. doi:10.1145/3812.3818. [16] M. Bellare, S. Micali, Non-interactive oblivious transfer and applications, in: G. Brassard (Ed.), Advances in Cryptology - CRYPTO ’89, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings, Vol. 435 of Lecture Notes in Computer Science, Springer, 1989, pp. 547–557. doi:10.1007/0-387-34805-0_48. [17] R. L. Rivest, Unconditionally secure commitment and oblivious transfer schemes using private channels and a trusted initializer (1999). URL https://people.csail.mit.edu/rivest/pubs/Riv99d.pdf [18] C. Crépeau, K. Morozov, S. Wolf, Efficient unconditional oblivious transfer from almost any noisy channel, in: C. Blundo, S. Cimato (Eds.), Security in Communication Networks, 4th International Conference, SCN 2004, Amalfi, Italy, September 8-10, 2004, Revised Selected Papers, Vol. 3352 of Lecture Notes in Computer Science, Springer, 2004, pp. 47–59. doi:10.1007/978-3-540-30598-9_4. [19] C. Peikert, V. Vaikuntanathan, B. Waters, A framework for efficient and composable oblivious transfer, in: Advances in Cryptology – CRYPTO 2008, Springer Berlin Heidelberg, 2008, pp. 554–571. doi:10.1007/978-3-540-85174-5_ 31. [20] Y. Ishai, E. Kushilevitz, R. Ostrovsky, M. Prabhakaran, A. Sahai, J. Wullschleger, Constant-rate oblivious transfer from noisy channels, in: P. Rogaway (Ed.), Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings, Vol. 6841 of Lecture Notes in Computer Science, Springer, 2011, pp. 667–684. doi:10.1007/978-3-642-22792-9_38. [21] Y. Lindell, B. Pinkas, Secure two-party computation via cut-and-choose oblivious transfer, in: Y. Ishai (Ed.), Theory of Cryptography - 8th Theory of Cryptography Conference, TCC 2011, Providence, RI, USA, March 28-30,

24

2011. Proceedings, Vol. 6597 of Lecture Notes in Computer Science, Springer, 2011, pp. 329–346. doi:10.1007/ 978-3-642-19571-6_20. [22] M. Liu, Y. Hu, Universally composable oblivious transfer from ideal lattice, Frontiers Comput. Sci. 13 (4) (2019) 879–906. doi:10.1007/S11704-018-6507-4. [23] D. Mansy, P. Rindal, Endemic oblivious transfer, in: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, CCS ’19, ACM, 2019, p. 309–326. doi:10.1145/3319535.3354210. [24] N. Döttling, S. Garg, M. Hajiabadi, D. Masny, D. Wichs, Two-round oblivious transfer from CDH or LPN, in: A. Canteaut, Y. Ishai (Eds.), Advances in Cryptology - EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10-14, 2020, Proceedings, Part II, Vol. 12106 of Lecture Notes in Computer Science, Springer, 2020, pp. 768–797. doi:10.1007/978-3-030-45724-2_ 26. [25] N. Aragon, O. Blazy, N. Fournaise, P. Gaborit, CROOT: code-based round-optimal oblivious transfer, in: P. Samarati, S. D. C. di Vimercati, M. S. Obaidat, J. Ben-Othman (Eds.), Proceedings of the 17th International Joint Conference on e-Business and Telecommunications, ICETE 2020 - Volume 2: SECRYPT, Lieusaint, Paris, France, July 8-10, 2020, ScitePress, 2020, pp. 76–85. doi:10.5220/0009776700760085. [26] Y. Lai, S. D. Galbraith, C. D. de Saint Guilhem, Compact, efficient and UC-secure isogeny-based oblivious transfer, in: A. Canteaut, F. Standaert (Eds.), Advances in Cryptology - EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17-21, 2021, Proceedings, Part I, Vol. 12696 of Lecture Notes in Computer Science, Springer, 2021, pp. 213–241. doi:10.1007/ 978-3-030-77870-5_8. [27] S. Badrinarayanan, D. Masny, P. Mukherjee, Efficient and tight oblivious transfer from PKE with tight multi-user security, in: G. Ateniese, D. Venturi (Eds.), Applied Cryptography and Network Security - 20th International Conference, ACNS 2022, Rome, Italy, June 20-23, 2022, Proceedings, Vol. 13269 of Lecture Notes in Computer Science, Springer, 2022, pp. 626–642. doi:10.1007/978-3-031-09234-3_31. [28] P. Branco, N. Döttling, A. Srinivasan, Two-round maliciously-secure oblivious transfer with optimal rate, in: M. Joye, G. Leander (Eds.), Advances in Cryptology – EUROCRYPT 2024, Springer Nature Switzerland, Cham, 2024, pp. 271–300. doi:10.1007/978-3-031-58751-1_10. [29] A. Abadi, Y. Desmedt, Supersonic OT: Fast unconditionally secure oblivious transfer, Cryptology ePrint Archive, Paper 2024/1012 (2024). URL https://eprint.iacr.org/2024/1012 [30] G. Couteau, L. Devadas, S. Devadas, A. Koch, S. Servan-Schreiber, QuietOT: Lightweight oblivious transfer with a public-key setup, in: K.-M. Chung, Y. Sasaki (Eds.), Advances in Cryptology – ASIACRYPT 2024, Springer Nature Singapore, Singapore, 2025, pp. 197–231. doi:10.1007/978-981-96-0888-1_7. [31] F. Berti, C. Hazay, I. Levi, LR-OT: leakage-resilient oblivious transfer, Cryptography and Communications 17 (5) (2025) 1191–1248. doi:10.1007/s12095-025-00824-4. [32] Y.-G. Yang, S. Qiu, Y. Chang, G.-B. Xu, D.-H. Jiang, D. Li, Quantum oblivious transfer for quantum messages, Physical Review A 112 (4) (2025) 042617. doi:10.1103/8963-6537. [33] Y.-G. Yang, S. Qiu, R.-C. Huang, Y.-C. Wang, G.-B. Xu, D.-H. Jiang, D. Li, All-or-nothing quantum oblivious transfer for unknown unitary operations, Advanced Quantum Technologies 8 (11) (2025) e00511. doi:10.1002/ qute.202500511. [34] A. Abadi, Y. Desmedt, Oblivis: A framework for delegated and efficient oblivious transfer, to appear at PETS 2026 (2026). arXiv:2603.14492, doi:10.48550/arXiv.2603.14492. [35] V. K. Yadav, N. Andola, S. Verma, S. Venkatesan, A survey of oblivious transfer protocol, ACM Comput. Surv. 54 (10s) (Sep. 2022). doi:10.1145/3503045. [36] M. Naor, B. Pinkas, Oblivious transfer and polynomial evaluation, in: Proceedings of the thirty-first annual ACM symposium on Theory of Computing, STOC99, ACM, 1999, p. 245–254. doi:10.1145/301250.301312. [37] G. Di Crescenzo, T. Malkin, R. Ostrovsky, Single database private information retrieval implies oblivious transfer, in: Advances in Cryptology – EUROCRYPT 2000, Springer Berlin Heidelberg, 2000, pp. 122–138. doi:10.1007/ 3-540-45539-6_10. [38] T. Chou, C. Orlandi, The simplest protocol for oblivious transfer, Cryptology ePrint Archive, Paper 2015/267 (rev 2018). URL https://eprint.iacr.org/2015/267 [39] Z. A. Genç, V. Iovino, A. Rial, “the simplest protocol for oblivious transfer” revisited, Inf. Process. Lett. 161 (2020) 105975. doi:10.1016/J.IPL.2020.105975. [40] S. Sarkar, V. Srivastava, T. Mohanty, S. K. Debnath, S. Mesnager, An efficient quantum oblivious transfer protocol, Cluster Computing 27 (10) (2024) 14037–14048. doi:10.1007/s10586-024-04642-w. [41] X. Zhang, C. Wei, S. Qin, F. Gao, Q. Wen, Practical efficient 1-out-of-n quantum oblivious transfer protocol, Quantum Inf. Process. 22 (2) (2023) 99. doi:10.1007/S11128-022-03817-X. [42] A. Gan, S. Yuki, T. Rogers, Z. Ghodsi, Cuot: Accelerating oblivious transfer on gpus for privacy-preserving computation, in: 2025 IEEE International Symposium on Hardware Oriented Security and Trust (HOST), IEEE, 2025, pp. 300–311. doi:10.1109/HOST64725.2025.11050054.

25

[43] C. Lin, K. Yang, T. Xu, L. Liang, Y. Wang, Z. Chen, R. Wang, M. Gao, M. Li, Ironman: Accelerating oblivious transfer extension for privacy-preserving AI with near-memory processing, in: Proceedings of the 58th IEEE/ACM International Symposium on Microarchitecture, 2025, pp. 354–368. doi:10.1145/3725843.3756025. [44] A. Abadi, Y. Desmedt, Scalable post-quantum oblivious transfers for resource-constrained receivers, IACR Cryptol. ePrint Arch. (2025) 36. URL https://eprint.iacr.org/2025/036 [45] E. Barker, Recommendation for key management:: part 1 - general, Tech. Rep. 800-57 Pt1, National Institute of Standards and Technology (U.S.), Gaithersburg, MD (2020). doi:10.6028/nist.sp.800-57pt1r5. [46] National Institute of Standards and Technology (U.S.), SHA-3 standard: permutation-based hash and extendableoutput functions, Tech. Rep. 202, National Institute of Standards and Technology (U.S.), Gaithersburg, MD (Aug. 2015). doi:10.6028/nist.fips.202. [47] I. McQuoid, M. Rosulek, L. Roy, Batching base oblivious transfers, in: M. Tibouchi, H. Wang (Eds.), Advances in Cryptology - ASIACRYPT 2021 - 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6-10, 2021, Proceedings, Part III, Vol. 13092 of Lecture Notes in Computer Science, Springer, 2021, pp. 281–310. doi:10.1007/978-3-030-92078-4_10. [48] M. Bellare, A. Desai, D. Pointcheval, P. Rogaway, Relations among notions of security for public-key encryption schemes, in: Advances in Cryptology — CRYPTO ’98, Springer Berlin Heidelberg, 1998, pp. 26–45. doi:10.1007/ bfb0055718. [49] R. Pass, A. Rosen, New and improved constructions of non-malleable cryptographic protocols, in: H. N. Gabow, R. Fagin (Eds.), Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, ACM, 2005, pp. 533–542. doi:10.1145/1060590.1060670. [50] R. J. Davis, R. Zuccherato, J. Randall, Comments on nist special publication 800-57, recommendation for key management, part 1: General, Draft comments, National Institute of Standards and Technology (NIST) (2005). URL https://csrc.nist.gov/files/pubs/sp/800/57/pt1/final/docs/sp800-57-pt1-draft-apr2005-comments. pdf [51] R. Canetti, Universally composable security: A new paradigm for cryptographic protocols, in: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE, 2001, pp. 136–145. doi: 10.1109/SFCS.2001.959888.

Appendix A. Probabilistic and Bayesian Analysis of the Check-Congruency Game In this appendix, we present a thorough probabilistic analysis of the Check-Congruency game introduced in Figure 4 and discussed in Section 5.2. We start by reasoning on the Sender’s optimal malicious strategy and we then derive the probabilistic estimates that justify the choice of ℓ in the protocol. Finally, we conclude by presenting an alternative Bayesian formulation of the same problem that better captures the Receiver’s confidence in the test result. We recall the objective of the check congruency game being to allow the Receiver to verify whether the Sender generated a valid modulus n (with p ≡4 q ≡4 1) or not, by challenging the Sender with random values and checking the distribution of the responses. In details, during the Check-Congruency phase, the Receiver samples ℓ random values x ∈ Zn , which it then uses to challenge the Sender by sending y = −xc mod n for some random exponent c ←$ {1, 2}. The Sender is required to answer r = isQR(y), i.e. whether y is a quadratic residue modulo n or not. Observe that, when the Sender is honest (i.e. p ≡4 q ≡4 1), the response r is fully determined by the protocol semantics. Conversely, when the Sender is malicious, r is no longer deterministic and can be partially controlled. In this case, when c = 2, the value −x2 is not a quadratic residue, but the Sender can attempt to deceive the Receiver by claiming it is. However, when c = 1, the value −x is a quadratic residue with probability 1/4 and the Sender cannot control the actual probability. Let then p1 , p2 ∈ [0, 1] be the two probabilities pc = P[r = T | c] that the Sender produces in response to the Receiver’s challenge. The Receiver expects p1 = 1/4 (the natural probability that a random element of Zn is a quadratic residue) and p2 = 1 (since the Sender knows the factorisation of n, it can always identify −x2 as a quadratic residue). The Sender, on the other hand, wants to deceive the Receiver by making p1 as close as possible to 1/4 while also making p2 as close as possible to 1. We now characterise the optimal strategy a malicious Sender can adopt, and the resulting values of p1 , p2 that the Receiver observes.

26

A.1. Best malicious sender strategy. From a malicious Sender perspective (meaning −1 ̸∈ QR) upon receiving y = −xc , we have that P[y ∈ QR | c = 1] = 1/4

P[y ̸∈ QR | c = 1] = 3/4

,

and P[y ∈ QR | c = 2] = 0

,

P[y ̸∈ QR | c = 2] = 1 .

P[y ∈ QR] = 1/8

,

P[y ̸∈ QR] = 7/8 .

Hence As a consequence, it is straightforward to see that P[c = 1 | y ∈ QR] = 1

P[c = 2 | y ∈ QR] = 0

,

while, by applying Bayes theorem, we have 3 4 , P[c = 2 | y ̸∈ QR] = . 7 7 It follows that responding T with probability ρ when y ̸∈ QR leads to a disclosure of the malevolent 4 behaviour with probability 1 − ρ /7ℓ . It is easy to compute that, even for ρ ∼ 0.95, the disclosure probability is higher than 1/2 as ℓ ≥ 24, and for ρ > .95 there is no sensible gain in risking the disclosure (later we estimate reasonable values of ℓ ∼ 215); hence the best strategy consists in setting ρ = 1, i.e. responding T whenever y ̸∈ QR. It follows that, whenever y ∈ QR, since c = 1 must hold, the response can safely be F. This leads to the best strategy being ( F if y ∈ QR r= , T otherwise P[c = 1 | y ̸∈ QR] =

which yields p2 = P[r = T | c = 2] = 1 and p1 = P[r = T | c = 1] = 3/4, that is, R being distributed like a Bernoulli(3/4) instead of the Bernoulli(1/4) expected from an honest Sender. In what follows, we hence focus on the case c = 1, which is the only one that allows the Receiver to discriminate between honest and malicious Senders, since for c = 0 the sender will always return a correct answer. In particular, this can be done by checking the distribution of the responses against Bernoulli(1/4) = D0 vs. Bernoulli(3/4) = D1 . As usual, given l consecutive i.i.d. samples, let Sl be the number of positive ones sampled from the chosen distribution D. Do note that here l do represent the number of √ samples picked with c = 1 and, since c is uniformly sampled in {0, 1}, then we typically require ℓ ∼ 2 2 · l samples (it is easy to see √ that at least l samples are picked with c = 1 if ℓ = 2 2 · l when l > 40). Then, we have that    k  l−k 3 l 1 P[Sl = k | D0 ] = 4 4 k and P[Sl = k | D1 ] =

   k  l−k l 3 1 k 4 4

2 l 3l which can be approximated p as a normal distribution N (µ, σ ) centred at µ0 = /4 (resp. µ1 = /4) with standard deviation σ = 3l/16 for large enough l; a depiction of the corresponding PDFs for l = 30 and l = 75 can be found in Figure 7 as a reference. It can be noted that the two PDFs are centred in l/4 and 3l/4 respectively, and are hence symmetrical one to the other w.r.t. l/2, suggesting that whenever Sl > l/2, then samples are drawn from D1 with higher probability. In particular, we have that

P[Sl > l/2 | D0 ] =

l X k=l/2+1

P[Sl = k | D0 ]

27

Fig. 7. Probability Density Functions (PDFs) of elements sampled from the expected distribution D0 (blue circles) and produced according to the best malicious strategy D1 (orange stars) when the samples are (left panel) k = 30 and (right panel) k = 75. The normal approximations of the two Bernoulli are represented for comparison as full lines. Do notice that y-scales are different being the domains different in size. or, by adopting the normal approximation, that " # " √ #   l/2 − µ l/4 S − µ l l P[Sl > l/2 | D0 ] = P > =P Z> p =P Z> √ 3l/16 σ σ 3 with Z being the standard normal distribution N (0, 1). Hence, since P[Z ≥ 5] ≈ 2.87 × 10−7 , we √ √ can confidently say that P[Sl > l/2 | D0 ] is negligible for l/ 3 ≥ 5, i.e. l ≥ 75. Clearly, the same bound can also be obtained for the reverse proposition, meaning that P[Sl < l/2 | D1 ] is negligible when l ≥ 75. Collecting the two properties together, we can claim that “the probability of the Sender deceiving the Receiver with confidence greater√than 2.87 × 10−7 is less than 2.87 × 10−7 after l = 75 experiments”. It follows that choosing ℓ = 2 · 2 · l ∼ 215 is way more than sufficient for the Receiver to be sure that the Sender is behaving honestly, see also Figure 8. A.2. Bayesian approach to the effective size of the test set. Alongside the classical probabilistic discussion, which involves the normal approximation of the Bernoulli and provides us with a suitable value for ℓ, we can also discuss the confidence of any specific experiment result by adopting a Bayesian approach. In particular, this gives us the opportunity to introduce a novel parameter δ ∈ [0, 1] representing the Receiver’s distrust in the Sender’s behaviour, where δ = 0 implies the Sender is always trusted (honest-but-curious), δ = 1 identifies a malevolent Sender who is always trying to cheat on the protocol, and δ = 1/2 represents the unbiased situation where no a priori information is available. In the context of a Bayesian approach, we can shape such a value δ as the probability that D1 was chosen rather than D0 , the so-called prior distribution, i.e. P[D0 ] = 1 − δ

,

P[D1 ] = δ .

Given a specific experiment producing k true responses out of l tests, we can express the likelihood ratio of the Sender behaving maliciously as
3
k 1
l−k  3 k  1 l−k  l−k l P[Sl = k | D1 ] 1 k k 4 4 4 4 =

k
l−k = 1 = (3) = 32k−l Λl (k) = 3 l 1 3 P[Sl = k | D0 ] 3 4 4 k

4

4

where it is interesting to notice that the log-likelihood ratio (LLR) is linear llrl (k) = log(Λl (k)) = log(P[Sl = k | D1 ]) − log(P[Sl = k | D0 ]) = (2Sl − k) log 3 .

28

Fig. 8. Probability of exceeding a given number x of positive responses for the two distributions D0 and D1 from Figure 7 when the number of samples is set to (left panel) k = 30 and (right panel) k = 50. D1 (orange star) probabilities are modelled with the Cumulative Distribution Function (CDF), while values from D0 (blue circles) are obtained from the survival function or Complementary Cumulative Distribution Function (CCDF). Normal approximations are represented as full lines for comparison. Do notice that perceivable (yet infinitesimal) numerical differences occur between exact and approximate values due to the inherent approximation of D0 and D1 being defined on discrete sets of values x.

Fig. 9. Bayesian analysis of the probability that the Sender is badly behaving w.r.t. the number of t samples obtained in R (top panels) and corresponding uncertainty (bottom panels). Results are presented for three values of Receiver distrust δ ∈ {1/100, 1/2, 3/4} (from left to right). Do notice that the x-axis is 0-1 normalised to make plots at the varying of l comparable and limited to [1/5, 4/5] for readability. Distribution means (1/2 ± 1/4) are highlighted by vertical dashed lines. Then, the probability that the Sender is behaving maliciously given the result of an experiment is: P[Sl = k | D1 ] · P[D1 ] P[Sl = k | D1 ] · δ = P[D1 |Sl = k] = P[Sl = k] P[Sl = k | D1 ] · δ + P[Sl = k | D0 ] · (1 − δ) Λl (k) · δ 1 1 = = = (1−δ) (1−δ) Λl (k) · δ + (1 − δ) 1+ Λl (k)−1 1+ 3l−2k δ

δ

29

and analogously P[D0 | Sl = k] =

1 1 = δ δ 1 + 1−δ Λl (k) 1 + 1−δ 32k−l

δ where we recall that 1−δ 32k−l is also referred to as posterior odds. Finally, we can evaluate the uncertainty in the decision as the Bayesian decision error, i.e. Perr = min(P[D1 |Sl = k], P[D0 |Sl = k]), which evaluates to ! 1 1 , Perr = min l−2k 1 + δ 32k−l 1 + (1−δ) 1−δ δ 3

Figure 9 reports the P[D1 |Sl = k] and the corresponding Perr at the varying of the sample set size |R| = l ∈ {10, 20, 30, 45, 75}. Results are presented for three example values of trustworthiness: strong Sender trust (δ = 1/100), no prior assumption (δ = 1/2), and small Sender distrust (δ = 3/4). In particular, do notice that, being the distribution discrete, then Perr does not always reach the value of 1/2 as theoretically expected since it can happen that theoretical maximal uncertainty is located within two possible k values: it is the case, e.g., when l is odd and δ = 1/2, as we can see for l = 75; here the maximum is located in l/2 = 37.5, i.e.k/l = 1/2, which is not an actual achievable number of t responses. Appendix B. Security Games B.1. Choice Obliviousness Game. The Choice Obliviousness Game between a Receiver challenger C and a (possibly unbounded) Sender adversary A is defined as follows. Setup: The challenger generates an RSA modulus n = pq, where p ≡ q ≡ 1 (mod 4), and sends n to A. Query: A may request polynomially many honest executions of the protocol, obtaining the corresponding public values r generated according to honest Receiver behaviour. These queries model full protocol transcripts available to the Sender. Challenge: C samples a value k ←$ Zn/2 and a challenge bit b ←$ {0, 1} uniformly at random, and computes r = (−1)b · k 2 mod n . The value r is given to A. Query: A second query phase is run as above, with fresh independent protocol executions. Guess: The adversary A outputs a bit b′ ∈ {0, 1}. Winning condition: The adversary wins if b′ = b. The advantage of A in the Choice Obliviousness Game is defined as ′ 1 Advchoice I-(OT )2 (A) = Pr[b = b] − 2 .

Theorem 1 (Perfect Choice Obliviousness). For any (possibly unbounded) Sender adversary A, the advantage in the Choice Obliviousness Game is zero, i.e., Advchoice I-(OT )2 (A) = 0 . Proof. We begin the proof, noticing that the query phases provide the adversary only with independent samples drawn from the same distribution as the challenge value r, and therefore do not affect the indistinguishability argument below. For uniformly random k ←$ Zn/2 , the distributions of k 2 and −k 2 modulo n are identical. Indeed, since p ≡ q ≡ 1 (mod 4), there exists I ∈ Zn such that I 2 ≡ −1 (mod n), and thus (−1) · k 2 ≡ (I · k)2

(mod n) .

As multiplication by I is a bijection over Zn , it follows that the random variables k 2 mod n and (I · k)2 mod n have identical distributions when k is sampled uniformly from Zn/2 . Therefore, the challenge value r is identically distributed for b = 0 and b = 1. It follows that Pr[b′ = b] = 12 for any adversary A, and hence Advchoice I-(OT )2 (A) = 0 .

30

□ B.2. Receiver Message Obliviousness Game. Let A be a PPT honest-but-curious Receiver and let C be a challenger playing the role of the Sender. We define the following game. Init: C generates and publishes the modulus n = pq, where p ≡ q ≡ 1 (mod 4). Setup: C fixes the public description of the keyed KDF F◦ (·) and the hash function H(·). Query1 : A may adaptively request polynomially many honest executions of the protocol (under fresh s values) by specifying arbitrary message pairs (M0 , M1 ). These queries model full protocol transcripts available to an honest-but-curious Receiver. Challenge: A outputs two challenge messages (M0 , M1 ) of equal length, samples a fresh session key k ∈ Zn , selects a choice bit b ∈ {0, 1} (as it would regularly do it in the protocol), and sends r = (−1)b k 2 mod n to C. The challenger samples a fresh KDF key s⋆ ←$ Zn and sends it to A. C then computes the (j) (j) (j) four square roots {ki } of ±r, derives the corresponding message keys Ki = Fs⋆ (ki ), and (j) forms the digests {di } according to the protocol. (j) For each pair (i, j), the challenger samples an independent bit βi ←$ {0, 1} and replaces (j) (j) Ki with a random value whenever βi = 0, consequently creating and returning compliant or random cyphertexts to A. Query2 : A second query phase is run as before, under different fresh secrets s ∈ Zn . (j) Guess: A outputs guesses β̄i ∈ {0, 1} for all (i, j) ̸= (b, ĵ) and wins if h i 1 (j) (j) Pr β̄i = βi ≥ + ε(κ) for some (i, j) ̸= (b, ĵ), 2 where ε(κ) is non-negligible. Theorem 2 (Receiver Message Security). Assume that factoring n = pq is hard and that the keyed KDF Fs (·) and the Hash function H(·) are secure. Then, for any PPT honest-but-curious Receiver A, its advantage is defined as 1 (j) (j) Advmessage max Pr[β̄i = βi ] − . I-(OT )2 (A) = 2 (i,j)̸=(b,ĵ) We say that A wins if Advmessage I-(OT )2 (A) ≥ ε(κ) for some non-negligible ε. Proof. We first observe that the adversary’s access to the two query phases does not increase its distinguishing power on the challenge execution. Each query execution is performed under a freshly sampled and independent KDF key s, and the Receiver learns at most one square root per execution. Under the hardness of factoring n, knowledge of a square root in one session does not enable computing any other square roots of ±r in that session, nor does it provide information about roots arising in independent sessions. Moreover, by the security of the keyed KDF Fs (·), for any query execution the distribution of ciphertexts corresponding to unknown roots is computationally indistinguishable from encryptions under random keys. Therefore, the entire view of A in both query phases can be simulated without knowledge of any additional square roots, and without affecting A’s advantage in the challenge phase. Then, assume for contradiction that there exists a PPT adversary A and a non-negligible function ε(κ) such that Advmessage I-(OT )2 (A) ≥ ε(κ). Then there exists (at least) an index (i⋆ , j ⋆ ) ̸= (b, ĵ) such that A distinguishes whether the ciphertext is real or random with non-negligible advantage ε(κ). Under the security of the keyed KDF Fs⋆ (·), the output Fs⋆ (x) is computationally indistinguishable from random for any unknown input x. Therefore, distinguishing a real key (j ⋆ ) (j ⋆ ) Ki⋆ = Fs⋆ (ki⋆ )

31 (j ⋆ )

from random with non-negligible advantage implies recovering information about ki⋆ . (j ⋆ ) However, for any (i⋆ , j ⋆ ) ̸= (b, ĵ), the value ki⋆ is a square root of ±r distinct from the root k held by the Receiver. Computing such a root from r without knowing the factorisation of n is equivalent to factoring n = pq, which is assumed to be computationally infeasible. (j) (j) Additionally, the digests di = H(ki ) provided to A serve solely as identifiers and do not allow enforcing correlation tests under the security assumptions of the hash function: by the preimage(j) resistance property of H, they do not allow the Receiver to derive any unknown square roots ki or correlate them with other roots, and therefore leak no information beyond what is already implied by r (i.e. check whether a candidate c is a root, provided A can always verify it by evaluating c2 =(?) r). (j ⋆ )

Consequently, A cannot distinguish Fs⋆ (ki⋆ ) from a uniformly random value without either breaking the security of the KDF or factoring n, both of which contradict our assumptions. It follows that, for all (i, j) ̸= (b, ĵ), h i 1 (j) (j) ≤ Negl(κ), Pr β̄i = βi − 2 and hence Advmessage I-(OT )2 (A) ≤ Negl(κ). Since the above argument holds independently of the number and adaptivity of the query executions, it applies equally in the presence of both pre- and post-challenge queries. □