Geoffroy Couteau
email: couteau@irif.fr

Bill Roscoe
email: awroscoe@gmail.com

Peter Ryan
email: peter.ryan@uni.lu

Partially-Fair Computation from Timed-Release Encryption and Oblivious Transfer

Keywords: Fair exchange, partial fairness, timed-release encryption

We describe a new protocol to achieve two party ε-fair exchange: at any point in the unfolding of the protocol the difference in the probabilities of the parties having acquired the desired term is bounded by a value ε that can be made as small as necessary. Our construction uses oblivious transfer and sidesteps previous impossibility results by using a timed-release encryption, that releases its contents only after some lower bounded time. We show that our protocol can be easily generalized to an ε-fair two-party protocol for all functionalities. To our knowledge, this is the first protocol to truly achieve ε-fairness for all functionalities. All previous constructions achieving some form of fairness for all functionalities (without relying on a trusted third party) had a strong limitation: the fairness guarantee was only guaranteed to hold if the honest parties are at least as powerful as the corrupted parties and invest a similar amount of resources in the protocol, an assumption which is often not realistic. Our construction does not have this limitation: our protocol provides a clear upper bound on the running time of all parties, and partial fairness holds even if the corrupted parties have much more time or computational power than the honest parties. Interestingly, this shows that a minimal use of timed-release encryption suffices to circumvent an impossibility result of Katz and Gordon regarding ε-fair computation for all functionalities, without having to make the (unrealistic) assumption that the honest parties are as computationally powerful as the corrupted parties -this assumption was previously believed to be unavoidable in order to overcome this impossibility result. We present detailed security proofs of the new construction, which are non-trivial and form the core technical contribution of this work.

Introduction

Secure computation allows parties to perform a joint computation on their private data, without compromising their security. An important security property of secure computation protocols is known as fairness: intuitively, it states that either all participants to the protocol should receive the output, or none should. In a wide variety of real-world situations, ensuring that no participant can get an unfair advantage by learning the output early is highly desirable. Unfortunately, a well-known result of Cleve [START_REF] Cleve | Limits on the security of coin flips when half the processors are faulty (extended abstract)[END_REF] established that fairness is impossible to achieve in its full generality -in fact, it is already impossible to achieve for very simple functionality such as coin tossing, or exchange of values. As a consequence of this impossibility result, a large body of work has been devoted to developing mechanisms to achieve some relaxed notion of fairness. We overview the main existing approaches below, and outline their advantages and drawbacks.

Relaxed Notions of Fairness

Some lines of research overcome Cleve's impossibility result by relying to some extent on a trusted third party [START_REF] Avoine | Optimistic fair exchange based on publicly verifiable secret sharing[END_REF][START_REF] Cachin | Optimistic fair secure computation[END_REF][START_REF] Dodis | Optimistic fair exchange in a multi-user setting[END_REF], non-standard communication models [START_REF] Lepinski | Completely fair sfe and coalition-safe cheap talk[END_REF], or by punishing unfair behaviour through smart contracts [START_REF] Kumaresan | How to use bitcoin to incentivize correct computations[END_REF][START_REF] Kumaresan | How to use bitcoin to play decentralized poker[END_REF][START_REF] Küpçü | Usable optimistic fair exchange[END_REF][START_REF] Andrew | Legally-enforceable fairness in secure two-party computation[END_REF]. Another approach works by gradually increasing the parties' confidence in the output [START_REF] Beaver | Multiparty computation with faulty majority[END_REF][START_REF] Goldwasser | Fair computation of general functions in presence of immoral majority[END_REF][START_REF] Luby | How to simultaneously exchange a secret bit by flipping a symmetrically-biased coin[END_REF]; however, this approach is inherently limited to protocols with a single-bit output, and where the output is the same for all parties; furthermore, they allow the adversary to significantly bias the output of the honest parties by aborting early.

Fairness From Gradual Weakening of Encryption. Most closely related to our work is the following important line of research in fairness, which seeks to achieve a relaxed notion of fairness where if the adversary can recover the output in time T , then the honest parties can recover it as well within time s • T , where s is some slackness parameter [START_REF] Blum | How to exchange (secret) keys (extended abstract)[END_REF][START_REF] Boneh | Timed commitments[END_REF][START_REF] Damgård | Practical and provably secure release of a secret and exchange of signatures[END_REF][START_REF] Even | A randomized protocol for signing contracts[END_REF][START_REF] Galil | Cryptographic computation: Secure faut-tolerant protocols and the public-key model[END_REF][START_REF] Pinkas | Fair secure two-party computation[END_REF]. Therefore, this approach guarantees fairness, as long as all honest parties are at least as computationally powerful as the corrupted parties. At an intuitive level, this approach will proceed by letting the parties jointly compute an encryption of the output, and gradually "weakening" its security in rounds, until its content can be recovered by brute-force. This approach, however, has several downsides: when an adversary aborts early, the protocol does not specify how a party should decide whether to invest the necessary computational effort to recover the output. More generally, the protocol does not provide any a priori (polynomial) upper-bound on the computational effort that honest parties might have to invest in the protocol: if any such precise bound is given, the adversary is guaranteed to break the fairness property by investing more resources than specified by this bound. In any real-world situation, this mean that the protocol will only satisfy fairness under the unrealistic assumption that the corrupted parties will never be able to spend more computational resources than the honest parties.

An alternative to all of the above is the notion of partial fairness. Since it will be the main focus of our work, we elaborate on it in the next section.

Partial Fairness

The notion of partial fairness was introduced by Katz and Gordon in [START_REF] Gordon | Partial fairness in secure two-party computation[END_REF], and was recently re-discovered by Roscoe and Ryan in a different context [START_REF] Roscoe | Auditable PAKEs: Approaching fair exchange without a TTP[END_REF], where it was called stochastic fairness. Partial fairness relaxes the standard fairness notion to hold except with some non-negligible probability, which can be made smaller than any given (inverse polynomial) threshold. In an informal sense, partial fairness corresponds to a best-possible notion of fairness, in settings where one does not want to rely on trusted parties, or to assume that the computational power of honest parties will be as high as those of malicious parties. An important feature of the notion partial fairness is that it fits nicely in the standard simulation paradigm of secure computation, allowing to provide formal security proofs. Indeed, the simulation paradigm established the security of a protocol by exhibiting a simulator which is given access to an ideal functionality, and whose behavior cannot be distinguished from that of a honest user. Now, proving that a protocol satisfies 1/p-partial fairness (for some polynomial p) is done by exhibiting a simulator which is given access to a perfectly fair functionality, and whose behavior cannot be distinguished from that of a honest user except with 1/p probability.

In [START_REF] Gordon | Partial fairness in secure two-party computation[END_REF], Katz and Gordon exhibit a generic partially-fair secure computation protocol, provided that either one of the inputs or one of the outputs comes from a polynomial-size domain. While this already considerably broadens the type of functionalities that can be implemented compared to the setting of full fairness, this remains a rather strong limitation. It prevents, for example, to evaluate functionalities as simple and useful as fair exchange of data, unless one of the data comes from a very small domain. Unfortunately, Katz and Gordon showed that this limitation is inherent [18, Section 4], by proving that it is already impossible to securely execute (with partial fairness) a form of authenticated fair exchange (where two parties wish to exchange values if and only if they have been correctly authenticated via some one-time MAC scheme) when the values come from a large domain. Katz and Gordon further mention that their setting requires a polynomial upper-bound on the running time of the parties, which is why alternative fairness notions (based on gradually weakening a commitment to the output until it can be opened by brute-force) escape their impossibility result.

Context and Motivation

The starting point of our work, and its initial motivation, stems from considerations regarding the security some existing password-authenticated key-exchange (PAKE, [START_REF] Bellovin | Encrypted key exchange: Password-based protocols secure against dictionary attacks[END_REF]) protocols against a form of online attacks which are not captured by the standard security model for PAKE. A PAKE is an interactive protocol between a server and a user, both holding a (low-entropy) password, who wish to securely generate a shared secret-key provided that their passwords are equal. The protocol should resist offline dictionary attacks: an adversary should not be able, given only the transcript of a PAKE execution, to try out many passwords against this transcript. In the past decade, numerous PAKE protocols have been proposed, satisfying this natural security notion, under a variety of cryptographic assumptions [4-6, 15, 20].

However, the standard security model for PAKE does not preclude the following simple online attack: an adversary could potentially attempt to guess the password, learn from the protocol whether his guess was successful or not, and then abort the protocol before the server gets to know that the user tried to execute the PAKE with an incorrect password. Since network failures are relatively common, the server cannot distinguish in this scenario a malicious attempt at guessing the password from a network failure for an honest user. Because of this, the adversary could potentially repeat this attack several times before the repeated failures become suspicious. This form of online attack was first identified and studied by Ryan and Roscoe in [START_REF] Roscoe | Auditable PAKEs: Approaching fair exchange without a TTP[END_REF]. This is not a purely theoretical concern: studies indicate that human-generated passwords have less that 7 bits of min-entropy on average [START_REF] Jaeger | Honey encryption beyond message recovery security[END_REF]. Even if the servers enforce the use of strong passwords, with (say) 20 bits of entropy, and assuming a medium-scale deployement of a PAKE system with 2 10 online services protected by the system, and an adversary allowed to make 2 10 online guesses with the above attack (possibly spanning over a reasonable period of time) would break into one of the services with good probability. To mitigate this attack, [START_REF] Roscoe | Auditable PAKEs: Approaching fair exchange without a TTP[END_REF] suggest to rely on a fair exchange protocol, and show that such a protocol can be used to ensure that the adversary cannot learn whether his guess was correct without the server learning it as well. Since fair exchange protocols are impossible in general, [START_REF] Roscoe | Auditable PAKEs: Approaching fair exchange without a TTP[END_REF] suggests to rely on a protocol with partial fairness (or stochastic fairness, using their terminology). This way, any adversary attempting to mount an online guessing attack has a high (yet not overwhelming) probability of getting caught doing so.

Our Contribution

In this work, we develop a new method to construct protocols with partial fairness. Inspired by the above scenario, we introduce a new partially-fair exchange protocol (i.e., a (p + O(1))-round two-party protocol which allows for exchange of values, and satisfies 1/p-fairness in the framework of [START_REF] Gordon | Partial fairness in secure two-party computation[END_REF]), and seek to obtain a protocol as concretely efficient as possible. Afterward, we observe that our protocol extends naturally to an authenticated partially fair exchange protocol, and show that this naturally gives rise to a secure computation protocol with partial fairness for all functionalities. Because of the impossibility result of Katz and Gordon, this can provably not be achieved directly within the standard model of computation, and all previous works aiming at fairness for all functionalities could only achieve a very relaxed notion of partial fairness (either using trusted parties, or assuming that the honest parties are computationally more powerful than corrupted parties). We stress that this is the case even for protocol that used tools such as gradual weakening of encryptions, or time-lock puzzles -even though the use of these primitives does, in principle, escape the impossibility result of Katz and Gordon, since they do not fit directly into the standard model of computation.

