Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
Optimizing Attribute-based Encryption for Circuits using Compartmented Access Structures
No full textAttribute-based encryption (ABE) is an asymmetric encryption method that allows expressive access granting mechanisms, with high applicability in modern IT infrastructure, such as Cloud or IoT systems. (Ezhilarasi et al., 2021; Touati and Challal, 2016) One open problem regarding ABE is using Boolean circuits as access structures. While Boolean Formulae were supported since the first ABE scheme proposed, there is still no efficient construction that supports Boolean circuits. We propose a new ABE scheme for a new access structure type, situated between Boolean formulae and Boolean circuits in terms of expressiveness. This key point in our construction is the usage of CAS-nodes, a structure modeling compartmented groups access structures. We also show that our CAS-nodes can be used to improve the efficiency of existing ABE schemes for Boolean circuits. Our construction is secure in the Selective Set Model under the bilinear Decisional Diffie-Hellman Assumption
A New Linear Distinguisher for Four-Round AES
Get PDFIn SAC\u2714, Biham and Carmeli presented a novel attack on DES, involving a variation of Partitioning Cryptanalysis. This was further extended in ToSC\u2718 by Biham and Perle into the Conditional Linear Cryptanalysis in the context of Feistel ciphers. In this work, we formalize this cryptanalytic technique for Substitution-Permutation Networks and derive several properties. A conditional approximation is then used to approximate the function, which forms the only source of non-linearity in the AES. By extending the approximation to encompass the full AES round function, a linear distinguisher for 4-round AES using known-plaintexts is constructed; the existence of which is often understood to be impossible. We furthermore demonstrate how to recover 32 key bits directly from this distinguisher with no data or time overhead. In addition to suggesting a new approach to advancing the cryptanalysis of the AES, this result moreover demonstrates a caveat in the standard interpretation of the Wide Trail Strategy — the design framework underlying many SPN-based ciphers published in recent years
Perfect MPC over Layered Graphs
Get PDFThe classical BGW protocol (Ben-Or, Goldwasser and Wigderson, STOC 1988) shows that secure multiparty computation (MPC) among parties can be realized with perfect full security if parties are corrupted. This holds against malicious adversaries in the standard model for MPC, where a fixed set of parties is involved in the full execution of the protocol.
However, the picture is less clear in the mobile adversary setting of Ostrovsky and Yung (PODC 1991), where the adversary may periodically move by uncorrupting parties and corrupting a new set of parties. In this setting, it is unclear if full security can be achieved against an adversary that is maximally mobile, i.e., moves after every round. The question is further motivated by
the You Only Speak Once (YOSO) setting of Gentry et al. (Crypto 2021), where not only the adversary is mobile but also each round is executed by a disjoint set of parties. Previous positive results in this model do not achieve perfect security, and either assume probabilistic corruption and a nonstandard communication model, or only realize the weaker goal of security-with-abort. The question of matching the BGW result in these settings remained open.
In this work, we tackle the above two challenges simultaneously. We consider a layered MPC model, a simplified variant of the fluid MPC model of Choudhuri et al. (Crypto 2021). Layered MPC is an instance of standard MPC where the interaction pattern is defined by a layered graph of width , allowing each party to send secret messages and broadcast messages only to parties in the next layer. We require perfect security against a malicious adversary who may corrupt at most parties in each layer.
Our main result is a perfect, fully secure layered MPC protocol with an optimal corruption threshold of , thus extending the BGW feasibility result to the layered setting. This implies perfectly secure MPC protocols against a maximally mobile adversary
Deuring for the People: Supersingular Elliptic Curves with Prescribed Endomorphism Ring in General Characteristic
Get PDFConstructing a supersingular elliptic curve whose endomorphism ring is isomorphic to a given quaternion maximal order (one direction of the Deuring correspondence) is known to be polynomial-time assuming the generalized Riemann hypothesis [KLPT14; Wes21], but notoriously daunting in practice when not working over carefully selected base fields.
In this work, we speed up the computation of the Deuring correspondence in general characteristic, i.e., without assuming any special form of the characteristic. Our algorithm follows the same overall strategy as earlier works, but we add simple (yet effective) optimizations to multiple subroutines to significantly improve the practical performance of the method.
To demonstrate the impact of our improvements, we show that our implementation achieves highly practical running times even for examples of cryptographic size. One implication of these findings is that cryptographic security reductions based on KLPT-derived algorithms (such as [EHLMP18; Wes22]) have become tighter, and therefore more meaningful in practice.
Another is the pure bliss of fast(er) computer algebra: We provide a Sage implementation which works for general primes and includes many necessary tools for computational number theorists\u27 and cryptographers\u27 needs when working with endomorphism rings of supersingular elliptic curves. This includes the KLPT algorithm, translation of ideals to isogenies, and finding supersingular elliptic curves with known endomorphism ring for general primes.
Finally, the Deuring correspondence has recently received increased interest because of its role in the SQISign signature scheme [DeF+20]. We provide a short and self-contained summary of the state-of-the-art algorithms without going into any of the cryptographic intricacies of SQISign
An Auditable Confidentiality Protocol for Blockchain Transactions
Get PDFBlockchain exposes all users’ transaction data to the public, including account balances, asset holdings, trading history, etc. Such data exposure leads to potential security and personal privacy risks that restrict blockchain from broader adoption. Although some existing projects focus on single-chain confidential payment, no existing cross-chain system supports private transactions yet, which is incompatible with privacy regulations such as GDPR. Also, current confidential payment systems require users to pay high extra fees. However, a private and anonymous protocol encrypting all transaction data raises concerns about malicious and illegal activities since the protocol is difficult to audit. We need to balance privacy and auditability in blockchain.
We propose an auditable and affordable protocol for cross-chain and single-chain transactions. This protocol leverages zero-knowledge proofs to encrypt transactions and perform validation without disclosing sensitive users\u27 data. To meet regulations, each auditor from an auditing committee will have an encrypted secret share of the transaction data. Auditors may view the private transaction data only if a majority of the committee agrees to decrypt the data. We employ a ZK-rollup scheme by processing multiple transactions in batches, which reduces private transaction costs to 90\% lower compared with solutions without ZK-rollup. We implemented the proposed scheme using Zokrates and Solidity and evaluated the protocol on the Ethereum test network, and the total one-to-one private transactions cost only 5 seconds. We also proved the security of the protocol utilizing the standard real/ideal world paradigm
A Hybrid of Lattice-reduction and Meet-LWE via Near-Collision on Babai\u27s Plane
Get PDFA cryptographic primitive based on the Learning With Errors (LWE) problem with variants is a promising candidate for the efficient quantum-resistant public key cryptosystem. As the parameters for such cryptosystems are chosen by the concrete attack cost for the corresponding LWE problem, improving the LWE solving algorithm has a significant importance.
In this paper, we present a new hybrid attack on the LWE problem. This new attack combines the primal lattice attack and an improved variant of the MitM attack, Meet-LWE, suggested by May (Crypto\u2721). This resolves the major open problem posed in the same paper.
To this end, we develop several technical tools for hybrid attacks; a new property of Babai\u27s nearest plane algorithm with respect to projection, an approximate variant of Meet-LWE, and a locality-sensitive hashing-based near-collision finding algorithm.
We also present a comprehensive analysis of the proposed attack, which involves the complicated arguments of both lattice and representation techniques.
We finally estimate the concrete cost of our attack for sparse LWE keys. For some currently deployed parameter sets in fully homomorphic encryption libraries, our attack achieves up to bits improvement than the previous primal hybrid attacks
TRIFORS: LINKable Trilinear Forms Ring Signature
Get PDFWe present TRIFORS (TRIlinear FOrms Ring Signature), a logarithmic post-quantum (linkable) ring signature based on a novel assumption regarding the equivalence of alternating trilinear forms. The basis of this work is the construction by Beullens, Katsumata and Pintore from Asiacrypt 2020 to obtain a linkable ring signature from a cryptographic group action. The group action on trilinear forms used here is the same employed in the signature presented by Tang et al. at Eurocrypt 2022. We first define a sigma protocol that, given a set of public keys, the ring, allows us to prove the knowledge of a secret key corresponding to a public one in the ring. Furthermore, some optimisations are used to reduce the size of the signature: among others, we use a novel application of the combinatorial number system to the space of the challenges. Using the Fiat-Shamir transform, and taking into account the attack of Beullens from Crypto 2023, we obtain a (linkable) ring signature of competitive length with the state-of-the-art among post-quantum proposals for security level 128
Privacy-Preserving Epidemiological Modeling on Mobile Graphs
Get PDFThe latest pandemic COVID-19 brought governments worldwide to use various containment measures to control its spread, such as contact tracing, social distance regulations, and curfews. Epidemiological simulations are commonly used to assess the impact of those policies before they are implemented. Unfortunately, the scarcity of relevant empirical data, specifically detailed social contact graphs, hampered their predictive accuracy. As this data is inherently privacy-critical, a method is urgently needed to perform powerful epidemiological simulations on real-world contact graphs without disclosing any sensitive information.
In this work, we present RIPPLE, a privacy-preserving epidemiological modeling framework enabling standard models for infectious disease on a population’s real contact graph while keeping all contact information locally on the participants’ devices. As a building block of independent interest, we present PIR-SUM, a novel extension to private information retrieval for secure download of element sums from a database. Our protocols are supported by a proof-of-concept implementation, demonstrating a 2-week simulation over half a million participants completed in 7 minutes, with each participant communicating less than 50 KB
Exploiting Decryption Failures in Mersenne Number Cryptosystems
Get PDFMersenne number schemes are a new strain of potentially quantum-safe cryptosystems that use sparse integer arithmetic modulo a Mersenne prime to encrypt messages. Two Mersenne number based schemes were submitted to the NIST post-quantum standardization process: Ramstake and Mersenne-756839. Typically, these schemes admit a low but non-zero probability that ciphertexts fail to decrypt correctly.
In this work we show that the information leaked from failing ciphertexts can be used to gain information about the secret key. We present an attack exploiting this information to break the IND-CCA security of Ramstake. First, we introduce an estimator for the bits of the secret key using decryption failures. Then, our estimates can be used to apply the Slice-and-Dice attack due to Beunardeau et al. at significantly reduced complexity to recover the full secret.
We implemented our attack on a simplified version of the code submitted to the NIST competition. Our attack is able to extract a good estimate of the secrets using decryption failures, corresponding to ~failing ciphertexts in the original scheme. Subsequently the exact secrets can be extracted in about quantum computational steps
How Does Satoshi Set His Clock? Full Analysis of Nakamoto Consensus
Get PDFNakamoto consensus, arguably the most exciting development in decentralized computation in the last few years, is in a sense a recasting of the traditional state machine replication problem in an unauthenticated setting, where furthermore parties come and go without warning. The protocol relies on a cryptographic primitive known as proof of work (PoW) which is used to throttle message passing. Importantly, the PoW difficulty level is appropriately adjusted throughout the course of the protocol execution relying on the blockchain’s timekeeping ability.
While the original formulation was only accompanied by rudimentary analysis, significant and steady progress has been made in abstracting the protocol’s properties and providing a formal analysis under various restrictions and protocol simplifications. Still, a full analysis of the protocol that includes its PoW target value recalculation and, notably, its timestamp adjustment mechanism, which equip it to operate in its intended setting of bounded communication delays, imperfect clocks and dynamic participation, has remained open. (Specifically, the protocol allows incoming block timestamps in the near future, as determined by a protocol parameter, and rejects blocks that have a timestamp in the past of the median time of a specific number of blocks on-chain [namely, 11].)
The gap is that Nakamoto’s protocol fundamentally depends on the blockchain itself to be a consistent timekeeper that should advance roughly on par with real time. In order to tackle this question we introduce a new analytical tool we call `hot-hand executions,\u27 which capture the regular occurrence of high concentration of honestly generated blocks, and correspondingly put forth and prove a new blockchain property called `concentrated chain quality,\u27 which may be of independent interest. Utilizing these tools and techniques we demonstrate that Nakamoto’s protocol achieves, under suitable conditions, consistency, liveness as well as (consistent) timekeeping