International Association
for Cryptologic Research

Event date: 1 June to 5 June 2020
Submission deadline: 31 January 2020
Notification: 29 February 2020

A canonical identification (CID) scheme is a 3-move protocol consisting of a commitment, challenge, and response. It constitutes the core design of many cryptographic constructions such as zero-knowledge proof systems and various types of signature schemes. Unlike number-theoretic constructions, CID in the lattice setting usually forces provers to abort and repeat the whole authentication process once the distribution of the computed response does not follow a target distribution independent from the secret key. This concept has been realized by means of rejection sampling, which makes sure that the secrets involved in a protocol are concealed after a certain number of repetitions. This however has a negative impact on the efficiency of interactive protocols because it leads to a number of communication rounds that is multiplicative in the number of aborting participants (or rejection sampling procedures). In this work we show how the CID scheme underlying many lattice-based protocols can be designed with smaller number of aborts or even without aborts. Our new technique exploits (unbalanced) binary hash trees and thus significantly reduces the communication complexity. We show how to apply this new method within interactive zero-knowledge proofs. We also present BLAZE+: a further application of our technique to the recently proposed lattice-based blind signature scheme BLAZE (FC20). We show that BLAZE+ has an improved performance and communication complexity compared to BLAZE while preserving the size of signatures.

The GPV construction [GPV08] presents a generic construction of signature schemes in the Hash and Sign paradigm. This construction requires a family F of trapdoor preimage sampleable functions (TPSF). In this work we extend this notion to the weaker Average TPSF (ATPSF) and show that the GPV construction also holds for ATPSF in the Random Oracle Model. We also introduce the problem of finding a Claw with a random function (Claw(RF)) and present a tight security reduction to the Claw(RF) problem. Our reduction is also optimal meaning that an algorithm that solves the Claw(RF) problem breaks the scheme. We extend these results to the quantum setting and prove this same tight and optimal reduction in the QROM. Finally, we apply these results to code-based signatures, notably the Wave signature scheme and prove tight and optimal reductions for it in the ROM and the QROM improving and extending the original analysis of [DST19a]

Lai-Massey scheme is a well-known block cipher structure which has been used in the design of the ciphers PES, IDEA, WIDEA, FOX and MESH. Recently, the lightweight block cipher FLY applied this structure in the construction of a lightweight $8 \times 8$ S-box from $4 \times 4$ ones. In the current paper, firstly we investigate the linear, differential and algebraic properties of the general form of S-boxes used in FLY, mathematically. Then, based on this study, a new cipher structure is proposed which we call generalized Lai-Massey scheme or GLM. We give upper bounds for the maximum average differential probability (MADP) and maximum average linear hull (MALH) of GLM and after examination of impossible differentials and zero-correlations of one round of this structure, we show that two rounds of GLM do not have any structural impossible differentials or zero-correlations. As a measure of structural security, we prove the pseudo-randomness of GLM by the H-coefficient method.

Privacy-preserving currency exchange between different cryptocurrencies on blockchain remains an open problem as the existing currency exchange schemes cannot provide anonymity of users or confidentiality of exchange amount. To solve this problem, we introduce BPCEX: a privacy-preserving currency exchange scheme which protects users' identities and the exchange amount, by usage of techniques including linkable ring signature, range proof, Diffie-Hellman key exchange, Pedersen commitment and UTXO swap. In BPCEX, the users' identities are hidden to verifiers and dealmakers, while the exchange amounts are hidden to the verifiers. BPCEX supports floating exchange rate, partial deal and public verification, without additional confirmation of traders, which improves the success rate and shortens the waiting time of the deal. Moreover, BPCEX is compatible with the regulatable privacy-preserving blockchain system, which realizes the traceability of users' identities and the exchange amount to prevent money laundering and illegal exchange, making BPCEX suitable in real-life applications, including currency market and stock market.

