1 of 22

Lec 15: PAKE Based on SPHF (cont’d)

2 of 22

Recap

 

 

 

 

 

 

 

 

 

3 of 22

  •  

4 of 22

  •  

5 of 22

  •  

 

 

 

 

 

 

 

 

6 of 22

Summary: gap between game-based and UC

  • 1. UC implies forward secrecy, game-based does not
    • EKE with plain Diffie-Hellman is not UC-secure
  • 2. UC requires password guess extraction from adversarial protocol messages
    • SPAKE2 is not UC-secure w.r.t. standard UC functionality
  • 3. UC requires simulation of session key after successful online attack
    • SPHF-based PAKE is not UC-secure

​

  • 1: “actual” attack
  • 2,3: simulation failure, unclear what “actual” attack is

7 of 22

Instantiations

8 of 22

  •  

9 of 22

10 of 22

Comparison

​

​

​

​

​

​

  • If we get “standard” SPHF for Cramer-Shoup → best of 2 worlds (more about this later)

​

computation cost

communication cost

round

complexity

From Cramer-Shoup [KOY01]

6 exp

(both parties)

​

3 message flows

From Naor-Yung [KV11]

BAD

70 elements

(both directions)

1-simultaneous round

 

11 of 22

History of SPHF-Based PAKE

12 of 22

  • [CS98]: Cramer-Shoup encryption scheme
  • [KOY01]: PAKE from SPHF for Cramer-Shoup
    • No concept of SPHF then, somehow analyzed the whole protocol as a monolith
  • [CS02] (rewrite of [CS98]): introduction of SPHF, reinterpreting Cramer-Shoup using SPHF
    • Cramer-Shoup itself uses SPHF, and then you can use Cramer-Shoup-based SPHF to construct a PAKE…
  • [GL03]: reinterpreting KOY using SPHF

13 of 22

  • Optimizations of KOY/GL
    • [KMTG05]: 2nd message only needs a CPA-secure encryption scheme (doesn’t apply to our protocol)
    • [Gennaro08]: replace one-time signature with MAC
    • …
  • [KV09]: lattice-based SPHF (and PAKE)
  • [KV11]: 1-simultaneous round PAKE
    • In SPHF for Naor-Yung, projection key does not rely on statement
    • Using such an SPHF, 3-message KOY “collapses” into 1-simultaneous round

14 of 22

Homework problem 1

  • Recall that the SPHF for Cramer-Shoup is a “relaxed” notion where the projection key relies on the statement (whereas the SPHF for Naor-Yung is “standard”, but Naor-Yung is less efficient than Cramer-Shoup).
  • There is a paper that constructs a “standard” SPHF for Cramer-Shoup.
  • (a) What is this paper?
    • If you cannot find it, send me an email/message or ask around
    • If you can find it yourself, that’s 1 bonus point

15 of 22

  •  

16 of 22

Homework problem 2

  • There is a paper that introduced security against plaintext-checking attack (PCA-security) for public-key encryption schemes, which is weaker than CCA-security. It also claimed that in the SPHF-based PAKE we saw last time, using a PCA-secure encryption scheme instead of a CCA-secure one suffices.
  • (a) What is this paper?
    • If you cannot find it, send me an email/message or ask around
    • If you can find it yourself, that’s 1 bonus point
  • (b) Describe what PCA-security is. An informal but clear description is fine.
    • My answer only has 1 sentence…

17 of 22

  • (c) Explain, in your own words, why the CCA-secure encryption scheme in PAKE can be replaced by a PCA-secure one. An informal but clear explanation is fine.
    • Pinpoint the argument under which hybrids in last lecture’s security proof need to change, and how exactly
    • My answer has 2 sentences

18 of 22

Homework problem 3 [difficult, optional, bonus 5 points]

  • The PAKE protocol in [KV11, Thm 1] requires a CCA-secure labeled encryption scheme. The reason why they do it is…
  • …the security proof I showed in Lec 14 is flawed; to fix it, you need a labeled encryption scheme.
  • Where exactly does my proof break down, and how does the “label” help?
    • I stared at this for 1 hour before realizing the issue, so don’t feel bad if you cannot solve it…

19 of 22

  • Submit a paper copy of your solution in class on 03/11 (Tue)

20 of 22

References

  • [CS98] Ronald Cramer and Victor Shoup. A Practical Public Key Cryptosystem Provably Secure Against Adaptive Chosen Ciphertext Attack. In CRYPTO 1998.
  • [KOY01] Jonathan Katz, Rafael Ostrovsky, and Moti Yung. Efficient Password-Authenticated Key Exchange Using Human-Memorable Passwords. In EUROCRYPT 2001.
  • [CS02] Ronald Cramer and Victor Shoup. Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption. In EUROCRYPT 2002.

21 of 22

  • [GL03] Rosario Gennaro and Yehuda Lindell. A Framework for Password-Based Authenticated Key Exchange. In EUROCRYPT 2003.
  • [KMTG05] Jonathan Katz, Philip MacKenzie, Gelareh Taban, and Virgil Gligor. Two-Server Password-Only Authenticated Key Exchange. In ACNS 2005.
  • [Gennaro08] Rosario Gennaro. Faster and Shorter Password-Authenticated Key Exchange. In TCC 2008.
  • [KV09] Smooth Projective Hashing and Password-Based Authenticated Key Exchange from Lattices. In ASIACRYPT 2009.

22 of 22

  • [KV11] Jonathan Katz and Vinod Vaikuntanathan. Round-Optimal Password-Based Authenticated Key Exchange. In TCC 2011.