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 a 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 $(pk,sk)$, each signer also generates a pair of public key and secret key $(opk,osk)$ of a one-time signature. The signer then computes $PK=pk \oplus H(opk)$ for some appropriate hash function $H(\cdot)$. The new public key is $PK$ and the secret key is $SK= (sk,opk,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 $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 SHA-256, 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 $PK$? (i.e. the first one must be the product of exactly two primes; the second should be 65537 or one of a few other whitelisted values)

$PK_{RSA}=pk_{RSA}\oplus H_\text{SHA-256}(\_)$
^ This seems so impossible and ridiculous (despite the authors of this paper listing RSA explicitly as a supported algorithm, and SHA-256 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?

For instance, how would I, "mechanically", (in, say, pycryptodome) enact this line, if we take SHA-256 as $H$ and RSA as the $\text{Type-H}$ signature scheme?

  • $\begingroup$ Can you consider XOF? eXtendible-Output-Functions like SHAkE128 and SHAKE256 that can output desired digest size. $\endgroup$ – kelalaka May 3 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$ – JamesTheAwesomeDude May 3 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 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$ – JamesTheAwesomeDude May 3 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$ – JamesTheAwesomeDude May 3 at 21:54

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$.

  • 1
    $\begingroup$ That's a great insight! To be clear, in “multiplication modulo $N$”, $N$ refers to the public modulus $n$ (aka $pq$)? [Related answer] $\endgroup$ – JamesTheAwesomeDude May 4 at 18:45
  • $\begingroup$ Also — something I've realized during my own reading of the paper — it appears that $PK$ is actually a public key in $\Pi^{OTS}$, which is a one-time signature scheme (conventionally Lamport, it seems); it looks like this scheme has no constraints — in fact it expects random data for the keys — “Alice uses the random number generator to produce 256 pairs of [256-bit] random numbers…This is her private key and she will store it away in a secure place for later use.” -so perhaps an arbitrary serialization is what's intended $\endgroup$ – JamesTheAwesomeDude May 4 at 18:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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