Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
AGATE: Augmented Global Attested Trusted Execution in the Universal Composability framework
Get PDFA Trusted Execution Environment (TEE) is a security technology,
implemented by CPU manufacturers, which guarantees integrity and confidentiality
on a restricted execution environment to any remote verifier through attestation. TEEs are deployed
on various consumer and commercial hardware platforms, and have been widely adopted as a component in the design of cryptographic protocols both theoretical and practical.
Within the provable security community, the use of TEEs as a setup assumption
has converged to a standard ideal definition in the Universal Composability
setting (, defined by Pass et al., Eurocrypt \u2717). However, it is unclear
whether any real TEE design can actually realise such a level of security, or whether the diverse capabilities of today\u27s TEE implementations will in fact converge to a single standard. Therefore, it is necessary for cryptographers and protocol designers to specify what assumptions are necessary for the TEE they are using to support the correctness and security of their protocol.
To this end, this paper provides a more careful treatment of trusted execution
than the existing literature, focusing on the capabilities of enclaves and
adversaries. Our goal is to provide meaningful patterns for comparing different
classes of TEEs, particularly how a weaker TEE functionality can implement a
stronger one given an appropriate mechanism to bridge the two. We introduce a
new, modular definition of TEEs that captures a broad range of pre-existing
functionalities defined in the literature while maintaining their high level of
abstraction. While our goal is not directly to model implementations of specific
commercial TEE providers, our modular definition provides a way to capture more
meaningful and realistic hardware capabilities. We propose to
characterise TEE capabilities along the following terms:
- the set of trusted features available to the enclave;
- the set of possible attacks on an enclave;
- the content of attestation signatures.
We then define various possible ideal modular functionality
instantiations that capture existing variants in the literature. Finally, we
conclude the paper by constructing a protocol template to realise
stronger setups from weaker ones, and provide an example of removing an attack
A Better Kyber Butterfly for FPGAs
Get PDFKyber was selected by NIST as a Post-Quantum
Cryptography Key Encapsulation Mechanism standard. This
means that the industry now needs to transition and adopt
these new standards. One of the most demanding operations in
Kyber is the modular arithmetic, making it a suitable target for
optimization. This work offers a novel modular reduction design
with the lowest area on Xilinx FPGA platforms. This novel design,
through K-reduction and LUT-based reduction, utilizes 49 LUTs
and 1 DSP as opposed to Xing and Li’s 2021 CHES design
requiring 90 LUTs and 1 DSP for one modular multiplication.
Our design is the smallest modular multiplier reported as of
today
Raccoon: A Masking-Friendly Signature Proven in the Probing Model
Get PDFThis paper presents Raccoon, a lattice-based signature scheme submitted to the NIST 2022 call for additional post-quantum signatures. Raccoon has the specificity of always being masked. Concretely, all sensitive intermediate values are shared into parts. The main design rationale of Raccoon is to be easy to mask at high orders, and this dictated most of its design choices, such as the introduction of new algorithmic techniques for sampling small errors. As a result, Raccoon achieves a masking overhead that compares favorably with the overheads observed when masking standard lattice signatures. In addition, we formally prove the security of Raccoon in the -probing model: an attacker is able to probe shares during each execution of the main algorithms (key generation, signing, verification). While for most cryptographic schemes, the black-box -probing security can be studied in isolation, in Raccoon this analysis is performed jointly. To that end, a bridge must be made between the black-box game-based EUF-CMA proof and the usual simulation proofs of the ISW model (CRYPTO 2003). We formalize an end-to-end masking proof by deploying the probing EUF-CMA introduced by Barthe et al.(Eurocrypt 2018) and exhibiting the simulators of the non-interference properties (Barthe et al. CCS 2016). The proof is divided into three novel parts:
- a simulation proof in the ISW model that allows to propagate the dependency to a restricted number of inputs and random coins,
- a game-based proof showing that the security of Raccoon with probes can be reduced to an instance of Raccoon with smaller parameters,
- a parameter study to ensure that the smaller instance is secure, using a robust generalization of the Rényi divergence.
While we apply our techniques to Raccoon, we expect that the algorithmic and proof techniques we introduce will be helpful for the design and analysis of future masking-friendly schemes
An Improved Algorithm for Code Equivalence
Get PDFWe study the linear code equivalence problem (LEP) for linear -codes over finite fields . Recently, Chou, Persichetti and Santini gave an elegant algorithm that solves LEP over large finite fields (with ) in time , where denotes the binary entropy function. However, for small finite fields, their algorithm can be significantly slower. In particular, for fields of constant size , its runtime increases by an exponential factor in .
We present an improved version of their algorithm, which achieves the desired runtime of for all finite fields of size . For a wide range of parameters, this improves over the runtime of all previously known algorithms by an exponential factor
Rondo: Scalable and Reconfiguration-Friendly Randomness Beacon
Get PDFWe present Rondo, a scalable and reconfiguration-friendly distributed randomness beacon (DRB) protocol in the partially synchronous model. Rondo is the first DRB protocol that is built from batched asynchronous verifiable secret sharing (bAVSS) and meanwhile avoids the high message cost, where is the number of nodes. Our key contribution lies in the introduction of a new variant of bAVSS called batched asynchronous verifiable secret sharing with partial output (bAVSS-PO). bAVSS-PO is a weaker primitive than bAVSS but allows us to build a secure and more scalable DRB protocol. We propose a bAVSS-PO protocol Breeze. Breeze achieves the optimal messages for the sharing stage and allows Rondo to offer better scalability than prior DRB protocols.
Additionally, to support the reconfiguration, we introduce Rondo-BFT, a dynamic and partially synchronous Byzantine fault-tolerant protocol inspired by Dyno (S\&P 2022). Unlike Dyno, Rondo-BFT provides a communication pattern that generates randomness beacon output periodically, making it well-suited for DRB applications.
We implement our protocols and evaluate the performance on Amazon EC2 using up to 91 instances. Our evaluation results show that Rondo achieves higher throughput than existing works and meanwhile offers better scalability, where the performance does not degrade as significantly as grows
Improved Alternating-Moduli PRFs and Post-Quantum Signatures
Get PDFWe revisit the alternating-moduli paradigm for constructing symmetric-key primitives with a focus on constructing efficient protocols to evaluate them using secure multi-party computation (MPC). The alternating-moduli paradigm of Boneh, Ishai, Passelègue, Sahai, and Wu (TCC 2018) enables the construction of various symmetric-key primitives with the common characteristic that the inputs are multiplied by two linear maps over different moduli.
The first contribution focuses on efficient two-party evaluation of alternating-moduli pseudorandom functions (PRFs), effectively building an oblivious PRF. We present a generalized alternating-moduli PRF construction along with methods to lower the communication and computation. We then provide several variants of our protocols with different computation and communication tradeoffs for evaluating the PRF. Most of our protocols are in the hybrid model while one is based on specialized garbling. Our most efficient protocol effectively is about faster and requires less communication.
Our next contribution is the efficient evaluation of the one-way function (OWF) proposed by Dinur, Goldfeder, Halevi, Ishai, Kelkar, Sharma, and Zaverucha (CRYPTO 21) where , and is multiplication mod . This surprisingly simple OWF can be evaluated within MPC by secret sharing over , locally computing , performing a modulus switching protocol to shares, followed by locally computing the output shares .
We design a bespoke MPC-in-the-Head (MPCitH) signature scheme that evaluates the aforementioned OWF, achieving state-of-the-art performance. The resulting signature has a size ranging from to KB, achieving between reduction compared to the prior work. To the best of our knowledge, this is only larger than the smallest signature based on symmetric-key primitives, including the latest NIST post-quantum cryptography competition submissions. We also show that our core techniques can be extended to build very small post-quantum ring signatures for rings of small to medium size, which are competitive with state-of-the-art lattice-based schemes. Our techniques are in fact more generally applicable to set membership in MPCitH
Dynamic Decentralized Functional Encryptions from Pairings in the Standard Model
Get PDFDynamic Decentralized Functional Encryption (DDFE), introduced by Chotard et al. (CRYPTO\u2720), represents a robust generalization of (Multi-Client) Functional Encryption. It allows users to dynamically join and contribute private inputs to individually controlled joint functions without requiring a trusted authority.
Recently, Shi and Vanjani (PKC\u2723) proposed the first Multi-Client Functional Encryption scheme for function-hiding inner products (FH-IP) without relying on random oracles. Unfortunately, their construction still requires a trusted key authority, leaving open the question of whether a full-fledged FH-IP-DDFE can exist in the standard model.
In this work, we answer this question affirmatively by introducing Updatable Pseudorandom Zero Sharing, a novel concept that provides both the critical functionality and security properties needed to construct secure DDFE schemes in the standard model.
Our second contribution is a novel proof strategy, which preserves adaptive security when transforming any functional encryption scheme for FH-IP into FH-IP-DDFE. Together, these two techniques enable a modular construction of FH-IP-DDFE that is secure against adaptive message and key queries in the standard model.
Additionally, our pseudorandom zero-sharing scheme is highly versatile, enabling the first DDFE for attribute-weighted sums in the standard model, complementing the recent ROM-based construction by Agrawal et al. (CRYPTO\u2723)
Reduce and Prange: Revisiting Prange\u27s ISD for Solving LPN/RSD over Large Fields
Get PDFThe Learning Parity with Noise (LPN) problem and its regular noise variant are fundamental to many cryptographic primitives. While recent proposals extend these problems to larger fields to enhance cryptographic applications, the security implications of LPN over large fields remain understudied. This gap has facilitated more effective attacks, potentially compromising the security of LPN-based primitives over large fields.
In this paper, we present an improved algorithm for solving LPN over large fields. Our method enhances the classical Gaussian elimination attack, specifically Prange\u27s information set decoding algorithm, by iteratively applying Gaussian elimination to reduced-size matrices rather than the full-size matrix.
We call this the ``Reduce and Prange (RP) algorithm and demonstrate its effectiveness for both LPN and its variant with regular noise over large finite fields (e.g., ). Building on the RP algorithm, we develop a modified algebraic algorithm for LPN with regular noise over with , extending the work of Briaud and Øygard (Eurocrypt\u2723). Furthermore, we demonstrate that Scalable Multiparty Garbling (CCS\u2723) fails to meet their claimed security levels.
For LPN over large fields (e.g., 128-bit field size), our algorithm reduces bit-security by up to 9 bits relative to Liu et al. (Eurocrypt\u2724). In the case of LPN with regular noise, our RP algorithm surpasses both Liu et al. and Briaud and Øygard (Eurocrypt\u2723) under specific parameter settings, achieving up to 16-bit reduction in security
LatticeFold: A Lattice-based Folding Scheme and its Applications to Succinct Proof Systems
Get PDFFolding is a recent technique for building efficient recursive SNARKs. Several elegant folding protocols have been proposed, such as Nova, Supernova, Hypernova, Protostar, and others. However, all of them rely on an additively homomorphic commitment scheme based on discrete log, and are therefore not post-quantum secure and require a large (256-bit) field. In this work we present LatticeFold, the first lattice-based folding protocol based on the Module SIS problem. This folding protocol naturally leads to an efficient recursive lattice-based SNARK and an efficient PCD scheme. LatticeFold supports folding low-degree relations, such as R1CS, as well as high-degree relations, such as CCS. The key challenge is to construct a secure folding protocol that works with the Ajtai commitment scheme. The difficulty is ensuring that extracted witnesses are low norm through many rounds of folding. We present a novel technique using the sumcheck protocol to ensure that extracted witnesses are always low norm no matter how many rounds of folding are used. Since LatticeFold can operate over a small (64-bit) field, our evaluation of the final proof system suggests that it is as performant as Hypernova, while providing plausible post-quantum security. Moreover, LatticeFold operates over the same module structure used by fully homomorphic encryption (FHE) and lattice signatures schemes, and can therefore benefit from software optimizations and custom hardware designed to accelerate these lattice schemes
OCash: Fully Anonymous Payments between Blockchain Light Clients
Get PDFWe study blockchain-based provably anonymous payment systems between light clients. Such clients interact with the blockchain through full nodes, which can see what the light clients read and write. The goal of our work is to enable light clients to perform anonymous payments, while maintaining privacy even against the full nodes through which they interact with the blockchain. We formalize the problem in the UC model and present a provably secure solution. We show that a variation of tree ORAM gives obliviousness even when an adversary can follow how its own data elements move in the tree. We use this for anonymity via shuffling of payments on the blockchain, while at the same time allowing the light client to know a few positions among which to find its payment without knowing the current state of the blockchain. In comparison to existing works, we are the first ones that simultaneously provide strong anonymity guarantees, provable security, and anonymity with respect to full nodes. Along the way, we make several contributions that may be of independent interest. We define and construct anonymous-coin friendly encryption schemes and show how they can be used within anonymous payment systems. We define and construct efficient compressible randomness beacons, which produce unpredictable values in regular intervals and allow for storing all published values in a short digest