International Association
for Cryptologic Research

We present HPolyC, a construction which builds on Poly1305, XChaCha12, and a single block cipher invocation per message to offer length-preserving encryption with a fast constant-time implementation where crypto instructions are absent. On an ARM Cortex-A7 processor, HPolyC decrypts 4096-byte messages at 14.5 cycles per byte, over four times faster than AES-256-XTS. Assuming secure primitives, we prove an advantage bound of $\approx 2^{-111}q^2(l + 156)$, where $q$ is the number of queries and $l$ is the sum of message and tweak length in bits.

The computer science department at the University of Twente is expanding its capacity and is looking for candidates at levels ranging from junior to more senior, for both combined research and education positions (assistant / associate professor), and education positions (lecturer).

Cybersecurity (broadly conceived) is by all means among the topics of interest!

The full announcement of these positions can be found here:
https://www.utwente.nl/en/organization/careers/vacancy/!/421417/6-assistantassociate-professors-and-lecturers-in-computer-science

Closing date for applications: 31 August 2018

More information: https://www.utwente.nl/en/organization/careers/vacancy/

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 (the group has other projects, some of which have a later ending date) 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 September 2018

Contact: Helger Lipmaa

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

Event date: 5 June to 7 June 2019
Submission deadline: 22 January 2019
Notification: 22 March 2019

Recent works by Kellaris et al. (CCS’16) and Lacharite et al. (SP’18) demonstrated attacks of data recovery for encrypted databases that support rich queries such as range queries. In this paper, we develop the first data recovery attacks on encrypted databases supporting one-dimensional k-nearest neighbor (k-NN) queries, which are widely used in spatial data management. Our attacks exploit a generic k-NN query leakage profile: the attacker observes the identifiers of matched records. We consider both unordered responses, where the leakage is a set, and ordered responses, where the leakage is a k-tuple ordered by distance from the query point.

As a first step, we perform a theoretical feasibility study on exact reconstruction, i.e., recovery of the exact plaintext values of the encrypted database. For ordered responses, we show that exact reconstruction is feasible if the attacker has additional access to some auxiliary information that is normally not available in practice. For unordered responses, we prove that exact reconstruction is impossible due to the infinite number of valid reconstructions. As a next step, we propose practical and more realistic approximate reconstruction attacks so as to recover an approximation of the plaintext values. For ordered responses, we show that after observing enough query responses, the attacker can approximate the client’s encrypted database with considerable accuracy. For unordered responses we characterize the set of valid reconstructions as a convex polytope in a k-dimensional space and present a rigorous attack that reconstructs the plaintext database with bounded approximation error.

As multidimensional spatial data can be efficiently processed by mapping it to one dimension via Hilbert curves, we demonstrate our approximate reconstruction attacks on privacy-sensitive geolocation data. Our experiments on real-world datasets show that our attacks reconstruct the plaintext values with relative error ranging from 2.9% to 0.003%.

Randomness is essential but expensive resource for cryptography, and secure (and efficient) implementations of randomness using pseudorandom generators (PRGs) are much concerned in this area. On the other hand, implementations of randomness without losing the correctness of the underlying cryptosystem should be important but seem to be less concerned in the literature. The results in this paper show that the problem of the correct implementation of randomness in cryptosystems is in general non-trivial even by using secure PRGs. Namely, we construct two examples with the following properties:

- There are a secure and correct public key encryption (PKE) scheme (with negligible decryption error probability) and a secure PRG satisfying that, implementing the key generation algorithm by using the PRG makes the scheme incorrect. The reason of this phenomenon is that, the standard formulation of correctness of PKE schemes does in general not imply that erroneous keys (that yield non-negligible decryption error probability for some plaintext) are efficiently detectable.

- There are a secure and correct PKE scheme and a PRG secure against uniform distinguishers, satisfying that, implementing the encryption algorithm by using the PRG makes the scheme incorrect. The reason of this phenomenon is that, when a PKE scheme is incorrect, a plaintext that yields non-negligible decryption error probability is in general not efficiently samplable by a uniform algorithm; hence security of the PRG against non-uniform distinguishers is required. We also discuss a possibility to avoid the reliance on PRGs secure against non-uniform distinguishers.

