NIST Logo and ITL Banner Link to the NIST Homepage Link to the ITL Homepage Link to the NIST Homepage
Search CSRC:

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 was published in the NIST Journal of Research (http://dx.doi.org/10.6028/jres.120.002). 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

Back to Top of Page


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 are difficult or intractable for conventional computers. If large-scale quantum computers are ever built, they will be able to break the existing infrastructure of public-key cryptography. The focus of the Post Quantum Cryptography project is to identify candidate quantum-resistant systems that are 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.

In FY 2014, CSD researchers internally presented 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. The project members also created evaluation criteria to compare proposed post quantum cryptosystems with the end goal of standardization.

CSD staff also engaged the international cryptographic community with presentations and publications. Presentations were made at the 2014 Conference on Theory of Quantum Computation, Communication, and Cryptography, CRYPTO 2014, and PQCrypto 2014 Conference. Invited talks included QCrypt 2014, and at PQCrypto 2014 Conference. A CSD staff member gave a course on quantum algorithms. CSD staff helped organize the joint NIST-University of Maryland Workshop on Quantum Information and Computer Science. CSD also contributed to the European Telecommunications Standards Institute white-paper on quantum-safe cryptography. The CSD also hosted two leading experts in the field, Dr. Jintai Ding and Dr. Vadim Lyubashevsky, for extended visits.

In FY 2015, the CSD 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, CSD will be prepared for possible standardization efforts in this area. The CSD held a workshop on cybersecurity in a post-quantum world in April of 2015. The workshop was attended by approximately 140 participants from all around the world. Presentations given included new proposals for quantum-safe cryptosystems, discussions on how to standardize hash-based signatures and key management issues, as well as new ideas on cryptanalysis of the many post-quantum systems.

Contacts:

Dr. Dustin Moody
(301) 975-8136
dustin.moody@nist.gov
Dr. Lily Chen
(301) 975-6974
lily.chen@nist.gov
Dr. Yi-Kai Liu
(301) 975-6499
yi-kai.liu@nist.gov
 

Back to Top of Page


Privacy Enhancing Cryptography Project

The privacy-enhancing cryptography project seeks to promote the use of communication protocols that do not reveal unneeded private information of the communicating parties. There are many technical challenges in doing this, as it is typically hard to separate private data from general data (e.g. to convert a third-party-signed date-of-birth certificate into a certificate indicating that a person is of voting age). Zero-knowledge (ZK) proof techniques and their variants can be used to accomplish this for a large class of assertions. These techniques allow one party to prove to another party that a given statement is true, without conveying any additional information apart from the fact that the statement is indeed true. However, even though many such ZK protocols are practical, adoption by industry is slow. CSD’s CTG is also following the progress of emerging technologies, such as fully homomorphic encryption (FHE). FHE could potentially solve a large class of problems by allowing computation on encrypted data without decryption. CTG has also shown that the NIST Randomness Beacon (discussed below) can be used as a primitive in secure multi-party computation, such as sealed-bid online auctions, in which losing bids are never opened.

Team members continue to work in collaboration with the National Strategy for Trusted Identities in Cyberspace (NSTIC) program and the Federal Cloud Credential Exchange (FCCX) project. In this context, CTG has served as evaluators and in technical support roles. Information about NSTIC and FCCX is available at http://www.nist.gov/nstic/.

Current communication security standards are primarily designed for two-party communication. CTG believes that future protocols, such as those for identification, commercial transactions, and social media, will necessitate standards for three-party communications (e.g., two parties involved in a commercial transaction and a third party that serves as an enabler of some aspects of the transaction). This is particularly important if standards are to provide privacy protection. CTG has developed some basic protocols for this purpose. One such protocol allows for privacy-preserving identification with the aid of a mediator. In this protocol, the issuer of an assertion, such as “John Smith is an employee of the Department of Commerce,” does not need to know who the consumer of the assertion is, yet it can encrypt the assertion with a key only known to that consumer (i.e. the mediator cannot see the unencrypted assertion).

Contact:
Dr. Rene Peralta
(301) 975-8702
peralta@nist.gov

Back to Top of Page


Cryptography for Constrained Environments

There are several emerging areas in which highly constrained devices are interconnected, typically communicating wirelessly with one another, and working in concert to accomplish some task. Examples of these areas include: sensor networks, healthcare, distributed control systems, the Internet of Things, cyber physical systems, and the smart grid. Security and privacy can be very important in all of these areas. Because the majority of current cryptographic algorithms were designed for desktop/server environments, many of these algorithms do not fit into the constrained resources. If current algorithms can be made to fit into the limited resources of constrained environments, their performance is typically not acceptable.

CTG is studying the use of the NIST-approved symmetric-key algorithms in constrained environments. CTG has developed microcontroller implementations of the Advanced Encryption Standard (AES) to provide both confidentiality and the AES-based message authentication code, Cipher-based Message Authentication Code (CMAC), for authentication. Additionally, CTG has implemented the 256-bit version of the Secure Hash Algorithm (SHA-256) to provide a Hash-based Message Authentication Code (HMAC) for authentication. SHA-3, as specified in Draft FIPS 202, SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions, and a variant of KECCAK using an 800-bit permutation has also been implemented. CTG has demonstrated that SHA-3 allows a more efficient construction for computing Message authentication codes (MACs) than the HMAC construction, which is required when using SHA-256. CTG has also investigated other, non-NIST-approved algorithms for constrained environments.

CTG has also begun to examine applications in constrained environments to determine whether NIST should develop a lightweight encryption standard. CTG has talked with industry experts to understand challenges, limitations, and work from other standardization bodies in this area. Also, CTG has had internal discussions on additional considerations for a lightweight standard, as restrictions on its use would be necessary in order to prevent the adoption of a lightweight cipher where the strong protection of AES is required.

In July 2015, NIST will organize the Lightweight Crypto Workshop to discuss issues related to the security and resource requirements of applications in constrained environments, and potential future standardization of lightweight primitives.

Contacts:

Mr. Lawrence Bassham
(301) 975-3292
lawrence.bassham@nist.gov
Dr. Kerry McKay
(301) 975-4969
kerry.mckay@nist.gov
Dr. Meltem Sönmez Turan
(301) 975-4391
meltem.turan@nist.gov
 

Back to Top of Page


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

Back to Top of Page