International Association
for Cryptologic Research

Proof-carrying data (PCD) is a powerful cryptographic primitive that enables mutually distrustful parties to perform distributed computations that run indefinitely. Known approaches to construct PCD are based on succinct non-interactive arguments of knowledge (SNARKs) that have a succinct verifier or a succinct accumulation scheme for their proofs.

In this paper we show how to obtain PCD without relying on SNARKs. We construct a PCD scheme given any non-interactive argument of knowledge (e.g., with linear-size proofs) that has a *split accumulation scheme*, which is a weak form of accumulation that we introduce.

We additionally construct a transparent non-interactive argument of knowledge for R1CS whose accumulation is verifiable via a *constant number of group and field operations*. This leads, via the random oracle heuristic and our result above, to efficiency improvements for PCD. Along the way, we construct a split accumulation scheme for a simple polynomial commitment scheme based on Pedersen commitments.

Our results are supported by a modular and efficient implementation.

We study non-interactive arguments of knowledge (AoKs) for commitments in groups of hidden order. We provide protocols whereby a Prover can demonstrate certain properties of and relations between committed sets/multisets, with succinct proofs that are publicly verifiable against the constant-sized commitments. In particular, we provide AoKs for the disjointness of committed sets/multisets in cryptographic accumulators, with a view toward applications to verifiably outsourcing data storage and sharded stateless blockchains.

Recent work ([DGS20]) suggests that the hidden order groups need to be substantially larger in size that previously thought, in order to ensure the desired security level. Thus, in order to keep the communication complexity between the Prover and the the Verifier to a minimum, we have designed the protocols so that the proofs entail a constant number of group elements, independent of the number of the committed sets/multisets rather than just independent of the sizes of these sets/multisets.

If the underlying group of hidden order is an appropriate imaginary quadratic class group or a genus three Jacobian, the argument systems are transparent. Furthermore, since all challenges are public coin, the protocols can be made non-interactive using the Fiat-Shamir heuristic. We build on the techniques from [BBF19] and [Wes18].

In Chen-Cramer Crypto 2006 paper \cite{cc} algebraic geometric secret sharing schemes were proposed such that the ``Fundamental Theorem in Information-Theoretically Secure Multiparty Computation" by Ben-Or, Goldwasser and Wigderson \cite{BGW88} and Chaum, Cr\'{e}peau and Damg{\aa}rd \cite{CCD88} can be established over constant-size base finite fields. These algebraic geometric secret sharing schemes defined by a curve of genus $g$ over a constant size finite field ${\bf F}_q$ is quasi-threshold in the following sense, any subset of $u \leq T-1$ players (non qualified) has no information of the secret and any subset of $u \geq T+2g$ players (qualified) can reconstruct the secret. It is natural to ask that how far from the threshold these quasi-threshold secret sharing schemes are? How many subsets of $u \in [T, T+2g-1]$ players can recover the secret or have no information of the secret?

In this paper it is proved that almost all subsets of $u \in [T,T+g-1]$ players have no information of the secret and almost all subsets of $u \in [T+g,T+2g-1]$ players can reconstruct the secret when the size $q$ goes to the infinity and the genus satisfies $\lim \frac{g}{\sqrt{q}}=0$. Then algebraic geometric secretsharing schemes over large finite fields are asymptotically threshold in this case. We also analyze the case when the size $q$ of the base field is fixed and the genus goes to the infinity.

Multipartite secret sharing schemes are those that have multipartite access structures. The set of the participants in those schemes is divided into several parts, and all the participants in the same part play the equivalent role. One type of such access structure is the compartmented access structure. We propose an ideal and efficient compartmented multi-secret sharing scheme based on the linear homogeneous recurrence (LHR) relations. In the construction phase, the shared secrets are hidden in some terms of the linear homogeneous recurrence sequence. In the recovery phase, the shared secrets are obtained by solving those terms in which the shared secrets are hidden. When the global threshold is $t$, our scheme can reduce the computational complexity from $O(n^{t-1})$ to $O(n^{\max(t_i-1)}\log n)$, where $t_i<t$. The security of the proposed scheme is based on Shamir's threshold scheme. Moreover, it is efficient to share the multi-secret and to change the shared secrets in the proposed scheme. That is, the proposed scheme can improve the performances of the key management and the distributed system.

