International Association
for Cryptologic Research

The School of Electrical Engineering and Computer Science at Oregon State University invites applications for one or more full time nine-month tenure-track faculty positions in the area of data science and engineering broadly construed. Subareas of interest include (but are not limited to) databases and data management, visualization and visual analytics, security, data mining, and signal processing for big data. The appointments are anticipated at the Assistant Professor rank, but exceptionally strong candidates may be considered at the rank of Associate Professor or Professor.

For full consideration, apply online by February 15, 2016.

Closing date for applications: 15 February 2016

Contact: Brenda Langley, Brenda.Langley (at) oregonstate.edu

More information: http://jobs.oregonstate.edu/applicants/Central?quickFind=68792

Universal hashing, discovered by Carter and Wegman in 1979, has many important applications in computer science. The following family, called MMH$^*$ by Halevi and Krawczyk in 1997, is well known: Let $p$ be a prime and $k$ be a positive integer. Define \begin{align*} \text{MMH}^*:=\lbrace g_{\mathbf{x}} \; : \; \mathbb{Z}_p^k \rightarrow \mathbb{Z}_p \; | \; \mathbf{x}\in \mathbb{Z}_p^k \rbrace, \end{align*} where \begin{align*} g_{\mathbf{x}}(\mathbf{m}) := \mathbf{m} \cdot \mathbf{x} \pmod{p} = \sum_{i=1}^k m_ix_i \pmod{p}, \end{align*} for any $\mathbf{x}=\langle x_1, \ldots, x_k \rangle \in \mathbb{Z}_p^k$, and any $\mathbf{m}=\langle m_1, \ldots, m_k \rangle \in \mathbb{Z}_p^k$. In this paper, we first give a new proof for the $\triangle$-universality of MMH$^*$, shown by Halevi and Krawczyk in 1997, via a novel approach, namely, connecting the universal hashing problem to the number of solutions of (restricted) linear congruences. We then introduce a new hash function family --- a variant of MMH$^*$ --- that we call GRDH, where we use an arbitrary integer $n>1$ instead of prime $p$ and let the keys $\mathbf{x}=\langle x_1, \ldots, x_k \rangle \in \mathbb{Z}_n^k$ satisfy the conditions $\gcd(x_i,n)=t_i$ ($1\leq i\leq k$), where $t_1,\ldots,t_k$ are given positive divisors of $n$. Applying our aforementioned approach, we prove that the family GRDH is an $\varepsilon$-almost-$\triangle$-universal family of hash functions for some $\varepsilon<1$ if and only if $n$ is odd and $\gcd(x_i,n)=t_i=1$ $(1\leq i\leq k)$. Furthermore, if these conditions are satisfied then GRDH is $\frac{1}{p-1}$-almost-$\triangle$-universal, where $p$ is the smallest prime divisor of $n$. Finally, as an application of our results, we give a generalization of the authentication code with secrecy studied by Alomair, Clark, and Poovendran.

In this paper, using properties of Ramanujan sums and of the discrete Fourier transform of arithmetic functions, we give an explicit formula for the number of solutions of the linear congruence $a_1x_1+\cdots +a_kx_k\equiv b \pmod{n}$, with $\gcd(x_i,n)=t_i$ ($1\leq i\leq k$), where $a_1,t_1,\ldots,a_k,t_k, b,n$ ($n\geq 1$) are arbitrary integers. Some special cases of this problem have been already studied in many papers. The problem is very well-motivated and in addition to number theory has intriguing applications in combinatorics, computer science, and cryptography, among other areas.

