QR ⇒ IBE (Cocks, random oracle model)
Statement
Let be a Blum integer and a hash function from identities to , the units of Jacobi symbol . In Cocks’s scheme and . Since , exactly one of is a square for , and the key of is a square root of it, computed with . A bit is encrypted as for independent uniform of Jacobi symbol , and decrypted as the Jacobi symbol of if and of if . If QR is hard and is modelled as a random oracle, the scheme is an IND-ID-CPA-secure IBE — Coc01.
Notes
- Decryption is correct because when , and when , so each has the Jacobi symbol of , respectively , unless , respectively , which happens with negligible probability — Coc01.
- Each plaintext bit costs two elements of , one for each sign of , since the sender does not know which of is a square — Coc01.
- Quadratic residuosity also gives a space-efficient IBE in the random-oracle model, whose ciphertext on an -bit message is one element of and bits — BGH07.