A long standing question in the context of cryptocurrencies based on Nakamoto consensus is whether such constructions are incentive compatible, i.e., the intended properties of the system emerge from the appropriate utility model for participants. Bribing and other related attacks, such as front-running or Goldfinger attacks, aim to directly influence the incentives of actors within (or outside) of the targeted cryptocurrency system. The theoretical feasibility of bribing attacks on cryptocurrencies was first highlighted in 2016 by Bonneau, with various different techniques and approaches having since been proposed. Some of these attacks are designed to gain in-band profits, while others intend to break the mechanism design and render the cryptocurrency worthless. In this paper, we systematically expose the large but scattered body of research in this area which has accumulated over the years. We summarize these bribing attacks and similar techniques that leverage on programmatic execution and verification under the term algorithmic incentive manipulation (AIM) attacks, and show that the problem space is not yet fully explored. Based on our analysis we present several research gaps and opportunities that warrant further investigation. In particular, we highlight no- and near-fork attacks as a powerful, yet largely underestimated, AIM category that raises serious security concerns not only for smart contract platforms.

Event date: to
Submission deadline: 31 July 2021

We have an opening for an excellent, motivated, self-driven post-doctoral researcher to work in the area of password-based cryptography. The University of Erlangen Nürnberg is the most innovative university in Germany and ranks 14th worldwide according to Reuters "The World's Most Innovative Universities". We are an international group; working and teaching language is English. Roughly 20% of the people in Erlangen are foreigners, and learning German is not necessary. We offer an internationally competitive salary. The position is initially for one year with the possibility for extension to two additional years.

What we expect:

• A PhD degree in Cryptography
• Strong publication record
• Research statement
• Ideally two reference letters
• High motivation

Closing date for applications:

Contact: Dominique Schröder

The School of Mathematical and Statistical Sciences at Clemson University invites applications for a tenure-track faculty position starting with the Fall 2021 semester. The position will be targeted toward mathematics of communication, that is, mathematics with applications in areas such as cybersecurity, coding theory, computational number theory, blockchain technology, artificial intelligence and/or machine learning.

Closing date for applications:

Contact: Felice Manganiello

More information: https://www.mathjobs.org/jobs/list/17017

FACULTY POSITIONS AT DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING, NATIONAL SUN YAT-SEN UNIVERSITY, TAIWAN The Department of Computer Science and Engineering at National Sun Yat-sen University invites applications for tenure-track positions from August 2021. Applicants in areas of information security, network security, communication security, hardware security, and artificial intelligence are sought. Applicants for assistant professorship must demonstrate strong research potential, in addition to good teaching ability. Applicants for associate professorship and professorship must have an exceptional record of research achievement. All successful candidates are expected to conduct both research and teaching activities. The department offers BS, MS and Ph. D. degrees in Computer Science and Engineering. The official language of teaching is Chinese, and English teaching is encouraged by the university. For more information, please visit our website: https://cse.nsysu.edu.tw/index.php?Lang=en Applications should include a curriculum vitae, recent publications, and reference letters from at least three people who can comment on the applicant's professional qualification. Other supporting material is welcome. Applications should be sent to: Faculty Recruiting Committee Department of Computer Science and Engineering National Sun Yat-sen University Kaohsiung, Taiwan 80424 Email:srkuang@cse.nsysu.edu.tw TEL:+886-7-5252000 ext. 4340 FAX:+886-7-5254301 The deadline for applications is February 28, 2021.

Closing date for applications:

Contact: Prof. S.R. Kuang, Email: srkuang@cse.nsysu.edu.tw, TEL:+886-7-5252000 ext. 4340, FAX:+886-7-5254301

More information: https://cse.nsysu.edu.tw/index.php?Lang=en

The Division of Science at NYU Abu Dhabi (NYUAD) invites applications for tenured / tenure-track open-rank faculty positions within its Computer Science Program. Multidisciplinary research and exceptional teaching in a highly diverse and inclusive campus community are hallmarks of the University’s mission. Faculty within the Program of Computer Science at NYUAD are highly collaborative and pursue cutting edge research that is highly interdisciplinary. The internationally renowned research projects in fields that include, but are not limited to: artificial intelligence; bioinformatics; cybersecurity; computational geometry; computer social science; human data interaction; information and communication technologies for development; natural language processing; and theoretical computer science.

Closing date for applications:

Contact: Christina Poepper, christina.poepper@nyu.edu

More information: https://apply.interfolio.com/77776

Cryptography Services @ NCC Group | NYC, SF, Chicago and Waterloo, Ontario, Canada

NCC Group Crypto Services is hiring interns for summer 2021! We're a small-ish team auditing applied crypto and doing research in the field. If you like cryptography and security, and would like to pursue a research project in any of the applied crypto areas, such as (but not limited to):

- cryptographic implementations (cryptographic protocols or primitives block ciphers, elliptic cures, hash functions, lightweight crypto, post-quantum crypto)
- cryptocurrencies (audits of novel consensus algorithms, privacy preserving technologies in this space, etc.)
- audits of existing cryptographic software

