### Fuzzy Identity Based Signature

```Based on P Yang et al 2008
Kittipat Virochsiri
Introduction

• What is it?
• Applications
What is it?

 An Identity Based Signature scheme
 With some error tolerance
 A signature issued by a user with identity  can be
verified by another user with identity ′
 If  and ′ are within a certain distance judged by
some metric
Applications

 Attribute-based signature
 Biometric identity based signature
Preliminaries

• Bilinear Pairing
• Computational Diffie-Hellman
• Threshold Secret Sharing Schemes
Bilinear pairing

 Let  and  be multiplicative groups of the same
prime order
 Bilinear pairing is a map :  ×  →  with
following properties:
 Bilinear:   ,   = (, ) , where ,  ∈  and
,  ∈ ℤ
 Non-degeneracy: ∃ ,  ∈ :  ,  ≠ 1
 Computability: It is efficient to compute (, ) for all
,  ∈
Computational DiffieHellman (CDH)

,  =  ,  =
Challenger

ℬ
∈
CDH Assumption

Pr ℬ ,  ,  =  ≥
 The computational (t,) - DH assumption holds if no
in solving the game
Threshold Secret Sharing
Scheme

Threshold Secret Sharing
Scheme

 Let:
   be a finite field with  ≥  elements
  ∈   be the secret
   =+
−1

=1
 Assign every player  with a unique field element
  =
 Set of players , where  ≥  can recover secret using
   =
∈ Δ ,
 Δ ,  =
=
−
∈,≠  −

∈ Δ ,

Fuzzy Identity Based
Signature (FIBS) scheme

Consisted of 4 steps:
•
Setup
•
Extract
•
Sign
•
Verify
1
Setup

FIBS schemes


Sign

Extract
Verify

0/1
′
Security Model

Unforgeable Fuzzy Identity Based Signature against ChosenMessage Attack (UF-FIBS-CMA)
Security Model

Setup
,

Private
Key
Oracle
Signing
Oracle

∗ for (∗ , )

Definition

 ’s success probability is
−−
,
= Pr  , ,  = 1
 The fuzzy identity based signature scheme FIBS is
said to be UF-FIBS-CMA secure if
−−
,
is negligible in the security
parameter
The Scheme

,
1
Setup

FIBS schemes


Sign

Extract
Verify

invalid/valid
0/1
′
′
Building Blocks

  and   are groups of the prime order
 Bilinear pairing :  ×  →
  is a generator of
 Identities are sets of  elements of ℤ∗
 Δ,  =
−
∈,≠  −

Setup ,

 Choose 1 =   , 2 ∈
 Choose 1 , … , +1 uniformly random from
 Let  be the set 1, … ,  + 1

Δ

,
+1
   = 2

=1
 Select a random integer  ′ ∈ ℤ
 Select a random vector  = 1 , … ,  ∈ ℤ

′
 Public parameters  = 1 , 2 , 1 , … , +1 ,  ′ =   , 1
Extract , ,

 Choose a random  − 1 degree polynomial  such
that  0 =
 Return  =  ∈ ,  ∈ ∈ 2

  = 2
  = −
  is a random number from ℤ defined for all  ∈
Sign ,  ,

 A bit string  = 1 ⋯  ∈ 0,1
 Select a random  ∈ ℤ for  ∈
 Output
=
∈ 3
∙
′

=1

,
∈
−
,

∈
∈
′
Verify ,  , ,

 =
1

, 2
∈
′ ∩

∈
, 3
∈
 ′ where
≥
 Choose an arbitrary -element subset  of ′ ∩
 Verify

1 ,  ∙  2 ,
Correctness check




1 ,  ∙  2 ,

2

2



2

2 ,

2 ,







∙

, ∙
,
Δ, 0
Δ, 0

Δ, 0
2 ,
2 ,
2 , 1
1 , 2
0
∙ ′

∙  3 ,  ′

=1
, ∙

′

=1
Δ, 0
,  ∙  − ,

=1
∙  − ,  ′
, ∙
−
,
Δ, 0

=1
∙
−
,
′

=1
Δ, 0
Security Proof

Security Game

Setup
,  ∗
∗

Private
Key
Oracle
,  ,
Signing
Oracle

∗ for (∗ , )
Simulator ℬ

Theorem

 Let  be an adversary that makes at most  ≪
signature queries and produces a successful forgery
against the scheme with probability  in time
 Then there exists an algorithm ℬ that solves the CDH

problem in ℤ with probability  ≥  in time  ≈
4
Setup

 Select a random identity  ∗
 Choose
 A random number  ∈ 0, … ,
 Random numbers  ′ , 1 , … ,  in the interval
0, … , 2 − 1
 Random exponents  ′ , 1 , … ,  ∈ ℤ
Setup

 Let 1 =  and 2 =
 Choose
 A random  degree polynomial
 An  degree polynomial   such that ∀   = −  if and only if
∈

  = 2
   =

2

for  from 1 to  + 1
+1
=1

2

Δ,
  = , 1 , 2 , 1 , … , +1 ,  ′ = 2
=
+
2
′ −2
′

,  = 2
=1,…,
, =
Private Key Oracle

 Answer private key query on identity
  ∩ ∗ <
 Define Γ, Γ ′ ,
 Γ=∩
 Γ ⊆ Γ ′ ⊆  and Γ ′ =  − 1
  = Γ′ ∪ 0
Private Key Oracle

 Define private key  for  ∈
 For  ∈ Γ ′

∈Γ′ = 2
,
′
∈Γ
∈Γ′
= −
∈Γ′
  and  are chosen randomly in ℤ
 For  ∈  − Γ ′
=
=
Δ,
2
∈Γ′
−Δ0,
−
+
1
′

−

1 +
+()
2

′
Δ0,
Private Key Oracle

 Define  − 1 degree polynomial   as   =  ,  0
=
 Let  =
′
−

+
Δ0,
 For  ∈  − Γ ′ , it can be shown that

= 2
= −
Signing Oracle

 Answer signature query on identity  ∗ for some
= 1 ⋯
  = −2 +  ′ +
=1
  = ′ +

=1
 If  ≡ 0   , then the simulator aborts
 Select a random set Λ
 Λ ⊂ ∗
 Λ =−1
Signing Oracle

 For  ∈ Λ

′
=
′
 ′ is chosen randomly in ℤ
 For  ∈  ∗ − Λ

′

=
−1
=1

′ Δ,∗
Δ0,∗

Signing Oracle

 Pick random  ,  for  ∈  ∗
 Compute

1 =
′

−

1
−

2 = −

3 =
′
2

Signing Oracle

 For  =  −
()
1

′

, it can be shown that
′
= 2

3 = −

′

=1

Producing Forgery

 Output a valid forgery  ∗
=
1
∗
∗
, 2
∈
∗
∗
1 ⋯  ∈
=
0,1
  ∗ = −2 +  ′ +

∗

=1
∗ or  ∗ ≢ 0
∗
, 3
∈
for
∈
on ∗
identity

∗

=1
 ∗ =  ′ +
 If  ≠
, then aborts.
Producing Forgery

 For some ∗ , ∗ ∈ ℤ
1
∗
=
∗

∗
2

∗
∗
∗ ∗

= 2
∗
∗
−

2 =
∗
∗
−

3 =
′

=1
∗

∗

Producing Forgery

 Select a random set Λ′ such that Λ′ ⊂  and Λ′ =
 Compute
1∗
=
=

2∗
3∗
=
=
∈Λ′
∈Λ′
1
∗
Δ,
∗
∗ ∗
Δ

Δ

,
,

Δ

∗ ,
2
′
∈Λ
Δ

∗ ,
3
=
∈Λ′
=
∈Λ′
∈Λ′
∗
−Δ

,

−Δ,  ∗

Solving CDH

 ℬ could solve the CDH instance by outputting
∗
∗
∗ ∗
1 ∙ 2 ∙ 3
=
 The probability is
Pr ℎ
= Pr  =  ∗ ∙ Pr  ≢ 0   ∙ Pr  ∗ ≡ 0
1
1
1
1
= ∙ 1−
∙
≤

2 2 4
  ≥  ∙ Pr ℎ    ≥  ∙
1
4
Issues

• Privacy
• Capture and replay
Privacy

 No anonymity for signer
Capture and replay

 Only secure when forgery of identity can be detected
Conclusion

Conclusion

 Allows identity  to issue a signature that identity
′ can verify
 Provided that  and ′ are within some distance
 Unforgeable against adaptively chosen message
attack
Thank you

Question?
References

1.
2.
3.
4.
5.
6.
Dan Boneh and Matthew K. Franklin. Identity-based encryption from the
weil pairing. In CRYPTO ’01: Proceedings of the 21st Annual International
Cryptography Conference on Advance in Cryptology, page 213-229, London,
UK, 2001. Springer-Verlag.
Jin Li and Kwangjo Kim. Attribute-based ring signature. Cryptology
ePrint Archive, Report 2008/394, 2008.
Amit Sahai and Brent Waters. Fuzzy Identity-Based encryption. In
Advance in Cryptography – EUROCRYPT 2005, page 457-473. 2005.
Siamak F Shahandashti and Reihaneh Safavi-Naini. Threshold attributebased signatures and their application to anonymous credential systems.
Cryptology ePrint Archive, Report 2009/126, 2009.
Brent Waters. Efficient Identity-Based encryption without random oracles.
In Advance in Cryptography – EUROCRYPT 2005, page 114-127. 2005.
Piyi Yang, Zhenfu Cao, and Xiaolei Dong. Fuzzy identity based signature.
Cryptology ePrint Archive, Report 2008/002, 2008.
```