International Association
for Cryptologic Research

This is a joint project between Simula@UiB and NTNU and others, funded by the Research Council of Norway. The main objective of this project is to develop cryptographic protocols and primitives that realize trusted and secure communication in an IoT ecosystem.

We are entering the era of the Internet of Things (IoT). The IoT connects not only classical computing and communication devices, but all kinds of other gadgets that we use in our everyday lives. For IoT, security concerns go beyond traditional privacy or denial of service; also the immediate physical security of humans is at stake, and the cost of security failures becomes much more severe. Moreover, the IoT will be comprised of heterogeneous and lightweight devices, many of which may be unable to perform the complex computations required by modern security protocols.

The constrained IoT environment poses novel challenges for cryptographic protocol design and analysis. The PhD fellow will study protocols implementing either traditional trusted third party trust mechanism and/or newer (but less well-understood) notions of distributed trust. In both cases the protocols will rely on quantum-safe primitives. Of particular interest is the construction of security proofs for such light-weight protocols, requiring tight proofs as well as high assurance (e.g. automatic verification of security proofs).

Closing date for applications: 18 June 2018

Contact: Professor Kristian Gjøsteen (kristian.gjosteen (at) ntnu.no)

More information: https://www.jobbnorge.no/ledige-stillinger/stilling/153293/

The positions are connected to the project «Secure, Usable and Robust Cryptographic Voting Systems». This is a joint project between NTNU and the University of Luxembourg, funded by the Research Council of Norway and the Luxembourg National Research Fund. The goal of the project is to study the security of cryptographic voting schemes.

Traditional voting has some significant limitations. From a security viewpoint, it has relied heavily on trust in the election officials, which in turn restricts independent verifiability and high assurance regarding confidentiality of votes. In addition, traditional voting has problems regarding errors in counting, accessibility, and timeliness.

Although cryptographic voting systems have been proposed almost 30 years ago, and deployed in many countries more recently, there remain major obstacles to their widespread adoption. As we have seen in recent years, voting systems sometimes fail and they are susceptible to a range of attacks, even in established democracies.

This project will investigate the security of voting systems and increase our assurance in state-of-the-art voting systems. In particular, the project will study user confidence in cryptographic voting systems, security proofs for such systems, as well as options for long-term security (including post-quantum security).

Security proofs will be a particular focus for one PhD fellow, while long-term security will be a particular focus for the other PhD fellow.

Closing date for applications: 18 June 2018

Contact: Professor Kristian Gjøsteen (kristian.gjosteen (at) ntnu.no), or Professor Colin Boyd (colin.boyd (at) ntnu.no).

More information: https://www.jobbnorge.no/ledige-stillinger/stilling/153300/

The position is connected to the project «Secure, Usable and Robust Cryptographic Voting Systems». This is a joint project between NTNU and the University of Luxembourg, funded by the Research Council of Norway and the Luxembourg National Research Fund. The goal of the project is to study the security of cryptographic voting schemes.

Traditional voting has some significant limitations. From a security viewpoint, it has relied heavily on trust in the election officials, which in turn restricts independent verifiability and high assurance regarding confidentiality of votes. In addition, traditional voting has problems regarding errors in counting, accessibility, and timeliness.

Although cryptographic voting systems have been proposed almost 30 years ago, and deployed in many countries more recently, there remain major obstacles to their widespread adoption. As we have seen in recent years, voting systems sometimes fail and they are susceptible to a range of attacks, even in established democracies.

This project will investigate the security of voting systems and increase our assurance in state-of-the-art voting systems. In particular, the project will study user confidence in cryptographic voting systems, security proofs for such systems, as well as options for long-term security (including post-quantum security).

Closing date for applications: 18 June 2018

Contact: Professor Kristian Gjøsteen (kristian.gjosteen (at) ntnu.no) or Professor Colin Boyd (colin.boyd (at) ntnu.no).

More information: https://www.jobbnorge.no/ledige-stillinger/stilling/153320/