Traceable range proof (TRP) plays a major role in the construction of regulatable privacy-preserving blockchains, as it empowers regulators with traceability of the hidden amount in each transaction. In this paper, we give new constructions of TRPs with improved efficiency and more regulatory functions. In particular, we introduce sTBoRP: a simplified traceable Borromean range proof directly from Borromean ring signature without additional validity proofs for tracing keys, sTBoRP can be applied for multiple regulation between different regulators, and can be further modified to be secure against malicious regulators. Moreover, we introduce jTBuRP: a modified traceable Bulletproofs range proof to support joint regulation against collusion attack of malicious regulators, by improving the generation algorithm of tracing keys. We also give the security proofs for both schemes and give the comparisons of efficiency and security.

Let $f:\{-1,1\}^n\rightarrow \{-1,1\}$ be with total degree $d$, and $\widehat{f}(i)$ be the linear Fourier coefficients of $f$. The relationship between the sum of linear coefficients and the total degree is a foundational problem in theoretical computer science. In 2012, O'Donnell Conjectured that \[ \sum_{i=1}^n \widehat{f}(i)\le d\cdot {d-1 \choose \lfloor\frac{d-1}{2}\rfloor}2^{1-d}. \] In this paper, we prove that the conjecture is equivalent to a conjecture on the cryptographic Boolean function. We then prove that the conjecture is true for $d=1,n-1$. Moreover, we count the number of $f$'s such that the upper bound is achieved.

Event date: 24 May to 26 May 2020

Constructing an elliptic curve of prime order has a significant role in elliptic curve cryptography. For security purposes, we need an elliptic curve of almost prime order. In this paper, we propose an efficient technique to generate an elliptic curve of nearly prime order. In practice, this algorithm produces an elliptic curve of order 2 times a prime number. Therefore, these elliptic curves are appropriate for practical uses. Presently, the most known working algorithms for generating elliptic curves of prime order are based on complex multiplication. The advantages of the proposed technique are: it does not require a deep mathe- matical theory, it is easy to implement in any programming language and produces an elliptic curve with a remarkably simple expression.

We provide an inclusive environment and are committed to a recruitment process free from discrimination. We believe that supporting a variety of career trajectories is vital for world class computer science to flourish. The post holder will create and disseminate knowledge through initiating and conducting original research, through publication and by seeking external funding, and through developing and delivering undergraduate and postgraduate programmes in computer security, and computer science. They may also seek non-academic impact, recognising the importance of Computer Science to society. They will also contribute to the School’s operation through management, leadership and enterprise activities, and other School events. The successful candidate will normally hold a higher degree (usually PhD) in computer science, engineering, mathematics or a closely related field, or equivalent qualifications or experience. They will have significant research experience and it would be beneficial if they can demonstrate an ability to balance long-term fundamental research with short-term applied projects. A growing international research record in computer science (or related inter-disciplinary areas), evident from publications in leading international conferences and journals, is required. Candidates must have the ability to design, deliver, assess and revise teaching programmes and be experienced in developing appropriate approaches to learning and teaching. They will also have the ability to contribute to School/Departmental management processes. To download the full job description and details of this position and submit an electronic application online please click on the Apply Online button below or visit https://www.birmingham.ac.uk/staff/jobs/index.aspx

Closing date for applications:

Contact: Kate Campbell, k.campbell.1@bham.ac.uk

More information: http://www.download.bham.ac.uk/vacancies/jd/95549.pdf

An opportunity has arisen for a 3-year postdoctoral researcher to be appointed as soon as possible. The candidate will be concerned with design and analysis of different cryptographic primitives and protocols. Examples may include lightweight identification and authentication protocols, key management protocols providing long-term security, incremental cryptographic primitives, and quantum-secure protocols based on different post-quantum primitives. Technique of formal analysis, including reductionist security and suitable symbolic analysis methods, may be used.

The candidate will work on a project entitled "Lightweight Cryptography for Future Smart Networks" funded by the Norwegian Research Council. The project will develop new primitives and protocols for lightweight cryptography fitting the needs of the two critical and strongly related future network architectures, IoT and 5G.

Postdoctoral candidates are normally remunerated from NOK 515 200 before tax per year. Completion of a doctoral degree in cryptology or network security is required.