Escaping the Impossibility Result. To escape the impossibility result of Katz and Gordon, we rely on a timed-release encryption scheme, a primitive introduced in [START_REF] Ronald L Rivest | Time-lock puzzles and timedrelease crypto[END_REF] which allows to encrypt a message such that it can only be recovered after some time period has elapsed. A timed-release encryption scheme is simply a public-key version of the most well-known notion of timelock puzzles; this is similar to the primitive employed in [START_REF] Blum | How to exchange (secret) keys (extended abstract)[END_REF][START_REF] Boneh | Timed commitments[END_REF][START_REF] Damgård | Practical and provably secure release of a secret and exchange of signatures[END_REF][START_REF] Even | A randomized protocol for signing contracts[END_REF][START_REF] Galil | Cryptographic computation: Secure faut-tolerant protocols and the public-key model[END_REF][START_REF] Pinkas | Fair secure two-party computation[END_REF], and can be constructed under the assumption that some tasks inherently require a long sequential computation -the most classical construction relying on the hardness of parallelizing squaring modulo an RSA modulus [START_REF] Ronald L Rivest | Time-lock puzzles and timedrelease crypto[END_REF].

However, there is an important difference between our work and all previous works on fairness which relied on time-lock puzzle, timed-release encryption, or gradual weakening of secrets: in all these works, the use of these primitives only guarantees fairness when the honest parties are always able to invest more computational resources than the corrupted parties, a scenario which we already said is unrealistic. In contrast, our protocol truly achieves partial fairness, even if the corrupted parties are allowed a much longer running time than the honest parties; in fact, our protocol does even guarantee a strict polynomial upper-bound on the running time of all parties, hence does not suffer from the important downside of these works. We note that this is a surprising result, as the absence of a strict polynomial upper bound on the running time of the honest parties was pointed out in [START_REF] Gordon | Partial fairness in secure two-party computation[END_REF] as the reason why fair exchange protocols could escape their impossibility result; our result shows that this is not the case, and that a minimal use of a primitive in the spirit of time-lock puzzles already suffices to overcome this barrier.

In addition to timed-release encryption, we assume only standard generic cryptographic primitives, such as commitment schemes and oblivious transfers. To optimize for concrete efficiency, we do not employ zero-knowledge proofs and do not target security against malicious adversaries; rather, we prove that our protocol is directly secure against covert adversaries [START_REF] Aumann | Security against covert adversaries: Efficient protocols for realistic adversaries[END_REF]: an adversary can deviate from the specifications of the protocol, but will be caught (with probability one) if he does so. Note that in the motivating scenario of preventing online guessing attacks on PAKEs, security against covert adversaries captures the desired security notion, since our aim is to distinguish guessing attacks from honest network failures. The security of our protocol can easily be enhanced to the malicious setting using zero-knowledge proofs.

To summarize, our main contributions are -On the practical side, a new partially fair key exchange protocol from timedrelease encryption and standard cryptographic primitives, which is formally proven secure against covert adversaries in the framework of [START_REF] Gordon | Partial fairness in secure two-party computation[END_REF]. Our protocol is concretely efficient: when instantiating the oblivious transfer with the DDH-based OT of [START_REF] Peikert | A framework for efficient and composable oblivious transfer[END_REF], the protocol communicates only 4p log p+O(1) group elements in p + O(1) rounds to reach 1/p-fairness. This protocol can be used to mitigate the risk of online guessing attacks on password-authenticated key exchange protocols. -On the theoretical side, a generic secure two-party computation protocol for all polynomial-size circuits (with input and output domain of arbitrary size) which achieves 1/p-fairness in p + O(1) rounds using Õ(λp) + O(c) bits of communication (where λ is a security parameter, and c is the communication of a protocol computing the circuit and satisfying security with aborts), which is (to our knowledge) the very first protocol to achieve partial fairness for all functionalities (or even for the fair exchange functionalities). Our protocol makes a minimal use of a timed-release encryption scheme (which seems unavoidable by the impossibility result of [START_REF] Gordon | Partial fairness in secure two-party computation[END_REF]), where each party sends a single timed-release encryption right before the output phase, and must complete the phase before the time bound elapses. In particular, our protocol is the first of its kind to guarantee a polynomial upper-bound on the running time of all parties, for arbitrary functionalities.

In particular, this means that the fairness guarantee that we obtain does also extend to the (very realistic) scenarios where the adversaries might be more powerful than the honest parties; to our knowledge, every previous paper achieving some form of fairness for all functionalities (without the help of a trusted third party, or a smart contracts) could not guarantee this highly desirable property. In addition, our protocol is not purely of theoretical interest: it is practical, and its building blocks can be instantiated efficiently from a variety of standard cryptographic assumptions.

Our Method

Our starting point is an idea sketched in [START_REF] Roscoe | Auditable PAKEs: Approaching fair exchange without a TTP[END_REF], which achieves partial fairness by creating a randomly permuted size-p list of masked values, one of them being the target value to be exchanged, and the remaining ones being dummy values. Each list of masked values is permuted by both parties, so that the actual permutation remains unknown to each party. Before the exchange phase, the parties encrypt a string indicating their choices of permutations (for both lists), as well as the mask used to hide the values, using a timed-release encryption scheme which ensures that the encrypted values remain hidden for a time T . Afterward, the parties simply exchange the permuted values one-by-one, using p rounds of interaction, so that the last value of the list is exchanged before time T elapse. Intuitively, partial fairness stems from the fact that if the adversary aborts at any point in the computation, he does not know yet whether his opponent already sent him the right masked value (he will only discover this after time T has elapsed). Therefore, the best advantage he can obtain over his opponent is by aborting right after he received any given message, which gives him a probability roughly 1/p of discovering later on that he had already received the masked output, while his opponent had not.

The protocol developed in [START_REF] Roscoe | Auditable PAKEs: Approaching fair exchange without a TTP[END_REF], however, relies on an ad-hoc construction using discrete-log-hard groups; more importantly, it entirely lacks any security analysis. We therefore first develop and elegant partially-fair exchange protocol, inspired by the approach of [START_REF] Roscoe | Auditable PAKEs: Approaching fair exchange without a TTP[END_REF], relying on a (simulatable) oblivious transfer protocol, a timed-release encryption scheme, and a commitment scheme. Afterward, we provide a detailed security analysis of our protocol in the framework of [START_REF] Gordon | Partial fairness in secure two-party computation[END_REF], and show that it 1/p-realizes a perfect fair exchange functionality in the presence of covert adversaries. While the security of the protocol is relatively intuitive, the proof turns out to be non-trivial, and is the main technical contribution of this work. To establish the existence of an efficient simulator, we must rely on cryptographic primitives with strong simulation guarantees; in particular, we need a simulatable oblivious transfer (as defined in [START_REF] Peikert | A framework for efficient and composable oblivious transfer[END_REF]), together with an equivocable trapdoor commitment: in addition to the standard hiding and binding properties, we require that with an appropriate trapdoor, any commitment can be opened to an arbitrary value; yet, at the same time, the commitment must be weakly extractable, meaning that with another appropriate trapdoor, an extraction algorithm can recover a message m such that no PPT adversary (without the equivocation trapdoor) can open this commitment to a value m = m. The proof requires carefully tracking the advantage of a polynomial time adversary in distinguishing the real protocol from the simulated one, where we must show that the (non-negligible) distinguishing advantage can be broken in two parts, one corresponding to a malicious behavior of a non-aborting adversary (which we show can be detected with overwhelming probability, hence is acceptable in the setting of security against covert adversaries), and another quantity which corresponds to the fairness error induced by an aborting adversary, which we must show to be bounded by 1/p. To prove the latter, we introduce a useful proof technique, whih is new to our knowledge and might have other applications for building and analyzing protocols using timed-release encryption: we analyze the advantage adversary conditioned on aborting at any given round, and crucially rely on the fact that if we know that the adversary is going to abort at round i (since we condition on this event), then the adversary can be thought of as having running time bounded above by the time bound of the timed-release encryption scheme, hence we can use this adversary to derive a contradiction with respect to the semantic security of the timed-release encryption scheme. This is a rather unusual method, in the sense that this step allows us to replace values from a distribution in the security game by values from another distribution which is not indistinguishable from the first one from the viewpoint of the environment; however, it cannot be distinguished from the first one by the environment before the adversary aborts the protocol, due to the timed-release property and the conditionning on an early abort of the adversary.

Informal Overview of the Protocol

We described here a simplified version of the protocol, to ease the presentationthe actual protocol handles additional technicalities required to achieve provable security. We assume familiarity with standard cryptographic primitives such as oblivious transfer here -necessary details about standard primitives can be found in the preliminaries. At a high level, our protocol proceeds as follows: it is parametrized by a polynomial p = p(λ), which will correspond to the number of rounds of the protocol. Intuitively, the parties will exchange values V A and V B , hidden among dummy values and appropriately masked, such that the parties will only learn after the protocol the round number at which they actually got their output value -guaranteeing that any attempt to abort before the protocol is completed will not allow them to break fairness, except with probability roughly 1/p. More precisely:

-First, the two parties (Alice and Bob) generate random masks (k A , k B ), and pick random indices (i A , i B ) between 1 and p, as well as random permutations

(π A , π B , k A ⊕ V A ) of [1, p].
-A will then commit to her index (let r A be the opening information), and encrypt (r

A , i A , π A , k A ⊕ V A )
with a timed-release encryption scheme, that can only be bruteforced after some time T has elapsed (unless the secret key is known). Alice sends the commitment and the encryption to Bob; Bob executes a similar procedure in the other direction. -Both parties exchange the first flow of a 1-out-of-p oblivious transfer protocol, each playing the role of the receiver in the parallel instances, using their random choice of index as their selection value. -Alice and Bob each compute their p messages (m i A ) i≤p and (m i B ) i≤p , playing the role of the sender in the two parallel OT instances, each using their random masks (k A for Alice, k B for Bob) as input for each of the p messages (that is, all p input messages of the player P are equal to k P for P ∈ {A, B}).

-In each of the next rounds, for i = 1 to p, Alice sends m

