pith. machine review for the scientific record. sign in

arxiv: 2605.04975 · v1 · submitted 2026-05-06 · 💻 cs.CR

Recognition: unknown

Probabilistic Atomic Swaps for Bitcoin and Friends

Paul Gerhart , Jay Taylor , Sri Aravinda Krishnan Thyagarajan
Authors on Pith no claims yet

Pith reviewed 2026-05-08 17:03 UTC · model grok-4.3

classification 💻 cs.CR
keywords probabilistic atomic swapsadaptor signaturesoblivious pseudorandom functionsBitcoincross-chain swapsrandomized exchangetrustless lotteries
0
0 comments X

The pith

Probabilistic swaps extend atomic swaps so one party's transfer occurs with a fixed public probability that neither side can bias or predict.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a new primitive for trustless randomized exchanges across blockchains, such as lotteries or probabilistic allocations, where atomicity is relaxed to a verifiable probability rather than an all-or-nothing outcome. It does so by composing adaptor signatures with oblivious pseudorandom functions to embed the probability in the protocol while keeping both parties from learning or influencing the result beforehand. The construction reuses standard Bitcoin scripts and timelocks, so it adds no extra on-chain data beyond ordinary atomic swaps and produces transactions that look identical to normal ones. Formal security arguments and working implementations on Bitcoin testnet and Lightning Network are supplied to show the approach is practical and deployable on any chain that already supports atomic swaps.

Core claim

We introduce probabilistic swaps, a cryptographic primitive in which one party's asset transfer executes with a fixed, publicly specified probability that is embedded in the protocol and cannot be biased by either participant; the construction combines adaptor signatures with oblivious pseudorandom functions to realize this unbiased outcome, introduces an auxiliary mechanism for atomic exchange of OPRF evaluations, and preserves the minimal on-chain footprint of standard atomic-swap protocols while remaining compatible with existing Bitcoin scripts.

What carries the argument

Adaptor signatures combined with oblivious pseudorandom functions (OPRFs) to enforce an unbiased, publicly verifiable probability through atomic exchange of OPRF evaluations.

If this is right

  • Trustless lotteries and randomized cross-chain allocations become possible without intermediaries.
  • The same on-chain footprint as ordinary atomic swaps allows immediate deployment on Bitcoin and Lightning.
  • Transactions remain indistinguishable from standard ones, preserving privacy and fungibility.
  • A new auxiliary primitive for atomic OPRF evaluation exchange is available for other protocols.
  • Formal security definitions support the claim that neither party can bias the embedded probability.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The OPRF-exchange mechanism could be reused in other settings that need private yet verifiable randomness tied to payments.
  • Probabilistic swaps open a route to decentralized mechanisms for fair random allocation of scarce on-chain resources.
  • The approach could be generalized to multi-party probabilistic exchanges if the OPRF composition extends cleanly.

Load-bearing premise

Adaptor signatures and OPRFs can be composed so that the resulting probability is fixed, publicly verifiable, and immune to prediction or bias by either participant.

What would settle it

Multiple executions of the protocol on Bitcoin testnet in which the observed frequency of the probabilistic transfer deviates from the specified probability by more than statistical sampling error, or in which one party succeeds in forcing a particular outcome.

Figures

Figures reproduced from arXiv: 2605.04975 by Jay Taylor, Paul Gerhart, Sri Aravinda Krishnan Thyagarajan.

