International Association
for Cryptologic Research

We initiate the study of perfect (rather than merely statistical) reductions among cryptographic primitives. For simplicity, we focus on finite functionalities.

In addition to the obvious theoretical appeal of the question towards better understanding secure computation, perfect, as opposed to statistical reductions may be useful for designing MPC protocols with high concrete efficiency, achieved by eliminating the dependence on a security parameter.

1-out-of-2 bit-OT (dubbed OT) was shown to be complete for statistically secure 2PC for all functionalities [Kil88, IPS08]. Existing protocols in the OT-hybrid model only offer statistically secure with abort (efficient) protocols (requiring no further computational assumptions). In general, fairness can not be guaranteed, and only security with abort is achievable [Cleve86]. If the protocol is not required to be efficient in the security parameter $k$, then all 2PC functionalities can be securely evaluated [GK10] with statistical security in the OT-hybrid model.

As opposed to the statistical setting, it is not known whether OT is complete for perfectly secure 2PC. Furthermore, only a few examples of functionalities that have such protocols are known: we are only aware of string-OT and TO (OT with reversed roles) as perfectly reducible to OT. On the negative side, a large class is known, as implied by the fairness literature. By definition, functionalities not securely computable with fairness require super-polynomial in $k$ computational (and round) complexity to evaluate with error $neg(k)$ in the OT-hybrid model. This implies that these functionalities not computable with fairness are also not computable with perfect security (in the OT-hybrid model). For symmetric boolean functionalities, this class been fully characterized [ABMO15].

Back to the statistical world, quite surprisingly [IKOPS11] demonstrate that all client-server functionalities can be efficiently reduced to OT with statistical full security (no abort) in only one round.

Motivated by this relative ``ease'' of client-server functionalities for statistically secure 2PC in the OT-hybrid model, we study perfect reductions to OT for this class of functions. We prove that for many client-server functions of the form $f: X\times Y\rightarrow \{0,1\}$, where server domain size $|Y|$ is larger than client domain size $X$, have a perfect reduction to OT. More precisely, a $g(|X|,|Y|)=\Omega(1)$-fraction of functions are perfectly reducible to OT. This fraction grows roughly as $1-exp(|X|-|Y|)$. Furthermore, our reduction is 1-round using an oracle to secure evaluation of ${\text{OT}}^l$ (as in [IKOPS11]). As an example, this class contains $\text{2-out-of-5-OT}$. More generally, for $f: X\times Y\rightarrow Z$, $\Omega(1)$ of the functions with $|Y|>|X|(|Z|-1)$ are perfectly reducible to OT in 1 round.

Our work leaves open the question of whether all finite client-server functionalities are perfectly reducible to OT (not necessarily in one round). Another open question is whether 2PC functionalities that do have perfectly secure protocols in the OT hybrid model differ in round complexity, as is the case for statistical protocols.

We present a variation on the CM method that produces elliptic curves over prime fields with nearly prime order that do not admit many efficiently computable isogenies. Assuming the Bateman-Horn conjecture, we prove that elliptic curves produced this way almost always have a large embedding degree, and thus are resistant to the MOV attack on the ECDLP.

The security analysis of real-world protocols involves reduction steps that are conceptually simple but have to handle complicated protocol details. Taking inspiration from Universal Composability, Abstract Cryptography, Pi-calculus and F*-based analysis we propose a new technique for writing simple reductions to avoid mistakes, have more selfcontained concrete security statements, and allow the writer and reader to focus on the interesting steps of the proof. Our method replaces a monolithic protocol game with a collection of so-called packages that are composed by calling each other. Every component scheme is replaced by a package parameterized by a bit b. Packages with a bit 0 behave like a concrete scheme, while packages with a bit 1 behave like an ideal version. The indistinguishability of the two packages captures security properties, such as the concrete pseudo-random function being indistinguishable from a random function. In a security proof of a real-life protocol, one then needs to flip a package’s bit from 0 to 1. To do so, in our methodology, we consider all other packages as the reduction. We facilitate the concise description of such reductions by a number of Pi-calculus-style algebraic operations on packages that are justified by state separation and interface restrictions. Our proof method handles “simple” steps using algebraic rules and leaves “interesting” steps to existing game-based proof techniques such as, e.g., the code-based analysis suggested by Bellare and Rogaway. In addition to making simple reductions more precise, we apply our techniques to two composition proofs: a proof of self-composition using a hybrid argument, and the composition of key generating and key consuming components. Consistent with our algebraic style the proofs are generic. For concreteness, we apply them to the KEM-DEM proof of hybrid-encryption by Cramer and Shoup and the proof for composability of Bellare-Rogaway secure key exchange protocols with symmetric-key protocols.

