research-article

On cryptography with auxiliary input

Authors:

Yevgeniy Dodis,

Yael Tauman Kalai,

Shachar LovettAuthors Info & Claims

STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

Pages 621 - 630

https://doi.org/10.1145/1536414.1536498

Published: 31 May 2009 Publication History

Abstract

We study the question of designing cryptographic schemes which are secure even if an arbitrary function f(sk) of the secret key is leaked, as long as the secret key sk is still (exponentially) hard to compute from this auxiliary input. This setting of auxiliary input is more general than the more traditional setting, which assumes that some of information about the secret key sk may be leaked, but sk still has high min-entropy left. In particular, we deal with situations where f(sk) information-theoretically determines the entire secret key sk.

As our main result, we construct CPA/CCA secure symmetric encryption schemes that remain secure with exponentially hard-to-invert auxiliary input. We give several applications of such schemes. * We construct an average-case obfuscator for the class of point functions, which remains secure with exponentially hard-to-invert auxiliary input, and is reusable. * We construct a reusable and robust extractor that remains secure with exponentially hard-to-invert auxiliary input. Our results rely on a new cryptographic assumption, Learning Subspace-with-Noise (LSN), which is related to the well known Learning Parity-with-Noise (LPN) assumption.

References

[1]

A. Akavia, S. Goldwasser, and V. Vaikuntanathan. Simultaneous Hardcore Bits and Cryptography Against Memory Attacks. In TCC 2009.

Digital Library

[2]

B. Applebaum. Fast Cryptographic Primitives Based on the Hardness of Decoding Random Linear Code. Unpublished Manuscript.

[3]

B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. P. Vadhan, and K. Yang. On the (Im)possibility of Obfuscating Programs. In CRYPTO 2001: 1--18.

Digital Library

[4]

B. Barak, R. Shaltiel, and A. Wigderson. Computational analogues of entropy. In Proc. of 7th Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), 2003.

[5]

M. Bellare and C. Namprempre. Authenticated encryption: Relations among notions and analysis of the generic composition paradigm In Advances in Cryptology -- ASIACRYPT}, volume 1976 of Lecture Notes in Computer Science, pp. 531--545, 2000.

Digital Library

[6]

A. Blum, M. L. Furst, M. J. Kearns, and R. J. Lipton. Cryptographic Primitives Based on Hard Learning Problems. In CRYPTO 1993: 278--291.

Digital Library

[7]

A. Blum, A. Kalai, and H. Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. In STOC 2000: 435--440.

Digital Library

[8]

X. Boyen. Reusable cryptographic fuzzy extractors. In ACM Conference on Computer and Communications Security 2004: 82--91.

Digital Library

[9]

X. Boyen, Y. Dodis, J. Katz, R. Ostrovsky, A. Smith. Secure Remote Authentication Using Biometric Data. In EUROCRYPT, pp. 147--163, 2005.

Digital Library

[10]

R. Canetti. Towards Realizing Random Oracles: Hash Functions That Hide All Partial Information. In CRYPTO 1997: 455--469.

Digital Library

[11]

R. Canetti, R. R. Dakdouk. Obfuscating Point Functions with Multibit Output. In EUROCRYPT 2008: 489--508.

Digital Library

[12]

R. Canetti, Y. Dodis, S. Halevi, E. Kushilevitz, and A. Sahai. Exposure-Resilient Functions and All-or-Nothing Transforms. In EUROCRYPT 2000: 453--469.

Digital Library

[13]

R. Canetti, D. Eiger, S. Goldwasser, and D. Lim. How to Protect Yourself without Perfect Shredding. In ICALP (2) 2008: 511--523.

Digital Library

[14]

R. Canetti, D. Micciancio, and O. Reingold. Perfectly One-Way Probabilistic Hash Functions (Preliminary Version). In STOC 1998: 131--140.

Digital Library

[15]

D. Cash, Y. Z. Ding, Y. Dodis, W. Lee, R. J. Lipton, and S. Walfish. Intrusion--Resilient Key Exchange in the Bounded Retrieval Model. In TCC 2007: 479--498.

Digital Library

[16]

J. Coron, M. Joye, D. Naccache, and P. Paillier. Universal Padding Schemes for RSA. In CRYPTO 2002: 226--241.

Digital Library

[17]

G. Di Crescenzo, R. Lipton and S. Walfish. Perfectly Secure Password Protocols in the Bounded Retrieval Model. In Theory of Cryptography Conference}, pp. 225--244, 2006.

Digital Library

[18]

Y. Dodis. PhD Thesis, "Exposure-Resilient Cryptography". Massachussetts Institute of Technology, August 2000.

Digital Library

[19]

Y. Dodis, Y. Kalai, and S. Lovett. On Cryptiography with Auxiliary Input. Preliminary version in STOC 2009. Full Version.

Digital Library

[20]

Y. Dodis, J. Katz, L. Reyzin, and A. Smith. Robust Fuzzy Extractors and Authenticated Key Agreement from Close Secrets. In CRYPTO 2006: 232--250.

Digital Library

[21]

