TY - GEN
T1 - Efficient public-key cryptography in the presence of key leakage
AU - Dodis, Yevgeniy
AU - Haralambiev, Kristiyan
AU - López-Alt, Adriana
AU - Wichs, Daniel
PY - 2010
Y1 - 2010
N2 - We study the design of cryptographic primitives resistant to a large class of side-channel attacks, called "memory attacks", where an attacker can repeatedly and adaptively learn information about the secret key, subject only to the constraint that the overall amount of such information is bounded by some parameter ℓ. Although the study of such primitives was initiated only recently by Akavia et al. [2], subsequent work already produced many such "leakage-resilient" primitives [48,4,42], including signature, encryption, identification (ID) and authenticated key agreement (AKA) schemes. Unfortunately, every existing scheme, - for any of the four fundamental primitives above, - fails to satisfy at least one of the following desirable properties: - Efficiency. While the construction may be generic, it should have some efficient instantiations, based on standard cryptographic assumptions, and without relying on random oracles. - Strong Security. The construction should satisfy the strongest possible definition of security (even in the presence of leakage). For example, encryption schemes should be secure against chosen ciphertext attack (CCA), while signatures should be existentially unforgeable. - Leakage Flexibility. It should be possible to set the scheme parameters so that the leakage bound ℓ can come arbitrarily close to the secret-key size. In this work we design the first signature, encryption, ID and AKA schemes which overcome these limitations, and satisfy all the properties above. Moreover, all our constructions are generic, in several cases elegantly simplifying and generalizing the prior constructions (which did not have any efficient instantiations). We also introduce several tools of independent interest, such as the abstraction (and constructions) of true-simulation extractable NIZK arguments, and a new deniable DH-based AKA protocol based on any CCA-secure encryption.
AB - We study the design of cryptographic primitives resistant to a large class of side-channel attacks, called "memory attacks", where an attacker can repeatedly and adaptively learn information about the secret key, subject only to the constraint that the overall amount of such information is bounded by some parameter ℓ. Although the study of such primitives was initiated only recently by Akavia et al. [2], subsequent work already produced many such "leakage-resilient" primitives [48,4,42], including signature, encryption, identification (ID) and authenticated key agreement (AKA) schemes. Unfortunately, every existing scheme, - for any of the four fundamental primitives above, - fails to satisfy at least one of the following desirable properties: - Efficiency. While the construction may be generic, it should have some efficient instantiations, based on standard cryptographic assumptions, and without relying on random oracles. - Strong Security. The construction should satisfy the strongest possible definition of security (even in the presence of leakage). For example, encryption schemes should be secure against chosen ciphertext attack (CCA), while signatures should be existentially unforgeable. - Leakage Flexibility. It should be possible to set the scheme parameters so that the leakage bound ℓ can come arbitrarily close to the secret-key size. In this work we design the first signature, encryption, ID and AKA schemes which overcome these limitations, and satisfy all the properties above. Moreover, all our constructions are generic, in several cases elegantly simplifying and generalizing the prior constructions (which did not have any efficient instantiations). We also introduce several tools of independent interest, such as the abstraction (and constructions) of true-simulation extractable NIZK arguments, and a new deniable DH-based AKA protocol based on any CCA-secure encryption.
UR - http://www.scopus.com/inward/record.url?scp=78650817944&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=78650817944&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-17373-8_35
DO - 10.1007/978-3-642-17373-8_35
M3 - Conference contribution
AN - SCOPUS:78650817944
SN - 3642173721
SN - 9783642173721
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 613
EP - 631
BT - Advances in Cryptology, ASIACRYPT 2010 - 16th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
PB - Springer Verlag
T2 - 16th Annual International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2010
Y2 - 5 December 2010 through 9 December 2010
ER -