International Association
for Cryptologic Research

As cryptographic protocols transition to post-quantum security, most adopt hybrid solutions combining pre-quantum and post-quantum assumptions. However, this shift often introduces trade-offs in terms of efficiency, compactness, and in some cases, even security. One such example is deniability, which enables users, such as journalists or activists, to deny authorship of potentially incriminating messages. While deniability was once mainly of theoretical interest, protocols like X3DH, used in Signal and WhatsApp, provide it to billions of users. Recent work (Collins et al., PETS'25) has further bridged the gap between theory and real-world applicability. In the post-quantum setting, however, protocols like PQXDH, as well as others such as Apple’s iMessage with PQ3, do not support deniability. This work investigates how to preserve deniability in the post-quantum setting by leveraging unconditional (statistical) guarantees instead of computational assumptions - distinguishing deniability from confidentiality and authenticity.

As a case study, we present a hybrid authenticated key encapsulation mechanism (AKEM) that provides statistical deniability, while maintaining authenticity and confidentiality through a combination of pre-quantum and post-quantum assumptions. To this end, we introduce two combiners at different levels of abstraction. First, at the highest level, we propose a black-box construction that combines two AKEMs, showing that deniability is preserved only when both constituent schemes are deniable. Second, we present Shadowfax, a non-black-box combiner that integrates a pre-quantum NIKE, a post-quantum KEM, and a post-quantum ring signature. We demonstrate that Shadowfax ensures deniability in both dishonest and honest receiver settings. When instantiated, we rely on statistical security for the former, and on a pre- or post-quantum assumption in the latter. Finally, we provide an optimised, yet portable, implementation of a specific instantiation of Shadowfax yielding ciphertexts of 1781 bytes and public keys of 1449 bytes. Our implementation achieves competitive performance: encapsulation takes 1.9 million cycles and decapsulation takes 800000 cycles on an Apple M1 Pro.

Quasi-cyclic moderate-density parity check (QC-MDPC) code-based encryption schemes under iterative decoders offer highly-competitive performance in the quantum-resistant space of cryptography, but the decoding-failure rate (DFR) of these algorithms are not well-understood. The DFR decreases extremely rapidly as the ratio of code-length to error-bits increases, then decreases much more slowly in regimes known as the waterfall and error-floor, respectively.

This work establishes three, successively more detailed probabilistic models of the DFR for iterative decoders for QC-MPDC codes: the simplified model, the refined model for perfect keys, and the refined model for all keys. The models are built upon a Markov model introduced by Sendrier and Vasseur that closely predicts decoding behavior in the waterfall region but does not capture the error floor behavior. The simplified model introduces a modification which captures the dominant contributor to error floor behavior which is convergence to near codewords introduced by Vasseur in his PhD thesis. The refined models give more accurate predictions taking into account certain structural features of specific keys.

Our models are based on the step-by-step decoder, which is highly simplified and experimentally displays worse decoding performance than parallel decoders used in practice. Despite the use of the simplified decoder, we obtain an accurate prediction of the DFR in the error floor and demonstrate that the error floor behavior is dominated by convergence to a near codeword during a failed decoding instance. Furthermore, we have run this model for a simplified version of the QC-MDPC code-based cryptosystem BIKE to better ascertain whether the DFR is low enough to achieve IND-CCA2 security. Our model for a modified version of BIKE 1 gives a DFR which is below $2^{-129.5}$, using a block length $r = 13477$ instead of the BIKE 1 parameter $r = 12323$.

We propose the first $\textit{distributed}$ version of a simple, efficient, and provably quantum-safe pseudorandom function (PRF). The distributed PRF (DPRF) supports arbitrary threshold access structures based on the hardness of the well-studied Learning with Rounding (LWR) problem. Our construction (abbreviated as $\mathsf{PQDPRF}$) practically outperforms not only existing constructions of DPRF based on lattice-based assumptions, but also outperforms (in terms of evaluation time) existing constructions of: (i) classically secure DPRFs based on discrete-log hard groups, and (ii) quantum-safe DPRFs based on any generic quantum-safe PRF (e.g. AES). The efficiency of $\mathsf{PQDPRF}$ stems from the extreme simplicity of its construction, consisting of a simple inner product computation over $\mathbb{Z}_q$, followed by a rounding to a smaller modulus $p < q$. The key technical novelty of our proposal lies in our proof technique, where we prove the correctness and post-quantum security of $\mathsf{PQDPRF}$ (against semi-honest corruptions of any less than threshold number of parties) for a polynomial $q/p$ (equivalently, "modulus to modulus")-ratio.

Our proposed DPRF construction immediately enables efficient yet quantum-safe instantiations of several practical applications, including key distribution centers, distributed coin tossing, long-term encryption of information, etc. We showcase a particular application of $\mathsf{PQDPRF}$ in realizing an efficient yet quantum-safe version of distributed symmetric-key encryption ($\mathsf{DiSE}$ -- originally proposed by Agrawal et al. in CCS 2018), which we call $\mathsf{PQ-DiSE}$. For semi-honest adversarial corruptions across a wide variety of corruption thresholds, $\mathsf{PQ-DiSE}$ substantially outperforms existing instantiations of $\mathsf{DiSE}$ based on discrete-log hard groups and generic PRFs (e.g. AES). We illustrate the practical efficiency of our $\mathsf{PQDPRF}$ via prototype implementation of $\mathsf{PQ-DiSE}$.

We propose a quantum function secret sharing scheme in which the communication is exclusively classical. In this primitive, a classical dealer distributes a secret quantum circuit $C$ by providing shares to $p$ quantum parties. The parties on an input state $\ket{\psi}$ and a projection $\Pi$, compute values $y_i$ that they then classically communicate back to the dealer, who can then compute $\lVert\Pi C\ket{\psi}\rVert^2$ using only classical resources. Moreover, the shares do not leak much information about the secret circuit $C$. Our protocol for quantum secret sharing uses the Cayley path, a tool that has been extensively used to support quantum primacy claims. More concretely, the shares of $C$ correspond to randomized version of $C$ which are delegated to the quantum parties, and the reconstruction can be done by extrapolation. Our scheme has two limitations, which we prove to be inherent to our techniques: First, our scheme is only secure against single adversaries, and we show that if two parties collude, then they can break its security. Second, the evaluation done by the parties requires exponential time in the number of gates.

We give a sieving algorithm for finding pairs of primes with small multiplicative orders modulo each other. This problem is a necessary condition for obtaining constructions of $2$-cycles of pairing-friendly curves, which have found use in cryptographic applications. Our database of examples suggests that, with the exception of a well-known infinite family of such primes, instances become increasingly rare as the size of the primes increase. This leads to some interesting open questions for which we hope our database prompts further investigation.

We are looking for a permanent researcher to join the Cryptographic Protocols team within the Cryptography Research Center (CRC) at TII. The main task of the team is to conduct applied academic research and assist in product development, spanning topics such as: TLS, QUIC, Tor, Key Exchange, secure channels, cryptographic primitives and their implementation, privacy enhancing technologies, MLS and Secure Messaging, WebRTC, and formal methods. The nature of our work spans both theory and practice, covering aspects such as provable security, security models, efficient designs, implementation aspects, and attacks.

Applicants should have completed (or be close to completing) their PhD in a related area and preferably also have postdoctoral research experience. Preference will be given to applicants with publications in top-tier venues such as CRYPTO, EUROCRYPT, ASIACRYPT, ACM CCS, IEEE S&P, and USENIX.

Required Skills:

• Fluency in English (verbal and written) and an ability to communicate research effectively.
• Good problem-solving skills and an ability to conduct research independently.
• Good interpersonal and collaborative skills.
• Solid knowledge in cryptography with a focus on one or more of the following: Key Exchange, Secure Messaging, Postquantum cryptography, Provable Security, Cryptography Engineering, and Cryptographic Protocols more generally.

Valuable Skills:

• Strong background in Mathematics and/or Computer Science.
• Programming, Software Engineering, experience in implementing cryptographic primitives and attacks on real-world cryptosystems, reverse engineering of closed-source protocols.
• Experience in analyzing protocol standards and specifications.
• Experience in Formal Methods and related tools.

What we offer:

• Vibrant working environment, flexible working conditions, and travel funding.
• Industry-competitive tax-free salary.
• Family-wide health insurance and children’s education allowance.

Closing date for applications:

Contact: Jean Paul Degabriele

More information: https://www.tii.ae/cryptography

We are inviting talented and highly motivated applicants to submit applications for a PhD studentship at School of Cryptology, University of Chinese Academy of Sciences, Beijing, China. The positions are fully funded and have a 3 to 5-year duration, with a negotiable start date.

We explore topics including, but not limited to:

Design and cryptanalysis of symmetric-key cryptographic primitives

Post-quantum cryptography

Tools for cryptanalysis

Applicant skills/background:

A strong background in cryptography, Computer Science, Engineering, Mathematics, or a related discipline .

Excellent communication and interpersonal skills, with the ability to thrive in a collaborative research environment.

Critical thinking and analytical skills, with fluency in technical English.

Proficiency in programming.

Closing date for applications:

Contact: Siwei Sun (siweisun.isaac at gmail.com)

We are looking for a bright and motivated PhD student to work in the topics of information security and cryptography.

The student is expected to work on topics that include security and privacy issues in authentication. More precisely, the student will be working on investigating efficient and privacy-preserving authentication that provides: i) provable security guarantees, and ii) rigorous privacy guarantees.

