International Association
for Cryptologic Research

Two-party Secure Function Evaluation (SFE) allows two parties to evaluate a function known to both parties on their private inputs. In some settings, the input of one of the parties is the definition of the computed function, and requires protection as well. The standard solution for SFE of private functions (PF-SFE) is to rely on Universal Circuits (UC), which can be programmed to implement any circuit of size s. Recent UC optimizations report the cost of UC for s-gate Boolean circuits is \approx 5s log s.

Instead, we consider garbling that allows evaluating one of a given set S of circuits. We show how to evaluate one of the circuits in S at the communication cost comparable to that of evaluating the largest circuit in S. In other words, we show how to omit generating and sending inactive GC branches. Our main insight is that a garbled circuit is just a collection of garbled tables, and as such can be reused to emulate the throw-away computation of an inactive execution branch without revealing to the Evaluator whether it evaluates active or inactive branch.

This cannot be proven within the standard BHR garbled circuits framework because the function description is inseparable from the garbling by denition. We carefully extend BHR in a general way, introducing topology-decoupling circuit garbling. We preserve all existing constructions and proofs of the BHR framework, while allowing this and other future constructions which may treat garbled tables separately from function description.

Our construction is presented in the semi-honest model.

Vehicular communication (V2X) technologies are expected to be common in the future, providing better transportation safety and efficiency. However, their large-scale deployment requires addressing some challenges. In particular, to prevent abuse by drivers and by the system itself, V2X architectures must: (1) ensure the authenticity of messages, which is usually accomplished by means of digital certification; and (2) preserve the privacy of honest users, so owners of non-revoked certificates cannot be easily identified or tracked by eavesdroppers. A promising solution for managing V2X-oriented certificates in an efficient manner is the Security Credential Management System (SCMS), which is among the main candidates for standardization in the United States. In this paper, aiming to enhance and address issues in the SCMS architecture, we provide three main contributions. First, we describe and fix two birthday attacks against SCMS's certificate revocation process, thus preventing the system's security degradation with the number of issued and revoked certificates. In addition, we describe a mechanism for improving the flexibility of revocation, allowing certificates and their owner's privacy to be temporarily revoked in an efficient manner; this functionality is useful, for example, in case of vehicle theft or kidnapping. Finally, we propose a method that simplifies SCMS's system architecture, removing the need for the so-called Linkage Authorities (LAs); this not only results in cost reductions for SCMS's implementation, but also improves its security and privacy due to the removal of one potential point of failure/collusion.

Private Set Intersection (PSI) allows two parties, the sender and the receiver, to compute the intersection of their private sets without revealing extra information to each other. We are interested in the {\it unbalanced} PSI setting, where (1) the receiver's set is significantly smaller than the sender's, and (2) the receiver (with the smaller set) has a low-power device. Also, in a {\it Labeled PSI} setting, the sender holds a label per each item in its set, and the receiver obtains the labels from the items in the intersection. We build upon the unbalanced PSI protocol of Chen, Laine, and Rindal (CCS~2017) in several ways: we add efficient support for arbitrary length items, we construct and implement an unbalanced Labeled PSI protocol with small communication complexity, and also strengthen the security model using Oblivious Pseudo-Random Function (OPRF) in a pre-processing phase. Our protocols outperform previous ones: for an intersection of $2^{20}$ and $512$ size sets of arbitrary length items our protocol has a total online running time of just $1$~second (single thread), and a total communication cost of $4$~MB. For a larger example, an intersection of $2^{28}$ and $1024$ size sets of arbitrary length items has an online running time of $12$ seconds (multi-threaded), with less than $18$~MB of total communication.

In this paper, we start with a discussion of discrete Gaussian measures on lattices. Several results of Banaszczyk are analyzed, different approaches are suggested. In the second part of the paper we prove two new bounds for the smoothing parameter of lattices. Under the natural assumption that $\varepsilon$ is suitably small, we obtain two estimations of the smoothing parameter:

