Learning with Errors Problem - Lab Report Example

Learning with Errors Problem Name Tutor 01.05.2011 LEARNING WITH ERRORS (LWE) PROBLEM Learning with errors has come to be one of the best bases for cryptographic construction. This is made possible by learning with errors being as hard as the worst-case lattice problems thus making cryptographic construction to be secure (Micciancio and Regev, 2008). Learning with errors uses algorithms to solve problems. These algorithms are such as the maximum likelihood algorithm which assumes that with high probability the solutions arrived at is always unique. Another algorithm is the Blum et al algorithm that solves a problem using 20(n) samples and time. It finds a small set of S equations among the 20(n) equations. Through the summing up of the equations, the coordinates of s can be recovered after the collision. The third algorithm keeps asking for learning with error samples until poly (n) equations of the form s1 are seen. This is repeated till all the s1 coordinates are recovered. Some of the reasons that make learning with errors to be considered hard are such as the running of the best known algorithm in exponential time. Another reason is that learning with errors is seen to be a natural extension of the learning parity with noise problem which is also believed to be hard. Assumptions made regarding the worst case hardness of standard lattice problem such as the decision version of the shortest vector problem (GAPSVP) and the shortest independent vectors problem (SIVP) make learning with errors to be hard. Even with quantum computer it still remains hard to approximate GAPSVP or SIVP. For example having polynomial module q it is hard for GAPSVP to be approximated within polynomial factors d. (Regev, 2009). Application of learning with errors in cryptography Learning with error is widely used in cryptography to ensure the security and correctness of data. It is mostly used as basis for public key encryption schemes, identity based encryption and various forms of leakage resilient encryption. The learning with errors cryptography is stronger than other cryptography due to its hardness. Its implementation in cryptography reduces the complexity of encryption. For example taking a cryptosystem parameterized with the following integers: n- Security parameter, m- Number of equations, q- Modulus, α >0- which is a noise parameter. To guarantee security using the learning with errors we have to choose q to be a prime number between n squared and 2n squared, m=1.1.nlogq and α=1/ 1/(n log2 n). Learning with error will enable the cryptosystem to come up with the public key, private key to carry out decryption and encryption. Through learning with errors elements of encryption will have the following values: - Private Key: This will be a vector chosen uniformly from n to q. Public key: This will consist of m samples from the learning with errors distribution with secret s, modulus q, and error parameter α. Decryption: This is the decryption of a pair (a, b) is 0 if b-(a, s) is closer than to [q/2] modulo q and 1 otherwise. Public Key Infrastructure The public key infrastructure is used to ensure the integrity, privacy and security of messages by people who transfer data over a network. A user can use two keys one which is a private key and the other one which is the public key or use the same key to encrypt the message. The efficiency of this is assured by how safe the key is kept by the users. To ensure the safety of the key storage is done in the client computer or temper resistant devices. The temper resistant devices once tampered with the key cannot be accessed because the key will be spoilt once the device is tampered with. Another way of ensuring that the key is secure is changing the key as frequently as possible. The public key infrastructure consists of the following elements: A certificate authority that issues the digital signatures by creating the public key and the private key for the user. A registration authority that acts as the verifier for the certificate A directory where the certificates with public keys are held. The public key infrastructure ensures that once a person is involved in a transaction the person cannot deny the transaction by use of digital signatures which are generated when the transaction is taking place. Through the verification of the identity of a person by a digital signature accountability and trust is created between parties over the internet. Encryption in public key infrastructure In the public key infrastructure they are two ways through encryption can be performed. One of these methods is symmetric encryption and the other one is asymmetric encryption. For communication to take place an encryption and decryption key have to be available. In symmetric encryption the same key is used for both activities while in asymmetric encryption two keys are used namely the private key and public key. Symmetrical encryption has a problem because it has to transport the key over a network which leaves it exposed to the hackers over the network. This leads to the need of the asymmetrical encryption. In the asymmetrical encryption the public key encrypts a message and the private key decrypts the message once it is received. A private key cannot decrypt a message that is not encrypted in its own public key. One of the algorithms used in the asymmetric encryption is the riverst-shamir-adleman algorithm which allows any key to encrypt or decrypt the message. Another algorithm is the Elliptic Curve Digital Signature algorithm (ECDSA) which implements encryption with a smaller key without compromising their security. The effectiveness of the public key cryptography depends on the following family standards- 1. RSA encryption : provides for the construction of the digital signatures and digital envelopes 2. Diffie-Hellman key agreements- this is where two people can agree on a shared secret key that is known to both of them. Once one person sends the message he encrypts it with the key and the other person will use the key to decrypt the message. This people will not pass these key to a third party for privacy purposes. 3. Password based encryption- this are used to hide the private keys when transferring them between computer systems. This ensures that the keys cannot be accessed by any unauthorized person because for a person to access them they should have the password. 4. Extended certificate syntax- this allows addition of information to certificates. This information might be policies about the usage of the certificate. 5. Private Key information syntax- it describes how to include private key along with algorithm information and a set of attributes to offer a simple way of establishing trust in information needed. Hashing This is where a digital fingerprint is obtained for a given message. This hash can be used to validate the message without reproducing the message. Every message will have its own different hash code to ensure the effectiveness of the hash. The codes are normally 128 or 160 bits. These codes will be used to see if the message received resembles the initial message sent. Process of Obtaining a Digital signature To obtain a digital signature the message is first hashed and then the clear message is encrypted using the receiver’s public key. Once received the message is separated from the digital signature and then decrypted using the recipient private key. The message is then hashed to a digital fingerprint which is used to validate the received message. Through this the safety and the validity of the message is assured. Duties of certificate authorities Certificate issuance-this happen where a new user needs a certificate for use. Certificate renewal- once a user’s certificate period expires the user can be issued with the same certificate for another period of time. Certificate revocation- this is where the usage of a certain certificate is stopped when the private key has been compromised. Once a thief posses a private key and posses its accompanying certificate he can use the key to masquerade as the legitimate key holder without suspicion. When this is detected the certificate serial number is placed in the certificate revocation list so that the certificate or the key are not used again. Threats to certificate authority The certificate authority faces external and internal threats. External threats are those threats that attempt to steal the private key using external computers located outside the physical certificate authority system environment. These attacks may arrive via the internet where they break the firewall to get into the certificate authority environment and read the keys used in the organization. Internal attacks are posed by employees responsible for operating and maintaining the certificate authority. To prevent this administrator can limit the access to them and also ensure no one person has the full knowledge of a complete key. To limit access the administrator can come up with an access list of those users supposed to access the computers where he defines the responsibility of each user and privileges accorded to each user. This will ensure those user who do not have permission to access the certificate authority do not see it even if they access the system. The security of where these hard wares in which the certificate authority is stored should be maintained. This is done by having strong rooms where they are stored and screening workers who enter these rooms to ensure they have permission to get in and they don’t carry sensitive materials out of the room. The certificate practice statements (CPSs) The certificate practice statement contains detailed description of certificate policies and how the certificate is implemented by certain certificate authority. When two certificates from different certificate authorities negotiates they examine each other’s certificate practice statement so that to decide if they can trust each other and each certificate to know the trust the certificate authority has put into the certificate. The better the policies in the certificate practice statement the more trust is put in the certificate by the certificate authority. Encryption primer Encryption takes place to make plain text unreadable by unauthorized personnel. This is done by having a key and an algorithm which will achieve it. The key represents the number of positions a letter will have to be shifted. To increase the security of this we can increase the length of the key and device more complex algorithm. People are saved the trouble of coming up with their own algorithm but use already accepted algorithms. This algorithms includes the Data Encryption Standard (DES), International Data Encryption Algorithm (IDEA) which gives a key of 128 bit, Data Encryption Standard and RC4 which is an algorithm developed by Ron Rivest as a stream cipher with variable key length. Secret Key Cryptography This relies on the two parties’ sender and the receiver having the knowledge of a secret key they use to encrypt their message. They will both have access to the secret key. It works by the sender encrypting the message with the secret key and the receiver uses the same key to decrypt the message. A secret key for them to be passed between the parties without a third party having access to them is a necessity to ensure their privacy. To ensure this they are passed in special tamper proof envelopes or can be encapsulated in hardware devices such as smart cards. In cases where they are encrypted in hardware devices the user will not have access to them but he will use a pin which allows the secret key to be authenticated during the transaction without the user learning of the key that was used. Public key cryptography This is where a person is assigned a pair of keys namely the public key and private key. The public key is generated from the private key using some pre determined algorithms. The public key can be passed to other people while as the private key remains with the owner of the keys for privacy purposes. If a person A wishes to send a message to a person B. The person B will encrypt the message with the public key of A which is published over a directory or distributed in unsecured email. This message will be decrypted by the person holding the private key and not anybody else. This mode of encryption is heavy on system resources when a person is working with huge messages making huge message to use the secret key encryption. Security is ensured by making sure that the hacker cannot get the primary key by reversing the public key and also cracking the encrypted data to get the plain text message. Measures put to counter threat to Encryption using private and public key Two measures were brought forward to solve this problem which is the Key Escrow and key recovery. Key Escrow involves lodging copies of your private keys with trusted third parties who provide a secure facility for their storage. These keys are accessed only if need be and are used to decrypt the message. Instead of depositing the each private key the user can instead deposit the master private key which can decrypt any message. Some of the problems of depositing the master private key are that once one is allowed to have your master private key decryption of your past and future encrypted messages is possible leading to loss of secrecy of past and future messages. This has another problem because all the parties in the communication are not asked for permission of access of the encrypted message. Due to the weaknesses in the key escrow another proposal came into place which is key recovery. This does not require the lodging of the master private key to the trusted third party but keys used to encrypt each session are encrypted using the public key of the trusted third party and then embedded within the session data in a key recovery field. Once the need arises to access the encrypted data the key recovery field is supplied to the trusted third party who decrypts it using his own private key. This method has some advantages such as that the private key recovered is used to decrypt only that session and no any other session. It also ensures these keys are not stored with the trusted third party as was happening before ensuring secrecy of the private key. Critics have been against the idea of trusted third party by arguing that it is prone to be targeted by criminal element that would be able to access a lot of private data at a go. In cases where the master private key is supplied to the trusted third party a mistake by one client would make it all the sessions of the organization to be accessed exposing a lot of sensitive data by being decrypted with the master private key. Conclusion The public key infrastructure is becoming the preferred mode of ensuring security of data over the internet. This is made possible by it adding a layer of security to the public key and the secret key to enhance their efficiency. Organizations that need to achieve a full proof security using the public key infrastructure they will have to integrate it with comprehensive security architecture that includes the general purpose directory and the authorization services. Organizations are also trying to develop standards that will allow for wider deployment of the public key infrastructure in future. These standards are like the XML Key Management Services which will have a positive impact on the public key infrastructure. This leaves the public key infrastructure as the best choice to be used over network for security now and the future. References Micciancio, D. and O. Regev. (2008), Lattice-based cryptography, In D. J. Bernstein and J. Buchman, editors, Post-quantum Cryptography. Springer Regev, O. (2009), “On lattices, learning with errors, random linear codes, and cryptography”. Journal of the ACM, 56(6):34. Read More

