NIST, Computer Security Division, Computer Security Resource Center
cryptographic Research Projects
Pairing-Based Cryptography
Recently, what are known as “pairings” on elliptic curves have been a very active area of research in cryptography. A pairing is a function that maps a pair of points on an elliptic curve into a finite field. Their unique properties have enabled many new cryptographic protocols that had not previously been feasible.
In particular, identity-based encryption (IBE) is a pairing-based scheme that has received considerable attention. IBE uses some form of a person (or entity’s) identification to generate a public key. This could be an email address, for instance. An IBE scheme allows a sender to encrypt a message without needing a receiver’s public key to have been certified and distributed for subsequent use. Such a scenario is quite useful if the pre-distribution of public keys is impractical. Besides IBE, there are a number of other applications of pairing-based cryptography. These include many other identity-based cryptosystems (including signature schemes), key establishment schemes, functional and attribute-based encryption, and privacy-enhancing techniques, such as the use of anonymous credentials.
In 2008, NIST held a workshop on pairing-based cryptography. While the workshop showed that there was interest in pairing-based schemes, a common understanding was that further study was needed before NIST approved any such schemes. Starting in 2011, members of the Cryptographic Technology Group have conducted an extensive study on pairing-based cryptographic schemes. This included topics such as: the construction of pairing-friendly elliptic curves, a survey of pairing-based cryptographic schemes, implementation efficiency with respect to the required security, standard activities involving pairing-based schemes, use cases and practical implications. This work was summarized in a technical report, presented in the first quarter of 2012. The report is expected to be published soon. Throughout 2012, project members have been identifying use cases for pairing-based cryptography. At the NIST Cryptography for Emerging Technologies and Applications (CETA) Workshop in November 2011, there was a public call for feedback on potential use cases.
Pairing operations appear to be important tools for various cryptographic schemes used in cloud computing and privacy enhancing environments. Besides IBE, other demanding applications have also motivated the continuation of this study. Short signatures and broadcast encryption are examples of such applications.
Contacts:
pairings@nist.gov
| Dr. Dustin Moody (301) 975-8136 dustin.moody@nist.gov |
Dr. Lily Chen (301) 975-6974 lily.chen@nist.gov /td> |
Post-Quantum Cryptography
In recent years, there has been a substantial amount of research on quantum computers – machines that exploit quantum mechanical phenomena to solve problems that would be intractable for conventional computers. An early breakthrough in this area was Shor’s algorithm, which demonstrated that quantum computers could efficiently factor integers and compute discrete logarithms. These two problems play an essential role in cryptography: they are believed to be hard for classical computers, and they are the basis for nearly all of the public-key cryptosystems that are in widespread use today. If large-scale quantum computers are ever built, they will be able to break our existing public-key infrastructure.
The threat posed by quantum computers appears to be serious, but not immediate. While there has been dramatic progress in experimental quantum physics, the construction of large-scale quantum computers still seems to be many years away. Moreover, the discovery of Shor’s algorithm has also motivated researchers to propose so-called “post-quantum” cryptosystems – public-key cryptosystems that would be secure against quantum computers. It is hoped that these cryptosystems will allow us to maintain our public-key infrastructure in a world with quantum computers. For these reasons, NIST has started a project on post-quantum cryptography, with a view to possible future standards.
The primary focus of this project is to identify candidate quantum-resistant systems, based on algebraic codes, lattices, multivariate systems of equations, cryptographic hash functions, or any other construct that may be secure against both quantum and classical computers, as well as the impact that such post-quantum algorithms will have on current protocols and security infrastructures. The project endeavors to establish the viability of algorithms in these areas, the security of which have yet to be explained well even in the classical model, and, further, to verify the claims of quantum-resistance as quantum complexity theory matures. In the event that no candidate algorithm survives this examination, NIST intends to establish computer security architectures that are not dependent upon the classical public-key cryptographic algorithms, such as the RSA algorithm or the ECDSA algorithm.
In FY2012, NIST researchers Stephen Jordan, Yi-Kai Liu, Ray Perlner, and Daniel Smith-Tone internally presented preliminary status reports in the areas of quantum computation, coding-based cryptography, lattice-based cryptography, and multivariate cryptography, which included detailed surveys of the respective fields, as well as security overviews and specific results. These reports were further supplemented with a presentation from William Whyte and John Schanck from NTRU Cryptosystems on April 25, 2012, discussing the specific countermeasures being deployed in the wake of a serious attack on NTRUSign. NIST also engaged the international cryptographic community with presentations and publications by NIST researchers. At the very end of FY2011, on September 23, 2011, Stephen Jordan presented “Complexity Implications of Quantum Field Theory,” at the Schloss Dagstuhl Workshop on Quantum Cryptanalysis, discussing evidence that more modern quantum field theories may not give rise to greater computational power than the standard quantum circuit model. In the first quarter of FY2012, Daniel Smith-Tone published the paper, “On the Differential Security of Multivariate Cryptosystems,” at the Fourth International Conference on Post-Quantum Cryptography, suggesting a new security metric for multivariate cryptography. Daniel Smith-Tone also published, “The TriTon Transformation,” discussing risky design philosophies in multivariate cryptography at the Third Workshop on Mathematical Cryptology on July 9, 2012. On September 28, 2012 at the Quantum Information Science workshop at the NIST-UMD Joint Quantum Institute, Yi-Kai Liu gave a talk on “Applications of Quantum Information in Machine Learning and Cryptography,” which discussed the role played by quantum information in security proofs for lattice-based cryptosystems.
In FY2013, NIST will continue to explore the security capacity of purported quantum-resistant technologies with the ultimate goal of uncovering the fundamental mechanisms necessary for efficient, trustworthy, and cost-effective information assurance in the post-quantum market. Upon the successful completion of this phase of the project, NIST will be prepared for possible standardization.
Contacts:
| Dr. Daniel Smith-Tone (502) 852-6010 daniel.smith@nist.gov |
Dr. Lily Chen (301) 975-6974 lily.chen@nist.gov |
| Mr. Ray Perlner (301) 975-3357 ray.perlner@nist.gov |
Dr. Dustin Moody (301) 975-8136 dustin.moody@nist.gov |
| Dr. Yi-Kai Liu (301) 975-6499 yi-kai.liu@nist.gov |
Dr. Stephen P. Jordan (301) 975-6134 stephen.jordan@nist.gov |
Privacy Enhancing Cryptography Project
Modern cryptography provides powerful tools for protecting private information, but current standards are often blunt instruments for privacy protection. There are many ways we can develop and standardize new methods to use cryptography that enhance privacy. For example, public-key certificates used for authentication often reveal more personally identifiable information about the certificate holder than is required for a given application.
What is often at issue in accessing data or resources is not the identity of the customer, but whether the customer is a member of an eligible group. Methods that allow a user to selectively reveal and prove only a specific property (such as that the user is at least 21 years old, has a particular place of residence or citizenship) are approaching commercial practicality. Other techniques, such as those that will eventually allow us to search encrypted databases, are still in the research stage. However, these techniques are sufficiently advanced that it behooves us to take stock of the state-of-the-art at this point. Still other techniques, such as those that allow us to hold sealed-bid auctions without ever opening the bids, are known to be practical, yet have received little attention by those that might benefit from them. Such applications fall within the scope of what are known as secure multiparty computations.
In FY2012, NIST held a workshop on Privacy-Enhancing Cryptographic Techniques to explore processes, procedures, and potential applications that could benefit from the ability to operate on encrypted data without decrypting it (see http://www.nist.gov/itl/csd/ct/pec-workshop.cfm). Participants at the workshop included scientists, privacy advocates, and policy experts. We hope to have planted the seeds for cooperation among these different groups, and will continue to pursue this goal in the next fiscal year.
Another major activity for us was in support of the National Strategy for Trusted Identities in Cyberspace (NSTIC) (see http://www.nist.gov/nstic/). Different cryptographic techniques that may be important for this initiative are being continuously evaluated.
Contact:
Dr. Rene Peralta
(301) 975-8702
peralta@nist.gov
Stream Ciphers
Currently, the use of AES in the Output Feedback Mode (OFB) mode and the counter (CTR) mode are approved by NIST as block-cipher based stream ciphers. However, dedicated stream ciphers sometimes have performance advantages, especially for software applications with high throughput requirements, or for hardware applications with constrained resources (such as limited storage, gate count or power consumption). During FY2013, the performance of some of the well-understood stream ciphers (focusing on the eSTREAM finalists) will be studied and compared to the approved block-cipher based stream ciphers. A technical report is being finalized, and is expected to be published soon.
Contacts:
streamcipher@nist.gov
| Dr. Meltem Sonmez Turan (301) 975-4391 meltem.turan@nist.gov |
Dr. Lily Chen (301) 975-6974 lily.chen@nist.gov |
Secure Group Communications
Secure group communication has been shown to be important in public-safety networks, smart grids, and sensor networks. The existing schemes proposed in the research literature, such as multicast encryption schemes and group key-distribution schemes, have been considered as general solutions, but are less scalable for practical applications. In FY2012, we looked into existing results and explored different application scenarios. The requirements and the restrictions were also discussed. In FY2013, NIST will pursue well-tailored solutions for secure group communications.
Contacts:
| Dr. Dustin Moody (301) 975-8136 dustin.moody@nist.gov |
Dr. Lily Chen (301) 975-6974 lily.chen@nist.gov |
Group Signatures
Group signatures have been investigated for more than two decades. In general, a group signature scheme allows a group member to generate a signature on behalf of the group without revealing information about the specific signer. Numerous schemes have been proposed and analyzed in the research literature. Such an anonymity feature is useful for security applications in cloud computing. In FY2013, NIST will further explore the features and underlying mathematical structures for the existing schemes.
Contact:
Dr. James R. Nechvatal
(301) 975-5048
james.nechvatal@nist.gov
Circuit Complexity
Any function can be described as a circuit with operations modulo 2. If the circuit only contains additions, then the function is linear. Nonlinearity, which is fundamental to cryptographic applications, can only be achieved by the use of multiplications. The standard description of the AES S-Box, which is the nonlinearity component for AES, is that it does inversion in the field of 256 elements. The field's standard measure of nonlinearity of a function F is the Hamming distance of the spectrum of F to the closest linear spectrum. A different measure of nonlinearity is simply the number of multiplications necessary and sufficient to compute the function. This measure is called "multiplicative complexity". Minimizing the number of multiplications as a first step in Boolean circuit optimization is a powerful tool. Research has led to a vast reduction in the number of gates and/or the depth of many circuits used in cryptography. These include a circuit of depth 16 and size 128 for the AES S-Box, as well as reduced size/depth circuits for high-speed cryptography in characteristic 2. Additionally, circuits with a small number of multiplications can be used to significantly improve the communication complexity of secure multiparty computations, as well as the size of non-interactive zero-knowledge proofs of knowledge.
Contact:
Dr. Rene Peralta
(301) 975-8702
rene.peralta@nist.gov