More Web Proxy on the site http://driver.im/

Article

Key-Insulated Public Key Cryptosystems

Authors:

Yevgeniy Dodis,

Moti YungAuthors Info & Claims

EUROCRYPT '02: Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology

Pages 65 - 82

Published: 02 May 2002 Publication History

Abstract

Cryptographic computations (decryption, signature generation, etc.) are often performed on a relatively insecure device (e.g., a mobile device or an Internet-connected host) which cannot be trusted to maintain secrecy of the private key. We propose and investigate the notion of key-insulated security whose goal is to minimize the damage caused by secret-key exposures. In our model, the secret key(s) stored on the insecure device are refreshed at discrete time periods via interaction with a physically-secure - but computationally-limited - device which stores a "master key". All cryptographic computations are still done on the insecure device, and the public key remains unchanged. In a ( t, N )-key-insulated scheme, an adversary who compromises the insecure device and obtains secret keys for up to t periods of his choice is unable to violate the security of the cryptosystem for any of the remaining N-t periods. Furthermore, the scheme remains secure (for all time periods) against an adversary who compromises only the physically-secure device. We focus primarily on key-insulated public-key encryption. We construct a ( t, N )-key-insulated encryption scheme based on any (standard) publickey encryption scheme, and give a more efficient construction based on the DDH assumption. The latter construction is then extended to achieve chosen-ciphertext security.

References

[1]

M. Abdalla and L. Reyzin. A New Forward-Secure Digital Signature Scheme. Asiacrypt'00.

[2]

M. Abe and M. Kanda. A Key Escrow Scheme with Time-Limited Monitoring for One-Way Communication. ACISP '00.

[3]

R. Anderson. Invited lecture. ACM CCCS '97.

[4]

M. Bellare, A. Desai, E. Jokipii, and P. Rogaway. A Concrete Security Treatment of Symmetric Encryption: Analysis of the DES Modes of Operation. FOCS '97.

[5]

M. Bellare and S.K. Miner. A Forward-Secure Digital Signature Scheme. Crypto '99.

[6]

G. Blakley and C. Meadows. Security of Ramp Schemes. Crypto '84.

[7]

D. Boneh and M. Franklin. Identity-Based Encryption from the Weil Pairing. Crypto '01.

[8]

V. Boyko. On the Security Properties of the OAEP as an All-or-NothingT ransform. Crypto '99.

[9]

R. Canetti, Y. Dodis, S. Halevi, E. Kushilevitz, and A. Sahai. Exposure-Resilient Functions and All-Or-Nothing-Transforms. Eurocrypt '00.

[10]

B. Chor, A. Fiat, and M. Naor. TracingT raitors. Crypto '94.

[11]

R. Cramer and V. Shoup. A Practical Public-Key Cryptosystem Provably Secure against Adaptive Chosen-Ciphertext Attacks. Crypto '98.

[12]

A. De Santis, Y. Desmedt, Y. Frankel, and M. Yung. How to Share a Function Securely. STOC 94.

[13]

Y. Desmedt and Y. Frankel. Threshold cryptosystems. Crypto'89.

[14]

W. Diffie, P. van Oorschot and M. Wiener. Authentication and Authenticated Key Exchanges. Designs, Codes and Cryptography , 2:107-125, 1992.

[15]

Y. Dodis, J. Katz, S. Xu and M. Yung. Key-Insulated Signature Schemes. Manuscript, 2002.

[16]

A. Dyachkov and V. Rykov. A Survey of Superimposed Code Theory. In Problems of Control and Information Theory , vol. 12, no. 4, 1983.

[17]

T. El Gamal. A Public-Key Cryptosystem and a Signature Scheme Based on the Discrete Logarithm. IEEE Transactions of Information Theory , 31(4): 469-472, 1985.

[18]

P. Erdos, P. Frankl, and Z. Furedi. Families of Finite Sets in which no Set is Covered by the Union of r Others. In Israel J. Math. , 51(1-2): 79-89, 1985.