We apply Smith's construction to generate four-dimensional GLV curves with fast arithmetic in the group law as well as in the base field. As Costello and Longa did in [5] for a 128-bit security level, we btained an interesting curve for fast GLV scalar multiplication, providing a high level of security (254 bits). Our curve is defined over a well-known finite field: $\mathbb{F}_{p^2}$ where $p = 2^{255} - 19$. We finally explicit the two endomorphisms used during GLV decomposition.

Geosocial applications collect (and record) users’ precise location data to perform proximity computations, such as notifying a user or triggering a service when a friend is within geographic proximity. With the growing popularity of mobile devices that have sophisticated localization capability, it becomes more convenient and tempting to share location data. But the precise location data in plaintext not only exposes user’s whereabouts but also mobility pa erns that are sensitive and cannot be changed easily. This paper proposes cryptographic protocols on top of spatial cloaking to reduce the resolution of location and balance between data utility and privacy. Specifically, we interest in the setting that allows users to send periodic updates of precise coordinates and define privacy preferences to control the granularity of the location, both in an encrypted format. Our system supports three kinds of user queries — “Where is this user?”, “Who is nearby?”, and “How close is this user from another user?”. Also, we develop a new algorithm to improve the multidimensional data access by reducing significant masking error. Our prototype and various performance evaluations on different platforms demonstrated that our system is practical.

While many cryptographic protocols for card games have been proposed, all of them focus on card games where players have some state that must be kept secret from each other, e.g. closed cards and bluffs in Poker. This scenario poses many interesting technical challenges, which are addressed with cryptographic tools that introduce significant computational and communication overheads (e.g. zero-knowledge proofs). In this paper, we consider the case of games that do not require any secret state to be maintained (e.g. Blackjack and Baccarat). Basically, in these games, cards are chosen at random and then publicly advertised, allowing for players to publicly announce their actions (before or after cards are known). We show that protocols for such games can be built from very lightweight primitives such as digital signatures and canonical random oracle commitments, yielding constructions that far outperform all known card game protocols in terms of communication, computational and round complexities. Moreover, in constructing highly efficient protocols, we introduce a new technique based on verifiable random functions for extending coin tossing, which is at the core of our constructions. Besides ensuring that the games are played correctly, our protocols support financial rewards and penalties enforcement, guaranteeing that winners receive their rewards and that cheaters get financially penalized. In order to do so, we build on blockchain-based techniques that leverage the power of stateful smart contracts to ensure fair protocol execution.

In this position paper, we initiate a systematic treatment of reaching consensus in a permissionless network. We prove several simple but hopefully insightful lower bounds that demonstrate exactly why reaching consensus in a permissionless setting is fundamentally more difficult than the classical, permissioned setting. We then present a simplified proof of Nakamoto's blockchain which we recommend for pedagogical purposes. Finally, we survey recent results including how to avoid well-known painpoints in permissionless consensus, and how to apply core ideas behind blockchains to solve consensus in the classical, permissioned setting and meanwhile achieve new properties that are not attained by classical approaches.