π A (i) A and Bob sends m π B (i) B
. Note that the same message is 'encrypted' in all OT messages: however, the receiver security guarantees that the sender P ∈ {A, B} does not know which of the OT messages the receiver can decrypt to k P , while the permutation chosen by the sender ensures that the receiver himself cannot yet know which message he can decrypt (it is important here that the key k P is random, so that the receiver cannot notice a successful decryption attempt).

-Upon completion of all p rounds, Alice and Bob open the commitment and the encryption, revealing their secret index as well as

(k A ⊕ V A , k B ⊕ V B ),
from which each party can recover the output.

In the above protocol, all p rounds of interaction must be completed before the time T within which the timed-release encryption can be bruteforced has ellapsed. If any party aborts early, by the security of the commitment scheme and that of the timed-release encryption guarantees that this adversary cannot know whether he had or not already received the OT message that he can decrypt, nor whether or no his opponent did (unless, of course, the party aborts before his opponent received any message at all). Since aborting right before sending a message can only give, informally, 'one round of advance' to a cheating party, this party has only probability 1/p of having already received his outpout while his opponent has not -which both parties will find out within time T , by bruteforcing the timed-release encryption.

Unlike all previous protocols using similar primitives, it is not important here that T is higher than the time the corrupted party could possibly invest; rather, it suffices that T is higher than the time it takes to complete the p rounds of the protocol, and failing to complete the protocol within time T simply amounts to aborting before the end of the protocol -hence guaranteeing a strict upper bound on the running time of all parties. Of course, an adversary can cheat by putting wrong values inside the commitment and/or the timed-release encryption, hence the protocol is not secure against malicious adversaries; however, as we will formally show in the rest of this paper, the protocol outlined above does satisfy 1-deterrent covert security (meaning that if the adversary attempts to cheat, other than by aborting early, he will be detected with probability negligibly close to 1) and 1/p-fairness.

Preliminaries

A positive function f is negligible if for any polynomial p there exists a bound B > 0 such that, for any λ ≥ B, f (λ) ≤ 1/|p(λ)|. An event depending on λ occurs with overwhelming probability when its probability is at least 1 -negl(λ) for a negligible function negl. Given a finite set S, the notation x $ ← S means a uniformly random assignment of an element of S to the variable x. A distribution ensemble X is an infinite sequence of random variables X = {X(a, λ)} a∈D λ ,λ∈N , where D λ is a set that can depend on λ. Following [START_REF] Vanstone | Partial fairness in secure two-party computation[END_REF], we define for any poynomial p the notion of computational 1/p-indistinguishability: Definition 1 (Computational 1/p-Indistinguishability [START_REF] Vanstone | Partial fairness in secure two-party computation[END_REF]). Two distribution ensembles X = {X(a, λ)} a∈D λ ,λ∈N and Y = {Y (a, λ)} a∈D λ ,λ∈N are computationally 1/p-indistinguishable, and write X 1/p ≈ Y , if for any non-uniform PPT adversary Adv, there exists a function µ(

•) = negl(•) such that for any λ ∈ N, a ∈ D λ , | Pr[Adv(X(a, λ)) = 1] -Pr[Adv(Y (a, λ)) = 1]| ≤ 1 p(λ) + µ(λ).
Two distribution ensembles are computationally indistinguishable if they are computationally 1/p-indistinguishable for every polynomial p. Two Party Computation. A two-party protocol between parties A and B is said to compute a functionality f : (x, y) → (f A (x, y), f B (x, y)) if it runs in polynomial time and satisfies the following natural correctness requirement: at the end of the protocol, if A begins with input x and B begins with input y, then A outputs f A (x, y) and B outputs f B (x, y) (for simplicity, we consider only deterministic functionalities; the definition easily extends to randomized functionalities).

The security of a two-party computation protocol is usually defined in the real/ideal paradigm, by showing that every attack a real adversary can mount on the real protocol can be translated to an attack performed by an ideal adversary on an ideal functionality computing the desired function, which is perfectly secure by definition. Given an ideal functionality F, we define the random variable ideal F ,Adv (x, y, λ) as the output of an ideal adversary Adv together with the output of parties with respective inputs (x, y) following the execution of F on (x, y), with security parameter λ. Given a real protocol Π, we define the random variable real Π,Adv (x, y, λ) as the output of a real adversary Adv together with the output of parties with respective inputs (x, y) following the execution of Π on (x, y), with security parameter λ. Then a protocol Π is said to 1/p-securely compute a functionality F if Π emulates the ideal functionality F to within a difference of 1/p. More precisely, let p be an arbitrary polynomial.

Definition 2 (1/p-Secure Computation [START_REF] Vanstone | Partial fairness in secure two-party computation[END_REF]). Let F be an ideal functionality, and Π be a two-party protocol which computes F. Then Π is said to 1/psecurely compute F if for every non-uniform PPT Adv against Π, there exists a non-uniform PPT ideal adversary Sim (called the simulator) such that {ideal F ,Sim (x, y, λ)} x,y,λ

1/p ≈ λ {real Π,Adv (x, y, λ)} x,y,λ .
Two Party Computation against Covert Adversaries. The above definition of two-party computation captures security against malicious adversaries, who can mount arbitrary attacks on a protocol. A weaker security model, which remains very relevant in practice, is the covert security model : in this model, the parties might still arbitrarily deviate from the specification of the protocol, but they do not want to be caught cheating, hence they will not adopt a malicious behavior which would be detected with too high probability. This security model has been formalized in [START_REF] Aumann | Security against covert adversaries: Efficient protocols for realistic adversaries[END_REF], who gave several variants. In this work, we will focus on the failed simulation formulation, as this formulation can be integrated in a very natural way to the notion of 1/p-secure computation. Intuitively, the failed simulation formulation states that a malicious adversary can cause the simulation to fail by cheating, but if he can cause the simulation to fail with probability x, then he will be caught cheating with probability ε • x, where ε is called the deterrence factor of the protocol. Extending this definition to 1/p-secure computation, we will say that a protocol 1/p-securely compute a functionality against covert adversaries with deterrence factor ε if every time an adversary causes the simulation to be distinguishable from a real run of the protocol with probability 1/p + x, then he is caught cheating with probability x • ε. More formally, let us first define the notion of detection accuracy for protocols with static corruption from [START_REF] Aumann | Security against covert adversaries: Efficient protocols for realistic adversaries[END_REF]: Definition 3 (Detection Accuracy [START_REF] Aumann | Security against covert adversaries: Efficient protocols for realistic adversaries[END_REF]). A party P b in a two-party protocol Π (with b ∈ {0, 1}) is said to detect cheating the party P 1-b if it outputs corrupted 1-b in Π. A two-party protocol Π is detection accurate if the probability that a party outputs corrupted b when party P b is not corrupted is negligible.

We can now formally define covert 1/p-security: Definition 4 (Covert 1/p-Security). Let F be an ideal functionality, and Π be a two-party protocol between parties P 0 and P 1 which computes F. Then Π is said to 1/p-securely compute F in the presence of covert adversaries with εdeterrent if it is detection accurate and for every non-uniform PPT Adv against Π which corrupts P b , there exists a non-uniform PPT ideal adversary Sim (called the simulator) such that for every inputs (x, y) and every non-uniform PPT distinguisher D,

Pr[P 1-b outputs corrupted b ] ≥ ε(λ) • (| Pr[D(ideal F ,Sim (x, y, λ)) = 1] -Pr[D(real Π,Adv (x, y, λ)) = 1]| -1/p(λ)) -negl(λ).
3 A Partially-Fair Exchange Protocol

Definition

Informally, a partially-fair exchange protocol allows two parties to exchange their inputs, with the guarantee that either the two parties will learn their output, or none will, except with a 1/poly probability which can be made arbitrarily small. In other words, the protocol realizes the fair exchange functionality, except with probability 1/poly. More precisely: Definition 5 (Partially-Fair Exchange). A partially-fair exchange protocol is a family {Π p } p∈poly of two-party protocol such that for any polynomial p, the protocol Π p 1/p-securely compute the ideal functionality F fe represented on Figure 1.

Ideal Functionality F fe

The functionality interacts with parties through perfectly secure authenticated channels. It maintains a memory M . It ignores all incorrectly formatted messages.

Building Blocks

Equivocable Trapdoor Commitment. An equivocable trapdoor commitment scheme is computationally hiding, computationally binding commitment scheme which satisfies two properties:

it is equivocable, meaning that with some appropriate trapdoor, any commitment can be opened to an arbitrary value; it is weakly extractable, meaning that given an appropriate trapdoor, there is an extraction algorithm that recovers a message m from a commitment such that no PPT adversary can open this commitment to a value m = m.

We provide a formal definition below. Equivocable. A commitment scheme C is equivocable if for any and m ∈ M, the following distributions are indistinguishable:

{(pp, τ ) $ ← C.Setup(1 λ ), (c, d) $ ← C.Commit(pp, m) : (pp, c, d)} and {(pp, τ ) $ ← C.Setup(1 λ ), c $ ← C, d ← C.Equivocate(τ, c, m) : (pp, c, d)}.
Weakly Extractable. A commitment scheme C is weakly extractable if for any PPT adversary Adv, it holds that

Pr   (pp, τ ) $ ← C.Setup(1 λ ), (c, m, d) ← Adv(pp), m ← C.Extract(τ, c) : (m = m ) ∧ (C.Verify(pp, c, m, d) = 1)   ≈ 0.
Instantiating Equivocable Trapdoor Commitments. There are several possible approaches to constructing equivocable trapdoor commitments. The most natural one, however, is simply to start from a standard extractable commitment (e.g. ElGamal encryption), and to replace the usual opening (which consists in revealing the message m and the random coin r) by a zero-knowledge proof that the ciphertext encrypts m. Equivocability follows immediatly from the simulatability of the zero-knowledge proof, while weak-extractability follows directly from the extractability of the commitment scheme, together with the soundness of the proof system. Instantiating the extractable scheme with ElGamal, the zero-knowledge proof can either be any four-move interactive zero-knowledge proof for the DDH relation (very efficient and standard protocols exist for this relation), or a non-interactive proof (which can be secure in the random oracle, or alternatively rely on pairing-based cryptography if we use ElGamal over a pairing-friendly elliptic curve. We note that pairing-based non-interactive proofs for linear languages such as DDH relations can be as short as a single group element, using the scheme of Kiltz and Wee [START_REF] Kiltz | Quasi-adaptive NIZK for linear subspaces revisited[END_REF]).