Surrey Centre for Cyber Security (SCCS) and Surrey Space Centre (SSC) at the University of Surrey invite applications for a fully-funded PhD position in Satellite System Security to work on an industry-funded research project TargetSat: Security of COTS-based Satellite Systems.

The project is funded by the NCC Group and aims to develop understanding of security risks and requirements associated with the use of commercial off-the-shelf components (incl. operating systems and software) in satellites and ground control systems, identify weaknesses and vulnerabilities in existing single and multi-satellite architectures and communication protocols, and propose mitigating countermeasures. An appropriate test-bed facility will be developed as part of this project.

Successful applicants are expected to be familiar with:

• Linux-based OS systems, incl. kernel programming

• System- / network-level attacks (e.g. buffer overflows, command injection), penetration testing

• Programming languages: C/C++, Assembly, or Python

We particularly welcome applications from ongoing students who are projected to complete their degree in 2018.

This PhD studentship includes a tax-free PhD stipend of GBP 20,000 per year for 3.5 years of PhD studies. This stipend is significantly higher than an average PhD stipend in the UK. Additional funding is available to support conference travel, etc.

Closing and starting dates: This is a “rolling advert” with a nominal closing date. Applications are welcome at any time and the timing of the selection process will be dependent on the applications received. Planned start date is October 2018.

Applications should be sent via https://jobs.surrey.ac.uk/Vacancy.aspx?id=4966

Closing date for applications: 30 September 2018

Contact: Informal inquiries can be directed to Dr Mark Manulis (m.manulis (at) surrey.ac.uk)

More information: https://jobs.surrey.ac.uk/Vacancy.aspx?id=4966

Funded Ph.D. Student Positions in Hardware Security and Reliability, VLSI Testing and VLSI

Ph.D. student positions are available (start date: Fall 2018) in the field of hardware security, reliability, VLSI Testing and VLSI in the CSEE Department of University of Maryland, Baltimore County.

UMBC is ranked 55 in Computer Engineering according to US News, and places 7th in the ranking of Most Innovative national universities.

Our group has a strong background in hardware security, reliability, and trust, and in particular in side-channel analysis and fault analysis attacks, IC Counterfeiting, Trojan detection, IP/IC protection, Physically Unclonable Functions (PUFs) and Crypto devices as well as testing and reliability of secure devices and VLSI.

Requirements:

- M.Sc./B.Sc. in Computer Engineering or Electrical Engineering

- Solid knowledge in Hardware Description Languages (HDL)

- Solid Knowledge in digital design

Please contact me with your CV and Statement of Purpose by June 30th.

Naghmeh Karimi, Assistant Professor

Department of Computer Science and Electrical Engineering

University of Maryland, Baltimore County

Baltimore, MD 21250

Web: http://www.csee.umbc.edu/~nkarimi/

Closing Date for Applications: 2018-06-30

Closing date for applications: 30 June 2018

Contact: Naghmeh Karimi, Ph.D.

E-mail: nkarimi (at) umbc.edu

The Elliptic Curve Digital Signature Algorithm (ECDSA) is one of the most widely used schemes in deployed cryptography. Through its applications in code and binary authentication, web security, and cryptocurrency, it is likely one of the few cryptographic algorithms encountered on a daily basis by the average person. However, its design is such that executing multi-party or threshold signatures in a secure manner is challenging: unlike other, less widespread signature schemes, secure multi-party ECDSA requires custom protocols, which has heretofore implied reliance upon additional cryptographic assumptions and primitives such as the Paillier cryptosystem.

We propose new protocols for multi-party ECDSA key-generation and signing with a threshold of two, which we prove secure against malicious adversaries in the random oracle model using only the Computational Diffie-Hellman Assumption and the assumptions already relied upon by ECDSA itself. Our scheme requires only two messages, and via implementation we find that it outperforms the best prior results in practice by a factor of 56 for key generation and 11 for signing, coming to within a factor of 18 of local signatures. Concretely, two parties can jointly sign a message in just over three milliseconds.

