Overview of Identity-Based Encryption and Certificate Management
Identity-Based Encryption allows secure communication between participants without a shared secret. Participants obtain certificates from a Trusted Authority containing their public keys for authentication. The process involves issuing certificates, verifying public keys, and handling X.509.v3 standards. Challenges in PKI deployment include responsibility, maintenance, and regulations by the government or industry.
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Identity Based Encryption Debdeep Mukhopadhyay Associate Professor Dept of Computer Sc and Engg, IIT Kharagpur
Public Key Setting Alice and Bob might not have a prior shared secret. Each participant has a pair of public and private key for certain pre-specified cryptosystem or signature scheme. It is always necessary to authenticate the public keys of other people in the network. This requires some kind of Public Key Infrastructure (PKI) We assume there is a Trusted Authoruty (TA) or Certification Authority (CA) who signs the public keys of all people in the network. The public verification key, verTAof the TA is known to all.
Certificates A certificate for someone in the network will consist of: some identifying information for a person (eg, name, email address, etc.), their public keys, and the signature of the TA on that information. The certificate allows network users to verify the authenticity of each other s keys. How does Alice obtain a certificate from the TA which contains a copy of Alice s public verification key for a signature scheme?
A Protocol to Issue a Certificate to Alice The TA establishes Alice s identity by means of conventional forms of identification like birth certificate, passport etc. Then the TA forms a string ID(Alice), which contains Alice s identification. A private signing key for Alice, signAlice, and a corresponding public verification key verAliceare determined. The TA determines its signature: s=sigTA(ID(Alice)||verAlice) on Alice s identity string and verification key. The certificate Cert(Alice)=(ID(Alice)||verAlice||s) is given to Alice, along with Alice s private key, sigAlice.
Verification of the Public Key Any one who has the TA s verification key, verTAcan verify anyone else s certificate. Suppose, Bob wants to be sure that Alice s public key is authentic: Alice gives her certificate to Bob. Bob can then verify the signature of the TA by checking: verTA(ID(Alice)||verAlice||s)=true Note: The purpose of verifying a certificate is to authenticate the public key. Verifying the signature allows someone to verify that the certificate was issued by the CA. Having verified the signature, a user would then believe the information provided the CA can be trusted of verifying the information before signing.
X.509 v3 Version number Serial number Signature algorithm ID Issuer name Validity period Subject name (ie. Signature owner) Public key of owner Signature of CA on all the fields
Problems of PKI Many difficulties associated with practical large scale deployments of PKI Who is responsible for its deployment, maintenance, and regulations? Govt or Industry? What standards should be used?: certificate formats, cryptographic algorithms, revocation, etc. Lack of PKI compatible applications has slowed down its deployment.
Alternative to PKI Identity Based Encryption (IBE): Refers to Public Key Cryptography where the values of the public key are computed from the identity of the owners. Renders certificates unnecessary, and hence the need for an infrastructure to verify public keys is avoided.
ID-based Encryption Public Key for a user U is obtained by applying a public hash function h to the user s identity string, ID(U). The corresponding private key would be generated by a central trusted authority (denoted by TA). The private key would then be supplied to the user U after that user proves his or her identity to the TA. Issuance of private key by the TA replaces the issuing of a certificate. The resulting private and public keys are used in an encryption scheme, signature scheme, or other scheme. The scheme uses some fixed public parameters, incluiding a certain master key.
IBE and PKI IBE removes the need for certificates. However, still need a convenient and reliable method for associating an identity string with a person. However IBE alleviates many of the problems of PKI. Note that unlike PKI, in IBE any user, say Bob, can encrypt a message for Alice (using the IDAand the public key of the TA) before Alice has received her private key from the TA. Also Bob could include in the IDAany set of conditions that should be met before the TA issues the private key. Could include credit ratings, employment status, minimum age requirement, etc. Date in the IDAto solve the key revocation problem (ie. Private key will be issued only if it has not been revoked).
Designing an IBE Can a Public Key Cryptosystem be converted to an IBE? Let us try with RSA. The TA chooses the RSA modulus n=pq, as the public master key. The factors p and q are known only to the TA, and work as the master private key. How does a user U obtain its key pair?
RSA converted to IBE? Public Key of a user U is an encryption exponent and a private key is a decryption exponent. However, once U has a public key and private key pair, it can factor n. Once U knows the private master key, it can impersonate the TA. Can compute any one else s private key. The IBE fails! Thus IBE necessitates that a user s public key and private key cannot be used to determine the private master key of the TA.
Components of an IBE System Parameters: Master key generation: The TA generates the master public key Mpuband a corresponding master private key Mpriv. Master key, M=(Mpub,Mpriv). A hash function h is also public.
User Key Generation When a user U identifies himself to the TA, the TA uses a function extract to compute to compute U s private key private key Kupriv: Kupriv=extract(M,Kupub), where U s public key is Kupub=h(ID(U)). User U s key is KU=(Kupub, Kupriv).
Encryption and Decryption Encryption: User U s public key Kupubdefines a public encryption rule, eKU, that can be used by anyone to encrypt messages sent to U. Decryption: U s private key Kuprivdefines a private decryption rule dKU, that U will use to decrypt messages he receives.
The Cocks IBE Based on certain properties of the Jacobi symbols. It uses certain number theoretic properties of quadratic residues.
Quadratic Residues Suppose p is an odd prime and a is an integer. Quadratic Residue: a is defined to be a Quadratic Residue (QR) modulo p if a 0 (??? ?) and the congruence ?2 ? (??? ?) has a solution ? ??. a is defined as the quadratic non-residue modulo p if a 0 (??? ?) and a is not a quadratic residue modulo p.
Example Z11 12=1 22=4 32=9 42=5 52=3 62=3 72=5 82=9 92=4 102=1 Note, that the QR forms a palindrome There are exactly (11-1)/2=5 QRs. There are exactly (p-1)/2 QR (Quadratic Residues)
The QR Problem We have a polynomial time deterministic algorithm to solve this decision problem.
Euler comes to the rescue again The time complexity of this check is O(log p)3 by applying square and multiply method to raise an element to a power. Note that if then a is a non-quadratic residue. 1)/2 1(mod ) ( p a p
Jacobi Symbol: Generalization of Legendre Symbol
Example 6278 9975 Compute Note 9975=3x52x7x19 (prime power factorization) 2 6278 9975 6278 3 6278 5 6278 7 6278 19 = 2 = = 2 3 3 5 6 7 8 19 ( 1)( 1) ( 1)( 1) = 2 1
Example An Example
Computing Jacobi without factorization of n Input: m 0, n 1, n odd Output: JacobiSymbol(m,n) if(m==0) { if(n==1) return 1; else return 0;} else if (m>n) return JacobiSymbol(m mod n, n); else{ m=2 m ; (where m 1, m odd) return [JacobiSymbol(2,n)] [JacobiSymbol(n,m )] /* Use -, if m n 3 (mod n), + otherwise */}
Complexity Roughly O(log n)3 Only arithmetic operations are factoring out powers of two and modular reductions. Former depends on number of trailing zeros if the number is encoded as binary. So, dominated by modular reduction. Roughly O(log n) modular reductions necessary, each can be done in O(log n)2
QR(n) QR(n)={x2mod n: x Zn*}, where n=pq. 0 ??gcd ?,? > 1 ? ?= ? ?= 1 ?? ? ?= ? ?= 1 1 ?? ? ?= ? ???? ? ? ?? 1 ??? ? ? ?? ?? ?? 1 1 ?? ??? ?? Note that x is a quadratic residue modulo n iff : ? ? ? ? = = 1 ? ?=1}. Define: \QR ? : ?? ? = {? ?? ? ?= ? ?= 1}. Thus, : ?? ? = {? ?? The later are called as pseudo-square modulo n. The cardinality of both the sets are same, ie. (p-1)(q-1)/4.
Composite Quadratic Residues A positive integer n that is the product of two unknown distinct odd primes p and q, and an integer x Zn* such that Question: Is x QR(n)? This can be no difficult that factorizing n. If you can factorize n, then you can solve it! However if the factorization of n is not known, there does not seem to be an efficient way. ? ?=1.
An easy algorithm to compute square root of y mod p, for ? 3 (??? 4) Note p+1/4 is an integer. ?+1 2 ??? ? ? 1 2 ??? ? Also, note that ( ?(?+1)/4)2 ? ? Note, if y is a quadratic residue (from Euler s Criteria), we have ? Hence, the two square roots are ?(?+1)/4 Note, for cases where ? 1 (??? 4), there is no polynomial time deterministic algorithm. ? 1 2 1 ??? ? .
Cocks Identity Based Encryption Let p, q be two primes such that ? ? 3 ??? 4, and define ? ??. System Parameters: The master key M=(Mpub,Mpriv), where Mpub=n, and Mpriv=(p,q). Hash function h: {0,1}* Zn is a public hash function with the property that ? ??(?) ? 0,1 . ??(?) for all
User Key Generation For a user U, the key KU=(KUpub,KUpriv), where: Kupub=h(ID(U)) and: ??? ?? ?? ?? ??? ??(?) ??? ????)2= ?? (?? ????? ?? ??(?)
Encryption A plaintext is an element in the set {-1,1}. To encrypt perform the following steps: Choose two random values t1,t2 Zn, such that the Jacobi symbols ?1 ? = ? = ?. Compute ?1= ?1+ ?? ?2= ?2 ?? The ciphertext y=(y1,y2) ?2 ????1 ????2 1??? ? 1??? ?
Decryption Given the ciphertext y=(y1,y2), y is decrypted as follows: ????2= ?? Compute the Jacobi symbol: ???? ???, then define s=y1, else define s=y2. If ?? ?+2?? ? = ? The decrypted plaintext is x.
Proof of Decryption Correctness Suppose U receives a ciphertext, (y1,y2), and that ?? ?1+ 2?? ????2= ?? ???, then we show that: ???? ? = ?
???? ????1 1+2?? ? ???? ?1+2?? ?1+?? = ? ????+(?? ????)2?1 1 ?1+2?? = ? ?????1 ????)2?1 1+ (?? ? 2) ?1(1 + 2?? = 2 ?????1 1 ? 1+?? ?1 ? =?1 = = x. ? Note, we use the fact that second Jacobi is 1, as the top part is a quadratic residue for sure.
Cocks IBE is IND-CPA Secure Quadratic Residue Assumption: Jn*={a Zn*|(a/n)=1}. Note: |QRn*|=|Jn*\QRn*| =1/2|Jn*| <n S(1*),a QRn*> <n S(1*), a Jn*\QRn*> It is hard to distinguish between a random quadratic residue and a random non-quadratic residue, given both has Jacobi symbol 1)
Cocks IBE is IND-CPA Secure ???=a=Jn*\QRn*, then Enc(a,+1) Enc(a,-1), ie. ie. Pr[Enc(a,1)=c]=Pr[Enc(a,-1)=c] If ?? ? ?= ? ?=-1. Note, Let c=t+a/t, for some t=t0 Zn*. Note c is the ciphertext produced for a message, m {-1,1} using t, where ?=m. Each possible value of t, thus relates to a message, and thus let us see the probability distribution of this Jacobi. ?
Indistinguishability of the cipher There could be 4 possible solutions to the above equations. We write them using CRT in Zn* and have 4 solutions: <?0 ??? ?,?0??? ? > ?? ?????? <?/?0 ??? ?,?0??? ? > has Jacobi symbol, -1 ?0 <?0 ??? ?,?/?0??? ?> has Jacobi symbol, -1 ?0 Let in form of CR, t1=?/?0 ??? ?, t1=?0??? ? ?= ? ? ? ? 1 2=? ?0 ?0 ? ? ? ? ? ?0 ? ?1 ?1 ?1 ?= ?0 ?/?0 ?0 ? ?0 ? ?0 ?=-1 ?0 ? = ? 1 2 ? 1 2 =- ? ? ?0 ? a t0 ?/?0 ? Note, = = ? 1 2= ? 1 =?0 ?0 1 ?0 ? ? ?=-1, ?0 ? Also note, =?0 ? 1 2
Indistinguishability of the cipher <?/?0 ??? ?,?/?0??? ? > has Jacobi symbol ?0 Note, it means that there is an equal chance st. is inferred. Or, -1?0 ? is inferred. Thus the indistinguishability of the probability distribution. ? ?0 ?
IND-CPA-security Under the assumption of QRA, we can prove the IND-CPA security of the scheme. <n,a QRn*,Enc(a,+1)> <n, a Jn*\QRn* ,Enc(a,+1)> <n, a Jn*\QRn* ,Enc(a,-1)> <n, a QRn* ,Enc(a,-1)>