The goal of white-box cryptography is to implement cryptographic algorithms securely in software in the presence of an adversary that has complete access to the software's program code and execution environment. In particular, white-box cryptography needs to protect the embedded secret key from being extracted. As for today, all publicly available white-box implementations turned out succeptible to key extraction attacks. In the meanwhile, white-box cryptography is widely deployed in commercial implementations that claim to be secure. Bos, Hubain, Michiels and Teuwen (CHES 2016) introduced differential computational analysis (DCA), the first automated attack on white-box cryptography. The DCA attack performs a statistical analysis on execution traces. These traces contain information about the execution, such as memory addresses or register values, that is collected via binary instrumentation tooling during the encryption process. The white-box implementations that were attacked by Bos et al., as well as white-box implementations that have been described in the literature, protect the embedded key by using internal encodings techniques that have been introduced by Chow, Eisen, Johnson and van Oorschot (SAC 2002). In this paper, we prove rigorously that such internal encodings are too weak to protect against the DCA attack and thereby explain the experimental success of the DCA attack of Bos et al.

Modern web applications using advanced cryptographic methods may need to calculate a large number of modular exponentiations. Performing such calculations in the web browser efficiently is a known problem. We propose a solution to this problem based on outsourcing the computational effort to untrusted exponentiation servers. We present several efficient outsourcing protocols for different settings and a practical implementation consisting of a JavaScript client library and a server application. Compared to browser-only computation, our solution improves the overall computation time by an order of magnitude.

This is an extended version of a paper accepted and presented at the Voting’18 workshop of the Financial Cryptography and Data Security 2018 conference. It will be included in the conference’s LNCS proceedings and available on the Springer web site.

The cryptography group at the Institute of Computer Science of the University of Tartu seeks 1-2 postdoctoral researchers in cryptography. The positions will be supporting an EU H2020 project on privacy-enhancing cryptography for distributed ledgers (PRIViILEDGE). The candidate(s) should have a strong track record in cryptography, and in particular in the design of efficient privacy-preserving protocols (e.g., zero-knowledge proofs) and/or blockchain.

We expect candidates to be able to develop and devote significant time to their own research agenda around the theme of the project. Successful candidates will help to design and evaluate privacy-enhancing cryptographic techniques for blockchains (e.g., SNARKs) and perform other research duties to help with the project, collaborate with partners and ensure the smooth administration of the project including the timely delivery of research output.

The EU H2020 project PRIViLEDGE requires travel to and collaboration with colleagues throughout the European Union. Full travel and equipment budget is available to support the activities of the project.

For any inquiries or to apply for the positions, submit a full research curriculum-vitae (cv), names of two references, and a research statement to Prof Helger Lipmaa (firstname.lastname (at) ut.ee) clearly indicating the position sought. This is crucial since we have several open positions.

The project started from January 1, 2018, and will last for three years. In the case of interest, the candidates may later seek further employment but this is not necessarily guaranteed. The position will stay open until we find a suitable candidate; please apply early.

Closing date for applications: 1 May 2018

Contact: Helger Lipmaa

More information: https://crypto.cs.ut.ee/index.php/Projects/PRIViLEDGE

Event date: 7 December to 8 December 2018
Submission deadline: 15 June 2018

Event date: 8 July to 15 July 2018

Event date: 13 September 2018
Submission deadline: 18 June 2018
Notification: 20 July 2018

Event date: 12 November to 14 November 2018
Submission deadline: 13 July 2018
Notification: 14 September 2018

Event date: 28 November to 30 November 2018
Submission deadline: 10 August 2018
Notification: 10 September 2018

This article describes a survey of long-term cryp- tographic public keys observed in real deployments of secure- shell, e-mail and web protocols in two similarly-sized countries – Ireland and Estonia. We find that keys are very widely re- used across multiple IP addresses, and even autonomous systems. From one run scanning 18,268 hosts in Ireland that run at least one TLS or SSH service, approximately 53% of the hosts involved are using keys that are also seen on some other IP address. For each key, if two IP addresses share that key, then those two IP addresses are considered members of the same cluster. In the same scan we find a maximum cluster size of 1,991 hosts and a total of 1,437 clusters, mostly with relatively few hosts per cluster (median cluster size was 26.5, most common cluster size is two). In that scan, of the 54,447 host/port combinations running cryptographic protocols, we only see 20,053 unique keys (36%), indicating significant key re-use across hosts and ports. We describe the methodology followed and the published source code and public data sources that enable researchers to replicate, validate and extend these results. Clearly, such key sharing can create undesirable security and privacy dependencies between cluster members. The author is currently starting the process of contacting local (Irish) asset-owners to try establish the reasons for this key sharing and to possibly assist with improving network posture.

