Kubernetes installation failing - Ubuntu 16.04

I am trying to install Kubernetes (kubectl) on Ubuntu 16.04 (x64) by following the instructions here. I am behind some proxy at work and I am sure that is the reason for the failure. I know there are a bunch of related questions out there but I have already tried any suggestion I could find. Any help will be greatly appreciated.

Currently, I am stuck at getting apt update to work. It is failing with -

W: The repository 'https://apt.kubernetes.io kubernetes-xenial Release' does not have a Release file.
N: Data from such a repository can't be authenticated and is therefore potentially dangerous to use.
N: See apt-secure(8) manpage for repository creation and user configuration details.
E: Failed to fetch https://apt.kubernetes.io/dists/kubernetes-xenial/main/binary-amd64/Packages  server certificate verification failed. CAfile: /etc/ssl/certs/ca-certificates.crt CRLfile: none

I have tried multiple things here - Updated my apt.conf(at /etc/apt/apt.conf) with

Acquire::https::packages.cloud.google.com::Verify-Peer "false";

I also tried by specifying the above as a command line argument -

sudo apt-get update -o Acquire::https::packages.cloud.google.com::Verify-Peer=false

I have tried running apt-get update with --allow-unauthenticated & --allow-insecure-repositories but somehow apt-secure is still ignoring all these instructions. I went through the man-page for apt-secure but couldn't find anything wrong with the options I specified.

I have updated keys using -

sudo apt-key adv --keyserver hkp://keyserver.ubuntu.com:80 --recv-keys 6A030B21BA07F4FB

I have updated my CA certs. I have ran - sudo rm /var/lib/apt/lists/* to remove all the lists.

Contents of /etc/apt/sources.list.d/kubernetes.list

deb https://apt.kubernetes.io/ kubernetes-xenial main

There will be a redirection issue sometimes.

Use the source below will solve this.

deb http://packages.cloud.google.com/apt/ kubernetes-xenial main