Key Responsibilities:

• Perform exciting and challenging research in the domain of information security and cryptography.
• Support and assist in teaching computer security and cryptography courses.

Profile:

• The PhD student is expected to have a MSc degree or equivalent, and strong background in cryptography, network security and mathematics.
• Experience in one or more domains such as cryptography, design of protocols, secure multi-party computation and differential privacy is beneficial.
• Excellent programming skills.
• Excellent written and verbal communication skills in English

The Chair of Cyber Security, https://cybersecurity.unisg.ch/, is a part of the Institute of Computer Science (ICS) at the University of St.Gallen. The chair was established in autumn semester 2020 and is led by Prof. Dr. Katerina Mitrokotsa. Our research interests are centered around information security and applied cryptography, with the larger goal of safeguarding communications and providing strong privacy guarantees. We are currently active in multiple areas including the design of provably secure cryptographic protocols and cryptographic primitives that can be employed for reliable authentication, outsourcing computations in cloud-assisted settings, network security problems as well as secure and privacy-preserving machine learning. As a doctoral student you will be a part of the Doctoral School of Computer Science (DCS), https://dcs.unisg.ch.

Please apply by 15th February 2025 through the job link. Applications will be evaluated continuously.

Closing date for applications:

Contact:
Eriane Breu (Administrative matters)
Prof. Katerina Mitrokotsa (Research related questions)

More information: https://jobs.unisg.ch/offene-stellen/funded-phd-student-in-applied-cryptography-privacy-preserving-authentication-m-f-d/36538ff2-210a-4dbd-bd48-575e4b7447cf

JAM Gray Paper: https://www.graypaper.com/

About Us

Parity is one of the world's most experienced core blockchain infrastructure companies, building the open-source technologies that will lay the foundation for the new decentralised internet.

Parity was founded by Dr. Gavin Wood, co-founder and former CTO of Ethereum, the primary engineer behind the Ethereum Virtual Machine (EVM), inventor of the Solidity programming language, and primary author of the Ethereum Yellowpaper.

We believe in a decentralised web that respects the freedom and data of individuals and empowers developers to create better services. Our vision is to create a world based on truthful, rather than trustful, interactions.

About the Team

The Incubation team operates at the forefront of blockchain innovation. Under the direct leadership of our founder, Dr. Gavin Wood, the team is responsible for identifying and prototyping new ideas for Polkadot. Currently, the team's primary focus is on advancing PolkaJAM - the next-generation decentralised virtual machine - a protocol combining the best elements of Polkadot and Ethereum.

About the Position

- Evaluate and refine technical designs proposed by the team, benchmarking them against blockchain scaling solutions.

- Conduct performance modelling and analysis.

- Document technical insights and formalise research findings.

- Collaborate with engineering teams, translating research insights into actionable technical strategies.

About You

- PhD in Computer Science, Cryptography, Distributed Systems, etc.

- Strong technical knowledge of Ethereum, Layer 2 scaling solutions, cryptography, or low-level systems programming.

- Ability to analyse and evaluate designs proposed by the team

- Experience developing performance models and defining measurement strategies to validate theoretical assumptions.

Closing date for applications:

Contact: Joe Mullaney

More information: https://jobs.ashbyhq.com/parity/c04f3045-bdad-45bf-81e2-e0c5fd7cbde0

The University of Manchester invites applications for a Professor in Quantum Technology, with a particular focus on Quantum Cryptography.

The successful candidate will lead cutting-edge research in quantum cryptography and related areas. The role includes securing external funding, publishing in top-tier venues, supervising PhD students, and contributing to teaching in the CS department.

Candidates should have a PhD in Computer Science, Mathematics, Physics or a related field, an outstanding research record in quantum cryptography or related areas, experience in securing research funding, and a strong teaching background.

The position is permanent and based in Manchester, a leading hub for quantum research. Salary is competitive and commensurate with experience. For more details and to apply, visit:
https://www.jobs.manchester.ac.uk/Job/JobDetail?JobId=31138

Application deadline: March 31, 2025.

Closing date for applications:

Contact: For informal enquiries please contact Bernardo Magri (bernardo dot magri at manchester.ac.uk)

More information: https://www.jobs.manchester.ac.uk/Job/JobDetail?JobId=31138

In this paper, we study practical constructions of asynchronous distributed key reconfiguration ($\mathsf{ADKR}$), which enables an asynchronous fault-tolerant system with an existing threshold cryptosystem to efficiently generate a new threshold cryptosystem for a reconfigured set of participants. While existing asynchronous distributed threshold key generation ($\mathsf{ADKG}$) protocols theoretically solve $\mathsf{ADKR}$, they fail to deliver satisfactory scalability due to cubic communication overhead, even with simplifications to the reconfiguration setting.

We introduce a more efficient \textit{share-dispersal-then-agree-and-recast} paradigm for constructing $\mathsf{ADKR}$ with preserving adaptive security. The method replaces expensive $O(n)$ asynchronous verifiable secret sharing protocols in classic $\mathsf{ADKG}$ with $O(n)$ cheaper dispersals of publicly-verifiable sharing transcripts; after consensus confirms a set of finished dispersals, it selects a small $\kappa$-subset of finished dispersals for verification, reducing the total overhead to $O(\kappa n^2)$ from $O(n^3)$, where $\kappa$ is a small constant (typically $\sim$30 or less). To further optimize concrete efficiency, we propose an interactive protocol with linear communication to generate publicly verifiable secret sharing (PVSS) transcripts, avoiding computationally expensive non-interactive PVSS. Additionally, we introduce a distributed PVSS verification mechanism, minimizing redundant computations across different parties and reducing the dominating PVSS verification cost by about one-third.

Our design also enables diverse applications: (i) given a quadratic-communication asynchronous coin-flipping protocol, it implies the first quadratic-communication $\mathsf{ADKG}$; and (ii) it can be extended to realize the first quadratic-communication asynchronous dynamic proactive secret sharing (ADPSS) protocol with adaptive security. Experimental evaluations on a global network of 256 AWS servers show up to 40\% lower latency compared to state-of-the-art $\mathsf{ADKG}$ protocols (with simplifications to the reconfiguration setting), highlighting the practicality of our $\mathsf{ADKR}$ in large-scale asynchronous systems.

OPC UA is a standardized Industrial Control System (ICS) protocol, deployed in critical infrastructures, that aims to ensure security. The forthcoming version 1.05 includes major changes in the underlying cryptographic design, including a Diffie-Hellmann based key exchange, as opposed to the previous RSA based version. Version 1.05 is supposed to offer stronger security, including Perfect Forward Secrecy (PFS).