Public-Key Encryption. We first recall the standard definition of a semanticallysecure public-key encryption scheme: Definition 7 (Encryption Scheme). An encryption scheme E is a triple of efficient algorithms (KeyGen, Enc, Dec) such that -KeyGen(1 λ ) outputs a public key pk and a secret key sk, pk specifies the message space M, the ciphertext space C, and the random source R; -Enc(pk, m; r), given the message m, outputs a ciphertext c, under the encryption key pk with the randomness r; -Dec(sk, c), outputs a plaintext m, encrypted in the ciphertext c using the decryption key sk.

Encryption schemes are assumed to satisfy the following properties:

Correctness. An encryption scheme Π is correct if for any pair of keys (pk, sk) generated by KeyGen and any message m ∈ M, it holds that Dec(Enc(m)) = m.

Semantic Security (IND-CPA). The classical security notion for encryption is the indistinguishability of ciphertexts: no adversary can distinguish the encryptions of the plaintexts m 0 and m 1 of its choice, given just access to public key.

Timed-Release Encryption. To define timed-release encryption, we first introduce the notion of a T -bounded algorithm: we say that an algorithm is Tbounded if it runs in sequential time strictly upper-bounded by T . A (T, T )-timed release encryption scheme, with T ≥ T , is a public-key encryption scheme where semantic security is relaxed to hold only against T -bounded PPT adversaries, with an additional T -bounded PPT algorithm ForceDec which, on input (pk, c), outputs m = Dec(sk, c). Timed-release encryption was introduced in [START_REF] Ronald L Rivest | Time-lock puzzles and timedrelease crypto[END_REF]; it can be constructed under the assumption that squaring modulo an RSA modulus cannot be parallelized efficiently [START_REF] Ronald L Rivest | Time-lock puzzles and timedrelease crypto[END_REF].

Oblivious Transfer. An oblivious transfer protocol allows a receiver to obliviously select one of n strings held by a sender, with the guarantee that the sender will not learn which string was selected, while the receiver will not learn anything about the strings he did not selected. We will rely in this work on a simulatable two-round 1-out-of-n oblivious transfer protocol (in the common reference string model); we provide a formal definition below. Sender Simulatability. There exists a simulator SenderSim which satisfies the following: for any (pp, τ ) ← Setup(1 λ , 0) and every (possibly malformed) c 1 , SenderSim(τ, c 1 ) outputs a value i such that for every pair of messages (m 0 , m 1 ), and every i = i, {OT 2 (pp, c 1 , i , m 0 )} and {OT 2 (pp, c 1 , i , m 1 )} are statistically indistinguishable.

Receiver Simulatability. There exists a simulator ReceiverSim which satisfies the following: for every i ∈ [n], the distributions

{(pp, τ ) $ ← Setup(1 λ , 1), (c 1 , o 1 , • • • , o n ) $ ← ReceiverSim(τ ) : (c 1 , o i )} and {(pp, τ ) $ ← Setup(1 λ , 1), (c 1 , o i ) $ ← OT 1 (pp, i) : (c 1 , o i )} are statistically in- distinguishable.
Instantiating Simulatable Oblivious Transfer. The most natural approach to instantiate the above primitive is to rely on the construction of [START_REF] Peikert | A framework for efficient and composable oblivious transfer[END_REF], which can be based on either DDH, quadratic residuosity, or LWE. The second message of a 1-out-of-p simulatable OT under the DDH assumption requires 2 log p group elements under the scheme of [START_REF] Peikert | A framework for efficient and composable oblivious transfer[END_REF], leading to the claimed communication in the introduction of this paper.

Protocol

We now proceed with the description of a partially-fair exchange protocol in the common reference string model. The protocol is parametrized with a polynomial p such that it 1/p-securely compute the fair exchange functionality F fe , with security against covert adversaries (and a negligible deterrence factor). The protocol relies on timed-release encryption; it assumes that both parties have access to a synchronized clock. Furthermore, for correctness, we assume that there is a known upper-bound ∆ on the network delay for message transmission. We represent the protocol on Figure 2.

Theorem 9. The protocol Π sfe 1/p-securely compute F fe in the presence of covert adversaries with 1-deterrent.

After providing an informal overview of the proof, we formally prove Theorem 9 in Section 3.5.

Informal Overview

To prove Theorem 9, we exhibit a simulator who "almost-correctly" simulates Π sfe given access to F sfe . The simulator, who does not know A's input x A , will play as follows: the initialization phase is executed honestly, except that the value (d A ||x A ) ⊕ K A in the ciphertext E A is replaced by a random value x A of the appropriate size (Sim will derive later on the appropriate mask K A to transmit to B so that x A is unmasked to (d A ||x A )). From the initial commitment com B and ciphertext E B of B, Sim extracts his input x B and sends it to the functionality F fe . He also extracts the round number i * at which B should obtain the key K A , if he did not abort before. Then, during the fair exchange phase, Sim computes his OT 2 messages on dummy inputs, except for round i * (the simulatability of the OT guarantees that all OT 2 messages are perfectly lossy, except for the one corresponding to the round i * identified by Sim, hence this simulation is indistinguishable from a real run of the protocol). At round i * , if B has not yet aborted, Sim will send proceed to the functionality F fe , and get x A . He will then equivocate the commitment com A to derive an appropriate opening d A which "explains" com A as a commitment to x A , and sends the key

K A ← x A ⊕(d A ||x A ) to B. If B aborts before round i * , Sim simply sends abort to F fe .
The above simulation fails in two situations:

-When B cheats by not transmitting the opening of com B to A, or by not including the random coins of his

OT 1 message c 1,B in E B . Protocol Π sfe
The protocol is parametrized with a polynomial p and a network delay upperbound ∆.

-Primitives. The protocol relies on an equivocable trapdoor commitment C = (C.Setup, C.Commit, C.Verify, C.Extract, C.Equivocate), a (T, T )-timed release encryption scheme (KeyGen, Enc, Dec, ForceDec) (where the value T is chosen so that executing steps 2-3 of the protocol takes time at most T given the upper-bound ∆ on the network delay), and a two-round simulatable 1-out-ofp(λ) oblivious transfer (Setup, OT1, OT2, Decode). -Inputs. The parties A and B holds respective inputs xA and xB (which are assumed to be λ-bit long for simplicity). -Setup. On input the security parameter 1 λ , the setup algorithm computes (pk A , skA)

$ ← KeyGen(1 λ ), (pk B , skB) $ ← KeyGen(1 λ ), (pp A , τA) $ ← Setup(1 λ , 0), (pp B , τB) $ ← Setup(1 λ , 0), and (pp, τ ) ← C.Setup(1 λ ). It outputs crs ← (pk A , pk B , pp A , pp B , pp).
We now proceed with the actual description of the protocol. -If B aborted before the start of the fair exchange phase, she outputs yA ← ⊥. -Otherwise, she executes the ForceDec procedure to recover (iB, rB, πB, x B ). She checks whether c1,B = OT1(pp B , iB; rB); if this checks fails, she outputs corrupted B . -Otherwise, let j denote the index of the round at which B aborted (or failed to send a message before time T elapsed); if B did not abort in the fair exchange phase, set j ← p(λ) + 1. A checks that both πA(iB) ≤ j and πB(iA) < j. If any of these checks fails, she outputs yA ← ⊥.

-Otherwise, she computes KB ← Decode(pp A , c 2,B,π B (i A ) , o1,A), xB||dB ←
x B ⊕KB, and she checks that C.Verify(pp, comB, xB, dB) = 1. If this check fails, she outputs corrupted B ; otherwise, she outputs yA ← xB. B performs the corresponding symmetrical operations and outputs yB (or corrupted A ).

Note that the values exchanged during the Reveal phase are not used in the output phase. The purpose of the Reveal phase is to let the parties obtain their output before the time T elapsed in practice, while being able to check later on (after executing the ForceDec procedure) whether their adversary was honest or malicious. For the security analysis, however, we only consider the outputs obtained by the parties after the ForceDec procedure. -When B aborts at a round j such that he already got enough information to obtain his output (after executing the ForceDec procedure), but A did not yet receive the information on her output. Indeed, in Sim's simulation, perfect fairness is always guaranteed by F fe .

The first issue corresponds to B following an active cheating strategy; however, this strategy is always successfully detected by A, who outputs corrupted B when she does not receive the appropriate opening and coins. This captures the fact that the protocol is secure against covert adversaries with 1-deterrent: a malicious adversary can deviate from the protocol (and break partial fairness), but will always be caught when doing so.

The second issue corresponds exactly to the 1/p gap in partial fairness. Most of the analysis will be devoted to proving that this situation happens with probability at most 1/p (conditioned on the first situation not happening, i.e., A not outputting corrupted B ). The analysis proceeds by considering the probability of this even conditioned on B aborting at round j, for every possible round j. Then, the crucial observation is that when he aborts early, B can be thought of as a T -bounded adversary. This will allow us to invoke the semantic security of the timed-release encryption scheme to show that its content is hidden from B. From this, we conclude that the rounds at which A and B must receive their outputs (respectively π B (i A ) and π A (i B )) are uniformly random (π A , i A are honestly picked at random by Sim, and they remain hidden from B, who chooses π B , i B ). Therefore, in the event of the round π B (i A ) being after some given round j, while π A (i B ) ≤ j, can be shown to be (almost) independent of B's behavior (including his choice to abort or not). This allows us to bound the probability of this event by j p • p+1-j p + negl(λ) for every j. Each term being upper bounded by 1/p + negl(λ), the security argument follows.

Security Analysis

First, it immediately follows by inspection that if all parties play honestly (except for potential early abortion), no party will output corrupted. Therefore, the protocol is detection accurate. We now proceed with the security analysis of the protocol. We do so by exhibiting a simulator Sim which simulates the protocol against a maliciously corrupted B, given access to the ideal functionality F fe ; the security against a corrupted A follows symmetrically. Let (x A , x B ) be two arbitrary inputs, and let D be a non-uniform PPT distinguisher. We proceed through a sequence of hybrids, denoted H i ; for each hybrid H i , we denote by hybrid i the random variable associated to the transcript and outputs of the parties in an execution of H i with a corrupted B and inputs (x A , x B ).

-Hybrid H 0 . The first hybrid, H 0 , corresponds to the real game, where Sim honestly emulates A (using her input x A ) and B is corrupted. By definition, hybrid 0 is the random variable real Π sfe ,B (x A , x B , λ) corresponding to the transcript and outputs of an execution of Π sfe with an honest A and a corrupted B.

Simulator Sim -Setup Simulation. On input the security parameter 1 λ , the simulated setup algorithm computes (pk A , skA)

