betaFeedback

WorksComputer Science

Deterministic ECDSA on secp256k1: the RFC 6979 assumption, a counterexample, and the state of deployed implementations

Abstract

RFC 6979 derives the ECDSA nonce as k=Fx(h)k = F_x(h), with FxF_x HMAC_DRBG keyed by the signing key x. We isolate the assumption its security rests on, A*: at known public key Q=xGQ = xG, the signing transcript under nonces Fx()F_x() is indistinguishable from the transcript under uniform nonces. A* suffices, and it is neither PRF security of HMAC nor auxiliary-input PRF security (AI-PRF) of FxF_x. A function F′(x,h)=PExt(xG)(h)F'(x, h) = P_{Ext(xG)}(h) is a PRF under standard assumptions yet leaks x from one signature; the same holds for unmodified RFC 6979 over a compression function that keeps the PRF and dual-PRF properties used in proofs of HMAC, given a collision-resistance premise. A* and AI-PRF are separated in both directions. A* does not imply AI-PRF if the one-bit hidden number problem is hard. Conversely, in the standard model: any AI-PRF can be modified so that it stays one while two chosen-digest signing queries reveal x; under DDH with one public random point, or decisional square Diffie-Hellman without it, there is an AI-PRF whose key is recovered from signatures on two ordinary hashed messages; and a third function, under PRF security and DLP, violates A* while the scheme stays unforgeable. With an ideal compression function, A* follows tightly from DLP in the presence of a randomized-ECDSA signing oracle, and a nonce key independent of x removes the assumption. The secret HMAC message block is 2−127.652^{-127.65} from uniform on secp256k1, 2−322^{-32} on P-256 and 0.336 on brainpoolP256r1. An audit of 31 secp256k1 implementations finds that 28 sign deterministically without added entropy and that the raw-message deviation from bits2octets of libsecp256k1 before 0.2.0 survives in NBitcoin, dcrd and btcec v2. Low-R grinding needs no assumption beyond A*, and every nonzero Fourier coefficient of the low-R nonce set is below 2−116.92^{-116.9} unconditionally. We give test vectors for the untested h>=nh >= n branch

Introduction

ECDSA leaks the signing key when the per-signature nonce kk is repeated, biased, or partially known. Deterministic nonce derivation (RFC 6979 [1]) removes the dependence on a run-time random number generator by computing kk from the signing key xx and the message hash hh with HMAC_DRBG. The construction is the de facto standard in the Bitcoin and Ethereum ecosystems: of the 31 secp256k1 implementations we audited, 28 sign ECDSA deterministically by default, and the dominant library, libsecp256k1, offers no other default.

The security argument that accompanies RFC 6979 is informal. Section 4 of the RFC states that HMAC_DRBG “is secure in that role as long as HMAC behaves as a PRF” and that the construction “requires HMAC_DRBG to keep on being a random oracle even when the public key is also known”. These two sentences describe two different assumptions, and we show that neither is the one actually needed.

Contributions.

  1. We formulate the assumption A∗A^* under which deterministic ECDSA is exactly as secure as randomized ECDSA (Theorem 3.1), and show that the auxiliary-input PRF assumption AI-PRF on FxF_x does not support such a reduction (§ 3).

  1. We give a counterexample: F′(x,h)=PExt⁡(xG)(h)F'(x,h)=P_{\operatorname{Ext}(xG)}(h), where PP is any PRF and Ext extracts ℓ\ell bits from the public key, is a PRF under the PRF security of PP and a standard randomness-extraction lemma, yet deterministic ECDSA with F′F' reveals xx from one signature (Theorem 4.5). Hence “PRF + DLP + randomized ECDSA is secure” does not imply that RFC 6979 is secure, and A∗A^* is a genuinely additional assumption. We lift the counterexample to the compression function: there is f∗f^* with the PRF and dual-PRF properties used in proofs of HMAC (given a collision-resistance premise) for which the unmodified RFC 6979 state machine is a PRF in xx and Det-ECDSA is broken with one signature (Theorem 4.8).

  1. We prove that A∗A^* and AI-PRF are not equivalent. A∗⇏A^* \nRightarrow AI-PRF holds conditionally on the hardness of the one-bit hidden number problem (§ 5). For AI-PRF ⇏A∗\nRightarrow A^*, the natural candidate—rejecting nonces unless lsb⁡(xk mod n)=0\operatorname{lsb}(xk\bmod n)=0—does not separate the two notions for any number of signing queries qq and any filter width ℓ\ell (Theorems 5.1 and 5.4), but two other constructions do, in the standard model. A planted nonce collision turns any AI-PRF into an AI-PRF under which two chosen-digest signing queries reveal xx (Theorem 5.7). Under the decisional square Diffie–Hellman assumption there is a single-key AI-PRF under which signatures on two ordinary SHA-256 messages reveal xx, so that a third message is forged (Theorem 5.9). Ordinary DDH suffices given one public random point, or, without any setup, given an AI-PRF and about 4λ4\lambda signatures; with a second secret scalar the existence of an AI-PRF alone suffices (Theorem 5.13, Table 3). An ordering bit hidden in a signature scalar violates A∗A^* with advantage 1/21/2 on three fixed hashed messages, under PRF security and DLP, and survives low-ss normalization (Theorem 5.11); that scheme remains unforgeable, so A∗A^* is sufficient but not necessary.

ConstructionAssumptionSetup and secretsSigning queries
F‾†\overline{F}^{\dagger} (Thm. 5.7)an AI-PRF existsnone; xx2, chosen digests
F‾♯\overline{F}^{\sharp} (Thm. 5.9)DSDH, PRFnone; xx2, hashed messages
Thm. 5.13(a)DDH, PRFone public random point; xx2, hashed messages
Thm. 5.13(b)DDH, an AI-PRF existsnone; xx≈1026\approx1026, hashed messages
Thm. 5.13(c)an AI-PRF existsnone; xx and a second scalar2, hashed messages

Table 3. Key-recovery separations AI-PRF ⇏\not\Rightarrow A*. In every row the nonce adversary queries arbitrary digests; the column “queries” restricts the signing attacker.

  1. We record what is provable: with an ideal compression function, A∗A^* follows from DLP in the presence of a randomized-ECDSA signing oracle, with no factor qHq_H (Theorem 6.1); a nonce key independent of xx makes it unnecessary (§ 6). We quantify the curve dependence of the standard part of the assumption (§ 7).

  1. We audit 31 implementations (§ 8): nonce defaults, bits2octets compliance, the retry and grinding logic, and test coverage. We prove that low-RR grinding, as deployed in Bitcoin Core, reduces to A∗A^* on an extended input domain plus randomized ECDSA (Theorem 8.1), we bound every nonzero Fourier coefficient of the low-RR nonce set unconditionally (Proposition 8.2), and we supply test vectors for the h≥nh \ge n branch, which no implementation we examined tests.

  1. We place the one-bit nonce-bias attack in context (§ 9): a modelled data threshold of 2472^{47} signatures for one error-free leaked bit on a 256-bit curve, with an honest uncertainty envelope of 2402^{40}–2472^{47}, and the observation that GLV decomposition of a uniform nonce creates no such bias.

All claims are tagged in the text as proved here [T], taken from the literature [L], established by inspection of source code [S], or estimates and interpretations [O].

Preliminaries

Curve and notation. secp256k1 is the curve y2=x3+7y^2=x^3+7 over Fp\mathbb{F}_p, p=2256−232−977p=2^{256}-2^{32}-977, with prime group order

n=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141n = \texttt{0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141}

and generator GG. We write t=2256−n=1.2708⋅2128t = 2^{256} - n = 1.2708 \cdot2^{128}. The signing key is x∈[1,n−1]x \in[1,n-1], the public key is Q=xGQ = xG. For a message mm with hash H(m)H(m) we write h=bits2int⁡(H(m)) mod nh = \operatorname{bits2int}(H(m)) \bmod n. An ECDSA signature on hh with nonce k∈[1,n−1]k \in[1,n-1] is (r,s)(r,s) with R=kGR = kG, r=x(R) mod nr = x(R) \bmod n, s=k−1(h+rx) mod ns = k^{-1}(h+rx) \bmod n.

RFC 6979. The nonce is k=Fx(h)k = F_x(h) where

Fx(h)=HMAC_DRBG⁡(int2octets⁡(x)∥bits2octets⁡(h))F_x(h) = \operatorname{HMAC\_DRBG}(\operatorname{int2octets}(x) \mathbin\Vert\operatorname{bits2octets}(h))

and candidates outside [1,n−1][1,n-1] are rejected by advancing the DRBG (step H.3). Section 3.6 of the RFC optionally appends additional data k′k' to the seed.

Three schemes. Rand-ECDSA: k←[1,n−1]k \leftarrow[1,n-1] uniformly. Det-ECDSA: k=Fx(h)k = F_x(h). Det′-ECDSA: k=Pz(h)k = P_z(h) for a PRF PP with key zz independent of xx.

Two assumptions. Let DD be a probabilistic polynomial-time distinguisher and R\mathcal{R} a random function.

Assumption 2.1 (AI-PRF). FF is an auxiliary-input PRF at the public key if for every DD

∣Pr⁡[DFx(⋅)(Q)=1]−Pr⁡[DR(⋅)(Q)=1]∣≤ε.\left\lvert\Pr\left[D^{F_x(\cdot)}(Q)=1\right] - \Pr\left[D^{\mathcal{R}(\cdot)}(Q)=1\right] \right\rvert\le\varepsilon.

Assumption 2.2 (A∗A^*). FF satisfies A∗A^* if for every DD

∣Pr⁡[DSign⁡x(⋅;Fx)(Q)=1]−Pr⁡[DSign⁡x(⋅;R)(Q)=1]∣≤ε,\left\lvert\Pr\left[D^{\operatorname{Sign}_x(\cdot;F_x)}(Q)=1\right] - \Pr\left[D^{\operatorname{Sign}_x(\cdot;\mathcal{R})}(Q)=1\right] \right\rvert\le\varepsilon,

where Sign⁡x(⋅;Fx)\operatorname{Sign}_x(\cdot;F_x) is the signing oracle using nonces Fx(h)F_x(h) and Sign⁡x(⋅;R)\operatorname{Sign}_x(\cdot;\mathcal{R}) the oracle using independent uniform nonces (with the same rejection rule).

Both assumptions are falsifiable in the sense of Naor [4]: an efficient distinguisher is a verifiable witness of failure.

Chosen digests and hashed messages. In both assumptions the distinguisher submits digests h∈Znh \in\mathbb{Z}_n directly; we call this the chosen-digest game. It is the interface of libsecp256k1 and of most libraries of Section 8, which sign a caller-supplied 32-byte digest. In the hashed-message game queries are restricted to h=bits2int⁡(H(m)) mod nh = \operatorname{bits2int}(H(m)) \bmod n for messages mm. An assumption stated for chosen digests implies its hashed-message version, whereas an attack that needs particular digests may not transfer. Forgery games are always played with hashed messages, because ECDSA is forgeable on chosen digests (see (3)).

What the reduction needs

Theorem 3.1 (A∗A^* suffices). For every forger AA against Det-ECDSA there is a forger BB against Rand-ECDSA and a distinguisher DD with

Adv⁡DetEUF-CMA(A)≤Adv⁡RandEUF-CMA(B)+Adv⁡A∗(D).\operatorname{Adv}_{\mathrm{Det}}^{\mathrm{EUF\text{-}CMA}}(A) \le\operatorname{Adv}_{\mathrm{Rand}}^{\mathrm{EUF\text{-}CMA}}(B) + \operatorname{Adv}_{A^*}(D).

Proof. Game 0 is the Det-ECDSA forgery game; Game 1 replaces the nonces by independent uniform values. Any AA whose success differs between the games is a distinguisher DD for A∗A^*: DD receives QQ, forwards signing queries to its oracle, and outputs 1 iff AA forges. Game 1 is the Rand-ECDSA game. [T]

Proposition 3.2 (AI-PRF does not support the reduction). A distinguisher for AI-PRF receives (Q,k1,…,kq)(Q, k_1, \ldots, k_q). To simulate the signing oracle for a Det-ECDSA forger it must produce si=ki−1(hi+rix)s_i = k_i^{-1}(h_i + r_i x), which requires xx. No generic reduction from AI-PRF to the security of Det-ECDSA can simulate signatures in the standard model. [T]

The proposition says only that the obvious reduction fails. The next section shows that no reduction that uses FxF_x purely as a PRF can succeed, and Theorems 5.7 and 5.9 that the same is true of AI-PRF: there are nonce functions satisfying it under which two signatures reveal the key, on chosen digests if any AI-PRF exists at all, and on ordinary hashed messages under decisional square Diffie–Hellman, or under DDH with a public random point.

A counterexample

Let enc⁡\operatorname{enc} be an injective encoding of the points of ⟨G⟩\langle G\rangle, including O\mathcal{O}, as strings of at most 258 bits, and let {hs}s\{h_s\}_s be a universal family of functions {0,1}258→{0,1}ℓ\{0,1\}^{258} \to\{0,1\}^{\ell}. For a seed ss fixed below put Ext⁡(Q):=hs(enc⁡(Q))\operatorname{Ext}(Q) := h_s(\operatorname{enc}(Q)). Let PP be any PRF with a uniform ℓ\ell-bit key, ℓ=128\ell= 128. Define

