International Association
for Cryptologic Research

Coconut [NDSS 2019] is an attribute-based credential scheme with threshold issuance. We analyze its security properties. To this end, we define an ideal functionality for attribute-based access control with threshold issuance. We describe a construction that realizes our functionality. Our construction follows Coconut with a few changes. In particular, it modifies the protocols for blind issuance of credentials and for credential show so that user privacy holds against computationally unbounded adversaries. The modified protocols are slightly more efficient than those of Coconut. Our construction also extends the public key, which seems necessary to prove unforgeability.

Many decentralized systems rely on flooding protocols for message dissemination. In such a protocol, the sender of a message sends it to a randomly selected set of peers. These peers again send the message to their randomly selected peers, until every network participant has received the message. This type of protocols clearly fail in face of an adaptive adversary who can simply corrupt all peers of the sender and thereby prevent the message from being delivered. Nevertheless, flooding protocols are commonly used within protocols that aim to be cryptographically secure, most notably in blockchain protocols. While it is possible to revert to static corruptions, this gives unsatisfactory security guarantees, especially in the setting of a blockchain that is supposed to run for an extended period of time. To be able to provide meaningful security guarantees in such settings, we give precise semantics to what we call $\delta$-delayed adversaries in the Universal Composability (UC) framework. Such adversaries can adaptively corrupt parties, but there is a delay of time $\delta$ from when an adversary decides to corrupt a party until they succeed in overtaking control of the party. Within this model, we formally prove the intuitive result that flooding protocols are secure against $\delta$-delayed adversaries when $\delta$ is at least the time it takes to send a message from one peer to another plus the time it takes the recipient to resend the message. To this end, we show how to reduce the adaptive setting with a $\delta$-delayed adversary to a static experiment with an Erdős–Rényi graph. Using the established theory of Erdős–Rényi graphs, we provide upper bounds on the propagation time of the flooding functionality for different neighborhood sizes of the gossip network. More concretely, we show the following for security parameter $\kappa$, point-to-point channels with delay at most $\Delta$, and $n$ parties in total, with a sufficiently delayed adversary that can corrupt any constant fraction of the parties: If all parties send to $\Omega(\kappa)$ parties on average, then we can realize a flooding functionality with maximal delay $\mathcal{O}\bigl(\Delta \cdot \log (n) \bigr)$; and if all parties send to $\Omega\bigl( \sqrt{\kappa n \log (n)} \bigr)$ parties on average, we can realize a flooding functionality with maximal delay $\mathcal{O}(\Delta)$.

Arguments of knowledge are powerful cryptographic primitives that allow a prover to demonstrate that it knows a satisfying witness to a prescribed statement. Tremendous progress has been made in developing efficient argument systems by leveraging homomorphic structure in an increasingly composable and recursive manner. However, the extent to which homomorphisms can be composed and manipulated in the service of efficient argument systems is still not well understood. To this end, we introduce reductions of knowledge, a generalization of arguments of knowledge, which reduce checking a statement in one relation to checking a derived statement in another, and better capture the composable and recursive nature of arguments over homomorphisms. We construct and study the tensor reduction, which is capable of reducing any homomorphic statement composed via the tensor product, and provides knowledge soundness unconditionally when working over vector spaces. We show that tensor reductions generalize a large class of prior recursive techniques including the ubiquitous sumcheck protocol. We additionally show that tensor reductions can be employed to construct reductions of knowledge with logarithmic communication for familiar linear algebraic statements, and in turn, these can be composed to recover a reduction of knowledge for NP with logarithmic communication.

Chandran et al. (SIAM J. Comput.'14) formally introduced the cryptographic task of position verification, where they also showed that it cannot be achieved by classical protocols. In this work, we initiate the study of position verification protocols with classical verifiers. We identify that proofs of quantumness (and thus computational assumptions) are necessary for such position verification protocols. For the other direction, we adapt the proof of quantumness protocol by Brakerski et al. (FOCS'18) to instantiate such a position verification protocol. As a result, we achieve classically verifiable position verification assuming the quantum hardness of Learning with Errors.

