NIST IR 8214A 日本語訳
英語タイトル : NIST Roadmap Toward Criteria for Threshold Schemes for Cryptographic Primitives日本語タイトル : 暗号プリミティブのしきい値方式の基準策定に向けた NIST ロードマップ
公開日 : 2020-07-07
原文URL : https://csrc.nist.gov/pubs/ir/8214/a/final
翻訳編集 : 自動生成(有志による非公式の日本語訳), 原文取得日 : 2026-10-31, 訳文 : 361 / 361 ブロック
[要約] NIST IR 8214A は、暗号プリミティブのしきい値方式の標準化に向けた基準を策定するための準備として、NIST が整理した枠組みを示す報告書です。NIST IR 8214 で特定された多様なしきい値方式を、単一デバイスとマルチパーティという二つの主要なトラックに沿って整理しています。標準化する項目の選定では、高度なセキュリティ特性、パラメーターの設定可能性、試験と検証、モジュール性と合成可能性、仕様の詳細度といった特徴を考慮する必要があるとしています。この構成は、利害関係者のコミュニティとの関与と、標準化の基準の策定、その後の貢献の募集に向けた準備にあたるとされています。
NISTIR 8214A
NISTIR 8214A
NIST Roadmap Toward Criteria for Threshold Schemes for Cryptographic Primitives
暗号プリミティブのしきい値方式の基準策定に向けた NIST ロードマップ
Luís T. A. N. Brandão Michael Davidson Apostol Vassilev
Luís T. A. N. Brandão Michael Davidson Apostol Vassilev
This publication is available free of charge from: https://doi.org/10.6028/NIST.IR.8214A
本刊行物は次のサイトから無料で入手できます: https://doi.org/10.6028/NIST.IR.8214A
NISTIR 8214A
NISTIR 8214A
NIST Roadmap Toward Criteria for Threshold Schemes for Cryptographic Primitives
暗号プリミティブのしきい値方式の基準策定に向けた NIST ロードマップ
Luís T. A. N. Brandão* Michael Davidson Apostol Vassilev Computer Security Division Information Technology Laboratory
Luís T. A. N. Brandão* Michael Davidson Apostol Vassilev Computer Security Division Information Technology Laboratory
* Contractor at NIST, employed by Strativia, since February 2020. Most work for this publication was done previously, as a non-contractor.
* 2020 年 2 月から Strativia に雇用された NIST の契約職員。本刊行物の作業の大部分は、それ以前に契約職員ではない立場で行われました。
This publication is available free of charge from: https://doi.org/10.6028/NIST.IR.8214A
本刊行物は次のサイトから無料で入手できます: https://doi.org/10.6028/NIST.IR.8214A
July 2020
2020 年 7 月
U.S. Department of Commerce Wilbur L. Ross, Jr., Secretary
米国商務省 Wilbur L. Ross, Jr., 長官
National Institute of Standards and Technology
National Institute of Standards and Technology
Walter G. Copan, NIST Director and Under Secretary of Commerce for Standards and Technology
Walter G. Copan、NIST所長兼商務省標準技術担当次官
National Institute of Standards and Technology Internal or Interagency Report 8214A 39 pages (July 2020)
National Institute of Standards and Technology Internal or Interagency Report 8214A 39 ページ(2020 年 7 月)
This publication is available free of charge from: https://doi.org/10.6028/NIST.IR.8214A
本刊行物は次のサイトから無料で入手できます: https://doi.org/10.6028/NIST.IR.8214A
Certain commercial entities, equipment, or materials may be identified in this document in order to describe an experimental procedure or concept adequately. Such identification is not intended to imply recommendation or endorsement by NIST, nor is it intended to imply that the entities, materials, or equipment are necessarily the best available for the purpose.
本書では、実験の手順や概念を適切に説明するために、特定の営利企業、設備、または資材を明示している場合があります。こうした明示は、NIST による推奨や推薦を意味するものではなく、それらの企業、資材、または設備が目的に対して必ずしも最良であることを意味するものでもありません。
There may be references in this publication to other publications currently under development by NIST in accordance with its assigned statutory responsibilities. The information in this publication, including concepts and methodologies, may be used by federal agencies even before the completion of such companion publications. Thus, until each publication is completed, current requirements, guidelines, and procedures, where they exist, remain operative. For planning and transition purposes, federal agencies may wish to closely follow the development of these new publications by NIST.
本刊行物では、NIST が法令で定められた責務に従って現在策定中の他の刊行物に言及している場合があります。概念や方法論を含む本刊行物の情報は、そうした関連刊行物の完成前であっても、連邦機関が利用してもよいです。したがって、各刊行物が完成するまでは、現行の要件、ガイドライン、および手順が存在する場合には、それらが引き続き有効です。計画および移行のため、連邦機関は、NIST によるこれらの新しい刊行物の策定状況を注意深く追うことを検討してもよいです。
Organizations are encouraged to review all draft publications during public comment periods and provide feedback to NIST. Many NIST cybersecurity publications, other than the ones noted above, are available at https://csrc.nist.gov/publications.
各組織は、公開意見募集期間中にすべてのドラフト刊行物を確認し、NIST にフィードバックを提供することが推奨されます。上記以外の NIST のサイバーセキュリティ関連刊行物の多くは、https://csrc.nist.gov/publications で入手できます。
Comments on this publication may be submitted to:
本刊行物に対する意見は、次の宛先へ提出できます。
National Institute of Standards and Technology Attn: Computer Security Division, Information Technology Laboratory 100 Bureau Drive (Mail Stop 8930) Gaithersburg, MD 20899-8930 Email: nistir-8214A-comments@nist.gov
National Institute of Standards and Technology Attn: Computer Security Division, Information Technology Laboratory 100 Bureau Drive (Mail Stop 8930) Gaithersburg, MD 20899-8930 Email: nistir-8214A-comments@nist.gov
All comments are subject to release under the Freedom of Information Act (FOIA).
すべての意見は、情報自由法(FOIA)に基づいて公開される場合があります。
Reports on Computer Systems Technology
コンピュータシステム技術に関する報告書
The Information Technology Laboratory (ITL) at the National Institute of Standards and Technology (NIST) promotes the U.S. economy and public welfare by providing technical leadership for the Nation’s measurement and standards infrastructure. ITL develops tests, test methods, reference data, proof of concept implementations, and technical analyses to advance the development and productive use of information technology. ITL’s responsibilities include the development of management, administrative, technical, and physical standards and guidelines for the cost-effective security and privacy of other than national security-related information in federal information systems.
National Institute of Standards and Technology(NIST)の Information Technology Laboratory(ITL)は、国の測定・標準のインフラストラクチャに技術的リーダーシップを提供することにより、米国の経済と公共の福祉の向上に貢献しています。ITL は、情報技術の開発と生産的な利用を進めるため、テスト、テスト手法、参照データ、概念実証の実装、および技術分析を開発しています。ITL の責務には、連邦情報システムにおける、国家安全保障に関連するもの以外の情報について、そのセキュリティとプライバシーを費用対効果よく確保するための、管理上、運用上、技術上、および物理上の標準とガイドラインの策定が含まれます。
Abstract
概要
This document constitutes a preparation toward devising criteria for the standardization of threshold schemes for cryptographic primitives by the National Institute of Standards and Technology (NIST). The large diversity of possible threshold schemes, as identified in the NIST Internal Report (NISTIR) 8214, is structured along two main tracks: single-device and multi-party. Each track covers cryptographic primitives in several possible threshold modes. The potential for real-world applications is taken as an important motivating factor for differentiating the pertinence of each possible threshold scheme. Also, the selection of items for standardization needs to consider diverse features, such as advanced security properties, configurability of parameters, testing and validation, modularity and composability (e.g., of gadgets vs. composites), and specification detail. Overall, the organization put forward serves as a preparation for an upcoming solicitation of feedback useful for considering a variety of threshold schemes, while differentiating standardization paths and timelines that may depend on the levels of technical and standardization challenges. This approach paves the way for an effective engagement with the community of stakeholders and constitutes a preparation for devising criteria for standardization and subsequent calls for contributions. While the terms standards and standardization are used throughout this report to refer to a set of possible final products, this does not imply a Federal Information Processing Standard (FIPS) as one or as the only intended format for NIST products of future threshold schemes for cryptographic primitives.
本書は、National Institute of Standards and Technology(NIST)による暗号プリミティブのしきい値方式の標準化基準を策定するための準備にあたるものです。NIST Internal Report(NISTIR)8214 で特定された多様なしきい値方式は、単一デバイスとマルチパーティという二つの主要なトラックに沿って整理されています。各トラックでは、いくつかの可能なしきい値モードで暗号プリミティブを扱います。個々のしきい値方式の適切さを区別する際には、実世界での応用可能性が重要な動機として考慮されます。また、標準化する項目の選定では、高度なセキュリティ特性、パラメーターの設定可能性、試験と検証、モジュール性と合成可能性(たとえば、ガジェットと複合体のどちらを対象とするか)、仕様の詳細度といった多様な特徴を考慮する必要があります。全体として、本書で示す構成は、多様なしきい値方式の検討に役立つフィードバックを近く募集するための準備となるとともに、技術面および標準化面の課題の水準に応じて異なる標準化の経路とスケジュールを区別するものです。このアプローチは、利害関係者のコミュニティとの効果的な連携への道を開き、標準化基準の策定と、その後の貢献募集に向けた準備となります。本報告書では、標準および標準化という用語を、考えられる最終成果物の集合を指すために使っていますが、これは、暗号プリミティブのしきい値方式に関する将来のNIST成果物の形式として、Federal Information Processing Standard(FIPS)を一つの形式とすることも、唯一の形式とすることも意味しません。
Keywords
キーワード
threshold schemes; cryptographic primitives; threshold cryptography; secure multi-party computation; intrusion tolerance; resistance to side-channel attacks; standards; testing and validation; secure implementations; distributed systems.
しきい値方式、暗号プリミティブ、しきい値暗号、セキュアマルチパーティ計算、侵入耐性、サイドチャネル攻撃への耐性、標準、試験と検証、セキュアな実装、分散システム。
Acknowledgments
謝辞
This document follows the NIST Internal Report 8214 and the NIST Threshold Cryptography Workshop, which benefited from the participation and feedback from numerous individuals, representing various organizations. The authors of this document thank Nicky Mouha and Matthew Watson for participating in discussions at numerous threshold cryptography meetings, Lily Chen and Andrew Regenscheid for additional feedback on the initial draft, and Terry Cohen, Dustin Moody, René Peralta Isabel Wyk and the NIST Editorial Review Board for additional editorial comments. The initial draft of this report was published online on November 8, 2019, for a period of public comments. We are thankful for the valuable feedback provided by external reviewers (in chronological order): Samuel Ranellucci from Unbound Tech; Jakob Pagter from Sepior; Tore Frederiksen from Alexandra Instituttet; Svetla Nikova and Vincent Rijmen from COSIC KU Leuven; Chelsea Komlo from University of Waterloo; Nigel Smart from COSIC KU Leuven; Phillip Hallam-Baker from Venture Cryptography; Ventzi Nikov from NXP Semiconductors; Simon Hoerder and Elke De Mulder from Rambus Inc; Ronald Tse, Wai Kit Wong, Daniel Wyatt, Nickolay Olshevsky and Jeffrey Lau from Ribose Inc.
本書は、NIST Internal Report 8214 と NIST Threshold Cryptography Workshop に続くものであり、これらは、さまざまな組織を代表する多数の人々の参加とフィードバックの恩恵を受けました。本書の著者は、多数のしきい値暗号会合での議論に参加した Nicky Mouha と Matthew Watson、初稿に追加のフィードバックを寄せた Lily Chen と Andrew Regenscheid、追加の編集コメントを寄せた Terry Cohen、Dustin Moody、René Peralta、Isabel Wyk、および NIST Editorial Review Board に感謝します。本報告書の初稿は、2019 年 11 月 8 日にオンラインで公開され、意見募集が行われました。外部査読者(時系列順)から寄せられた貴重なフィードバックに感謝します: Unbound Tech の Samuel Ranellucci、Sepior の Jakob Pagter、Alexandra Instituttet の Tore Frederiksen、COSIC KU Leuven の Svetla Nikova と Vincent Rijmen、University of Waterloo の Chelsea Komlo、COSIC KU Leuven の Nigel Smart、Venture Cryptography の Phillip Hallam-Baker、NXP Semiconductors の Ventzi Nikov、Rambus Inc の Simon Hoerder と Elke De Mulder、Ribose Inc の Ronald Tse、Wai Kit Wong、Daniel Wyatt、Nickolay Olshevsky、Jeffrey Lau。
Patent Disclosure Notice
特許開示に関する通知
NOTICE: The Information Technology Laboratory (ITL) has requested that holders of patent claims whose use may be required for compliance with the guidance or requirements of this publication disclose such patent claims to ITL. However, holders of patents are not obligated to respond to ITL calls for patents and ITL has not undertaken a patent search in order to identify which, if any, patents may apply to this publication.
通知: Information Technology Laboratory(ITL)は、本刊行物のガイダンスまたは要件への準拠にその使用が必要となる可能性のある特許請求項の保有者に対し、そのような特許請求項を ITL に開示するよう求めています。ただし、特許の保有者には、ITL による特許の募集に応じる義務はなく、ITL は、本刊行物に適用される可能性のある特許があるか、あるとすればどれかを特定するための特許調査を行っていません。
As of the date of publication and following call(s) for the identification of patent claims whose use may be required for compliance with the guidance or requirements of this publication, no such patent claims have been identified to ITL.
公表日の時点で、本刊行物のガイダンスまたは要件への準拠にその使用が必要となる可能性のある特許請求項の特定を求める募集を行った後も、そのような特許請求項は ITL に対して特定されていません。
No representation is made or implied by ITL that licenses are not required to avoid patent infringement in the use of this publication.
ITL は、本刊行物の使用にあたって特許侵害を避けるためにライセンスが不要であるとの表明を、明示的にも黙示的にも行っていません。
This disclosure notice is defined in the “ITL Patent Policy — Inclusion of Patents in ITL Publications” at https://www.nist.gov/itl/publications-0/itl-patent-policy-inclusion-patents-itl-publications
この開示に関する通知は、「ITL Patent Policy — Inclusion of Patents in ITL Publications」(https://www.nist.gov/itl/publications-0/itl-patent-policy-inclusion-patents-itl-publications)で定義されています。
Executive Summary
エグゼクティブサマリー
The Computer Security Division (CSD) at the National Institute of Standards and Technology (NIST) promotes the security of implementations and operations of cryptographic primitives, such as signatures and encryption. This security depends not only on the theoretical properties of the primitives, but also on the abilities to withstand attacks on their implementations and to ensure authorized operations. To advance this capability, NIST has initiated the Threshold Cryptography project. This project intends to drive an effort to standardize threshold schemes, which enable distribution of trust placed on human operators, and offer a path to prevent several single-points of failure at the technology level.
National Institute of Standards and Technology(NIST)の Computer Security Division(CSD)は、署名や暗号化などの暗号プリミティブの実装と運用のセキュリティを促進しています。このセキュリティは、プリミティブの理論的な特性だけでなく、その実装に対する攻撃に耐え、認可された運用を確保する能力にも左右されます。この能力を高めるため、NIST は Threshold Cryptography プロジェクトを開始しました。このプロジェクトは、人間の運用者に置かれた信頼を分散させ、技術面で複数の単一障害点を防ぐ道筋を提供する、しきい値方式を標準化する取り組みを推進することを目的としています。
Threshold schemes are composed of multiple components, and assembled in a way that enables enhanced security properties and operational features even when up to \(f\)-out-of-\(n\) of their components are compromised. In such case, \(f\) is called the threshold of compromise. This enables enhanced secrecy of cryptographic keys, integrity of computed values, and/or availability of operations. In a dual perspective, a threshold scheme requires the correct participation of at least \(k\)-out-of-\(n\) components, for an operational goal to be achieved. For example, in a threshold Rivest–Shamir–Adleman (RSA) signing scheme with participation threshold \(k\), the secret key is split (in a secret-shared way) across multiple signatories, such that: any subset of a threshold number \(k\) of honest signatories can produce a signature, without reconstructing the key; any subset of fewer than \(k\) signatories cannot produce a signature, nor find anything about the key.
しきい値方式は複数の構成要素から成り、最大で \(f\)-out-of-\(n\) の構成要素が危殆化されても、強化されたセキュリティ特性と運用機能が得られるように組み立てられています。この場合、\(f\) は危殆化のしきい値と呼ばれます。これにより、暗号鍵の秘匿性、計算値の完全性、および/または運用の可用性が強化されます。別の見方をすると、しきい値方式では、運用上の目標を達成するため、少なくとも \(k\)-out-of-\(n\) の構成要素が正しく参加する必要があります。たとえば、参加しきい値 \(k\) のしきい値 Rivest–Shamir–Adleman(RSA)署名方式では、秘密鍵を秘密分散の方法で複数の署名者に分割します。そのため、しきい値数である \(k\) 人の誠実な署名者の任意の部分集合は鍵を再構成せずに署名を生成でき、\(k\) 人未満の署名者の任意の部分集合は署名を生成できず、鍵に関する情報も得られません。
Threshold schemes can be applied to various cryptographic primitives, and in particular to NIST-approved algorithms. This includes the primitives that are part of asymmetric-key schemes, such as digital signatures (in FIPS 186) and key-establishment based on integer-factorization cryptography (IFC) (in SP 800-56B) or on discrete logarithm cryptography (DLC) (in SP 800-56A), namely elliptic-curve cryptography (ECC) [SP 800-186], and symmetric-key schemes, such as block-cipher operations (in FIPS 197). The primitives of interest encompass key generation, including requirements related to random-bit generation (in SP 800-90 series), and the related algorithms based on secret/private keys, such as signing, decryption within a public-key encryption (PKE) scheme, and enciphering and deciphering.
しきい値方式は、さまざまな暗号プリミティブ、特に NIST が承認したアルゴリズムに適用できます。これには、デジタル署名(FIPS 186)や、整数因数分解暗号(IFC)に基づく鍵確立(SP 800-56B)または離散対数暗号(DLC)に基づく鍵確立(SP 800-56A)、すなわち楕円曲線暗号(ECC)[SP 800-186] などの公開鍵方式の一部であるプリミティブと、ブロック暗号の演算(FIPS 197)などの共通鍵方式が含まれます。対象となるプリミティブには、乱数ビット生成(SP 800-90 シリーズ)に関する要件を含む鍵生成と、共通鍵/秘密鍵に基づく関連アルゴリズム、たとえば署名、公開鍵暗号(PKE)方式における復号、ならびに暗号化と復号が含まれます。
The structure devised in this document serves as a preparation toward the standardization by NIST, of threshold schemes for cryptographic primitives. This phase follows the publication of the NIST Internal Report “Threshold Schemes for Cryptographic Primitives” (NISTIR 8214), which positioned a preparatory framework and several representative questions, and the “NIST Threshold Cryptography Workshop” (NTCW) 2019, which brought together stakeholders to share perspectives from industry, academia and government.
本書で策定した構成は、NIST による暗号プリミティブのしきい値方式の標準化に向けた準備にあたります。この段階は、準備的な枠組みといくつかの代表的な問いを示した NIST Internal Report「Threshold Schemes for Cryptographic Primitives」(NISTIR 8214)の公表と、産業界、学術界、政府の視点を共有するために利害関係者が集まった「NIST Threshold Cryptography Workshop」(NTCW)2019 に続くものです。
The positive feedback received on the report (NISTIR 8214) and workshop (NTCW 2019) confirmed that there is interest and adequate knowledge by the stakeholders to initiate the process of standardization of threshold schemes. To prepare such an endeavor, this document tackles the challenge of differentiating various aspects of the standardization effort, while simultaneously aiming to enable an open and transparent process with the collaboration of the community of stakeholders. This document thus defines the approaches to devise criteria for future multiple open calls for contributions for standardization, with a focus on NIST-approved primitives. This provides a number of opportunities, but also requires dealing with a number of challenges.
報告書(NISTIR 8214)とワークショップ(NTCW 2019)に寄せられた好意的なフィードバックにより、利害関係者の間に、しきい値方式の標準化のプロセスを開始する関心と十分な知識があることが確認されました。そうした取り組みに備えるため、本書は、標準化の取り組みのさまざまな側面を区別するという課題に取り組みつつ、同時に、利害関係者のコミュニティの協力を得て、公開かつ透明なプロセスを可能にすることを目指しています。そこで本書は、NIST が承認したプリミティブに焦点を当て、将来の標準化への貢献を募る複数の公開募集のための基準を策定するアプローチを定義します。これは多くの機会をもたらしますが、多くの課題への対処も必要とします。
The main challenge is devising an effective mechanism to navigate the large diversity of possible threshold schemes, to identify priorities and to engage with the stakeholders for collaboration and feedback. To that end, this document starts by organizing the standardization effort into two different domains: single-device and multi-party.
主な課題は、多様なしきい値方式を見渡し、優先順位を特定し、協力とフィードバックを得るために利害関係者と関わるための、効果的な仕組みを策定することです。そのために、本書はまず、標準化の取り組みを、単一デバイスとマルチパーティという二つの異なる領域に整理するところから始めます。
As confirmed by feedback in the workshop (NTCW 2019), these domains have significantly different challenges and involve different threshold considerations. Each domain can encompass various base cryptographic primitives and corresponding threshold modes of operation. The perceived difficulty of standardization varies with the items, namely based on whether or not there exist related base standards, and on the dependence on complex techniques. This makes it likely that future new standards are reached in a sequence that first includes the simpler cases and only later the more complex cases.
ワークショップ(NTCW 2019)でのフィードバックで確認されたように、これらの領域には大きく異なる課題があり、しきい値に関する考慮事項も異なります。各領域は、さまざまな基盤となる暗号プリミティブと、それに対応するしきい値の動作モードを含みえます。標準化の難しさは、項目によって異なると認識されており、関連する基盤標準が存在するかどうかや、複雑な技術への依存度によって左右されます。このため、将来の新しい標準は、まず単純なケースを含み、複雑なケースは後になって含まれる、という順序で作成される可能性が高くなります。
Not all conceivable threshold schemes are appropriate for standardization. A weighting factor to consider is the potential for real-world applications, which to some extent may also affect the level of collaboration and engagement that the stakeholders are willing to undertake. An actual process of standardization also requires considering additional features, such as: the modular interplay of elements of different complexities (e.g., building blocks vs. composites) and different levels of specification; the specification of advanced security properties (e.g., composability) required for secure deployment; the suitability for testing and validation guidelines, to address regulatory requirements; and the availability of configurability options (e.g., threshold values).
考えうるすべてのしきい値方式が標準化に適しているわけではありません。考慮すべき重み付け要因の一つは、実世界で応用される可能性です。これはある程度、利害関係者が進んで取り組む協力と関与の水準にも影響する場合があります。実際の標準化プロセスでは、次のような追加の特徴も考慮する必要があります。複雑さの異なる要素(例: 構成要素と複合体)のモジュール的な相互作用と、仕様の水準の違い、セキュアな展開に必要な高度なセキュリティ特性(例: 合成可能性)の仕様、規制要件に対処するための試験・検証ガイドラインへの適合性、構成オプション(例: しきい値)の利用可能性です。
Using the outlined approach, this document identifies a diverse set of standardization objects (primitives and threshold modes) on which to focus, and enumerates several features that require further consideration. The elaboration of rationale intends to serve as a basis for subsequent discussions, and help organize the collaboration with stakeholders for devising concrete criteria. Overall, the combination of the multiple aspects under consideration may result in various distinct calls for contributions, as well as different timelines for the different foci. This roadmap is thus a step in a standardization process that intends to devise several useful new standards for different threshold schemes, including guidelines for testing and validation, and reference definitions of building blocks.
概説したアプローチを用いて、本書は、焦点を当てる多様な標準化対象(プリミティブとしきい値モード)を特定し、さらなる検討が必要ないくつかの特徴を列挙します。根拠の詳述は、その後の議論の土台となり、具体的な基準を策定するための利害関係者との協力を整理する助けとなることを意図しています。全体として、検討中の複数の側面を組み合わせると、さまざまな個別の貢献募集と、焦点ごとに異なるスケジュールが生じる可能性があります。したがって、このロードマップは、試験と検証のガイドラインや構成要素の参照定義を含め、さまざまなしきい値方式について複数の有用な新しい標準を策定することを目指す標準化プロセスの一歩です。
The end results of standardization may span new standalone documents, and be incorporated as addenda (e.g., specifying threshold modes) in existing standards, special publications, guidelines or introduced into external standards bodies. Furthermore, different items of standardization can have different associated timelines, with the latter depending on the corresponding complexity of the potential threshold schemes, and on criteria to be developed for their proposal, evaluation and selection.
標準化の最終的な成果は、新しい独立した文書として発行される場合もあれば、既存の標準、特別刊行物、ガイドラインへの追補(例: しきい値モードの規定)として取り込まれる場合や、外部の標準化団体に導入される場合もあります。さらに、標準化項目ごとに関連するスケジュールが異なる場合があり、そのスケジュールは、可能なしきい値方式の複雑さと、提案、評価、選定のために策定される基準に左右されます。
The main purpose of this document is to prepare a rationale structure that supports an upcoming solicitation of input for useful criteria for the standardization of threshold schemes for cryptographic primitives. This process includes obtaining technical comments about threshold schemes from experts in areas of threshold cryptography, strategic comments from those who work in cryptography standards but may be unfamiliar with threshold cryptography, and input about motivating application scenarios and restrictions from security practitioners and vendors.
本書の主な目的は、暗号プリミティブのしきい値方式の標準化のための有用な基準について、近く意見を募集する際の裏付けとなる、根拠の構造を準備することです。このプロセスには、しきい値暗号の分野の専門家からのしきい値方式に関する技術的なコメント、暗号標準に携わっているがしきい値暗号には不慣れな人々からの戦略的なコメント、およびセキュリティの実務者とベンダーからの、動機となる応用シナリオと制約についての意見を得ることが含まれます。
Table of Contents
目次
List of Figures
図の一覧
1 Introduction
1 はじめに
The Computer Security Division at the National Institute of Standards and Technology (NIST) has established the Threshold Cryptography project to drive an effort to standardize threshold schemes for cryptographic primitives. Threshold schemes enable distribution of trust placed on human operators, and offer a path to prevent several single-points of failure in conventional cryptographic implementations. They often build on top of secret-sharing schemes, which split a secret into parts, called shares, such that any “share” is unintelligible on its own, but enable recovering the secret once combined into a set with a threshold number of shares. However, threshold schemes go beyond secret-sharing and enable cryptographic operations (e.g., signing, encrypting and decrypting) without ever reconstructing the key in any place.
National Institute of Standards and Technology(NIST)の Computer Security Division は、暗号プリミティブのしきい値方式を標準化する取り組みを推進するため、Threshold Cryptography プロジェクトを設置しました。しきい値方式は、人間の運用者に寄せられた信頼を分散させ、従来の暗号実装における複数の単一障害点を防ぐ道筋を提供します。しきい値方式は、秘密を「シェア」と呼ばれる部分に分割する秘密分散方式の上に構築されることが多く、個々の「シェア」はそれ単体では意味をなしませんが、しきい値の数のシェアからなる集合に組み合わせると、秘密を復元できます。しかし、しきい値方式は秘密分散にとどまらず、どの場所でも鍵を再構成することなく、暗号操作(例: 署名、暗号化、復号)を可能にします。
This document comes on the heels of the NIST Internal Report (NISTIR) 8214, which posed representative questions about the standardization of threshold schemes, and the NIST Threshold Cryptography Workshop (NTCW) 2019, which brought together a variety of perspectives from stakeholders. The NISTIR 8214 had already identified the need to devise criteria for eventual calls for contributions for the development of new standards of threshold cryptographic schemes. The present document (NISTIR 8214A) is intended to serve as a preparation for definition of criteria. The goal is to lay out reference rationale (complementary to what the NISTIR 8214 has already done), terminology, and structure that are conducive, as the project moves forward, to a precise description of the material to standardize. In doing so, the document also tries to foresee the several phases of the standardization process. This is still an early step that identifies, at a high level, the space of standardization and a corresponding variety of manners to approach possible items, with possible different timelines.
本書は、しきい値方式の標準化に関する代表的な問いを提起した NIST Internal Report(NISTIR)8214 と、利害関係者のさまざまな視点が集まった NIST Threshold Cryptography Workshop(NTCW)2019 に続くものです。NISTIR 8214 はすでに、しきい値暗号方式の新しい標準の策定に向けた将来の貢献募集で用いる基準を考案する必要性を特定していました。本書(NISTIR 8214A)は、基準を定義するための準備となることを意図しています。目標は、プロジェクトが進むにつれて、標準化する題材を正確に記述することに資する、参照となる根拠(NISTIR 8214 がすでに行ったことを補完するもの)、用語、および構造を示すことです。その際、本書は標準化プロセスのいくつかの段階を見通すことも試みます。これはまだ初期のステップであり、標準化の領域と、それに対応する、スケジュールが異なる場合もある可能性のある項目への多様な取り組み方を、高いレベルで特定するものです。
The document covers various aspects pertinent to the standardization of threshold schemes for cryptographic primitives: identifying threshold modes of interest for the primitives to thresholdize (with a focus on NIST-approved cryptographic primitives); enumerating motivating applications; specifying intended interface and security properties; devising concrete criteria for calls for contribution, as well as for evaluating and selecting possible proposals, paths for testing and validation of algorithms and cryptographic modules in the threshold context; and ways of collaborating with stakeholders in an open and transparent process.
本書は、暗号プリミティブのしきい値方式の標準化に関連するさまざまな側面を扱います。しきい値化の対象となるプリミティブについて、関心のあるしきい値モードを特定すること(NIST が承認した暗号プリミティブに焦点を当てます)、動機となる応用を列挙すること、想定するインターフェースとセキュリティ特性を規定すること、貢献募集の具体的な基準および提案の評価・選定基準を策定すること、しきい値の文脈でアルゴリズムと暗号モジュールを試験・検証する道筋を定めること、そして公開かつ透明なプロセスで利害関係者と協力する方法を定めることです。
1.1 A multifaceted standardization effort
1.1 多面的な標準化の取り組み
Diverse stakeholders. The challenge inherent to this standardization endeavor goes beyond the technical considerations about the simple and sophisticated algorithms and techniques that enable threshold schemes for some cryptographic primitives. NIST recognizes a diverse set of stakeholders, including not only experts in the field of threshold cryptography, but also users, vendors, security practitioners, and those who work in cryptographic standards but may be unfamiliar with threshold techniques. The structure proposed in this document is intended to engage all stakeholders to generate feedback for the process ahead.
多様な利害関係者。この標準化の取り組みに内在する課題は、一部の暗号プリミティブについてしきい値方式を可能にする、単純で高度なアルゴリズムと技術についての技術的な検討にとどまりません。NIST は、しきい値暗号の分野の専門家だけでなく、利用者、ベンダー、セキュリティの実務者、そして暗号標準に携わっているがしきい値の技術には不慣れな人々を含む、多様な利害関係者を認識しています。本書で提案する構造は、今後のプロセスに向けたフィードバックを得るために、すべての利害関係者を巻き込むことを意図しています。
Diverse security properties. The standardization of threshold schemes can promote the advancement of security related to the implementation and operation of cryptographic primitives in the real world. This is applicable to diverse security properties, such as confidentiality, integrity and availability. If systems do fail in practice — often under attack — due to single points of failure, then threshold schemes can enhance their protection. The threshold approach can mitigate the consequences of those attacks and make them costlier to execute. Therefore, standardizing threshold schemes may also contribute to new best security practices in cybersecurity.
多様なセキュリティ特性。しきい値方式の標準化は、実世界における暗号プリミティブの実装と運用に関連するセキュリティの向上を促進できます。これは、機密性、完全性、可用性といった多様なセキュリティ特性に当てはまります。システムが実際に(しばしば攻撃を受けて)単一障害点が原因で故障するのであれば、しきい値方式はその保護を強化できます。しきい値によるアプローチは、そうした攻撃の影響を軽減し、攻撃の実行にかかるコストを高めることができます。したがって、しきい値方式を標準化することは、サイバーセキュリティにおける新たなベストプラクティスにも貢献する可能性があります。
On a variety of goals and paths. As the field of threshold schemes encompasses many possibilities, several approaches can be considered across various items, not all of which fall within the scope of developing new standards. For standardization, the current focus is on threshold schemes for NIST-approved cryptographic primitives. The goal is to enable the standardization of threshold modes of implementation for these primitives, as a way of promoting an improvement of best practices in settings where the implementation or operation of these primitives may be subject to attacks.
多様な目標と経路について。しきい値方式の分野は多くの可能性を含むため、さまざまな項目にわたっていくつかのアプローチを検討できますが、そのすべてが新しい標準の策定の範囲に入るわけではありません。標準化については、現在、NIST が承認した暗号プリミティブのしきい値方式に焦点を当てています。目標は、これらのプリミティブの実装または運用が攻撃を受けうる状況で、ベストプラクティスの改善を促進する手段として、これらのプリミティブのしきい値による実装モードの標準化を可能にすることです。
Some threshold schemes can be easily defined and applied to some cryptographic primitives. There are also demonstrably feasible threshold schemes whose consideration still raises difficulties for the selection of the best techniques, appropriate parameters, and building blocks. Some of the latter are within consideration for standardization, but attaining new standards will require first establishing a clear rationale to support concrete selections. Caution is needed in assessing whether particular techniques are ready for standardization, and which variations thereof are most appropriate, in particular those subject to very active research and fast-paced development. This is both a challenge and an opportunity, both of interest to a vibrant community of stakeholders.
一部のしきい値方式は、簡単に定義して、一部の暗号プリミティブに適用できます。また、実現可能であることが実証されているしきい値方式のなかにも、最良の技術、適切なパラメーター、構成要素の選定に関して、検討になお困難が伴うものがあります。後者の一部は標準化の検討対象になっていますが、新しい標準を得るには、まず、具体的な選定を裏付ける明確な根拠を確立する必要があります。特定の技術が標準化の準備ができているか、またそのどの変種が最も適切かを評価するには、特に、非常に活発に研究され、急速に開発が進んでいるものについては、慎重さが必要です。これは課題であると同時に機会でもあり、活気ある利害関係者のコミュニティにとって、どちらも関心事です。
This effort will inevitably lead to some open problems of interest to the research community. For example, threshold schemes are possible for candidate primitives under current evaluation within other NIST projects, such as the post-quantum cryptography and the lightweight cryptography. Although interesting, these cases are not considered in scope here for standardization, since the proposed conventional non-threshold primitives are still under security evaluation. Nonetheless, there is interest in learning about new research results and developments in the state of the art.
この取り組みは、必然的に、研究コミュニティにとって関心のあるいくつかの未解決問題につながります。たとえば、耐量子暗号や軽量暗号など、NIST の他のプロジェクトで現在評価中の候補プリミティブにも、しきい値方式が考えられます。これらのケースは興味深いものの、提案されている従来の非しきい値プリミティブがまだセキュリティ評価の途中であるため、ここでは標準化の対象範囲に含めていません。それでも、新しい研究成果や最先端の動向を知ることには関心があります。
On the types of standard/documents to produce. For some of the items identified in this document, a natural question is: how useful would a standard be for this item? The question leaves implicit the meaning of standard, which may vary with the context. While the terms standards and standardization are used throughout this report to refer to a set of possible final products, this does not imply a Federal Information Processing Standard (FIPS) as one or as the only intended format for NIST products of future threshold schemes for cryptographic primitives.
作成する標準・文書の種類について。本書で特定した項目の一部については、その項目について標準がどれほど有用かという問いが自然に生じます。この問いでは、文脈によって意味が異なりうる標準の意味が暗黙のままになっています。本報告書全体で「標準」および「標準化」という用語を、考えられる最終成果物の集合を指すために使っていますが、これは、暗号プリミティブのしきい値方式に関する NIST の将来の成果物について、Federal Information Processing Standard(FIPS)が唯一の想定形式であることも、想定される形式の一つであることも意味しません。
In some cases, a reasonable end goal may be to add an addendum (e.g., of a simple threshold mode) in an existing standard; in others, an appropriate goal may be to devise reference definitions of building blocks that may be useful for several threshold schemes to consider. In some cases, a worthy goal may be to devise implementation guidelines that enable validation within a certain security profile that confirms certain threshold properties. Some cases may warrant specifying new algorithms. The concrete form in which to deliver the new standards will become apparent as the process moves forward.
場合によっては、既存の標準に(たとえば単純なしきい値モードの)追補を加えることが妥当な最終目標となりえます。また、複数のしきい値方式が検討対象とできる構成要素の参照定義を策定することが適切な目標となる場合もあります。特定のしきい値特性を確認する、あるセキュリティプロファイルの範囲内での検証を可能にする実装ガイドラインを策定することが有意義な目標となる場合もあります。新しいアルゴリズムの規定が必要になる場合もあります。新しい標準を提供する具体的な形式は、プロセスが進むにつれて明らかになります。
A key note: Engaging with stakeholders is a priority in this project, toward an informed definition of criteria for standardization of threshold schemes for cryptographic primitives.
重要な注意点: 暗号プリミティブのしきい値方式の標準化の基準を、十分な情報に基づいて定義するために、このプロジェクトでは利害関係者との関与を優先しています。
1.2 A structured approach
1.2 構造化されたアプローチ
図です。最上段の箱には「Space of threshold schemes for cryptographic primitives」(暗号プリミティブのしきい値方式の空間)と書かれ、そこから「Single-device (domain)」(単一デバイスの領域)と「Multi-party (domain)」(複数主体の領域)の2つの箱に分かれます。単一デバイスの下には「Primitive a」…「Primitive b」、複数主体の下には「Primitive c」…「Primitive d」のプリミティブが並びます。「Primitive a」からは「Mode e」…「Mode f」、「Primitive d」からは「Mode g」…「Mode h」のモードに分かれ、「Primitive b」と「Primitive c」からはそれぞれ名前のない3本の枝が「…」とともに伸びています。
Figure 1. A depiction of a variety of primitives and threshold modes across two domains
図 1. 二つの領域にまたがるさまざまなプリミティブとしきい値モードの描写
1.2.1 The potential space of standardization
1.2.1 標準化の潜在的な領域
Considering several dimensions of the space of threshold schemes, the analysis of potential items for standardization benefits from a structured approach. It is useful to first distinguish between the single-device and the multi-party domains (Figure 1). Then, in each domain there are several cryptographic primitives that can be considered, each with a potential for implementation in various modes. However, not every conceivable possibility is suitable for standardization. Simplicity of standardization does not necessarily imply that an item should be standardized. Similarly, a perceived difficulty need not prevent advancement toward standardizing an item, even if it may take longer to achieve.
しきい値方式の領域には複数の次元があるため、標準化の候補となる項目の分析には、構造化されたアプローチが役立ちます。まず、単一デバイスとマルチパーティの領域を区別すると有用です(図 1)。そのうえで、各領域には検討対象となる複数の暗号プリミティブがあり、それぞれがさまざまなモードで実装できる可能性があります。ただし、考えうるすべての可能性が標準化に適しているわけではありません。標準化が簡単であることは、その項目を標準化すべきであることを必ずしも意味しません。同様に、難しいと認識されていても、達成により長い時間がかかるとしても、その項目の標準化に向けた前進が妨げられるとは限りません。
1.2.2 Motivating applications
1.2.2 動機となる応用
While there are many conceivable threshold schemes, for this project it is important to focus on where there is a high need and high potential for adoption. An overarching motivation in this effort is developing the ability to distribute trust in operations, and increase resistance against attacks on implementations. This applies to NIST-approved cryptographic primitives, since they already underpin the security of many real systems. Several potential applications can benefit directly from the threshold properties enabled in implementations of these cryptographic primitives. Along the process, stakeholders can provide feedback on concrete applications of interest.
考えうるしきい値方式は数多くありますが、このプロジェクトでは、必要性が高く、採用の可能性も高い領域に焦点を当てることが重要です。この取り組みの根底にある動機は、運用における信頼を分散させ、実装への攻撃に対する耐性を高める能力を開発することです。これは、NIST が承認した暗号プリミティブがすでに多くの実システムのセキュリティを支えているため、それらに当てはまります。これらの暗号プリミティブの実装で可能になるしきい値特性から、いくつかの潜在的な応用が直接的な恩恵を受けられます。プロセスを通じて、利害関係者は、関心のある具体的な応用についてフィードバックを提供できます。
1.2.3 Items across two tracks
1.2.3 二つのトラックにまたがる項目
At a high level, the standardization effort is organized into two separate tracks (one per domain): single-device and multi-party. The two domains differ substantially in system models, so the separation into tracks allows a better differentiation between concurrent approaches of standardization.
大局的には、標準化の取り組みは、単一デバイスとマルチパーティという二つの個別のトラック(領域ごとに一つ)に整理されています。二つの領域はシステムモデルが大きく異なるため、トラックに分けることで、標準化の並行するアプローチをよりよく区別できます。
The organization of possible items (primitive/mode) for standardization can be independently organized per track. Some of the default primitives to potentially consider for thresholdization come from NIST standards specifying the Rivest–Shamir–Adleman (RSA) signature and encryption schemes, the Elliptic Curve Digital Signature Algorithm (ECDSA), the Edwards Curve Digital Signature Algorithm (EdDSA), the Elliptic Curve Cryptography (ECC) Cofactor Diffie-Hellman (CDH) primitive, the Advanced Encryption Standard (AES), and methods for random number generation (RNG). There is a special interest in the primitives related to secret keys, such as key-generation, signing, decryption within a public-key encryption (PKE) scheme, and symmetric-key enciphering and deciphering. For each of them, it is important to identify relevant threshold modes of operation, and how some of their technical challenges may vary with respect to standardization.
標準化の可能性がある項目(プリミティブ/モード)の構成は、トラックごとに独立して整理できます。しきい値化を検討する可能性のある既定のプリミティブの一部は、Rivest–Shamir–Adleman(RSA)の署名方式と暗号化方式、Elliptic Curve Digital Signature Algorithm(ECDSA)、Edwards Curve Digital Signature Algorithm(EdDSA)、Elliptic Curve Cryptography(ECC)の Cofactor Diffie-Hellman(CDH)プリミティブ、Advanced Encryption Standard(AES)、および乱数生成(RNG)の方法を規定する NIST の標準に由来します。特に関心が持たれているのは、鍵生成、署名、公開鍵暗号(PKE)方式における復号、共通鍵の暗号化と復号など、秘密鍵に関連するプリミティブです。これらのそれぞれについて、関連するしきい値の動作モードを特定し、その技術的課題の一部が標準化に関してどのように異なりうるかを特定することが重要です。
1.2.4 Detailed features
1.2.4 詳細な特徴
Besides the high-level identification of threshold modes of interest, there are detailed features of fundamental importance in the upcoming phase of criteria definition. Three important aspects are:
関心のあるしきい値モードを大局的に特定することに加えて、今後の基準定義の段階で根本的に重要となる詳細な特徴があります。重要な側面は次の三つです。
•configurability and security features, whose specification is needed to characterize the threshold scheme, including its interface;
•構成可能性とセキュリティ機能。インターフェースを含め、しきい値方式を特徴付けるために、その仕様が必要です。
•suitability for validation, required in the process of allowing the use of cryptographic schemes in several application scenarios (e.g., in the U.S. federal context); and
•検証への適合性。(たとえば米国連邦政府の文脈など)さまざまな応用シナリオで暗号方式の使用を認める過程で必要になります。
•modularity of components and specification detail, which is relevant to identifying recurring building blocks (e.g., secret sharing) that may appear across several threshold schemes, as well as improving the security analysis and the simplicity of specification.
•構成要素のモジュール性と仕様の詳細度。複数のしきい値方式に現れうる繰り返し出現する構成要素(例: 秘密分散)を特定するうえで、また、セキュリティ分析と仕様の簡潔さを改善するうえで重要です。
1.2.5 Development phases
1.2.5 策定の段階
The standardization project encompasses phases of devising criteria for calls for contributions, evaluating proposed contributions, and writing documentation for new standards. Standardization items with different developmental needs may be organized into different tailored calls for contributions and corresponding timelines. This improves collaboration with a set of stakeholders interested in a variety of standardization items and challenges. Expected new standards and guidelines may include reference definitions (e.g., for secret sharing), algorithms/techniques for threshold implementations, and security profiles for validation/certification. The resulting documentation may span a variety of formats, including addenda to existing standards (e.g., a simple threshold mode of operation), and new standalone documents (e.g., describing new complex techniques and analysis).
標準化プロジェクトには、貢献募集の基準を策定する段階、提案された貢献を評価する段階、新しい標準の文書を作成する段階があります。策定上の必要性が異なる標準化項目は、それぞれに合わせた別々の貢献募集と、対応するスケジュールに整理できます。これにより、多様な標準化項目と課題に関心を持つ利害関係者との協力が改善されます。見込まれる新しい標準とガイドラインには、(たとえば秘密分散の)参照定義、しきい値による実装のためのアルゴリズムや技術、検証・認証のためのセキュリティプロファイルが含まれる可能性があります。結果として得られる文書は、既存の標準への追補(例: 単純なしきい値の動作モード)や、新しい独立した文書(例: 新しい複雑な技術と分析の記述)など、さまざまな形式にまたがりえます。
1.3 Feedback from stakeholders
1.3 利害関係者からのフィードバック
To drive an open and transparent standardization process, several phases present opportunities for public feedback. Currently, there is particular interest in the following topics:
公開かつ透明な標準化プロセスを推進するため、いくつかの段階で、一般からフィードバックを得る機会が設けられます。現在、特に次のトピックに関心があります。
1.standardization items (including threshold modes) that fit the described organization;
1.記述した構成に当てはまる標準化項目(しきい値モードを含む)
2.potential real-world applications that motivate concrete threshold schemes;
2.具体的なしきい値方式の動機となる、実世界での応用の可能性
3.interface and security properties of interest in the threshold scope;
3.しきい値の範囲で関心のあるインターフェースとセキュリティ特性
4.criteria for evaluating and comparing a variety of possible instantiations; and
4.考えうるさまざまなインスタンス化を評価し比較するための基準
5.forms of collaboration with stakeholders.
5.利害関係者との協力の形態
1.4 Organization
1.4 構成
Section 2 outlines a mapping of the potential standardization space into specification levels of domains, primitives, and threshold modes. Section 3 considers application motivations for threshold schemes. Section 4 discusses concrete primitives and threshold modes of interest in the multi-party and single-device domains. Section 5 emphasizes several features whose consideration is required when specifying criteria for concrete items. Section 6 discusses the generic phases of development toward new standards. Section 7 proposes and motivates high-level aspects of criteria and calls for contributions from stakeholders. Appendix A describes examples of motivating applications.
第 2 節では、標準化の潜在的な領域を、領域、プリミティブ、しきい値モードという仕様の水準に対応付けて概説します。第 3 節では、しきい値方式の応用上の動機を検討します。第 4 節では、マルチパーティと単一デバイスの領域で関心のある、具体的なプリミティブとしきい値モードを論じます。第 5 節では、具体的な項目の基準を規定する際に考慮が必要となる、いくつかの特徴を強調します。第 6 節では、新しい標準に向けた一般的な策定の段階を論じます。第 7 節では、基準の大局的な側面を提案してその動機を説明し、利害関係者に貢献を呼びかけます。付録 A では、動機となる応用の例を説明します。
2 The space of threshold schemes for potential standardization
2 標準化の可能性があるしきい値方式の領域
2.1 Two domains
2.1 二つの領域
As a way of organizing the potential space of standardization of threshold schemes, this project distinguishes two domains: single-device and multi-party. The denominations intend to be literal: the former refers to a single device that internally confines all logical components of the threshold scheme; the latter refers to a threshold system composed of multiple parties, possibly with independent locations. The single-device domain is associated with a rigidity of configuration of components, strictly defined physical boundaries, and a dedicated communication network. Conversely, the multi-party domain tends to enable a modularized patching of components (e.g., repairing newly found bugs in existing components, or replacing old components with new ones) and may allow dynamic configurations of the parties in a protocol (possibly decided by an administrative authority). The multi-party case may also require solving problems related to distributed systems, such as byzantine agreement (consensus).
しきい値方式の標準化の潜在的な領域を整理する方法として、このプロジェクトでは、単一デバイスとマルチパーティという二つの領域を区別します。この名称は文字どおりの意味を意図しています。前者は、しきい値方式のすべての論理的構成要素を内部に閉じ込める単一のデバイスを指し、後者は、場所が独立している可能性のある複数の関与者(パーティ)から成るしきい値システムを指します。単一デバイスの領域は、構成要素の構成が固定的であること、物理的な境界が厳密に定義されていること、専用の通信ネットワークがあることに関連付けられます。これに対し、マルチパーティの領域は、構成要素のモジュール化されたパッチ適用(例: 既存の構成要素で新たに見つかったバグの修正や、古い構成要素の新しいものへの置き換え)を可能にする傾向があり、プロトコル内のパーティの動的な構成(管理上の権限者が決定する場合もあります)を許容する場合があります。マルチパーティの場合は、ビザンチン合意(コンセンサス)など、分散システムに関連する問題の解決も必要になる場合があります。
The two domains share common features with respect to certain threshold elements, and some aspects may be cross-domain applicable. For example, secret-sharing is often a basic component applicable to both domains. Furthermore, the two domains can also be applied hierarchically, such as in a multi-party threshold implementation where each party is itself a thresholdized single-device.
二つの領域は、あるしきい値の要素に関して共通する特徴を持ち、一部の側面は領域をまたいで適用できる場合があります。たとえば、秘密分散は、多くの場合、両方の領域に適用できる基本的な構成要素です。さらに、二つの領域は、各パーティ自体がしきい値化された単一デバイスである、マルチパーティのしきい値実装のように、階層的に適用することもできます。
2.2 Primitives
2.2 プリミティブ
In the scope of this standardization endeavor, the [cryptographic] primitive layer is a main aspect of characterization of an item for thresholdization. The same conventional scheme (e.g., “encryption scheme”), often defined as a tuple of algorithms, can encompass several primitives of interest (e.g., key-generation vs. encryption vs. decryption). The separate consideration of primitives allows modularizing distinct concerns of single-points of failure, which may be considered differently across application settings. For example: on one hand, the ability to avoid a dealer of a secret key (i.e., having a dealerless scheme) may be a desirable feature for some application scenarios; on the other hand the use of a dealer is not necessarily a shortcoming, e.g., in certain application settings where the dealer is the enabler of a subsequent threshold scheme. Therefore, the need for threshold key-generation should be considered separately from the need for threshold signing, decryption or enciphering. Section 4 focuses on some NIST-approved algorithms defined in Federal Information Processing Standards (FIPS) and Special Publications in Computer Security (SP 800). Overall, these include concrete instantiations for signing, decryption (within a public-key encryption (PKE) scheme), enciphering/deciphering, key generation (including RNG), and one-side key-operations related to pair-wise key-agreement.
この標準化の取り組みの範囲では、[暗号]プリミティブの層が、しきい値化する項目を特徴付ける主要な側面です。同じ従来の方式(例: 「暗号化方式」)は、アルゴリズムのタプルとして定義されることが多く、複数の関心のあるプリミティブ(例: 鍵生成、暗号化、復号)を含みえます。プリミティブを個別に検討することで、単一障害点に関する別々の懸念をモジュール化でき、これらは応用の設定によって異なる扱いを受ける場合があります。たとえば、一方では、秘密鍵のディーラーを不要にする(すなわち、ディーラーを介さない方式にする)能力は、一部の応用シナリオでは望ましい機能となりえます。他方で、ディーラーの使用は必ずしも欠点ではなく、たとえば、ディーラーが後続のしきい値方式を可能にする役割を果たす特定の応用の設定がそうです。したがって、しきい値による鍵生成の必要性は、しきい値による署名、復号、暗号化の必要性とは別に検討すべきです。第 4 節では、Federal Information Processing Standards(FIPS)と Special Publications in Computer Security(SP 800)で定義された、NIST が承認したいくつかのアルゴリズムに焦点を当てます。全体として、これらには、署名、(公開鍵暗号(PKE)方式における)復号、暗号化/復号、(RNG を含む)鍵生成、およびペアワイズの鍵合意に関連する片側の鍵操作の、具体的なインスタンス化が含まれます。
The process of developing new standards must include establishing a clear rationale to support concrete selections. Therefore, it is likely that the first new published standards will stem from simple techniques capable of thresholdizing current NIST-approved algorithms. One probable example, simple and concrete, is that of a threshold version of RSA signing or decryption, where the private RSA key is initially secret-shared across several parties. This can be instantiated in a way that \(n\)-out-of-\(n\) or even \(k\)-out-of-\(n\) parties need to be present to produce the signature or decryption.
新しい標準を策定するプロセスには、具体的な選定を裏付ける明確な根拠を確立することを含めなければなりません。そのため、最初に公表される新しい標準は、現在 NIST が承認しているアルゴリズムをしきい値化できる単純な技術に由来する可能性が高いです。単純で具体的な、可能性の高い例の一つは、RSA の署名または復号のしきい値版であり、そこでは RSA 秘密鍵が最初に複数のパーティの間で秘密分散されます。これは、署名または復号を生成するために、\(n\)-out-of-\(n\)、あるいは \(k\)-out-of-\(n\) のパーティが存在する必要があるように、インスタンス化できます。
When a cryptographic operation is required, each party individually computes something with their secret share, and later the outputs are combined, without ever combining together the shares that would enable recovering the secret key. Other simple examples can include threshold schemes resulting from simple combinations of techniques similar or closely related to those standardized, as may happen to achieve some multi-signatures with independent keys.
暗号操作が必要なとき、各パーティは自分の秘密シェアを使って個別に何かを計算し、その後で出力が組み合わされますが、秘密鍵を復元できるようになるシェアが組み合わされることはありません。そのほかの単純な例には、標準化されたものと類似または密接に関連する技術の単純な組み合わせから生じるしきい値方式があり、独立した鍵を用いたマルチ署名の一部を実現する場合などが該当します。
Several threshold techniques enable distributing — across several parties or components — the trust about the secrecy of a private key, such that the compromise of the internal state of a single party would not completely break the security of the system. When having to sign or decrypt a plaintext, the set of parties operates in such a way that the end result is as if a cryptographic module held the key at some point in time, but in fact the result is obtained without the key ever being recombined in a particular place.
いくつかのしきい値の技術は、秘密鍵の秘匿性に関する信頼を、複数のパーティまたは構成要素に分散させることを可能にします。このため、単一のパーティの内部状態が危殆化しても、システムのセキュリティが完全に破られることはありません。平文に署名したり、平文を復号したりする必要があるとき、パーティの集合は、最終的な結果が、ある時点で暗号モジュールが鍵を保持していたかのようになるように動作しますが、実際には、特定の場所で鍵が再結合されることなく結果が得られます。
With respect to publishing standards, it is likely that with time it will be possible to reach schemes that require more complex compositional design approaches, possibly using some building blocks that do not currently appear in any NIST standard. The overall design of those schemes must have well-understood security properties. Since the base primitives of focus are NIST-approved cryptographic primitives, the task of analyzing the security and parameters of the original non-threshold algorithm is likely to not be a hindrance to the standardization process. For example, threshold RSA key generation can be comparatively difficult, but the decision of which parameters to use for RSA keys is already dealt with at the level of the non-threshold primitive. Rather, in such cases, the complexity of standardization is in specifying the building blocks, defining a protocol for a chosen threshold mode (Section 2.3), and analyzing the security of the composition.
標準の公表に関しては、時間が経てば、より複雑な合成的設計アプローチを必要とする方式にも到達できる可能性が高く、それには、現在どの NIST の標準にも見られない構成要素の一部を使う可能性もあります。そうした方式の全体設計には、よく理解されたセキュリティ特性がなければなりません。焦点を当てる基盤プリミティブは NIST が承認した暗号プリミティブであるため、元の非しきい値アルゴリズムのセキュリティとパラメーターを分析する作業は、標準化プロセスの妨げにならない可能性が高いです。たとえば、しきい値による RSA の鍵生成は比較的難しい場合がありますが、RSA 鍵にどのパラメーターを使うかの決定は、すでに非しきい値プリミティブの水準で扱われています。むしろ、そのような場合の標準化の複雑さは、構成要素を規定すること、選択したしきい値モードのプロトコルを定義すること(第 2.3 節)、そして合成のセキュリティを分析することにあります。
2.3 Modes of Input/Output interface
2.3 入出力インターフェースのモード
Before thresholdization, the conventional paradigm of interest is one where a client requests an operation from a cryptographic module, as depicted in Figure 2a. The client first sends, to the module, a request with some input, such as a plaintext \(p\) for encryption or for signing, or a ciphertext \(c\) for decryption); then the client receives back the reply with the intended output, such as a ciphertext block \(c = \mathrm{AES}_K(p)\), a signature \(\sigma = \mathrm{ECDSA}_K(p)\), or a decrypted plaintext \(p = \mathrm{RSA}_K(c)\), where \(K\) denotes the secret/private key.
しきい値化の前に関心の対象となる従来のパラダイムは、図 2a に示すように、クライアントが暗号モジュールに操作を要求するものです。クライアントはまず、暗号化や署名のための平文 \(p\)、または復号のための暗号文 \(c\) など、何らかの入力を含むリクエストをモジュールに送ります。その後、クライアントは、暗号文ブロック \(c = \mathrm{AES}_K(p)\)、署名 \(\sigma = \mathrm{ECDSA}_K(p)\)、復号された平文 \(p = \mathrm{RSA}_K(c)\) など、意図した出力を含むリプライを受け取ります。ここで \(K\) は共通鍵または秘密鍵を表します。
At a high level, a similar paradigm can be considered for threshold schemes, with respect to a client, with some input, requesting that some entity processes a cryptographic primitive. However, as a fundamental difference, the entity receiving and processing the request and outputting its result is a threshold entity, which is, in fact, a composite of components (either multiple parties, or a single-device with several components) enabling a threshold property for some security property.
大局的には、しきい値方式についても同様のパラダイムを考えることができます。すなわち、何らかの入力を持つクライアントが、あるエンティティに、暗号プリミティブを処理するよう要求するものです。ただし、根本的な違いとして、リクエストを受け取って処理し、その結果を出力するエンティティはしきい値エンティティであり、これは実際には、あるセキュリティ特性についてしきい値特性を可能にする構成要素(複数のパーティ、または複数の構成要素を持つ単一デバイス)の複合体です。
Within the client–module paradigm, this document uses the notion of threshold mode to refer to the level of characterization that distinguishes, from the perspective of the client, variations of the threshold scheme. It is thus possible to refer to multiple distinct thresholdized modes for the same cryptographic primitive. Note: the meaning of “mode” here should not be confused with the usage in “block-cipher mode of operation”, which identifies how a block-cipher can be used to encrypt and decrypt large messages.
クライアント–モジュールのパラダイムの中で、本書は、クライアントの視点から、しきい値方式のバリエーションを区別する特徴付けの水準を指すために、しきい値モードという概念を用います。したがって、同じ暗号プリミティブに対して、複数の異なるしきい値化されたモードに言及することが可能です。注: ここでの「モード」の意味は、ブロック暗号を用いて大きなメッセージを暗号化・復号する方法を示す「ブロック暗号の動作モード」での用法と混同してはなりません。
5つのブロック図です。(a) Conventional (non-threshold)(従来型、しきい値なし):「Client」(クライアント)の箱が「request」(要求)を「(Conventional) Cryptographic Module」(従来型の暗号モジュール)の箱に送り、「reply」(応答)を受け取ります。(b) Not-shared-IO:クライアントは「request」を送り、「reply」を受け取ります。「Inter-node network」(ノード間ネットワーク)が「Component C1」「Component C2」…「Component Cn」とつながっている箱です。(c) Shared-IO:クライアントは、ノード間ネットワークにつながった「Component C1」から「Component Cn」のそれぞれと、「request to C1」/「reply from C1」、「request to C2」/「reply from C2」…「request to Cn」/「reply from Cn」をやり取りします。(d) Shared-I:クライアントは「request to C1」「request to C2」…「request to Cn」を構成要素に送り、単一の「reply」がクライアントに戻ります。構成要素はノード間ネットワークにつながっています。(e) Shared-O:クライアントは単一の「request」を送り、ノード間ネットワークにつながった構成要素から「reply from C1」「reply from C2」…「reply from Cn」を受け取ります。
Figure 2. Several threshold interfaces (and one non-threshold case)
図 2. いくつかのしきい値インターフェース(および一つの非しきい値の場合)
From the perspective of a client, the threshold entity can still be abstracted as a cryptographic module (and in some cases may even be indistinguishable from a conventional one). Nonetheless, this may possibly involve some sophistication in the interface and/or on how to interpret the input and output. While it is relevant to keep it simple on the client-side, some sophistication is allowed: the use of client-side secret-sharing (or reconstruction), or the ability to perform additional verifications (e.g., signature verifications).
クライアントの視点からは、しきい値エンティティは依然として暗号モジュールとして抽象化できます(場合によっては従来のものと区別できないこともあります)。ただし、これにはインターフェース、または入力と出力の解釈方法、あるいはその両方に、何らかの高度な仕組みが関わる可能性があります。クライアント側では単純に保つことが重要ですが、クライアント側での秘密分散(または復元)の使用や、追加の検証(例: 署名の検証)を行う能力など、ある程度の高度な仕組みは許容されます。
With respect to the input/output (I/O) interface, Figure 2 depicts four distinct cases: no I/O secret-sharing (Figure 2b), secret-sharing of both input and output (Figure 2c), secret-sharing of only the input (Figure 2d), and secret-sharing of only the output (Figure 2e). The figures are mere abstractions. The actual communication medium and the input/output connections depend on the implementation and on a more detailed specification of the threshold scheme.
入出力(I/O)インターフェースについて、図 2 は四つの異なるケースを示しています。I/O の秘密分散なし(図 2b)、入力と出力の両方の秘密分散(図 2c)、入力のみの秘密分散(図 2d)、出力のみの秘密分散(図 2e)です。これらの図は単なる抽象化です。実際の通信媒体と入出力の接続は、実装と、しきい値方式のより詳細な仕様に依存します。
The following description conveys additional detail about the interfaces:
以下の説明では、インターフェースの詳細を補足します。
•Not-shared-IO: The client sends the full input to the threshold entity (via a relaying proxy or primary component, or by broadcasting to all components), and later receives back the output, exactly as in the non-threshold scheme. See Figure 2b.
•共有なし IO(Not-shared-IO): クライアントは、(中継プロキシまたは主たる構成要素を介して、あるいはすべての構成要素へのブロードキャストによって)完全な入力をしきい値エンティティに送り、非しきい値方式とまったく同じように、その後で出力を受け取ります。図 2b を参照してください。
•Shared-I: The client secret-shares the input in a \(k\)-out-of-\(n\) manner, and then sends each share to each component of the threshold scheme. The components may then communicate between themselves to securely compute the output (e.g., a ciphertext \(c\)) without learning the input. This mode is relevant for enhanced secrecy of the input (e.g., a plaintext submitted for symmetric encryption, or possibly even for signing). See Figure 2d.
•共有 I(Shared-I): クライアントは、入力を \(k\)-out-of-\(n\) の方式で秘密分散し、各シェアをしきい値方式の各構成要素に送ります。構成要素は、その後、相互に通信して、入力を知ることなく、出力(例: 暗号文 \(c\))を安全に計算できます。このモードは、入力(例: 共通鍵暗号のために提出される平文、場合によっては署名のために提出されるものも)の秘匿性を高めるのに関係する場合があります。図 2d を参照してください。
•Shared-O: Upon the completion of a threshold computation, each component obtains only a secret share of the output (e.g., of a decrypted plaintext), and sends it to the client. The client then reconstructs the final output from the shares. This mode is relevant for enhanced secrecy of output (e.g., a plaintext obtained from threshold decryption). See Figure 2e.
•共有 O(Shared-O): しきい値計算が完了すると、各構成要素は出力(例: 復号された平文)の秘密シェアだけを得て、それをクライアントに送ります。その後、クライアントはシェアから最終的な出力を復元します。このモードは、出力(例: しきい値復号で得られる平文)の秘匿性を高めるのに関係します。図 2e を参照してください。
•Shared-IO: Both the input (I) and the output (O) are secret-shared across the components of the threshold scheme. Only the client sees the complete input and output. See Figure 2c.
•共有 IO(Shared-IO): 入力(I)と出力(O)の両方が、しきい値方式の構成要素の間で秘密分散されます。完全な入力と出力を見るのはクライアントだけです。図 2c を参照してください。
“Shared-I/O” is used to denote any case within shared-I, shared-O, and shared-IO. Other threshold mode aspects may be considered throughout the standardization process.
「Shared-I/O」は、shared-I、shared-O、shared-IO のいずれかのケースを指すために使います。そのほかのしきい値モードの側面は、標準化プロセスを通じて検討される場合があります。
Note on key generation. The above distinctions apply well to primitives with a clearly defined input/output (e.g., ciphertext/plaintext). This includes cases where the needed secret or private key has been secret-shared in advance. The case of key generation as a primitive can be slightly different, if the administrator client does not intend to learn the generated secret (symmetric) or private (asymmetric) key but rather intends the threshold entity (module) to be updated with a new internal secret-shared key. In that case, the input sent by the client to the threshold entity is a key length and some generic protocol parameters, different from an actual input for signing or encryption/decryption. As output of the threshold computation, the client receives a public-key, if applicable, and nothing else (apart from protocol metadata, e.g., a confirmation of success). Nonetheless, the shared-I/O mode is still conceivable, if useful for some application. For example, the client could provide the input (e.g., a base element of a public key) in a shared-I mode, and/or the “public key” could be calculated in a shared-O manner, such that the client would collect those shares and locally calculate the public key.
鍵生成に関する注記。上記の区別は、入力と出力が明確に定義されたプリミティブ(例: 暗号文/平文)によく当てはまります。これには、必要な共通鍵または秘密鍵があらかじめ秘密分散されているケースが含まれます。プリミティブとしての鍵生成のケースは、管理者であるクライアントが、生成された共通鍵または秘密鍵を知ることを意図せず、むしろしきい値エンティティ(モジュール)が、秘密分散された新しい内部鍵で更新されることを意図する場合には、やや異なります。その場合、クライアントがしきい値エンティティに送る入力は、鍵長といくつかの汎用的なプロトコルパラメーターであり、署名や暗号化/復号の実際の入力とは異なります。しきい値計算の出力として、クライアントは、該当する場合は公開鍵を受け取り、それ以外は何も受け取りません(プロトコルのメタデータ、たとえば成功の確認を除く)。それでも、一部の応用で有用であれば、shared-I/O モードは依然として考えられます。たとえば、クライアントが入力(例: 公開鍵の基底要素)を shared-I モードで提供したり、「公開鍵」が shared-O の方法で計算されたりして、クライアントがそれらのシェアを集めて、ローカルで公開鍵を計算することもありえます。
Note on intermediaries. A not-shared-IO mode may in some cases be achieved based on a shared-I/O mode, by incorporating in the threshold entity an intermediate secret-sharing / reconstructor proxy mediating the communication between the client and the threshold components (except if the underlying shared-I/O mode requires communication authentication between the client and components). In a not-shared-IO mode, the client may or may not be aware of the threshold nature of the cryptographic “module”.
仲介者に関する注記。共有なし IO(not-shared-IO)モードは、場合によっては、クライアントとしきい値の構成要素との間の通信を仲介する、秘密分散/復元用の中間プロキシをしきい値エンティティに組み込むことで、shared-I/O モードに基づいて実現できます(基盤となる shared-I/O モードが、クライアントと構成要素との間の通信認証を必要とする場合を除きます)。共有なし IO モードでは、クライアントは、暗号「モジュール」がしきい値であることを認識している場合も、認識していない場合もあります。
Note on the scope of possible modes. With respect to standardization, it is important to consider the dimension of interoperability between threshold and non-threshold schemes (Section 2.4), particularly from the perspective of a client requesting a service (e.g., signature, encryption, decryption) from a cryptographic module. The possible adaptation of clients to perform secret-sharing and/or reconstruction is an exception that yields the various shared-I, shared-O and shared-IO modes. Some additional aspects of client involvement may be implicit within communication protocols, such as possibly using transport layer security (TLS) between the client and the threshold entity.
可能なモードの範囲に関する注記。標準化に関しては、特に暗号モジュールにサービス(例: 署名、暗号化、復号)を要求するクライアントの視点から、しきい値方式と非しきい値方式との間の相互運用性という次元(第 2.4 節)を考慮することが重要です。クライアントが秘密分散や復元、あるいはその両方を行うように適応させる可能性は例外であり、これにより、さまざまな shared-I、shared-O、shared-IO モードが生じます。クライアントの関与に関するいくつかの追加の側面は、クライアントとしきい値エンティティとの間でトランスポート層セキュリティ(TLS)を使用するなど、通信プロトコルの中に暗黙的に含まれる場合があります。
The presented interface alternatives, limited to secret-sharing, do not cover all conceivable multi-party protocols, but they address some privacy and integrity concerns about input/output. Some conceivable alternatives requiring sophisticated client enhancements are left out of the current scope. For example, one could conceive interactions where the client would interact in a secure two-party computation with the module (threshold entity) in order to let go of the secrecy of the input and output, even if the module is not thresholdized. This would be a case where even a collusion of all of the components/parties of the threshold scheme would not learn anything about the input of the client. This approach falls outside of the direct scope of the threshold cryptography project, but is within the area of interest of the privacy-enhancing cryptography project.
秘密分散に限定した、ここで示したインターフェースの選択肢は、考えうるすべてのマルチパーティプロトコルを網羅するわけではありませんが、入出力に関するプライバシーと完全性の懸念の一部に対処します。クライアントに高度な拡張を必要とする、考えうる選択肢の一部は、今回の対象範囲から外しています。たとえば、モジュールがしきい値化されていない場合でも、入力と出力の秘匿性を手放すために、クライアントがモジュール(しきい値エンティティ)とのセキュアな二者間計算で対話するようなやり取りを考えることができます。これは、しきい値方式のすべての構成要素/パーティが結託しても、クライアントの入力について何も知ることができないケースとなります。このアプローチは、Threshold Cryptography プロジェクトの直接の対象範囲外ですが、プライバシー強化暗号プロジェクトの関心領域の範囲内にあります。
2.4 Notions of interoperability for the client
2.4 クライアントにとっての相互運用性の概念
It is useful to characterize the interoperability of a threshold scheme from the perspective of a client. Section 2.3 discussed the input/output interface nuances. The present section considers the functional properties of the output of a cryptographic primitive. In particular, if a client is capable of interpreting and operating on outputs of the non-threshold scheme, then it is relevant to determine whether the client is also able to handle the final output produced by the threshold implementation. The functional scope refers to the main output, ignoring whether it may have had to be reconstructed from shares (when in a shared-O/IO mode), and whether or not there may exist additional protocol metadata made available to the client (e.g., public-keys and/or authentication by each threshold component). For the purpose of this document it is useful to define some terminology.
クライアントの視点から、しきい値方式の相互運用性を特徴付けると有用です。第 2.3 節では、入出力インターフェースの細かな違いを論じました。本節では、暗号プリミティブの出力の機能的な特性を検討します。特に、クライアントが非しきい値方式の出力を解釈して操作できる場合、そのクライアントが、しきい値による実装が生成した最終的な出力も扱えるかどうかを判断することが重要です。機能的な範囲とは、主要な出力を指し、(shared-O/IO モードのとき)それがシェアから復元される必要があったかどうかや、クライアントが追加のプロトコルメタデータ(例: 公開鍵、各しきい値構成要素による認証)を利用できるかどうかは考慮しません。本書の目的のために、いくつかの用語を定義すると有用です。
Functional equivalence. A threshold scheme for a cryptographic primitive is functionally equivalent to its non-threshold counterpart if for each input in the threshold scheme the output probability distribution is identical. Examples of functional equivalence:
機能的同等性。暗号プリミティブのしきい値方式は、しきい値方式への各入力に対して出力の確率分布が同一である場合に、その非しきい値の対応物と機能的に同等です。機能的同等性の例を挙げます。
•Block-cipher. Since a block-cipher is a function, a threshold implementation of it must lead to the same output as the non-threshold counterpart (possibly after computations related to the input/output interface mode).
•ブロック暗号。ブロック暗号は関数であるため、そのしきい値による実装は、(場合によっては入出力インターフェースモードに関連する計算の後に)非しきい値の対応物と同じ出力をもたらさなければなりません。
•Decryption. A decryption algorithm, upon inputted with a well-formed ciphertext, must return the corresponding unique plaintext that was encrypted. The equivalence applies for decryption with any secret key possible in the threshold scheme, even if the key generation itself is non-equivalent (example in next bullet), as long as it is secure.
•復号。復号アルゴリズムは、整形式の暗号文を入力として受け取ると、暗号化された対応する一意の平文を返さなければなりません。この同等性は、しきい値方式で可能な任意の共通鍵による復号に適用されます。これは、安全である限り、鍵生成自体が同等でない場合(例は次の箇条書き)でも当てはまります。
Functional interchangeability. A threshold scheme for a cryptographic primitive (e.g., signing) is functionally interchangeable, with respect to a subsequent operation (e.g., verification), if the final output of the threshold executing of the primitive can be used instead of the output of the conventional (non-threshold) primitive, with respect to the referred operation that uses said output as an input. Examples of functional interchangeability:
機能的互換性。暗号プリミティブ(例: 署名)のしきい値方式は、後続の操作(例: 検証)に関して、そのプリミティブのしきい値による実行の最終的な出力を、その出力を入力として使う当該の操作において、従来の(非しきい値の)プリミティブの出力の代わりに使用できる場合に、機能的に互換です。機能的互換性の例を挙げます。
•Key-generation is interchangeable with respect to signing and decryption, if the generated keys are compatible with those operations. For example, a distributed RSA key generation may be functionally interchangeable even if it biases the probabilistic distribution of the output keys to be RSA moduli with both primes equal to 3 mod 4.
•鍵生成は、生成された鍵が署名や復号の操作と適合する場合、それらの操作に関して互換です。たとえば、分散 RSA 鍵生成は、出力される鍵の確率分布に偏りを生じさせ、RSA 法の二つの素数がともに 3 mod 4 になるようにしても、機能的に互換でありえます。
•Probabilistic vs. deterministic signatures can be interchangeable if the client can verify them using the same algorithm, for each possible public key. For example, a probabilistic signature using secret randomness may, with respect to signature verifiability, be functionally interchangeable with a version that uses pseudo-randomness seeded with the secret key, but it is not equivalent since the distribution is altered. This difference is non-trivial for some applications, as it may, for example, be relevant for applications relying on determinism for recreating the signature. Still, when focused on verifiability a client with access to the verification key can verify signatures regardless of whether they came from the non-threshold scheme or the interchangeable threshold one.
•確率的署名と決定論的署名は、クライアントが、考えうる各公開鍵について同じアルゴリズムで検証できる場合、互換でありえます。たとえば、秘密の乱数を用いる確率的署名は、署名の検証可能性に関して、シークレット鍵をシードとする擬似乱数を用いる版と機能的に互換でありえますが、分布が変わるため同等ではありません。この違いは、署名の再作成に決定性を利用する応用など、一部の応用に関係する場合があります。それでも、検証可能性に着目すると、検証鍵にアクセスできるクライアントは、署名が非しきい値方式から来たものか、互換性のあるしきい値方式から来たものかにかかわらず、署名を検証できます。
Functional interchangeability is being considered with respect to honest executions, rather than as an assertion about security. However, for standardization the interest is to consider schemes that are secure with respect to defined properties (e.g., unforgeability) and/or ideal functionalities. Thus, a threshold scheme that is functionally interchangeable but not equivalent to some non-threshold primitive needs to have its security properties more carefully assessed in the new context. For example, while conditioning the primes of an RSA modulus to be 3 mod 4 may pose no security threat, there would be a problem if the primes were limited to a small set.
機能的互換性は、セキュリティに関する主張ではなく、正直な実行に関して検討されています。しかし標準化においては、定義された特性(例: 偽造不可能性)や理想機能、あるいはその両方に関してセキュアな方式を検討することに関心があります。したがって、ある非しきい値プリミティブと機能的に互換であっても同等ではないしきい値方式は、新しい文脈でそのセキュリティ特性をより慎重に評価する必要があります。たとえば、RSA 法の素数を 3 mod 4 に制約することはセキュリティ上の脅威にならないかもしれませんが、素数が小さな集合に限定されるなら問題が生じます。
It is important to consider interoperability when evaluating threshold schemes for standardization. Functional interchangeability is one useful notion, among other possibilities. Other scopes of interoperability may be considered as well. For example, deployment-wise it is relevant to consider how much of a client implementation can remain the same.
しきい値方式を標準化のために評価する際には、相互運用性を考慮することが重要です。機能的互換性は、他の可能性のなかの一つの有用な概念です。相互運用性のほかの範囲も考慮される場合があります。たとえば、展開の観点では、クライアントの実装のどれだけの部分を同じままにできるかを考慮することが重要です。
2.5 Auditability from a client viewpoint
2.5 クライアントの視点からの監査可能性
For the purposes of this document, a threshold scheme is called functionally auditable if the client can prove to a third party that the output of the cryptographic primitive was generated in a threshold manner. Examples:
本書の目的では、クライアントが、暗号プリミティブの出力がしきい値の方法で生成されたことを第三者に証明できる場合に、しきい値方式を機能的に監査可能と呼びます。例を挙げます。
•Additional data. Besides the information needed to reconstruct the intended output, the client may receive from each participant component of the threshold scheme a (PKI verifiable) signature of the output.
•追加のデータ。クライアントは、意図した出力を復元するために必要な情報に加えて、しきい値方式の各参加構成要素から、出力に対する(PKI で検証可能な)署名を受け取る場合があります。
•Multi-signatures. The public-keys of each participating signatory are combined into a single public-key for signature verification (e.g., functionally interchangeable with EdDSA), such that the public-key combination also enables later proving which independent signers participated in the signature. (This requires the infeasibility of finding two distinct sets of public keys that yield the same combined public key.)
•マルチ署名。参加する各署名者の公開鍵が、署名検証のための単一の公開鍵(例: EdDSA と機能的に互換)に結合され、その公開鍵の結合によって、どの独立した署名者が署名に参加したかを後から証明することも可能になります。(これには、同じ結合公開鍵になる異なる二つの公開鍵の集合を見つけることが計算上不可能であることが必要です。)
Orthogonality to the I/O interface. Although a shared-I/O mode may be auditable, the mode itself does not imply auditability. Even though a client uses secret-sharing, the client may remain unable to externally prove that a threshold computation took place. Conversely, a not-shared-IO mode may allow auditability, if the client receives complementary information (e.g., zero-knowledge proofs, or authenticated transcripts) that allow an external verification of the participation of multiple components with registered identities.
I/O インターフェースとの直交性。shared-I/O モードは監査可能でありえますが、モード自体が監査可能性を意味するわけではありません。クライアントが秘密分散を使っていても、しきい値計算が行われたことを外部に証明できないままである場合があります。逆に、not-shared-IO モードでも、クライアントが、登録された識別情報を持つ複数の構成要素の参加を外部から検証できるようにする補完的な情報(例: ゼロ知識証明や認証済みのトランスクリプト)を受け取る場合には、監査可能性を実現できる場合があります。
Compatibility with functional interchangeability. Depending on the details, it is possible that “auditability” and “functional interchangeability” are simultaneously achievable. For example, this happens if (i) there is audit-enabling metadata (which the client can decide to use or not), and (ii) the client can still extract from the received information an element that is functionally interchangeable with the corresponding non-threshold output.
機能的互換性との両立可能性。詳細によっては、「監査可能性」と「機能的互換性」が同時に達成可能な場合があります。たとえば、(i) 監査を可能にするメタデータ(クライアントが使うかどうかを決められるもの)があり、かつ (ii) クライアントが、受け取った情報から、対応する非しきい値の出力と機能的に互換な要素を取り出せる場合が、これに当たります。
Auditability may be a desirable feature for some use-cases, but it is not a necessary requirement. For example, a threshold deployment scenario may favor privacy of the identities of the threshold components, which in turn may be achievable to the detriment of auditability.
監査可能性は、一部のユースケースでは望ましい機能となりえますが、必須の要件ではありません。たとえば、しきい値の展開シナリオでは、しきい値の構成要素の識別情報のプライバシーを優先する場合があり、その結果、監査可能性を損なうことがあります。
3 Motivating applications
3 動機となる応用
The selection of items (primitive–mode) of interest for standardization should consider potential applications taking advantage of threshold schemes for cryptographic primitives. The consideration of applications can help foresee potential deployment scenarios and be useful to tailor future calls for contributions. It can also help characterize the set of stakeholders potentially interested in providing contributions to the standardization effort. Motivation may come from:
標準化の対象として関心のある項目(プリミティブ–モード)の選定では、暗号プリミティブのしきい値方式を活用する潜在的な応用を考慮すべきです。応用を考慮することは、潜在的な展開シナリオを見通す助けとなり、将来の貢献募集を調整するのに役立ちます。また、標準化の取り組みに貢献することに関心を持ちうる利害関係者の集合を特徴付けるのにも役立ちます。動機は、次のものから生じえます。
•Deployed applications making use of threshold schemes, despite lack of standards (or NIST standards). The development of new standards can promote best practices and interoperability in a field with already concretely demonstrated use-cases.
•しきい値方式を利用している展開済みの応用。標準(または NIST の標準)がなくても利用されています。新しい標準の策定は、すでに具体的に実証されたユースケースがある分野で、ベストプラクティスと相互運用性を促進できます。
•Potential applications whose deployment would be facilitated by new standards for threshold schemes. Particularly, for widely used NIST-approved cryptographic (key-based) primitives a default motivation for thresholdization is the ability to distribute trust across several operators.
•新しいしきい値方式の標準によって展開が容易になる潜在的な応用。特に、広く使われている NIST が承認した(鍵ベースの)暗号プリミティブについては、しきい値化の既定の動機は、複数の運用者に信頼を分散させる能力です。
A strong motivation for achieving threshold properties in a cryptosystem implementation is to reduce its susceptibility to single points of failure. These failures can often affect a combination of confidentiality, integrity, and availability. Correspondingly, threshold schemes can be designed to enhance a combination of properties, often with tradeoffs. Usually, some form of secret sharing or distributed key generation is employed in order to initially distribute trust, across multiple parties or components, on the protection of a secret. Other threshold schemes can then retain this distribution of trust while the shared key is used to perform cryptographic operations.
暗号システムの実装でしきい値特性を実現する強い動機は、単一障害点への脆弱性を減らすことです。こうした障害は、機密性、完全性、可用性の組み合わせに影響することがよくあります。それに応じて、しきい値方式は、多くの場合トレードオフを伴いながら、特性の組み合わせを強化するように設計できます。通常は、秘密の保護に関する信頼を、複数のパーティまたは構成要素に最初に分散させるために、何らかの形の秘密分散または分散鍵生成が用いられます。そのうえで、ほかのしきい値方式は、共有鍵を使って暗号操作を行う間、この信頼の分散を維持できます。
In the multi-party domain, the distribution of shares across multiple parties can enable removing single points of failure of various kinds. For example: of availability, by not requiring all parties to be present; of confidentiality, by requiring a greater number of colluding parties to find the key; and of integrity, by implementing robust techniques that detect and address faults from malicious parties.
マルチパーティの領域では、複数のパーティにシェアを分散させることで、さまざまな種類の単一障害点をなくせます。たとえば、可用性については、すべてのパーティの出席を求めないことで、機密性については、鍵を見つけるために、より多くのパーティが結託することを求めることで、完全性については、悪意あるパーティによる障害を検出して対処する堅牢な技術を実装することで、それぞれ単一障害点をなくせます。
In the single-device domain, the goal is also to prevent key-leakage, e.g., from exploitation by side-channel and fault-injection attacks, and can include improving integrity and availability. A threshold circuit design can prevent the secret key from being in an identifiable location, thereby making its leakage much more difficult. For example, certain exploits may then require collecting a number of traces that is exponential in the number of secret shares.
単一デバイスの領域でも、サイドチャネル攻撃やフォールトインジェクション攻撃による悪用などによる秘密鍵の漏えいを防ぐことが目標であり、完全性と可用性の改善を含むこともあります。しきい値による回路設計は、秘密鍵が特定可能な場所に存在しないようにできるため、その漏えいをはるかに難しくします。たとえば、特定のエクスプロイトでは、秘密シェアの数に対して指数関数的な数のトレースを収集する必要が生じる場合があります。
For the multi-party domain, the focus is on applications in the active model, where corrupted parties can deviate arbitrarily from the protocol specification. As such, it is relevant to consider enabling verification of correctness of a produced output (or contributed share). For the single-device domain there is also interest in exploring schemes with active security, but there is also value in developing passively secure schemes against key-leakage.
マルチパーティの領域では、攻撃を受けたパーティがプロトコルの仕様から任意に逸脱しうる能動モデルにおける応用に焦点を当てます。そのため、生成された出力(または提供されたシェア)の正しさの検証を可能にすることを検討することが重要です。単一デバイスの領域でも、能動的なセキュリティを備えた方式を探ることに関心がありますが、鍵の漏えいに対して受動的にセキュアな方式を開発することにも価値があります。
Appendix A describes potential application use-cases, such as single-device encryption resistant to side-channel attacks, protection of secrets at rest, trust decentralization for key generation and distribution, accountability and prevention of ill-intentioned operations, confidential communication, password authentication, and interacting hardware security modules.
付録 A では、サイドチャネル攻撃に耐える単一デバイスの暗号化、保存時の秘密の保護、鍵生成と鍵配布における信頼の分散、説明責任と悪意ある操作の防止、機密通信、パスワード認証、連携するハードウェアセキュリティモジュールなど、潜在的な応用のユースケースを説明します。
4 Standardization items to consider
4 検討すべき標準化項目
The development of standards for threshold schemes has a potential to improve best-practices in the implementation and operation of cryptographic primitives. However, the matter of deciding which items to standardize, which techniques to support them, and which new documents to emerge as standards, is a complex matter that requires careful ponderation and a participative process. In this process it is useful to identify commonalities and synergies that may ease the development of standards for a variety of items.
しきい値方式の標準の策定は、暗号プリミティブの実装と運用におけるベストプラクティスを改善する可能性があります。しかし、どの項目を標準化するか、それをどの技術で支えるか、どの新しい文書を標準として策定するかを決めることは複雑な問題であり、慎重な検討と参加を伴うプロセスが必要です。このプロセスでは、さまざまな項目の標準策定を容易にしうる共通点と相乗効果を特定することが有用です。
This section describes at a high level some technical aspects required for threshold schemes for some primitives and modes being pondered for standardization. Since the two domains (multi-party and single-device) correspond to substantially different implementation scenarios, their corresponding standardization processes are referred to as different tracks. Furthermore, within each domain there are issues that potentially differentiate items in terms of being considered simple vs. more complex, which in turn hints at different standardization timelines and paths.
本節では、標準化が検討されている一部のプリミティブとモードについて、しきい値方式に必要な技術的側面を大局的に説明します。二つの領域(マルチパーティと単一デバイス)は、実装シナリオが大きく異なるため、それぞれに対応する標準化プロセスを別々のトラックと呼んでいます。さらに、各領域には、項目を単純とみなすかより複雑とみなすかという点で区別されうる課題があり、それが標準化のスケジュールと経路の違いを示唆します。
The initial emphasis is on obtaining threshold versions of NIST-approved conventional primitives. Some threshold schemes may originate from simple well-defined techniques, already based on properties of the underlying cryptographic primitive. Other cases may require more complex techniques, e.g., generation, use and verification of correlated-randomness in the single-device domain, and building blocks from secure multiparty computation in the multi-party domain.
当初の重点は、NIST が承認した従来のプリミティブのしきい値版を得ることにあります。一部のしきい値方式は、基盤となる暗号プリミティブの特性にすでに基づいた、単純で明確に定義された技術から生まれる場合があります。そのほかのケースでは、より複雑な技術が必要になる場合があり、たとえば単一デバイスの領域では相関する乱数性の生成、使用、検証、マルチパーティの領域ではセキュアマルチパーティ計算の構成要素が挙げられます。
Section 4.1 and Section 4.2 leave out of scope some trivial threshold schemes, such as those based solely on trivial concatenation (e.g., of signatures), or nesting (e.g., of encryption, in a cascade mode), or of repetition from multiple implementations of approved conventional primitives implemented with independent keys. Conversely, a related but within scope case is that of multi-signatures, which, despite being usable in a setting with multiple independent (public/private) keys pairs, enable producing concise signatures with size independent of the number of participants.
第 4.1 節と第 4.2 節では、単純な連結(例: 署名の連結)や入れ子(例: カスケードモードでの暗号化)だけに基づくもの、あるいは独立した鍵で実装された承認済みの従来のプリミティブを複数の実装から繰り返すものなど、一部の自明なしきい値方式を対象範囲外としています。逆に、関連はするが対象範囲内のケースとしてマルチ署名があり、これは、複数の独立した(公開鍵/秘密鍵)ペアがある設定で使用できる一方で、参加者の数に依存しないサイズの簡潔な署名を生成できます。
The set of items identified ahead is not assumed to be exhaustive.
以下で特定する項目の集合が網羅的であるとは想定していません。
4.1 Multi-party track
4.1 マルチパーティのトラック
4.1.1 Simpler cases
4.1.1 より単純なケース
4.1.1.1 RSA signing.
4.1.1.1 RSA 署名
The essential challenge for producing a threshold RSA signature is in thresholdizing the modular exponentiation, which needs the secret key and the hashed-and-encoded plaintext as input. The hashing-and-encoding can be performed by the client, by a proxy, or (if it is not a problem to leak the clear plaintext) by the components of the threshold entity. The focus is on obtaining a not-shared-IO mode. There is also interest in considering the shared-I mode, in which case the client would secret-share the hashed-and-encoded the plaintext. (These two modes are considered of interest for all upcoming mentioned signing primitives.)
しきい値 RSA 署名を生成するうえでの本質的な課題は、秘密鍵と、ハッシュ化およびエンコードされた平文を入力として必要とするべき乗剰余演算をしきい値化することにあります。ハッシュ化とエンコードは、クライアント、プロキシ、または(平文をそのまま漏えいしても問題がない場合には)しきい値エンティティの構成要素が行うことができます。焦点は、not-shared-IO モードを得ることにあります。shared-I モードを検討することにも関心があり、その場合、クライアントは平文をハッシュ化およびエンコードしたものを秘密分散することになります。(これら二つのモードは、以降に挙げるすべての署名プリミティブにとって関心のあるものと考えられます。)
4.1.1.2 RSA decryption.
4.1.1.2 RSA 復号
The primitive is similar to RSA signing, except that the input is a ciphertext and the output is a (possibly encoded) plaintext. There is a default interest in the not-shared-IO mode. Since the plaintext is the usual object of confidentiality concern, for the decryption operation it may also be relevant to consider the shared-O mode, i.e., as an enhanced way of preventing leakage of sensitive data.
このプリミティブは、入力が暗号文で、出力が(エンコードされている可能性のある)平文である点を除き、RSA 署名に似ています。既定では not-shared-IO モードに関心があります。平文は機密性に関する通常の懸念の対象であるため、復号操作では、機微なデータの漏えいを防ぐ強化された方法として、shared-O モードを検討することも重要になりえます。
4.1.1.3 EdDSA signing.
4.1.1.3 EdDSA 署名
The EdDSA1 is a deterministic variant of the Schnorr signature. There are probabilistic Schnorr signatures that can be easily thresholdized, in a simultaneously auditable and functionally interchangeable manner, with the signature being similar in syntax to an original non-threshold signature, and with the verification key depending on the set of participating signers for each signature. The concrete (deterministic) EdDSA replaces the randomness by a hash of the concatenation of the secret signing key and the message being signed. Thus, a threshold version of this EdDSA signature requires distributed hashing, where the hash function needs to be a NIST-approved function within the Secure Hash Algorithm (SHA) families SHA2 or SHA3. (Note: In the “HashEdDSA” version, the pre-computed hash of the message, instead of the possibly longer message, is used as input to the distributed hashing in a threshold implementation.) This is significantly costly to do in a distributed way for SHA2 or SHA3. This creates a technical difficulty (substantial inefficiency) for achieving a corresponding functionally equivalent threshold mode, compared to what would be possible for a probabilistic signature. This may either imply a more complex path of standardization, or additional possible considerations about the exact intended threshold mode.
EdDSA1 は、Schnorr 署名の決定論的な変種です。簡単にしきい値化できる確率的な Schnorr 署名があり、これは、監査可能で、かつ機能的に互換な形で実現でき、署名の構文は元の非しきい値の署名と似ており、検証鍵は署名ごとの参加署名者の集合に依存します。具体的な(決定論的な)EdDSA は、乱数性を、署名用秘密鍵と署名対象メッセージを連結したもののハッシュに置き換えます。したがって、この EdDSA 署名のしきい値版には分散ハッシュが必要であり、そのハッシュ関数は、Secure Hash Algorithm(SHA)ファミリーの SHA2 または SHA3 に含まれる、NIST が承認した関数でなければなりません。(注: 「HashEdDSA」版では、しきい値による実装での分散ハッシュへの入力として、場合によってはより長いメッセージの代わりに、事前に計算されたメッセージのハッシュを使用します。)SHA2 や SHA3 を分散して行うには、かなりのコストがかかります。このため、確率的署名で可能なことと比べて、対応する機能的に互換なしきい値モードを実現するうえで、技術的な困難(大幅な非効率)が生じます。これは、標準化の経路がより複雑になることを意味する場合もあれば、意図するしきい値モードそのものについて追加の考慮が必要になる可能性を意味する場合もあります。
4.1.1.4 Key generation for elliptic curve cryptography (ECC).
4.1.1.4 楕円曲線暗号(ECC)の鍵生成
For EdDSA and ECDSA signatures, the secret key is a multiplicative factor (in elliptic curve notation) that operates on the public generator to produce the public key. Secret keys for the mentioned elliptic-curve signatures can be easily generated from independent random shares. To ensure that each party ends with an actual random share, the distributed key generation may also include multiparty coin-flipping and commitments to the shares held by every party. The consideration of threshold techniques for key generation for ECC should take into account the NIST recommendations (e.g., SP 800-186) on parameters acceptable for elliptic curves.
EdDSA と ECDSA の署名では、秘密鍵は、(楕円曲線の表記では)公開の生成元に作用して公開鍵を生成する乗法的な因子です。これらの楕円曲線署名の秘密鍵は、独立した乱数のシェアから簡単に生成できます。各パーティが最終的に実際の乱数シェアを持つことを保証するために、分散鍵生成には、マルチパーティのコイン投げと、各パーティが保持するシェアへのコミットメントも含まれる場合があります。ECC の鍵生成におけるしきい値の技術を検討する際は、楕円曲線として許容されるパラメーターに関する NIST の推奨事項(例: SP 800-186)を考慮に入れるべきです。
4.1.1.5 Pair-Wise Key-Establishment Schemes Using ECC.
4.1.1.5 ECC を用いたペアワイズ鍵確立方式
Pair-wise key agreement is a fundamental tool for many two-party protocols. There are simple techniques to achieve it, such as those described in SP 800-56A based on discrete-log cryptography. These can be based on operations over elliptic curves, which may be easy to thresholdize due to inherent homomorphic group operations. Even though key-agreement is a protocol with more than one party, its thresholdization is considered per party, with respect to the operations with secret keys. For example, in an ECC Cofactor Diffie-Hellman (ECC-CDH) key agreement, the basic building block is simply a “multiplication” with a secret key (the equivalent of an “exponentiation” if done under integer finite-fields). With respect to homomorphic properties this is somewhat similar to the RSA threshold case, but with the simpler setting of a known group order.
ペアワイズ鍵合意は、多くの二者間プロトコルの基本的なツールです。離散対数暗号に基づく SP 800-56A で説明されているものなど、これを実現する単純な技術があります。これらは楕円曲線上の演算に基づくことができ、群演算が本来的に準同型であるため、しきい値化しやすい場合があります。鍵合意は複数のパーティが関わるプロトコルですが、そのしきい値化は、秘密鍵を用いる演算に関して、パーティごとに検討されます。たとえば、ECC Cofactor Diffie-Hellman(ECC-CDH)鍵合意では、基本的な構成要素は、秘密鍵による単純な「乗算」(整数の有限体上で行う場合の「べき乗」に相当するもの)です。準同型の特性という点では、これは RSA のしきい値の場合にいくらか似ていますが、群の位数が既知というより単純な設定です。
4.1.2 More complex cases
4.1.2 より複雑なケース
4.1.2.1 RSA key-generation.
4.1.2.1 RSA 鍵生成
Threshold modes of interest for RSA key-generation require multiple parties jointly computing a public modulus without any threshold set learning anything secret about the prime factors, along with all of the parties learning secret shares of the secret decryption/signing key \(d\). This can be achieved based on secure multi-party computation, and there are implementations that demonstrate its feasibility.
RSA 鍵生成で関心のあるしきい値モードでは、複数のパーティが、どのしきい値の集合も素因数に関する秘密情報を学習しないようにしながら、公開法を共同で計算するとともに、すべてのパーティが復号・署名用秘密鍵 \(d\) のシェアを得ることが求められます。これはセキュアマルチパーティ計算に基づいて実現でき、その実現可能性を示す実装があります。
4.1.2.2 ECDSA signature.
4.1.2.2 ECDSA 署名
A technical difficulty in threshold ECDSA is jointly computing a secret sharing of a multiplicative inverse of an additively-shared secret value. This is less straightforward than a simple homomorphic computation (e.g., as in the case of threshold RSA), but it can, nonetheless, be feasibly performed based on state-of-the-art techniques. There is interest in the not-shared-IO mode, possibly simultaneously auditable. Being a signature, the shared-I mode may also be of interest.
しきい値 ECDSA の技術的な困難は、加法的に共有されたシークレット値の乗法的な逆元の秘密分散を、共同で計算することにあります。これは、(しきい値 RSA の場合のような)単純な準同型の計算ほど簡単ではありませんが、それでも最先端の技術に基づいて実現可能です。not-shared-IO モードに関心があり、場合によっては同時に監査可能なものです。署名であるため、shared-I モードにも関心が持たれる場合があります。
4.1.2.3 AES enciphering and deciphering.
4.1.2.3 AES の暗号化と復号
The mathematical structure of the AES S-Box (the non-linear component of AES) does not provide homomorphic properties enabling an easy thresholdization in the multi-party setting. Nonetheless, threshold versions can be implemented based on techniques of secure multiparty computation. Threshold versions of enciphering and deciphering can be of interest in the shared-I and shared-O modes, respectively. Both primitives can also be relevant in a not-shared-IO mode.
AES の S-Box(AES の非線形の構成要素)の数学的構造は、マルチパーティの設定で容易にしきい値化できるような準同型の特性を備えていません。それでも、しきい値版は、セキュアマルチパーティ計算の技術に基づいて実装できます。暗号化と復号のしきい値版は、それぞれ shared-I モードと shared-O モードで関心が持たれる場合があります。どちらのプリミティブも、not-shared-IO モードで関係する場合もあります。
4.2 Single-device track
4.2 単一デバイスのトラック
Historically, cryptographic algorithms were implemented in hardware devices long before cryptography appeared in software. As software cryptographic implementations started to dominate the mainstream technology used at home and the office, people again turned to hardware for acceleration and security. For example, AES instructions and SHA extensions were provided on Intel x86, AMD and ARM processors. More recently, as the complexity of single-chip devices increased and the emergence of Systems on a Chip (SoC) technology became mainstream, more complete implementations of cryptographic capabilities appeared in hardware. For example, there has been a rapid and accelerating growth of Field Programmable Gate Arrays (FPGA) devices in recent years in response to existing and emerging computational needs in different domains, including deep learning and artificial intelligence. Consequently, the FPGA platform can be used as both an accelerator for cryptographic algorithms and as a host platform with cryptographic capabilities intended to protect the intellectual property of the customization logic programmed on the platform.
歴史的には、暗号アルゴリズムは、暗号がソフトウェアに現れるよりもずっと前から、ハードウェアデバイスに実装されていました。ソフトウェアによる暗号の実装が、家庭やオフィスで使われる主流の技術を占めるようになると、人々は高速化とセキュリティのために再びハードウェアに目を向けました。たとえば、AES 命令と SHA 拡張が、Intel x86、AMD、および ARM のプロセッサで提供されました。さらに最近では、シングルチップデバイスの複雑さが増し、System on a Chip(SoC)技術の登場が主流になるにつれて、暗号機能のより完全な実装がハードウェアに現れました。たとえば、ディープラーニングや人工知能を含むさまざまな領域の、既存および新たな計算ニーズに応えて、近年、Field Programmable Gate Array(FPGA)デバイスが急速に、かつ加速度的に成長しています。その結果、FPGA プラットフォームは、暗号アルゴリズムのアクセラレーターとして、また、プラットフォーム上でプログラムされたカスタマイズロジックの知的財産を保護するための暗号機能を備えたホストプラットフォームとして、どちらにも利用できます。
One of the most widely implemented algorithms in hardware is AES. At the same time, it is well-known that hardware implementations of cryptographic algorithms, AES in particular, bring specific security challenges to the table. Side channel leakage has been a difficult problem for hardware manufacturers over the years. In practice, the hardware industry relies on empirical and expensive techniques to mitigate the potential leakage weakness of cryptographic algorithm hardware implementations. There is a significant industry need for implementing AES in a way that provides better mitigation of side-channel leakage in hardware.
ハードウェアで最も広く実装されているアルゴリズムの一つが AES です。同時に、暗号アルゴリズム、特に AES のハードウェア実装には、特有のセキュリティ上の課題があることはよく知られています。サイドチャネルの漏えいは、長年にわたってハードウェア製造者にとって難しい問題でした。実際には、ハードウェア業界は、暗号アルゴリズムのハードウェア実装における潜在的な漏えいの弱点を緩和するために、経験的で高価な技術に頼っています。ハードウェアにおけるサイドチャネルの漏えいをより適切に緩和する方法で AES を実装することについては、産業界に大きなニーズがあります。
4.2.1 Simpler cases
4.2.1 より単純なケース
4.2.1.1 AES enciphering with masked input.
4.2.1.1 マスクされた入力による AES 暗号化
Leakage resilience can be achieved based on masking techniques for generic Boolean circuits. This involves a secret-sharing of the input key material so that each wire or register only “sees” a share, and never an actual secret bit. Furthermore, the protection needs to be propagated across the circuit path, in order to prevent leakage of sensitive internal states of the computation. Under certain attack models, the number of side-channel traces that need to be collected is exponential in the number of shares. It is pertinent to consider how many traces (e.g., up to several million) a feasible adversary is expected to be able to collect, in order to successfully perform, for example, a partial-key recovery.
漏えい耐性は、汎用のブール回路に対するマスキング技術に基づいて実現できます。これには、入力された鍵素材を秘密分散して、各配線またはレジスタがシェアだけを「見る」ようにし、実際のシークレットのビットは決して見ないようにすることが含まれます。さらに、計算の機微な内部状態の漏えいを防ぐために、保護を回路の経路全体に伝播させる必要があります。特定の攻撃モデルでは、収集する必要のあるサイドチャネルのトレースの数は、シェアの数に対して指数関数的です。たとえば部分鍵の復元に成功するために、実行可能な敵対者が何本のトレース(例: 数百万本まで)を収集できると見込まれるかを検討することが適切です。
4.2.1.2 Distributed random number generation.
4.2.1.2 分散乱数生成
Randomness is fundamental for masking techniques. If only one randomness source is available, then that becomes an attackable single-point of failure. Therefore, there is interest in exploring circuit implementations that are able to leverage multiple on-chip sources of randomness and combine them in a threshold manner.
乱数性は、マスキング技術の基本です。利用できる乱数源が一つだけであれば、それが攻撃可能な単一障害点になります。したがって、チップ上の複数の乱数源を活用し、それらをしきい値の方法で組み合わせることができる回路実装を探ることに関心があります。
4.2.1.3 Others.
4.2.1.3 その他
As a use-case for threshold circuit design, the initial phase of this project is comparatively more focused on AES. Nonetheless, it is foreseeable that the insights gained in developing guidelines for the implementation and validation of threshold circuit designs for AES may also be applicable to other symmetric-key cryptographic algorithms, e.g., a hash-based message authentication code (HMAC). Public-key cryptography is also implemented in single devices, and for some particular schemes, it is possible to enhance side-channel resistance by using masking-type techniques. For example, an approach may be to ensure that some repeated operation (e.g., an exponentiation) sensitive to side-channel attacks (e.g., timing attacks) does not operate on the actual secret as input.
しきい値回路設計のユースケースとして、このプロジェクトの初期段階では、比較的 AES により焦点を当てています。それでも、AES のしきい値回路設計の実装と検証のガイドラインを策定するなかで得られた知見は、ハッシュベースのメッセージ認証コード(HMAC)など、ほかの共通鍵暗号アルゴリズムにも適用できる可能性が見込まれます。公開鍵暗号も単一デバイスに実装されており、特定の方式については、マスキング型の技術を用いてサイドチャネル耐性を高めることが可能です。たとえば、あるアプローチは、サイドチャネル攻撃(例: タイミング攻撃)に対して脆弱な繰り返し演算(例: べき乗)が、実際のシークレットを入力として動作しないようにすることでしょう。
4.2.2 More complex cases
4.2.2 より複雑なケース
4.2.2.1 Actively secure AES enciphering.
4.2.2.1 能動的にセキュアな AES 暗号化
Beyond passive security, it is desirable to develop resistance against combined attacks (side-channel and injected faults). An active adversary may, for example, be able to inject a certain number of faults (e.g., controlled or random value in a certain number of controlled locations) in some data unit (e.g., bit or byte), and may be able to collect numerous execution traces (e.g., up to several million). Thwarting these attacks may involve more sophisticated techniques (e.g., producing and distributing correlated randomness, and verifying it), and is, therefore, considered more complex. Ways of achieving this include cryptographic checksums (such as message authentication codes), whose result cannot be predicted by an adversary with only a partial view of the internal state. To be pertinent these schemes should be demonstrably better than a simple redundant execution of the circuit computation.
受動的なセキュリティを超えて、複合的な攻撃(サイドチャネル攻撃とフォールト注入)への耐性を開発することが望まれます。能動的な敵対者は、たとえば、あるデータ単位(例: ビットやバイト)に、一定数のフォールト(例: 制御された一定数の箇所に制御された値またはランダムな値)を注入し、多数の実行トレース(例: 数百万本まで)を収集できる可能性があります。これらの攻撃を阻止するには、より高度な技術(例: 相関する乱数性の生成と配布、およびその検証)が必要になる場合があり、したがって、より複雑であると考えられます。これを実現する方法には、内部状態の一部しか見えない敵対者には結果を予測できない、暗号チェックサム(メッセージ認証コードなど)があります。適切な方式とするには、回路計算を単純に冗長実行する場合より優れていることを実証すべきです。
5 Features of standardization items
5 標準化項目の特徴
The previous section enumerated several examples of possible standardization items at a high-level (domain–primitive–mode). However, an actual process of standardization will require taking into consideration factors such as validation suitability (Section 5.1), configurability and security features (Section 5.2), and modularity (Section 5.3).
前節では、標準化項目の候補となりうるいくつかの例を、大局的に(領域–プリミティブ–モードで)列挙しました。しかし、実際の標準化のプロセスでは、検証への適合性(第 5.1 節)、構成可能性とセキュリティ機能(第 5.2 節)、モジュール性(第 5.3 節)といった要因を考慮する必要があります。
5.1 Validation suitability
5.1 検証への適合性
The process of standardizing new threshold schemes entails devising corresponding testing and validation requirements, which may differ from those for conventional implementations. This applies both to validation of modules and validation of the algorithms therein. Therefore, the validation framework should be looked at to consider which/whether extensions may be useful to accommodate a feasible validation of implementations of threshold schemes. Ideally, the proposed test and certification procedures should integrate with hardware and software development processes, clarifying which security levels they achieve.
新しいしきい値方式を標準化するプロセスには、対応する試験と検証の要件を策定することが伴い、それは従来の実装に対するものとは異なる場合があります。これは、モジュールの検証と、そこに含まれるアルゴリズムの検証の両方に当てはまります。したがって、しきい値方式の実装を現実的に検証できるようにするために、どのような拡張が有用でありうるか、あるいは拡張が有用か否かを検討するため、検証の枠組みを見直すべきです。理想的には、提案する試験と認証の手順は、ハードウェアおよびソフトウェアの開発プロセスに統合され、それらが達成するセキュリティレベルを明確にするものであるべきです。
Validation of modules. FIPS 140-2 and FIPS 140-3 (similarly, ISO/IEC 19790:2012(E)) are security standards for cryptographic modules. They mandate the use of NIST-approved cryptographic primitives, referenced in Annexes to these standards in the cryptographic modules validated under them. The testing of the algorithm primitives is delegated to the Cryptographic Algorithm Validation Program (CAVP) as a prerequisite for module validation. In addition, FIPS 140-3 introduces requirements for side-channel leakage testing in its Annex F. These requirements are particularly important for single-chip implementations of threshold-schemes for cryptographic primitives, especially for block ciphers (Section 4.2).
モジュールの検証。FIPS 140-2 と FIPS 140-3(同様に ISO/IEC 19790:2012(E))は、暗号モジュールのセキュリティ標準です。これらは、それらの下で検証される暗号モジュールにおいて、これらの標準の附属書で参照されている、NIST が承認した暗号プリミティブの使用を義務付けています。アルゴリズムプリミティブの試験は、モジュール検証の前提条件として、Cryptographic Algorithm Validation Program(CAVP)に委ねられています。加えて、FIPS 140-3 は、その附属書 F で、サイドチャネル漏えい試験の要件を導入しています。これらの要件は、暗号プリミティブのしきい値方式の、特にブロック暗号の、シングルチップ実装にとって特に重要です(第 4.2 節)。
Validation of algorithms. The CAVP is established by NIST to validate the algorithm primitives used in modules. The CAVP uses automated tests based on the known-answer testing methodology. These tests try to assess the correctness and robustness of the implementation with emphasis currently given to the former.
アルゴリズムの検証。CAVP は、モジュールで使われるアルゴリズムプリミティブを検証するために NIST が設置したものです。CAVP は、既知解テストの方法論に基づく自動化されたテストを使用します。これらのテストは、実装の正しさと堅牢性を評価しようとするもので、現在は前者に重点が置かれています。
In a typical scenario, one of the two participating parties (the NIST validation server and the client with an algorithm implementation under testing) using the Automated Cryptographic Validation Protocol (ACVP) sends to the other the pre- and post-conditions for a specific test of an implementation of a cryptographic algorithm. The other party performs the same test with the received pre-conditions on an independently developed implementation of the same algorithm and verifies that the post-conditions are the same. Going forward, the CAVP is working on enhancing the depth and coverage of algorithm tests to cover a bigger portion of the security assertions contained in any of the cryptographic primitive standards (e.g., digital signatures (FIPS 186) and AES (FIPS 197)).
典型的なシナリオでは、Automated Cryptographic Validation Protocol(ACVP)を使用する二つの参加パーティ(NIST の検証サーバーと、試験対象のアルゴリズム実装を持つクライアント)の一方が、暗号アルゴリズムの実装の特定のテストの事前条件と事後条件を、もう一方に送ります。もう一方のパーティは、受け取った事前条件を用いて、同じアルゴリズムの独立に開発された実装で同じテストを実行し、事後条件が同じであることを検証します。今後、CAVP は、暗号プリミティブの標準(例: デジタル署名(FIPS 186)や AES(FIPS 197))のいずれかに含まれるセキュリティアサーションのより多くの部分を網羅できるよう、アルゴリズムテストの深さと網羅範囲を強化する作業を進めています。
5.2 Configurability and security features
5.2 構成可能性とセキュリティ機能
Some important configuration details and security features need to be considered in the phases of defining criteria for calls for contribution, and their evaluation/comparison. These details and features may also depend on the considered application scenarios.
貢献募集の基準を定義する段階と、その評価・比較の段階では、いくつかの重要な構成の詳細とセキュリティ機能を考慮する必要があります。これらの詳細と機能は、検討する応用シナリオにも依存する場合があります。
5.2.1 Threshold numbers
5.2.1 しきい値の数
It is important to identify the proportion of dishonest parties (e.g., dishonest minority, all-but-one dishonest) that is allowed for each security property of interest, and whether threshold values are static or dynamic. For example, threshold schemes are typically based on some kind of \(k\)-out-of-\(n\) secret sharing, possibly with variable \(k\) and \(n\) across the lifetime of the scheme. The parameter \(k\) may imply different thresholds for different properties. Particular cases may also be relevant, such as the special case of \(n\)-out-of-\(n\) case with static \(n\), especially when significantly more efficient.
関心のあるセキュリティ特性ごとに、許容される不正なパーティの割合(例: 不正なパーティが少数派、一つを除いてすべてが不正)と、しきい値が静的か動的かを特定することが重要です。たとえば、しきい値方式は通常、何らかの \(k\)-out-of-\(n\) の秘密分散に基づいており、方式の存続期間を通じて \(k\) と \(n\) が変化する場合もあります。パラメーター \(k\) は、特性ごとに異なるしきい値を意味する場合があります。静的な \(n\) による \(n\)-out-of-\(n\) の特殊なケースなど、特定のケースも、特にはるかに効率的な場合には、関係してくる可能性があります。
5.2.2 Rejuvenation of components
5.2.2 構成要素のリジュビネーション
In several application settings of threshold schemes, the ability to support the rejuvenation of components is essential. Rejuvenations can be proactive or reactive, and parallel or sequential. For reactive rejuvenations the system needs to be capable of some kind of intrusion detection. In particular, the recovery may be more efficient if the detection is accompanied by the ability to identify the misbehaving components. In the multi-party domain, a rejuvenation may include an actual replacement of a physical machine, or the rebooting of a virtual machine with corresponding onboarding of its state. In the single-device setting this may involve redoing a secret sharing of an encryption key. Forward secrecy is one property of interest that can be related to rejuvenations. In some settings, past actions may remain secured (e.g., with respect to confidentiality) even if the threshold assumption is broken at a point in time.
しきい値方式の複数の応用の設定では、構成要素のリジュビネーションをサポートする能力が不可欠です。リジュビネーションには、事前対応型と事後対応型、並列型と逐次型があります。事後対応型のリジュビネーションでは、システムに何らかの侵入検知の能力が必要です。特に、検知に、不正な動作をする構成要素を特定する能力が伴っていれば、復旧がより効率的になる場合があります。マルチパーティの領域では、リジュビネーションには、物理マシンの実際の交換や、仮想マシンの再起動とそれに伴う状態のオンボーディングが含まれる場合があります。単一デバイスの設定では、暗号化鍵の秘密分散をやり直すことが含まれる場合があります。前方秘匿性は、リジュビネーションに関連しうる、関心のある特性の一つです。設定によっては、ある時点でしきい値の前提が破られても、過去の行動は(たとえば機密性に関して)保護されたままである場合があります。
5.2.3 Advanced security properties
5.2.3 高度なセキュリティ特性
A meaningful assertion of security for a threshold scheme depends greatly on the applicability of the underlying model, on the environmental conditions in which a scheme is implemented, and on what happens when assumptions are violated. Therefore, when devising, evaluating, and comparing possible threshold schemes for standardization, it is important to consider to what extent the schemes need to satisfy certain properties and/or have new requirements.
しきい値方式についての意味のあるセキュリティの主張は、基盤となるモデルの適用可能性、方式が実装される環境条件、および前提が破られたときに何が起こるかに大きく左右されます。したがって、標準化の対象となりうるしきい値方式を策定、評価、比較する際には、方式がどの程度まで特定の特性を満たす必要があるか、あるいは新たな要件を持つ必要があるか、またはその両方を検討することが重要です。
•Composability. In what way does security remain when the scheme is composed with other protocols, including in concurrent executions, possibly depending on the actual instantiation of a required trusted setup?
•合成可能性。方式が他のプロトコルと合成された場合(並行実行を含む)に、必要な信頼されたセットアップの実際のインスタンス化にも左右されうる形で、どのようにセキュリティが維持されますか。
•Adaptive security. Is the adversary allowed to observe the protocol execution before deciding which components to corrupt?
•適応的セキュリティ。敵対者は、どの構成要素を侵害するかを決める前に、プロトコルの実行を観察することが許されますか。
•Graceful degradation. Is there a controlled vs. uncontrolled breakdown as soon as the threshold number of corruptions is surpassed?
•段階的な縮退。侵害された構成要素の数がしきい値を超えた時点で、制御された破綻と制御されない破綻のどちらが生じますか。
•Termination options. How is the scheme characterized in terms of termination, e.g., with respect to fairness, guaranteed output delivery and identifiable abort?
•終了のオプション。方式は、終了について、たとえば公平性、出力配送の保証、特定可能な中断の観点から、どのように特徴付けられますか。
•Cryptographic assumptions. Of the cryptographic and/or setup assumptions required by the threshold scheme, which ones (if any) differ (e.g., stronger and/or incomparable) from those of the original scheme? It is important to assess how the potential break of assumptions may jeopardize security in comparison with the original (1-out-of-1) scheme.
•暗号の前提。しきい値方式が必要とする暗号の前提やセットアップの前提のうち、元の方式のものと異なるもの(例: より強い、あるいは比較できない)があれば、それはどれか。前提が破られる可能性が、元の(1-out-of-1 の)方式と比べて、セキュリティをどのように危うくしうるかを評価することが重要です。
•New properties. The set of security properties to be required from threshold schemes can be more complex than with the corresponding conventional schemes, and may require some redefinition. For example, in an indistinguishability game for decryption, one may have to count adversarial queries made by isolated components, even if those are then not part of an actual decryption. As another example, in a multi-signature scheme one needs to require the infeasibility of finding two distinct sets of secret keys that yield the same combined public verification key.
•新しい特性。しきい値方式に求められるセキュリティ特性の集合は、対応する従来の方式よりも複雑になる可能性があり、何らかの再定義が必要になる場合があります。たとえば、復号の識別不能性ゲームでは、孤立した構成要素が行った敵対者のクエリを、それらが実際の復号の一部にならない場合でも数える必要があるかもしれません。別の例として、マルチ署名方式では、同じ結合検証公開鍵を生成する異なる二つの署名用秘密鍵の集合を見つけることが計算上困難であることを求める必要があります。
Other aspects. All aspects of implementation and application should be considered carefully when proposing the use of a threshold scheme. For example, a relevant concern in the execution of cryptographic primitives is determining the allowed scope of use of a secret key, such as whether it may be limited to signing only vs. decryption only.
その他の側面。しきい値方式の使用を提案する際には、実装と応用のあらゆる側面を慎重に検討すべきです。たとえば、暗号プリミティブの実行に関する懸念の一つは、秘密鍵の許容される使用範囲を決めることです。たとえば、署名のみに、または復号のみに制限してもよいかどうかです。
5.3 Modularity
5.3 モジュール性
The complex process of developing standards for threshold schemes can benefit from a modular approach at diverse levels. Upcoming standards should have the ability to share commonalities, and be flexible to enable appropriate solutions in a context of continuous innovation. Optimally, their building blocks can also be a useful basis for subsequent developments, without detriment to the effectiveness and credibility of each standard during its validity period. The process of standardizing multiple threshold schemes should consider appropriate tradeoffs of construction complexity (from building blocks to complex compositions) and specification detail (from security definitions to concrete instantiations). Figure 3 represents the abstract states and alternative paths of the evolution process, toward obtaining standardized threshold schemes that are concrete and provably secure instantiations of compositions of well-understood building blocks. The figure shows four symbolic quadrants, explained below.
しきい値方式の標準を策定する複雑なプロセスは、さまざまな水準でのモジュール的なアプローチから恩恵を受けられます。今後の標準は、共通点を共有できるとともに、絶え間ない革新の文脈で適切な解決策を可能にするよう柔軟であるべきです。最適な場合には、その構成要素は、各標準の有効期間中の有効性と信頼性を損なうことなく、その後の開発の有用な基盤にもなりえます。複数のしきい値方式を標準化するプロセスでは、構築の複雑さ(構成要素から複雑な合成まで)と仕様の詳細度(セキュリティの定義から具体的なインスタンス化まで)の適切なトレードオフを考慮すべきです。図 3 は、よく理解された構成要素の合成の、具体的で証明可能にセキュアなインスタンス化である、標準化されたしきい値方式を得るための、進化プロセスの抽象的な状態と代替経路を表しています。この図は、四つの象徴的な象限を示しており、以下で説明します。
5.3.1 Security definitions of building blocks (Q1)
5.3.1 構成要素のセキュリティ定義(Q1)
Reference definitions of abstract gadgets (e.g., secret sharing and commitment schemes) can be reused across various threshold schemes, promoting interoperability and alleviating redundant redefinitions. This allows a more modular/compositional description of complex protocols. When incorporating a gadget into a standard for the first time, the gadget should have a well-defined interface specified in that standard. This makes it possible that future standards refer to such descriptions based only on the corresponding interface and security properties. Some other examples of gadgets may include consensus, generation of correlated randomness, reliable broadcast, oblivious transfer, and garbled circuits. Their treatment as modules alleviates the burden of compiling from scratch arguments about the security of a more complex concrete protocol based on them, provided that composability properties are taken into consideration.
抽象的なガジェット(例: 秘密分散やコミットメント方式)の参照定義は、さまざまなしきい値方式で再利用でき、相互運用性を促進し、冗長な再定義を軽減します。これにより、複雑なプロトコルを、よりモジュール的/合成的に記述できます。ガジェットを最初に標準に組み込む際には、そのガジェットは、その標準で規定された明確に定義されたインターフェースを持つべきです。これにより、将来の標準が、対応するインターフェースとセキュリティ特性だけに基づいて、そうした記述を参照できるようになります。ガジェットのそのほかの例には、コンセンサス、相関する乱数性の生成、信頼できるブロードキャスト、オブリビアス転送、ガーブル回路などがあります。これらをモジュールとして扱うことで、合成可能性の特性が考慮されている限り、それらに基づくより複雑な具体的プロトコルのセキュリティについての議論を、一から組み立てる負担が軽減されます。
In a similar vein, it can be useful to identify the basic arithmetic operations (e.g., modular exponentiation, ECC point multiplication and generation of random numbers) that may be common across multiple threshold schemes (e.g., within DLC and IFC), as well as the techniques to implement them in a way that offers some resistance to side-channel attacks.
同様に、複数のしきい値方式(例: DLC と IFC の中)にわたって共通しうる基本的な算術演算(例: べき乗剰余、ECC の点の乗算、乱数の生成)と、それらを、サイドチャネル攻撃に対してある程度の耐性を持つ形で実装する技術を特定することも有用です。
2軸の図です。縦軸は「Construction complexity」(構成の複雑さ)で、下半分が「Building blocks (gadgets)」(構成部品、ガジェット)、上半分が「Complex compositions」(複雑な組み合わせ)です。横軸は「Specification detail」(仕様の詳しさ)で、左が「Security definitions」(安全性の定義)、右が「Concrete instantiations」(具体的な実装)です。破線で平面が4つに分けられ、それぞれに青い点「Q1」(左下)、「Q2」(右下)、「Q3」(左上)、「Q4」(右上)があります。破線の矢印が Q1 から Q2 へ、Q3 から Q4 へ、Q1 から Q3 へ、Q2 から Q4 へ向かっています。
Figure 3. Modularity tradeoffs
図 3. モジュール性のトレードオフ
Secret sharing is a particular case of a gadget applicable across all primitives. On its own it can also be useful to facilitate policies regarding separation of duties. Additionally, assuming that a key has been secret shared, some simple threshold schemes follow in a straightforward manner, using techniques very similar to the original algorithm. Standards for more complex threshold schemes may also rely on other gadgets, and thus benefit from corresponding reference definitions, since they may be substantially different from the baseline cryptographic primitive being thresholdized.
秘密分散は、すべてのプリミティブに適用できるガジェットの特殊なケースです。それ単体でも、職務の分離に関するポリシーを促進するのに有用でありえます。さらに、鍵が秘密分散されていると仮定すれば、一部の単純なしきい値方式は、元のアルゴリズムと非常によく似た技術を使って、簡単に導かれます。より複雑なしきい値方式の標準も、ほかのガジェットに依存する場合があり、そうしたガジェットは、しきい値化される基準の暗号プリミティブとは大きく異なる可能性があるため、対応する参照定義の恩恵を受けられます。
5.3.2 Concrete instantiations of building blocks (Q2)
5.3.2 構成要素の具体的なインスタンス化(Q2)
The optimized low-level specification of a gadget, such as a commitment scheme, can vary across concrete protocols. Useful guidance may compare concrete constructions of gadgets applicable across various threshold schemes. For example, for commitment schemes one could devise guidance on how to implement hash-based commitments and Pedersen commitments, and in which cases each may be preferable, based on comparative advantages. In the single-device setting, these gadgets may correspond to components useful in a circuit, such as an AES S-box and finite-field multipliers.
コミットメント方式などのガジェットの、最適化された低水準の仕様は、具体的なプロトコルによって異なりえます。有用なガイダンスとしては、さまざまなしきい値方式に適用できるガジェットの具体的な構成を比較するものが考えられます。たとえば、コミットメント方式については、ハッシュベースのコミットメントと Pedersen コミットメントをどのように実装するか、また、比較上の利点に基づいて、それぞれがどのような場合に望ましいかについて、ガイダンスを策定できます。単一デバイスの設定では、これらのガジェットは、AES の S-box や有限体の乗算器など、回路で有用な構成要素に対応する場合があります。
Certain building blocks are in a peculiar position of having very well understood properties, and being widely useful, but not having standardized a version suitable to certain threshold schemes. For example, the current set of NIST standardized hash functions does not include those hash functions referred to as friendly for multi-party computation (MPC-friendly), which — compared with SHA-2 and SHA-3 — would significantly improve by orders of magnitude the efficiency of distributed computation of a hash. This begs the question of whether some non-standardized versions of building blocks, if determined as the best for use in a future standard of threshold scheme, should first be developed as an independent standard, or be (initially) specified as a module inside of a broader threshold-scheme standard that uses said building block.
特定の構成要素は、特性が非常によく理解されていて広く有用であるにもかかわらず、特定のしきい値方式に適したバージョンが標準化されていないという、特殊な状況にあります。たとえば、現在の NIST が標準化したハッシュ関数の集合には、マルチパーティ計算に適した(MPC-friendly)と呼ばれるハッシュ関数が含まれていません。そうしたハッシュ関数は、SHA-2 や SHA-3 と比べて、ハッシュの分散計算の効率を桁違いに大きく向上させるでしょう。このため、構成要素の標準化されていないバージョンが、将来のしきい値方式の標準で使うのに最適であると判断された場合、それをまず独立した標準として策定すべきか、あるいは、その構成要素を使用する、より広範なしきい値方式の標準の中のモジュールとして(当初は)規定すべきか、という問いが生じます。
5.3.3 Security definitions for complex compositions (Q3)
5.3.3 複雑な合成のセキュリティ定義(Q3)
There are significant advantages of clarity offered by the specification of ideal functionalities, or by a defined interface and comprehensive set of security properties. These can be used for defining the threshold modes being sought and the properties that the protocols need to satisfy. They are, however, not the final goal in terms of standardization, but only a logical abstraction on the way.
理想機能の仕様、または定義されたインターフェースと包括的なセキュリティ特性の集合によって、明確さという大きな利点が得られます。これらは、求められているしきい値モードと、プロトコルが満たす必要のある特性を定義するために使えます。ただし、これらは標準化という観点での最終目標ではなく、その途中にある論理的な抽象化にすぎません。
5.3.4 Concrete instantiations of complex compositions (Q4)
5.3.4 複雑な合成の具体的なインスタンス化(Q4)
For each threshold functionality (Q3) identified as being of interest for standardization, a concrete threshold scheme (Q4) should eventually be specified. This should be describable as a composition of building blocks (Q1) that are, as much as possible (without compromising security and efficiency), interoperable across different threshold schemes, even under different instantiations (Q2).
標準化の対象として関心があると特定された各しきい値機能(Q3)について、最終的には具体的なしきい値方式(Q4)を規定すべきです。これは、(セキュリティと効率を損なわない範囲で)可能な限り、異なるインスタンス化(Q2)の下でも、異なるしきい値方式の間で相互運用できる構成要素(Q1)の合成として記述できるべきです。
6 Development phases
6 策定の段階
This section discusses the possible development phases toward standardization, putting special emphasis on the types of calls for contributions that they may entail. The goal is to have a transparent and open process, involving the community of stakeholders [NISTIR 7977].
本節では、標準化に向けて考えられる策定の段階を、それらに伴いうる貢献募集の種類に特に重点を置いて論じます。目標は、利害関係者のコミュニティを巻き込んだ、透明で公開されたプロセスを実現することです [NISTIR 7977]。
The following discussion is in context with the structure given in the preceding part of this document, including the organization of the high-dimensional space of potential threshold schemes for standardization (Section 2), a consideration of motivating applications (3), the initial high-level identification of possible standardization items (Section 4), and various important features (Section 5).
以下の議論は、本書の前半で示した構造に沿っています。これには、標準化の可能性があるしきい値方式の高次元の領域の構成(第 2 節)、動機となる応用の考慮(第 3 節)、可能な標準化項目の最初の大局的な特定(第 4 節)、およびさまざまな重要な特徴(第 5 節)が含まれます。
The upcoming process for new standards of threshold schemes is envisioned in four phases:
しきい値方式の新しい標準に向けて今後行うプロセスは、四つのフェーズで構想されています。
1.Criteria. Develop differentiated criteria suitable for various foreseen standardization items.
1.基準。見込まれるさまざまな標準化項目に適した、差別化された基準を策定します。
2.Calls. Perform calls for contributions, based on criteria and timelines.
2.募集。基準とスケジュールに基づいて貢献募集を行います。
3.Evaluation. Obtain and evaluate input obtained in the context of calls for contributions.
3.評価。貢献募集の中で得られた意見を入手し、評価します。
4.Publish. Write and publish new standards and guidelines
4.公表。新しい標準とガイドラインを作成し、公表します。
While most of the preparatory phase has been common to the two tracks, and has addresses the primitives generically, the definition of criteria and the subsequent phases should be tailored independently for each track, and possibly per identified standardization item, possibly with distinct timelines. For some items, some phases may have several rounds, such as possibly alternating several calls for contributions (phase 2) and corresponding evaluations (phase 3).
準備段階の大部分は二つのトラックに共通で、プリミティブを総称的に扱ってきましたが、基準の定義とその後のフェーズは、トラックごとに、また場合によっては特定された標準化項目ごとに、別々に、場合によっては異なるスケジュールで、調整すべきです。一部の項目では、複数の貢献募集(フェーズ 2)とそれに対応する評価(フェーズ 3)を交互に行うなど、一部のフェーズが複数のラウンドになる場合があります。
Each phase is composed of three sub-phases (possibly with several internal rounds):
各フェーズは、(場合によっては内部に複数のラウンドを持つ)三つのサブフェーズから成ります。
a.Produce draft documentation and call for feedback.
a.ドラフト文書を作成し、フィードバックを募集します。
b.Evaluate and integrate external feedback.
b.外部からのフィードバックを評価し、統合します。
c.Publish documentation.
c.文書を公表します。
6.1 Phase 1 — Develop criteria
6.1 フェーズ 1 — 基準の策定
The NISTIR 8214 has already enumerated several representative questions to consider when reflecting on criteria. Some of the relevant aspects are:
NISTIR 8214 はすでに、基準を検討する際に考慮すべき代表的な問いをいくつか列挙しています。関連する側面の一部を挙げます。
1.Definition of system model and threat model.
1.システムモデルと脅威モデルの定義。
2.Description of characterizing features.
2.特徴付ける機能の記述。
3.Analysis of efficiency and practical feasibility.
3.効率と実用的な実現可能性の分析。
4.Existence of open-source reference implementations.
4.オープンソースの参照実装の有無。
5.Concrete benchmarking (threshold vs. conventional; different platforms).
5.具体的なベンチマーク(しきい値と従来のもの、異なるプラットフォーム)。
6.Detailed description of operations.
6.操作の詳細な記述。
7.Example application scenarios.
7.応用シナリオの例。
8.Security analysis (see also Section 5.2).
8.セキュリティ分析(第 5.2 節も参照)。
9.Automated testing and validation of implementations (see also Section 5.1).
9.実装の自動化された試験と検証(第 5.1 節も参照)。
10.Disclosure and licensing of intellectual property.
10.知的財産の開示とライセンス。
The above items are important factors to take into consideration but are not themselves a specification of criteria. It is important to obtain further feedback about these items, and several of them represent useful topics for future discussions.
上記の項目は、考慮すべき重要な要因ですが、それ自体が基準の仕様ではありません。これらの項目についてさらにフィードバックを得ることが重要であり、その多くは今後の議論に有用なトピックとなります。
Several of these items also encompass various sub-factors. For example, with respect to efficiency and practical feasibility, there are numerous metrics to benchmark, depending on the setting. In a single-device setting, it can be relevant to consider circuit area, number of clock cycles, frequency, and number of required random or pseudorandom bits, among other possibilities. Also from an adversarial point of view, it can be relevant to assess what limitations exist with respect to the rate of possible collection of traces, namely compared with feasible rates of re-keying. In a multi-party setting, one should consider the overall communication between parties, the round complexity, and the computational resources per party. The use of a reference platform(s) may also be beneficial when comparing various techniques.
これらの項目の多くは、さまざまな副次的な要因も含みます。たとえば、効率と実用的な実現可能性については、設定に応じて、ベンチマークの対象となる数多くのメトリクスがあります。単一デバイスの設定では、回路面積、クロックサイクル数、周波数、必要な乱数または擬似乱数のビット数などを考慮することが関係してくる場合があります。また敵対者の視点でも、トレースを収集できる速度に関してどのような制限があるか、特に、実現可能な再鍵設定の速度と比べてどうかを評価することが関係してくる場合があります。マルチパーティの設定では、パーティ間の通信全体、ラウンド複雑度、パーティごとの計算リソースを考慮すべきです。さまざまな技術を比較する際には、参照プラットフォームを使用することも有益な場合があります。
The goal of phase 1 is to issue criteria that are refined per standardization item. However, such criteria will only emerge after consideration of feedback from stakeholders, and may happen with different timelines for different items. Furthermore, certain aspects have a life span that goes beyond the initial (future) issuance of criteria. This is, for example, the case of performing benchmarks, collecting reference implementations developed by the community, and developing testing and validation procedures. The development of these continues after the selection of concrete threshold schemes in subsequent phases.
フェーズ 1 の目標は、標準化の項目ごとに洗練された基準を発行することです。ただし、そうした基準は、利害関係者からのフィードバックを検討した後にはじめて現れるものであり、項目によって異なる時期に現れる場合があります。さらに、特定の側面には、基準が最初に(将来)発行された後も続くものがあります。たとえば、ベンチマークの実施、コミュニティが開発した参照実装の収集、試験と検証の手順の策定がこれに当たります。これらの開発は、その後のフェーズで具体的なしきい値方式が選定された後も続きます。
Section 7 adds more notes about expected feedback useful for a reflection on criteria.
第 7 節では、基準を検討するうえで有用な、期待されるフィードバックについての注記を追加します。
6.2 Phase 2 — Issue calls for contributions
6.2 フェーズ 2 — 貢献募集の公示
The word “contributions” has a broad meaning. The type of expected contributions can significantly vary with the technical difficulties associated with the intended standardization item. Based on this, different initial types of calls are envisioned (and described here at a high level):
「貢献」という語は広い意味を持ちます。期待される貢献の種類は、対象とする標準化項目に伴う技術的な難しさによって大きく異なりえます。これに基づき、異なる種類の最初の募集が想定されます(ここでは大局的に説明します)。
1.Simpler cases: proposals for new standards or guidelines.
1.より単純なケース: 新しい標準またはガイドラインの提案。
2.More complex cases: preliminary exploration and reference descriptions/implementations.
2.より複雑なケース: 予備的な探索と、参照となる記述や実装。
3.Out of scope of standardization: new research contributions.
3.標準化の対象範囲外: 新しい研究上の貢献。
For some simple items, as well as for simple gadgets (e.g., secret sharing), a contribution call may simply ask for complementary feedback on a base scheme proposal by NIST. Some simple items may nonetheless also involve an actual call for proposals of threshold schemes. These cases are not being envisioned as competitions, as it is more likely that different proposals share common features and it may be desirable to adapt features for some final protocols.
一部の単純な項目や、(秘密分散などの)単純なガジェットについては、貢献募集は、NIST による基本的な方式の提案に対する補完的なフィードバックを求めるだけの場合があります。それでも、一部の単純な項目では、しきい値方式の提案の実際の募集を伴う場合があります。こうしたケースはコンペティションとしては想定されていません。異なる提案が共通の特徴を持つ可能性のほうが高く、最終的なプロトコルのために特徴を適応させることが望ましい場合があるためです。
The more technically challenging items may require complex choices about their internal gadgets and their composition.
技術的により難しい項目では、内部のガジェットとその合成について、複雑な選択が必要になる場合があります。
There is also interest in research results about useful threshold schemes that are out of scope for this standardization effort. For the multi-party setting, this includes schemes for post-quantum public-key encryption (i.e., their decryption and key-generation algorithms) and signatures. For the single-device setting, this may conceivably include schemes for threshold enciphering, authenticated encryption with associated data (AEAD), and/or hashing related to lightweight cryptographic schemes being currently evaluated. However, this interest does not imply a direct interest for corresponding new standards.
この標準化の取り組みの対象範囲外にある、有用なしきい値方式についての研究成果にも関心があります。マルチパーティの設定では、これには、耐量子の公開鍵暗号(すなわち、その復号アルゴリズムと鍵生成アルゴリズム)と署名の方式が含まれます。単一デバイスの設定では、これには、現在評価中の軽量暗号方式に関連する、しきい値による暗号化、関連データ付き認証暗号(AEAD)、ハッシュの方式が含まれる可能性があります。ただし、この関心は、対応する新しい標準への直接の関心を意味するものではありません。
6.3 Phase 3 — Evaluation of contributions
6.3 フェーズ 3 — 貢献の評価
The process must enable an adequate evaluation and selection across a wide span of possible protocols for the same intended functionality. In this case, a multi-stage contribution process may be appropriate, starting with a request for information and progressing to concrete protocol proposals over time. It is important that the process itself has a pace that enables a proper review by the public, including the participation of stakeholders (in particular cryptography experts) to scrutinize the presented proposals.
このプロセスは、同じ意図した機能に対する幅広い範囲のプロトコル候補にわたる、適切な評価と選定を可能にするものでなければなりません。この場合、情報提供依頼から始めて、時間をかけて具体的なプロトコルの提案に進む、多段階の貢献プロセスが適切かもしれません。提示された提案を精査する利害関係者(特に暗号の専門家)の参加を含め、一般による適切なレビューを可能にするペースで、プロセス自体が進むことが重要です。
It is a priority of this project to engage with the research community in structured manners (e.g., dedicated workshops), to keep informed about the state-of-the-art in the corresponding fields, and to converge to solutions whose soundness is widely accepted.
研究コミュニティと(専用のワークショップなど)構造化された方法で関わり、関連分野の最先端の動向を把握し続け、健全性が広く受け入れられる解決策に収束させることは、このプロジェクトの優先事項です。
6.4 Phase 4 — Publish new standards
6.4 フェーズ 4 — 新しい標準の公表
The process of developing and adopting new standards will take into consideration the possible options and corresponding security evaluations. This includes soliciting corresponding public feedback from external stakeholders.
新しい標準を策定し採用するプロセスでは、考えうる選択肢と、それに対応するセキュリティ評価を考慮します。これには、外部の利害関係者から、対応する一般からのフィードバックを募ることが含まれます。
In some cases, a simple addendum to an existing standard may be sufficient to define the new mode or modes of threshold operation. For example, for some threshold circuit designs, the standardization of the technique may correspond to defining guidelines with implementation requirements to achieve certification at some security level. For other items, the standardization may result into a new standalone standard.
場合によっては、既存の標準への単純な追補だけで、新しいしきい値の動作モードを定義するのに十分なことがあります。たとえば、一部のしきい値回路設計では、技術の標準化は、あるセキュリティレベルでの認証を達成するための実装要件を含むガイドラインを定義することに相当する場合があります。それ以外の項目では、標準化の結果として、新しい独立した標準が生まれる場合もあります。
Ideally, the upcoming standards will be clear and instructive, and they will serve as an aid for developing secure system designs. In any case, the goal of achieving upcoming standards of threshold schemes is that they are useful on arrival (rather than obsolete), and enhance the security of the implementation of the corresponding cryptographic primitives, namely with respect to a wide range of side-channel and fault-injection attacks.
理想的には、今後の標準は明確で示唆に富み、セキュアなシステム設計を開発する助けとなります。いずれの場合も、しきい値方式の今後の標準を実現する目標は、それらが(陳腐化したものではなく)完成時点で有用であり、対応する暗号プリミティブの実装のセキュリティ、特に幅広いサイドチャネル攻撃やフォールトインジェクション攻撃に対するセキュリティを強化することです。
7 Collaboration with stakeholders
7 利害関係者との協力
As an immediate follow-up to this document, it is necessary to gather specific feedback on the criteria for subsequent calls for contributions. To this effect, it is important to obtain feedback from stakeholders about the security definitions and interfaces (and/or ideal functionalities) (see Q3) upon which protocols/techniques should be evaluated.
本書の直接のフォローアップとして、その後の貢献募集の基準について、具体的なフィードバックを集める必要があります。そのために、プロトコルや技術を評価する際の拠り所となる、セキュリティの定義とインターフェース(または理想機能、あるいはその両方)(Q3 を参照)について、利害関係者からフィードバックを得ることが重要です。
NIST values the expert technical feedback from stakeholders and that feedback will be incorporated it in the standardization process. Along the way, future NIST Threshold Cryptography Workshops (NTCW) may constitute an essential way to obtain interactive public feedback. This can be a place to discuss evaluations about contributions made thus far within the standardization process, while covering a variety of approaches across the different domains, and considering distinguished features of interest across various items. Overall, the standardization process itself needs to lead the upcoming standards to be of high quality.
NIST は、利害関係者からの専門的な技術的フィードバックを重視しており、そのフィードバックは標準化プロセスに取り入れられます。その過程で、将来開催される NIST Threshold Cryptography Workshops(NTCW)は、双方向の公開フィードバックを得る重要な手段になりえます。このワークショップでは、標準化プロセスでこれまでに寄せられた貢献の評価について議論し、異なる領域にわたるさまざまなアプローチを扱い、各項目で注目すべき特徴を考慮できます。全体として、標準化プロセス自体が、今後の標準を高品質なものにするよう導く必要があります。
Section 6.1 has already mentioned important elements of desired feedback from stakeholders. The following subsections enumerate a few further important aspects, as the process progresses toward issuing criteria for new threshold schemes in each domain.
第 6.1 節では、利害関係者からの望ましいフィードバックの重要な要素をすでに述べました。以下の小節では、各領域で新しいしきい値方式の基準を発行する方向にプロセスが進むにあたって、さらにいくつかの重要な側面を列挙します。
7.1 Multi-party setting
7.1 マルチパーティの設定
There is interest in the development of multi-party threshold schemes that improve key-confidentiality, as well as operational integrity and availability for the implementation of cryptographic primitives. It is relevant to:
暗号プリミティブの実装における鍵の機密性、ならびに運用上の完全性と可用性を改善するマルチパーティしきい値方式の開発に関心があります。次の点が関連します。
1.Enumerate useful threshold modes of operation.
1.有用なしきい値の動作モードを列挙します。
2.For each intended mode, define the intended ideal functionality (and identify corresponding possible trusted setups) and/or game-based security definitions.
2.意図する各モードについて、意図する理想機能(および、対応して可能な信頼されたセットアップの特定)、またはゲームベースのセキュリティ定義、あるいはその両方を定義します。
3.Identify main security properties to be derived from ideal functionalities when their trusted setups are bootstrapped in concrete settings and with concrete techniques.
3.具体的な設定で具体的な技術を用いて信頼されたセットアップをブートストラップする場合に、理想機能から導出される主要なセキュリティ特性を特定します。
4.Enumerate the gadgets whose reference definition is useful (as well as definitions already present in other standards).
4.参照定義が有用なガジェットを(ほかの標準にすでに存在する定義も含めて)列挙します。
7.2 Single-device setting
7.2 単一デバイスの設定
There is interest in the development of threshold circuit designs that improve resistance against side-channel attacks and/or fault attacks in the single-device domain. It is relevant to:
単一デバイスの領域で、サイドチャネル攻撃やフォールト攻撃、あるいはその両方に対する耐性を改善する、しきい値回路設計の開発に関心があります。次のことが重要です。
1.Enumerate and define the desirable properties (e.g., uniformity and non-completeness) that are possible to achieve in threshold circuit designs.
1.しきい値回路設計で達成可能な望ましい特性(例: 一様性と非完全性)を列挙し、定義します。
2.Identify useful construction paradigms for threshold circuit design and the gadgets that are useful to implement them.
2.しきい値回路設計に有用な構築パラダイムと、それを実装するのに有用なガジェットを特定します。
3.Indicate the models/conditions under which the threshold schemes may enable a higher resistance to side-channel and/or fault attacks (e.g., quantifying the increase in the number of traces required for a successful differential power analysis attack).
3.しきい値方式が、サイドチャネル攻撃やフォールト攻撃、あるいはその両方に対する、より高い耐性を可能にしうるモデルや条件を示します(例: 差分電力解析攻撃を成功させるために必要なトレース数の増加を定量化する)。
4.Indicate possible parameters (e.g., masking order and number of shares) for realistic implementations of threshold circuit designs.
4.しきい値回路設計の現実的な実装について、考えうるパラメーター(例: マスキングの次数とシェアの数)を示します。
References
参考文献
[ACVP] National Institute of Standards and Technology (2019). Automated Cryptographic Validation Protocol. GitHub:usnistgov/ACVP, https://github.com/usnistgov/ACVP.
[ACVP] National Institute of Standards and Technology (2019). Automated Cryptographic Validation Protocol. GitHub:usnistgov/ACVP, https://github.com/usnistgov/ACVP.
[CAVP] National Institute of Standards and Technology. Cryptographic Algorithm Validation Program. https://csrc.nist.gov/projects/cryptographic-algorithm-validation-program. Accessed 2019.
[CAVP] National Institute of Standards and Technology. Cryptographic Algorithm Validation Program. https://csrc.nist.gov/projects/cryptographic-algorithm-validation-program. 2019 年にアクセス。
[FIPS 140-2] National Institute of Standards and Technology (2001). Security Requirements for Cryptographic Modules. (U.S. Department of Commerce, Washington, D.C.) Federal Information Processing Standards Publication (FIPS PUBS) 140-2. Change Notice 2 — December 03, 2002. DOI: 10.6028/NIST.FIPS.140-2.
[FIPS 140-2] National Institute of Standards and Technology (2001). Security Requirements for Cryptographic Modules. (U.S. Department of Commerce, Washington, D.C.) Federal Information Processing Standards Publication (FIPS PUBS) 140-2. Change Notice 2 — December 03, 2002. DOI: 10.6028/NIST.FIPS.140-2.
[FIPS 140-3] National Institute of Standards and Technology (2019). Security Requirements for Cryptographic Modules. (U.S. Department of Commerce, Washington, D.C.) Federal Information Processing Standards Publication (FIPS PUBS) 140-3. DOI: 10.6028/NIST.FIPS.140-3.
[FIPS 140-3] National Institute of Standards and Technology (2019). Security Requirements for Cryptographic Modules. (U.S. Department of Commerce, Washington, D.C.) Federal Information Processing Standards Publication (FIPS PUBS) 140-3. DOI: 10.6028/NIST.FIPS.140-3.
[FIPS 186-5] National Institute of Standards and Technology (2019). Digital Signature Standard (DSS). (U.S. Department of Commerce, Washington, D.C.) Draft Federal Information Processing Standards Publication (FIPS PUBS) 186-5. DOI: 10.6028/NIST.FIPS.186-5-Draft.
[FIPS 186-5] National Institute of Standards and Technology (2019). Digital Signature Standard (DSS). (U.S. Department of Commerce, Washington, D.C.) Draft Federal Information Processing Standards Publication (FIPS PUBS) 186-5. DOI: 10.6028/NIST.FIPS.186-5-Draft.
[FIPS 197] National Institute of Standards and Technology (2001). Advanced Encryption Standard (AES). (U.S. Department of Commerce, Washington, D.C.) Federal Information Processing Standards Publication (FIPS PUBS) 197. DOI: 10.6028/NIST.FIPS.197.
[FIPS 197] National Institute of Standards and Technology (2001). Advanced Encryption Standard (AES). (U.S. Department of Commerce, Washington, D.C.) Federal Information Processing Standards Publication (FIPS PUBS) 197. DOI: 10.6028/NIST.FIPS.197.
[NISTIR 7977] Cryptographic Technology Group (2016). NIST Cryptographic Standards and Guidelines Development Process. (U.S. Department of Commerce, Washington, D.C.) National Institute of Standards and Technology Internal Report (NISTIR) 7977. DOI: 10.6028/NIST.IR.7977.
[NISTIR 7977] Cryptographic Technology Group (2016). NIST Cryptographic Standards and Guidelines Development Process. (U.S. Department of Commerce, Washington, D.C.) National Institute of Standards and Technology Internal Report (NISTIR) 7977. DOI: 10.6028/NIST.IR.7977.
[NISTIR 8214] Luís T. A. N. Brandão, Nicky Mouha, and Apostol (2019) Vassilev. Threshold Schemes for Cryptographic Primitives: Challenges and Opportunities in Standardization and Validation of Threshold Cryptography. (U.S. Department of Commerce, Washington, D.C.) National Institute of Standards and Technology Internal Report (NISTIR) 8214. DOI: 10.6028/NIST.IR.8214.
[NISTIR 8214] Luís T. A. N. Brandão, Nicky Mouha, and Apostol (2019) Vassilev. Threshold Schemes for Cryptographic Primitives: Challenges and Opportunities in Standardization and Validation of Threshold Cryptography. (U.S. Department of Commerce, Washington, D.C.) National Institute of Standards and Technology Internal Report (NISTIR) 8214. DOI: 10.6028/NIST.IR.8214.
[NTCW 2019] National Institute of Standards and Technology (2019). NIST Threshold Cryptography Workshop. https://csrc.nist.gov/Events/2019/NTCW19. Gaithersburg, March 11–12.
[NTCW 2019] National Institute of Standards and Technology (2019). NIST Threshold Cryptography Workshop. https://csrc.nist.gov/Events/2019/NTCW19. Gaithersburg, March 11–12.
[Proj-LWC] National Institute of Standards and Technology (2020). Lightweight Cryptography Project. https://csrc.nist.gov/projects/Lightweight-Cryptography.
[Proj-LWC] National Institute of Standards and Technology (2020). Lightweight Cryptography Project. https://csrc.nist.gov/projects/Lightweight-Cryptography.
[Proj-PEC] National Institute of Standards and Technology (2020). Privacy-Enhancing Cryptography Project. https://csrc.nist.gov/projects/Privacy-Enhancing-Cryptography.
[Proj-PEC] National Institute of Standards and Technology (2020). Privacy-Enhancing Cryptography Project. https://csrc.nist.gov/projects/Privacy-Enhancing-Cryptography.
[Proj-PQC] National Institute of Standards and Technology (2020). Post-quantum Cryptography Project. https://csrc.nist.gov/projects/post-quantum-cryptography.
[Proj-PQC] National Institute of Standards and Technology (2020). Post-quantum Cryptography Project. https://csrc.nist.gov/projects/post-quantum-cryptography.
[Proj-TC] National Institute of Standards and Technology (2020). Threshold Cryptography Project. https://csrc.nist.gov/projects/Threshold-Cryptography.
[Proj-TC] National Institute of Standards and Technology (2020). Threshold Cryptography Project. https://csrc.nist.gov/projects/Threshold-Cryptography.
[SP 800-56A] Elaine Barker, Lily Chen, Allen Roginsky, Apostol Vassilev, and Richard Davis (2018). Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography. (National Institute of Standards and Technology, Gaithersburg, MD) NIST Special Publication (SP) 800-56A Rev. 3. DOI: 10.6028/NIST.SP.800-56Ar3.
[SP 800-56A] Elaine Barker, Lily Chen, Allen Roginsky, Apostol Vassilev, and Richard Davis (2018). Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography. (National Institute of Standards and Technology, Gaithersburg, MD) NIST Special Publication (SP) 800-56A Rev. 3. DOI: 10.6028/NIST.SP.800-56Ar3.
[SP 800-56B] Elaine Barker, Lily Chen, Allen Roginsky, Apostol Vassilev, Richard Davis, and Scott Simon (2019). Recommendation for Pair-Wise Key-Establishment Using Integer Factorization Cryptography. (National Institute of Standards and Technology, Gaithersburg, MD) NIST Special Publication (SP) 800-56B Rev. 2. DOI: 10.6028/NIST.SP.800-56Br2.
[SP 800-56B] Elaine Barker, Lily Chen, Allen Roginsky, Apostol Vassilev, Richard Davis, and Scott Simon (2019). Recommendation for Pair-Wise Key-Establishment Using Integer Factorization Cryptography. (National Institute of Standards and Technology, Gaithersburg, MD) NIST Special Publication (SP) 800-56B Rev. 2. DOI: 10.6028/NIST.SP.800-56Br2.
[SP 800-90A] Elaine Barker and John Kelsey (2015). Recommendation for Random Number Generation Using Deterministic Random Bit Generators. (National Institute of Standards and Technology, Gaithersburg, MD) NIST Special Publication (SP) 800-90A, Rev. 1. DOI: 10.6028/NIST.SP.800-90Ar1.
[SP 800-90A] Elaine Barker and John Kelsey (2015). Recommendation for Random Number Generation Using Deterministic Random Bit Generators. (National Institute of Standards and Technology, Gaithersburg, MD) NIST Special Publication (SP) 800-90A, Rev. 1. DOI: 10.6028/NIST.SP.800-90Ar1.
[SP 800-186] Lily Chen, Dustin Moody, Andrew Regenscheid, and Karen Randall (2019). Recommendations for Discrete Logarithm-Based Cryptography: Elliptic Curve Domain Parameters. (National Institute of Standards and Technology, Gaithersburg, MD) Draft NIST Special Publication (SP) 800-186. DOI: 10.6028/NIST.SP.800-186-draft.
[SP 800-186] Lily Chen, Dustin Moody, Andrew Regenscheid, and Karen Randall (2019). Recommendations for Discrete Logarithm-Based Cryptography: Elliptic Curve Domain Parameters. (National Institute of Standards and Technology, Gaithersburg, MD) Draft NIST Special Publication (SP) 800-186. DOI: 10.6028/NIST.SP.800-186-draft.
Appendix A — Application use cases
付録 A — 応用のユースケース
This section describes at a high level several conceivable applications that take advantage of threshold schemes for cryptographic primitives. This is intended to be an aid to identify, motivate and select concrete items of interest for standardization.
本節では、暗号プリミティブのしきい値方式を活用する、考えうるいくつかの応用を大局的に説明します。これは、標準化の対象として関心のある具体的な項目を特定し、その動機を示し、選定する助けとなることを意図しています。
A.1 Single-device encryption resistant to side-channel attacks
A.1 サイドチャネル攻撃に耐える単一デバイスの暗号化
The hardware implementation of cryptographic algorithms has gained a significant and growing stake in the industry. Large amounts of sensitive data are now processed in hardware, which creates the need for faster implementations. Most semiconductor manufacturers have incorporated dedicated hardware accelerators for cryptography that perform orders of magnitude faster than software implementations. Algorithms of asymmetric cryptography, such as RSA and ECC digital signatures, can be implemented by a hardware accelerator, as a way to reduce the processing time of private key operations. However, these algorithms are sometimes not suitable for severely constrained devices in the Internet of Things (IoT), due to the significant resources required, which results in low performance on such platforms. Indeed, many IoT devices have only hardware engines for symmetric cryptography primitives, such as AES.
暗号アルゴリズムのハードウェア実装は、産業界で大きく、かつ拡大する位置を占めるようになりました。現在では大量の機微なデータがハードウェアで処理されており、これが、より高速な実装の必要性を生んでいます。ほとんどの半導体製造者は、ソフトウェア実装より桁違いに高速に動作する、暗号用の専用ハードウェアアクセラレーターを組み込んでいます。RSA や ECC のデジタル署名などの公開鍵暗号のアルゴリズムは、秘密鍵の演算の処理時間を短縮する方法として、ハードウェアアクセラレーターで実装できます。しかし、これらのアルゴリズムは、必要とするリソースが大きく、そのようなプラットフォームでは性能が低くなるため、モノのインターネット(IoT)の、厳しく制約されたデバイスには適さない場合があります。実際、多くの IoT デバイスには、AES などの共通鍵暗号プリミティブのためのハードウェアエンジンしかありません。
At the same time, conventional hardware implementations of cryptographic algorithms have created significant problems in terms of side-channel leakage. Traditional techniques for leakage mitigation are costly and ad hoc, and such implementations are also susceptible to fault attacks. Thus, a question arises: what type of algorithm is the most widely used in hardware and stands to gain the most from a standard mechanism for mitigating leakage and/or fault attacks, if threshold schemes for it are developed and standardized?
同時に、暗号アルゴリズムの従来のハードウェア実装は、サイドチャネル漏えいの面で大きな問題を生んできました。漏えいを緩和する従来の技術はコストが高く場当たり的であり、そうした実装はフォールト攻撃にも脆弱です。そこで、次の問いが生じます。しきい値方式が開発され標準化された場合に、ハードウェアで最も広く使われ、漏えい攻撃やフォールト攻撃、あるいはその両方を緩和する標準的な仕組みから最も多くの利益を得られるのは、どの種類のアルゴリズムか。
Symmetric-key cryptographic algorithms, such as block ciphers and message authentication codes, tend to be difficult to protect. Furthermore, the leakage pattern of hardware implementations is vastly different from what emanates from software implementations. Glitches and other physical effects result in stronger leakage for hardware implementations of symmetric cryptographic algorithms (compared to software ones). Based on this, for the single-device track there is value in focusing on hardware implementations of block-cipher algorithms (AES strongly preferred) and in developing standards for threshold schemes to mitigate the risks of side-channel leakage and/or fault attacks.
ブロック暗号やメッセージ認証コードなどの共通鍵暗号アルゴリズムは、保護が難しい傾向があります。さらに、ハードウェア実装の漏えいのパターンは、ソフトウェア実装から発せられるものとは大きく異なります。グリッチなどの物理的な効果によって、共通鍵暗号アルゴリズムのハードウェア実装では、(ソフトウェア実装と比べて)より強い漏えいが生じます。これに基づき、単一デバイスのトラックでは、ブロック暗号アルゴリズム(AES が強く望まれます)のハードウェア実装に焦点を当て、サイドチャネル漏えいやフォールト攻撃、あるいはその両方のリスクを緩和するしきい値方式の標準を策定することに価値があります。
A.2 Protection of secrets at rest
A.2 保存時の秘密の保護
Most cryptographic applications involve a secret, which if revealed to an adversary results in a security failure. For example: a secret key corresponding to a public certificate can decrypt encrypted messages whose content was intended only for the key owner; a secret key from a crypto-currency can be used to spend the original funds of the owner; the secret signing key of a certificate authority (CA) can sign certificates as the CA. The key must also be available to the legitimate user — losing the key may imply losing a digital identity, in the case of a signing key, or losing access to funds, in the case of a crypto-currency private key.
ほとんどの暗号アプリケーションにはシークレットが関わっており、それが敵対者に明らかになると、セキュリティが破綻します。たとえば、公開証明書に対応する秘密鍵は、鍵の所有者だけに向けた内容の暗号化メッセージを復号できます。暗号通貨の秘密鍵は、所有者の元の資金を使うために使用できます。認証局(CA)の署名用秘密鍵は、CA として証明書に署名できます。鍵は正当な利用者も利用できなければなりません。署名用の鍵であれば、鍵を失うことはデジタルアイデンティティを失うことを意味する場合があり、暗号通貨の秘密鍵であれば、資金へのアクセスを失うことを意味する場合があります。
In any of the mentioned cases, the storage of the secret key in one place represents a single point of failure for confidentiality, integrity, or availability. This can be mitigated by using secret sharing to distribute, across multiple parties, the trust in the storage of secrets. In one use-case, a CA may have its signing key secret-shared among several employees, such that no single employee alone has access to the key. In another use-case, a “social backup” system for crypto-currency wallets may allow the user to distribute shares of the key to several friends, such that if the device of user device is lost or breaks, the user can still recover the key from the shares. Once a secret key is protected at rest using secret sharing, there are threshold schemes that enable avoiding reconstruction of the key even when the key needs to be used in some operation.
上記のいずれの場合も、秘密鍵を一か所に保管することは、機密性、完全性、可用性に関する単一障害点となります。これは、秘密分散を使って、シークレットの保管に関する信頼を複数のパーティに分散させることで緩和できます。あるユースケースでは、CA の署名用秘密鍵を複数の従業員の間で秘密分散し、どの従業員も単独では鍵にアクセスできないようにできます。別のユースケースでは、暗号通貨ウォレット向けの「ソーシャルバックアップ」システムにより、利用者が鍵のシェアを複数の友人に配布し、利用者のデバイスが失われたり壊れたりしても、シェアから鍵を復元できるようにできます。秘密鍵が秘密分散によって保存時に保護されれば、何らかの操作で鍵を使う必要がある場合でも、鍵を再構成せずに済むしきい値方式があります。
A.3 Confidential communication
A.3 機密通信
For secure communications it is essential to ensure that secret messages are only decrypted by legitimate recipients. An attacker who steals Alice’s secret decryption key can read messages intended for Alice. Threshold decryption can help protect confidentiality. It can, for example, be used across devices, analogously to multi-factor “authentication” for a single person, such that unauthorized parties (in this case hacked or stolen devices) cannot break the confidentiality of messages, without using multiple shares of the key. Similar considerations apply to the protection of message authenticity, (i.e., preventing an attacker from masquerading as Alice to others, with respect to a secret signing key).
セキュアな通信では、秘密のメッセージが正当な受信者によってのみ復号されることを確保することが不可欠です。Alice の復号用秘密鍵を盗んだ攻撃者は、Alice 宛てのメッセージを読めます。しきい値復号は、機密性の保護に役立ちます。たとえば、一人の人に対する多要素「認証」に似て、複数のデバイスにまたがって使用でき、許可されていない者(この場合は、ハッキングされたり盗まれたりしたデバイス)が、鍵の複数のシェアを使わずにメッセージの機密性を破れないようにできます。メッセージの真正性の保護(すなわち、署名用秘密鍵に関して、攻撃者が他者に対して Alice になりすますことを防ぐこと)にも、同様の考慮事項が当てはまります。
Using a threshold decryption (e.g., RSA) in a shared-O mode, the multiple parties compute separate shares of the decryption plaintext. Then, a combiner (possibly the end recipient, i.e., the client) receives the shares and computes the plaintext from them. This mode of operation protects the secrecy of the (distributed) key (as a main feature) as well as the confidentiality of the decrypted message (as an added feature). In some settings this may provide a kind of accountability, since it requires the explicit participation of multiple parties, who can, for example, log their operations for future audits. Also, if the scheme is auditable then the recipient of the final decryption can verify which decryptor parties were involved.
shared-O モードでしきい値復号(例: RSA)を使うと、複数のパーティが、復号された平文の個別のシェアを計算します。その後、結合者(エンドの受信者、すなわちクライアントの場合もあります)がシェアを受け取り、そこから平文を計算します。この動作モードは、(分散された)鍵の秘匿性を(主な機能として)、また復号されたメッセージの機密性を(追加の機能として)保護します。設定によっては、複数のパーティの明示的な参加が必要で、それらのパーティが、たとえば将来の監査のために自らの操作を記録できるため、一種の説明責任を提供する場合があります。また、方式が監査可能であれば、最終的な復号結果の受信者は、どの復号パーティが関与したかを検証できます。
A.4 Decentralization of trust for key generation and distribution
A.4 鍵生成と鍵配布における信頼の分散
Key generation and distribution are essential phases of many cryptographic schemes and applications. For example, a key distribution center (KDC) can act as a trusted service that distributes symmetric secret keys to clients, to enable private communication within groups or to mediate access to other services. Thus, a KDC represents a single point of failure. If the KDC is offline, the clients cannot securely communicate or access needed services. If the KDC is hacked, the attacker can learn the secret keys in use by clients, and can obtain tickets to access any services. The same considerations apply, for example, to an identity-based encryption scheme, where a trusted server holds the master key that is required to generate a new secret key for every new member (identity) in an organization. Yet another example is the use of a “dealer” as a trusted party generating a secret key (possibly with a complex structure, such as an RSA key), only to then secret share it across multiple parties of a subsequent threshold signing or decryption scheme.
鍵生成と鍵配布は、多くの暗号方式や応用の本質的な段階です。たとえば、鍵配布センター(KDC)は、グループ内の非公開通信を可能にしたり、他のサービスへのアクセスを仲介したりするために、クライアントに共通鍵を配布する信頼されたサービスとして機能できます。このため、KDC は単一障害点となります。KDC がオフラインになると、クライアントはセキュアに通信したり、必要なサービスにアクセスしたりできなくなります。KDC がハッキングされると、攻撃者はクライアントが使用している共通鍵を知ることができ、あらゆるサービスにアクセスするためのチケットを取得できます。同じ考慮事項は、たとえば、組織内の新しいメンバー(アイデンティティ)ごとに新しい秘密鍵を生成するために必要なマスター鍵を、信頼されたサーバーが保持するアイデンティティベース暗号方式にも当てはまります。さらにもう一つの例は、(RSA 鍵のような複雑な構造を持つ場合もある)秘密鍵を生成し、後続のしきい値署名または復号方式の複数のパーティに秘密分散する信頼されたパーティとして「ディーラー」を使うことです。
To eliminate this single point of failure, a set of servers can jointly act as a KDC or dealer in a way that no individual server knows any of the secret keys, and so that services remain available as long as a certain threshold number of servers have not been hacked or taken offline. This threshold property can be based on distributed key generation and use of secret sharing, possibly with proactive and verifiable properties. The latter properties allow the servers to jointly refresh the secret shares (in order to recover from the potential compromise of some servers) and to ensure that their shares are consistent. The distribution of servers prevents any server from learning any master secret key, while the actual distribution of new keys may fit within a shared-O mode, so that no server learns any new secret key. For example, verifiable delay functions (which can be useful for various applications) can be based on an RSA public key whose corresponding secret key needs to be unknown to everyone.
この単一障害点をなくすために、一組のサーバーが共同で KDC またはディーラーとして機能し、個々のサーバーがどのシークレット鍵も知らないようにしつつ、ハッキングされたりオフラインになったりしていないサーバーの数が一定のしきい値以上である限り、サービスが利用可能であるようにできます。このしきい値特性は、分散鍵生成と、場合によっては事前対応的で検証可能な特性を持つ秘密分散の使用に基づけます。後者の特性により、サーバーは(一部のサーバーが危殆化した可能性から回復するために)共同で秘密シェアを更新し、シェアの整合性を確保できます。サーバーを分散させることで、どのサーバーもマスターシークレット鍵を知ることがなくなります。新しい鍵は実際にはshared-O モードで配布できるため、どのサーバーも新しいシークレット鍵を知りません。たとえば、(さまざまな応用で有用な)検証可能遅延関数は、対応する秘密鍵が誰にも知られていない必要がある RSA 公開鍵に基づけます。
A.5 Accountability and prevention of ill-intentioned operations
A.5 説明責任と悪意ある操作の防止
Entrusting a single individual with the ability to decrypt or sign a message may invite foul play, if the result cannot be externally verified as correct or its computation does not require agreement between multiple parties.
メッセージを復号したり署名したりする能力を一人の個人に委ねると、結果が正しいことを外部から検証できない場合や、その計算に複数のパーティの同意が必要でない場合には、不正行為を招く可能性があります。
For example, to authorize a large bank transfer, it can be useful to require agreement between several managers. A policy can state that transactions above a certain amount are only valid after signed off by at least two out of three bank managers, to prevent the authorization of errant transfers intended by a single ill-intentioned manager. Certain threshold signature schemes (including multi-signatures) enable this in a functionally interchangeable mode, such that the output is syntactically equivalent to an original signature. This property can be important for records where size matters (e.g., storage in a blockchain) and where the policy on the number of signers may be dynamic. If a single original signing key was secret-shared between the managers, then the bank can internally know that a large enough subset of managers got together, though possibly not knowing (from the signature itself) which ones. If a “multi-signature” scheme is used, then each manager can have their own independent secret-public key pair. This becomes auditable in the sense of allowing to check which managers participated, thereby facilitating accountability. The same consideration could be applied, for example, to an application use-case of notary services.
たとえば、多額の銀行送金を承認するために、複数の管理者の同意を求めることが有用な場合があります。ポリシーで、一定額を超える取引は、3 人の銀行管理者のうち少なくとも 2 人が承認した後にのみ有効と定めることで、悪意ある一人の管理者が意図した不正な送金の承認を防げます。特定のしきい値署名方式(マルチ署名を含む)は、これを機能的に互換なモードで可能にし、出力を元の署名と構文的に同等にします。この特性は、サイズが重要な記録(例: ブロックチェーンへの保存)や、署名者の数に関するポリシーが動的でありうる場合に重要になることがあります。一つの元の署名用秘密鍵が管理者の間で秘密分散されていれば、どの管理者かは(署名自体からは)分からない場合があるものの、銀行は十分な数の管理者が集まったことを内部で把握できます。「マルチ署名」方式が使われる場合は、各管理者がそれぞれ独立した秘密鍵と公開鍵のペアを持てます。どの管理者が参加したかを確認できるという意味で監査可能になり、それによって説明責任が促進されます。同じ考慮事項は、たとえば公証サービスの応用例にも当てはまります。
Compared with a simple concatenation of signatures, certain concise threshold signatures (e.g., when the secret-key is secret-shared) may also be desirable as a feature of not exposing the identity of the signers and the corresponding organizational structure.
署名の単純な連結と比べて、特定の簡潔なしきい値署名(たとえば、シークレット鍵が秘密分散されている場合)は、署名者の識別情報と対応する組織構造を公開しないという機能としても望ましいことがあります。
A.6 Distribution of trust across secure environments
A.6 セキュアな環境間での信頼の分散
Hardware security modules (HSMs) are often used to safeguard high-value secret keys. They perform cryptographic operations, such as signatures, only inside a hardened-security environment that attempts to prevent exfiltration of the keys. However, even HSMs are subject to new vulnerabilities and side-channel attacks that enable an insider attacker, with physical access to an HSM, to exfiltrate a signing key before the HSM is patched. To mitigate this attack, it is possible to use a diversity of HSMs as multiple parties in a threshold scheme.
ハードウェアセキュリティモジュール(HSM)は、価値の高い秘密鍵を保護するためによく使われます。HSM は、鍵の持ち出しを防ごうとする強化されたセキュリティ環境の内部でのみ、署名などの暗号操作を行います。しかし、HSM であっても、新たな脆弱性やサイドチャネル攻撃にさらされ、HSM に物理的にアクセスできる内部の攻撃者が、HSM にパッチが適用される前に署名用秘密鍵を持ち出せる可能性があります。この攻撃を緩和するために、多様な HSM をしきい値方式の複数のパーティとして使うことができます。
For certain threshold schemes, such as a threshold RSA signature, each HSM only has to perform an already supported cryptographic operation. Each HSM simply computes and outputs a regular RSA signature, using a signing key share, and then some external non-HSM device combines the output shares to obtain the final RSA signature. This application can be enabled by a dealer that, in an initial safe/protected phase, secret-shares the RSA key, and distributes one share to each HSM (across diverse locations). For more complex threshold schemes (including RSA key generation without a dealer), the threshold operations may require customized programing and interactions between parties. This can be achieved for example by diverse virtual machines running in various and diversified computers (e.g., with different operating systems and protected by different access control mechanisms).
しきい値 RSA 署名など、特定のしきい値方式では、各 HSM は、すでにサポートされている暗号操作を行うだけで済みます。各 HSM は、署名用秘密鍵のシェアを使って通常の RSA 署名を計算して出力するだけで、その後、HSM ではない外部デバイスが出力シェアを組み合わせて、最終的な RSA 署名を得ます。この応用は、最初の安全で保護された段階で RSA 秘密鍵を秘密分散し、多様な場所にある各 HSM に一つずつシェアを配布するディーラーによって可能になります。より複雑なしきい値方式(ディーラーなしの RSA 鍵生成を含む)では、しきい値の演算に、カスタマイズされたプログラミングとパーティ間の対話が必要になる場合があります。これは、たとえば、(異なるオペレーティングシステムを持ち、異なるアクセス制御の仕組みで保護された)さまざまな多様化されたコンピューター上で動作する、多様な仮想マシンによって実現できます。
A.7 Distributed password authentication
A.7 分散パスワード認証
In a typical password-based authentication, a client sends its username and password to a server, via an encrypted channel, and then the server computes a salted hash of the password and checks the result against a verification table of hashes. This setting has several single-points of failure: (i) if the server fails, then the authentication service becomes unavailable; (ii) if the server’s database is leaked by an intruder, then an attacker can use an offline “dictionary attack” to find which passwords in the dictionary match the database; and (iii) if the server is hacked with spyware, then the intruder may be able to read in real time the passwords sent by clients.
典型的なパスワードベースの認証では、クライアントは、暗号化されたチャネルを介して、ユーザー名とパスワードをサーバーに送り、サーバーは、パスワードのソルト付きハッシュを計算して、その結果をハッシュの検証テーブルと照合します。この設定には、複数の単一障害点があります。(i) サーバーが故障すると、認証サービスが利用できなくなります。(ii) サーバーのデータベースが侵入者によって漏えいすると、攻撃者は、オフラインの「辞書攻撃」を使って、辞書内のどのパスワードがデータベースと一致するかを見つけられます。(iii) サーバーがスパイウェアでハッキングされると、侵入者は、クライアントが送るパスワードをリアルタイムで読み取れる可能性があります。
Without changing the underlying hash-based mechanism, the first two mentioned issues can be rectified by a simple threshold approach. Each salt in the verification table can be secret-shared across a set of \(n\) servers, such that any subset of \(f\) or fewer shares has no information about the not-in-use verification salts, and any subset of \(f + 1 + a\) uncompromised servers (for some non-negative \(a\)) can reconstruct a verification (salted) hash when so requested. In this example, the enhanced confidentiality of the values stems from the threshold property of the threshold secret sharing, without using any encryption. The use of salts prevents the attacker from benefiting from pre-computations in the case where the verification table is leaked (if more than the threshold number of servers is compromised).
基盤となるハッシュベースの仕組みを変えることなく、最初の二つの問題は、単純なしきい値のアプローチで是正できます。検証テーブルの各ソルトを \(n\) 台のサーバーの間で秘密分散し、\(f\) 個以下のシェアの任意の部分集合は検証用ソルトについて何の情報も持たず、\(f + 1 + a\) 台(\(a\) は何らかの非負の値)の危殆化していないサーバーの任意の部分集合は、要求があれば検証用の(ソルト付き)ハッシュを再構成できるようにします。この例では、値の機密性の強化は、暗号化を一切使わずに、しきい値秘密分散のしきい値特性から得られます。ソルトを使うことで、(しきい値の数を超えるサーバーが危殆化して)検証テーブルが漏えいした場合に、攻撃者が事前計算の恩恵を受けることを防げます。
The online attack (issue iii above) can be addressed with extra steps, such as: (i) the client sends the password in a shared-I mode (i.e., as separate secret shares to each server); (ii) then the servers, each with a salt share, jointly compute the salted hash, but without recombining the salt (efficiency-wise this may benefit from a hash function that is friendly with respect to distributed computations); and (iii) if the output matches the expected hash, then the user is authenticated. Thus, besides the secret-sharing of the input, the complexity of the operation lies only on the side of the servers.
オンライン攻撃(上記の問題 iii)には、次のような追加のステップで対処できます。(i) クライアントが、shared-I モードで(すなわち、各サーバーへの個別の秘密シェアとして)パスワードを送ります。(ii) 次に、各サーバーがソルトのシェアを持ち、ソルトを再結合することなく、共同でソルト付きハッシュを計算します(効率の面では、分散計算に適したハッシュ関数が役立つ場合があります)。(iii) 出力が想定されるハッシュと一致すれば、利用者が認証されます。したがって、入力の秘密分散のほかには、操作の複雑さはサーバー側にだけあります。
The above description is meant for illustration purposes only. An actual consideration for a real authentication scheme with threshold properties would require a proper security analysis and would likely warrant further considerations. For example, other solutions exist to prevent the client from leaking any information about the password. Some of these solutions are implemented in practice in the space of password authenticated key exchange (PAKE), and their threshold variants could be performed using threshold versions of oblivious pseudo-random functions. These can be resilient against an active eavesdropper even if the client does not have an initial secure channel with the servers. However, some of these solutions go beyond the scope of the threshold modes currently defined in Section 2.3, since they require the client to actively participate in a secure computation, performing actions beyond secret-sharing.
上記の説明は、例示を目的としたものです。しきい値特性を持つ実際の認証方式を検討するには、適切なセキュリティ分析が必要であり、さらなる検討も必要になる可能性が高いです。たとえば、クライアントがパスワードに関する情報を一切漏えいしないようにするための、ほかの解決策もあります。これらの解決策の一部は、パスワード認証鍵交換(PAKE)の分野で実際に実装されており、そのしきい値版は、オブリビアス擬似ランダム関数のしきい値版を使って実現できます。これらは、クライアントがサーバーとの初期セキュアチャネルを持たない場合でも、能動的な盗聴者に対してレジリエントでありえます。ただし、これらの解決策の一部は、クライアントがセキュアな計算に積極的に参加して秘密分散を超える動作を行う必要があるため、第 2.3 節で現在定義されているしきい値モードの範囲を超えています。