F′(x,h):=PExt⁡(xG)(h).(1)F'(x,h) := P_{\operatorname{Ext}(xG)}(h). \tag*{(1)}

The key xx enters F′F' only through Ext⁡(xG)\operatorname{Ext}(xG), which is a function of the public key.

Lemma 4.1 (extraction). For xx uniform on [1,n−1][1,n-1],

EsSD⁡(hs(enc⁡(xG)),Uℓ)≤122(ℓ−log⁡2(n−1))/2,\mathbb{E}_s \operatorname{SD}(h_s(\operatorname{enc}(xG)), U_\ell) \le\frac{1}{2}2^{(\ell-\log_2(n-1))/2},

which is 2−652^{-65} for ℓ=128\ell= 128. Hence there is a seed ss with δExt⁡:=SD⁡(Ext⁡(xG),Uℓ)≤2−65\delta_{\operatorname{Ext}} := \operatorname{SD}(\operatorname{Ext}(xG), U_\ell) \le2^{-65}; we fix such an ss. [T]

Proof. xGxG is uniform on n−1n-1 points and enc⁡\operatorname{enc} is injective, so H∞(enc⁡(xG))=log⁡2(n−1)H_\infty(\operatorname{enc}(xG)) = \log_2(n-1). Apply the leftover hash lemma [11] and average over ss.

Remark 4.2 (deterministic truncation). A seedless alternative is to truncate the abscissa, but the available bounds are for the least significant bits: Chevalier, Fouque, Pointcheval and Zimmer [10 Thm. 14] prove SD⁡(lsb⁡k(x(U)),Uk)≤2(k+m+log⁡2m)/2+3−log⁡2n\operatorname{SD}(\operatorname{lsb}_k(x(U)), U_k) \le2^{(k+m+\log_2 m)/2+3-\log_2 n} for UU uniform on ⟨G⟩\langle G\rangle and m=⌈log⁡2p⌉m = \lceil\log_2 p\rceil, i.e. 2k/2−1212^{k/2-121} on secp256k1 and 2−572^{-57} for k=128k = 128. The work of Fouque, Pointcheval, Stern and Zimmer [9] concerns subgroups of Zp∗\mathbb{Z}_p^* only. We use the seeded extractor throughout because § 4.1 needs extraction from a non-uniform subset of the group, where the leftover hash lemma applies verbatim.

