Research

  • Research

Below is a general overview of my research areas.

Vector Commitments

A vector commitment (VC) scheme allows a committer to generate a commitment \com to a vector \vec{x}. Later, the committer can open the commitment \com to some function-image tuple (f, \vec{y}) and convince anyone that the committed vector \vec{x} satisfies f(\vec{x}) = \vec{y} by generating an opening proof \pi.

There are two notions of binding for VCs. The weaker version says it is infeasible to open a commitment \com to (f,\vec{y}) and (f,\vec{y}') with \vec{y} \neq \vec{y}'. The stronger version says it is infeasible to open a commitment \com to inconsistent function-image tuples.

A VC is said to be succinct if commitments \com and opening proofs \pi are both of size sublinear in |\vec{x}| (but could be linear in |\vec{y}|). A strong notion called compactness further requires sublinearity in |\vec{y}|.

In this CRYPTO ’19 paper we constructed compact VCs for subvector functions, i.e. functions f_I such that f_I(\vec{x}) = \vec{x}_I, and linear maps.

Succinct Arguments

An argument system for a relation R is a protocol between a prover \prover and a verifier \verifier. The prover’s task is to convince the verifier about some statemnet \stmt — there exists a witness \wit such that (\stmt,\wit) \in R.

Roughly, an argument system is

  • complete if (\stmt,\wit) \in R \implies (\verifier \to 1),
  • sound if (\verifier \to 1) \implies (\stmt,\wit) \in R,
  • succinct if the communication cost betwen \prover and \verifier is sublinear in |\stmt| and |\wit|, and
  • zero-knowledge if \verifier learns nothing about \wit beyond (\stmt,\wit) \in R.

In this CRYPTO ’19 paper we constructed a compiler based on vector commitments for subvector functions (resp. linear maps) turning a (resp. linear) probabilistically checkable proof into a succinct argument.

In this CCS ’19 paper we extended an existing succinct argument system “Bulletproof” for proving finite-field arithmetic relations into a succinct argument which is native for proving (bilinear-)group arithmetic relations — algebraic relations between group elements and their exponents.

In this CRYPTO ’21 paper we studied “Bulletproof” in the lattice setting and gave both positive and negative results. Some results in this work are summarised in this blog post.

Decentralised Anonymous Systems

By a decentralised anonymous system, we refer to a system with the following characteristics:

  • It involves a dynamic set of users, who can join (and maybe leave) the system freely (without others’ permission).
  • It involves a dynamic set of accounts, each owned by a user. A user can own many accounts. We call the set of all accounts the “universe”.
  • Each account is associated with an attribute, which could change over the lifetime of the system.
  • Each user can perform certain admissible actions anonymously which could affect the attributes of their own accounts as well as those of other users.
  • The accounts involved an action are anonymous within a “ring” — a set containing the acting accounts and other decoy accounts — sampled by a “ring sampler”.
  • The level of anonymity is parameterised by the size of rings, ranging from no anonymity when rings contain the acting accounts only to full anonymity when rings are the universe.

Ring confidential transaction (RingCT) systems are a special case of decentralised anonymous systems as characterised above. An attribute in a RingCT system includes an amount of coins. An admissible action is payment — transferring an amount of coins from one user to another. The popular anonymous cryptocurrency Monero is based on RingCT.

In this CCS ’19 paper we presented a formal model of RingCT, gave a generic construction, and showed how the generic construction can be efficiently instantiated with group-based building blocks and a succinct argument system which is native for proving group-arithmetic relations.

In this PoPETs ’21 paper we initiated the formal study of ring samplers. We defined an entropy-based metric for the “local” anonymity of ring samplers, and analysed three natural classes of ring samplers — uniform, mimicking, and partitioning — according to this metric.

In this PoPETs ’22 paper we showed that, under certain conjectures about the connectivity of directed graphs, it suffices to set the ring size of a partitioning sampler to be logarithmic in the universe size to resist graph-based deanonymisation.

Homomorphic Secret Sharing

Homomorphic secret sharing (HSS) schemes are natural secret-sharing counterparts of homomorphic encryption (HE) schemes. An HSS scheme allows one or several clients to secret sharing a vector \vec{x} to multiple servers. Each server can then locally evaluate an admissible function f on its share to produce some output shares. The image f(\vec{x}) can then be recovered given all output shares.

Compared to HE schemes, HSS schemes tend to be more lightweight and instantiable from weaker and a wider range of assumptions. Some HSS schemes are even information-theoretically secure.

In this ASIACRYPT ’18 paper we constructed HSS schemes in a public-key model for evaluating low-degree polynomials. We then generalised the construction in this PKC ’21 paper. There, we presented an HE-based compiler which turns an information-theoretic HSS for low-degree polynomials into a computational HSS for higher-degree polynomials.

In this TCC ’20 paper we view HSS schemes as private information retrieval (PIR) schemes for structured databases. We obtained both positive and negative results on the computational complexity of certain classes of PIR schemes for structured databases.

Password-based Cryptography

Password-based cryptography differs from conventional cryptography in that the security of systems is based on the secrecy of passwords, or other low-entropy secrets in general, instead of long cryptographic keys. Password-based systems are therefore inherently vulnerable to brute-force password guessing attacks, which must be modelled and mitigated, e.g. by forcing password guessing attacks to be performed online.

A vast number of currently deployed online services use a simple password-based authentication method. A user logs into the system by sending its password to the server, who checks whether the candidate password matches the one stored (often in hashed and/or encrypted form) in its database. This simple mechanism has an obvious vulnerability that, when the server is compromised or is itself malicious, an offline brute-force attack can be carried out to recover the passwords of its users.

Password-hardening (PH) is a general paradigm for strengthening the security of password-based authentication mechanisms by distributing the task of password validity checking to two or more parties: the original login server and some additional servers called rate-limiters. Now, when a user submits a candidate password to the login server, the latter must communicate with the rate-limiters to check whether the candidate password is valid.

A PH protocol is required to satisfy a number of properties (or otherwise it is trivial):

  • The rate-limiters learn nothing about the password being validated. A relaxation allows them to learn whether the candidate password is valid but nothing else.
  • The rate-limiters cannot deceive the login server into drawing a false conclusion about the validity of a candidate password.
  • A mechanism is in place for the login server and the rate-limiters to refresh their secret keys. Afterwards, the login server can locally update user records to make them compatible with the refreshed secret keys.

In this USENIX Security ’17 paper we proposed a lightweight PH protocol. Then, in this USENIX Security ’18 paper we extended the notion of PH into that of password-hardened encryption (PHE) which equips a PH protocol with a data encryption functionality, and gave a lightweight construction. In this CCS ’20 paper we further extended the PHE protocol to the threshold setting, where security is retained even if a number of rate-limiters are corrupt.

Multichannel Source Coding

Source coding is a classic subfield of information theory. A central question in this area is how to construct a source code for a given information source such that the expected descriptive length of a codeword is optimal. Traditionally, the source coding problem is considered in the single-channel setting, where a codeword is a single string consisting of symbols chosen from a single alphabet. We are interested in the multichannel setting where a codeword is a tuple of strings where each component consists of symbols chosen from a possibly different alphabet.

An important class of source codes is that of prefix(-free) codes, where every pair of codewords is prefix-free to each other. A tree-decodable code is a prefix code which admits a decoding tree.

A classic question in the area of source coding is the following: Does there exist a prefix code with a given multiset of codeword lengths? While the question could be answered by simply checking the satisfiability of the Kraft inequality in the single channel setting, the approach fails even for n = 2 channels. In this ISIT ’19 paper, by casting the problem into an n-dimensional packing problem, we showed that the problem can be decided in polynomial time in the 2-channel case. In this follow up work in ITW ’21 we further showed that the corresponding search problem can also be solved in polynomial time.

Another classic question concerns about tree-decodable codes. In the single channel setting, it is well-kwown that all prefix codes are tree-decodable, and the Huffman procedure produces an optimal tree-decodable code in polynomial time. In the multichannel case, however, it is known that prefix codes are generally not tree-decodable. In this ISIT’ 21 paper we showed that all 2-channel prefix codes are tree-decodable, and that a multichannel generalisation of the Huffman procedure indeed produces an optimal tree-decodable code. However, it is unclear whether the generalised Huffman procedure can be computed in polynomial time.

 

Last Updated on 20/02/2022.