We perform a formal security analysis of the security protocols specified in OPC UA v1.05 and v1.04, for the RSA-based and the new DH-based mode, using the state-of-the-art symbolic protocol verifier ProVerif. Compared to previous studies, our model is much more comprehensive, including the new protocol version, combination of the different sub-protocols for establishing secure channels, sessions and their management, covering a large range of possible configurations. This results in one of the largest models ever studied in ProVerif raising many challenges related to its verification mainly due to the complexity of the state machine. We discuss how we mitigated this complexity to obtain meaningful analysis results. Our analysis uncovered several new vulnerabilities, that have been reported to and acknowledged by the OPC Foundation. We designed and proposed provably secure fixes, most of which are included in the upcoming version of the standard.

We develop an efficient algorithm to detect whether a superspecial genus 2 Jacobian is optimally $(N, N)$-split for each integer $N \leq 11$. Incorporating this algorithm into the best-known attack against the superspecial isogeny problem in dimension 2 (due to Costello and Smith) gives rise to significant cryptanalytic improvements. Our implementation shows that when the underlying prime $p$ is 100 bits, the attack is sped up by a factor of $25$; when the underlying prime is 200 bits, the attack is sped up by a factor of $42$; and, when the underlying prime is 1000 bits, the attack is sped up by a factor of $160$. Furthermore, we describe a more general algorithm to find endomorphisms of superspecial genus 2 Jacobians.

This paper presents a novel single-trace side-channel attack on FALCON---a lattice-based post-quantum digital signature protocol recently approved for standardization by NIST. We target the discrete Gaussian sampling operation within the FALCON key generation scheme and use a single power measurement trace to succeed. Notably, negating the 'shift right 63-bit' operation (for 64-bit values) leaks critical information about the '-1' vs. '0' assignments to intermediate coefficients. These leaks enable full recovery of the generated secret keys. The proposed attack is implemented on an ARM Cortex-M4 microcontroller running both reference and optimized software implementation from FALCON's NIST Round 3 package. Statistical analysis with 500k tests reveals a per coefficient success rate of 99.9999999478% and a full key recovery success rate of 99.99994654% for FALCON-512. This work highlights the vulnerability of current software solutions to single-trace attacks and underscores the urgent need to develop single-trace resilient software for embedded systems.

Overclocking is a a supported functionality of Nvidia GPUs, and is a common performance enhancement practice. However, overclocking poses a danger for cryptographic applications. As the temperature in the overclocked GPU increases, spurious computation faults occur. Coupled with well known fault attacks against RSA implementations, one can expect such faults to allow compromising RSA private keys during decryption or signing.

We first validate this hypothesis: We evaluate two commercial-grade GPU-based implementations of RSA within openSSL (called RNS and MP), under a wide range of overclocking levels and temperatures, and demonstrate that both implementations are vulnerable.

However, and more importantly, we show for the first time that even if the GPU is benignly overclocked to a seemingly ``safe'' rate, a successful attack can still be mounted, over the network, by simply sending requests at an aggressive rate to increase the temperature. Hence, setting any level of overclocking on the GPU is risky.

Moreover, we observe a huge difference in the implementations' vulnerability: the rate of RSA breaks for RNS is 4 orders of magnitude higher than that of MP. We attribute this difference to the implementations' memory usage patterns: RNS makes heavy use of the GPU's global memory, which is accessed via both the Unified (L1) cache and the L2 cache; MP primarily uses ``shared'' on-chip memory, which is local to each GPU Streaming MultiProcessor (SM) and is uncached, utilizing the memory banks used for the L1 cache. We believe that the computation faults are caused by reads from the global memory, which under a combination of overclocking, high temperature and high memory contention, occasionally return stale values.

Accumulation schemes are powerful primitives that enable distributed and incremental verifiable computation with less overhead than recursive SNARKs. However, existing schemes with constant-size accumulation verifiers, suffer from linear-sized accumulators and deciders, leading to linear-sized proofs that are unsuitable in distributed settings. Motivated by the need for bandwidth efficient accountable voting protocols, (I) We introduce KZH, a novel polynomial commitment scheme, and (II) KZH-fold, the first sublinear accumulation scheme where the verifier only does $3$ group scalar multiplications and $O(n^{1/2})$ accumulator size and decider time. Our scheme generalizes to achieve accumulator and decider complexity of $k \cdot n^{1/k}$ with verifier complexity $k$. Using the BCLMS compiler, (III) we build an IVC/PCD scheme with sublinear proof and decider. (IV) Next, we propose a new approach to non-uniform IVC, where the cost of proving a step is proportional only to the size of the step instruction circuit, and unlike previous approaches, the witness size is not linear in the number of instructions. (V) Leveraging these advancements, we demonstrate the power of KZH-fold by implementing an accountable voting scheme using a novel signature aggregation protocol supporting millions of participants, significantly reducing communication overhead and verifier time compared to BLS-based aggregation. We implemented and benchmarked our protocols and KZH-fold achieves a 2000x reduction in communication and a 50x improvement in decider time over Nova when proving 2000 Poseidon hashes, at the cost of 3x the prover time.

