The Weizmann I n s t i t u t e of S c i e n c e Rehovot, 7 6 1 0 0 I s r a e l THE IDEA I n t h i s p a p e r w e i n t r o d u c e a novel t y p e of c r y p t o g r a p h i c scheme, which e n a b l e s any p a i r o f u s e r s t o communicate s e c u r e l y and t o v e r i f y The scheme assumes t h e e x i s t e n c e of t r u s t e d key g e n e r a t i o n cent e r s , whose s o l e p u r p o s e i s t o g i v e each u s e r a p e r s o n a l i z e d s m a r t c a r d when he f i r s t j o i n s t h e network. u s e r l i s t . The c e n t e r s c a n b e c l o s e d a f t e r a l l t h e c a r d s a r e i s s u e d , and t h e n e t w o r k c a n c o n t i n u e t o f u n c t i o n i n a completely d e c e n t r a l i z e d way f o r an i n d e f i n i t e p e r i o d . The scheme i s i d e a l f o r c l o s e d groups of u s e r s such a s t h e execut i v e s of a m u l t i n a t i o n a l company or t h e branches of a l a r g e b a n k , s i n c e t h e h e a d q u a r t e r s of t h e c o r p o r a t i o n can s e r v e a s a key g e n e r a t i o n cent e r t h a t e v e r y o n e t r u s t s . The scheme remains p r a c t i c a l even on a n a t i o nwide scale w i t h h u n d r e d s of key g e n e r a t i o n c e n t e r s and m i l l i o n s o f u s e r s , and it can be t h e b a s i s f o r a new t y p e of p e r s o n a l i d e n t i f i c a t i o n c a r d w i t h which e v e r y o n e c a n e l e c t r o n i c a l l y s i g n checks, c r e d i t card s l i p s , l e g a l documents, and e l e c t r o n i c m a i l . The schsme is b a s e d on a p u b l i c key cryptosystem with a n e x t r a t w i s t : I n s t e a d of g e n e r a t i n g a random p a i r of p u b l i c / s e c r e t k e y s and p u b l i s h i n g one of t h e s e k e y s , t h e u s e r chooses h i s name and network ad- o t h e r p a r t y . The c o r r e s p o n d i n g s e c r e t key is computed by a key g e n e r at i o n c e n t e r and i s s u e d t o t h e u s e r i n t h e form of smart c a r d when h e f i r s t j o i n s t h e n e t w o r k . The c a r d c o n t a i n s a m i c r o p r o c e s s o r , a n 1/0 p o r t , a RAM, a ROM w i t h t h e secret key, and programs f o r message enc r y p t i o n / d e c r y p t i o n anL s i g n a t u r e generation/verification. An i d e n t i t y -b a s e d scheme resembles an i d e a l m a i l system: I f you know somebody's name and a d d r e s s you can send him messages t h a t o n l y h e can r e a d , and you c a n v e r i f y t h e s i g n a t u r e s t h a t o n l y he c o u l d h a v e produced. I t makes t h e c r y p t o g r a p h i c a s p e c t s of t h e communication a lmost t r a n s p a r e n t t o t h e u s e r , and i t can be used e f f e c t i v e l y e v e n b y laymen who know n o t h i n g a b o u t k e y s o r p r o t o c o l s . When u s e r A w a n t s t o s e n d a message t o u s e r B , h e s i g n s it w i t h t h e secret key i n h i s s m a r t card, e n c r y p t s t h e r e s u l t by u s i n g B's name and network a When B r e c e i v e s t h e message, he d e c r y p t s it u s i n g t h e secret k e y i n h i s s m a r t c a r d , and then v e r i f i e s t h e s i g n a t u r e by u s i n g t h e s e n d e r ' s name a n d network a d d r e s s a s a v e r i f i c a t i o n k e y . t o t h e p u b l i c k e y s " B " , " C " , e t c . , and t h e scheme would n o t be s e c u r e . The key g e n e r a t i o n c e n t e r c a n be i n a p r i v i l e g e d p o s i t i o n by knowing some secret i n f o r m a t i o n ( s u c h a s t h e f a c t o r i z a t i o n o f a l a r g e number) which e n a b l e s i t t o compute t h e secret keys of a l l t h e u s e r s i n t h e network. The o v e r a l l s e c u r i t y o f t h e scheme depends on t h e f o l l o w i n g p o i n t s : ( a ) The s e c u r i t y of t h e u n d e r l y i n g c r y p t o g r a p h i c f u n c t i o n s . ( b ) The sec r e c y of t h e p r i v e i e g e d i n f o r m a t i o n s t o r e d a t t h e key g e n e r a t i o n c e n t e r s . t h e c e n t e r must c a r e f u l l y s c r e e n r e q u e s t s f o r c a r d s t o p r e v e n t m i s r e p r es e n t a t i o n s , and must c a r e f u l l y p r o t e c t i t s "stamps" t o p r e v e n t f o r g e r i e s . Users c a n p r o t e c t t h e m s e l v e s a g a i n s t u n a u t h o r i z e d u s e o f t h e i r c a r d s v i a a password system or by memorizing p a r t of t h e key. The d i f f e r e n c e s between p r i v a t e -k e y , public-key, and i d e n t i t y -b a s e d c r y p t o s y s t e m s a r e summarized i n F i g . 1. I n a l l t h e s e schemes, t h e m e s - t h e exposed c h a n n e l , and d e c r y p t e d under key kd. The c h o i c e of k e y s i s based on a t r u l y random seed k. and t h e s e p a r a t e key c h a n n e l (which i s u s u a l l y a c o u r i e r ) must p r e s e r v e both t h e s e c r e c y a n d ti:2 a u t h e n t i c i t y of t h e key. I n public-key schemes, the e n c r y p t i o n and d e c r y p t i o n k e y s a r e d e r i v e d from k v i a two d i f f e r e n t f u n c t i o n s ke = f e ( k ) and kd = f d ( k ) , and t h e s e p a r a t e key c h a n n e l (which i s u s u a l l y a d i r e c t o r y ) must p r e s e r v e o n l y t h e a u t h e n t i c i t y of t h e key. The s e p a r a t e key c h a n n e l between t h e u s e r s i s completely e l i m i n a t e d , and i s r e p l a c e d by a s i n g l e i n t e r a c t i o n w i t h t h e key g e n e r a t i o n c e n t e r when t h e r e c i p i e n t f i r s t j o i n s t h e network. I n p r i v a t e -k e y schemes, k e = k d = k , THE IMPLEMENTATION When t h e s e e d k i s known, secret k e y s c a n b e e a s i l y computed f o r a n o n -n e g l i g i b l e f r a c t i o n of t h e p o s s i b l e p u b l i c keys. s e e d k from s p e c i f i c p u b l i c / s e c r e t key p a i r s g e n e r a t e d w i t h t h i s k i s i n t r a c t a b l e . ( b ) The problem of computing t h e U n f o r t u n a t e l y , t h e FGA scheme c a n n o t be used i n a way t h a t s a t i sf i e s t h e s e c o n d i t i o n s s i m u l t a n e o u s l y : ( a ) I f t h e modulus n i s a pseudorandom f u n c t i o n of t h e u s e r ' s i d e n t i t y , even t h e key g e n e r a t i o n c e n t e r c a n n o t f a c t o r t h i s n and c a n n o t compute t h e d e c r y p t i o n exponent d from t h e e n c r y p t i o n e x p o n e n t e. ( b ) I f t h e modulus n i s u n i v e r s a l and t h e seed i s i t s s e c r e t f a c t o r i z a t i o n , t h e n anyone who knows an e n c r y p t i o n exponent e and i t s c o r r e s p o n d i n g d e c r y p t i o n exponent d can compute t h e seed. A t t h i s s t a g e w e h a v e c o n c r e t e implementation p r o p o s a l s o n l y f o r i d e n t i t y -b a s e d s i g n a t u r e schemes, b u t w e c o n j e c t u r e t h a t i d e n t i t y -b a s e d c r y p t o s y s t e m s e x i s t a s w e l l a n d w e encourage t h e r e a d e r t o l o o k f o r s u c h systems. T h i s s i t u a t i o n i s r e m i n i s c e n t of t h e 1 9 7 6 p e r i o d , when p u b l i c key c r y p t o s y s t e m s w e r e d e f i n e d and t h e i r p o t e n t i a l a p p l i c a t i o n s w e r e where -m i s t h e message -s , t i s t h e s i g n a t u r e -i i s t h e u s e r ' s i d e n t i t y -n i s t h e p r o d u c t o f two l a r g e primes -e i s a l a r g e p r i m e which i s r e l a t i v e l y prime t o 9 ( n ) -f i s a o n e way f u n c t i o n . The p a r a m e t e r s n , e and t h e f u n c t i o n f are chosen by t h e k e y g e n e ra t i o n c e n t e r , and a l l t h e u s e r s have t h e same n , e and t h e same a l g o r i t hm i c d e s c r i p t i o n o f f s t o r e d i n t h e i r smart c a r d s . These v a l u e s c a n be made p u b l i c , b u t t h e f a c t o r i z a t i o n of n should be known o n l y t o t h e key g e n e r a t i o n c e n t e r . The o n l y d i f f e r e n c e between u s e r s i s t h e v a l u e of i , and t h e secret key which c o r r e s p o n d s t o i i s t h e ( u n i q u e ) number g such t h a t g e = i (mod n ) . T h i s g can be e a s i l y computed by t h e key g e n e r a t i o n c e n t e r , b u t if t h e RSA scheme i s s e c u r e n o o n e e l s e can e x t r a c t e -t h r o o t s mod n. Each message m h a s a l a r g e number of p o s s i b l e ( s , t ) s i g n a t u r e s , b u t t h e i r d e n s i t y i s so l o w t h a t a random s e a r c h i s e x t r e m e l y u n l i k e l y t o d i s c o v e r any o n e o f them. Any a t t e m p t t o s e t one of ( s , t ) t o a random v a l u e and s o l v e f o r t h e o t h e r v a r i a b l e r e q u i r e s t h e e x t r a c t i o n o f modular r o o t s , which i s b e l i e v e d t o be an exceedingly d i f f i c u l t comput a t i o n a l t a s k . However, when g is known, t h e r e i s a very s i m p l e way t o g e n e r a t e any number o f s i g n a t u r e s of any message even when t h e fact o r i z a t i o n of n i s unknown. T o s i g n t h e message m , t h e u s e r chooses a random number r a n d comp u t e s e t = r (mod n ) . The v e r i f i c a t i o n c o n d i t i o n c a n be r e w r i t t e n a s S i n c e e i s r e l a t i v e l y prime t o c p ( n ) , w e can e l i m i n a t e t h e common f a c t o r e from t h e e x p o n e n t s s = g -r f ( t r m ) (mod n ) 51 and thus s can be computed without any root extraction. TO prevent attacks based on multiplicative relationships between the identities (and thus also the g values) of different users, it is advisable to expand the string that describes the user's identity into a long pseudo-random sLring via a universal one way function, and use the expanded form as i in the verification condition. Since everyone in thenetwork knows how to apply this function, the scheme retains its identity-based flavour even though the signature verification key is not strictly equal to the user's identity. The security of the scheme depends on the inability of the cryptanalyst to isolate g by analysing a large number of valid signatures of messages of his choice. If the gcd of f and e is c # 1, it is possible to extract the c-th root of i by manipulating the verification condition, and thus it is essential to make e a sufficiently large prime and f a sufficiently strong one way function so that this case will never arise in practice. The value of r should never be reused or revealed, since g is protected in any concrete signature by its randomness and secrecy. The variants of the verification condition in which one of the two occurrences of t is eliminated (e.g., by replacing it with a constant) are insecure. It is thus important to use a one way function that mixes t and m thoroughly (preferably via non-arithmetic and non-invertible operations) and which has a large range of possible values. We believe that with a proper choice of parameters this scheme can be made very secure, but we cannot prove that breaking it is equivalent to solving some well known computational problem. Its main purpose is didactic, to serve as the first existence proof for identity based schemes. The Ong-Schnorr-Shamir signature scheme (described elsewhere in these proceedings) can also be used as an identity-based scheme, but its security is still an open problem in light of Pollard's successful attacks against its earlier verisons. As always, we do not recommend to use this scheme right away, before the cryptographic community had ample time to assess its security.
The work REF proposes the idea of an identity-based cryptosystem in which arbitrary strings can act as public keys so that there is no need for public-key certificates.