Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
Trust Nobody: Privacy-Preserving Proofs for Edited Photos with Your Laptop
Get PDFThe Internet has plenty of images that are transformations (e.g., resize, blur) of confidential original images. Several scenarios (e.g., selling images over the Internet, fighting disinformation, detecting deep fakes) would highly benefit from systems allowing to verify that an image is the result of a transformation applied to a confidential authentic image. In this paper, we focus on systems for proving and verifying the correctness of transformations of authentic images guaranteeing: 1) confidentiality (i.e., the original image remains private), 2) efficient proof generation (i.e., the proof certifying the correctness of the transformation can be computed with a common laptop) even for high-resolution images, 3) authenticity (i.e., only the advertised transformations have been applied) and 4) fast detection of fraud proofs. Our contribution consists of the following results:
- We present new definitions following in part the ones proposed by Naveh and Tromer [IEEE S&P 2016] and strengthening them to face more realistic adversaries.
- We propose techniques leveraging the way typical transformations work to then efficiently instantiate ZK-snarks circumventing the major bottlenecks due to claims about large pre-images of cryptographic hashes.
- We present a 1st construction based on an ad-hoc signature scheme and an and-hoc cryptographic hash function, obtaining for the first time all the above 4 properties.
- We present a 2nd construction that, unlike in previous results, works with the signature scheme and cryptographic hash function included in the C2PA specifications.
Experimental results confirm the viability of our approach: in our 1st construction, an authentic transformation (e.g., a resize or a crop) of a high-resolution image of 30 MP can be generated on a common 8 cores PC in about 41 minutes employing less than 4 GB of RAM. Our 2nd construction is roughly one order of magnitude slower than our 1st construction. Prior results instead either require expensive computing resources or provide unsatisfying confidentiality
A New Fine Tuning Method for FHEW/TFHE Bootstrapping with IND-CPAD Security
Get PDFFully homomorphic encryption (FHE) schemes enable computation on encrypted data, making them a crucial component of privacy-enhancing technologies.
The availability of encrypted computation arises a new security notion, so-called -security, proposed by Li et al. (CRYPTO\u2722), which considers both computational and statistical security.
The key challenge is that, unlike computational security (commonly fixed at 128, 192, or 256 bits), statistical security requirements depend heavily on the application (e.g., circuit shape or number of queries).
Thus, smooth control over the statistical security parameter is essential.
FHEW-like schemes offer the best latency and smallest key sizes. However, Cheon et al. (CCS\u2724) showed a key-recovery attack that exploits failure events during legitimate evaluation queries.
Consequently, achieving a sufficiently low bootstrapping failure probability, proportional to , is critical for the statistical security of FHEW-like schemes.
A major limitation is that FHEW’s parameter sets are sparse, and suitable parameters achieving the exact target failure probability often do not exist.
This typically forces the use of unnecessarily large parameters, leading to excessive computational costs.
Recently, Bernard et al. (Eurocrypt\u2725) introduced a method that significantly reduces bootstrapping failure probability with minimal overhead, but their parameter sets remain sparse.
In this work, we propose a new bootstrapping technique, cutoff blind rotation, which provides an additional axis of parameter optimization by enabling a smooth trade-off between computation and failure probability.
This technique allows nearly continuous control of the bootstrapping failure probability in FHEW-like schemes without extra client-side overhead.
We further provide concrete parameter sets achieving various failure probabilities (, , and ) in our OpenFHE implementation.
The implementation results show that the bootstrapping runtime can be reduced by refining the failure probability
Probabilistic Attacks and Enhanced Security for Private Set Intersection in the Internet Setting from Lightweight Oblivious PRF
Get PDFPrivacy Set Intersection (PSI) has been an important research topic within privacy computation. Its main function is to allow two parties to compute the intersection of their private sets without revealing any other private information. Therefore, PSI can be applied to various real-world scenarios.
Chase and Miao presented an impressive construction ``Private set intersection in the Internet setting from lightweight oblivious prf\u27\u27 (CM20 for short) at Crypto 2020, highlighting its convenient structure and optimal communication cost. However, it does have some security vulnerabilities. Let be the privacy set of user , be the privacy set of user . The CM20 protocol uses a pseudorandom function (PRF) to encrypt the privacy of into and the privacy of into , as . It then sends random data to user and random data to user using a random oblivious transfer technique. User computes and sends to user , and user uses and to re-encrypt . Repeat this until re-encrypts all the privacy in all the privacy sets , packages them up and sends them to , who completes the privacy set intersection. However, if an adversary obtains and by any means, they can recover the PRF\u27s encryption of the user\u27s privacy, and the recovery process is non-trivial. This significantly weakens the security of the CM20 protocol.
In this paper, we make three main contributions. First, based on the above analysis, we present a method for attacking CM20, called {\em probabilistic attacks}. This attack is based on estimating and analysing the frequency distribution of the encrypted data from the PRF and the probability distribution of the original private data, and determining the relationship between the two. Although not 100\% effective, this method of attack poses a significant threat to the security of user data.
Secondly, we introduce a new tool called the {\em perturbed pseudorandom generator} (PPRG). We show that the PPRG can overcome probabilistic attacks by replacing the random oblivious transfer and one of the hash functions (originally there were two) in CM20.
Finally, we provide a dedicated indistinguishability against chosen-plaintext attack (IND-CPA) security model for this PSI protocol. The efficiency analysis shows that the proposed PSI is comparable to CM20\u27s PSI, whether on a PC, MAC, pad or mobile phone
Efficient 2PC for Constant Round Secure Equality Testing and Comparison
Get PDFSecure equality testing and comparison are two important primitives widely used in many secure computation scenarios, such as privacy-preserving machine learning, private set intersection, and secure data mining, etc. This work proposes new constant-round two-party computation (2PC) protocols for secure equality testing and comparison.
Our protocols are designed in the online/offline paradigm.
For 32-bit inputs, the online communication cost of our equality testing protocol and secure comparison protocol are as low as 76 bits (1\% of ABY) and 384 bits (5\% of ABY) , respectively.
Our benchmarks show that (i) for 32-bit equality testing, our scheme performs faster than the Guo \emph{et al.} (EUROCRYPT 2023) and of the garbled circuit (GC) with the half-gate optimization (CRYPTO 2015). (ii) for 32-bit secure comparison, our scheme performs faster than Guo \emph{et al.} (EUROCRYPT 2023), faster than both Rathee \emph{et al.} (CCS 2020) and GC with the half-gate optimization
Quantum-Safe Public Key Blinding from MPC-in-the-Head Signature Schemes
Get PDFKey blinding produces pseudonymous digital identities by rerandomizing public keys of a digital signature scheme. It is used in anonymous networks to provide the seemingly contradictory goals of anonymity and authentication. Current key blinding schemes are based on the discrete log assumption. Eaton, Stebila and Stracovsky (LATINCRYPT 2021) proposed the first key blinding schemes from lattice assumptions. However, the large public keys and lack of QROM security means they are not ready to replace existing solutions.
We present a new way to build key blinding schemes form any MPC-in-the-Head signature scheme. These schemes rely on well-studied symmetric cryptographic primitives and admit short public keys. We prove a general framework for constructing key blinding schemes and for proving their security in the quantum random oracle model (QROM).
We instantiate our framework with the recent AES-based Helium signature scheme (Kales and Zaverucha, 2022). Blinding Helium only adds a minor overhead to the signature and verification time. Both Helium and the aforementioned lattice-based key blinding schemes were only proven secure in the ROM. This makes our results the first QROM proof of Helium and the first fully quantum-safe public key blinding scheme
Scalable Collaborative zk-SNARK and Its Application to Fully Distributed Proof Delegation
Get PDFCollaborative zk-SNARK (USENIX\u2722) allows multiple parties to compute a proof over distributed witness. It offers a promising application called proof delegation (USENIX\u2723), where a client delegates the tedious proof generation to many servers while ensuring no one can learn the witness. Unfortunately, existing works suffer from significant efficiency issues and face challenges when scaling to complex applications.
In this work, we introduce the first scalable collaborative zk-SNARK for general circuits, built upon HyperPlonk (Eurocrypt\u2723). Our result overcomes existing barriers, offering fully distributed workload and small communication. For data-parallel circuits, the communication overhead is even sublinear.
We propose several efficient collaborative and distributed protocols for multivariate primitives, which form the main building blocks of our results and may be of independent interest.
In addition, we design a new permutation check protocol for Plonk arithmetization, which is MPC-friendly and suitable for collaborative zk-SNARKs.
With 128 servers jointly generating a proof for a circuit of size gates, the experiment demonstrates over speedup and reduced RAM requirements compared to a local prover, while the witness is still private. Previous works were unable to achieve such savings in both time and memory efficiency. Moreover, our protocol performs well under various network conditions, making it practical for real-world applications
A new multivariate primitive from CCZ equivalence
Get PDFMultivariate Cryptography is one of the candidates for Post-quantum Cryptography. Multivariate schemes are usually constructed by applying two secret affine invertible transformations to a set of multivariate polynomials (often quadratic). The polynomials possess a trapdoor that allows the legitimate user to find a solution of the corresponding system, while the public polynomials look like random polynomials. The polynomials and are said to be affine equivalent. In this article, we present a more general way of constructing a multivariate scheme by considering the CCZ equivalence, which has been introduced and studied in the context of vectorial Boolean functions
On the Independence Heuristic in the Dual Attack
Get PDFPost-quantum cryptography deals with the development and analysis of cryptographic schemes that are assumed to be secure even against attackers with access to a powerful quantum computers. Along the main candidates for quantum-safe solutions are cryptographic schemes, whose security are based on classic lattice problems such
as the bounded-distance decoding (BDD) problem or learning with errors (LWE) problem. In this work we contribute to the analysis of an attack category against these problems called dual attack.
Our first contributions is to provide theoretical counterarguments against a so-called independence assumption, which was used in earlier works on this attack, and which was shown to be contradicting practical experiments. Then, we provide estimates on the success probability and the cost of the dual attack against the decisional version of the BDD problem. These estimates are derived both rigorously and heuristically. Finally, we also provide experimental evidence that confirms these results
Randomness Generation for Secure Hardware Masking - Unrolled Trivium to the Rescue
Get PDFMasking is a prominent strategy to protect cryptographic implementations against side-channel analysis. Its popularity arises from the exponential security gains that can be achieved for (approximately) quadratic resource utilization. Many variants of the countermeasure tailored for different optimization goals have been proposed. The common denominator among all of them is the implicit demand for robust and high entropy randomness. Simply assuming that uniformly distributed random bits are available, without taking the cost of their generation into account, leads to a poor understanding of the efficiency vs. security tradeoff of masked implementations. This is especially relevant in case of hardware masking schemes which are known to consume large amounts of random bits per cycle due to parallelism. Currently, there seems to be no consensus on how to most efficiently derive many pseudo-random bits per clock cycle from an initial seed and with properties suitable for masked hardware implementations.
In this work, we evaluate a number of building blocks for this purpose and find that hardware-oriented stream ciphers like Trivium and its reduced-security variant Bivium B outperform most competitors when implemented in an \emph{unrolled} fashion. Unrolled implementations of these primitives enable the flexible generation of many bits per cycle, which is crucial for satisfying the large randomness demands of state-of-the-art masking schemes.
According to our analysis, only Linear Feedback Shift Registers (LFSRs), when also unrolled, are capable of producing long non-repetitive sequences of random-looking bits at a higher rate per cycle for the same or lower cost as Trivium and Bivium B. Yet, these instances do not provide black-box security as they generate only linear outputs. We experimentally demonstrate that using multiple output bits from an LFSR in the same masked implementation can violate probing security and even lead to harmful randomness cancellations. Circumventing these problems, and enabling an independent analysis of randomness generation and masking, requires the use of cryptographically stronger primitives like stream ciphers.
As a result of our studies, we provide an evidence-based estimate for the cost of securely generating fresh random bits per cycle. Depending on the desired level of black-box security and operating frequency, this cost can be as low as to ASIC gate equivalent (GE) or to FPGA look-up tables (LUTs), where is the number of random bits required. Our results demonstrate that the cost per bit is (sometimes significantly) lower than estimated in previous works, incentivizing parallelism whenever exploitable. This provides further motivation to potentially move low randomness usage from a primary to a secondary design goal in hardware masking research
hodlCoin: A Financial Game
Get PDFThe hodlCoin game is a competitive zero-sum massively multiplayer staking protocol where the goal is to hodl (stake) an asset for long periods of time. By hodling, a user deposits coins of a given asset in a common reserve and receives a proportional amount of hodlCoins. Users who un-hodl (unstake) pay a fee that is accumulated in the common reserve. Thus, the longer a user hodls, in comparison with other users, the more the user will benefit from fees paid by the users who are un-hodling earlier. Surprisingly, we prove here that, thanks to the accumulation of fees, the price of hodlCoins in comparison with the underlying asset never decreases