Y. Dodis, R. Ostrovsky, L. Reyzin, and A. Smith. Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. In SIAM Journal of Computing, 38(1):97--139, 2008.

Digital Library

[22]

Y. Dodis, L. Reyzin, A. Smith. Fuzzy Extractors. In Security with Noisy Data (edited by Pim Tuyls, Boris Skoric, and Tom Kevenaar), Springer, 2007.

[23]

Y. Dodis, A. Sahai, and A. Smith. On Perfect and Adaptive Security in Exposure-Resilient Cryptography. In EUROCRYPT 2001: 301--324.

Digital Library

[24]

Y. Dodis, A. Smith. Correcting Errors Without Leaking Partial Information In STOC 2005: 654--663.

Digital Library

[25]

S. Dziembowski. On Forward-Secure Storage. In CRYPTO 2006: 251--270.

Digital Library

[26]

S. Dziembowski. Intrusion-Resilience Via the Bounded-Storage Model. In TCC 2006: 207--224.

Digital Library

[27]

S. Dziembowski and K. Pietrzak. Intrusion-Resilient Secret Sharing. In FOCS 2007: 227--237.

Digital Library

[28]

S. Dziembowski and K. Pietrzak. Leakage-Resilient Cryptography. In FOCS 2008: 293--302.

Digital Library

[29]

G. Forney. Concatenated Codes. MIT Press, Cambridge, MA, 1966.

[30]

S. Goldwasser and Y. T. Kalai. On the Impossibility of Obfuscation with Auxiliary Input. In FOCS 2005: 553--562.

Digital Library

[31]

O. Goldreich and L. A. Levin. A Hard-Core Predicate for all One-Way Functions. In STOC 1989: 25--32.

Digital Library

[32]

S. Goldwasser and G. N. Rothblum. On Best-Possible Obfuscation. In TCC 2007: 194--213.

Digital Library

[33]

S. Haber and B. Pinkas. Securely combining public-key cryptosystems. In ACM Conference on Computer and Communications Security 2001:215--224.

Digital Library

[34]

S. Hada. Zero-Knowledge and Code Obfuscation. In ASIACRYPT 2000: 443--457.

Digital Library

[35]

D. Hofheinz, J. Malone-Lee and M. Stam. Obfuscation for Cryptographic Purposes. In TCC 2007: 214--232.

Digital Library

[36]

S. Hohenberger, G. N. Rothblum, A. Shelat, and V. Vaikuntanathan. Securely Obfuscating Re-encryption. In TCC 2007: 233--252.

Digital Library

[37]

N. J. Hopper, Manuel Blum. Secure Human Identification Protocols. In ASIACRYPT 2001:52--66.

Digital Library

[38]

C. Hsiao, C. Lu, and L. Reyzin. Conditional Computational Entropy, or Toward Separating Pseudoentropy from Compressibility. In EUROCRYPT 2007: 169--186.

Digital Library

[39]

Y. Ishai, M. Prabhakaran, A. Sahai, and D. Wagner. Private Circuits II: Keeping Secrets in Tamperable Circuits. In EUROCRYPT 2006: 308--327.

Digital Library

[40]

Y. Ishai, A. Sahai, and D. Wagner. Private Circuits: Securing Hardware against Probing Attacks. In CRYPTO 2003: 463--481.

[41]

A. Juels and S. A. Weis. Authenticating Pervasive Devices with Human Protocols. In CRYPTO 2005:293--308.

Digital Library

[42]

J. Katz and J. S. Shin. Parallel and Concurrent Security of the HB and HB+ Protocols. In EUROCRYPT 2006: 73--87.

Digital Library

[43]

B. Lynn, M. Prabhakaran, and A. Sahai. Positive Results and Techniques for Obfuscation. In EUROCRYPT 2004: 20--39.

[44]

S. Micali and L. Reyzin. Physically Observable Cryptography (Extended Abstract). In TCC 2004: 278--296.

[45]

M. Naor. On Cryptographic Assumptions and Challenges. In CRYPTO 2003: 96--109.

[46]

M. Naor and M Ying. Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks. In STOC 1990: 427--437.

Digital Library

[47]

N. Nisan and D. Zuckerman. More deterministic simulation in logspace. In STOC, pp. 235--244, 1993.

Digital Library

[48]

K. Pietrzak. A Leakage-Resilient Mode of Operation. In EUROCRYPT 2009.

[49]

R. Raz. Private communication.

[50]

O. Regev. On lattices, learning with errors, random linear codes, and cryptography. In STOC 2005: 84--93.

Digital Library

[51]

A. Sahai. Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security. In FOCS, pp. 543--553, 1999.

Digital Library

[52]

A.Shamir. Identity-Based Cryptosystems and Signature Schemes. In CRYPTO 1984: 47--53.

Digital Library

[53]

Hoeteck Wee. On obfuscating point functions. In STOC, pp. 523--532.

Digital Library

[54]

D. Zuckerman. Private communication.

Cited By