One important open question in the field of side-channel analysis is to find out whether all the leakage samples in an implementation can be exploited by an adversary, as suggested by masking security proofs. For concrete attacks exploiting a divide-and-conquer strategy, the answer is negative (i.e., only the leakages corresponding to the first/last rounds of a block cipher can be exploited). Soft Analytical Side-Channel Attacks (SASCA) have been introduced as a powerful solution to mitigate this limitation. They represent the target implementation and its leakages as a code (similar to a Low Density Parity Check code) that is then decoded thanks to belief propagation. Previous works have shown the low data complexities that SASCA can reach in practice (at the cost of a higher time complexity). In this work, we revisit these attacks by modeling them with a variation of the Random Probing Model used in masking security proofs, that we denote as the Local Random Probing Model (LRPM). Our study establishes interesting connections between this model and the erasure channel used in coding theory, leading to the following benefits. First, the LRPM allows assessing the security of concrete implementations against SASCA in a fast and intuitive manner. We use it to confirm that the leakage of any operation in a block cipher can be exploited, although the leakages of external operations dominate in known-plaintext/ciphertext attack scenarios. Second, we show that the LRPM is a tool of choice for the (nearly worst-case) analysis of masked implementations in the noisy leakage model, taking advantage of all the operations performed, and leading to new possibilities of tradeoffs between their amount of randomness and physical noise level.

Recently, several practical attacks raised serious concerns over the security of searchable encryption. The attacks have brought emphasis on forward privacy, which is the key concept behind solutions to the adaptive leakage-exploiting attacks, and will very likely to become a must-have property of all new searchable encryption schemes. For a long time, forward privacy implies inefficiency and thus most existing searchable encryption schemes do not support it. Very recently, Bost (CCS 2016) showed that forward privacy can be obtained without inducing a large communication overhead. However, Bost’s scheme is constructed with a relatively inefficient public key cryptographic primitive, and has poor I/O performance. Both of the deficiencies significantly hinder the practical efficiency of the scheme, and prevent it from scaling to large data settings. To address the problems, we first present FAST, which achieves forward privacy and the same communication efficiency as Bost’s scheme, but uses only symmetric cryptographic primitives. We then present FASTIO, which retains all good properties of FAST, and further improves I/O efficiency. We implemented the two schemes and compared their performance with Bost’s scheme. The experiment results show that both our schemes are highly efficient.

Private set intersection (PSI) is an essential cryptographic protocol that has many real world applications. As cloud computing power and popularity have been swiftly growing, it is now desirable to leverage the cloud to store private datasets and delegate PSI computation to it. Although a set of efficient PSI protocols have been designed, none support outsourcing of the datasets and the computation. In this paper, we propose two protocols for delegated PSI computation on outsourced private datasets. Our protocols have a unique combination of properties that make them particularly appealing for a cloud computing setting. Our first protocol, O-PSI, satisfies these properties by using additive homomorphic encryption and point-value polynomial representation of a set. Our second protocol, EO-PSI, is mainly based on a hash table and point-value polynomial representation and it does not require public key encryption; meanwhile, it retains all the desirable properties and is much more efficient than the first one. We also provide a formal security analysis of the two protocols in the semi-honest model and we analyze their performance utilizing prototype implementations we have developed. Our performance analysis shows that EO-PSI scales well and is also more efficient than similar state-of-the-art protocols for large set sizes.

