Back to search results

PhD Studentship - Conditional Sampling and Property Testing of Probability Distributions for Cryptographic Applications

University of Birmingham - School of Computer Science

Qualification Type: PhD
Location: Birmingham
Funding for: UK Students
Funding amount: £17,668 Stipend pa. Tuition fee: £4,596 pa.
Hours: Full Time
Placed On: 30th March 2023
Closes: 1st May 2023

Funding: 

The student should have background in Computer Science and knowledge of basic probability theory.

We will consider applications from students wishing to start during the 2022-23 academic year or who wish to begin their studies in autumn 2023.

The position offered is for three and a half years full-time study. The current (2022-23) value of the award is stipend; £17,668 pa; tuition fee: £4,596 pa. Awards are usually incremented on 1 October each following year.

Hypothesis testing on probability distributions has a wide range of applications, including Statistical Learning Theory and Cryptography. The problem asks to determine, with some “confidence”, whether an unknown probability distribution D over a domain S satisfies certain property (null hypothesis) or it is statistically far from any distribution having that property (alternate hypothesis). Traditional statistical tests follow the standard sampling model, where the tester can draw independent samples following D. Efficiency of statistical or algorithmic testers is measured by the sample complexity. For testing whether a distribution is uniform, information-theoretic lower bounds force any algorithm or statistical test to draw at least √|S| samples from D. If S is the set of 256-bit binary strings, the above bound translates to requiring 2^128 many samples! Security of cryptographic constructions, in particular candidate pseudorandom functions and permutations, is crucially reliant on the infeasibility of efficient testing of probability distributions.

The recently introduced framework of Conditional Sampling surprisingly allows efficient testing with sample complexity of O(log |S|) and sometimes even independent of |S|. In this framework, the tester is allowed to draw samples from D conditioned on an arbitrary subset of S. The specific topic of interest is the subcube conditional framework, where the conditioning is done by fixing some bits of the output and studying the residual distribution.

The aim of the project is to develop algorithms in the subcube conditioning framework [1] and analyse the security of modern cryptosystems in this framework. The existing results in testing with subcube conditional samples only work when the null hypothesis assumes the underlying distribution to satisfy the target property. However, the distributions are often statistically close to one satisfying the property. The first objective of this project would be to develop algorithms to test the closeness of distributions using subcube conditional samples. The second objective of the project would be to develop a new cryptanalysis technique using these algorithms and analyse the security of popular cryptographic constructions. The project will be supervised by Dr Rishiraj Bhattacharyya (r.bhattacharyya@bham.ac.uk).

References:

[1] Rishiraj Bhattacharyya and Sourav Chakraborty. Property testing of joint distributions using
conditional samples. ACM Trans. Comput. Theory, 10(4):16:1–16:20, 2018. url: https://rishirajb.github.io/pubs/cond.pdf 

To apply, please click on the ‘Apply’ button above.

We value your feedback on the quality of our adverts. If you have a comment to make about the overall quality of this advert, or its categorisation then please send us your feedback
Advert information

Type / Role:

Subject Area(s):

Location(s):

PhD tools
 

PhD Alert Created

Job Alert Created

Your PhD alert has been successfully created for this search.

Your job alert has been successfully created for this search.

Ok Ok

PhD Alert Created

Job Alert Created

Your PhD alert has been successfully created for this search.

Your job alert has been successfully created for this search.

Manage your job alerts Manage your job alerts

Account Verification Missing

In order to create multiple job alerts, you must first verify your email address to complete your account creation

Request verification email Request verification email

jobs.ac.uk Account Required

In order to create multiple alerts, you must create a jobs.ac.uk jobseeker account

Create Account Create Account

Alert Creation Failed

Unfortunately, your account is currently blocked. Please login to unblock your account.

Email Address Blocked

We received a delivery failure message when attempting to send you an email and therefore your email address has been blocked. You will not receive job alerts until your email address is unblocked. To do so, please choose from one of the two options below.

Max Alerts Reached

A maximum of 5 Job Alerts can be created against your account. Please remove an existing alert in order to create this new Job Alert

Manage your job alerts Manage your job alerts

Creation Failed

Unfortunately, your alert was not created at this time. Please try again.

Ok Ok

Create PhD Alert

Create Job Alert

When you create this PhD alert we will email you a selection of PhDs matching your criteria.When you create this job alert we will email you a selection of jobs matching your criteria. Our Terms and Conditions and Privacy Policy apply to this service. Any personal data you provide in setting up this alert is processed in accordance with our Privacy Notice

Create PhD Alert

Create Job Alert

When you create this PhD alert we will email you a selection of PhDs matching your criteria.When you create this job alert we will email you a selection of jobs matching your criteria. Our Terms and Conditions and Privacy Policy apply to this service. Any personal data you provide in setting up this alert is processed in accordance with our Privacy Notice

 
 
 
More PhDs from University of Birmingham

Show all PhDs for this organisation …

More PhDs like this
Join in and follow us

Browser Upgrade Recommended

jobs.ac.uk has been optimised for the latest browsers.

For the best user experience, we recommend viewing jobs.ac.uk on one of the following:

Google Chrome Firefox Microsoft Edge