research-article

How to keep a secret: leakage deterring public-key cryptosystems

Authors:

Aggelos Kiayias,

Qiang TangAuthors Info & Claims

CCS '13: Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security

Pages 943 - 954

https://doi.org/10.1145/2508859.2516691

Published: 04 November 2013 Publication History

Get Access

Abstract

How is it possible to prevent the sharing of cryptographic functions? This question appears to be fundamentally hard to address since in this setting the owner of the key is the adversary: she wishes to share a program or device that (potentially only partly) implements her main cryptographic functionality. Given that she possesses the cryptographic key, it is impossible for her to be prevented from writing code or building a device that uses that key. She may though be deterred from doing so. We introduce leakage-deterring public-key cryptosystems to address this problem. Such primitives have the feature of enabling the embedding of owner-specific private data into the owner's public-key so that given access to any (even partially functional) implementation of the primitive, the recovery of the data can be facilitated. We formalize the notion of leakage-deterring in the context of encryption, signature, and identification and we provide efficient generic constructions that facilitate the recoverability of the hidden data while retaining privacy as long as no sharing takes place.

References

[1]

M. Bellare and O. Goldreich. On defining proofs of knowledge. In CRYPTO, pages 390--420, 1992.

Digital Library

Google Scholar

[2]

M. Bellare and G. Neven. Multi-signatures in the plain public-key model and a general forking lemma. In ACM CCS, pages 390--399, 2006.

Digital Library

Google Scholar

[3]

M. Bellare and P. Rogaway. Random oracles are practical: A paradigm for designing efficient protocols In ACM CCS, pages 62--73, 1993.

Digital Library

Google Scholar

[4]

J. Camenisch and A. Lysyanskaya. An efficient systemfor non-transferable anonymous credentials with optional anonymity revocation. In EUROCRYPT, pages 93--118, 2001.

Digital Library

Google Scholar

[5]

R. Canetti, M. Charikar, S. R. Sridhar Rajagopalan, A. Sahai, and A. Tomkins. Non-transferrable anonymous credentials. US Patent 7,222,362., 2008.

Google Scholar

[6]

B. Chor, A. Fiat, and M. Naor. Tracing traitors. In CRYPTO, pages 257--270, 1994.

Digital Library

Google Scholar

[7]

R. Cramer and V. Shoup. Design and analysis ofpractical public-key encryption schemes secure againstadaptive chosen ciphertext attack. SIAM J. Comput., 33(1):167--226, 2004.

Digital Library

Google Scholar

[8]

I. Damgard. On o-protocols. In http://www.daimi.au.dk/ ivan/Sigma.pdf, 2010.

Google Scholar

[9]

C. Dwork, J. B. Lotspiech, and M. Naor. Digital signets: Self-enforcing protection of digital information (preliminary version). In STOC, pages 489--498, 1996.

Digital Library

Google Scholar

[10]

S. Dziembowski and K. Pietrzak. Leakage-resilient cryptography. In FOCS, pages 293--302, 2008.

Digital Library

Google Scholar

[11]

A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. In CRYPTO, pages 186--194, 1986.

Digital Library

Google Scholar

[12]

O. Goldreich and L. A. Levin. A hard-core predicate for all one-way functions. In STOC, pages 25--32, 1989.

Digital Library

Google Scholar

[13]

O. Goldreich, B. Pfitzmann, and R. L. Rivest. Self-delegation with controlled propagation-or-what if you lose your laptop. In CRYPTO, pages 153--168, 1998.

Digital Library

Google Scholar

[14]

P. Golle, F. McSherry, and I. Mironov. Data collection with self-enforcing privacy. In ACM CCS, pages 69--78, 2006.

Digital Library

Google Scholar

[15]

V. Goyal. Reducing trust in the pkg in identity based cryptosystems. In CRYPTO, pages 430--447, 2007.

Digital Library

Google Scholar

[16]

V. Goyal, S. Lu, A. Sahai, and B. Waters. Black-box accountable authority identity-based encryption. In ACM CCS, pages 427--436, 2008.

Digital Library

Google Scholar

[17]

V. Guruswami and P. Indyk. Expander-based constructions of efficiently decodable codes. In FOCS, pages 658{667, 2001.

Digital Library

Google Scholar

[18]

S. Haber and B. Pinkas. Securely combining public-key cryptosystems. In ACM CCS, pages 215--224, 2001.

Digital Library

Google Scholar

[19]

C.-Y. Hsiao, C.-J. Lu, and L. Reyzin. Conditional computational entropy, or toward separating pseudoentropy from compressibility. In EUROCRYPT, pages 169--186, 2007.

Digital Library

Google Scholar

[20]

Y. Ishai, A. Sahai, and D. Wagner. Private circuits: Securing hardware against probing attacks. In CRYPTO, pages 463--481, 2003.

Crossref

Google Scholar

[21]

M. Jakobsson, A. Juels, and P. Q. Nguyen. Proprietary certificates. In CT-RSA, pages 164--181, 2002.

Digital Library

Google Scholar

[22]

A. Kiayias and M. Yung. Breaking and repairing asymmetric public-key traitor tracing. In Digital Rights Management Workshop, pages 32--50, 2002.

Google Scholar

[23]

A. Kiayias and M. Yung. Traitor tracing with constant transmission rate. In EUROCRYPT, pages 450--465, 2002.

Digital Library

Google Scholar

[24]

H. Komaki, Y. Watanabe, G. Hanaoka, and H. Imai. Efficient asymmetric self-enforcement scheme with public traceability. In Public Key Cryptography, pages 225--239, 2001.

Digital Library

Google Scholar

[25]

B. Libert and D. Vergnaud. Towards black-box accountable authority ibe with short ciphertexts and private keys. In Public Key Cryptography, pages 235--255, 2009.

Digital Library

Google Scholar

[26]

H. Lipmaa, G. Wang, and F. Bao. Designated verifier signature schemes: Attacks, new security notions and a new construction. In ICALP, pages 459--471, 2005.

Digital Library

Google Scholar

[27]

A. Lysyanskaya, R. L. Rivest, A. Sahai, and S. Wolf. Pseudonym systems. In International Workshop on Selected Areas in Cryptography, SAC '99, pages 184--199, 2000.

Digital Library

Google Scholar

[28]

D. Naccache, A. Shamir, and J. P. Stern. How to copyright a function? In Public Key Cryptography, pages 188--196, 1999.

Digital Library

Google Scholar

[29]

D. Pointcheval and J. Stern. Security arguments for digital signatures and blind signatures. J. Cryptology, 13(3):361--396, 2000.

Digital Library

Google Scholar

[30]

A. Sahai and H. Seyalioglu. Fully secure accountable-authority identity-based encryption. In Public Key Cryptography, pages 296--316, 2011.

Digital Library

Google Scholar

[31]

T. Sander and A. Ta-Shma. Auditable, anonymous electronic cash extended abstract. In CRYPTO, pages 555--572, 1999.

Digital Library

Google Scholar

[32]

S. F. Shahandashti and R. Safavi-Naini. Construction of universal designated-verifier signatures and identity-based signatures from standard signatures. In Public Key Cryptography, pages 121--140, 2008.

Digital Library

Google Scholar

Cited By

View all

Mangipudi ERao KClark JKate A(2023)Pepal: Penalizing multimedia breaches and partial leakagesInternational Journal of Information Security10.1007/s10207-023-00744-523:1(447-465)Online publication date: 14-Sep-2023
https://doi.org/10.1007/s10207-023-00744-5
Dziembowski SFaust SLizurej T(2023)Individual CryptographyAdvances in Cryptology – CRYPTO 202310.1007/978-3-031-38545-2_18(547-579)Online publication date: 20-Aug-2023
https://dl.acm.org/doi/10.1007/978-3-031-38545-2_18
Zhang JLi TJiang QMa J(2022)Enabling efficient traceable and revocable time-based data sharing in smart cityEURASIP Journal on Wireless Communications and Networking10.1186/s13638-021-02072-52022:1Online publication date: 4-Jan-2022
https://doi.org/10.1186/s13638-021-02072-5
Show More Cited By

Index Terms

How to keep a secret: leakage deterring public-key cryptosystems
1. Security and privacy
  1. Cryptography
    1. Public key (asymmetric) techniques
      1. Public key encryption
2. Social and professional topics
  1. Computing / technology policy
    1. Computer crime

Recommendations

Traitor Deterring Schemes: Using Bitcoin as Collateral for Digital Content
CCS '15: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security

We put forth a new cryptographic primitive called a Traitor Deterring Scheme (TDS). A TDS is a multi-recipient public-key encryption scheme where an authority issues decryption keys to a set of users. The distinguishing feature of a TDS is that secret-...
Adaptive CCA broadcast encryption with constant-size secret keys and ciphertexts

We consider designing public-key broadcast encryption schemes with constant-size secret keys and ciphertexts, achieving chosen-ciphertext security. We first argue that known CPA-to-CCA transforms currently do not yield such schemes. We then propose a ...
A Non-interactive Public-Key Distribution System

An identity-based non-interactive public key distribution system is presented that is based on a novel trapdoor one-way function allowing a trusted authority to compute the discrete logarithms modulo a publicly known composite number m while this is ...

Reviews

Reviewer: Patriciu V Victor-Valeriu

Any implementation of the cryptographic function leads to the recovery of some private information by some third-party entities. The paper tackles the problem of leakage deterring in public-key cryptosystems. The authors clearly present their proposed idea and implementation, and also talk in detail about the main security requirements needed for the algorithms at each step. They emphasize the fact that any leakage deterring primitive should offer privacy and recoverability for the owner. This means that as long as no implementation of the primitive is leaked, the user is safe. It is also important that the introduction of the additional functionality does not disturb the standard cryptographic properties of the primitive. The construction starts with a comparison against additive homomorphic encryption schemes and a security analysis in which the authors analyze correctness and the security properties. The identification of leakage deterring signatures, in order to prevent forgeries and impersonations by an adversary, is also discussed. “The security proofs of these signatures rely on the fact that if the adversary can forge one signature, then he could also forge another correlated signature for the same message with the same random [input] but a different random oracle,” leading to the extraction of the secret key. The signature algorithm is “based on two independent digital signatures ... that are unforgeable under adaptively chosen message attacks.” Finally, the authors present some applications of their algorithms in practice. More exactly, depending on the application scenario, they embedded various types of private owner information to prevent the leakage of a cryptographic functionality, such as self-enforcement, all-or-nothing sharing of cryptographic functions, and anonymity revocation from implementations. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

CCS '13: Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security

November 2013

1530 pages

ISBN:9781450324779

DOI:10.1145/2508859

General Chair:
Ahmad-Reza Sadeghi
TU Darmstadt, CASED, Intel ICRI-SC, Germany
,
Program Chairs:
Virgil Gligor
Carnegie Mellon University, USA
,
Moti Yung
Columbia University, USA

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 November 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CCS'13

Sponsor:

SIGSAC

CCS'13: 2013 ACM SIGSAC Conference on Computer and Communications Security

November 4 - 8, 2013

Berlin, Germany

Acceptance Rates

CCS '13 Paper Acceptance Rate 105 of 530 submissions, 20%;

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
451
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)2

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Mangipudi ERao KClark JKate A(2023)Pepal: Penalizing multimedia breaches and partial leakagesInternational Journal of Information Security10.1007/s10207-023-00744-523:1(447-465)Online publication date: 14-Sep-2023
https://doi.org/10.1007/s10207-023-00744-5
Dziembowski SFaust SLizurej T(2023)Individual CryptographyAdvances in Cryptology – CRYPTO 202310.1007/978-3-031-38545-2_18(547-579)Online publication date: 20-Aug-2023
https://dl.acm.org/doi/10.1007/978-3-031-38545-2_18
Zhang JLi TJiang QMa J(2022)Enabling efficient traceable and revocable time-based data sharing in smart cityEURASIP Journal on Wireless Communications and Networking10.1186/s13638-021-02072-52022:1Online publication date: 4-Jan-2022
https://doi.org/10.1186/s13638-021-02072-5
Li YSusilo WYang GYu YPhuong TLiu DCao JHo Au MLin ZYung M(2021)Non-Equivocation in Blockchain: Double-Authentication-Preventing Signatures Gone ContractualProceedings of the 2021 ACM Asia Conference on Computer and Communications Security10.1145/3433210.3437516(859-871)Online publication date: 24-May-2021
https://dl.acm.org/doi/10.1145/3433210.3437516
Kim SWu D(2021)Watermarking Cryptographic Functionalities from Standard Lattice AssumptionsJournal of Cryptology10.1007/s00145-021-09391-234:3Online publication date: 26-May-2021
https://doi.org/10.1007/s00145-021-09391-2
Ning JCao ZDong XWei L(2018)White-Box Traceable CP-ABE for Cloud Storage Service: How to Catch People Leaking Their Access Credentials EffectivelyIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2016.260834315:5(883-897)Online publication date: 1-Sep-2018
https://doi.org/10.1109/TDSC.2016.2608343
Lai JTang Q(2018)Making Any Attribute-Based Encryption Accountable, EfficientlyComputer Security10.1007/978-3-319-98989-1_26(527-547)Online publication date: 7-Aug-2018
https://doi.org/10.1007/978-3-319-98989-1_26
Poettering BStebila D(2017)Double-authentication-preventing signaturesInternational Journal of Information Security10.1007/s10207-015-0307-816:1(1-22)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1007/s10207-015-0307-8
Baldimtsi FKiayias ASamari K(2017)Watermarking Public-Key Cryptographic Functionalities and ImplementationsInformation Security10.1007/978-3-319-69659-1_10(173-191)Online publication date: 20-Oct-2017
https://doi.org/10.1007/978-3-319-69659-1_10
Kiayias ATang QRay ILi NKruegel C(2015)Traitor Deterring SchemesProceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security10.1145/2810103.2813698(231-242)Online publication date: 12-Oct-2015
https://dl.acm.org/doi/10.1145/2810103.2813698
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Traitor Deterring Schemes: Using Bitcoin as Collateral for Digital Content

Adaptive CCA broadcast encryption with constant-size secret keys and ciphertexts

A Non-interactive Public-Key Distribution System

Reviews

Access critical reviews of Computing literature here