Why this talk?

Privacy-Enhancing
Signatures§ We just heard about ring signatures “for blockchain”.
§ 1-out-of-n proof (’94); Ring signature (’01)§ Linkable ring sig. (’04); Traceable ring sig. (’07)§ But we have bitcoin in 2008
§ Who knows what will happen next?
§ Let’s (re-)visit various different “flavors” of signatures!

Chinese University of Hong Kong

20th November 2018

22nd Workshop on
Elliptic Curve Cryptography

1

20th November 2018

22nd Workshop on
Elliptic Curve Cryptography2㻛㻡㻢Roadmap

I. Signatures with Verifiability Privacy§ This talk covers various privacy concerns of signatures inthese 30 years!

§ Alice is making a signed offer to Bob§ Bob can not use Alice’s offer as leverage to negotiate
better terms with, say, Carol§ Verifiability Privacy§ Undeniable Sig. (’89) à Non-Interactive Confirmer Sig. (’11)§ We want the (verifiability of the) signature to be “private”.

§ (Accountable) Signer Privacy§ Undeniable sig.: can only be verified with Alice’s help

§ Group Sig. (’91) à Group Sig. w/ Event-Dependent Opening (’19)§ Message Privacy§ Cannot deny if Alice did sign (only confirm or disavow)§ Sanitizable Sig. (’05) à Unlinkable Sanitizable Sig. (’16)§ The talk will also briefly discuss 2 core pairing-based
techniques, and if time permits, 2 pairing-based schemes.
20th November 2018

22nd Workshop on
Elliptic Curve Cryptography

3㻛㻡㻢

20th November 2018

22nd Workshop on
Elliptic Curve Cryptography4㻛㻡㻢Confirmer Signature

Designated-Verifier Proof/Signature§ What if the signer disappear?
§ Signer can appoint a confirmer in advance§ “It is either Alice or Bob’s signature”§ Just like a 2-user ring signature§ Confirmer can confirm(/deny) a signature§ Confirmer can also extract an ordinary signature out of it§ Bob knows that he didn’t sign but Carol does not know about that

§ But what if Alice later repudiate?

§ Undeniable/Confirmer signatures allow one to choose
whether to engage in the confirm/disavow protocol§ Require the confirmer to be online and answer requests§ But what if an attacker sit in the middle between Alice andBob and see everything? It will still be convinced
20th November 2018

22nd Workshop on
Elliptic Curve Cryptography5㻛㻡㻢§ “It is by Bob, not by me!” i.e., no non-repudiation§ Undeniable (’89) à Confirmer (’94) à Designated-ver. (’96)§ What else have been done in these two decades?

20th November 2018

22nd Workshop on
Elliptic Curve Cryptography

Online-Untransferable Signature

Just don’t do it online!

§ Bob can “transfer” the validity of the signature to
Carol by interacting with Alice and Carol concurrently§ New notion proposed by [C-Haralambiev @ CTRSA ’11]
§ Non-interactive confirmer signatures (NICS)§ “Confirmer” just converts an ordinary sig. to an NICS

§ All constructions of confirmer signatures provide only
offline untransferability [Liskov-Micali @ PKC ’08]

§ Like DVS, NICS can only convince the designated verifier§ “Confirmer” is like that in “universal” DVS, anyone can do the conversion§ Their construction uses “cut-and-choose” technique§ Prepare many “copies”, reveal some of them (no privacy)
and verify, hope the remaining unrevealed are well-formed.
§ But that is the source of inefficiency: For security parameterk, the signature of this scheme includes O(k) ciphertext
20th November 2018

22nd Workshop on
Elliptic Curve Cryptography

6㻛㻡㻢

7㻛㻡㻢

§ No online interaction, “online-”untransferability comes naturally§ But, again, what if the true signer repudiate?
§ It adds “extractability” on top of (U)DVS§ [Steinfeld-Bull-Wang-Piperzyk @ AsiaCrypt ’03]

§ This proposed construction is efficient (O(1))
20th November 2018

22nd Workshop on
Elliptic Curve Cryptography8㻛㻡㻢Traditional vs. Universal confirmer

Construction Idea

§ Traditional confirmer signature§ “σ is a valid signature signed by either Alice or Bob”