The computation of private set union/intersection cardinality (PSU-CA/PSI-CA) is one of the most intensively studied problems in Privacy Preserving Data Mining (PPDM). However, existing protocols are computationally too expensive to be employed in real-world PPDM applications. In response, we propose efficient approximate protocols, whose accuracy can be tuned according to application requirements. We first propose a two-party PSU-CA protocol based on Flajolet-Martin sketches. The protocol has logarithmic computational/communication complexity and relies mostly on symmetric key operations. Thus, it is much more efficient and scalable than existing protocols. In addition, our protocol can hide its output. This feature is necessary in PPDM applications, since the union cardinality is often an intermediate result that must not be disclosed. We then propose a two-party PSI-CA protocol, which is derived from the PSU-CA protocol with virtually no cost. Both our two-party protocols can be easily extended to the multiparty setting. We also design an efficient masking scheme for (1,n)-OT. The scheme is used in optimizing the two-party protocols and is of independent interest, since it can speed up (1,n)-OT significantly when n is large. Last, we show through experiments the effectiveness and efficiency of our protocols.

The Ring Learning with Errors problem (RLWE) introduced by Lyubashevsky, Peikert and Regev (LPR, Eurocrypt 2010, Eurocrypt 2013) quickly became a central element in cryptographic literature and a foundation to numerous cryptosystems. RLWE is an average case problem whose hardness is provably related to the worst case hardness of ideal lattice problems. However, in many cases optimizations and other considerations necessitate generating RLWE instances from distributions for which the worst case reduction does not apply, thus leaving the resulting cryptosystem secure only by heuristic reasons.

The focus of this work is RLWE with non-uniform distribution on secrets. A legal RLWE secret is (roughly) a uniform element in the ring of integers of a number field, modulo an integer $q$. We consider two main classes of "illegal" distributions of secrets.

The first is sampling from a subring of the intended domain. We show that this translates to a generalized form of RLWE that we call Order-LWE, we provide worst case hardness results for this new problem, and map out regimes where it is secure and where it is insecure. Two interesting corollaries are a (generalization of) the known hardness of RLWE with secrets sampled from the ring of integers of a subfield, and a new hardness results for the Polynomial-LWE (PLWE) problem, with different parameters than previously known.

The second is sampling from a $k$-wise independent distribution over the CRT representation of the secret. We cannot show worst case hardness in this case, but instead present a single average case problem (specifically, bounded distance decoding on a fixed specific distribution over lattices) whose hardness implies the hardness of RLWE for all such distributions of secrets.

Extensive efforts are currently put into securing messaging platforms, where a key challenge is that of protecting against man-in-the-middle attacks when setting up secure end-to-end channels. The vast majority of these efforts, however, have so far focused on securing user-to-user messaging, and recent attacks indicate that the security of group messaging is still quite fragile.

