International Association
for Cryptologic Research

The knapsack cryptography is the public-key cryptography whose security depends mainly on the hardness of the subset sum problem. Many of knapsack schemes were able to break by low-density attacks, which are attack methods to use the situation that a shortest vector or a closest vector in a lattice corresponds to a solution of the subset sum problem. For the case when the Hamming weight of a solution for a random instance of the subset sum problem is arbitrary, if the density is less than 0.9408, then the instance can be solvable almost surely by a single call of lattice oracle. This fact was theoretically shown by Coster et al.

In Crypto 2000, Okamoto, Tanaka and Uchiyama introduced the concept of quantum public key cryptosystems and proposed a knapsack cryptosystem, so-called OTU cryptosystem. However, no known algorithm breaks the OTU cryptosystem.

In this paper, we introduced Szemer\'{e}di-type assumptions, which are the imitations of the statement of Szemer\'{e}di's theorem on arithmetic progressions. From this mathematical point of view, we make clear what the average case and the worst case are. For low density attacks, we give better heuristics for orthogonal lattices than Gaussian heuristics. Consequently, we show that the OTU scheme can be broken under some heuristic assumptions.

Existing models for non-interactive MPC cannot provide full privacy for inputs, because they inherently leak the residual function (i.e., the output of the function on the honest parties’ input together with all possible values of the adversarial inputs). For example, in any non-interactive sealed-bid auction, the last bidder can figure out what was the highest previous bid.

We present a new MPC model which avoids this privacy leak. To achieve this, we utilize a blockchain in a novel way, incorporating smart contracts and arbitrary parties that can be incentivized to perform computation (“bounty hunters,” akin to miners). Security is maintained under a monetary assumption about the parties: an honest party can temporarily supply a recoverable collateral of value higher than the computational cost an adversary can expend.

We thus construct non-interactive MPC protocols with strong security guarantees (full security, no residual leakage) in the short term. Over time, as the adversary can invest more and more computational resources, the security guarantee decays. Thus, our model, which we call Gage MPC, is suitable for secure computation with limited-time secrecy, such as auctions.

A key ingredient in our protocols is a primitive we call “Gage Time Capsules” (GaTC): a time capsule that allows a party to commit to a value that others are able to reveal but only at a designated computational cost. A GaTC allows a party to commit to a value together with a monetary collateral. If the original party properly opens the GaTC, it can recover the collateral. Otherwise, the collateral is used to incentivize bounty hunters to open the GaTC. This primitive is used to ensure completion of Gage MPC protocols on the desired inputs.

As a requisite tool (of independent interest), we present a generalization of garbled circuit that are more robust: they can tolerate exposure of extra input labels. This is in contrast to Yao’s garbled circuits, whose secrecy breaks down if even a single extra label is exposed.

Finally, we present a proof-of-concept implementation of a special case of our construction, yielding an auction functionality over an Ethereum-like blockchain.

With the proposal of Picnic3, it has become interesting to investigate the security of LowMC with a full S-box layer. To significantly improve the efficiency of the Picnic signature, the designers of Picnic3 recommended to use the 4-round LowMC as the underlying block cipher, which has been shown to be insecure with 2 chosen plaintexts by Liu-Isobe-Meier. However, the attack scenario is very different and constrained in Picnic as the attacker is only allowed to know one single plaintext-ciphertext pair under the same key for LowMC. Recently, Banik et al. proposed guess-and-determine attacks on reduced LowMC in the Picnic setting. A major finding in their attacks is that the 3-bit S-box of LowMC can be linearized by guessing a quadratic equation. Notably, the attack on 2-round LowMC with a full S-box layer can be achieved with time complexity $2^{2m}$ where $m$ is the number of S-boxes in each round. As $k=3m$, their attacks can not reach 3 rounds where $k$ is the length of the key in bits. Although Banik et al. have improved the attacks with the meet-in-the-middle strategies, its memory complexity is rather high, which is $m\times 2^m$ bits of memory. In this note, we aim at low-memory key-recovery attacks as it is more fair to compare it with a pure exhaustive search. Specifically, we will describe improved algebraic attacks on 2-round LowMC by expressing the 3-bit S-box as 14 linearly independent quadratic boolean equations, which is inspired by the unsuccessful algebraic attacks on AES. As a result, the algebraic attacks on 2-round LowMC with key sizes of 129/192/255 bits can be improved by a factor of $2^{4}/2^{6.3}/2^{7.6}$, respectively. It seems that our attacks imply the attacks on 3-round LowMC. However, by taking the cost of gaussian elimination into account, the derived attacks on 3-round LowMC with key sizes of 192 and 255 bits are only about $2^{2.3}$ and $2^{3.7}$ times faster than the brute force.

A Sidon space is a subspace of an extension field over a base field in which the product of any two elements can be factored uniquely, up to constants. This paper proposes a new a public-key cryptosystem of the multivariate type which is based on Sidon spaces, and has the potential to remain secure even if quantum supremacy is attained. This system, whose security relies on the hardness of the well-known MinRank problem, is shown to be resilient to several straightforward algebraic attacks. In particular, it is proved that the two popular attacks on the MinRank problem, the kernel attack and the minor attack, succeed only with exponentially small probability. The system is implemented in software, and its hardness is demonstrated experimentally.

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.

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.

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.

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 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.

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, JoC’10). 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 (JoC’10), 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.

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.

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.

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.

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 &#937;(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.

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.

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.

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.

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.

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.

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.