§ Signature is ambiguous (not binding to the signer)§ Confirmer convinces verifier about its validity§ Confirmation requires “secret” (not universal)§ Confirmer does not create this by directly “signing”§ But by converting an ordinary signature then proving:§ Secret key, or randomness used in signing

Source Privacy§ Non-interactive confirmer signature§ Signature is an ordinary one at the first place§ Need a step to make it ambiguous§ Yet still convincing to the verifier§ An ordinary one can be extracted by a (passive) “adjudicator”
20th November 2018

Encryptvk’=(vk0)a(vk1)b22nd Workshop on
Elliptic Curve Cryptography

9㻛㻡㻢

20th November 2018

Unforgeability

Encrypt
signature σ
into cExtraction Soundness
Prove that c isencrypting σ,
which is valid forvk’
and a + b = 1,
0 ≤ a, b ≤ 1

22nd Workshop on
Elliptic Curve Cryptography

10㻛㻡㻢

GS Proof [Groth-Sahai @ Eurocrypt ’08]

Some blockchain questions to ponder§ Fiat-Shamir heuristics for NIZK relies on the random oracle§ Can we do NIZK proof without random oracle?
§ Yes in general, but inefficient§ Before proving, you need to model the computation§ Everything including the signatures are put on theblockchain, perhaps “delayed” verifiability is useful?
§ Integrate NICS with smart-contracts, only pay (i.e.,
reveal the signature) when the contract is fulfilled?

§ e.g., hash function mapping to a group element, as a circuit§ Groth-Sahai proof makes an NIZK proof system§ for pairing product equations§ e.g., e(A, X)e(B, Y) = T§ where (A, B) is the witness to be proved about; X, Y, T are public

20th November 2018

22nd Workshop on
Elliptic Curve Cryptography11㻛㻡㻢

§ Just some random thoughts at this stage…
§ Shouldn’t we build crypto but not just thinking about
cryptocurrency?

20th November 2018

22nd Workshop on
Elliptic Curve Cryptography

12㻛㻡㻢II. Signer/Authenticator Privacy

Another application: Wikipedia§ An organization employs the cloud service§ Many members belong to this organization§ The cloud authenticates the users§ Everyone can write on different topics.
§ Writers/Reviewers may want privacy (or anonymity)Data§ e.g., multiple posts are unlinkable

Flow§ But the wikipedia administrator needs to ban“misbehaving” users

User
Cloud Servers§ posting advertisement, using abusive language, etc.

Data Flow
Data
Flow

User

§ In general, “Web 2.0” applications§ But the cloud is not an internal server!
§ It shouldn’t know “too much” about the users
20th November 2018

§ relies on users participation§ but also needs moderation

User

22nd Workshop on
Elliptic Curve Cryptography

13㻛㻡㻢

20th November 2018

22nd Workshop on
Elliptic Curve Cryptography

Dilemma

Balancing Privacy and Identification§ Online Privacy§ Traditional PKI-based certificate§ user expect actions online are unlinkable to real-world identity§ user will not be identified (and “punished”)

14㻛㻡㻢§ No anonymity at all§ Also, certificate may reveal privacy-related information§ Accountability§ A certificate contains many different fields for other purposes§ yet, perfect anonymity might be abused§ what if we identify some misbehavior?
§ “someone” should be the judge§ and has the power to find what other “damage” has been done

§ Just gives all users the same private key§ Unconditional anonymity may be abused§ If any one (or at least any users) know the same private key,can it still be treated as a form of “secret”?

§ Anonymity + Revocability

20th November 2018

22nd Workshop on
Elliptic Curve Cryptography

15㻛㻡㻢

20th November 2018

22nd Workshop on
Elliptic Curve Cryptography16㻛㻡㻢Signatures with Identity Privacy

Ring Signatures [Rivest-Shamir-Tauman ’01]

§ Signature is meant to be associated with a signer.
§ How can one hide the identity of the signer?!
§ An answer: hide it within a “group”§ The verifier only knows that 1 of the members in thegroup has issued the signature, but not exactly whom.
§ How the group is formed? Ring sig. vs. Group sig.
§ Another answer: Anonymous signature schemes§ How to Leak a Secret, in AsiaCrypt ’01§ 1-out-of-n Non-Interactive Zero-Knowledge (NIZK) proof§ Without the message, one needs to try all possible public key
to figure out who is the signer. [Yang-Wong-Deng-Wang ’06]
20th November 2018

