Report

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 Adversary ℬ ∈ CDH Assumption An adversary ℬ has at least advantage if: Pr ℬ , , = ≥ The computational (t,) - DH assumption holds if no polynomial-time adversary has at least advantage 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 , Adversary 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 , ∗ ∗ Adversary 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.