Kyosuke Yamashita（Osaka Univ./AIST）

Keisuke Hara（AIST/Yokohama National Univ.）

�Supported by

JSPS JP23H00468

On the Black-Box Impossibility of

Multi-Designated Verifiers Signature Schemes from Ring Signature Schemes

Summary

• Two-decades prolonged folklore: �Ring Signature (RS) ⇒ Multi-Designated Verifiers Signature (MDVS) [1]
• This work denies the folklore in a black-box sense.
• no reduction from unforgeability (UNF) of MDVS to UNF of RS
• In [1], no formal discussion was given.
• formalization of MDVS– 2012 [2], 2020 [3], 2023 [4]

1

[1] Fabien Laguillaumie and Damien Vergnaud. “Multi-designated verifiers signatures”. ICICS2004.

[2] Zhang, Y., Au, M.H., Yang, G., Susilo, W. “(strong) multi-designated verifiers signatures secure against rogue key attack”. NSS2012.

[3] Damgård, I., Haagh, H., Mercer, R., Nitulescu, A., Orlandi, C., Yakoubov, S. “Stronger security and constructions of multi-designated verifier signatures”. TCC2020.

[4] S. Chakraborty, D. Hofheinz, U. Maurer, and G. Rito. Deniable authentication when signing keys leak. EUROCRYPT 2023

Black-Box (Im)possibility

Black-Box (BB) Construction

• Construct a primitive A from anothe primitive B (B ⇒ A) �without relying on algebraic structure.

Ex) OWF ⇒ Signature

​

​

​

​

• A = B if A⇒B and B⇒A

​

2

OWF

Signature

RSA

DH

Black-Box (Im)possibility

BB Impossibility

• Deny a black-box construction of a primitive A from a primitive B (B ⇒ A)

​

Ex) OWP ⇒ Key Agreement

​

​

​

​

​

• Clarifies relationship between primitives
• B is strictly weaker than A if B⇒A and A⇒B

​

​

3

OWP

KA

What is good for Showing BB Impossiblity?

It opens new research direction.

• A ⇒ B

​

​

​

• Adding a new feature？

​

​

• Combine with other primitive？

​

​

⇒ Investigation for essential features of primitives

4

A

B

A’

A+C

?

?

MDVS

5

signer

DVs

other

verifier

cannot trust

the signature

Applications of MDVS

• Messaging Apps

6

can distinguish whose signature

(if he didn’t join the simulation,

then it’s the signer’s)

cannt identify whose message

due to OTR

group chat

RS

7

Anonymity of RS

• Anonymity

ring

verifier

some member’s signature

• can identify a member’s sig
• cannot identify who signed

• the signer’s pk ∈ {pk_i}_i
• write R = {pk_i}_i and call it a ring

Folklore: RS → MDVS

8

a member’s

signature

ring

RS

MDVS

• cannot identify whose signature

• anonymity ⇒ OTR!!!!!!

[1] Fabien Laguillaumie and Damien Vergnaud. “Multi-designated verifiers signatures”. ICICS2004.

The idea of [1]: regard a ring as a set of a signer and DVs

Main Theorem

9

No formal discussion in [1]

​

“The unforgeability of MDVS is guaranteed by the unforgeability

of the underlying RS. The source hiding property (OTR) comes naturally from the source hiding (anonymity) of the ring signature.”

​

Main Theorem

There is no black-box construction of an MDVS based on an RS,

whose unforgeability is reduced to unforgeability of the RS.

There is a “gap” in the definitions of UNF.

❗️Caveat ❗️

• We provide intuition of the definition of UNF and our proof.
• less precise
• For precise information, please read the article.
• Journal of Mathematical Cryptology
• https://eprint.iacr.org/2023/1249

​

10

The “gap”

MDVS: Some (but not all) DVs can be corrupted in the experiment

11

RS: Ring members cannot be corrupted

UNF of MDVS

12

MDVS Ch

MDVS Adv

(ssk, spk) ← SKG

∀ i ∈ [n], (vsk_i, vpk_i) ← VKG

choose D* ⊆ {vpk_i}_i∈[n]

spk, {vpk_i}_i∈[n], D*

vpk_j

vsk_j

corruption query

(D* can be corrupted)

UNF Experiment (simplified)

(m*, σ*)

Adv wins if ∃ vpk_k ∈ D* s.t.

Vrf(D*, vsk_k, spk, m*, σ*) = 1

∧ vpk_k is not corrupted

UNF of RS

13

RS Ch

RS Adv

∀ i ∈ [n], (sk_i, pk_i) ← KG

choose R* ⊆ {pk_i}_i∈[n]

{pk_i}_i∈[n], R*

UNF Experiment (simplified)

(m*, σ*)

σ*: signature w.r.t R*

Adv wins if

Vrf(R*, m*, σ*) = 1

∧ R* is not corrupted

pk_j

sk_j

corruption query

(R* cannot be corrupted)

Reduction

• Assume ∃ a BB construction of MDVS from RS.

14

attacker against MDVS

attacker against RS

• In the experiment...

RS Ch

RS

Adv

MDVS

Adv

simulates

MDVS experiment

Proof Overview

1. Assumption (for contradiction)
• ∃ such a BB consrcution
2. By assumption
• if ∃ a PPT adversary A that breaks EUF of MDVS, �then ∃ another PPT adversary B s.t. B^A breaks EUF of RS (∃ Recuction)
3. We can construct a PPT B’ that breaks EUF of RS without A

⇒ contradicts to the security of π_RS

​

15

Main Theorem

There is no black-box construction of an MDVS based on an RS,

whose unforgeability is reduced to unforgeability of the RS.

Reduction Overview

16

The idea of [1]: regard a ring as a set of a signer and DVs

⇒ R* = D*

RS Ch

B

A

forged signature

R*

forged signature

corruption query

corruption query

answer

answer

D*

A corruption query for D*?

17

RS Ch

A

forged signature

R*

forged signature

corrupt D*

corrupt R*?

?

answer

D*

B

R* cannot be corrupted

correct answer

is returned

(by assumption)

🤔

B is powerful

18

RS Ch

A

forged signature

R*

forged signature

corrupt D*

corrupt R*?

?

answer

D*

B computes a secret key by itself

B

💪

B computes it

by itself!

Construct Another PPT B’

19

RS Ch

R*

(m*, σ*)

B’

• compute a sk
• create σ* on (m*, R*)

forgery succeed!

• Wrong assumption:
• if ∃ a PPT attacker A that breaks EUF of π_MDVS, �then ∃ another PPT attacker B s.t. B^A breaks EUF of π_RS (∃ Recuction)

​

⇒ There is no such BB construction. (QED)

⇒ contradiction!

💪

Side Note of the Proof

20

Conclusion and Future Work

Concludion

• We have denied the two-decades prolonged folklore
• The construction of an MDVS from RS is not trivial
• It has been overlooked due to lack of formal discussion

​

Future Work

• How about less weak MDVS?
• MDVS that D* cannot be corrupted in the EUF experiment.
• How about more strong model?
• random oracle model
• stronger RS

21