22nd Workshop on
Elliptic Curve Cryptography17㻛㻡㻢§ e.g., for DLP, I know a secret key x s.t. y = gx is in {y1, y2, … yn}§ Spontaneity: A signer can conscript any group of n users§ This group may even not be aware that they have “joined”§ Anonymity: Verifier cannot determine who is the real signer§ Usually unconditional! (vs. computational anonymity)§ Sometimes “linkability” can be useful§ e.g., double-spending detection in electronic cash, or
cryptocurrency (Monero) // Fujisaki’s talk yesterday
20th November 2018

22nd Workshop on
Elliptic Curve Cryptography

Linkable Ring Sig. [Liu-Wei-Wong ’04]

“Verifiable” Authorship§ Signatures from the same signer can be linkable [ACISP’04]§ Suppose there is a group element h denoting the “event”§ Verifiable Ring Signatures --- authorship can be claimed/denied.
§ Any user can prove that s/he is the signer§ e.g., h = H(“event info/linkability context”, “ring” of n public keys)§ Put “linkability tag” hxi w/ ring sig via an “AND of OR proof”§ Anonymous under DDH assumption (becomes comp. anonymity)§ i.e., a proof that t = hx AND (x = x1 OR x = x2 OR … OR x = xn)§ Verifiable encryption of hxi§ e.g., recipient-free e-voting [C-Liu-Wong @ NDSS ’08]
22nd Workshop on
Elliptic Curve Cryptography§ [Lv-Wang @ DMS ’03]

§ Any user can prove that s/he did not sign
§ [Bultel-Lafourcade @ CANS ’17]

§ Accountable Ring Signatures --- signer identity can be revealed by a“trusted” opening authority§ [Xu-Yung @ CARDIS ’04]
§ [Bootle et al. @ ESORICS ’15]

§ “Escrowed” linkability [C-Susilo-Yuen @ VietCrypt ’06]

20th November 201818㻛㻡㻢

§ You’ll see them again in Group Signatures and Sanitizable Signatures.
19㻛㻡㻢

20th November 2018

22nd Workshop on
Elliptic Curve Cryptography

20㻛㻡㻢Group Signatures

Applications§ Group-oriented signatures with anonymity§ Direct anonymous attestation§ But with an explicit group formation (diff. from ring signature)§ A group manager (GM) issues credentials§ Any member can sign for the group§ remain anonymous within the group§ signatures are unlinkable§ but, unconditional anonymity may be abused§ Privacy-Preserving Identity-Management§ An opening authority can “open” a group signature toreveal its true signer
20th November 2018

22nd Workshop on
Elliptic Curve Cryptography§ [Brickell-Camenisch-Chen @ CCS ’04]
§ Authenticate an application’s executable code to a server§ Trusted Computing Group (TCG)§ Next Generation Secure Computing Base(NGSCB a.k.a. Palladium)21㻛㻡㻢

Vehicular Safety Communication§ [C-He-Hui-Yiu @ ACNS ’12]

20th November 2018

22nd Workshop on
Elliptic Curve Cryptography

22㻛㻡㻢

Basic Algorithms of Group Signatures

Accident ahead!
Let’s go toanother tunnel§ Setup§ key pairs for the group and the opening authority§ param = (gpk, opk), secret key = (gsk, osk)

§ Join§ interactive protocol between GM and user
§ user get the member key pair (pki, ski)§ the GM updates the membership archive DB with infoi§ Sign(ski, m) à σ, Verify(σ, m) à “True”/”False”§ Open(σ, osk, DB) à IDi // “revocable” anonymity
20th November 2018

22nd Workshop on
Elliptic Curve Cryptography

23㻛㻡㻢

20th November 2018

22nd Workshop on
Elliptic Curve Cryptography

24㻛㻡㻢

Design of Group Signatures

Signature as a Credential§ Credential issuing§ GM is the Signer§ Message: Attribute of a User, e.g., ID, user public-key§ The signature certifies “Membership of a Group”§ Using gsk to issue a “signature” s on (ID, pki)

§ Proving the knowledge of credential§ Proving about (s, ski)
§ User should have his/her own secret key for non-framability§ a.k.a. exculpability --- not guilty of wrongdoing§ Use the user (private) key to certify the actual message§ Delegating the signing power§ Identity is encrypted s.t. the public cannot see§ But decryptable by the opening authority