We initiate the study of out-of-band authentication in the group setting, extending the user-to-user setting where messaging platforms (e.g., Telegram and WhatsApp) protect against man-in-the-middle attacks by assuming that users have access to an external channel for authenticating one short value (e.g., two users who recognize each other's voice can compare a short value). Inspired by the frameworks of Vaudenay (CRYPTO '05) and Naor et al. (CRYPTO '06) in the user-to-user setting, we assume that users communicate over a completely-insecure channel, and that a group administrator can out-of-band authenticate one short message to all users. An adversary may read, remove, or delay this message (for all or for some of the users), but cannot undetectably modify it.

Within our framework we establish tight bounds on the tradeoff between the adversary's success probability and the length of the out-of-band authenticated message (which is a crucial bottleneck given that the out-of-band channel is of low bandwidth). We consider both computationally-secure and statistically-secure protocols, and for each flavor of security we construct an authentication protocol and prove a lower bound showing that our protocol achieves essentially the best possible tradeoff.

In particular, considering groups that consist of an administrator and $k$ additional users, for statistically-secure protocols we show that at least $(k+1)\cdot (\log(1/\epsilon) - \Theta(1))$ bits must be out-of-band authenticated, whereas for computationally-secure ones $\log(1/\epsilon) + \log k$ bits suffice, where $\epsilon$ is the adversary's success probability. Moreover, instantiating our computationally-secure protocol in the random-oracle model yields an efficient and practically-relevant protocol (which, alternatively, can also be based on any one-way function in the standard model).

At CRYPTO 2017, Belaïd et al. presented two new private multiplication algorithms over finite fields, to be used in secure masking schemes. To date, these algorithms have the lowest known complexity in terms of bilinear multiplication and random masks respectively, both being linear in the number of shares $d+1$. Yet, a practical drawback of both algorithms is that their safe instantiation relies on finding matrices satisfying certain conditions. In their work, Belaïd et al. only address these up to $d=2$ and 3 for the first and second algorithm respectively, limiting so far the practical usefulness of their constructions.

In this paper, we use in turn an algebraic, heuristic, and experimental approach to find many more safe instances of Belaïd et al.'s algorithms. This results in explicit instantiations up to order $d = 6$ over large fields, and up to $d = 4$ over practically relevant fields such as $\mathbb{F}_{2^8}$.

In this paper, we consider the conjugacy separation search problem in braid groups. We deeply redesign the algorithm presented in (Myasnikov & Ushakov, 2009) and provide an experimental evidence that the problem can be solved for $100\%$ of very long randomly generated instances. The lengths of tested randomly generated instances is increased by the factor of two compared to the lengths suggested in the original proposal for $120$ bits of security.

An implementation of our attack is freely available in CRAG. In particular, the implementation contains all challenging instances we had to deal with on a way to $100\%$ success. We hope it will be useful to braid-group cryptography community.

Implementing the masking countermeasure in hardware is a delicate task. Various solutions have been proposed for this purpose over the last years: we focus on Threshold Implementations (TIs), Domain-Oriented Masking (DOM), the Unified Masking Approach (UMA) and Generic Low Latency Masking (GLM). The latter generally come with innovative ideas to prevent physical defaults such as glitches. Yet, and in contrast to the situation in software-oriented masking, these schemes have not been formally proven at arbitrary security orders and their composability properties were left unclear. So far, only a 2-cycle implementation of the seminal masking scheme by Ishai, Sahai and Wagner has been shown secure and composable in the robust probing model -- a variation of the probing model aimed to capture physical defaults such as glitches -- for any number of shares. In this paper, we argue that this lack of proofs for TIs, DOM, UMA and GLM makes the interpretation of their security guarantees difficult as the number of shares increases. For this purpose, we first put forward that the higher-order variants of all these schemes are affected by (local or composability) security flaws in the (robust) probing model, due to insufficient refreshing. We then show that composability and robustness against glitches cannot be analyzed independently. We finally detail how these abstract flaws translate into concrete (experimental) attacks, and discuss the additional constraints robust probing security implies on the need of registers. Despite not systematically leading to improved complexities at low security orders, e.g., with respect to the required number of measurements for a successful attack, we argue that these weaknesses provide a case for the need of security proofs in the robust probing model at higher security orders.

Cloud computing has become an irreversible trend. Together comes the pressing need for verifiability, to assure the client the correctness of computation outsourced to the cloud. Existing verifiable computation techniques all have a high overhead, thus if being deployed in the clouds, would render cloud computing more expensive than the on-premises counterpart. To achieve verifiability at a reasonable cost, we leverage game theory and propose a smart contract based solution. In a nutshell, a client lets two clouds compute the same task, and uses smart contracts to stimulate tension, betrayal and distrust between the clouds, so that rational clouds will not collude and cheat. In the absence of collusion, veri cation of correctness can be done easily by crosschecking the results from the two clouds. We provide a formal analysis of the games induced by the contracts, and prove that the contracts will be e ective under certain reasonable assumptions. By resorting to game theory and smart contracts, we are able to avoid heavy cryptographic protocols. The client only needs to pay two clouds to compute in the clear, and a small transaction fee to use the smart contracts. We also con- ducted a feasibility study that involves implementing the contracts in Solidity and running them on the o cial Ethereum network.

Substitution-Permutation Networks (SPNs) refer to a family of constructions which build a $wn$-bit (tweakable) block cipher from $n$-bit public permutations. Many widely deployed block ciphers are part of this family and rely on very small public permutations. Surprisingly, this structure has seen little theoretical interest when compared with Feistel networks, another high-level structure for block ciphers.

This paper extends the work initiated by Dodis et al. in three directions; first, we make SPNs tweakable by allowing keyed tweakable permutations in the permutation layer, and prove their security as tweakable block ciphers. Second, we prove beyond-the-birthday-bound security for $2$-round non-linear SPNs with independent S-boxes and independent round keys. Our bounds also tend towards optimal security $2^n$ (in terms of the number of threshold queries) as the number of rounds increases. Finally, all our constructions permit their security proofs in the multi-user setting.

As an application of our results, SPNs can be used to build provably secure wide tweakable block ciphers from several public permutations, or from a block cipher. More specifically, our construction can turn two strong public $n$-bit permutations into a tweakable block cipher working on $wn$-bit blocks and using a $6n$-bit key and an $n$-bit tweak (for any $w\geq 2$); the tweakable block cipher provides security up to $2^{2n/3}$ adversarial queries in the random permutation model, while only requiring $w$ calls to each permutation and $3w$ field multiplications for each $wn$-bit block.

In 2015, Abdalla et al. introduced Inner Product Functional Encryption, where both ciphertexts and decryption keys are vectors of fixed size $n$, and keys enable the computation of an inner product between the two. In practice, however, the size of the data parties are dealing with may vary over time. Having a public key of size $n$ can also be inconvenient when dealing with very large vectors. We define the Unbounded Inner Product functionality in the context of Public-Key Functional Encryption, and introduce the first scheme that realizes it under standard assumptions. In an Unbounded Inner Product Functional Encryption scheme, a public key allows anyone to encrypt unbounded vectors, that are essentially mappings from $\mathbb{N}^*$ to $\mathbb{Z}_p$. The owner of the master secret key can generate functional decryption keys for other unbounded vectors. These keys enable one to evaluate the inner product between the unbounded vector underlying the ciphertext and the unbounded vector in the functional decryption key, provided certain conditions on the two vectors are met. We build Unbounded Inner Product Functional Encryption by introducing pairings, using a technique similar to that of Boneh-Franklin Identity-Based Encryption. A byproduct of this is that our scheme can be made Identity-Based "for free". It is also the first Public-Key Inner Product Functional Encryption Scheme with a constant size public key (and master secret key).

Secure two-party computation has witnessed significant efficiency improvements in the recent years. Current implementations of protocols with security against passive adversaries generate and process data much faster than it can be sent over the network, even with a single thread. This paper introduces novel methods to further reduce the communication bottleneck and round complexity of semi-honest secure two-party computation. Our new methodology creates a trade-off between communication and computation, and we show that the added computing cost for each party is still feasible and practicable in light of the new communication savings. We first improve communication for Boolean circuits with 2-input gates by factor 1.9x when evaluated with the protocol of Goldreich-Micali-Wigderson (GMW). As a further step, we change the conventional Boolean circuit representation from 2-input gates to multi-input/multi-output lookup tables (LUTs) which can be programmed to realize arbitrary functions. We construct two protocols for evaluating LUTs offering a trade-off between online communication and total communication. Our most efficient LUT-based protocol reduces the communication and round complexity by a factor 2-4x for several basic and complex operations. Our proposed scheme results in a significant overall runtime decrease of up to a factor of 3x on several benchmark functions.

We revisit the ordinary isogeny-graph based cryptosystems of Couveignes and Rostovtsev–Stolbunov, long dismissed as impractical. We give algorithmic improvements that accelerate key exchange in this framework, and explore the problem of generating suitable system parameters for contemporary pre- and post-quantum security that take advantage of these new algorithms. We also prove the session-key security of this key exchange in the Canetti–Krawczyk model, and the IND-CPA security of the related public-key encryption scheme, under reasonable assumptions on the hardness of computing isogeny walks. Our systems admit efficient key-validation techniques that yield CCA-secure encryption, thus providing an important step towards efficient post-quantum non-interactive key exchange.