Agreements
FAPESP and Intel Call for Proposals - 2015
FAPESP AND INTEL CALL FOR PROPOSALS (CFP)
INTRODUCTION
FAPESP and Intel invite interested researchers from public or private higher education or research institutions in the State of São Paulo to submit research proposals for funding under the cooperation agreement between FAPESP and Intel, and under the terms and conditions hereinafter set forth.
SUBJECT
Academic research on hardware implementation aspects of post-quantum cryptography. Proposed investigations, while hardware-focused in the issues they explore, may leverage software for rapid development and maximum flexibility in constructing prototypes and performance studies.
OVERVIEW
FAPESP and Intel invite proposals from researchers in the State of São Paulo, Brazil on hardware implementation aspects of post-quantum cryptography. With the rapid development of quantum computing technology comes the potential for polynomial-time algorithms for solving the ostensibly hard mathematical problems underlying modern public-key cryptography (integer factorization, discrete logarithm, elliptic curve discrete logarithm). Post-quantum cryptography explores alternative public-key algorithms that are believed to be resistant to quantum computer attacks utilizing Shor’s algorithm. While research in post-quantum cryptography algorithms has been ongoing, more work is needed to understand hardware implementation aspects of such new approaches as hash-based cryptography, code-based cryptography, lattice-based cryptography, and multivariate cryptography. This CFP requests proposals for research leading to a better comparative understanding of post-quantum cryptography approaches and new optimizations techniques based on metrics like implementation complexity, performance, energy requirements, code size, data structure size, storage requirements, and vulnerability to side channel attack. Proposed investigations, while hardware-focused in the issues they explore, may leverage software for rapid development and maximum flexibility in constructing prototypes and performance studies.
BACKGROUND
Modern public-key (asymmetric) cryptography is based on established mathematical problems with no efficient solution known, or whose solution is widely regarded to be computationally infeasible. That is, while generating public and private key pairs is not difficult, no efficient methods are known for deriving a private key from its public key. Some well-known mathematical problems (one-way functions) include integer factorization in which an attacker must decompose a large composite integer into the product of smaller prime integers (the basis of RSA), the discrete logarithm problem in which an attacker must find the logarithm of a large number, and the elliptic curve discrete logarithm in which an attacker must find the logarithm of a random elliptic curve with respect to its known base point.
While no known algorithms exist for solving cryptography’s underlying mathematical problems in polynomial time on conventional computers, mathematician Peter Shor in 1994 discovered an algorithm that could solve the integer factorization problem in polynomial time on a quantum computer.1 Quantum computers are an alternative to conventional digital computers built with transistors. While transistors employ binary digits, or bits, to encode state in the form of a 1 or 0, quantum computers employ quantum bits, or qubits, and can encode multiple states. In fact, a quantum computer with n qubits can support up to 2n different states simultaneously. Quantum entanglement among groups of particles is one approach currently being explored to implement qubits based on quantum mechanical phenomena.
Shor’s algorithm leverages quantum circuits for its period-finding subroutine. A superposition of states is created using a quantum Fourier transform. Then, modular exponentiation using repeated squaring is implemented as a quantum transform. A quantum Fourier transform is used to return the correct answer with high probability. The process may loosely be seen as a quantum phase estimation algorithm which approximates the eigenphase of an eigenvector of a unitary gate in polynomial time. A similar subroutine can be applied to solve the discrete logarithm problem. The quantum computing notion of superposition of states is what allows the computation of all points of a function simultaneously. A new complexity class called “BQP” has been created to designate problems that can be solved in “bounded error quantum polynomial time”.
Post-quantum cryptography explores algorithms based on hard mathematical problems that are not reducible to those problems that can be solved by Shor’s algorithm in polynomial time. At this time, there are at least four well-recognized families of algorithms:
-
Hash-based Cryptography. Addresses the problem of constructing digital signatures using one-way hash functions. Merkle Hash Trees have been shown to be as secure as the underlying cryptographically secure hash function on which they are based. Hash-based cryptography provides an alternative to digital signatures based on RSA and DSA.
-
Code-based Cryptography. Provides asymmetric encryption based on error-correcting codes. The best known is McEliece which, in original form, uses binary Goppa codes over finite fields. McEliece and other schemes rely on the underlying hardness of decoding a linear code (the Syndrome Decoding Problem) which is known to be NP-hard.
-
Lattice-based Cryptography. Provides asymmetric encryption and signature schemes based on the mathematical properties of lattices, sets of points in n-dimensional Euclidean space with strong periodicity and with a large number of bases represented by a linear combination of vectors. Encryption schemes include Ring-LWE, GGH, and NTRUEncrypt, and signature schemes include Ring-LWE, GGH, and NTRUSign. The underlying hardness of lattice-based cryptography leverages such problems as the Shortest Vector Problem and the Closest Vector Problem which are NP-hard.
-
Multivariate Cryptography. Addresses the problem of constructing digital signatures using multivariate polynomials over finite fields. Rainbow (Unbalanced Oil and Vinegar) is based on the NP-hard problem of solving a system of minimal quadratic equations.
While a great deal of academic research has been done over the last decade on post-quantum cryptography algorithms, including the underlying mathematics and accompanying theoretical analysis, there is a strong need for better understanding the implications of such algorithms for hardware implementation.
At a high level, research should help to understand in a comparative manner the hardware implementation pros and cons of various post-quantum cryptography algorithms for:
-
Public key encryption,
-
Signature schemes, and
-
Key exchange schemes with forward secrecy.
Research on a particular algorithm should address both comparisons with existing alternatives and variants within the post-quantum cryptography space, and comparisons with conventional (non-post-quantum) cryptography algorithms which provide well-understood points of reference. Researchers are also invited to consider new approaches and optimizations that can increase the efficiency of such implementations wherever possible.
While research is expected to explore the hardware implications of post-quantum cryptography, it is understood that prototypes and empirical studies can use software for rapid development and maximum flexibility. That is, while research is expected to be hardware-focused in the issues it explores, prototypes are not necessarily expected to leverage RTL-based designs or to make extensive use of FPGAs. (Such prototypes can be useful and are a plus if researchers already have such expertise, but it is not required.)
Metrics of interest for understanding hardware implementation aspects of various post-quantum cryptographic solutions include:
-
Implementation complexity. What is the required complexity of an algorithm implementation, and how does that compare to various alternatives? What optimizations are possible that could reduce this complexity?
-
Performance. What kind of performance can be expected from an algorithm implementation, and how might that performance be improved through potential optimization approaches? (e.g., time for key generation, time for signature generation, time for verification)
-
Energy requirements. How much energy is required for an algorithm implementation on a specific hardware platform? What components of the algorithm require the most energy and could modifications to the algorithm or implementation reduce requirements?
-
Code size. How much memory is required for a given algorithm implementation? How might an implementation reduce these requirements?
-
Data structure size. How much state must be maintained in memory (e.g., intermediate results) for a given implementation? How might an implementation reduce the requirement?
-
Storage requirements. How much storage is required for the cryptographic solution? How does this compare to various alternatives? What optimizations are possible?
-
Side channel vulnerabilities and resistance. What side channel information vulnerabilities are associated with an algorithm implementation? What techniques could be applied to address the problem of side channel attack?
We note that the properties of a particular algorithm may become more or less important with different usage scenarios. Some usages to consider in this call for proposals include:
-
Secure boot which requires robust image verification during the power-on sequence. Implementation resource requirements and verification time are critical.
-
Secure firmware and software update which also require robust image verification. Implementation resource requirements and verification time are once again critical.
-
Attestation, including signatures involving secret keys in hardware. Critical issues include protection against side channel attack, time to compute signatures, and public key generation time.
-
Secure communication establishment (e.g., TLS, IKE), including authenticated key exchange. Critical issues include protecting secret keys from side channel attack and the time criticality of all computations, including public key generation.
Nearly all cryptographic algorithms include configuration parameters such as key size, number of iterations, and algorithm-specific parameters that define security levels. Researchers should consider a range of possible security levels in their work, and strive to comprehend not just what is practical for today’s computing systems (e.g., 128-bit security), but what will be supported by hardware platforms of the future. In particular, attackers in a post-quantum computing world will have at their disposal quantum computers, and security levels will need to comprehend this new capability. To illustrate using symmetric cryptography, symmetric algorithms may require 256 bit keys to achieve 128 bit security within a post quantum world. Another motivation for considering forward-looking configuration parameters is that many devices (e.g., IoT) are expected to be deployed for long periods of time (e.g., decades). Such long-lived usages means that cryptographic solutions must anticipate the attack climate of future compute eras.
Much of the existing research literature on post-quantum cryptography (e.g., lattice-based cryptography) focuses on asymptotic security analyses and doesn’t provide practical parameter recommendations. In contrast, we ask that researchers participating in this call develop such recommendations as a part of their work, along with accompanying analysis and empirical studies that shed light on why particular selections are desirable.
Researchers are expected to make use of Intel platforms for their work, but there are no constraints beyond this broad guideline in order to allow flexibility of approach, device context, and usage scenario. For thoroughness, empirical analysis may also consider other relevant platforms as a point of comparison, and since the broader ecosystem will be interested in a range of platforms.
Finally, work examining energy requirements should make use of empirical-based measurement methodologies (e.g., power meters, instrumented platforms) rather than speculative analytic models.
1Peter W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, Proceedings of the 35th Annual Symposium on Foundations of Computer Science, November 1994.
RESEARCH AREAS
The focus of this research call, broadly stated, is on understanding hardware implementation aspects of today’s established post-quantum cryptography algorithms. In the process, researchers are encouraged to consider new approaches and optimizations that can increase the efficiency of such implementations wherever possible.
Research proposals in response to this challenge are expected to address one or more of the following three research vectors: RV1: Implementation Efficiency, RV2: Side Channel Attack, and RV3: Cryptography Applications. Note that these vectors are not intended to be mutually exclusive. Researchers are free to develop proposals that address any one vector, a combination of two vectors, or even all three vectors simultaneously. In addition, proposals that suggest a compelling topic lying outside these research vectors yet in the spirit of program objectives and goals are welcome. For example, significant cryptanalysis advancements besides SCA are of interest.
RV1: Implementation Efficiency
The goal of this research vector is to examine how one or more post-quantum cryptography algorithms rank in terms of hardware implementation efficiency. Focus may be on implementation complexity, performance, energy requirements, code size, data structure size, storage requirements, and other key metrics. Researchers are asked to identify key features and issues, to understand the variants of an approach, and compare the approach against other competing approaches, both post-quantum and conventional. New implementation approaches and optimizations that address problems and challenges are welcome.
RV2: Side Channel Attack
The goal of this research vector is to examine the potential for side channel information vulnerabilities associated with one or more post-quantum cryptography algorithms. Side channel information leaks may include (but are not limited to) variations in execution time, power consumption, data communication and memory access patterns, hardware execution context, or system fault behavior. Researchers are asked to identify key information leak sensitivities associated with the algorithm and its variants, and to rank the severity of the vulnerability with respect to other competing approaches, both post-quantum and conventional. New approaches to attack mitigation are welcome. Investigation of new types of side channel attacks that are uniquely enabled by quantum technology is also possible.
RV3: Cryptography Applications
The goal of this research vector is to examine hardware-related implementation issues and considerations for more specific usage scenarios. A number of important usage scenarios were listed in the previous section: secure boot, secure firmware and software update, attestation, and secure communication establishment (e.g., TLS, IKE), including authenticated key exchange. Other applications are also possible. Researchers may, furthermore, choose to consider specific computing device contexts for their work; for example, various IoT domain verticals (wearables, transportation, smart cities, retail, health, and so on) are currently of great interest to Intel and the broader technology ecosystem. Researchers are welcome to draw from device usage scenarios with significance to Brazil -- for example, SoC devices associated with DTV media services, transportation/cargo tracking, building energy management systems, environment monitoring, and so on.
Regardless of the research vector(s) addressed, research should be well-grounded in real-world case studies and hardware platforms, yet possess a level of generality that makes research outcomes applicable to a broad spectrum of devices. This broader significance is especially important in post-quantum cryptography since our theoretical understanding of algorithm strength is often limited.
GOALS OF RESEARCH
FAPESP and Intel seek projects that clearly address the broader objectives of research:
-
Understanding the hardware implementation issues surrounding key post-quantum cryptography algorithms that have emerged in recent years, and
-
Proposing new approaches and optimizations that can increase the efficiency of such implementations wherever possible.
In support of these broader objectives, research should address the following specific goals:
Quantified Comparisons:
Goal 1: Researchers provide quantified comparisons between algorithm variants and competing approaches, both post-quantum and conventional. Metrics can include (but are not limited to):
-
Complexity (e.g., number of operations)
-
Performance (e.g. ops/sec, workload completion time)
-
Energy requirements (e.g., performance/kJ or W)
-
Code size (e.g., KB)
-
Data structure size (e.g., KB)
-
Storage requirements (e.g., KB)
-
Application-specific metrics
Configuration Parameters:
Goal 2a: Researchers consider a range of possible security levels to address current and future computing capabilities. Key sizes should be chosen to be survivable in a post-quantum world.
-
g., key size
Goal 2b: Researchers develop specific algorithmic parameter recommendations and demonstrate their efficacy using empirical arguments.
-
g., hash length, algorithm-specific parameters
New Optimizations:
Goal 3: Researchers demonstrate greater than 50% improvement over state-of-the-art for a given algorithm using one or more metrics defined in Goal 1.
Side Channel Attack:
Goal 4a: Researchers demonstrate the side channel attack feasibility and quantify its requirements and complexity.
Goal 4b: Researchers demonstrate the efficacy of a specific countermeasure and quantify the requirements and complexity.
Cryptanalysis:
Goal 5: As appropriate, researchers provide cryptanalytic arguments to demonstrate the security robustness or fragility of post-quantum schemes under study.
ELIGIBILITY
In order to qualify for this Request for Proposals in the FAPESP-INTEL Agreement, the proponent should satisfy in the following prerequisites:
a) The conditions and restrictions of the FAPESP Program for Cooperative Research for Technological Innovation (PITE) described at www.fapesp.br/pite are applied here, excluding those restrictions and conditions explicitly excepted in this CFP.
b) The proposals may be submitted by researchers from Higher Education or Research Institutions in the State of São Paulo.
c) Proposals that are incomplete, inaccurate, or are otherwise not responsive to the terms and conditions of this CFP will, at the sole discretion of the Joint Steering Committee for the FAPESP-INTEL cooperation, be excluded from consideration.
PROGRAM SCOPE AND FUNDING
FAPESP and Intel contemplate funding a cluster of 2-year grant proposals. Each would be renewable annually contingent upon satisfactory progress and continued promise in research direction.
The total amount available for this CFP is US$ 200,000. FAPESP and Intel reserve the right to propose lower funding levels for projects.
The appropriateness of the requested funding in relation to the proposal goals and qualification of the proposing team is a primary review consideration.
PROPOSAL FORMAT
The proposal should clearly state the problems and opportunities to be addressed and the potential impact if the research is successful. It should specifically address the quantifiable goals listed in this request for proposals and provide milestones reflecting the progress towards them.
Please note that FAPESP and Intel are unable to receive proposals that are under an obligation of confidentiality. All proposals submitted should therefore include only public information.
Each proposal must contain the following items (to see the complete checklist of requested documents, please access the submission form, item 16, page 7).
FAPESP-INTEL proposal submission form, in Portuguese (form available at https://fapesp.br./9724).
FAPESP Summary of CV, in English, for the PI and each Associated Investigator, including those from Intel, when applicable. Instructions for elaborating the Summary of the Principal Investigator CV are available at www.fapesp.br/en/6351.
Research team: Listing of all contributing researchers, in English, including Host Institution, Entity. For each one, his or her role in the research project must be defined succinctly, as well as the weekly workload. Each participant must sign his or her agreement to participate in the project. Agreement can be downloaded at https://fapesp.br./9724.
Proposals should be submitted in English and be 12-14 pages in length (not including citations or cost volume), using font Arial size 10 and double spacing. Section 7 is not counted under this page limitation. Please address the sections listed below, from 1 to 6 under separate numbered headings. Each response should comprise the following sections:
1. Cover page {1 page}. Title of proposal, name(s) of author(s), contact information, name of university, funds requested, the amount of cost share (if any)
2. Executive summary {1 page}. Define the problem/challenge that this research will address, the effort’s technical objectives/success criteria, and the basic proposed approach.
3. Relevance and impact claims {1-2 pages}. This section is the centerpiece of the proposal. It should succinctly describe the uniqueness and non-incremental benefits of the proposed objective and approach relative to the state-of-the-art and current approaches.
4. Detailed technical rationale, approach, and constructive plan {2-4 pages}. Details of proposed research. Proposals should address key issues along one or more of the above research vectors (or another topic still addressing program objectives and goals), and the rationale should include a basis of confidence for meeting the program metrics.
5. Statement of work, schedule, milestones, success criteria and deliverables {2 pages}. Outline the scope of the effort including tasks to be performed, schedule, milestones, deliverables, and success criteria. It is understood that this is an exploratory research effort and schedules/deliverables reflect intentions rather than a firm commitment.
6. Proposal team {1-2 pages}. Summarize the members of the program team, their qualifications, and their level of participation in the project.
7. Other support {1 page}. List other contributions by the Host Institution to this project (cash, goods, or services), if any, but not including items such as the use of university facilities otherwise provided on an ongoing basis. Note that authors of selected proposals will be required to present an original letter on university letterhead signed by the director of the Host Institution certifying the commitment of any additional support.
8. Fellowships {unlimited}: The proposed budget may include costs for Scientific Initiation, Masters or Post-Doctoral fellowships. The ending dates for each fellowship must happen at or before the ending date of the project. Fellowships can be covered with funds from Intel depending on the analysis of the proposal and the availability of resources, to be verified at the time of selection of proposals. For each requested fellowship a work plan with up to two pages must be submitted together with the research proposal. Work plans must include: Title for the Fellowship research project, Summary, and Description of the plan. It is not necessary to nominate the holder of the fellowship. If the grant is approved, the Principal Investigator will be in charge of organizing a public selection process to select the appointees for the fellowships through a merit review process.
9. Citations {unlimited}.
10. Requested budget description {unlimited}. Proposals must include separate budget descriptions for the items requested to FAPESP and to Intel. It is desirable to keep the fraction of the total amount requested for each of the parties at around 50%. Such a balance is desirable but not mandatory, and may deviate from 50% due to specific circumstances to be justified.
a) The budget items that may be requested to FAPESP are those traditionally supported by the Foundation and described in www.fapesp.br/1656.
b) The budget items that can be covered with funds from Intel should be limited to:
i. Resources invested in capital goods or equipment associated with the project if they are donated to the Higher Education and Research Institutions in the State of Sao Paulo;
ii. Resources invested in Scientific Initiation, Masters or Post-Doctoral fellowships with values at least equal to the grants from FAPESP for these fellowships;
iii. Resources invested in consumables and services of third parties when directly associated with the project;
iv. Resources invested in infrastructure associated with the project;
v. Resources for the temporary hiring, during the period of the project, of researchers and technical support staff dedicated to the project in the Host Institution.
vi. Resources for salary complementation of researchers participating in the project employed by the Host Institution;
vii. Special cases documented by a detailed justification within the proposal will be analyzed in each case by the Joint Steering Committee.
c) The budget request must be presented using specific spreadsheets (available at https://fapesp.br./9724) which include:
i. Consolidated Budget Request, classified by types of expense and font sources (FAPESP, Intel and other sources);
ii. Separate Budget Request spreadsheets for FAPESP and Intel, by types of expense, following FAPESP’s standards;
iii. Spreadsheets for financial and physical schedule (FAPESP and Intel).
IMPORTANT: It is necessary to attach three quotes for each capital and equipment expense requested (national or imported). If it is not possible to obtain the 3 quotes requested, please attach a clarification letter.
PROPOSAL SUBMISSION
Proposals should be submitted in a paper copy accompanied by a digital version with a unique PDF file containing the complete proposal.
Proposals that are incomplete, inaccurate, that request funds in excess of the maximum award available, or are otherwise not responsive to the terms and conditions of this CFP will be excluded from consideration.
The envelope containing the proposal should be addressed to:
PROPOSTA DE PESQUISA CHAMADA FAPESP-INTEL 2015
FAPESP – Fundação de Amparo à Pesquisa do Estado de São Paulo
Rua Pio XI, 1500 - Alto da Lapa
CEP 05468-901 - São Paulo - SP
Proposals will not be accepted by any other means.
Submitted proposals under this CFP will not be returned to the proponents. For record-keeping and administrative purposes, the copy will be archived by FAPESP.
No proposals will be accepted after the closing date for submission, nor will any addendum or explanation be accepted, unless those explicitly and formally requested by FAPESP or Intel.
EVALUATION CRITERIA
All received proposals adherent to the terms of this Request for Proposals will be analyzed.
The selection process is based on merit review and comparative analysis. To this end FAPESP will use reviewers' reports and the Foundation’s Area and Supervising Panels.
The criteria used will be that applied to the selection of proposals in the FAPESP Program for Cooperative Research for Technological Innovation (PITE), with the addition of the analysis by the Joint Steering Committee for the FAPESP-INTEL cooperation.
Researchers participating in any submitted proposal will not take part in the analysis and selection process.
The evaluation criteria for this solicitation are as follows:
a) Adherence to the terms of this CFP;
b) Novelty and Ambition of the proposed academic research project, as it relates to the goals of this CFP;
c) Qualification of the research project, in the specification of clear goals, milestones, and success criteria. Clarity of challenges to be overcome and the scientific, technical and material means and ways for this, in relation to the state-of-the-art in the Field, including interface definitions, testing methodology, and plans for experimental deployment;
d) Adequate existing institutional infrastructure, offered by the Hosting Institution;
e) Qualifications of Principal Investigator and his team, including previous history of work in areas relevant to this CFP, successful completion of previously funded projects, teaching awards, and publications, all of those items being demonstrated in the Curricular Summary of the CV of the Principal Investigators;
f) Ability to complete the project, including the adequacy of available resources, institutional support, reasonableness of timelines, and number and qualifications of identified contributors. Encompasses the efficient use of requested resources and funding, and represent realistic results for the value invested;
g) Potential for wide dissemination and use of intellectual property created, including specific plans for publications, conference presentations, web sites, as well as plans to distribute content in multiple formats or languages;
h) Formation of new researchers and professionals, as a result of the execution of the Project;
i) Potential for technological innovation. The extent to which the proposal’s problem formulation and key approaches are innovative, important, and relevant to the problem at hand. Novelty and ambition of the proposed academic research project, as it relates to the goals of this CFP. Potential for technological innovation as measured by comparisons with existing and competing technologies.
j) Potential contribution and relevance to Intel. The estimated degree to which proposals have a substantial potential for influencing the direction of Intel’s long range technology plans.
SCHEDULE
|
Event |
Date |
|
Launching of the CFP at FAPESP Web site |
02/09/2015 |
|
Last date for receiving proposals |
13/11/2015 |
|
Publication of results of the analysis and selection process |
From 11/03/2016 |
ANNOUNCEMENT OF RESULTS
The results of the selection process will be announced in FAPESP’s Web Site at www.fapesp.br and by direct communication to the proponents.
CONTRACTING OF THE SELECTED PROPOSALS
For each research proposal selected, the relationship between FAPESP, Intel and the Principal Investigator Institution will be determined by an agreement defining:
a. Schedule of disbursements and financial reporting on the amounts disbursed;
b. Definition and timing of expected results at each stage of the project;
c. Intellectual property, confidentiality and possible exploitation of project results;
d. Term;
e. Legal venue.
CANCELLATION OF THE AWARD
The award may be cancelled by Intel and FAPESP by mutual agreement, in the event of justifiable cause, on the basis of evaluation by the Scientific Directors of FAPESP and Intel. Cancellation does not preclude other measures that might be deemed necessary.
GRANTS, PROGRESS ANALYSIS AND EVALUATION
If the application is approved, a Grant Contract will be made, which will be signed by the Principal Investigator and the Host Institution´s representative.
The results will be evaluated by progress reports and financial reports that should be submitted on the dates established in the Grant Contract.
AGREEMENT TO TERMS AND CONDITIONS
By submitting an application under this CFP, applicants confirm that they have read, understood and agreed to the terms and conditions of the CFP and the conditions attached to any successful awards.
INFORMATION AND CLARIFICATION
All questions related to this CFP must be directed to: chamada_intel@fapesp.br.
Please, put “CFP FAPESP-INTEL” in the subject line of your e-mail to ensure a prompt and proper response.