Rotatable Zero Knowledge Sets

In this research, the concept of Rotatable Zero Knowledge Sets is explored in the context of Post-Compromise Secure Auditable Dictionaries with application to Key Transparency. The study delves into how users can verify the correctness of their public keys stored in auditable dictionaries and how auditors can validate commitments. Additionally, the paper discusses the importance of privacy preservation in Key Transparency and presents the contribution of Rotatable Zero Knowledge Sets in enhancing security measures. The content covers various aspects of end-to-end encrypted communication systems, key transparency, and privacy concerns in existing solutions.

• Security
• Auditable Dictionaries
• Key Transparency
• Privacy Preservation
• Encryption

ahnest Follow

Uploaded on Feb 17, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

Presentation Transcript

1. Rotatable Zero Knowledge Sets Post Compromise Secure Auditable Dictionaries with application to Key Transparency Brian Chen1, Yevgeniy Dodis2, Esha Ghosh3, Eli Goldin2, Balachandar Kesavan1, Antonio Marcedone1, Merry Ember Mou1 1. Zoom 2. NYU 3. Microsoft Research 1

2. End-to-End Encrypted (E2EE) Communication Systems Server Alice Bob 2

3. Key Transparency/Auditable Dictionaries Users can verify their public key is stored correctly using proof and commitment com com. com com com com0 0 Identity com com1 1 pk com com2 2 Note: at most one pk per identity! 3

4. Key Transparency/Auditable Dictionaries Auditors can verify commitments are updated correctly using i i com com com com0 0 1 1 Identity com com1 1 2 2 pk com com2 2 Note: at most one pk per identity! 4

5. Privacy Preserving KT By default, does not preserve privacy Existing solutions: CONIKS [MBBFF15], SEEMless [CDGM19] 5

6. aZKS pk SEEMless - append-only Zero Knowledge Sets General Database (label = identity, val = pk) Append-only Privacy-preserving proofs (zero knowledge) Needs secret key com com com com0 0 1 1 com com1 1 label sk DATABASE 2 2 com com2 2 val 6

7. Privacy Totally Lost on Corruption 1 1 2 2 3 3 D:com D:com0 0 D:com D:com1 1 D:com D:com2 2 D:com D:com3 3 1 1 2 2 3 3 D:com D:com0 0 D:com D:com1 1 D:com D:com2 2 D:com D:com3 3 7

8. Our Contribution (Rotatable Zero Knowledge Sets) 1 1 2 2 3 3 D:com D:com0 0 D:com D:com1 1 D:com D:com2 2 D:com D:com3 3 ROTATE 1 1 2 2 3 3 D:com D:com0 0 D:com D:com1 1 D:com D:com2 2 D:com D:com3 3 ROTATE 8

9. Basic Construction (warmup w/o privacy guarantees) com com label val' val 9

10. Key Transparency - aZKS com com com com label label val' com(val ) com(val ) val com com(val) 10

11. Key Transparency - aZKS com com com com label label? val' com(val ) com(val ) val com com(val) 11

12. Key Transparency - aZKS com com com com label com com(label)? val' com(val ) com(val ) val com com(val) 12

13. Key Transparency - aZKS sk com com com com label PRF( , label)? val' com(val ) com(val ) val com com(val) 13

14. Key Transparency - aZKS sk pk com com com com label VRF VRF( , label) val' com(val ) com(val ) val com com(val) 14

15. = VRF = VRF( , x) x VRF KeyGen sk pk Query( , x) ( , ) x Verify( , x, y, ) 0/1 Uniqueness: Verify 1 iff y = x x Pseudorandomness: looks random 15

16. Key Rotation sk pk sk pk com com com com Rotate VRF VRF( , label) VRF VRF( , label) com com(val) com com(val) 16

17. = VRF = VRF( , x) x Rotatable VRF = VRF = VRF( , x) x x1 x1 x2 x2 Rotate x3 x3 x4 x4 17

18. = VRF = VRF( , x) x Rotatable VRF = VRF = VRF( , x) x KeyGen , sk pk x Query( , x) ( , ) Verify( , x, y, ) 0/1 Rotate( , x Rotate( , x1 1, , x , , xk k) , , ) , , rot sk rot pk VerRotate( , , y VerRotate( , , y1 1, , y , , yk k, y , y1 1 , , y , , yk k ) 0/1 ) 0/1 VerRotate 1 iff yi= PCS: pseudorandom even given xi and yi = xi xi 18

19. VRF Security Rotatable Uniqueness Extractability Pseudorandomness PCS Zero-Knowledge 19

20. Rotatable VRF Security - Zero Knowledge Init Prove Rotate Corrupt x x x x x x, (x) VRF VRF x x x VRF Idealized Object Alice x 20