We translate the expand-and-extract framework by Fitzi, Liu-Zhang, and Loss (PODC 21) to the asynchronous setting. While they use it to obtain a synchronous BA with $2^{-\lambda}$ error probability in $\lambda+1$ rounds, we make it work in asynchrony in $\lambda+3$ rounds. At the heart of their solution is a generalization of crusader agreement and graded agreement to any number of grades called proxcensus. They achieve graded consensus with $2^r+1$ grades in $r$ rounds by reducing proxcensus with $2s-1$ grades to proxcensus with $s$ grades in one round. The expand-and-extract paradigm uses proxcensus to expand binary inputs to $2^\lambda+1$ grades in $\lambda$ rounds before extracting a binary output by partitioning the grades using a $\lambda$ bit common coin. However, the proxcensus protocol by Fitzi et al. does not translate to the asynchronous setting without lowering the corruption threshold or using more rounds in each recursive step.

This is resolved by attaching justifiers to all messages: forcing the adversary to choose between being ignored by the honest parties, or sending messages with certain validity properties. Using these we define validated proxcensus and show that it can be instantiated in asynchrony with the same recursive structure and round complexity as synchronous proxcensus. In asynchrony the extraction phase incurs a security loss of one bit which is recovered by expanding to twice as many grades using an extra round of communication. This results in a $\lambda+2$ round VABA and a $\lambda+3$ round BA, both with $2^{-\lambda}$ error probability and communication complexity matching Fitzi et al.

We present hax, a verification toolchain for Rust targeted at security-critical software such as cryptographic libraries, protocol imple- mentations, authentication and authorization mechanisms, and parsing and sanitization code. The key idea behind hax is the pragmatic observation that different verification tools are better at handling different kinds of verification goals. Consequently, hax supports multiple proof backends, including domain-specific security analysis tools like ProVerif and SSProve, as well as general proof assistants like Coq and F*. In this paper, we present the hax toolchain and show how we use it to translate Rust code to the input languages of different provers. We describe how we systematically test our translated models and our models of the Rust system libraries to gain confidence in their correctness. Finally, we briefly overview various ongoing verification projects that rely on hax.

Timed cryptography has initiated a paradigm shift in the design of cryptographic protocols: Using timed cryptography we can realize tasks fairly, which is provably out of range of standard cryptographic concepts. To a certain degree, the success of timed cryptography is rooted in the existence of efficient protocols based on the sequential squaring assumption.

In this work, we consider space analogues of timed cryptographic primitives, which we refer to as space-hard primitives. Roughly speaking, these notions require honest protocol parties to invest a certain amount of space and provide security against space constrained adversaries. While inefficient generic constructions of timed-primitives from strong assumptions such as indistinguishability obfuscation can be adapted to the space-hard setting, we currently lack concrete and versatile algebraically structured assumptions for space-hard cryptography. In this work, we initiate the study of space-hard primitives from concrete algebraic assumptions relating to the problem of root-finding of sparse polynomials. Our motivation to study this problem is a candidate construction of VDFs by Boneh et al. (CRYPTO 2018) which are based on the hardness of inverting permutation polynomials. Somewhat anticlimactically, our first contribution is a full break of this candidate. However, we then revise this hardness assumption by dropping the permutation requirement and considering arbitrary sparse high degree polynomials. We argue that this type of assumption is much better suited for space-hardness rather than timed cryptography. We then proceed to construct both space-lock puzzles and verifiable space-hard functions from this assumption.

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).