Along the way, we develop the notion of 1-of-2 non-local soundness for a natural non-local game for 1-of-2 puzzles, first introduced by Radian and Sattath (AFT'19), which can be viewed as a computational unclonability property. We show that 1-of-2 non-local soundness follows from the standard 2-of-2 soundness (and therefore the adaptive hardcore bit property), which could be of independent interest.

Known constructions of (efficient) blind signatures either rely on non-standard hardness assumptions or require parameters that grow linearly with the number of concurrently issued signatures. This holds true even in the random oracle model.

Katz, Loss and Rosenberg (ASIACRYPT 2021) presented a generic construction that boosts a scheme supporting logarithmically many concurrent signing sessions to a scheme that supports polynomially many. Unfortunately, this construction has two drawbacks: 1) the communication between the signer and the user still grows linearly with the number of issued signatures 2) their schemes inherit a very loose security bound from the underlying scheme and, as a result, require impractical parameter sizes.

In this paper, we eliminate these two drawbacks by proposing two highly practical blind signature schemes from the CDH and RSA assumptions. Our resulting schemes have communication which grows only logarithmically in the number of issued signatures. In addition, we introduce new techniques to mitigate the large security loss in the construction of Katz et al. Overall, we obtain the following parameter sizes (providing 128 bits of security):

- Our main scheme PIKA is based on the BLS blind signature scheme (Boldyreva, PKC 2003) and is secure under the \cdh assumption over a standard-sized group. Signatures are of size roughly 3KB and communication per signature is roughly 150KB. - Our RSA-based scheme is based on the Okamoto-Guillou-Quisquater blind signature scheme (Okamoto, CRYPTO 1992). It has signatures and communication of roughly 9KB and 8KB, respectively.

Lattice-based blind signature schemes have been receiving some recent attention lately. Earlier efficient 3-round schemes (Asiacrypt 2010, Financial Cryptography 2020) were recently shown to have mistakes in their proofs, and fixing them turned out to be extremely inefficient and limited the number of signatures that a signer could send to less than a dozen (Crypto 2020). In this work we propose a round-optimal, 2-round lattice-based blind signature scheme which produces signatures of length 150KB. The running time of the signing protocol is linear in the maximum number signatures that can be given out, and this limits the number of signatures that can be signed per public key. Nevertheless, the scheme is still quite efficient when the number of signatures is limited to a few dozen thousand, and appears to currently be the most efficient lattice-based candidate.

The generation of pseudorandom binary sequences is of a great importance in numerous applications stretching from simulation and gambling to cryptography. Pseudorandom bit generators (PRBGs) can be split into two classes depending on their claimed security. The first includes PRBGs that are provably secure (such as the Blum-Blum-Shub one). Security of the second class rests on heuristic arguments. Sadly, PRBG from the first class are inherently inefficient and some PRBG are insecure against quantum attacks. While, their siblings from the second class are very efficient, but security relies on their resistance against known cryptographic attacks.

This work presents a construction of PRBG from the asymmetric numeral system (ANS) compression algorithm. We define a family of PRBGs for $2^R$ ANS states and prove that it is indistinguishable from a truly random one for a big enough $R$. To make our construction efficient, we investigate PRBG built for smaller $R=7,8,9$ and show how to remove local correlations from output stream. We permute output bits using rotation and Keccak transformations and show that permuted bits pass all NIST tests. Our PRBG design is provably secure (for a large enough $R$) and heuristically secure (for a smaller $R$). Besides, we claim that our PRBG is secure against quantum adversaries.

Event date: 12 September to 14 September 2022
Submission deadline: 24 April 2022
Notification: 12 June 2022

Event date: 14 July to 16 July 2022
Submission deadline: 16 February 2022
Notification: 15 April 2022

We look for postdoc in side channel attacks (SCA) for a project in threshold implementation (TI). The position is within RCN project "Threshold Implementation and Boolean Functions" with key members Lilya Budaghyan, Claude Carlet and Vincent Rijmen, and in cooperation with COSIC group at KU Leuven. It is for 3 year period (possible extension to 4 years). For application and more information see https://www.jobbnorge.no/en/available-jobs/job/215372/postdoctoral-research-fellow-position-in-informatics-cryptography

Closing date for applications:

Contact: Prof. Lilya Budaghyan lilya.budaghyan@uib.no

More information: https://www.jobbnorge.no/en/available-jobs/job/215372/postdoctoral-research-fellow-position-in-informatics-cryptography

Seoul National University of Science and Technology is currently recruiting research professors and the application process ends on January 11. Applicants will be matched with advisors, so they must choose them in advance.
The Cryptography and Information Security Lab, led by Professor Changhoon Lee, is looking for a candidate who is interested in cryptography and information security. The successful candidate will work on research projects, attend lab seminars, and publish SCI(E) papers under the direction of advisor. We expect a successful candidate to be able to publish SCI (E) papers related to hash function and cryptocurrency security.
Required Qualifications:

Candidate must have recently received a Ph.D. degree (no more than 5 years from the date of obtaining the degree) or expect to receive it before March 1, 2022.

Candidate must have published 2 or more SCI(E) papers in the last 3 years.
Appointment term and salary:

Contract term: from appointment date (March 1, 2022) 1 year

Salary (gross): 39,6 million won per year

Closing date for applications:

Contact: Interested candidates should email professor Changhoon Lee (chlee@seoultech.ac.kr) before January, 9.

More information: https://cis.seoultech.ac.kr/

The Department of Computer Science at the University of Surrey is seeking to appoint a Reader or Senior Lecturer in Software Security to strengthen its research and ambitious strategic growth within the Surrey Centre for Cyber Security (SCCS). This appointment is on a full-time and permanent basis.

The Department of Computer Science has a world-class reputation in cyber security and regularly publishes at top-tier venues. The Department is home to Surrey Centre for Cyber Security (SCCS) and Surrey is only one of four institutions in the UK holding recognition from the National Cyber Security Centre as an Academic Centre of Excellence in both Cyber Security Research and in Cyber Security Education (Gold). SCCS delivers world-leading research expertise in applied cryptography, trusted computing, privacy and authentication, secure communications, blockchain and distributed ledger technologies, and security verification. The Centre includes 16 academics across two research groups: Secure Systems and Distributed and Networked Systems, with around 30 research associates and PhD students. SCCS is leading the recently established Surrey Security Network through which our cross-disciplinary research agenda in cyber security is delivered across the School of Computer Science and Electronic Engineering and across all Faculties of the University. SCCS maintains close links with leading industries, the public sector and governmental bodies, leading to a strong heritage of real-world impact. Our Computer Science BSc programme has been running successfully for many years and continues to attract strong students. The Department offers Information Security MSc and Data Science MSc programmes with growing student numbers. The Department has made significant investment in its facilities with a new 200-seater computer science teaching laboratory, a virtual cloud computing platform, a secure systems facility and an HPC cluster for research.

Research areas of particular interest include (but are not limited to) the following: software security, malware analysis, offensive security. Applicants in related applied areas of research are also invited to apply.

Closing date for applications:

Contact: Steve Schneider (s.schneider@surrey.ac.uk)

More information: https://jobs.surrey.ac.uk/vacancy.aspx?ref=085321

The Cybersecurity - Identity Management group at the Hasso-Plattner-Institute (HPI), University of Potsdam is looking for motivated PhD students and Postdocs in the area of cryptography and privacy.

Research Topics: Development and analysis of provably secure cryptographic protocols for real-world problems. Topics of interest include (but are not limited to): privacy-enhancing technologies, password-based cryptography, as well as foundations for real-world cryptography.

Requirements: Master’s degree (or PhD for postdoctoral position) in Computer Science, Mathematics, or a related area by the time of appointment. Profound knowledge and interest in the areas of cryptography and IT security. Fluency in English (written and spoken).

There are two types for the positions: One comes with a teaching obligation for which also sufficient German language skills are required. Review of applicants will start immediately until the position is filled. The starting date is flexible. The other is through the scholarship program of the HPI. Deadline for scholarship applications is February 1st, and the positions usually start around April.

We look forward to your application including a CV and motivation letter. Applications for the PhD position should also include a list of attended Master courses and grades, whereas applications for the Postdoc position should include contact information for two references. Please submit your application documents (only as PDF) via email, and indicate whether you are interested in a scholarship or teaching position.

Closing date for applications:

Contact: Anja Lehmann (firstname.lastname@hpi.de)

More information: https://hpi.de/lehmann/home.html

iTrust is a Cyber Security Research Center in SUTD and a National Satellite of Excellence in Singapore for securing critical infrastructure. iTrust hosts the world-class cyber-physical system (CPS) testbeds which are used for research, education, training, live-fire exercise, and technology validation.

We are looking for postdocs / research fellows with expertise on cybersecurity in general and CPS security in particular. The candidates should have track record of strong R&D capability, with publications at leading security conferences. The candidates familiar with shipboard OT systems or autonomous vehicles will be considered with the priority. Candidate working in the current position less than one year will not be considered (unless due to the end of contract). Fresh PhD graduates are welcome. Only short-listed candidates will be contacted for interview. Successful candidates will be offered internationally competitive remuneration.

Interested candidates please send your CV to Prof. Jianying Zhou. Email: jianying_zhou (at) sutd.edu.sg. Home: http://jianying.space/

Closing date for applications:

Contact: Prof. Jianying Zhou

More information: http://jianying.space/

We present a new construction for publicly verifiable anonymous tokens with private metadata. This primitive enables an issuer to generate an anonymous authentication token for a user while embedding a single private metadata bit. The token can be publicly verified, while the value of the private metadata is only accessible to the party holding the secret issuing key and remains hidden to any other party, even to the user. The security properties of this primitive also include unforgeability, which guarantees that only the user can generate new valid tokens, and unlinkability that guarantees that tokens issued with the same private metadata bit are indistinguishable. Our anonymous tokens scheme builds on the top of blind Schnorr signatures.

We analyze its security in the algebraic group model and prove its security under the modified ROS assumption, one-more discrete logarithm, and decisional Diffie-Hellman assumptions.

Blind signature schemes are one of the best and best-studied tools for privacy-preserving authentication. It has a blind signing protocol in which a signer learns nothing about the message being signed or the resulting signature; thus such a signature can serve as an anonymous authentication token. Thus, constructing efficient blind signatures secure under realistic cryptographic assumptions is an important goal.

