International Association
for Cryptologic Research

Cleve’s celebrated lower bound (STOC’86) showed that a de facto strong fairness notion is impossible in 2-party coin toss, i.e., the corrupt party always has a strategy of biasing the honest party’s outcome by a noticeable amount. Nonetheless, Blum’s famous coin-tossing protocol(CRYPTO’81) achieves a strictly weaker “game-theoretic” notion of fairness — specifically, it is a 2-party coin toss protocol in which neither party can bias the outcome towards its own preference; and thus the honest protocol forms a Nash equilibrium in which neither party would want to deviate. Surprisingly, an n-party analog of Blum’s famous coin toss protocol was not studied till recently. The elegant work by Chung et al. was the first to explore the feasibility of game-theoretically fair n-party coin toss in the presence of corrupt majority. We may assume that each party has a publicly stated preference for either the bit 0 or 1, and if the outcome agrees with the party’s preference, it obtains utility 1; else it obtains nothing.A natural game-theoretic formulation is to require that the honest protocol form a coalition-resistant Nash equilibrium, i.e., no coalition should have incentive to deviate from the honest behavior. Chung et al. phrased this game-theoretic notion as “cooperative-strategy-proofness”or “CSP-fairness” for short. Unfortunately, Chung et al. showed that under (n−1)-sized coalitions, it is impossible to design such a CSP-fair coin toss protocol, unless all parties except one prefer the same bit.In this paper, we show that the impossibility of Chung et al. is in fact not as broad as it may seem. When coalitions are majority but not n−1 in size, we can indeed get feasibility results in some meaningful parameter regimes. We give a complete characterization of the regime in whichCSP-fair coin toss is possible, by providing a matching upper- and lower-bound. Our complete characterization theorem also shows that the mathematical structure of game-theoretic fairness is starkly different from the de facto strong fairness notion in the multi-party computation literature.

A dominant approach towards the solution of the scalability problem in blockchain systems has been the development of layer 2 protocols and specifically payment channel networks (PCNs) such as the Lightning Network (LN) over Bitcoin. Routing payments over LN requires the coordination of all path intermediaries in a multi-hop round trip that encumbers the layer 2 solution both in terms of responsiveness as well as privacy. The issue is resolved by “virtual channel” protocols that, capitalizing on a suitable setup operation, enable the two endpoints to engage as if they had a direct payment channel between them.

Apart from communication efficiency, virtual channel constructions have three natural desiderata. A virtual channel constructor is recursive if it can also be applied on pre-existing virtual channels, variadic if it can be applied on any number of pre-existing channels and symmetric if it encumbers in an egalitarian fashion all channel participants both in optimistic and pessimistic execution paths. We put forth the first Bitcoin-suitable recursive variadic virtual channel construction. Furthermore our virtual channel constructor is symmetric and offers optimal round complexity both in the optimistic and pessimistic execution paths. Our virtual channels can be implemented over Bitcoin assuming the ANYPREVOUT signature type, a feature that we prove necessary for any efficient protocol that has parties maintain a set of Bitcoin transactions in their local state. We express and prove the security of our construction in the universal composition setting.

Field Programmable Gate Arrays (FPGAs) used as hardware accelerators in the cloud domain allow end-users to accelerate their custom applications while ensuring minimal dynamic power consumption. Cloud infrastructures aim to maximize profit by achieving optimized resource sharing among its cloud users. However, the FPGAs' reconfigurable nature poses unique security and privacy challenges in a shared cloud environment. In this paper, we aim to understand the interactions between FPGA and the host servers on the cloud to analyze FaaS platforms' security. We propose a vulnerability taxonomy based on the runtime attributes of the FaaS platforms. The taxonomy aims to assist the identification of critical sources of vulnerabilities in the platform in allowing focused security verification. We demonstrate the proof-of-concept by characterizing the potential source of vulnerabilities in the Stratix-10 FaaS platforms. We then focused on only one major source to perform more focused verification. The proof-of-concept is demonstrated by identifying the potential source of vulnerabilities in the Stratix-10 FaaS platforms. Then, to conduct more focused verification, we narrowed our focus to only one major source. It aided in the identification of several low-level software vulnerabilities. The discovered vulnerabilities could be remotely exploited to cause denial-of-service and information leakage attacks. The concerned entities have released software updates to address the vulnerabilities.