Hazay CVenkitasubramaniam MWeiss M(2024)Protecting Distributed Primitives Against Leakage: Equivocal Secret Sharing and moreJournal of Cryptology10.1007/s00145-024-09524-338:1Online publication date: 30-Oct-2024
https://doi.org/10.1007/s00145-024-09524-3
Zhang YLing YChen JWang L(2024)Leakage-Resilient Attribute-Based Encryption with Attribute-HidingInformation Security and Cryptology – ICISC 202310.1007/978-981-97-1238-0_7(113-132)Online publication date: 8-Mar-2024
https://doi.org/10.1007/978-981-97-1238-0_7
Liu HWang XYang KYu Y(2024)The Hardness of LPN over Any Integer Ring and Field for PCG ApplicationsAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58751-1_6(149-179)Online publication date: 26-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58751-1_6
Show More Cited By

Index Terms

On cryptography with auxiliary input
1. Theory of computation

Recommendations

Adaptively secure forward-secure non-interactive threshold cryptosystems
Inscrypt'11: Proceedings of the 7th international conference on Information Security and Cryptology

Threshold cryptography aims at enhancing the availability and security of decryption and signature schemes by splitting private keys into several (say n) shares (typically, each of size comparable to the original secret key). In these schemes, a quorum ...
Adaptively secure non-interactive threshold cryptosystems
ICALP'11: Proceedings of the 38th international conference on Automata, languages and programming - Volume Part II

Threshold cryptography aims at enhancing the availability and security of decryption and signature schemes by splitting private keys into several (say n) shares (typically, each of size comparable to the original secret key). In these schemes, a quorum ...
Adaptively secure non-interactive threshold cryptosystems

Threshold cryptography aims at enhancing the availability and security of decryption and signature schemes by splitting private keys into several (say n) shares (typically, each of size comparable to the original secret key). In these schemes, a quorum ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

May 2009

750 pages

ISBN:9781605585062

DOI:10.1145/1536414

Program Chair:
Michael Mitzenmacher
Harvard University

Copyright © 2009 ACM.

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 May 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '09

Sponsor:

STOC '09: Symposium on Theory of Computing

May 31 - June 2, 2009

MD, Bethesda, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

151
Total Citations
View Citations
864
Total Downloads

Downloads (Last 12 months)56
Downloads (Last 6 weeks)1

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hazay CVenkitasubramaniam MWeiss M(2024)Protecting Distributed Primitives Against Leakage: Equivocal Secret Sharing and moreJournal of Cryptology10.1007/s00145-024-09524-338:1Online publication date: 30-Oct-2024
https://doi.org/10.1007/s00145-024-09524-3
Zhang YLing YChen JWang L(2024)Leakage-Resilient Attribute-Based Encryption with Attribute-HidingInformation Security and Cryptology – ICISC 202310.1007/978-981-97-1238-0_7(113-132)Online publication date: 8-Mar-2024
https://doi.org/10.1007/978-981-97-1238-0_7
Liu HWang XYang KYu Y(2024)The Hardness of LPN over Any Integer Ring and Field for PCG ApplicationsAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58751-1_6(149-179)Online publication date: 26-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58751-1_6
Cimorelli Belfiore RDe Cosmo AFerrara A(2024)Identity-Based Matchmaking Encryption from Standard Lattice AssumptionsApplied Cryptography and Network Security10.1007/978-3-031-54773-7_7(163-188)Online publication date: 29-Feb-2024
https://doi.org/10.1007/978-3-031-54773-7_7
Boyen XLi Q(2024)Identity-Based Matchmaking Encryption with Enhanced Privacy – A Generic Construction with Practical InstantiationsComputer Security – ESORICS 202310.1007/978-3-031-51476-0_21(425-445)Online publication date: 11-Jan-2024
https://doi.org/10.1007/978-3-031-51476-0_21
Cai CPan SYuen TYiu S(2023)Practical fully leakage resilient signatures with auxiliary inputsFuture Generation Computer Systems10.1016/j.future.2022.11.027141:C(448-461)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1016/j.future.2022.11.027
Bossert JList ELucks S(2023)Implicit Key-Stretching Security of Encryption SchemesInformation Security and Cryptology – ICISC 202210.1007/978-3-031-29371-9_2(17-40)Online publication date: 31-Mar-2023
https://doi.org/10.1007/978-3-031-29371-9_2
Cai CYuen TYiu S(2022)Hash Proof System with Auxiliary Inputs and Its Application2022 IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom)10.1109/TrustCom56396.2022.00018(52-59)Online publication date: Dec-2022
https://doi.org/10.1109/TrustCom56396.2022.00018
Tjuawinata IXing C(2022)Leakage-Resilient Secret Sharing With Constant Share SizeIEEE Transactions on Information Theory10.1109/TIT.2022.319840768:12(8228-8250)Online publication date: Dec-2022
https://doi.org/10.1109/TIT.2022.3198407
Brian GFaonio AObremski MRibeiro JSimkin MSkorski MVenturi D(2022)The Mother of All Leakages: How to Simulate Noisy Leakages via Bounded Leakage (Almost) for FreeIEEE Transactions on Information Theory10.1109/TIT.2022.319384868:12(8197-8227)Online publication date: Dec-2022
https://doi.org/10.1109/TIT.2022.3193848
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.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents