TL;DR
This paper introduces a novel framework for building leakage-resilient identification (ID) protocols in the bounded retrieval model (BRM) by transforming zero-knowledge proofs of storage (ZK-PoS). They present the first RSA-based ZK-PoS, which, when plugged into their framework, yields the first RSA-based ID protocol in the BRM, offering improved efficiency and relying on standard cryptographic assumptions.
What Problem Does This Paper Address?
In modern cryptography, schemes are often designed assuming adversaries can't learn any secret key information. However, real-world attacks like side-channel attacks and memory leakage can reveal partial information about secret keys. Leakage-resilient cryptosystems aim to maintain security even when such partial information is leaked, with the bounded retrieval model (BRM) being a prominent model where the adversary's leakage is strictly bounded.
Specifically, this paper tackles the problem of constructing identification schemes that are leakage-resilient in the BRM. Identification schemes allow a party (the prover) to prove their identity to another party (the verifier) using a secret key. The challenge is to design these schemes so that even if an adversary leaks a bounded amount of information about the prover's secret key, they still cannot impersonate a legitimate user. Existing solutions often rely on complex constructions or strong assumptions, and this paper seeks to provide a more practical and efficient approach.
Methods
The core contribution of this paper is a generic transformation that converts any computationally zero-knowledge (ZK) publicly-verifiable proof of storage (PoS) into a leakage-resilient identification scheme in the BRM.
Here's a breakdown of their approach:
- Proofs of Storage (PoS): A PoS is an interactive protocol where a server proves to a verifier that it is faithfully storing a file. Publicly-verifiable means anyone can check the proof, and computationally ZK means the verification process leaks no useful information about the file to a bounded adversary.
- The Transformation: The paper's framework uses the file itself as the secret key for the ID protocol and the PoS's state information as the public key. The prover then executes the PoS verification phase to prove possession of the file, which indirectly proves their identity.
- Zero-Knowledge PoS is Key: A crucial aspect is using a zero-knowledge PoS. This ensures that even if the adversary leaks some information about the file (up to the bound λ in the BRM), the ZK property prevents them from learning enough to successfully impersonate the prover. The ZK property guarantees that the verification process is "hiding" and doesn't reveal the file's contents.
- RSA-based ZK-PoS: To make this concrete, the authors construct a novel ZK-PoS scheme based on the standard RSA assumption. This is significant because it's the first ZK-PoS scheme based on RSA, and it's proven secure in the random oracle model (ROM).
Datasets
Not discussed in the paper.
Key Insights and Ideas
- ZK-PoS as a Building Block for Leakage Resilience: The paper demonstrates a powerful connection: ZK-PoS schemes are not just for data integrity but can be fundamental building blocks for leakage-resilient ID protocols in the BRM. This opens up new avenues for designing secure systems in the face of side-channel attacks.
- Efficiency Gains through RSA: By constructing a ZK-PoS based on RSA, the authors achieve a practical and efficient BRM-ID scheme. This is a significant improvement over prior constructions that might rely on more complex or less efficient cryptographic primitives.
- Bridging Theoretical Models and Practical Attacks: The work effectively bridges the gap between theoretical leakage models (like BRM) and practical security concerns arising from side-channel attacks, offering a concrete solution for secure identification in vulnerable environments.
- The Importance of "Knowledge Soundness": The paper emphasizes the role of "knowledge soundness" in PoS. This property, captured by an extractor, is crucial for proving that an adversary who successfully impersonates can be used to extract the secret file, thus breaking the security of the ID scheme.
Key Results
- Generic Transformation: A general method to construct BRM-ID schemes from ZK-PoS.
- First RSA-based ZK-PoS: The paper presents the first ZK-PoS scheme based on the standard RSA assumption, proven secure in the ROM.
- First RSA-based BRM-ID: This ZK-PoS, when used with their transformation, yields the first RSA-based ID protocol in the BRM.
- Efficiency: The proposed RSA-based BRM-ID scheme is shown to be more efficient than previously known constructions.
- Security Proofs: The paper provides formal security proofs for their constructions, relying on standard cryptographic assumptions.
Limitations and Future Work
- Open Problem: Efficient Compiler for Homomorphic ID to Leakage-Resilient ID: The authors note that while their work establishes a connection between homomorphic ID and leakage-resilient ID schemes (via PoS), an efficient compiler between PoS and ZK-PoS is still an open problem. This is a key missing piece for fully realizing the potential of their framework.
- RSA Group Size: A noted drawback of their RSA-based scheme is that RSA groups are larger than groups used in constructions based on the Gap Diffie-Hellman (GDH) assumption, which can impact performance.
- Secret Key Size vs. Leakage Tolerated: Another point of comparison is the ratio between the secret key size and the amount of leakage tolerated, where RSA-ID has a less favorable ratio compared to GDH-ID.
- Future Work: The paper suggests exploring efficient compilers for ZK-PoS and investigating further optimizations and applications of their framework.
Summary updated