Following the pioneering work of Boneh and Franklin (CRYPTO '01), the challenge of constructing an identity-based encryption scheme based on the Diffie-Hellman assumption remained unresolved for more than 15 years. Evidence supporting this lack of success was provided by Papakonstantinou, Rackoff and Vahlis (ePrint '12), who ruled out the existence of generic-group identity-based encryption schemes supporting an identity space of sufficiently large polynomial size. Nevertheless, the breakthrough result of D{\"{o}}ttling and Garg (CRYPTO '17) settled this long-standing challenge via a non-generic construction.

We prove a tight impossibility result for generic-group identity-based encryption, ruling out the existence of any non-trivial construction: We show that any scheme whose public parameters include $n_{\sf pp}$ group elements may support at most $n_{\sf pp}$ identities. This threshold is trivially met by any generic-group public-key encryption scheme whose public keys consist of a single group element (e.g., ElGamal encryption).

In the context of algebraic constructions, generic realizations are often both conceptually simpler and more efficient than non-generic ones. Thus, identifying exact thresholds for the limitations of generic groups is not only of theoretical significance but may in fact have practical implications when considering concrete security parameters.

In this paper, we introduce a new method to prove the knowledge of an isogeny of given degree between two supersingular elliptic curves. Our approach can be extended to verify the evaluation of the secret isogeny on some points of the domain. The main advantage of this new proof of knowledge is its compactness which is orders of magnitude better than existing proofs of isogeny knowledge. The principle of our method is to reveal some well-chosen endomorphisms and does not constitute a zero-knowledge proof. However, when the degree is a large prime, we can introduce a new hardness assumption upon which we build the first verifiable random function (VRF) based on isogenies. Our protocol can be seen as a generalization of the BLS-style classical construction from elliptic curves and achieves one-time pseudo-randomness in the random oracle model. We propose concrete parameters for this new scheme which reach post-quantum NIST-1 level of security. Our VRF has an overall cost (proof size, key size and output size) of roughly $1$KB, which is shorter than all the other post-quantum instantiations based on lattices. In the process, we also develop several algorithmic tools to solve norm equations over quaternion orders that may be of independent interest.

We propose Manta, a plug and play private DeFi stack that consists of MantaDAP, a multi-asset decentralized anonymous payment scheme and MantaDAX, an automated market maker(AMM) based decentralized anonymous exchange scheme. Compared with existing privacy preserving cryptocurrencies such as Zcash and Monero,Manta supports multiple base assets and allows the privatized assets to be exchanged anonymously via MantaDAX. We think this is a major step forward towards building a privacy preserving DeFi stack. Thanks to the efficiency of modern NIZKs (non-interactive zero-knowledge proof systems) and our carefully crafted design,Manta is efficient: our benchmarks reports a 15 second, off-line zero-knowledge proof (ZKP) generation time, and a 6 millisecond, on-line proof verification time.

Proof-of-Stake (PoS) distributed ledgers are the most common alternative to Bitcoin’s Proof-of-Work (PoW) paradigm, replacing the hardware dependency with stake, i.e., assets that a party controls. Similar to PoW’s mining pools, PoS’s stake pools, i.e., collaborative entities comprising of multiple stakeholders, allow a party to earn rewards more regularly, compared to participating on an individual basis. However, stake pools tend to increase centralization, since they are typically managed by a single party that acts on behalf of the pool’s members. In this work we propose Conclave, a formal design of a Collective Stake Pool, i.e., a decentralized pool with no single point of authority. We formalize Conclave as an ideal functionality and implement it as a distributed protocol, based on standard cryptographic primitives. Among Conclave’s building blocks is a weighted threshold signature scheme (WTSS); to that end, we define a WTSS ideal functionality — which might be of independent interest — and propose two constructions based on threshold ECDSA, which enable (1) fast trustless setup and (2) identifiable aborts.

This short note shows that NTRU in NIST PQC Round~3 finalist is anonymous in the QROM if the underlying NTRU PKE is strongly disjoint-simulatable and a hybrid PKE scheme constructed from NTRU as KEM and appropriate DEM is anonymous and robust.

This solves the the open problem to investigate anonymity and robustness of NTRU posed by Grubbs, Maram, and Paterson (Cryptography ePrint Archive 2021/708).}