$ ← KeyGen(1 λ ), (pk B , skB) $ ← KeyGen(1 λ ), (pp A , τA) $ ← Setup(1 λ , 1), (pp B , τB) $ ← Setup(1 λ , 0), and (pp, τ ) ← C.Setup(1 λ ). It outputs crs ← (pk A , pk B , pp A , pp B , pp).
Sim stores the trapdoor (skB, τA, τB, τ ). Let sid be the session id for this execution of F fe . -Hybrid H 1 . In hybrid H 1 , instead of generating (pp A , τ A ) -Hybrid H 2 . In hybrid H 2 , Sim extract i B ← SenderSim(τ B , c 1,B ), using the simulator for the sender simulatability of the oblivious transfer, and computes i * ← π A (i B ) (which is the index of the round at which the OT message that B can decode will be sent). At every round j = i * , Sim sends c 2,A,j -Hybrid H 4 . In hybrid H 4 , Sim now computes E A as Enc(pk A , (i A , r A , π A , x A ))

$ ← Setup(1 λ , 0) as in H 0 , (pp A , τ A ) is generated as (pp A , τ A ) $ ← Setup(1 λ , 1)
for a uniformly random We now analyze the advantage of D in distinguishing hybrid 4 from hybrid 5 . First, note that the only difference between the transcripts produced by Sim in H 4 and H 5 (setting the outputs aside) is the way c 2,A,i * is computed; Sim computes all other messages identically in H 4 and H 5 . Let us denote c * ← c 2,A,i * for notational simplicity. In both hybrids, c * is constructed as OT 2 (pp B , c 1,B , i * , (d A ||x A ) ⊕ x A ); the only difference lies in the way x A is determined by Sim: in H 4 , Sim knows A's input x A from the start, while in H 5 , Sim obtain x A by extracting x B from com B (using the trapdoor τ ) and sending it to F fe on behalf of the ideal B, until he receives x A from F fe . By definition of F fe , independently of whether Sim extracted the correct input x B from B, it always hold that the value x A sent by F fe is exactly A's input. Therefore, the transcript produced by Sim is always exactly the same in both H 4 and H 5 , so we can upper bound the probability that D distinguishes hybrid 4 from hybrid 5 by the probability that the (simulated) output of A in H 4 differs from the output of the ideal A in H 5 . We analyze this probability below.

x A $ ← {0, 1} 2λ . At round j = i * , he computes c 2,A,j ← OT 2 (pp B , c 1,B , π A (j), (d A ||x A )⊕x A ).
For j = 0 to j = p + 1, let Abort j denote the event "B aborts at round j" (Abort 0 is the event of B aborting in the initialization; Abort p+1 is the event of B not aborting).

= y 5 A | Abort 0 ∧ NotCorrupt] = negl(λ).
This claim also follows immediately, as the output in both H 4 and H 5 is equal to ⊥ when B aborts during the initialization.

Claim. For any

j ∈ {1, • • • , p}, it holds that Pr[y 4 A = y 5 A | Abort j ∧ NotCorrupt] ≤ j • (p + 1 -j) p 2 + negl(λ).
Observe that in H 5 , the functionality guarantees perfect fairness: either both A and B get their output, or none does. If B aborts at round j, and Sim does not output corrupted B in H 4 , then the only situation in which the output y 4 A in H 4 differs from y 5

A is the following: B already obtained the OT 2 message corresponding to his OT 1 message and will get his output (i.e., π A (i B ) ≤ j), but A did not (i.e., π B (i A ) ≥ j) -this corresponds to the situation where fairness fails to hold in H 4 . Let us denote BadEvent j this event. In all other situations, either y 4 A = y 5 A = x B , or y 4 A = y 5 A = ⊥. We now analyze the probability

Pr[BadEvent j | Abort j ∧ NotCorrupt] = Pr[(π A (i B ) ≤ j) ∧ (π B (i A ) ≥ j) | Abort j ∧ NotCorrupt].
The core observation toward proving the claim is that, conditioned on B aborting at round j ≤ p, B is a T -bounded adversary. This allows us to invoke the semantic security of the timed-release encryption scheme. Indeed, consider the following hybrids:

-Hybrid H 4 . In H 4 , Sim plays exactly as in H 4 , except that he computes E A as a random encryption of a dummy string of the appropriate length.

-Hybrid H 4 . In H 4 , Sim plays exactly as in H 4 , except that he computes c 1,A using the algorithm ReceiverSim (given by the receiver simulatability property of the OT scheme) with input τ A .

Note that both H 4 and H 4 do not correspond to "proper simulations", in the sense that the external distinguisher D will easily distinguish H 4 and H 4 from H 4 (in particular because he can run in time longer than T ). However, they intuitively correspond to partial simulations that cannot be distinguished from H 4 by B, who aborts early.

We first observe that the probability of BadEvent j happening in H 4 (conditioned on Abort j ∧ NotCorrupt) must be essentially the same as the probability of BadEvent j happening in H 4 , i.e.:

| Pr[BadEvent j in H 4 | Abort j ∧ NotCorrupt]- Pr[BadEvent j in H 4 | Abort j ∧ NotCorrupt]| = negl(λ).
This follows from the semantic security of the timed-release encryption scheme: as Sim can observe when BadEvent j happens, a party B aborting at round j (hence T -bounded) causing BadEvent j to happen with significantly different probability in H 4 immediately allows Sim to distinguish with non-negligible probability between the "real" E A and the dummy one given access to the T -bounded adversary B, contradicting the semantic security of the scheme.

The indistinguishability of H 4 and H 4 follows directly from the receiver simulatability property of the OT scheme, hence we get:

| Pr[BadEvent j in H 4 | Abort j ∧ NotCorrupt]- Pr[BadEvent j in H 4 | Abort j ∧ NotCorrupt]| = negl(λ).
Now, observe that in H 4 , i A and π A are chosen uniformly at random (respectively from [1, p] and from the set of permutations of [1, p]) by Sim. Furthermore, in H 4 , B gets no information about i A and π A (the content of E A being replaced by a dummy string, and c 1,A being simulated without using i A ). This implies that the probability of π B (i A ) ≥ j in H 4 is exactly the probability that a random integer in [1, p] is bigger than j, i.e., j/p. Similarly, the probability of π A (i B ) ≤ j in H 4 is equal to (p+1-j)/j. Importantly, both probabilities are also independent with each other, and independent of the events Abort j ∧ NotCorrupt (they only depend on random coins of Sim which are kept perfectly hidden from B). We therefore obtain:

Pr[BadEvent j in H 4 | Abort j ∧ NotCorrupt]| = j p • p + 1 -j p ,
which concludes the proof of the claim. We can now finish the proof of Theorem 9: by the previous claims, using the fact that j p • p+1-j p ≤ 1/p for every j ∈ [1, p], we have for every j ∈ [0, p + 1],

Pr[y 4 A = y 5 A | Abort j ∧ NotCorrupt] ≤ 1/p + negl(λ),
which gives via Bayes rule

p+1 j=0 Pr[(y 4 A = y 5 A )∧Abort j ∧ NotCorrupt] = Pr[(y 4 A = y 5 A ) ∧ NotCorrupt] ≤ (1/p + negl(λ)) • p+1 j=0 Pr[Abort j ∧ NotCorrupt] ≤ (1/p + negl(λ)) • p+1 j=0 Pr[Abort j ] = 1/p + negl(λ).
We therefore obtain

Pr[(y 4 A = y 5 A ) ∧ NotCorrupt] ≤ 1/p + negl(λ) =⇒ Pr[(y 4 A = y 5 A )] • (1 -Pr[Corrupt]) ≤ 1/p + negl(λ) =⇒ Pr[(y 4 A = y 5 A )] -(1/p + negl(λ)) ≤ Pr[(y 4 A = y 5 A )] • Pr[Corrupt] =⇒ Pr[(y 4 A = y 5 A )] -(1/p + negl(λ)) ≤ Pr[Corrupt].
Plugging this last inequality in our initial observation that Pr[(y 4 A = y negl(λ), which concludes the proof of Theorem 9.

Extensions

We sketch how the protocol Π sfe can be naturally extended to more complex functionalities. Observe that, after the initialization phase, both parties hold (equivocable and weakly-extractable) commitments to the values of their opponent. At this stage, the parties can rely on zero-knowledge proof to prove arbitrary statements of their choice regarding their committed value to their opponent, or execute any two-party computation protocol (satisfying only security with abort) to guarantee any specific property of the committed value without disclosing them -as long as this phase is completed before a time T elapses.

In particular, the parties can for example rely on a generic two-party computation protocol satisfying security with abort to check that the committed value of their opponent verifies correctly with respect to their secret-key of a one-time MAC scheme; the 1/p-fairness of the resulting scheme follows immediately from the 1/p-security of Π sfe and the security with abort of the generic two-party computation protocol. This shows that our minimal use of a delayed encryption scheme already suffices to get around the impossibility result of [START_REF] Gordon | Partial fairness in secure two-party computation[END_REF], which was established exactly for this primitive. More generally, the two parties can compute arbitrary functionalities with 1/p-fairness as follows: first: they execute a generic two-party computation protocol which computes a modified functionality, whose output is a random xor sharing of the desired output. This protocol only needs to be secure with abort, since no early abortion during its execution can allow the adversary to learn the output, each share revealing nothing about the output. Then, the two parties execute the protocol Π sfe on those outputs shares, and rely on a generic zeroknowledge proof system (before the start of step 2) to demonstrate that the value committed in the initialization phase is the correct output of the modified functionality on their private input. After completion of the protocol Π sfe , both parties reconstruct the output by XORing the exchanged values. It immediately follows from the security-with-abort of the generic two-party protocol, the security of the zero-knowledge proof system, and the 1/p-security of Π sfe , that the resulting protocol does 1/p-securely compute the desired functionality.

Other Applications of Partially-Fair Exchange

The partially-fair exchange mechanisms proposed here can find application in other contexts, for example contract signing. Note that there are some interesting issues of incentives here: in the application to PAKEs the attacker wants to provide the correct confirmation value if possible. There is no incentive for him to provide an "invalid" V value. This is in contrast to, say, contract signing, where each party may well be incentivised to submit invalid signatures. The standard way to handle this is to introduce optimistic protocols: that will invoke a judge or TTP in the event of problems. In this context it is not clear that our partially-fair exchange construction provides any advantage over such optimistic protocols.

A protocol may satisfy fair-exchange and still admit the possibility that at some point in the execution one party has the power to determine whether or not the protocol will terminate successfully, and furthermore be able to prove this to a third party. This may be an issue if this party can use this a leverage to bargain more favourably with the third party. Abuse-freeness seeks to counter this by requiring that neither party can demonstrate to a third party that they can control whether or not the protocol will complete. Our SFE construction denies the parties knowledge of the point at which they acquire the desired terms and so could provide the basis for abuse-freeness.

Conclusions

In this paper we have presented a new construction for partially-fair exchange, based on oblivious transfer and a delay primitive. While the original motivation came from making PAKE protocols "auditable", the protocol we obtain achieves a very interesting property, which we believe to be of broader independent interest: it provides the first generic method to achieve 1/p-fairness, for every functionality (without limitations on the input size or the output size as in the paper of Katz and Gordon), while guaranteeing at the same time a polynomial upper bound on the running time of all parties. In particular, this means that the fairness guarantee that we obtain does also extend to the scenarios where the adversaries might be considerably more powerful than the honest parties; to our knowledge, every previous paper achieving some form of fairness for all functionalities (without the help of a trusted third party, or a smart contracts) could not guarantee this highly desirable property. In addition, our protocol is not purely of theoretical interest: it remains practical, and its building blocks can be instantiated efficiently from a variety of standard cryptographic assumptions.

Fig. 1 .

 1 Fig. 1. Ideal Functionality F fe for fair exchange between two parties A and B.

Definition 6 .

 6 (Equivocable Trapdoor Commitment) An equivocable trapdoor commitment C with message space M, commitment space C, opening space D, and random source R, is a 5-tuple of PPT algorithms (C.Setup, C.Commit, C.Verify, C.Extract, C.Equivocate), such that -C.Setup(1 λ ), on input the security parameter, generates the public parameters pp of the scheme and a trapdoor τ , -C.Commit(pp, m; r), given the message m ∈ M and some random coins r ∈ R, outputs a pair commitment-opening (c, d), -C.Verify(pp, c, m, d), given a commitment c ∈ C, a message m ∈ M, and an opening d ∈ D, outputs a bit b ∈ {0, 1}, -C.Extract(τ, c), given a trapdoor τ and a commitment c, outputs a message m ∈ M, -C.Equivocate(τ, c, m), given a trapdoor τ , a commitment c, and a message m, output an opening d ∈ D, which satisfies the following properties: Correctness. For any (pp, τ ) ← C.Setup(1 λ ), any (m, r) ∈ M × R, if (c, d) = C.Commit(pp, m; r), then C.Verify(pp, c, m, d) = 1.

Definition 8 (← 2 $← = 1 .

 821 Simulatable Oblivious Transfer). A two-round simulatable 1-out-of-n oblivious transfer protocol in the common reference string model is a quadruple of PPT algorithms (Setup, OT 1 , OT 2 , Decode) such that -Setup(1 λ , b), on input the security parameter an a bit b (called the mode), outputs a pair (pp, τ ) where pp a set of public parameters, and τ is a trapdoor (used only in the simulation); -OT 1 (pp, i), on input a selection value i ∈ [n], outputs a pair (c 1 , o) where o is called the opening information; -OT 2 (pp, c 1 , i , m), on input a value c 1 , a value i ∈ [n], and a message m ∈ M (M is the message space), outputs a value c 2 ; -Decode(pp, c 2 , o), on input a value c 2 and an opening information o, outputs a message m ∈ M ∪ {⊥}. The scheme is assumed to satisfy the following properties: Correctness. For any i ∈ [n] and any message m ∈ M, OT 1 (pp, i), c OT 2 (pp, c 1 , i, m) : Decode(pp, c 2 , o) = m  Indistinguishability of Modes. The distributions D 0 and D 1 , where D b = {(pp, τ ) $ ← Setup(1 λ , b) : pp}, are computationally indistinguishable.

1 .

 1 Initialization. A picks a random index iA $ ← [p(λ)], a random key KA $ ← {0, 1} 2λ , a random coin rA for the oblivious transfer, and a random permutation πA of [p(λ)]. She computes (comA, dA) $ ← C.Commit(pp, xA), EA $ ← Enc(pk A , (iA, rA, πA, (dA||xA) ⊕ KA)), (c1,A, o1,A) ← OT1(pp A , iA; rA), and sends (EA, c1,A, comA) to B. B executes the corresponding symmetrical operations (with public parameters pk B , pp B ), and sends (EB, c 1,b , comB) to A. Upon reception of the other party's message, both parties start a timer. 2. Fair Exchange. This phase proceeds in p(λ) rounds. For j = 1 to p(λ), the parties execute the following simultaneously: A sends c2,A,j $ ← OT2(pp B , c1,B, πA(j), KA), and B sends c2,B,j $ ← OT2(pp A , c1,A, πB(j), KB). 3. Reveal. A sends (xA, πA) to B. Simultaneously, B sends (xB, πB) to A. 4. Output. In the output phase, A does the following:

Fig. 2 .

 2 Fig. 2. Partially-Fair Exchange Protocol Π sfe between two parties A and B.

1 .

 1 Initialization. Sim simulates A as follows: he picks a random index iA $ ← [p(λ)], a random x A $ ← {0, 1} 2λ , a random coin rA for the oblivious transfer, and a random permutation πA of [p(λ)]. He computes EA $ ← Enc(pk A , (iA, rA, πA, x A )) and (c1,A, o1,A) ← OT1(pp A , iA; rA), picks a random comA ∈ C, and sends (EA, c1,A, comA) to B. Upon reception of (EB, c1,B, comB) Sim starts a timer and does the following: he computes (iB, rB, πB, x B ) ← Dec(skB, EB); he computes i B ← SenderSim(τB, c1,B), and set i * ← πA(i B ); he computes xB ← C.Extract(τ, comB), sends (input, sid, xB, A, B) to F fe on behalf of the ideal B, and waits for the answer (ready, sid, A, B) from F fe . -If B aborts in this phase, Sim sends (abort, sid, A, B) to F fe on behalf of the ideal B. 2. Fair Exchange. For j = 1 to p(λ), Sim plays as follows: -If j = i * , and B did not abort, Sim sends c2,A,j $ ← OT2(pp B , c1,B, πA(j), 0 λ ). -If j < i * and B aborts, Sim sends (abort, sid, A, B) to F fe on behalf of the ideal B. if j = i * and B did not abort in the previous rounds, Sim sends (proceed, sid, A, B) on behalf of the ideal B, and wait until he receives xA from F fe . He computes dA ← C.Equivocate(τ, comA) and sends c2,A,i * $ ← OT2(pp B , c1,B, πA(j), x A ⊕ (dA||xA)). 3. Reveal. If B did not abort during the fair exchange phase, then Sim received xA from F fe at round i * . Sim sends (xA, πA) to B.

Fig. 3 .

 3 Fig. 3. Simulator Sim for the protocol Π sfe against a maliciously corrupted B. Sim is given access to the ideal functionality F fe .

  in H 1 ; the rest of the protocol remains unchanged. By the indistinguishability of the modes of the simulatable OT scheme, we have | Pr[D(hybrid 0 ) = 1] -Pr[D(hybrid 1 ) = 1]| = negl(λ).

$←

  OT 2 (pp B , c 1,B , π A (j), 0 λ ). By the sender simulatability property, the simulated c 2,A,j for j = i * are statistically indistinguishable from honest c 2,A,j , hence we have| Pr[D(hybrid 1 ) = 1]-Pr[D(hybrid 2 ) = 1]| = negl(λ). -Hybrid H 3 . In hybrid H 3 , Sim does not compute (com A , d A ) as (com A , d A ) $ ← C.Commit(pp, x A ) anymore; instead,she picks a random com A $ ← C from the commitment space, and set d A ← C.Equivocate(τ, c, m). By the equivocability of the commitment scheme, we have | Pr[D(hybrid 2 ) = 1] -Pr[D(hybrid 3 ) = 1]| = negl(λ).

  This hybrid is perfectly indistinguishable from the previous one: Pr[D(hybrid 3 ) = 1] = Pr[D(hybrid 4 ) = 1]. -Hybrid H 5 . Hybrid H 5 corresponds to the simulation described on Figure 3; therefore, hybrid 5 = ideal F fe ,Sim (x A , x B , λ). Below, we analyze the advantage of D in distinguishing hybrid 4 from hybrid 5 .

5 A

 5 )] ≥ | Pr[D(hybrid 4 ) = 1] -Pr[D(hybrid 5 ) = 1]|, we obtain Pr[Corrupt] ≥ | Pr[D(hybrid 4 ) = 1] -Pr[D(hybrid 5 ) = 1]| -1/p -negl(λ).By the analysis ofH 0 = real Π sfe ,B (x A , x B , λ) to H 4 , we had | Pr[D(real Π sfe ,B (x A , x B , λ)) = 1] -Pr[D(hybrid 5 ) = 1]| = negl(λ),which finally gives usPr[Corrupt] ≥ | Pr[D(real Π sfe ,B (x A , x B , λ)) = 1] -Pr[D(ideal F fe ,Sim (x A , x B , λ)) = 1]| -1 p(λ)

  Otherwise, ignore the input. 2. On input a message (proceed, sid, A, B) from A and B, search M for an item (sid, A, B, xA, xB) for some (xA, xB) (ignore if there is none). Send xB to A and xA to B, and erase (sid, A, B, xA, xB) from M . 3. On input a message (abort, sid, A, B) from either A or B, search M for an item (sid, A, B, xA, xB) for some (xA, xB) (ignore if there is none). Send ⊥ to A and B, and erase (sid, A, B, xA, xB) from M .

1. On input a message (input, sid, xA, A, B) from A and (input, sid, xB, B, A) from B, where sid is a unique session identifier, if M does not contain an item starting with (sid, A, B), store (sid, A, B, xA, xB) in M , and send (ready, sid, A, B) to Adv.

  Let NotCorrupt denote the event of Sim not outputting corrupted B in H 4 . Let y 4 A denote Sim's output in H 4 , and let y 5 A denote the output of the ideal A in H 5 . This follows immediately from the previous analysis. Indeed, if B does not abort during the protocol and Sim does not output corrupted B in H 4 , then it holds that y 4 A = x B , where x B comes from the pair x B ||d B ← x B ⊕ K B , which Sim obtained by computing K B ← Decode(pp A , c 2,B,π B (i A ),o 1,A ) and x B ← ForceDec(pk B , E B ). As Sim does not output corrupted B , it also necessarily holds that C.Verify(pp, com B , x B , d B ) = 1. By the weak extractability property of C, this implies that the value C.Extract(τ, com B ) computed by Sim in H 5 is equal to x B , except with probability negl(λ). But this extracted value x B is the one sent by Sim to F fe on behalf of B, hence by the functionality of F fe , it is also the output y 5 A of the ideal A, hence the claim.

	Claim. It holds that
	Pr[y 4 A = y 5 A | Abort p+1 ∧ NotCorrupt] = negl(λ).
	Claim. It holds that
	Pr[y 4 A


Antonin Louiset

Sylvie Schamm-Chardon

Oleg Kononchuk

Nikolay Cherkashin

Reconstruction of

come

In the context of growing interest in strain engineering, we present a theoretical protocol for the reconstruction of extrinsic and intrinsic strain tensors in single-crystals attached to a template, with an arbitrary oriented coordinate system. Input data for the protocol are extrinsic deformations of lattice planes, i.e. measured with reference to a template. By combining the protocol with elasticity theory, material property modification can be elucidated. Different methods for strain measurements can take advantage of this approach. It has been applied for reconstruction of strain tensor depth distribution in off-axis LiTaO 3 crystal implanted with H + ions, which is the key step for piezoelectric thin film-on-insulator fabrication by Smart Cut process. Modifications of composition, lattice parameters and elastic constants are indicated and discussed.

Today, crystalline thin films are widely used in the industry. Investigating strain inside these layers has become a key subject of interest since strain is responsible for various modifications of material properties. In semiconductors, strain enhances carriers mobility 1 and thus performance of Metal-Oxide-Semiconductor Field-Effect Transistors. 2 Strain plays a major role in complex oxide integration in microelectronics. Piezoelectric and ferroelectric crystals are especially of concern thanks to their electro-mechanical and dielectric properties. 3 Direct epitaxial integration of ferroelectric thin films allowed substantial engineering of their spontaneous polarization and Curie temperature. 4 Modern radio frequency front end modules like Temperature Compensated Surface Acoustic Wave filters 5,[START_REF] Balysheva | Wave Electronics and its Application in Information and Telecommunication Systems (WECONF)[END_REF] involve Lithium Tantalate (LiTaO 3 or LTO)-On-Insulator (SiO 2 ) (LTOI) substrates [START_REF] Tauzin | [END_REF][START_REF] Gorisse | IEEE Intern. Ultrasonics Symposium (IUS)[END_REF] which are fabricated by film transfer using the Smart-Cut TM technology. [START_REF] Bruel | [END_REF] There, strain gradients are introduced unintentionally during the key process step based on H + ions implantation, which should impact LTOI devices performance.

When the [0001] c-axis is perpendicular to the wafer surface (Z-Cut orientation) and the implanted layer is pseudomorphic to a template, there is only one nonzero out-of-plane strain component of the extrinsic (reference to a template lattice) strain tensor, which can be directly measured. 10 Real devices require off-axis single crystals with the piezoelectric axis tilted away from the normal to the wafer surface and rotated around the [1 120] direction. 11 In that case, the surface does not correspond to any crystallographic plane (Fig. 1) and nonzero shear strain component appears in such coordinates system. Direct measurement of the out-of-plane and shear strain components is impossible in this system, unless they are reconstructed from measurable deformation of a) Author to whom correspondence should be addressed: nikolay.cherkashin@cemes.fr existing crystalline planes. However, such strain tensor reconstruction, especially as a function of depth, may not be that obvious to obtain and require some approximations. Various experimental techniques like Raman spectroscopy, 13 Quantitative Transmission Electron Microscopy (QTEM), [14][15][16][17] and X-ray Diffraction (XRD), 18 different in their precision, accuracy and sensitivity to depth distribution, allow the measurement of single plane deformation compared to some reference lattice present nearby. Reconstruction of an extrinsic then intrinsic 2D or 3D strain tensor defined with respect to its own unstrained lattice is a further step, which has not been proposed and challenges a development of dedicated experimental and theoretical protocol.

In this Letter, we present a theoretical protocol for the reconstruction of the extrinsic and intrinsic strain tensors in single-crystals, with an arbitrary oriented coordinate system, by using the measurement of lattice plane extrinsic deformations. The deformation is defined as extrinsic (intrinsic) when the reference and strained materials do not have (do have) the same structure and composition.

Reconstruction of depth resolved strain tensor in off-axis single crystals: application to H + ions implanted LiTaO 3 2 First, we construct reciprocal intrinsic and extrinsic continuum body cells that reflect the corresponding displacement gradients. Any reciprocal vector of the strained material is then expressed in units of intrinsic and extrinsic cells. From the measurement of crystallographic plane extrinsic deformations, we deduce the units of the extrinsic cell, then the coordinates of the strained reciprocal vectors and, finally, the units of the intrinsic cell. The units of the cells are used to calculate the corresponding extrinsic and intrinsic strain tensors.

The protocol is then applied to a practical case, an offaxis LTO 300 µm-thick substrate implanted over 1 µm depth with H + ions. Impact of H + ions implantation on the LTO properties is considered through the analysis of the extracted strain tensor depth distribution.