A recent paper by Benhamouda, Lepoint, Loss, Orr\`u, and Raykova (Eurocrypt '21) showed that a large class of blind signature schemes secure in the stand-alone setting are no longer secure when multiple instances of the blind signing protocol are executed concurrently. The best known technique to salvage the security of such blind signatures was recently proposed by Katz, Loss, and Rosenberg (Asiacrypt '21). For the security parameter $\kappa$, their technique transforms blind signature schemes that are secure for $\mathcal{O}(\log \kappa)$ concurrent executions of the blind signing protocol into ones that are secure for any $N = \mathsf{poly}(\kappa)$ concurrent executions. The resulting, transformed blind signing protocol needs $\mathcal{O}(N)$ times more computation and communication than the original one.

In this paper, we give an improved transform for obtaining a secure blind signing protocol tolerating $N = \mathsf{poly}(\kappa)$ concurrent executions from one that is secure for $\mathcal{O}(\log \kappa)$ concurrent executions. Our technique still needs $\mathcal{O}(N)$ times more computation, but only $\mathcal{O}(\log N)$ more communication than the original blind signature.

This paper presents a key recovery attack on the cryptosystem proposed by Lau and Tan in a talk at ACISP 2018. The Lau-Tan cryptosystem uses Gabidulin codes as the underlying decodable code. To hide the algebraic structure of Gabidulin codes, the authors chose a matrix of column rank $n$ to mix with a generator matrix of the secret Gabidulin code. The other part of the public key, however, reveals crucial information about the private key. Our analysis shows that the problem of recovering the private key can be reduced to solving a multivariate linear system, rather than solving a multivariate quadratic system as claimed by the authors. Apparently, this attack costs polynomial time, and therefore completely breaks the cryptosystem.

We study the provable security claims of two NIST Lightweight Cryptography (LwC) finalists, GIFT-COFB and Photon-Beetle, and present several attacks whose complexities contradict their claimed bounds in their final round specification documents. For GIFT-COFB, we show an attack using $q_e$ encryption queries and no decryption query to break privacy (IND-CPA). The success probability is $O(q_e/2^{n/2})$ for $n$-bit block while the claimed bound contains $O(q^2_e/2^{n})$. This positively solves an open question posed in~[Khairallah, ePrint~2021/648]. For Photon-Beetle, we show attacks using $q_e$ encryption queries (using a small number of input blocks) followed by a single decryption query and no primitive query to break authenticity (INT-CTXT). The success probability is $O(q^2_e/2^{b})$ for $b$-bit block permutation, and it is significantly larger than what the claimed bound tells. We also analyze other (improved/modified) bounds of Photon-Beetle shown in the subsequent papers~[Chakraborty et al., ToSC 2020(2) and Chakraborty et al., ePrint~2019/1475].

We emphasize that our results do not contradict the claimed ``bit security'' in the LwC specification documents for any of the schemes that we studied. That is, we do not negate the claims that GIFT-COFB is $(n/2 - \log n)$-bit secure for $n=128$, and Photon-Beetle is $(b/2 - \log b/2)$-bit secure for $b=256$ and $r=128$, where $r$ is a rate.

GoUncle is a blockchain for permissionless participation by modest computers. As in GHOST (Greedy Heaviest Observed SubTree, in successful implementation and use by the Ethereum blockchain's Proofs-of-Work version), GoUncle blocks also record the public-key IDs of some temporary forking blocks finders who are dearly called ``uncles'' (poorly named ``orphans'' in Bitcoin). While GHOST uncles are for saving PoW computations, GoUncle assigns jobs for its uncles to do. In a payload distillation job, uncles choose from block payloads only the logs which comply with the blockchain database (DB) policy to announce for to survive the blockchain gossip protocol. With uncles distillations, the blockchain address, aka height, for a no-longer-need-to-trust block, is deterministic right upon the block extending the blockchain. The deterministic blockchain addresses can index partition the distributed DB into small files to store in nowadays over provisioned external storage even for a low-cost computer. The index partitioned DB files can be fast operable for input, output, lookup, insert, update, manage, ..., etc., as a standard DB management system (DBMS) can. It is the fast operable property of the DBMS, even by a modest computer, that secures the blockchain DBMS by a hop-by-hop firewall among vast semantics gossipers who each looks up the local DBMS to judge either writing to the DB correct uncles distillations and forwarding them on, or discarding incorrect ones, both operations being quick. Since the hop-by-hop firewall works exactly as correctness probability amplification by repeated execution of a randomized probabilistic (RP) algorithm, the GoUncle work establishes:

$$\mbox{Blockchains} \subset \mbox{RP}.$$

Also to be manifested in the present work are more general blockchain consensus layer computations that uncles can and should execute and disseminate the execution output as No-Spam and No-Single-Point-of-Failure (No-SPOF) set of blockchain servers.

Verifiable encryption (VE) is a protocol where one can provide assurance that an encrypted plaintext satisfies certain properties. It is an important buiding block in cryptography with many useful applications, such as key escrow, group signatures, optimistic fair exchange, etc. However, a majority of previous VE schemes are restricted to instantiation with specific public-key encryption schemes or relations.

In this work, we propose a novel framework that realizes VE protocols using the MPC-in-the-head zero-knowledge proof systems (Ishai et al. STOC 2007). Our generic compiler can turn a large class of MPC-in-the-head ZK proofs into secure VE protocols for any CPA secure public-key encryption (PKE) schemes with the undeniability property, a notion that essentially guarantees binding of encryption when used as a commitment scheme.

Our framework is versatile: because the circuit proven by the MPC-in-the-head prover is decoupled from a complex encryption function, the prover’s work can be focused on proving properties (i.e. relation) about the encrypted data, not the proof of plaintext knowledge. Hence, our approach allows for instantiation with various combinations of properties about encrypted data and encryption functions. As concrete applications we describe new approaches to verifiably encrypting discrete logarithms in any prime order group and AES private keys.