The Boneh-Katz transformation (CT-RSA 2005) converts a selectively-secure identity/tag-based encryption scheme into a public-key encryption scheme secure against chosen-ciphertext attacks. We show that if the underlying primitives are pseudorandom, then the public-key encryption scheme obtained by the Boneh-Katz transformation is also pseudorandom. A similar result holds for oblivious sampleability (Canetti and Fischlin (CRYPTO 2001)).

As applications, we can construct

* pseudorandom and obliviously-samplable public-key encryption schemes from lattices and codes,

* universally-composable non-interactive bit-commitment from lattices,

* public-key steganography which is steganographically secure against adaptive chosen-covertext attacks and steganographic key-exchange from lattices and codes,

* anonymous authenticated key exchange from lattices and codes,

* public-key encryption secure against simulation-based, selective-opening chosen-ciphertext attacks from lattices and codes.

Garbled circuits are a fundamental cryptographic building block to encode Boolean circuits as a sequence of encrypted values. This sequence allows two parties to securely evaluate the circuit, e.g., without revealing their respective inputs. At the heart of any garbling scheme lies a randomized algorithm projecting the plain values into a larger domain. Emerging from a large body of work, the common paradigm meets two implicit properties: the circuit is garbled progressively gate-wise; and all underlying algorithms are linear. In this setting, the communication complexity is measured in the number of sent ciphertexts and shown to be optimal with a scheme sending two ciphertexts per AND gate and no ciphertexts per XOR gate (Zahur, Rosulek and Evans, Eurocrypt'15).

We revisit the common paradigm and extend the seminal work of Bellare, Hoang, and Rogaway from CCS 2012 to present for the first time an abstraction of the garbling algorithm itself. This abstraction highlights how Yao's work (Yao, FOCS'86) and all its optimizations focused on improving just one aspect of the garbling. We then discuss how improving the other aspects could provide new ways to overcome the limitations of existing schemes. As a proof of concept we present a non-bijective scheme avoiding Zahur et al.'s bound, achieving a communication complexity of a single data item which is not a ciphertext.

The existence of one-way functions implies secure digital signatures, but not public-key encryption (at least in a black-box setting). Somewhat surprisingly, though, efficient public-key encryption schemes appear to be much easier to construct from concrete algebraic assumptions (such as the factoring of Diffie-Hellman-like assumptions) than efficient digital signature schemes. In this work, we provide one reason for this apparent difficulty to construct efficient signature schemes.

Specifically, we prove that a wide range of algebraic signature schemes (in which verification essentially checks a number of linear equations over a group) fall to conceptually surprisingly simple linear algebra attacks. In fact, we prove that in an algebraic signature scheme, sufficiently many signatures can be linearly combined to a signature of a fresh message. We present attacks both in known-order and hidden-order groups (although in hidden-order settings, we have to restrict our definition of algebraic signatures a little). More explicitly, we show: - the insecurity of all signature schemes in Maurer's generic group model (in pairing-free groups), as long as the signature schemes do not rely on other cryptographic assumptions, such as hash functions. - the insecurity of a natural class of signatures in hidden-order groups, where verification consists of linear equations over group elements.

We believe that this highlights the crucial role of public verifiability in digital signature schemes. Namely, while public-key encryption schemes do not require any publicly verifiable structure on ciphertexts, it is exactly this structure on signatures that invites attacks like ours and makes it hard to construct efficient signatures.

