Everlasting (EL) privacy offers an attractive solution to the Store-Now-Decrypt-Later (SNDL) problem, where future increases in the attacker's capability could break systems which are believed to be secure today. Instead of requiring full information-theoretic security, everlasting privacy allows computationally-secure transmissions of ephemeral secrets, which are only "effective" for a limited periods of time, after which their compromise is provably useless for the SNDL attacker. In this work we revisit such everlasting privacy model of Dodis and Yeo (ITC'21), which we call Hypervisor EverLasting Privacy (HELP). HELP is a novel architecture for generating shared randomness using a network of semi-trusted servers (or "hypervisors"), trading the need to store/distribute large shared secrets with the assumptions that it is hard to: (a) simultaneously compromise too many publicly accessible ad-hoc servers; and (b) break a computationally-secure encryption scheme very quickly. While Dodis and Yeo presented good HELP solutions in the asymptotic sense, their solutions were concretely expensive and used heavy tools (like large finite fields or gigantic Toeplitz matrices). We abstract and generalize the HELP architecture to allow for more efficient instantiations, and construct several concretely efficient HELP solutions. Our solutions use elementary cryptographic operations, such as hashing and message authentication. We also prove a very strong composition theorem showing that our EL architecture can use any message transmission method which is computationally-secure in the Universal Composability (UC) framework. This is the first positive composition result for everlasting privacy, which was otherwise known to suffer from many "non-composition" results (Müller-Quade and Unruh; J of Cryptology'10).
Everlasting (EL) privacy offers an attractive solution to the Store-Now-Decrypt-Later (SNDL) problem, where future increases in the attacker's capability could break systems which are believed to be secure today. Instead of requiring full information-theoretic security, everlasting privacy allows computationally-secure transmissions of ephemeral secrets, which are only "effective" for a limited periods of time, after which their compromise is provably useless for the SNDL attacker. In this work we revisit such everlasting privacy model of Dodis and Yeo (ITC'21), which we call Hypervisor EverLasting Privacy (HELP). HELP is a novel architecture for generating shared randomness using a network of semi-trusted servers (or "hypervisors"), trading the need to store/distribute large shared secrets with the assumptions that it is hard to: (a) simultaneously compromise too many publicly accessible ad-hoc servers; and (b) break a computationally-secure encryption scheme very quickly. While Dodis and Yeo presented good HELP solutions in the asymptotic sense, their solutions were concretely expensive and used heavy tools (like large finite fields or gigantic Toeplitz matrices). We abstract and generalize the HELP architecture to allow for more efficient instantiations, and construct several concretely efficient HELP solutions. Our solutions use elementary cryptographic operations, such as hashing and message authentication. We also prove a very strong composition theorem showing that our EL architecture can use any message transmission method which is computationally-secure in the Universal Composability (UC) framework. This is the first positive composition result for everlasting privacy, which was otherwise known to suffer from many "non-composition" results (Müller-Quade and Unruh; J of Cryptology'10).
In this work we challenge the common misconception that information-theoretic (IT) privacy is too impractical to be used in the real-world: we propose to build simple and reusable IT-encryption solutions whose only efficiency penalty (compared to computationally-secure schemes) comes from a large secret key size, which is often a rather minor inconvenience, as storage is cheap. In particular, our solutions are stateless and locally computable at the optimal rate, meaning that honest parties do not maintain state and read only (optimally) small portions of their large keys with every use. Moreover, we also propose a novel architecture for outsourcing the storage of these long keys to a network of semi-trusted servers, trading the need to store large secrets with the assumption that it is hard to simultaneously compromise too many publicly accessible ad-hoc servers. Our architecture supports everlasting privacy and post-application security of the derived one-time keys, resolving two major limitations of a related model for outsourcing key storage, called bounded storage model. Both of these results come from nearly optimal constructions of so called doubly-affine extractors: locally-computable, seeded extractors Ext(X,S) which are linear functions of X (for any fixed seed S), and protect against bounded affine leakage on X. This holds unconditionally, even if (a) affine leakage may adaptively depend on the extracted key R = Ext(X,S); and (b) the seed S is only computationally secure. Neither of these properties are possible with general-leakage extractors.
We address the problem of the-security of cryptographic protocols in face of future advances in computing technology and algorithmic research. The problem stems from the fact may be deemed that computations which at a given point in time may be deemed infeasible, can, in the course of years or decades, be made possible with improved hardware and/or breakthroughs in code-breaking algorithms. In such cases, the security of historical , but nonetheless highly confidential data may be in jeopardy. We present a scheme for efficient secure two-party communication with provable everlasting security. The security is guaranteed in face of any future technological advances, given the current state of of the art. Furthermore, the security of the messages is also guaranteed even if the secret encryption/decryption key is revealed in the future, The scheme is based on the bounded storage model and provides information-theoretic security in this model. The bounded storage model postulates an adversary who is computationally unbounded, and is only bounded in the amount of storage (not computation space) available to store the output of his computation. The bound on the storage can be arbitrarily large (e.g., 100 Tbytes), as long as it is fixed. Given this storage bound, our protocols guarantee that even a computationally all powerful adversary gains no information about a message (except with a probability that is exponentially small in the security parameter k). The bound on storage space need only hold at the time of the message transmission. Thereafter, no additional storage space or, computational power can help the adversary in deciphering the message. We present two protocols. The first protocol, which elaborates on the autoregressive (AR) protocol of Aumann and Rabin (see Advances in Cryptology-Crypto '99, p. 65-79, 1999), employs a short secret key whose size is independent of the length of the message, but uses many public random bits. The second protocol uses an optimal number of public random bits, but employs a longer secret key. Our proof of security utilizes a novel linear algebraic technique.
Abstract Everlasting security models the setting where hardness assumptions hold during the execution of a protocol but may get broken in the future. Due to the strength of this adversarial model, achieving any meaningful security guarantees for composable protocols is impossible without relying on hardware assumptions (Müller-Quade and Unruh, JoC’10). For this reason, a rich line of research has tried to leverage physical assumptions to construct well-known everlasting cryptographic primitives, such as commitment schemes. The only known everlastingly UC secure commitment scheme, due to Müller-Quade and Unruh (JoC’10), assumes honestly generated hardware tokens. The authors leave the possibility of constructing everlastingly UC secure commitments from malicious hardware tokens as an open problem. Goyal et al. (Crypto’10) constructs unconditionally UC-secure commitments and secure computation from malicious hardware tokens, with the caveat that the honest tokens must encapsulate other tokens. This extra restriction rules out interesting classes of hardware tokens, such as physically uncloneable functions (PUFs). In this work, we present the first construction of an everlastingly UC-secure commitment scheme in the fully malicious token modelwithout requiringhonest token encapsulation. Our scheme assumes the existence of PUFs and is secure in the common reference string model. We also show that our results are tight by giving an impossibility proof for everlasting UC-securecomputationfrom non-erasable tokens (such as PUFs), even with trusted setup.
Electronic voting (e-voting) has emerged as a transformative technology in the modern digital era. Many countries across the world are using e-voting systems in different types of elections, from political to non-political. One of the primary goals of e-voting is ensuring both verifiability and privacy simultaneously, which we refer to as security. Verifiability is a security feature that guarantees voters can confirm their vote is reflected in the final election result, while privacy guarantees that no one is able to link a vote to the voter who cast it. Verifiability needs to hold only for the duration of the election, whereas privacy needs to extend beyond the election period, even decades after the election. This property, known as everlasting privacy in the literature, ensures that even computationally unbounded adversaries cannot compromise voter privacy, securing elections against future advances in computing, including quantum computing. Researchers have proposed a wide variety of protocols to achieve this ambitious goal in secure e-voting, however, these protocols differ significantly, making the analysis and state-of-the-art complicated. In this thesis, we first address this fragmentation by systematically analyzing all existing e-voting protocols designed to ensure everlasting privacy. We map out the relationships and dependencies among these protocols, evaluate their security and efficiency under realistic assumptions, and identify unresolved challenges in the field. Our work provides a foundational reference for researchers aiming to design secure e-voting systems with everlasting privacy, paving the way for privacypreserving elections in the post-quantum era. Building on these insights, we propose a novel e-voting system that integrates the best practices from prior research while addressing their limitations. Leveraging the Hyperion scheme as a foundation, we develop an enhanced protocol that not only guarantees everlasting privacy but also introduces everlasting receipt-freeness and coercion mitigation. Unlike existing systems like Selene and Hyperion, which rely on computational assumptions for privacy, our protocol offers privacy even against adversaries with unlimited computational power. In secure electronic voting systems with everlasting privacy, the focus is on futureproofing privacy, while sometimes election verifiability relies on the computational soundness of zero-knowledge proofs (ZKP), which are vulnerable to quantum adversaries. Therefore, a key technical challenge is designing e-voting systems with efficient post-quantum cryptographic primitives to secure both privacy and verifiability against quantum attacks. In this thesis, we advance the state of post-quantum ZKPs by focusing on the ZKPs proposed by Jain et al., which are based on the conservative Learning Parity with Noise (LPN) assumption. We optimize the efficiency of these ZKPs, achieve formal security verification using EasyCrypt, and uncover flaws in existing implementations, demonstrating their vulnerability to malicious provers. Additionally, we construct the first code-based ZKP of shuffle, enabling a verifiable and privacy-preserving e-voting protocol with mixing-based tallying. Our e-voting system ensures both verifiability and vote privacy through the computational difficulty of decoding random linear codes, marking it as the first verifiable code-based e-voting system.
We revisit the impossibility of a variety of cryptographic tasks including privacy and differential privacy with imperfect randomness. For traditional notions of privacy, such as security of encryption, commitment or secret sharing schemes, dramatic impossibility results are known [MP90,DOPS04] for several concrete sources R, including a (seemingly) very “nice and friendly” Santha-Vazirani (SV) source. Moreover, Bosley and Dodis [BD07] gave strong evidence that many traditional privacy tasks (e.g., encryption) inherently require an “extractable” source of randomness. The common interpretation of these negative results is that privacy is impossible even with “very structured” imperfect sources. Somewhat surprisingly, Dodis et al. [DLMV12] put a slight dent in this belief, by showing that non-trivial differential privacy is possible with the SV sources. This suggested a qualitative gap between traditional and differential privacy, and left open the question if differential privacy is possible with more realistic (i.e., less structured) sources than the SV sources. Motivated by solving this question, we introduce a new, modular framework for showing strong impossibility results for (either traditional or differential) privacy under a general imperfect source R. In particular, we introduce natural and easy-to-understand concepts of expressiveness and separability of a given imperfect source R, and show the following results: – Low levels of expressiveness generically imply strong impossibility results for both traditional and differential privacy. – Separability implies expressiveness; NON-separability is equivalent to “weak bit extraction”. – While the separability of some concrete (e.g., SV) sources R was implicitly known, we show new separability results for several important sources, including general “block sources”. As direct corollaries of these general results, we get the following corollaries: – Existing, but quantitatively improved, impossibility results for traditional privacy, but under a wider variety of sources R. – First impossibility results for differential privacy. Although, unsurprisingly, these results (barely) miss the highly structured SV sources, they come back extremely quickly once the source becomes slightly more realistic (e.g., a realistic “block source”). – Any imperfect source allowing (either traditional or differential) privacy admits a certain type of deterministic bit extraction. (This result is incomparable to the result of [BD07].) Overall, we believe our results provide an intuitive, modular and unified picture elucidating the (im)possibility of privacy with general imperfect sources.
Computational security in cryptography has a risk that computational assumptions underlying the security are broken in the future. One solution is to construct information-theoretically-secure protocols, but many cryptographic primitives are known to be impossible (or unlikely) to have information-theoretical security even in the quantum world. A nice compromise (intrinsic to quantum) is certified everlasting security, which roughly means the following. A receiver with possession of quantum encrypted data can issue a certificate that shows that the receiver has deleted the encrypted data. If the certificate is valid, the security is guaranteed even if the receiver becomes computationally unbounded. Although several cryptographic primitives, such as commitments and zero-knowledge, have been made certified everlasting secure, there are many other important primitives that are not known to be certified everlasting secure. In this paper, we introduce certified everlasting FE. In this primitive, the receiver with the ciphertext of a message m and the functional decryption key of a function f can obtain f(m) and nothing else. The security holds even if the adversary becomes computationally unbounded after issuing a valid certificate. We, first, construct certified everlasting FE for P/poly circuits where only a single key query is allowed for the adversary. We, then, extend it to q-bounded one for NC1 circuits where q-bounded means that q key queries are allowed for the adversary with an a priori bounded polynomial q. For the construction of certified everlasting FE, we introduce and construct certified everlasting versions of secret-key encryption, public-key encryption, receiver non-committing encryption, and a garbling scheme, which are of independent interest.