The position will possibly be fully remote. The intern will get a feel of what crypto consulting looks like and do a research project with the help of a member of NCC Group CS team. Only candidates with legal permission to work in US or Canada would be considered due to short-term nature of the job.

Closing date for applications:

Contact: cs-intern-jobs@nccgroup.com

More information: https://www.nccgroup.com/us/our-services/cyber-security/specialist-practices/cryptography-services/

Ciet et al.(2006) proposed an elegant method for trading inversions for multiplications when computing [2] P+Q from two given points P and Q on elliptic curves of Weierstrass form. Motivated by their work, this paper proposes a fast algorithm for computing [4] P with only one inversion in affine coordinates. Our algorithm that requires 1I+ 8S+ 8M, is faster than two repeated doublings whenever the cost of one field inversion is more expensive than the cost of four field multiplications plus four field squarings (ie I> 4M+ 4S). It saves one field multiplication and one field squaring in comparison with the Sakai-Sakurai method (2001). Even better, for special curves that allow" a= 0"(or" b= 0") speedup, we obtain [4] P in affine coordinates using just 1I+ 5S+ 9M (or 1I+ 5S+ 6M, respectively).

Payment Channel Networks (PCNs) have given a huge boost to the scalability of blockchain-based cryptocurrencies: Beyond improving the transaction rate, PCNs enabled cheap cross-currency payments and atomic swaps. However, current PCNs proposals either heavily rely on special scripting features of the underlying blockchain (e.g. Hash Time Lock Contracts) or are tailored to a handful of digital signature schemes, such as Schnorr or ECDSA signatures. This leaves us in an unsatisfactory situation where many currencies that are being actively developed and use different signature schemes cannot enjoy the benefits of a PCN.

In this work, we investigate whether we can construct PCNs assuming the minimal ability of a blockchain to verify a digital signature, for any signature scheme. In answering this question in the affirmative, we introduce the notion of lockable signatures, which constitutes the cornerstone of our PCN protocols. Our approach is generic and the PCN protocol is compatible with any digital signature scheme, thus inheriting all favorable properties of the underlying scheme that are not offered by Schnorr/ECDSA (e.g.\ aggregatable signatures or post-quantum security).

While the usage of generic cryptographic machinery makes our generic protocol impractical, we view it as an important feasibility result as it may serve as the basis for constructing optimized protocols for specific signature schemes. To substantiate this claim, we design a highly efficient PCN protocol for the special case of Boneh-Lynn-Shacham (BLS) signatures. BLS signatures enjoy many unique features that make it a viable candidate for a blockchain, e.g. short, unique, and aggregatable signatures. Yet, prior to our work, no PCN was known to be compatible with it (without requiring an advanced scripting language). The cost of our PCN is dominated by a handful of calls to the BLS algorithms. Our concrete evaluation of these basic operations shows that users with commodity hardware can process payments with minimal overhead.

Hierarchical secret sharing is an important key management technique since it is specially customized for hierarchical organizations with different departments allocated with different privileges, such as the government agencies or companies. Hierarchical access structures have been widely adopted in secret sharing schemes, where efficiency is the primary consideration for various applications. How to design an efficient hierarchical secret sharing scheme is an important issue. In 2007, a famous hierarchical secret sharing (HSS) scheme was proposed by Tassa based on Birkhoff interpolation, and later, based on the same method, many other HSS schemes were proposed. However, these schemes all depend on Polya's condition, which is a necessary condition not a sufficient condition. It cannot guarantee that Tassa's HSS scheme always exists. Furthermore, this condition needs to check the non-singularity of many matrices. We propose a hierarchical multi-secret sharing scheme based on the linear homogeneous recurrence (LHR) relations and the one-way function. In our scheme, we select $m$ linearly independent homogeneous recurrence relations. The participants in the highly-ranked subsets $\gamma_1, \gamma_2 ,\cdots, \gamma_{j-1}$ join in the $j$-th subset to construct the $j$-th LHR relation. In addition, the proposed hierarchical multi-secret sharing scheme just requires one share for each participant, and keeps the same computational complexity. Compared with the state-of-the-art hierarchical secret sharing schemes, our scheme has high efficiency.