GIFT-COFB is a finalist of NIST Lightweight cryptography project that aims at standardizing authenticated encryption schemes for constrained devices. It is a block cipher-based scheme and comes with a provable security result. This paper studies the tightness of the provable security bounds of GIFT-COFB, which roughly tells that, if instantiated by a secure $n$-bit block cipher, we need $2^{n/2}$ encrypted blocks or $2^{n/2}/n$ decryption queries to break the scheme. This paper shows that the former condition is indeed tight, by presenting forgery attacks that work with $2^{n/2}$ encrypted blocks with single decryption query. This fills the missing spot of previous attacks presented by Khairallah, and confirms the tightness of the security bounds with respect to encryption. We remark that our attacks work independent of the underlying block cipher.

Machine Learning (ML) algorithms, especially deep neural networks (DNN), have proven themselves to be extremely useful tools for data analysis, and are increasingly being deployed in systems operating on sensitive data, such as recommendation systems, banking fraud detection, and healthcare systems. This underscores the need for privacy-preserving ML (PPML) systems, and has inspired a line of research into how such systems can be constructed efficiently. We contribute to this line of research by proposing a framework that allows efficient and secure evaluation of full-fledged state-of-the-art ML algorithms via secure multi-party computation (MPC). This is in contrast to most prior works on PPML, which require advanced ML algorithms to be substituted with approximated variants that are ``MPC-friendly'', before MPC techniques are applied to obtain a PPML algorithm. A drawback of the latter approach is that it requires careful fine-tuning of the combined ML and MPC algorithms, and might lead to less efficient algorithms or inferior quality ML (such as lower prediction accuracy). This is an issue for secure training of DNNs in particular, as this involves several arithmetic algorithms that are thought to be ``MPC-unfriendly'', namely, integer division, exponentiation, inversion, and square root extraction.

In this work, we propose secure and efficient protocols for the above seemingly MPC-unfriendly computations (but which are essential to DNN). Our protocols are three-party protocols in the honest-majority setting, and we propose both passively secure and actively secure with abort variants. A notable feature of our protocols is that they simultaneously provide high accuracy and efficiency. This framework enables us to efficiently and securely compute modern ML algorithms such as Adam (Adaptive moment estimation) and the softmax function ``as is'', without resorting to approximations. As a result, we obtain secure DNN training that outperforms state-of-the-art three-party systems; our \textit{full} training is up to $6.7$ times faster than just the \textit{online} phase of the recently proposed FALCON (Wagh et al. at PETS'21) on the standard benchmark network for secure training of DNNs. To further demonstrate the scalability of our protocols, we perform measurements on real-world DNNs, AlexNet and VGG16, which are complex networks containing millions of parameters. The performance of our framework for these networks is up to a factor of about $12\sim 14$ faster for AlexNet and $46\sim 48$ faster for VGG16 to achieve an accuracy of $70\%$ and $75\%$, respectively, when compared to FALCON.

We study masking countermeasures for side-channel attacks against signature schemes constructed from the MPC-in-the-head paradigm, specifically when the MPC protocol uses preprocessing. This class of signature schemes includes Picnic, an alternate candidate in the third round of the NIST post-quantum standardization project. The only previously known approach to masking MPC-in-the-head signatures suffers from interoperability issues and increased signature sizes. Further, we present a new attack to demonstrate that known countermeasures are not sufficient when the MPC protocol uses a preprocessing phase, as in Picnic3.

We overcome these challenges by showing how to mask the underlying zero-knowledge proof system due to Katz–Kolesnikov–Wang (CCS 2018) for any masking order, and by formally proving that our approach meets the standard security notions of non-interference for masking countermeasures. As a case study, we apply our masking technique to Picnic. We then implement different masked versions of Picnic signing providing first order protection for the ARM Cortex M4 platform, and quantify the overhead of these different masking approaches. We carefully analyze the side-channel risk of hashing operations, and give optimizations that reduce the CPU cost of protecting hashing in Picnic by a factor of five. The performance penalties of the masking countermeasures ranged from 1.8 to 5.5, depending on the degree of masking applied to hash function invocations.

We provide three first-order sharings of the AES each allowing for a different trade-off between the number of shares and the number of register stages. All sharings use a generalization of the changing of the guards method by allowing randomness to be used in the shared S-box. As a result, the sharings have minimal randomness requirements. The sharings are written out in detail to ease implementation efforts.

We present a framework GenoPPML for privacy-preserving machine learning in the context of sensitive genomic data processing. The technology combines secure multiparty computation techniques based on the recently proposed Manticore secure multiparty computation framework for model training and fully homomorphic encryption based on TFHE for model inference. The framework was successfully used to solve breast cancer prediction problems on gene expression datasets coming from distinct private sources while preserving their privacy – the solution winning 1st place for both Tracks I and III of the genomic privacy competition iDASH'2020.

In this paper, we present preimage attacks on 4-round Keccak-224/256 as well as 4-round Keccak[$r = 640,c = 160,l = 80$] in the preimage challenges. We revisit the Crossbred algorithm for solving the Boolean multivariate quadratic (MQ) system, propose a new view for the case $D = 2$ and elaborate the computational complexity. The result shows that the Crossbred algorithm outperforms brute force theoretically and practically with feasible memory costs. In our attacks, we construct Boolean MQ systems in order to make full use of variables. With the help of solving MQ systems, we successfully improve preimage attacks on Keccak-224/256 reduced to 4 rounds. Moreover, we implement the preimage attack on 4-round Keccak[$r = 640,c = 160,l = 80$], an instance in the Keccak preimage challenges, and find 78-bit matched \textit{near preimages}. Due to the fundamental rule of solving MQ systems, the complexity elaboration of Crossbred algorithm is of independent interest.

The idea of hybrid homomorphic encryption (HHE) is to drastically reduce bandwidth requirements when using homomorphic encryption (HE) at the cost of more expensive computations in the encrypted domain. To this end, various dedicated schemes for symmetric encryption have already been proposed. However it is still unclear if those ideas are already practically useful, because (1) no cost-benefit analysis was done for use cases and (2) very few implementations are publicly available. We address this situation in several ways. After we formally define HHE in a broader sense than before, we build an open-source benchmarking framework involving several use cases covering three popular libraries. Using this framework, we explore properties of the respective HHE proposals. It turns out that even medium-sized use cases are infeasible, especially when involving integer arithmetic. Consequently, we propose Pasta, a cipher thoroughly optimized for integer HHE use cases. Pasta is designed to minimize the multiplicative depth, while also leveraging the structure of both state-of-the-art integer HE schemes (BFV and BGV) to minimize the homomorphic evaluation latency. Using our new benchmarking environment, we extensively evaluate Pasta in SEAL and HElib and compare its properties to 7 existing ciphers in two use cases. Our evaluations show that Pasta outperforms its competitors for HHE both in terms of homomorphic evaluation time and noise consumption, showing its efficiency for applications in real-world HE use cases. Concretely, Pasta outperforms Agrasta by a factor of up to 82 and Masta by a factor of up to 6 when applied to the two use cases.

Event date: 29 September to 1 October 2021
Submission deadline: 30 June 2021

We are seeking a Postdoctoral Researcher to join us in our project to ensure reliable and trustworthy power grid operation. In this project, we will approach the security challenges from three angles; secure energy transactions, secure decentralized storage for collaboration, and secure end-to-end communication for resource monitoring and control.

Your Responsibilities

• Conduct research on provable data possession and secure collaborative storage.
• Develop and improve upon techniques to provide Completeness, Correctness, and Freshness guarantees on stored data in collaborative applications.
• Implement the developed solutions

Basic Requirements

• PhD in Cryptography, Applied Cryptography, Information Theory, Mathematics, Computer Science or related areas.
• Excellent track record in reputable Cryptography and Security venues.
• Ability to perform research independently.
• Good communication skills and ability to collaborate with a team of researchers and engineers.
• Experience or interest in software prototyping.

Nice to Have

• Experience in data/message integrity research, such as Provable Data Possession, Proof of Data Retrievability.
• Familiar with or interested in Cloud and IoT concepts, DER and Grid 2.0 paradigm.

For more information, please visit ADSC's website: http://adsc.illinois.edu/.

Closing date for applications:

Contact: Interested candidates should apply online at https://my.engr.illinois.edu/apply/.