20th November 2018

22nd Workshop on
Elliptic Curve Cryptography§ 2-level (hierarchical) signature25㻛㻡㻢

20th November 2018

22nd Workshop on
Elliptic Curve Cryptography26㻛㻡㻢

Signatures with “Efficient Protocols”

BBS+ Signature [Au-Susilo-Mu-C’13]§ To issue a credential, the GM signs on two things§ Signature on a vector of messages§ Based on Boneh-Boyen-Shacham @ Crypto ’04]
§ System Parameter : (g, g0, g1, …, gn) for n-block message§ Signature Requester picks a random r’§ Compute C = g0^{r’}Πgi^{mi}§ Allow more efficient zero-knowledge proof if the components of amessage vector are treated “separately”§ User secret key should be hidden in a commitment§ Signature on the commitment§ Commitment of n-block messages§ Compute PoK{(r’, m1, …i, mn): C = g0^{r’}Πgi^{mi}}§ Allow signing on the message committed in the commit§ Allows proving the knowledge of such a message-signature pair

§ Both notions can be combined:§ i.e., signing on a vector of messages, some of them can bepresented in the form of a commitment
20th November 2018

22nd Workshop on
Elliptic Curve Cryptography27㻛㻡㻢

§ Signer picks r’’ and e, define r* = r’ + r’’§ Return A = (g ‫ ڄ‬g0^{r’’} ‫ ڄ‬C)^{1/(β + e)}§ Signature = (A = (g ‫ ڄ‬g0^{r*} Πgi^{mi})^{1/(β + e)}, e, r*)
20th November 2018

22nd Workshop on
Elliptic Curve Cryptography28㻛㻡㻢

Identity-Escrow

World of Group Signatures§ Proof of Knowledge (PoK) of a signature“Traceable Signatures”[Kiayias-Tsiounis-Yung04]§ without showing the GM’s signature§ the group member proves that the member private key
signed by the GM is used to sign the final message

Efficient Tracing+ Authorship
Claiming§ Proof for the correctness of encrypting identification

Group
Signatures(opening)§ user’s public key / credential

20th November 2018

22nd Workshop on
Elliptic Curve Cryptography“Real Traceable Signatures”[C09]“Double-Trapdoor Anonymous Tag”
[Abe-C-Haralambiev-Ohkubo’11/’13]29㻛㻡㻢

20th November 2018+
Anonymous
Tracing+ Authorship
Deniability

Verifier-Local
Revocation(Group)Signatures(tracing)

22nd Workshop on
Elliptic Curve Cryptography

30㻛㻡㻢

Subtle Issue of Opening“Catch-22” Issue of Opening§ Separation was not nicely done in many schemes.
§ Key issuing updates a membership database.

§ Identified by Kiayias-Zhou at FC ’07§ So, how exactly opening can be done?
§ 0) The membership database is public: Not an option.
§ 1) GM gives the membership database to OA.

§ Opening just reveals info in this database§ e.g., a user public key§ OA is too powerful. Member cannot “sign in peace”.

§ But not the user identity§ Need to link them back§ 2) GM keeps such a membership database to itself.

20th November 2018

22nd Workshop on
Elliptic Curve Cryptography§ OA talks to GM every time, GM should remains online§ GM may even refuse to help. No separation of power.
§ This DB attracts attacker: All members are potential signers.
31㻛㻡㻢

20th November 2018

22nd Workshop on
Elliptic Curve Cryptography

32㻛㻡㻢

Hidden Identity-Based Signatures (HIBS)

HIBS as a Refinement of Group Sig.

§ Group signature: “No-win” no matters what you do.
§ The crux of the problem: member list should not exist!
§ Identity-based signatures (IBS) [Shamir @ Crypto ’84]

§ User identity is only hidden in the signature§ There is no membership list whatsoever§ Join§ Private key generator (PKG) create a master key pair: (mpk, msk)
§ PKG generates user secret key (skID) for an user with given its ID§ Anyone can verify a signature given (mpk, ID) and the message§ Hidden identity-based signatures [Kiayias-Zhou @ FC ’07]

22nd Workshop on
Elliptic Curve Cryptography§ Opening just takes in OA’s secret key and output signer ID§ Open(osk, σ) à ID