1. \[ \eta_{\varepsilon}(\mathbb{Z}) \le \sqrt{\frac{\ln \big(\frac{\varepsilon}{44}+\frac{2}{\varepsilon}\big)}{\pi}}. \]

2. For a lattice ${\cal L}\subset \mathbb{R}^n$ of dimension $n$, \[ \eta_{\varepsilon}({\cal L}) \le \sqrt{\frac{\ln \big(n-1+\frac{2n}{\varepsilon}\big)}{\pi}}\tilde{bl}({\cal L}). \]

We introduce a new homomorphic encryption scheme that is natively capable of computing with complex numbers. This is done by generalizing recent work of Chen, Laine, Player and Xia, who modified the Fan-Vercauteren scheme by replacing the integral plaintext modulus $t$ by a linear polynomial $X - b$. Our generalization studies plaintext moduli of the form $X^m + b$. Our construction significantly reduces the noise growth in comparison to the original FV scheme, so much deeper arithmetic circuits can be homomorphically executed.

We propose a new construction of tweakable block ciphers from standard block ciphers. Our construction, dubbed XHX2, is the cascade of two independent XHX block ciphers, so it makes two call to the underlying block cipher using tweak-dependent keys. We prove the security of XHX2 up to min{2^{2(n+m)/3},2^{n+m/2}} queries (ignoring logarithmic factors) in the ideal cipher model, when the block cipher operates on n-bit blocks using m-bit keys. The XHX2 tweakable block cipher is the first construction that achieves beyond-birthday-bound security with respect to the input size of the underlying block cipher in the ideal cipher model.

Length doublers are cryptographic functions that transform an n-bit cryptographic primitive into an efficient and secure cipher that length-preservingly encrypts strings of length in [n,2n-1]. All currently known constructions are only proven secure up to the birthday bound, and for all but one construction this bound is known to be tight. We consider the remaining candidate, LDT by Chen et al.(ToSC 2017(3)), and prove that it achieves beyond the birthday bound security for the domain [n,3n/2). We generalize the construction to multiple rounds and demonstrate that by adding one more encryption layer to LDT, beyond the birthday bound security can be achieved for all strings of length in [n,2n-1]: security up to around 2^{2n/3} for the encryption of strings close to n and security up to around 2^{n} for strings of length close to 2n. The security analysis of both schemes is performed in a modular manner through the introduction and analysis of a new concept called ``harmonic permutation primitives.''

Recently Castryck, Lange, Martindale, Panny, and Renes published CSIDH, a new key exchange scheme using supersingular elliptic curve isogenies. Due to its small key sizes, and the possibility of a non-interactive and a static-static key exchange, CSIDH seems very interesting for practical applications. However, the performance is rather slow. Therefore, we employ some techniques to speed up the algorithms, mainly by restructuring the elliptic curve point multiplications and by using twisted Edwards curves in the isogeny image curve computations, yielding a speed-up factor of 1.33 in comparison to the implementation of Castryck et al. Furthermore, we suggest techniques for constant-time implementations.

In this work, we develop a framework for building leakage-resilient cryptosystems in the bounded leakage model from puncturable primitives and indistinguishability obfuscation ($\iO$). Our main results are as follows:

We build leakage-resilient weak pseudorandom functions (PRFs) from weak puncturable PRFs and $\iO$, which readily imply leakage-resilient secret-key encryption.

We build leakage-resilient publicly evaluable pseudorandom functions (PEPRFs) from puncturable PEPRFs and $\iO$, which readily imply leakage-resilient key encapsulation mechanism and thus public-key encryption. As a building block of independent interest, we realize puncturable PEPRFs from either new puncturable objects including puncturable trapdoor functions and puncturable extractable hash proof systems or existing puncturable PRFs with $\iO$.

We construct the first leakage-resilient public-coin signature from selective puncturable PRFs, leakage-resilient one-way functions and $\iO$. This settles the open problem posed by Boyle, Segev and Wichs (Eurocrypt 2011).

By further assuming the existence of lossy functions, all the above constructions achieve optimal leakage rate of $1-o(1)$. Such a leakage rate is not known to be achievable for weak PRFs, PEPRFs and public-coin signatures before.