Singapore University of Technology and Design (SUTD) is a young university which was established in collaboration with MIT. iTrust is a Cyber Security Research Center with about 15 inter-disciplinary faculty members from SUTD. It has the world\'s best facilities in cyber-physical systems (CPS) including testbeds for Secure Water Treatment (SWaT), Water Distribution (WADI), Electric Power and Intelligent Control (EPIC), and IoT. (See more info at https://itrust.sutd.edu.sg/research/testbeds/.)

I am looking for PhD interns with interest in cyber-physical system security (IoT, water, power grid, transportation, and autonomous vehicle etc.). The attachment will be at least 3 months. Allowance will be provided for local expenses.

Interested candidates please send your CV with a research statement to Prof. Jianying Zhou.

Closing date for applications: 30 May 2018

Contact: Prof. Jianying Zhou

Email: jianying_Zhou (at) sutd.edu.sg

More information: http://jianying.space/

We survey elliptic curve implementations from several vantage points. We perform internet-wide scans for TLS on a large number of ports, as well as SSH and IPsec to measure elliptic curve support and implementation behaviors, and collect passive measurements of client curve support for TLS. We also perform active measurements to estimate server vulnerability to known attacks against elliptic curve implementations, including support for weak curves, invalid curve attacks, and curve twist attacks. We estimate that 0.77% of HTTPS hosts, 0.04% of SSH hosts, and 4.04% of IKEv2 hosts that support elliptic curves do not perform curve validity checks as specified in elliptic curve standards. We describe how such vulnerabilities could be used to construct an elliptic curve parameter downgrade attack called CurveSwap for TLS, and observe that there do not appear to be combinations of weak behaviors we examined enabling a feasible CurveSwap attack in the wild. We also analyze source code for elliptic curve implementations, and find that a number of libraries fail to perform point validation for JSON Web Encryption, and find a flaw in the Java and NSS multiplication algorithms.

This paper initiates a study of Fine Grained Secure Computation: i.e. the construction of secure computation primitives against ``moderately complex" adversaries. We present definitions and constructions for Fully Homomorphic Encryption and Verifiable Computation secure against (non-uniform) $\mathsf{NC}^1$ adversaries. We also present two application scenarios for our model: (i) hardware chips that prove their own correctness, and (ii) protocols against rational adversaries potentially relevant to the Verifier's Dilemma in smart-contracts transactions such as Ethereum.

Ratcheted key exchange (RKE) is a cryptographic technique used in instant messaging software like Signal and the WhatsApp messenger for attaining strong security in the face of state exposure attacks (including automatic healing from the latter). RKE received first academic attention in the recent works of Cohn-Gordon et al. (EuroS&P 2017) and Bellare et al. (CRYPTO 2017). While the former is analytical in the sense that it aims primarily at assessing the security that one particular protocol does achieve, rather than looking for a strong notion of security that it could achieve, the authors of the latter follow a different approach in that they first develop a notion of security they want to achieve, and then securely instantiate it. Unfortunately, however, their model is too restricted to serve for the analysis of real-world messenger apps, for considering exclusively unidirectional communication, and for considering only the exposure of the state of only one party.

In this article we resolve the limitations of prior work by developing alternative security definitions, for unidirectional RKE as well as for RKE where both parties can contribute. We follow a purist approach, aiming at finding strong yet convincing notions that cover a realistic communication model; in particular, and in contrast to prior work, our models support fully concurrent operation of both participants.

We further propose secure instantiations (as the protocols analyzed or proposed by Cohn-Gordon et al. and Bellare et al. turn out to be weak in our models). While our scheme for the unidirectional case builds on a generic KEM as the main building block (differently to prior work that requires explicitly Diffie-Hellman), our schemes for bidirectional communication require, perhaps surprisingly, considerably stronger tools.