Applicants should send an expression of interest to Colin Boyd together with a recent CV.

Closing date for applications:

Contact: Prof Colin Boyd

The Cryptanalysis Taskforce at Nanyang Technological University in Singapore led by Prof. Jian Guo is seeking for candidates to fill 3 postdoctoral research fellow positions on symmetric-key cryptography, including but not limited to the following sub-areas:

• tool aided cryptanalysis, such as MILP, CP, STP, and SAT
• machine learning aided cryptanalysis and designs
• privacy-preserving friendly symmetric-key designs
• quantum cryptanalysis
• cryptanalysis against SHA-3 and AES

Established in 2014, the Cryptanalysis Taskforce is a group dedicated for research in symmetric-key cryptography. Since then, the team has been active in both publications in and services for IACR. It has done quite some cryptanalysis work on targets such as SHA-3, and is expanding its interests to the areas mentioned above, with strong funding support from the university and government agencies in Singapore. We offer competitive salary package with extremely low tax, as well as excellent environment dedicating for research in Singapore. The contract will be initially for 2 years, and has the possibility to be extended. Candidates are expected to have proven record of publications in IACR conferences. Interested candidates are to send their CV and 2 reference letters to Jian Guo. Review of applicants will start immediately until the positions are filled. More information about the Cryptanalysis Taskforce research group can be found via http://team.crypto.sg

Closing date for applications:

Contact: Asst Prof. Jian Guo, guojian@ntu.edu.sg

More information: http://team.crypto.sg

Juan de la Cierva Grants 2019 for Young Doctors – Call for Expression of Interest The Research group on Cryptology and Information Security (GiCSI) of the Spanish National Research Council is seeking highly motivated professionals in conducting research in the area of blockchain-based protocols, security protocols, cryptographic privacy-enhancing technologies, data curation protocols and fake news detection. There are two types of Juan de la Cierva grants: Juan de la Cierva Training Grants (Juan de la Cierva-Formación) are aimed at candidates that have been awarded their PhD between 01/01/2018 and 31/12/2019. These grants are aimed to complete their postdoctoral research training in Spanish R&D centers other than those in which they carried out their predoctoral training. Juan de la Cierva Incorporation Grants (Juan de la Cierva-Incorporación) are aimed at those who were awarded their PhD between 01/01/2015 and 31/12/2017. These grants are intended to strengthen the grantee’s acquired skills during a first stage of postdoctoral training. Interested candidates are encouraged to contact us as soon as possible. Deadline: 18/12/2019-15/01/2020 Contact: David Arroyo, david.arroyo (at) cscic.es

Closing date for applications:

Contact: David Arroyo Guardeño, email: david.arroyo (at) csic.es

More information: http://www.ciencia.gob.es/portal/site/MICINN/menuitem.791459a43fdf738d70fd325001432ea0/?vgnextoid=909662ecfa1de610VgnVCM

We introduce new authenticated key exchange protocols which on one hand do not resort to standard public key setups with corresponding assumptions of computationally hard problems, but on the other hand are more efficient than distributing symmetric keys among the participants. To this end, we rely on a trusted central authority distributing key material which size is independent of the total number of users, and which allows the users to obtain shared secret keys. We analyze the security of our construction taking into account various attack models. Importantly, only symmetric primitives are needed in the protocol making it an alternative to quantum-safe key exchange protocols which rely on hardness assumptions.

The videos of talks at CHES 2019 are now on the IACR YouTube channel

Recently, Srinath and Chandrasekaran have proposed an undeniable blind signature scheme (UBSS) from supersingular isogeny to provide signer’s control in a quantum-resistant blind signature. However, certain weaknesses of undeniable signature have already been observed and have been overcome by formalizing the designated verifier signature (DVS). In this paper, we explore the possibility of generic construction of a DVS from hard homogeneous spaces. Further, following this motivation, we realize a quantum-resistant designated verifier blind signature (DVBS) scheme based on supersingular isogenies from the proposed generic construction. In contrast to the UBSS, our construction do not require interactive communication between the signer and the verifier, yet engages the signer in the verification. The compact signature adds more security properties in a quantum-resistant blind signature to be useful in specific applications including electronic tendering, online auctions etc.

