Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs
Get PDFWe describe several families of efficiently implementable Boolean functions achieving provable trade-offs between resiliency, nonlinearity, and algebraic immunity. In particular, the following statement holds for each of the function families that we propose. Given integers , , and , it is possible to construct an -variable function which has resiliency at least , linear bias (which is an equivalent method of expressing nonlinearity) at most and algebraic immunity at least ; further, is linear in , and , and the function can be implemented using 2-input gates, which is essentially optimal
Efficient Fuzzy PSI Based on Prefix Representation
Get PDFFuzzy PSI is a variant of PSI, which on input a set of points from the receiver and sender respectively, allows the receiver to learn which of the sender\u27s points lie within a threshold distance under a specific distance metric.
Baarsen and Pu (EUROCRYPT\u2724) first proposed efficient fuzzy PSI protocols for general distances (where ) in -dimensional space, achieving communication complexity linear in the input size, , and . However, they leave open the question of whether the prefix technique of Chakraborti et al. (USENIX Security\u2723) can further reduce the communication complexity of their fuzzy PSI protocols in both low and high dimensions.
In this work, we thoroughly explore using the prefix technique to reduce the complexity of fuzzy PSI. First, we propose fuzzy matching protocols for and distances, where the communication complexity is improved from to for , and from to for distance. By applying our fuzzy matching protocol in conjunction with spatial hashing, we propose fuzzy PSI protocols for low-dimensional space. For high-dimensional space, we present the first fuzzy PSI protocols achieving communication and computation complexity that scales logarithmically in and linearly in dimension and input set sizes.
We implement our fuzzy PSI protocols and compare them with state-of-the-art protocols. Experimental results demonstrate that our protocols achieve superior performance for large : for input size , , and , our protocol requires -- less running time and -- lower communication than existing protocols
There are siblings of which are permutations for even
No full textLet be the all-one vector and denote the component-wise multiplication of two vectors in . We study the vector space over generated by the functions , where and is the cyclic left shift function. The functions in are shift-invariant and the well known function used in several cryptographic primitives is contained in . For even , we show that the permutations from with respect to composition form an Abelian group, which is isomorphic to the unit group of the residue ring . This isomorphism yields an efficient theoretic and algorithmic method for constructing and studying a rich family of shift-invariant permutations on which are natural generalizations of . To demonstrate it, we apply the obtained results to investigate the function on
Batched & Non-interactive Blind Signatures from Lattices
Get PDFNon-interactive blind signatures (NIBS; Eurocrypt \u2723) allow a signer to asynchronously generate presignatures for a recipient, ensuring that only the intended recipient can extract a blinded signature for a random message.
We introduce a new generalization called non-interactive batched blind signatures (NIBBS). Our goal is to reduce the computation and communication costs for signers and receivers, by batching multiple blind signature queries. More precisely, we define the property of \u27succinct communication\u27 which requires that the communication cost from signer to receiver be independent of the batch size. NIBBS is very suitable for large-scale deployments requiring only minimal signer-side effort.
We design a NIBBS scheme and prove its security based on the hardness of lattice assumptions (in the random oracle model). When instantiated with the low-depth PRF candidate Crypto Dark Matter (TCC \u2718) and the succinct lattice-based proof system for rank-1 constraint systems (Crypto \u2723), our final signature size is 308 KB with <1 KB communication
Sandwich BUFF: Achieving Non-Resignability Using Iterative Hash Functions
Get PDFWe revisit the BUFF transform, which was proposed by Cremers et al. (S&P\u2721) as a means to achieve security properties beyond standard unforgeability for digital signature schemes. One of these properties, non-resignability (NR), has recently drawn some attention due to a strong impossibility result for the original definition of the property. Recent follow-up work then considered a variant (sNR) of the original definition, and showed that it is satisfied by the BUFF transform when the underlying hash function is modeled as a random oracle - while the original impossibility result still applies for the plain model. This raises the natural question of whether the BUFF transform satisfies sNR in a more fine-grained use of the random oracle model, when we consider a real-life iterative-hash-function design (such as Merkle-Damgaard or Sponge) and instead idealize the round function. Our discoveries in this direction are two-fold:
First, contrary to what one might expect, we show that there is a simple attack on the non-resignability property sNR of the BUFF-transform when instantiated with an iterative hash function. The attack relies on leaking an intermediate result of the hash computation to the adversary who is challenged to resign the message. This negative result once more shows the subtlety in the non-resignability property.
Second, on the positive side, we propose a small modification to the original BUFF transform, which we call Sandwich BUFF (for reasons to become clear), and prove the non-resignability property sNR of Sandwich BUFF both for Merkle-Damgaard-based hash functions in the random oracle model, and for Sponge-based hash functions in the random permutation model
Differentially Private Compression and the Sensitivity of LZ77
Get PDFWe initiate the study of differentially private data-compression schemes motivated by the insecurity of the popular Compress-Then-Encrypt framework. Data compression is a useful tool which exploits redundancy in data to reduce storage/bandwidth when files are stored or transmitted. However, if the contents of a file are confidential then the length of a compressed file might leak confidential information about the content of the file itself. Encrypting a compressed file does not eliminate this leakage as data encryption schemes are only designed to hide the content of confidential message instead of the length of the message. In our proposed Differentially Private Compress-Then-Encrypt framework, we add a random positive amount of padding to the compressed file to ensure that any leakage satisfies the rigorous privacy guarantee of -differential privacy. The amount of padding that needs to be added depends on the sensitivity of the compression scheme to small changes in the input, i.e., to what degree can changing a single character of the input message impact the length of the compressed file. While some popular compression schemes are highly sensitive to small changes in the input, we argue that effective data compression schemes do not necessarily have high sensitivity. Our primary technical contribution is analyzing the fine-grained sensitivity of the LZ77 compression scheme (IEEE Trans. Inf. Theory 1977) which is one of the most common compression schemes used in practice. We show that the global sensitivity of the LZ77 compression scheme has the upper bound where denotes the size of the sliding window. When , we show the lower bound for the global sensitivity of the LZ77 compression scheme which is tight up to a sublogarithmic factor
Precision Strike: Targeted Misclassification of Accelerated CNNs with a Single Clock Glitch
Get PDFFault injection attacks (FIAs) present a significant threat to the integrity of deep neural networks (DNNs), particularly in hardware-accelerated deployments on field-programmable gate arrays (FPGAs). These attacks intentionally introduce faults into the system, leading the DNN to generate incorrect outputs. This work presents the first successful targeted misclassification attack against a convolutional neural network (CNN) implemented on FPGA hardware, achieved by injecting a single clock glitch at the final layer (argmax) to manipulate the predicted output class. Our attack targets the commonly adopted argmax layer, a lightweight replacement for softmax in resource-constrained implementations. By precisely injecting a single clock glitch during the comparison phase of the argmax operation, the attack reliably induces misclassifications, forcing the model to \u27skip\u27 a specifically chosen class and output an incorrect label for it without affecting the computed scores of other classes.
Unlike prior works that only cause random misclassifications, our attack achieves a high success rate of 80–87% for a targeted class, without inducing collateral misclassifications of other classes. Our evaluations show a significant reduction in classification accuracy, with the model’s performance dropping from an initial 94.7% to an average final accuracy ranging from 7.7–14.7%. Our attack is demonstrated on a CNN model implemented using a common systolic array architecture, which is well-suited for resource-constrained edge devices and artificial intelligence (AI) accelerators. Our study confirms the vulnerability of hardware-accelerated machine learning systems to low-cost physical attacks, emphasizing the critical need for hardware-level countermeasures in safety-critical machine learning applications
Is It Even Possible? On the Parallel Composition of Asynchronous MPC Protocols
Get PDFDespite several known idiosyncrasies separating the synchronous and the asynchronous models, asynchronous secure multi-party computation (MPC) protocols demonstrate high-level similarities to synchronous MPC, both in design philosophy and abstract structure. As such, a coveted, albeit elusive, desideratum is to devise automatic translators (e.g., protocol compilers) of feasibility and efficiency results from one model to the other.
In this work, we demonstrate new challenges associated with this goal. Specifically, we study the case of parallel composition in the asynchronous setting. We provide formal definitions of this composition operation in the UC framework, which, somewhat surprisingly, have been missing from the literature. Using these definitions, we then turn to charting the feasibility landscape of asynchronous parallel composition.
We first prove strong impossibility results for composition operators that do not assume knowledge of the functions and/or the protocols that are being composed. These results draw a grim feasibility picture, which is in sharp contrast with the synchronous model, and highlight the question:
Is asynchronous parallel composition even a realistic goal?
To answer the above (in the affirmative), we provide conditions on the composed protocols that enable a useful form of asynchronous parallel composition, as it turns out to be common in existing constructions
Lattice-Based Group Signatures in the Standard Model, Revisited
Get PDFThe study of lattice-based group signatures has been a prominent research direction since 2010. While recent advances in the field have yielded schemes in the random oracle model with strong security properties and nearly practical efficiency, the current state of affairs for lattice-based group signatures in the standard model is still much less satisfactory. Existing schemes, proposed by Katsumata and Yamada (EUROCRYPT\u2719) or implied by generic non-interactive zero-knowledge proofs for NP (by Peikert and Shiehian at CRYPTO\u2719 and by Waters at STOC\u2724), either only fulfil a weak notion of anonymity called selfless anonymity, or require a strong lattice assumption, or suffer from extremely large signatures and/or public keys.
This work aims to enhance the state of affairs for lattice-based group signatures in the standard model. We provide improved constructions that simultaneously achieves: (i) signature and public key sizes significantly smaller than those of known schemes; (ii) full anonymity in the CPA and CCA senses; (iii) security based on standard SIS and LWE assumptions with polynomial approximation factors regarding worst-case lattice problems (in general lattices). Our design approach slightly departs from that of existing pairing-based and lattice-based constructions. In the design process, we adapt and develop several lattice-based cryptographic ingredients that may be of independent interest. At the heart of our constructions is a reasonably efficient non-interactive zero-knowledge proof system for relations typically appearing in advanced privacy-preserving lattice-based cryptographic protocols. These relations are addressed by a trapdoor -protocol with an inverse polynomial soundness error, which is made non-interactive via the standard-model Fiat-Shamir transform of Canetti et al. (STOC\u2719) and a compiler by Libert et al. (ASIACRYPT\u2720)
Computationally-Sound Symbolic Cryptography in Lean
Get PDFWe present a formally-verified (in Lean 4) framework for translating symbolic cryptographic proofs into the computationally-sound ones. Symbolic cryptography is a well-established field that allows reasoning about cryptographic protocols in an abstract way and is relatively easy to verify using proof assistants. Unfortunately, it often lacks a connection to the computational aspects of real-world cryptography. Computationally-sound cryptography, on the other hand, captures this connection much better, but it is often more complex, less accessible, and much harder to verify formally. Several works in the past have provided a bridge between the two, but, to our knowledge, none of them have been implemented in a proof assistant.
We close this gap by formalizing the translation from symbolic to computationally-sound cryptography in Lean 4. Our framework is based on the work of Micciancio (Eurocrypt, 2010) and Li and Micciancio (CSF, 2018), which builds on the idea of using co-induction (instead of induction) for reasoning about an adversary\u27s knowledge in a symbolic setting. Our work encompasses (1) the formalization of the symbolic cryptography framework, (2) the formalization of the computationally sound cryptography framework, and (3) the formalization of the translation between the two. We also provide (4) an extended example of circuit garbling, which is a well-known cryptographic protocol frequently used in secure multi-party computation.
We believe that our work will serve as a foundation for future research in the area of formal verification of cryptographic protocols, as it enables reasoning about cryptographic protocols more abstractly while still providing a formally verified connection to the computational aspects of real-world cryptography