Alice has a master private key scalar $a$, with corresponding public key $A=aG$. $G$ is a well-known base point on the curve.
Alice deterministically creates a new identity associated with a particular message $m$. She calculates the private key $b = HKDF_s(a, m)$, where $\operatorname{HKDF_s}$ means to use HKDF to derive a scalar result. Alice calculates the corresponding public key $B=bG$.
Alice encrypts her master private key with a uniformly random scalar $k$, as $a'=a+k$. She calculates $K=kG$.
Alice discloses $A$, $B$, $K$ and $a'$ to the Oracle. The Oracle verifies that $a'G\overset{?}{=} A+K$.
The Oracle signs the tuple ($B$, $K$, $a'$, $m$, timestamp) and stores that signed tuple as part of the public record. The Oracle does not disclose $A$ publicly. This signed tuple asserts that the Oracle allows the public key $B$ to be associated with $m$.
From now on, when signing messages associated with this tuple, Alice must sign twice - once with $B$ and once with $K$.
This proves that Alice knows both $b$ and $k$.
Alice cannot disclose $b$ and $k$ to Sam, because Sam would be able to recover $a$ as $a = a'-k$.
Note: scalar addition and subtraction are modulo the order of group generated by the base point.