21. Rotatable VRF Security - Zero Knowledge Sim Corrupt (gets all previous queries) Init Prove Rotate x x x x x x, (x) VRF VRF x x x VRF Idealized Object Alice x 21

22. DDH Tuples (g, h, ga, ha) [ChaumPederson93]: ZK proof (DDH + ROM for Fiat-Shamir) 22

23. Standard VRF [GRPV22] F : M G (random oracle) g (group generator) KeyGen sk, pk = gsk VRF(sk, x) = F(x)sk 23

24. Standard VRF - Query pk = gskand VRF(sk, x) = F(x)sk Query(sk, x): y = F(x) F(x)sk = proof (g, F(x), pk, y) is a DDH-tuple sk, Why? pk = g pk = gsk sk y = F(x) y = F(x)sk sk 24

25. Standard VRF - Rotate pk = gskand VRF(sk, x) = F(x)sk Rotate(sk, x): Choose random exponent a sk * a sk gsk = pka pk 25

26. Rotatable VRF - Rotate pk = gskand VRF(sk, x) = F(x)sk Rotate(sk, x): sk = sk * a, pk = pka, y = VRF(sk, x), y = VRF(sk, x ) = proof (pk, y, pk , y ) is a DDH-tuple Why? y = F(x) y = F(x)sk sk, pk = pk , pk = pka a y = y y = ya a= F(x) = F(x)sk * a sk * a= VRF(sk , x) = VRF(sk , x) 26

27. Rotatable VRF - Zero Knowledge Ignoring rotations: DDH Assumption + programmable ROM Zero Knowledge Idea: program F(x) so y = F(x)sk 27

28. Rotatable VRF - Zero Knowledge With corruptions: pk = gskcommits to sk! If we give (pk, pk ), commit to (sk, sk ) need F(x)sk= y and F(x)sk = y May be impossible! But does it lead to an attack? 28

29. Rotatable VRF - Zero Knowledge Solution: Stronger idealized models Shoup s Generic Group Model (GGM) gx x EXP * ga, gb ga+b= EXP(EXP-1(a) + EXP-1(b)) 29

30. Rotatable VRF - Zero Knowledge Key trick: in GGM, giving pk = gskdoes not commit to sk. Don t need to define discrete logs until corruption 30

31. Rotatable VRF - Zero Knowledge (Lazy GGM) Query Query Query Query Query Group Element Group Element Group Element Group Element Group Element Discrete Log Discrete Log Discrete Log Discrete Log Discrete Log F(x) F(x) F(x) F(x) F(x) 7314153 7314153 7314153 7314153 7314153 1243543 Bx Bx Bx Bx pk1 pk1 pk1 pk1 pk1 1531678 1531678 1531678 1531678 1531678 9857043 9857043 A1 A1 A1 pk2 pk2 pk2 pk2 pk2 9817532 9817532 9817532 9817532 9817532 8247931 8247931 A1*A2 A1*A2 A1*A2 VRF1(x) VRF1(x) VRF1(x) VRF1(x) VRF1(x) 1253278 1253278 1253278 1253278 1253278 3423921 3423921 3423921 A1*Bx A1*Bx VRF2(x) VRF2(x) VRF2(x) VRF2(x) VRF2(x) 0982436 0982436 0982436 0982436 0982436 0928353 0928353 0928353 A1*A2*Bx A1*A2*Bx 2*pk1*VRF1(x) pk1*VRF1(x) pk1*VRF1(x) pk1*VRF1(x) pk1*VRF1(x) 4732814 4732814 4732814 4732814 4732814 1253192 1253192 1253192 1253192 A1+Bx*A1 31

32. Rotatable VRF - Zero Knowledge (Lazy GGM) Query Group Element Discrete Log Query Group Element Discrete Log F(x) 7314153 Bx F(x) 7314153 Bx pk1 1531678 A1 pk1 1531678 153 Corrupt pk2 9817532 A1*A2 pk2 9817532 102 VRF1(x) 1253278 A1*Bx VRF1(x) 1253278 153*Bx VRF2(x) 0982436 A1*A2*Bx VRF2(x) 0982436 102*Bx pk1*VRF1(x) 4732814 A1+Bx*A1 pk1*VRF1(x) 4732814 153+102*Bx Replacing Aigives VRF(sk, x) = F(x)skfor all sk, x Degree only increases on rotation! Schwartz-Zippel 32

33. Conclusion Using GGM polynomial programming, show RVRF satisfies zero-knowledge RVRF then gives us post-compromise secure auditable dictionary (RZKS) Many additional subtleties/small improvements in both parts 33