§ Supporting above features should not penalize theperformance of other algorithms§ Anyone can verify a signature given mpk and the message§ An OA can open the signature and reveals the signer’s ID

20th November 2018

§ interactive protocol between GM and user
§ user get the member key pair (pki, ski)§ the GM updates the membership archive DB with infoi§ Time and space costs for opening are independent of #members§ “Real HIBS” based on GS-proof [C-Zhang-Zhang @ FC 䇻17]33㻛㻡㻢20th November 2018

22nd Workshop on
Elliptic Curve Cryptography34㻛㻡㻢

Two Existing HIBS Schemes

Is membership list an old (’07) issue?

§ 1. A pairing-based scheme [KZ’07] with Open() returns gID§ Requiring solving discrete logarithm (or a small ID space)§ or maintaining a mapping between ID and gID§ Other scheme which opens to gID also exists§ Membership DB “affects” recent study of group signatures.

§ e.g. [Boyen-Waters @ PKC ’07]

§ 2. A scheme based on Paillier encryption [IET-Info Sec ’09]
§ Rely on the Decisional Composite Residuosity assumption§ Working with an RSA modulus is not that efficient§ Larger group elements, more involved zero-knowledge proof
20th November 2018

22nd Workshop on
Elliptic Curve Cryptography35㻛㻡㻢

§ Get Shorty via Group Signatures without Encryption[Bichsel et al. @ SCN ’10]
§ Opening/“Decryption” by referring to DB à linear in |DB|§ (Dynamic Group Signature from) Short Accountable Ring
Signatures based on DDH [Bootle et al. @ ESORICS ’15]
§ The group public key is simply a list of all user public keys!
20th November 2018

22nd Workshop on
Elliptic Curve Cryptography36㻛㻡㻢Traceable (Group) Signatures

Real Traceable Signature§ Opening is too powerful§ When an abusive user is identified§ Trace all signatures from this user
§ Traceable Sig. [KTY @ Eurocrypt ’04]

§ Assign a seed to every member§ Signature on a block of messages§ User identity, user public/private key, the seed

§ Tag is PRFseed(ctr)§ PRF is a pseudorandom function§ ctr is a counter maintained by the user
§ deterministic given seed and ctr§ Check each candidate signature§ Real Traceable Sig. [C @ SAC ’09]
§ “Pointing to” signatures

20th November 2018

22nd Workshop on
Elliptic Curve Cryptography§ Range proof ensures ctr < N (a system parameter)

37㻛㻡㻢

Modular Approach: The Missing Piece

20th November 2018

22nd Workshop on
Elliptic Curve Cryptography38㻛㻡㻢

A Modular Traceable Sig. Construction[AFGHO10] Signatures[BB04] One-Time Signatures“Traceable Signature” = “Signature” + “Revocation Mechanism”

Groth-Sahai
Proof System

Anonymous
Tag System[ACHO @ ACNS ’11
or @ IJIS ’13]

“Traceable Signature” = “Signature” + “Revocation Mechanism”- Guarantees integrity of messages.
- Authenticate the signer.

- Opening, Tracing- Claiming, Denial

Glued by NIZK that guarantees
correct computation while hiding
privacy related objects in each part.
20th November 2018

22nd Workshop on
Elliptic Curve Cryptography

39㻛㻡㻢

20th November 2018

22nd Workshop on
Elliptic Curve Cryptography

40㻛㻡㻢Structure-Preserving Signatures

Double-Trapdoor Anonymous Tag§ Structure-preserving§ A tag is produced by a user-secret w.r.t user public key.
§ All tags of a given user are anonymous and unlinkable.
§ The master-secret key can create a user-specific token.
§ Token links all tags, but remain anonymous w.r.t. upk.

§ [Abe-Fuchsbauer-Groth-Haralambiev-Ohkubo @ Crypto ’10]:§ Message M to be signed is a base group element§ The signature is also formed by base group elements (not GT)§ GS proof cannot prove things about GT elements§ Yet, signature like Mβ is insecure (cf., textbook RSA)
§ Needs at least 2 equations to verify§ With the user-secret, the user can claim the authorship.
§ (And also deny the authorship of any other’s tags.)§ The claim will be associated to the user public key.

§ (a proven minimum)

22nd Workshop on
Elliptic Curve Cryptography

20th November 201841㻛㻡㻢Anonymous Tag (Construction)42㻛㻡㻢

