Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
Posterior Security: Anonymity and Message Hiding of Standard Signatures
Get PDFWe introduce posterior security of digital signatures, the additional security features after the original signature is generated. It is motivated by the scenario that some people store their secret keys in secure hardware and can only obtain a standard signature through a standardized interface. In this paper, we consider two different posterior security features: anonymity and message hiding.
We first introduce incognito signature, a new mechanism to anonymize a standard signature. Different from other ring or group signatures, the signer generates a standard (non-anonymous) signature first. The signature is then anonymized by a converter before sending to the verifier, by hiding the signer public key with a set of decoy public keys. We then introduce concealed signature which hides the message in a commitment. The standard signature is converted such that it can be verified with the commitment. The models of posterior anonymity and posterior message hiding capture the separation of the signer and the converter. Anonymity or message hiding is provided by the converter after the creation of a standard signature by the signer.
We give generic constructions of incognito signature and concealed signature. It can be applied to standard signatures like Schnorr. It gives the first practical anonymized ECDSA signature, and the signature size is logarithmic to the number of decoy public keys . The existing ring signature scheme with ECDSA keys is at least 152 times longer than our scheme for .
The incognito signature and concealed signature can be composed to provide posterior anonymity and message hiding. It is useful in applications like two-tier central bank digital currency, where users want to hide their addresses (public keys) and transaction amounts (messages) when the payment is settled in the interbank layer
DNDK: Combining Nonce and Key Derivation for Fast and Scalable AEAD
Get PDFAuthenticated encryption with associated data (AEAD) schemes are responsible for securing increasingly critical digital infrastructure. Unfortunately, current widely deployed schemes suffer from various limitations that make them difficult to use securely in practice. Popular schemes like AES-GCM limit the amount of data that can be encrypted with a single key, preventing secure scaling to modern workloads. At the same time, practitioners may not be able to move away from the use of AES-GCM due to mature and widely deployed implementations, legacy constraints, and compliance.
In this paper, we provide approaches to improve the secure scaling of AEAD schemes via what we call derived-nonce, derived-key (DNDK) transforms. At a high level, such transforms use a root key to derive a nonce and key for use with an underlying scheme. The challenge is doing so in a way that introduces as little overhead as possible, while relying on a small number of assumptions on the used primitives. We provide some general results about secure scaling transforms and a concrete design for AES-GCM that is called DNDK-GCM. It requires as little as three additional AES calls to enable use of the same key to encrypt up to bytes of data, even when using random nonces. We also provide a detailed performance analysis. DNDK-GCM is now a draft IETF standard, and is already deployed at cloud scale by companies including Meta
Homomorphic Encryption with Authority
Get PDFFully homomorphic encryption enables computations over encrypted data, which allows privacy-preserving services to be held between a server and a client. However, real-world applications demand practical considerations, especially concerning public safety and legal investigations. Existing FHE schemes focus solely on privacy, neglecting the societal risks posed by criminal activities utilizing privacy-preserving services. This paper introduces Homomorphic Encryption with Authority (HEwA), a novel framework that balances data privacy with public safety by incorporating an authority party. The proposed HEwA system operates in two phases: a normal phase, where client data privacy is protected, and an investigative phase, where the authority referring to a legally authorized entity such as government agencies exerts the right to recover suspicious client’s data. We formalize the security model for HEwA, ensuring that client privacy is protected during the normal phase while enabling authorities to recover encrypted data in the investigative phase. As a concrete example, we design an efficient HEwA system solely based on the CKKS homomorphic encryption scheme, which supports approximate computations over real-number data, making it highly suitable for fruitful applications in AI such as secure genomic analysis. We further provide rigorous security proofs. This new approach addresses the tension between privacy and public safety in cloud services, paving the way for responsible use of homomorphic encryption in practice
Revocable Encryption, Programs, and More: The Case of Multi-Copy Security
Get PDFFundamental principles of quantum mechanics have inspired many new research directions, particularly in quantum cryptography. One such principle is quantum no-cloning which has led to the emerging field of revocable cryptography. Roughly speaking, in a revocable cryptographic primitive, a cryptographic object (such as a ciphertext or program) is represented as a quantum state in such a way that surrendering it effectively translates into losing the capability to use this cryptographic object. All of the revocable cryptographic systems studied so far have a major drawback: the recipient only receives one copy of the quantum state. Worse yet, the schemes become completely insecure if the recipient receives many identical copies of the same quantum state---a property that is clearly much more desirable in practice.
While multi-copy security has been extensively studied for a number of other quantum cryptographic primitives, it has so far received only little treatment in context of unclonable primitives. Our work, for the first time, shows the feasibility of revocable primitives, such as revocable encryption and revocable programs, which satisfy multi-copy security in oracle models. This suggest that the stronger notion of multi-copy security is within reach in unclonable cryptography more generally, and therefore could lead to a new research
direction in the field
Polynomial Time Cryptanalytic Extraction of Deep Neural Networks in the Hard-Label Setting
Get PDFDeep neural networks (DNNs) are valuable assets, yet their public accessibility raises security concerns about parameter extraction by malicious actors. Recent work by Carlini et al. (Crypto’20) and Canales- Martínez et al. (Eurocrypt’24) has drawn parallels between this issue and block cipher key extraction via chosen plaintext attacks. Leveraging differential cryptanalysis, they demonstrated that all the weights and biases of black-box ReLU-based DNNs could be inferred using a polynomial number of queries and computational time. However, their attacks relied on the availability of the exact numeric value of output logits, which allowed the calculation of their derivatives. To overcome this limitation, Chen et al. (Asiacrypt’24) tackled the more realistic hard-label scenario, where only the final classification label (e.g., dog or car ) is accessible to the attacker. They proposed an extraction method requiring a polynomial number of queries but an exponential execution time. In addition, their approach was applicable only to a restricted set of architectures, could deal only with binary classifiers, and was demonstrated only on tiny neural networks with up to four neurons split among up to two hidden layers.
This paper introduces new techniques that, for the first time, achieve cryptanalytic extraction of DNN parameters in the most challenging hard-label setting, using both a polynomial number of queries and polynomial time. We validate our approach by extracting nearly one million parameters from a DNN trained on the CIFAR-10 dataset, comprising 832 neurons in four hidden layers. Our results reveal the surprising fact that all the weights of a ReLU-based DNN can be efficiently determined by analyzing only the geometric shape of its decision boundaries
The Supersingular Isogeny Path and Endomorphism Ring Problems: Unconditional Reductions
Get PDFIn this paper we study several computational problems related to current post-quantum cryptosystems based on isogenies between supersingular elliptic curves. In particular we prove that the supersingular isogeny path and endomorphism ring problems are unconditionally equivalent under polynomial time reductions. We show that access to a factoring oracle is sufficient to solve the Quaternion path problem of KLPT and prove that these problems are equivalent, where previous results either assumed heuristics or the generalised Riemann Hypothesis (GRH). Consequently, given Shor’s quantum algorithm for factorisation, our results yield unconditional quantum polynomial reductions between the isogeny path and EndRing problems. Recently these reductions have become foundational for the security of isogeny-based cryptograph
A New World in the Depths of Microcrypt: Separating OWSGs and Quantum Money from QEFID
Get PDFWhile in classical cryptography, one-way functions (OWFs) are widely regarded as the “minimal assumption,” the situation in quantum cryptography is less clear. Recent works have put forward two concurrent candidates for the minimal assumption in quantum cryptography: One-way state generators (OWSGs), postulating the existence of a hard search problem with an efficient verification algorithm, and EFI pairs, postulating the existence of a hard distinguishing problem. Two recent papers [Khurana and Tomer STOC’24; Batra and Jain FOCS’24] showed that OWSGs imply EFI pairs, but the reverse direction remained open. In this work, we give strong evidence that the opposite direction does not hold: We show that there is a quantum unitary oracle relative to which EFI pairs exist, but OWSGs do not. In fact, we show a slightly stronger statement that holds also for EFI pairs that output classical bits (QEFID).
As a consequence, we separate, via our oracle, QEFID, and one-way puzzles from OWSGs and several other Microcrypt primitives, including efficiently verifiable one-way puzzles and unclonable state generators. In particular, this solves a problem left open in [Chung, Goldin, and Gray Crypto’24].
Using similar techniques, we also establish a fully black-box separation (which is slightly weaker than an oracle separation) between private-key quantum money schemes and QEFID pairs.
One conceptual implication of our work is that the existence of an efficient verification algorithm may lead to qualitatively stronger primitives in quantum cryptography
Dynamic zk-SNARKs (with applications to sparse zk-SNARKs and IVC)
Get PDFIn this work, we introduce dynamic zk-SNARKs. A dynamic zk-SNARK extends a standard zk-SNARK with an additional update algorithm. This algorithm takes as input a valid source statement–witness pair together with a verifying proof , and a valid target statement–witness pair . It outputs a verifying proof for in sublinear time (when and have small Hamming distance), potentially with the help of a data structure. To the best of our knowledge, no commonly used zk-SNARKs are dynamic: even a single update to currently requires recomputing the proof from scratch, which takes at least linear time. After formally defining dynamic zk-SNARKs, we present two constructions: one with update time and proof size (Dynaverse), and another with update time and proof size (Dynalog). Both Dynaverse and Dynalog rest on Dynamo, a new zk-SNARK for permutation relations that we introduce. Crucially, Dynamo is sparse, meaning its prover complexity depends only on the number of non-zero entries in the input vector. Our constructions can also be made universal in the random oracle model. We highlight two central applications of dynamic zk-SNARKs. First, we show that they naturally give rise to sparse zk-SNARKs—SNARKs whose prover complexity can be sublinear when the witness vector contains many zeros. In addition, by slightly modifying Dynaverse (rather than using it as a black box), we construct Aero, which to the best of our knowledge is the first sparse zk-SNARK with prover complexity, where is the Hamming weight of the witness. Second, we develop a compiler from any dynamic zk-SNARK to recursion-free and bounded incremental verifiable computation (BIVC). Interestingly, when instantiated with a dynamic zk-SNARK that uses a sublinear-size data structure (which we build and call Dynavold), this transformation yields the first BIVC scheme with sublinear state. We finally discuss further applications of dynamic zk-SNARKs, including dynamic state proofs and dynamic ML proofs for retraining
A Simple Framework for Secure Key Leasing
Get PDFSecure key leasing (a.k.a. key-revocable cryptography) enables us to lease a cryptographic key as a quantum state in such a way that the key can be later revoked in a verifiable manner. We propose a simple framework for constructing cryptographic primitives with secure key leasing via the certified deletion property of BB84 states. Based on our framework, we obtain the following schemes.
- A public key encryption scheme with secure key leasing that has classical revocation based on any IND-CPA secure public key encryption scheme. Prior works rely on either quantum revocation or stronger assumptions such as the quantum hardness of the learning with errors (LWE) problem.
- A pseudorandom function with secure key leasing that has classical revocation based on one-way functions. Prior works rely on stronger assumptions such as the quantum hardness of the LWE problem.
- A digital signature scheme with secure key leasing that has classical revocation based on the quantum hardness of the short integer solution (SIS) problem. Our construction has static signing keys, i.e., the state of a signing key almost does not change before and after signing. Prior constructions either rely on non-static signing keys or indistinguishability obfuscation to achieve a stronger goal of copy-protection.
In addition, all of our schemes remain secure even if a verification key for revocation is leaked after the adversary submits a valid certificate of deletion. To our knowledge, all prior constructions are totally broken in this setting. Moreover, in our view, our security proofs are much simpler than those for existing schemes
FLUENT: A Tool for Efficient Mixed-Protocol Semi-Private Function Evaluation
Get PDFIn modern business to customer interactions, handling private or confidential data is essential. Private Function Evaluation (PFE) protocols ensure the privacy of both the customers\u27 input data and the business\u27 function evaluated on it which is often sensitive intellectual property (IP). However, fully hiding the function in PFE results in high performance overhead. Semi-Private Function Evaluation (SPFE) is a generalization of PFE to only partially hide the function, whereas specific non-critical components remain public. Our paper introduces a novel framework designed to make SPFE accessible to non-experts and practical for real-world deployments.
To achieve this, we improve on previous SPFE solutions in two aspects.
First, we enhance the developer experience by leveraging High-Level Synthesis (HLS), making our tool more user-friendly than previous SPFE frameworks.
Second, we achieve a speedup compared to the previous state-of-the-art through more efficient underlying constructions and the usage of Lookup Tables (LUTs).
We evaluate the performance of our framework in terms of communication and runtime efficiency. Our final implementation is available as an open-source project, aiming to bridge the gap between advanced cryptographic protocols and their practical application in industry scenarios