[19]

M. Franklin, M. Yung. Communication Complexity of Secure Computation. STOC '92.

[20]

E. Gafni, J. Staddon, and Y. L. Yin. Efficient Methods for Integrating Traceability and Broadcast Encryption. Crypto '99.

[21]

M. Girault. RelaxingT amper-Resistance Requirements for Smart Cards Using (Auto)-Proxy Signatures. CARDIS '98.

[22]

O. Goldreich, B. Pfitzmann, and R.L. Rivest. Self-Delegation with Controlled Propagation - or - What if You Lose Your Laptop? Crypto '98.

[23]

S. Goldwasser, S. Micali, and R.L. Rivest. A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks. SIAM J. Computing 17(2): 281-308 (1988).

[24]

P. Indyk. Personal communication.

[25]

G. Itkis and L. Reyzin. Forward-Secure Signatures with Optimal Signing and Verifying. Crypto '01.

[26]

S. Jarecki and A. Lysyanskaya. Concurrent and Erasure-Free Models in Adaptively-Secure Threshold Cryptography. Eurocrypt '00.

[27]

H. Krawczyk. Secret SharingMade Short. Crypto '93.

[28]

H. Krawczyk. Simple Forward-Secure Signatures From any Signature Scheme. ACM CCCS '00.

[29]

R. Kumar, S. Rajagopalan, and A. Sahai. Coding Constructions for Blacklisting Problems without Computational Assumptions. Crypto '99.

[30]

C.-F. Lu and S.W. Shieh. Secure Key-EvolvingProto cols for Discrete Logarithm Schemes. RSA 2002, to appear.

[31]

T. Malkin, D. Micciancio, and S. Miner. Efficient Generic Forward-Secure Signatures With an Unbounded Number of Time Periods. These proceedings.

[32]

R. Ostrovsky and M. Yung. How to Withstand Mobile Virus Attacks. PODC '91.

[33]

T. Pedersen. Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. Crypto '91.

[34]

R. Rivest. All-or-NothingEncryption and the Package Transform. FSE '97.

[35]

A. Shamir. How to share a secret. Comm. ACM , 22(11):612-613, 1979.

[36]

W.-G. Tzengand Z.-J. Tzeng. Robust Key-EvolvingPublic-Key Encryption Schemes. Available at http://eprint.iacr.org.

Cited By

Shikata JWatanabe Y(2019)Identity-based encryption with hierarchical key-insulation in the standard modelDesigns, Codes and Cryptography10.1007/s10623-018-0503-487:5(1005-1033)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1007/s10623-018-0503-4
Lee KChoi SLee DPark JYung M(2017)Self-updatable encryptionTheoretical Computer Science10.1016/j.tcs.2016.12.027667:C(51-92)Online publication date: 8-Mar-2017
https://dl.acm.org/doi/10.1016/j.tcs.2016.12.027
Itkis GShen EVaria MWilson DYerukhimovich A(2017)Bounded-Collusion Attribute-Based Encryption from Minimal AssumptionsProceedings, Part II, of the 20th IACR International Conference on Public-Key Cryptography --- PKC 2017 - Volume 1017510.1007/978-3-662-54388-7_3(67-87)Online publication date: 28-Mar-2017
https://dl.acm.org/doi/10.1007/978-3-662-54388-7_3
Show More Cited By

Key-Insulated Public Key Cryptosystems

Recommendations

Securely combining public-key cryptosystems
CCS '01: Proceedings of the 8th ACM conference on Computer and Communications Security

It is a maxim of sound computer-security practice that a cryptographic key should have only a single use. For example, an RSA key pair should be used only for public-key encryption or only for digital signatures, and not for both.In this paper we show ...
Timed-release and key-insulated public key encryption
FC'06: Proceedings of the 10th international conference on Financial Cryptography and Data Security