Figure 1
Figure 1. Figure 1: Ideal functionality F B ProSwap for probabilistic swaps. The dealer inputs ν coins and the party inputs one coin. The functionality samples b ←$ Bernoulli(p) and always transfers one coin to the dealer. If b = 1, the party receives ν coins; otherwise, the dealer is refunded its ν coins. Probabilistic swaps subsume atomic swaps [61] when setting p = 1 = ν. 2 view at source ↗
Figure 2
Figure 2. Figure 2: Transaction output using BIP 65. This output can be spent by pktmp at any time, and by pk after time T. 3 Solution Overview Before presenting our solution for probabilistic swap protocols, let us first recall our setting. We consider two entities, a dealer and a party, who wish to engage in a coin exchange with asymmetric and probabilistic outcomes. In contrast to deterministic atomic swaps, the dealer rec… view at source ↗
Figure 3
Figure 3. Figure 3: The dealer acts as the OPRF server. The party submits guesses ygss,0, ytgt, ygss,2 and obtains the corresponding OPRF outputs. Only one guess ytgt corresponds to a valid witness ywin; the remaining outputs (red, dashed) are invalid. This is where adaptor signatures enter again. The party prepares the dealer’s payment transaction σePD, but using the ephemeral key Z as the adaptor statement and sends the res… view at source ↗
Figure 4
Figure 4. Figure 4: Protocol overview. (1) D sends Ywin, binding ytgt under its OPRF key. (2) P sends a blinded OPRF request for its hidden guess ygss. (3) D returns an OPRF response encrypted under ephemeral key Z, and pre-signs P’s reward w.r.t. Ywin. (4) P pre-signs D’s payment w.r.t. Z; D posts it on-chain, revealing z. P extracts z, decrypts the response, and adapts σeDP to claim the reward iff ygss = ytgt. 3.4 Proving W… view at source ↗
Figure 5
Figure 5. Figure 5: The ideal functionality F B ProSwap. Other key differences with the functionality of [61]. While our functionality follows the high-level structure of [61], we introduce several modifications that facilitate practical realizations. Refunds. The functionality of [61] assumes that funds can be atomically unfrozen. In most protocols, however, refunding requires active participation of the party controlling th… view at source ↗
Figure 6
Figure 6. Figure 6: Two-party DLog keypair generation functionality. sampled uniformly at random. In particular, this enables us to learn the adversarial share of the secret key while determining the joint public key, which will be crucial in the security proof. We formalize the standard protocol realizing this two-party key generation functionality in view at source ↗
Figure 7
Figure 7. Figure 7: Two-Party protocol ΓDL for generating a DLog keypair. C.f view at source ↗
Figure 8
Figure 8. Figure 8: Two-Party Schnorr pre-signing protocol ΓpSign. Protocol description. Using the above building blocks, we can describe our probabilistic atomic swap protocol. The protocol reads as public input a buyout amount νD, a winning probability p = 1/m, the dealer’s public key pkD, the counterparty’s public key pkP , and two timeout parameters TD and TP. The protocol’s output is a reallocation of the dealer’s and pl… view at source ↗
Figure 9
Figure 9. Figure 9: Our probabilistic atomic swap protocol from adaptor signatures and oblivious pseudorandom functions for exchange probabilities in the powers of two. 15 view at source ↗
Figure 10
Figure 10. Figure 10: Performance and proof size for different instantiations of the well-formedness proof of Ywin. The parameter ℓ corresponds to the winning party’s probability via p = 2−ℓ . Cross-chain swap: Bitcoin × Litecoin. To test the cross-chain variant from Section 6, we ran the protocol on Bitcoin testnet4 and Litecoin testnet. Both chains support Taproot Schnorr spends over secp256k1, so the same adaptor-signature … view at source ↗
Figure 11
Figure 11. Figure 11: Request privacy, uniqueness, and pseudorandomness experiments for OPRFs. For the security proof of our theorem, we require non-blackbox access to the underlying structure of the OPRF. In particular, our simulator needs to be able to program the OPRF output to a target value. To allow this, we restrict our theorem to the family of two-hash OPRFs, which all share the same structure. We follow the abstractio… view at source ↗
Figure 12
Figure 12. Figure 12: Pseudorandomness experiment for OPRFs. Our modified 2HashDH OPRF. To enable cut-and-choose proofs, we slightly modify the 2HashDH OPRF construction, such that the dealer can provide openings without revealing the OPRF evaluation’s message. In particular, our OPRF has the following form: Let G be a cyclic group of prime order p, and let Hp and HG be hash functions mapping to Zp and G, respectively. The pub… view at source ↗
Figure 13
Figure 13. Figure 13: The security game ExtA,AS(λ). Definition 3 (Pre-signature adaptability). An adaptor signature scheme AS satisfies pre-signature adaptability, if for all λ ∈ N, messages m ∈ {0, 1} ∗ , statement/witness pairs (Y, y) ∈ R, public keys pk and pre-signatures σe ∈ {0, 1} ∗ we have pVrfy(pk, m, Y, σe) = 1, then Vrfy(pk, m,Adapt(pk, σ, y e )) = 1. A.1 Non-interactive Arguments We follow the notion of [26]. A non-… view at source ↗
Figure 14
Figure 14. Figure 14: Interactive Schnorr proof for the relation REnc. Proofs of knowledge for commitment-opening, and secret keys. The relation RC is satisfied, if a party knows an opening (sk, ω) for a commitment C = g skh ω. The relation RDL is satisfied if a party knows the discrete logarithm sk of a group element pk. RC :=  x = (C, G, g, h) w = (sk, ω) : C = g skh ω  RDL :=  x = (pk, G, g) w = sk : pk = g sk  We depic… view at source ↗
Figure 15
Figure 15. Figure 15: Interactive Schnorr proof for the relation RC. Lemma 2. The cut-and-choose protocol in view at source ↗
Figure 16
Figure 16. Figure 16: Interactive Schnorr proof for the relation RDL. Public inputs: a group (G, g, p), and hash functions HG : {0, 1} ∗ → G, Hp : {0, 1} ∗ → Zp, and a statement x = (pk, Ywin, ℓ). The prover provides w = (sk, ytgt) as additional input, and the verifier has no additional input. Proving: 1. The prover samples scalars (α1, . . . , αλ, r1, . . . , rλ) ←$ Zp, computes the λ commitments n Hp view at source ↗
Figure 17
Figure 17. Figure 17: Interactive cut-and-choose proof for Rwin. 33 view at source ↗
Figure 18
Figure 18. Figure 18: Interactive Schnorr OR proof for well-formedness of cut-and-choose openings ( view at source ↗
Figure 19
Figure 19. Figure 19: Interactive Schnorr OR proof that (U, V ) is well formed as U = u ρ and V = h sk y · g ρ for some y ∈ {0, 1} ℓ . 36 view at source ↗
Figure 20
Figure 20. Figure 20: Interactive Chaum–Pedersen proof for well-formedness of (X, Y ) with hidden base h. 37 view at source ↗
read the original abstract

Atomic swaps are a fundamental primitive for the trustless exchange of digital assets across blockchains: they guarantee that either both parties receive the agreed assets or neither party transfers. While this all-or-nothing guarantee is powerful, it also imposes an inherent determinism that rules out exchanges whose intended outcome is probabilistic. As a result, existing atomic swaps cannot realize trustless exchanges in which one party pays for a fixed chance of receiving a larger asset or reward, as in lotteries, randomized allocation mechanisms, and probabilistic cross-chain trades. We introduce probabilistic swaps, a new cryptographic primitive that extends atomic swaps to the probabilistic setting. In a probabilistic swap, one party's transfer is executed with a fixed, publicly specified probability embedded in the protocol and cannot be biased by either party. This yields a trustless mechanism for randomized exchange with verifiable odds and no trusted intermediary. Our construction combines adaptor signatures with oblivious pseudorandom functions (OPRFs) to realize the desired probabilistic outcome while ensuring that neither party can predict or bias it in advance. Along the way, we introduce a new mechanism for the atomic exchange of OPRF evaluations for payments, which may be of independent interest. A key feature of our approach is that it preserves the minimal on-chain footprint of modern atomic-swap protocols. The protocol relies only on standard Bitcoin scripts, such as digital signatures and timelocks, and is deployable on any blockchain that already supports atomic swaps. Consequently, probabilistic swaps are indistinguishable from ordinary on-chain transactions, which helps preserve privacy and fungibility. We provide formal security foundations and demonstrate practicality through a probabilistic swap in the Bitcoin testnet and in the Lightning Network.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces probabilistic atomic swaps as an extension of atomic swaps, enabling trustless exchanges where one party's transfer executes with a fixed, publicly specified probability p that cannot be biased by either party. The construction combines adaptor signatures with oblivious pseudorandom functions (OPRFs) and introduces a new atomic exchange mechanism for OPRF evaluations; it claims formal security foundations and demonstrates the protocol via a Bitcoin testnet implementation and Lightning Network deployment using only standard scripts such as signatures and timelocks.

Significance. If the security claims hold, the work enables new applications including trustless lotteries, randomized allocations, and probabilistic cross-chain trades without intermediaries. The preservation of minimal on-chain footprint and indistinguishability from ordinary transactions are practical strengths that could extend the applicability of atomic-swap infrastructure while maintaining privacy and fungibility.

major comments (2)
  1. [§4] §4 (Atomic OPRF Exchange Mechanism): The load-bearing claim that the new atomic exchange of OPRF evaluations enforces an unbiased probability p rests on the composition preserving the OPRF output distribution under adaptor-signature locking; however, the description does not detail how Bitcoin-script timelocks and signature verification interact with the OPRF to prevent early revelation or bias by an adaptive party.
  2. [§5] §5 (Security Foundations): The formal security reduction for the probabilistic swap is asserted to follow from the security of adaptor signatures and OPRFs, but the proof sketch does not explicitly address whether the custom atomic-exchange sub-protocol preserves both atomicity and the exact uniform distribution of the OPRF output in the presence of concurrent executions or script-specific constraints.
minor comments (2)
  1. [§6] The testnet demonstration would be strengthened by reporting the empirical distribution of outcomes over multiple runs to allow direct verification that the realized probability matches the specified p.
  2. Notation for the probability parameter p and the OPRF evaluation output could be introduced more explicitly in the preliminaries to improve readability for readers unfamiliar with the composition.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive and detailed feedback. We address each major comment below and indicate the specific revisions planned for the next version of the manuscript.

read point-by-point responses

  1. Referee: [§4] §4 (Atomic OPRF Exchange Mechanism): The load-bearing claim that the new atomic exchange of OPRF evaluations enforces an unbiased probability p rests on the composition preserving the OPRF output distribution under adaptor-signature locking; however, the description does not detail how Bitcoin-script timelocks and signature verification interact with the OPRF to prevent early revelation or bias by an adaptive party.

    Authors: We agree that the current description in §4 would benefit from greater explicitness on the interaction between adaptor signatures, OPRF outputs, timelocks, and signature verification. In the revised manuscript we will augment §4 with a precise transaction-sequence diagram and accompanying prose that shows: (1) how the adaptor-signature lock is placed on the OPRF evaluation result, (2) the role of the timelock in preventing premature revelation of the OPRF output, and (3) why an adaptive party cannot bias the outcome or extract the output before the protocol reaches the intended phase. These additions will make the preservation of the uniform distribution under the Bitcoin-script constraints explicit. revision: yes

  2. Referee: [§5] §5 (Security Foundations): The formal security reduction for the probabilistic swap is asserted to follow from the security of adaptor signatures and OPRFs, but the proof sketch does not explicitly address whether the custom atomic-exchange sub-protocol preserves both atomicity and the exact uniform distribution of the OPRF output in the presence of concurrent executions or script-specific constraints.

    Authors: We acknowledge that the security reduction sketch in §5 is currently high-level and does not spell out the composition with the atomic-exchange sub-protocol under concurrency or script constraints. We will expand the proof sketch to include: (i) a modular argument showing that atomicity is inherited from the underlying adaptor-signature and OPRF definitions, (ii) an explicit claim that the uniform distribution of the OPRF output is preserved because the only way the output becomes public is through the locked adaptor-signature path, and (iii) a brief discussion of why concurrent executions and Bitcoin-script execution semantics do not introduce additional leakage or bias. We believe these clarifications can be added without altering the core claims. revision: yes

Circularity Check

0 steps flagged

No circularity: new composition of independent primitives with claimed formal security

full rationale

The paper defines probabilistic swaps as a new primitive extending atomic swaps via a combination of adaptor signatures and OPRFs, plus a novel atomic OPRF-evaluation exchange mechanism. It explicitly states that the construction relies on the standard security properties of these existing primitives and provides formal security foundations. No equations, definitions, or self-citations in the abstract or described structure reduce the central claim to a fitted input, self-definition, or load-bearing prior result by the same authors. The derivation chain is self-contained against external cryptographic assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The abstract relies on standard cryptographic assumptions for adaptor signatures and OPRFs; no free parameters, new invented entities, or ad-hoc axioms are introduced in the provided text.

axioms (1)
  • domain assumption Security properties of adaptor signatures and oblivious pseudorandom functions hold under standard cryptographic assumptions
    The protocol's bias-resistance and atomicity claims depend on these primitives behaving as expected in the described composition.

pith-pipeline@v0.9.0 · 5600 in / 1268 out tokens · 64472 ms · 2026-05-08T17:03:37.473957+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

95 extracted references · 46 canonical work pages

  1. [1]

    Emulating op_rand in bitcoin.https://delvingbitcoin.org/t/emulating-op-rand/1409/5(2025), delving Bitcoin forum discussion

    2025

  2. [2]

    In: Lie, D., Mannan, M., Backes, M., Wang, X

    Agrawal, S., Miao, P., Mohassel, P., Mukherjee, P.: PASTA: PASsword-based threshold authentication. In: Lie, D., Mannan, M., Backes, M., Wang, X. (eds.) ACM CCS 2018. pp. 2042–2059. ACM Press (Oct 2018).https: //doi.org/10.1145/3243734.3243839

    work page doi:10.1145/3243734.3243839 2018

  3. [3]

    In: 2014 IEEE Symposium on Security and Privacy

    Andrychowicz, M., Dziembowski, S., Malinowski, D., Mazurek, L.: Secure multiparty computations on Bitcoin. In: 2014 IEEE Symposium on Security and Privacy. pp. 443–458. IEEE Computer Society Press (May 2014). https://doi.org/10.1109/SP.2014.35

    work page doi:10.1109/sp.2014.35 2014

  4. [4]

    In: Tibouchi, M., Wang, H

    Aumayr, L., Ersoy, O., Erwig, A., Faust, S., Hostáková, K., Maffei, M., Moreno-Sanchez, P., Riahi, S.: Gen- eralized channels from limited blockchain scripts and adaptor signatures. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021, Part II. LNCS, vol. 13091, pp. 635–664. Springer, Cham (Dec 2021).https://doi.org/10. 1007/978-3-030-92075-3_22

    2021

  5. [5]

    In: Yin, H., Stavrou, A., Cremers, C., Shi, E

    Aumayr, L., Thyagarajan, S.A.K., Malavolta, G., Moreno-Sanchez, P., Maffei, M.: Sleepy channels: Bi-directional payment channels without watchtowers. In: Yin, H., Stavrou, A., Cremers, C., Shi, E. (eds.) ACM CCS 2022. pp. 179–192. ACM Press (Nov 2022).https://doi.org/10.1145/3548606.3559370

    work page doi:10.1145/3548606.3559370 2022

  6. [6]

    In: Kalai, Y.T., Kamara, S.F

    Badertscher, C., Campanelli, M., Ciampi, M., Russo, L., Siniscalchi, L.: Universally composable SNARKs with transparent setup without programmable random oracle. In: Kalai, Y.T., Kamara, S.F. (eds.) CRYPTO 2025, Part VII. LNCS, vol. 16006, pp. 225–258. Springer, Cham (Aug 2025).https://doi.org/10. 1007/978-3-032-01907-3_8

    2025

  7. [7]

    Cryptology ePrint Archive, Report 2025/388 (2025),https://eprint.iacr.org/ 2025/388

    Baecker, R., Gerhart, P., Katz, J., Schröder, D.: Fair exchange for decentralized autonomous organizations via threshold adaptor signatures. Cryptology ePrint Archive, Report 2025/388 (2025),https://eprint.iacr.org/ 2025/388

    2025

  8. [8]

    In: Financial Cryptography and Data Security

    Bartoletti, M., Zunino, R.: Constant-deposit multiparty lotteries on bitcoin. In: Financial Cryptography and Data Security. pp. 231–247. Springer International Publishing, Cham (2017)

    2017

  9. [9]

    In: Fehr, S., Fouque, P.A

    Basso, A., Maino, L.: POKÉ: A compact and efficient PKE from higher-dimensional isogenies. In: Fehr, S., Fouque, P.A. (eds.) EUROCRYPT 2025, Part II. LNCS, vol. 15602, pp. 94–123. Springer, Cham (May 2025). https://doi.org/10.1007/978-3-031-91124-8_4

    work page doi:10.1007/978-3-031-91124-8_4 2025

  10. [10]

    In: Garay, J.A., Gennaro, R

    Bentov, I., Kumaresan, R.: How to use Bitcoin to design fair protocols. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part II. LNCS, vol. 8617, pp. 421–439. Springer, Berlin, Heidelberg (Aug 2014).https://doi. org/10.1007/978-3-662-44381-1_24

    work page doi:10.1007/978-3-662-44381-1_24 2014

  11. [11]

    Beullens, L

    Beullens, W., Dodgson, L., Faller, S.H., Hesse, J.: The 2Hash OPRF framework and efficient post-quantum instantiations. In: Fehr, S., Fouque, P.A. (eds.) EUROCRYPT 2025, Part VIII. LNCS, vol. 15608, pp. 332–362. Springer, Cham (May 2025).https://doi.org/10.1007/978-3-031-91101-9_12

    work page doi:10.1007/978-3-031-91101-9_12 2025

  12. [12]

    Bitcoin Optech: Point time-locked contracts (ptlcs).https://bitcoinops.org/en/topics/ptlc/, accessed: 2026- 04-27

    2026

  13. [13]

    In: 20th ACM STOC

    Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications (extended abstract). In: 20th ACM STOC. pp. 103–112. ACM Press (May 1988).https://doi.org/10.1145/62212.62222

    work page doi:10.1145/62212.62222 1988

  14. [14]

    In: 2018 IEEE Symposium on Security and Privacy

    Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs: Short proofs for confidential transactions and more. In: 2018 IEEE Symposium on Security and Privacy. pp. 315–334. IEEE Computer Society Press (May 2018).https://doi.org/10.1109/SP.2018.00020

    work page doi:10.1109/sp.2018.00020 2018

  15. [15]

    In: Ray, I., Li, N., Kruegel, C

    Camenisch, J., Lehmann, A., Neven, G.: Optimal distributed password verification. In: Ray, I., Li, N., Kruegel, C. (eds.) ACM CCS 2015. pp. 182–194. ACM Press (Oct 2015).https://doi.org/10.1145/2810103.2813722

    work page doi:10.1145/2810103.2813722 2015

  16. [16]

    In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D

    Choudhuri, A.R., Green, M., Jain, A., Kaptchuk, G., Miers, I.: Fairness in an unfair world: Fair multiparty computation from public bulletin boards. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017. pp. 719–728. ACM Press (Oct / Nov 2017).https://doi.org/10.1145/3133956.3134092

    work page doi:10.1145/3133956.3134092 2017

  17. [17]

    In: Handschuh, H., Lysyanskaya, A

    Davies, G.T., Faller, S.H., Gellert, K., Handirk, T., Hesse, J., Horváth, M., Jager, T.: Security analy- sis of the WhatsApp end-to-end encrypted backup protocol. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023, Part IV. LNCS, vol. 14084, pp. 330–361. Springer, Cham (Aug 2023).https://doi.org/10. 1007/978-3-031-38551-3_11 24

    2023

  18. [18]

    In: Kilian, J

    De Santis, A., Di Crescenzo, G., Ostrovsky, R., Persiano, G., Sahai, A.: Robust non-interactive zero knowledge. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 566–598. Springer, Berlin, Heidelberg (Aug 2001). https://doi.org/10.1007/3-540-44647-8_33

    work page doi:10.1007/3-540-44647-8_33 2001

  19. [19]

    In: Chen, L., Li, N., Liang, K., Schneider, S.A

    Esgin, M.F., Ersoy, O., Erkin, Z.: Post-quantum adaptor signatures and payment channel networks. In: Chen, L., Li, N., Liang, K., Schneider, S.A. (eds.) ESORICS 2020, Part II. LNCS, vol. 12309, pp. 378–397. Springer, Cham (Sep 2020).https://doi.org/10.1007/978-3-030-59013-0_19

    work page doi:10.1007/978-3-030-59013-0_19 2020

  20. [20]

    Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. Commun. ACM28(6), 637–647 (Jun 1985).https://doi.org/10.1145/3812.3818,https://doi.org/10.1145/3812.3818

    work page doi:10.1145/3812.3818 1985

  21. [21]

    In: Jung, J., Holz, T

    Everspaugh, A., Chatterjee, R., Scott, S., Juels, A., Ristenpart, T.: The pythia PRF service. In: Jung, J., Holz, T. (eds.) USENIX Security 2015. pp. 547–562. USENIX Association (Aug 2015),https://www.usenix.org/ conference/usenixsecurity15/technical-sessions/presentation/everspaugh

    2015

  22. [22]

    In: Galbraith, S.D., Nandi, M

    Faust, S., Kohlweiss, M., Marson, G.A., Venturi, D.: On the non-malleability of the Fiat-Shamir transform. In: Galbraith, S.D., Nandi, M. (eds.) INDOCRYPT 2012. LNCS, vol. 7668, pp. 60–79. Springer, Berlin, Heidelberg (Dec 2012).https://doi.org/10.1007/978-3-642-34931-7_5

    work page doi:10.1007/978-3-642-34931-7_5 2012

  23. [23]

    In: Odlyzko, A.M

    Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO’86. LNCS, vol. 263, pp. 186–194. Springer, Berlin, Heidelberg (Aug 1987).https: //doi.org/10.1007/3-540-47721-7_12

    work page doi:10.1007/3-540-47721-7_12 1987

  24. [24]

    In: Kilian, J

    Freedman, M.J., Ishai, Y., Pinkas, B., Reingold, O.: Keyword search and oblivious pseudorandom functions. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 303–324. Springer, Berlin, Heidelberg (Feb 2005).https: //doi.org/10.1007/978-3-540-30576-7_17

    work page doi:10.1007/978-3-540-30576-7_17 2005

  25. [25]

    In: Stern, J

    Gennaro, R., Jarecki, S., Krawczyk, H., Rabin, T.: Secure distributed key generation for discrete-log based cryptosystems. In: Stern, J. (ed.) EUROCRYPT’99. LNCS, vol. 1592, pp. 295–310. Springer, Berlin, Heidelberg (May 1999).https://doi.org/10.1007/3-540-48910-X_21

    work page doi:10.1007/3-540-48910-x_21 1999

  26. [26]

    In: Advances in Cryptology – EUROCRYPT 2026

    Gerhart, P., Calsi, D.L., Russo, L., Schröder, D.: Fully-adaptive two-round threshold schnorr signatures from DDH. In: Advances in Cryptology – EUROCRYPT 2026. Lecture Notes in Computer Science, Springer (2026)

    2026

  27. [27]

    In: Proceedings of the 2026 ACM SIGSAC Conference on Computer and Communications Security

    Gerhart, P., Rausch, D., Schröder, D.: Universally composable adaptor signatures. In: Proceedings of the 2026 ACM SIGSAC Conference on Computer and Communications Security. Association for Computing Machinery (2026)

    2026

  28. [28]

    (eds.) EUROCRYPT 2024, Part II

    Gerhart,P.,Schröder,D.,Soni,P.,Thyagarajan,S.A.K.:Foundationsofadaptorsignatures.In:Joye,M.,Leander, G. (eds.) EUROCRYPT 2024, Part II. LNCS, vol. 14652, pp. 161–189. Springer, Cham (May 2024).https: //doi.org/10.1007/978-3-031-58723-8_6

    work page doi:10.1007/978-3-031-58723-8_6 2024

  29. [29]

    In: Yin, H., Stavrou, A., Cremers, C., Shi, E

    Glaeser, N., Maffei, M., Malavolta, G., Moreno-Sanchez, P., Tairi, E., Thyagarajan, S.A.K.: Foundations of coin mixing services. In: Yin, H., Stavrou, A., Cremers, C., Shi, E. (eds.) ACM CCS 2022. pp. 1259–1273. ACM Press (Nov 2022).https://doi.org/10.1145/3548606.3560637

    work page doi:10.1145/3548606.3560637 2022

  30. [30]

    In: 17th ACM STOC

    Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems (extended ab- stract). In: 17th ACM STOC. pp. 291–304. ACM Press (May 1985).https://doi.org/10.1145/22145.22178

    work page doi:10.1145/22145.22178 1985

  31. [31]

    In: Handschuh, H., Lysyanskaya, A

    Golovnev, A., Lee, J., Setty, S.T.V., Thaler, J., Wahby, R.S.: Brakedown: Linear-time and field-agnostic SNARKs for R1CS. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023, Part II. LNCS, vol. 14082, pp. 193–226. Springer, Cham (Aug 2023).https://doi.org/10.1007/978-3-031-38545-2_7

    work page doi:10.1007/978-3-031-38545-2_7 2023

  32. [32]

    In: Katz, J., Shacham, H

    Groth, J., Maller, M.: Snarky signatures: Minimal signatures of knowledge from simulation-extractable SNARKs. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part II. LNCS, vol. 10402, pp. 581–612. Springer, Cham (Aug 2017).https://doi.org/10.1007/978-3-319-63715-0_20

    work page doi:10.1007/978-3-319-63715-0_20 2017

  33. [33]

    In: Hanaoka, G., Yang, B.Y

    Groth, J., Malvai, H., Miller, A., Zhang, Y.N.: Constraint-friendly map-to-elliptic-curve-group relations and their applications. In: Hanaoka, G., Yang, B.Y. (eds.) ASIACRYPT 2025, Part II. LNCS, vol. 16246, pp. 511–543. Springer, Singapore (Dec 2025).https://doi.org/10.1007/978-981-95-5096-8_16

    work page doi:10.1007/978-981-95-5096-8_16 2025

  34. [34]

    Do you play it by the books? a study on incident response playbooks and influencing factors,

    Hanzlik, L., Loss, J., Thyagarajan, S.A.K., Wagner, B.: Sweep-UC: Swapping coins privately. In: 2024 IEEE Symposium on Security and Privacy. pp. 3822–3839. IEEE Computer Society Press (May 2024).https://doi. org/10.1109/SP54263.2024.00081

    work page doi:10.1109/sp54263.2024.00081 2024

  35. [35]

    In: NDSS 2017

    Heilman, E., Alshenibr, L., Baldimtsi, F., Scafuro, A., Goldberg, S.: TumbleBit: An untrusted Bitcoin-compatible anonymous payment hub. In: NDSS 2017. The Internet Society (Feb / Mar 2017).https://doi.org/10.14722/ ndss.2017.23086

    work page arXiv 2017

  36. [36]

    In: Hazay, C., Stam, M

    Hesse, J., Jarecki, S., Krawczyk, H., Wood, C.: Password-authenticated TLS via OPAQUE and post-handshake authentication. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part V. LNCS, vol. 14008, pp. 98–127. Springer, Cham (Apr 2023).https://doi.org/10.1007/978-3-031-30589-4_4

    work page doi:10.1007/978-3-031-30589-4_4 2023

  37. [37]

    Jarecki, A

    Jarecki, S., Kiayias, A., Krawczyk, H.: Round-optimal password-protected secret sharing and T-PAKE in the password-only model. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014, Part II. LNCS, vol. 8874, pp. 233–253. Springer, Berlin, Heidelberg (Dec 2014).https://doi.org/10.1007/978-3-662-45608-8_13 25

    work page doi:10.1007/978-3-662-45608-8_13 2014

  38. [38]

    In: 2016 IEEE European Symposium on Security and Privacy (EuroS&P)

    Jarecki, S., Kiayias, A., Krawczyk, H., Xu, J.: Highly-efficient and composable password-protected secret sharing (or: How to protect your bitcoin wallet online). In: 2016 IEEE European Symposium on Security and Privacy (EuroS&P). pp. 276–291 (2016).https://doi.org/10.1109/EuroSP.2016.30

    work page doi:10.1109/eurosp.2016.30 2016

  39. [39]

    In: Nielsen, J.B., Rijmen, V

    Jarecki, S., Krawczyk, H., Xu, J.: OPAQUE: An asymmetric PAKE protocol secure against pre-computation attacks. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part III. LNCS, vol. 10822, pp. 456–486. Springer, Cham (Apr / May 2018).https://doi.org/10.1007/978-3-319-78372-7_15

    work page doi:10.1007/978-3-319-78372-7_15 2018

  40. [40]

    In: NDSS 2019

    Kaptchuk, G., Green, M., Miers, I.: Giving state to the stateless: Augmenting trustworthy computation with ledgers. In: NDSS 2019. The Internet Society (Feb 2019).https://doi.org/10.14722/ndss.2019.23060

    work page doi:10.14722/ndss.2019.23060 2019

  41. [41]

    Chapman and Hall, CRC Press, third edn

    Katz, J., Lindell, Y.: Introduction to Modern Cryptography. Chapman and Hall, CRC Press, third edn. (2014)

    2014

  42. [42]

    In: Ray, I., Li, N., Kruegel, C

    Kumaresan, R., Moran, T., Bentov, I.: How to use Bitcoin to play decentralized poker. In: Ray, I., Li, N., Kruegel, C. (eds.) ACM CCS 2015. pp. 195–206. ACM Press (Oct 2015).https://doi.org/10.1145/2810103.2813712

    work page doi:10.1145/2810103.2813712 2015

  43. [43]

    Kurbatov, O.: Emulating op_rand in bitcoin (2025),https://arxiv.org/abs/2501.16451

    work page arXiv 2025

  44. [44]

    Cryptology ePrint Archive, Report 2016/046 (2016),https://eprint.iacr.org/2016/046

    Lindell, Y.: How to simulate it - A tutorial on the simulation proof technique. Cryptology ePrint Archive, Report 2016/046 (2016),https://eprint.iacr.org/2016/046

    2016

  45. [45]

    Lindell,Y.,Pinkas,B.:Securetwo-partycomputationviacut-and-chooseoblivioustransfer.JournalofCryptology 25(4), 680–722 (Oct 2012).https://doi.org/10.1007/s00145-011-9107-0

    work page doi:10.1007/s00145-011-9107-0 2012

  46. [46]

    In: NDSS 2023

    Madathil, V., Thyagarajan, S.A.K., Vasilopoulos, D., Fournier, L., Malavolta, G., Moreno-Sanchez, P.: Crypto- graphic oracle-based conditional payments. In: NDSS 2023. The Internet Society (Feb 2023)

    2023

  47. [47]

    In: NDSS 2019

    Malavolta, G., Moreno-Sanchez, P., Schneidewind, C., Kate, A., Maffei, M.: Anonymous multi-hop locks for blockchain scalability and interoperability. In: NDSS 2019. The Internet Society (Feb 2019).https://doi.org/ 10.14722/ndss.2019.23330

    work page doi:10.14722/ndss.2019.23330 2019

  48. [48]

    In: 2017 IEEE European Symposium on Security and Privacy Workshops (EuroS&PW)

    Miller, A., Bentov, I.: Zero-collateral lotteries in bitcoin and ethereum. In: 2017 IEEE European Symposium on Security and Privacy Workshops (EuroS&PW). pp. 4–13 (2017).https://doi.org/10.1109/EuroSPW.2017.44

    work page doi:10.1109/eurospw.2017.44 2017

  49. [49]

    In: Goldberg, I., Moore, T

    Miller, A., Bentov, I., Bakshi, S., Kumaresan, R., McCorry, P.: Sprites and state channels: Payment networks that go faster than lightning. In: Goldberg, I., Moore, T. (eds.) FC 2019. LNCS, vol. 11598, pp. 508–526. Springer, Cham (Feb 2019).https://doi.org/10.1007/978-3-030-32101-7_30

    work page doi:10.1007/978-3-030-32101-7_30 2019

  50. [50]

    Nolan, T.: Alt chains and atomic transfers.https://bitcointalk.org/index.php?topic=193281.0(2013)

    2013

  51. [51]

    In: 2013 IEEE Symposium on Security and Privacy

    Parno, B., Howell, J., Gentry, C., Raykova, M.: Pinocchio: Nearly practical verifiable computation. In: 2013 IEEE Symposium on Security and Privacy. pp. 238–252. IEEE Computer Society Press (May 2013).https: //doi.org/10.1109/SP.2013.47

    work page doi:10.1109/sp.2013.47 2013

  52. [52]

    In: 2023 IEEE Symposium on Security and Privacy

    Qin, X., Pan, S., Mirzaei, A., Sui, Z., Ersoy, O., Sakzad, A., Esgin, M.F., Liu, J.K., Yu, J., Yuen, T.H.: BlindHub: Bitcoin-compatible privacy-preserving payment channel hubs supporting variable amounts. In: 2023 IEEE Symposium on Security and Privacy. pp. 2462–2480. IEEE Computer Society Press (May 2023).https: //doi.org/10.1109/SP46215.2023.10179427

    work page doi:10.1109/sp46215.2023.10179427 2023

  53. [53]

    Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM56(6) (Sep 2009). https://doi.org/10.1145/1568318.1568324,https://doi.org/10.1145/1568318.1568324

    work page doi:10.1145/1568318.1568324 2009

  54. [54]

    In: 40th FOCS

    Sahai, A.: Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security. In: 40th FOCS. pp. 543–553. IEEE Computer Society Press (Oct 1999).https://doi.org/10.1109/SFFCS.1999.814628

    work page doi:10.1109/sffcs.1999.814628 1999

  55. [55]

    In: 2021 IEEE Symposium on Security and Privacy

    Tairi, E., Moreno-Sanchez, P., Maffei, M.: A2L: Anonymous atomic locks for scalability in payment channel hubs. In: 2021 IEEE Symposium on Security and Privacy. pp. 1834–1851. IEEE Computer Society Press (May 2021). https://doi.org/10.1109/SP40001.2021.00111

    work page doi:10.1109/sp40001.2021.00111 2021

  56. [56]

    In: Borisov, N., Díaz, C

    Tairi, E., Moreno-Sanchez, P., Maffei, M.: Post-quantum adaptor signature for privacy-preserving off-chain pay- ments. In: Borisov, N., Díaz, C. (eds.) FC 2021, Part II. LNCS, vol. 12675, pp. 131–150. Springer, Berlin, Heidelberg (Mar 2021).https://doi.org/10.1007/978-3-662-64331-0_7

    work page doi:10.1007/978-3-662-64331-0_7 2021

  57. [57]

    Taylor, J.: Bitcoin probabilistic swaps.https://github.com/EzePze/bitcoin-probabilistic-swaps(2026), ac- cessed: 2026-05-05

    2026

  58. [58]

    Financial Cryptography and Data Security (2026),https://fc26.ifca.ai/preproceedings/113

    Taylor, J., Gerhart, P., Thyagarajan, S.A.: How to make delegated payments on bitcoin: A question for the AI agentic future. Financial Cryptography and Data Security (2026),https://fc26.ifca.ai/preproceedings/113. pdf

    2026

  59. [59]

    In: Ligatti, J., Ou, X., Katz, J., Vigna, G

    Thyagarajan, S.A.K., Bhat, A., Malavolta, G., Döttling, N., Kate, A., Schröder, D.: Verifiable timed signatures made practical. In: Ligatti, J., Ou, X., Katz, J., Vigna, G. (eds.) ACM CCS 2020. pp. 1733–1750. ACM Press (Nov 2020).https://doi.org/10.1145/3372297.3417263

    work page doi:10.1145/3372297.3417263 2020

  60. [60]

    2021 IEEE Symposium on Security and Privacy (SP) pp

    Thyagarajan, S.A.K., Malavolta, G.: Lockable signatures for blockchains: Scriptless scripts for all signatures. 2021 IEEE Symposium on Security and Privacy (SP) pp. 937–954 (2021),https://api.semanticscholar.org/ CorpusID:231732350

    2021

  61. [61]

    Model Stealing Attacks Against Inductive Graph Neural Networks

    Thyagarajan, S.A.K., Malavolta, G., Moreno-Sanchez, P.: Universal atomic swaps: Secure exchange of coins across all blockchains. In: 2022 IEEE Symposium on Security and Privacy. pp. 1299–1316. IEEE Computer Society Press (May 2022).https://doi.org/10.1109/SP46214.2022.9833731 26

    work page doi:10.1109/sp46214.2022.9833731 2022

  62. [62]

    In: Dunkelman, O., Dziembowski, S

    Tyagi, N., Celi, S., Ristenpart, T., Sullivan, N., Tessaro, S., Wood, C.A.: A fast and simple partially oblivious PRF, with applications. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022, Part II. LNCS, vol. 13276, pp. 674–705. Springer, Cham (May / Jun 2022).https://doi.org/10.1007/978-3-031-07085-3_23

    work page doi:10.1007/978-3-031-07085-3_23 2022

  63. [63]

    In: Luo, B., Liao, X., Xu, J., Kirda, E., Lie, D

    Vanjani, N., Soni, P., Thyagarajan, S.A.K.: Functional adaptor signatures: Beyond all-or-nothing blockchain- based payments. In: Luo, B., Liao, X., Xu, J., Kirda, E., Lie, D. (eds.) ACM CCS 2024. pp. 1493–1507. ACM Press (Oct 2024).https://doi.org/10.1145/3658644.3690240 A Preliminaries We recall preliminaries on oblivious PRFs, adaptor signatures, and ze...

    work page doi:10.1145/3658644.3690240 2024

  64. [64]

    The prover samplesrsk, rα ←$ Zp and computes the commitmentsR1 :=g rsk , R2 :=g rα , R3 :=Z rα ·req rsk .It sends(R 1, R2, R3)to the verifier

  65. [66]

    Verification:Parsectas(c 1, c2)

    The prover computes the responseszsk :=r sk +c·sk, z α :=r α +c·α,and sends(z sk, zα)to the verifier. Verification:Parsectas(c 1, c2). Upon receiving(R1, R2, R3, zsk, zα), the verifier accepts iff gzsk ? =R 1 ·pk c ∧g zα ? =R 2 ·c c 1 ∧Z zα ·req zsk ? =R 3 ·c c 2. Fig.14.Interactive Schnorr proof for the relationREnc. Proofs of knowledge for commitment-op...

  66. [67]

    The prover samplesrsk, rω ←$ Zp and computes the commitmentR:=g rsk hrω .It sendsRto the verifier

  67. [69]

    Verification:Upon receiving(R, z sk, zω), the verifier accepts iffgzsk hzω ? =R·C c

    The prover computes the responseszsk :=r sk +c·sk, z ω :=r ω +c·ω,and sends(z sk, zω)to the verifier. Verification:Upon receiving(R, z sk, zω), the verifier accepts iffgzsk hzω ? =R·C c. Fig.15.Interactive Schnorr proof for the relationRC. Lemma 2.The cut-and-choose protocol in Figure 17 is complete, computationally sound under the DDH assumption, and hon...

  68. [70]

    The prover samplesr← $ Zp and computesR:=g r.It sendsRto the verifier

  69. [72]

    Verification:Upon receiving(R, z), the verifier accepts iffgz ? =R·pk c

    The prover computes the responsez:=r+c·skand sendszto the verifier. Verification:Upon receiving(R, z), the verifier accepts iffgz ? =R·pk c. Fig.16.Interactive Schnorr proof for the relationRDL. Public inputs: a group(G, g, p), and hash functionsH G :{0,1} ∗ →G,H p :{0,1} ∗ →Z p, and a statement x= (pk, Y win, ℓ). The prover providesw= (sk, y tgt)as addit...

  70. [73]

    , αλ, r1,

    The prover samples scalars(α1, . . . , αλ, r1, . . . , rλ)← $ Zp, computes theλcommitments n Hp HG(ytgt)sk·αi +r i, Ri =g ri , Ai =g αi o 1≤i≤λ , and sends them to the verifier

  71. [74]

    The verifier selectsλ/2random indices and sends them to the prover

  72. [75]

    In addition, for each unselected commitment with indexk, the prover outputs(αk, sk =r k +y win)

    For each indexjselected by the verifier, the prover outputs(r j,H G(y)sk·αj ), and a proof of well-formedness ofH G(y)sk·αj w.r.t.pk,g αj, and all possible valuesˆy∈ {0,1} ℓ (depicted in Figure 18). In addition, for each unselected commitment with indexk, the prover outputs(αk, sk =r k +y win). Verification:The verifier obtainsrj,H G(y)sk·αj and a proof o...

  73. [76]

    For each selected indexj, the verifier verifies the opening by checking the proof of well-formedness, and by asserting thatr j is a correct opening forRj

  74. [77]

    Fig.17.Interactive cut-and-choose proof forR win

    For each unselected indexk, the verifier asserts that the valuesk is well-formed by checking ifYwin ·R k ? =g sk andA k =g αk. Fig.17.Interactive cut-and-choose proof forR win. 33 any of the selected instances’ OR statements either. Hence for each selected indexjthe prover must either produce an accepting transcript of Lemma 3 without a valid witness, or ...

  75. [78]

    For the real branchˆy=y, the prover computesBy :=h α y .It samplest α, tsk ←$ Zp and computes a1,y =g tα , a 2,y =h tα y , a 3,y =g tsk , a 4,y =B tsk y

  76. [79]

    For every simulated branchˆy∈ {0,1} ℓ \ {y}, the prover samplesc ˆy, zα,ˆy, zsk,ˆy, βˆy←$ Zp,definesB ˆy:=h β ˆy ˆy , and computes a1,ˆy=g zα,ˆyA−c ˆy, a 2,ˆy=h zα,ˆy ˆy B −c ˆy ˆy , a 3,ˆy=g zsk,ˆypk−c ˆy, a 4,ˆy=B zsk,ˆy ˆy T −c ˆy

  77. [80]

    The prover sends, for everyˆy∈ {0,1}ℓ, the first message Bˆy, a1,ˆy, a2,ˆy, a3,ˆy, a4,ˆy to the verifier

  78. [82]

    The prover setscy :=c− P ˆy∈{0,1}ℓ\{y} cˆy,and computes the real responses zα,y :=t α +c yα, z sk,y :=t sk +c ysk

  79. [83]

    Verification:Upon receiving Bˆy, a1,ˆy, a2,ˆy, a3,ˆy, a4,ˆy, cˆy, zα,ˆy, zsk,ˆy ˆy∈{0,1}ℓ ,the verifier accepts iff:

    The prover sends, for everyˆy∈ {0,1}ℓ, the tuple(cˆy, zα,ˆy, zsk,ˆy)to the verifier. Verification:Upon receiving Bˆy, a1,ˆy, a2,ˆy, a3,ˆy, a4,ˆy, cˆy, zα,ˆy, zsk,ˆy ˆy∈{0,1}ℓ ,the verifier accepts iff:

  80. [84]

    The branch challenges sum to the global challenge:P ˆy∈{0,1}ℓ cˆy≡c(modp)

Showing first 80 references.