Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
Identity-Based Matchmaking Encryption with Enhanced Privacy Against Chosen-Ciphertext Attacks
Get PDFIdentity-based matchmaking encryption (IB-ME) proposed by Ateniese et al. [CRYPTO 2019; Journal of Cryptology 2021] enables users to communicate privately, anonymously, and authentically. Following the seminal work of Ateniese et al., considerable research has been conducted on the security and construction of IB-ME schemes, but no scheme with enhanced privacy against chosen-ciphertext attacks is known. In this paper, we propose two IB-ME schemes that simultaneously achieve enhanced privacy against chosen-ciphertext attacks. The first scheme is built on the bilinear Diffie–Hellman assumption in the random oracle model. Inspired by the scheme of Ateniese et al., our construction attains stronger security guarantees while providing more compact decryption keys and ciphertexts than the scheme of Ateniese et al. The second scheme is a generic construction built upon anonymous identity-based encryption, digital signatures, NIZK systems, and reusable extractors. This scheme is obtained by generalizing the specific scheme of Francati et al. [INDOCRYPT 2021] and constitutes the first IB-ME scheme achieving the stronger security notions in the standard model. As an additional contribution, we classify existing authenticity notions for IB-ME into four categories—no message attacks (NMA) and chosen message attacks (CMA), each considered against both insiders and outsiders. This taxonomy enables a precise comparison among existing IB-ME schemes
Populating the Zoo of Rugged Pseudorandom Permutations
Get PDFA Rugged Pseudorandom Permutation (RPRP) is a variable-input-length tweakable cipher satisfying a security notion that is intermediate between tweakable PRP and tweakable SPRP. It was introduced at CRYPTO 2022 by Degabriele and Karadžić, who additionally showed how to generically convert such a primitive into nonce-based and nonce-hiding AEAD schemes satisfying either misuse-resistance or release-of-unverified-plaintext security as well as Nonce-Set AEAD which has applications in protocols like QUIC and DTLS. Their work shows that RPRPs are powerful and versatile cryptographic primitives. However, the RPRP security notion itself can seem rather contrived, and the motivation behind it is not immediately clear. Moreover, they only provided a single RPRP construction, called UIV, which puts into question the generality of their modular approach and whether other instantiations are even possible. In this work, we address this question positively by presenting new RPRP constructions, thereby validating their modular approach and providing further justification in support of the RPRP security definition. Furthermore, we present a more refined view of their results by showing that strictly weaker RPRP variants, which we introduce, suffice for many of their transformations. From a theoretical perspective, our results show that the well-known three-round Feistel structure achieves stronger security as a permutation than a mere pseudorandom permutation---as was established in the seminal result by Luby and Rackoff. We conclude on a more practical note by showing how to extend the left domain of one RPRP construction for applications that require larger values in order to meet the desired level of security
Flexway O-Sort: Enclave-Friendly and Optimal Oblivious Sorting
Get PDFOblivious algorithms are being deployed at large scale in real world to enable privacy-preserving applications such as Signal\u27s private contact discovery. Oblivious sorting is a fundamental building block in the design of oblivious algorithms for numerous computation tasks. Unfortunately, there is still a theory-practice gap for oblivious sort. The commonly implemented bitonic sorting algorithm is not asymptotically optimal, whereas known asymptotically optimal algorithms suffer from large constants.
In this paper, we construct a new oblivious sorting algorithm called flexway o-sort, which is asymptotically optimal, concretely efficient, and suitable for implementation in hardware enclaves such as Intel SGX. For moderately large inputs of GB, our flexway o-sort algorithm outperforms known oblivious sorting algorithms by to when the data fits within the hardware enclave, and by to when the data does not fit within the hardware enclave. We also implemented various applications of oblivious sorting, including histogram, database join, and initialization of an ORAM data structure. For these applications and data sets from 8GB to 32GB, we achieve speedup over bitonic sort when the data fits within the enclave, and speedup when the data does not fit within the enclave
Improved Polynomial Secret-Sharing Schemes
Get PDFDespite active research on secret-sharing schemes for arbitrary access structures for more than 35 years, we do not understand their share size the best known upper bound for an arbitrary n-party access structure is while the best known lower bound is . Consistent with our knowledge, the share size can be anywhere between these bounds. To better understand this question, one can study specific families of secret-sharing schemes. For example, linear secret-sharing schemes, in which the sharing and reconstruction are computed by linear mappings, have been studied in many papers, e.g., it is known that they require shares of size at least . Secret-sharing schemes in which the sharing and/or reconstruction are computed by low-degree polynomials have been recently studied by Paskin-Cherniavsky and Radune [ITC 2020] and by Beimel, Othman, and Peter [CRYPTO 2021]. It was shown that secret-sharing schemes with sharing and reconstruction computed by polynomials of degree 2 are more efficient than linear schemes (i.e., schemes in which the sharing and reconstruction are computed by polynomials of degree one).
Prior to our work, it was not known if using polynomials of higher degree can reduce the share size. We show that this is indeed the case, i.e., we construct secret-sharing schemes with reconstruction by degree- polynomials, where as the reconstruction degree increases, the share size for arbitrary access structures decreases. As a step in our construction, we construct conditional disclosure of secrets (CDS) protocols. For example, we construct 2-server CDS protocols for functions with reconstruction computed by degree-d polynomials with message size . Combining our results with a lower bound of Beimel et al. [CRYPTO 2021], we show that increasing the degree of the reconstruction function in CDS protocols provably reduces the message size. To construct our schemes, we define sparse matching vectors, show constructions of such vectors, and design CDS protocols and secret-sharing schemes with degree- reconstruction from sparse matching vectors
Incompressiblity and Next-Block Pseudoentropy
Get PDFA distribution is k-incompressible, Yao [FOCS ’82], if no efficient compression scheme compresses it to less than k bits. While being a natural measure, its relation to other computational analogs of entropy such as pseudoentropy, Hastad, Impagliazzo, Levin, and Luby [SICOMP 99], and to other cryptographic hardness assumptions, was unclear.
We advance towards a better understating of this notion, showing that a k-incompressible distribution has (k−2) bits of next-block pseudoentropy, a refinement of pseudoentropy introduced by Haitner, Reingold, and Vadhan [SICOMP ’13]. We deduce that a samplable distribution X that is (H(X) + 2)-incompressible, implies the existence of one-way functions
The Internet Computer for Geeks
Get PDFSmart contracts are a new form of software that will revolutionize how software is written, IT systems are maintained, and applications and whole businesses are built. Smart contracts are composable and autonomous pieces of software that run on decentralized blockchains, which makes them tamperproof and unstoppable.
In this paper, we describe the Internet Computer (IC), which is a radical new design of blockchain that unleashes the full potential of smart contracts, overcoming the limitations of smart contracts on traditional blockchains with respect to speed, storage costs, and computational capacity. This allows smart contracts for the first time to implement fully decentralized applications that are hosted end to end on blockchain.
The IC consists of a set of cryptographic protocols that connects independently operated nodes into a collection of blockchains. These blockchains host and execute ``canisters\u27\u27, the IC’s form of smart contracts. Canisters can store data, perform very general computations on that data, and provide a complete technology stack, serving web pages directly to end users. Computational and storage costs are covered by a ``reverse-gas model\u27\u27, where canister developers pre-pay costs in cycles that are obtained from ICP, the native token of the IC. ICP tokens are also used for governance: the IC is governed by a decentralized autonomous organization, or DAO, which, among other things, determines changes to the topology of the network and upgrades to the protocol
SPHINCS-: A Compact Stateless Hash-Based Signature Scheme
No full textHash-based signatures offer a conservative alternative to post-quantum signatures with arguably better-understood security than other post-quantum candidates. As a core building block of hash-based signatures, the efficiency of one-time signature (OTS) largely dominates that of hash-based signatures. The WOTS signature scheme (Africacrypt 2013) is the current state-of-the-art OTS adopted by the signature schemes standardized by NIST---XMSS, LMS, and SPHINCS.
A natural question is whether there is (and how much) room left for improving one-time signatures (and thus standard hash-based signatures). In this paper, we show that the WOTS one-time signature, when adopting the constant-sum encoding scheme (Bos and Chaum, Crypto 1992), is size-optimal not only under Winternitz\u27s OTS framework, but also among all tree-based OTS designs. Moreover, we point out a flaw in the DAG-based OTS design previously shown to be size-optimal at Asiacrypt 1996, which makes the constant-sum WOTS the most size-efficient OTS to our knowledge. Finally, we evaluate the performance of constant-sum WOTS integrated into the SPHINCS (CCS 2019) and XMSS (PQC 2011) signature schemes, which exhibit certain degrees of improvement in both sign time and signature size
Searchable Encryption for Conjunctive Queries with Extended Forward and Backward Privacy
Get PDFRecent developments in the field of Dynamic Searchable Symmetric Encryption (DSSE) with forward and backward privacy have attracted much attention from both research and industrial communities. However, most DSSE schemes with forward and backward privacy schemes only support single keyword queries, which impedes its prevalence in practice. Although some forward and backward private DSSE schemes with expressive queries (e.g., conjunctive queries) have been introduced, their backward privacy either essentially corresponds to single keyword queries or forward privacy is not comprehensive. In addition, the deletion of many DSSE schemes is achieved by addition paired with a deletion mark (i.e., lazy deletion). To address these problems, we present two novel DSSE schemes with conjunctive queries (termed \texttt{SDSSE-CQ} and \texttt{SDSSE-CQ-S}), which achieve both forward and backward privacy. To analyze their security, we present two new levels of backward privacy (named Type-O and Type-O, more and more secure), which give a more comprehensive understanding of the leakages of conjunctive queries in the \texttt{OXT} framework. Eventually, the security analysis and experimental evaluations show that the proposed schemes achieve better security with reasonable computation and communication increase
On Quantum Query Complexities of Collision-Finding in Non-Uniform Random Functions
Get PDFCollision resistance and collision finding are now extensively exploited in Cryptography, especially in the case of quantum computing. For any function with uniformly distributed over , Zhandry has shown that the number of queries is both necessary and sufficient for finding a collision in with constant probability. However, there is still a gap between the upper and the lower bounds of query complexity in general non-uniform distributions.
In this paper, we investigate the quantum query complexity of collision-finding problem with respect to general non-uniform distributions. Inspired by previous work, we pose the concept of collision domain and a new parameter that heavily depends on the underlying non-uniform distribution. We then present a quantum algorithm that uses quantum queries to find a collision for any non-uniform random function. By making a transformation of a problem in non-uniform setting into a problem in uniform setting, we are also able to show that quantum queries are necessary in collision-finding in any non-uniform random function.
The upper bound and the lower bound in this work indicates that the proposed algorithm is nearly optimal with query complexity in general non-uniform case
An Addendum to the ZUC-256 Stream Cipher
Get PDFZUC-256 is a stream cipher, together with AES-256 and SNOW-V, proposed as the core primitive in future set of 3GPP confidentiality and integrity algorithms for the upcoming 5G applications which offer the 256-bit security. \\
While the original initialization scheme of ZUC-256 can work with a 256-bit key and an IV of length up to 184 bits, we describe a new initialization scheme of ZUC-256 that supports an IV of the exact 128 bits in this paper. Compared to the original initialization scheme, this new key/IV setup algorithm avoids the division of the whole key/IV byte and provides a simple and natural-looking initialization scheme for ZUC-256