In this paper we consider two security notions related to Identity Based Encryption: Key-insulated public key encryption, introduced by Dodis, Katz, Xu and Yung; and Timed-Release Public Key cryptography, introduced independently by May and Rivest, ...
Chosen ciphertext secure keyed-homomorphic public-key cryptosystems

In homomorphic encryption schemes, anyone can perform homomorphic operations, and therefore, it is difficult to manage when, where and by whom they are performed. In addition, the property that anyone can "freely" perform the operation inevitably means ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

EUROCRYPT '02: Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology

May 2002

545 pages

ISBN:3540435530

Editor:
Lars R. Knudsen

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 02 May 2002

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

79
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Shikata JWatanabe Y(2019)Identity-based encryption with hierarchical key-insulation in the standard modelDesigns, Codes and Cryptography10.1007/s10623-018-0503-487:5(1005-1033)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1007/s10623-018-0503-4
Lee KChoi SLee DPark JYung M(2017)Self-updatable encryptionTheoretical Computer Science10.1016/j.tcs.2016.12.027667:C(51-92)Online publication date: 8-Mar-2017
https://dl.acm.org/doi/10.1016/j.tcs.2016.12.027
Itkis GShen EVaria MWilson DYerukhimovich A(2017)Bounded-Collusion Attribute-Based Encryption from Minimal AssumptionsProceedings, Part II, of the 20th IACR International Conference on Public-Key Cryptography --- PKC 2017 - Volume 1017510.1007/978-3-662-54388-7_3(67-87)Online publication date: 28-Mar-2017
https://dl.acm.org/doi/10.1007/978-3-662-54388-7_3
Yamada S(2016)Adaptively Secure Identity-Based Encryption from Lattices with Asymptotically Shorter Public ParametersProceedings, Part II, of the 35th Annual International Conference on Advances in Cryptology --- EUROCRYPT 2016 - Volume 966610.5555/3081738.3081740(32-62)Online publication date: 8-May-2016
https://dl.acm.org/doi/10.5555/3081738.3081740
Thangam VChandrasekaran K(2016)Elliptic Curve Based Proxy Re-EncryptionProceedings of the Second International Conference on Information and Communication Technology for Competitive Strategies10.1145/2905055.2905337(1-6)Online publication date: 4-Mar-2016
https://dl.acm.org/doi/10.1145/2905055.2905337
Xiang TLi XChen FMu YChen XWang XHuang X(2016)Bilateral-secure Signature by Key EvolvingProceedings of the 11th ACM on Asia Conference on Computer and Communications Security10.1145/2897845.2897864(523-533)Online publication date: 30-May-2016
https://dl.acm.org/doi/10.1145/2897845.2897864
Rao YDutta R(2016)Bandwidth-efficient attribute-based key-insulated signatures with message recoveryInformation Sciences: an International Journal10.1016/j.ins.2016.07.039369:C(648-673)Online publication date: 10-Nov-2016
https://dl.acm.org/doi/10.1016/j.ins.2016.07.039
Hartung GKaidel BKoch AKoch JRupp A(2016)Fault-Tolerant Aggregate SignaturesProceedings, Part I, of the 19th IACR International Conference on Public-Key Cryptography --- PKC 2016 - Volume 961410.1007/978-3-662-49384-7_13(331-356)Online publication date: 6-Mar-2016
https://dl.acm.org/doi/10.1007/978-3-662-49384-7_13
Watanabe YShikata J(2016)Identity-Based Hierarchical Key-Insulated Encryption Without Random OraclesProceedings, Part I, of the 19th IACR International Conference on Public-Key Cryptography --- PKC 2016 - Volume 961410.1007/978-3-662-49384-7_10(255-279)Online publication date: 6-Mar-2016
https://dl.acm.org/doi/10.1007/978-3-662-49384-7_10
Yang GLiu JHan L(2016)An ID-based node key management scheme based on PTPM in MANETsSecurity and Communication Networks10.1002/sec.12069:15(2816-2826)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1002/sec.1206
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents