International Association
for Cryptologic Research

A natural and recurring idea in the knapsack/lattice cryptography literature is to start from a lattice with remarkable decoding capability as your private key, and hide it somehow to make a public key. This is also how the code-based encryption scheme of McEliece (1978) proceeds.

This idea has never worked out very well for lattices: ad-hoc approaches have been proposed, but they have been subject to ad-hoc attacks, using tricks beyond lattice reduction algorithms. On the other hand the framework offered by the Short Integer Solution (SIS) and Learning With Errors (LWE) problems, while convenient and well founded, remains frustrating from a coding perspective: the underlying decoding algorithms are rather trivial, with poor decoding performance.

In this work, we provide generic realizations of this natural idea (independently of the chosen remarkable lattice) by basing cryptography on the lattice isomorphism problem (LIP). More specifically, we provide:

- a worst-case to average-case reduction for search-LIP and distinguish-LIP within an isomorphism class, by extending techniques of Haviv and Regev (SODA 2014). - a zero-knowledge proof of knowledge (ZKPoK) of an isomorphism. This implies an identification scheme based on search-LIP. - a key encapsulation mechanism (KEM) scheme and a hash-then-sign signature scheme, both based on distinguish-LIP.

The purpose of this approach is for remarkable lattices to improve the security and performance of lattice-based cryptography. For example, decoding within poly-logarithmic factor from Minkowski's bound in a remarkable lattice would lead to a KEM resisting lattice attacks down to poly-logarithmic approximation factor, provided that the dual lattice is also close to Minkowski's bound. Recent works have indeed reached such decoders for certain lattices (Chor-Rivest, Barnes-Sloan), but these do not perfectly fit our need as their duals have poor minimal distance.

By exploiting the inherent randomness used by certain digital signature protocols, subliminal channels can subvert these protocols without degrading their security. Due to their nature, these channels cannot be easily detected by an outside observer. Therefore, they pose a severe challenge for protocol designers. More precisely, designers consider certain assumptions implicitly, but in reality these assumptions turn out to be false or cannot be enforced or verified. In this paper we exemplify exactly such a situation by presenting several subliminal channels with a small capacity in Zhang et al. and Dong et al.'s subliminal-free signature protocols.

Two common variations of ECDSA signatures are additive key derivation and presignatures. Additive key derivation is a simple mechanism for deriving many subkeys from a single master key, and is already widely used in cryptocurrency applications with the Hierarchical Deterministic Wallet mechanism standardized in Bitcoin Improvement Proposal 32 (BIP32). Because of its linear nature, additive key derivation is also amenable to efficient implementation in the threshold setting. With presignatures, the secret and public nonces used in the ECDSA signing algorithm are precomputed. In the threshold setting, using presignatures along with other precomputed data allows for an extremely efficient ``online phase'' of the protocol. Recent works have advocated for both of these variations, sometimes combined together. However, somewhat surprisingly, we are aware of no prior security proofs of either of these variations in isolation, let alone in combination with one another.

In this paper, we provide a thorough analysis of these variations, both in isolation and in combination. Our analysis is in the generic group model (GGM). Importantly, we do not modify ECDSA or weaken the standard notion of security in any way. Of independent interest, we also present a version of the GGM that is specific to elliptic curves. This EC-GGM better models some of the idiosyncrasies (such as the conversion function and malleability) of ECDSA. In addition to this analysis, we report security weaknesses in these variations that apparently have not been previously reported. For example, we show that when both variations are combined, there is a cube-root attack on ECDSA, which is much faster than the best known, square-root attack on plain ECDSA. We also present two mitigations against these weaknesses: re-randomized presignatures and homogeneous key derivation. Each of these mitigations is very lightweight, and when used in combination, the security is essentially the same as that of plain ECDSA (in the EC-GGM).

Evaluating a block cipher’s strength against differential or linear cryptanalysis can be a difficult task. Several approaches for finding the best differential or linear trails in a cipher have been proposed, such as using mixed integer linear programming or SAT solvers. Recently a different approach was suggested, modelling the problem as a staged, acyclic graph and exploiting the large number of paths the graph contains. This paper follows up on the graph-based approach and models the prob- lem via compressed right-hand side equations. The graph we build contains paths which represent differential or linear trails in a cipher with few active S-boxes. Our method incorporates control over the memory usage, and the time complexity scales linearly with the number of rounds of the cipher being analysed. The proposed method is made available as a tool, and using it we are able to find differential trails for the Klein and Prince ciphers with higher probabilities than previously published.

The majority of recently demonstrated Deep-Learning Side-Channel Attacks (DLSCAs) use neural networks trained on a segment of traces containing operations only related to the target subkey. However, when the number of training traces are restricted such as in this paper only 5K power traces, deep-learning models always suffer from underfitting since the insufficient training data. One data-level solution is called data augmentation, which is to use the additional synthetically modified traces to act as a regularizer to provide a better generalization capacity for deep-learning models. In this paper, we propose a cross-subkey training approach which acts as a trace augmentation. We train deep-learning models not only on a segment of traces containing the SBox operation of the target subkey of AES-128, but also on segments for other 15 subkeys. Experimental results show that the accuracy of the subkey combination training model is 28.20% higher than that of the individual subkey training model on trajectories captured in the microcontroller implementation of the STM32F3 with AES-128. At the same time, the number of traces that need to be captured when the model is trained is greatly reduced, demonstrating the effectiveness and practicality of the method.

Most cryptography is based on assumptions such as factoring and discrete log, which assume an adversary has bounded computational power. With the recent development in quantum computing as well as concern with everlasting security, there is an interest in coming up with information-theoretic constructions in the bounded storage model. In this model, an adversary is computationally unbounded but has lim- ited space. Past works have constructed schemes such as key exchange and bit commitment in this model. In this work, we expand the function- alities further by building a semi-honest MPC protocol in the bounded storage model. We use the hardness of the parity learning problem (recently shown by Ran Raz (FOCS 16) without any cryptographic assump- tions) to prove the security of our construction, following the work by Guan and Zhandry (EUROCRYPT 19).

Implantable medical devices, sensors and wearables are widely deployed today. However, establishing a secure wireless communication channel to these devices is a major challenge, amongst others due to the constraints on energy consumption and the need to obtain immediate access in emergencies. To address this issue, researchers have proposed various key agreement protocols based on the measurement of physiological signals such as a person's heart signal. At the core of such protocols are fuzzy cryptographic primitives that allow to agree on a shared secret based on several simultaneous, noisy measurements of the same signal. So far, although many fuzzy primitives have been proposed, there is no comprehensive evaluation and comparison yet of the overhead that such methods incur on resource-constrained embedded devices. In this paper, we study the feasibility of six types of fuzzy cryptographic primitives on embedded devices for 128-bit key agreement. We configure several variants for each fuzzy primitive under different parameter selections and mismatch rates of the physiological signal measurements on an MSP430 microcontroller, and then measure and compare their energy consumption and communication overhead. The most efficient constructions consume between 0.021 mJ and 0.198 mJ for the transmitter and between 0.029 mJ and 0.380 mJ for the receiver under different mismatch rates. Subsequently, we modify the best performing methods so that they run in constant time to protect against timing side-channel attacks, and observe that these changes only minimally affect resource consumption. Finally, we provide open-source implementations and energy consumption data of each fuzzy primitive as a reference for real-world designs.

Decentralized multi-authority attribute-based encryption (????????-????????????) is a strengthening of standard ciphertext-policy attribute-based encryption so that there is no trusted central authority: any party can become an authority and there is no requirement for any global coordination other than the creation of an initial set of common reference parameters. Essentially, any party can act as an authority for some attribute by creating a public key of its own and issuing private keys to different users that reflect their attributes. This paper presents the first ????????-???????????? proven secure under the standard search variant of bilinear Diffie-Hellman (CBDH) and in the random oracle model. Our scheme supports all access policies captured by ????????1 circuits. All previous constructions were proven secure in the random oracle model and additionally were based on decision assumptions such as the DLIN assumption, non-standard ????-type assumptions, or subspace decision assumptions over composite-order bilinear groups.

In a lockable obfuscation scheme, a party called the obfuscator takes as input a circuit C, a lock value y and, a message m, and outputs an obfuscated circuit. Given the obfuscated circuit, an evaluator can run it on an input x and learn the message if C(x) = y. For security, we require that the obfuscation reveals no information on the circuit as long as the lock y has high entropy even given the circuit C.

The only known constructions of lockable obfuscation schemes require indistinguishability obfuscation (iO) or the learning with errors (LWE) assumption. Furthermore, in terms of technique, all known constructions, excluding iO-based, are build from provably secure variations of graph-induced multilinear maps.

We show a generic construction of a lockable obfuscation scheme build from a (leveled) fully homomorphic encryption scheme that is circularly insecure. Specifically, we need a fully homomorphic encryption scheme that is secure under chosen-plaintext attack (IND-CPA) but for which there is an efficient cycle tester that can detect encrypted key cycles. Our finding sheds new light on how to construct lockable obfuscation schemes and shows why cycle tester constructions were helpful in the design of lockable obfuscation schemes. One of the many use cases for lockable obfuscation schemes are constructions for IND-CPA secure but circularly insecure encryption schemes. Our work shows that there is a connection in both ways between circular insecure encryption and lockable obfuscation.

This paper investigates __anonymity__ of all NIST PQC Round~3 KEMs: Classic McEliece, Kyber, NTRU, Saber, BIKE, FrodoKEM, HQC, NTRU Prime (Streamlined NTRU Prime and NTRU LPRime), and SIKE. We show the following results:

* NTRU is anonymous in the quantum random oracle model (QROM) if the underlying deterministic PKE is strongly disjoint-simulatable. NTRU is collision-free in the QROM. A hybrid PKE scheme constructed from NTRU as KEM and appropriate DEM is anonymous and robust. Similar results hold for BIKE, FrodoKEM, HQC, NTRU LPRime, and SIKE.

* Classic McEliece is anonymous in the QROM if the underlying PKE is strongly disjoint-simulatable and a hybrid PKE scheme constructed from it as KEM and appropriate DEM is anonymous.

* Streamlined NTRU Prime has an obstacle for the IND-CCA security proof as Grubbs, Maram, and Paterson pointed out that Kyber and Saber has a gap in the current IND-CCA security proof (Cryptography ePrint Archive 2021/708).

Those answer the open problem to investigate the anonymity and robustness of NIST PQC Round~3 KEMs posed by Grubbs, Maram, and Paterson (Cryptography ePrint Archive 2021/708).

We use strong disjoint-simulatability of the underlying PKE of KEM and strong pseudorandomness and smoothness of KEMs, which will be of independent interest.

The SIDH key exchange is the main building block of SIKE, the only isogeny based scheme involved in the NIST standardization process. In 2016, Galbraith et al. presented an adaptive attack on SIDH. In this attack, a malicious party manipulates the torsion points in his public key in order to recover an honest party's static secret key, when having access to a key exchange oracle. In 2017, Petit designed a passive attack (which was improved by de Quehen et al. in 2020) that exploits the torsion point information available in SIDH public key to recover the secret isogeny when the endomorphism ring of the starting curve is known.

In this paper, firstly, we generalize the torsion point attacks by de Quehen et al. Secondly, we introduce a new adaptive attack vector on SIDH-type schemes. Our attack uses the access to a key exchange oracle to recover the action of the secret isogeny on larger subgroups. This leads to an unbalanced SIDH instance for which the secret isogeny can be recovered in polynomial time using the generalized torsion point attacks. Our attack is different from the GPST adaptive attack and constitutes a new cryptanalytic tool for isogeny based cryptography. This result proves that the torsion point attacks are relevant to SIDH parameters in an adaptive attack setting. We suggest attack parameters for some SIDH primes and discuss some countermeasures.

Fair data trading online is a challenging task when there is mistrust between data providers and data collectors. The trust issue leads to an unsolvable situation where the data collector is unwilling to pay until she receives the data while the data provider will not send the data unless she receives the payment. The traditional solutions toward fair data trading rely on the trust-third party. After the emergence of the blockchain, many researchers use a smart contract on blockchain as a trust-less third party to address the mistrust deadlock. However, involving a smart contract in the protocol inevitably exposes some information to the public if the smart contract is on public blockchain cryptocurrency systems. We observe that the existing fair data trading protocols do not take privacy into account, which, for instance, is critical when trading the sensitive data or the players simply do not want to leak any information about the tradings on the public blockchain. In this paper, we construct a fair trading protocol based on a smart contract that provides better privacy to the participants. We introduce new security notions for privacy-preserving blockchain-based fair data trading protocol and prove our protocol is secure under our new notions. Furthermore, we give a prototype implementation on Ethereum smart contract.

Event date: 25 July to 28 July 2022

Simula UiB (http://simula-uib.com) in Bergen, Norway, has a 4-year PhD position available in the field of cryptography. PhD students at Simula UiB enjoy an inclusive working environment with competitive salaries.

Job description

The PhD student we are looking for is eager to dive deeper into selected research topics in cryptography. The supervisor for this position is Chief Research Scientist Håvard Raddum, and the possible research areas of interest are: cryptanalysis of crypto primitives, fully homomorphic encryption with applications, or lattice-based cryptography. This list is not exhaustive, other topics will also be considered. The job consists of doing research on a daily basis, moving the research front on one or a few selected areas. Writing research papers and presenting them is an important part of the position. All research will be done with the aim of the student obtaining a PhD degree. The candidate will receive the PhD degree from the University of Bergen. 25% of the 4-year period is compulsory work related to the PhD student’s research area. Examples of compulsory work are teaching courses, outreach, applied research experiments, etc.

Closing date for applications:

Contact: Håvard Raddum - email: haavardr@simula.no. For administrative enquiries, contact bergen@simula.no.

More information: https://www.simula.no/about/job/call-phd-student-cryptography

Supersingular isogeny Diffie-Hellman (SIDH) is attractive for small public key size, but it is still unsatisfactory due to its efficiency, compared to other post-quantum proposals. In this paper, we focus on the performance of SIDH when the starting curve is $E_6:y^2=x^3+6x^2+x$, which is fixed in Round-3 SIKE implementation. We present several tricks to accelerate key generation of SIDH by precomputing few elements in the base field. We also point out that the main ideas of Costello et al. and Faz-Hern\'andez et al. to improve the ladder performance of SIDH, of which the starting curve is $E_0:y^2=x^3+x$, could be still utilized for the current SIDH protocol.

A recent work of Benhamouda and Lin (TCC~'20) identified a dream version of secure multiparty computation (MPC), termed **Multiparty reusable Non-Interactive Secure Computation** (MrNISC), that combines at the same time several fundamental aspects of secure computation with standard simulation security into one primitive: round-optimality, succinctness, concurrency, and adaptivity. In more detail, MrNISC is essentially a two-round MPC protocol where the first round of messages serves as a reusable commitment to the private inputs of participating parties. Using these commitments, any subset of parties can later compute any function of their choice on their respective inputs by broadcasting one message each. Anyone who sees these parties' commitments and evaluation messages (even an outside observer) can learn the function output and nothing else. Importantly, the input commitments can be computed without knowing anything about other participating parties (neither their identities nor their number) and they are reusable across any number of computations.

By now, there are several known MrNISC protocols from either (bilinear) group-based assumptions or from LWE. They all satisfy semi-malicious security (in the plain model) and require trusted setup assumptions in order to get malicious security. We are interested in maliciously secure MrNISC protocols **in the plain model, without trusted setup**. Since the standard notion of polynomial simulation is un-achievable in less than four rounds, we focus on MrNISC with **super-polynomial**-time simulation (SPS).

Our main result is the first maliciously secure SPS MrNISC in the plain model. The result is obtained by generically compiling any semi-malicious MrNISC and the security of our compiler relies on several well-founded assumptions, including an indistinguishability obfuscator and a time-lock puzzle (all of which need to be sub-exponentially hard). As a special case we also obtain the first 2-round maliciously secure SPS MPC based on well-founded assumptions. This MPC is also concurrently self-composable and its first message is short (i.e., its size is independent of the number of the participating parties) and reusable throughout any number of computations.

A ring signature is a signature scheme that provides the authenticity of a message anonymously. In this paper, we first present a post-quantum sigma protocol for a ring that relies on the supersingular isogeny-based interactive zero-knowledge identification scheme proposed by De Feo, Jao, and Plût in 2014. We prove the correctness, 2-special soundness, and honest-verifier zero-knowledge properties of the proposed protocol. Then, we construct a ring signature from the proposed sigma protocol for a ring by applying the Fiat-Shamir transform. In order to reduce the size of the exchanges, we use the Merkle tree and show that the signature size increases logarithmically in the size of the ring. The complexity analyses of the proposed protocols are also provided.

Use of game theory and mechanism design in cloud security is a well-studied topic. When applicable, it has the advantages of being efficient and simple compared to cryptography alone. Most analyses consider two-party settings, or multi-party settings where coalitions are not allowed. However, many cloud security problems that we face are in the multi-party setting and the involved parties can almost freely collaborate with each other. To formalize the study of disincentivizing coalitions from deviating strategies, a well-known definition named k-resiliency has been proposed by Abraham et al. (ACM PODC '06). Since its proposal, k-resiliency and related definitions are used extensively for mechanism design. However, in this work we observe the shortcoming of k-resiliency. That is, although it is secure, these definitions are too strict to use for many cases and rule out secure mechanisms as insecure. To overcome this, we propose a new definition named l-repellence against the presence of a single coalition to replace k-resiliency. Our definition incorporates transferable utility in game theory as it is realistic in many distributed and multi-party computing settings. We also propose m-stability definition against the presence of multiple coalitions, which is inspired by threshold security in cryptography. We then show the advantages of our novel definitions on three mechanisms, none of which were previously analyzed against coalitions: incentivized cloud computation, forwarding data packages in ad hoc networks, and connectivity in ad hoc networks. Regarding the former, our concepts improve the proposal by Küpçü (IEEE TDSC '17), by ensuring a coalition-proof mechanism.

Evaluating the side-channel resistance of a device in practice is a problematic and arduous process. Current certification schemes require to attack the device under test with an ever-growing number of techniques to validate its security. In addition, the success or failure of these techniques strongly depends on the individual implementing them, due to the fallible and human intrinsic nature of several steps of this path.

To alleviate this problem, we propose a battery of automated attacks as a side-channel analysis robustness assessment of an embedded device. To prove our approach, we conduct realistic experiments on two different devices, creating a new dataset (AES_RA) as a part of our contribution. Furthermore, we propose a novel way of performing these attacks using Principal Component Analysis, which also serves as an alternative way of selecting optimal principal components automatically. In addition, we perform a detailed analysis of automated attacks against masked AES implementations, comparing our method with the state-of-the-art approaches and proposing two novel initialization techniques to overcome its limitations in this scenario. We support our claims with experiments on AES_RA and a public dataset (ASCAD), showing how our, although fully automated, approach can straightforwardly provide state-of-the-art results.

In known constructions of classical zero-knowledge protocols for NP, either of zero-knowledge or soundness holds only against computationally bounded adversaries. Indeed, achieving both statistical zero-knowledge and statistical soundness at the same time with classical verifier is impossible for NP unless the polynomial-time hierarchy collapses, and it is also believed to be impossible even with a quantum verifier. In this work, we introduce a novel compromise, which we call the certified everlasting zero-knowledge proof for QMA. It is a computational zero-knowledge proof for QMA, but the verifier issues a classical certificate that shows that the verifier has deleted its quantum information. If the certificate is valid, even unbounded malicious verifier can no longer learn anything beyond the validity of the statement. We construct a certified everlasting zero-knowledge proof for QMA. For the construction, we introduce a new quantum cryptographic primitive, which we call commitment with statistical binding and certified everlasting hiding, where the hiding property becomes statistical once the receiver has issued a valid certificate that shows that the receiver has deleted the committed information. We construct commitment with statistical binding and certified everlasting hiding from quantum encryption with certified deletion by Broadbent and Islam [TCC 2020] (in a black box way), and then combine it with the quantum sigma-protocol for QMA by Broadbent and Grilo [FOCS 2020] to construct the certified everlasting zero-knowledge proof for QMA. Our constructions are secure in the quantum random oracle model. Commitment with statistical binding and certified everlasting hiding itself is of independent interest, and there will be many other useful applications beyond zero-knowledge.