Double-Trapdoor Structure

Decision Linear Assumption (DLIN)
Given (g1, g2, g3, g1a, g2b, g3c),
decide c = a + b or not.

Tracing

=

mtsk

=

=

=

mtsk

22nd Workshop on
Elliptic Curve Cryptography

20th November 2018

Decision Reciprocity Assumption (DRA)
Given (h1, h2, h3, h1u, h2v, h3c),
decide c = u/v or not.

utsk

utsk

tag

tag
token

DLIN

Authorship claiming and denying:
The token will be hidden by NIZK.

DRA
20th November 2018

22nd Workshop on
Elliptic Curve Cryptography

43㻛㻡㻢

20th November 2018

22nd Workshop on
Elliptic Curve Cryptography

44㻛㻡㻢Restrict the Power of Opening

Restrict the Power of Opening, for real

§ Opening is too powerful§ When an abusive user is identified§ Trace all signatures from this user

§ Message-Dependent Opening (MDO) --- opening asignature on m needs an additional trapdoor for m§ The first construction is proposed by [Sakai, Emura,Hanaoka, Kawai, Matsuda, Omote @ Pairing ’12]
§ Relied on k-resilient identity-based encryption (IBE)§ This is “Tracing”, NOT “Opening”!

§ [Libert and Joye @ CTRSA ’14] achieved MDO by
proposing partially structure-preserving IBE.
§ The message to encrypt is in G, but not the identity§ The original opening key is still needed for opening.
20th November 2018

22nd Workshop on
Elliptic Curve Cryptography45㻛㻡㻢

20th November 2018

22nd Workshop on
Elliptic Curve Cryptography

46㻛㻡㻢

Group Sig. w/ Event-Dependent Opening

III. Message Privacy§ Event-dependent opening (EDO) decouples the
opening criteria from the signed message.

§ For outsourcing database, say, for further processing,
not all data should be revealed.

§ e.g., the event is for e-voting§ cf. “linkability context” in linkable ring signature§ Event-dependent trapdoor is derived by opening key.
§ Opening key is no longer an input for the opening algorithm.

§ [Zhang-Wu-C@CTRSA’19] proposed structure-preserving
certificateless encryption and group signature w/ EDO.

20th November 2018

22nd Workshop on
Elliptic Curve Cryptography47㻛㻡㻢

§ E.g. 1: Personal identification information for a medical
record should be sanitized.
§ E.g. 2: Secure routing [Ateniese et al. @ ESORICS ’15]

§ It is desirable to sanitize sensitive signed information
without asking the original signer to sign again,
before releasing the information to public.
§ *Computation over data signed by multiple signers,see [Lai-Tai-Wong-C @ AsiaCrypt ’18]
20th November 2018

22nd Workshop on
Elliptic Curve Cryptography

48㻛㻡㻢

Sanitizable Signatures

Accountability vs. Privacy§ Proposed by [Ateniese et al. @ ESORICS ’15]
§ Signer signs the fixed part and modification allowed§ Support “controlled malleability”§ A designated sanitizer can sanitize a signature§ Accountability is easy to achieve without privacy.
§ Transparency: Sanitized and fresh signatures should beindistinguishable.

§ without the help of the original owner§ Signer Accountability: Signer cannot accuse sanitizer.
§ Sanitizer Accountability: Sanitizer can’t accuse signer.

20th November 2018

22nd Workshop on
Elliptic Curve Cryptography49㻛㻡㻢

§ Unlinkability: Sanitized signature from different sources
should be indistinguishable[Brzuska et al. @ PKC ’10]
§ Sig(m’) àσ’ ≈ σ ß San(m, σ, Mod)
§ where m’ = Mod(m)§ 2 modular approaches (with new building blocks) areproposed by [Lai-Zhang-C-Schröder @ ESORICS ’16]
20th November 2018

22nd Workshop on
Elliptic Curve Cryptography

50㻛㻡㻢

Sanitizable Sig. from Rerandomizable Tag

Sanitizable Sig. from Accountable Ring Sig.

§ A new building block proposed by [LZCS@ESORICS ’16]
§ Issuer generates a tag using its secret key§ The first construction is transparent but not unlinkable.
§ The signer ring-signs with the ring = {signer, sanitizer}.
§ The signer signs the fixed part with a regular signature.
§ To sanitize, ring-signs with a new message.