Bitcoin is a decentralized cryptocurrency payment system, working without a single administrator or a third party bank. A bitcoin is created by miners, using complex mathematical "proof of work" procedure by computing hashes. For each successful attempt, miners get rewards in terms of bitcoin and transaction fees. Miners participate in mining to get this reward as income. Mining of cryptocurrency such as bitcoin becomes a common interest among the miners as the bitcoin market value is very high. Bitcoin is a non-renewable resource, since the reward of mining a bitcoin decreases over time, obvious questions that arise are what will be the incentive for miners in bitcoin mining over time? Moreover, how will balance be maintained in the bitcoin mining market as time goes on ? From the fact that at any time only one miner will be rewarded (the one who will win the mining game by first creating and updating the blocks and the remaining miners effort will be wasted at that time), it is better for them to mine strategically. However, this strategy could be a plan of action designed to achieve a long-term goal, either Cooperative--- where miners can benefit by cooperating and binding agreements or Non-Cooperative-- where miners do not make binding agreements and compete against each other. In this paper we create a game theoretic model where we consider bitcoin mining as a continuous time dynamic game which is played an infinite number of times. We propose two different types of game theory solutions: Social optimum: (Cooperative) when the miners altogether maximize their total profit and Nash equilibrium: (Non-Cooperative) when each miner behaves selfishly and individually wants to maximize his/her total profit. Note that in our game theory model, a player represents a single "miner" or a single "mining pool" who is responsible to create a block in the blockchain. Our work here found that the bitcoin is never sustainable and depleted very fast for the Nash equilibrium even if it is sustainable for the Social optimum. Our result is quite intuitive to the common belief that mining in cooperation will give the higher payoff or profit to each miner than mining individually. Finally, to retain the bitcoin market at equilibrium we also propose a linear tax system which is of Pigovian type in order to enforce social optimality in our bitcoin dynamic game model.

We present a group signature scheme, based on the hardness of lattice problems, whose outputs are more than an order of magnitude smaller than the currently most efficient schemes in the literature. Since lattice-based schemes are also usually non-trivial to efficiently implement, we additionally provide the first experimental implementation of lattice-based group signatures demonstrating that our construction is indeed practical -- all operations take less than half a second on a standard laptop.

A key component of our construction is a new zero-knowledge proof system for proving that a committed value belongs to a particular set of small size. The sets for which our proofs are applicable are exactly those that contain elements that remain stable under Galois automorphisms of the underlying cyclotomic number field of our lattice-based protocol. We believe that these proofs will find applications in other settings as well.

The motivation of the new zero-knowledge proof in our construction is to allow the efficient use of the selectively-secure signature scheme (i.e. a signature scheme in which the adversary declares the forgery message before seeing the public key) of Agrawal et al. (Eurocrypt 2010) in constructions of lattice-based group signatures and other privacy protocols. For selectively-secure schemes to be meaningfully converted to standard signature schemes, it is crucial that the size of the message space is not too large. Using our zero-knowledge proofs, we can strategically pick small sets for which we can provide efficient zero-knowledge proofs of membership.

Polynomial Pigeonhole Principle (PPP) is an important subclass of TFNP with profound connections to the complexity of the fundamental cryptographic primitives: collision-resistant hash functions and one-way permutations. In contrast to most of the other subclasses of TFNP, no complete problem is known for PPP. Our work identifies the first PPP-complete problem without any circuit or Turing Machine given explicitly in the input, and thus we answer a longstanding open question from [Papadimitriou1994]. Specifically, we show that constrained-SIS (cSIS), a generalized version of the well-known Short Integer Solution problem (SIS) from lattice-based cryptography, is PPP-complete.

In order to give intuition behind our reduction for constrained-SIS, we identify another PPP-complete problem with a circuit in the input but closely related to lattice problems. We call this problem BLICHFELDT and it is the computational problem associated with Blichfeldt's fundamental theorem in the theory of lattices.

Building on the inherent connection of PPP with collision-resistant hash functions, we use our completeness result to construct the first natural hash function family that captures the hardness of all collision-resistant hash functions in a worst-case sense, i.e. it is natural and universal in the worst-case. The close resemblance of our hash function family with SIS, leads us to the first candidate collision-resistant hash function that is both natural and universal in an average-case sense.

Finally, our results enrich our understanding of the connections between PPP, lattice problems and other concrete cryptographic assumptions, such as the discrete logarithm problem over general groups.

The notion of decryption rights delegation was initially introduced by Blaze et al. in EUROCRYPT 1998. It, defined as \emph{proxy re-encryption}, allows a semi-trusted proxy to convert a ciphertext intended for a party to another ciphertext of the same plaintext, without knowledge of the underlying plaintext and decryption key. It has been explored to many real-world applications, e.g., encrypted email forwarding. However, the intrinsic all-or-nothing share feature of proxy re-encryption yields a limitation that the share cannot be revoked. This may hinder the scalability of its applications in practice. In this paper, for the first time, we define the concept of revocability in terms of decryption rights delegation. The novel concept enables data owner to revoke the shared decryption rights when needed. Inspired by the seminal lattice-based proxy re-encryption proposed in PKC 2014, we design a concrete lattice-based construction which satisfies the notion. In our construction, we make use of binary-tree structure to implement the revocation of decryption rights, so that the update of re-encryption key is reduced to $O(logN)$ (instead of $O(N)$), where $N$ is the maximum number of delegatee. Furthermore, the security of our scheme is based on the standard learning with errors problem, which could be reduced to the worst-case hard problems (such as GapSVP and SIVP) in the context of lattices. The scheme is chosen ciphertext secure in the standard model. As of independent interest, our scheme achieves both backward and forward security, which means that once a user is revoked after a time period $\mathbf{t}$, it cannot gain access to all encrypted files before and after $\mathbf{t}$.

Event date: 29 November to 1 December 2018
Submission deadline: 30 September 2018
Notification: 10 October 2018

We are seeking to fill several Research Staff Member (RSM) and Post-Doc positions at IBM Research – Zurich in the area of cryptography and privacy.

Candidates for both types of openings are required to have a Ph.D. in Computer Science, Mathematics, or a related area by the time of appointment and an outstanding research record, demonstrated in the form of publications at top cryptography or security conferences (Crypto, Eurocrypt, CCS, S&P, ...).

The ideal applicant for an RSM position is someone with demonstrated ability to perform top notch independent work, who is also keen on pursuing joint research directions with the current members of the group. The possibility of establishing one's own research team, including Ph.D. students and post-docs, would also be supported.

Particular topics of interest include (but are not limited to):

• Verifiable computing and zero-knowledge proofs
• Foundations & solutions for real-world cryptography
• Privacy-enhancing technologies

The cryptography and privacy group at IBM Research - Zurich offers an exciting research environment with the ability to cooperate with researchers working on various aspects of security and cryptography, including lattice-based cryptography, provably secure protocol design, blockchain, and system security.

Cooperation with other academic and industry researchers outside IBM, as well as acquisition of external research funding, e.g., European grants (including the ERC) is also possible and encouraged.

The positions offer a very competitive salary and the opportunity to live in the Zurich area, which is consistently ranked as one of the top 5 cities with the best quality of life.

Review of applications will begin mid-September and continue until the positions are filled. Ideally, the successful applicants would start in the beginning of 2019, but other possibilities can be negotiated.

Closing date for applications:

Contact: For informal enquiries please contact:

? Anja Lehmann (anj (at) zurich.ibm.com) and/or

? Vadim Lyubashevsky (vad (at) zurich.ibm.com).

To apply, please send your CV, including contact information for three references, to cryptojobs (at) zurich.ibm.com

Applications are invited for the post of Lecturer (teaching focussed) in the Information Security Group at Royal Holloway, University of London. The post is for 12 months and covers a period of parental leave.

The post holder will contribute to the creation and/or revision, delivery and assessment of postgraduate (MSc) and undergraduate teaching modules across a wide range of topics in the field of information/cyber security.

Applicants should have a Ph.D. in a relevant subject or equivalent and have a sound knowledge of information/cyber security. Applicants should be able to demonstrate an enthusiasm for teaching and communicating with diverse audiences, as well as show an awareness of contemporary issues relating to cyber security. See the URL for more details. The URL has a link to the online application form.

Closing date for applications: 2 September 2018

Contact:

Peter Komisarczuk

Email peter.komisarczuk (at) rhul.ac.uk

More information: https://jobs.royalholloway.ac.uk/vacancy.aspx?ref=0818-321

We construct a publicly verifiable non-interactive delegation scheme for log-space uniform bounded depth computations in the common reference string (CRS) model, where the CRS is long (as long as the time it takes to do the computation).

The soundness of our scheme relies on the assumption that there exists a group with a bilinear map, such that given group elements $g,h,h^t,h^{t^2},$ it is hard to output $g^a,g^b,g^c$ and $h^a,h^b,h^c$ such that $a \cdot t^2 + b \cdot t + c = 0$, but $a,b,c$ are not all zero.

Previously, such a result was only known under knowledge assumptions (or in the Random Oracle model), or under non-standard assumptions related to obfuscation or zero-testable homomorphic encryption.

We obtain our result by converting the interactive delegation scheme of Goldwasser, Kalai and Rothblum (J. ACM 2015) into a publicly verifiable non-interactive one. As a stepping stone, we give a publicly verifiable non-interactive version of the sum-check protocol of Lund, Fortnow, Karloff, Nisan (J. ACM 1992).

The Fiat-Shamir paradigm encompasses many different ways of turning a given identification scheme into a signature scheme. Security proofs pertain sometimes to one variant, sometimes to another. We systematically study three variants that we call the challenge (signature is challenge and response), commit (signature is commitment and response) and transcript (signature is challenge, commitment and response) variants. Our framework captures the variants via transforms that determine the signature scheme as a function of not only the identification scheme and hash function (to cover both standard and random oracle model hashing), but also what we call a signing algorithm, to cover both classical and with-abort signing. We relate the security of the signature schemes produced by these transforms, giving minimal conditions under which uf-security of one transfers to the other. To apply this comprehensively, we formalize linear identification schemes, show that many schemes in the literature are linear, and show that any linear scheme meets our conditions for the signature schemes given by the three transforms to have equivalent uf-security. Our results give a comprehensive picture of the Fiat-Shamir zoo and allow proofs of security in the literature to be transferred automatically from one variant to another.

We present threshold ring multi-signatures (thring signatures) for collaborative computation of ring signatures, discuss a game of existential forgery for thring signatures, and discuss the uses of thring signatures in digital currencies, including spender-ambiguous cross-chain atomic swaps for confidential amounts without a trusted set-up. We present an implementation of thring signatures inspired by the works of [13], [20], [14], [1], [18], and [15] we call linkable spontaneous threshold anonymous group (LSTAG) signatures, and we prove the implementation existentially unforgeable under the plain public key and random oracle models.

In this work, we construct a short one-out-of-many proof from (Module-SIS) lattices, allowing one to prove knowledge of a secret associated with one of the public values in a set. The proof system follows a combination of ideas from the efficient proposals in the discrete logarithm setting by Groth and Kohlweiss (EUROCRYPT '15) and Bootle et al. (ESORICS '15), can have logarithmic communication complexity in the set size and does not require a trusted setup.

Our work resolves an open problem mentioned by Libert et al. (EUROCRYPT '16) of how to efficiently adapt the above discrete logarithm proof techniques to the lattice setting. To achieve our result, we introduce technical tools for design and analysis of algebraic lattice-based zero-knowledge proofs, which may be of independent interest.

Using our proof system as a building block, we design a short lattice-based ring signature scheme. Our scheme offers post-quantum security and practical usability in cryptocurrencies and e-voting systems. Even for a very large ring size such as 1 billion, our ring signature size is only 4.5 MB for 100-bit security level compared to 166 MB in the best existing lattice-based result by Libert et al. (EUROCRYPT '16).