The Shell sort algorithm is one of the most practically effective sorting algorithms. However, it is difficult to execute this algorithm with its intended running time complexity on data encrypted using fully homomorphic encryption (FHE), because the insertion sort in Shell sort has to be performed by considering the worst-case input data. In this paper, in order for the sorting algorithm to be used on FHE data, we modify the Shell sort with an additional parameter $\alpha$ and a gap sequence of powers of two. The modified Shell sort is found to have the trade-off between the running time complexity of $O(n^{3/2}\sqrt{\alpha+\log\log n})$ and the sorting failure probability of $2^{-\alpha}$. Its running time complexity is close to the intended running time complexity of $O(n^{3/2})$ and the sorting failure probability can be made very low with slightly increased running time. Further, the optimal window length of the modified Shell sort is also derived via convex optimization. The proposed analysis of the modified Shell sort is numerically confirmed by using randomly generated arrays. Further, the performance of the modified Shell sort is numerically compared with the case of Ciura's optimal gap sequence and the case of the optimal window length obtained through the convex optimization.

In 2020 Xin et al.proposed a new identity-based quantum signature based on Bell states scheme. By using a one-time padding (OTP) for both-side transfer operations like, "XOR", Hadamard H, and Y, they confirmed the security of the proposed scheme. However, after analyses, we found that the scheme cannot resist both the existing forgery attack and meaningful message attack. Therefore, we modified their scheme to include the required security, unforgeability, which is very important in quantum signature scheme.

At CRYPTO '12, Landecker et al. introduced the cascaded LRW2 (or CLRW2) construction, and proved that it is a secure tweakable block cipher up to roughly $ 2^{2n/3} $ queries. Recently, Mennink presented a distinguishing attack on CLRW2 in $ 2n^{1/2}2^{3n/4} $ queries. In the same paper, he discussed some non-trivial bottlenecks in proving tight security bound, i.e. security up to $ 2^{3n/4} $ queries. Subsequently, he proved security up to $ 2^{3n/4} $ queries for a variant of CLRW2 using $ 4 $-wise independent AXU assumption and the restriction that each tweak value occurs at most $ 2^{n/4} $ times. Moreover, his proof relies on a version of mirror theory which is yet to be publicly verified. In this paper, we resolve the bottlenecks in Mennink's approach and prove that the original CLRW2 is indeed a secure tweakable block cipher up to roughly $ 2^{3n/4} $ queries. To do so, we develop two new tools: first, we give a probabilistic result that provides improved bound on the joint probability of some special collision events; second, we present a variant of Patarin's mirror theory in tweakable permutation settings with a self-contained and concrete proof. Both these results are of generic nature, and can be of independent interests. To demonstrate the applicability of these tools, we also prove tight security up to roughly $ 2^{3n/4} $ queries for a variant of DbHtS, called DbHtS-p, that uses two independent universal hash functions.

Verifiable outsourcing systems offload a large computation to a remote server, but require that the remote server provide a succinct proof, called a SNARK, that proves that the server carried out the computation correctly. Real-world applications of this approach can be found in several blockchain systems that employ verifiable outsourcing to process a large number of transactions off-chain. This reduces the on-chain work to simply verifying a succinct proof that transaction processing was done correctly. In practice, verifiable outsourcing of state updates is done by updating the leaves of a Merkle tree, recomputing the resulting Merkle root, and proving using a SNARK that the state update was done correctly.

In this work, we use a combination of existing and novel techniques to implement an RSA accumulator inside of a SNARK, and use it as a replacement for a Merkle tree. We specifically optimize the accumulator for compatibility with SNARKs. Our experiments show that the resulting system can dramatically reduce costs compared to existing approaches that use Merkle trees for committing to the current state. These results apply broadly to any system that needs to offload batches of state updates to an untrusted server.