Thermal laser stimulation (TLS) is a failure analysis technique, which can be deployed by an adversary to localize and read out stored secrets in the SRAM of a chip. To this date, a few proof-of-concept experiments based on TLS or similar approaches have been reported in the literature, which do not reflect a real attack scenario. Therefore, it is still questionable whether this attack technique is applicable to modern ICs equipped with side-channel countermeasures. The primary aim of this work is to assess the feasibility of launching a TLS attack against a device with robust security features. To this end, we select a modern FPGA, and more specifically, its key memory, the so-called battery-backed SRAM (BBRAM), as a target. We demonstrate that an attacker is able to extract the stored 256-bit AES key used for the decryption of the FPGA’s bitstream, by conducting just a single non-invasive measurement. Moreover, it becomes evident that conventional countermeasures are incapable of preventing our attack since the FPGA is turned off during key recovery. Based on our time measurements, the required effort to develop the attack is shown to be less than 7 hours. To avert this powerful attack, we propose a low-cost and CMOS compatible countermeasure circuit, which is capable of protecting the BBRAM from TLS attempts even when the FPGA is powered off. Using a proof-of-concept prototype of our countermeasure, we demonstrate its effectiveness against TLS key extraction attempts.

We provide lattice-based protocols allowing to prove relations among committed integers. While the most general zero-knowledge proof techniques can handle arithmetic circuits in the lattice setting, adapting them to prove statements over the integers is non-trivial, at least if we want to handle exponentially large integers while working with a polynomial-size modulus $q$. For a polynomial $L$, we provide zero-knowledge arguments allowing a prover to convince a verifier that committed $L$-bit bitstrings $x$, $y$ and $z$ are the binary representations of integers $X$, $Y$ and $Z$ satisfying $Z=X+Y$ over $\mathbb{Z}$. The complexity of our arguments is only linear in $L$. Using them, we construct arguments allowing to prove inequalities $X<Z$ among committed integers, as well as arguments showing that a committed $X$ belongs to a public interval $[\alpha,\beta]$, where $\alpha$ and $\beta$ can be arbitrarily large. Our range arguments have logarithmic cost (i.e., linear in $L$) in the maximal range magnitude. Using these tools, we obtain zero-knowledge arguments showing that a committed element $X$ does not belong to a public set $S$ using $\widetilde{\mathcal{O}}(n \cdot \log |S|)$ bits of communication, where $n$ is the security parameter. We finally give a protocol allowing to argue that committed $L$-bit integers $X$, $Y$ and $Z$ satisfy multiplicative relations $Z=XY$ over the integers, with communication cost subquadratic in $L$. To this end, we use our protocol for integer addition to prove the correct recursive execution of Karatsuba's multiplication algorithm. The security of our protocols relies on standard lattice assumptions with polynomial modulus and polynomial approximation factor.

Searchable symmetric encryption (SSE) schemes are commonly proposed to enable search in a protected unstructured documents such as email archives or any set of sensitive text files. However, some SSE schemes have been recently proposed in order to protect relational databases. Most of the previous attacks on SSE schemes have only targeted its common use case, protecting unstructured data. In this work, we propose a new inference attack on relational databases protected via SSE schemes. Our inference attack enables a passive adversary with only basic knowledge about the meta-data information of the target relational database to recover the attribute names of some observed queries. This violates query privacy since the attribute name of a query is secret.

In this document, we introduce PKP-DSS: a Digital Signature Scheme based on the so-called Permuted Kernel Problem (PKP). PKP is an NP-complete algebraic problem that consists of finding a kernel vector with particular entries for a publicly known matrix. It's simple, and needs only basic linear algebra. Hence, this problem was used to develop the first Identification Scheme (IDS) which has an efficient implementation on low-cost smart cards. We construct PKP-DSS from a Zero-Knowledge Identification Scheme (ZK-IDS) based on PKP. We derive the signature scheme PKP-DSS by using the traditional Fiat-Shamir (FS) transform. Thus, PKP-DSS has a security that can be provably reduced, in the (classical) random oracle model, to essentially the hardness of random instances of PKP. Following the State-of-the-art attacks of PKP, we propose several sets of parameters for different security levels. Each parameter set arises signatures of length smaller than the other signatures derived from Zero-Knowledge identification schemes. In particular, PKP-DSS-128 gives a signature size about $29$ KBytes for $128$ bits of classical security, while the best known signature schemes built from a ZK-IDS (such as MQDSS, Picnic,... ) give bigger signatures ($> 32$ KB).

Two vectorial Boolean functions are ``CCZ-equivalent'' if there exists an affine permutation mapping the graph of one to the other. It preserves many of the cryptographic properties of a function such as its differential and Walsh spectra, which is why it could be used by Dillon et al. to find the first APN permutation on an even number of variables. However, the meaning of this form of equivalence remains unclear. In fact, to the best of our knowledge, it is not known how to partition a CCZ-equivalence class into its Extended-Affine (EA) equivalence classes; EA-equivalence being a simple particular case of CCZ-equivalence.

In this paper, we characterize CCZ-equivalence as a property of the zeroes in the Walsh spectrum of a function $F : \mathbb{F}_2^{n} \to \mathbb{F}_2^{m}$ or, equivalently, of the zeroes in its Difference Distribution Table. We use this framework to show how to efficiently upper bound the number of distinct EA-equivalence classes in a given CCZ-equivalence class. More importantly, we prove that it is possible to go from a specific member of any EA-equivalence class to a specific member of another EA-equivalence class in the same CCZ-equivalence class using an operation called \emph{twisting}; so that CCZ-equivalence can be reduced to the association of EA-equivalence and twisting. Twisting a function is a simple process and its possibility is equivalent to the existence of a particular decomposition of the function considered. Using this knowledge, we revisit several results from the literature on CCZ-equivalence and show how they can be interpreted in light of our new framework.

Our results rely on a new concept, the ``thickness'' of a space (or linear permutation), which can be of independent interest.

A verifiable delay function (VDF) is an important tool used for adding delay in decentralized applications. This short note briefly surveys and compares two recent beautiful Verifiable Delay Functions (VDFs), one due to Pietrzak and the other due to Wesolowski. We also provide a new computational proof of security for one of them, and compare the complexity assumptions needed for both schemes.

Group key distribution protocol is a mechanism in which a group key is generated and distributed by KGC to a set of communicating parties in a group. This group key generally ensures secure communication among communicating parties in an unsecure channel. Harn and Lin protocol is one such. It is based on Shamir's secret sharing scheme. Nam et al. exposed the vulnerability in Harn and Lin protocol through their replay attack and proposed a countermeasure using nonce mechanism. In this paper, we are generalizing the replay attack proposed by Nam et al. and proposing an alternative countermeasure without using nonce mechanism. Novelty of our countermeasure is that KGC is not required to detect replay messages and hence each user doesn't need to compute authentication message as in Nam et al. Proposed countermeasure thereby brings down the computational complexity of the scheme.

Secure Multi-Party Computation (MPC) with small number of parties is an interesting area of research, primarily due to its ability to model most real-life MPC applications and the simplicity and efficiency of the resulting protocols. In this work, we present efficient, constant-round 3-party (3PC) and 4-party (4PC) protocols in the honest-majority setting that achieve strong security notions of fairness (corrupted parties receive their output only if all honest parties receive output) and guaranteed output delivery (corrupted parties cannot prevent honest parties from receiving their output). Being constant-round, our constructions are suitable for Internet-like high-latency networks and are built from garbled circuits (GC).

Assuming the minimal model of pairwise-private channels, we present two protocols that involve computation and communication of a single GC-- (a) a 4-round 3PC with fairness, (b) a 5-round 4PC with guaranteed output delivery. Empirically, our protocols are on par with the best known 3PC protocol of Mohassel et al. [CCS 2015] that only achieves security with selective abort, in terms of the computation time, LAN runtime, WAN runtime and communication cost. In fact, our 4PC outperforms the 3PC of Mohassel et al. significantly in terms of per-party computation and communication cost. With an extra GC, we improve the round complexity of our 4PC to four rounds. The only 4PC in our setting, given by Ishai et al. [CRYPTO 2015], involves 12 GCs.

Assuming an additional broadcast channel, we present a 5-round 3PC with guaranteed output delivery that involves computation and communication of a single GC. A broadcast channel is inevitable in this setting for achieving guaranteed output delivery, owing to an impossibility result in the literature. The overall broadcast communication of our protocol is nominal and most importantly, is independent of the circuit size. This protocol too induces a nominal overhead compared to the protocol of Mohassel et al.

The key exchange protocol of Diffie and Hellman, which can be defined for any group, has the special feature of using only exponentiations. In particular, it can also be instantiated in Kummer varieties, which are not groups, and in the post-quantum isogeny-based setting, with the supersingular isogeny DH scheme of De Feo, Jao and Plût (SIDH).

In this article, we propose a new simple oblivious transfer (OT) protocol, based on the Diffie-Hellman key exchange, that only uses exponentiations; we also revisit the older Wu-Zhang-Wang scheme. Both protocols can be directly instantiated on fast Kummer varieties; more importantly, they can also be transposed in the post-quantum SIDH setting. The security of our proposals relies on the hardness of non-standard versions of the (supersingular) Diffie-Hellman problem, that are investigated within this article. To the best of our knowledge, these protocols are the simplest secure discrete-log based OT schemes using only exponentiations, and the first isogeny-based OT schemes.

The ongoing CAESAR competition aims at finding authenticated encryption schemes that offer advantages over AES-GCM for several use-cases, including lightweight applications. ACORN and Ascon are the two finalists for this profile. Our paper compares these two candidates according to their resilience against differential power analysis and their ability to integrate countermeasures against such attacks. Especially, we focus on software implementations and provide benchmarks for several security levels on anARM Cortex-M3 embedded microprocessor.