Through learning with errors elements of encryption will have the following values: - Private Key: This will be a vector chosen uniformly from n to q. Public key: This will consist of m samples from the learning with errors distribution with secret s, modulus q, and error parameter α. Decryption: This is the decryption of a pair (a, b) is 0 if b-(a, s) is closer than to [q/2] modulo q and 1 otherwise. Public Key Infrastructure The public key infrastructure is used to ensure the integrity, privacy and security of messages by people who transfer data over a network.

A user can use two keys one which is a private key and the other one which is the public key or use the same key to encrypt the message. The efficiency of this is assured by how safe the key is kept by the users. To ensure the safety of the key storage is done in the client computer or temper resistant devices. The temper resistant devices once tampered with the key cannot be accessed because the key will be spoilt once the device is tampered with. Another way of ensuring that the key is secure is changing the key as frequently as possible.

The public key infrastructure consists of the following elements: A certificate authority that issues the digital signatures by creating the public key and the private key for the user. A registration authority that acts as the verifier for the certificate A directory where the certificates with public keys are held. The public key infrastructure ensures that once a person is involved in a transaction the person cannot deny the transaction by use of digital signatures which are generated when the transaction is taking place.

Through the verification of the identity of a person by a digital signature accountability and trust is created between parties over the internet. Encryption in public key infrastructure In the public key infrastructure they are two ways through encryption can be performed. One of these methods is symmetric encryption and the other one is asymmetric encryption. For communication to take place an encryption and decryption key have to be available. In symmetric encryption the same key is used for both activities while in asymmetric encryption two keys are used namely the private key and public key.