Begin by considering the intrinsic Lagrange strain tensor of a material body in real space, for an arbitrary oriented coordinate system x ′ y ′ z ′ , within the general finite strain theory, i.e. when large shape changes are expected. For the sake of simplicity, we describe the 2D strain tensor, here in the y ′ z ′ -plane. First, we choose an unstrained square-like body cell with dimensions dy ′ × dz ′ and sides parallel to y ′ and z ′ axes. One of its vertices is placed at the coordinate system origin (Fig. 2 The body is strained when the three other vertices of the cell are displaced in the y ′ z ′ -plane by u(y ′ , z ′ ) (Fig. 2(a), red solid lines). The vertex placed on the y ′ -axis is displaced in the y ′ direction by a quantity ∂u y ′ ∂y ′ dy ′ and in the z ′ direction by a quantity ∂u z ′ ∂y ′ dy ′ . The displacements of the vertex placed on the z ′ -axis can be described ac-cordingly by exchanging y ′ , z ′ indexes. The components of the Lagrange strain tensor are then given by the expressions

ε ij = 1 2 ( ∂ui ∂xj + ∂uj ∂xi + ∂uk ∂xj ∂uk ∂xi )
, where x i = y ′ and x j = z ′ , ε y ′ y ′ is in-plane strain, ε z ′ z ′ is out-of-plane strain, ε y ′ z ′ is shear strain. Note that the strained body cell like presented in Fig. 2(a) has a negative shear strain component.

Generally speaking, the strain tensor is deduced from the relative change of the body cell shape and, alternatively, can be described as a function of angles α and β and relative change in the distances between cell sides, from dy ′ to d 1 and from dz ′ to d 2 (Fig. 2(a)). From a practical point of view, such a change has to be preferentially introduced in reciprocal space. For this, we construct a reciprocal unstrained body cell with the dimensions i × j where i = j = 1 and sides i, j are aligned along y ′ and z ′ axes (Fig. 2(b)). When strained, the reciprocal body cell obtains the dimensions i S × j S where i S = dy ′ /d 1 , j S = dz ′ /d 2 and i S , j S are orthogonal to the z ′ S and y ′ S axes, respectively, which are aligned along the sides of the real space strained body cell. Figure 2(b) shows that i S and j S can be expressed in the (i, j) reference as

i S = i S y ′ i + i S z ′ j and j S = j S y ′ i + j S z ′ j. (1)
So, one set of reciprocal vectors (i, j) describes the unstrained cell and the other (i S , j S ) the strained one. Note that after real-to-reciprocal space transformation shear strain component inverts the sign. Using this formalism and correcting for the sign of shear strain component, all components of the intrinsic strain tensor can be redefined in reciprocal space as

ε y ′ y ′ =[ 1 i S -1] + [ 1 2 (( 1 i S -1) 2 + ( i S z ′ i S y ′ ) 2 )] , ε z ′ z ′ =[ 1 j S -1] + [ 1 2 (( 1 j S -1) 2 + ( j S y ′ j S z ′ ) 2 )] , ε y ′ z ′ =[- 1 2 ( i S z ′ i S y ′ + j S y ′ j S z ′ )]+ [- 1 2 (( 1 i S -1)( i S z ′ i S y ′ ) + ( 1 j S -1)( j S y ′ j S z ′ ))]. ( 2
)
The first terms in square brackets approximate the infinitesimal strain tensor valid for deformations which are much smaller than the body dimensions. In order to deduce such intrinsic strain tensor, the 4 coordinates of i S and j S should be determined as a function of measurable quantities. In practice, these are plane deformations determined with respect to a template lattice. First, one should link the continuum body reciprocal cell (i, j) to the periodic reciprocal lattice of the studied material. The latter is composed of reciprocal vectors characterized by proper hkl indexes and lattice parameters. Let's choose the orthogonal to y ′ z ′ -plane, the x ′axis, to be parallel to some zone axis of the lattice. Any This is the author's peer reviewed, accepted manuscript. However, the online version of record will be different from this version once it has been copyedited and typeset.

PLEASE CITE THIS ARTICLE AS DOI: 10.1063/5.0040729

Reconstruction of depth resolved strain tensor in off-axis single crystals: application to H + ions implanted LiTaO 3 3 reference reciprocal vector g hkl perpendicular to that zone axis can be expressed in units of the (i, j) cell as

g hkl = g hkl y ′ i + g hkl z ′ j (3)
with (g hkl y ′ , g hkl z ′ ) ∈ ℜ 2 (Fig. 2(b)). When the lattice is strained, this vector becomes g S hkl and is expressed in units of the (i S , j S ) cell as

g S hkl = g hkl y ′ i S + g hkl z ′ j S . (4)
Assignment of the identical numerical values of g hkl y ′ and g hkl z ′ in Eqs. ( 3) and ( 4) is imposed by the lattice periodicity.

Second, similarly, when the reference is changed to the template material lattice (Fig. 2(c)), the reference reciprocal vector is defined as

g T uvw = g T uvw y ′ i + g T uvw z ′ j, (5)
and the same g S hkl is redefined as a function of vectors i ST and j ST (the superscript ST stands for "strained" with reference to "template" lattice)

g S hkl = g T uvw y ′ i ST + g T uvw z ′ j ST . (6)
Note that application of such finite strain theory allows different crystal structures for the strained material and that of the template. However, when the strained layer and the template have at least similar structures, the infinitesimal strain is more convenient to apply, because it is linear. In that case, g T uvw must not be too different (in length and direction) to g hkl .

Finally, the measurable strain of the (hkl) plane with reference to the (uvw) one, the so-called plane extrinsic deformation, is defined by

ε T hkl = [ g T uvw g S hkl -1] + [ 1 2 ( g T uvw g S hkl -1) 2 ] (7)
The first term in square brackets describes the plane deformation in the frame of infinitesimal strain theory. By combining Eqs.( 1), ( 5), ( 6) and ( 7), it can be written

ε T hkl = [ g T uvw y ′ 2 + g T uvw z ′ 2 (g T uvw y ′ i ST y ′ + g T uvw z ′ j ST y ′ ) 2 + (g T uvw y ′ i ST z ′ + g T uvw z ′ j ST z ′ ) 2 -1] + [ 1 2 ( g T uvw y ′ 2 + g T uvw z ′ 2 (g T uvw y ′ i ST y ′ + g T uvw z ′ j ST y ′ ) 2 + (g T uvw y ′ i ST z ′ + g T uvw z ′ j ST z ′ ) 2 -1) 2 ]. (8)
Accordingly, by using the values of four plane deformations measured with reference to the template, the four coordinates of i ST and j ST are determined using Eq. ( 8). These quantities, when substituted for i S and j S in Eqs. (2), provide the extrinsic strain tensor with reference to a template lattice or, when substituted in Eqs.( 6) and equalizing Eq. ( 4) and Eqs.( 6), provide the coordinates of i S and j S . Finally, by substituting the latter into Eqs.(2) one can find the components of the intrinsic strain tensor.

In the following, we present an application of this method for the reconstruction of the depth-resolved strain tensor in off-axis Y42-Cut LTO wafer implanted with H + ions at room temperature (RT) at an energy of 110 keV with a fluence of 9×10 16 cm -2 . This particular off-axis orientation corresponds to the piezoelectric c-axis being rotated around the x=[1 120] direction by θ = 48 • . We choose the x ′ y ′ z ′ coordinate system with x ′ parallel to [1 120], z ′ normal to the wafer surface and y ′ normal to the x ′ z ′ -plane (Fig. 1(a)). Secondary Ion Mass Spectroscopy (SIMS) was used to measure hydrogen concentration as a function of depth. Hydrogen is distributed within a 900 nm-thick superficial layer (Fig. 3(b)). High Resolution XRD (HR-XRD) measurements were realized in skew geometry, in order to satisfy Bragg conditions for different (hkl) reflections. HR-XRD experimental curves were simulated by using RaDMaX software. 19 One would expect the implanted layer to be pseudomorphic to the substrate and weakly strained similarly to the situation observed for other implanted materials 18,20 and epitaxially grown layers. 21 As a consequence, all crystallographic directions and interplanar distances of the implanted layer should coincide in the x ′ y ′ -plane with that of the substrate. Thus, one can set i ST = i and g T uvw = g T hkl as represented in Fig. 2(d). That reduces the number of unknown parameters, namely the coordinates of j ST , to 2. Using the approximation of infinitesimal strain theory valid for weak strains, Eq. ( 8) is simplified to a form

ε T hkl = g T hkl y ′ 2 + g T hkl z ′ 2 (g T hkl y ′ + g T hkl z ′ j ST y ′ ) 2 + (g T hkl z ′ j ST z ′ ) 2 -1, ( 9
)
which indicates that, in the present application, measurement of only two plane deformations is sufficient for the determination of j ST . Note that here g T hkl =g T hkil are those of pristine hexagonal LTO (space group: R3C, a T = 5.1542 Å, c T = 13.783 Å measured at RT in this study) with

g T hkil 2 = 4 3
h 2 + hk + k 2 a T 2 + l 2 c T 2 . ( 10
)
Following the procedure described above, the strain tensor with respect to the template lattice has been determined. First, XRD spectra were obtained for g 2204 , g 00012 and g 1108 making an angle of 9 • , 48 • and 27 • with the normal to the wafer surface, respectively. As described in the Supplementary Material, plane deformation profiles along corresponding g T hkil directions were extracted from RaDMaX simulations and then recalculated as a function of z ′ -depth. This is the author's peer reviewed, accepted manuscript. However, the online version of record will be different from this version once it has been copyedited and typeset.

PLEASE CITE THIS ARTICLE AS DOI: 10.1063/5.0040729

Reconstruction of depth resolved strain tensor in off-axis single crystals: application to H + ions implanted LiTaO 3 4

Figure 3(a) shows the resulting ε T 2204 (z ′ ) (red) , ε T 00012 (z ′ ) (blue) and ε T 1108 (z ′ ) (green) profiles. The profiles have a similar shape with non zero values at the surface and a maximum value at the same depth of ≈ 720 nm. ε T 2204 (z ′ ) and ε T 00012 (z ′ ) were used to calculate j ST y ′ (z ′ ) and j ST z ′ (z ′ ). We verified our hypothesis of a layer pseudomorphic to the substrate (see Supplementary material) by comparing reconstructed ε T,simu 1108 (z ′ ) with that obtained experimentally (Fig. 3(a), green). The very good agreement between these two profiles proves the robustness of the hypothesis and the absence of in-plane plastic relaxation, i.e. ε T y ′ y ′ is equal to zero all over the depth. The remaining unknown components of 2D strain tensor defined with reference to the LTO lattice were then calculated by substituting j ST y ′ (z ′ ) and j ST z ′ (z ′ ) in Eqs. (2). The resulting ε T z ′ z ′ (z ′ ) and ε T y ′ z ′ (z ′ ) are plotted in Fig. 3(b). There are gradually changing negative shear strain and tensile out-of-plane strain in the implanted layer. The negative values of ε T y ′ z ′ (z ′ ) indicate that the body cell is more strongly tensile strained along the caxis rather than the a-axis like shown in Fig. 2(a). Surprisingly, both ε T z ′ z ′ (z ′ ) and ε T y ′ z ′ (z ′ ) start with non zero values of 0.5% and -0.3% at the surface, increase in amplitude until reaching a maximum value of 1.5% and -1.3% at a depth of ≈720 nm, respectively, then rapidly fall down within a distance of 300 nm. Note that in piezoelectric actuators, strain induced by electric field when exceeding 0.5% is considered giant. 22 One would expect strain to be directly related to local hydrogen concentration like observed in H + ions implanted Si 23,24 . Here, strain profiles being compared to H depth distribution (Fig. 3(b), blue line) only partly support such hypothesis. The depth where strain and H reach their maximum values is the same (the observed peak valley is considered to be a SIMS measurement artifact likely related to the presence of molecular H 2 25 ). However, while there is almost no hydrogen near the surface, lattice is still considerably strained there. These data that became accessible only by properly calculating the strain tensor using the analytical model presented in this Letter, strongly support the idea that the implanted layer is no more composed of pristine LTO but of a complex LTO-like alloy with its own gradually changing composition, lattice parameters and elastic constants.

In order to reconstruct intrinsic strain tensor (Eq. ( 2)), a and c lattice parameters of the alloy should be known (Eq. ( 4)), which is not the case here. To find these parameters, one can combine our protocol with elasticity theory. Stress and strain are related through elastic constants by σ i

′ j ′ = C i ′ j ′ k ′ l ′ .ε k ′ l ′ where C i ′ j ′ k ′ l ′
is the fourth order stiffness tensor defined in this particular x ′ y ′ z ′ coordinate system. In case of in-plane biaxially stressed layer where no force is applied in the z ′ direction, the boundary conditions, σ z ′ z ′ = 0 and σ y ′ z ′ = 0, are applied. These two equations link strain components through elastic constants that allows two unknown parameters to be restored. To begin with, we supposed that elastic constants of the alloy equal that of pristine LTO. Within such first order approximation, alloy lattice parameters were calculated. At H maximum concentration, a is found to be larger by 19% and c lower by 24.5% than those of pristine LTO. Such differences would impose a drastic change of the implanted LTO structure 26 while it is not confirmed by our X-ray diffraction data. Thus, a change in the elastic constants of the implanted layer should be taken into account as well. Some independent in-plane stress measurements 27 could further reduce the number of unknown parameters. But it comes out of the scope of the present Letter. Anyway, our finding strongly supports the idea that H + ions implantation in LTO gradually modifies composition, lattice parameters and elastic constants of the material.

In the context of a growing interest in strain tensor determination in off-axis crystals, in particular, in piezoelectric and ferroelectric materials, we provided an analytical and experimental protocol for the calculation of the 2D finite strain tensor first with reference to a template lattice and then to its unstrained state (intrinsic strain tensor) regardless of crystal orientation. This method requires a measurement of some (maximum 4) plane deformations with reference to a template lattice. The method was applied to successfully reconstruct the Reconstruction of depth resolved strain tensor in off-axis single crystals: application to H + ions implanted LiTaO 3 5 strain tensor depth distribution in H + ions implanted offaxis single LTO crystal, with reference to the LTO lattice. Zero in-plane, strong gradually changing negative shear and tensile out-of-plane strain were demonstrated in the implanted layer. Our experiment highlighted a non-direct relation between hydrogen concentration and strain indicating a complex composition and, thus, lattice parameters and elastic constants modification in such piezoelectric material.

The robustness of the approach was approved when applied for prediction of a single plane deformation profile. The method is perfectly compatible with QTEM techniques used for plane deformation measurements. 28 The protocol is applicable to any type of crystalline materials. Finally, the principles of the method can be easily extended for reconstruction of a 3D strain tensor.

SUPPLEMENTARY MATERIAL.

See Supplementary Materials [URL will be inserted by publisher] for a more detailed information on XRD experiments and associated RaDMaX simulations, as well as a more detailed explanation on the verification of our hypothesis of a layer pseudomorphic to the substrate.

12

 12

FIG. 1 .

 1 FIG. 1. LTO Y42-Cut viewed along the [1 120] direction: (a) Right-handed coordinate systems with crystallographic directions in the implanted wafer and (b) atomic structure and orientation of some studied planes.

  (a), black dashed lines).

FIG. 2 .

 2 FIG. 2. Unstrained and strained continuum body cells represented: (a) in real space, (b)-(d) in reciprocal space. Unstrained and strained reciprocal lattice vectors represented in units of the continuum body cells: (b) intrinsic case, (c) extrinsic case, (d) a layer pseudomorphic to its substrate. Black, blue and red stand for unstrained, extrinsic strained and intrinsic strained, respectively.

FIG. 3 .

 3 FIG. 3. (a) Plane deformations and (b) strain tensor components with H concentration as a function of z ′ -depth obtained for a Y42-Cut LTO wafer implanted with H + ions.

ACKNOWLEDGEMENTS

The authors acknowledge useful discussions with Didier Landru from Soitec and Alain Claverie from CEMES. We also would like to thank the Laboratoire de Physique et Chimie des Nano-objets for providing access to XRD facilities (Toulouse, France).

DATA AVAILABILITY

The data that support the findings of this study are available from the corresponding author upon reasonable request.