Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
Quasi-perfect (de)compression of elliptic curve points in the highly -adic scenario
Get PDFIn this short note, a new laconic, secure, and efficient (de)compression method is provided for points of any elliptic curve over any highly -adic finite field of large characteristic. Such fields are ubiquitous in modern elliptic curve cryptography, whereas they severely slow down the conventional -coordinate (de)compression technique. In comparison with the current state of the art in the given research direction, the new method requires neither complicated mathematical formulas nor conditions on the curve, nor reliable pseudo-random generators. Thereby, the present work is universal and much more implementation-friendly, which justifies its existence, despite the absence of interesting mathematics behind it
IPCrypt: Optimal, Practical Encryption of IP Addresses for Privacy and Measurement
Get PDFThis paper introduces efficient, practical methods for encrypting IPv4/IPv6 addresses while preserving utility in logs, telemetry, and third-party data exchange.
We focus on three practical goals: (i) format-compatible encryption that keeps outputs in the IPv6 address space and handles IPv4 inputs canonically; (ii) prefix-preserving encryption that retains network structure for analytics while hiding host identity; and (iii) non-deterministic encryption that resists correlation while remaining compact and invertible.
We give deterministic, prefix-preserving, and two non-deterministic variants, with security models and arguments under standard assumptions, plus explicit usage bounds and operating limits.
We also relate each variant to known efficiency lower bounds (ciphertext expansion and primitive calls) and state our claims within deployable parameter ranges
Diffie–Hellman Key Exchange from Commutativity to Group Laws
Get PDFIn Diffie–Hellman key exchange, the commutativity of power operations is instrumental in the agreement of keys. Viewing commutativity as a law in abelian groups, we propose Diffie–Hellman key exchange in the group action framework (Brassard–Yung, Crypto\u2790; Ji–Qiao–Song–Yun, TCC\u2719), for actions of non-abelian groups with laws. The security of this protocol is shown, following Fischlin, Günther, Schmidt, and Warinschi (IEEE S&P\u2716), based on a pseudorandom group action assumption. A concrete instantiation is proposed based on the monomial code equivalence problem
Dory: Streaming PCG with Small Memory
Get PDFPseudorandom correlation generators (PCGs) have been popular in generating a huge amount of correlated randomness, a critical resource in secure computation. However, existing PCGs are memory-consuming and not friendly to resource-constrained devices. Even for moderate devices, the need for large memory can also be a disadvantage in applications like zero-knowledge proofs or large-scale secure computation. In this paper, we propose a malicious streaming PCG (sPCG), which generates a bounded number of tuples of subfield vector oblivious linear evaluation (sVOLE) on-the-fly, each with sublinear memory and computation.
1. We propose an efficient protocol that replaces the relaxed distributed comparison function in the best pseudorandom correlation function (PCF) for sVOLE (CRYPTO\u2722), which has the same streaming features for any polynomial number of tuples. With this protocol, our sPCG is doubly efficient in memory and the computation per sVOLE. Moreover, we augment the black-box distributed setup to malicious security and yield 4x communication improvement. Our sPCG can be extended to a more efficient sVOLE PCF with the same improvements in memory and computation, and a 2x faster malicious non-black-box distributed setup.
2. We present a practical attack on the Learning Parity with Noise (LPN) assumption for expand-accumulate codes with regular noise, revealing that some previous parameters provide around 14~22 bits of security over binary noises, far below the target 128 bits. To address this, we introduce a low-Hamming-weight noise distribution to withstand the attack. We then derive some updated LPN parameters with the new noise distribution, restoring 128-bit security and reducing the noise-related computation and communication.
3. We provide an implementation of our sPCG for the special case of correlated oblivious transfer (COT). In addition to the improvements over the best PCF, our sPCG can have a comparable end-to-end performance to Ferret (CCS\u2720) and the PCG from expand-convolute codes (CRYPTO\u2723), two state-of-the-art PCGs, with the advantage of being able to produce 10 million COTs on-the-fly and reducing the memory from 337 MB and 624 MB to 20 MB, respectively
ORQ: Complex Analytics on Private Data with Strong Security Guarantees
Get PDFWe present ORQ, a system that enables collaborative analysis of large private datasets using cryptographically secure multi-party computation (MPC). ORQ protects data against semi-honest or malicious parties and can efficiently evaluate relational queries with multi-way joins and aggregations that have been considered notoriously expensive under MPC. To do so, ORQ eliminates the quadratic cost of secure joins by leveraging the fact that, in practice, the structure of many real queries allows us to join records and apply the aggregations “on the fly” while keeping the result size bounded. On the system side, ORQ contributes generic oblivious operators, a data-parallel vectorized query engine, a communication layer that amortizes MPC network costs, and a dataflow API for expressing relational analytics—all built from the ground up.
We evaluate ORQ in LAN and WAN deployments on a diverse set of workloads, including complex queries with multiple joins and custom aggregations. When compared to state-of-the-art solutions, ORQ significantly reduces MPC execution times and can process one order of magnitude larger datasets. For our most challenging workload, the full TPC-H benchmark, we report results entirely under MPC with Scale Factor 10—a scale that had previously been achieved only with information leakage or the use of trusted third parties
Forgetful Encryption
Get PDFWe put forward the concept of forgetful encryption . A forgetful public-key encryption scheme guarantees that (a limited amount of) information that is leaked through the encryption process does not reveal the whole message. This notion is related to, but different from leakage-resilient encryption (where leakage on the decryption key is considered) and big-key encryption (which is defined for secret-key encryption).
Forgetful encryption is useful, e.g., in settings in which a cloud server encrypts data stored for a client, using that client’s public key. In that setting, a limited form of leakage on the encryption process may occur accidentally, through security breaches, or through targeted attacks.
In this work, we define the notion of forgetful encryption using the simulation paradigm, and provide a number of instantiations from mild computational assumptions. In the random oracle model, we provide a generic instantiation from “lossy key encapsulation mechanisms”, an existing paradigm that allows for efficient instantiations in the group, RSA, and lattice settings. In the standard model, we provide a somewhat less efficient construction (that can also be instantiated under standard assumptions) from a mild variant of (sender-)deniable encryption
Rayls II: Fast, Private, and Compliant CBDCs
Get PDFIn this work, we introduce an upgrade to Rayls, a novel central bank digital currency (CBDC) design that provides privacy, high performance, and regulatory compliance. In the Rayls construction, commercial banks each run their own (private) ledger and are connected to an underlying decentralized programmable blockchain via a relayer.
We introduce an improved and more efficient protocol that allows for efficient anonymous transactions between banks, which is (still) called Enygma. Our design is \u27quantum-private\u27 as a quantum adversary is not able to infer any information (i.e., payer, payee, amounts) about the transactions that take place in the network. One of the main improvements of this work is that the design is now completely quantum-secure except for the current use of ZK-SNARKs. We note, however, that this is modular and can simply be updated as desired.
We achieve high performance in cross-bank settlement via the use of ZK-SNARKs and \u27double\u27 batching and an optimized ZK implementation, with a prover time three times faster than the initial implementation and a cheaper on-chain verifier. Our transactions consist of a set of commitments and a zero-knowledge proof. As a result, each transaction can pay more than 1 bank at once and, secondly, each of these individual commitments can contain aggregated transfers from multiple users. For example, bank A transfers $1M to a different bank B and that amount is actually a sum of multiple users making transfers to bank B. Commercial banks can then enforce regulatory rules locally within their ledgers. Our system is in production with one of the largest clearing houses in the world and is currently being explored in a CBDC pilot
Solving Concealed ILWE and its Application for Breaking Masked Dilithium
Get PDFLattice-based signatures like Dilithium (ML-DSA) prove knowledge of a secret key by using Integer LWE (ILWE) samples , for some known hash value of the message and unknown error . Rejection sampling guarantees zero-knowledge, which makes the ILWE problem, that asks to recover s from many z’s, unsolvable.
Side-channel attacks partially recover y, thereby obtaining more informative samples resulting in a—potentially tractable—ILWE problem. The standard method to solve the resulting problem is Ordinary Least Squares (OLS), which requires independence of from —an assumption that is violated by zero-knowledge samples.
We present efficient algorithms for a variant of the ILWE problem that was not addressed in prior work, which we coin Concealed ILWE (CILWE). In this variant, only a fraction of the ILWE samples is zero-knowledge. We call this fraction the concealment rate. This ILWE variant naturally occurs in side-channel attacks on lattice-based signatures. A case in point are profiling side-channel attacks on Dilithium implementations that classify whether . This gives rise to either zero-error ILWE samples with (in case of correct classification), or ordinary zero-knowledge ILWE samples (in case of misclassification).
As we show, OLS is not practical for CILWE instances, as it requires a prohibitively large amount of samples for even small (under 10%) concealment rates. A known integer linear programming-based approach can solve some CILWE instances, but suffers from two short-comings. First, it lacks provable efficiency guarantees, as ILP is NP-hard in the worst case. Second, it does not utilize small, independent error samples, that could occur in addition to zero-knowledge samples.
We introduce two statistical regression methods to cryptanalysis, Huber and Cauchy regression. They are both efficient and can handle instances with all three types of samples. At the same time, they are capable of handling high concealment rates, up to 90% in practical experiments. While Huber regression comes with theoretically appealing correctness guarantees, Cauchy regression performs best in practice.
We use this efficacy to execute a novel profiling attack against a masked Dilithium implementation. The resulting ILWE instances suffer from both concealment and small, independent errors. As such, neither OLS nor ILP can recover the secret key. Cauchy regression, however, allows us to recover the secret key in under two minutes for all NIST security levels
Transforming the POKE public key Protocol into a Key Encapsulation Mechanism
Get PDFThe inherent presence of large-scale quantum computers is
deemed to threaten the traditional public-key cryptographic systems.
As a result, NIST has necessitated the development of post-quantum
cryptography (PQC) algorithms. Isogeny-based schemes have compact
key sizes; however, there have been some fundamental vulnerabilities in
the smooth-degree isogeny systems. Therefore, the literature has concentrated its efforts on higher-dimensional isogenies of non-smooth degrees.
In this work, we present POKE-KEM, a key encapsulation mechanism
(KEM) derived from the POKE public-key encryption (PKE) scheme
via a Fujisaki-Okamoto (FO) transformation with its corresponding optimized security levels during transformation. Despite POKE’s efficiency
advantages, its current formulation provides only IND-CPA security, limiting practical deployment where adaptive chosen-ciphertext security is
essential. The resulting POKE-KEM construction achieves IND-CCA security under the computational hardness of the C-POKE problem in both
the random oracle model (ROM) and quantum random oracle model
(QROM). Our implementation demonstrates significant practical advantages across all NIST security levels (128, 192, and 256 bits), supporting
the practical viability of POKE-KEM for post-quantum cryptographic
deployments. We provide a comprehensive security analysis including
formal proofs of correctness, rigidity, and IND-CCA security. Our underlying construction leverages the difficulty of recovering isogenies with
unknown, non-smooth degrees, resistant to known quantum attack
Breaking Omertà: On Threshold Cryptography, Smart Collusion, and Whistleblowing
Get PDFCryptographic protocols often make honesty assumptions---e.g., fewer than out of participants are adversarial. In practice, these assumptions can be hard to ensure, particularly given monetary incentives for participants to collude and deviate from the protocol.
In this work, we explore combining techniques from cryptography and mechanism design to discourage collusion. We formalize protocols in which colluders submit a cryptographic proof to whistleblow against their co-conspirators, revealing the dishonest behavior publicly. We provide general results on the cryptographic feasibility, and show how whistleblowing fits a number of applications including secret sharing, randomness beacons, and anonymous credentials.
We also introduce smart collusion---a new model for players to collude. Analogous to blockchain smart contracts, smart collusion allows colluding parties to arbitrarily coordinate and impose penalties on defectors (e.g., those that blow the whistle). We show that unconditional security is impossible against smart colluders even when whistleblowing is anonymous and can identify all colluding players.
On the positive side, we construct a whistleblowing protocol that requires only a small deposit and can protect against smart collusion even with roughly times larger deposit