Lemma 4.3 (PRF security). Adv⁡F′PRF⁡(A)≤Adv⁡PPRF⁡(B)+δExt⁡\operatorname{Adv}^{\operatorname{PRF}}_{F'}(A) \le\operatorname{Adv}^{\operatorname{PRF}}_{P}(B) + \delta_{\operatorname{Ext}}. [T]

Proof. Replace Ext⁡(xG)\operatorname{Ext}(xG) by a uniform key (loss δExt⁡\delta_{\operatorname{Ext}} by Lemma 4.1); BB forwards AA's queries to its PP oracle. No circular-security assumption is needed because xx is used only as PRF key material.

Lemma 4.4 (key recovery). Given QQ and one Det-ECDSA signature (r,s)(r,s) on hh with k=F′(x,h)k = F'(x,h), anyone computes K=Ext⁡(Q)K = \operatorname{Ext}(Q), k=PK(h)k = P_K(h) and x=(sk−h)r−1 mod nx = (sk-h)r^{-1} \bmod n. [T]

Theorem 4.5 (counterexample). Assume PP is a PRF, DLP is hard on secp256k1 and Rand-ECDSA is EUF-CMA-secure. Then F′F' is a PRF (Lemma 4.3), all three premises hold, and Det-ECDSA with F′F' is totally broken (Lemma 4.4). Consequently no reduction that treats the nonce function only as a PRF—in particular none that uses only the PRF security of HMAC—can prove RFC 6979 secure. F′F' also violates AI-PRF: anyone holding QQ recomputes all its outputs. [T]

Remark 4.6. A variant F∘(x,h)=x+PExt⁡(xG)(h)F^\circ(x,h) = x + P_{\operatorname{Ext}(xG)}(h) would require adding xx to oracle answers in the PRF reduction and therefore a circular-key assumption; the variant (1) avoids this entirely.

Opening the box: the SHA-256 compression function

Theorem 4.5 treats FxF_x as a black box. HMAC_DRBG is not an arbitrary PRF: proofs of HMAC rest on properties of the SHA-256 compression function f:{0,1}256×{0,1}512→{0,1}256f : \{0,1\}^{256} \times\{0,1\}^{512} \to\{0,1\}^{256}, and one might hope that these properties, together with the specific state machine of RFC 6979 §3.2, imply A∗A^*. They do not, given a collision-resistance premise.

Block layout. With K0=0x0032K_0 = \texttt{0x00}^{32} and V0=0x0132V_0 = \texttt{0x01}^{32}, step d computes

K1=HMAC⁡K0(V0∥0x00∥int2octets⁡(x)∥bits2octets⁡(h)).K_1 = \operatorname{HMAC}_{K_0}(V_0 \mathbin\Vert\texttt{0x00} \mathbin\Vert\operatorname{int2octets}(x) \mathbin\Vert\operatorname{bits2octets}(h)).

The inner hash first compresses the public block (K0∥0256)⊕ipad⁡=0x3664(K_0 \mathbin\Vert0^{256}) \oplus\operatorname{ipad} = \texttt{0x36}^{64}, giving a public chaining value IV1IV_1, and then the 97-byte message; the total length is 161 bytes, L=1288L = 1288 bits. The two message blocks are

m1=V0∥0x00∥x[0..30],m2=x[31]∥bits2octets⁡(h)∥0x80∥0176∥⟨L⟩64,m_1 = V_0 \mathbin\Vert\texttt{0x00} \mathbin\Vert x_{[0..30]}, \qquad m_2 = x_{[31]} \mathbin\Vert\operatorname{bits2octets}(h) \mathbin\Vert\texttt{0x80} \mathbin\Vert0^{176} \mathbin\Vert\langle L\rangle_{64},

where x[i]x_{[i]} is the ii-th byte of int2octets⁡(x)\operatorname{int2octets}(x). Step f has the same layout with V1V_1, 0x01\texttt{0x01} and the secret chaining value derived from K1K_1. Write Pad⁡={0x80∥0176∥⟨L⟩64:L≠0}\operatorname{Pad} = \{\texttt{0x80}\mathbin\Vert0^{176}\mathbin\Vert\langle L\rangle_{64} : L \ne0\} for the 31-byte SHA-256 padding tails. In every other block of the computation—HMAC key setup, outer hashes, steps e, g, h, and the retry step H.3—either byte 32 is not in {0x00,0x01}\{\texttt{0x00},\texttt{0x01}\} or bytes 33–63 lie in Pad⁡\operatorname{Pad}. Writing x=28x~+bx = 2^8\widetilde{x} + b with x~=int⁡(x[0..30])\widetilde{x} = \operatorname{int}(x_{[0..30]}) and b=x[31]b = x_{[31]}, we have 28x~G=Q−bG2^8\widetilde{x}G = Q - bG.

[T]

Properties of ff

We use three properties.

  • (A1) PRF in the chaining value: f(cv,⋅)f(cv,\mathord\cdot) is a PRF for uniform secret cvcv.

  • (A2) Dual PRF with a key in the first half of the block: for uniform secret u∈{0,1}256u \in\{0,1\}^{256}, the map (cv,w)↦f(cv,u∥w)(cv,w) \mapsto f(cv,u\mathbin\Vert w) is a PRF. This is the property used for HMAC with 256-bit keys and for the outer hash [5, 6].

  • (A2′λ_\lambda) Tail-keyed pseudorandomness: for public cv0cv_0, a public 264-bit prefix π\pi and uniform K∈{0,1}λK \in\{0,1\}^{\lambda}, the value y=f(cv0,π∥K∥0248−λ)y = f(cv_0,\pi\mathbin\Vert K\mathbin\Vert0^{248-\lambda}) is pseudorandom. A standard-model proof that RFC 6979 is a PRF in xx needs (A2248′)(A2'_{248}) with π=V0∥0x00\pi= V_0\mathbin\Vert\texttt{0x00} and K=x[0..30]K = x_{[0..30]} (§ 7).

Construction. Let ℓ≤184\ell\le184, let {hs}\{h_s\} be as in § 4 and read w∈{0,1}248w \in\{0,1\}^{248} as an integer. Define

f∗(cv,u∥c∥w)={f(cv,u∥c∥hs(enc⁡(28wG))∥0248−ℓ),c∈{0x00,0x01}, w∉Pad⁡,f(cv,u∥c∥w),otherwise,f^*(cv,u\mathbin\Vert c\mathbin\Vert w)= \begin{cases} f(cv,u\mathbin\Vert c\mathbin\Vert h_s(\operatorname{enc}(2^8wG))\mathbin\Vert0^{248-\ell}), & c\in\{\texttt{0x00},\texttt{0x01}\},\ w\notin\operatorname{Pad},\\ f(cv,u\mathbin\Vert c\mathbin\Vert w), & \text{otherwise}, \end{cases}

with u∈{0,1}256u \in\{0,1\}^{256} and c∈{0,1}8c \in\{0,1\}^{8}. Let Adv⁡CR\operatorname{Adv}^{\mathrm{CR}} denote the advantage of an efficient algorithm that, given ss, outputs w≠w′w \ne w' in {0,1}248∖Pad⁡\{0,1\}^{248}\setminus\operatorname{Pad} with hs(enc⁡(28wG))=hs(enc⁡(28w′G))h_s(\operatorname{enc}(2^8wG)) = h_s(\operatorname{enc}(2^8w'G)), and put δℓ=122(ℓ−248)/2\delta_\ell= \frac{1}{2}2^{(\ell-248)/2}.

Lemma 4.7 (f∗f^* inherits the properties). Adv⁡f∗A1≤Adv⁡fA1+Adv⁡CR\operatorname{Adv}^{A1}_{f^*} \le\operatorname{Adv}^{A1}_f + \operatorname{Adv}^{\mathrm{CR}}, Adv⁡f∗A2≤Adv⁡fA2+Adv⁡CR\operatorname{Adv}^{A2}_{f^*} \le\operatorname{Adv}^{A2}_f + \operatorname{Adv}^{\mathrm{CR}}, and f∗f^* satisfies (A2248′)(A2'_{248}) whenever ff satisfies (A2ℓ′)(A2'_\ell) and (A2248′)(A2'_{248}), with additional loss δℓ+2−184\delta_\ell+ 2^{-184}.

[T]

Proof. f∗(cv,m)=f(cv,φ(m))f^*(cv,m) = f(cv,\varphi(m)) for a public map φ\varphi. The two branches never collide under φ\varphi: on the first branch the last 248−ℓ≥64248-\ell\ge64 bits are zero, whereas every element of Pad⁡\operatorname{Pad} ends in a non-zero length field, and for c∉{0x00,0x01}c \notin\{\texttt{0x00},\texttt{0x01}\} the byte cc already differs. Hence φ\varphi is injective on any set of queries that contains no collision of the composite map, and a distinguisher for (A1) or (A2) of f∗f^* is one for ff unless it finds such a collision. For (A2248′)(A2'_{248}) with prefix byte c∈{0x00,0x01}c \in\{0x00,0x01\} and uniform ww: w∈Padw \in\mathrm{Pad} with probability ≤264−248\le2^{64-248}; the map w↦28wGw \mapsto2^8wG is injective on [0,2248)[0,2^{248}) because 282^8 is invertible modulo nn and ∣w−w′∣<n\lvert w-w'\rvert<n, so H∞(enc⁡(28wG))=248H_{\infty}(\operatorname{enc}(2^8wG))=248 and the leftover hash lemma gives distance δℓ\delta_{\ell} for all but a small fraction of seeds; choose ss good for this and for Lemma 4.1 simultaneously. Then apply (A2ℓ′)(A2'_{\ell}). For other prefix bytes f∗=ff^*=f.

Theorem 4.8 (white-box counterexample). Assume ff satisfies (A1)(A1), (A2)(A2) and (A2ℓ′)(A2'_{\ell}) and that the composite map above is collision resistant. Let Fx∗(h)F_x^*(h) be the unmodified RFC 6979 §3.2 nonce derivation with the SHA-256 compression function replaced by f∗f^*. Then:

  1. f∗f^* satisfies (A1)(A1), (A2)(A2) and (A2248′)(A2'_{248}) (Lemma 4.7);

  2. F∗F^* is a PRF in xx: for qq queries, Adv⁡F∗PRF≤δℓ+256/n+2−184+Adv⁡fA2ℓ′+O(q)(Adv⁡fA1+Adv⁡fA2)\operatorname{Adv}^{\mathrm{PRF}}_{F^*} \le\delta_{\ell}+256/n+2^{-184}+\operatorname{Adv}^{A2'_{\ell}}_f+O(q)(\operatorname{Adv}^{A1}_f+\operatorname{Adv}^{A2}_f);

  3. given QQ and one Det-ECDSA signature under F∗F^*, xx is recovered with at most 256 runs of the nonce derivation, so Det-ECDSA with F∗F^* is totally broken and A∗A^* fails.

Consequently A∗A^* for HMAC_DRBG does not follow from (A1)(A1), (A2)(A2) and (A2248′)(A2'_{248}) of the compression function together with DLP and the EUF-CMA security of Rand-ECDSA, provided a collision-resistant map of this form exists. [T]

Proof. (2) The pair (x~,b)(\widetilde{x},b) is within 256/n256/n of independent uniform values on its range. x~\widetilde{x} enters the computation only in block 1 of steps d and f, and there only through K=hs(enc⁡(28x~G))K=h_s(\operatorname{enc}(2^8\widetilde{x}G)), except when x~∈Pad\widetilde{x}\in\mathrm{Pad}. Replace KK by a uniform UU (loss δℓ\delta_{\ell}); x~\widetilde{x} then disappears from the game. Now cv1=f(IV1,V0∥0x00∥U∥0248−ℓ)\mathrm{cv1}=f(\mathrm{IV1},V_0\mathbin{\|}0\mathrm{x}00\mathbin{\|}U\mathbin{\|}0^{248-\ell}) is pseudorandom by (A2ℓ′)(A2'_{\ell}). Block 2 of step d is f(cv1,b∥h∥⋯ )f(\mathrm{cv1},b\mathbin{\|}h\mathbin{\|}\cdots), a random function of hh by (A1)(A1); distinct queries hh give distinct inputs. The outer hash and the key setup of K1K_1 are keyed in the first half of the block by (A2)(A2); step e is (A1)(A1); block 1 of step f is f(Kin∗,V1∥0x01∥U∥0248−ℓ)f(K_{\mathrm{in}}^*,V_1\mathbin{\|}0\mathrm{x}01\mathbin{\|}U\mathbin{\|}0^{248-\ell}) under (A1)(A1); the remaining evaluations of steps f–h and the retries are evaluations of ff handled by (A1)(A1) and (A2)(A2). The final nonces are independent and uniform for distinct hh.

(3) For each b^∈[0,255]\hat{b}\in[0,255] compute K^=hs(enc⁡(Q−b^G))\widehat{K}=h_s(\operatorname{enc}(Q-\hat{b}G)). Every evaluation of f∗f^* in the derivation depends on x[0..30]x_{[0..30]} only through 28x~G2^8\widetilde{x}G, hence through K^\widehat{K} when b^=b\hat{b}=b, and on x[31]x_{[31]} directly. Run the derivation with K^\widehat{K} and b^\hat{b}, obtain k^\hat{k}, and test x^=(sk^−h)r−1\hat{x}=(s\hat{k}-h)r^{-1} against x^G=Q\hat{x}G=Q. For b^=b\hat{b}=b this returns xx, unless x~∈Pad\widetilde{x}\in\mathrm{Pad} (probability ≤2−184\le2^{-184}).

Remark 4.9 (on the collision premise). hsh_s alone is not collision resistant once ss is known: a linear universal family has collisions in a known kernel. Exploiting a kernel element, however, requires a ww with prescribed point 28wG2^8wG, i.e. a discrete logarithm. In the generic group model [7] encodings are random and collisions of the composite cost 2ℓ/22^{\ell/2} (Table 1). We know no reduction to DLP, so the premise is non-standard and is stated explicitly. [O]

ℓ\ellδℓ\delta_{\ell}collision, generic group
1282−612^{-61}2642^{64}
1602−452^{-45}2802^{80}
1842−332^{-33}2922^{92}

Table 1. Parameters of f∗f^*: extraction loss and generic cost of a collision. [T][O]

Remark 4.10 (why the collision term is there). A proof of item (2) by statistical extraction must replace all information about x~\widetilde{x} that enters f∗f^* by a uniform string, which the leftover hash lemma allows only for strings shorter than H∞(x~)=248H_{\infty}(\widetilde{x})=248 bits. The first branch of f∗f^* is then not injective in ww, and (A1)(A1) for f∗f^* needs collision resistance. A two-call variant that feeds enc⁡(2ℓwG)\operatorname{enc}(2^{\ell}wG) in clear into a second compression call restores injectivity but breaks item (2): after KK is replaced by UU, the point still appears in the second call of steps d and f, and the hybrid argument cannot proceed. Computational extraction could avoid the term at the price of another non-standard assumption. Theorem 4.8 does not exclude proofs of A∗A^* from other properties of ff, such as correlation intractability, or in the random-oracle model (Theorem 6.1). [O]

A∗A^* and AI-PRF are not equivalent

A∗A^* does not imply AI-PRF

Take FF with a one-bit leak: Fx(h)=Px(h)F_x(h)=P_x(h) with its least significant bit replaced by a bit computable from (x,h)(x,h) and checkable from QQ. AI-PRF is broken with O(1)O(1) queries. For A∗A^* an observer of signatures knows one bit of every kik_i; this is the hidden number problem with one known bit per sample, equivalently a half-range nonce after the substitution k=2k′+bk=2k^\prime+b. The best known attack is Bleichenbacher’s at 2N/52^{N/5} (Aranha et al. [23]), about 2522^{52} for 256 bits by scaling, 2472^{47} by the model of § 9. A generic reduction AI-PRF-distinguisher ⇒A∗\Rightarrow A^*-distinguisher would therefore yield a polynomial-time distinguisher for signatures with one-bit nonce bias. The separation holds conditionally on the one-bit HNP being hard, which is the same assumption the practical relevance of RFC 6979 rests on. [O]

AI-PRF does not imply A∗A^*: a natural candidate that fails

A separating predicate π(x,k)\pi(x,k) must (i) be computable by the signer, who knows xx; (ii) not be computable from (Q,k)(Q,k), else the AI-PRF distinguisher sees it; (iii) be efficiently detectable from the transcript (Q,R,s,h)(Q,R,s,h), else A∗A^* is not violated. The natural candidate is π(x,k)=lsb⁡(xk mod n)\pi(x,k)=\operatorname{lsb}(xk\bmod n). (Conditions on the point kQkQ fail (ii): the AI-PRF distinguisher computes kQkQ itself.)

Construction. Let PP be a PRF with an independent key zz and define

F(x,z)(h):=Pz(h,i∗),i∗=min⁡{i:lsb⁡ℓ(x⋅Pz(h,i) mod n)=0ℓ}.(2)F^{(x,z)}(h):=P_z(h,i^*),\qquad i^*=\min\{i:\operatorname{lsb}_{\ell}(x\cdot P_z(h,i)\bmod n)=0^{\ell}\}. \tag*{(2)}

The expected number of trials is 2ℓ2^{\ell}. The PRF key must not be xx itself, since the AI-PRF security of PxP_x at known QQ is the assumption under study.

Simulatability of a signature. For uniform hh and kk, the tuple (Q,R,s,h)(Q,R,s,h) has the same distribution as the tuple built without xx:

a←Zn,b←Zn∗,R=aG+bQ,r=x(R) mod n,s=rb−1,h=arb−1,(3)a\gets\mathbb{Z}_n,\quad b\gets\mathbb{Z}_n^*,\quad R=aG+bQ,\quad r=x(R)\bmod n,\quad s=rb^{-1},\quad h=arb^{-1}, \tag*{(3)}

under which k=a+bxk=a+bx and xk≡ax+bx2(modn)xk\equiv ax+bx^2\pmod n; the inverse map is a=s−1ha=s^{-1}h, b=s−1rb=s^{-1}r. This is the observation underlying Fersch, Kiltz and Poettering [12]. Consequently an observer of one signature solves “lsb⁡(ax+bx2 mod n)\operatorname{lsb}(ax+bx^2\bmod n) from (Q,a,b)(Q,a,b)” with uniform (a,b)(a,b). [T]

Theorem 5.1 (one signature). A predictor of lsb⁡(xk mod n)\operatorname{lsb}(xk\bmod n) from (Q,R,s,h)(Q,R,s,h) with advantage δ\delta over 1/21/2, for uniform hh and kk, yields a DLP solver running in time poly⁡(log⁡n,1/δ)\operatorname{poly}(\log n,1/\delta). [T]

Proof. By (3) the reduction constructs the tuple for any chosen (a,b)(a,b) and so obtains an oracle B~(a,b)\widetilde{B}(a,b) predicting lsb⁡(ax+bx2 mod n)\operatorname{lsb}(ax+bx^2\bmod n). By Markov’s inequality there is b0b_0 for which g(a):=B~(a,b0)g(a):=\widetilde{B}(a,b_0) predicts lsb⁡([ax+c0]n)\operatorname{lsb}([ax+c_0]_n), c0=b0x2c_0=b_0x^2, with advantage ≥δ/2\geq\delta/2. Lemma 5.2 recovers xx. □\square

RegimeAI-PRFA∗A^*Separation
q=1q = 1, ℓ=1\ell= 1holds under PRF + DLP [T]holds under PRF + DLP (Thm. 5.1) [T]no
q>1q > 1, ℓ≥4\ell\ge4broken: 1D-HNP, lattice [T]broken: 2D-HNP, lattice [T]no
q>1q > 1, ℓ=1\ell= 1conditional on 1-bit 1D-HNPconditional on 1-bit 2D-HNPno

Table 2. Status of the candidate F′′F'' by number of queries qq and filter width ℓ\ell.

Lemma 5.2 (ACGS with an unknown shift). Let x∈Zn∗x \in\mathbb{Z}_n^*, let c0∈Znc_0 \in\mathbb{Z}_n be unknown, and let g:Zn→{0,1}g : \mathbb{Z}_n \to\{0,1\} satisfy Pr⁡a[g(a)=lsb⁡([ax+c0]n)]≥12+ε\Pr_a[g(a) = \operatorname{lsb}([ax+c_0]_n)] \ge\frac{1}{2} + \varepsilon. Then O(ε−2log⁡n)O(\varepsilon^{-2}\log n) non-adaptive queries to gg and O(ε−5log⁡n)O(\varepsilon^{-5}\log n) time recover xx with probability ≥3/4\ge3/4. [T]

Proof sketch. Follow Alexi, Chor, Goldreich and Schnorr [15] (in the form of Fischlin and Schnorr [16]). Query points ak,i=2−k+iu+va_{k,i}=2^{-k}+iu+v for random (u,v)(u,v), k=0,…,⌈log⁡2n⌉k=0,\ldots,\lceil\log_2 n\rceil, i=1,…,mi=1,\ldots,m. Then ak,ix+c0≡2−kx+iY+Za_{k,i}x+c_0 \equiv2^{-k}x+iY+Z with Y=[ux]nY=[ux]_n and Z=[vx+c0]nZ=[vx+c_0]_n. The unknown shift enters only through ZZ, whose least significant bit and coarse approximation are enumerated exactly as ACGS enumerates them for [vx]n[vx]_n; the search space does not grow. The ak,ia_{k,i} are pairwise independent in ii because nn is prime, so Chebyshev’s inequality bounds the error of the majority vote at each halving step; a union bound over the ⌈log⁡2n⌉+1\lceil\log_2 n\rceil+1 steps gives success probability 3/43/4 with m=⌈8log⁡2n/ε2⌉m=\lceil8\log_2 n/\varepsilon^2\rceil. The final candidate 2K⌈nγK⌉ mod n2^K\lceil n\gamma_K\rceil\bmod n is checked against xG=QxG=Q. Full details are in Appendix § 11. □

Corollary 5.3 (q=1q=1). With one signing query, F′′F'' with ℓ=1\ell=1 satisfies both AI-PRF (Yao’s lemma plus the hardcore property of the least significant bit of the discrete logarithm [17]; no hybrid is needed) and A∗A^* (Theorem 5.1), assuming PP is a PRF and DLP is hard. It does not separate the notions. For ℓ>1\ell>1 the simultaneous hardcore property of ℓ\ell bits is needed. [T][L]

Theorem 5.4 (q>1q>1). For q>1q>1 signing queries, neither side of F′′F'' reduces to DLP:

  1. The hybrid argument fails for AI-PRF: Yao’s lemma over qq samples with a common secret xx requires the reduction to sample ki∈Sx={k:lsb⁡(xk mod n)=0}k_i \in S_x=\{k:\operatorname{lsb}(xk\bmod n)=0\} without knowing xx, which is the bit it is trying to predict. The AI-PRF game for F′′F'' is the one-dimensional HNP

(2−ℓki)x mod n∈[0,n/2ℓ),i=1,…,q.(2^{-\ell k_i})x \bmod n \in[0,n/2^\ell), \qquad i=1,\ldots,q.
  1. On the A∗A^* side the hint sis_i eliminates kik_i: xki≡aix+biyxk_i \equiv a_i x+b_i y with y=x2y=x^2, and the filter gives the two-dimensional HNP

(2−ℓai)x+(2−ℓbi)y mod n∈[0,n/2ℓ),i=1,…,q.(2^{-\ell a_i})x+(2^{-\ell b_i})y \bmod n \in[0,n/2^\ell), \qquad i=1,\ldots,q.

For ℓ≥4\ell\ge4 on a 256-bit curve both are solved by the Boneh–Venkatesan lattice [18], the AI-PRF side in lower dimension and with half the samples. For ℓ=1\ell=1 both are conditional on the hardness of one-bit HNP, in one and two dimensions respectively. A separation would require “1D-HNP hard, 2D-HNP easy”, for which there is no evidence. [T]

Remark 5.5 (oracle separation). F′′F'' does separate the notions relative to an oracle. Let HH be a random oracle and let QQ(R,s,m)Q_Q(R,s,m) return lsb⁡(CDH⁡(Q,R))\operatorname{lsb}(\operatorname{CDH}(Q,R)) when r=x(R) mod n≠0r=x(R)\bmod n\ne0, s∈Zn∗s\in\mathbb{Z}_n^* and sR=H(m)G+rQsR=H(m)G+rQ, and ⊥\perp otherwise. An observer of one such break has A∗A^* with advantage 1/21/2, while AI-PRF at q=1q=1 holds up to the probability of a key-only forgery under QQ, which reduces to DLP in the bijective random-oracle model of [12]: the reduction answers ⊥\perp throughout, and the hash-free forgery R=aG+bQR=aG+bQ does not qualify because h=ar/b≠H(m)h=ar/b\ne H(m). The oracle must be bound to QQ; one that accepts arbitrary keys Q∗Q^* admits a rogue-key attack (R:=Q,s:=1,Q∗:=r−1(R−H(m)G))(R:=Q,s:=1,Q^*:=r^{-1}(R-H(m)G)). Section 5.3 makes the oracle unnecessary. [T]

Remark 5.6. Candidates of the type of F′′F'' fail for a simple reason: a relation between the nonce kik_i and xx that the signature equation siki=hi+rixs_i k_i=h_i+r_i x exposes is exposed more directly by the public pair (Q,ki)(Q,k_i) in the AI-PRF game. [O]

AI-PRF does not imply A*: standard-model separations

F′′F^{\prime\prime} places the relation between the nonce and xx in the output of the nonce function, where the AI-PRF adversary reads it off. The three constructions below hide it elsewhere: in an input that only a signature reveals, in a PRF key derived from a point that only a signature reveals, and in one bit of a signature scalar, which a nonce observer knows only in the exponent. Write r(k)=x(kG) mod nr(k)=x(kG)\bmod n. Since p<2np<2n, at most two field elements reduce to a given rr and each is the abscissa of at most two points, so at most four scalars kk share a value r(k)r(k).

Theorem 5.7 (planted collision: one key, two chosen digests). Let PP be a nonce function with outputs in Zn∗\mathbb{Z}_n^* that satisfies AI-PRF at Q=xGQ=xG. Put a=Px(0)a=P_x(0) and

Fx†(h)={a,ah∈{x,−x},Px(h),otherwise.F_x^{\dagger}(h)=\begin{cases} a, & ah\in\{x,-x\},\\ P_x(h), & \text{otherwise}. \end{cases}
  1. For every distinguisher DD there are BB and CC, running in the time of DD plus one scalar multiplication per query, with

Adv⁡Fx†AI-PRF(D)≤Adv⁡PAI-PRF(B)+Pr⁡[C(xG)=x].\operatorname{Adv}_{F_x^{\dagger}}^{\mathrm{AI\text{-}PRF}}(D)\le\operatorname{Adv}_{P}^{\mathrm{AI\text{-}PRF}}(B)+\Pr[C(xG)=x].

There is no factor in the number of queries.

  1. There is a distinguisher D†D^{\dagger} making two signing queries with

Adv⁡A∗(D†)≥1−Adv⁡PAI-PRF(B′)−8n−9,\operatorname{Adv}_{A^*}(D^{\dagger})\ge1-\operatorname{Adv}_{P}^{\mathrm{AI\text{-}PRF}}(B')-\frac{8}{n-9},

also against a signer that normalizes to low ss. The two signatures reveal xx.

[T]

Proof. (1) BB receives QQ and an oracle OO, asks a=O(0)a=O(0), and answers a query hh of DD with aa if (ah)G∈{Q,−Q}(ah)G\in\{Q,-Q\} and with O(h)O(h) otherwise. For O=PxO=P_x this is exactly Fx†F_x^{\dagger}. For a random function O=RO=\mathcal{R} the answers are those of R\mathcal{R} unless DD submits an exceptional hh; CC runs the same simulation with a lazily sampled R\mathcal{R} and, at the first exceptional query, outputs ahah or −ah-ah according to which point matched. The simulator recognizes the hit itself, so no query index is guessed.

(2) D†D^{\dagger} queries the digest 00, receives (r0,s0)(r_0,s_0) and computes t=s0/r0t=s_0/r_0. The raw signature scalar is a−1r0xa^{-1}r_0x, so t=±x/at=\pm x/a, the sign depending on normalization; this is why both signs are exceptional. D†D^{\dagger} picks h∈{t,−t}h\in\{t,-t\} with hG+r0Q≠OhG+r_0Q\ne O, which holds for at least one sign because t≠0t\ne0, queries hh, and outputs 1 iff r1=r0r_1=r_0. In the real game ah=±xah=\pm x, so the nonce is aa again and r1=r0r_1=r_0; the choice of sign makes s1≠0s_1\ne0, so there is no retry. The real game fails only if r(a)=0r(a)=0, an event that is publicly testable from a=O(0)a=O(0) and therefore has probability at most 4/(n−1)+Adv⁡PAI-PRF(B′)4/(n-1)+\operatorname{Adv}_{P}^{\mathrm{AI\text{-}PRF}}(B'). In the ideal game h≠0h\ne0 is fresh and the nonce is uniform among the at least n−9n-9 valid candidates, of which at most four give r1=r0r_1=r_0.

For key recovery, the raw scalars satisfy as0=r0xas_0=r_0x and as1=h+r0xas_1=h+r_0x, hence a=h/(s1−s0)a=h/(s_1-s_0) and x=as0/r0x=as_0/r_0; under low-ss normalization the four sign combinations are tried and tested against QQ.

Remark 5.8 (scope of Theorem 5.7). A discrete-logarithm solver distinguishes PxP_x from a random function at known QQ, so Pr⁡[C(xG)=x]≤2Adv⁡PAI-PRF(C′)\Pr[C(xG)=x]\le2\operatorname{Adv}_{P}^{\mathrm{AI\text{-}PRF}}(C'); the theorem assumes only that some AI-PRF exists, and turns it into one under which signing leaks the key. The secret xx is the only key; no independent seed is used. The attack needs digests of the adversary’s choice, namely 00 and ±x/a\pm x/a. The anchor 00 can be replaced by any fixed digest h0h_0 by planting the collision at ah=±(h0+r(a)x)ah=\pm(h_0+r(a)x), that is at h=±s0h=\pm s_0, which is tested publicly by (ah)G=±(h0G+r(a)Q)(ah)G=\pm(h_0G+r(a)Q). The second digest still depends on the first signature, so the attack does not pass through a

hash function without computing preimages; Theorem 5.9 removes this restriction at the price of a stronger assumption. No comparable attack on Rand-ECDSA is known: key recovery with a chosen-digest signing oracle is the assumption DLP-Sign of Theorem 6.1. [T]

Theorem 5.9 (hidden seed: one key, two hashed messages). Let λ=⌈log⁡2p⌉\lambda= \lceil\log_{2} p \rceil and κ=⌊λ/4⌋\kappa= \lfloor\lambda/4 \rfloor, let PP be a PRF with κ\kappa-bit keys and outputs in Zn∗\mathbb{Z}_{n}^{*}, and let m0m_{0} be a fixed public message with digest h0h_{0}. Fix a representation of the field F2λ\mathbb{F}_{2^{\lambda}} and write ⊙\odot for its multiplication, applied to abscissas read as λ\lambda-bit strings (the point at infinity is encoded by pp). For a signing key xx with Q=xGQ = xG let

W=x2G,J=⌊2κx(W)p⌋,a=PJ(h0),c=h0r(a),T=a−1(W−c2G),W = x^{2}G,\qquad J = \left\lfloor\frac{2^{\kappa}x(W)}{p} \right\rfloor,\qquad a = P_{J}(h_{0}),\qquad c = \frac{h_{0}}{r(a)},\qquad T = a^{-1}(W-c^{2}G),

with c=0c=0 if r(a)=0r(a)=0, let L=msb⁡κ(x(Q)⊙x(T))L=\operatorname{msb}_{\kappa}(x(Q)\odot x(T)), and define

Fx♯(h)={PJ(h),h=h0,PL(h),h≠h0.F_{x}^{\sharp}(h)= \begin{cases} P_{J}(h), & h=h_{0},\\ P_{L}(h), & h\ne h_{0}. \end{cases}

Candidates rejected by the signer are replaced by including a retry counter in the PRF input. On secp256k1, where κ=64\kappa=64:

  1. for every distinguisher DD, making any number of adaptive queries,

Adv⁡F♯AI-PRF(D)≤Adv⁡DSDH(B)+Adv⁡PPRF(B1)+Adv⁡PPRF(B2)+2−55.9,\operatorname{Adv}_{F^{\sharp}}^{\mathrm{AI\text{-}PRF}}(D) \le\operatorname{Adv}^{\mathrm{DSDH}}(B) + \operatorname{Adv}_{P}^{\mathrm{PRF}}(B_{1}) + \operatorname{Adv}_{P}^{\mathrm{PRF}}(B_{2}) + 2^{-55.9},

where Adv⁡DSDH(B)\operatorname{Adv}^{\mathrm{DSDH}}(B) is the advantage of BB in distinguishing (Q,x2G)(Q,x^{2}G) from (Q,W)(Q,W) with WW a uniform point independent of QQ;

  1. an adversary that sees QQ and the signatures on m0m_{0} and on one further message m1m_{1} of its choice recovers xx, except with probability at most Adv⁡F♯AI-PRF(D′)+8/(n−1)\operatorname{Adv}_{F^{\sharp}}^{\mathrm{AI\text{-}PRF}}(D') + 8/(n-1), and then signs any message. This holds in the hashed-message game and against a signer that normalizes to low ss.

[T]

Proof. (1) The whole nonce oracle is a function of the two points (Q,W)(Q,W): BB computes JJ, aa, cc, TT and LL from them without knowing xx and answers every query. For W=x2GW=x^{2}G this is Fx♯F_{x}^{\sharp}, so replacing WW by an independent uniform point costs Adv⁡DSDH(B)\operatorname{Adv}^{\mathrm{DSDH}}(B), for adaptive queries on arbitrary digests. In that hybrid two statistical facts suffice.

JJ is close to uniform. The value J=jJ=j corresponds to an interval of abscissas of length p/2κp/2^{\kappa}. The character-sum estimate in the proof of Proposition 8.2 applies to every interval, so the number NjN_{j} of points in the jj-th bucket differs from n/2κn/2^{\kappa} by at most D+3D+3 with D<2137.06D<2^{137.06}, and the statistical distance of JJ from uniform is at most 2κ−1(D+3)/n<2−55.92^{\kappa-1}(D+3)/n<2^{-55.9}.

LL is close to uniform given QQ and JJ. Condition on J=jJ=j. Then aa and cc are fixed, WW is uniform on NjN_{j} points and W↦a−1(W−c2G)W\mapsto a^{-1}(W-c^{2}G) is a bijection, so TT is uniform on NjN_{j} points. An abscissa has at most two preimages, so the collision probability of x(T)x(T) is at most 2/Nj2/N_{j}, and on average over jj at most ∑j(Nj/n)(2/Nj)≤2κ+1/n\sum_{j}(N_{j}/n)(2/N_{j})\le2^{\kappa+1}/n. For a uniform multiplier uu the family v↦msb⁡κ(u⊙v)v\mapsto\operatorname{msb}_{\kappa}(u\odot v) is universal, and the average-case leftover hash lemma [21] bounds the distance of LL from uniform by 1222κ+1/n\frac{1}{2}\sqrt{2^{2\kappa+1}/n}. The actual multiplier x(Q)x(Q) is independent of (J,T)(J,T) and takes each value with probability at most 2/(n−1)2/(n-1), which is at most 2λ+1/(n−1)<2.012^{\lambda+1}/(n-1)<2.01 times the uniform probability; the bound becomes 2−63.52^{-63.5}.

Hence (Q,J,L)(Q,J,L) is within 2−55.92^{-55.9} of (Q,U,U′)(Q,U,U') for independent uniform keys, and two PRF steps, on the disjoint domains {h0}\{h_{0}\} and its complement, turn the oracle into a random function.

(2) The raw scalar of the first signature is s0=a−1(h0+r0x)=(r0/a)(x+c)s_0 = a^{-1}(h_0+r_0x) = (r_0/a)(x+c) with r0=r(a)r_0 = r(a), so

s0r0(Q−cG)=(x+c)(x−c)aG=x2−c2aG=T.\frac{s_0}{r_0}(Q-cG)=\frac{(x+c)(x-c)}{a}G=\frac{x^2-c^2}{a}G=T.

Everything on the left is public once the signature is seen, since c=h0/r0c=h_0/r_0. Low-ss normalization may replace s0s_0 by −s0-s_0 and TT by −T-T, which has the same abscissa. One signature therefore yields LL, the key of every non-anchor nonce. The adversary computes k1=PL(h1)k_1=P_L(h_1), reproducing retries because the validity of a candidate is publicly testable from (Q,h1,k1)(Q,h_1,k_1), and obtains x=(±k1s1−h1)/r1x=(\pm k_1s_1-h_1)/r_1, testing both signs against QQ. The attack fails only if the first anchor candidate is rejected, that is if r(a)=0r(a)=0 or Q=−cGQ=-cG; both events are publicly testable from a=Fx‡(h0)a=F^\ddagger_x(h_0) and QQ, so their probability is bounded by part (1). □

Remark 5.10 (scope of Theorem 5.9). The decisional square Diffie–Hellman assumption [20] is at least as strong as DDH, since a DDH oracle decides it, and it holds in the generic group model. It enters because the reduction must evaluate the oracle from (Q,x2G)(Q,x^2G); Theorem 5.13 replaces it by ordinary DDH at a price listed in Table 3. Compare F′F' of § 4: there the PRF key is a function of QQ alone, so AI-PRF fails; here the key LL depends in addition on the point TT, which is hidden behind x2Gx^2G and which one signature reveals. With κ=64\kappa=64 the instance has a 2642^{64} exhaustive-search ceiling on its AI-PRF security (search for JJ from aa); the separation is asymptotic, with κ=⌊λ/4⌋\kappa=\lfloor\lambda/4\rfloor, while the key recovery is concrete. We ran it on 16 secp256k1 keys with the messages 0, 1 and a forgery on 2: an independent ECDSA verifier accepted all 16 forgeries, covering the four combinations of low-ss sign changes, and the oracle computed from (Q,x2G)(Q,x^2G) alone agreed with the signer on every tested key. [T][S]

Theorem 5.11 (ordering bit: hashed messages). Let PP be a PRF with outputs in Zn∗\mathbb{Z}_n^* and a key zz independent of xx, and fix three public messages m0,m1,m2m_0,m_1,m_2 with distinct digests h0,h1,h2h_0,h_1,h_2; for SHA-256 the one-byte messages 0, 1, 2 qualify. Let a=Pz(h0)a=P_z(h_0), u=Pz(h1)u=P_z(h_1), v=Pz(h2)v=P_z(h_2), s0=a−1(h0+r(a)x)s_0=a^{-1}(h_0+r(a)x) and

β(s)=1{min⁡([s]n,[−s]n)≤⌊n/4⌋}.\beta(s)=\mathbf{1}\{\min([s]_n,[-s]_n)\le\lfloor n/4\rfloor\}.

Define F(x,z)‡(h0)=aF^\ddagger_{(x,z)}(h_0)=a; let (F‡(h1),F‡(h2))(F^\ddagger(h_1),F^\ddagger(h_2)) be (u,v)(u,v) or (v,u)(v,u), whichever makes r(F‡(h1))<r(F‡(h2))r(F^\ddagger(h_1))<r(F^\ddagger(h_2)) equivalent to β(s0)=1\beta(s_0)=1, with ties in rr broken by the scalar and the pair left as (u,v)(u,v) if r(a)=0r(a)=0 or s0=0s_0=0; and F‡(h)=Pz(h)F^\ddagger(h)=P_z(h) for every other hh. On secp256k1:

  1. for every distinguisher DD, making any number of adaptive queries,

Adv⁡F‡AI-PRF(D)≤Adv⁡PPRF(B)+2Adv⁡β(C)+O(1/n),\operatorname{Adv}^{\mathrm{AI\text{-}PRF}}_{F^\ddagger}(D)\le\operatorname{Adv}^{\mathrm{PRF}}_P(B)+2\operatorname{Adv}^{\beta}(C)+O(1/n),

where Adv⁡β(C)\operatorname{Adv}^{\beta}(C) is the advantage over 1/21/2 of CC in predicting β(y)\beta(y) from yGyG for uniform yy; a predictor with advantage ϵ\epsilon yields a DLP solver running in time poly⁡(log⁡n,1/ϵ)\operatorname{poly}(\log n,1/\epsilon);

  1. the distinguisher D‡D^\ddagger that requests signatures on m0,m1,m2m_0,m_1,m_2 and outputs 1 iff {r1<r2}=β(s0)\{r_1<r_2\}=\beta(s_0) has Adv⁡A∗(D‡)≥1/2−O(1/n)\operatorname{Adv}_{A^*}(D^\ddagger)\ge1/2-O(1/n), in the hashed-message game and against a signer that normalizes to low ss.

[T]

Proof. (1) Replace PzP_z by a random function; the PRF distinguisher BB samples xx itself. The view of DD is now determined by QQ, aa, the unordered pair {u,v}\{u,v\}, the bit β(s0)\beta(s_0) and independent uniform values. If β(s0)\beta(s_0) is replaced by an independent fair bit, the pair (F‡(h1),F‡(h2))(F^\ddagger(h_1),F^\ddagger(h_2)) is exactly uniform, because arranging two independent uniform draws in an order chosen by a fair coin restores their joint distribution. One bit is involved, so a distinguisher yields a predictor

of β(s0)\beta(s_0) from (Q,a)(Q,a) with half the advantage, and no hybrid over a shared secret is needed (compare Theorem 5.4).

Given a challenge Y=yGY=yG with uniform yy, sample aa uniformly with r(a)≠0r(a)\ne0 and set Q=r(a)−1(aY−h0G)Q=r(a)^{-1}(aY-h_0G). For fixed aa the map y↦x=(ay−h0)/r(a)y\mapsto x=(ay-h_0)/r(a) is an affine bijection of Zn\mathbb{Z}_n, so (Q,a)(Q,a) is distributed as in the game up to the event x=0x=0, and s0=ys_0=y exactly; fixing the digest h0h_0 in advance is what makes this embedding possible. A predictor of β(s0)\beta(s_0) from (Q,a)(Q,a) therefore predicts β(y)\beta(y) from YY.

Finally, n=4ν+1n=4\nu+1 on secp256k1, and β(y)=1{[y+ν]n≤2ν}=1−lsb⁡([2(y+ν)]n)\beta(y)=1\{[y+\nu]_n\le2\nu\}=1-\operatorname{lsb}([2(y+\nu)]_n). For a uniform point W=wGW=wG put Y=2−1W−νGY=2^{-1}W-\nu G; then β(y)=1−lsb⁡(w)\beta(y)=1-\operatorname{lsb}(w). Applying the predictor to cWcW for chosen cc gives an oracle for lsb⁡([cw]n)\operatorname{lsb}([cw]_n) that is correct with probability 1/2+ε1/2+\varepsilon over uniform cc, and Lemma 5.2 with c0=0c_0=0 recovers ww.

(2) β(−s)=β(s)\beta(-s)=\beta(s) and normalization does not change rr, so the test is unaffected by it. In the real game the relation holds by construction unless a candidate is rejected, probability O(1/n)O(1/n). In the ideal game the nonces at h1h_1 and h2h_2 are independent, uniform, and independent of the first signature, so 1{r1<r2}1\{r_1<r_2\} is a fair coin up to ties, which have probability at most 4/(n−1)4/(n-1). □

Remark 5.12 (A* is not necessary). Det-ECDSA with F†F^\dagger is as unforgeable as Rand-ECDSA, although it violates A*. After the PRF step, a forger against Rand-ECDSA simulates the signer by resampling, as in Theorem 8.1: whenever a signature on one of m0,m1,m2m_0,m_1,m_2 is requested, it draws fresh signatures on that message until the relation 1{r1<r2}=β(s0)1\{r_1<r_2\}=\beta(s_0) is consistent with those already issued (when β(s0)\beta(s_0) is known and m1m_1 is asked before m2m_2, it keeps the smaller or larger rr of two draws). The expected number of extra queries is constant and all of them are on messages the adversary asked for, so its forgery stays fresh. Theorems 5.7 and 5.9, in contrast, destroy the scheme. [T]

Trading the assumption against setup, secrets and queries. Theorem 5.9 uses the square x2Gx^2G because the hidden point must be computable from xx and from nothing else. Each of the three variants below gives up one feature of that theorem and weakens the assumption in return. Write E(V)=⌊2κx(V)/p⌋E(V)=\lfloor2^\kappa x(V)/p\rfloor with E(O)=0E(O)=0, and r′=r(a)r'=r(a) if r(a)≠0r(a)\ne0, r′=1r'=1 otherwise.

Theorem 5.13 (variants of the hidden seed). With the notation of Theorem 5.9, on secp256k1, each nonce function below satisfies AI-PRF against any number of adaptive queries on arbitrary digests, and its key is recovered from signatures on ordinary hashed messages, also against a signer that normalizes to low ss.

(a) A public point; DDH; two signatures. Let BB be a uniform non-identity point, sampled independently of xx and published. Put W=xBW=xB, J=E(W)J=E(W), a=PJ(h0)a=P_J(h_0), T=a−1(h0B+r′W)T=a^{-1}(h_0B+r'W) and L=msb⁡κ(x(Q)⊙x(T))L=\operatorname{msb}_\kappa(x(Q)\mathbin{\odot} x(T)); the nonce is PJ(h)P_J(h) at h0h_0 and PL(h)P_L(h) elsewhere. With the probability taken also over BB,

Adv⁡AI-PRF(D)≤Adv⁡DDH(B0)+Adv⁡PPRF(B1)+Adv⁡PPRF(B2)+2−55.9.\operatorname{Adv}^{\mathrm{AI\text{-}PRF}}(D)\le\operatorname{Adv}^{\mathrm{DDH}}(B_0)+\operatorname{Adv}^{\mathrm{PRF}}_P(B_1)+\operatorname{Adv}^{\mathrm{PRF}}_P(B_2)+2^{-55.9}.

and T=s0BT=s_0B, so the signatures on m0m_0 and on one further message reveal xx as in Theorem 5.9.

(b) No setup, one key; DDH and an AI-PRF; about 4λ4\lambda signatures. Let AA be a nonce function with outputs in Zn∗\mathbb{Z}_n^* satisfying AI-PRF at QQ. From outputs of AxA_x at reserved inputs derive scalars aa and dd, λ2\lambda^2 coin bits (the parities of fresh outputs) and 2λ22\lambda^2 further scalars. Put B=dGB=dG and L=E(da−1(h0G+r′Q))L=E(d a^{-1}(h_0G+r'Q)). Fix 2λ22\lambda^2 public carrier messages with distinct digests, different from h0h_0, arranged in λ\lambda blocks of λ\lambda pairs. Arrange the coins in λ\lambda words of λ\lambda bits and replace the first word that is the abscissa of a curve point by x(B)x(B). The nonce is aa at h0h_0; on the jj-th pair of block ii it is the two scalars reserved for that pair, in increasing order of f(r,k)f(r,k) if bit jj of word ii is 00 and in decreasing order otherwise; and PL(h)P_L(h) at every other digest, the reserved inputs included. Then

Adv⁡AI-PRF(D)≤Adv⁡AAI-PRF(B0)+Adv⁡DDH(B1)+Adv⁡PPRF(B2)+2−55.9+O(1/n).\operatorname{Adv}^{\mathrm{AI\text{-}PRF}}(D)\le\operatorname{Adv}^{\mathrm{AI\text{-}PRF}}_A(B_0)+\operatorname{Adv}^{\mathrm{DDH}}(B_1)+\operatorname{Adv}^{\mathrm{PRF}}_P(B_2)+2^{-55.9}+O(1/n).

An adversary reads x(B)x(B) from the order of the values rr on the carrier messages, block by block up to the first valid word, and continues as in (a) with L=E(s0B)L = E(s_0B). It asks for 2+2λ/ρ≈10262 + 2\lambda/\rho\approx1026 signatures in expectation, where ρ=(n−1)/2λ+1\rho= (n - 1)/2^{\lambda+1}, and for at most 2+2λ22 + 2\lambda^2.

(c) Two secrets; an AI-PRF alone; two signatures. Let the signer hold, besides xx, an independent uniform a∈Zn∗a \in\mathbb{Z}_n^*, and let AyA_y satisfy AI-PRF at yGyG. Put s=a−1(h0+r(a)x)s = a^{-1}(h_0 + r(a)x); the nonce is aa at h0h_0 and As(h)A_s(h) elsewhere (with a fixed fallback if r(a)=0r(a) = 0 or $s = 0). Then Adv⁡AI-PRF(D)≤Adv⁡AAI-PRF(B0)+O(1/n)\operatorname{Adv}^{\mathrm{AI\text{-}PRF}}(D) \le\operatorname{Adv}^{\mathrm{AI\text{-}PRF}}_A(B_0) + O(1/n), and the first signature reveals ±s\pm s, the key of every later nonce.

[T]

Proof. (a) The oracle is a function of the three points (Q,B,W)(Q, B, W), and ordinary DDH [19] replaces W=xBW = xB by a uniform point independent of QQ and BB; this is where the independent point removes the square. Given BB and JJ the map W↦TW \mapsto T is an affine bijection, because r′≠0r' \ne0, and the statistical argument of Theorem 5.9 applies unchanged. For a valid anchor, h0B+r(a)W=(h0+r(a)x)Bh_0B + r(a)W = (h_0 + r(a)x)B, so T=s0BT = s_0B, and its abscissa is unaffected by the sign of s0s_0. The bound is an average over BB: for a point whose discrete logarithm β\beta the adversary knows, W=βQW = \beta Q and the function is not an AI-PRF.

(b) First replace AxA_x by a random function. The reduction to the AI-PRF security of AA learns aa, dd, the coins and the reserved scalars from its oracle and computes da−1(h0G+r′Q)d a^{-1}(h_0G + r'Q) from QQ, so it answers every query without xx. Next, da−1(h0G+r′Q)=a−1(h0B+r′xB)d a^{-1}(h_0G + r'Q) = a^{-1}(h_0B + r'xB) with B=dGB = dG uniform, and apart from this point dd is used only through x(B)x(B); a DDH challenge (Q,B,W)(Q, B, W) therefore replaces xBxB by a uniform WW. The hidden point is then uniform and independent of (Q,B,a)(Q, B, a), its bucket LL is within 2−55.92^{-55.9} of uniform, and a PRF step makes all outputs outside h0h_0 and the carriers random. Finally, every abscissa is that of exactly two points, so x(B)x(B) is uniform on the set of valid words, which is the conditional distribution of the word it replaces given its position and all other words: the replacement preserves the joint distribution of the words, the no-valid-word case included. The bits are exactly fair, since n−1n - 1 is even, and independent of the reserved scalars, and ordering two independent uniform scalars by a fair bit restores their joint distribution, as in the proof of Theorem 5.11. For the attack, the bit of a pair is 1{r>r~}1\{r > \tilde r\} for its two signatures; either point with the recovered abscissa serves as BB, because E(s0B)E(s_0B) depends on the abscissa only. A valid word fails to appear with probability (1−ρ)λ=2−256(1-\rho)^\lambda= 2^{-256}, and ties or rejected candidates on the carriers have probability O(λ2/n)O(\lambda^2/n).

(c) Given an AI-PRF challenge (Y=yG,O)(Y = yG, O) for AA, sample aa and present Q=r(a)−1(aY−h0G)Q = r(a)^{-1}(aY - h_0G), as in the proof of Theorem 5.11: xx is uniform up to O(1/n)O(1/n) and s=ys = y exactly. Answer h0h_0 with aa and every other digest with OO. This is the construction if O=AyO = A_y and a random function if OO is one. The embedding uses the independence of aa from xx; with a=Ax(h0)a = A_x(h_0) the key ss would be related to xx, and that step is not proved. □

Remark 5.14 (what remains). A pseudorandom function exists if DDH is hard, so (a) rests on DDH alone. We checked the variants on secp256k1 with HMAC-SHA-256 as a functional stand-in for PP and AA: 16 two-signature key recoveries for (a) and 16 for (c), covering the four combinations of low-ss sign changes, and 10 for (b), which needed 514, 1026 or 2050 signatures; every forgery on a fresh message was accepted by an independent verifier. Such runs test the constructions and say nothing about HMAC. No row of Table 3 achieves everything at once: two hashed-message signatures, the original parameters, xx as the only secret, and no assumption beyond DLP or the existence of an AI-PRF. [T][S]

Summary. A∗A^* and AI-PRF are incomparable. AI-PRF is not sufficient: under the AI-PRF function F†F^\dagger two chosen-digest signatures reveal the key, and under F‡F^\ddagger, given DSDH, so do signatures on two ordinary hashed messages; Table 3 lists the variants under DDH. It is not necessary either, if one-bit HNP is hard (§ 5.1). A∗A^* is sufficient (Theorem 3.1) and not necessary (Remark 5.12). All of these separations concern constructed nonce functions; whether HMAC_DRBG satisfies A∗A^* is untouched by them.

What is provable

Theorem 6.1 (ideal compression function). Model the SHA-256 compression function as a random oracle ff. For every distinguisher DD for A∗A^* that makes qsq_s signing queries and qfq_f queries to ff there is an algorithm BB, running in time Time⁡(D)+O((qf+qs)log⁡n)\operatorname{Time}(D) + O((q_f + q_s)\log n) group operations, with

Adv⁡A∗(D)≤Adv⁡DLP-Sign(B)+16qs(qf+16qs)+qf2256,\operatorname{Adv}_{A^*}(D) \le\operatorname{Adv}^{\mathrm{DLP\text{-}Sign}}(B) + \frac{16q_s(q_f + 16q_s) + q_f}{2^{256}},

where Adv⁡DLP-Sign(B)\operatorname{Adv}^{\mathrm{DLP\text{-}Sign}}(B) is the probability that BB computes xx from QQ given a Rand-ECDSA signing oracle Sign⁡x(⋅;R)\operatorname{Sign}_x(\mathord{\cdot};\mathcal{R}). Moreover Adv⁡DLP-Sign(B)≤Adv⁡RandEUF-CMA(B′)\operatorname{Adv}^{\mathrm{DLP\text{-}Sign}}(B) \le\operatorname{Adv}^{\mathrm{EUF\text{-}CMA}}_{\mathrm{Rand}}(B'), and if h=H(m)h = H(m) for a programmable random oracle HH, Adv⁡DLP-Sign\operatorname{Adv}^{\mathrm{DLP\text{-}Sign}} can be replaced by Adv⁡DLP\operatorname{Adv}^{\mathrm{DLP}}. [T]

Proof. Without loss of generality DD never repeats hh, since both oracles in Assumption 2.2 are functions of hh; rejections in step H.3 are handled identically in all games. Each signing query costs at most 15 compression evaluations plus block 1 of step d, which is shared. Let Ask be the event that DD queries ff at an input whose last 31 bytes equal x[0..30]x[0..30] (§ 4.1). Game 0 is the real game; Game 1 aborts on Ask. Conditioned on ¬\negAsk, block 1 of steps d and f is evaluated at points DD never queries, so the chaining values they produce are uniform and hidden, and every later evaluation is at a fresh point unless an internal collision occurs or DD queries a hidden chaining value; this has probability at most (16qs(qf+16qs)+qf)/2256(16q_s(q_f + 16q_s) + q_f)/2^{256}. In Game 2 the nonces are therefore independent and uniform, which is the Sign⁡x(⋅;R)\operatorname{Sign}_x(\mathord{\cdot};\mathcal{R}) oracle. The games are identical until Ask or a collision, so it remains to bound Pr⁡[Ask]\Pr[\mathrm{Ask}] in Game 2. There BB receives QQ and the signing oracle, answers signing queries with it and ff-queries by lazy sampling, and keeps the table T={Q−bG:0≤b≤255}T = \{Q - bG : 0 \le b \le255\}. For every ff-query with tail ww it checks whether 28wG∈T2^8wG \in T, at the cost of one scalar multiplication, and on a hit outputs x=28w+bx = 2^8w + b. No query index is guessed, so there is no factor qfq_f. B′B' runs BB and forges with the recovered xx. If HH is programmable, the simulation (3) answers signing queries without xx. □\square

Remark 6.2. The distinguisher in Assumption 2.2 chooses hh itself. Without a programmable message hash, a DLP reduction cannot answer its signing queries (Proposition 3.2), so the ideal-compression-function argument yields A∗A^* from DLP in the presence of a signing oracle, not from plain DLP. Combined with Theorem 3.1, Adv⁡DetEUF-CMA≤2Adv⁡RandEUF-CMA+(16qs(qf+16qs)+qf)/2256\operatorname{Adv}^{\mathrm{EUF\text{-}CMA}}_{\mathrm{Det}} \le2\operatorname{Adv}^{\mathrm{EUF\text{-}CMA}}_{\mathrm{Rand}} + (16q_s(q_f + 16q_s) + q_f)/2^{256} up to the running-time overhead of BB.

Theorem 6.3 (independent nonce key). For Det′\mathrm{Det}'-ECDSA with k=Pz(h)k = P_z(h) and zz independent of xx (or (x,z)=PRG⁡(seed)(x,z) = \operatorname{PRG}(\mathrm{seed})),

Adv⁡Det′EUF-CMA(A)≤Adv⁡RandEUF-CMA(B)+Adv⁡PPRF(D)\operatorname{Adv}^{\mathrm{EUF\text{-}CMA}}_{\mathrm{Det}'}(A) \le\operatorname{Adv}^{\mathrm{EUF\text{-}CMA}}_{\mathrm{Rand}}(B) + \operatorname{Adv}^{\mathrm{PRF}}_{P}(D)

in the standard model. [T]

Proof. The PRF distinguisher DD knows xx (it is not the PRF key) and simulates signatures with the nonces returned by its oracle.

This is precisely the construction that RFC 6979 §3.6 describes as “additional secret data . . . may help in formally proving the security”. EdDSA [2] obtains it by splitting (a, prefix)=SHA-512⁡(seed)(a,\ \mathrm{prefix}) = \operatorname{SHA-512}(\mathrm{seed}). BIP-340 [3] does not: t=d⊕Haux(aux)t = d \oplus H_{\mathrm{aux}}(\mathrm{aux}), k=Hnonce(t∥P∥m)k = H_{\mathrm{nonce}}(t \parallel P \parallel m) still needs an A∗A^*-type assumption, discharged in the ROM. Table 4 summarizes.

SchemeAssumptionModelStatus
k=HMAC_DRBG⁡(x∥h)k = \operatorname{HMAC\_DRBG}(x\mathbin\Vert h), RFC 6979A∗A^{*}standardopen; no attack; falsifiable
sameDLP with a Rand-ECDSA signing oracle; plain DLP if HH programmableideal compression functionproved, no qHq_H factor
k=HMAC_DRBG⁡(x∥h∥k′)k = \operatorname{HMAC\_DRBG}(x\mathbin\Vert h\mathbin\Vert k^{\prime}), RFC 6979 §3.6A∗A^{*} for any k′k^{\prime}; nothing extra if k′k^{\prime} uniform and secretROMas above
BIP-340 SchnorrA∗A^{*}-analogue for tagged SHA-256ROMproved in ROM
k=Pz(h)k = P_z(h), zz independentPRF security of PPstandardproved
EdDSA prefixPRF security of HH with prefix as keystandard (ROM in [30])proved in ROM
F′(x,h)=PExt⁡(xG)(h)F^{\prime}(x,h)=P_{\operatorname{Ext}(xG)}(h)—standardPRF, but key revealed by one signature
RFC 6979 over f∗f^{*} (Section 4.1)—standard; f∗f^{*} has (A1), (A2), (A248′A^{\prime}_{248}) given CRPRF in xx, key revealed by one signature
F†F^{\dagger}, planted collision (Theorem 5.7)—standardAI-PRF, key revealed by two chosen-digest signatures
F‡F^{\ddagger}, hidden seed (Theorem 5.9)—standardAI-PRF under DSDH + PRF; key revealed by signatures on two hashed messages
Variants of F‡F^{\ddagger} (Theorem 5.13)—standardAI-PRF under DDH with a public point, or DDH and an AI-PRF, or an AI-PRF and a second secret; key revealed through hashed messages
F‡F^{\ddagger}, ordering bit (Theorem 5.11)—standardAI-PRF under PRF + DLP; A∗A^{*} fails with advantage 1/2; unforgeable

Table 4. Assumptions beyond the security of Rand-ECDSA.

Curve dependence of the standard part

A∗A^* itself is curve-independent. What depends on the curve is the standard part of a proof that HMAC_DRBG is a PRF in xx. In step d of RFC 6979 §3.2 the HMAC key is the public K0=0x0032K_0 = \mathtt{0x00}^{32}, and xx enters the message: bytes 0–30 fill the tail of block 1 and byte 31 opens block 2 (§ 4.1). Bellare’s PRF theorem for HMAC [5], which assumes a uniform secret key, therefore does not apply to step d. What step d needs is property (A2′248_{248}): f(IV1,V0∥0x00∥x[0..30])f(IV_1,V_0\mathbin\Vert\mathtt{0x00}\mathbin\Vert x_{[0..30]}) is pseudorandom. Once K1K_1 is pseudorandom, Bellare’s theorem applies to HMAC⁡K1\operatorname{HMAC}_{K_1} in the later steps. For xx uniform on [1,n−1][1,n-1], the secret tail x[0..30]=⌊x/256⌋x_{[0..30]} = \lfloor x/256 \rfloor is at statistical distance ≈(2256−n)/2256\approx(2^{256} - n)/2^{256} from uniform on {0,1}248\{0,1\}^{248}.

The same number governs every place in the secp256k1 stack where a 256-bit value is reduced modulo nn without rejection. For TT uniform on [0,2256)[0,2^{256}) and k=T mod nk = T \bmod n, the statistical distance from uniform, the Fourier coefficient ∣B1∣=∣Ee2πik/n∣|B_1| = |\mathbb{E}e^{2\pi i k/n}| relevant to Bleichenbacher’s attack, and Pr⁡[T≥n]\Pr[T \ge n] all equal 1.2708⋅2−128=2−127.6541.2708 \cdot2^{-128} = 2^{-127.654} to three digits [T]. A data threshold of order ∣B1∣−2≈2255|B_1|^{-2} \approx2^{255} signatures makes the bias irrelevant in practice; transplanted verbatim to P-256 the same operation gives 2−322^{-32} (threshold ≈264\approx2^{64}) and on brainpoolP256r1 0.1660.166 (lattice attacks with hundreds of signatures). RFC 9591 (FROST) requires ∣n−2256∣<2128|n - 2^{256}| < 2^{128} to skip the range check; secp256k1 misses this criterion by 0.35 bit, which changes nothing in practice. [T]

Deployed implementations

We reviewed the source of 31 secp256k1 implementations (18 libraries, 7 wallets and nodes, 6 hardware wallets) at their default branches on 2026-10-18, and libsecp256k1 at commit 04b91ce (2026-10-19). Line numbers refer to those snapshots. [S]

Nonce defaults

28 of 31 implementations (90%) sign ECDSA deterministically without additional entropy; none of the 18 libraries hedges by default although 9 expose an API for it. The exceptions are python-ecdsa (sign() draws a uniform kk), LDK (hedges its own commitment and sweep transactions) and BitBox02 (anti-klepto with host entropy). For BIP-340, 15 of 26 implementations sign with zero auxiliary randomness; Bitcoin Core’s source reads “Use uint256{} as aux_rnd for now”. The RFC 6979 §3.6 construction with an independent nonce key, which would discharge A∗A^* by Theorem 6.3, is used nowhere in the sample. [S]

Among general-purpose libraries the default differs: OpenSSL 3.x hedges (ossl_bn_gen_dsa_nonce_fixed_top, SHA-512 over priv || dgst || random; RFC 6979 only with nonce_type=1); wolfSSL, Crypto+++, libgcrypt, Botan (current head), Bouncy Castle’s stock ECDSA signer and python-ecdsa draw random nonces, with RFC 6979 as an opt-in; fastecdsa is deterministic by default; MIRACL Core has no RFC 6979 at all. None of these produces a biased nonce out of the box: the random paths use either rejection sampling or at least 64 extra bits before reduction. [S]

Compliance: bits2octets

RFC 6979 feeds bits2octets(hh) = int2octets(bits2int(hh) mod nn) to the DRBG. libsecp256k1 reduced the message only from version 0.2.0 (2022-12-12); the changelog reads “now reduces the message hash modulo the group order to match the specification”. Ports made earlier retain the raw hash: NBitcoin (msg32.CopyTo(keydata)), dcrd (copy(keyBuf[offset:], hash)) and btcec v2, which delegates to dcrd; through them LND, btcd and go-ethereum in its non-cgo build. go-ethereum’s cgo build uses a vendored libsecp256k1 that reduces, so the two builds of the same program produce different signatures when h≥nh \ge n. On secp256k1 with SHA-256 the discrepancy is observable only when h≥nh \ge n, probability 2−127.652^{-127.65}, and it has no security consequence: hh is public and A∗A^* is stated for any injective encoding of hh. It is a compatibility bug. [S][T]

elliptic and Bouncy Castle truncate to ⌈log⁡2n⌉\lceil\log_2 n\rceil bits before a single subtraction of nn; since the truncated value is below 2⌈log⁡2n⌉≤2n2^{\lceil\log_2 n\rceil} \le2n, one subtraction is exactly bits2octets for every hash length and every curve. The Ledger SDK’s open implementation (lib_cxng/src/cx_rng_rfc6979.c) has two 2−2562^{-256}-probability deviations: it leaves bits2int(hh) unreduced when it equals nn exactly, and it does not reject the candidate k=0k = 0. [S][T]

Retry and grinding

All implementations with an FxF_x advance the DRBG on rejection as in step H.3. Trezor and the Ledger SDK apply the K,VK,V update eagerly after every output, libsecp256k1 lazily at the start of the next generate; the output sequences coincide. [S]

Bitcoin Core (default since 0.17), libwally (EC_FLAG_GRIND_R, used by Core Lightning), rustsecp256k1 (sign_ecdsa_low_r, used by BDK), Jade and Coldcard grind for a low RR: they pass a counter cc as the §3.6 additional data (no data for the first attempt, then the 32-byte little-endian counter) and keep the first signature whose rr fits in 32 DER bytes. This selects k=Fx(h,c∗)k = F_x(h,c^*) with c∗=min⁡{c:π(Fx(h,c)G)}c^* = \min\{c : \pi(F_x(h,c)G)\} for the public predicate π(R)⇔x(R) mod n<2255\pi(R) \Leftrightarrow x(R) \bmod n < 2^{255}.

Theorem 8.1 (grinding). Let π\pi be any public predicate on points with ρ=Pr⁡k[π(kG)]>0\rho= \Pr_k[\pi(kG)] > 0. For every forger AA against grinding Det-ECDSA there are BB and DD with

Adv⁡Grind-DetEUF-CMA(A)≤Adv⁡RandEUF-CMA(B)+Adv⁡A∗(D),\operatorname{Adv}^{\mathrm{EUF\text{-}CMA}}_{\mathrm{Grind\text{-}Det}}(A) \le\operatorname{Adv}^{\mathrm{EUF\text{-}CMA}}_{\mathrm{Rand}}(B) + \operatorname{Adv}_{A^*}(D),

where A∗A^* is A∗A^* for Fx(h,c)F_x(h,c) on the extended input domain and BB makes qs/ρq_s/\rho signing queries in expectation. [T]

Proof. By Ac∗A^*_c the candidates k0,k1,…k_0,k_1,\ldots are independent and uniform, so the selected nonce is uniform on Sπ={k:π(kG)}S_\pi= \{k : \pi(kG)\}. BB simulates this signer with the Rand oracle: on query mm it requests signatures on mm until one satisfies π\pi, returns it, and discards the rest. The distribution is identical (first success in a sequence of independent uniform nonces). Every extra query of BB is on a message AA queried, so AA’s forgery is fresh for BB. The number of attempts is geometric with parameter ρ\rho; for low RR, ρ≈1/2\rho\approx1/2. The attempt count c∗c^*, observable through timing, adds nothing: BB reproduces its distribution. □

Ac∗A^*_c is the assumption already required by the rejection loop, which also selects a non-first output. Under it the selected nonce is uniform on the low-RR set, whose Fourier coefficients—the bias a Bleichenbacher-type attack would use—can be bounded without any model.

Proposition 8.2 (the low-RR set). Let L=2255L = 2^{255}, em(w)=exp⁡(2πiw/m)e_m(w) = \exp(2\pi i w/m), S={k∈Zn∗:x(kG)<L}S = \{k \in\mathbb{Z}_n^* : x(kG) < L\} and S′={k∈Zn∗:x(kG) mod n<L}S' = \{k \in\mathbb{Z}_n^* : x(kG) \bmod n < L\}, the set selected by grinding. On secp256k1, with its standard generator,

∣∣S∣n−1−12∣<2−118.9,max⁡t≠0∣1∣S∣∑k∈Sen(tk)∣<2−117.9,\left|\frac{|S|}{n-1} - \frac{1}{2}\right| < 2^{-118.9}, \qquad\max_{t\ne0}\left|\frac{1}{|S|}\sum_{k\in S} e_n(tk)\right| < 2^{-117.9},

and the same holds for S′S' with 2−117.92^{-117.9} and 2−116.92^{-116.9}. Both sets are symmetric under k↦−kk \mapsto-k, so all coefficients are real. [T][L]

Proof. Expand the indicator of [0,L)⊂Fp[0,L) \subset\mathbb{F}_p in additive characters, 1[0,L)(w)=∑jcjep(jw)\mathbf{1}_{[0,L)}(w) = \sum_j c_j e_p(jw). Then c0=L/pc_0 = L/p, and ∣cj∣≤1/(p∣sin⁡(πj/p)∣)≤1/(2∣j∣)|c_j| \le1/(p|\sin(\pi j/p)|) \le1/(2|j|) for 0<∣j∣≤(p−1)/20 < |j| \le(p-1)/2 gives ∑j≠0∣cj∣≤1+ln⁡((p−1)/2)\sum_{j \ne0}|c_j| \le1+\ln((p-1)/2). The group E(Fp)E(\mathbb{F}_p) is cyclic of prime order nn, so its characters are kG↦en(tk)kG \mapsto e_n(tk), and the function xx has degree 2 with a single pole, at infinity. The bound of Kohel and Shparlinski [22] for functions whose polar divisor is supported at one point gives, for every j≠0j \ne0 and every tt,

∣∑k=1n−1en(tk)ep(jx(kG))∣≤3p.\left|\sum_{k=1}^{n-1} e_n(tk)e_p(jx(kG))\right| \le3\sqrt{p}.

Put D=3p(1+ln⁡((p−1)/2))<2137.06D=3\sqrt{p}(1+\ln((p-1)/2))<2^{137.06}. The term j=0j=0 contributes (n−1)L/p(n-1)L/p for t=0t=0 and −L/p-L/p for t≠0t\ne0, so

∣∣S∣−(n−1)L/p∣≤D,∣∑k∈Sen(tk)+L/p∣≤D(t≠0).\left||S|-(n-1)L/p\right| \le D,\qquad\left|\sum_{k\in S}e_n(tk)+L/p\right| \le D\quad(t\ne0).

and L/p−1/2=2−225L/p-1/2=2^{-225}. For S′S' the set of abscissas is [0,L)∪[n,p)[0,L)\cup[n,p), since p−n<Lp-n<L: two intervals, hence the error 2D2D, around the density (L+p−n)/p=1/2+2−127.65(L+p-n)/p=1/2+2^{-127.65}. □

An attack driven by this bias would need more than 22332^{233} signatures. The bound is unconditional and holds for the actual curve and generator; it is within a factor of about 2112^{11} of the 2−1282^{-128} typical of a random subset of density 1/21/2, which is what the bijective random-oracle model of [12] would predict, and the difference is the logarithmic loss of the completion argument. On a toy prime-order curve with p=65167p=65167 the largest coefficient we measured is 2.2p2.2\sqrt{p} before normalization, against the bound 34p34\sqrt{p}. [T] The cost of grinding is an extra loop in the signer (a fault-injection surface) and twice the FxF_x evaluations.

Testability

The branch k∉[1,n−1]k\notin[1,n-1] is unreachable with natural inputs. libsecp256k1 tests it with nonce_function_test_retry (tests.c:6721–6744), which returns 0, 2256−12^{256}-1, 2256−22^{256}-2, nn and n+1n+1 before a valid candidate and checks that the result equals the untampered RFC 6979 output. The branch h≥nh\ge n is tested by no implementation we examined; Appendix B gives vectors that distinguish the conformant and raw-hash variants. Deterministic and hedged signatures are indistinguishable on chain, so the deployed share of each cannot be measured. [S]

Nonce bias in context

A single error-free leaked most-significant bit of kk on a 256-bit curve has not been attacked. Aranha et al. [23] broke a one-bit bias on a 160-bit curve with 2332^{33} signatures and estimated 2522^{52} signatures, 2582^{58} time, 2522^{52} memory for 256 bits by the scaling 2N/52^{N/5}. LadderLeak [24] broke one-bit leakage on P-192 with about 292^{9} signatures and left P-256 with one-bit leakage open; its P-256 estimate (≈5⋅105\approx5\cdot10^5 signatures) is for two-bit leakage. Lattice methods reach one-bit leakage on 160-bit curves [26] and two-bit leakage on 256-bit curves with 146 signatures [25].

Our model of the sort-and-difference/FFT attack (five reduction rounds, 24-bit FFT) gives 247.42^{47.4} signatures for one error-free bit on 256 bits. A toy calibration on curves q=2m−1q=2^m-1 for 32≤m≤8832\le m\le88 reproduces the model within 1.3 bits (mean absolute gap 0.3 bit), and calibration against the LadderLeak P-192 experiment gives 2402^{40}–2452^{45}. The honest envelope is 2402^{40}–2472^{47}; the figure 2522^{52} is the published scaling. [O] These are to be contrasted with 22552^{255} for the naive-reduction bias of § 7: the two regimes differ by 127 bits in ∣B1∣|B_1| and are not continuations of each other.

GLV decomposition in the signing path (noble-secp256k1 1.7.1, dcrd under the tinygo tag, k256 without precomputed-tables, elliptic’s fallback) decomposes a uniform kk into k=k1+λk2k = k_1+\lambda k_2 and leaves the distribution of kk unchanged; the dangerous pattern is recomposition from short random halves, which no reviewed implementation does, and which on secp256k1 (D=−3D=-3) yields a short-vector bias of 0.112 rather than the GLS value 2/π2/\pi (exact computation; Monte Carlo 0.113). The real GLV-specific risk is the decomposition side channel of [23], a lattice attack with tens of signatures. [S][T]

Conclusion and open problems

The security of RFC 6979 on secp256k1 is equivalent, up to the security of randomized ECDSA, to the assumption A∗A^* on HMAC_DRBG at known public key. A∗A^* does not follow from the PRF security of HMAC and the hardness of DLP, nor, given a collision-resistance premise, from the PRF and dual-PRF properties of the SHA-256 compression function. It is not implied by auxiliary-input PRF security either: in the standard model there are nonce functions with that property under which two signatures reveal the key—on chosen digests if any such function exists, on ordinary hashed messages under decisional square Diffie–Hellman, or under DDH with one public random point—or under which three signatures on fixed messages distinguish the transcript of a scheme that stays unforgeable. A∗A^* follows, with an ideal compression function, from DLP in the presence of a randomized-ECDSA signing oracle; for HMAC_DRBG itself it is violated by no known attack, and it is falsifiable. It is probably the most widely deployed unproven assumption in ECDSA practice. Separating the nonce key from the signing key, as RFC 6979 §3.6 and EdDSA do, makes it unnecessary, but is incompatible with existing keys and is used by none of the 31 implementations audited.

Open: a standard-model proof or refutation of A∗A^* for HMAC_DRBG; removing the collision-resistance premise from Theorem 4.8; a two-signature key-recovery separation through ordinary message hashing with the original parameters and xx as the only secret, from DLP or from the bare existence of an AI-PRF (Table 3 lists what each relaxation costs); closing the factor 2112^{11} between the proved and the heuristic Fourier bound for the low-RR set; and a measured, rather than modelled, cost for one-bit nonce leakage on a 256-bit curve.

Lemma 5.2: details

Write [z]n[z]_n for the residue of zz in {0,…,n−1}\{0,\ldots,n-1\}, nn an odd prime. Let tk=2−k mod nt_k=2^{-k}\bmod n, K=⌈log⁡2n⌉K=\lceil\log_2 n\rceil, m=⌈8log⁡2n/ε2⌉m=\lceil8\log_2 n/\varepsilon^2\rceil, M=⌈8/ε⌉M=\lceil8/\varepsilon\rceil. Fix random (u,v)∈Zn2(u,v)\in\mathbb{Z}_n^2 and query gg at ak,i=tk+iu+va_{k,i}=t_k+iu+v for k=0,…,Kk=0,\ldots,K, i=1,…,mi=1,\ldots,m. Then

ak,ix+c0≡tkx+iY+Z(modn),Y=[ux]n, Z=[vx+c0]n.a_{k,i}x+c_0\equiv t_kx+iY+Z\pmod n,\qquad Y=[ux]_n,\ Z=[vx+c_0]_n.

Enumerate βY=lsb⁡(Y)\beta_Y=\operatorname{lsb}(Y), βZ=lsb⁡(Z)\beta_Z=\operatorname{lsb}(Z), an approximation αY=U/(mM)\alpha_Y=U/(mM) with 0≤Y/n−αY<1/(mM)0\le Y/n-\alpha_Y<1/(mM), an approximation αZ=V/M\alpha_Z=V/M with 0≤Z/n−αZ<1/M0\le Z/n-\alpha_Z<1/M, and an initial approximation γ0=X0/M\gamma_0=X_0/M with 0≤[t0x]n/n−γ0<1/M0\le[t_0x]_n/n-\gamma_0<1/M; in total 4mM3=O(ε−5log⁡n)4mM^3=O(\varepsilon^{-5}\log n) branches, and the query set does not depend on xx.

In the correct branch maintain 0≤[tkx]n/n−γk<1/M0\le[t_kx]_n/n-\gamma_k<1/M. For Sk,i=([tkx]n+iY+Z)/nS_{k,i}=([t_kx]_n+iY+Z)/n and S^k,i=γk+iαY+αZ\widehat{S}_{k,i}=\gamma_k+i\alpha_Y+\alpha_Z one has S^k,i≤Sk,i<S^k,i+3/M\widehat{S}_{k,i}\le S_{k,i}<\widehat{S}_{k,i}+3/M, hence [Sk,i]=[S^k,i]=:wk,i[S_{k,i}]=[\widehat{S}_{k,i}]=:w_{k,i} whenever [ak,ix+c0]n≥3n/M[a_{k,i}x+c_0]_n\ge3n/M, and then, nn being odd,

lsb⁡([tkx]n)=g(ak,i)⊕(iβY mod 2)⊕βZ⊕(wk,i mod 2)\operatorname{lsb}([t_kx]_n)=g(a_{k,i})\oplus(i\beta_Y\bmod2)\oplus\beta_Z\oplus(w_{k,i}\bmod2)

whenever gg answers correctly. The event “g(a)g(a) correct and [ax+c0]n≥3n/M[ax+c_0]_n\ge3n/M” depends only on aa, has probability ≥12+ε−3/M≥12+ε/2\ge\frac{1}{2}+\varepsilon-3/M\ge\frac{1}{2}+\varepsilon/2, and the indicators over ii are pairwise independent. because ak,ia_{k,i} are pairwise independent and uniform (nn prime, m<nm < n). Chebyshev bounds the majority-vote error at step kk by 1/(mε2)≤1/(8log⁡2n)1/(m\varepsilon^2) \le1/(8\log^2 n); a union bound over K+1K + 1 steps gives success probability ≥3/4\ge3/4. With the bit bk=lsb⁡([tkx]n)b_k = \operatorname{lsb}([t_kx]_n) known, [tk+1x]n=([tkx]n+bkn)/2[t_{k+1}x]_n = ([t_kx]_n + b_kn)/2, so γk+1=(γk+bk)/2\gamma_{k+1} = (\gamma_k + b_k)/2 preserves the invariant and halves the error; after KK steps the error is below 1/n1/n and [tKx]n=⌈nγK⌉[t_Kx]_n = \lceil n\gamma_K\rceil (the ceiling, since the invariant is one-sided), whence x=2K[tKx]n mod nx = 2^K[t_Kx]_n \bmod n, verified against xG=QxG = Q.

Test vectors for the h≥nh \ge n branch

secp256k1, SHA-256, HMAC_DRBG as in RFC 6979 §3.2; the implementation used to produce these values reproduces the RFC’s own P-256/SHA-256 vector for the message “sample” (k=k = A6E3C57D . . . 8AAD60). “RFC” seeds the DRBG with int2octets(xx) ∥\parallel bits2octets(hh); “raw” seeds it with x∥hx \parallel h unreduced (libsecp256k1 before 0.2.0, NBitcoin, dcrd, btcec v2).

x=1x = 1, h=n+1h = n + 1 (h mod n=1h \bmod n = 1):

kRFC=k_{\mathrm{RFC}} = 9a409dab05968059da3efb323dc67c96f234571b965fd39810ca0643fbb795ac

kraw=k_{\mathrm{raw}} = daf2c4e18d51a5918522bc9ab5856ed4682208ed35315c9365b86e90dae8e3e3

x=1x = 1, h=2256−1h = 2^{256} - 1 (h mod n=th \bmod n = t):

kRFC=k_{\mathrm{RFC}} = 71139aac71b52f7d5961915af1b30f94baf35e39b0043c33d41a57d476a8905c

kraw=k_{\mathrm{raw}} = 1a3bf84f9a0fd1fff4655ba0ec976b542621fd87b88c3ca6770d4183cbc0e741

Expected behaviour: libsecp256k1 ≥0.2.0\ge0.2.0, secp256k1-zkp, elliptic, Bouncy Castle, Trezor, the Ledger SDK, OpenSSL, libgcrypt and fastecdsa return kRFCk_{\mathrm{RFC}}; NBitcoin, dcrd, btcec v2, LND and go-ethereum (non-cgo) return krawk_{\mathrm{raw}}. Signatures must verify in both cases, since the signature equation uses h mod nh \bmod n.

Declaration of Generative AI Use

During the preparation of this work, the authors used Claude Fable 5.2 and ChatGPT Astra to prove mathematical correctness, improve readability, check grammar, and refine phrasing. After using this tool, the authors manually reviewed and edited all text and take full responsibility for the content of the publication.

References

CurveDistanceConsequence
secp256k12−127.652^{-127.65}(A248′A^{\prime}_{248}) applies with loss 2−127.652^{-127.65}
P-2562−322^{-32}(A248′A^{\prime}_{248}) applies with loss 2−322^{-32}
brainpoolP256r1≈0.336\approx0.336extra assumption: (A248′A^{\prime}_{248}) for keys from a density-0.664 subset

Table 5. Distance of the secret tail x[0..30]x_{[0..30]} of block 1 from uniform. [T]

References

  1. [1]T. Pornin. Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA). RFC 6979, 2013. https://datatracker.ietf.org/doc/html/rfc6979DOI
  2. [2]S. Josefsson, I. Liusvaara. Edwards-Curve Digital Signature Algorithm (EdDSA). RFC 8032, 2017.DOI
  3. [3]P. Wuille, J. Nick, T. Ruffing. Schnorr Signatures for secp256k1. BIP-340. https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki
  4. [4]M. Naor. On Cryptographic Assumptions and Challenges. CRYPTO 2003.
  5. [5]M. Bellare. New Proofs for NMAC and HMAC: Security without Collision-Resistance. CRYPTO 2006; ePrint 2006/043.
  6. [6]M. Backendal, M. Bellare, F. Günther, M. Scarlata. When Messages are Keys: Is HMAC a dual-PRF? CRYPTO 2023; ePrint 2023/861.DOI
  7. [7]V. Shoup. Lower Bounds for Discrete Logarithms and Related Problems. EUROCRYPT 1997.DOI
  8. [9]P.-A. Fouque, D. Pointcheval, J. Stern, S. Zimmer. Hardness of Distinguishing the MSB or LSB of Secret Keys in Diffie–Hellman Schemes. ICALP 2006.DOI
  9. [10]C. Chevalier, P.-A. Fouque, D. Pointcheval, S. Zimmer. Optimal Randomness Extraction from a Diffie–Hellman Element. EUROCRYPT 2009, LNCS 5479, pp. 572–589.DOI
  10. [11]R. Impagliazzo, L. Levin, M. Luby. Pseudo-random Generation from One-way Functions. STOC 1989.
  11. [12]M. Fersch, E. Kiltz, B. Poettering. On the Provable Security of (EC)DSA Signatures. CCS 2016.DOI
  12. [15]W. Alexi, B. Chor, O. Goldreich, C.-P. Schnorr. RSA and Rabin Functions: Certain Parts are as Hard as the Whole. SIAM J. Comput. 17(2), 1988.
  13. [16]R. Fischlin, C.-P. Schnorr. Stronger Security Proofs for RSA and Rabin Bits. J. Cryptology 13, 2000.
  14. [17]J. Håstad, M. Näslund. The Security of all RSA and Discrete Log Bits. J. ACM 51(2), 2004.
  15. [18]D. Boneh, R. Venkatesan. Hardness of Computing the Most Significant Bits of Secret Keys in Diffie–Hellman and Related Schemes. CRYPTO 1996.
  16. [19]D. Boneh. The Decision Diffie–Hellman Problem. ANTS-III, LNCS 1423, pp. 48–63, 1998.
  17. [20]F. Bao, R. H. Deng, H. Zhu. Variations of Diffie–Hellman Problem. ICICS 2003, LNCS 2836, pp. 301–312.DOI
  18. [21]Y. Dodis, R. Ostrovsky, L. Reyzin, A. Smith. Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. SIAM J. Comput. 38(1), 2008.
  19. [22]D. R. Kohel, I. E. Shparlinski. On Exponential Sums and Group Generators for Elliptic Curves over Finite Fields. ANTS-IV, LNCS 1838, pp. 395–404, 2000.
  20. [23]D. F. Aranha, P.-A. Fouque, B. Gérard, J.-G. Kammerer, M. Tibouchi, J.-C. Zapalowicz. GLV/GLS Decomposition, Power Analysis, and Attacks on ECDSA Signatures with Single-Bit Nonce Bias. ASIACRYPT 2014, LNCS 8873, pp. 262–281.
  21. [24]D. F. Aranha, F. R. Novaes, A. Takahashi, M. Tibouchi, Y. Yarom. LadderLeak: Breaking ECDSA with Less than One Bit of Nonce Leakage. CCS 2020; ePrint 2020/615.
  22. [25]L. Xu, Z. Dai, B. Wu, D. Lin. Improved Attacks on (EC)DSA with Nonce Leakage by Lattice Sieving with Predicate. TCHES 2023(2).
  23. [26]J. Gao, Y. Wang, L. Hu, J. He. Lattice sieving with predicate for one-bit nonce leakage. ASIACRYPT 2024; ePrint 2024/296.
  24. [30]J. Brendel, C. Cremers, D. Jackson, M. Zhao. The Provable Security of Ed25519: Theory and Practice. IEEE S&P 2021.

Paper details

vlnc:W_cda5rpd5
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude Fable 5.2, ChatGPT Astra

View statement
Looking for related papers…
Contents