In Lu, Au and Zhang's 2019 paper (Linkable) Ring Signature from Hash-Then-One-Way Signature, they

…extend [M. Abe, M. Ohkubo, and K. Suzuki's 2019 1-out-of-n signatures from a variety of keys] framework to its linkable variant. Borrowing the idea from [our previous lattice-based linkable ring signature scheme, Raptor], we adopt [some] one-time signature scheme ($\Pi^{OTS}$). We build a generic method of constructing linkable ring signature based on $\Pi^{OTS}$ and $\text{Type-H}$ signature with uniform distributed public key. During the key generation procedure, in addition to the public key and secret key pair $(\text{pk},\text{sk})$, each signer also generates a pair of public key and secret key $(\text{opk},\text{osk})$ of a one-time signature. The signer then computes $\text{PK}=\text{pk}\oplus\text{H}(\text{opk})$ for some appropriate hash function $\text{H}(\cdot)$. The new public key is $\text{PK}$ and the secret key is $\text{SK}=(\text{sk},\text{opk},\text{osk})$.

I take it (perhaps incorrectly in this case) that this symbol, $\oplus$, in that second-to-last equation represents exclusive-or, but how is that implemented here?

They explicitly list RSA as a supported $\text{Type-H}$ signature scheme to underly this linkable ring signature scheme, but this leaves two large questions:

  1. how does one use an RSA public key $\text{pk}$, which is an ordered sequence of two integers, one of which is at least 1024 bits, as an argument to XOR with the output of a hash function such as SHA256, which is merely 256 bits?

  2. How would you interpret the (identically random) result of an XOR with a cryptographic hash digest back into such a particularly constrained sequence of integers as RSA public key $\text{PK}$? (i.e. the first one must be the product of exactly two primes; the second should be less than around 1024 bits) -- and then how would you ensure that $\text{SK}$ comprised its factors?

^ This seems so impossible and ridiculous (despite the authors of this paper listing RSA explicitly as a supported algorithm, and SHA256 being practically "the" standard cryptographic hash) that I am sure I'm misinterpreting something — probably the $\oplus$ symbol, though I cannot fathom what it might mean instead — so, what is represented in that line? Am I misinterpreting what $\text{PK}$ represents?

For instance, how would I, "mechanically", (in, say, pycryptodome) enact or implement this line, if we take SHA256 as $\text{H}$, RSA as the $\text{Type-H}$ signature scheme, and (say) Lamport signatures as $\Pi^{OTS}$?

  • $\begingroup$ Can you consider XOF? eXtendible-Output-Functions like SHAkE128 and SHAKE256 that can output desired digest size. $\endgroup$
    – kelalaka
    May 3, 2021 at 20:53
  • $\begingroup$ @kelalaka Setting the hash output size to that of the public key only partially covers (1) — how is this sequence of two integers then to be serialized for XORing? — and it leaves (2) unanswered. (I'm, frankly, not even sure if those 2 questions are what I should be asking, though.) $\endgroup$ May 3, 2021 at 21:09
  • $\begingroup$ public key $pk$ is doesn't include $p$ and $q$. RSA public key is just $(n,e)$, nothing more. $\endgroup$
    – kelalaka
    May 3, 2021 at 21:14
  • $\begingroup$ @kelalaka Yes, an RSA public key is a sequence of two integers $(n,e)$. This does not address the question of what serialization mapping $(n\in\mathbb{Z}|n=p_\text{prime}q_\text{prime},\mathbb{Z})_\to\{0,1\}^*$ should be done on $pk$ to prepare it for the $\oplus$ operation (can an arbitrary mapping be chosen? anything injective? something particular? I'm trying to figure out what the authors meant by this line), as well as how to deserialize the result into a valid $PK$ afterwards. $\endgroup$ May 3, 2021 at 21:30
  • $\begingroup$ (That is, assuming that that operation even represents XOR, and serializing/deserializing a sequence of integers is appropriate or necessary in this case.) $\endgroup$ May 3, 2021 at 21:54

1 Answer 1


Reading section III A of the paper (caveat, I've not read the whole paper), it looks like the construction has been generalised so that $H$ maps to the abelian group where the public key operations take place. As such the $\oplus$ operation generalises to the abelian group operation. This notation is unwelcome, but I think in previous work the abelian group in question did combine with XOR.

In the RSA case it would appear that the operation is multiplication modulo $N$ and the hash function maps to $\mathbb Z/N\mathbb Z$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.