Pseudorandom functions (PRFs) are one of the most fundamental building blocks in cryptography with numerous applications such as message authentication codes and private key encryption. In this work, we propose a new paradigm to construct PRFs with the overall goal to build efficient PRFs from standard assumptions with an almost tight proof of security. We start from a PRF for any small domain (i.e.~poly-sized domain) and we turn it into a bounded pseudorandom functions (bPRF). Recall that a function $F$ is an $\ell$-bounded pseudorandom function, if the outputs of $F$ are pseudorandom for the first $\ell$ distinct queries to $F$. In the second step, we apply a novel technique which we call \emph{on-the-fly adaptation} that turns any bPRF into a fully-fledged (large domain) PRF. Both steps of our paradigm have a tight security reduction, meaning that any successful attacker can be turned into an efficient algorithm for the underlying hard computational problem without any significant increase in the running time or loss of success probability.

Instantiating our paradigm with specific number theoretic assumptions, we construct a PRF based on $k$-LIN (and thus DDH) that is faster than all known constructions, which reduces almost tightly to the underlying problem, and which has shorter keys. Instantiating our paradigm with general assumptions, we construct a PRF with very flat circuits whose security almost tightly reduces to the security of some small domain PRF. As an exemplifying instance, we use the PRF of Banerjee, Peikert, and Rosen (EUROCRYPT'12) based on LWE, as the underlying small domain PRF and we obtain a construction that is secure (for large domains) under a weaker assumption, with a tighter proof of security, and the resulting circuit is shallower than instantiating the BPR scheme with a large domain directly.

This paper introduces a new central trapdoor for multivariate quadratic (MQ) public-key cryptosystems that allows for encryption, in contrast to time-tested MQ primitives such as Unbalanced Oil and Vinegar or Hidden Field Equations which only allow for signatures. Our construction is a mixed-field scheme that exploits the commutativity of the extension field to dramatically reduce the complexity of the extension field polynomial implicitly present in the public key. However, this reduction can only be performed by the user who knows concise descriptions of two simple polynomials, which constitute the private key. After applying this transformation, the plaintext can be recovered by solving a linear system. We use the minus and projection modifiers to inoculate our scheme against known attacks. A straightforward C++ implementation confirms the efficient operation of the public key algorithms.

We present an efficient method for answering one-dimensional range and closest-point queries in a verifiable and privacy-preserving manner. We consider a model where a data owner outsources a dataset of key-value pairs to a server, who answers range and closest-point queries issued by a client and provides proofs of the answers. The client verifies the correctness of the answers while learning nothing about the dataset besides the answers to the current and previous queries. Our work yields for the first time a zero-knowledge privacy assurance to authenticated range and closest-point queries. Previous work leaked the size of the dataset and used an inefficient proof protocol. Our construction is based on hierarchical identity-based encryption. We prove its security and analyze its efficiency both theoretically and with experiments.

The Chaskey MAC algorithm was presented by Mouha et al. at SAC 2014. It is designed for real-world applications where 128-bit keys are required, but standard cryptographic algorithms cannot be implemented because of stringent requirements on speed, energy consumption, or code size. Shortly after its publication, Chaskey was considered for standardization by ISO/IEC JTC 1/SC 27/WG 2. At the October 2015 meeting, the ISO/IEC committee decided to terminate the study period on Chaskey, and to circulate a first working draft. Since Chaskey was introduced, many follow-up results were published, including improved cryptanalysis results, new security proofs and more efficient implementations. This paper gives a comprehensive overview of those results, and introduces a twelve-round variant of Chaskey: Chaskey-12. Although the original eight-round Chaskey remains unbroken, Chaskey-12 has a much more conservative design, while reducing the performance by only 15% to 30%, depending on the platform.

Stream ciphers based on Linear Feedback Shift Registers (LFSRs) have faced algebraic attacks. To avoid this kind of attacks, Feedback with Carry Shift Registers (FCSRs) have been proposed as an alternative. In order to eliminate a so-called LFSRization weakness, FCSRs have been implemented using ring representation instead of the Galois one. A ring FCSR is determined by its transition matrix $A$. Its connection integer, which is related to the properties of the output sequences, is $q=\mbox{det}(I-2A)$. In this paper, we show how to calculate the determinant $\mbox{det}(I-2A)$ of transition matrices with a critical path of length 1 and fan-out 2. Moreover, we propose algorithms to construct such transition matrices (binary case) based on searching target connection integers.

The cryptography group at the Institute of Science and Technology Austria, located in the Vienna woods and headed by Krzysztof Pietrzak, is looking for excellent and highly motivated PhD students and Postdoc researchers. The research topics currently investigated in our group include

• Cryptocurrencies
• Leakage-Resilient Cryptography
• Symmetric Cryptography
• Computational Entropy (aka Pseudoentropy)
• Adaptive Security
• Memory-Hard Functions

Interested PhD students are expected to have a very strong background in mathematics and/or computer science and must apply via the IST Austria graduate school (http://ist.ac.at/graduate-school), the deadline for applications to the graduate school is January 8, 2016.

Postdocs applicants are expected to have a solid publication record in cryptography, including at least some papers in top crypto or TCS conferences like Crypto, Eurocrypt, TCC, FOCS, STOC, ICALP,... and should contact Krzysztof Pietrzak directly ( pietrzak (at) ist.ac.at )

Closing date for applications: 8 January 2016

Contact: Krzysztof Pietrzak
https://ist.ac.at/research/research-groups/pietrzak-group/
pietrzak (at) ist.ac.at

More information: http://pub.ist.ac.at/crypto/

Job Description: Northern Arizona University is launching a Cyber-Security research program focusing at first on hardware authentication, and the design of secure circuits with embedded secure memories, Physically Unclonnable Functions (PUFs), Random Number Generators (RNG), and crypto-processors.

The Job responsibilities include but are not limited to:

• Design memory state machines with FPGA (or/and ASIC) and surrounding analog interface to drive the PUFs, RNG, and other cryptographic functions.
• Design micro-controller based test board to emulate full authentication, Challenges and Responses of the PUFs, and extract Challenge/Response Pair error rate
• Conduct autonomous research work to study innovative architectures
• Consider ways to test the new structures, and incorporate Build In Self Test (BIST) in the state machine

Minimum Qualifications:

• Earned PhD in Electrical Engineering, Microelectronics, or related field by the time of the appointment

Preferred Qualifications:

• Demonstrated experience in at least one of the following field: mixed mode design, memory design, state machine architecture, BIST,
• Experience in installing and debugging FPGA boards, and micro-controller systems, including embedded software
• Strong publication record
• Experience and/or commitment to work effectively with NAU’s diverse faculty, staff, and student populations.

Knowledge Skills and Abilities:

• Proficiency in using ASIC or FPGA software development tools
• Ability to understand hardware architecture and VHDL design methodology
• Understanding how the basic operations of a memory state machine operate: Read, Program, Erase
• Creative, and independent
• Ability to work effectively in diverse, interdisciplinary research environment

Closing date for applications: 29 January 2016

Contact: Bertrand Cambou, Bertrand.cambou (at) nau.edu

More information: http://nau.edu/Human-Resources/Careers/Staff-Welcome-Page/

Event date: 9 June to 10 June 2016
Submission deadline: 4 March 2016
Notification: 4 May 2016

The CWI Cryptology Group is looking for a post-doc with a very strong research record in the area of lattice-based cryptography (design and/or cryptanalysis). The position is opened in connection with a fundamental, practise-oriented research project that will start early 2016 and that is carried out in collaboration with an industrial partner. The duration of the initial contract is one year, with possible extension. To apply, submit a CV with a cover-letter by email to the addresses listed below.

Closing date for applications: 29 February 2016

Contact:

Ronald Cramer (Head of the CWI Cryptology Group & Professor, Math Inst, Leiden U.) and Leo Ducas (Scientific Staff Member, CWI Cryptology Group).

Email: {cramer,ducas}@cwi.nl

This paper presents Secure Comparator, a way to implement Zero Knowledge Proof algorithm called Socialist Millionaire’s Problem, to compare secrets between two parties. Compared to existing implementations, Secure Comparator provides better security guarantees, stronger cryptographic math, and, possibly, more integration-friendly architecture.

The security of pairing-based cryptography is based on the hardness of solving the discrete logarithm problem (DLP) over extension field F_{p^n} of characteristic p and degree n. Joux et al. proposed an asymptotically fastest algorithm for solving DLP over F_{p^n} (JLSV06-NFS) as the extension of the number field sieve over prime field F _p (JL03-NFS). The lattice sieve is often used for a large-scaled experiment of solving DLP over F_p by the number field sieve. Franke and Kleinjung proposed a 2-dimensional lattice sieve which efficiently enumerates all the points in a given sieve region of the lattice. However, we have to consider a sieve region of more than 2 dimensions in the lattice sieve of JLSV06-NFS. In this paper, we extend the Franke-Kleinjung method to 3-dimensional sieve region. We construct an appropriate basis using the Hermite normal form, which can enumerate the points in a given sieve region of the 3-dimensional lattice. From our experiment on F_{p^{12}} of 303 bits, we are able to enumerate more than 90\% of the points in a sieve region in the lattice generated by special-q. Moreover, we implement the number field sieve using the proposed 3-dimensional lattice sieve. Our implementation of the JLSV06 over F_{p^6} of 240 bits is about as efficient as that of the current record over F_{p^6} using 3-dimensional line sieve by Zajac.

We present a new non-malleable commitment protocol. Our protocol has the following features:

\begin{itemize} \item The protocol has only \emph{three rounds} of interaction. Pass (TCC 2013) showed an impossibility result for a two-round non-malleable commitment scheme w.r.t. a black-box reduction to any ``standard" intractability reduction. Thus, this resolves the round complexity of non-malleable commitment at least w.r.t. black-box security reductions. Our construction is secure as per the standard notion of non-malleability w.r.t. commitment.

\item Our protocol is \emph{truly efficient}. In our basic protocol, the entire computation of the committer is dominated by just three invocations of a non-interactive statically binding commitment scheme, while, the receiver computation (in the commitment stage) is limited to just sampling a random string. Unlike many previous works, we directly construct a protocol for large tags and hence avoid any non-malleability amplification steps.

\item Our protocol is based on a black-box use of any non-interactive statistically binding commitment scheme. Such schemes, in turn, can be based on any one-to-one one-way function (or any one-way function at the cost of an extra initialization round). Previously, the best known black-box construction of non-malleable commitments required a larger (constant) number of rounds.

\item Our construction is public-coin and makes use of only black-box simulation. Prior to our work, no public-coin constant round non-malleable commitment schemes were known based on black-box simulation.

\end{itemize}

Our techniques depart \emph{significantly} from the techniques used previously to construct non-malleable commitment schemes. As a main technical tool, we rely on non-malleable codes in the split state model. Our proofs of security are purely combinatorial in nature.

In addition, we also present a simple construction of constant round non-malleable commitments from any one-way function. While this result is not new, the main feature is its simplicity compared to \emph{any} previous construction of non-malleable commitments (in any number of rounds). We believe the construction is simple enough to be covered in a graduate level course on cryptography. The construction uses non-malleable codes in the split state model in a black-box way.

Telegram is a popular messaging app which supports end-to-end encrypted communication. In Spring 2015 we performed an audit of Telegram's source code. This short paper summarizes our findings.

Our main discovery is that the symmetric encryption scheme used in Telegram -- known as MTProto -- is not IND-CCA secure, since it is possible to turn any ciphertext into a different ciphertext that decrypts to the same message.

We stress that this is a theoretical attack on the definition of security and we do not see any way of turning the attack into a full plaintext-recovery attack. At the same time, we see no reason why one should use a less secure encryption scheme when more secure (and at least as efficient) solutions exist.

The take-home message (once again) is that well-studied, provably secure encryption schemes that achieve strong definitions of security (e.g., authenticated-encryption) are to be preferred to home-brewed encryption schemes.

Private query processing is a very attractive problem in the fields of both cryptography and databases. In this work, we restrict our attention to the efficiency aspect of the problem, particularly for basic queries with conditions on various combinations of equality. Without loss of generality, these conditions can be regarded as a Boolean function, and this Boolean function can then be evaluated at ciphertexts produced by a fully homomorphic encryption (FHE) scheme without decryption. From the efficiency perspective, the remaining concern is to efficiently test the equality function without severely downgrading the performance of FHE-based querying solutions.

To this end, we first analyze the multiplicative depth required for an equality test algorithm with respect to the plaintext space inhabited by general FHE schemes. The primary reason for this approach is that given an equality test algorithm, its efficiency is measured in terms of the multiplicative depth required to construct its arithmetic circuit expression. Indeed, the implemented equality test algorithm dominates the entire performance of FHE-based query solutions, apart from the performance of the underlying FHE scheme. Then, we measure the multiplicative depth considering an FHE scheme that takes an extension field as its plaintext space and that supports the depth-free evaluation of Frobenius maps. According to our analysis, when the plaintext space of an FHE scheme is a field of characteristic $2$, the equality test algorithm for $\ell$-bit messages requires the lowest multiplicative depth $\lceil\log{\ell}\rceil$. Furthermore, we design a set of private query protocols for conjunctive, disjunctive, and threshold queries based on the equality test algorithm. Similarly, applying the equality test algorithm over $\F_{2^{\ell}}$, our querying protocols require the minimum depths. More specifically, a multiplicative depth of $\lceil\log{\ell}\rceil+\lceil\log{(1+\rho)}\rceil$ is required for conjunctive and disjunctive queries, and a depth of $\lceil\log{\ell}\rceil+2\lceil\log{(1+\rho)}\rceil$ is required for threshold conjunctive queries, when their query conditions have $\rho$ attributes to be compared. Finally, we provide a communication-efficient version of our solutions, though with additional computational costs, when an upper bound $\delta$~($0\leq \delta\leq 1$) on the selectivity of a database is given. Consequently, we reduce the communication cost from $n$ to approximately $\lfloor\delta n\rfloor$ ciphertexts with $\lceil\log{n}\rceil$ additional depth when the database consists of $n$ tuples.

Event date: 20 April to 22 April 2016
Submission deadline: 15 January 2016

Event date: 16 March to 18 March 2016
Submission deadline: 23 December 2015

This position requires a sound academic background in both analytical and theoretical fields. The positions will primarily focus on work such as characterizing secure data communications in terms of encryption, encoding and other signal modifications and then providing the necessary technical elaboration to help engineering teams develop and implement techniques to efficiently handle these signals.

In this position, it would be a requirement to develop mathematical techniques to find solutions and then implement the solutions as efficiently as possible in both computer hardware and software. These techniques will also be used to evaluate cryptographic algorithms and protocols as well as provide guidance on the design and development of cryptographic systems. Areas of mathematics particularly applicable to this position at CipherQ include:

• Abstract algebra (especially finite field theory)
• Computational number theory
• Linear algebra and numerical methods
• Statistics
• Combinatorics
• Cryptography and Applied Cryptanalysis
• Theoretical computer science

Expertise and applied knowledge of modern cryptographic algorithms and protocols is a mandatory requirement. Additional capabilities in cryptography that will be an asset include but are not limited to:

• Lattice-based
• Multivariate
• Hash-based
• Code-based
• Discrete Finite Fields and Elliptic Curves
• Quantum key distribution

Other areas of knowledge that would be considered key assets:

• Strong knowledge of computer programming languages: C/C++, Java, Python, Octave/Mathematica/Maple/Matlab environments.
• Knowledge of telecommunications and networking principles
• An understanding of modern computer architectures and information technology architectures including cloud computing

Education: Doctoral degree in Mathematics, or equivalent degree in other mathematical sciences or engineeri

Closing date for applications: 31 March 2016

Contact: Dr. Christian Weedbrook