diff --git a/services/core/java/com/android/server/backup/BackupUtils.java b/services/core/java/com/android/server/backup/BackupUtils.java
index e5d564d..d817534 100644
--- a/services/core/java/com/android/server/backup/BackupUtils.java
+++ b/services/core/java/com/android/server/backup/BackupUtils.java
@@ -18,9 +18,12 @@
 
 import android.content.pm.ApplicationInfo;
 import android.content.pm.PackageInfo;
+import android.content.pm.PackageManagerInternal;
 import android.content.pm.Signature;
 import android.util.Slog;
 
+import com.android.internal.util.ArrayUtils;
+
 import java.security.MessageDigest;
 import java.security.NoSuchAlgorithmException;
 import java.util.ArrayList;
@@ -30,13 +33,13 @@
 public class BackupUtils {
     private static final String TAG = "BackupUtils";
 
-    private static final boolean DEBUG = false; // STOPSHIP if true
+    private static final boolean DEBUG = false;
 
-    public static boolean signaturesMatch(ArrayList<byte[]> storedSigHashes, PackageInfo target) {
-        if (target == null) {
+    public static boolean signaturesMatch(ArrayList<byte[]> storedSigHashes, PackageInfo target,
+            PackageManagerInternal pmi) {
+        if (target == null || target.packageName == null) {
             return false;
         }
-
         // If the target resides on the system partition, we allow it to restore
         // data from the like-named package in a restore set even if the signatures
         // do not match.  (Unlike general applications, those flashed to the system
@@ -47,48 +50,53 @@
             return true;
         }
 
-        // Allow unsigned apps, but not signed on one device and unsigned on the other
-        // !!! TODO: is this the right policy?
-        Signature[] deviceSigs = target.signatures;
-        if (DEBUG) Slog.v(TAG, "signaturesMatch(): stored=" + storedSigHashes
-                + " device=" + deviceSigs);
-        if ((storedSigHashes == null || storedSigHashes.size() == 0)
-                && (deviceSigs == null || deviceSigs.length == 0)) {
-            return true;
-        }
-        if (storedSigHashes == null || deviceSigs == null) {
+        // Don't allow unsigned apps on either end
+        if (ArrayUtils.isEmpty(storedSigHashes)) {
             return false;
         }
 
-        // !!! TODO: this demands that every stored signature match one
-        // that is present on device, and does not demand the converse.
-        // Is this this right policy?
-        final int nStored = storedSigHashes.size();
-        final int nDevice = deviceSigs.length;
-
-        // hash each on-device signature
-        ArrayList<byte[]> deviceHashes = new ArrayList<byte[]>(nDevice);
-        for (int i = 0; i < nDevice; i++) {
-            deviceHashes.add(hashSignature(deviceSigs[i]));
+        Signature[][] deviceHistorySigs = target.signingCertificateHistory;
+        if (ArrayUtils.isEmpty(deviceHistorySigs)) {
+            Slog.w(TAG, "signingCertificateHistory is empty, app was either unsigned or the flag" +
+                    " PackageManager#GET_SIGNING_CERTIFICATES was not specified");
+            return false;
         }
 
-        // now ensure that each stored sig (hash) matches an on-device sig (hash)
-        for (int n = 0; n < nStored; n++) {
-            boolean match = false;
-            final byte[] storedHash = storedSigHashes.get(n);
-            for (int i = 0; i < nDevice; i++) {
-                if (Arrays.equals(storedHash, deviceHashes.get(i))) {
-                    match = true;
-                    break;
+        if (DEBUG) {
+            Slog.v(TAG, "signaturesMatch(): stored=" + storedSigHashes
+                    + " device=" + deviceHistorySigs);
+        }
+
+        final int nStored = storedSigHashes.size();
+        if (nStored == 1) {
+            // if the app is only signed with one sig, it's possible it has rotated its key
+            // the checks with signing history are delegated to PackageManager
+            // TODO(b/73988180): address the case that app has declared restoreAnyVersion and is
+            // restoring from higher version to lower after having rotated the key (i.e. higher
+            // version has different sig than lower version that we want to restore to)
+            return pmi.isDataRestoreSafe(storedSigHashes.get(0), target.packageName);
+        } else {
+            // the app couldn't have rotated keys, since it was signed with multiple sigs - do
+            // a check to see if we find a match for all stored sigs
+            // since app hasn't rotated key, we only need to check with deviceHistorySigs[0]
+            ArrayList<byte[]> deviceHashes = hashSignatureArray(deviceHistorySigs[0]);
+            int nDevice = deviceHashes.size();
+            // ensure that each stored sig matches an on-device sig
+            for (int i = 0; i < nStored; i++) {
+                boolean match = false;
+                for (int j = 0; j < nDevice; j++) {
+                    if (Arrays.equals(storedSigHashes.get(i), deviceHashes.get(j))) {
+                        match = true;
+                        break;
+                    }
+                }
+                if (!match) {
+                    return false;
                 }
             }
-            // match is false when no on-device sig matched one of the stored ones
-            if (!match) {
-                return false;
-            }
+            // we have found a match for all stored sigs
+            return true;
         }
-
-        return true;
     }
 
     public static byte[] hashSignature(byte[] signature) {
diff --git a/services/core/java/com/android/server/pm/PackageManagerService.java b/services/core/java/com/android/server/pm/PackageManagerService.java
index f0922b34..d9c0f2f 100644
--- a/services/core/java/com/android/server/pm/PackageManagerService.java
+++ b/services/core/java/com/android/server/pm/PackageManagerService.java
@@ -176,6 +176,7 @@
 import android.content.pm.PackageParser.PackageParserException;
 import android.content.pm.PackageParser.ParseFlags;
 import android.content.pm.PackageParser.ServiceIntentInfo;
+import android.content.pm.PackageParser.SigningDetails;
 import android.content.pm.PackageParser.SigningDetails.SignatureSchemeVersion;
 import android.content.pm.PackageStats;
 import android.content.pm.PackageUserState;
@@ -23383,6 +23384,36 @@
         }
 
         @Override
+        public boolean isDataRestoreSafe(byte[] restoringFromSigHash, String packageName) {
+            SigningDetails sd = getSigningDetails(packageName);
+            if (sd == null) {
+                return false;
+            }
+            return sd.hasSha256Certificate(restoringFromSigHash,
+                    SigningDetails.CertCapabilities.INSTALLED_DATA);
+        }
+
+        @Override
+        public boolean isDataRestoreSafe(Signature restoringFromSig, String packageName) {
+            SigningDetails sd = getSigningDetails(packageName);
+            if (sd == null) {
+                return false;
+            }
+            return sd.hasCertificate(restoringFromSig,
+                    SigningDetails.CertCapabilities.INSTALLED_DATA);
+        }
+
+        private SigningDetails getSigningDetails(@NonNull String packageName) {
+            synchronized (mPackages) {
+                PackageParser.Package p = mPackages.get(packageName);
+                if (p == null) {
+                    return null;
+                }
+                return p.mSigningDetails;
+            }
+        }
+
+        @Override
         public int getPermissionFlagsTEMP(String permName, String packageName, int userId) {
             return PackageManagerService.this.getPermissionFlags(permName, packageName, userId);
         }
diff --git a/services/core/java/com/android/server/pm/ShortcutPackageInfo.java b/services/core/java/com/android/server/pm/ShortcutPackageInfo.java
index 520ed25..eeaa333 100644
--- a/services/core/java/com/android/server/pm/ShortcutPackageInfo.java
+++ b/services/core/java/com/android/server/pm/ShortcutPackageInfo.java
@@ -18,10 +18,13 @@
 import android.annotation.NonNull;
 import android.annotation.UserIdInt;
 import android.content.pm.PackageInfo;
+import android.content.pm.PackageManagerInternal;
 import android.content.pm.ShortcutInfo;
+import android.content.pm.Signature;
 import android.util.Slog;
 
 import com.android.internal.annotations.VisibleForTesting;
+import com.android.server.LocalServices;
 import com.android.server.backup.BackupUtils;
 
 import libcore.util.HexEncoding;
@@ -137,7 +140,8 @@
 
     //@DisabledReason
     public int canRestoreTo(ShortcutService s, PackageInfo currentPackage, boolean anyVersionOkay) {
-        if (!BackupUtils.signaturesMatch(mSigHashes, currentPackage)) {
+        PackageManagerInternal pmi = LocalServices.getService(PackageManagerInternal.class);
+        if (!BackupUtils.signaturesMatch(mSigHashes, currentPackage, pmi)) {
             Slog.w(TAG, "Can't restore: Package signature mismatch");
             return ShortcutInfo.DISABLED_REASON_SIGNATURE_MISMATCH;
         }
@@ -159,13 +163,15 @@
     public static ShortcutPackageInfo generateForInstalledPackageForTest(
             ShortcutService s, String packageName, @UserIdInt int packageUserId) {
         final PackageInfo pi = s.getPackageInfoWithSignatures(packageName, packageUserId);
-        if (pi.signatures == null || pi.signatures.length == 0) {
+        // retrieve the newest sigs
+        Signature[][] signingHistory = pi.signingCertificateHistory;
+        if (signingHistory == null || signingHistory.length == 0) {
             Slog.e(TAG, "Can't get signatures: package=" + packageName);
             return null;
         }
+        Signature[] signatures = signingHistory[signingHistory.length - 1];
         final ShortcutPackageInfo ret = new ShortcutPackageInfo(pi.getLongVersionCode(),
-                pi.lastUpdateTime, BackupUtils.hashSignatureArray(pi.signatures),
-                /* shadow=*/ false);
+                pi.lastUpdateTime, BackupUtils.hashSignatureArray(signatures), /* shadow=*/ false);
 
         ret.mBackupSourceBackupAllowed = s.shouldBackupApp(pi);
         ret.mBackupSourceVersionCode = pi.getLongVersionCode();
@@ -185,7 +191,15 @@
             Slog.w(TAG, "Package not found: " + pkg.getPackageName());
             return;
         }
-        mSigHashes = BackupUtils.hashSignatureArray(pi.signatures);
+        // retrieve the newest sigs
+        Signature[][] signingHistory = pi.signingCertificateHistory;
+        if (signingHistory == null || signingHistory.length == 0) {
+            Slog.w(TAG, "Not refreshing signature for " + pkg.getPackageName()
+                    + " since it appears to have no signature history.");
+            return;
+        }
+        Signature[] signatures = signingHistory[signingHistory.length - 1];
+        mSigHashes = BackupUtils.hashSignatureArray(signatures);
     }
 
     public void saveToXml(ShortcutService s, XmlSerializer out, boolean forBackup)
@@ -221,7 +235,6 @@
 
     public void loadFromXml(XmlPullParser parser, boolean fromBackup)
             throws IOException, XmlPullParserException {
-
         // Don't use the version code from the backup file.
         final long versionCode = ShortcutService.parseLongAttribute(parser, ATTR_VERSION,
                 ShortcutInfo.VERSION_CODE_UNKNOWN);
diff --git a/services/core/java/com/android/server/pm/ShortcutService.java b/services/core/java/com/android/server/pm/ShortcutService.java
index 265cc8e..15b4617 100644
--- a/services/core/java/com/android/server/pm/ShortcutService.java
+++ b/services/core/java/com/android/server/pm/ShortcutService.java
@@ -3121,7 +3121,8 @@
         try {
             return mIPackageManager.getPackageInfo(
                     packageName, PACKAGE_MATCH_FLAGS
-                            | (getSignatures ? PackageManager.GET_SIGNATURES : 0), userId);
+                            | (getSignatures ? PackageManager.GET_SIGNING_CERTIFICATES : 0),
+                    userId);
         } catch (RemoteException e) {
             // Shouldn't happen.
             Slog.wtf(TAG, "RemoteException", e);