§ w.r.t. a user public key.

§ Issuer can claim the authorship of the tag.
§ User can use its own secret key to rerandomize the tag.
§ Randomized tags are indistinguishable from issuer’s one.
§ Issuer can then deny the authorship of the tag.

§ Accountability features reveals the true signer.
§ In [LZCS @ ESORICS ’16], signer is opening authority.
§ In [Bultel-Lafourcade @ CANS ’17], the sanitizer can
prove that s/he didn’t sanitize.

§ The original embedded randomness is “spoiled”.

§ It’s a dual notion of double-trapdoor anonymous tag.
§ We only know how to construct it with lattice.
20th November 2018

22nd Workshop on
Elliptic Curve Cryptography

51㻛㻡㻢

20th November 2018

22nd Workshop on
Elliptic Curve Cryptography52㻛㻡㻢References (1/2)

References (2/2)§ Sherman S. M. Chow, Willy Susilo, Tsz Hon Yuen: Escrowed
Linkability of Ring Signatures and Its Applications.
VIETCRYPT 2006: 175-192§ Sherman S. M. Chow, Joseph K. Liu, Duncan S. Wong:
Robust Receipt-Free Election System with Ballot Secrecy
and Verifiability. NDSS 2008
§ Sherman S. M. Chow: Real Traceable Signatures. Selected
Areas in Cryptography 2009: 92-107§ Sherman S. M. Chow, Kristiyan Haralambiev: Noninteractive Confirmer Signatures. CT-RSA 2011: 49-64§ Sherman S. M. Chow, Yi Jun He, Lucas Chi Kwong Hui, SiuMing Yiu: SPICE - Simple Privacy-Preserving IdentityManagement for Cloud Environment. ACNS 2012: 526-543§ Masayuki Abe, Sherman S. M. Chow, Kristiyan Haralambiev, Miyako
Ohkubo: Double-trapdoor anonymous tags for traceable signatures.
Int. J. Inf. Sec. 12(1): 19-31 (2013)§ Man Ho Au, Willy Susilo, Yi Mu, Sherman S. M. Chow: Constant-Size
Dynamic $k$-Times Anonymous Authentication. IEEE Systems Journal
7(2): 249-261 (2013)§ Russell W. F. Lai, Tao Zhang, Sherman S. M. Chow, Dominique
Schröder: Efficient Sanitizable Signatures Without Random Oracles.
ESORICS (1) 2016: 363-380§ Sherman S. M. Chow, Haibin Zhang, Tao Zhang: Real Hidden IdentityBased Signatures. Financial Cryptography 2017: 21-38§ Russell W. F. Lai, Raymond K. H. Tai, Harry W. H. Wong, Sherman S. M.
Chow: Multi-Key Homomorphic Signatures Unforgeable under Insider
Corruption. ASIACRYPT 2018. To appear.
§ Tao Zhang, Huangting Wu, Sherman S. M. Chow: Structure-Preserving
Certificateless Encryption. CT-RSA 2019. To appear.

20th November 2018

22nd Workshop on
Elliptic Curve Cryptography53㻛㻡㻢

20th November 2018

22nd Workshop on
Elliptic Curve Cryptography

Summary

Q&A: sherman@ie.cuhk.edu.hk§ We quickly went through part of the 30-years history ofsignatures with privacy concerns.
§ We briefly discussed 2 core pairing-based techniques:
Groth-Sahai proof and Structure-Preserving Signature.
§ We briefly discussed 2 pairing-based constructions:
BBS+ signatures and double-trapdoor anonymous tag.

§ Verifiability Privacy

54㻛㻡㻢

§ Undeniable Signatures§ (Universal) Designated Verifier Signatures§ (Non-Interactive) Confirmer Signatures§ (Accountable) Signer Privacy§ Ring Signatures (with (Escrowed) Linkability)§ Verifiable Ring Signatures§ Accountable Ring Signatures§ Hidden ID-Based Signatures (or No-Member-List Group Signatures)§ (Real) Traceable (Group) Signatures (with Denial Proof)§ Message Privacy§ Unlinkable and (Strongly) Accountable Sanitizable Signatures
20th November 2018

22nd Workshop on
Elliptic Curve Cryptography

55㻛㻡㻢

20th November 2018

22nd Workshop on
Elliptic Curve Cryptography

56㻛㻡㻢