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:
03 March 2021
Mark Abspoel, Ronald Cramer, Daniel Escudero, Ivan Damgård, Chaoping Xing
In 2016, Guruswami and Wootters showed Shamir's secret-sharing scheme defined over an extension field has a regenerating property. Namely, we can compress each share to an element of the base field by applying a linear form, such that the secret is determined by a linear combination of the compressed shares. Immediately it seemed like an application to improve the complexity of unconditionally secure multiparty computation must be imminent; however, thus far, no result has been published.
We present the first application of regenerating codes to MPC, and show that its utility lies in reducing the number of rounds. Concretely, we present a protocol that obliviously evaluates a depth-$d$ arithmetic circuit in $d + O(1)$ rounds, in the amortized setting of parallel evaluations, with $o(n^2)$ ring elements communicated per multiplication. Our protocol is secure against the maximal adversary corrupting $t < n/2$ parties. All existing approaches in this setting have complexity $\Omega(n^2)$.
Moreover, we extend some of the theory on regenerating codes to Galois rings. It was already known that the repair property of MDS codes over fields can be fully characterized in terms of its dual code. We show this characterization extends to linear codes over Galois rings, and use it to show the result of Guruswami and Wootters also holds true for Shamir's scheme over Galois rings.
We present the first application of regenerating codes to MPC, and show that its utility lies in reducing the number of rounds. Concretely, we present a protocol that obliviously evaluates a depth-$d$ arithmetic circuit in $d + O(1)$ rounds, in the amortized setting of parallel evaluations, with $o(n^2)$ ring elements communicated per multiplication. Our protocol is secure against the maximal adversary corrupting $t < n/2$ parties. All existing approaches in this setting have complexity $\Omega(n^2)$.
Moreover, we extend some of the theory on regenerating codes to Galois rings. It was already known that the repair property of MDS codes over fields can be fully characterized in terms of its dual code. We show this characterization extends to linear codes over Galois rings, and use it to show the result of Guruswami and Wootters also holds true for Shamir's scheme over Galois rings.
02 March 2021
Michael Zuzak, Yuntao Liu, Ankur Srivastava
Logic locking has been proposed to counter security threats during IC fabrication. Such an approach restricts unauthorized use by injecting sufficient module level error to derail application level IC functionality. However, recent research has identified a trade-off between the error rate of logic locking and its resilience to a Boolean satisfiablity (SAT) attack. As a result, logic locking often cannot inject sufficient error to impact an IC while maintaining SAT resilience. In this work, we propose using architectural context available during resource binding to co-design architectures and locking configurations capable of high corruption and SAT resilience simultaneously. To do so, we propose 2 security-focused binding/locking algorithms and apply them to bind/lock 11 MediaBench benchmarks. The resulting circuits showed a 26x and 99x increase in the application errors of a fixed locking configuration while maintaining SAT resilience and incurring minimal overhead compared to other binding schemes. Locking applied post-binding could not achieve a high application error rate and SAT resilience simultaneously.
Sebastian Faust, Carmit Hazay, David Kretzler, Benjamin Schlosser
Covert security has been introduced as a compromise between semi-honest and malicious security. In a nutshell, covert security guarantees that malicious behavior can be detected by the honest parties with some probability, but in case detection fails all bets are off. While the security guarantee offered by covert security is weaker than full-fledged malicious security, it comes with significantly improved efficiency. An important extension of covert security introduced by Asharov and Orlandi (ASIACRYPT'12) is public verifiability, which allows the honest parties to create a publicly verifiable certificate of malicious behavior. Public verifiability significantly strengthen covert security as the certificate allows punishment via an external party, e.g., a judge.
Most previous work on publicly verifiable covert (PVC) security focuses on the two-party case, and the multi-party case has mostly been neglected. In this work, we introduce a novel compiler for multi-party PVC secure protocols. Our compiler leverages time-lock encryption to offer high probability of cheating detection (often also called deterrence factor) independent of the number of involved parties. Moreover, in contrast to the only earlier work that studies PVC in the multi-party setting (CRYPTO'20), we provide the first full formal security analysis.
Most previous work on publicly verifiable covert (PVC) security focuses on the two-party case, and the multi-party case has mostly been neglected. In this work, we introduce a novel compiler for multi-party PVC secure protocols. Our compiler leverages time-lock encryption to offer high probability of cheating detection (often also called deterrence factor) independent of the number of involved parties. Moreover, in contrast to the only earlier work that studies PVC in the multi-party setting (CRYPTO'20), we provide the first full formal security analysis.
Onur Gunlu
This thesis addresses security and privacy problems for digital devices and biometrics, where a secret key is generated for authentication, identification, or secure computations. A physical unclonable function (PUF) is a promising solution for local security in digital devices. A low-complexity transform-coding algorithm is developed to make the information-theoretic analysis tractable and motivate a noisy (hidden) PUF source model.
The optimal trade-offs between the secret-key, privacy-leakage, and storage rates for multiple measurements of hidden PUFs are characterized. The first optimal and low-complexity code constructions are proposed. Polar codes are designed to achieve the best known rate tuples. The gains from cost-constrained controllable PUF measurements are illustrated to motivate extensions.
The optimal trade-offs between the secret-key, privacy-leakage, and storage rates for multiple measurements of hidden PUFs are characterized. The first optimal and low-complexity code constructions are proposed. Polar codes are designed to achieve the best known rate tuples. The gains from cost-constrained controllable PUF measurements are illustrated to motivate extensions.
Karlo Knezevic, Juraj Fulir, Domagoj Jakobovic, Stjepan Picek
The choice of activation functions can have a significant effect on the performance of a neural network. Although the researchers have been developing novel activation functions, Rectified Linear Unit ($ReLU$) remains the most common one in practice. This paper shows that evolutionary algorithms can discover new activation functions for side-channel analysis (SCA) that outperform $ReLU$.
Using Genetic Programming (GP), candidate activation functions are defined and explored (neuroevolution). As far as we know, this is the first attempt to develop custom activation functions for SCA. The ASCAD database experiments show this approach is highly effective compared to the state-of-the-art neural network architectures.
While the optimal performance is achieved when activation functions are evolved for the particular task, we also observe that these activation functions show the property of generalization and high performance for different SCA scenarios.
Bernardo Magri, Giulio Malavolta, Dominique Schröder, Dominique Unruh
Everlasting security models the setting where hardness assumptions hold during the execution of a protocol but may get broken in the future. Due to the strength of this adversarial model, achieving any meaningful security guarantees for composable protocols is impossible without relying on hardware assumptions (Müller-Quade and Unruh, JoC10). For this reason, a rich line of research has tried to leverage physical assumptions to construct well-known everlasting cryptographic primitives, such as commitment schemes. The only known everlastingly UC secure commitment scheme, due to Müller-Quade and Unruh (JoC10), assumes honestly generated hardware tokens. The authors leave the possibility of constructing everlastingly UC
secure commitments from malicious hardware tokens as an open problem.
In this work we close this gap by presenting the first construction of an everlastingly UC-secure commitment scheme in the fully malicious token model. Our scheme assumes the existence of physically uncloneable functions (PUFs) and is secure in the common reference string model. We also show that our results are tight by giving an impossibility proof for everlasting UC-secure computation from non-erasable tokens (such as PUFs), even with trusted setup.
In this work we close this gap by presenting the first construction of an everlastingly UC-secure commitment scheme in the fully malicious token model. Our scheme assumes the existence of physically uncloneable functions (PUFs) and is secure in the common reference string model. We also show that our results are tight by giving an impossibility proof for everlasting UC-secure computation from non-erasable tokens (such as PUFs), even with trusted setup.
David Knichel, Pascal Sasdrich, Amir Moradi
With an increasing number of mobile devices and their high accessibility, protecting the implementation of cryptographic functions in the presence of physical adversaries has become more relevant than ever. Over the last decade, a lion's share of research in this area has been dedicated to developing countermeasures at an algorithmic level. Here, masking has proven to be a promising approach due to the possibility of formally proving the implementation's security solely based on its algorithmic description by elegantly modeling the circuit behavior. Theoretically verifying the security of masked circuits becomes more and more challenging with increasing circuit complexity. This motivated the introduction of security notions that enable masking of single gates while still guaranteeing the security when the masked gates are composed. Systematic approaches to generate these masked gates - commonly referred to as gadgets - were restricted to very simple gates like 2-input AND gates. Simply substituting such small gates by a secure gadget usually leads to a large overhead in terms of fresh randomness and additional latency (register stages) being introduced to the design.
In this work, we address these problems by presenting a generic framework to construct trivially composable and secure hardware gadgets for arbitrary vectorial Boolean functions, enabling the transformation of much larger sub-circuits into gadgets. In particular, we present a design methodology to generate first-order secure masked gadgets which is well-suited for integration into existing Electronic Design Automation (EDA) tools for automated hardware masking as only the Boolean function expression is required. Furthermore, we practically verify our findings by conducting several case studies and show that our methodology outperforms various other masking schemes in terms of introduced latency or fresh randomness - especially for large circuits.
Shengyuan Feng, Junqing Gong, Jie Chen
In this paper, we propose the first generic framework for attribute-based encryptions (ABE) with master-secret-key-dependent-message security (mKDM security) for affine functions via predicate encodings by Chen, Gay and Wee [Eurocrypt 2015]. The construction is adaptively secure under standard $k$-Lin assumption in prime-order bilinear groups. By this, we obtain a set of new mKDM-secure ABE schemes with high expressiveness that have never been reached before: we get the first hierarchical IBE (HIBE) scheme and the first ABE scheme for arithmetic branching program (ABP) with mKDM security for affine functions. Thanks to the expressiveness (more concretely, delegability like HIBE), we can obtain mKDM-secure ABE against chosen-ciphertext attack (i.e., CCA security) via a classical CPA-to-CCA transformation that works well in the context of mKDM.
Yanbin Pan , Jun Xu, Nick Wadleigh, Qi Cheng
Any non-zero ideal in a number field can be factored into a product of prime ideals. In this paper we report a surprising connection between the complexity of the shortest vector problem (SVP) of prime ideals in number fields and their decomposition groups. When applying the result to number fields popular in lattice based cryptosystems, such as power-of-two cyclotomic fields, we show that a majority of rational primes lie under prime ideals admitting a polynomial time algorithm for SVP. Although the shortest vector problem of ideal lattices underpins the security of the Ring-LWE cryptosystem, this work does not break Ring-LWE, since the security reduction is from the worst case ideal SVP to the average case Ring-LWE, and it is one-way.
Alexander Bienstock, Yevgeniy Dodis, Kevin Yeo
In this paper, we study forward secret encrypted RAMs (FS eRAMs) which enable clients to outsource the storage of an n-entry array to a server. In the case of a catastrophic attack where both client and server storage are compromised, FS eRAMs guarantee that the adversary may not recover any array entries that were deleted or overwritten prior to the attack. A simple folklore FS eRAM construction with O(log n) overhead has been known for at least two decades. Unfortunately, no progress has been made since then. We show the lack of progress is fundamental by presenting an Ω(log n) lower bound for FS eRAMs proving that the folklore solution is optimal. To do this, we introduce the symbolic model for proving cryptographic data structures lower bounds that may be of independent interest.
Given this limitation, we investigate applications where forward secrecy may be obtained without the additional O(log n) overhead. We show this is possible for oblivious RAMs, memory checkers, and multicast encryption by incorporating the ideas of the folklore FS eRAM solution into carefully chosen constructions of the corresponding primitives.
Given this limitation, we investigate applications where forward secrecy may be obtained without the additional O(log n) overhead. We show this is possible for oblivious RAMs, memory checkers, and multicast encryption by incorporating the ideas of the folklore FS eRAM solution into carefully chosen constructions of the corresponding primitives.
Gayathri Garimella, Payman Mohassel, Mike Rosulek, Saeed Sadeghian, Jaspal Singh
Private set intersection reveals the intersection of two private sets, but many real-world applications require the parties to learn $\textit{only}$ partial information about the intersection.
In this paper we introduce a new approach for computing arbitrary functions of the intersection, provided that it is safe to also reveal the cardinality of the intersection. In the most general case, our new protocol provides the participants with secret shares of the intersection, which can be fed into any generic 2PC protocol. Certain computations on the intersection can also be done even more directly and efficiently, avoiding this secret-sharing step. These cases include computing only the cardinality of intersection, or the ``cardinality-sum'' application proposed in Ion et al. (ePrint 2017). Compared to the state-of-the-art protocol for computing on intersection (Pinkas et al., Eurocrypt 2019), our protocol has about $2.5-3\times$ less communication, and has faster running time on slower (50Mbps) networks.
Our new techniques can also be used to privately compute the {\em union} of two sets as easily as computing the intersection. Our protocol concretely improves the leading private set union protocol (Kolesnikov et al., Asiacrypt 2020) by a factor of $2-2.5\times$, depending on the network speed.
We then show how private set union can be used in a simple way to realize the ``Private-ID'' functionality suggested by Buddhavarapu et al.~(ePrint 2020). Our protocol is significantly faster than the prior Private-ID protocol, especially on fast networks.
All of our protocols are in the two-party setting and are secure against semi-honest adversaries.
Ju-Hwan Kim, Ji-Eun Woo, Soo-Jin Kim, So-Yeon Park, Dong-Guk Han
Recently, Machine Learning (ML) is widely investigated in the side-channel analysis (SCA) community. As an artificial neural network can extract the feature without preprocessing, ML-based SCA methods relatively less rely on the attacker's ability. Consequently, they outperform traditional methods.
Hiding is a countermeasure against SCA that randomizes the moments of manipulating sensitive data. Since hiding could disturb the neural network's learning, an attacker should design a proper architecture against hiding. In this paper, we propose inherently robust architecture against every kind of desynchronization. We demonstrated the proposed method with plenty of datasets, including open datasets. As a result, our method outperforms state-of-the-art on every dataset.
Saikrishna Badrinarayanan, Peihan Miao, Pratyay Mukherjee, Divya Ravi
We study the problem of secure multiparty computation for functionalities where only one party receives the output, to which we refer as solitary MPC. Recently, Halevi et al. (TCC 2019) studied fully secure (i.e., with guaranteed output delivery) solitary MPC and showed impossibility of such protocols for certain functionalities when there is no honest majority among the parties.
In this work, we study fully secure solitary MPC in the honest majority setting and focus on its round complexity. We note that a broadcast channel or public key infrastructure (PKI) setup is necessary for an $n$-party protocol against malicious adversaries corrupting up to $t$ parties where $n/3 \leq t < n/2$. Therefore, we study the following settings and ask the question: Can fully secure solitary MPC be achieved in fewer rounds than fully secure standard MPC in which all parties receive the output?
- When there is a broadcast channel and no PKI:
* We start with a negative answer to the above question. In particular, we show that the exact round complexity of fully secure solitary MPC is 3, which is the same as fully secure standard MPC.
* We then study the minimal number of broadcast rounds needed in the design of round-optimal fully secure solitary MPC. We show that both the first and second rounds of broadcast are necessary when $2 \lceil n/5 \rceil \leq t < n/2$, whereas pairwise-private channels suffice in the last round. Notably, this result also applies to fully secure standard MPC in which all parties receive the output.
- When there is a PKI and no broadcast channel, nevertheless, we show more positive results:
* We show an upper bound of 5 rounds for any honest majority. This is superior to the super-constant lower bound for fully secure standard MPC in the exact same setting.
* We complement this by showing a lower bound of 4 rounds when $3\lceil n/7 \rceil \leq t < n/2$.
* For the special case of $t=1,n=3$, when the output receiving party does not have an input to the function, we show an upper bound of $2$ rounds, which is optimal. When the output receiving party has an input to the function, we show a lower bound of 3, which matches an upper bound from prior work.
* For the special case of $t=2,n=5$, we show a lower bound of 3 rounds (an upper bound of 4 follows from prior work).
All our results also assume the existence of a common reference string (CRS) and pairwise-private channels. Our upper bounds use a decentralized threshold fully homomorphic encryption (dTFHE) scheme (which can be built from the learning with errors (LWE) assumption) as the main building block.
In this work, we study fully secure solitary MPC in the honest majority setting and focus on its round complexity. We note that a broadcast channel or public key infrastructure (PKI) setup is necessary for an $n$-party protocol against malicious adversaries corrupting up to $t$ parties where $n/3 \leq t < n/2$. Therefore, we study the following settings and ask the question: Can fully secure solitary MPC be achieved in fewer rounds than fully secure standard MPC in which all parties receive the output?
- When there is a broadcast channel and no PKI:
* We start with a negative answer to the above question. In particular, we show that the exact round complexity of fully secure solitary MPC is 3, which is the same as fully secure standard MPC.
* We then study the minimal number of broadcast rounds needed in the design of round-optimal fully secure solitary MPC. We show that both the first and second rounds of broadcast are necessary when $2 \lceil n/5 \rceil \leq t < n/2$, whereas pairwise-private channels suffice in the last round. Notably, this result also applies to fully secure standard MPC in which all parties receive the output.
- When there is a PKI and no broadcast channel, nevertheless, we show more positive results:
* We show an upper bound of 5 rounds for any honest majority. This is superior to the super-constant lower bound for fully secure standard MPC in the exact same setting.
* We complement this by showing a lower bound of 4 rounds when $3\lceil n/7 \rceil \leq t < n/2$.
* For the special case of $t=1,n=3$, when the output receiving party does not have an input to the function, we show an upper bound of $2$ rounds, which is optimal. When the output receiving party has an input to the function, we show a lower bound of 3, which matches an upper bound from prior work.
* For the special case of $t=2,n=5$, we show a lower bound of 3 rounds (an upper bound of 4 follows from prior work).
All our results also assume the existence of a common reference string (CRS) and pairwise-private channels. Our upper bounds use a decentralized threshold fully homomorphic encryption (dTFHE) scheme (which can be built from the learning with errors (LWE) assumption) as the main building block.
Mark Zhandry, Cong Zhang
The random oracle, generic group, and generic bilinear map models (ROM, GGM, GBM, respectively) are fundamental heuristics used to justify new computational assumptions and prove the security of efficient cryptosystems. While known to be invalid in some contrived settings, the heuristics generally seem reasonable for real-world applications.
In this work, we ask: \emph{which heuristics are closer to reality?} Or conversely, which heuristics are a larger leap? We answer this question through the framework of computational indifferentiability, showing that the ROM is a strictly ``milder'' heuristic than the GGM, which in turn is strictly milder than the GBM. While this may seem like the expected outcome, we explain why it does not follow from prior works and is not the a priori obvious conclusion. In order to prove our results, we develop new ideas for proving computational indifferentiable separations.
In this work, we ask: \emph{which heuristics are closer to reality?} Or conversely, which heuristics are a larger leap? We answer this question through the framework of computational indifferentiability, showing that the ROM is a strictly ``milder'' heuristic than the GGM, which in turn is strictly milder than the GBM. While this may seem like the expected outcome, we explain why it does not follow from prior works and is not the a priori obvious conclusion. In order to prove our results, we develop new ideas for proving computational indifferentiable separations.
Panagiotis Chatzigiannis, Foteini Baldimtsi, Konstantinos Chalkias
Enforcement of policy regulations and availability of auditing mechanisms are crucial building blocks for the adoption of distributed payment systems.
This paper reviews a number of existing proposals for distributed payment systems that offer some form of auditability for regulators. We identify two major distinct lines of work: payment systems that are not privacy-preserving such as Bitcoin, where regulation functionalities are typically tailored for organizations controlling many accounts, and privacy-preserving payment systems where regulation functionalities are typically targeted to user level.
We provide a systematization methodology over several axes of characteristics and performance, while highlighting insights and research gaps that we have identified, such as lack of dispute-resolution solutions between the regulator and the entity under audit, and the incompatibility of ledger pruning or off-chain protocols with regulatory requirements.
Based on our findings, we propose a number of exciting future research directions.
Gregor Leander, Shahram Rasoolzadeh
CRAFT is a lightweight tweakable Substitution-Permutation-Network (SPN) block cipher optimized for efficient protection of its implementations against Differential Fault Analysis (DFA) attacks. In this paper, we present an equivalent description of CRAFT up to a simple mapping on the plaintext, ciphertext and round tweakeys. We show that the new representation, for a sub-class of keys, leads to a new structure which is a Feistel network, i.e., with half state non-linear operation and half state key addition. This has two interesting consequences: First, the new structure of the cipher is less resistant against differential and linear cryptanalyses. Second, it allows a more efficient implementation of the cipher.
Ehsan Ebrahimi
In this paper, we show that OAEP transform is
indistinguishable under chosen ciphertext attack in the quantum random oracle model
if the underlying trapdoor permutation is quantum partial-domain one-way.
The existing post-quantum security of OAEP (TCC 2016-B )
requires a modification to the OAEP transform using an extra hash function.
We prove the security of the OAEP transform without any modification
and this answers an open question in
one of the finalists of NIST competition, NTRU submission, affirmatively.
Patrik Ekdahl, Thomas Johansson, Alexander Maximov, Jing Yang
In this paper we propose a faster variant of SNOW-V, called SNOW-Vi, that can perform fast enough not only in cloud settings but also on low grade CPUs. The increase in software performance is around 50% in average, up to 92 Gbps. This makes the applicability of the cipher much wider and it covers more use cases. SNOW-Vi differs in the way how the LFSR is updated and also introduces a new location of the tap $T2$ for a stronger security, while everything else is kept the same as in SNOW-V. The security analyses previously done for SNOW-V are not affected in most aspects, and SNOW-Vi provides the same 256-bit security level as SNOW-V.
Denis Diemert, Kai Gellert, Tibor Jager, Lin Lyu
We construct the currently most efficient signature schemes with tight multi-user security against adaptive corruptions. It is the first generic construction of such schemes, based on lossy identification schemes (Abdalla etal; JoC 2016), and the first to achieve strong existential unforgeability. It also has significantly more compact signatures than the previously most efficient construction by Gjosteen and Jager (CRYPTO 2018). When instantiated based on the decisional Diffie-Hellman assumption, a signature consists of only three exponents.
We propose a new variant of the generic construction of signatures from sequential OR-proofs by Abe, Ohkubo, and Suzuki (ASIACRYPT 2002) and Fischlin, Harasser, and Janson (EUROCRYPT 2020). In comparison to Fischlin etal, who focus on constructing signatures in the non-programmable random oracle model (NPROM), we aim to achieve tight security against adaptive corruptions, maximize efficiency, and to directly achieve strong existential unforgeability (also in the NPROM). This yields a slightly different construction and we use slightly different and additional properties of the lossy identification scheme.
Signatures with tight multi-user security against adaptive corruptions are a commonly-used standard building block for tightly-secure authenticated key exchange protocols. We also show how our construction improves the efficiency of all existing tightly-secure AKE protocols.
We propose a new variant of the generic construction of signatures from sequential OR-proofs by Abe, Ohkubo, and Suzuki (ASIACRYPT 2002) and Fischlin, Harasser, and Janson (EUROCRYPT 2020). In comparison to Fischlin etal, who focus on constructing signatures in the non-programmable random oracle model (NPROM), we aim to achieve tight security against adaptive corruptions, maximize efficiency, and to directly achieve strong existential unforgeability (also in the NPROM). This yields a slightly different construction and we use slightly different and additional properties of the lossy identification scheme.
Signatures with tight multi-user security against adaptive corruptions are a commonly-used standard building block for tightly-secure authenticated key exchange protocols. We also show how our construction improves the efficiency of all existing tightly-secure AKE protocols.
Alessandro Budroni, Igor Semaev
In this note, an LWE problem with a hidden trapdoor is introduced. It is used to construct an efficient public-key crypto-system EHT. The new system is significantly different from LWE based NIST candidates like FrodoKEM. The performance of EHT compares favorably with FrodoKEM.