Symmetrical encryption has a problem because it has to transport the key over a network which leaves it exposed to the hackers over the network. This leads to the need of the asymmetrical encryption. In the asymmetrical encryption the public key encrypts a message and the private key decrypts the message once it is received. A private key cannot decrypt a message that is not encrypted in its own public key. One of the algorithms used in the asymmetric encryption is the riverst-shamir-adleman algorithm which allows any key to encrypt or decrypt the message.

Another algorithm is the Elliptic Curve Digital Signature algorithm (ECDSA) which implements encryption with a smaller key without compromising their security. The effectiveness of the public key cryptography depends on the following family standards- 1. RSA encryption : provides for the construction of the digital signatures and digital envelopes 2. Diffie-Hellman key agreements- this is where two people can agree on a shared secret key that is known to both of them. Once one person sends the message he encrypts it with the key and the other person will use the key to decrypt the message.

This people will not pass these key to a third party for privacy purposes. 3. Password based encryption- this are used to hide the private keys when transferring them between computer systems. This ensures that the keys cannot be accessed by any unauthorized person because for a person to access them they should have the password. 4. Extended certificate syntax- this allows addition of information to certificates. This information might be policies about the usage of the certificate. 5. Private Key information syntax- it describes how to include private key along with algorithm information and a set of attributes to offer a simple way of establishing trust in information needed.

Read More