International Association
for Cryptologic Research

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).

LowMC is a block cipher family that is optimized for practical instantiations of multi-party computation, fully homomorphic encryption, and zero-knowledge proofs. It was designed in 2015 by Albrecht et al., and has recently become a substantial building block in several novel post-quantum cryptosystems. A large portion of LowMC instances use a relatively recent design strategy (initiated by G\`{e}rard et al. at CHES 2013) of applying the non-linear layer to only a part of the state in each round, where the shortage of non-linear operations is partially compensated by heavy linear algebra. Since the high linear algebra complexity has been a bottleneck in several applications, one of the open questions raised by the designers was to reduce it, without introducing additional non-linear operations (or compromising security).

In this paper, we consider LowMC instances with block size $n$, partial non-linear layers of size $s \leq n$ and $r$ encryption rounds. We show that when $s < n$, each LowMC instance belongs to a large class of equivalent instances. We then select a \emph{representative instance} from this class for which encryption (and decryption) can be implemented much more efficiently than for an arbitrary instance. This yields a new encryption algorithm that is equivalent to the standard one, but reduces the evaluation time and storage of the linear layers from $r \cdot n^2$ bits to about $r \cdot n^2 - (r-1)(n-s)^2$, which is a substantial improvement for small $s$ and a reasonable choice of $r$. For standard LowMC parameters, our new encryption algorithm achieves a reduction by a factor between 2 and 4, while for more extreme parameter choices (suggested by the designers) the reduction is by a factor of more than 140. Furthermore, our new encryption algorithm is applicable to all SP-networks with partial non-linear layers.

An additional unique feature of LowMC is that the linear layers of its instances are sampled at random. In the second part of the paper, we show how to reduce the sampling time and randomness complexities (i.e., the number of random bits used) by directly sampling representative instances. Finally, we formalize the notion of linear equivalence of block ciphers with partial non-linear layers and prove that the memory complexity of our encryption algorithm and the randomness complexity of our sampling algorithm are optimal.

We give a simple construction of indistinguishability obfuscation for Turing machines where the time to obfuscate grows only with the description size of the machine and otherwise, independent of the running time and the space used. While this result is already known [Koppula, Lewko, and Waters, STOC 2015], our construction and its analysis are conceptually much simpler. In particular, the main technical component in the proof of our construction is a simple combinatorial pebbling argument [Garg and Srinivasan, EUROCRYPT 2018]. Our construction makes use of indistinguishability obfuscation for circuits and laconic oblivious transfer.

We formulate and study the security of cryptographic hash functions in the backdoored random-oracle (BRO) model, whereby a big brother designs a "good" hash function, but can also see arbitrary functions of its table via backdoor capabilities. This model captures intentional (and unintentional) weaknesses due to the existence of collision-finding or inversion algorithms, but goes well beyond them by allowing, for example, to search for structured preimages. The latter can easily break constructions that are secure under random inversions.

BROs make the task of bootstrapping cryptographic hardness somewhat challenging. Indeed, with only a single arbitrarily backdoored function no hardness can be bootstrapped as any construction can be inverted. However, when two (or more) independent hash functions are available, hardness emerges even with unrestricted and adaptive access to all backdoor oracles. At the core of our results lie new reductions from cryptographic problems to the communication complexities of various two-party tasks. Along the way we establish a communication complexity lower bound for set-intersection for cryptographically relevant ranges of parameters and distributions and where set-disjointness can be easy.

Almost perfect nonlinear (APN) functions over fields of characteristic 2 play an important role in cryptography, coding theory and, more generally, information theory as well as mathematics. Building new APN families is a challenge which has not been successfully addressed for more than seven years now. The most general known equivalence relation preserving APN property in characteristic 2 is CCZ-equivalence. Extended to general characteristic, it also preserves planarity. In the case of quadratic planar functions, it is a particular case of isotopic equivalence. We apply the idea of isotopic equivalence to transform APN functions in characteristic 2 into other functions, some of which can be APN. We deduce new quadratic APN functions and a new quadratic APN family.

We present and analyze the performance of DRANKULA, a McEliece-like cryptosystem implementation using \textit{rank metric} instead of Hamming distance. Namely, we use the scheme proposed by Loidreau in PQCrypto 2017 using Gabidulin codes. We propose a set of carefully selected parameters and we address several non-trivial issues when porting this scheme into real-world systems as, for example, the generation of errors of a given rank. We provide the pseudo-code of the core algorithms of the cryptosystem. In addition, we also show code optimization when special instructions like Carry-less multiplications are available. Moreover, we argue how to have a practical and side-channel resistant version of the cryptosystem. We integrated the scheme in Open Quantum Safe and benchmarked it against the other schemes implemented there. Our results show that DRANKULA can be a practical alternative to other well-known quantum-safe schemes.

As part of a joint project between the University of South Florida (USF, based in Tampa) and Florida Atlantic University (FAU, based in Boca Raton), we expect to hire two postdocs for 2 years each. The starting date is negotiable (immediate start is possible).

The areas of interest are

• Lattice based cryptography.
• Isogeny-based cryptography.
• Cryptocurrencies.
• Classical and quantum cryptanalysis.

The person recruited at USF will report to Dr. Jean-Francois Biasse. They will work on fundamental aspects of the aforementioned topics and be hired by the Mathematics department. The annual salary will be $47,659

The person recruited at FAU will report to Dr Reza Azarderakhsh. They will work on efficient implementations related to the topics of interests, with an emphasis on hardware solutions. They will be hired by the Department of Computer and Electrical Engineering and Computer Science. The annual salary will be $50,000.

If you are interested in either position, please send a CV and a 1 page research statement to usf.fau.crypto.postdoc (at) gmail.com.

Review of applications will start immediately and will continue until both positions are filled.

Closing date for applications: 31 December 2018

This document presents Xoodoo, a 48-byte cryptographic permutation that allows very efficient symmetric crypto on a wide range of platforms and a suite of cryptographic functions built on top of it. The central function in this suite is Xoofff, obtained by instantiating Farfalle with Xoodoo. Xoofff is what we call a deck function and can readily be used for MAC computation, stream encryption and key derivation. The suite includes two session authenticated encryption (SAE) modes: Xoofff-SANE and Xoofff-SANSE. Both are built on top of Xoofff and differ in their robustness with respect to nonce misuse. The final members of the suite are a tweakable wide block cipher Xoofff-WBC and authenticated encryption mode Xoofff-WBC-AE, obtained by instantiating the Farfalle-WBC and Farfalle-WBC-AE constructions with Xoofff. This paper is a specification and security claim reference for the Xoodoo suite. It is a standing document: over time, we may extend the Xoodoo suite, e.g., with a hash function or a dedicated lightweight MAC function and we will update it accordingly.

Event date: 10 October 2018