Function Secret Sharing (FSS), introduced by Boyle et al. (Eurocrypt 2015), provides a way for additively secret-sharing a function from a given function family $\mathcal F$. More concretely, an $m$-party FSS scheme splits a function $f:\{0,1\}^n\to \mathbb G$, for some abelian group $\mathbb G$, into functions $f_1,\ldots,f_m$, described by keys $k_1,\ldots,k_m$, such that $f=f_1+\ldots+f_m$ and every strict subset of the keys hides $f$. A Distributed Point Function (DPF) is a special case where $\mathcal F$ is the family of point functions, namely functions $f_{\alpha,\beta}$ that evaluate to $\beta$ on the input $\alpha$ and to 0 on all other inputs.

FSS schemes are useful for applications that involve privately reading from or writing to distributed databases while minimizing the amount of communication. These include different flavors of private information retrieval (PIR), as well as a recent application of DPF for large-scale anonymous messaging. We improve and extend previous results in several ways:

- Simplified FSS constructions. We introduce a tensoring operation for FSS which is used to obtain a conceptually simpler derivation of previous constructions and present our new constructions.

- Improved 2-party DPF. We reduce the key size of the PRG-based DPF scheme of Boyle et al. roughly by a factor of 4 and optimize its computational cost. The optimized DPF significantly improves the concrete costs of 2-server PIR and related primitives.

- FSS for new function families. We present an efficient PRG-based 2-party FSS scheme for the family of decision trees, leaking only the topology of the tree and the internal node labels. We apply this towards FSS for multi-dimensional intervals. We also present a general technique for obtaining more expressive FSS schemes by increasing the number of parties.

- Verifiable FSS. We present efficient protocols for verifying that keys $(k^*_1,\ldots,k^*_m)$, obtained from a potentially malicious user, are consistent with some $f\in\mathcal F$. Such a verification may be critical for applications that involve private writing or voting by many users.

Distributed Oblivious RAM (DORAM) protocols---in which parties obliviously access a shared location in a shared array---are a fundamental component of secure-computation protocols in the RAM model. We show here an efficient, 3-party DORAM protocol with semi-honest security for a single corrupted party. To the best of our knowledge, ours is the first protocol for this setting that runs in constant rounds, requires sublinear communication and linear work, and makes only black-box use of cryptographic primitives. We believe our protocol is also concretely more efficient than existing solutions.

As a building block of independent interest, we construct a 3-server distributed point function with security against two colluding servers that is simpler and has better concrete efficiency than prior work.

An argument of knowledge allows a prover to convince a verifier of the validity of certain statements. We construct succinct arguments of knowledge with an optimal communication complexity of $O(\lambda)$ bits in the standard model, thereby resolving an open problem posed by Kilian (CRYPTO' 95), assuming that the strong root problem is hard over groups of unknown order. Our protocol can be generically transformed into a zero-knowledge succinct non-interactive argument of knowledge (zk-SNARK) with proofs of size $O(\lambda)$ bits, with efficient trusted setup in the random oracle model. These results can be instantiated under the strong RSA assumption. For groups that admit a public-coin setup, the transformation yields a zk-SNARK without setup. A plausible candidate family of such groups is class groups of imaginary quadratic orders. Existing zk-SNARKs with optimal proof size require inefficient trusted setup and use bilinear maps. Our main technical tool is a generalization of vector commitments called subvector commitments. The latter allows one to open a commitment of a vector at a set of positions, where the opening size is independent of the size of the set. Apart from the new application in constructing succinct arguments, subvector commitments generally serve as a more efficient replacement of vector commitments in all applications where the prover needs to decommit at more than one position.

The success of the Ethereum blockchain as a decentralized application platform with a distributed consensus protocol has made many organizations start to invest in running their business on top of it. Technically, the most impressive feature behind Ethereum's success is its support for a Turing complete language. On the other hand, the inherent transparency and, consequently, the lack of privacy pose a great challenge for many financial applications. In this paper, we tackle this challenge and present a smart contract for a verifiable sealed-bid auction on the Ethereum blockchain. In a nutshell, initially, the bidders submit homomorphic commitments to their sealed-bids on the contract. Subsequently, they reveal their commitments secretly to the auctioneer via a public key encryption scheme. Then, according to the auction rules, the auctioneer determines and claims the winner of the auction. Finally, we utilize interactive zero-knowledge proof protocols between the smart contract and the auctioneer to verify the correctness of such a claim. The underlying protocol of the proposed smart contract is partially privacy-preserving. To be precise, no information about the losing bids is leaked to the bidders. We provide an analysis of the proposed protocol and the smart contract design, in addition to the estimated gas costs associated with the different transactions.