IACR News
Updates on the COVID-19 situation are on the
Announcement channel.
Here you can see all recent updates to the IACR webpage. These updates are also available:
24 April 2023
Universitat Rovira i Virgili, Department of Computer Science and Mathematics, Spain
Organisation:
The CRISES research group at Rovira i Virgili University is seeking to recruit a full-time postdoctoral researcher in computer security. The group focuses on theoretical advances for computer security and privacy, often in collaboration with industry and the government. The successful candidate will work in an exciting international campus located at the sunny and Mediterranean city of Tarragona, Spain. For further information please check: https://crises-deim.urv.cat/
Your role:
The successful candidate is expected to contribute to the HERMES project, which focuses on supply chain security and data provenance. The post, however, offers the candidate the opportunity to develop their own research agenda within the area of security and privacy of software systems. The successful candidate will work under the direction of Dr. Rolando Trujillo together with other members of the CRISES research group. Candidates with experience in cryptographic protocols, threat modelling or formal verification are encouraged to apply.
Offer:
The University offers a two-year employment that may be extended up to three years. The University offers highly competitive salaries and is an equal opportunity employer.
Applications:
Applications will be considered on receipt until 15 Jun 2023 (closing date).
Closing date for applications:
Contact: Dr. Rolando Trujillo (rolando.trujillo@urv.cat)
Shanghai Jiao Tong University
The School of Cyber Science and Engineering (formerly known as the School of Information Security Engineering) of Shanghai Jiao Tong University was founded in October 2000. It was the first school-level training base for high-level information security professionals in China and was jointly established by the Ministry of Education of China, the Ministry of Science and Technology of China, and the Shanghai Municipal People’s Government. The undergraduate and postgraduate students of the school mainly come from the top 100 key high schools and 985/double first-class universities in China. The school is ranked among the best cyberspace security nationwide every year. The school has a solid foundation and strength in the field of academic research and technological innovation on cyberspace security. The school is committed to building a world-class academic research center, cultivating the talents of the country and society. The school is in great demand of a number of world renowned professors, outstanding young researchers, full-time research fellows and post-doctors. The school now has a few positions available at the rank of tenure-track Assistant/Associate Professors, tenured Full Professors as well as Research Assistants/Associates and Post-Doctors in theory and practice of cyberspace security.
Applicants should have (a) a doctoral degree in Computer Science, Electronic Engineering, Communication, Mathematics or Statistics; (b) an established track record in research and scholarship; (c) expertise in the cryptographic and security research areas; and (d) a demonstrated commitment to excellence in teaching.
The school will provide highly competitive remuneration packages and assist applicants to apply for various national, provincial and ministerial level talent programs such as “Outstanding Youth Talents Program”, Shanghai “Talents Program”,etc. We will also assist on employment of spouses, schooling for children and medical care.
Applicants should have (a) a doctoral degree in Computer Science, Electronic Engineering, Communication, Mathematics or Statistics; (b) an established track record in research and scholarship; (c) expertise in the cryptographic and security research areas; and (d) a demonstrated commitment to excellence in teaching.
The school will provide highly competitive remuneration packages and assist applicants to apply for various national, provincial and ministerial level talent programs such as “Outstanding Youth Talents Program”, Shanghai “Talents Program”,etc. We will also assist on employment of spouses, schooling for children and medical care.
Closing date for applications:
Contact:
Chaoping Xing, emial: xingcp@sjtu.edu.cn;
Ni Liang, email: liangni@sjtu.edu.cn
Abhiram Kothapalli, Srinath Setty
This paper introduces HyperNova, a recursive argument for proving incremental computations whose steps are expressed with CCS (Setty et al. ePrint 2023), a customizable constraint system that simultaneously generalizes Plonkish, R1CS, and AIR without overheads. A distinguishing aspect of HyperNova is that the prover’s cost at each step is dominated by a single multi-scalar multiplication (MSM) of size equal to the number of variables in the constraint system, which is optimal when using an MSM-based commitment scheme.
To construct HyperNova, we generalize folding schemes (CRYPTO 22), to allow instances from two (potentially) different NP relations, that share the same structure, to be folded; we refer to this generalization as multi-folding schemes. Furthermore, we devise a public-coin, multi-folding scheme for instances in CCS and linearized CCS (a variant of CCS that we introduce). This construction can be viewed as an “early stopping” version of Spartan (CRYPTO 20), applied to a carefully-crafted polynomial that includes claims about prior linearized CCS instances. The prover’s work in the multi-folding scheme is a linear number of finite field operations and the verifier’s work is a logarithmic number of finite field operations and a single group scalar multiplication. We then construct incrementally verifiable computation (IVC) from non-interactive multi-folding schemes with the lowest prover costs and the lowest recursion overheads in the literature. We also provide an alternate realization of HyperNova with a black box use of Nova, which nearly eliminates the need for deferred arithmetic when instantiated with a cycle of elliptic curves.
As an additional contribution, we describe nlookup, a lookup argument, that is particularly suited for recursive arguments based on folding schemes. Specifically, at a particular step in an incremental computation, for m lookups into a table of size $n$ $(m << n)$, the prover’s work is dominated by $O(n)$ finite field operations and it requires only $O(m \cdot \log{n})$ degree-2 constraints and $O(\log{n})$ hash evaluations in the incremental computation. nlookup is currently not suitable for efficiently encoding bitwise operations, but it provides a powerful tool for efficiently encoding (large) finite state machines and proving their transitions with recursive SNARKs.
To construct HyperNova, we generalize folding schemes (CRYPTO 22), to allow instances from two (potentially) different NP relations, that share the same structure, to be folded; we refer to this generalization as multi-folding schemes. Furthermore, we devise a public-coin, multi-folding scheme for instances in CCS and linearized CCS (a variant of CCS that we introduce). This construction can be viewed as an “early stopping” version of Spartan (CRYPTO 20), applied to a carefully-crafted polynomial that includes claims about prior linearized CCS instances. The prover’s work in the multi-folding scheme is a linear number of finite field operations and the verifier’s work is a logarithmic number of finite field operations and a single group scalar multiplication. We then construct incrementally verifiable computation (IVC) from non-interactive multi-folding schemes with the lowest prover costs and the lowest recursion overheads in the literature. We also provide an alternate realization of HyperNova with a black box use of Nova, which nearly eliminates the need for deferred arithmetic when instantiated with a cycle of elliptic curves.
As an additional contribution, we describe nlookup, a lookup argument, that is particularly suited for recursive arguments based on folding schemes. Specifically, at a particular step in an incremental computation, for m lookups into a table of size $n$ $(m << n)$, the prover’s work is dominated by $O(n)$ finite field operations and it requires only $O(m \cdot \log{n})$ degree-2 constraints and $O(\log{n})$ hash evaluations in the incremental computation. nlookup is currently not suitable for efficiently encoding bitwise operations, but it provides a powerful tool for efficiently encoding (large) finite state machines and proving their transitions with recursive SNARKs.
Sashidhar Jakkamsetti, Zeyu Liu, Varun Madathil
Private messaging systems that use a bulletin board, like privacy-preserving blockchains, have been a popular topic during the last couple of years.
In these systems, typically a private message is posted on the board for a recipient and the privacy requirement is that no one can determine the sender and the recipient of the message.
Until recently, the efficiency of these recipients was not considered, and the party had to perform a naive scan of the board to retrieve their messages.
More recently, works like Fuzzy Message Detection (FMD),
Private Signaling (PS),
and Oblivious Message Retrieval (OMR)
have studied the problem of protecting recipient privacy
by outsourcing the message retrieval process to an untrusted server.
However, FMD only provides limited privacy guarantees, and PS and OMR greatly lack scalability.
In this work, we present a new construction for private signaling which is both asymptotically superior and concretely orders of magnitude faster than all prior works while providing full privacy. Our constructions make use of a trusted execution environment (TEE) and an Oblivious RAM to improve the computation complexity of the server. We also improve the privacy guarantees by keeping the recipient hidden even during the retrieval of signals from the server. Our proof-of-concept open-source implementation shows that for a server serving a hundred thousand recipients and ten million messages, it only takes $< 6$ milliseconds to process a sent message, and $< 200$ milliseconds to process a retrieval (of 100 signals) request from a recipient.
In this work, we present a new construction for private signaling which is both asymptotically superior and concretely orders of magnitude faster than all prior works while providing full privacy. Our constructions make use of a trusted execution environment (TEE) and an Oblivious RAM to improve the computation complexity of the server. We also improve the privacy guarantees by keeping the recipient hidden even during the retrieval of signals from the server. Our proof-of-concept open-source implementation shows that for a server serving a hundred thousand recipients and ten million messages, it only takes $< 6$ milliseconds to process a sent message, and $< 200$ milliseconds to process a retrieval (of 100 signals) request from a recipient.
Abtin Afshar, Geoffroy Couteau, Mohammad Mahmoody, Elahe Sadeghi
In this work, we initiate a study of $K$-NIKE protocols in the fine-grained setting, in which there is a polynomial gap between the running time of the honest parties and that of the adversary. Our goal is to show the possibility, or impossibility, of basing such protocols on weaker assumptions than those of $K$-NIKE for $K \geq 3$. Our contribution is threefold.
- We show that random oracles can be used to obtain fine-grained $K$-NIKE protocols for every constant $K$. In particular, we show how to generalize Merkle's two-party protocol to $K$ parties in such a way that the honest parties ask $n$ queries each, while the adversary needs $n^{K/(K-1)}$ queries to the random oracle to find the key.
- We then improve the security by further using algebraic structures, while avoiding pairings. In particular, we show that there is a 4-party NIKE in Shoup's generic group model with a quadratic gap between the number of queries by the honest parties vs. that of the adversary.
- Finally, we show a limitation of using purely algebraic methods for obtaining $3$-NIKE. In particular, we show that any $n$-query $3$-NIKE protocol in Maurer's generic group model can be broken by a $O(n^2)$-query attacker. Maurer's GGM is more limited compared with Shoup's both for the parties and the adversary, as there are no explicit labels for the group elements. Despite being more limited, this model still captures the Diffie Hellman protocol. Prior to our work, it was open to break $3$-NIKE protocols in Maurer's model with any polynomial number of queries.
Kai-Min Chung, Yao-Ting Lin, Mohammad Mahmoody
Commitments are fundamental in cryptography. In the classical world, commitments are equivalent to the existence of one-way functions. It is also known that the most desired form of commitments in terms of their round complexity, i.e., non-interactive commitments, cannot be built from one-way functions in a black-box way [Mahmoody-Pass, Crypto'12]. However, if one allows the parties to use quantum computation and communication, it is known that non-interactive commitments (to classical bits) are in fact possible [Koshiba-Odaira, Arxiv'11 and Bitansky-Brakerski, TCC'21].
We revisit the assumptions behind non-interactive commitments in a quantum world and study whether they can be achieved using quantum computation and classical communication based on a black-box use of one-way functions. We prove that doing so is impossible unless the Polynomial Compatibility Conjecture [Austrin et al. Crypto'22] is false. We further extend our impossibility to protocols with quantum decommitments. This complements the positive result of Bitansky and Brakerski [TCC'21], as they only required a classical decommitment message. Because non-interactive commitments can be based on injective one-way functions, assuming the Polynomial Compatibility Conjecture, we also obtain a black-box separation between one-way functions and injective one-way functions (e.g., one-way permutations) even when the construction and the security reductions are allowed to be quantum. This improves the separation of Cao and Xue [Theoretical Computer Science'21] in which they only allowed the security reduction to be quantum.
At a technical level, we prove that sampling oracles at random from ``sufficiently large'' sets (of oracles) will make them one-way against polynomial quantum-query adversaries who also get arbitrary polynomial-size quantum advice about the oracle. This gives a natural generalization of the recent results of Hhan et al.[Asiacrypt'19] and Chung et al. [FOCS'20].
We revisit the assumptions behind non-interactive commitments in a quantum world and study whether they can be achieved using quantum computation and classical communication based on a black-box use of one-way functions. We prove that doing so is impossible unless the Polynomial Compatibility Conjecture [Austrin et al. Crypto'22] is false. We further extend our impossibility to protocols with quantum decommitments. This complements the positive result of Bitansky and Brakerski [TCC'21], as they only required a classical decommitment message. Because non-interactive commitments can be based on injective one-way functions, assuming the Polynomial Compatibility Conjecture, we also obtain a black-box separation between one-way functions and injective one-way functions (e.g., one-way permutations) even when the construction and the security reductions are allowed to be quantum. This improves the separation of Cao and Xue [Theoretical Computer Science'21] in which they only allowed the security reduction to be quantum.
At a technical level, we prove that sampling oracles at random from ``sufficiently large'' sets (of oracles) will make them one-way against polynomial quantum-query adversaries who also get arbitrary polynomial-size quantum advice about the oracle. This gives a natural generalization of the recent results of Hhan et al.[Asiacrypt'19] and Chung et al. [FOCS'20].
Antonio Faonio, Dario Fiore, Markulf Kohlweiss, Luigi Russo, Michal Zajac
We study sufficient conditions for compiling simulation-extractable zkSNARKs from information-theoretic interactive oracle proofs (IOP) using a simulation-extractable commit-and-prove system for its oracles.
Specifically, we define simulation extractability for opening and evaluation proofs of polynomial commitment schemes, which we then employ to prove the security of zkSNARKS obtained from polynomial IOP prove systems, such as Plonk and Marlin. To instantiate our methodology we additionally prove that KZG commitments satisfy our simulation extractability requirement, despite being naturally malleable. To this end, we design a relaxed notion of simulation extractability that matches how KZG commitments are used and optimized in real-world prove systems.
Only the proof that KZG satisfies this relaxed simulation extractability property relies on the algebraic group model (AGM) and random oracle (RO). We thus isolate the use of (and thus the reliance on) these strong heuristics.
Marc Titus Trifan, Alexandru Nicolau, Alexander Veidenbaum
The increased popularity of Machine Learning as a Service (MLaaS) makes the privacy of user data and network weights a critical concern. Using Torus FHE (TFHE) offers a solution for privacy-preserving computation in a cloud environment by allowing computation directly over encrypted data. However, software TFHE implementations of cyphertext-cyphertext multiplication needed when both input data and weights are encrypted are either lacking or are too slow. This paper proposes a new way to improve the performance of such multiplication by applying carry save addition. Its theoretical speedup is proportional to the bit width of the plaintext integer operands. This also speeds up multi-operand summation. A speedup of 15x is obtained for 16-bit multiplication on a 64-core processor when compared to previous results. Multiplication also becomes more than twice as fast on a GPU if our approach is utilized. This leads to much faster dot product and convolution computations, which combine multiplications and a multi-operand sum. A 45x speedup is achieved for a 16-bit, 32-element dot product and a ~30x speedup for a convolution with a 32x32 filter size.
Sanjam Garg, Abhishek Jain, Pratyay Mukherjee, Rohit Sinha, Mingyuan Wang, Yinuo Zhang
We propose hinTS --- a new threshold signature scheme built on top of the widely used BLS signatures. Our scheme enjoys the following attractive features:
\begin{itemize} \item A {\em silent setup} process where the joint public key of the parties is computed as a deterministic function of their locally computed public keys. \item Support for {\em dynamic} choice of thresholds and signers, after the silent setup, without further interaction. \item Support for {\em general} access policies; in particular, native support for {\em weighted} thresholds with zero additional overhead over standard threshold setting. \item Strong security guarantees, including proactive security and forward security. \end{itemize}We prove the security of our scheme in the algebraic group model and provide implementation and extensive evaluation. Our scheme outperforms all prior proposals that aim to avoid distributed key generation in terms of aggregation time, signature size, and verification time. As an example, the aggregation time for 1000 signers is under 0.5 seconds, while both signing and verification are constant time algorithms, taking roundly 1 ms and 17.5 ms respectively.
The key technical contribution of our work involves the design of special-purpose succinct proofs to {\em efficiently} prove the well-formedness of aggregated public keys. Our solution uses public ``hints'' released by the signers as part of their public keys (hence the name hinTS).
\begin{itemize} \item A {\em silent setup} process where the joint public key of the parties is computed as a deterministic function of their locally computed public keys. \item Support for {\em dynamic} choice of thresholds and signers, after the silent setup, without further interaction. \item Support for {\em general} access policies; in particular, native support for {\em weighted} thresholds with zero additional overhead over standard threshold setting. \item Strong security guarantees, including proactive security and forward security. \end{itemize}We prove the security of our scheme in the algebraic group model and provide implementation and extensive evaluation. Our scheme outperforms all prior proposals that aim to avoid distributed key generation in terms of aggregation time, signature size, and verification time. As an example, the aggregation time for 1000 signers is under 0.5 seconds, while both signing and verification are constant time algorithms, taking roundly 1 ms and 17.5 ms respectively.
The key technical contribution of our work involves the design of special-purpose succinct proofs to {\em efficiently} prove the well-formedness of aggregated public keys. Our solution uses public ``hints'' released by the signers as part of their public keys (hence the name hinTS).
Zhuohui Feng, Ye Luo, Chao Wang, Qianqian Yang, Zhiquan Liu, Ling Song
Plaintext structures are a commonly-used technique for improving differential cryptanalysis. Generally, there are two types of plaintext structures: multiple-differential structures and truncated-differential structures. Both types have been widely used in cryptanalysis of S-box-based ciphers while for SPECK, an Addition-Rotation-XOR (ARX) cipher, the truncated-differential structure has not been used so far. In this paper, we investigate the properties of modular addition and propose a method to construct truncated-differential structures for SPECK. Moreover, we show that a combination of both types of structures is also possible for SPECK. For recovering the key of SPECK, we propose dedicated algorithms and apply them to various differential distinguishers, which helps to obtain a series of improved attacks on all variants of SPECK. Notably, on SPECK128, the time complexity of the attack can be reduced by a factor up to 2^15. The results show that the combination of both structures helps to improve the data and time complexity at the same time, as in the cryptanalysis of S-box-based ciphers.
Pratish Datta, Tapas Pal
This paper presents the first decentralized multi-authority attribute-based inner product functional encryption (MA-ABIPFE) schemes supporting vectors of a priori unbounded lengths. The notion of AB-IPFE, introduced by Abdalla et al. [ASIACRYPT 2020], combines the access control functionality of attribute-based encryption (ABE) with the possibility of evaluating linear functions on encrypted data. A decentralized MA-ABIPFE defined by Agrawal et al. [TCC 2021] essentially enhances the ABE component of AB-IPFE to the decentralized multi-authority setting where several authorities can independently issue user keys involving attributes under their control. In MA-ABIPFE for unbounded vectors (MA-ABUIPFE), encryptors can encrypt vectors of arbitrary length under access policies of their choice whereas authorities can issue secret keys to users involving attributes under their control and vectors of arbitrary lengths. Decryption works in the same way as for MA-ABIPFE provided the lengths of the vectors within the ciphertext and secret keys match.
We present two MA-ABUIPFE schemes supporting access policies realizable by linear secret sharing schemes (LSSS), in the significantly faster prime-order bilinear groups under decisional assumptions based on the target groups which are known to be weaker compared to their counterparts based in the source groups. The proposed schemes demonstrate different trade-offs between versatility and underlying assumptions. The first scheme allows each authority to control a bounded number of attributes and is proven secure under the well-studied decisional bilinear Diffie-Hellman (DBDH) assumption. On the other hand, the second scheme allows authorities to control exponentially many attributes, that is, supports large attribute universe, and is proven secure under a non-interactive q-type variant of the DBDH assumption called L-DBDH, similar to what was used in prior large-universe multi-authority ABE (MA-ABE) construction.
When compared with the only known MA-ABIPFE scheme due to Agrawal et al. [TCC 2021], our schemes offer significantly higher efficiency while offering greater flexibility and security under weaker assumptions at the same time. Moreover, unlike Agrawal et al., our schemes can support the appearance of the same attributes within an access policy arbitrarily many times. Since efficiency and practicality is the prime focus of this work, we prove the security of our constructions in the random oracle model against static adversaries similar to prior works on MA-ABE with similar motivations and assumptions. On the technical side, we extend the unbounded IPFE techniques of Dufour-Sans and Pointcheval [ACNS 2019] to the context of MA-ABUIPFE by introducing a novel hash-decomposition technique.
James Bartusek, Dakshita Khurana, Akshayaram Srinivasan
Can a sender non-interactively transmit one of two strings to a receiver without knowing which string was received? Does there exist minimally-interactive secure multiparty computation that only makes (black-box) use of symmetric-key primitives? We provide affirmative answers to these questions in a model where parties have access to shared EPR pairs, thus demonstrating the cryptographic power of this resource.
First, we construct a one-shot (i.e., single message) string oblivious transfer (OT) protocol with random receiver bit in the shared EPR pairs model, assuming the (sub-exponential) hardness of LWE. Building on this, we show that {\em secure teleportation through quantum channels} is possible. Specifically, given the description of any quantum operation $Q$, a sender with (quantum) input $\rho$ can send a single classical message that securely transmits $Q(\rho)$ to a receiver. That is, we realize an ideal quantum channel that takes input $\rho$ from the sender and provably delivers $Q(\rho)$ to the receiver without revealing any other information. This immediately gives a number of applications in the shared EPR pairs model: (1) non-interactive secure computation of unidirectional \emph{classical} randomized functionalities, (2) NIZK for QMA from standard (sub-exponential) hardness assumptions, and (3) a non-interactive \emph{zero-knowledge} state synthesis protocol.
Next, we construct a two-round (round-optimal) secure multiparty computation protocol for classical functionalities in the shared EPR pairs model that is \emph{unconditionally-secure} in the (quantum-accessible) random oracle model.
Classically, both of these results cannot be obtained without some form of correlated randomness shared between the parties, and the only known approach is to have a trusted dealer set up random (string) OT correlations. In the quantum world, we show that shared EPR pairs (which are simple and can be deterministically generated) are sufficient. At the heart of our work are novel techniques for making use of entangling operations to generate string OT correlations, and for instantiating the Fiat-Shamir transform using correlation-intractability in the quantum setting.
First, we construct a one-shot (i.e., single message) string oblivious transfer (OT) protocol with random receiver bit in the shared EPR pairs model, assuming the (sub-exponential) hardness of LWE. Building on this, we show that {\em secure teleportation through quantum channels} is possible. Specifically, given the description of any quantum operation $Q$, a sender with (quantum) input $\rho$ can send a single classical message that securely transmits $Q(\rho)$ to a receiver. That is, we realize an ideal quantum channel that takes input $\rho$ from the sender and provably delivers $Q(\rho)$ to the receiver without revealing any other information. This immediately gives a number of applications in the shared EPR pairs model: (1) non-interactive secure computation of unidirectional \emph{classical} randomized functionalities, (2) NIZK for QMA from standard (sub-exponential) hardness assumptions, and (3) a non-interactive \emph{zero-knowledge} state synthesis protocol.
Next, we construct a two-round (round-optimal) secure multiparty computation protocol for classical functionalities in the shared EPR pairs model that is \emph{unconditionally-secure} in the (quantum-accessible) random oracle model.
Classically, both of these results cannot be obtained without some form of correlated randomness shared between the parties, and the only known approach is to have a trusted dealer set up random (string) OT correlations. In the quantum world, we show that shared EPR pairs (which are simple and can be deterministically generated) are sufficient. At the heart of our work are novel techniques for making use of entangling operations to generate string OT correlations, and for instantiating the Fiat-Shamir transform using correlation-intractability in the quantum setting.
Lennart Braun, Moritz Huppert, Nora Khayata, Thomas Schneider, Oleksandr Tkachenko
Secure Multi-Party Computation (MPC) is continuously becoming more and more practical. Many optimizations have been introduced, making MPC protocols more suitable for solving real-world problems. However, the MPC protocols and optimizations are usually implemented as a standalone proof of concept or in an MPC framework and are tightly coupled with special-purpose circuit formats, such as Bristol Format. This makes it very hard and time-consuming to re-use algorithmic advances and implemented applications in a different context. Developing generic algorithmic optimizations is exceptionally hard because the available MPC tools and formats are not generic and do not provide the necessary infrastructure.
In this paper, we present FUSE: A Framework for Unifying and Optimizing Secure Multi-Party Computation Implementations with Efficient Circuit Storage. FUSE provides a flexible intermediate representation (FUSE IR) that can be used across different platforms and in different programming languages, including C/C++, Java, Rust, and Python. We aim at making MPC tools more interoperable, removing the tight coupling between high-level compilers for MPC and specific MPC protocol engines, thus driving knowledge transfer. Our framework is inspired by the widely known LLVM compiler framework. FUSE is portable, extensible, and it provides implementation-agnostic optimizations.
As frontends, we implement HyCC (CCS'18), the Bristol circuit format, and MOTION (TOPS'22), meaning that these can be automatically converted to FUSE IR. We implement several generic optimization passes, such as automatic subgraph replacement and vectorization, to showcase the utility and efficiency of our framework. Finally, we implement as backends MOTION and MP-SPDZ (CCS'20), so that FUSE IR can be run by these frameworks in an MPC protocol, as well as other useful backends for JSON output and the DOT language for graph visualization. With FUSE, it is possible to use any implemented frontend with any implemented backend and vice-versa. FUSE IR is not only efficient to work on and much more generic than any other format so far -- supporting, e.g., function calls, hybrid MPC protocols as well as user-defined building blocks, and annotations -- while maintaining backwards-compatibility, but also compact, with smaller storage size than even minimalistic formats such as Bristol already for a few hundred operations.
In this paper, we present FUSE: A Framework for Unifying and Optimizing Secure Multi-Party Computation Implementations with Efficient Circuit Storage. FUSE provides a flexible intermediate representation (FUSE IR) that can be used across different platforms and in different programming languages, including C/C++, Java, Rust, and Python. We aim at making MPC tools more interoperable, removing the tight coupling between high-level compilers for MPC and specific MPC protocol engines, thus driving knowledge transfer. Our framework is inspired by the widely known LLVM compiler framework. FUSE is portable, extensible, and it provides implementation-agnostic optimizations.
As frontends, we implement HyCC (CCS'18), the Bristol circuit format, and MOTION (TOPS'22), meaning that these can be automatically converted to FUSE IR. We implement several generic optimization passes, such as automatic subgraph replacement and vectorization, to showcase the utility and efficiency of our framework. Finally, we implement as backends MOTION and MP-SPDZ (CCS'20), so that FUSE IR can be run by these frameworks in an MPC protocol, as well as other useful backends for JSON output and the DOT language for graph visualization. With FUSE, it is possible to use any implemented frontend with any implemented backend and vice-versa. FUSE IR is not only efficient to work on and much more generic than any other format so far -- supporting, e.g., function calls, hybrid MPC protocols as well as user-defined building blocks, and annotations -- while maintaining backwards-compatibility, but also compact, with smaller storage size than even minimalistic formats such as Bristol already for a few hundred operations.
Liliya Kraleva, Mohammad Mahzoun, Raluca Posteuca, Dilara Toprakhisar, Tomer Ashur, Ingrid Verbauwhede
Physically Unclonable Functions (PUFs) are being proposed as a low cost alternative to permanently store secret keys or provide device authentication without requiring non-volatile memory, large e-fuses or other dedicated processing steps. In the literature, PUFs are split into two main categories. The so-called strong PUFs are mainly used for authentication purposes, hence also called authentication PUFs. They promise to be lightweight by avoiding extensive digital post-processing and cryptography. The so-called weak PUFs, also called key generation PUFs, can only provide authentication when combined with a cryptographic authentication protocol.
Over the years, multiple research results have demonstrated that Strong PUFs can be modeled and attacked by machine learning techniques. Hence, the general assumption is that the security of a strong PUF is solely dependent on its security against machine learning attacks. The goal of this paper is to debunk this myth, by analyzing and breaking three recently published Strong PUFs (Suresh et al., VLSI Circuits 2020; Liu et al., ISSCC 2021; and Jeloka et al., VLSI Circuits 2017). The attacks presented in this paper have practical complexities and use generic symmetric key cryptanalysis techniques.
Bhuvnesh Chaturvedi, Anirban Chakraborty, Ayantika Chatterjee, Debdeep Mukhopadhyay
Fully Homomorphic Encryption (FHE) promises to secure our data on the untrusted cloud, by allowing arbitrary computations on encrypted data. However, the malleability and flexibility provided by FHE schemes also open up arena for integrity issues where a cloud server can intentionally or accidentally perturb client’s data. Contemporary FHE schemes do not provide integrity guarantees and, thus, assume a honest-but-curious server who, although curious to glean sensitive information, performs all operations judiciously. However, in practice, a server can also be malicious as well as compromised, where it can perform crafted perturbations in the cloud-stored data and computational results to entice the client into providing feedback. While some effort has been made to protect FHE schemes against such adversaries, they do not completely stop such attacks, given the wide scope of deployment of contemporary FHE schemes in modern-day applications. In this work, we demonstrate reaction-based full-key recovery attack on two of the well-known FHE schemes, TFHE and FHEW. We first define practical scenarios where a client pursuing FHE services from a malicious server can inadvertently act as a Ciphertext Verification Oracle (CVO) by reacting to craftily perturbed computations. In particular, we propose two novel and distinct reaction attacks on both TFHE and FHEW. In the first attack, the adversary (malicious server) extracts the underlying error values to form an exact system of Learning with Errors (LWE) equations. As the security of LWE collapses with the leakage of the errors, the adversary is capable of extracting the secret key. In the second attack, we show that the attacker can directly recover the secret key in a bit-by-bit fashion by taking advantage of the key distribution of these FHE schemes. The results serve as a stark reminder that FHE schemes need to be secured at the application level apart from being secure at the primitive level so that the security of participants against realistic attacks can be ensured. As the currently available verifiable FHE schemes in literature cannot stop such attacks, we propose vr$^2$FHE (Verify - then - Repair or React) that is built on top of present implementations of TFHE and FHEW, using the concept of the Merkle tree. vr$^2$FHE first verifies the computational results at the client end and then, depending on the perturbation pattern, either repairs the message or chooses to request for recomputation. We show that such requests are benign as they do not leak exploitable information to the server, thereby thwarting both the attacks on TFHE and FHEW.
Jonathan Bootle, Vadim Lyubashevsky, Ngoc Khanh Nguyen, Alessandro Sorniotti
We present a framework for building practical anonymous credential schemes based on the hardness of lattice problems. The running time of the prover and verifier is independent of the number of users and linear in the number of attributes. The scheme is also compact in practice, with the proofs being as small as a few dozen kilobytes for arbitrarily large (say up to $2^{128}$) users with each user having several attributes. The security of our scheme is based on a new family of lattice assumptions which roughly states that given short pre-images of random elements in some set $S$, it is hard to create a pre-image for a fresh element in such a set. We show that if the set admits efficient zero-knowledge proofs of knowledge of a commitment to a set element and its pre-image, then this yields practically-efficient privacy-preserving primitives such as blind signatures, anonymous credentials, and group signatures. We propose a candidate instantiation of a function from this family which allows for such proofs and thus yields practical lattice-based primitives.
James Bartusek, Dakshita Khurana, Giulio Malavolta, Alexander Poremba, Michael Walter
We develop a simple compiler that generically adds publicly-verifiable deletion to a variety of cryptosystems. Our compiler only makes use of one-way functions (or one-way state generators, if we allow the public verification key to be quantum). Previously, similar compilers either relied on the use of indistinguishability obfuscation (Bartusek et. al., ePrint:2023/265) or almost-regular one-way functions (Bartusek, Khurana and Poremba, arXiv:2303.08676).
Alia Umrani, Paolo Palmieri
User authentication and message confidentiality are the basic security requirements of high-end applications such as multicast communication and distributed systems. Several efficient signature-then-encrypt cryptographic schemes have been proposed to offer these security requirements with lower computational cost and communication overhead. However, signature-then-encryption techniques take more computation time than signcryption techniques. Signcryption accomplishes both digital signature and public key encryption functions in a single logical step and at a much lower cost than ``signature followed by encryption.'' Several signcryption schemes based on bilinear pairing operations have been proposed. Similarly, anonymous multi-receiver encryption has recently risen in prominence in multicast communication and distributed settings, where the same messages are sent to several receivers but the identity of each receiver should remain private. Anonymous multi-receiver encryption allows a receiver to obtain the plaintext by decrypting the ciphertext using their own private key, while their identity is kept secret to anyone, including other receivers. Among the Certificateless Multi-receiver Encryption (CLMRE) schemes that have been introduced, Hung et al. proposed an efficient Anonymous Multireceiver Certificateless Encryption (AMCLE) scheme ensuring confidentiality and anonymity based on bilinear pairings and is secure against IND-CCA and ANON-CCA.
In this paper, we substantially extend Hung et al.’s multireceiver certificateless encryption scheme to a Multireceiver Certificateless Signcryption (MCLS) scheme that provides confidentiality along with authentication. We show that, as compared to Hung et al.’s encryption scheme, our signcryption scheme requires only three additional multiplication operations for signcryption and unsigncryption phases. Whereas, the signcryption cost is linear with the number of designated receivers while the unsigncryption cost remains constant for each designated receiver. We compare the results with other existing single receiver and multireceiver signcryption schemes in terms of number of operations, exemption of key escrow problem, and public key settings. The scheme proposed in this paper is more efficient for single and multireceiver signcryption schemes while providing exemption from the key escrow problem, and working in certificateless public key settings.
In this paper, we substantially extend Hung et al.’s multireceiver certificateless encryption scheme to a Multireceiver Certificateless Signcryption (MCLS) scheme that provides confidentiality along with authentication. We show that, as compared to Hung et al.’s encryption scheme, our signcryption scheme requires only three additional multiplication operations for signcryption and unsigncryption phases. Whereas, the signcryption cost is linear with the number of designated receivers while the unsigncryption cost remains constant for each designated receiver. We compare the results with other existing single receiver and multireceiver signcryption schemes in terms of number of operations, exemption of key escrow problem, and public key settings. The scheme proposed in this paper is more efficient for single and multireceiver signcryption schemes while providing exemption from the key escrow problem, and working in certificateless public key settings.
Ittai Abraham, Gilad Asharov, Shravani Patil, Arpita Patra
We prove that perfectly-secure optimally-resilient secure Multi-Party Computation (MPC) for a circuit with $C$ gates and depth $D$ can be obtained in $O((Cn+n^4 + Dn^2)\log n)$ communication complexity and $O(D)$ expected time. For $D \ll n$ and $C\geq n^3$, this is the first perfectly-secure optimal-resilient MPC protocol with linear communication complexity per gate and constant expected time complexity per layer.
Compared to state-of-the-art MPC protocols in the player elimination framework [Beerliova and Hirt TCC'08, and Goyal, Liu, and Song CRYPTO'19], for $C>n^3$ and $D \ll n$, our results significantly improve the run time from $\Omega(n+D)$ to expected $O(D)$ while keeping communication complexity at $O(Cn\log n)$.
Compared to state-of-the-art MPC protocols that obtain an expected $O(D)$ time complexity [Abraham, Asharov, and Yanai TCC'21], for $C>n^3$, our results significantly improve the communication complexity from $O(Cn^4\log n)$ to $O(Cn\log n)$ while keeping the expected run time at $O(D)$.
One salient part of our technical contribution is centered around a new primitive we call "detectable secret sharing". It is perfectly-hiding, weakly-binding, and has the property that either reconstruction succeeds or $O(n)$ parties are (privately) detected. On the one hand, we show that detectable secret sharing is sufficiently powerful to generate multiplication triplets needed for MPC. On the other hand, we show how to share $p$ secrets via detectable secret sharing with communication complexity of just $O(n^4\log n+p \log n)$. When sharing $p\geq n^4$ secrets, the communication cost is amortized to just $O(1)$ field elements per secret.
Our second technical contribution is a new Verifiable Secret Sharing protocol that can share $p$ secrets at just $O(n^4\log n+pn\log n)$ word complexity. When sharing $p\geq n^3$ secrets, the communication cost is amortized to just $O(n)$ filed elements per secret. The best prior required $\Omega(n^3)$ communication per secret.
Compared to state-of-the-art MPC protocols in the player elimination framework [Beerliova and Hirt TCC'08, and Goyal, Liu, and Song CRYPTO'19], for $C>n^3$ and $D \ll n$, our results significantly improve the run time from $\Omega(n+D)$ to expected $O(D)$ while keeping communication complexity at $O(Cn\log n)$.
Compared to state-of-the-art MPC protocols that obtain an expected $O(D)$ time complexity [Abraham, Asharov, and Yanai TCC'21], for $C>n^3$, our results significantly improve the communication complexity from $O(Cn^4\log n)$ to $O(Cn\log n)$ while keeping the expected run time at $O(D)$.
One salient part of our technical contribution is centered around a new primitive we call "detectable secret sharing". It is perfectly-hiding, weakly-binding, and has the property that either reconstruction succeeds or $O(n)$ parties are (privately) detected. On the one hand, we show that detectable secret sharing is sufficiently powerful to generate multiplication triplets needed for MPC. On the other hand, we show how to share $p$ secrets via detectable secret sharing with communication complexity of just $O(n^4\log n+p \log n)$. When sharing $p\geq n^4$ secrets, the communication cost is amortized to just $O(1)$ field elements per secret.
Our second technical contribution is a new Verifiable Secret Sharing protocol that can share $p$ secrets at just $O(n^4\log n+pn\log n)$ word complexity. When sharing $p\geq n^3$ secrets, the communication cost is amortized to just $O(n)$ filed elements per secret. The best prior required $\Omega(n^3)$ communication per secret.
Quan Yuan, Mehdi Tibouchi, Masayuki Abe
In post-quantum cryptography, hash-based signature schemes are attractive choices because of the weak assumptions. Most existing hash-based signature schemes are proven secure against post-quantum chosen message attacks (CMAs), where the adversaries are able to execute quantum computations and classically query to the signing oracle. In some cases, the signing oracle is also considered quantum-accessible, meaning that the adversaries are able to send queries with superpositions to the signing oracle. Considering this, Boneh and Zhandry [BZ13] propose a stronger security notion called existential unforgeability under quantum chosen message attacks (EUF-qCMA). We call it quantum-access security (or Q2 security in some literature). The quantum-access security of practical signature schemes is lacking in research, especially of the hash-based ones. In this paper, we analyze the quantum-access security of hash-based signature schemes in two directions. First, we show concrete quantum chosen message attacks (or superposition attacks) on existing hash-based signature schemes, such as SPHINCS and SPHINCS+. The complexity of the attacks is obviously lower than that of optimal classical chosen message attacks, implying that quantum chosen message attacks are more threatening than classical ones to these schemes. Second, we propose a simple variant of SPHINCS+ and give security proof against quantum chosen message attacks. As far as we know, it is the first practical hash-based stateless signature scheme against quantum chosen message attacks with concrete provable security.