Today, users' data is gathered and analyzed on a massive scale. While user data analytics such as personalized advertisement need to make use of this data, users may not wish to divulge their information without security and privacy guarantees. Private Stream Aggregation (PSA) allows the secure aggregation of time-series data, affording security and privacy to users' private data, which is much more efficient than general secure computation such as homomorphic encryption, multiparty computation, and secure hardware based approaches. Earlier PSA protocols face limitations including needless complexity or a lack of post-quantum security. In this work, we present SLAP, a lattice-based PSA protocol. SLAP features two variants with post-quantum security, with simpler and more efficient computations enabled by (1) the white- box approach that builds the encryption directly from the Ring Learning With Error assumption and (2) the state-of-the-art algorithmic optimization in lattice-based cryptography. We show that SLAP meets the security and privacy requirements of PSA, and show experimentally the improvements of SLAP over similar work. We show a speedup of 20.76x over the previous state-of-the-art lattice-based PSA work's aggregation, and apply techniques including RNS, NTT, and batching to obtain a throughput of over 600,000 aggregations per second.

Ransomware is a type of malware that blocks an user’s access to files and requests him/her a ransom. The main approach of an attacker is to encrypt the user’s files and give him/her the decrypting tool only after he/she pays the requested amount of money. The payment is usually done in difficult to trace currencies. In this paper, we provide a review of the ransomware phenomenon, making a clear distinction between the threats before and after WannaCry (which appeared in May 2017). Initially, we give two taxonomy examples from the literature and one designed by us. The first two taxonomies use ”Platform”, ”Cryptosystem”/”Crypto”, ”Severity”, ”Attack” and ”Target” as criteria (the terms appear in one of them or both), but we have chosen ”Target Zone”, ”Propagation”, ”Payment” and ”Weakness”. We further describe/compare ransomware programs, taking into account several aspects including how they work (e.g., encryption methods), whom they target (e.g., individuals/organizations), what impact they have and what weaknesses can be used to provide countermeasures (besides the general prevention techniques that we mention briefly).

In 2017, Tang et al. have introduced a generic construction for bent functions of the form $f(x)=g(x)+h(x)$, where $g$ is a bent function satisfying some conditions and $h$ is a Boolean function. Recently, Zheng et al. generalized this result to construct large classes of bent vectorial Boolean function from known ones in the form $F(x)=G(x)+h(X)$, where $G$ is a bent vectorial and $h$ a Boolean function. In this paper we further generalize this construction to obtain vectorial bent functions of the form $F(x)=G(x)+\mathbf{H}(X)$, where $\mathbf{H}$ is also a vectorial Boolean function. This allows us to construct new infinite families of vectorial bent functions, EA-inequivalent to $G$, which was used in the construction. Most notably, specifying $\mathbf{H } (x)=\mathbf{h} (Tr_1^n(u_1x),\ldots,Tr_1^n(u_tx))$, the function $\mathbf{h} :\mathbb{F}_2^t \rightarrow \mathbb{F}_{2^t}$ can be chosen arbitrary which gives a relatively large class of different functions for a fixed function $G$. We also propose a method of constructing vectorial $(n,n)$-functions having maximal number of bent components.

Competitions are widely viewed as the safest way to select cryptographic algorithms. This paper surveys procedures that have been used in cryptographic competitions, and analyzes the extent to which those procedures reduce security risks.

Cryptocurrencies and decentralized ledger technology has been widely adopted over the last decades. However, there isn’t yet a decentralized exchange that protects users’ privacy from end to end. In this paper, we construct the first ledger-based decentralized token exchange with strong privacy guarantees. We propose the first Decentralized Anonymous eXchange scheme (DAX scheme) based on automated market maker (AMM) and zkSNARK and present a formal definition of its security and privacy properties.

Homomorphic encryption (HE) is considered as one of the most important primitives for privacy-preserving applications. However, an efficient approach to evaluate both polynomial and non-polynomial functions on encrypted data is still absent, which hinders the deployment of HE to real-life applications. To address this issue, we propose a practical framework PEGASUS. PEGASUS can efficiently switch back and forth between a packed CKKS ciphertext and FHEW ciphertexts without decryption, allowing us to evaluate arithmetic functions efficiently on the CKKS side, and to evaluate look-up tables on FHEW ciphertexts. Our FHEW ! CKKS conversion algorithm is more practical than the existing methods. We improve the computational complexity from linear to sublinear. Moreover, the size of our conversion key is significantly smaller, e.g., reduced from 80 gigabytes to 12 megabytes. We present extensive benchmarks of PEGASUS, including sigmoid/ReLU/min/max/division, sorting and max-pooling. To further demonstrate the capability of PEGASUS, we developed two more applications. The first one is a private decision tree evaluation whose communication cost is about two orders of magnitude smaller than the previous HE-based approaches. The second one is a secure K-means clustering that is able to run on thousands of encrypted samples in minutes that outperforms the best existing system by 14  – 20. To the best of our knowledge, this is the first work that supports practical K-means clustering using HE in a single server setting.