[Invited Talk] On the Impossibility of Constructing Efficient Key Encapsulation and Programmable Hash Functions in Prime Order
スポンサーリンク
概要
- 論文の詳細を見る
In this invited talk, we introduce the lecture with the same title presented at the 32nd International Cryptology Conference (CRYPTO 2012) held from August 19th to 23rd, 2012, at Santa Barbara, USA.\\ \\[Abstract from the original paper (with a slight modification):] In this work, we focus on the problem of minimizing ciphertext overhead, and discuss the (im)possibility of constructing key encapsulation mechanisms (KEMs) with low ciphertext overhead. More specifically, we rule out the existence of algebraic black-box reductions from the (one-way, bounded) CCA security of a natural class of KEMs to any non-interactive problem. The class of KEMs captures the structure of the currently most efficient KEMs defined in standard prime order groups, but restricts an encapsulation to consist of a single group element and a string. This result suggests that we cannot rely on existing techniques to construct a CCA secure KEM in standard prime order groups with a ciphertext overhead lower than two group elements. Furthermore, we show how the properties of an (algebraic) programmable hash function can be exploited to construct a simple, efficient and (one-way, bounded) CCA secure KEM based on the hardness of the computational Diffie-Hellman problem with the ciphertext overhead of just a single group element. Since this KEM construction is covered by the above mentioned impossibility result, this enables us to derive a lower bound on the hash key size of an algebraic programmable hash function, and rule out the existence of algebraic $({\sf poly},n)$-programmable hash functions in prime order groups for any integer $n$. The latter result answers an open question posed by Hofheinz and Kiltz (CRYPTO'08, J. Cryptology'12) in the case of algebraic programmable hash functions in prime order groups.
- 2012-12-05
著者
-
花岡 悟一郎
産業技術総合研究所 情報セキュリティ研究センター
-
JacobC.N. SCHULDT
ロンドン大学ロイヤル・ホロウェイ校
-
松田 隆宏
産業技術総合研究所セキュアシステム研究部門
-
松田 隆宏
産業技術総合研究所
-
花岡 悟一郎
産業技術総合研究所
-
花岡 悟一郎
産業技術総合研究所セキュアシステム研究部門
関連論文
- BDDH仮定と Square BDDH 仮定の関係の考察
- L-006 双方向放送サービスのための効率的なプロバイダ認証(ネットワーク・セキュリティ,一般論文)
- トレードオフ不正利用者追跡法
- 鍵漏洩耐性を持つ不正者追跡法
- 次世代認証基盤
- Oblivious Polynomial Evaluationを用いた非対称不正者追跡法
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- ゼロ知識性の完全化による'On the Fly'認証方式の効率化(セキュリティ関係,一般)
- 鍵漏洩耐性を持つ不正者追跡法
- 双方向放送サービスのための効率的なStrong Key-Insulated署名
- 双方向放送サービスのための効率的なStrong Key-Insulated署名
- 双方向放送サービスのための効率的な Strong Key-Insulated 署名
- 個別メッセージの暗号化機能を有する効率的なブロードキャスト暗号(セキュリティ関係,一般)
- 個別メッセージの暗号化機能を有する効率的なブロードキャスト暗号(セキュリティ関係,一般)
- 個別メッセージの暗号化機能を有する効率的なブロードキャスト暗号(セキュリティ関係,一般)
- 不要な通信機能削除による閾値型ID-based鍵配送方式の最適化手法
- Advanced KPSにおけるprovider間の鍵の不正導出とその対応に関する一検討
- 情報量的安全性に基づく署名方式における安全性の概念について
- IDベース暗号の安全性定義とそれらの関係
- IDベース暗号の安全性定義とそれらの関係
- Forward Secure 暗号, Key-Insulated 暗号およびそのハイブリッド方式
- ID-based Encryption for Directed Acyclic Graph Hierarchies and Applications to Key-evolving Encryption Primitives
- 情報量的安全性に基づく暗号技術
- Key-Insulated 暗号の一般的構成方法
- 信頼できる仲裁者を必要としない非対称認証符号の不可能性について
- IDに基づく暗号系における鍵更新
- ペアリングを用いた不正利用者追跡法への攻撃
- 情報量的安全性に基づく暗号化方式に対する安全性の概念および構成法について
- 情報量的安全性に基づく暗号化方式に対する安全性の概念および構成法について
- 情報量的安全性に基づく電子入札方式に関する一考察
- 情報量的安全性に基づく暗号化方式について
- 不正者追跡可能なデジタル署名方式
- 情報量的安全性に基づく署名方式の構成法について
- 情報量的安全性に基づく署名方式の構成法について
- ID方式に関するメモ
- 情報量的安全性に基づく暗号系について (特集 暗号の数理--デジタル社会のセキュリティ)
- Secure Electronic Transaction(SET)の高速化に関する一手法
- Secure Electronic Transaction (SET) の高速化に関する一検討
- PA-3-5 情報量的安全性に基づく署名方式
- 階層型モデルにおける情報量的安全性に基づく鍵配送の効率化
- Key Predistribution Systemにおけるオーソリティの階層化に関する考察
- Key Predistribution Systemにおけるオーソリティの階層化に関する考察
- 1-6 鍵漏洩耐性を有するプロバイダ認証方式(第1部門 音声処理・セキュリティ)
- [Invited Talk] On the Impossibility of Constructing Efficient Key Encapsulation and Programmable Hash Functions in Prime Order
- 効率的かつCCA安全なプロキシ再暗号化方式の構成
- A-7-1 ECIESのPlaintext Awarenessについて : On the Plaintext Awareness of ECIES(A-7.情報セキュリティ)
- 効率的かつCCA安全なプロキシ再暗号化方式の構成
- 効率的かつCCA安全なプロキシ再暗号化方式の構成
- A-7-2 匿名属性認証とその応用(A-7.情報セキュリティ)
- 国際会議ASIACRYPT 2012参加報告
- L-027 多者多重署名とその応用(L分野:ネットワーク・セキュリティ,一般論文)